隊(duì)列的基本操作及其應(yīng)用

1、廣西工學(xué)院計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告書實(shí)驗(yàn)四 隊(duì)列的基本操作及其應(yīng)用 學(xué)生姓名：李四 學(xué) 號：2012 班級：計(jì)Y124 指導(dǎo)老師：王日鳳 專 業(yè)：計(jì)算機(jī)學(xué)院軟件學(xué)院提交日期：2013年6月20日1 實(shí)驗(yàn)?zāi)康?）通過對隊(duì)列特點(diǎn)的分析，掌握隊(duì)列的存儲結(jié)構(gòu)及其基本操作，學(xué)會定義隊(duì)列的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，在實(shí)際問題中靈活運(yùn)用。2）掌握隊(duì)列先進(jìn)先出的特點(diǎn)，掌握隊(duì)列的基本操作，如出隊(duì)列、入隊(duì)列、判隊(duì)列空、判隊(duì)列滿等，熟悉各種操作的實(shí)現(xiàn)方法。3）通過具體的應(yīng)用實(shí)例，進(jìn)一步熟悉和掌握隊(duì)列的實(shí)際應(yīng)用。2.實(shí)驗(yàn)內(nèi)容（1）建立一個(gè)含n個(gè)數(shù)據(jù)的隊(duì)列，實(shí)現(xiàn)隊(duì)列的基本操作。包括：§ /1. 初始化

2、,構(gòu)造一個(gè)空隊(duì)列void initQueue(Queue &Q)§ /2. 判斷隊(duì)列空, 空則返回truebool QueueEmpty(seqQueue &Q) § /3. 判斷隊(duì)列滿, 滿則返回truebool QueueFull(seqQueue &Q) § /4. 取隊(duì)頭元素, 用x返回隊(duì)頭元素，返回true；空隊(duì)列則返回falseBool QueueHead(seqQueue &Q, elementType &x)§ /5. 入隊(duì)列，在隊(duì)尾插入新元素x （流程圖）bool pushQueue (seqQu

3、eue &Q, elementType x)§ /6. 出隊(duì)列，用x帶回隊(duì)頭元素，并在隊(duì)頭刪除，返回true，隊(duì)列空則返回false（流程圖）bool popQueue (seqQueue &Q, elementType &x) § /7. 輸出隊(duì)列,從隊(duì)頭到隊(duì)尾依次輸出void printQueue(seqQueue Q)（2）隊(duì)列應(yīng)用：利用隊(duì)列操作打印楊輝三角形的 前n行（如n=7）。3實(shí)驗(yàn)要求（1） 上機(jī)前交實(shí)驗(yàn)源程序（紙質(zhì)版），由學(xué)習(xí)委員統(tǒng)一收好交老師（附上不交同學(xué)名單）。（2） 用一切你能想到的辦法解決遇到的問題，培養(yǎng)解決問題的能力。（3）

4、 實(shí)驗(yàn)課上進(jìn)行答辯。（4） 實(shí)驗(yàn)報(bào)告當(dāng)場交。報(bào)告內(nèi)容包括 ：實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)代碼、實(shí)驗(yàn)輸入輸出結(jié)果以及實(shí)驗(yàn)體會供五部分。3主要算法3.1 順序存儲結(jié)構(gòu)（1） 結(jié)構(gòu)定義：#include<stdio.h>#include<stdlib.h> #include<malloc.h>#include <conio.h>/各個(gè)頭文件#define OK 1#define ERROR 0 #define OVERFLOW -2/定義宏參#define MAXQSIZE 100/最大隊(duì)列長度typedef int QElemType;/引用整型數(shù)據(jù)類型

5、別名/順序表的儲存結(jié)構(gòu)typedef struct QElemType *base;/初始化的動態(tài)分配內(nèi)存空間 int front;/頭指針int rear;/尾指針SqQueue; int N; /=函數(shù)聲明=/int InitQueue(SqQueue &Q);/初始化void creatQueue(SqQueue &Q,int n);/創(chuàng)建int QueueLength(SqQueue &Q);/求長度void EnQueue(SqQueue &Q,QElemType e);/入隊(duì)int DeQueue(SqQueue &Q);/出隊(duì)int Que

