[IT計算機]數(shù)據(jù)結構實驗設計雙端隊列

1、 江西農業(yè)大學軟件學院數(shù)據(jù)結構實驗報告專業(yè)班級：軟件1104班學生姓名：彭勝學號：20111523指導老師：楊文姬老師聯(lián)系郵箱：799275381目錄一系統(tǒng)簡介3二需求分析4三功能分析5四概要設計7五詳細設計9六體會心得32實驗題目：雙端隊列雙端隊列是插入和刪除操作可以在兩端進行的線性表，表的兩端分別稱作端點1和端點2.設計雙端隊列的數(shù)據(jù)結構，實現(xiàn)入隊、出隊等基本操作。一系統(tǒng)簡介雙端隊列是限定插入和刪除操作在表的兩端進行的線性表。這兩端分別稱做端點1和端點2（如下圖(a)所示）。也可像棧一樣，可以用一個鐵道轉軌網絡來比喻雙端隊列，如下圖(b)所示。在實際使用中，還可以有輸出受限的雙

2、端隊列（即一個端點允許插入和刪除，另一個端點只允許插入的雙端隊列）和輸入受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只允許刪除的雙端隊列）。而如果限定雙端隊列從某個端點插入的元素只能從該端點刪除，則該雙端隊列就蛻變?yōu)閮蓚€棧底相鄰的棧了。 一 盡管雙端隊列看起來似乎比棧和隊列更靈活，但實際上在應用程序中遠不及棧和隊列有用。 雙端隊列與?；蜿犃邢啾?，是一種多用途的數(shù)據(jù)結構，在容器類庫中有時會用雙端隊列來提供棧和隊列兩種功能。二需求分析1.雙端隊列定義 雙端隊列是一個兩端都是結尾的隊列，是在簡單隊列數(shù)據(jù)結構上的改進，其數(shù)據(jù)結構類似于雙向鏈表，在每頭分別設有對頭和隊尾兩個指針；雙端隊列是一種具

3、有隊列和棧的性質的數(shù)據(jù)結構。雙端隊列中的元素可以從兩端彈出，其限定插入和刪除操作在表兩端進行；雙端隊列在隊列的基礎上，對其進行了堆?；?2.雙端隊列特點 雙端隊列同時具有隊列和棧的性質；雙端隊列中的元素可以從兩端彈出；如果嚴格禁用右段的操作，雙端隊列功能就和棧一樣；如果嚴格禁用左段的操作，它的功能就和隊列一樣；雙端隊列與?；蜿犃邢啾?，是一種多用途的數(shù)據(jù)結構，在容器類庫中有時會用雙端隊列來提供棧和隊列兩種功能。雙端隊列由程序員是控制的3.雙端隊列功能 設計雙端隊列的數(shù)據(jù)結構，實現(xiàn)入隊、出隊等基本操作;4.雙端隊列實驗的基本運算 定義雙端隊列的抽象數(shù)據(jù)類型；設計存儲結構存儲雙端隊列；分析算法的時間

4、性能；雙端隊列初始化；雙端隊列清空；雙端隊列頭插入雙端隊列頭取數(shù)據(jù)雙端隊列尾插入 雙端隊列尾取數(shù)據(jù) 5.雙端隊列實驗的接口要求 用戶能輸入數(shù)據(jù)，和程序能有交互 三功能分析該程序主要實現(xiàn)以下5個功能：1. 從隊列首輸入數(shù)據(jù)2. 從隊列尾輸入數(shù)據(jù)3. 從隊列首取數(shù)據(jù)4. 從隊列尾取數(shù)據(jù)5. 隊列清空針對需要實現(xiàn)的功能做出詳細的算法設計采用雙向隊列來實現(xiàn)，隊列中有兩個指針，一個指針指向隊首結點，一個指向隊尾結點。定義一個結構體，其中包含一個數(shù)據(jù)域和兩個指針域，數(shù)據(jù)域用來存放數(shù)據(jù)，一個指針域用來存放指向前驅結點的指針，另一個指針域用來存放指向后繼結點的指針。1.新建結點就是分配一個新的內存空間。2.每

