队列的链式表示和实现(含源程序)

数学与计算科学学院实验报告实验项目名称队列的链式表示和实现所属课程名称数据结构实验类型验证型实验日期2013年11月14日班级学号姓名成绩1一、实验概述：【实验目的】1.队列的逻辑结构特征1.1是一种只允许在表的一端进行插入，在另一端删除元素的线性表；1.2是一种先进先出的线性表。2.掌握队列的特点及单链队列在链式存储结构上的实现。【实验原理】1.队列的特点1.1队列是一种先进先出的特殊线性表；1.2队列中，队尾允许插入元素，队头允许删除元素。2.单链队列的类C语言------------队列的链式存储结构-----------typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;【实验环境】VC++6.0二、实验内容：【实验方案】编写主函数，调用初始化建空队列、插入、删除、销毁队列的算法，调试运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）一．典型错误举例21.运行算法时遇到的典型错误例1：错误分析：仔细观察会发现此处是大小输入错误，导致报出错误P为定义，应该把大写的P改为小写p。由于p的大小写区别不大，因此每次在输入时一定要格外小心，避免再出现同样的错误。例2:错误分析：表示未对P进行定义，双击错误行，指向p=(QueuePtr)malloc(sizeof(QNode));返回查看之后，发现不是把小写p输成大写P了，所以错误就是p没有给出定义。故在所指行的前面加上QueuePtrp;对p进行定义就可以了。2.编写主函数时遇到的典型错误例：调试结果：错误分析：表示DestroyQueue未定义，3双击错误行，显示：这里显示的DestroyQueue未定义的错误只可能是DestroyQueue拼写错误，错误所指行拼写无误，返回上面查找DestroyQueue的拼写错误：将DestoryQueue改为DestroyQueue，再次调试：输入主函数之前运行算法时，由于后面没有出现DestroyQueue，故不会出现前后不一致的情况，便不会报错。3.完善主函数时遇到的典型错误例：调试结果：运行结果：4错误分析：观察以上现象发现调试无误，但是在输完6个数后，却没有重新打印出顺序栈，返回主函数初始化建空栈的重新打印输入的顺序栈一行查找错误：发现打印顺序栈的语句的位置放错了，应该放在for语句的前面：改正之后运行出结果：5在程序运行的过程中，往往容易忘记程序中算法的顺序，导致运行时不知怎么操作，于是在主函数中添加汉字提示，会使得程序运行起来更加方便快捷。二．测试数据1.前面几次运行，输入栈的数字小而且单一，没有代表性，于是需换些比较复杂一点的数字进行测试。第一组测试，结果：第二组测试，结果：6第三组测试，结果：观察上面的输出窗口，发现此三组数据测试无误。2．当实际输入的元素个数小于理论上应该输入的个数n时，就按了Enter键，第三行不会显示任何数据，但是有一个闪动光标暗示我们还需继续输入，当输入个数刚好等于n时，按Enter键，还是一样会重新打印输入的顺序栈。3.当输入到栈中的元素不是数字而是字母时会报错：7栈是一种特殊的线性表，而线性表本身就是一种数据结构，因此输入字母是不对的。【实验结论】（结果）【实验小结】（收获体会）本次实验不仅加深了我对顺序栈特点的理解，掌握了顺序栈的基本运算，而且实践了用顺序存储结构实现顺序栈的基本操作。几次实验之后，敲算法不出错误对我们来说已经不是难事了，还记得第一次实验的时候，一堆输入语法错误。因此敲算法不仅锻炼人的耐力，更能体现一个人做事的态度，多敲算法，多实践总归是好的。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.8成绩：指导教师签名：批阅日期：附录1：源程序#includestdio.h#includestdlib.h#defineOK1#defineOVERFLOW-2#defineERROR0typedefintStatus;typedefintQElemType;typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//对头指针QueuePtrrear;//队尾指针}LinkQueue;StatusInitQueue(LinkQueue&Q){//构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);//存储分配失败9Q.front-next=NULL;returnOK;}StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素QueuePtrp;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；//否则返回ERRORQueuePtrp;if(Q.front==Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}10StatusDestroyQueue(LinkQueue&Q){//销毁队列Qwhile(Q.front){Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;}returnOK;}voidmain(){LinkQueueQ;InitQueue(Q);//初始化建空队列QueuePtrq,p;QElemTypee,n,i;printf(请输入您需要建立的空间个数n：);scanf(%d,&n);printf(请输入n个数：);for(i=n;i0;--i){Q.rear-next=(QueuePtr)malloc(sizeof(QNode));Q.rear=Q.rear-next;scanf(%d,&Q.rear-data);//逐个输入队列元素}Q.rear-next=NULL;p=Q.front;printf(输入后的新队列Q：);for(q=Q.front;Q.front-next;Q.front=Q.front-next)printf(%d,Q.front-next-data);11printf(\n);Q.front=p;printf(输入元素e为Q的新的队尾元素：);scanf(%d,&e);printf(插入队尾元素后的队列Q：);EnQueue(Q,e);//插入新的队尾元素，并用e返回p=Q.front;for(q=Q.front;Q.front-next;Q.front=Q.front-next)printf(%d,Q.front-next-data);printf(\n);Q.front=p;printf(删除Q的对头元素，并用e返回其值：);DeQueue(Q,e);//删除Q的队头元素，并用e返回printf(e=%d\n,e);p=Q.front;printf(删除队头元素后的队列Q：);for(q=Q.front;Q.front-next;Q.front=Q.front-next)printf(%d,Q.front-next-data);printf(\n);Q.front=p;DestroyQueue(Q);//销毁队列Qsystem(pause);}附录2：实验报告填写说明1．实验项目名称：要求与实验教学大纲一致。122．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3．实验原理：简要说明本实验项目所涉及的理论知识。4．实验环境：实验用的软、硬件环境。5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。7．实验结论（结果）：根据实验过程中得到的结果，做出结论。8．实验小结：本次实验心得体会、思考和建议。9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。