雙端隊(duì)列測(cè)試用例課件

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

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

馬伽樂70811304004234代碼編寫

施明亮70811303000435代碼編寫

沈平36代碼編寫

何斌70811434000237測(cè)試江濤70811335000138測(cè)試

徐超70811435000339文檔

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

分析算法的時(shí)間性能。

棧操作實(shí)驗(yàn)⑴建立一個(gè)空棧⑵

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

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

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

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

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

實(shí)驗(yàn)匯報(bào)完畢!!!!雙端隊(duì)列

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

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

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

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

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

詳細(xì)設(shè)計(jì)棧實(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è)計(jì)棧實(shí)現(xiàn)的功能棧

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