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
z Lưutrữ Mảng 1 chiều
z Lưutrữ Mảng 2 chiều
z Các phép toán trên cấutrúcMảng
– Danh sách tuyếntính
z Lưutrữ kế tiếp
z Lư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
z Index 1 chiều : {0, 1, 2, …, n-1}
z Index 2 chiều : {(0,0) , (0,1), (0,2), …,(0,n), (1,0), (1,1) ….}
Kiểudữ liệutrừutượng Mảng
z Cá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ó

– char word[25];
–
Tham chiếu
z Cá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

02
a
01
a
00
a
32
a
31
a
30
a
22
a
21
a
20
a
12
a
11
a
10
a
02
a
01
a
00
Từ mảng 2 chiềulưutrữ

a
32
a
22
a
12
a
02
a
31
a
21
a
11
a
01
a
30
a
20
a
10
a
00
Từ mảng 2 chiềulưutrữ
sang bộ nhớ kế tiếpsử dụng
thứ tựưutiêncột
Danh sách tuyếntính
– Danh sách là mộttậphợpcóthứ tự gồmmộtsố biến
động các phầntử cùng kiểu{a

z Các phầntử liên kếtvớinhaubằng con trỏ
– Dùng địachỉ gián tiếp
z Các phầntửđượclưutrữ trong các ô nhớởcác vị trí tùy ý
trong bộ nhớ
z Có mộtmảng địachỉ trong đóphầntử thứ i củamảng chứa
địachỉ củaphầntử thứ i trong danh sách
Lưutrữ kế tiếp đốivớidanhsách
– Danh sách lưutrữ trong mộtphầnbộ nhớ bao gồm
các ô nhớ liên tiếp
z Các phầntử liềnkề nhau đượclưutrữ trong những ô nhớ
liềnkề nhau
z Mỗiphầntử của danh sách cũng đượcgánmộtchỉ số chỉ thứ
tựđượclưutrữ trong vector
z Có mộtchỉ số last dùng để xác định chỉ số củaphầntử cuối
cùng trong danh sách
A
123 last
i
max
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 8
Lưutrữ kế tiếp đốivới danh sách
– Khai báo danh sách sử dụng lưutrữ kế tiếp trong C
#define max 100
typedef etype integer
typedef struct LIST{
etype elements[max];
int last;
} LISTTYPE
Lưutrữ kế tiếp đốivới danh sách

1. {Danh sách đã đầy} if (last > max) then ERROR;
2. {Kiểmtragiáitrị p} else if (p > last ) OR (p < 1) then ERROR;
3. else
begin {Dịch chuyểncácphầntử, tạoô trống để bổ sung}
for i = last down to p do L[i+1] = L[i];
{Lưu giá trị mớivàovị trí p} L[p] = x;
last = last+1; {Số lượng phầntử trong danh sách tăng thêm 1}
end.
End
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 10
Các thao tác trên danh sách kế tiếp
– Loạibỏ mộtphầntử trong danh sách
A
123
last
p
A
123 last
x
p
A
13 last
p
2
Các thao tác trên danh sách kế tiếp
Procedure DELETE-LIST(L, p)
Begin
{ Loạibỏ phầntửởvị trí p trong danh sách kế tiếpL.
L có tối đamax phầntử , hiệntạiphầntử cuốicùngở vị trí last}

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 12
Danh sách móc nối đơn
z Danh sách rỗng là danh sách không có chứa nút nào, lúc
đó L = NULL
z Tham chiếu đếncácthànhphầncủamột nút có địachỉ p
(trỏ bởi con trỏ p)
– INFO(p): Tham chiếuvàogiátrị
z INFO(p) = 234 ÅÆ giá trị dữ liệulưutrữ tạinúttrỏ bởi
p là 234;
– NEXT(p)
z NEXT(p) = 234 ÅÆ Ô nhớ chứaphầntử sau nút trỏ
bởip cóđịachỉ là 234
z Cấp phát một nút trống sẽđượctrỏ bởip
Câu lệnh trong giả ngôn ngữ : call New(p)
z Thu hồimộtnúttrỏ bởip
Câu lệnh trong giả ngôn ngữ: call Dispose(p)
Danh sách móc nối đơn
– Khai báo trong ngôn ngữ C
typedef <kiểudữ liệucủaphầntử> element_type;
struct node{
element_type info;
struct node * next;
} ;
typedef struct node LISTNODE;
typedef LISTNODE *LISTNODEPTR;
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 13
Các thao tác trên danh sách nối đơn
z Duyệt danh sách nối đơn:
.

Call New(Temp) ;
INFO(Temp) = X;
2. { Gắn nút mớivàovị trí cầnchèn}
NEXT(Temp) = NEXT(P);
NEXT(P) = Temp;
End
Các thao tác trên danh sách nối đơn
L
BCGH
P
X
Temp
Sau khi khởitạo nút mới và gán giá trị cho phầntử mới
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 15
Các thao tác trên danh sách nối đơn
L
BCGH
P
X
Temp
NEXT(P)
Sau khi thựchiện NEXT(Temp) = NEXT(P);
Các thao tác trên danh sách nối đơn
L
BCGH
P
X
Temp
Sau khi thựchiện NEXT(P) = Temp;

Minh họa thao tác trong NNLT C
– Khai báo danh sách
struct node{
int info;
struct node * next;
} ;
typedef struct node LISTNODE;
typedef LISTNODE *LISTNODEPTR;
void insert(LISTNODEPTR *, int );
int delete(LISTNODEPTR *, int);
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 18
void INSERT_ORDER( LISTNODEPTR *startPtr, int value){
/* Chương trình bổ sung một nút vào danh sách có sắpxếptheochiềutăng dần
của giá trị các phầntử */
LISTNODEPTR temp, current, previous ;
temp = malloc(sizeof(LISTNODE));
if (temp!= NULL) {
1. temp->info = value; temp->next = NULL;
previous = NULL; current = *startPtr;
2. while (current != NULL && value >current->info) {
previous = current; current = current->next;
}
3. if (previous = NULL) {
temp->next = *startPtr;
*startPtr = temp;
}
4. else { previous->next = temp; temp->next = current; }
}
}

prev next
info
nút
Danh sách nối kép
– Khai báo danh sách nối kép trong C
struct dlnode{
int info;
struct dlnode *next;
struct dlnode *prev;
} ;
typedef struct dlnode DLNODE;
typedef DLNODE *DLNODEPTR;
DLNODEPTR left, right;
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 20
Các thao tác trên danh sách nối kép
L
BCGH
R
X
M
L
BC GH
R
X
M
L
BCGH
R
Bổ sung mộtphầntử vào sau một nút đượctrỏ bởicon trỏ M biếttrước

L
BCGH
R
L
BCGH
R
M
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 22
Các thao tác trên danh sách nối kép
z Giảithuậtloạibỏ mộtphầntử khỏi danh sách nốikép
Procedure DELETE-DOUBLE (L, R, M)
{Loạibỏ phầntử trỏ bởiM }
1. {Danh sách rỗng}
if L= R= NULL then return;
2. {Loạibỏ}
if L= R and L = M then L:=R:= NULL;
else if M = L then begin L:= NEXT(L); PREV(L) := NULL; end;
else if M = R then begin R:= PREV(R); NEXT(R) := NULL; end;
else begin NEXT(PREV(M)) :=NEXT(M); PREV(NEXT(M)) := PREV(M);
end;
call Dispose(M);
3. return.
Biểudiễn đathứcsử dụng danh sách
– Bài toán cộng hai đathức
z Dạng tổng quát củamột đathức
z Viếtgiảithuật tìm tổng 2 đathứctrên
01
1
1

– Phầntử thứ i trong vector lưutrữ lưu thông tin về số hạng
a
i-1
x
i-1
z Phầntử thứ 1 lưutrữ thông tin a
0
z Phầntử thứ 2 lưutrữ thông tin về a
1
z …
Cách tiếpcậnsử dụng lưutrữ kế tiếp
– Ví dụ:
2-5000034-7
A[9]A[8]A[7]A[6]A[5]A[4]A[3]A[2]A[1]
65-2010-800
B[9]B[8]B[7]B[6]B[5]B[4]B[3]B[2]B[1]
24678
278
8256)(
74352)(
xxxxxxB
xxxxxA
−+−+=
−++−=
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 24
Cách tiếpcậnsử dụng lưutrữ kế tiếp
– Giảithuậtcộng hai đathứclưutrữ trên vector
Procedure ADD-POLY1(A,m, B, n, C)
Begin

14
-8
2
B
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 25
Cách tiếpcậnsử dụng lưutrữ móc nối
≠
Procedure ADD-POLY2(A, B, C)
Begin
1. p:= A; q:=B;
2. call New(C) ; d:= C; {d trỏ vào nút cuối cùng củaC}
3. while p <> NULL and q <> NULL do
case
EXP(p) = EXP(q): x := COEF(p) + COEF(q) ;
if x<>0 then call ATTACH(x, EXP(p), d) ;
p:= LINK(p) ; q:= LINK(q);
EXP(p) > EXP(q): call ATTACH(COEF(p), EXP(p),d);
p:= LINK(p);
EXP(p) < EXP(q): call ATTACH(COEF(q), EXP(q),d);
q:= LINK(q);
end case; {Còn tiếp}
Cách tiếpcậnsử dụng lưutrữ móc nối
≠
4. {Trường hợpA kết thúc trước, A ngắnhơn}
while q <> NULL do begin
call ATTACH(COEF(q), EXP(q),d); q:= LINK(q);
end ;
5. {Trường hợpB kết thúc trước}
while p <> NULL do begin