《数据结构java实验三.docx》由会员分享，可在线阅读，更多相关《数据结构java实验三.docx（5页珍藏版）》请在三一文库上搜索。
1、数据结构 java 实验三数据结构 (JAVA) 综合性、设计性实验成绩单开设时间 :班级学号姓名实验三栈与队列及递归算法实验题目成绩教师签名数据结构 (JAVA) 实 验 报 告实验题目 :栈与队列及递归算法指导教师 :实验组长 (姓名 +学号 ):组员 (姓名 +学号 ):实验时间 :组长签名 :一、实验报告撰写提纲1、实验目的数据结构 java 实验三1 理解栈与队列抽象数据类型,掌握栈与队列的存储结构与操作实现,理解栈与队列在实际应用问题的作用。2、实验内容（ 1） 使用一个栈 ,将十进制转换成二进制。（ 2） 分别用循环单链表、循环双链表结构设计队列,并讨论她们之间的差别。（3）使用
2、 3 个队列分别保留手机最近10 个“未接来电” 、“已接来电” 、“以拨电话” 。（4）走迷宫。一个迷宫如图所示 ,她有一个入口与一个出口,其中白色单元表示通路 ,黑色单元表示不通路。 试寻找一条从入口到出口的路径,每一部只能从一个白色单元走到相邻的白色单元 ,直至出口。分别用站与队列求解问题。入口出口(5) 骑士游历骑士游历问题就是指,在国际象棋的棋盘(8 行 *8列 )上 ,一个马要遍历棋盘 ,即走到棋盘上的每一格 ,并且每隔只到达一次。设码在棋盘的某一位置(x,y) 上 ,按照“走马日”的规则 ,下一步有 8个方向走 ,如图所示。 若给定起始位置 (x0,y0),使用站与队列探索出一条
3、马遍历棋盘的路劲。123456788172马63543、实验步骤与结果(1) 审题 :使用一个栈 ,将十进制转换成二进制。编程 :本代码使用了一个顺序栈 SeqStack,编写一个循环让十进制数除 2 的余数入站 ,然后让全部余数出栈 ,输出二进制数。验证结果 :图 1(2) 审题 :分别用循环单链表、循环双链表结构设计队列,并讨论她们之间的差别。编程 :首先先编写一个队列抽象数据类型QQueue,然后编写循环单链表SlinkedQueue 与 双数据结构 java 实验三链表 DlinkedQueue 逐一实现Qqueue 中的三个方法,即判断就是否队列为空、入队与出队。循环双链表所占的时间
4、复杂度与空间复杂度比单链表多。验证结果 :两个均可被调用。(3) 审题 :使用 3 个队列分别保留手机最近 10 个“未接来电” 、“已接来电” 、“以拨电话” 。编程 :1 10 代表未接来电 ,11 20 代表已接来电 ,21 30 代表以拨电话 ,编写三个顺序栈stack1,stack2,stack3,运用条件语句存储10 个号码 ,然后输出。验证结果 :图 2(4) 审题 : 一个迷宫 , 她有一个入口与一个出口,其中白色单元表示通路 ,黑色单元表示不通路。试寻找一条从入口到出口的路径,每一部只能从一个白色单元走到相邻的白色单元,直至出口。分别用站与队列求解问题。编程 :暂时做不出验证
5、结果 :(5) 审题 :骑士游历问题就是指 ,在国际象棋的棋盘 (8 行 *8 列)上,一个马要遍历棋盘 ,即走到棋盘上的每一格 ,并且每隔只到达一次。设码在棋盘的某一位置(x,y) 上 ,按照“走马日”的规则 ,下一步有 8 个方向走 ,如图所示。若给定起始位置 (x0,y0),使用站与队列探索出一条马遍历棋盘的路劲。编程 :利用预见算法解这类问题 ,以二维数组 chessboard表示棋盘并保存问题的一个解 ;将棋盘上一格的位置(x,y) 声明为一个内部类Position;start(x,y) 方法从 (x,y) 格开始游历,初始位置p=new Position(x,y); 判断就是否满n
6、*n, 不满的话选择一个方向direction=select(p); 判断就是否有方向可选 ,有的话步数加 1,向所选方向前进一步 p=goaStep(p,direction), 递归执行上述算法 ; 如果无方向可选 ,则无路可通 ;当慢 n*n 步时 ,成功输出。验证结果 :图 34、源码见附录 :附录中的源代码在同一个包中。数据结构 java 实验三5、结论与讨论通过本次试验 ,我们刚开始时遇到了很多问题 ,比如说做骑士游历这道题 ,刚瞧到她们的时候根本就就是无法下手 ,但经过我们小组的讨论 ,我们最后解决 了这道题。但对于走迷宫这道题有本小组知识有限 ,思考能力也有限 ,暂时还就是没找到做出的方法 ,相信过一段时间后就会被我们做出。本次试验让我们对栈与队列有了进一步的加深认识与了解 ,对栈与队列的结构了解更加彻底与清晰。,