数据结构实验指导书（JAVA版）.pdf

《数据结构实验指导书（JAVA版）.pdf》由会员分享，可在线阅读，更多相关《数据结构实验指导书（JAVA版）.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验指导书（JAVA 版）实验一、单链表的基本操作 一、实验目的 1、掌握线性链表的操作特点，即指针是逻辑关系的映像。2、掌握动态产生单链表的方法。3、熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。4、熟练掌握单链表的取元素操作 二、实验内容 1、定义单链表类型并动态创建单链表；2、实现单链表的取元素操作、插入操作和删除操作；3、实现输出单链表中各元素值的操作；4、将单链表中的最小元素移到最前面。三、实验环境 eclipse 环境 四、实验步骤 1、定义单链表节点类；2、定义单链表类，并实现单链表的创建、插入、删除、取元素操作和将单链表中的最小元素移到最前面的操作；3、从键

2、盘上依次输入21、75、30、18、42、56，顺序或逆序创建单链表，并输出单链表中的各元素值；5、分别在单链表的第 3 个位置和第 9 个位置插入 67 和 10，给出插入成功或失败的信息，并输出单链表中的各元素值；6、删除单链表中的第 6 个数据元素和第 8 个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值；7、取单链表中的第 5 个数据元素和第 7 个数据元素；8、将单链表中的最小元素移到最前面，并输出单链表中的各元素以检查操作是否正确实现。五、问题讨论 1、单链表具有什么优缺点？2、单链表的定义与顺序表的定义有什么区别？3、逆序创建单链表有什么好处？六、实验报告内容 1、

3、实验目的 2、实验内容和具体要求 3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法 4、程序清单 5、所输入的数据及相应的运行结果 6、问题讨论回答 7、实验心得 实验二、二叉树的遍历和二叉查找树 一、实验目的 1、掌握二叉树的特点及其存储方式；2、掌握二叉树的创建；3、掌握二叉树前序、中序、后序遍历的基本方法及应用；4、掌握二叉查找树的特点；5、掌握二叉查找树查找（包含 contain）、插入和删除操作的实现。二、实验内容 1、用前序方法建立一棵二叉树；2、实现前序、中序和后序遍历二叉树的操作；3、实现统计二叉树叶子结点个数或计算二叉树深度的操作；4、将输入的一组数据逐个插入

4、实现创建二叉查找树；5、用非递归实现二叉查找树的查找和删除操作。三、实验环境 eclipse 环境 四、实验步骤 1、二叉链表节点类的定义；2、二叉树类的定义；3、建立下图所示的二叉树 c a b e f d 以字符串的形式“根左右”定义一棵二叉树时，写出创建二叉树的操作：4、编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列；5、完成统计以上二叉树中叶子结点的个数或计算以上二叉树的深度；6、定义二叉查找树类；实现二叉查找树的查找、插入和删除操作；7、从键盘上输入六个整数 45、24、53、12、37、9 构造二叉查找树，输出二叉查找树的中序遍历结果；8、在二叉查找树上查找 37 和

5、50，并输出能否查找成功；9、删除数据元素 24 和 53，输出其中序遍历结果。五、问题讨论 1、先序、中序、后序遍历二叉树的区别？2、在先序、中序非递归算法中为什么使用栈？能不能借助其它数据结构来实现？3、二叉查找树中序遍历结果有什么特点？4、在二叉查找树中插入一个新结点，总是插入到叶结点下面吗？5、在任意一棵非空二叉查找树中，删除某结点后又将其插入，则所得二叉查找树与原二叉查找树相同吗？六、实验报告内容 1、实验目的 2、实验内容和具体要求 3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法 4、程序清单 5、所输入的数据及相应的运行结果 6、问题讨论回答 7、实验心得 实验

6、三、内部排序 一、实验目的 1、理解排序的有关概念和特点。2、熟练掌握直接插入排序、希尔排序、快速排序、堆排序、归并排序算法的基本思想。3、关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。二、实验内容 输入一组数据,然后用直接插入排序、希尔排序、快速排序、堆排序、归并排序算法进行排序。三、实验环境 eclipse 环境 四、实验步骤 1、实现直接插入排序、希尔排序、快速排序、堆排序、归并排序算法；要求输出各种排序算法每一趟排序的结果；2、从键盘输入 8 个整数12,45,21,12,30,2,68,33，存放在数组quick8中，调用各种排序算法，观察每一趟排序

7、结果次序的变化；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、直接插入排序、希尔排序、快速排序、堆排序、归并排序中哪些排序方 法比较次数与初

8、始序列有关，哪些无关？3、在初始序列基本有序的前提条件下，哪种排序方法效率最高？六、实验报告内容 1、实验目的 2、实验内容和具体要求 3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法 4、程序清单 5、所输入的数据及相应的运行结果 6、问题讨论回答 7、实验心得 实验四、图的基本操作 一、实验目的 1、熟练掌握图的邻接矩阵和邻接表存储结构；2、掌握图的创建方法；3、掌握求顶点度的方法；4、掌握图的深度优先和广度优先遍历方法；二、实验内容 1、分别定义图的邻接矩阵和邻接表存储结构；2、分别在两种存储结构下根据输入的顶点和边（或弧）创建图；3、分别在两种存储结构下实现求顶点度的操

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