Chương 4: Danh sách - Cấu trúc dữ liệu và giải thuật | Trường Đại học CNTT Thành Phố Hồ Chí Minh

Chöông 4 – Danh saùch
Chöông 4 – DANH SAÙCH
Chuùng ta ñaõ laøm quen vôùi caùc danh saùch haïn cheá nhö ngaên xeáp vaø haøng, trong
ñoù vieäc theâm/ bôùt döõ lieäu chæ thöïc hieän ôû caùc ñaàu cuûa danh saùch. Trong chöông
naøy chuùng ta tìm hieåu caùc danh saùch thoâng thöôøng hôn maø trong ñoù vieäc theâm,
loaïi hoaëc truy xuaát phaàn töû coù theå thöïc hieän taïi baát kyø vò trí naøo trong danh saùch.
Ñònh nghóa danh saùch
Chuùng ta baét ñaàu baèng vieäc ñònh nghóa kieåu caáu truùc döõ lieäu tröøu töôïng goïi laø
danh saùch (list). Cuõng gioáng nhö ngaên xeáp vaø haøng, danh saùch bao goàm moät chuoãi
noái tieáp caùc phaàn töû döõ lieäu. Tuy nhieân, khaùc vôùi ngaên xeáp vaø haøng, danh saùch
cho pheùp thao taùc treân moïi phaàn töû.
Ñònh nghóa: Danh saùch caùc phaàn töû kieåu T laø moät chuoãi noái tieáp höõu haïn caùc
phaàn töû kieåu T cuøng caùc taùc vuï sau:
1. Taïo moät danh saùch roãng.
2. Xaùc ñònh danh saùch coù roãng hay khoâng.
3. Xaùc ñònh danh saùch coù ñaày hay chöa.
4. Tìm soá phaàn töû cuûa danh saùch. 5. Laøm roãng danh saùch.
6. Theâm phaàn töû vaøo moät vò trí naøo ñoù cuûa danh saùch.
7. Loaïi phaàn töû taïi moät vò trí naøo ñoù cuûa danh saùch.
8. Truy xuaát phaàn töû taïi moät vò trí naøo ñoù cuûa danh saùch.
9. Thay theá phaàn töû taïi moät vò trí naøo ñoù cuûa danh saùch.
10. Duyeät danh saùch, thöïc hieän moät coâng vieäc cho tröôùc treân moãi phaàn töû.
Ngoaøi ra coøn moät soá taùc vuï khaùc coù theå aùp leân moät chuoãi noái tieáp caùc phaàn töû.
Chuùng ta coù theå xaây döïng raát nhieàu daïng khaùc nhau cho caùc kieåu caáu truùc döõ lieäu
tröøu töôïng töông töï baèng caùch söû duïng caùc goùi taùc vuï khaùc nhau. Baát kyø moät trong
caùc daïng naøy ñeàu coù theå ñöôïc ñònh nghóa cho teân goïi CTDL danh saùch. Tuy nhieân,
chuùng ta chæ taäp trung vaøo moät danh saùch cuï theå maø caùc taùc vuï cuûa noù coù theå ñöôïc
xem nhö moät khuoân maãu ñeå minh hoïa yù töôûng vaø caùc vaán ñeà caàn giaûi quyeát treân danh saùch.
Ñaëc taû caùc phöông thöùc cho danh saùch
Khi baét ñaàu tìm hieåu ngaên xeáp, chuùng ta nhaán maïnh vieäc che daáu thoâng tin
baèng caùch phaân bieät giöõa vieäc söû duïng ngaên xeáp vaø vieäc laäp trình cho caùc taùc vuï
treân ngaên xeáp. Ñoái vôùi haøng, chuùng ta tieáp tuïc yù töôûng naøy vaø ñaõ nhanh choùng
tìm ñöôïc raát nhieàu caùch hieän thöïc coù theå coù. Caùc danh saùch thoâng duïng cho pheùp
truy xuaát vaø thay ñoåi baát kyø phaàn töû naøo. Do ñoù nguyeân taéc che daáu thoâng tin ñoái
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
Chöông 4 – Danh saùch
vôùi danh saùch caøng quan troïng hôn nhieàu so vôùi ngaên xeáp vaø haøng. Chuùng ta haõy
ñaëc taû cho caùc taùc vuï treân danh saùch:
Constructor caàn coù tröôùc khi danh saùch ñöôïc söû duïng:
ñoái töôïng danh saùch roãng ñaõ ñöôïc taïo.
Taùc vuï thöïc hieän treân moät danh saùch ñaõ coù vaø laøm roãng danh saùch:
Moïi phaàn töû cuûa danh saùch ñaõ ñöôïc giaûi phoùng, danh saùch trôû neân roãng.
Caùc taùc vuï xaùc ñònh traïng thaùi cuûa danh saùch:
traû veà true neáu danh saùch roãng, ngöôïc laïi traû veà false. Danh saùch khoâng ñoåi.
traû veà true neáu danh saùch ñaày, ngöôïc laïi traû veà false. Danh saùch khoâng ñoåi.
traû veà soá phaàn töû cuûa danh saùch. Danh saùch khoâng ñoåi.
Chuùng ta xem xeùt tieáp caùc taùc vuï truy xuaát caùc phaàn töû cuûa danh saùch. Töông
töï nhö ñoái vôùi ngaên xeáp vaø haøng, caùc taùc vuï naøy seõ traû veà khi caàn thieát.
Chuùng ta duøng moät soá nguyeân ñeå chæ vò trí (
) cuûa phaàn töû trong danh
saùch. Vò trí ôû ñaây ñöôïc hieåu laø thöù töï cuûa phaàn töû trong danh saùch. Caùc vò trí
trong danh saùch ñöôïc ñaùnh soá 0, 1, 2, ...Vieäc xaùc ñònh moät phaàn töû trong danh
saùch thoâng qua vò trí raát gioáng vôùi söï söû duïng chæ soá trong daõy, tuy nhieân vaãn coù
moät soá ñieåm khaùc nhau quan troïng. Neáu chuùng ta theâm moät phaàn töû vaøo moät vò
trí naøo ñoù trong danh saùch thì vò trí cuûa taát caû caùc phaàn töû phía sau seõ taêng leân 1.
Neáu loaïi moät phaàn töû thì vò trí caùc phaàn töû phía sau giaûm 1. Vò trí cuûa caùc phaàn
töû trong danh saùch ñöôïc xaùc ñònh khoâng xeùt ñeán caùch hieän thöïc. Ñoái vôùi danh
saùch lieân tuïc, hieän thöïc baèng daõy, vò trí phaàn töû roõ raøng laø chæ soá cuûa phaàn töû
trong daõy. Nhöng chuùng ta cuõng vaãn thoâng qua vò trí ñeå tìm caùc phaàn töû trong
danh saùch lieân keát duø raèng danh saùch lieân keát khoâng coù chæ soá.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
Chöông 4 – Danh saùch
Chuùng ta seõ ñaëc taû chính xaùc caùc phöông thöùc lieân quan ñeán chæ moät phaàn töû
cuûa danh saùch döôùi ñaây.
Neáu danh saùch chöa ñaày vaø ≤ ≤
laø soá phaàn töû hieän coù cuûa danh saùch, phöông thöùc traû veà : moïi phaàn töû töø
ñeán cuoái danh saùch seõ coù vò trí
taêng leân 1, x ñöôïc theâm vaøo taïi
; ngöôïc laïi, danh saùch khoâng ñoåi, seõ
cho bieát loãi cuï theå. Phöông thöùc chaáp nhaän
baèng vì noù chaáp nhaän theâm phaàn
töû môùi ngay sau phaàn töû cuoái. Tuy nhieân, caùc phöông thöùc sau chæ chaáp nhaän
, vì chuùng chæ thöïc hieän treân nhöõng phaàn töû ñaõ coù saün. : Neáu ≤
laø soá phaàn töû hieän coù cuûa danh saùch, phöông thöùc traû veà : phaàn töû taïi
ñöôïc loaïi khoûi danh saùch, trò cuûa noù ñöôïc cheùp vaøo x, caùc
phaàn töû phía sau giaûm vò trí bôùt 1; ngöôïc laïi, danh saùch khoâng ñoåi, seõ cho bieát loãi cuï theå. Neáu 0 ≤
laø soá phaàn töû hieän coù cuûa danh saùch, phöông thöùc traû veà phaàn töû taïi
ñöôïc cheùp vaøo x, danh saùch khoâng ñoåi; ngöôïc laïi,
seõ cho bieát loãi cuï theå. Caû hai tröôøng hôïp danh saùch ñeàu khoâng ñoåi. Neáu 0 ≤
laø soá phaàn töû hieän coù cuûa danh saùch, phöông thöùc traû veà phaàn töû taïi
ñöôïc thay theá bôûi x; ngöôïc laïi, danh saùch khoâng ñoåi,
seõ cho bieát loãi cuï theå.
Phöông thöùc duyeät danh saùch ñeå thöïc hieän moät nhieäm vuï naøo ñoù cho töøng
phaàn töû cuûa danh saùch thöôøng toû ra coù lôïi, ñaëc bieät cho muïc ñích kieåm tra. Ngöôøi
söû duïng goïi phöông thöùc naøy khi muoán thöïc hieän moät coâng vieäc gì ñoù treân töøng
phaàn töû cuûa danh saùch. Chaúng haïn, ngöôøi söû duïng coù hai haøm vaø vaø moät ñoái töôïng cuûa lôùp
, coù theå söû duïng leänh hoaëc
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
Chöông 4 – Danh saùch
ñeå thöïc hieän moät trong hai haøm treân leân moãi phaàn töû cuûa danh saùch. Neáu ngöôøi
söû duïng muoán in moïi phaàn töû cuûa danh saùch thì goïi nhö sau: vôùi
laø moät haøm duøng ñeå in moät phaàn töû cuûa danh saùch. Khi goïi phöông thöùc
, ngöôøi söû duïng gôûi teân cuûa haøm laøm thoâng soá.
Trong C++, teân cuûa haøm maø khoâng coù caëp daáu ngoaëc chính laø con troû chæ ñeán haøm. Thoâng soá hình thöùc
döôùi ñaây cuûa phöông thöùc
caàn ñöôïc khai baùo nhö moät con troû chæ ñeán haøm.
Ngoaøi ra, khai baùo con troû haøm laøm thoâng soá phaûi coù kieåu traû veà laø
vaø coù thoâng soá tham chieáu ñeán .
Coâng vieäc ñaëc taû bôûi haøm
ñöôïc thöïc hieän laàn löôït treân töøng phaàn töû cuûa danh saùch,
baét ñaàu töø phaàn töû thöù 0.
Cuõng gioáng nhö moïi thoâng soá khaùc,
chæ laø teân hình thöùc vaø chæ ñöôïc
gaùn bôûi moät con troû thöïc söï khi
baét ñaàu thöïc thi. Bieåu dieãn
thay maët cho haøm seõ ñöôïc söû duïng ñeå xöû lyù cho töøng phaàn töû cuûa danh saùch khi thöïc thi.
Trong phaàn keá tieáp chuùng ta seõ hieän thöïc caùc phöông thöùc naøy.
Hieän thöïc danh saùch
Chuùng ta ñaõ ñaëc taû ñaày ñuû caùc taùc vuï mong muoán ñoái vôùi danh saùch. Phaàn naøy
seõ hieän thöïc chi tieát chuùng trong C++. Ngaên xeáp vaø haøng ñaõ ñöôïc hieän thöïc caû
hai daïng lieân tuïc vaø lieân keát. Chuùng ta cuõng seõ laøm töông töï cho danh saùch.
Hieän thöïc danh saùch lieân tuïc
Trong hieän thöïc danh saùch lieân tuïc (contiguous list), caùc phaàn töû cuûa danh saùch coù kieåu laø
ñöôïc chöùa trong daõy kích thöôùc laø . Cuõng gioáng
nhö hieän thöïc ngaên xeáp lieân tuïc, ôû ñaây chuùng ta caàn moät bieán ñeám soá phaàn
töû hieän coù trong danh saùch. Sau ñaây laø ñònh nghóa lôùp
coù hai thuoäc tính
thaønh phaàn vaø taát caû caùc phöông thöùc maø chuùng ta ñaõ ñaëc taû.
Caùc phöông thöùc cuûa kieåu döõ lieäu tröøu töôïng danh saùch
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
Chöông 4 – Danh saùch
Caùc thuoäc tính cho hieän thöïc danh saùch lieân tuïc
Haàu heát caùc phöông thöùc ( ) raát deã hieän thöïc.
: traû veà soá phaàn töû cuûa danh saùch. Danh saùch khoâng ñoåi.
Chuùng ta daønh caùc phöông thöùc ñôn giaûn khaùc laïi cho phaàn baøi taäp. ÔÛ ñaây
chuùng ta seõ taäp trung vaøo caùc phöông thöùc truy xuaát döõ lieäu. Khi theâm moät phaàn
töû môùi, caùc phaàn töû trong daõy phaûi ñöôïc di chuyeån ñeå nhöôøng choã.
Neáu danh saùch chöa ñaày vaø 0 ≤ ≤
laø soá phaàn töû hieän coù cuûa danh saùch, phöông thöùc traû veà : moïi phaàn töû töø
ñeán cuoái danh saùch seõ coù vò trí
taêng leân 1, x ñöôïc theâm vaøo taïi
; ngöôïc laïi, danh saùch khoâng ñoåi, seõ cho bieát loãi cuï theå.
Coù bao nhieâu coâng vieäc maø haøm treân caàn phaûi laøm? Neáu phaàn töû môùi ñöôïc
theâm vaøo cuoái danh saùch thì haøm chæ phaûi thöïc hieän moät soá khoâng ñoåi caùc leänh.
Trong tröôøng hôïp ngöôïc laïi, neáu phaàn töû ñöôïc theâm vaøo ñaàu danh saùch, haøm seõ
phaûi dòch chuyeån moät soá phaàn töû lôùn nhaát ñeå taïo choã troáng, neáu danh saùch ñaõ
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
Chöông 4 – Danh saùch
khaù daøi thì coâng vieäc caàn laøm raát nhieàu. Xeùt bình quaân, neáu chuùng ta giaû söû moïi
vò trí trong danh saùch ñeàu coù khaû naêng theâm phaàn töû môùi nhö nhau, haøm treân seõ
phaûi dòch chuyeån moät nöûa soá phaàn töû trong danh saùch. Chuùng ta noùi raèng soá vieäc
caàn laøm trong haøm tæ leä vôùi chieàu daøi n cuûa danh saùch.
Töông töï, vieäc loaïi phaàn töû trong danh saùch cuõng caàn phaûi dòch chuyeån caùc
phaàn töû ñeå laáp choã troáng vaø vieäc loaïi naøy cuõng toán thôøi gian tæ leä vôùi chieàu daøi n cuûa danh saùch.
Khaùc vôùi hai tröôøng hôïp treân, haàu heát caùc phöông thöùc coøn laïi khoâng caàn thöïc
hieän voøng laëp naøo vaø thôøi gian thöïc hieän laø haèng soá. Toùm laïi,
Trong xöû lyù danh saùch lieân tuïc coù n phaàn töû: • vaø
caàn thôøi gian tæ leä vôùi n. • vaø thöïc hieän
trong thôøi gian khoâng ñoåi.
Chuùng ta chöa keå ra ñaây phöông thöùc
vì thôøi gian thöïc hieän coøn
phuï thuoäc vaøo thoâng soá haøm visit. Rieâng
thì ít nhaát cuõng caàn thôøi gian
tæ leä vôùi n do phaûi coù voøng laëp ñeå duyeät qua heát caùc phaàn töû cuûa danh saùch. Tuy
nhieân, vôùi cuøng moät haøm thì
caàn thôøi gian tæ leä vôùi n.
Coâng vieäc ñaëc taû bôûi haøm
ñöôïc thöïc hieän laàn löôït treân töøng phaàn töû cuûa danh saùch,
baét ñaàu töø phaàn töû thöù 0.
Hieän thöïc danh saùch lieân keát ñôn giaûn Caùc khai baùo
Ñeå hieän thöïc danh saùch lieân keát (linked list), chuùng ta baét ñaàu vôùi khai baùo
döôùi ñaây cuõng töông töï nhö trong ngaên xeáp lieân keát vaø haøng lieân keát. aùc thuoäc tính
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
Chöông 4 – Danh saùch
Caùc phöông thöùc cuûa danh saùch lieân keát (cuõng gioáng nhö cuûa danh saùch lieân tuïc)
Caùc phöông thöùc baûo ñaûm tính an toaøn cho CTDL coù chöùa thuoäc tính con troû.
Caùc thuoäc tính cho hieän thöïc lieân keát cuûa danh saùch
Con troû chæ phaàn töû ñaàu cuûa danh saùch.
Trong ñònh nghóa treân chuùng ta khoâng lieät keâ laïi caùc phöông thöùc cuûa danh
saùch lieân keát vì chuùng cuõng töông töï nhö ñoái vôùi danh saùch lieân tuïc. Trong phaàn
chuùng ta coù boå sung phöông thöùc
maø chuùng ta seõ thaáy
ích lôïi cuûa noù trong khi hieän thöïc caùc phöông thöùc khaùc. Ví duï
Hình 4.1 minh hoïa vieäc theâm bôùt döõ lieäu trong danh saùch qua moät ví duï söûa
ñoåi vaên baûn. Moãi phaàn töû trong danh saùch chöùa moät töø vaø moät tham chieáu ñeán
phaàn töû keá. Hình a laø danh saùch chöùa caâu ban ñaàu laø “Stacks are lists” . Neáu
chuùng ta theâm töø “simple” tröôùc töø “lists” chuùng ta coù danh saùch nhö hình b. Tieáp
theo chuùng ta quyeát ñònh thay theá töø “lists” bôûi töø “structures” vaø theâm ba töø “but
important data” thì coù hình c. Cuoái cuøng chuùng ta laïi quyeát ñònh boû ñi caùc töø
“simple but” ñeå coù ñöôïc caâu cuoái cuøng “Stacks are important data structures”.
Tìm ñeán moät vò trí trong danh saùch
Chuùng ta thieát keá moät haøm
ñeå ñöôïc goïi trong moät vaøi phöông
thöùc. Haøm naøy nhaän thoâng soá laø
(moät soá nguyeân chæ vò trí phaàn töû
trong danh saùch) vaø traû veà con troû tham chieáu ñeán phaàn töû töông öùng trong danh saùch.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
Chöông 4 – Danh saùch
Hình 4.1- Caùc thao taùc treân danh saùch lieân keát.
Neáu ngöôøi söû duïng nhìn thaáy ñöôïc
thì hoï seõ coù theå truy xuaát
ñeán moïi phaàn töû trong danh saùch. Vì vaäy, ñeå duy trì tính ñoùng kín cuûa döõ lieäu,
chuùng ta seõ khoâng cho pheùp ngöôøi söû duïng nhìn thaáy haøm . Baèng caùch khai baùo
chuùng ta baûo ñaûm raèng haøm naøy chæ ñöôïc goïi trong caùc
phöông thöùc khaùc cuûa danh saùch.
Caùch deã nhaát ñeå xaây döïng haøm
laø baét ñaàu duyeät töø ñaàu cuûa
danh saùch cho ñeán phaàn töû maø chuùng ta muoán tìm.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
Chöông 4 – Danh saùch phaûi hôïp leä
traû veà ñòa chæ cuûa phaàn töû taïi .
Do chuùng ta naém ñöôïc chính xaùc caùc phöông thöùc naøo caàn goïi ñeán
, trong haøm naøy chuùng ta khoâng caàn kieåm tra loãi. Thay vaøo ñoù
chuùng ta baûo ñaûm baèng
cho noù. Coù nghóa laø caùc phöông thöùc tröôùc khi goïi
seõ kieåm tra tröôùc vaø chæ goïi khi ñieàu kieän hôïp leä. Vieäc
kieåm tra seõ khoâng phaûi laëp laïi trong haøm naøy, chöông trình seõ hieäu quaû hôn.
Neáu moïi phaàn töû ñöôïc truy xuaát vôùi xaùc suaát ngang nhau thì trung bình haøm
seõ phaûi duyeät qua moät nöûa soá phaàn töû trong danh saùch ñeå ñeán
ñöôïc vò trí caàn thieát. Thôøi gian naøy tæ leä vôùi chieàu daøi n cuûa danh saùch.
Theâm phaàn töû vaøo danh saùch
Tieáp theo chuùng ta seõ xem xeùt vaán ñeà theâm moät phaàn töû môùi vaøo danh saùch.
Neáu chuùng ta coù moät phaàn töû môùi vaø chuùng ta muoán cheøn phaàn töû naøy vaøo moät vò
trí naøo ñoù trong danh saùch, ngoaïi tröø vò trí ñaàu danh saùch, nhö hình 4.2, chuùng ta caàn coù hai con troû vaø
chæ ñeán hai phaàn töû tröôùc vaø sau vò
trí caàn cheøn. Neáu con troû
ñang chæ phaàn töû môùi caàn cheøn thì caùc leänh
gaùn sau seõ cheøn ñöôïc phaàn töû môùi vaøo danh saùch: Trong phöông thöùc döôùi ñaây pheùp gaùn
ñöôïc thöïc hieän thoâng qua constructor coù nhaän thoâng soá thöù hai laø .
Vieäc theâm phaàn töû vaøo ñaàu danh saùch caàn ñöôïc xöû lyù rieâng, do tröôøng hôïp naøy
khoâng coù phaàn töû naøo naèm tröôùc phaàn töû môùi neân chuùng ta khoâng söû duïng con troû
, thay vaøo ñoù thuoäc tính
chæ ñeán phaàn töû ñaàu cuûa danh saùch phaûi ñöôïc gaùn laïi.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
Chöông 4 – Danh saùch
Hình 4.2- Theâm phaàn töû vaøo danh saùch lieân keát.
Neáu danh saùch chöa ñaày vaø 0 ≤ ≤
laø soá phaàn töû hieän coù cuûa danh saùch, phöông thöùc traû veà : moïi phaàn töû töø
ñeán cuoái danh saùch seõ coù vò trí taêng
leân 1, x ñöôïc theâm vaøo taïi
; ngöôïc laïi, danh saùch khoâng ñoåi, seõ cho bieát loãi cuï theå.
// Tröôøng hôïp ñaëc bieät: phaàn töû môùi theâm vaøo ñaàu danh saùch.
// Tröôøng hôïp toång quaùt.
// Tìm phaàn töû phía tröôùc vò trí caàn theâm phaàn töû môùi.
// Tröôøng hôïp ñaëc bieät: phaàn töû môùi theâm vaøo ñaàu danh saùch.
// Tröôøng hôïp toång quaùt.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät