《大數據結構隊列實驗報告材料》由會員分享，可在線閱讀，更多相關《大數據結構隊列實驗報告材料（58頁珍藏版）》請在裝配圖網上搜索。

1、word隊列實驗報告小組成員：xxxxxxxx日期：xxxxxxxx一、 需求分析xxx1. 鏈隊列1） 在本演示程序中，首先要鏈隊列添加一個頭結點，并判斷隊列是否為空，它只允許在表的一端進展插入，而在另一端刪除元素，允許插入的一段叫隊尾，允許刪除的一端如此為對頭，接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。最后銷毀隊列，釋放空間。2） 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“歡迎來到鏈隊列“元素入隊“元素出隊“銷毀隊列“清空隊列之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，相應的運算數據和顯示結果顯示在其后。3） 程序執(zhí)行的命令包括：歡迎來到鏈隊列

2、1輸出隊列長度2元素入隊3元素出隊4銷毀隊列5清空隊列6對頭元素7退出鏈隊列4） 測試數據入隊 1 2 3 4 5分別執(zhí)行“元素入隊“元素出隊“銷毀隊列“清空隊列等操作。2. 順序隊列1） 在本演示程序中，首先要順序隊列添加一個頭結點，并判斷隊列是否為空，它只允許在表的一端進展插入，而在另一端刪除元素，允許插入的一段叫隊尾，允許刪除的一端如此為對頭，接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。2） 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“歡迎來到鏈隊列“元素入隊“元素出隊“取得頭結點“輸出顯示之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，相應的運算數

3、據和顯示結果顯示在其后。3程序執(zhí)行的命令包括：歡迎來到順序隊列1入隊2出隊3判斷是否為空4取得頭結點5輸出顯示6退出順序隊列4測試數據入隊 1 2 3 4 5分別執(zhí)行“元素入隊“元素出隊等操作。3循環(huán)隊列1在本演示程序中，首先要順序隊列添加一個頭結點，并判斷隊列是否為空，初始化建空隊列時，令front=rear=0,每當插入新的隊列尾元素時，“尾指針增1；每當刪除隊列頭元素時，“頭指針增1。接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。2） 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“歡迎來到鏈隊列“元素入隊“元素出隊“取得頭結點“輸出顯示之后。由用戶在鍵盤上

4、輸入演示程序中規(guī)定的運算命令，相應的運算數據和顯示結果顯示在其后。3程序執(zhí)行的命令包括：歡迎來到循環(huán)隊列1入隊2出隊3判斷是否為空4取得頭結點5輸出顯示6退出順序隊列4測試數據入隊 1 2 3 4 5分別執(zhí)行“元素入隊“元素出隊等操作。二 概要設計(xxxx) 為實現上述算法，需要順序表的抽象數據類型，抽象數據類型定義如下：ADT Queue 數據對象：D= ai|aiElemSet, i=1,2,3.,n, n=0 數據關系: R= |ai-1,aiD,i=2,.,n 根本操作： InitQueue (&Q) 操作結果：構造一個空隊列。 DestroyQueue (&Q) 初始條件：隊列Q已

5、存在。 操作結果：隊列Q已被銷毀。 ClearQueue(&Q) 初始條件：隊列Q已存在。 操作結果：將Q清為空隊列。 QueueEmpty(Q) 初始條件：隊列Q已存在。 操作結果：假如Q為空隊列，如此返回TRUE,否如此FALSE。 QueueLength(Q) 初始條件：隊列Q已存在。 操作結果：返回Q元素的個數，即隊列的長度。 GetHead(Q,&e) 初始條件:Q為非空隊列。 操作結果：用e返回Q的隊頭元素。 EnQueue (&Q,e) 初始條件：隊列Q已存在。 操作結果：插入e返回Q的新的隊尾元素。DeQueue (&Q，&e) 初始條件：Q為非空隊列。 操作結果：刪除Q的隊頭

6、元素，并用e返回其值。 ADT Queuetypedef struct QNode QElemType; struct QNode *next;/指針域QNode,*QueuePtr;Typedef structQueuePtr front;QueuePtr rear;LinkQueue;Status InitQueue (LinkQueue&Q) /構造一個空隊列。 Status DestroyQueue (LinkQueue&Q) /銷毀隊列Q，Q不存在。 Status ClearQueue(LinkQueue&Q) /將Q清為空隊列。 Status QueueEmpty(LinkQueu

7、eQ) /假如Q為空隊列，如此返回TRUE,否如此FALSE。 int QueueLength(LinkQueueQ) /返回Q元素的個數，即隊列的長度。 Status GetHead(LinkQueueQ,QElemType&e) /假如隊列不為空，如此用e返回Q的隊頭元素，并返回OK;否如此返回ERROR。 Status EnQueue (LinkQueue&Q,QElemType e)/插入e返回Q的新的隊尾元素。Status DeQueue (LinkQueue&Q,QElemType&e) /假如隊列不空，如此刪除Q的隊頭元素，并用e返回其值，并返回OK;否如此返回ERROR。 三詳

