雙端隊列測試用例課件

實驗報告：特殊的線性表班級：計算機(jī)軟件工程第一小組實驗報告：特殊的線性表班級：計算機(jī)軟件工程第一小組第一小組人員名單項目經(jīng)理郭圣紅70811304000531系統(tǒng)分析魏鍇70811305000132算法設(shè)計

顧振挺70811304003633算法設(shè)計

馬伽樂70811304004234代碼編寫

施明亮70811303000435代碼編寫

沈平36代碼編寫

何斌70811434000237測試江濤70811335000138測試

徐超70811435000339文檔

朱國鋒708141040025310自由人陳茹708113040041311第一小組人員名單項目經(jīng)理郭圣紅70811304雙端隊列⑴定義雙端隊列的抽象數(shù)據(jù)類型；⑵設(shè)計存儲結(jié)構(gòu)存儲雙端隊列；⑶設(shè)計雙端隊列的插入和刪除算法；⑷

分析算法的時間性能。

棧操作實驗⑴建立一個空棧⑵

對已建立的棧進(jìn)行插入、刪除、取棧頂元素等基本操作。

實驗內(nèi)容特殊的線性表雙端隊列棧操作實驗實驗內(nèi)容特殊的線性表時間進(jìn)度安排.xlsAddYourText特殊的線性表共提交文檔任務(wù)說明書.DOC雙端隊列測試用例.DOC實驗需求說明書.DOC雙端隊列和棧測試報告.DOC雙端隊列和棧測試操作說明書.DOC雙端隊列和棧詳細(xì)設(shè)計說明書.DOC試驗二：特殊的線性表.doc數(shù)據(jù)結(jié)構(gòu)上機(jī)試驗人員Top組.doc數(shù)據(jù)結(jié)構(gòu)實驗會議紀(jì)要源程序和可執(zhí)行程序數(shù)據(jù)結(jié)構(gòu)上機(jī)試驗演示.PPT時間進(jìn)度安排.xlsAddYourText特殊的線性表共棧和雙端隊列的章節(jié)安排雙端隊列棧每實驗均六章測試結(jié)果需求分析用戶使用方法調(diào)試分析概要設(shè)計詳細(xì)設(shè)計棧和雙端隊列的章節(jié)安排雙端隊列棧每實驗均六章測試結(jié)果需求分析雙端隊列需求分析1.雙端隊列定義雙端隊列是一個兩端都是結(jié)尾的隊列，是在簡單隊列數(shù)據(jù)結(jié)構(gòu)上的改進(jìn)，其數(shù)據(jù)結(jié)構(gòu)類似于雙向鏈表，在每頭分別設(shè)有對頭和隊尾兩個指針；雙端隊列是一種具有隊列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。雙端隊列中的元素可以從兩端彈出，其限定插入和刪除操作在表兩端進(jìn)行；雙端隊列在隊列的基礎(chǔ)上，對其進(jìn)行了堆棧化;2.雙端隊列特點雙端隊列同時具有隊列和棧的性質(zhì)；雙端隊列中的元素可以從兩端彈出；如果嚴(yán)格禁用右段的操作，雙端隊列功能就和棧一樣；如果嚴(yán)格禁用左段的操作，它的功能就和隊列一樣；雙端隊列與棧或隊列相比，是一種多用途的數(shù)據(jù)結(jié)構(gòu)，在容器類庫中有時會用雙端隊列來提供棧和隊列兩種功能。雙端隊列由程序員是控制的雙端隊列需求分析1.雙端隊列定義雙端隊列需求分析3.雙端隊列功能

設(shè)計雙端隊列的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)入隊、出隊等基本操作;4.雙端隊列實驗的基本運算定義雙端隊列的抽象數(shù)據(jù)類型；設(shè)計存儲結(jié)構(gòu)存儲雙端隊列；分析算法的時間性能；雙端隊列初始化；雙端隊列清空雙端隊列頭插入雙端隊列頭取數(shù)據(jù)雙端隊列尾插入

