东北林业大学

《东北林业大学》由会员分享，可在线阅读，更多相关《东北林业大学（13页珍藏版）》请在装配图网上搜索。

1、数据结构实验指导书（第2版）东北林业大学信息与计算机工程学院计算机科学与技术专业1 实验目的与要求12 实验环境13实验一般步骤14 实验时数25 实验内容和要求3实验一线性表的顺序存储结构3实验二链式存储结构（一）单向链表的有关操作 4实验三链式存储结构（二）双向链表的有关操作5实验四栈和队 列的有关操作6实验五二叉树的常见操作7实验六图的有关操作8实验七查找的有关操作9实验八排序的有关操作101实验目的与要求从以往的教学事先实习的经验来看，在初学阶段执行严格的实习步骤规范（包括上机 操作规范），机时利用率会大大提高，有助于养成良好的程序编制风格，培养严谨、科学、 高效的工作方式。在以往的教

2、学实践中，经常发现很多学生抱怨说，化了两个小时才找出一个错误，甚 至一无所获。他们不明白造成这种情况的原因，正是他们自己。有的学生不屑于按实习步 骤规范去做，甚至对于实习步骤的要求和建议看都不看一遍，认为那是浪费时间，这是及 其害的。实习步骤规范不但可以培养科学化的工作作风，而且还能有效地避免错误。2实验环境（1）计算机的硬件配置pc系列微机。（2）计算机的软件配置DOS6.22 或 Windows 98、 Windows xp、 Windows 2000。C语言的集成开发环境TurboC V3.0，或Visual C+6.0。3实验一般步骤问题分析与系统的结构设计充分地分析和理解问题本身，弄

3、清要求作什么，限制条件是什么。按照以数据结构为 中心的原则划分模块，即定义数据结构及其在这些结构之上的操作，使得对数据结构的存 取通过这些操作加以实现。在这个过程中，要综合考 虑系统功能。要考虑系统结构清晰、 合理、简单并且易于调试。最后写出每个子程序（过程或函数）的规格说明，列出它们之 间的调用关系，可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。详细设计和编码详细设计的目的是对子程序（过程或函数）的进一步求精。用IF、WHILE和赋值语句 等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入细节。在编码是，可 以对详细设计的结果进一步求精，用高级语言表示出来。程序的每一

4、行最好不超过60个字符。每个子程序（或过程、函数）通常不要太长， 以40行为宜。子程序（或过程、函数）包含的程序行数太多，易于造成理解的困难。控 制IF、WHILE等语句的连续嵌套的深度。程序的目的性必须明确。对每一段程序完成的作 用，除非常明显的除外（如：x=x+1;注释为x加1，没有什么意义），都应加以注释。这 会对程序的调试提供很多方便。另外，根据情况可以设立若干调试点，即输出若干信息， 用于验证和你的设想是否一致。另外，对于输入输出语句，必须对它们的作用加以说明。 否则，在调试程序时，无法了解系统需要输入说明，系统输出的又是什么。程序的书写， 必须按照一定的规范，如保留字小写时涂黑，或

5、者大写等等。具体的要求可参看软件工程 中的有关规定。上机准备和静态检查 高级语言文本 熟悉机器的用户手册，熟悉常用的命令。 准备调试的工具，考虑调试方案。如果机器上没有现成的调试工具可供利用，可以 自己先设计一些以供使用。 静态检查自己用一组数据手动执行程序；或同同学一起阅读自己的程序，以全面地了解该程序 的逻辑。上机调试程序自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联调。调试正确 后将源程序和运行结果加以列印输出。实习报告的整理 需求及规格说明问题描述，求解的问题是什么。 设计：设计思想：存储结构、主要的算法思想。设计表示：子程序（过程或函数）的规格说明，通过调用关系图表示

6、它们之间的调用 关系。实现注释：详细设计表示：主要算法的框架。 用户手册：使用说明。 调试报告：问题是如何解决的，讨论与分析、改进设想、经验与体会、时空复杂度 等。 附录源程序清单和结果：源程序必须有注释，以及必要的测试数据和运行结果数据。提倡 用英文描述。 实验报告要求：在程序开发过程中，逐步形成各种必要的文档及资料。可以写在实验报告纸上，或以 电子文档的形式进行书写。4实验时数总实验时数不得少于16学时。5实验内容和要求以下的实习题目配合课程的进度，请同学们自己务必完成。为了锻炼自己的应用各种 不同的数据结构的能力，尽可能的多作一些题目是非常必要的。在完成各种不同题目的过 程中，对各种算法

