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

Dựa trên tính chất của các giải thuật, các ứng dụng của ngăn xếp có thể được chia làm bốn nhóm như sau: đảo ngược dữ liệu, phân tích biên dịch dữ liệu, trì hoãn công việc và các giải thuật
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu ( chương 14)Chöông 14 – ÖÙng duïng cuûa ngaên xeáp Phaàn 3 – CAÙC ÖÙNG DUÏNG CUÛA CAÙC LÔÙP CTDLChöông 14 – ÖÙNG DUÏNG CUÛA NGAÊN XEÁP Döïa treân tính chaát cuûa caùc giaûi thuaät, caùc öùng duïng cuûa ngaên xeáp coù theå ñöôïcchia laøm boán nhoùm nhö sau: ñaûo ngöôïc döõ lieäu, phaân tích bieân dòch döõ lieäu, trìhoaõn coâng vieäc vaø caùc giaûi thuaät quay lui. Moät ñieàu ñaùng chuù yù ôû ñaây laø khi xemxeùt caùc öùng duïng, chuùng ta khoâng bao giôø quan taâm ñeán caáu truùc chi tieát cuûa ngaênxeáp. Chuùng ta luoân söû duïng ngaên xeáp nhö moät caáu truùc döõ lieäu tröøu töôïng vôùi caùcchöùc naêng maø chuùng ta ñaõ ñònh nghóa cho noù.14.1. Ñaûo ngöôïc döõ lieäu Trong phaàn trình baøy veà ngaên xeáp chuùng ta ñaõ ñöôïc laøm quen vôùi moät ví duïxuaát caùc phaàn töû theo thöù töï ngöôïc vôùi thöù töï nhaäp vaøo. ÔÛ ñaây chuùng ta tieáp tuïctham khaûo theâm öùng duïng ñoåi moät soá thaäp phaân sang moät soá nhò phaân.ÖÙng duïng ñoåi soá thaäp phaân sang soá nhò phaân Giaûi thuaät döôùi ñaây chuyeån ñoåi soá thaäp phaân decNum sang moät soá nhò phaân. 1 loop (decNum > 0) 1 digit = decNum % 2 2 xuaát (digit) 3 decNum = decNum / 2 2 endloop Tuy nhieân caùc kyù soá ñöôïc xuaát ra seõ laø thöù töï ngöôïc cuûa keát quaû maø chuùng tamong muoán. Chaúng haïn soá 19 leõ ra phaûi ñöôïc ñoåi thaønh 10011 chöù khoâng phaûi laø11001. Thöïc laø deã daøng neáu chuùng ta söû duïng ngaên xeáp ñeå khaéc phuïc ñieàu naøy.Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 365Chöông 14 – ÖÙng duïng cuûa ngaên xeáp void DecimalToBinary (val int decNum) post: soá nhò phaân töông ñöông vôùi soá thaäp phaân decNum seõ ñöôïc xuaát ra. uses: söû duïng lôùp Stack ñeå ñaûo ngöôïc thöù töï caùc soá 1 vaø soá 0. { 1. Stack reverse; // Khôûi taïo ngaên xeáp ñeå chöùa caùc kyù soá 0 vaø 1. 2. loop (decNum > 0) 1. digit = decNum % 2 2. reverse.push(digit) 3. decNum = decNum / 2 3. endloop 4. loop (!reverse.empty()) 1. reverse.top(digit) 2. reverse.pop() 3. xuaát(digit) 5 endloop } Moät ñieàu deã nhaän thaáy laø neáu chuùng ta duøng moät maûng lieân tuïc (array trongC++) ñeå chöùa caùc soá digit roài tìm caùch in theo thöù töï ñaûo laïi, chuùng ta seõ phaûitieâu toán söùc löïc vaøo vieäc quaûn lyù caùc bieán chæ soá chaïy treân maûng. Ñoù laø ñieàu neântraùnh. Vieäc tuaân thuû lôøi khuyeân naøy giuùp chuùng ta coù thoùi quen toát khi ñuïng phaûinhöõng baøi toaùn lôùn hôn: chuùng ta coù theå taäp trung vaøo giaûi quyeát nhöõng vaán ñeàchính cuûa baøi toaùn.14.2. Phaân tích bieân dòch (parsing) döõ lieäu Vieäc phaân tích döõ lieäu thöôøng bao goàm phaân tích töø vöïng vaø phaân tích cuùphaùp. Chaúng haïn, ñeå chuyeån ñoåi moät chöông trình nguoàn ñöôïc vieát bôûi moät ngoânngöõ naøo ñoù thaønh ngoân ngöõ maùy, trình bieân dòch caàn taùch chöông trình aáy rathaønh caùc töø khoùa, caùc danh hieäu, caùc kyù hieäu, sau ñoù tieán haønh kieåm tra tínhhôïp leä veà töø vöïng, veà cuù phaùp. Trong vieäc kieåm tra cuù phaùp thì vieäc kieåm tra caáutruùc khoái loàng nhau moät caùch hôïp leä laø moät trong nhöõng ñieàu coù theå ñöôïc thöïchieän deã daøng nhôø ngaên xeáp.ÖÙng duïng kieåm tra tính hôïp leä cuûa caùc caáu truùc khoái loàng nhau Ñeå kieåm tra tính hôïp leä cuûa caùc caáu truùc khoái loàng nhau, chuùng ta caàn kieåmtra caùc caëp daáu ngoaëc nhö [], {}, () phaûi tuaân theo moät thöù töï ñoùng môû hôïp leä, coùnghóa laø moãi khoái caàn phaûi naèm goïn trong moät khoái khaùc, neáu coù. Lyù do söû duïng ngaên xeáp ñöôïc giaûi thích nhö sau: theo thöù töï xuaát hieän, moätdaáu ngoaëc môû xuaát hieän sau caàn phaûi coù daáu ngoaëc ñoùng töông öùng xuaát hieäntröôùc. Ví duï […(…)…] laø hôïp leä, […(…]…) laø khoâng hôïp leä. Ñieàu naøy roõ raøng lieân quanñeán nguyeân taéc FILO cuûa ngaên xeáp. Moãi caáu truùc khoái seõ ñöôïc chuùng ta bieát ñeánGiaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 366Chöông 14 – ÖÙng duïng cuûa ngaên xeápkhi baét ñaàu gaëp daáu ngoaëc môû cuûa noù, vaø chuùng ta seõ chôø cho ñeán khi naøo gaëp daáungoaëc ñoùng töông öùng cuûa noù thì xem nhö chuùng ta ñaõ duyeät qua caáu truùc ñoù. Caùcdaáu ngoaëc môû maø chuùng ta gaëp, chuùng ta seõ laàn löôït löu vaøo ngaên xeáp, neáu ñoaïnchöông trình hôïp leä, thì chuùng ta cöù yeân taâm raèng caùc daáu ngoaëc ñoùng töông öùngcuûa chuùng seõ xuaát hieän theo ñuùng thöù töï ngöôïc laïi. Nhö vaäy, moãi khi gaëp moät daáungoaëc ñoùng, vieäc caàn laøm laø laáy töø ngaên xeáp ra moät daáu ngoaëc môû vaø so truøng. Vaên baûn caàn kieåm tra thöôøng laø moät bieåu thöùc tính toaùn hay moät ñoaïn chöôngtrình. Giaûi thuaät: Ñoïc ñoaïn vaên baûn töøng kyù töï moät. Moãi daáu ngoaëc môû (, [, { ñöôïcx ...