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

数据结构实验报告姓名学号号实验地点数学楼指导教师实验名称队列的表示与实现1、实验目的了解和掌握队列的数据类型描述及其特点；完成链队列的初始化、入队、出队、取对头元素、显示操作的实现；掌握队列的链式存储表示与基本操作算法实现；掌握队列在实际问题中的应用和基本编程技巧。2、实验方法队列的抽象数据类型定义：ADT Queue/数据对象:D=ai|aiElemSet,i=1,2,.,n,n=0/数据关系：R1=|ai-1,aiD,i=2,.,n /约定其中a1端为队列头，an端为队列尾/基本操作：InitQueue(&Q)/操作结果：构造一个空队列Q。DestoryQueue(&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(&Q,&e)/初始条件：Q为非空队列 /操作结果：删除Q的队头元素，并用e返回其值QueueTraverse(Q,visit()/初始条件：Q已存在且非空 /操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ADT Queue与线性表类似，队列有两种存储表示链队列和循环队列。/-基本操作的函数原型说明-status INitQueue(LinkQueue &Q)/构造一个空队列QStatus DestoryQueue(LinkQueue &Q)/销毁队列Q,Q不再存在Status ClearQueue(LinkQueue &Q)/将Q清为空队列Status QueueEmpty(LinkQueue Q)/若队列Q为空队列，则返回TRUE，否则返回FALSEint QueueLength(LinkQueue Q)/返回Q的元素个数，即为队列的长度Status GetHead(LinkQueue Q,QElemType &e)/若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERRORStatus ENQueue(LinkQueue &Q,QElemType e)/插入元素e为Q的新的队尾元素Status DeQueue(LinkQueue &Q,QElemType &e)/若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERRORstatus QueueTraverse(linkQueue Q,visit()/从队头到队尾依次对队列Q中的每个元素调用函数visit()。一旦visit失败，则操作失败。链队列：/单链队列队列的链式存储结构typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;/队头指针QueuePtr rear;/队尾指针LinkQueue;/-单链队列的基本操作的算法描述-status INitQueue(LinkQueue &Q)/构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front )exit(OVERFLOW); /存储分配失败Q.front -next =NULL;return OK;Status DestoryQueue(LinkQueue &Q)/销毁队列Q,Q不再存在while(Q.front)Q.rear=Q.front -next;free(Q.front );Q.front =Q.rear ;return OK;Status ClearQueue(LinkQueue &Q)/将Q清为空队列Status QueueEmpty(LinkQueue Q)/若队列Q为空队列，则返回TRUE，否则返回FALSEint QueueLength(LinkQueue Q)/返回Q的元素个数，即为队列的长度Status GetHead(LinkQueue Q,QElemType &e)/若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERRORStatus ENQueue(LinkQueue &Q,QElemType e)/插入元素e为Q的新的队尾元素p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(OVERFLOW); /存储分配失败p-data=e;p-next=NULL;Q.rear -next =p;Q.rear =p;return OK;Status DeQueue(LinkQueue &Q,QElemType &e)/若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERRORif(Q.front=Q.rear) return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;status QueueTraverse(linkQueue Q,visit()/从队头到队尾依次对队列Q中的每个元素调用函数visit()。/一旦visit失败，则操作失败。循环队列：/循环队列队列的顺序存储结构#define MAXQSIZE 100 /最大队列长度typedef structQElemType *base;/初始化的动态分配存储空间int front; /头指针，若队列不空，指向队列头元素int rear; /尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;/-循环队列的基本操作的算法描述-Status InitQueue(SqQueue &Q)/构造一个空队列QQ.base=(QElemType *)malloc(MAXQSIZE *sizeof(QElemType);if(!Q.base) exit (OVERFLOW);/存储分配失败Q.front=Q.rear=0;return OK;int QueueLength(SqQueue Q)/返回Q的元素个数，即队列的长度return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;status EnQueue(SqQueue &Q,QElemType)/插入元素e为Q的新的队尾元素if(Q.rear+1)%MAXQSIZE=Q.front) return ERROR;/队列满Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;Status DeQueue(Squeue &Q,QElemType &e)/若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；/否则返回ERRORif(Q.front=Q.rear) return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;3、事先定义的常量和类型/*C函数库定义*/#include /EOF NULL#include #include /malloc();#include /ENT MAX#include #include /floor(),fabs(),abs(),ceil(),#include /eof()#include /exit()#include /cout,cin/*函数结果状态代码*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/#define OVERFLOW -2 / 因为math.h中已经定义OVERFLOW为3typedef int QElemType;/ElemType是变量的类型定义typedef int Status;/Status是函数的类型，其值是函数结果状态代码,如OK，TRUE。4、实验过程链队列#include#include#include#define OK 1#define ERROR 0#define OVERFLOW 0typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q)Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode);if(!Q.rear)exit(OVERFLOW);Q.front-next=NULL;return OK;void QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)printf(该链队为空:);elseprintf(该链队不为空:);void EnQueue(LinkQueue &Q,int e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)printf(error);p-data=e;Q.rear-next=p;Q.rear=p;printf(元素%d入队成功,e);int EnnQueue(LinkQueue &Q,int e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)return ERROR;p-data=e;Q.rear-next=p;Q.rear=p; return OK;void DeQueue(LinkQueue &Q)QueuePtr p;if(Q.front=Q.rear)printf(该链队为空);p=Q.front-next;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);printf(队首元素删除成功);void GetHead(LinkQueue &Q)QueuePtr p;if(Q.front=Q.rear)printf(该链队为空);p=Q.front-next;printf(队首元素为:%d,p-data);void OutQueue(LinkQueue &Q)QueuePtr p;if(Q.front=Q.rear)printf(该链队为空);p=Q.front-next;while(p!=Q.rear-next)printf(%d,p-data);p=p-next;void LengthQueue(LinkQueue &Q)int f=0;QueuePtr p;if(Q.front=Q.rear)printf(该队列的长度是:%d,f);elsep=Q.front-next;while(p!=Q.rear-next)p=p-next;f+; printf(该队列的长度是:%d,f); void main()system(cls);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(*链队列功能菜单*n);printf(1:初始化链队列, 2:判断链队列是否为空, 3:进入队列, 4:取出队首元素n);printf(5:输出该队列的所有元素, 6:输出该队列的长度, 7:结束程序, 8:清屏n);while(flag)printf(n请输入操作符:);scanf(%d,&i);switch(i)case 1:int e,n,k;printf(请输入队列的长度:);scanf(%d,&n);printf(请输入队列的元素:);for(e=1;e=n;e+)scanf(%d,&k);EnnQueue(Q,k);printf(初始化链队成功);break;case 2:QueueEmpty(Q);break;case 3:int j;printf(请输入要进入队列的元素);scanf(%d,&j);EnQueue(Q,j);break;case 4:GetHead(Q);break;case 5:printf(该队列的元素是:);OutQueue(Q);break;case 6:LengthQueue(Q);break;case 7:flag=0;break;case 8:system(cls);break;printf(程序结束);循环队列#include#include#include#define MAXSIZE 10;#define OK 1;#define ERROR 0;#define OVERFLOW 0;typedef struct int *data; int front ; int rear;SqQueue;int InitQueue_Sq(SqQueue &Q) Q.data=(int*)malloc(10*sizeof(int);if(!Q.data)exit(0);Q.front=Q.rear=0;return OK;int EnQueue_Sq(SqQueue &Q,int e)if(Q.rear+1)%10=Q.front)return ERROR;Q.dataQ.rear=e;Q.rear=(Q.rear+1)%10;return OK;void IfEmpty(SqQueue Q)if(Q.rear=Q.front)printf(该循环队列是空队列n);elseprintf(该循环队列不是空队列n);void IfFull(SqQueue Q)if(Q.rear+1)%10=Q.front)printf(该循环队列已满n);elseprintf(该循环队列未满n);void InQueue_Sq(SqQueue &Q,int e)if(Q.rear+1)%10=Q.front)printf(循环队列已满n);else Q.dataQ.rear=e; Q.rear=(Q.rear+1)%10; printf(元素%d成功进入循环队列n,e);void DeQueue_Sq(SqQueue &Q)int e;if(Q.front=Q.rear)printf(循环队列为空n);e=Q.dataQ.front;printf(循环队列队首元素是:%dn,e);void DE_Sq(SqQueue &Q)int *w;w=&Q.dataQ.front;Q.front=Q.front+1;printf(队首元数%d删除成功n,*w);int Length_Sq(SqQueue &Q)int s; s=(Q.rear-Q.front+10);return s%10;int OutQueue_Sq(SqQueue Q)SqQueue p;p=Q;int i,n;n=Length_Sq(p);for(i=0;in;i+)printf(%d,p.datap.front);p.front+;return OK;void Delet(SqQueue &Q)free(Q.data);printf(释放成功);void main()system(cls);printf(*循环队列功能菜单*n);printf(1.初始化队列输入的数不超过10个, 2.判断队列是否空, 3.判断队列是否满, n);printf(4.将元素入队, 5.取队列首元素, 6.队列的长度, 7.遍历循环队列,n);printf(8.删除队首元素, 9.释放队列, 10.清屏, 0.结束程序,n);int flag=1,i;SqQueue Q;InitQueue_Sq(Q);w