數(shù)據(jù)結(jié)構(gòu)--04隊(duì)列的基本操作

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告院系光電與信息工程學(xué)院專業(yè)電子信息工程姓名學(xué)號(hào)電話2011級(jí)2班2013年4月20日1 .實(shí)驗(yàn)題目實(shí)驗(yàn)4對(duì)列的基本操作2 .需求分析(1)編寫鏈接隊(duì)列的基本操作函數(shù)，調(diào)用上述函數(shù)實(shí)現(xiàn)下列操作，操作步驟如下：調(diào)用進(jìn)隊(duì)函數(shù)建立一個(gè)隊(duì)列。讀取隊(duì)列中的第一個(gè)元素。從隊(duì)列中刪除元素。輸出隊(duì)列中的所有元素。(2)編寫環(huán)型隊(duì)列的基本操作函數(shù)。調(diào)用上述函數(shù)實(shí)現(xiàn)下列操作，操作步驟如下：調(diào)用進(jìn)隊(duì)函數(shù)建立一個(gè)隊(duì)列。讀取隊(duì)列中的第一個(gè)元素。從隊(duì)列中刪除元素。輸出隊(duì)列中的所有元素。鏈接隊(duì)列： 進(jìn)隊(duì)操彳EnQueue(LinkQueue*Q,QElemTypee)出隊(duì)操作，隊(duì)空DeQueue(LinkQu

2、eue*Q,QElemType*e) 輸出隊(duì)列中元素0utputQueue(LinkQueueQ)環(huán)型隊(duì)列：進(jìn)隊(duì)操作，返回1為隊(duì)滿EnQueue(SqQueue*Q,QElemTypee)出隊(duì)操作，返回1為隊(duì)空DeQueue(SqQueue*Q,QElemType*e) 輸出隊(duì)列中元素outPutQMeue(SqQueueQ)輸入形式：整型數(shù)。3 .概要設(shè)計(jì)(1)鏈接隊(duì)列ADTQNode數(shù)據(jù)對(duì)象：D=ai|aiCIntegerSet,i=0,1,2,，n,n>0結(jié)構(gòu)關(guān)系：R=<a,ai+1>|ai,ai+1CD基本操作：InitQueue(LinkQueue*Q)操作前提：Q

3、是一個(gè)未初始化的鏈接隊(duì)列操作結(jié)果：將Q初始化為一個(gè)空的鏈接隊(duì)列EnQueue(LinkQueue*Q,QElemTypee)操作前提：鏈接隊(duì)列Q已存在操作結(jié)果：將元素e插入到鏈接隊(duì)列中DeQueue(LinkQueue*Q,QElemType*e)操作前提：鏈接隊(duì)列Q已存在操作結(jié)果：將鏈接隊(duì)列Q中隊(duì)頭元素刪除，刪除的元素值通過(guò)e返回0utputQueue(LinkQueueQ)操作前提：鏈接隊(duì)列Q已存在操作結(jié)果：將鏈接隊(duì)列Q中的元素顯示到屏幕上本程序包含5個(gè)函數(shù)：主函數(shù)main()初始化鏈接隊(duì)列函數(shù)InitQueue()進(jìn)隊(duì)函數(shù)EnQueue()出隊(duì)函數(shù)DeQueue()輸出隊(duì)列中元素函數(shù)Ou

4、tputStack()各函數(shù)調(diào)用關(guān)系：主函數(shù)main調(diào)用其他四個(gè)函數(shù)主函數(shù)的偽碼main()定義變量i,n,m;定義一個(gè)LinkQueue變量Lq初始化Lq；輸入隊(duì)列元素的個(gè)數(shù)；For循環(huán)(i=1;i<=n;i+)調(diào)用EnQueue函數(shù)；輸出隊(duì)列中元素；調(diào)用DeQueue函數(shù)；顯示刪除的隊(duì)頭元素；顯示Lq；(2)環(huán)形隊(duì)列ADTSqQueue數(shù)據(jù)對(duì)象：D=ai|aIntegerSet,i=0,1,2,，n,n>0結(jié)構(gòu)關(guān)系：R=<a,ai+1>|ai,ai+1CD基本操作：InitQueue(SqQueue&Q)操作前提：Q是一個(gè)未初始化的環(huán)型隊(duì)列操作結(jié)果：將Q初始

