数据结构实验指导书(java版).doc

实验一、单链表的基本操作一、实验目的1、掌握线性链表的操作特点，即指针是逻辑关系的映像。2、掌握动态产生单链表的方法。3、熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。4、熟练掌握单链表的取元素操作二、实验内容1、定义单链表类型并动态创建单链表；2、实现单链表的取元素操作、插入操作和删除操作；3、实现输出单链表中各元素值的操作；4、将单链表中的最小元素移到最前面。三、实验环境eclipse环境四、实验步骤1、定义单链表节点类；2、定义单链表类，并实现单链表的创建、插入、删除、取元素操作和将单链表中的最小元素移到最前面的操作； 3、从键盘上依次输入21、75、30、18、42、56，顺序或逆序创建单链表，并输出单链表中的各元素值；5、分别在单链表的第3个位置和第9个位置插入67和10，给出插入成功或失败的信息，并输出单链表中的各元素值；6、删除单链表中的第6个数据元素和第8个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值；7、取单链表中的第5个数据元素和第7个数据元素；8、将单链表中的最小元素移到最前面，并输出单链表中的各元素以检查操作是否正确实现。五、问题讨论1、单链表具有什么优缺点？2、单链表的定义与顺序表的定义有什么区别？3、逆序创建单链表有什么好处？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题讨论回答7、实验心得实验二、二叉树的遍历和二叉查找树一、实验目的1、掌握二叉树的特点及其存储方式；2、掌握二叉树的创建；3、掌握二叉树前序、中序、后序遍历的基本方法及应用；4、掌握二叉查找树的特点；5、掌握二叉查找树查找（包含contain）、插入和删除操作的实现。二、实验内容1、用前序方法建立一棵二叉树；2、实现前序、中序和后序遍历二叉树的操作；3、实现统计二叉树叶子结点个数或计算二叉树深度的操作；4、将输入的一组数据逐个插入实现创建二叉查找树；5、用非递归实现二叉查找树的查找和删除操作。三、实验环境eclipse环境四、实验步骤1、二叉链表节点类的定义；2、二叉树类的定义；3、建立下图所示的二叉树cabefd以字符串的形式“根左右”定义一棵二叉树时，写出创建二叉树的操作：4、编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列；5、完成统计以上二叉树中叶子结点的个数或计算以上二叉树的深度；6、定义二叉查找树类；实现二叉查找树的查找、插入和删除操作；7、从键盘上输入六个整数45、24、53、12、37、9构造二叉查找树，输出二叉查找树的中序遍历结果；8、在二叉查找树上查找37和50，并输出能否查找成功；9、删除数据元素24和53，输出其中序遍历结果。五、问题讨论1、先序、中序、后序遍历二叉树的区别？2、在先序、中序非递归算法中为什么使用栈？能不能借助其它数据结构来实现？3、二叉查找树中序遍历结果有什么特点？4、在二叉查找树中插入一个新结点，总是插入到叶结点下面吗？ 5、在任意一棵非空二叉查找树中，删除某结点后又将其插入，则所得二叉查找树与原二叉查找树相同吗？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题讨论回答7、实验心得 实验三、内部排序一、实验目的1、理解排序的有关概念和特点。2、熟练掌握直接插入排序、希尔排序、快速排序、堆排序、归并排序算法的基本思想。3、关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。二、实验内容 输入一组数据,然后用直接插入排序、希尔排序、快速排序、堆排序、归并排序算法进行排序。三、实验环境eclipse环境四、实验步骤 1、实现直接插入排序、希尔排序、快速排序、堆排序、归并排序算法；要求输出各种排序算法每一趟排序的结果； 2、从键盘输入8个整数 12 , 45 , 21 , 12 , 30 , 2 , 68 , 33 ，存放在数组quick8中，调用各种排序算法，观察每一趟排序结果次序的变化； 3、如果上述8个整数按照升序输入，即k1= 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 ，输出各种排序算法每一趟排序的结果，观察关键字次序的变化；4、如果上述8个整数按照降序输入，即k2= 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2，输出各种排序算法每一趟排序的结果，观察关键字次序的变化；5、随机产生3万个数，对其进行排序，观察其结果，并测试各排序算法的执行时间，比较执行效率。五、问题讨论1、直接插入排序、希尔排序、快速排序、堆排序、归并排序中哪些是稳定的排序方法，哪些是不稳定的？2、直接插入排序、希尔排序、快速排序、堆排序、归并排序中哪些排序方法比较次数与初始序列有关，哪些无关？3、在初始序列基本有序的前提条件下，哪种排序方法效率最高？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题讨论回答7、实验心得实验四、图的基本操作一、实验目的1、熟练掌握图的邻接矩阵和邻接表存储结构；2、掌握图的创建方法；3、掌握求顶点度的方法；4、掌握图的深度优先和广度优先遍历方法；二、实验内容1、分别定义图的邻接矩阵和邻接表存储结构；2、分别在两种存储结构下根据输入的顶点和边（或弧）创建图；3、分别在两种存储结构下实现求顶点度的操作；3、分别在两种存储结构下实现图的深度和广度优先遍历算法。三、实验环境eclipse环境四、实验步骤1、定义图的存储结构2、实现图的创建方法，并创建一个如下的图：V1V2V3V43、实现求第一个邻接点firstAdjVex()和下一个邻接点nextAdjVex()的操作；4、写一个算法，求各个顶点的度；5、对创建的图进行深度优先和广度优先遍历。五、问题讨论1、图的邻接矩阵和邻接表的存储结构