數(shù)據結構--04隊列的基本操作

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

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

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

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

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

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

7、結點Q->front->next=NULL;(2)進隊voidPush(SqStack&S,inte)定義QueuePtr變量p；p=申請新的空間；如果申請失敗，結束程序p->data=e;p->next=NULL;如果是第一個元素則Q->front->next=p;Q->rear->next=p;Q->rear=p;(3)出隊intPop(SqStack*S,inte)定義QueuePtr變量p；如果隊空則返回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;如果隊空則返回0;p=Q.front->next;while(p)printf("%d",p->data);p=p->next;printf("n");返回1;(2)環(huán)形隊列類型定義typedefstructint*base;intfront;intrear;SqQueue;基本操作的偽碼算法(1)初始化voidInitQue

9、ue(SqQueue&Q)Q.base=申請新的空間；如果申請失敗，結束程序；Q.front=Q.rear=0;(2)進隊intEnQueue(SqQueue*Q,inte)如果隊滿了則返回1；Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXQSIZE;返回0;出隊intDeQueue(SqQueue*Q,int*e)DeQueue(SqQueue*Q,int*e)如果隊空則返回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 .調試分析鏈接隊列：調試是出現(xiàn)錯誤，經過檢查發(fā)現(xiàn)在某些地方分號用中文表示，出現(xiàn)空指針問題。環(huán)型隊列：出現(xiàn)空指針問題，內存不能讀取等6 .使用說明(1)鏈接隊列：程序執(zhí)行過程如下：提示用戶輸入元素個數(shù)；用戶按要求輸入一個整型數(shù)；程序輸出構造好的鏈接隊列；調用出隊函數(shù)，并把剩余元素顯示在屏幕上；(2)環(huán)型隊列：程序執(zhí)行過程如下：提示用戶輸入隊列元素個數(shù)；用戶按要求輸入一個整型數(shù)；程序用輸入的整型數(shù)構建一個環(huán)型隊列，并輸出

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

12、然后輸入隊列中元素：23451請輸入隊列的長度”隊列的元素為:12345隊列中的第一個元素為；1刪除對頭元素,輸出隊列元素Q345Pressanykeytocontinua8 .參考文獻數(shù)據結構(c語言版)9 .附錄源程序文件如下：(1)鏈接隊列#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("構造一個空的鏈接隊列");InitQueue(&Lq);printf("n請輸入隊列的元素個數(shù)：")；scanf("%d",&n);for(i=1;i<=n;i+)EnQueue(&Lq,i);printf("隊列中的元素為:");OutputQueue(Lq);DeQueue(&Lq,&m)

16、;printf("刪除隊列中的第一個元素n此時隊列中的元素為：");OutputQueue(Lq);2)環(huán)形隊列#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("構造空的環(huán)型隊列n");In