1、數據結構實驗報告院系光電與信息工程學院專業電子信息工程學號2011級 2班 2013年4月20日1 實驗題目實驗4 .對列的基本操作2. 需求分析(1) 編寫隊列的基本操作函數，調用上述函數實現下列操作，操作步驟如下：調用進隊函數建立一個隊列。 讀取隊列中的第一個元素。從隊列中刪除元素。輸出隊列中的所有元素。(2) 編寫環型隊列的基本操作函數。調用上述函數實現下列操作，操作步驟如下： 調用進隊函數建立一個隊列。讀取隊列中的第一個元素。從隊列中刪除元素。輸出隊列中的所有元素。隊列： 進隊操作En Queue(L in kQueue *Q, QEIemType e) 出隊操作，隊空DeQueue(

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

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

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

5、e返回操作結果：將環型隊列 Q中隊頭元素刪除，刪除的元素值通過outPutQMeue(SqQueue *Q)操作前提：環型隊列Q已存在操作結果：將環型隊列 Q中的元素顯示到屏幕上本程序包含 5 個函數： 主函數 main() 初始化隊列函數 InitQueue() 進隊函數 EnQueue() 出隊函數 DeQueue() 輸出隊列中元素函數 OutputStack() 各函數調用關系：主函數 main 調用其他四個函數函數的偽碼main()定義 SqQueue 變量 sq;定義整型變量 n,i,m;構造空的環型隊列； 輸入隊列的長度； For 循環( i=1;ifront=Q-rear= 申

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

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

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

10、5(2)環形隊列建立空隊列，程序運行后屏幕顯示：輸入隊列元素的長度 輸入5后，屏幕顯示隊列的元素：1 2 3 4 5接著屏幕又顯示：隊列中的第一個元素為：1調用出隊函數，然后輸入隊列中元素：2 3 4 58. 參考文獻數據結構(c語言版)9 附錄源程序文件如下：(1)隊列#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(構造一個空的隊列);Ini tQueue(&Lq);printf(n請輸入隊列的元素個數：”)；sca nf(%d,&n);for(i=1;i=n ;i+)En Queue(&Lq,i);printf(隊列中的元素為:);OutputQueue(Lq);DeQueue(&Lq,&m);printf(刪除隊列中的第一個元素n此時隊列中的元素為：”);OutputQueue(Lq);2)環形隊列#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