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

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告院系光電與信息工程學(xué)院專業(yè)電子信息工程學(xué)號2011級 2班 2013年4月20日1 實(shí)驗(yàn)題目實(shí)驗(yàn)4 .對列的基本操作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ì)操作En Queue(L in kQueue *Q, QEIemType e) 出隊(duì)操作，隊(duì)空DeQueue(

2、L in kQueue *Q, QEIemType *e) 輸出隊(duì)列中元素0utputQueue(Li nkQueue Q)環(huán)型隊(duì)列： 進(jìn)隊(duì)操作，返回 1 為隊(duì)滿En Queue(SqQueue *Q, QElemType e) 出隊(duì)操作，返回 1 為隊(duì)空DeQueue(SqQueue *Q, QElemType *e) 輸出隊(duì)列中元素outPutQMeue(SqQueue Q)輸入形式：整型數(shù)。3. 概要設(shè)計(jì)(1)隊(duì)列ADT QNode數(shù)據(jù)對象：D=a i|ai IntegerSet,i=0,1,2,n,n 0結(jié)構(gòu)關(guān)系：R=|ai,ai+1 D基本操作：Ini tQueue(L in kQu

3、eue *Q)操作前提：Q是一個(gè)未初始化的隊(duì)列操作結(jié)果：將Q初始化為一個(gè)空的隊(duì)列En Queue(L in kQueue *Q, QElemType e)操作前提：隊(duì)列Q已存在操作結(jié)果：將元素 e插入到隊(duì)列中DeQueue(Li nkQueue *Q, QElemType *e)操作前提：隊(duì)列Q已存在操作結(jié)果：將隊(duì)列 Q中隊(duì)頭元素刪除，刪除的元素值通過e返回0utputQueue(L in kQueue Q)操作前提：隊(duì)列Q已存在操作結(jié)果：將隊(duì)列 Q中的元素顯示到屏幕上本程序包含5個(gè)函數(shù)：主函數(shù)main()初始化隊(duì)列函數(shù)Ini tQueue()進(jìn)隊(duì)函數(shù)EnQueue()出隊(duì)函數(shù)DeQueue(

4、) 輸出隊(duì)列中元素函數(shù)OutputStack()各函數(shù)調(diào)用關(guān)系：主函數(shù) main調(diào)用其他四個(gè)函數(shù)主函數(shù)的偽碼mai n()定義變量i, n, m;定義一個(gè) LinkQueue 變量Lq初始化Lq ；輸入隊(duì)列元素的個(gè)數(shù)；For 循環(huán)(i=1;i 0結(jié)構(gòu)關(guān)系：R=|ai,ai+1 D基本操作：Ini tQueue(SqQueue &Q)操作前提：Q是一個(gè)未初始化的環(huán)型隊(duì)列 操作結(jié)果：將Q初始化為一個(gè)空的環(huán)型隊(duì)列En Queue(SqQueue *Q,i nt e)操作前提：環(huán)型隊(duì)列Q已存在操作結(jié)果：將元素 e插入到隊(duì)列中DeQueue(SqQueue *Q,int *e)操作前提：環(huán)型隊(duì)列Q已存在

5、e返回操作結(jié)果：將環(huán)型隊(duì)列 Q中隊(duì)頭元素刪除，刪除的元素值通過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ù)的偽碼main()定義 SqQueue 變量 sq;定義整型變量 n,i,m;構(gòu)造空的環(huán)型隊(duì)列； 輸入隊(duì)列的長度； For 循環(huán)( i=1;ifront=Q-rear= 申

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

7、； 釋放 p 的空間； 返回 1；(4) 輸出元素int OutputQueue(LinkQueue Q) 定義QueuePtr變量p;如果隊(duì)空則返回0;p=Q.front-next;while(p)printf(%d ,p-data);p=p-next;printf(n);返回 1;（2）環(huán)形隊(duì)列類型定義typedef structint *base;int front;int rear;SqQueue;基本操作的偽碼算法（1）初始化void InitQueue（SqQueue &Q）Q.base=申請新的空間；如果申請失敗，結(jié)束程序；Q.front=Q.rear=0;（2）進(jìn)隊(duì)int En

8、Queue(SqQueue *Q,int e) 如果隊(duì)滿了則返回 1；Q-baseQ-rear=e;Q-rear=(Q-rear+1)%MAXQSIZE;返回0;出隊(duì)int DeQueue(SqQueue *Q,int *e)DeQueue(SqQueue *Q,int *e)如果隊(duì)空則返回 1；*e=Q-baseQ-front;Q-front=(Q-front+1)%MAXQSIZE;返回 0；(4)輸出元素void outPutQMeue(SqQueue *Q)定義整型變量 i；For 循環(huán)( i=Q-front;irear;i+)輸出 Q-basei ； 換行；5 調(diào)試分析隊(duì)列：調(diào)試是出

9、現(xiàn)錯(cuò)誤，經(jīng)過檢查發(fā)現(xiàn)在某些地方分號用中文表示，出現(xiàn)空指針問題。 環(huán)型隊(duì)列：出現(xiàn)空指針問題，存不能讀取等6使用說明(1) 隊(duì)列:程序執(zhí)行過程如下： 提示用戶輸入元素個(gè)數(shù)； 用戶按要求輸入一個(gè)整型數(shù)； 程序輸出構(gòu)造好的隊(duì)列；調(diào)用出隊(duì)函數(shù)，并把剩余元素顯示在屏幕上；(2) 環(huán)型隊(duì)列：程序執(zhí)行過程如下：提示用戶輸入隊(duì)列元素個(gè)數(shù)；用戶按要求輸入一個(gè)整型數(shù)；程序用輸入的整型數(shù)構(gòu)建一個(gè)環(huán)型隊(duì)列，并輸出隊(duì)列元素; 調(diào)用出棧函數(shù)，刪除棧頂，顯示棧中元素；7. 測試結(jié)果(1)隊(duì)列構(gòu)造一個(gè)空的隊(duì)列后，屏幕顯示：請輸入隊(duì)列的元素個(gè)數(shù): 輸入5后，屏幕顯示建立的隊(duì)列元素：1 2 34 5調(diào)用出隊(duì)函數(shù)后，屏幕顯示：234

10、5(2)環(huán)形隊(duì)列建立空隊(duì)列，程序運(yùn)行后屏幕顯示：輸入隊(duì)列元素的長度 輸入5后，屏幕顯示隊(duì)列的元素：1 2 3 4 5接著屏幕又顯示：隊(duì)列中的第一個(gè)元素為：1調(diào)用出隊(duì)函數(shù)，然后輸入隊(duì)列中元素：2 3 4 58. 參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)(c語言版)9 附錄源程序文件如下：(1)隊(duì)列#in clude#in cludetypedef struct QNodeint data;struct QNode *n ext;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;Lin kQueue;void In itQueue(L in kQueu

