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