数据结构与算法实验指导书(计科1021)

《数据结构与算法》实验指导书

实验课程编号：07ZB101109 实验室名称：多媒体技术实验室 系（院）：数计学院 实验室地点：N5-402 实验课学时：36 实验类别：专业课 适用专业：计算机科学与技术 是否独立设课：是

执笔人：李文新 审批人： 一、实验课程教学目的和要求

《数据结构与算法》是一门实践性很强的课程，光靠读书和做习题是不能提高实践能力的。

《数据结构与算法》的实验与程序设计语言课程中的实验不同，后者更多的强调语言方面的功能实现，而前者更接近实际，需要同学们自己分析问题，设计模型和算法，再上机调试完成。 《数据结构与算法》的实验的目的主要有两个：

1）深化理解书本上的理论知识，将书本的知识变“活”（为已掌握，为已活用）；

2）理论和实践相结合，学会将相关的数据结构和算法应用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。

《数据结构与算法》的实验类型

1）验证性实验—主要是验证教材中已有的数据结构和算法。 2）设计性实验—针对具体问题，应用某一个知识点，自己设计数据结构和算法，培养对数据结构的简单运用能力。

3）综合性实验—针对具体问题，应用某几个知识点，自己设计数据结构和算法，培养对数据结构的综合运用能力。 《数据结构与算法》的实验安排 项目 一 二 三 实验题目 结构体的运用 结构体与指针的运用 顺序表的保序插入操作 链表的保序插入操作 学时 2 2 2 2 2 2 2 2 2 2 2 2 2 说明 设计 设计 设计 设计 设计 验证 设计 验证 设计 验证 设计 设计 验证 四 循环单链表的插入和删除 五 六 七 八 九 十 十一 十二 栈与队的操作 栈与队的的应用 对称矩阵的压缩存储 压缩矩阵的应用 二叉树的操作 二叉树的应用 二叉树的应用 图的操作 十三 十四 十五 十六 十七 十八

图的应用 图的应用 查找操作 查找应用 排序操作 排序应用 2 2 2 2 2 2 设计 设计 验证 设计 验证 设计 《数据结构与算法》实验的一般步骤

1）需求分析：要对简单的问题描述进行详细的分析，充分理解问题，明确问题要求做什么，有什么数据，边界条件……。

2）概要设计：针对问题描述中涉及到数据定义抽象数据类型，设计数据结构和算法模型。本部分不必考虑实现的细节。

3）详细设计：设计具体的存储结构（用C++实现抽象数据类型对应的类）。此外，还要设计对象间的调用关系及输入输出。 4）上机调试（运行代码，修正语法及逻辑错误） 5）结果与总结

《数据结构与算法》的实验要求： 1）完成实验预习； 2）完成并上交实验报告； 3）完成电子设计文档 预习/实验报告的格式要求： 1）实验名称

2）实验目的 3）实验内容及要求 4）概要设计：ADT 5）详细设计：C++类或C函数 6）调试分析： 7）结果与总结

实验一: 结构体的运用

一、实验目的：

1）结合C++的输入输出流复习C语言的知识； 3）掌握结构体的运用方法。 二、实验内容及要求：

一个班有n个学生，每个学生有学号（no）、姓名（name）、年龄（age）、成绩（score）。定义结构体来描述学生信息。并定义n个学生的结构体数组。

要求：

设计一个函数，输入n个学生的数据；提示性输入。 设计一个函数，输出n个学生的数据；输出整齐，控制域宽。 设计主函数，调用输入输出函数。

分别定义结构体数组为全局变量和局部变量两种情形进行调试和运行程序。

结构体与指针的运用

一、实验目的：

1）结合C++的输入输出流及动态分配/撤消运算符复习C语言的知识；

3）掌握结构体与指针的运用。 二、实验内容及要求：

建立一个动态链表，链表的结点结构： data next

其中：data为整数类型，next为指针类型 链表示例： head 18 7 15 20∧ 其中：head为指向该链表的头指针。 要求：

定义一个结构体：描述结点信息； 设计一个函数，动态建立该链表； 设计一个函数，输出该链表的数据；

设计主函数，调用建立链表和输出链表数据的函数。

分别定义head为全局变量和局部变量两种情形进行调试和运行程序。当head为局部变量时应将建立链表函数的参数设为引用参数。

3) 遍历算法分别用递归和非递归算法。