6、ueTraverse(SqQueue &Q);/顯示隊(duì)列int GetHead(SqQueue Q);/取頭元素int DestroyQueue(SqQueue &Q);/銷毀順序表int ClearQueue(SqQueue &Q);/清空順序表int yanghui(int n);/楊輝三角int ElemptyQueue(SqQueue &Q);/判空 /=函數(shù)聲明=/構(gòu)造空隊(duì)列int InitQueue(SqQueue &Q)/操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q printf("輸入分配空間大小: "); scanf(" %

7、d",&N); Q.base=(QElemType *)malloc(N*sizeof(QElemType);/動態(tài)分配內(nèi)存空間，以下同樣if(!Q.base|N<0|N>MAXQSIZE) /若n值不合理，則返回ERROR，以下同樣 printf("構(gòu)造失敗!"); printf("ntt按任意鍵返回主菜單!"); getch(); return ERROR; Q.front=Q.rear=0;/隊(duì)列設(shè)置為空，以下同樣printf("構(gòu)造成功!"); printf("ntt按任意鍵返回主菜單!

8、"); getch(); return OK; /初始化隊(duì)列int InitQue(SqQueue &Q,int n) /操作結(jié)果:初始化一個(gè)空隊(duì)列Q.base=(QElemType *)malloc(n*sizeof(QElemType); if(!Q.base|n<0|n>MAXQSIZE) return ERROR; Q.front=Q.rear=0; return OK; /創(chuàng)建隊(duì)列void creatQueue(SqQueue &Q,int n) /初始條件：Q已經(jīng)存在/操作結(jié)果：向隊(duì)列輸入n個(gè)元素int m; if(!Q.base|n<0

9、|n>N) printf("初始化未完成或超出隊(duì)列長度，無法創(chuàng)建!"); printf("ntt按任意鍵返回主菜單!"); getch(); return; printf("請輸入入隊(duì)元素!n"); for(int i=0;i<n;i+)/將元素逐個(gè)從隊(duì)列尾部插入 printf("請輸入第%d個(gè)數(shù)據(jù)：",i+1); scanf(" %d",&m); Q.rear=i; Q.baseQ.rear=m; Q.rear=(Q.rear+1)%N;/尾指針后移一位 printf(&q

10、uot;創(chuàng)建成功!n"); QueueTraverse(Q);/調(diào)用顯示函數(shù) printf("ntt按任意鍵返回主菜單!"); getch(); return; /求隊(duì)列的長度int QueueLength(SqQueue &Q) /初始條件：Q已經(jīng)存在 /操作結(jié)果：返回隊(duì)列的長度QueueTraverse(Q);/調(diào)用顯示函數(shù) printf("nThe Queue length is: %d",(Q.rear-Q.front+N)%N);/打印表長printf("nn");printf("ntt按任意鍵返

11、回主菜單!"); getch(); return OK; /入隊(duì)列void EnQueue(SqQueue &Q,QElemType e) /初始條件：Q已經(jīng)存在 /操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素if(Q.rear+1) % N=Q.front) /隊(duì)列為滿的情況 printf("隊(duì)列已滿,無法插入!"); printf("ntt按任意鍵返回主菜單!"); getch(); return; Q.baseQ.rear=e; Q.rear=(Q.rear+1) % N; /尾指針后移一位 printf("入隊(duì)成功!n&qu

12、ot;);QueueTraverse(Q);/調(diào)用顯示函數(shù) printf("ntt按任意鍵返回主菜單!"); getch(); return; /入隊(duì)列void EnQueu(SqQueue &Q,QElemType e) /初始條件：Q已經(jīng)存在/操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素if(Q.rear+1)%MAXQSIZE=Q.front) return; Q.baseQ.rear=e; Q.rear=(Q.rear+1) % MAXQSIZE; /出隊(duì)列int DeQueue(SqQueue &Q) /初始條件：Q已經(jīng)存在 /操作結(jié)果：若隊(duì)列不空，刪除

13、Q的隊(duì)頭元素，/用e返回其值，并返回，否則返回int e;if(Q.front=Q.rear) /隊(duì)列為空的情況 printf("隊(duì)列為空，無法出隊(duì)!"); printf("ntt按任意鍵返回主菜單!"); getch(); return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1) % N;/頭指針后移一位 printf("隊(duì)頭元素出隊(duì)成功!n"); printf("這隊(duì)頭元素是：%d",e);printf("ntt按任意鍵返回主菜單!"); getc

14、h();return OK; /出隊(duì)列int DeQueu(SqQueue &Q) /初始條件：Q已經(jīng)存在 /操作結(jié)果：若隊(duì)列不空，刪除Q的隊(duì)頭元素，/用e返回其值，并返回，否則返回int e; if(Q.front=Q.rear) /隊(duì)列為空的情況 return ERROR; e=Q.baseQ.front; /將頭元素賦給e Q.front=(Q.front+1) % MAXQSIZE;/頭指針后移一位return e;/顯示int QueueTraverse(SqQueue &Q) /初始條件：Q已經(jīng)存在 /操作結(jié)果：把隊(duì)列中的元素輸出到顯示屏int i; i=Q.fro

15、nt; if(Q.front=Q.rear) /隊(duì)列為空的情況 printf("The Queue is Empty!"); printf("ntt按任意鍵返回主菜單!"); getch(); return ERROR; else printf("The Queue is:"); while(i!=Q.rear) /當(dāng)隊(duì)列不為空時(shí) printf("%3d",Q.basei); i=(i+1)%N; printf("n");printf("顯示成功!"); return OK;

16、 /取隊(duì)頭元素int GetHead(SqQueue Q) /初始條件：Q已經(jīng)存在 /操作結(jié)果：若隊(duì)列不空，返回其值，否則返回int e; if(Q.front=Q.rear) /隊(duì)列為空的情況 printf("The Queue is Empty!"); printf("ntt按任意鍵返回主菜單!"); getch(); return ERROR; e=*(Q.base+Q.front);/將頭元素賦給e return e; /判斷順序表是否為空int ElemptyQueue(SqQueue &Q) /初始條件：Q已經(jīng)存在 /操作結(jié)果：若隊(duì)列

