数据结构实验及实验报告规范

试验一集合交、并和差运算实现1.试验性质：设计性试验2.要求：（1）对两个集合建立单链表存放构造；（2）实现集合交集、并集和差集运算；（3）实现运算时，不另外申请存放空间。3.目标：掌握线性表链式存放方式及其操作实现注：根据自己编程能力，交集、并集和差集运算能够选择其中之一进行。1/11试验二括号匹配

1.试验性质：设计性试验2.要求：

输入带括号体现式，判断其中括号是否配对。3.目标：掌握栈基本操作并会应用。扩展功能：根据自己编程能力，能够增加功能，例如

给出配对括号位序和不配对括号位序。2/11试验三二叉树综合操作

1.试验性质：综合性试验2.要求：

A.采取二叉链表构造建立二叉树；

B.显示对其先、中、后序和层序遍历成果。3.目标：A.掌握二叉树二叉链表存放方式及二叉树特性；B.学会应用栈和队列。

扩展功能：根据自己编程能力，能够增加如下功能：

A.

先序/中序/后序遍历之一必须采取非递归实现；B.

求出该树高度和叶子结点个数。

C.图形显示出该树。等等….3/111．试验性质：综合性试验2．要求：

A.初始化：从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树；B.编码：根据哈夫曼树对树中叶子结点进行哈夫曼编码；C.输出哈夫曼编码。

3.目标：

掌握哈夫曼树构造办法和哈夫曼编码办法.

选做功能：（1）对输入字符串利用上述哈夫曼编码进行译码并输出译码后成果；（2）将已在内存中哈夫曼树以直观方式（画图）显示出来。

试验三哈夫曼编码实现

(选作)4/11试验四图建立和遍历

1．试验性质：验证性试验2．要求：

A.选择所建立图类型（无向图，有向图，无向网络，有向网络），采取邻接表存放方式实现；

B.采取深度优先/广度优先搜索方式遍历图。3.目标：

（1）掌握图邻接表存放方式；

（2）掌握图遍历方式。5/11试验五次序查找和折半查找性能比较

1.试验性质：设计性试验2.要求：A.对于有序数组，改善教材上次序查找算法，利用数组有序性提升查找性能；B.实现折半查找算法；C.对于相同数组元素，同样待查值，将上述两种查找算法进行比较，给出不一样算法进行比较详细结论（即比较次数和移动次数）。3.目标：

(1)掌握次序查找和折半查找办法；

(2)比较上述查找办法性能。6/11试验五二叉排序树建立和查找1.试验性质：设计性试验2.要求：A.输入一组整数构造一棵二叉排序树；B.二叉排序树建立过程即是对这组整数查找和插入过程。3.目标：

掌握二叉排序树创建、查找和插入操作实现。7/11试验六多种排序算法时间性能比较1.试验性质：综合性试验2.要求：A.挑选课本中已经讲过几个排序算法设计并实现；

B.产生正序和逆序初始排列分别调用上述排序算法，并比较时间性能：

C.产生随机初始排列分别调用上述排序算法，并比较时间性能。

3.目标:

(1)掌握多种排序算法实现；(2)比较多种排序算法时间性能。8/11试验六多种排序算法时间性能比较1.试验性质：综合性试验2.要求：A.挑选课本中已经讲过几个排序算法设计并实现；

B.产生正序和逆序初始排列分别调用上述排序算法，并比较时间性能：

C.产生随机初始排列分别调用上述排序算法，并比较时间性能。

注：对于基于比较内排序而言，其时间主要消耗在排序过程中进行元素比较和移动上，因此，统计在相同数据状态下不一样排序算法比较次数和移动次数，即可实现比较多种排序算法目标。9/11试验报告规范一.实验要求二.实验目三.设计思想四.主要源代码五.调试与测试数据六.实验总结开头：题目班级姓名学号10/11设计思想：将程序提成合理多种模块（函数），每个模块做详细某一事情,写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。主要源代码：函数调用格式、参数含义、返回值描述、函数功能；函数之间调用关系图、程序总体执行流程图;主要函数详细代码(加文档说明).调试与测试数据：犯错次数、