5、次分配空間都需要判斷是否能分配到內存空間，如果未得到內存空間則終止當前操作。3.隊列中只有頭結點，該隊列即為空隊列。以上3點后面不再重復說明。 (一)從頂部入隊列新建一個結點，如果隊列為空，則將隊列的隊首指針和隊尾指針均指向新建結點，如不為空則將隊首指針指向新建結點，并將新建結點的后繼指針指向原隊首結點，原隊首結點的指針指向新建結點。(二)從頂部出隊列首先判斷隊列是否為空，如為空則提示隊列為空，如不為空則將隊首結點賦給臨時結點。將隊首結點的后繼指針賦給隊列的隊首指針，再將隊首結點的前驅指針置空。最后返回臨時結點或所需要的數(shù)據(jù)。(三)從底部入隊列新建一個結點，如果隊列為空，則將隊列的隊首指針和隊

6、尾指針均指向新建結點，如不為空則將隊尾指針指向新建結點，并將新建結點的前驅指針指向原隊尾結點，原隊尾結點的指針指向新建結點。(四)從底部出隊列首先判斷隊列是否為空，如為空則提示隊列為空，如不為空則將隊尾結點賦給臨時結點。將隊尾結點的前驅指針賦給隊列的隊尾指針，再將隊尾結點的后繼指針置空。最后返回臨時結點或所需要的數(shù)據(jù)。(五)隊列清空將隊列的隊首指針和隊尾指針置空即可。操作如下是限定插入和刪除操作是在表的兩端進行的線性表.這兩端分別稱為端點1和端點2a1 a2 a3.an 插入刪除端1端2隊列q=(a1,a2,an)插入刪除四概要設計（1）系統(tǒng)功能結構設計 該程序主要實現(xiàn)以下5個功能： 1. 從

7、隊列首輸入數(shù)據(jù) 2. 從隊列尾輸入數(shù)據(jù) 3. 從隊列首取數(shù)據(jù) 4. 從隊列尾取數(shù)據(jù) 5. 隊列清空 6.退出（2）數(shù)據(jù)結構設計針對需要實現(xiàn)的功能做出詳細的算法設計采用雙向隊列來實現(xiàn)，隊列中有兩個指針，一個指針指向隊首結點，一個指向隊尾結點。定義一個結構體，其中包含一個數(shù)據(jù)域和兩個指針域，數(shù)據(jù)域用來存放數(shù)據(jù)，一個指針域(front)用來存放指向前驅結點的指針，另一個指針域(rear)用來存放指向后繼結點的指針。1.新建結點就是分配一個新的內存空間。2.每次分配空間都需要判斷是否能分配到內存空間，如果未得到內存空間則終止當前操作。3.隊列中只有頭結點，該隊列即為空隊列。以上3點后面不再重復說明。（

8、3）模塊接口設計a. 從頂部入隊列新建一個結點，如果隊列為空，則將隊列的隊首指針和隊尾指針均指向新建結點，如不為空則將隊首指針指向新建結點，并將新建結點的后繼指針指向原隊首結點，原隊首結點的指針指向新建結點。b. 從頂部出隊列首先判斷隊列是否為空，如為空則提示隊列為空，如不為空則將隊首結點賦給臨時結點。將隊首結點的后繼指針賦給隊列的隊首指針，再將隊首結點的前驅指針置空。最后返回臨時結點或所需要的數(shù)據(jù)。c. 從底部入隊列新建一個結點，如果隊列為空，則將隊列的隊首指針和隊尾指針均指向新建結點，如不為空則將隊尾指針指向新建結點，并將新建結點的前驅指針指向原隊尾結點，原隊尾結點的指針指向新建結點。d.

9、 從底部出隊列首先判斷隊列是否為空，如為空則提示隊列為空，如不為空則將隊尾結點賦給臨時結點。將隊尾結點的前驅指針賦給隊列的隊尾指針，再將隊尾結點的后繼指針置空。最后返回臨時結點或所需要的數(shù)據(jù)。e. 隊列清空將隊列的隊首指針和隊尾指針置空即可。五詳細設計函數(shù)的類型：queuenotempty(lqueue q)queueappend(lqueue *q ,datatype x)queuedelete(lqueue *q,datatype *d)queueget雙端函數(shù)：elementtype front (queue q)取隊頭元素void push (elementtype x)在隊頭執(zhí)行入隊

