队列子系统

电子信息学院实验报告书课程名：数据结构题目：队列子系统实验类别验证班级：BX1001学号：101003020141姓名：赵艳2011年10月11日《算法设计与分析》实验报告-1-1、实验目的（1)掌握栈的特点及其描述方法；（2)用链式存储结构实现一个队列；（3)掌握队列的各种基本操作；（4)掌握队列的简单应用程序。2、实验内容（1）设计一个字符型的链队列。（2）编写进队、出队、读队头元素、显示队列中全部元素的程序。（3）设计一个输入限制性的双队列，要求：①输入只能在一端进行，而输出可以选择从队头输出或队尾输出，全部选择完毕后能显示所选择的输出结果。②设计一个选择式菜单，以菜单方式选择队列的各种基本操作。菜单形式如下：队列子系统**********************************************1---------进队**2---------出队**3---------读队头元素**4---------显示**5---------双队列**0---------退出***********************************************请选择菜单号（0—5）：3、实验步骤和源程序（1）实验步骤开始定义队列元素的类型，然后定义五个函数，分别是进队函数、出队函数、显示队列函数、读队首元素函数、从两端输出队列函数，最后是主函数对这几个函数的调用。进栈函数主要是开辟空间，构造新结点，并将新结点插入队尾。出栈是通过将队头结点从队列中断开，最后一个结点出队回收头结点来实现。读队头函数是通过断开队头结点，赋值于x带回主调函数来实现。从队尾出队和从队头出队过程相似，都是首先判断队是否为空，再使元素出队来实现的。主函数是运用printf（）创造一个选择菜单还有switch（）选择语句以及对定义过的函数的调用来实现的。（2）源程序#includestdio.htypedefstructqueuenode《算法设计与分析》实验报告-2-{intdata;structqueuenode*next;}QueueNode;typedefstruct{QueueNode*front,*rear;}LinkQueue;voidInQueue(LinkQueue*q){intx;QueueNode*p=newQueueNode;printf(\n\t\t请键入一个整数:);scanf(%d,&x);getchar();p-data=x;p-next=NULL;if(q-front==NULL)q-front=p;elseq-rear-next=p;q-rear=p;if(p)printf(\n\t\t%d进队成功!,x);}intOutQueue(LinkQueue*q,int*v){QueueNode*p;if(q-front==NULL)return0;else《算法设计与分析》实验报告-3-{p=q-front;*v=p-data;q-front=p-next;if(q-front=NULL)q-rear=NULL;deletep;return1;}}voidShowQueue(LinkQueue*q){QueueNode*p=q-front;if(p==NULL)printf(\n\t\t队列为空!\n);else{printf(\n\t\t队列中的元素为:);while(p!=NULL){printf(%6d,p-data);p=p-next;}printf(\n);}}voidReadFront(LinkQueue*q){if(q==NULL||q-front==NULL)printf(\n\t\t队列为空!没有队顶元素!\n);else《算法设计与分析》实验报告-4-printf(\n\t\t队首元素是:%4d\n,q-front-data);}#defineQUEUEMAX20intqueue[QUEUEMAX];intfront=-1;intrear=-1;voidInQueue(intval){rear=(rear++)%QUEUEMAX;if(front==rear)printf(\n\t\t队列已满!);elsequeue[rear]=val;}intOutQueue_rear(){intt;if(front==rear)return-1;t=queue[rear--];if(rear0&&front!=-1)rear=QUEUEMAX-1;returnt;}intOutQueue_front(){intt;if(front==rear)return-1;t=queue[++front];《算法设计与分析》实验报告-5-if(front==QUEUEMAX)front=0;returnt;}voidDQ(){intchoice;intout[5];intin[5]={5,4,3,2,1};intt,pos=0,i;for(i=0;i5;i++)InQueue(in[i]);printf(\n\t\t初始化顺序是:);for(i=0;i5;i++)printf([%d],in[i]);printf(\n\n\t\t1------从头出队2------从尾出队\n\n);while(front!=rear){printf(\t\t请输入选择(1或2):);scanf(%d,&choice);switch(choice){case1:t=OutQueue_front();out[pos++]=t;break;case2:t=OutQueue_rear();out[pos++]=t;break;《算法设计与分析》实验报告-6-}}printf(\n\t\t数据输出顺序是:);for(i=0;i5;i++)printf([%d],out[i]);printf(\n);getchar();}voidmain(){LinkQueue*q=newLinkQueue;intval,i=1;charw,choice;q-front=q-rear=NULL;while(i){printf(\n);printf(\n\t\t队列子系统);printf(\n\t\t**************************************************************);printf(\n\t\t*1------进队*);printf(\n\t\t*2------出队*);printf(\n\t\t*3------读队头元素*);printf(\n\t\t*4------显示*);printf(\n\t\t*5------双队列*);printf(\n\t\t*6------返回*);printf(\n\t\t**************************************************************);printf(\n\t\t请选择菜单号(0--5):);《算法设计与分析》实验报告-7-scanf(%c,&choice);getchar();switch(choice){case'1':InQueue(q);break;case'2':if(OutQueue(q,&val)==0)printf(\n\t\t队列为空!\n);elseprintf(\n\t\t出队元素为:%d,val);break;case'3':ReadFront(q);break;case'4':ShowQueue(q);break;case'5':DQ();break;case'0':i=0;break;default:;}if(choice=='1'||choice=='2'||choice=='3'||choice=='4'||choice=='5'){printf(\n\n\t\t按【Enter】键继续,按任意键返回主菜单,\n);《算法设计与分析》实验报告-8-w=getchar();if(w!='\xA')i=0;}}}4.测试数据与实验结果（可以抓图粘贴）《算法设计与分析》实验报告-9-5.结果分析与实验体会程序成功运行，结果准确，这个实验式书上原来的程序，我在看题目的过程中觉得每个程序分开来其实不难。而且刚刚看过栈相关函数，所以觉得栈和队列处理有很多共同之处，看起来就相对简单了。进队和出队时要判断队满和队空，而且判断方法和栈的处理有一定区别，这个值得注意。读队首元素时也要记得判断队是否为空，队列只能单端输入，但是可以双端输出，我们可以选择在队尾输出或者队首输出。在输出队列元素时，队列头尾两个指针要注意，很容易出错，一不小心就会使元素不能调用。我们在编写程序时更应该全神贯注，否则容易出错，后面检查时错误较多会影响我们编程的积极性，而且不易发现。所以我们在编程时能不错尽量不要出错。最后，我觉得这个验证性实验很有意义，我们对队列的性质更加了解了。