《数据结构》实验指导书最终.doc
数据结构实验指导书一、实验目的实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常实验题中的问题比平时的练习题要复杂，也更接近实际。实验的目的是旨在使学生进一步巩固课堂上所学的理论知识；深化理解和灵活掌握教学内容；培养学生算法设计的能力和解决实际问题的程序设计的能力。二、实验名称与学时分配序号实 训 名 称学时数1熟悉线性表的插入、删除操作，实现约瑟夫环的求解22实现对二叉树的一个指定的操作或用二叉树解决一应用问题23实现对图的一个指定的操作或用图解决一个应用问题24掌握内部排序方法，用其中一种指定的排序方法进行排序2三、实验考核每次实验结束后，均应上交实验报告。实验成绩占数据结构课程结业成绩的20%。实验报告应包括如下内容： 1、问题描述：简述题目要解决的问题是什么。2、设计：包括存储结构设计、主要算法设计等。用C语言或C+实现。3、调试报告：调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、算法分析与改进：算法的时间复杂度和空间复杂度分析；算法改进的设想。5、经验和体会附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含有其它测试数据和运行输出（在需要多组数据时）。四、实验时间 8学时五、实验部分实验一、 线性表应用一、目的与要求（一）目的了解线性表及在计算机中的两类不同的存储结构；熟练掌握线性表的查找、插入和删除等算法并灵活运用这些算法。（二）要求用C语言编写程序，实现求解约瑟夫问题。二、实验内容1、题目 约瑟夫问题编号为1，2，···，n的n个人围坐在一圆桌旁，从第s个人开始报数，报到第m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。例如，设s=1，m=4，n=8，则退席的人的编号依次为4，8，5，2，1，3，7，6。2、实验指导： （1）以顺序表为存储结构 int pn; （2）以循环链表为存储结构typedef struct lnodeint data;struct lnode *next; lnode；实验二、二叉树及其先序遍历、中序遍历一、目的与要求（一）目的熟悉二叉树的链表存储结构；熟练掌握二叉树的先序遍历算法和中序遍历算法。（二）要求用C语言编写程序，实现二叉树的先序遍历和中序遍历。二、实验内容1、题目： 已知二叉树（如图所示），要求编程实现此二叉树的先序遍历和中序遍历。ABCDE 2、实验指导：（1）、树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的语法结构，在数据库系统中，数型结构也是信息的重要组织形式。（2）、节点的有限集合（N大于等于0）,在一棵非空数里：（a）、有且仅有一个特定的根节点；（b）、当N大于1时，其余结点可分为M（M大于0）个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树的定义是以递归形式给出的。（3）二叉树是另一种树型结构。它的特点是每个结点最多有两棵子树，并且，二叉树的子树有左右之分，其次序不能颠倒。（4）二叉树的结点存储结果示意图如下：左指针域数据域右指针域开始建立 二叉树先序遍历二叉树结束（5）、程序流程图： 先序遍历空树输出开始BT=NIL?输出结点先序遍历左孩子先序遍历右孩子结束 实验三、图的拓扑排序操作一、目的与要求（一）目的1、了解拓扑排序的方法及其在工程建设中的实际意义。2、掌握拓扑排序的算法，了解拓扑排序的有向图的数据结构。（二）要求用C语言编写程序，实现图的拓扑排序操作。二、实验内容1、题目：实现下图的拓扑排序。 1 2 3 4 5 2、实验指导： 首先对有向图，我们采取邻接表作为数据结构。且将表头指针改为头结点，其数据域存放该结点的入度，入度设为零的结点即没有前趋。在建立邻接表输入之前，表头向量的每个结点的初始状态为数据域VEX（入度）为零，指针域NXET为空，每输入一条弧< J, K > 建立链表的一个结点，同时令k 的入度加1，因此在输入结束时，表头的两个域分别表示顶点的入度和指向链表的第一个结点指针。在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减1。（1）、查邻接表中入度为零的顶点，并进栈。（2）、当栈为空时，进行拓扑排序。（a）、退栈，输出栈顶元素V。（b）、在邻接表中查找Vj的直接后继Vk，将Vk的入度减一，并令入度减至零的顶点进栈。（3）、若栈空时输出的顶点数不是N个则说明有向回路，否则拓扑排序结束。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面，借用入度为零的数据域存放带链栈的指针域（下一个入度的顶点号）。实验四、内部排序一、目的与要求（一）目的1、理解排序的定义和各种排序方法的特点，并能加以灵活应用；2、掌握各种内部排序方法。（二）要求对一组给定的无序序列，用C语言或C+实现一种指定的排序方法（快速排序或归并排序）。二、实验内容1、题目：编写程序对无序序列5 1 7 3 1 6 9 4 2 8 6，用指定方法进行排序。2、实验指导：（1）、快速排序：假设待排的序列为RS, RS+1, RS+2,， RT。首先任意选取一个记录，RS作为枢轴，然后重新排列其它记录。将所有关键字比它小的记录都放在它的前面，其它所有关键字比它大的记录放在它的后面。由此可以将记录以“枢轴”为界，将记录分为两个子序列，这个过程称为一趟快速排序。以后再分别对两个子序列进行快速排序，重复进行这个过程，直到整个序列全部有序为止，就平均时间而言，快排是被认为最好的内部排序方法。（2）、归并排序：归并排序是又一类不同的排序方法。“归并的含义是将两个或两个以上的有序表合成一个新的有序表。它的实现方法早已为同学们所熟悉，无论是顺序存储结构还是链式存储结构，都可以在O（M+N）的时间量级上实现，利用归并的思想容易实现归并排序。 假设，初始序列有N个记录，则可以看作是N个有序的子序列，每个子序列的长度为1，然后两两归并，得到 N/2 个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为N 的有序序列为止，这种排序方法称为2-路归并排序，本实验采用的就是2-路归并排序。递归形式的2-路归并排序比较简洁，但是实用性较差，与快速排序和堆选排序相比，归并排序的最大优点就是它是一种稳定的排序方法。