17、為空返回，否則返回if(Q.front=Q.rear)/隊(duì)列為空的情況 return OK; else return ERROR; /銷毀鏈表int DestroyQueue(SqQueue &Q)/初始條件:順序表已存在/操作結(jié)果:銷毀順序表Q.front=Q.rear=0; return OK;/清空隊(duì)列int ClearQueue(SqQueue &Q)/初始條件:順序表已存在/操作結(jié)果:清空順序表Q.front=Q.rear=0; return OK;/楊輝三角int yanghui(int n) /打印輸出楊輝三角的前n( n>0 )行if(n<0|n&g

18、t;MAXQSIZE) printf("行數(shù)不合理，無法顯示!"); printf("ntt按任意鍵返回主菜單!"); getch(); return ERROR; SqQueue Q;/定義新的循環(huán)隊(duì)列 int k,e,p; for(int i=1;i<=n;i+) printf(" "); printf("1n");/在中心位置輸出楊輝三角最頂端的"1" InitQue(Q,n+2);/設(shè)置最大容量為n+2 的空隊(duì)列 EnQueu(Q,0);/添加行界值EnQueu(Q,1); EnQ

19、ueu(Q,1);/第一行的值入隊(duì)列 k=1; while(k<n) /通過循環(huán)隊(duì)列輸出前n-1 行的值 for(int i=1;i<=n-k;i+) printf(" ");/輸出n-k個(gè)空格以保持三角型 EnQueu(Q,0);/行界值"0"入隊(duì)列 do /輸出第k 行，計(jì)算第k+1 行 p=DeQueu(Q); e=GetHead(Q); if(e) printf("%d ",e);/若e為非行界值，則打印輸出e else printf("n");/否則回車換行，為下一行輸出做準(zhǔn)備 EnQueu(

20、Q,p+e); while(e!=0); k+; e=DeQueu(Q);/行界值"0"出隊(duì)列 while(!ElemptyQueue(Q) /單獨(dú)處理第n 行的值的輸出 e=DeQueu(Q); printf("%d ",e); printf("ntt顯示成功!"); printf("ntt按任意鍵返回主菜單!"); getch(); return OK; /主函數(shù)void main() SqQueue Q;/定義隊(duì)列變量int b,c,f;/定義整型數(shù)據(jù)變量int j,k;/設(shè)置選項(xiàng)變量while(1) sys

21、tem("cls");/清屏 printf("nt*"); printf("nt* 隊(duì)列的基本操作及其應(yīng)用 *"); printf("nt*n"); printf("t * 1.初始化隊(duì)列 2.創(chuàng)建隊(duì)列 *n"); printf("t * 3.隊(duì)列長度 4.入隊(duì)隊(duì)列 * n"); printf("t * 5.取頭元素 6.顯示隊(duì)列 * n"); printf("t * 7.楊輝三角 8.銷毀隊(duì)列 * n"); printf("

22、t * 9.清空隊(duì)列 0.退出 *n"); printf("t*n"); printf("請選擇選項(xiàng)<1-9>: ");/打印選項(xiàng)功能提示 scanf(" %d",&k); if(k<0|k>9) printf("輸入有誤，請重新輸入!");printf("n");printf("nttt按任意鍵進(jìn)行重新操作!"); getch(); continue; switch(k)/分支結(jié)構(gòu)來調(diào)用各功能子函數(shù) case 1: printf(&

23、quot;創(chuàng)建空的循環(huán)隊(duì)列n"); InitQueue(Q);/調(diào)用初始化函數(shù)printf("n"); break;/退出并重新進(jìn)入主菜單case 2: printf("創(chuàng)建新的循環(huán)隊(duì)列n"); printf("輸入長度:"); scanf("%d",&f); creatQueue(Q,f);/調(diào)用創(chuàng)建函數(shù) break; case 3: printf("求表長!n"); QueueLength(Q);/調(diào)用求表長函數(shù) break;case 4: printf("入隊(duì)!

24、n"); printf("輸入入隊(duì)元素: "); scanf("%d",&b); EnQueue(Q,b);/調(diào)用入隊(duì)函數(shù)QueueTraverse(Q);/調(diào)用顯示函數(shù) break; case 5:printf("出隊(duì)!n"); DeQueue(Q);/調(diào)用出隊(duì)函數(shù) break; case 6:printf("顯示順序表!n"); QueueTraverse(Q);/調(diào)用顯示函數(shù)getch(); break; case 7: system("cls");/清屏printf("楊輝三角!n"); printf("輸入其行數(shù): "); scanf(" %d",&c);/輸入行數(shù)+1 printf("楊輝三角顯示為:n"); yanghui(c-1);/調(diào)用楊輝三角函數(shù) break; case 8: printf("你真確定要銷毀隊(duì)列! 1.YES 2.NOn");printf("請選擇項(xiàng)<1-2>: ");scanf("%d",&j);if(j=1) DestroyQue