大數(shù)據(jù)結(jié)構(gòu)隊列實驗報告材料

word隊列實驗報告小組成員：xxxxxxxx日期：xxxxxxxx一、 需求分析xxx1. 鏈隊列1） 在本演示程序中，首先要鏈隊列添加一個頭結(jié)點，并判斷隊列是否為空，它只允許在表的一端進展插入，而在另一端刪除元素，允許插入的一段叫隊尾，允許刪除的一端如此為對頭，接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。最后銷毀隊列，釋放空間。2） 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“歡迎來到鏈隊列“元素入隊“元素出隊“銷毀隊列“清空隊列之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，相應(yīng)的運算數(shù)據(jù)和顯示結(jié)果顯示在其后。3） 程序執(zhí)行的命令包括：歡迎來到鏈隊列1輸出隊列長度2元素入隊3元素出隊4銷毀隊列5清空隊列6對頭元素7退出鏈隊列4） 測試數(shù)據(jù)入隊 1 2 3 4 5分別執(zhí)行“元素入隊“元素出隊“銷毀隊列“清空隊列等操作。2. 順序隊列1） 在本演示程序中，首先要順序隊列添加一個頭結(jié)點，并判斷隊列是否為空，它只允許在表的一端進展插入，而在另一端刪除元素，允許插入的一段叫隊尾，允許刪除的一端如此為對頭，接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。2） 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“歡迎來到鏈隊列“元素入隊“元素出隊“取得頭結(jié)點“輸出顯示之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，相應(yīng)的運算數(shù)據(jù)和顯示結(jié)果顯示在其后。3程序執(zhí)行的命令包括：歡迎來到順序隊列1入隊2出隊3判斷是否為空4取得頭結(jié)點5輸出顯示6退出順序隊列4測試數(shù)據(jù)入隊 1 2 3 4 5分別執(zhí)行“元素入隊“元素出隊等操作。3循環(huán)隊列1在本演示程序中，首先要順序隊列添加一個頭結(jié)點，并判斷隊列是否為空，初始化建空隊列時，令front=rear=0,每當插入新的隊列尾元素時，“尾指針增1；每當刪除隊列頭元素時，“頭指針增1。接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。2） 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“歡迎來到鏈隊列“元素入隊“元素出隊“取得頭結(jié)點“輸出顯示之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，相應(yīng)的運算數(shù)據(jù)和顯示結(jié)果顯示在其后。3程序執(zhí)行的命令包括：歡迎來到循環(huán)隊列1入隊2出隊3判斷是否為空4取得頭結(jié)點5輸出顯示6退出順序隊列4測試數(shù)據(jù)入隊 1 2 3 4 5分別執(zhí)行“元素入隊“元素出隊等操作。二 概要設(shè)計(xxxx) 為實現(xiàn)上述算法，需要順序表的抽象數(shù)據(jù)類型，抽象數(shù)據(jù)類型定義如下：ADT Queue 數(shù)據(jù)對象：D= ai|aiElemSet, i=1,2,3.,n, n>=0 數(shù)據(jù)關(guān)系: R= <ai-1,ai>|ai-1,aiD,i=2,.,n 根本操作： InitQueue (&Q) 操作結(jié)果：構(gòu)造一個空隊列。 DestroyQueue (&Q) 初始條件：隊列Q已存在。 操作結(jié)果：隊列Q已被銷毀。 ClearQueue(&Q) 初始條件：隊列Q已存在。 操作結(jié)果：將Q清為空隊列。 QueueEmpty(Q) 初始條件：隊列Q已存在。 操作結(jié)果：假如Q為空隊列，如此返回TRUE,否如此FALSE。 QueueLength(Q) 初始條件：隊列Q已存在。 操作結(jié)果：返回Q元素的個數(shù)，即隊列的長度。 GetHead(Q,&e) 初始條件:Q為非空隊列。 操作結(jié)果：用e返回Q的隊頭元素。 EnQueue (&Q,e) 初始條件：隊列Q已存在。 操作結(jié)果：插入e返回Q的新的隊尾元素。DeQueue (&Q，&e) 初始條件：Q為非空隊列。 操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。 ADT Queuetypedef struct QNode QElemType; struct QNode *next;/指針域QNode,*QueuePtr;Typedef structQueuePtr front;QueuePtr rear;LinkQueue;Status InitQueue (LinkQueue&Q) /構(gòu)造一個空隊列。 Status DestroyQueue (LinkQueue&Q) /銷毀隊列Q，Q不存在。 Status ClearQueue(LinkQueue&Q) /將Q清為空隊列。 Status QueueEmpty(LinkQueueQ) /假如Q為空隊列，如此返回TRUE,否如此FALSE。 int QueueLength(LinkQueueQ) /返回Q元素的個數(shù)，即隊列的長度。 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。 三詳細設(shè)計xxx1. 順序隊列的實現(xiàn)和運算1元素的類型typedef struct Datatype dataMAXSIZE; int front,rear; Squeue;2空的隊列的構(gòu)造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 *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("隊列已空，無法出隊!"); return 0; else *e=q->dataq->front; return 1; 7遍歷順序隊列的算法void display1(Squeue1 q) /遍歷順序?qū)α?printf("此隊列數(shù)據(jù)為:n"); if (q.front=q.rear) printf("此隊列為空!"); else while(q.front < q.rear) printf("%dt", q.dataq.front); q.front=(q.front+1)%MAXSIZE; printf("n"); 2. 鏈式隊列的實現(xiàn)和運算1構(gòu)造空隊列的算法void InitQueue2(LinkQueue *q) / 構(gòu)造一個空隊列Q q->front=q->rear=malloc(sizeof(QNode); if(!q->front) exit(1); q->front->next=NULL;2元素的入隊算法void EnQueue2(LinkQueue *q, QElemType e)/將元素e進隊 QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);/創(chuàng)建新節(jié)點if(!p)/如果內(nèi)存分配成功exit(1);p->data=e;/初始化新節(jié)點數(shù)據(jù)為e p->next=NULL;q->rear->next=p;q->rear=p;3元素的出隊的算法int DeQueue2(LinkQueue *q,QElemType e)/隊頭結(jié)點出隊,將出隊的元素存入eQueuePtr p;if(q->front=q->rear)/隊列為空return 0;p=q->front->next;/初始化temp為要出隊的結(jié)點指針if(q->front->next=q->rear)/要出隊的結(jié)點為最后一個結(jié)點q->rear=q->front;e=p->data;/要出隊的數(shù)據(jù)元素為eq->front->next=p->next;/使下一個結(jié)點變?yōu)閷︻^free(p);/刪除要出隊的結(jié)點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);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);temp=q->front;q->front=q->rear=NULL;free(temp);8返回對頭元素的算法int GetHead2(LinkQueue *q, int *e)/返回對頭結(jié)點元素，存入eif(q->front=q->rear)return 0;*e=q->front->next->data;return 1;3. 循環(huán)隊列的實現(xiàn)和運算1隊列的初始化算法void InitSqueue3(Squeue3 *p) /*初始化隊列*/ p->base=(Datatype *)malloc(sizeof(Datatype)* MAXSIZE); p->front=0; p->rear=0; 2入隊的算法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; *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)隊列的算法void display3(Squeue3 *q) /遍歷循環(huán)對列 int tail; tail=q->front; printf("此隊列數(shù)據(jù)為: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,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("請輸入數(shù)據(jù)個數(shù)j1="); scanf("%d",&j1); for(i1=1; i1<=j1;i1+) /輸入的數(shù)據(jù)個數(shù)不要超過MAXSIZE,多了的局部沒有插入隊列 printf("請輸入第%d個數(shù)據(jù):",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); Ensqueue1(&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; 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("輸入將建立鏈隊列元素的個數(shù):n2="); scanf("%d",&n2); printf("請輸入隊列的元素：n"); for(i2=1;i2<=n2;i2+) printf("請輸入第%d個元素:",i2); scanf("%d",&e2); EnQueue2(&q,e2); a2=-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; 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();break;/switch/while /case2 break;/* case 3: system("cls"); InitSqueue3(&Q); printf("創(chuàng)建隊列完成!n"); printf("請輸入數(shù)據(jù)個數(shù)j3="); scanf("%d",&j3); for(i3=1; i3<=j3;i3+) /輸入的數(shù)據(jù)個數(shù)不要超過MAXSIZE,多了的局部沒有插入隊列 printf("請輸入第%d個數(shù)據(jù):",i3); scanf("%d",&a3); Ensqueue3(&Q,a3); printf("對頭為:%dn",Q.baseQ.front); printf("隊尾為:%dn",Q.baseQ.front+j3-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; start3(); 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: printf(" 謝謝使用!n"); break;/*/switch/while /main四 調(diào)試分析xxx順序隊列1. 編譯并調(diào)試，運行程序。2. 設(shè)計測試用例，分析測試結(jié)果，以驗證所完成的系統(tǒng)是否達到預(yù)期效果。3.判斷隊列是否為空。隊列是否為空的標志就是隊頭指針和隊尾指針是否同時指向隊列中的同一個位置，即隊頭指針和隊尾指針是否相等。4.隊列滿時候不能入隊列，否如此會出現(xiàn)溢出現(xiàn)象。即先要判斷隊列是否已經(jīng)已滿，因為隊尾指針的最大值是MAXQSIZE，所以通過檢查隊尾指針rear是否等于MAXQSIZE來判斷隊列是否已滿。在刪除隊首元素時，應(yīng)首先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空。5.在元素出隊操作，先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空，空時不能操作，這是要注意的。6.程序滿足了本次試驗的目的和任務(wù)要求，可以進展人機交互，在后來的程序中將會做些改良，以增強人機交互性。7.本程序存在較多不足，如有問題，參考用戶手冊。8.在程序語句中，原本使用了大量的生僻的函數(shù)名，經(jīng)過改良，目前使用都是通俗易懂的函數(shù)名稱，方便用戶理解。鏈隊列1.編譯并調(diào)試，運行程序。2.設(shè)計測試用例，分析測試結(jié)果，以驗證所完成的系統(tǒng)是否達到預(yù)期效果。3.要注意設(shè)定一個在鏈隊列添加一個頭結(jié)點并令指針指向頭結(jié)點。同時，刪除不可以在最后面進展刪除，但是插入可以最后一個進展插入，這點需要注意4.需要分別指向隊頭和隊尾的指針。5.程序滿足了本次試驗的目的和任務(wù)要求，可以進展人機交互，在后來的程序中將會做些改良，以增強人機交互性。6.本程序存在較多不足，如有問題，參考用戶手冊。7.在程序語句中，原本使用了大量的生僻的函數(shù)名，經(jīng)過改良，目前使用都是通俗易懂的函數(shù)名稱，方便用戶理解。循環(huán)隊列1.編譯并調(diào)試，運行程序。2.設(shè)計測試用例，分析測試結(jié)果，以驗證所完成的系統(tǒng)是否達到預(yù)期效果。3.為了防止順序隊列造成的“假溢出現(xiàn)象，我們通常采用順序循環(huán)隊列實現(xiàn)隊列的順序存儲。4.隊頭指針和對尾指針與隊列元素之間關(guān)系和順序隊列一樣，不變。5.先判斷隊列是否為空。就是看隊頭指針和隊尾指針是否同時指向隊列中的同一個位置，即隊頭指針和隊尾指針是否相等，空時不能操作，這是要注意的。6.在將元素插入到隊列之前首先要判斷隊列是否已經(jīng)已滿，根據(jù)順序循環(huán)隊列隊滿條件front=(rear+1)%MAXQSIZE來判斷隊列是否已滿。在刪除隊首元素時，應(yīng)首先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空。6.程序滿足了本次試驗的目的和任務(wù)要求，可以進展人機交互，在后來的程序中將會做些改良，以增強人機交互性。7.本程序存在較多不足，如有問題，參考用戶手冊。8.在程序語句中，原本使用了大量的生僻的函數(shù)名，經(jīng)過改良，目前使用都是通俗易懂的函數(shù)名稱，方便用戶理解。五、用戶手冊(xx)(1) 本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件名為：j.exe.(2) 進入演示程序后即顯示文本方式的用戶界面，輸入元素1,2,3,4,5創(chuàng)建隊列。（3） 根據(jù)提示，選擇操作2執(zhí)行元素入隊操作?；剀?， 輸入入隊元素0，回車，將0插入到隊列中。4選擇操作3執(zhí)行元素出隊操作，回車，隊首元素1出隊。5選擇操作1執(zhí)行輸出隊列長度操作，回車，輸出隊列長度為5.6選擇操作5執(zhí)行清空隊列操作，回車，清空。（7） 選擇操作6執(zhí)行輸出隊頭元素操作，回車，輸出元素2。2. 順序隊列1創(chuàng)建隊列，輸入數(shù)據(jù) 1,2,3,4,5.（2）3選擇操作2，執(zhí)行出隊操作。隊首元素1出隊.4選擇操作3，判斷對是否為空（5） 選擇操作4，輸出對頭元素2.（6） 選擇操作5，顯示隊列元素 3、循環(huán)隊列1創(chuàng)建隊列，輸入數(shù)據(jù) 1,2,3,4,5. 23選擇操作2，執(zhí)行出隊操作。隊首元素1出隊.（3） 選擇操作3，判斷對是否為空（5） 選擇操作4，輸出對頭元素2.（6） 選擇操作5，顯示隊列元素為,2,3,4,5,0六測試結(jié)果xxx1. 順序隊列的實現(xiàn)和運算1輸入1即可進展進入到順序隊列2順序隊列的建立，輸入元素的個數(shù)為5，輸入的數(shù)據(jù)分別為1 ，2 ， 3 ，4 ，5 ，對頭為1，隊尾為5，此時隊列的數(shù)據(jù)為1 2 3 4 53輸入2即可進展入隊運算，輸入的入隊元素為0，此時的隊列的數(shù)據(jù)為1 2 3 4 5 0 4輸入3即可進展判斷隊列的是否為空，如如下圖：5輸入4即可進展去的對頭元素的算法，如如下圖所示：6此時的隊列的數(shù)據(jù)為2 3 4 5 0，如如下圖：7輸入0即可退出順序隊列，如如下圖：8輸入3即可進展順序隊列的算法，如如下圖所示：9輸入1即可進展相應(yīng)的入隊運算，如如下圖所示：10輸入2即可進展隊列的出隊運算，如如下圖所示：11輸入3即可判斷順序隊列是否為空的算法，如如下圖所示：12輸入4即可進展去的頭結(jié)點的運算，如如下圖所示：13輸入5即可進展隊列的輸出顯示的運算，如如下圖所示：14輸入0即可進展退出順序隊列的算法，如如下圖所示：2. 鏈式隊列的實現(xiàn)和運算1隊列的建立以與隊列的個數(shù)輸入為5，輸入的數(shù)據(jù)分別為1 ，2 ，3 ，4 ，5.如如下圖：2輸入2即可進入到元素的入隊運算，輸入入隊的元素的為0，輸入3即可進展相應(yīng)的元素的出隊運算，出隊元素為1.如如下圖：3如此此時的隊列的長度為5，輸入4即可進展隊列的銷毀以與輸入5即可進展隊列的清空運算，如如下圖：4輸入6即可進展輸出隊列的對頭元素，輸入0即可進展退出鏈隊列的運算3循環(huán)隊列的實現(xiàn)和運算1輸入3即可進展循環(huán)隊列的操作，輸入5個數(shù)據(jù)，它們分別為1 2 3 4 5，輸入1，即可進展入隊操作，輸入入隊的元素為0，如此此時的數(shù)據(jù)為1 2 3 4 5 0，如如下圖所示：2輸入2即可進展出隊運算，如如下圖所示：3輸入3即可進展判斷隊列的是否為空，如如下圖所示：4輸入4即可進展取得對頭元素，如如下圖所示：5)輸入5即可進展輸出所有的數(shù)據(jù)顯示，如如下圖所示：七心得體會xx隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端front進展刪除操作，而在表的后端rear進展插入操作，和棧一樣，隊列是一種操作受限制的線性表。進展插入操作的端稱為隊尾，進展刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。在隊列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將是最后被刪除的元素，因此隊列又稱為“先進先出 的線性表。注意的是為了防止順序隊列造成的“假溢出現(xiàn)象，我們通常采用順序循環(huán)隊列實現(xiàn)隊列的順序存儲。還有要注意的是在C語言中不能用動態(tài)分配的一維數(shù)組來實現(xiàn)循環(huán)隊列，如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊列，如此必須為它設(shè)定一個最大隊列長度；假如用戶無法估計所用隊列的最大長度，如此宜采用鏈式隊列。58 / 58