5、化為一個(gè)空的環(huán)型隊(duì)列EnQueue(SqQueue*Q,inte)操作前提：環(huán)型隊(duì)列Q已存在操作結(jié)果：將元素e插入到隊(duì)列中DeQueue(SqQueue*Q,int*e)操作前提：環(huán)型隊(duì)列Q已存在操作結(jié)果：將環(huán)型隊(duì)列Q中隊(duì)頭元素刪除，刪除的元素值通過(guò)e返回outPutQMeue(SqQueue*Q)操作前提：環(huán)型隊(duì)列Q已存在操作結(jié)果：將環(huán)型隊(duì)列Q中的元素顯示到屏幕上本程序包含5個(gè)函數(shù)：主函數(shù)main()初始化鏈接隊(duì)列函數(shù)InitQueue()進(jìn)隊(duì)函數(shù)EnQueue()出隊(duì)函數(shù)DeQueue()輸出隊(duì)列中元素函數(shù)OutputStack()各函數(shù)調(diào)用關(guān)系：主函數(shù)main調(diào)用其他四個(gè)函數(shù)函數(shù)的偽碼m

6、ain()定義SqQueue變量sq;定義整型變量n,i,m;構(gòu)造空的環(huán)型隊(duì)列；輸入隊(duì)列的長(zhǎng)度；For循環(huán)(i=1;i<=n;i+)調(diào)用EnQueue函數(shù)；輸出隊(duì)列元素；刪除對(duì)頭元素；輸出隊(duì)列元素；4 .詳細(xì)設(shè)計(jì)(1)鏈接隊(duì)列(1) 類型定義typedefstructQNodeintdata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;QueuePtrrear;LinkQueue;基本操作的偽碼算法(1)初始化voidInitQueue(LinkQueue*Q)Q->front=Q->rear=申請(qǐng)新

7、結(jié)點(diǎn)Q->front->next=NULL;(2)進(jìn)隊(duì)voidPush(SqStack&S,inte)定義QueuePtr變量p；p=申請(qǐng)新的空間；如果申請(qǐng)失敗，結(jié)束程序p->data=e;p->next=NULL;如果是第一個(gè)元素則Q->front->next=p;Q->rear->next=p;Q->rear=p;(3)出隊(duì)intPop(SqStack*S,inte)定義QueuePtr變量p；如果隊(duì)空則返回0；p=Q->front->next;*e=p->data;Q->front->next=p

8、->next;如果Q->rear=p則Q->rear=Q->front;；釋放p的空間；返回1；(4)輸出元素intOutputQueue(LinkQueueQ)定義QueuePtr變量p;如果隊(duì)空則返回0;p=Q.front->next;while(p)printf("%d",p->data);p=p->next;printf("n");返回1;(2)環(huán)形隊(duì)列類型定義typedefstructint*base;intfront;intrear;SqQueue;基本操作的偽碼算法(1)初始化voidInitQue

9、ue(SqQueue&Q)Q.base=申請(qǐng)新的空間；如果申請(qǐng)失敗，結(jié)束程序；Q.front=Q.rear=0;(2)進(jìn)隊(duì)intEnQueue(SqQueue*Q,inte)如果隊(duì)滿了則返回1；Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXQSIZE;返回0;出隊(duì)intDeQueue(SqQueue*Q,int*e)DeQueue(SqQueue*Q,int*e)如果隊(duì)空則返回1；*e=Q->baseQ->front;Q->front=(Q->front+1)%MAXQSIZE;返回0；(4)輸出元素vo

10、idoutPutQMeue(SqQueue*Q)定義整型變量i；For循環(huán)(i=Q->front;i<Q->rear;i+)輸出Q->basei；換行；5 .調(diào)試分析鏈接隊(duì)列：調(diào)試是出現(xiàn)錯(cuò)誤，經(jīng)過(guò)檢查發(fā)現(xiàn)在某些地方分號(hào)用中文表示，出現(xiàn)空指針問(wèn)題。環(huán)型隊(duì)列：出現(xiàn)空指針問(wèn)題，內(nèi)存不能讀取等6 .使用說(shuō)明(1)鏈接隊(duì)列：程序執(zhí)行過(guò)程如下：提示用戶輸入元素個(gè)數(shù)；用戶按要求輸入一個(gè)整型數(shù)；程序輸出構(gòu)造好的鏈接隊(duì)列；調(diào)用出隊(duì)函數(shù)，并把剩余元素顯示在屏幕上；(2)環(huán)型隊(duì)列：程序執(zhí)行過(guò)程如下：提示用戶輸入隊(duì)列元素個(gè)數(shù)；用戶按要求輸入一個(gè)整型數(shù)；程序用輸入的整型數(shù)構(gòu)建一個(gè)環(huán)型隊(duì)列，并輸出

