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

Chúng ta có tìm hiểu một CTDL đơn giản nhất, đó là ngăn xếp, một cách nhất quán như phần giới thiệu môn học đã trình bày, mỗi CTDL đều được xây dựng theo đúng trình tự
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu ( chương 2) Chöông 2 – Ngaên xeáp Phaàn 2 – CAÙC CAÁU TRUÙC DÖÕ LIEÄU Chöông 2 – NGAÊN XEÁP Chuùng ta seõ tìm hieåu moät CTDL ñôn giaûn nhaát, ñoù laø ngaên xeáp. Moät caùch nhaát quaùn nhö phaàn giôùi thieäu moân hoïc ñaõ trình baøy, moãi CTDL ñeàu ñöôïc xaây döïng theo ñuùng trình töï: • Ñònh nghóa. • Ñaëc taû. • Phaân tích caùc phöông aùn hieän thöïc. • Hieän thöïc. 2.1. Ñònh nghóa ngaên xeáp Vôùi ñònh nghóa danh saùch trong chöông môû ñaàu, chuùng ta hieåu raèng trong danh saùch, moãi phaàn töû, ngoaïi tröø phaàn töû cuoái, ñeàu coù duy nhaát moät phaàn töû ñöùng sau noù. Ngaên xeáp laø moät tröôøng hôïp cuûa danh saùch, ñöôïc söû duïng trong caùc öùng duïng coù lieân quan ñeán söï ñaûo ngöôïc. Trong CTDL ngaên xeáp, vieäc theâm hay laáy döõ lieäu chæ ñöôïc thöïc hieän taïi moät ñaàu. Döõ lieäu theâm vaøo tröôùc seõ laáy ra sau, tính chaát naøy coøn ñöôïc goïi laø vaøo tröôùc ra sau (First In Last Out - FILO). Ñaàu theâm hay laáy döõ lieäu cuûa ngaên xeáp coøn goïi laø ñænh (top) cuûa ngaên xeáp. Hình 2.1- Theâm phaàn töû vaøo vaø laáy phaàn töû ra khoûi ngaên xeáp. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 17 Chöông 2 – Ngaên xeáp Vaäy chuùng ta coù ñònh nghóa cuûa ngaên xeáp döôùi ñaây, khoâng khaùc gì ñoái vôùi ñònh nghóa danh saùch, ngoaïi tröø caùch thöùc maø ngaên xeáp cho pheùp thay ñoåi hoaëc truy xuaát ñeán caùc phaàn töû cuûa noù. Ñònh nghóa: Moät ngaên xeáp caùc phaàn töû kieåu T laø moät chuoãi noái tieáp caùc phaàn töû cuûa T, keøm caùc taùc vuï sau: 1. Taïo moät ñoái töôïng ngaên xeáp roãng. 2. Ñaåy (push) moät phaàn töû môùi vaøo ngaên xeáp, giaû söû ngaên xeáp chöa ñaày (phaàn töû döõ lieäu môùi luoân ñöôïc theâm taïi ñænh). 3. Laáy (pop) moät phaàn töû ra khoûi ngaên xeáp, giaû söû ngaên xeáp chöa roãng (phaàn töû bò loaïi laø phaàn töû ñang naèm taïi ñænh). 4. Xem phaàn töû taïi ñænh ngaên xeáp (top). Löu yù raèng ñònh nghóa naøy khoâng quan taâm ñeán caùch hieän thöïc cuûa kieåu döõ lieäu tröøu töôïng ngaên xeáp. Chuùng ta seõ tìm hieåu moät vaøi caùch hieän thöïc khaùc nhau cuûa ngaên xeáp vaø taát caû chuùng ñeàu phuø hôïp vôùi ñònh nghóa naøy. 2.2. Ñaëc taû ngaên xeáp Ngoaøi caùc taùc vuï chính treân, caùc phöông thöùc khaùc coù theå boå sung tuyø vaøo nhu caàu maø chuùng ta thaáy caàn thieát: + empty: cho bieát ngaên xeáp coù roãng hay khoâng. + full: cho bieát ngaên xeáp coù ñaày hay chöa. + clear: xoùa saïch taát caû döõ lieäu vaø laøm cho ngaên xeáp trôû neân roãng. Chuùng ta löu yù raèng, khi thieát keá caùc phöông thöùc cho moãi lôùp CTDL, ngoaøi moät soá phöông thöùc chính ñeå theâm vaøo hay laáy döõ lieäu ra, chuùng ta coù theå boå sung theâm nhieàu phöông thöùc khaùc. Vieäc theâm döïa vaøo quan nieäm cuûa moãi ngöôøi veà söï tieän duïng cuûa lôùp CTDL ñoù. Nhöng ñieàu ñaëc bieät quan troïng ôû ñaây laø caùc phöông thöùc ñoù khoâng theå maâu thuaãn vôùi ñònh nghóa ban ñaàu cuõng nhö caùc chöùc naêng maø chuùng ta ñaõ ñònh ra cho lôùp. Chaúng haïn, trong tröôøng hôïp ngaên xeáp cuûa chuùng ta, ñeå baûo ñaûm quy luaät “Vaøo tröôùc ra sau” thì traät töï cuûa caùc phaàn töû trong ngaên xeáp laø raát quan troïng. Chuùng ta khoâng theå cho chuùng moät phöông thöùc coù theå thay ñoåi traät töï cuûa caùc phaàn töû ñang coù, hoaëc phöông thöùc laáy moät phaàn töû taïi moät vò trí baát kyø naøo ñoù cuûa ngaên xeáp. Treân ñaây laø nhöõng phöông thöùc lieân quan ñeán caùc thao taùc döõ lieäu treân ngaên xeáp. Ñoái vôùi baát kyø lôùp CTDL naøo, chuùng ta cuõng khoâng theå khoâng xem xeùt ñeán hai phöông thöùc cöïc kyø quan troïng: ñoù chính laø hai haøm döïng lôùp vaø huûy lôùp: constructor vaø destructor. Trong C++ caùc haøm constructor vaø destructor ñöôïc Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 18 Chöông 2 – Ngaên xeáp trình bieân dòch goïi khi moät ñoái töôïng vöøa ñöôïc taïo ra hoaëc saép bò huûy. Chuùng ta caàn baûo ñaûm cho moãi ñoái töôïng CTDL ñöôïc taïo ra coù traïng thaùi ban ñaàu laø hôïp leä. Söï hôïp leä naøy seõ tieáp tuïc ñöôïc duy trì bôûi caùc phöông thöùc thao taùc döõ lieäu beân treân. Traïng thaùi ban ñaàu hôïp leä laø traïng thaùi roãng khoâng chöùa döõ lieäu naøo hoaëc traïng thaùi ñaõ chöùa moät soá döõ lieäu theo nhö mong muoán cuûa ngöôøi laäp trình söû duïng CTDL. Nhö vaäy, moãi lôùp CTDL luoân coù moät constructor maëc ñònh (khoâng coù thoâng soá) ñeå taïo ñoái töôïng roãng, caùc constructor coù thoâng soá khaùc chuùng ta coù theå thieát keá boå sung neáu thaáy hôïp lyù vaø caàn thieát. Moät ñoái töôïng CTDL khi bò huûy phaûi ñaûm baûo khoâng ñeå laïi raùc trong boä nhôù. Chuùng ta ñaõ bieát raèng, vôùi caùc bieán caáp phaùt tónh, trình bieân dòch seõ töï laáy laïi nhöõng vuøng nhôù ñaõ caáp phaùt cho chuùng. Vôùi caùc bieán caáp phaùt ñoäng thì ngöôïc laïi, vuøng nhôù phaûi ñöôïc chöông trình giaûi phoùng khi khoâng coøn söû duïng ñeán. Nhö vaäy, ñoái vôùi moãi phöông aùn hieän thöïc cuï theå cho moãi lôùp CTDL maø coù söû duïng vuøng nhôù caáp phaùt ñoäng, chuùng ta seõ xaây döïng destructor cho noù ñeå lo vieäc giaûi phoùng vuøng nhôù tröôùc khi ñoái töôïng bò huûy. Trong C++, constructor coù cuøng teân vôùi lôùp vaø khoâng coù kieåu traû veà. Constructor cuûa moät lôùp ñöôïc goïi moät caùch töï ñoäng khi moät ñoái töôïng cuûa lôùp ñoù ñöôïc khai baùo. Ñaëc taû constructor cho lôùp ngaên xeáp, maø chuùng ta ñaët teân laø lôùp Stack, nhö sau: template Stack::Stack(); pre: khoâng coù. post: ñoái töôïng ngaên xeáp vöøa ñöôïc taïo ra laø roãng. uses: khoâng coù. Ñeå ñaëc taû tieáp cho caùc phöông thöùc khaùc, chuùng ta choïn ra caùc trò cuûa ErrorCode ñuû ñeå söû duïng cho lôùp Stack laø: success, overflow, underflow Caùc thoâng soá daønh cho caùc phöông thöùc döôùi ñaây ñöôïc thieát keá tuøy vaøo ...