8、細設計xxx1. 順序隊列的實現和運算1元素的類型typedef struct Datatype dataMAXSIZE; int front,rear; Squeue;2空的隊列的構造void InitSqueue(Squeue *p) /*初始化隊列*/ p-front=0; p-rear=0; 3元素的入隊int Ensqueue1(Squeue1 *q, Datatype e) /*入隊*/ if(q-rear+1)% MAXSIZE = q-front) printf(n隊列已滿n); return 0; 4元素的出隊int DeSqueue1(Squeue1 *q,Datatype

9、 *e) /*出隊*/ if (q-front=q-rear) printf(隊列已空,無法出隊!); return 0; *e=q-dataq-front; q-front=(q-front+1)%MAXSIZE; return 1; 5判斷隊列是否為空int QueueEmpty1(Squeue1 q) / 判斷是否為空 if (q.front=q.rear) return 1; else return 0; 6隊頭元素的取值的算法int Gethead1(Squeue1 *q,Datatype *e) / 取對頭元素 if (q-front=q-rear) printf(隊列已空，無法出

10、隊!); return 0; else *e=q-dataq-front; return 1; 7遍歷順序隊列的算法void display1(Squeue1 q) /遍歷順序對列 printf(此隊列數據為:n); if (q.front=q.rear) printf(此隊列為空!); else while(q.front front=q-rear=malloc(sizeof(QNode); if(!q-front) exit(1); q-front-next=NULL;2元素的入隊算法void EnQueue2(LinkQueue *q, QElemType e)/將元素e進隊 Queue

11、Ptr p;p=(QueuePtr)malloc(sizeof(QNode);/創(chuàng)建新節(jié)點if(!p)/如果內存分配成功exit(1);p-data=e;/初始化新節(jié)點數據為e p-next=NULL;q-rear-next=p;q-rear=p;3元素的出隊的算法int DeQueue2(LinkQueue *q,QElemType e)/隊頭結點出隊,將出隊的元素存入eQueuePtr p;if(q-front=q-rear)/隊列為空return 0;p=q-front-next;/初始化temp為要出隊的結點指針if(q-front-next=q-rear)/要出隊的結點為最后一個結點

12、q-rear=q-front;e=p-data;/要出隊的數據元素為eq-front-next=p-next;/使下一個結點變?yōu)閷︻^free(p);/刪除要出隊的結點return e;4隊列的長度算法void QueueLength2(LinkQueue *q)/返回隊列長度QueuePtr p;int i=0; p=q-front-next;while(p)+i;p=p-next;printf(鏈隊列長度為:%dn,i);5隊列的銷毀void DestroyQueue2(LinkQueue *q)while(q-front)q-rear=q-front-next;free(q-front);

13、q-front=q-rear;if(!q-rear)free(q-rear);free(q-front);6隊列的輸出算法void output2(LinkQueue *q)/輸出隊列QueuePtr p;p=q-front-next;printf(鏈隊列元素依次為:);while(p)printf(%d-,p-data);p=p-next;printf(n);7隊列的清空的算法void Clear2(LinkQueue *q)/清空隊列QueuePtr temp=q-front-next;while(temp)QueuePtr tp=temp;temp=temp-next;free(tp);

14、temp=q-front;q-front=q-rear=NULL;free(temp);8返回對頭元素的算法int GetHead2(LinkQueue *q, int *e)/返回對頭結點元素，存入eif(q-front=q-rear)return 0;*e=q-front-next-data;return 1;3. 循環(huán)隊列的實現和運算1隊列的初始化算法void InitSqueue3(Squeue3 *p) /*初始化隊列*/ p-base=(Datatype *)malloc(sizeof(Datatype)* MAXSIZE); p-front=0; p-rear=0; 2入隊的算法

15、int Ensqueue3(Squeue3 *q, Datatype e) /*入隊*/ if(q-rear+1)% MAXSIZE = q-front) printf(n隊列已滿n); return 0; else q-baseq-rear=e;/*將接收到得值付給隊尾所指的節(jié)點*/ q-rear=(q-rear+1) % MAXSIZE;/*隊尾向后移一位完成入隊*/ return 1; 3出隊的算法int DeSqueue3(Squeue3 *q,Datatype *e) /*出隊*/ if (q-front=q-rear) printf(隊列已空,無法出隊!); return 0; *

16、e=q-baseq-front; q-front=(q-front+1)%MAXSIZE; return 1; 4判斷隊列是否為空的算法int QueueEmpty3(Squeue3 q) / 判斷是否為空 if (q.front=q.rear) return 1; else return 0; 5對頭元素的返還的算法int Gethead3(Squeue3 *q,Datatype *e) / 取對頭元素 if (q-front=q-rear) printf(隊列已空，無法出隊!); return 0; else *e=q-baseq-front; return 1; 6遍歷循環(huán)隊列的算法vo

17、id display3(Squeue3 *q) /遍歷循環(huán)對列 int tail; tail=q-front; printf(此隊列數據為:n); if (q-front=q-rear) printf(此隊列為空!); else while(tail!=q-rear) printf(%dt, q-basetail); tail=(tail+1)%MAXSIZE; printf(n); void main() int choice;Datatype e1;int i1,a1,x1,s1,j1; /順序隊列定義的量 int e2,i2,n2,s2,a2; /鏈隊列定義的量int i3,a3,x3,

18、s3,j3; /循環(huán)隊列定義的量Datatype e3;Squeue1 Q1; /* LinkQueue q;/*Squeue3 Q;/* choice=-1; Begin(); while(choice!=0) scanf(%d,&choice); switch(choice) case 1:/順序隊列 system(cls); InitSqueue1(&Q1); printf(創(chuàng)建隊列完成!n); printf(請輸入數據個數j1=); scanf(%d,&j1); for(i1=1; i1=j1;i1+) /輸入的數據個數不要超過MAXSIZE,多了的局部沒有插入隊列 printf(請輸

19、入第%d個數據:,i1); scanf(%d,&a1); Ensqueue1(&Q1,a1); printf(對頭為:%dn,Q1.dataQ1.front); printf(隊尾為:%dn,Q1.dataQ1.front+j1-1); display1(Q1); s1=-1; start1(); while(s1!=0) scanf(%d,&s1); switch(s1) case 0: system(cls); choice=-1; Begin();break; case 1: system(cls); printf(請輸入入隊元素:n ); scanf(%d,&x1); Ensqueue

20、1(&Q1,x1); display1(Q1); s1=-1; start1(); break; case 2: system(cls); DeSqueue1(&Q1,&e1); display1(Q1); s1=-1; start1(); break; case 3: system(cls); if(QueueEmpty1(Q1) printf(此隊列為空!n); else printf(此隊列不為空!n); s1=-1; start1(); break; case 4: system(cls); Gethead1(&Q1,&e1); printf(對頭元素為:%dn,e1); s1=-1;

21、 start1(); break; case 5: system(cls); display1(Q1); s1=-1; start1(); break; /switch/while /case1 break;/* case 2: system(cls); InitQueue2(&q); printf(創(chuàng)建隊列完成!n); printf(輸入將建立鏈隊列元素的個數:n2=); scanf(%d,&n2); printf(請輸入隊列的元素：n); for(i2=1;i2=n2;i2+) printf(請輸入第%d個元素:,i2); scanf(%d,&e2); EnQueue2(&q,e2); a

22、2=-1; start2(); while(a2!=0) scanf(%d,&a2); switch(a2) case 1:system(cls); QueueLength2(&q); a2=-1; start2(); break;case 2:system(cls);printf(請輸入入隊元素:);scanf(%d,&e2); EnQueue2(&q,e2);output2(&q); a2=-1; start2(); break;case 3: system(cls); e2=DeQueue2(&q,e2);output2(&q);printf(出隊元素為:%dn,e2); a2=-1;

23、start2();break;case 4:DestroyQueue2(&q); printf(隊列已銷毀!n);a2=0; system(cls); choice=-1; Begin();break;case 5:Clear2(&q); printf(隊列已清空n);a2=0; system(cls); choice=-1; Begin();break;case 6:system(cls); GetHead2(&q,&e2); printf(隊頭元素為:%dn,e2); s2=-1; start2(); break;case 0: system(cls); choice=-1; Begin(

24、);break;/switch/while /case2 break;/* case 3: system(cls); InitSqueue3(&Q); printf(創(chuàng)建隊列完成!n); printf(請輸入數據個數j3=); scanf(%d,&j3); for(i3=1; i3=j3;i3+) /輸入的數據個數不要超過MAXSIZE,多了的局部沒有插入隊列 printf(請輸入第%d個數據:,i3); scanf(%d,&a3); Ensqueue3(&Q,a3); printf(對頭為:%dn,Q.baseQ.front); printf(隊尾為:%dn,Q.baseQ.front+j3

25、-1); display3(&Q); s3=-1; start3(); while(s3!=0) scanf(%d,&s3); switch(s3) case 0: system(cls); choice=-1; Begin(); break; case 1: system(cls); printf(請輸入入隊元素:n ); scanf(%d,&x3); Ensqueue3(&Q,x3); display3(&Q); s3=-1; start3(); break; case 2: system(cls); DeSqueue3(&Q,&e3); display3(&Q); s3=-1; star

26、t3(); break; case 3: system(cls); if(QueueEmpty3(Q) printf(此隊列為空!n); else printf(此隊列不為空!n); s3=-1; start3(); break; case 4: system(cls); Gethead3(&Q,&e3); printf(對頭元素為:%dn,e3); s3=-1; start3(); break; case 5: system(cls); display3(&Q); s3=-1; start3(); break; /switch /while /case 3 break; case 0: pr

27、intf( 謝謝使用!n); break;/*/switch/while /main四 調試分析xxx順序隊列1. 編譯并調試，運行程序。2. 設計測試用例，分析測試結果，以驗證所完成的系統是否達到預期效果。3.判斷隊列是否為空。隊列是否為空的標志就是隊頭指針和隊尾指針是否同時指向隊列中的同一個位置，即隊頭指針和隊尾指針是否相等。4.隊列滿時候不能入隊列，否如此會出現溢出現象。即先要判斷隊列是否已經已滿，因為隊尾指針的最大值是MAXQSIZE，所以通過檢查隊尾指針rear是否等于MAXQSIZE來判斷隊列是否已滿。在刪除隊首元素時，應首先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空。5.在元

28、素出隊操作，先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空，空時不能操作，這是要注意的。6.程序滿足了本次試驗的目的和任務要求，可以進展人機交互，在后來的程序中將會做些改良，以增強人機交互性。7.本程序存在較多不足，如有問題，參考用戶手冊。8.在程序語句中，原本使用了大量的生僻的函數名，經過改良，目前使用都是通俗易懂的函數名稱，方便用戶理解。鏈隊列1.編譯并調試，運行程序。2.設計測試用例，分析測試結果，以驗證所完成的系統是否達到預期效果。3.要注意設定一個在鏈隊列添加一個頭結點并令指針指向頭結點。同時，刪除不可以在最后面進展刪除，但是插入可以最后一個進展插入，這點需要注意4.需要分別指向隊

29、頭和隊尾的指針。5.程序滿足了本次試驗的目的和任務要求，可以進展人機交互，在后來的程序中將會做些改良，以增強人機交互性。6.本程序存在較多不足，如有問題，參考用戶手冊。7.在程序語句中，原本使用了大量的生僻的函數名，經過改良，目前使用都是通俗易懂的函數名稱，方便用戶理解。循環(huán)隊列1.編譯并調試，運行程序。2.設計測試用例，分析測試結果，以驗證所完成的系統是否達到預期效果。3.為了防止順序隊列造成的“假溢出現象，我們通常采用順序循環(huán)隊列實現隊列的順序存儲。4.隊頭指針和對尾指針與隊列元素之間關系和順序隊列一樣，不變。5.先判斷隊列是否為空。就是看隊頭指針和隊尾指針是否同時指向隊列中的同一個位置，

30、即隊頭指針和隊尾指針是否相等，空時不能操作，這是要注意的。6.在將元素插入到隊列之前首先要判斷隊列是否已經已滿，根據順序循環(huán)隊列隊滿條件front=(rear+1)%MAXQSIZE來判斷隊列是否已滿。在刪除隊首元素時，應首先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空。6.程序滿足了本次試驗的目的和任務要求，可以進展人機交互，在后來的程序中將會做些改良，以增強人機交互性。7.本程序存在較多不足，如有問題，參考用戶手冊。8.在程序語句中，原本使用了大量的生僻的函數名，經過改良，目前使用都是通俗易懂的函數名稱，方便用戶理解。五、用戶手冊(xx)(1) 本程序的運行環(huán)境為DOS操作系統，執(zhí)行文件

31、名為：j.exe.(2) 進入演示程序后即顯示文本方式的用戶界面，輸入元素1,2,3,4,5創(chuàng)建隊列。（3） 根據提示，選擇操作2執(zhí)行元素入隊操作。回車， 輸入入隊元素0，回車，將0插入到隊列中。4選擇操作3執(zhí)行元素出隊操作，回車，隊首元素1出隊。5選擇操作1執(zhí)行輸出隊列長度操作，回車，輸出隊列長度為5.6選擇操作5執(zhí)行清空隊列操作，回車，清空。（7） 選擇操作6執(zhí)行輸出隊頭元素操作，回車，輸出元素2。2. 順序隊列1創(chuàng)建隊列，輸入數據 1,2,3,4,5.（2）3選擇操作2，執(zhí)行出隊操作。隊首元素1出隊.4選擇操作3，判斷對是否為空（5） 選擇操作4，輸出對頭元素2.（6） 選擇操作5，顯示

32、隊列元素 3、循環(huán)隊列1創(chuàng)建隊列，輸入數據 1,2,3,4,5. 23選擇操作2，執(zhí)行出隊操作。隊首元素1出隊.（3） 選擇操作3，判斷對是否為空（5） 選擇操作4，輸出對頭元素2.（6） 選擇操作5，顯示隊列元素為,2,3,4,5,0六測試結果xxx1. 順序隊列的實現和運算1輸入1即可進展進入到順序隊列2順序隊列的建立，輸入元素的個數為5，輸入的數據分別為1 ，2 ， 3 ，4 ，5 ，對頭為1，隊尾為5，此時隊列的數據為1 2 3 4 53輸入2即可進展入隊運算，輸入的入隊元素為0，此時的隊列的數據為1 2 3 4 5 0 4輸入3即可進展判斷隊列的是否為空，如如下圖：5輸入4即可進展去

33、的對頭元素的算法，如如下圖所示：6此時的隊列的數據為2 3 4 5 0，如如下圖：7輸入0即可退出順序隊列，如如下圖：8輸入3即可進展順序隊列的算法，如如下圖所示：9輸入1即可進展相應的入隊運算，如如下圖所示：10輸入2即可進展隊列的出隊運算，如如下圖所示：11輸入3即可判斷順序隊列是否為空的算法，如如下圖所示：12輸入4即可進展去的頭結點的運算，如如下圖所示：13輸入5即可進展隊列的輸出顯示的運算，如如下圖所示：14輸入0即可進展退出順序隊列的算法，如如下圖所示：2. 鏈式隊列的實現和運算1隊列的建立以與隊列的個數輸入為5，輸入的數據分別為1 ，2 ，3 ，4 ，5.如如下圖：2輸入2即可進

34、入到元素的入隊運算，輸入入隊的元素的為0，輸入3即可進展相應的元素的出隊運算，出隊元素為1.如如下圖：3如此此時的隊列的長度為5，輸入4即可進展隊列的銷毀以與輸入5即可進展隊列的清空運算，如如下圖：4輸入6即可進展輸出隊列的對頭元素，輸入0即可進展退出鏈隊列的運算3循環(huán)隊列的實現和運算1輸入3即可進展循環(huán)隊列的操作，輸入5個數據，它們分別為1 2 3 4 5，輸入1，即可進展入隊操作，輸入入隊的元素為0，如此此時的數據為1 2 3 4 5 0，如如下圖所示：2輸入2即可進展出隊運算，如如下圖所示：3輸入3即可進展判斷隊列的是否為空，如如下圖所示：4輸入4即可進展取得對頭元素，如如下圖所示：5)

35、輸入5即可進展輸出所有的數據顯示，如如下圖所示：七心得體會xx隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端front進展刪除操作，而在表的后端rear進展插入操作，和棧一樣，隊列是一種操作受限制的線性表。進展插入操作的端稱為隊尾，進展刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。在隊列這種數據結構中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將是最后被刪除的元素，因此隊列又稱為“先進先出 的線性表。注意的是為了防止順序隊列造成的“假溢出現象，我們通常采用順序循環(huán)隊列實現隊列的順序存儲。還有要注意的是在C語言中不能用動態(tài)分配的一維數組來實現循環(huán)隊列，如果用戶的應用程序中設有循環(huán)隊列，如此必須為它設定一個最大隊列長度；假如用戶無法估計所用隊列的最大長度，如此宜采用鏈式隊列。58 / 58