Homework and Lab for Harbin Institute of Technology data structure and algorithm.
Please do not copy the code directly.
I am very glad to accept issues if there is a problem with the code.
- HW1 线性结构的存储结构与应用
- 用线性表实现顺序存储结构 (SeqList) 和链式存储结构 (LinkList)
- 在上书存储结构的基础上,分别实现以下算法:
- 删除给定元素的算法
- 对于一排好序的线性表,删除所有重复元素的算法
- 线性表“逆置”算法
- 线性表循环左移/右移k位的算法
- 合并两个已排好序的线性表的算法
- 实现线性表的静态链表存储结构
- 在静态链表上实现线性表的“逆置”算法
- LAB1 栈结构及其应用
- 表达式求值是实现程序设计语言的基本问题之一,也是栈的应用的一个典型例子。一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数,运算符只含加减乘除等四种二元 运算符,界限符有左右括号和表达式起始、结束符“#”,如:#(7+15)* (23-28/4)#。引入表达式起始、结束符是为了方便。设计一个程序,演示算 术表达式求值的过程。
- 实验要求:
- 从文本文件输入任意一个语法正确的(中缀)表达式,显示并保存该表达式。
- 利用栈结构,把(中缀)表达式转换成后缀表达式,并以适当的方式展示栈 的状态变化过程和所得到的后缀表达式。
- 利用栈结构,对后缀表达式进行求值,并以适当的方式展示栈的状态变化过 程和最终结果。
- 选做:将操作数类型扩充到实数、扩充运算符集合,并引入变量操作数,来 完成表达式求值。
- 选做:设计和实现结合 2 和 3 的“算法优先法”。
- HW2 树形结构及其应用
- 编写建立二叉树的动态(或者静态)二叉链表存储结构(左右链表示)的程序,并以适当的形式显示和保存二叉树
- 采用二叉树的上述二叉链表存储结构,编写程序实现二叉树的先序、中序和 后序遍历的递归和非递归算法以及层序遍历算法,并以适当的形式显示和保 存二叉树及其相应的遍历序列;
- 设计并实现判断任意一棵二叉树是否为完全二叉树的算法。
- 设计并实现计算任意一棵二叉树的宽度的(递归或非递归)算法。二叉树的宽度是指其各层结点数的最大值。
- LAB2 哈夫曼树的建立
- 树形结构及其应用
- 哈夫曼编码是一种以哈夫曼树(最优二叉树,带权路径长度最小的二叉树) 为基础变长编码方法。其基本**是:将使用次数多的代码转换成长度较短的编 码,而使用次数少的采用较长的编码,并且保持编码的唯一可解性。在计算机信息 处理中,经常应用于数据压缩。是一种一致性编码法(又称"熵编码法"),用于 数据的无损压缩。要求实现一个完整的哈夫曼编码与译码系统。
- 实验要求
- 从文件中读入任意一篇英文文本文件,分别统计英文文本文件中各字符(包 括标点符号和空格)的使用频率;
- 根据已统计的字符使用频率构造哈夫曼编码树,并给出每个字符的哈夫曼编 码(字符集的哈夫曼编码表);
- 将文本文件利用哈夫曼树进行编码,存储成压缩文件(哈夫曼编码文件);
- 计算哈夫曼编码文件的压缩率;
- 将哈夫曼编码文件译码为文本文件,并与原文件进行比较。 以下为选做(可以不做,不扣分),供学有余力、有兴趣的同学思考和探索。
- 能否利用堆结构,优化的哈夫曼编码算法。
- 上述 1-5 的编码和译码是基于字符的压缩,考虑基于单词的压缩,完成上述 工作,讨论并比较压缩效果。
- 上述 1-5 的编码是二进制的编码,可以采用 K 叉的哈夫曼树完成上述工作, 实现“K 进制”的编码和译码,并与二进制的编码和译码进行比较。
- HW3 图形结构及其应用
- 分别实现无向图(或有向图)的邻接矩阵和邻接表存储结构的建立算法,分析和比较各建立算法的时间复杂度以及存储结构的空间占用情况。
- 实现无向图(或有向图)的邻接矩阵和邻接表两种存储结构的相互转换算法。
- 在上述两种存储结构上,分别实现无向图(或有向图)的深度优先搜索(递归 和非递归)和广度优先搜索算法。并以适当的方式存储和展示相应的搜索结果, 包括:深度优先或广度优先生成森林(或生成树)、深度优先或广度优先序列和 深度优先或广度优先编号。并分析搜索算法的时间复杂度和空间复杂度。
- (1)对于无向图,采用“邻接表”存储结构,设计和实现计算每个顶点度的算 法,并分析其时间复杂度。或者,
- (2)对于有向图,采用“邻接表”存储结构,设计和实现计算每个顶点入度、 出度和度的算法,并分析其时间复杂度。
- 以适当的方式输入图的顶点和边,并显示相应的结果。要求顶点不少于 10 个,边不少于 13 个。
- LAB3 图形结构及其应用
- 最小生成树算法
- 实验内容: 最小生成树是数据结构与算法中图的一种重要应用,在图中对于具有 n 个顶点的连通网可以建立许多不同结构的生成树,最小生成树就是在所有生成树中边 权值之和最小的生成树。在计算机领域和实际工程中具有广泛的应用,如局域网的搭建,道路网(畅通工程)、地下管网的设计等。本实验要求设计和实现 Prim 和 Kruskal 等算法,求解最小生成树问题。
- 选择并建立加权连通图的存储结构,实现求解加权连通图的 Prim 算法,并 输出连接各顶点的最小生成树。
- 利用并查集,实现求解加权连通图的 Kruskal 算法,并输出连接各顶点的最 小生成树。
- 以文件形式输入图的顶点和边,并以适当的方式展示相应的结果。要求顶点 不少于 10 个,边不少于 13 个。
- (选做)通过实验的方法,比较 Prim 和 Kruskal 算法的时间性能,并与理论 分析结果进行比较。你的实验结果是否与理论分析结果一致?你的实验结果 是否支持“Prim 算法对边稠密的图更有优势,而 Kruskal 算法对边稀疏的图 更具优势”这个结论?
- (选做)利用堆结构(优先级队列)改进和优化 Prim 算法,实现改进和优 化的 Prim 算法,并与原算法进行实验比较。
- (选做)设计并实现其他最小生成树算法。例如,管梅谷破圈算法、Sollin (Boruvka)算法。
- HW4 查找结构与排序方法
- BST 查找结构与折半查找方法的实现与实验比较
- 要求编写程序实现 BST 存储结构的建立(插入)、删除、查找和排序算 法;实现折半查找算法;比较 BST 查找与折半查找方法的时间性能。
- 设计 BST 的左右链存储结构,并实现 BST 插入(建立)、删除、查找和排序算法。
- 实现折半查找算法。 3.实验比较:设计并产生实验测试数据,考察比较两种查找方法的时间性能, 并与理论结果进行比较。以下具体做法可作为参考:
- (1) 第 1 组测试数据: n = 1024 个已排序的整数序列(如 0 至 2048 之间 的奇数);第 2 组测试数据:第 1 组测试数据的随机序列。
- (2) 以上述两组测试数据作为输入,分别建立 BST 查找结构。
- (3) 编写程序计算所建的两棵 BST 的查找成功和查找失败的平均查找长度 (主要是改造 Search 算法,对“比较”进行计数),并与理论结果比较。
- (4) 分别以上述 BST 查找结构的中序遍历序列作为折半查找算法的输入,编 写程序分别计算折半查找的查找成功和查找失败的平均查找长度,并与理 论结果比较。
- (5) 以上实验能否说明:就平均性能而言,BST 的查找与折半查找差不多,为什么?
- HW5 排序方法
- 排序简答题
- (1) 指出堆和二叉排序树的区别;
- (2) 若只想得到一个序列中第 k (k ≥ 5) 个最小元素之前的部分排序序列,则 最好采用什么排序方法?
- (3) 已知由𝑛 (𝑛 ≥ 2) 个正整数构成的集合𝐴 = {𝑎: 0 ≤ 𝑘 < 𝑛},将其划分为两 个不相交的子集𝐴1和𝐴2,元素个数分别是𝑛1和𝑛2,𝐴1和𝐴2中的元素之和分别为 𝑆1和𝑆2。设计一个尽可能高效的划分算法,满足|𝑛1 − 𝑛2|最小且|𝑆1 − 𝑆2|最大。要 求:
- 1)给出算法的基本设计**;
- 2)根据设计**,采用 C/C++语言描述算法,关键之处给出注释;
- 3)说明你所设计算法的平均时间复杂度和空间复杂度。