7、的时、空复杂性的分析，将帮助您在更高的角度解决各种应用问题。每次实验后要交实验报告，实验报告的内容应包括：（1）实验题目、班级、学号、 姓名、完成日期；（2）简要的需求分析与概要设计；（3）详细的算法描述；（4）程序 清单与运行结果；（5）收获与体会。实验一 线性表的顺序存储结构一、实验学时：2学时二、背景知识：顺序表的插入、删除及应用。三、目的要求：掌握顺序存储结构的特点。掌握顺序存储结构的常见算法。四、实验内容：输入一组整型元素序列，建立顺序表。实现该顺序表的遍历。在该顺序表中进行顺序查找某一元素，查找成功返回1，否则返回0。判断该顺序表中元素是否对称，对称返回1，否则返回0。实现把该表中

8、所有奇数排在偶数之前，即表的前面为奇数，后面为偶数。输入整型元素序列利用有序表插入算法建立一个有序表。利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。编写一个主函数，调试上述算法。*综合训练：利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、 查找等）五、实验说明：算法1至算法7可以以头文件的方式存储，主函数实现该头文件的包含即可调用存储定义#define MAXSIZE 100 /表中元素的最大个数typedef int ElemType； /元素类型typedef struct list（ElemType elemMAXSIZE； 静态线性表int length

9、；/表的实际长度SqList； /顺序表的类型名建立顺序表时可利用随机函数自动产生数据。六、注意问题：插入、删除时元素的移动原因、方向及先后顺序。解不同的函数形参与实参的传递关系。实验二 链式存储结构（一）单向链表的有关操作一、实验学时：2学时二、背景知识：单向链表的插入、删除及应用。三、目的要求：掌握单向链表的存储特点及其实现。掌握单向链表的插入、删除算法及其应用算法的程序实现。四、实验内容：随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。遍历单向链表。把单向链表中元素逆置（不允许申请新的结点空间）。在单向链表中删除所有的偶数元素结点。编写在非递减有序链表中插入一个元素使链表

10、元素仍有序的函数，并利用该函数建 立一个非递减有序单向链表。利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个 全部为偶数（尽量利用已知的存储空间）。*采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。在主函数中设计一个简单的菜单，分别调试上述算法。*（11）综合训练：利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、 查找等，并能够实现将数据存储到文件中）五、实验说明：类型定义#include typedef int

11、ElemType； /元素类型typedef struct LNode（ElemType data；struct LNode *next；LNode, *LinkList；为了算法实现简单，最好采用带头结点的单向链表。六、注意问题：重点理解链式存储的特点及指针的含义。注意比较顺序存储与链式存储的各自特点。注意比较带头结点、无头结点链表实现插入、删除算法时的区别。单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。实验三 链式存储结构（二）双向链表的有关操作一、实验学时：2学时二、背景知识：双向链表的插入、删除及应用。三、目的要求：掌握双向链表的存储特点及其实现。掌握双向链表的插

12、入、删除算法及其应用算法的程序实现。四、实验内容：利用尾插法建立一个双向链表。遍历双向链表。实现双向链表中删除一个指定元素。在非递减有序双向链表中实现插入元素e仍有序算法。判断双向链表中元素是否对称若对称返回1否则返回0。设元素为正整型，实现算法把所有奇数排列在偶数之前。在主函数中设计一个简单的菜单调试上述算法。五、双向链表的类型定义：typedef int ElemType； /元素类型typedef struct DuLNode（ ElemType data；struct DuLNode *prior, *next；DuLNode, *DuLinkList；六、注意问题：注意比较单向、双向

13、链表的特点。实验四 栈和队列的有关操作一、实验学时：2学时二、背景知识：入栈、出栈，入队、出队。三、目的要求：掌握栈、队列的思想及其存储实现。掌握栈、队列的常见算法的程序实现。四、实验内容：采用链式存储实现栈的初始化、入栈、出栈操作。采用顺序存储实现栈的初始化、入栈、出栈操作。采用链式存储实现队列的初始化、入队、出队操作。采用顺序存储实现循环队列的初始化、入队、出队操作。在主函数中设计一个简单的菜单，分别测试上述算法。*综合训练：利用栈实现表达式求值算法。利用栈实现迷宫求解。五、实验说明：基本要求：实现算法1、3或算法2、4即可。类型定义顺序栈小例#define MAX 100 栈的最大值ty

