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

..隊列實驗報告小組成員：********日期：********需求分析〔**x〕鏈隊列在本演示程序中，首先要鏈隊列添加一個頭結(jié)點，并判斷隊列是否為空，它只允許在表的一端進(jìn)展插入，而在另一端刪除元素，允許插入的一段叫隊尾，允許刪除的一端那么為對頭，接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。最后銷毀隊列，釋放空間。演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示"歡送來到鏈隊列〞"元素入隊〞"元素出隊〞"銷毀隊列〞"清空隊列〞之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，相應(yīng)的運算數(shù)據(jù)和顯示結(jié)果顯示在其后。程序執(zhí)行的命令包括：歡送來到鏈隊列1輸出隊列長度2元素入隊3元素出隊4銷毀隊列5清空隊列6對頭元素7退出鏈隊列測試數(shù)據(jù)入隊12345分別執(zhí)行"元素入隊〞"元素出隊〞"銷毀隊列〞"清空隊列〞等操作。順序隊列在本演示程序中，首先要順序隊列添加一個頭結(jié)點，并判斷隊列是否為空，它只允許在表的一端進(jìn)展插入，而在另一端刪除元素，允許插入的一段叫隊尾，允許刪除的一端那么為對頭，接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示"歡送來到鏈隊列〞"元素入隊〞"元素出隊〞"取得頭結(jié)點〞"輸出顯示〞之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，相應(yīng)的運算數(shù)據(jù)和顯示結(jié)果顯示在其后。3〕程序執(zhí)行的命令包括：歡送來到順序隊列1入隊2出隊3判斷是否為空4取得頭結(jié)點5輸出顯示6退出順序隊列4〕測試數(shù)據(jù)入隊12345分別執(zhí)行"元素入隊〞"元素出隊〞等操作。3循環(huán)隊列1〕在本演示程序中，首先要順序隊列添加一個頭結(jié)點，并判斷隊列是否為空，初始化建空隊列時，令front=rear=0,每當(dāng)插入新的隊列尾元素時，"尾指針增1〞；每當(dāng)刪除隊列頭元素時，"頭指針增1〞。接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示"歡送來到鏈隊列〞"元素入隊〞"元素出隊〞"取得頭結(jié)點〞"輸出顯示〞之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，相應(yīng)的運算數(shù)據(jù)和顯示結(jié)果顯示在其后。3〕程序執(zhí)行的命令包括：歡送來到循環(huán)隊列1入隊2出隊3判斷是否為空4取得頭結(jié)點5輸出顯示6退出順序隊列4〕測試數(shù)據(jù)入隊12345分別執(zhí)行"元素入隊〞"元素出隊〞等操作。概要設(shè)計(****)⒈為實現(xiàn)上述算法，需要順序表的抽象數(shù)據(jù)類型，抽象數(shù)據(jù)類型定義如下：ADTQueue{數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,3...,n,n>=0}數(shù)據(jù)關(guān)系:R={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}根本操作：InitQueue(&Q)操作結(jié)果：構(gòu)造一個空隊列。DestroyQueue(&Q)初始條件：隊列Q已存在。操作結(jié)果：隊列Q已被銷毀。ClearQueue(&Q)初始條件：隊列Q已存在。操作結(jié)果：將Q清為空隊列。QueueEmpty(Q)初始條件：隊列Q已存在。操作結(jié)果：假設(shè)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返回其值。}ADTQueue2.單鏈隊列typedefstructQNode{QElemType;structQNode*next;//指針域}QNode,*QueuePtr;Typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;StatusInitQueue(LinkQueue&Q)//構(gòu)造一個空隊列。StatusDestroyQueue(LinkQueue&Q)//銷毀隊列Q，Q不存在。StatusClearQueue(LinkQueue&Q)//將Q清為空隊列。StatusQueueEmpty(LinkQueueQ)//假設(shè)Q為空隊列，那么返回TRUE,否那么FALSE。intQueueLength(LinkQueueQ)//返回Q元素的個數(shù)，即隊列的長度。StatusGetHead(LinkQueueQ,QElemType&e)//假設(shè)隊列不為空，那么用e返回Q的隊頭元素，并返回OK;否那么返回ERROR。StatusEnQueue(LinkQueue&Q,QElemTypee)//插入e返回Q的新的隊尾元素。StatusDeQueue(LinkQueue&Q,QElemType&e)//假設(shè)隊列不空，那么刪除Q的隊頭元素，并用e返回其值，并返回OK;否那么返回ERROR。三．詳細(xì)設(shè)計〔**x〕1.順序隊列的實現(xiàn)和運算1〕元素的類型typedefstruct{Datatypedata[MAXSIZE];intfront,rear;}Squeue;2〕空的隊列的構(gòu)造voidInitSqueue(Squeue*p)/*初始化隊列*/{p->front=0;p->rear=0;}3〕元素的入隊intEnsqueue1(Squeue1*q,Datatypee)/*入隊*/{if((q->rear+1)%MAXSIZE==q->front){printf("\n隊列已滿\n");return0;}4〕元素的出隊intDeSqueue1(Squeue1*q,Datatype*e)/*出隊*/{if(q->front==q->rear){printf("隊列已空,無法出隊!");return0;}*e=q->data[q->front];q->front=(q->front+1)%MAXSIZE;return1;}5〕判斷隊列是否為空intQueueEmpty1(Squeue1q)//判斷是否為空{(diào)if(q.front==q.rear)return1;elsereturn0;}6〕隊頭元素的取值的算法intGethead1(Squeue1*q,Datatype*e)//取對頭元素{if(q->front==q->rear){printf("隊列已空，無法出隊!");return0;}else*e=q->data[q->front];return1;}7〕遍歷順序隊列的算法voiddisplay1(Squeue1q)//遍歷順序?qū)α衶printf("此隊列數(shù)據(jù)為:\n");if(q.front==q.rear)printf("此隊列為空!");else{while(q.front<q.rear){printf("%d\t",q.data[q.front]);q.front=(q.front+1)%MAXSIZE;}printf("\n");}2.鏈?zhǔn)疥犃械膶崿F(xiàn)和運算1〕構(gòu)造空隊列的算法voidInitQueue2(LinkQueue*q){//構(gòu)造一個空隊列Qq->front=q->rear=malloc(sizeof(QNode));if(!q->front)exit(1);q->front->next=NULL;}2〕元素的入隊算法voidEnQueue2(LinkQueue*q,QElemTypee)//將元素e進(jìn)隊{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));//創(chuàng)立新節(jié)點if(!p)//如果存分配成功exit(1);p->data=e;//初始化新節(jié)點數(shù)據(jù)為e p->next=NULL;q->rear->next=p;q->rear=p;}3〕元素的出隊的算法intDeQueue2(LinkQueue*q,QElemTypee)//隊頭結(jié)點出隊,將出隊的元素存入e{QueuePtrp;if(q->front==q->rear)//隊列為空return0;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é)點returne;}4〕隊列的長度算法voidQueueLength2(LinkQueue*q)//返回隊列長度{QueuePtrp;inti=0;p=q->front->next;while(p) {++i;p=p->next; }printf("鏈隊列長度為:%d\n",i);}5〕隊列的銷毀voidDestroyQueue2(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〕隊列的輸出算法voidoutput2(LinkQueue*q)//輸出隊列{QueuePtrp;p=q->front->next;printf("鏈隊列元素依次為:");while(p) {printf("%d->",p->data);p=p->next; }printf("\n");}7〕隊列的清空的算法voidClear2(LinkQueue*q)//清空隊列{QueuePtrtemp=q->front->next;while(temp) {QueuePtrtp=temp;temp=temp->next;free(tp); }temp=q->front;q->front=q->rear=NULL;free(temp);}8〕返回對頭元素的算法intGetHead2(LinkQueue*q,int*e)//返回對頭結(jié)點元素，存入e{if(q->front==q->rear)return0;*e=q->front->next->data;return1;}3.循環(huán)隊列的實現(xiàn)和運算1〕隊列的初始化算法voidInitSqueue3(Squeue3*p)/*初始化隊列*/{p->base=(Datatype*)malloc(sizeof(Datatype)*MAXSIZE);p->front=0;p->rear=0;}2〕入隊的算法intEnsqueue3(Squeue3*q,Datatypee)/*入隊*/{if((q->rear+1)%MAXSIZE==q->front){printf("\n隊列已滿\n");return0;}elseq->base[q->rear]=e;/*將接收到得值付給隊尾所指的節(jié)點*/q->rear=(q->rear+1)%MAXSIZE;/*隊尾向后移一位完成入隊*/return1;}3〕出隊的算法intDeSqueue3(Squeue3*q,Datatype*e)/*出隊*/{if(q->front==q->rear){printf("隊列已空,無法出隊!");return0;}*e=q->base[q->front];q->front=(q->front+1)%MAXSIZE;return1;}4判斷隊列是否為空的算法intQueueEmpty3(Squeue3q)//判斷是否為空{(diào)if(q.front==q.rear)return1;elsereturn0;}5〕對頭元素的返還的算法intGethead3(Squeue3*q,Datatype*e)//取對頭元素{if(q->front==q->rear){printf("隊列已空，無法出隊!");return0;}else*e=q->base[q->front];return1;}6〕遍歷循環(huán)隊列的算法voiddisplay3(Squeue3*q)//遍歷循環(huán)對列{inttail;tail=q->front;printf("此隊列數(shù)據(jù)為:\n");if(q->front==q->rear)printf("此隊列為空!");else{while(tail!=q->rear){printf("%d\t",q->base[tail]);tail=(tail+1)%MAXSIZE;}printf("\n");}}4.主函數(shù)的算法voidmain(){intchoice;Datatypee1;inti1,a1,x1,s1,j1;//順序隊列定義的量inte2,i2,n2,s2,a2;//鏈隊列定義的量inti3,a3,x3,s3,j3;//循環(huán)隊列定義的量Datatypee3;Squeue1Q1;//*******************************LinkQueueq;//********************************Squeue3Q;//****************************choice=-1;Begin();while(choice!=0){scanf("%d",&choice);switch(choice) {case1://順序隊列{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("對頭為:%d\n",Q1.data[Q1.front]);printf("隊尾為:%d\n",Q1.data[Q1.front+j1-1]);display1(Q1);s1=-1;start1();while(s1!=0) {scanf("%d",&s1);switch(s1){case0:system("cls");choice=-1;Begin();break;case1:{system("cls");printf("請輸入入隊元素:\n");scanf("%d",&x1);Ensqueue1(&Q1,x1);display1(Q1);s1=-1;start1();break;}case2:{system("cls");DeSqueue1(&Q1,&e1);display1(Q1);s1=-1;start1();break;}case3:{system("cls");if(QueueEmpty1(Q1))printf("此隊列為空!\n");elseprintf("此隊列不為空!\n");}s1=-1;start1();break;case4: {system("cls");Gethead1(&Q1,&e1);printf("對頭元素為:%d\n",e1);s1=-1;start1();break; }case5: {system("cls");display1(Q1);s1=-1;start1();break; }}//switch } //while}//case1break;//*************************************************case2:{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) {case1:system("cls");QueueLength2(&q);a2=-1;start2();break;case2:{system("cls");printf("請輸入入隊元素:");scanf("%d",&e2);EnQueue2(&q,e2);output2(&q);a2=-1;start2();}break;case3:system("cls");e2=DeQueue2(&q,e2);output2(&q);printf("出隊元素為:%d\n",e2);a2=-1;start2();break;case4:DestroyQueue2(&q);printf("隊列已銷毀!\n");a2=0;system("cls");choice=-1;Begin();break;case5:Clear2(&q);printf("隊列已清空\n");a2=0;system("cls");choice=-1;Begin();break;case6:system("cls");GetHead2(&q,&e2);printf("隊頭元素為:%d\n",e2);s2=-1;start2();break;case0:system("cls");choice=-1;Begin();break; }//switch }//while}//case2break;//**************************************************case3:{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("對頭為:%d\n",Q.base[Q.front]);printf("隊尾為:%d\n",Q.base[Q.front+j3-1]);display3(&Q);s3=-1;start3();while(s3!=0){scanf("%d",&s3);switch(s3){case0:system("cls");choice=-1;Begin();break;case1:{system("cls");printf("請輸入入隊元素:\n");scanf("%d",&x3);Ensqueue3(&Q,x3);display3(&Q);s3=-1;start3();break;}case2: {system("cls");DeSqueue3(&Q,&e3);display3(&Q);s3=-1;start3();break; }case3:{system("cls");if(QueueEmpty3(Q))printf("此隊列為空!\n");elseprintf("此隊列不為空!\n");}s3=-1;start3();break;case4: {system("cls");Gethead3(&Q,&e3);printf("對頭元素為:%d\n",e3);s3=-1;start3();break; }case5: {system("cls");display3(&Q);s3=-1;start3();break; }}//switch} //while}//case3break;case0:printf("使用!!!!\n");break;//*************************** }//switch }//while}//main調(diào)試分析〔**x〕順序隊列編譯并調(diào)試，運行程序。設(shè)計測試用例，分析測試結(jié)果，以驗證所完成的系統(tǒng)是否到達(dá)預(yù)期效果。3.判斷隊列是否為空。隊列是否為空的標(biāo)志就是隊頭指針和隊尾指針是否同時指向隊列中的同一個位置，即隊頭指針和隊尾指針是否相等。4.隊列滿時候不能入隊列，否那么會出現(xiàn)溢出現(xiàn)象。即先要判斷隊列是否已經(jīng)已滿，因為隊尾指針的最大值是MAXQSIZE，所以通過檢查隊尾指針rear是否等于MAXQSIZE來判斷隊列是否已滿。在刪除隊首元素時，應(yīng)首先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空。5.在元素出隊操作，先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空，空時不能操作，這是要注意的。6.程序滿足了本次試驗的目的和任務(wù)要求，可以進(jìn)展人機交互，在后來的程序中將會做些改良，以增強人機交互性。7.本程序存在較多缺乏，如有問題，參考用戶手冊。8.在程序語句中，原本使用了大量的生僻的函數(shù)名，經(jīng)過改良，目前使用都是通俗易懂的函數(shù)名稱，方便用戶理解。鏈隊列1.編譯并調(diào)試，運行程序。2.設(shè)計測試用例，分析測試結(jié)果，以驗證所完成的系統(tǒng)是否到達(dá)預(yù)期效果。3.要注意設(shè)定一個在鏈隊列添加一個頭結(jié)點并令指針指向頭結(jié)點。同時，刪除不可以在最后面進(jìn)展刪除，但是插入可以最后一個進(jìn)展插入，這點需要注意4.需要分別指向隊頭和隊尾的指針。5.程序滿足了本次試驗的目的和任務(wù)要求，可以進(jìn)展人機交互，在后來的程序中將會做些改良，以增強人機交互性。6.本程序存在較多缺乏，如有問題，參考用戶手冊。7.在程序語句中，原本使用了大量的生僻的函數(shù)名，經(jīng)過改良，目前使用都是通俗易懂的函數(shù)名稱，方便用戶理解。循環(huán)隊列1.編譯并調(diào)試，運行程序。2.設(shè)計測試用例，分析測試結(jié)果，以驗證所完成的系統(tǒng)是否到達(dá)預(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ù)要求，可以進(jìn)展人機交互，在后來的程序中將會做些改良，以增強人機交互性。7.本程序存在較多缺乏，如有問題，參考用戶手冊。8.在程序語句中，原本使用了大量的生僻的函數(shù)名，經(jīng)過改良，目前使用都是通俗易懂的函數(shù)名稱，方便用戶理解。五、用戶手冊(**)1.鏈隊列(1)本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件名為：j.exe.(2)進(jìn)入演示程序后即顯示文本方式的用戶界面，輸入元素1,2,3,4,5創(chuàng)立隊列。根據(jù)提示，選擇操作2執(zhí)行元素入隊操作?；剀?，輸入入隊元素0，回車，將0插入到隊列中?！?〕選擇操作3執(zhí)行元素出隊操作，回車，隊首元素1出隊?！?〕選擇操作1執(zhí)行輸出隊列長度操作，回車，輸出隊列長度為5.〔6〕選擇操作5執(zhí)行清空隊列操作，回車，清空。選擇操作6執(zhí)行輸出隊頭元素操作，回