11、隊(duì)列元素;調(diào)用出棧函數(shù)，刪除棧頂，顯示棧中元素；7 .測(cè)試結(jié)果(1)鏈接隊(duì)列構(gòu)造一個(gè)空的鏈接隊(duì)列后，屏幕顯示：請(qǐng)輸入隊(duì)列的元素個(gè)數(shù):輸入5后，屏幕顯示建立的隊(duì)列元素：12345調(diào)用出隊(duì)函數(shù)后，屏幕顯示：2345"VLQ期2011099陳海蠅實(shí)蛉GDebug譚堵軸造接隊(duì)列構(gòu)造一個(gè)空的諳接隊(duì)列防俞人隊(duì)列的元素個(gè)數(shù)：5隊(duì)列中的元素為2346.而除隊(duì)列中的第一個(gè)元素止恨寸隊(duì)列中的元素為：2345PressanykeytoGontinue(2)環(huán)形隊(duì)列建立空隊(duì)列，程序運(yùn)行后屏幕顯示：輸入隊(duì)列元素的長(zhǎng)度輸入5后，屏幕顯示隊(duì)列的元素：12345接著屏幕又顯示：隊(duì)列中的第一個(gè)元素為：1調(diào)用出隊(duì)函數(shù)，

12、然后輸入隊(duì)列中元素：23451請(qǐng)輸入隊(duì)列的長(zhǎng)度”隊(duì)列的元素為:12345隊(duì)列中的第一個(gè)元素為；1刪除對(duì)頭元素,輸出隊(duì)列元素Q345Pressanykeytocontinua8 .參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)9 .附錄源程序文件如下：(1)鏈接隊(duì)列#include<stdlib.h>#include<stdio.h>typedefstructQNodeintdata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;QueuePtrrear;LinkQueue;voidInitQueue(LinkQue

13、ue*Q)Q->front=Q->rear=(QNode*)malloc(sizeof(QNode);Q->front->next=NULL;voidEnQueue(LinkQueue*Q,inte)QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(1);p->data=e;p->next=NULL;if(Q->front->next=NULL)Q->front->next=p;Q->rear->next=p;Q->rear=p;intDeQueue(Link

14、Queue*Q,int*e)QueuePtrp;if(Q->front=Q->rear)return0;p=Q->front->next;*e=p->data;Q->front->next=p->next;if(Q->rear=p)Q->rear=Q->front;free(p);return1;intOutputQueue(LinkQueueQ)QueuePtrp;if(Q.front=Q.rear)return0;p=Q.front->next;while(p)printf("%d",p->d

15、ata);p=p->next;printf("n");return1;voidmain()inti,n;intm;LinkQueueLq;printf("構(gòu)造一個(gè)空的鏈接隊(duì)列");InitQueue(&Lq);printf("n請(qǐng)輸入隊(duì)列的元素個(gè)數(shù)：")；scanf("%d",&n);for(i=1;i<=n;i+)EnQueue(&Lq,i);printf("隊(duì)列中的元素為:");OutputQueue(Lq);DeQueue(&Lq,&m)

16、;printf("刪除隊(duì)列中的第一個(gè)元素n此時(shí)隊(duì)列中的元素為：");OutputQueue(Lq);2)環(huán)形隊(duì)列#include<stdio.h>#include<stdlib.h>#defineMAXQSIZE100typedefstructint*base;intfront;intrear;SqQueue;voidInitQueue(SqQueue&Q)Q.base=(int*)malloc(MAXQSIZE*sizeof(int);if(!Q.base)exit(1);Q.front=Q.rear=0;intEnQueue(SqQueu

17、e*Q,inte)if(Q->rear+1)%MAXQSIZE=Q->front)return1;Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXQSIZE;return0;intDeQueue(SqQueue*Q,int*e)if(Q->front=Q->rear)return1;*e=Q->baseQ->front;Q->front=(Q->front+1)%MAXQSIZE;return0;voidoutPutQMeue(SqQueue*Q)inti;for(i=Q->front;i<Q->rear;i+)printf("%d",Q->basei);printf("n");voidmain()SqQueuesq;intn,i,m;printf("構(gòu)造空的環(huán)型隊(duì)列n");In