Tài liệu CTDL 2005 chuong 4 docx

Chöông 4 – Danh saùch

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 51

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.

4.1. Ñò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.

4.2. Ñ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

Chöông 4 – Danh saùch

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 52

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:

template <class Entry>

List<Entry>::List();

post: ñ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:

template <class Entry>

void List<Entry>::clear();

post: 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:

template <class Entry>

bool List<Entry>::empty() const;

post: traû veà true neáu danh saùch roãng, ngöôïc laïi traû veà false. Danh saùch khoâng ñoåi.

template <class Entry>

bool List<Entry>::full() const;

post: traû veà true neáu danh saùch ñaày, ngöôïc laïi traû veà false. Danh saùch khoâng ñoåi.

template <class Entry>

int List<Entry>::size() const;

post: 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à ErrorCode khi caàn

thieát.

Chuùng ta duøng moät soá nguyeân ñeå chæ vò trí (position) 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á.