11、e *Q)Q-front=Q-rear=(QNode *)malloc(sizeof(QNode);Q-fro nt- next=NULL;void En Queue(L in kQueue *Q,i nt e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(1);p-data=e;p- next=NULL;if(Q-fro nt- next=NULL)Q-fr ont_n ext=p;Q-rear- n ext=p;Q-rear=p;int DeQueue(L in kQueue *Q,int *e)QueuePtr p;if(Q

12、-front=Q_rear)return 0;p=Q-fro nt_n ext;*e=p_data;Q-front-n ext=p-n ext;if(Q-rear=p)Q-rear=Q-fr on t;free(p);return 1;int OutputQueue(L in kQueue Q)QueuePtr p;if(Q.fr on t=Q.rear)return 0;p=Q.fro nt-n ext;while(p)prin tf(%d ,p-data);p=p-n ext;prin tf(n);return 1;void mai n() int i,n;int m;Lin kQueue

13、 Lq;printf(構(gòu)造一個(gè)空的隊(duì)列);Ini tQueue(&Lq);printf(n請輸入隊(duì)列的元素個(gè)數(shù)：”)；sca nf(%d,&n);for(i=1;i=n ;i+)En Queue(&Lq,i);printf(隊(duì)列中的元素為:);OutputQueue(Lq);DeQueue(&Lq,&m);printf(刪除隊(duì)列中的第一個(gè)元素n此時(shí)隊(duì)列中的元素為：”);OutputQueue(Lq);2)環(huán)形隊(duì)列#include #include #define MAXQSIZE 100 typedef structint *base;int front;int rear;SqQueue;vo

14、id InitQueue(SqQueue &Q)Q.base=(int *)malloc(MAXQSIZE*sizeof(int); if(!Q.base)exit(1);Q.front=Q.rear=0;int EnQueue(SqQueue *Q,int e)if(Q-rear+1)%MAXQSIZE=Q-front)return 1; Q-baseQ-rear=e;Q-rear=(Q-rear+1)%MAXQSIZE;return 0;int DeQueue(SqQueue *Q,int *e) if(Q-front=Q-rear)return 1; *e=Q-baseQ-front; Q-front=(Q-front+1)%MAXQSIZE; return 0;void outPutQMeue(SqQueue *Q) int i;for(i=Q-front;irear;i+) printf(%d ,Q-basei); printf(n);void main()SqQueue sq;int