雙端隊列尾取數(shù)據(jù)5.雙端隊列實驗的接口要求用戶能輸入數(shù)據(jù)，和程序能有交互雙端隊列需求分析3.雙端隊列功能雙端隊列需求分析下圖是我們對這個雙端隊列實驗的感性認(rèn)識雙端隊列TAILPTRHEADPTRNextPrevObjectNextPrevObjectNextPrevObjectNULLApplicationDataApplicationDataApplicationDataNULL雙端隊列需求分析下圖是我們對這個雙端隊列實驗的感性認(rèn)識雙端雙端隊列概要設(shè)計該程序主要實現(xiàn)以下5個功能：1.從隊列首輸入數(shù)據(jù)2.從隊列尾輸入數(shù)據(jù)3.從隊列首取數(shù)據(jù)4.從隊列尾取數(shù)據(jù)5.隊列清空雙端隊列概要設(shè)計該程序主要實現(xiàn)以下5個功能：雙端隊列概要設(shè)計針對需要實現(xiàn)的功能做出詳細(xì)的算法設(shè)計采用雙向隊列來實現(xiàn)，隊列中有兩個指針，一個指針指向隊首結(jié)點，一個指向隊尾結(jié)點。定義一個結(jié)構(gòu)體，其中包含一個數(shù)據(jù)域和兩個指針域，數(shù)據(jù)域用來存放數(shù)據(jù)，一個指針域用來存放指向前驅(qū)結(jié)點的指針，另一個指針域用來存放指向后繼結(jié)點的指針。1.新建結(jié)點就是分配一個新的內(nèi)存空間。2.每次分配空間都需要判斷是否能分配到內(nèi)存空間，如果未得到內(nèi)存空間則終止當(dāng)前操作。3.隊列中只有頭結(jié)點，該隊列即為空隊列。以上3點后面不再重復(fù)說明。雙端隊列概要設(shè)計針對需要實現(xiàn)的功能做出詳細(xì)的算法設(shè)計雙端隊列概要設(shè)計一、 從頂部入隊列新建一個結(jié)點，如果隊列為空，則將隊列的隊首指針和隊尾指針均指向新建結(jié)點，如不為空則將隊首指針指向新建結(jié)點，并將新建結(jié)點的后繼指針指向原隊首結(jié)點，原隊首結(jié)點的指針指向新建結(jié)點。二、 從頂部出隊列首先判斷隊列是否為空，如為空則提示隊列為空，如不為空則將隊首結(jié)點賦給臨時結(jié)點。將隊首結(jié)點的后繼指針賦給隊列的隊首指針，再將隊首結(jié)點的前驅(qū)指針置空。最后返回臨時結(jié)點或所需要的數(shù)據(jù)。三、 從底部入隊列新建一個結(jié)點，如果隊列為空，則將隊列的隊首指針和隊尾指針均指向新建結(jié)點，如不為空則將隊尾指針指向新建結(jié)點，并將新建結(jié)點的前驅(qū)指針指向原隊尾結(jié)點，原隊尾結(jié)點的指針指向新建結(jié)點。四、 從底部出隊列首先判斷隊列是否為空，如為空則提示隊列為空，如不為空則將隊尾結(jié)點賦給臨時結(jié)點。將隊尾結(jié)點的前驅(qū)指針賦給隊列的隊尾指針，再將隊尾結(jié)點的后繼指針置空。最后返回臨時結(jié)點或所需要的數(shù)據(jù)。五、 隊列清空將隊列的隊首指針和隊尾指針置空即可。雙端隊列概要設(shè)計一、 從頂部入隊列雙端隊列詳細(xì)設(shè)計雙端隊列數(shù)據(jù)類型

