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)说明你所设计算法的平均时间复杂度和空间复杂度。
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent