栈和队列实验报告
栈和队列实验报告
覃孔林数据结构报告
数据结构(2013)实验报告02 班级: 姓名: 实验方式:上机成绩: 教师批阅处:
一、实验名称
栈和队列基本操作的编程实现
二、实验目的
栈和队列基本操作的编程实现(2学时，验证型)，掌握栈和队列的建立、进
栈、出栈、进队、出队等基本操作的编程实现，也可以进一步编程实现实用的功能等操作，具体编程存储结构要求是顺序存储结构(链表存储结构建议作为课外实验)，可以依次完成主要功能来体现功能的正确性，用菜单进行管理完成大部分功能，要求可以重复运行。
三、实验内容
(一)栈基本功能的编程实现
1、实验设计
(1)栈的基本功能清单:数据进栈、数据出栈、输出栈中的数据、求栈中元素的
个数、销毁此栈和结束程序等。栈的所有功能利用链接存储结构实现。
(2)数据进栈的方式采用从键盘逐个输入(没输入一个数据按回车键)，数据出
栈按照“后进先出”的原则输出。
2、界面设计
(1)主菜单:
图 1
第 1 页共 5 页
覃孔林数据结构报告
(2)数据进栈:
图 2
(3)数据出栈:
图 3
(4)显示栈中数据:
图 4
3、栈功能菜单设计特点:
由于考虑到，栈功能的实现必须在先有数据进栈的前提下，才能进行数据出栈、显示栈中所有数据、求栈长度以及读取栈顶数据等功能。所以当用户进入该栈
功能菜单时，如果不是先进行数据进栈操作，而检测后面的功能时，则提示先输入数据，再进行相应操作，比如:
图 5
4、栈操作示意图
(1)当有数据要进栈的时候，便申请一个空间。然后将新的结点的next指向栈顶top，接着移动top指针，使其指向新的结点。示意图如下:
linkstacktop 30 20 10 ^
40 newnodep
^
图 6 链表的进栈操作示意图
第 2 页共 5 页
覃孔林数据结构报告
(2)当要执行数据出栈操作时，将top指针往后移，指向其next指向的结点，然后删除top之前指向的结点。示意图如下:
Linkstacktop 20 30 10 ^
newnodep
图 7 链栈的出栈操作示意图
(二)队列基本功能的编程实现
1、实验设计
(1)队列的基本功能菜单:数据入队、数据出队、显示队列数据、求队列长度、读取对头数据、清空队列和退出程序等功能。队列的基本功能采用链接存储的结构来实现。
(2)数据进栈的方式同样采用键盘输入的方式(没输入一个数据按回车键)，输出则按照队列的性质“先入先出”输出。
2、界面设计
(1)主界面:
图 8
(2)数据入队:
图 9
第 3 页共 5 页
覃孔林数据结构报告
(3)数据出队:
图 10
显示队列的数据:
图 11
3、队列功能设计特点:
和栈的设计一样，用户要操作队列时，队列里必须先有数据，否则将无法进行其他的操作。当用户在没有先录入数据的情况下进行显示、清空等操作时，则提示先输入数据，再进行相应的操作，按任意键即回到主菜单重新选择。例如:
图 12
4、队列功能操作示意图
(1)当执行数据进队时，先申请一个空间供其存放;然后使新产生的结点的next 指向rear指向的结点，最后将rear指针后移，是其指向新的结点。示意图如下:
10 20 front 30 ^ ^
rear newnodep
图 13 数据进队示意图
(2)当有数据要出队时，先使front指向front的next指向的指针结点，然后删除front之前指向的结点。示意图如下:
10 20 front 30 ^
rear
图 14 数据出队示意图
第 4 页共 5 页
覃孔林数据结构报告
四、实验总结
1、实验中遇到的问题
在做堆栈的实验时，在遍历栈中的所有数据时，其余的输出都正常，唯独没有输出数据，百思不得其解。经过请教同学后，将输出所用的cout改为printf输出时，终于得到了想要的结果。不过不知道是为什么。
2、实验的不足
本次实验只能完成难度系数比较低的实验，即只能完成栈和队列最基本功能的编程实现，不能完成更深层次的实验，比如进制转换、汉字回文等实验。还有，对链表的操作还不是很熟练，经常还要对照教材才能完成编程。
3、努力方向及感想
在努力完成所有实验的同时，尽力多抽出些空闲的时间，多去练习编程，尤其是对链表的实际操作，要加把劲快点赶上。通过这两次实验，我发现链表这一块内容，实在是太陌生了。所以在学习新的知识的同时，还要不断复习练习旧的知识内容，所谓温故知新。其实很多时候，我都是首先被自己打败了，首先觉得自己没学好，不可能编出程序来的，所以就不敢做。但当硬着头皮去做时，并坚持着时，会发现很所难题会迎刃而解。实践出真知，敢于尝试，总是会有收获的。
第 5 页共 5 页