Lecturer: PhD. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Cấu trúc dữ liệu và giải thuật
Bài 2. MẢNG
@Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
1
Bài 2. Mảng
Nội dung:
1. Khái niệm về mảng.
2. Biểu diễn mảng 1 chiều (1D).
3. Biểu diễn mảng 2 chiều (2D).
4. Các phép toán trên mảng 1D.
5. Các phép toán trên mảng 2D.
Tham khảo:
Deshpande Kakde –C and data structures
Chapter 18 –Arrays, Searching, and Sorting
Chapter 23 –Problem in Arrays, Searching, Sorting, and Hashing
@Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
2
2.1. Khái niệm về mảng (1/2)
Mảng là cấu trúc dữ liệu do người dùng định nghĩa,
có kích thước cố định và đồng nhất.
Theo tính chất đồng nhất, các thành phần có cùng kiểu, được
gọi là element type hoặc base type.
Theo tính chất có kích thước cố định, ta không thể thay đổi
kích thước của mảng khi đang sử dụng.
Mảng có thể coi là cấu trúc dữ liệu cho phép truy cập
ngẫu nhiên thông qua chỉ số của chúng.
@Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
3
2.1. Khái niệm về mảng (2/2)
Các thành phần của mảng được truy cập thông qua chỉ số,
chỉ số là số nguyên để chỉ vị trí của thành phần đó trong
mảng.
Như vậy, một mảng được hình thành bởi một cặp (value,
index);
Nếu chỉ số là 1 số, mảng được gọi là mảng 1 chiều. Nếu
chỉ số có dạng {i1, i2, i3,….., in}, mảng được gọi là mảng n
chiều.
@Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
4
2.2. Biểu diễn mảng 1 chiều (1D) (1/3)
•Mảng được thể hiện trong bộ nhớ bằng ánh xạ tuần
tự.
•Đặc tính cơ bản của ánh xạ tuần tự cho mỗi phần tử của
mảng có “khoảng cách” cố định với phần tử đầu của mảng.
•Như vậy, nếu phần tử thứ iánh xạ tới vị trí athì phần tử
thứ (i+1) ánh xạ tới vị trí (a+1).
@Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University
5