typedefstructnodeptrdatanode;typedefstructnodeptr{void*data;datanode*prev,*next;}node;typedefstruct{node*head,*tail,*cursor;intsize,item_deleted;}queue;雙端隊列詳細(xì)設(shè)計雙端隊列數(shù)據(jù)類型雙端隊列詳細(xì)設(shè)計雙端隊列實現(xiàn)的功能intQ_Init(queue*q);函數(shù)：初始化隊列intQ_Empty(queue*q);函數(shù)：隊列清空intQ_PushHead(queue*q,int*d);函數(shù):數(shù)值入隊列首intQ_PushTail(queue*q,int*d);函數(shù)：數(shù)值入隊列尾intQ_PopHead(queue*q);函數(shù)：首部出隊列intQ_PopTail(queue*q);函數(shù)：尾部出隊列雙端隊列詳細(xì)設(shè)計雙端隊列實現(xiàn)的功能雙端隊列調(diào)試分析Step1運行主程序顯示主選擇項測試結(jié)果：按任務(wù)書所要求的存數(shù)據(jù)入首、尾隊列，隊列首、尾取數(shù)據(jù)，隊列清空，退出等選項顯示清晰，達(dá)到要求雙端隊列測試用例1雙端隊列調(diào)試分析Step1運行主程序顯示主選擇項雙端隊雙端隊列調(diào)試分析Step2從隊列首添加數(shù)據(jù)的測試測試結(jié)果：通過監(jiān)視隊列l(wèi)ine，可知內(nèi)部的節(jié)點秩序與屏幕輸出的秩序一致，因此從隊列首添加數(shù)據(jù)的代碼執(zhí)行正確2雙端隊列測試用例雙端隊列調(diào)試分析Step2從隊列首添加數(shù)據(jù)的測試2雙雙端隊列調(diào)試分析Step3從隊列尾添加數(shù)據(jù)的測試測試結(jié)果：通過監(jiān)視隊列l(wèi)ine，可知，里面的節(jié)點秩序與屏幕輸出的秩序一致，因此從隊列尾添加數(shù)據(jù)的代碼執(zhí)行正確3雙端隊列測試用例雙端隊列調(diào)試分析Step3從隊列尾添加數(shù)據(jù)的測試3雙端隊列調(diào)試分析Step4從隊列首取四個數(shù)據(jù)的測試測試結(jié)果：通過監(jiān)視隊列l(wèi)ine，可知，里面的節(jié)點秩序與屏幕輸出的秩序一致，因此從隊列首部取四個數(shù)據(jù)代碼執(zhí)行正確雙端隊列測試用例4雙端隊列調(diào)試分析Step4從隊列首取四個數(shù)據(jù)的測試雙端隊列調(diào)試分析Step5從隊列尾取四個數(shù)據(jù)的測試測試結(jié)果：內(nèi)部的節(jié)點值與屏幕輸出的秩序一致，因此從隊列尾部取四個數(shù)據(jù)代碼執(zhí)行正確5雙端隊列測試用例雙端隊列調(diào)試分析Step5從隊列尾取四個數(shù)據(jù)的測試雙端隊列調(diào)試分析Step6從隊列清空數(shù)據(jù)的測試測試結(jié)果：隊列清空代碼執(zhí)行正確6雙端隊列測試用例雙端隊列調(diào)試分析Step6從隊列清空數(shù)據(jù)的測試6雙端雙端隊列調(diào)試分析代碼測試按照正常的系統(tǒng)使用條件：測試人員對本系統(tǒng)的逐個功能進(jìn)行使用，填寫入測試報告。測試人員測試結(jié)束后，對所呈現(xiàn)bug，開發(fā)人員對系統(tǒng)中問題進(jìn)行分析，確定故障的原因，并制定相應(yīng)的對策。測試方法說明采用VC集成開發(fā)環(huán)境，①在代碼中嵌入屏幕輸出代碼，在程序測試運行時，可隨時觀察程序運行的狀態(tài)，數(shù)據(jù)輸出是否準(zhǔn)確，并記錄測試結(jié)果。②在各函數(shù)中設(shè)定中斷，采用debug調(diào)試程序，觀察和監(jiān)視雙端隊列中各節(jié)點的變化過程。對于程序中的故障，亦可設(shè)置斷點進(jìn)行參數(shù)監(jiān)視，逐一排查。雙端隊列調(diào)試分析代碼測試雙端隊列調(diào)試分析使用上述用例經(jīng)過5輪測試。共發(fā)現(xiàn)7個缺陷，所發(fā)現(xiàn)的問題已經(jīng)全部得到解決，代碼現(xiàn)已處在一個穩(wěn)定運行階段，達(dá)到任務(wù)書提出的要求，功能滿足了系統(tǒng)設(shè)計要求，達(dá)到了系統(tǒng)設(shè)計的目標(biāo)雙端隊列調(diào)試分析使用上述用例經(jīng)過5輪測試。共發(fā)現(xiàn)7個缺陷，雙端隊列用戶使用方法1.s運行雙端隊列可執(zhí)行程序DEQUE.exe,程序?qū)霈F(xiàn)先的畫面，然后根據(jù)程序提示進(jìn)行相關(guān)操作雙端隊列用戶使用方法1.s運行雙端隊列可執(zhí)行程序DEQUE雙端隊列測試結(jié)果1.s從隊列首添加數(shù)據(jù)雙端隊列測試結(jié)果1.s從隊列首添加數(shù)據(jù)雙端隊列測試結(jié)果2.s從隊列尾添加數(shù)據(jù)雙端隊列測試結(jié)果2.s從隊列尾添加數(shù)據(jù)雙端隊列測試結(jié)果3.s從隊列首取四個數(shù)據(jù)雙端隊列測試結(jié)果3.s從隊列首取四個數(shù)據(jù)雙端隊列測試結(jié)果4.s從隊列尾取四個數(shù)據(jù)雙端隊列測試結(jié)果4.s從隊列尾取四個數(shù)據(jù)雙端隊列

