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

数据结构实验报告 姓名 学号 号 实验地点 数学楼 指导教师 实验 名称 队列的表示与实现 1、实验目的 了解和掌握队列的数据类型描述及其特点； 完成链队列的初始化、入队、出队、取对头元素、显示操作的实现； 掌握队列的链式存储表示与基本操作算法实现； 掌握队列在实际问题中的应用和基本编程技巧。 2、实验方法 队列的抽象数据类型定义： ADT Queue{ //数据对象:D={a[i]|a[i]∈ElemSet,i=1,2,...,n,n=0} //数据关系：R1={a[i-1],a[i]|a[i-1],a[i]∈D,i=2,...,n} //约定其中a[1]端为队列头，a[n]端为队列尾 //基本操作： InitQueue(Q)//操作结果：构造一个空队列Q。 DestoryQueue(Q)//初始条件：队列Q已存在 //操作结果：队列Q被销毁，不再存在 ClearQueue(Q)//初始条件：队列Q已存在 //操作结果：将Q清为空队列 QueueEmpty(Q)//初始条件：队列Q已存在 //操作结果：若队列Q为空队列，则返回TRUE,否则FALSE QueueLength(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)//构造一个空队列Q Status DestoryQueue(LinkQueue Q)//销毁队列Q,Q不再存在 Status ClearQueue(LinkQueue Q)//将Q清为空队列 Status QueueEmpty(LinkQueue Q) //若队列Q为空队列，则返回TRUE，否则返回FALSE int QueueLength(LinkQueue Q)//返回Q的元素个数，即为队列的长度 Status GetHead(LinkQueue Q,QElemType e) //若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR Status ENQueue(LinkQueue Q,QElemType e)//插入元素e为Q的新的队尾元素 Status DeQueue(LinkQueue Q,QElemType e) //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR status QueueTraverse(linkQueue Q,visit()) //从队头到队尾依次对队列Q中的每个元素调用函数visit()。 一旦visit失败，则操作失败。 链队列： //单链队列——队列的链式存储结构 typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front;//队头指针 QueuePtr rear;//队尾指针 }LinkQueue; //-----单链队列的基本操作的算法描述------ status INitQueue(LinkQueue Q){//构造一个空队列Q Q.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 ClearQueu