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

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