数据结构java实验三

1、数据结构（JAVA）综合性、设计性实验成绩单开设时间： 班级学号姓名实验题目实验三 栈和队列及递归算法成绩教师签名数据结构（JAVA）实 验 报 告实验题目： 栈和队列及递归算法 指导教师： 实验组长（姓名+学号）： 组员（姓名+学号）： 实验时间： 组长签名： 一、实验报告撰写提纲1、实验目的1 理解栈和队列抽象数据类型，掌握栈和队列的存储结构和操作实现，理解栈和队列在实际应用问题的作用。2、实验内容（1） 使用一个栈，将十进制转换成二进制。（2） 分别用循环单链表、循环双链表结构设计队列，并讨论他们之间的差别。（3） 使用3个队列分别保留手机最近10个“未接来电”、“已接来电”、“以拨电话

2、”。（4） 走迷宫。一个迷宫如图所示，他有一个入口和一个出口，其中白色单元表示通路，黑色单元表示不通路。试寻找一条从入口到出口的路径，每一部只能从一个白色单元走到相邻的白色单元，直至出口。分别用站和队列求解问题。入口出口（5）骑士游历骑士游历问题是指，在国际象棋的棋盘（8行*8列）上，一个马要遍历棋盘，即走到棋盘上的每一格，并且每隔只到达一次。设码在棋盘的某一位置（x,y）上，按照“走马日”的规则，下一步有8个方向走，如图所示。若给定起始位置（x0,y0）,使用站和队列探索出一条马遍历棋盘的路劲。 12345 6 7 8 8172马63543、实验步骤与结果(1)审题：使用一个栈，将十进制转换

3、成二进制。编程：本代码使用了一个顺序栈SeqStack，编写一个循环让十进制数除2的余数入站，然后让全部余数出栈，输出二进制数。验证结果：图 1（2）审题：分别用循环单链表、循环双链表结构设计队列，并讨论他们之间的差别。编程：首先先编写一个队列抽象数据类型QQueue，然后编写循环单链表SlinkedQueue和 双链表DlinkedQueue逐一实现Qqueue中的三个方法，即判断是否队列为空、入队和出队。循环双链表所占的时间复杂度和空间复杂度比单链表多。验证结果：两个均可被调用。（3）审题：使用3个队列分别保留手机最近10个“未接来电”、“已接来电”、“以拨电话”。编程：110代表未接来电

4、，1120代表已接来电，2130代表以拨电话，编写三个顺序栈stack1，stack2，stack3，运用条件语句存储10个号码，然后输出。验证结果：图 2（4）审题：一个迷宫，他有一个入口和一个出口，其中白色单元表示通路，黑色单元表示不通路。试寻找一条从入口到出口的路径，每一部只能从一个白色单元走到相邻的白色单元，直至出口。分别用站和队列求解问题。编程：暂时做不出验证结果：（5）审题：骑士游历问题是指，在国际象棋的棋盘（8行*8列）上，一个马要遍历棋盘，即走到棋盘上的每一格，并且每隔只到达一次。设码在棋盘的某一位置（x,y）上，按照“走马日”的规则，下一步有8个方向走，如图所示。若给定起始位

5、置（x0,y0）,使用站和队列探索出一条马遍历棋盘的路劲。编程：利用预见算法解这类问题，以二维数组chessboard表示棋盘并保存问题的一个解；将棋盘上一格的位置（x，y）声明为一个内部类Position；start（x，y）方法从（x，y）格开始游历，初始位置p=new Position（x，y）；判断是否满n*n，不满的话选择一个方向direction=select（p）；判断是否有方向可选，有的话步数加1，向所选方向前进一步p=goaStep（p，direction），递归执行上述算法；如果无方向可选，则无路可通；当慢n*n步时，成功输出。验证结果：图 34、源码见附录：附录中的源代码在同一个包中。5.结论与讨论通过本次试验，我们刚开始时遇到了很多问题，比如说做骑士游历这道题，刚看到他们的时候根本就是无法下手，但经过我们小组的讨论，我们最后解决 了这道题。但对于走迷宫这道题，有本小组知识