Cấu trúc dữ liệu (chương 4)

Chúng ta đã làm quen với cách hạn chế như ngăn xếp và hàng, trong đó việc thêm/ bớt dữ liệu chỉ thực hiện ở các đầu của danh sách. Trong chương này chúng ta tìm hiểu các danh sách thông thường..
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu (chương 4)Chöông 4 – Danh saùchChöô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öôngnaø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ãinoá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ùchcho 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ùcphaà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äutröø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 trongcaù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å ñöôïcxem 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ândanh 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 tinbaè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ùngtì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ùptruy 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áiGiaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 51Chöông 4 – Danh saùchvôù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 List::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 void List::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 bool List::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 bool List::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 int List::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öôngtöï 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ànthieát. Chuùng ta duøng moät soá nguyeân ñeå chæ vò trí (position) cuûa phaàn töû trong danhsaù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 danhsaù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àntöû trong danh saùch ñöôïc xaùc ñònh khoâng xeùt ñeán caùch hieän thöïc. Ñoái vôùi danhsaù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öû trongdanh 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 52Chöông 4 – Danh saùch ...