# 数据结构与算法复习
## 1. 哈夫曼编码
- **定义**：一种无损数据压缩算法，通过字符频率生成变长编码。
- **构建方法**：
1. 创建节点列表，每个字符及其频率为一个节点。
2. 反复取出频率最小的两个节点，合并成新节点。
3. 重复此过程直到只剩一个根节点。
## 2. 树的遍历
- **前序遍历**：根 -> 左 -> 右
- **中序遍历**：左 -> 根 -> 右
- **后序遍历**：左 -> 右 -> 根
- **实现**：使用递归或栈。
## 3. 有向图与无向图
- **有向图**：边有方向，表示从一个顶点指向另一个。
- **无向图**：边没有方向，表示双向关系。
- **遍历方法**：深度优先搜索 (DFS) 或广度优先搜索 (BFS)。
## 4. 高精度
- **定义**：处理超出标准数据类型范围的数值运算。
- **工具**：使用高精度库，如 C++ 的 `BigInteger` 或 Python 的 `int`。
## 5. 位运算
- **定义**：对二进制位进行操作的运算。
- **常用技巧**：
- 判断奇偶：`x & 1`（0为偶数，1为奇数）
- 交换两个数：`a ^= b; b ^= a; a ^= b;`
- 清零最低位的 1：`x & (x - 1)`
## 复习建议
- **多做题**：刷题加深理解。
- **画图**：可视化树和图形。
- **总结知识点**：写下关键点，便于快速回顾。
祝你在 CSP 中取得好成绩！如有其他问题，随时问我！
by ran_qwq @ 2024-09-19 22:28:51
@[timestimes_2022](/user/1404097) **超出整形(int)和(long long)数据范围的数**
by Liziya @ 2024-09-19 22:29:25
@[ran_qwq](/user/743048) 谢。我是不是关过你？
by timestimes_2022 @ 2024-09-19 22:29:58
@[timestimes_2022](/user/1404097)
哈夫曼编码（[Huffman Coding）：是一种用于无损数据压缩的熵编码算法。它使用变长编码表来表示数据，其中频率高的数据使用较短的编码，频率低的数据使用较长的编码，从而达到压缩数据的目的。这种编码方式是由David A. Huffman于1952年提出的，它完全依据字符出现概率来构造平均长度最短的码字，有时也被称为最佳编码12。
树的前中后序遍历：树的前序遍历、中序遍历和后序遍历是二叉树遍历的三种基本方法。
前序遍历：首先访问根节点，然后遍历左子树，最后遍历右子树。
中序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树。
后序遍历：首先遍历左子树，然后遍历右子树，最后访问根节点。
有向无向图：图是由顶点（节点）和边构成的数学模型。
有向图：边有明确的方向，即每条边都有一个起始顶点和终止顶点。
无向图：边没有方向，即每对顶点之间有一条无方向的边连接。
高精度：在计算机科学和数学中，高精度计算通常指的是处理超出标准数据类型（如整数或浮点数）表示范围的大数或小数。这通常涉及到使用特殊的数据结构（如大数库）或算法来实现高精度的数学运算。
位运算：位运算直接对二进制位进行操作，包括但不限于按位与（&）、按位或（|）、按位异或（^）、按位非（~）、左移（<<）、带符号右移（>>）等。这些操作在计算机底层操作中非常常见，如整数除法、逻辑运算等。
by guanhetian @ 2024-09-19 22:30:05
@[timestimes_2022](/user/1404097) 位运算 n << 1,相当于n * 2. n >> 1，相当于n / 2
by xhx2011 @ 2024-09-19 22:30:10
@[ran_qwq](/user/743048) ~~CSP让用外置函数库吗~~
by Liziya @ 2024-09-19 22:30:44
@[guanhetian](/user/937470) 已关
by timestimes_2022 @ 2024-09-19 22:31:23