实验十：二叉树的应用 求二叉树叶子结点个数和深度

一、问题描述：

已知一棵二叉树，求该二叉树中的叶子结点的个数和深度。 二、基本要求：

1) 采用二叉链表存储结构；

2) 设计算法求二叉树中的叶子结点的个数和二叉树t的深度。 三、设计思想：

在实验九（二叉树的操作）的基础上设计算法求二叉树中的叶子结点个数和二叉树t的深度。

分别用递归和非递归算法。

实验十一：二叉树的应用（哈夫曼编码）

一、问题描述：

设某编码系统共有n个字符，使用频率分别为（w1,w2,…,wn）。设计一个不等长的编码方案，使用该编码系统的空间效率最好。 二、基本要求：

1) 设计数据结构； 2) 设计编码算法；

3）分析算法的时间复杂度和空间复杂度。

三、设计思想：

利用Huffman编码树求得最佳的编码方案。

根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组Huffman，保存哈夫曼树中各结点的信息，每个结点包括权值、左孩子、右孩子和双亲。由于哈夫曼树中共有2n－1个结点。并且进行n－1次合并操作，所以该数组的长度为2n－1。

weigth lchild rchild parent 在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼树编码。

实验十二：图的操作

一、实验目的：

1）掌握图的存储结构； 2）掌握构造邻接矩阵的方法； 3）掌握图的遍历算法的算法实现。 二、实验内容及要求：

按给定的任一连通无向图构造邻接矩阵，再进行深度优先遍历和广度优先遍历。

实验十三：图的应用 求无向连通图的生成树

一、问题描述：

求无向连通图的一棵生成树。 二、基本要求：

1）采用邻接矩阵存储； 2) 求深度优先生成树； 3) 输出该生成树的每一条边。 三、设计思想：

在一个连通无向图G=(V,E)中，如果从任一个顶点开始进行深度优先遍历，必定将边集E分成两个集合T和B,其中T是遍历过程中经历的边的集合，B是剩余的边的集合。显然，边集T和图G所有顶点一起构成连通图G的一棵生成树。因此，修改深度优先遍历算法，输出遍历所经过的边。

实验十四：图的应用

求有向图的路径

一、问题描述：

对于有向图G=(V,E),任意vi，vj (i≠j),判断从顶点vi到顶点vj是否存在路径。 二、基本要求：

1）有向图采用邻接矩阵存储； 2) 设计算法完成问题求解；

3) 设计存储结构存储从顶点vi到顶点vj的路径。

三、设计思想：

可以利用深度优先遍历，从顶点vi出发进行深度优先遍历，如果在遍历过程中，访问到顶点vj，则从顶点vi到顶点vj存在路径。 因此，修改深度优先遍历算法，判断在遍历中是否访问顶点vj。

实验十五：查找操作

一、实验目的：

1）掌握顺序查找技术和拆半查找技术； 2）掌握查找的算法实现； 二、实验内容及要求：

1、产生n个随机整数用顺序查找的方法进行查找操作，并统计查找的次数。

2、给定n个有序整数用折半查找的方法进行查找操作，并统计查找的次数。

要求分别用初始化函数，顺序查找函数，折半查找函数及输出函数来完成。

实验十六：查找应用 散列表的建立和查找

一、实验目的：

1）掌握散列查找的基本思想； 2）掌握闭散列表的构造方法； 3) 掌握线性探测处理冲突的方法；

4) 掌握散列技术的查找性能。 二、实验内容及要求：

1) 对于给定的一组整数和散列函数，采用线性探测法处理冲突构造散列表；

2) 设计查找算法，验证查找性能。

实验十七：排序操作

一、实验目的：

1）深刻理解各种排序算法的设计思想； 2）掌握各种排序算法的执行过程； 3）掌握各种排序算法的设计实现。 二、实验内容及要求：

产生n个随机整数分别采用直接插入排序、希尔排序和冒泡排序的方法进行排序。

要求分别采用各排序函数和输出函数来完成。

实验十八：排序应用

一、问题描述：

一个班有n个学生，每个学生有学号（no）、姓名（name）、年龄（age）、成绩（score）。定义数据结构来描述学生信息。并按成绩进行降序排列。 二、基本要求：

1) 可任用一种排序算法，按成绩进行降序排列。 2) 输出已排序的学生数据；要求输出整齐。

本文来源：https://www.bwwdw.com/article/ukda.html