CẤU TRÚC DANH SÁCH
(LIST)
Bmôn Công nghphn mm
Khoa Công nghthông tin & Truyn thông
Đi hc Cn Thơ
KHÁI NIỆM DANH SÁCH
Là tp hp hu hn các phn tcó cùng kiu
Kiu chung đưc gi là kiu phn t(element type)
Ta thưng biu din dng: a1, a2, a3, ..., an
Nu
•
n=0: danh sách rng
•
n>0: phn t đu tiên là a1, phn tcui cùng là an
Đ dài ca danh sách: sphn tca danh sách
Các phn ttrong danh sách có thttuyn tính
theo vtrí xut hin. Ta nói a
i
đng trưc a
i+1
(i=1..n-1)
PHÉP TOÁN TRÊN DANH SÁCH
MAKENULL_LIST(L): khi to danh sách
rng
EMPTY_LIST(L): kim tra danh sách rng.
FIRST(L): vtrí phn t đu tiên
END_LIST(L): vtrí sau phn tcui.
INSERT_LIST(X,P,L): xen phn tX vào v
trí P trong danh sách L.
DELETE_LIST(P,L): xóa phn t vtrí P
trong danh sách L.
PHÉP TOÁN TRÊN DANH SÁCH
PREVIOUS(P,L): vtrí ca phn t đng
trưc phn tP trong danh sách L.
NEXT(P,L): vtrí ca phn t đng sau phn
tP trong danh sách L
RETRIEVE(P,L): giá trphn t vtrí P.
LOCATE(X,L): xác đnh vtrí phn tX trong
danh sách L.
VÍ DỤ
void SORT(LIST L)
{ Position p,q; //kiu vtrí ca các phn ttrong danh sách
p= FIRST(L); //vtrí phn t đu tiên trong danh sách
while (p!=ENDLIST(L))
{ q=NEXT(p,L); //vtrí phn t đng ngay sau phn tp
while (q!=ENDLIST(L))
{ if (RETRIEVE(p,L) > RETRIEVE(q,L))
swap(p,q); // hoán đi ni dung 2 phn t
q=NEXT(q,L);
}
p=NEXT(p,L);
}
}