《数据结构》 实验指导书(java版)

实验一、单循环链表的基本操作一、实验目的1、掌握线性链表的操作特点，即指针是逻辑关系的映像。2、掌握动态产生带尾指针的单循环链表（有头结点）的方法。3、熟练掌握单循环链表基本操作的实现过程。二、实验内容1、定义单循环链表类型并动态创建使用tail指向尾结点的单循环链表（有头结点）；2、实现单循环链表的取元素、插入、删除、索引元素位置号等操作以及迭代器；3、实现输出单循环链表中各元素值的操作；4、将单循环链表中的最小元素移到最前面。三、实验环境Eclipse环境或C++编程环境四、实验步骤1、定义单循环链表结点类；2、定义单循环链表类，并实现使用tail指向尾结点的单循环链表（有头结点）的创建、插入、删除、取元素操作和将单链表中的最小元素移到最前面的操作，以及迭代器；3、从键盘上依次输入21、75、30、18、42、56，创建单循环链表，并输出单循环链表中的各元素值；5、分别在单链表的第3个位置和第9个位置插入67和10，给出插入成功或失败的信息，并输出单循环链表中的各元素值；6、删除单循环链表中的第4个数据元素和第8个数据元素，给出删除成功或失败的信息，并输出单循环链表中的各元素值；7、取单循环链表中的第5个数据元素和第7个数据元素；8、将单循环链表中的最小元素移到最前面，并输出单链表中的各元素以检查操作是否正确实现。五、问题讨论1、线性表的顺序存储和链式存储的区别是什么？分别有什么优缺点？2、带头指针的单循环链表和带尾指针的单循环链表有什么区别？带尾指针的单循环链表有什么优势？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题讨论回答7、实验心得

实验二、二叉树的遍历一、实验目的1、掌握二叉树的特点及其存储方式；2、掌握二叉树的创建；3、掌握二叉树先序、中序、后序遍历的基本方法及应用；4、掌握判断二叉树是否是完全二叉树的方法。二、实验内容1、用先序方法建立一棵二叉树；2、实现输出二叉树先序、中序和后序遍历序列中第k个数据元素的操作；3、实现判断二叉树是否是完全二叉树的操作。三、实验环境Eclipse环境或C++编程环境四、实验步骤1、二叉链表结点类的定义；2、二叉树类的定义；3、创建一棵二叉树：4、实现输出以上二叉树先序、中序和后序遍历序列中第k个数据元素的操作；5、判断二叉树是否是完全二叉树；五、问题讨论1、先序、中序、后序遍历二叉树的区别？2、完全二叉树的特点是什么？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题讨论回答7、实验心得

实验三、图的基本操作一、实验目的1、熟练掌握图的邻接矩阵和邻接表存储结构；2、掌握图的创建方法；3、掌握求顶点度的方法；4、掌握图的深度优先和广度优先遍历方法；5、掌握图的邻接矩阵和邻接表存储结构的转换。二、实验内容1、分别定义图的邻接矩阵和邻接表存储结构；2、分别在两种存储结构下根据输入的顶点和边（或弧）创建图；3、分别在两种存储结构下实现求顶点度的操作；4、分别在两种存储结构下实现图的深度和广度优先遍历算法；5、实现图的邻接矩阵和邻接表存储结构的转换。三、实验环境Eclipse环境或C++编程环境四、实验步骤1、定义图的存储结构2、实现图的创建方法，并创建一个如下的图：VV1V2V3V43、实现求第一个邻接点firstAdjVex()和下一个邻接点nextAdjVex()的操作；4、写一个算法，求各个顶点的度；5、对创建的图进行深度优先和广度优先遍历。6、将邻接表存储的有向图转换为邻接矩阵或将邻接矩阵存储的图转换为邻接表。五、问题讨论1、图的邻接矩阵和邻接表的存储结构各有什么特点？2、对于稀疏图和稠密图分别选择邻接矩阵和邻接表中的哪个存储更合适？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题讨论回答7、实验心得

实验四、折半查找和二叉排序树一、实验目的1、掌握查找的特点。2、掌握折半查找的基本思想及其算法。3、熟悉二叉排序树的特点，掌握二叉排序树的插入、删除操作。二、实验内容1、设有关键字序列k={5,14,18,21,23,29,31,35}，请找出小于29的最大关键字值是什么。2、根据关键字序列{45、24、53、12、37、93}构造二叉排序树，并完成插入13删除关键字53和24的操作。三、实验环境Eclipse环境或C++编程环境四、实验步骤1、折半查找（1）从键盘输入上述8个整数5,14,18,21,23,29,31,35，并输出其值检验输入是否正确。（2）实现找出小于29的最大关键字值是什么的操作。2、二叉排序树（1）二叉排序树存储定义（2）从键盘上输入六个整数45、24、53、12、37、9构造二叉排序树（3）输出其中序遍历结果。（4）插入数据元素13，输出其中序遍历结果。（5）删除数据元素24和53，输出其中序遍历结果，注明：既有左子树又有右子树删除时利用中序遍历的前驱结点替换要删除的结点，然后删除其前驱结点。五、问题讨论1、折半查找递归算法该怎么描述？2、二叉排序树中序遍历结果有什么特点？3、在二叉树排序树中插入一个新结点，总是插入到叶结点下面吗？4、在任意一棵非空二叉排序树中，删