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

數(shù)據(jù)結(jié)構(gòu)--04隊列的基本操作數(shù)據(jù)結(jié)構(gòu)--04隊列的基本操作數(shù)據(jù)結(jié)構(gòu)--04隊列的基本操作數(shù)據(jù)結(jié)構(gòu)--04隊列的基本操作編制僅供參考審核批準生效日期地址：電話：傳真:郵編:《數(shù)據(jù)結(jié)構(gòu)》實驗報告院系光電與信息工程學院專業(yè)電子信息工程姓名學號電話2011級2班2013年4月20日1．實驗題目實驗4.對列的基本操作2．需求分析（1）編寫鏈接隊列的基本操作函數(shù)，調(diào)用上述函數(shù)實現(xiàn)下列操作，操作步驟如下：調(diào)用進隊函數(shù)建立一個隊列。讀取隊列中的第一個元素。從隊列中刪除元素。輸出隊列中的所有元素。（2）編寫環(huán)型隊列的基本操作函數(shù)。調(diào)用上述函數(shù)實現(xiàn)下列操作，操作步驟如下:調(diào)用進隊函數(shù)建立一個隊列。讀取隊列中的第一個元素。從隊列中刪除元素。輸出隊列中的所有元素。鏈接隊列：①進隊操作EnQueue(LinkQueue*Q,QElemTypee)②出隊操作，隊空DeQueue(LinkQueue*Q,QElemType*e)③輸出隊列中元素0utputQueue(LinkQueueQ)環(huán)型隊列：①進隊操作，返回1為隊滿EnQueue(SqQueue*Q,QElemTypee)②出隊操作，返回1為隊空DeQueue(SqQueue*Q,QElemType*e)③輸出隊列中元素outPutQMeue(SqQueueQ)輸入形式：整型數(shù)。3．概要設(shè)計（1）鏈接隊列ADTQNode{數(shù)據(jù)對象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}結(jié)構(gòu)關(guān)系：R={<ai,ai+1>|ai,ai+1∈D}基本操作：InitQueue(LinkQueue*Q)操作前提：Q是一個未初始化的鏈接隊列操作結(jié)果：將Q初始化為一個空的鏈接隊列EnQueue(LinkQueue*Q,QElemTypee)操作前提：鏈接隊列Q已存在操作結(jié)果：將元素e插入到鏈接隊列中DeQueue(LinkQueue*Q,QElemType*e)操作前提：鏈接隊列Q已存在操作結(jié)果：將鏈接隊列Q中隊頭元素刪除，刪除的元素值通過e返回0utputQueue(LinkQueueQ)操作前提：鏈接隊列Q已存在操作結(jié)果：將鏈接隊列Q中的元素顯示到屏幕上}本程序包含5個函數(shù)：主函數(shù)main()初始化鏈接隊列函數(shù)InitQueue()進隊函數(shù)EnQueue()出隊函數(shù)DeQueue()輸出隊列中元素函數(shù)OutputStack()各函數(shù)調(diào)用關(guān)系：主函數(shù)main調(diào)用其他四個函數(shù)主函數(shù)的偽碼main(){定義變量i，n，m；定義一個LinkQueue變量Lq初始化Lq；輸入隊列元素的個數(shù)；For循環(huán)（i=1;i<=n;i++）｛調(diào)用EnQueue函數(shù)；｝輸出隊列中元素； 調(diào)用DeQueue函數(shù)；顯示刪除的隊頭元素；顯示Lq；｝（2）環(huán)形隊列ADTSqQueue{數(shù)據(jù)對象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}結(jié)構(gòu)關(guān)系：R={<ai,ai+1>|ai,ai+1∈D}基本操作：InitQueue(SqQueue&Q)操作前提：Q是一個未初始化的環(huán)型隊列操作結(jié)果：將Q初始化為一個空的環(huán)型隊列EnQueue(SqQueue*Q,inte)操作前提：環(huán)型隊列Q已存在操作結(jié)果：將元素e插入到隊列中DeQueue(SqQueue*Q,int*e)操作前提：環(huán)型隊列Q已存在操作結(jié)果：將環(huán)型隊列Q中隊頭元素刪除，刪除的元素值通過e返回outPutQMeue(SqQueue*Q)操作前提：環(huán)型隊列Q已存在操作結(jié)果：將環(huán)型隊列Q中的元素顯示到屏幕上}本程序包含5個函數(shù)：主函數(shù)main()初始化鏈接隊列函數(shù)InitQueue()進隊函數(shù)EnQueue()出隊函數(shù)DeQueue()輸出隊列中元素函數(shù)OutputStack()各函數(shù)調(diào)用關(guān)系：主函數(shù)main調(diào)用其他四個函數(shù)函數(shù)的偽碼main（）｛ 定義SqQueue變量sq;定義整型變量n,i,m;構(gòu)造空的環(huán)型隊列；輸入隊列的長度；For循環(huán)（i=1;i<=n;i++）｛調(diào)用EnQueue函數(shù)；｝輸出隊列元素；刪除對頭元素；輸出隊列元素；｝詳細設(shè)計（1）鏈接隊列類型定義typedefstructQNode{ intdata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront; QueuePtrrear;}LinkQueue;基本操作的偽碼算法（1）初始化voidInitQueue(LinkQueue*Q){Q->front=Q->rear==申請新結(jié)點;Q->front->next=NULL;}（2）進隊voidPush(SqStack&S,inte){定義QueuePtr變量p；p=申請新的空間；如果申請失敗，結(jié)束程序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->next;如果Q->rear==p則Q->rear=Q->front;；釋放p的空間；返回1；}（4）輸出元素intOutputQueue(LinkQueueQ){定義QueuePtr變量p；如果隊空則返回0； p=>next;while(p) { printf("%d",p->data); p=p->next; } printf("\n"); 返回1; }（2）環(huán)形隊列類型定義typedefstruct{ int*base; intfront; intrear;}SqQueue;基本操作的偽碼算法（1）初始化voidInitQueue(SqQueue&Q){=申請新的空間；如果申請失敗，結(jié)束程序；==0;}（2）進隊intEnQueue(SqQueue*Q,inte){如果隊滿了則返回1； Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%MAXQSIZE;返回0；｝出隊intDeQueue(SqQueue*Q,int*e)DeQueue(SqQueue*Q,int*e)｛如果隊空則返回1；*e=Q->base[Q->front]; Q->front=(Q->front+1)%MAXQSIZE;返回0；}（4）輸出元素voidoutPutQMeue(SqQueue*Q){定義整型變量i；For循環(huán)（i=Q->front;i<Q->rear;i++){輸出Q->base[i]；}換行；}調(diào)試分析鏈接隊列：調(diào)試是出現(xiàn)錯誤，經(jīng)過檢查發(fā)現(xiàn)在某些地方分號用中文表示，出現(xiàn)空指針問題。環(huán)型隊列：出現(xiàn)空指針問題，內(nèi)存不能讀取等使用說明（1）鏈接隊列：程序執(zhí)行過程如下：提示用戶輸入元素個數(shù)；用戶按要求輸入一個整型數(shù)；程序輸出構(gòu)造好的鏈接隊列；調(diào)用出隊函數(shù)，并把剩余元素顯示在屏幕上；（2）環(huán)型隊列：程序執(zhí)行過程如下：提示用戶輸入隊列元素個數(shù)；用戶按要求輸入一個整型數(shù)；程序用輸入的整型數(shù)構(gòu)建一個環(huán)型隊列，并輸出隊列元素；調(diào)用出棧函數(shù)，刪除棧頂，顯示棧中元素；測試結(jié)果（1）鏈接隊列構(gòu)造一個空的鏈接隊列后，屏幕顯示：請輸入隊列的元素個數(shù)：輸入5后，屏幕顯示建立的隊列元素：12345調(diào)用出隊函數(shù)后，屏幕顯示：2345（2）環(huán)形隊列建立空隊列，程序運行后屏幕顯示：輸入隊列元素的長度輸入5后，屏幕顯示隊列的元素：12345接著屏幕又顯示：隊列中的第一個元素為：1調(diào)用出隊函數(shù)，然后輸入隊列中元素：23458.參考文獻數(shù)據(jù)結(jié)構(gòu)（c語言版）9．附錄源程序文件如下：（1）鏈接隊列#include<>#include<>typedefstructQNode{ intdata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront; QueuePtrrear;}LinkQueue;voidInitQueue(LinkQueue*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(LinkQueue*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==return0; p=>next; while(p) { printf("%d",p->data); p=p->next; } printf("\n"); return1;}voidmain(){inti,n;intm; LinkQueueLq; printf("構(gòu)造一個空的鏈接隊列"); InitQueue(&Lq); printf("\n請輸入隊列的元素個數(shù):"); scanf("%d",&n); for(i=1;i<=n;i++) { EnQueue(&Lq,i); } printf("隊列中的元素為:");OutputQueue(Lq);DeQueue(&Lq,&m); printf("刪除隊列中的第一個元素\n此時隊列中的元素為:");OutputQueue(Lq);}（2）環(huán)形隊列#include<>#include<>#defineMAXQSIZE100typedefstruct{ int*base; intfront; intrear;}SqQueue;voidInitQueue(SqQueue&Q){ =(int*)malloc(MAXQSIZE*sizeof(int)); if(!exit(1); ==0;}intEnQueue(SqQueue*Q,inte){ if((Q->rear+1)%MAXQSIZE==Q->front)return1; Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%MAXQSIZE; return0;}int