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

1、數(shù)據(jù)結構實驗報告院系 光電與信息工程學院 專業(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, QElemType e)出隊操作，隊空 De

2、Queue(LinkQueue *Q, QElemType *e)輸出隊列中元素 0utputQueue(LinkQueue Q)環(huán)型隊列：進隊操作，返回1為隊滿 EnQueue(SqQueue *Q, QElemType e)出隊操作，返回1為隊空 DeQueue(SqQueue *Q, QElemType *e)輸出隊列中元素 outPutQMeue(SqQueue Q)輸入形式：整型數(shù)。 3概要設計（1）鏈接隊列 ADT QNode 數(shù)據(jù)對象：D=ai|aiIntegerSet,i=0,1,2,n,n0 結構關系：R=<ai,ai+1>|ai,ai+1 D 基本操作： Ini

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

4、nitQueue() 進隊函數(shù)EnQueue() 出隊函數(shù)DeQueue() 輸出隊列中元素函數(shù) OutputStack()各函數(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)形隊列ADT SqQueue 數(shù)據(jù)對象：D=ai|aiIntegerSet,i=0,1,2,n,n0 結構關系：R=<ai,ai+1>|ai,ai+

5、1 D 基本操作： InitQueue(SqQueue &Q) 操作前提：Q是一個未初始化的環(huán)型隊列 操作結果：將Q初始化為一個空的環(huán)型隊列 EnQueue(SqQueue *Q,int e) 操作前提：環(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ù) InitQue

6、ue() 進隊函數(shù)EnQueue() 出隊函數(shù)DeQueue() 輸出隊列中元素函數(shù) OutputStack()各函數(shù)調用關系：主函數(shù)main調用其他四個函數(shù)函數(shù)的偽碼main（）定義SqQueue 變量sq;定義整型變量n,i,m;構造空的環(huán)型隊列；輸入隊列的長度；For循環(huán)（i=1;i<=n;i+）調用EnQueue函數(shù)；輸出隊列元素；刪除對頭元素；輸出隊列元素；4 詳細設計（1）鏈接隊列（1） 類型定義typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr fro

7、nt;QueuePtr rear;LinkQueue;基本操作的偽碼算法（1）初始化void InitQueue(LinkQueue *Q) Q->front=Q->rear=申請新結點; 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

8、)出隊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;；釋放p的空間；返回1；（4）輸出元素int OutputQueue(LinkQueue Q) 定義QueuePtr變量 p；如果隊空則返回0；p=Q.front->next;while(p)printf("%d ",p->data);p=p-&g

9、t;next;printf("n");返回1;（2）環(huán)形隊列 類型定義typedef structint *base;int front;int rear;SqQueue;基本操作的偽碼算法（1）初始化void InitQueue(SqQueue &Q) Q.base=申請新的空間；如果申請失敗，結束程序；Q.front=Q.rear=0;（2）進隊 int EnQueue(SqQueue *Q,int e) 如果隊滿了則返回1；Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXQSIZE;返回0；出隊int D

10、eQueue(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循環(huán)（i=Q->front;i<Q->rear;i+)輸出Q->basei；換行；5 調試分析 鏈接隊列：調試是出現(xiàn)錯誤，經(jīng)過檢查發(fā)現(xiàn)在某些地方分號用中文表示，出現(xiàn)空指針問題。環(huán)型隊列：出現(xiàn)空指針問題，內存不能讀取等6 使用

11、說明 （1）鏈接隊列：程序執(zhí)行過程如下：提示用戶輸入元素個數(shù)；用戶按要求輸入一個整型數(shù)；程序輸出構造好的鏈接隊列；調用出隊函數(shù)，并把剩余元素顯示在屏幕上；（2）環(huán)型隊列：程序執(zhí)行過程如下：提示用戶輸入隊列元素個數(shù)；用戶按要求輸入一個整型數(shù)；程序用輸入的整型數(shù)構建一個環(huán)型隊列，并輸出隊列元素；調用出棧函數(shù)，刪除棧頂，顯示棧中元素； 7 測試結果（1）鏈接隊列構造一個空的鏈接隊列后，屏幕顯示：請輸入隊列的元素個數(shù)：輸入5后，屏幕顯示建立的隊列元素：1 2 3 4 5調用出隊函數(shù)后，屏幕顯示：2 3 4 5（2）環(huán)形隊列建立空隊列，程序運行后屏幕顯示：輸入隊列元素的長度輸入5后，屏幕顯示隊列的元素：

12、1 2 3 4 5接著屏幕又顯示：隊列中的第一個元素為：1調用出隊函數(shù)，然后輸入隊列中元素：2 3 4 58. 參考文獻數(shù)據(jù)結構（c語言版）9附錄源程序文件如下：（1）鏈接隊列 #include<stdlib.h> #include<stdio.h> typedef struct QNode int data; struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; void InitQueue(LinkQueue *Q) Q->fr

13、ont=Q->rear=(QNode *)malloc(sizeof(QNode); Q->front->next=NULL; void EnQueue(LinkQueue *Q,int e) QueuePtr p; 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; int DeQueue

14、(LinkQueue *Q,int *e) QueuePtr p; if(Q->front=Q->rear)return 0; p=Q->front->next; *e=p->data; Q->front->next=p->next; if(Q->rear=p)Q->rear=Q->front; free(p); return 1; int OutputQueue(LinkQueue Q) QueuePtr p; if(Q.front=Q.rear)return 0; p=Q.front->next; while(p) p

15、rintf("%d ",p->data); p=p->next; printf("n"); return 1; void main() int i,n; int m; LinkQueue Lq; printf("構造一個空的鏈接隊列"); InitQueue(&Lq); printf("n請輸入隊列的元素個數(shù):"); scanf("%d",&n); for(i=1;i<=n;i+) EnQueue(&Lq,i); printf("隊列中的元素為

16、:"); OutputQueue(Lq); DeQueue(&Lq,&m); printf("刪除隊列中的第一個元素n此時隊列中的元素為:"); OutputQueue(Lq); （2）環(huán)形隊列 #include<stdio.h> #include<stdlib.h> #define MAXQSIZE 100 typedef struct int *base; int front; int rear; SqQueue; void InitQueue(SqQueue &Q) Q.base=(int *)malloc(M

17、AXQSIZE*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;i<Q->rear;i+) printf("%d ",Q->basei); printf("n"); void main() SqQueue sq; int n,i,m; printf("構造空的環(huán)型隊列n"); InitQue