14、pedef struct( ElemType *base；int top；SqStack；顺序队列示例#define MAX 100 队列的最大长度typedef struct( ElemType *base；int front， rear；SqQueue；算法6的每个子功能尽可能写成函数形式。六、注意问题：重点理解栈、队列的算法思想，能够根据实际情况选择合适的存储结构。注意算法6的各个函数之间值的传递情况。栈、队列的算法是后续实验的基础(广义表、树、图、查找、排序等)。实验五 二叉树的常见操作一、实验学时：2学时二、背景知识：二叉树的存储、建立、遍历及其应用。三、目的要求：掌握二叉树的存储实

15、现。掌握二叉树的遍历思想。掌握二叉树的常见算法的程序实现。四、实验内容：输入字符序列，建立二叉链表。中序遍历二叉树：递归算法。中序遍历二叉树：非递归算法。（最好也能实现先序，后序非递归算法）求二叉树的高度。求二叉树的叶子个数。*将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。*7）建立中序线索二叉树，并实现中序遍历。借助队列实现二叉树的层次遍历。在主函数中设计一个简单的菜单，分别调试上述算法。*（1。）综合训练：为N个权值设计哈夫曼编码。五、实验说明：类型定义/二叉链表存储#define ElemType char/元素类型typedef struct BiTNode（ ElemType

16、 data；struct BiTNode *lchild， *rchild；BiTNode， *BiTree；元素类型可以根据实际情况选取。六、注意问题：注意理解递归算法的执行步骤。注意字符类型数据在输入时的处理。重点理解如何利用栈结构实现非递归算法。实验六图的有关操作一、实验学时：2学时二、背景知识：图的存储、遍历、及其应用。三、目的要求：掌握图的存储思想及其存储实现。掌握图的深度、广度优先遍历算法思想及其程序实现。掌握图的常见应用算法的思想及其程序实现。四、实验内容：键盘输入数据，建立一个有向图的邻接表。输出该邻接表。*建立一个无向图的十字链表。在有向图的邻接表的基础上计算各顶点的度，并输

17、出。以有向图的邻接表为基础实现输出它的拓扑排序序列。*采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。采用邻接表存储实现无向图的深度优先非递归遍历。采用邻接表存储实现无向图的广度优先遍历。*采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。*(1。)判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。(11)在主函数中设计一个简单的菜单，分别调试上述算法。*(12)综合训练：为计算机专业设计教学计划：4个学年，每学年2个学期，开设50门 课程，每学期所开课程门数尽量均衡，课程的安排必须满足先修关系。五、实验说明：类型定义(邻接表存储)#define MAX_VERTE

18、X_NUM 8 /顶点最大个数typedef struct ArcNode( int adjvex；struct ArcNode *nextarc；int weight； /边的权ArcNode；/表结点#define VertexType int /顶点元素类型typedef struct VNode( int degree， indegree； 顶点的度，入度VertexType data；ArcNode *firstarc；VNode/*头结点*/, AdjListMAX_VERTEX_NUM；typedef struct（AdjList vertices；int vexnum, arc

19、num； /顶点的实际数，边的实际数ALGraph；上述类型定义可以根据实际情况适当调整。算法7、8分别利用栈、队列实现非递归算法。六、注意问题：注意理解各算法实现时所采用的存储结构。注意区别正、逆邻接。实验七查找的有关操作一、实验学时：2学时二、背景知识：顺序查找、树表查找、散列查找。三、目的要求：掌握折半查找算法的思想及程序实现。掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表 的查找、建立。四、实验内容：利用实验一建立有序表，采用折半查找实现某一已知的关键字的查找。随机产生一组关键字，利用二叉排

20、序树的插入算法建立二叉排序树，然后删除某一 指定关键字元素。*建立AVL树并实现删除某一指定关键字元素。已知散列函数为H（key）=key%p （p为自定的常数），冲突处理方法分别为线性探测 法、外拉链法实现散列表的建立（利用插入算法实现）。五、实验说明：存储定义（散列表的外拉链法）#define n 9typedef struct node（int key；struct node *next；NODE；NODE *HashTable9；算法1、2、3可以参考顺序表，二叉链表的存储实现。各种关键字数据输入可利用随机函数自动产生，以便节省上机时间。算法1存储在文件seqlist.h中，算法2、3

21、存储在文件bintree.h中，算法4存储 在文件hash.h中六、注意问题：注意理解折半查找的适用条件（链表能否实现折半查找？）。注意建立二叉排序树、散列表时相同元素的处理。注意理解静态查找、动态查找概念。比较各种查找算法的各自特点，能够根据实际情况选择合适的查找方法。实验八排序的有关操作一、实验学时：2学时二、背景知识：各种排序方法三、目的要求：掌握常见的排序算法的思想及其适用条件。掌握常见的排序算法的程序实现。四、实验内容：输入一组关键字序列分别实现下列排序：实现简单选择排序、直接插入排序和冒泡排序。实现希尔排序算法。实现快速排序算法。实现堆排序算法。*快速排序的非递归算法。*实现折半插

22、入排序。*采用链式存储实现简单选择排序、直接插入排序和冒泡排序。在主函数中设计一个简单的菜单，分别测试上述算法。*综合训练：采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。五、实验说明：类型定义#define MAXSIZE 100 /*参加排序元素的最大个数*/typedef struct listint key；RedType；typedef struct RedType rMAXSIZE+1；int length； /*参加排序元素的实际个数*/SqList；算法5可以借助栈实现。六、注意问题：在RedType中增加一个数据项验证各种排序算法的稳定性。注意理解各种算法的思想、了解算法的适用情况及时间复杂度，能够根据实际情况 选择合适的排序方法。