數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 棧和隊(duì)列

第11頁北京郵電大學(xué)電信工程學(xué)院第1頁2007級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)二棧和隊(duì)列日期：2008年11月15日1．實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康耐ㄟ^選擇下面五個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：進(jìn)一步掌握指針、模板類、異常處理的使用掌握棧的操作的實(shí)現(xiàn)方法掌握隊(duì)列的操作的實(shí)現(xiàn)方法學(xué)習(xí)使用棧解決實(shí)際問題的能力學(xué)習(xí)使用隊(duì)列解決實(shí)際問題的能力實(shí)驗(yàn)內(nèi)容2.1題目1根據(jù)棧和隊(duì)列的抽象數(shù)據(jù)類型的定義，按要求實(shí)現(xiàn)一個(gè)?；蛞粋€(gè)隊(duì)列。要求：實(shí)現(xiàn)一個(gè)共享?xiàng)?shí)現(xiàn)一個(gè)鏈棧實(shí)現(xiàn)一個(gè)循環(huán)隊(duì)列實(shí)現(xiàn)一個(gè)鏈隊(duì)列編寫測試main()函數(shù)測試線性表的正確性。2.程序分析2.1存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：特殊線性表：棧，隊(duì)列下標(biāo)：下標(biāo)：01i-1共享?xiàng)1a2……aibj……b2b1棧1底top1top2棧2底StackSize-1循環(huán)隊(duì)列front循環(huán)隊(duì)列frontreara6a5a4a7an-1ana1∧棧頂棧底top鏈?！摹腶1a2an∧非空鏈隊(duì)列∧空鏈隊(duì)列frontrearfrontrear2.2關(guān)鍵算法分析共享?xiàng)５娜霔Ｋ惴▊未a（Push）：1．如果棧滿，拋出上溢異常。2．判斷是插在棧1還是棧2：2.1如果在棧1插入，則棧頂指針top1加1，在top1處填入元素x；2.2如果在棧2插入，則棧頂指針top2加1，在top2處填入元素x。共享?xiàng)５某鰲Ｋ惴▊未a（Pop）：1.判斷是在棧1刪除還是在棧2刪除。2.若是在棧1刪除，則2.1若棧1為空棧，拋出下溢異常；2.2刪除并返回棧1的棧頂元素；3.若是在棧2刪除，則3.1若棧2為空棧，拋出下溢異常；3.2刪除并返回棧2的棧頂元素。共享?xiàng)５娜ｍ斣厮惴▊未a（GetTop）：判斷是在棧1取還是棧2??；如果在棧1取，則2.1若棧1不空，返回棧頂元素的值，不刪除；2.2若棧1空，返回0；3．如果在棧2取，則3.1若棧2不空，返回棧頂元素的值，不刪除；3.2若棧2空，返回0。鏈棧的入棧算法偽碼（Push）：申請(qǐng)一個(gè)新的結(jié)點(diǎn)，數(shù)據(jù)域?yàn)閤；將新結(jié)點(diǎn)插在棧頂；棧頂指針重新指向棧頂元素。鏈棧的出棧算法偽碼（Pop）：如果?？?，拋出下溢異常；暫存棧頂元素；將棧頂結(jié)點(diǎn)摘鏈；刪除該結(jié)點(diǎn)，返回該元素的值。鏈棧的取棧頂元素算法的偽碼（GetTop）：如果棧非空，返回棧頂元素的值，不刪除。循環(huán)隊(duì)列的入隊(duì)算法偽碼（EnQueue）：如果隊(duì)滿，拋出上溢異常；隊(duì)尾指針在循環(huán)意義下加1；在隊(duì)尾插入元素。循環(huán)隊(duì)列的出隊(duì)算法偽碼（DeQueue）：如果隊(duì)空，拋出下溢異常；隊(duì)頭指針在循環(huán)意義下加1；讀取并返回出隊(duì)前的隊(duì)頭元素。循環(huán)隊(duì)列的取隊(duì)頭元素算法偽碼（GetQueue）：如果隊(duì)空，拋出下溢異常；值為隊(duì)頭指針的工作指針i在循環(huán)意義下加1，注意不給隊(duì)頭指針賦值；返回隊(duì)頭指針的隊(duì)頭元素。鏈隊(duì)列的入隊(duì)算法偽碼（EnQueue）：申請(qǐng)一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)；該結(jié)點(diǎn)的next域置空；將其插到隊(duì)尾。鏈隊(duì)列的出隊(duì)算法偽碼（DeQueue）：如果隊(duì)空，拋出下溢異常；暫存隊(duì)頭元素；將隊(duì)頭元素所在結(jié)點(diǎn)摘鏈；如果被刪除的隊(duì)頭元素同時(shí)也是隊(duì)尾元素，則修改隊(duì)尾指針。鏈隊(duì)列的取隊(duì)頭元素算法偽碼（GetQueue）：如果隊(duì)非空，返回隊(duì)頭元素的值，不刪除?！摹腶1∧特殊情況：隊(duì)列長度為1a1a2an∧一般情況：隊(duì)列長度大于1鏈隊(duì)列出隊(duì)操作frontrearfrontrearpp以上算法的時(shí)間復(fù)雜度均為O(1)?？杀容^的是空間性能。初始時(shí)順序棧必須確定一個(gè)固定的長度，所以有存儲(chǔ)元素個(gè)數(shù)的限制和空間浪費(fèi)的問題。鏈棧沒有棧滿的問題，只有當(dāng)內(nèi)存沒有可用空間時(shí)才會(huì)出現(xiàn)棧滿。但是每個(gè)元素都需要一個(gè)指針域，所以產(chǎn)生了結(jié)構(gòu)性開銷。循環(huán)隊(duì)列和鏈隊(duì)列的空間性能的比較與順序棧和鏈棧的空間性能比較類似，只是循環(huán)隊(duì)列不能像順序棧那樣共享空間，通常不能在一個(gè)數(shù)組中存儲(chǔ)兩個(gè)循環(huán)隊(duì)列。3.程序運(yùn)行結(jié)果開始開始新建共享?xiàng)對(duì)B入棧操作判斷兩個(gè)棧是否為空并輸出判斷結(jié)果對(duì)B取棧頂元素操作判斷兩個(gè)棧是否為空并輸出判斷結(jié)果判斷兩個(gè)棧是否為空并輸出判斷結(jié)果對(duì)B出棧操作共享?xiàng)Ｖ骱瘮?shù)流程圖：新建鏈棧LS新建鏈棧LS對(duì)LS入棧操作對(duì)LS取棧頂元素操作判斷棧是否為空并輸出結(jié)果對(duì)LS出棧操作判斷LS是否為空并輸出結(jié)果開始鏈棧主函數(shù)流程圖：新建循環(huán)隊(duì)列CQ新建循環(huán)隊(duì)列CQ對(duì)CQ入隊(duì)操作對(duì)C Q取隊(duì)頭元素操作判斷隊(duì)是否為空并輸出結(jié)果對(duì)CQ出隊(duì)操作判斷CQ是否為空并輸出結(jié)果開始循環(huán)隊(duì)列主函數(shù)流程圖：對(duì)LQ出隊(duì)操作對(duì)LQ出隊(duì)操作新建鏈隊(duì)列LQ判斷鏈隊(duì)列是否為空并輸出結(jié)果對(duì)LQ入隊(duì)操作判斷隊(duì)是否為空并輸出結(jié)果對(duì)LQ取隊(duì)頭元素操作判斷鏈隊(duì)列是否為空并輸出結(jié)果開始判斷鏈隊(duì)列是否為空并輸出結(jié)果鏈隊(duì)列主函數(shù)流程圖：測試條件：主函數(shù)都大都采用了使用循環(huán)來入棧（隊(duì)）（鏈隊(duì)列除外），問題規(guī)模取決于棧本身的大小，而鏈隊(duì)列和鏈棧不受限制（除非內(nèi)存沒了）。每次入棧（隊(duì)）、出棧（隊(duì)）、取棧頂（隊(duì)頭）元素前后都執(zhí)行函數(shù)Empty()判斷棧（隊(duì)列）是否為空。測試結(jié)論：程序可以正常且正確運(yùn)行?？偨Y(jié)調(diào)試時(shí)出現(xiàn)的問題及解決的方法對(duì)循環(huán)隊(duì)列進(jìn)行測試時(shí)，由于之前設(shè)定的隊(duì)列的大小是10，故在入隊(duì)時(shí)設(shè)定的k最大為9了即k<10，然而運(yùn)行時(shí)程序出錯(cuò)，于是試著把k<10改為了k<9，重新運(yùn)行便無問題了。這是因?yàn)檠h(huán)隊(duì)列實(shí)際上是留出了一個(gè)空的數(shù)組元素空間，以便判斷隊(duì)是否已滿，所以實(shí)際上最多只能儲(chǔ)存9個(gè)元素。故k=0;k<9。但后來添加了異常處理，故而改為可以由用戶自行輸入元素值。心得體會(huì)這次選擇的題目非?；荆枪蚕?xiàng)?、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列的基本實(shí)現(xiàn)，相對(duì)也比較容易，但卻是很基礎(chǔ)的，有些細(xì)節(jié)部分是值得高度重視的，也是容易出錯(cuò)的地方，例如上所寫的測試循環(huán)隊(duì)列時(shí)出現(xiàn)的問題。對(duì)這些基本的特殊線性表的測試與實(shí)現(xiàn)是編寫較復(fù)雜程序的基礎(chǔ)，應(yīng)該牢固掌握它們。這個(gè)實(shí)驗(yàn)也讓我學(xué)會(huì)了異常處理的方法。下一步的改