链队列存储表示及基本操作的实现

石家庄经济学院实验报告学院:数理学院专业:数学与应用数学班级:一班学号:XXXXXXXX姓名:XXXX信息工程学院计算机实验中心制实验题目：链队列存储表示及基本操作的实现实验室：260设备编号：402完成日期：一、实验目的1.掌握队列的思想及其存储实现。2.掌握队列的常见算法的程序实现。二、实验内容1.建立一个链式空队列，并能够完成出队、入队及求队长等基本操作。。三、实验的内容及完成情况1.需求分析(1)链队列的抽象数据类型ADT的描述及实现。本实验实现使用Visualc++6.0实现线性表顺序存储结构的表示及操作。具体实现要求：(2)完成链式队列的表示和实现。(3)实现链式队列的建立和初始化。(4)实现链式队列的入队、出队、求队长等操作。2．概要设计抽象数据类型队列的定义：ADTQueue{数据对象：D={ai|ai∈ElemSet,i=1,2,……,n,n≥0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,……,n}约定其中a1端为队列头，an端为队列尾。基本操作：InitQueue(&Q)

操作结果：构造一个空队列Q。EnQueue(&Q,e)

初始条件：队列Q已存在。

操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)

初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。Queuelength(&Q)

初始条件：队列Q已存在。

操作结果：返回Q的元素个数，即队列长度。DestroyQueue(LinkQueue&Q)//销毁队列Q，队列Q不再存在}ADTQueue;3．详细设计（1）抽象数据类型队列的表示和实现//链式队列结构类型typedefstructQNode{Qelemtypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;//构造一个空队列statusInitQueue(LinkQueue&Q){//构造一个空的队列Q Q.front=Q.rear=(QueuePtr)malloc(100*sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.rear->next=NULL; returnOK;}//插入队尾元素statusEnQueue(LinkQueue&Q,Qelemtypee){//插入元素e为Q的新的队尾元素 p=(QueuePtr)malloc(100*sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK;}//删除队头元素statusDeQueue(LinkQueue&Q,Qelemtype&e){//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；//否则返回ERROR; if(Q.rear==Q.front)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); returnOK;}//求队列长度voidQueuelength(LinkQueue&Q){ n=0;p=Q.front->next;while(p!=NULL){ n++;p=p->next;} printf("链队列长度为：%d\n",n);}//销毁队列statusDestroyQueue(LinkQueue&Q){//销毁队列 while(Q.front) { Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } printf("队列已销毁！\n"); returnOK;}（2）主函数的伪码算法voidmain()//主函数{ inta; printf("》》》》》》》》>>数据结构实验二<<《《《《《《《《\n"); printf("**********链队列存储表示及基本操作的实现*********\n"); do {menu(); printf("请按提示输入指令:"); scanf("%d",&a); switch(a) {//调用各函数 case1:{ input(); output(Q); }break; case2: Queuelength(Q);break; case3:{ printf("请输入入队元素："); scanf("%d",&e); if(EnQueue(Q,e)==1)output(Q); }break; case4:if(DeQueue(Q,e)==1) { output(Q); printf("出队元素为：%d\n",e); }elseprintf("队列为空~无法执行删除操作~\n");break; case5: DestroyQueue(Q);break; case0:printf("谢谢您的使用,再见(*^__^*)!\n"); return; default: printf("输入有误,请重新输入(*^__^*)\n"); } }while(a!=0);}4.调试分析(1) 调试过程中出现的问题经过上次试验的练习，这次调试过程没有出现变量定义问题等的小错误；主要是逻辑错误，可以通过组建和编译，但是运行的时候达不到要求。通过简单的修改就可以啦！(2) 经验和体会1.多思考、多尝试才能更好的完成程序的编写。2.算法是程序编写的灵魂，透彻的了解算法有助于编写程序。3.编写程序时细心才能少出错！(3) 算法的时空分析和改进入队操作：T(n)=O(1)；出队操作：T(n)=O(1)；求队列长度：T(n)=O(n)；销毁队列：T(n)=O(n)；5．用户使用说明打开可执行程序，即VisualC++6.0环境下，,参照用户选择界面提示即可使用本程序6．测试结果演示操作如下：运行程序输入指令：1创建队列并初始化初始化完毕，输入指令：3入队操作入队操作完毕，输入指令：4出队操作出队操作完毕，输入指令：2输出队列长操作完毕，输入指令：5销毁队列演示完毕，输入指令：0退出系统7．附录源程序清单：#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintQelemtype;typedefint status;typedefstructQNode{Qelemtypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;inte,i,n;QueuePtrp;LinkQueueQ;statusInitQueue(LinkQueue&Q){//构造一个空的队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL; returnOK;}statusEnQueue(LinkQueue&Q,Qelemtypee){//插入元素e为Q的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK;}statusDeQueue(LinkQueue&Q,Qelemtype&e){//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；//否则返回ERROR; if(Q.rear==Q.front)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); returnOK;}statusQueuelength(LinkQueue&Q){ if(Q.rear==Q.front)returnERROR; n=0;p=Q.front->next;while(p!=NULL){ n++;p=p->next;} printf("链队列长度为：%d\n",n); returnOK;}statusDestroyQueue(LinkQueue&Q){//销毁队列 while(Q.front) { Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } printf("队列已销毁！\n"); returnOK;}voidinput(){ if(InitQueue(Q)!=1)printf("分配空间失败！"); printf("输入将建立链队列元素的个数：n="); scanf("%d",&n);for(i=1;i<=n;i++){ printf("链队列第%d个元素的值为：",i);scanf("%d",&e);EnQueue(Q,e);}}voidoutput(LinkQueue&Q){p=Q.front->next;printf("链队列元素依次为：");while(p!=NULL){ printf("%d-->",p->data);p=p->next;}printf("\n");}voidmenu(){//菜单函数 printf("==================================================\n"); printf("★1建立队列并初始化\n"); printf("★2输出队列长度\n"); printf("★3元素入队\n"); printf("★4元素出队\n"); printf("★5销毁队列\n");printf("★0退出系统\n"); printf("==================================================\n");}//menuvoidmain()//主函数{ inta; printf("》》》》》》》》>>数据结构实验二<<《《《《《《《《\n"); printf("**********链队列存储表示及基本操作的实现*********\n"); do {menu(); printf("请按提示输入指令:"); scanf("%d",&a); switch(a) {//调用各函数 case1:{ input(); output(Q); }break; case2: Queuelength(Q);break; case3:{ printf("请输入入队元素："); scanf("%d",&e); if(EnQueue(Q,e)==1)output(Q); }break; case4:if(DeQueue(Q,e)==1) { output(Q); printf("出队元素为：%d\n",e); }