《数据结构》实验指导书最终.doc

《数据结构》实验指导书 一、实验目的 实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常实验题中的问题比平时的练习题要复杂，也更接近实际。 实验的目的是旨在使学生进一步巩固课堂上所学的理论知识；深化理解和灵活掌握教学内容；培养学生算法设计的能力和解决实际问题的程序设计的能力。 二、实验名称与学时分配 序号 实 训 名 称 学时数 1 熟悉线性表的插入、删除操作，实现约瑟夫环的求解 2 2 实现对二叉树的一个指定的操作或用二叉树解决一应用问题 2 3 实现对图的一个指定的操作或用图解决一个应用问题 2 4 掌握内部排序方法，用其中一种指定的排序方法进行排序 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 p[n]; （2）以循环链表为存储结构 typedef struct lnode{ int data; struct lnode *next; } lnode； 实验二、二叉树及其先序遍历、中序遍历 一、目的与要求 （一）目的 熟悉二叉树的链表存储结构；熟练掌握二叉树的先序遍历算法和中序遍历算法。 （二）要求 用C语言编写程序，实现二叉树的先序遍历和中序遍历。 二、实验内容 1、题目： 已知二叉树（如图所示），要求编程实现此二叉树的先序遍历和中序遍历。 2、实验指导： （1）、树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的语法结构，在数据库系统中，数型结构也是信息的重要组织形式。 （2）、节点的有限集合（N大于等于0）,在一棵非空数里： （a）、有且仅有一个特定的根节点； （b）、当N大于1时，其余结点可分为M（M大于0）个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树的定义是以递归形式给出的。 （3）．二叉树是另一种树型结构。它的特点是每个结点最多有两棵子树，并且，二叉树的子树有左右之分，其次序不能颠倒。 （4）．二叉树的结点存储结果示意图如下： 左指针域 数据域 右指针域 （5）、程序流程图： 先序遍历 实验三、图的拓扑排序操作 一、目的与要求 （一）目的 1、了解拓扑排序的方法及其在工程建设中的实际意义。 2、掌握拓扑排序的算法，了解拓扑排序的有向图的数据结构。 （二）要求 用C语言编写程序，实现图的拓扑排序操作。 二、实验内容 1、题目：实现下图的拓扑排序。 1 2 3 4 5 2、实验指导：