實驗匯報完畢!!!!雙端隊列

實驗匯報完畢!!!!棧需求分析1.棧定義棧（stack）在計算機(jī)科學(xué)中是限定僅在表尾進(jìn)行插入或刪除操作的線形表。棧是一種數(shù)據(jù)結(jié)構(gòu)，它按照后進(jìn)先出的原則存儲數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。棧是只能在某一端插入和刪除的特殊線性表。用桶堆積物品，先堆進(jìn)來的壓在底下，隨后一件一件往堆。取走時，只能從上面一件一件取。堆和取都在頂部進(jìn)行，底部一般是不動的。棧就是一種類似桶堆積物品的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行刪除和插入的一端稱棧頂，另一堆稱棧底。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進(jìn)先出表（LIFO表）棧需求分析1.棧定義棧需求分析2.棧特點棧是機(jī)器系統(tǒng)自動分配提供的數(shù)據(jù)結(jié)構(gòu)，特點是快速高效，缺點是有限制，數(shù)據(jù)不靈活，但程序員是無法控制的；棧對于進(jìn)程/線程是唯一的；棧的剩余空間大于所申請空間，系統(tǒng)將為程序提供內(nèi)存，否則將報異常提示棧溢出棧需求分析2.棧特點棧

概要設(shè)計1.順序棧實驗的要求實現(xiàn)一個空順序棧；并對已建立的棧進(jìn)行插入、刪除、取棧頂元素等基本操作；棧的順序存儲結(jié)構(gòu)簡稱為順序棧,它是運算受限的順序表2.順序棧實驗的基本運算置?？眨慌袟？?；判棧滿；進(jìn)棧；退棧；取棧頂元素棧概要設(shè)計1.順序棧實驗的要求棧

概要設(shè)計順序方式生成一個棧，并實現(xiàn)對棧的操作，具體操作有：入棧、出棧、取棧頂元素，棧內(nèi)存放數(shù)據(jù)為整數(shù)類型在main方法內(nèi)實現(xiàn)簡單的交互功能，根據(jù)輸入的命令調(diào)用對應(yīng)函數(shù)，可讀取一行數(shù)據(jù)，自左向右依次入棧。操作指令：入棧push/出棧pop/取棧頂gettop/退出exit例如：Push空格輸入數(shù)據(jù)/Push回車輸入數(shù)據(jù)scanf使用技巧：scanf會讀取用戶輸入的數(shù)據(jù)，并以空格、制表符為結(jié)束標(biāo)志讀取，同時scanf會返回，本次操作讀取到數(shù)據(jù)的數(shù)量，讀取一行多個數(shù)據(jù)時，可作為循環(huán)條件，判斷緩沖區(qū)是否讀取完畢。棧概要設(shè)計順序方式生成一個棧，并實現(xiàn)對棧的操作，具體操作有棧

詳細(xì)設(shè)計棧數(shù)據(jù)類型

typedefstruct{ int*base; int*top; intstacksize;}SqStack;棧詳細(xì)設(shè)計棧數(shù)據(jù)類型棧

詳細(xì)設(shè)計棧實現(xiàn)的功能StatusInitStack(Sqstack&s);函數(shù)：初始化棧StatusClearstack(Sqstack&s);函數(shù)：棧清空StatusGetTop(Sqstacks,SElemType&p);函數(shù):取棧頂元素StatusPush(Sqstack&s,SElemType&e);函數(shù)：進(jìn)棧函數(shù)StatusPop(Sqstack&s,SElemType&c);函數(shù)：出棧函數(shù)StatusObjection(Sqstack&s);函數(shù)：判斷輸入字符函數(shù)棧詳細(xì)設(shè)計棧實現(xiàn)的功能棧

調(diào)試分析按照正常的系統(tǒng)使用條件：測試人員對本系統(tǒng)的逐個功能進(jìn)行使用，填寫入測試報告。測試人員測試結(jié)束后，對所呈現(xiàn)的bug，開發(fā)人員對系統(tǒng)中問題進(jìn)行分析，確定故障的原因，并制定相應(yīng)的對