Kiu d liu danh sách
Lê S Vinh
B môn Khoa Hc Máy Tính – Khoa CNTT
ð$i Hc Công Ngh & ðHQGHN
Email: vinhioi@yahoo.com
Danh sách
Danh sách là gì?
Danh sách là c+u trúc d liu tuy/n tính, trong ñó các ph4n t5 d liu ñư7c
s8p x/p theo mt th; t< xác ñ=nh
Ví d>:
Danh sách sinh viên
Danh sách ñin tho$i
Danh sách môn hc
Danh sách bài hát
Danh sách công vic
Danh sách
Tru tưng hóa cu trúc danh sách
1. Mô t d liu
A= (a0, a1, …, an)
trong ñó ailà ph4n t5 th; i cEa danh sách A
Ví d>:
A
= (1, 2, 3, 3, 4, 5)
A
= (1, 2, 3, 3, 4, 5)
A= (‘Vinh’, ‘Tu+n’,. ‘Ánh’)
2. Mô t các phép toán trên c#u trúc danh sách
empty (A): Kim tra danh sách có rOng hay không
length (A): Cho bi/t sQ ph4n t5 cEa danh sách
element (A, i) : TrR ph4n t5 S v= trí th; icEa A.
Ví d>: A=(1,3,5)
Element (A, 0) → 1
Element (A, 2) → 5
Danh sách
insert (A, i, x): Thêm ph4n t5 xvào danh sách At$i v= trí i.
A = (a0, a1,…, an) → A = (a0,a1,…,ai,1, x, ai,…an)
Ví d>: A = (1,3,5)
insert (A, 1, 4) → A = (1, 4, 3, 5)
append (A, x): Thêm xvào ñuôi danh sách A
A = (a
, a
,…, a
) → A = (a
,a
,…,a
A = (a
0
, a
1
,…, a
n
) → A = (a
0
,a
1
,…,a
n
Ví d>: A= (1,3,5)
append (A, 8) → A = (1, 3, 5, 8)
delete (A, i): Lo$i ph4n t5 S v= trí th; itrong danh sách A
A = (a0, a1,…ai,1, ai, ai+1, an) → A = (a0,a1,…,ai,1, ai+1,…an)
Ví d>: A = (1,3,5)
delete (A, 1) → A = (1, 5)
Cài ñXt danh sách bYng mRng
Mng (array)
TZp h7p các ph4n t5 (các bi/n) có cùng mt kiu
Mt ph4n t5 c> th trong mRng s\ ñư7c xác ñ=nh và truy cZp bSi mt ch. s/
Trong C/C++, các ph4n t5 cEa m$ng ñư7c ñXt c$nh nhau t$o thành mt
khQi liên t>c. ð=a ch_ th+p nh+t tương ;ng vai ph4n t5 ñ4u tiên, ñ=a ch_ cao
nh+t tương ;ng vai ph4n t5 cuQi cùng
MRng thì có th là mt chicu hoXc nhicu chicu