Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 1
CấutrúcdữliệuvàGiảithuật
Chương III: Mảng và Danh sách
Mảng và Danh sách
Nội dung
–CấutrúcdữliệuMảng
zLưutrữMảng 1 chiều
zLưutrữMảng 2 chiều
zCác phép toán trên cấutrúcMảng
–Danh sách tuyếntính
zLưutrữkếtiếp
zLưutrữmóc nối
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 2
Kiểudữliệutrừutượng Mảng
zĐốitượng củaMảng:
–Mộttậpcáccặp (index, item)
–Vớimỗigiátrịcủa index sẽcó mộtgiátrịtương ứng
củaitem.
–Index là mộttậpcóthứtựcó mộtchiềuhoặc nhiều
chiều
zIndex 1 chiều : {0, 1, 2, …, n-1}
zIndex 2 chiều : {(0,0) , (0,1), (0,2), …,(0,n), (1,0), (1,1) ….}
Kiểudữliệutrừutượng Mảng
zCác phép toán
–Create(j, list) : tạomảng có j chiều, list là mộtj-bộvới
phầntửthứk của list là kích thướcchiềuthứk của
mảng.
–Retrieve(A,i) : Trảra giá trịcủaphầntửnhậnchỉsối
nếucó
–Store(A,i,x) : Trảra mộtmảng giống nhưmảng A đã
cho ban đầu, chỉkhác là mộtcặp(i,x) đãđượcbổ
sung vào vịtrí đúng
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 3
CấutrúcdữliệuMảng
zMảng là dãy các phầntửđượcđánh chỉsố
zKhi cài đặt trong máy tính, mảng đượclưutrữ
trong một dãy các ô nhớliên tiếp trong bộnhớ
zKích thướccủamảng đượcxácđịnh khi khởitạo
và không thay đổi
zMỗiphầntửtrong mảng có mộtchỉsốxác định
zTruy xuấtvàocácphầntửcủamảng sửdụng chỉ
sốcủaphầntử
Mảng trong các ngôn ngữlậptrình
–Tậpchỉsốcủamảng có thểkhác nhau
zC, Java : chỉsốlà sốnguyên, liên tục, bắtđầutừ0
zPascal : chỉsốcó thểcó giá trịrờirạc
zPerl: cho phép chỉsốkhông phảilàsố
–Mảng có thểlà thuầnnhấthoặc không thuầnnhất
–Mảng có thểcó thêm các thông tin bổsung ngoài các
phầntử
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 4
Mảng 1 chiều
–Khởitạo
zCầnchỉra sốphầntửcủamảng
zKhai báo mảng trong C:
<kiểudữliệucủaphầntử><tên biến>[size]
–int list[5];
–char word[25];
–Tham chiếu
zCác phầntửtrong mảng 1 chiềuđược tham chiếuđếnsử
dụng địachỉđượctính
–int list [5] Ælist[0] địachỉcơsở= α
list[1] α+ sizeof(int)
list[2] α+ 2*sizeof(int)
list[3] α+ 3*sizeof(int)
list[4] α+ 4*sizeof(int)
Mảng 1 chiều
Address Value
1228 0
1230 1
1232 2
1234 3
1236 4
int list[] = {0, 1, 2, 3, 4};
int *ptr; int rows = 5;
int i; ptr = list;
printf(“Address Value\n”);
for (i=0; i < rows; i++)
printf(“%8u%5d\n”, ptr+i, *(ptr+i));
printf(“\n”);
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 5
Mảng 2 chiều
–Khai báo
zCầnchỉra sốhàng, sốcột
zTrong C : <kiểuphầntử> <tên biến> [size1] [size2]
–int table[4][5];
zTruy xuấtmộtphầntử
–table[i][j]
–Lưutrữmảng 2 chiều trong bộnhớmáy tính
zTheo thứtựưu tiên hàng
zTheo thứtựưutiêncột
Mảng 2 chiều
–Lưutrữmảng 2 chiều theo thứtựưutiênhàng
a32
a31
a30
a22
a21
a20
a12
a11
a10
a02
a01
a00
a32
a31
a30
a22
a21
a20
a12
a11
a10
a02
a01
a00
Từmảng 2 chiềulưutrữ
sang bộnhớkếtiếpsửdụng
thứtựưu tiên hàng