算法与数据结构实验指导.ppt

实验一：栈与队列 实验二：单链表 实验三：二叉树 实验四：图 实验五：查找 实验六：排序 一、实验目的 二、实验任务 三、实验原理 四、程序清单 五、运行结果 六、心得体会（可选） 实验目的： 掌握栈和队列特点、逻辑结构和存储结构 熟悉对栈和队列的一些基本操作和具体的函数定义。 利用栈和队列的基本操作完成一定功能的程序。 实验任务： 给出顺序栈的类定义和函数实现，利用栈的基本操作完成十进制数N与其它d进制数的转换。（如N=1357,d=8） 给出顺序队列的类定义和函数实现，并利用队列计算并打印杨辉三角的前n行的内容。(n=8) 给出链栈的类定义和函数实现，并设计程序完成如下功能：读入一个有限大小的整数n，并读入n个数，然后按照与输入次序相反的次序输出各元素的值。 实验目的： 理解线性表的链式存储结构。 熟练掌握动态链表结构及有关算法的设计。 根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。 实验任务： 在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。 实验数据：链表元素为（10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8。 将单链表Ｌ中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。 实验测试数据基本要求： 第一组数据：链表元素为 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60） 第二组数据：链表元素为 （10,20,30,40,50,60,70,80,90,100） 3.求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。 实验测试数据基本要求： 第一组数据： 第一个链表元素为 （1，3，6，10，15，16，17，18，19，20） 第二个链表元素为 （1，2，3，4，5，6，7，8，9，10，18，20，30） 第二组数据： 第一个链表元素为 （1，3，6，10，15，16，17，18，19，20） 第二个链表元素为 （2，4，5，7，8，9，12，22） 实验目的： 掌握二叉树的动态链表存储结构及表示。 掌握二叉树的三种遍历算法（递归和非递归两类）。 运用二叉树三种遍历的方法求解有关问题。 实验任务： 建立一棵采用二叉链表结构存储的二叉树。 分别采用递归和非递归两种方式对该二叉树进行先序、中序和后序遍历。 求二叉树的高度以及二叉树中叶子结点的数目。 D E I A G F C B H 实验目的： 掌握图的基本概念。 掌握图的存储结构的设计与实现，基本运算的实现。 掌握图的两种遍历算法，以及遍历算法的应用。 实验任务： 分别以邻接矩阵和邻接表的存储结构建立图。 分别对图进行深度优先遍历和广度优先遍历。 求图中边的数目。 求顶点0到图中其余每个顶点的最短路径。 实验目的： 掌握顺序表的查找方法，尤其是二分查找方法。 掌握二叉排序树的建立及查找。 实验任务： 对下列数据表，分别采用二分查找算法实现查找，给出查找过程依次所比较的元素（的下标），并以二分查找的判定树来解释。 实验测试数据： 数据表为 (1,2,3,4,6,7,8,9,10,11,12,13,17,18,19,20,24,25,26,30,35,40,45,50,100) 查找的元素分别为： 2，8，20, 30，50，5，15，33，110 设计出在二叉排序树中插入结点的算法，在此基础上实现构建二叉排序树的算法，并给出其中序遍历序列。 实验测试数据： 构建二叉排序树的输入序列如下：100，150，120，50，70，60，80，170，180，160，110，30，40，35，175 设计算法在二叉排序树中查找指定值的结点。 在任务2所建立的二叉排序树中分别查找下列元素： 150，70，160，190，10，55，175 设计算法在二叉排序树中删除特定值的结点。（选做） 在任务2所建立的二叉排序树中依次删除下列元素： 30，150，100，并给出中序遍历结果。 实验目的： 掌握各种内部排序算法。 理解各种内部排序算法的特性、时间性能和空间性能，在此基础上能根据具体情况选择合适的排序算法。 实验任务： 实现希尔排序算法，并观察在采用不同的步长选取方法对排序过程中数据的比较和移动次数的影响。 测试数据： 数组元素分别为：（180,203,32,46,25,76,17,58,99,100,11,102,13,54,75,6,27,18,19,29,2,82） 实现堆排序算法，给出排序结果。 测试数据： （106,213