10、操作void pop(queue q)隊頭執(zhí)行出隊操作elementtype frontappend(queue q)出隊并取隊頭元素elementtype rear(queue)取隊尾元素void inject (elementtype x,queue q)在隊尾執(zhí)行入隊操作void eject(queue q)在隊尾執(zhí)行出隊操作element type rearandeject（queue q）雙端隊列數(shù)據(jù)類型typedef struct qnodedatatype data;struct qnode *next;lqnode;typedef struct lqnode *front;lq

11、node *rear;lqueue; 鏈式隊列的操作實現(xiàn)： void queueinitiate(lqueue *q) /*初始化*/q-rear=null;q-rear=null;int queuenotempty(lqueue q) /*非空否*/if (q.front=null) return 0;else return 1; int queueappend (lqueue *q, datatype x) /*入隊列*/lqnode *p;if(p=(lqnode *)malloc(sizeof(lqnode)=null)printf (空間不足!);return 0;p-data=x;

12、p-next=null;if (q-rear!=null)q-rear-next=p; q-rear=p;if (q-front=null)q-front=p;return 1;int queuedelete(lqueue *q, datatype *d) /*出隊列*/lqnode *p;if (q-front=null)printf (隊列已經空了，沒有數(shù)據(jù)元素出隊列!n);return 0;else *d=q-front-data;p=q-front;q-front=q-front-next;if (q-front=null)q-rear=null;free (p);return 1;i

13、nt queueget(lqueue q,datatype *d) /*取對頭數(shù)據(jù)元素*/if (q.front=null)printf (隊列已經空了，沒有數(shù)據(jù)元素出隊列!n);return 0;else *d=q.front-data;return 1;void destroy (lqueue q) /*撤消動態(tài)申請空間 destroy(slnode *head)*/lqnode *p,*p1;p=q.front ;while(p!=null)p1=p;p=p-next;free(p1); 雙端隊列實現(xiàn)的功能如下： 1. 從隊列首輸入數(shù)據(jù) 2. 從隊列尾輸入數(shù)據(jù) 3. 從隊列首取數(shù)據(jù) 4.

14、 從隊列尾取數(shù)據(jù) 5. 隊列清空/ 取隊頭元素elementtype front(queue q) if(!isempty(q)return q-arrayq-front;error(empty queue);return 0;queueappend(lqueue *q,datatype x) /插入函數(shù)在隊頭執(zhí)行入隊操作void push(elementtype x, queue q) if(isfull(q)error(full queue);elseq-size+;q-front = prev(q-front, q);q-arrayq-front = x;queuedelete(lque

15、ue *q,datatype x)/刪除函數(shù)/ 在隊頭執(zhí)行出隊操作void pop(queue q) if(isempty(q)error( empty queue );elseq-size-;q-front = succ(q-front, q);/ 出隊并取隊頭元素elementtype frontandpop(queue q) elementtype x = 0;if(isempty(q)error(empty queue);elseq-size-;x = q-arrayq-front;q-front = succ(q-front, q);return x;/取隊尾元素elementtyp

16、e rear(queue q) if(!isempty(q)return q-arrayq-rear;error(empty queue);return 0;queueappend(lqueue *q,datatype x)/插入函數(shù)/在隊尾執(zhí)行入隊操作void inject(elementtype x, queue q) if(isfull(q)error(full queue);elseq-size+;q-rear = succ(q-rear, q);q-arrayq-rear = x;queuedelete(lqueue *q,datatype x) /刪除函數(shù)/在隊尾執(zhí)行出隊操作voi

17、d eject(queue q) if(isempty(q)error( empty queue );elseq-size-;q-rear = prev(q-rear, q);/ 出隊并取隊尾元素elementtype rearandeject(queue q) elementtype x = 0;if(isempty(q)error(empty queue);elseq-size-;x = q-arrayq-rear;q-rear = prev(q-rear, q);return x;*/函數(shù)的界面設計：int main() char s10; int c; printf(n); print

18、f(1. 從隊列首插入數(shù)據(jù)=按鍵1:n); printf(2. 從隊列尾插入數(shù)據(jù)=按鍵2:n); printf(3. 從隊列首刪除數(shù)據(jù)=按鍵3:n); printf(4. 從隊列尾刪除數(shù)據(jù)=按鍵4:n); printf(5. 隊列清空=按鍵5:n); printf(6. 退出=按鍵6:n); printf(n輸入選項1-6: n);/輸入1-6選項 do gets(s); c=atoi(s);if( c 6) printf(請輸入正確的代碼。n); while( c 6); return c;函數(shù)的大體設計，功能設計差不多就是這樣的，具體的創(chuàng)建工程，頭文件和源文件在前面的代碼里。整體來講，這些

19、代碼還是比較繁瑣，不夠簡潔。但這是我目前盡所能寫代碼了，很多地方自己也覺得很不滿意，很多算法還是寫不出來。慢慢改進。源代碼：#include #include #include #include typedef int datatype;#include queue.hint main() char s10; int c; printf(n); printf(1. 從隊列首輸入入數(shù)據(jù)=按鍵1:n); printf(2. 從隊列尾輸入數(shù)據(jù)=按鍵2:n); printf(3. 從隊列首取四個數(shù)據(jù)=按鍵3:n); printf(4. 從隊列尾取四個數(shù)據(jù)=按鍵4:n); printf(5. 隊列清空=

20、按鍵5:n); printf(6. 退出=按鍵6:n); printf(n輸入選項1-6: n);/輸入1-6選項 do gets(s); c=atoi(s);if( c 6) printf(請輸入正確的代碼。n); while( c 6); return c;/*queueinitiate(&myqueue); elementtype front(queue q) / 取隊頭元素 if(!isempty(q)return q-arrayq-front;error(empty queue);return 0;queueappend(lqueue *q,datatype x)/插入函數(shù)void

21、push(elementtype x, queue q) /在隊頭執(zhí)行入隊操作 if(isfull(q)error(full queue);elseq-size+;q-front = prev(q-front, q);q-arrayq-front = x;queuedelete(lqueue *q,datatype x)/刪除函數(shù)void pop(queue q) / 在隊頭執(zhí)行出隊操作 if(isempty(q)error( empty queue );elseq-size-;q-front = succ(q-front, q);elementtype frontandpop(queue q

22、) / 出隊并取隊頭元素 elementtype x = 0;if(isempty(q)error(empty queue);elseq-size-;x = q-arrayq-front;q-front = succ(q-front, q);return x;elementtype rear(queue q) /取隊尾元素 if(!isempty(q)return q-arrayq-rear;error(empty queue);return 0;queueappend(lqueue *q,datatype x)/插入函數(shù)void inject(elementtype x, queue q)

23、/在隊尾執(zhí)行入隊操作 if(isfull(q)error(full queue);elseq-size+;q-rear = succ(q-rear, q);q-arrayq-rear = x;queuedelete(lqueue *q,datatype x) /刪除函數(shù)void eject(queue q) /在隊尾執(zhí)行出隊操作 if(isempty(q)error( empty queue );elseq-size-;q-rear = prev(q-rear, q);elementtype rearandeject(queue q) / 出隊并取隊尾元素 elementtype x = 0;

24、if(isempty(q)error(empty queue);elseq-size-;x = q-arrayq-rear;q-rear = prev(q-rear, q);return x;*/typedef struct qnodedatatype data;struct qnode *next;lqnode;typedef struct lqnode *front;lqnode *rear;lqueue; void queueinitiate(lqueue *q) /*初始化*/q-rear=null;q-rear=null;int queuenotempty(lqueue q) /*非

25、空否*/if (q.front=null) return 0;else return 1; int queueappend (lqueue *q, datatype x) /*入隊列*/lqnode *p;if(p=(lqnode *)malloc(sizeof(lqnode)=null)printf (空間不足!);return 0;p-data=x;p-next=null;if (q-rear!=null)q-rear-next=p; q-rear=p;if (q-front=null)q-front=p;return 1;int queuedelete(lqueue *q, dataty

26、pe *d) /*出隊列*/lqnode *p;if (q-front=null)printf (隊列已經空了，沒有數(shù)據(jù)元素出隊列!n);return 0;else *d=q-front-data;p=q-front;q-front=q-front-next;if (q-front=null)q-rear=null;free (p);return 1;int queueget(lqueue q,datatype *d) /*取對頭數(shù)據(jù)元素*/if (q.front=null)printf (隊列已經空了，沒有數(shù)據(jù)元素出隊列!n);return 0;else *d=q.front-data;re

27、turn 1;void destroy (lqueue q) /*撤消動態(tài)申請空間 destroy(slnode *head)*/lqnode *p,*p1;p=q.front ;while(p!=null)p1=p;p=p-next;free(p1); 六。調試分析系統(tǒng)最后還是沒能玩成所有的功能，在調試過程中，所出現(xiàn)的問題大致如下：sddldl.cpp(37) : error c2065: myqueue : undeclared identifier為什么開始會出現(xiàn)呢。開始以為定義了，仔細看看才發(fā)現(xiàn)定義的不是myqueue,而是lqueue,g:sddldl.cpp(37) : error

28、 c2501: queueinitiate : missing storage-class or type specifiersqueueinitiate初始化整個雙端隊列,缺少missing storage-class or type specifiers 這現(xiàn)在都沒有理解,g:sddldl.cpp(37) : error c2373: queueinitiate : redefinition; different type modifiers g:sddlqueue.h(16) : see declaration of queueinitiate出現(xiàn)很多關于queueinitiate初始化

29、的問題，初始化時根據(jù)課本上的要求來弄得，出現(xiàn)這么多問題，始料未及。這可能和后面的定義有關g:sddldl.cpp(37) : error c2440: initializing : cannot convert from int * to int this conversion requires a reinterpret_cast, a c-style cast or function-style castg:sddldl.cpp(40) : warning c4518: int : storage-class or type specifier(s) unexpected here; ig

30、noredg:sddldl.cpp(40) : error c2146: syntax error : missing ; before identifier q缺少分號？但是在代碼中明明是有分號的，可能這個函數(shù)的寫法存在錯誤，但是反復調試，修改。還是存在問題g:sddldl.cpp(40) : error c2556: void _cdecl main(void) : overloaded function differs only by return type from int _cdecl main(void)這個不懂，問題出在哪里調試不出來g:sddldl.cpp(8) : see d

31、eclaration of maing:sddldl.cpp(40) : error c2371: main : redefinition; different basic types g:sddldl.cpp(8) : see declaration of maing:sddldl.cpp(40) : fatal error c1004: unexpected end of file found執(zhí)行 cl.exe 時出錯.sddl.exe - 1 error(s), 0 warning(s) 這是在最后的調試中出現(xiàn)的結果，在前面的調試中更加有一百多個錯誤，雖然反復調試，錯誤雖有減少，但是仍然

32、存在錯誤。最后調試的自己無法解決，問題的癥結還是沒能找出來。很多問題不單單是細節(jié)，正的的構造好像還是欠缺了，雖然一步一步的寫下來，但是連接性還是不夠，整個系統(tǒng)來講，如果有一個錯誤，那么整個系統(tǒng)就不能運算出來，對于這次試驗，我認識到了自己很大的不足，今后不單單要在程序算法上下工夫。更多的要會用好的方法來調試程序。因為有些錯誤仍然沒該過來，很多功能還是不能運行，因此，只能將后面的代碼注釋掉。前面的運行結果截圖如下： 后面本來預計是從隊頭輸入四值然后進行隊頭的排列，然后從隊尾輸入四個值進行排列。但是調試這關沒過，回天無力。 代碼測試的基本要求：代碼測試按照正常的系統(tǒng)使用條件：測試人員對本系統(tǒng)的逐個功能進行使用，填寫入測試報告。測試人員測試結束后，對所呈現(xiàn)bug，開發(fā)人員對系統(tǒng)中問題進行分析，確定故障的原因，并制定相應的對策。測試方法說明采用