数据结构实验报告队列的表示与实现

1、数据结构实验报告姓名学号实验地点数学楼指导教师实验 名称队列的表示与实现1、实验目的了解和掌握队列的数据类型描述及其特点；完成链队列的初始化、入队、出队、取对头元素、显示操作的实现；掌握队列的链式存储表示与基本操作算法实现；掌握队列在实际问题中的应用和基本编程技巧。2、实验方法队列的抽象数据类型定义：ADT Queue/ 数据对象：D=ai|ai ElemSet,i=1,2,n,n>=0/ 数据关系：R仁<ai-1,ai>|ai-1,ai D,i=2,n/约定其中a1端为队列头，an端为队列尾/基本操作：In itQueue(&Q) 操作结果：构造一个空队列Q。Des

2、toryQueue(&Q) 初始条件：队列 Q已存在/操作结果：队列 Q被销毁，不再存在ClearQueue(&Q) 初始条件：队列 Q已存在/操作结果：将 Q清为空队列QueueEmpty(Q)/初始条件：队列 Q已存在/操作结果：若队列 Q为空队列，则返回 TRUE否则FALSEQueueLength(Q) 初始条件：队列 Q已存在/操作结果：返回 Q的元素个数，即队列的长度GetHead(Q,&e)初始条件：Q为非空队列/操作结果：用e返回Q的队头元素EnQueue(&Q,e)初始条件：队列 Q已存在/操作结果：插入元素e为Q的新的队尾元素DeQueue(

3、&Q,&e)初始条件：Q为非空队列/操作结果：删除 Q的队头元素，并用e返回其值QueueTraverse(Q,visit()初始条件：Q已存在且非空/操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit() 失败，则操作失败。ADT Queue与线性表类似，队列有两种存储表示链队列和循环队列。/-基本操作的函数原型说明-status INitQueue(Li nkQueue & Q)/构造一个空队列 QStatus DestoryQueue(LinkQueue &Q)/销毁队列 Q,Q 不再存在Status ClearQueue

4、(LinkQueue &Q)/将 Q清为空队列Status QueueEmpty(L in kQueue Q)/若队列Q为空队列，则返回 TRUE否则返回FALSEint QueueLength(LinkQueue Q)/返回Q的元素个数，即为队列的长度Status GetHead(Li nkQueue Q,QElemType &e)/若队列不空，则用 e返回Q的队头元素，并返回 OK否则返回ERRORStatus ENQueue(LinkQueue &Q,QElemType e)/插入元素 e 为 Q的新的队尾元素Status DeQueue(L in kQueue

5、& Q,QElemType &e)/若队列不空，则删除Q的队头元素，用e返回其值，并返回 OK否则返回ERRORstatus QueueTraverse(l in kQueue Q,visit()/从队头到队尾依次对队列Q中的每个元素调用函数 visit()。一旦visit失败，则操作失败。链队列：/单链队列一一队列的链式存储结构typedef struct QNodeQElemType data;struct QNode *n ext;QNode,*QueuePtr;typedef structQueuePtr fron t;队头指针QueuePtr rear;/ 队尾指针L

6、in kQueue;/-单链队列的基本操作的算法描述-status INitQueue(Li nkQueue & Q)构造一个空队列 QQ.fro nt=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.fro nt )exit(OVERFLOW); /存储分配失败Q.fro nt ->n ext =NULL;return OK;Status DestoryQueue(LinkQueue &Q)/销毁队列 Q,Q 不再存在while(Q.fro nt)Q.rear=Q.fr ont ->n ext;free(Q.fro nt);

7、Q.fro nt =Q.rear ;return OK;Status ClearQueue(L in kQueue &Q)/将Q清为空队列Status QueueEmpty(L in kQueue Q)/若队列Q为空队列，则返回 TRUE否则返回FALSEint QueueLe ngth(L in kQueue Q)/返回Q的元素个数，即为队列的长度Status GetHead(Li nkQueue Q,QElemType &e)/若队列不空，则用e返回Q的队头元素，并返回 OK否则返回ERRORStatus ENQueue(LinkQueue &Q,QElemType

8、 e)/ 插入元素 e 为 Q的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(OVERFLOW); /存储分配失败p->data=e;p->n ext=NULL;Q.rear ->n ext =p;Q.rear =p;return OK;Status DeQueue(Li nkQueue & Q,QEIemType & e)ERROR/若队列不空，则删除Q的队头元素，用e返回其值，并返回 OK否则返回if(Q.fro nt=Q.rear) return ERROR;p=Q.fr ont->n ex

9、t;e=p_>data;Q.front->n ext=p->n ext;if(Q.rear=p) Q.rear=Q.fro nt;free(p);return OK;status QueueTraverse(l in kQueue Q,visit()/从队头到队尾依次对队列Q中的每个元素调用函数visit()。/ 一旦visit 失败，则操作失败。循环队列：/循环队列一一队列的顺序存储结构#defi ne MAXQSIZE 100 / 最大队列长度typedef structQElemType *base;初始化的动态分配存储空间int front;/头指针，若队列不空，指向

10、队列头元素int rear;/尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;/-循环队列的基本操作的算法描述-Status Ini tQueue(SqQueue & Q)/构造一个空队列QQ.base=(QElemType *)malloc(MAXQSIZE *sizeof(QEIemType);if(!Q.base) exit (OVERFLOW);/存储分配失败Q.fr on t=Q.rear=0;return OK;int QueueLength(SqQueue Q)返回Q的元素个数，即队列的长度return(Q.rear-Q.fro nt+MAXQSIZE)%M

11、AXQSIZE;status EnQueue(SqQueue &Q,QEIemType)插入元素 e 为 Q 的新的队尾元素if(Q.rear+1)%MAXQSIZE=Q.fro nt) return ERROR;/队列满Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;Status DeQueue(Squeue & Q,QElemType & e)/若队列不空，则删除 Q的队头元素，用 e返回其值，并返回 OKII否则返回ERRORif(Q.fro nt=Q.rear) return ERROR;e=Q.baseQ

12、.fr on t;Q.fro nt=(Q.fro nt+1)%MAXQSIZE;return OK;3、事先定义的常量和类型i*c#in elude <stdio.h>函数库定义 *IIEOF NULL#in elude <stri ng.h> #in elude <malloe.h>#in elude <limits.h>IImalloe();IIENT MAX#in elude <stdlib.h>#in elude <math.h>IIfloor(),fabs(),abs(),eeil(),#in elude <

13、;io.h>#i nclude <proeess.h> #in elude <iostream.h>IIeof() IIexit() IIeout,ei n函数结果状态代码*/#defi ne TRUE 1#defi ne FALSE 0#defi ne OK 1#defi ne ERROR 0#define INFEASIBLE -1II#defi ne OVERFLOW -2IItypedef int QElemType;IIElemType因为math.h中已经定义OVERFLOW 3 是变量的类型定义typedef int Status;/Status是函

14、数的类型，其值是函数结果状态代码,如OK TRUE4、实验过程链队列#in clude<stdio.h>#in clude<stdlib.h>#i nclude<process.h>#defi ne OK 1#defi ne ERROR 0#defi ne OVERFLOW 0typedef struct QNodeint data;struct QNode *n ext;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;Lin kQueue;int Ini tQueue(L in kQue

15、ue &Q)Q.rear=Q.fro nt=(QueuePtr)malloc(sizeof(QNode);if(!Q.rear)exit(OVERFLOW);Q.fro nt-> next=NULL;return OK;void QueueEmpty(L in kQueue Q)if(Q.fr on t=Q.rear)printf(" 该链队为空：”)；elseprintf("该链队不为空:");void En Queue(L in kQueue &Q,i nt e)QueuePtr p;p=(QueuePtr)malloc(sizeof(Q

16、Node);if(!p)prin tf("error");p->data=e;Q.rear- >n ext=p;Q.rear=p;printf(”元素 dN队成功 ”,e);int Enn Queue(L in kQueue &Q,i nt e) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if(!p)return ERROR;p->data=e;Q.rear- >n ext=p; Q.rear=p;return OK;void DeQueue(L in kQueue &Q)QueueP

17、tr p;if(Q.fr on t=Q.rear)printf("该链队为空");p=Q.fro nt->n ext;Q.front->n ext=p->n ext; if(Q.rear=p)Q.rear=Q.fro nt;free(p);prin tf(" 队首元素删除成功");void GetHead(Li nkQueue &Q)QueuePtr p;if(Q.fr on t=Q.rear)printf("该链队为空");p=Q.fro nt->n ext;printf(”队首元素为:%d"

18、;,p->data);void OutQueue(L in kQueue &Q) QueuePtr p;if(Q.fr on t=Q.rear)printf("该链队为空");p=Q.fro nt->n ext;while(p!=Q.rear- >n ext)prin tf("%d",p->data);p=p >n ext;void Len gthQueue(L in kQueue &Q)int f=0;QueuePtr p;if(Q.fron t=Q.rear)printf(”该队列的长度是:%d"

19、;,f);else p=Q.fr ont->n ext; while(p!=Q.rear- >n ext) p=p->n ext; f+;:%d",f);prin tf("该队列的长度是void mai n()system("cls");int flag=1,i;Lin kQueue Q;Ini tQueue(Q);队列功能菜单 *n")判断链队列是否为空，3: 进入队列，4: 取出队首元素printf( "*printf("1:初始化链队列，2:n");printf("5:输出该队列的

20、所有元素，6: 输出该队列的长度，7: 结束程序，8: 清屏n");while(flag)printf("n请输入操作符:");scan f("%d"，&i);switch(i)case 1:int e，n，k;printf(”请输入队列的长度：”);scan f("%d"，&n);printf(”请输入队列的元素：”);for(e=1;e<=n; e+)sea nf("%d"，&k);Enn Queue(Q,k);printf(”初始化链队成功");break;c

21、ase 2:QueueEmpty(Q); break;case 3:int j;prin tf("请输入要进入队列的元素");scan f("%d",&j);En Queue(Q,j); break;case 4:GetHead(Q); break;case 5:printf("该队列的元素是:");OutQueue(Q); break;case 6:Len gthQueue(Q); break;case 7:flag=0;break;case 8:system("cls"); break;printf(&

22、quot;程序结束");循环队列#in clude<stdio.h>#in clude<stdlib.h>#i nclude<process.h>#defi ne MAXSIZE 10;#defi ne OK 1;#defi ne ERROR 0;#defi ne OVERFLOW 0;typedef structint *data;int front ;int rear;SqQueue;int Ini tQueue_Sq(SqQueue &Q)Q.data=(i nt*)malloc(10*sizeof(i nt);if(!Q.data)

23、exit(0);Q.fro nt=Q.rear=0;return OK;int En Queue_Sq(SqQueue &Q,i nt e)if(Q.rear+1)%10=Q.fro nt)return ERROR;Q.dataQ.rear=e;Q.rear=(Q.rear+1)%10;return OK;void lfEmpty(SqQueue Q)if(Q.rear=Q.fro nt)printf("该循环队列是空队列n");elseprintf("该循环队列不是空队列n");void lfFull(SqQueue Q)if(Q.rear+1

24、)%10=Q.fro nt)printf(" 该循环队列已满n");elseprintf(" 该循环队列未满n");void In Queue_Sq(SqQueue &Q,i nt e)if(Q.rear+1)%10=Q.fro nt)printf(" 循环队列已满n");elseQ.dataQ.rear=e;Q.rear=(Q.rear+1)%10;printf("元素d成功进入循环队列n",e);void DeQueue_Sq(SqQueue &Q)int e;if(Q.fron t=Q.rea

25、r)printf(”循环队列为空n");e=Q.dataQ.fro nt;prin tf("循环队列队首元素是：dn",e);void DE_Sq(SqQueue &Q)int *w;w=& Q.dataQ.fro nt;Q.fro nt=Q.fro nt+1;printf("队首元数4删除成功n",*w);int Len gth_Sq(SqQueue &Q)int s;s=(Q.rear-Q.fro nt+1O);return s%10;int OutQueue_Sq(SqQueue Q)SqQueue p;P=Q;i

26、nt i,n;n=Le ngth_Sq(p);for(i=0;i< n;i+)prin tf("%d",p.datap.fro nt);p.fron t+;return OK;void Delet(SqQueue &Q) free(Q.data);printf("释放成功");void mai n() system("cls");printf(循环队列功能菜单 *prin tf("1.初始化队列输入的数不超过10个，2.判断队列是否空，3.判断队列是否满n");printf("4.将元素入队,5.取队列首元素,6.队列的长度,7.遍历循环队列,n");printf("8.删除队首元素,9.释放队列，10.清屏,0.结束程序,n");int flag=1,i;SqQueue Q;Ini tQueue_Sq(Q);while (flag)printf("请输入操作符:&quo