《数据结构实验报告队列的表示与实现.pdf》由会员分享，可在线阅读，更多相关《数据结构实验报告队列的表示与实现.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构实验报告数据结构实验报告姓名实验名称1 1、实验目的、实验目的了解和掌握队列的数据类型描述及其特点；完成链队列的初始化、入队、出队、取对头元素、显示操作的实现；掌握队列的链式存储表示与基本操作算法实现；掌握队列在实际问题中的应用和基本编程技巧。2 2、实验方法、实验方法队列的抽象数据类型定义：ADT Queue/数据对象：D=ai|aiElemSet,i=1，2,.。,n，n=0/数据关系：R1=ai1，aiD，i=2，.。,n /约定其中 a1端为队列头，an端为队列尾学号实验地点数学楼队列的表示与实现指导教师/基本操作：InitQueue(Q)/操作结果：构造一个空队列Q。Dest
2、oryQueue（&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 的新的队尾元素D
3、eQueue（&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（L
4、inkQueue 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,QElemTyp
5、e&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;/-单链队列的基本
6、操作的算法描述-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(LinkQueu
7、e 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)ex
8、it(OVERFLOW）；/存储分配失败pdata=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。frontnext;e=pdata;Q.frontnext=p-next；if（Q.rear=p）Q。rear=Q.front；free（p)；return OK;status QueueTraverse(linkQ
9、ueue Q,visit（）)/从队头到队尾依次对队列Q 中的每个元素调用函数visit(）./一旦 visit 失败,则操作失败。循环队列：/循环队列队列的顺序存储结构define MAXQSIZE 100 /最大队列长度typedef structQElemType base；/初始化的动态分配存储空间int front;/头指针,若队列不空，指向队列头元素int rear;/尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;/-循环队列的基本操作的算法描述-Status InitQueue（SqQueue Q)/构造一个空队列 QQ。base=（QElemType*)mall
10、oc（MAXQSIZE sizeof（QElemType）；if（!Q。base)exit（OVERFLOW）;/存储分配失败Q。front=Q.rear=0；return OK；int QueueLength（SqQueue Q）/返回 Q 的元素个数，即队列的长度return（Q.rearQ.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.re
11、ar+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 3、事先定义的常量和类型、事先定义的常量和类型/*C 函数库定义*/include stdio。h /EOF NULLinclude#include malloc.h /malloc(）；include limi
12、ts.h /ENT MAXinclude stdlib。hinclude math。h /floor（）,fabs(）,abs（）,ceil（)，#include io.h /eof（）#include process。h /exit（)#include iostream。h /cout，cin/*函数结果状态代码*/define TRUE 1#define FALSE 0define OK 1define ERROR 0#define INFEASIBLE-1/define OVERFLOW 2 /因为 math。h 中已经定义 OVERFLOW 为 3typedef int QElemTy
13、pe;/ElemType是变量的类型定义typedef int Status；/Status 是函数的类型，其值是函数结果状态代码，如OK，TRUE。4 4、实验过程、实验过程链队列链队列includestdio.hincludeincludeprocess.hdefine OK 1define ERROR 0define OVERFLOW 0typedef struct QNodeint data;struct QNode next；QNode，QueuePtr；typedef structQueuePtr front;QueuePtr rear；LinkQueue；int InitQueu
14、e(LinkQueue&Q）Q。rear=Q。front=（QueuePtr)malloc（sizeof(QNode)）;if(!Q.rear)exit(OVERFLOW）;Q。frontnext=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)；pdata=e
15、;Q。rearnext=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.frontnext=pnext;if（Q。rear=p）Q.rear=
16、Q.front;free（p）；printf（”队首元素删除成功”);void GetHead（LinkQueue Q）QueuePtr p；if(Q。front=Q.rear)printf（”该链队为空”);p=Q.front-next；printf(”队首元素为：%d”，pdata);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（LinkQ
17、ueue Q）int f=0;QueuePtr p；if(Q。front=Q。rear)printf(该队列的长度是:d,f）；elsep=Q.front-next;while（p!=Q.rear-next)p=pnext;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:结束程序，
18、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
19、（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#includestdlib.hinclude#define MAXSIZE 10；define OK 1；define ERROR 0;define OVERFLOW 0;typedef structint data;int front；int rear;SqQueue；int Init
20、Queue_Sq（SqQueue&Q）Q。data=（int*）malloc（10sizeof(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”）;v
21、oid 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）;elseQ.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.fr
22、ont;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 s10；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；v
23、oid 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）；while（flag)printf(请输入操作符:”)；scanf（”
24、d”，&i）；switch(i）case 1:int n，j，m;printf（请输入初始化元素的个数:”）;scanf(”d，&n）;printf（请输入元素：)；for（j=0;jn;j+)scanf(%d,&m)；EnQueue_Sq(Q,m)；break；case 2:IfEmpty（Q);break；case 3：IfFull（Q）；break；case 4:int k;printf（”请输入要进入循环队列的元素:”）;scanf(%d”,&k）；InQueue_Sq（Q,k）;break;case 5：DeQueue_Sq(Q）；break;case 6:int f；f=Lengt
25、h_Sq（Q);printf(该循环队列的长度为:dn,f）；break;case 7：printf(”该循环队列为:”）；OutQueue_Sq(Q)；printf（”n”);break；case 8：DE_Sq(Q)；break;case 9:Delet(Q）;break;case 10：system(”cls);break；case 0：flag=0；break；printf（”程序结束”）;4 4、实验总结、实验总结队列是一种先进先出的线性表，它只允许在表的一端进行插入,而在另一端删除元素,在 C 语言中不能用动态分配的一维数组来实现循环队列，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。本次实验通过对队列的链式表示与实现、队列的顺序表示与实现，加深了对链队列和循环队列的特点的理解,并且熟悉了VC6.0集成环境,虽然在调试过程中遇到了一些问题,但经分析后达到了预期的结果.