本文诞生于一个非常危急的时刻，如果说这门没过的话这篇接着删。

本科阶段的数据结构通常涉及以下知识点

线性表

链表

学过C语言的都知道有一个链表，其结构如下：

链表头->元素->...->链表尾部

这个结构中每个元素都指向下一个元素的地址，可想而知我们只能知道下一个元素的地址，而下下个元素需要访问下一个元素才能知道，因此线性表是不支持随机访问的

链表也分很多种，主要是单链表和双向链表，区别主要就是指针是不是两头都有。

顺序表

这个就更好理解了，所有的元素在内存地址中都是按照一定的顺序排列在一起的，和链表相比这个是支持随机访问的，因为内存地址是有顺序的，数组就是顺序表的一种。

栈和队列

栈（stack）

栈遵循的是后入先出，也就是说永远优先取出最顶部的那层，最常见的就是所谓的函数栈，最顶部的函数最优先运行。由于栈的这个特性，所以栈一般与递归挂钩

队列（quene）

队列遵循的是先进先出，也就是说所有的元素就像排队一样一直往前走。

队列可能还会涉及计算有效元素数量的问题，有两种讨论方法

front和rear标志位

front（前），rear（后），通过这两个指针来计算队列的长度，其中front=/>/<都要分情况讨论。

count

使用count进行计数，入队就++，出队就--，个人感觉这是最优雅的方法。

二叉树

个人感觉二叉树最麻烦的就是与其相关的计算了

概念

一个节点分出两个子节点，然后这两个子节点又能各自分出自己的子节点，这就是二叉树。

• 节点：二叉树中的基本元素，可以包含一个值以及指向左右子节点的引用。

• 根节点：树最顶部的那个节点，没有父节点。

• 叶子节点：没有任何子节点的节点。

• 度：节点拥有的子节点数目；对于二叉树而言，任何节点的度都不会超过2。（可以理解成这个节点有几个“树枝”）

• 深度/高度：从根节点到某个节点的路径长度称为该节点的深度；而整棵树的最大深度即为树的高度。

• 层次：根节点位于第一层，其直接后继位于第二层，以此类推。

以下是二叉树的性质：

1. 在二叉树的第i层上至多有2^{(i-1)}个结点（i≥1）。

2. 深度为k的二叉树至多有2^k-1个结点（k≥1）。

3. 对于任意一棵二叉树T，如果其终端结点数为n_0​，度为2的结点数为n_2​，则n_0=n_2+1。(终端节点等于度数为2的节点总和+1)

4. 具有n个结点的完全二叉树的深度为[log_2(n)]+1。（二叉树深度就这么算）

5. 如果将一棵有n个结点的完全二叉树自顶向下、同层自左向右连续编号，则对于任一结点i：

   • 若i=1，则结点i是二叉树的根，无双亲；若i>1，则其双亲PARENT(i)是结点⌊i/2⌋。

   • 若2i>n，则结点i无左孩子；否则其左孩子LCHILD(i)是结点2i。

   • 若2i+1>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1

     （最后这两条简单点可以理解成2i比总结点数大的话就是左孩子）

二叉树的分类：

• 满二叉树：所有分支节点都有左右两个子节点，并且所有的叶子都在最后一层。

• 完全二叉树：除了最后一层外，其它各层的节点数都达到最大值，且最后一层的节点都尽可能地集中在左边。

• 平衡二叉树：如AVL树，保证了树的高度接近对数级别，从而提高了查找效率。

• 二叉查找树（BST）：也叫二叉搜索树，满足左子树上的所有键值小于根节点的键值，右子树上的所有键值大于根节点的键值

二叉树的遍历

前序、中序、后序，这三种说白了无外乎是以下三个操作的排列组合：

• 访问节点（V)

• 有左孩子就访问左孩子(L)

• 有右孩子就访问右孩子(R)

也就是说对于前序遍历，每个节点的过程是这样的：VLR

中序遍历就是：LVR

后序遍历就是：LRV

还有一个层次遍历就是一层一层遍历所有当前层次的子节点。

哈夫曼编码

实现步骤：

1. 统计各个字符频率

2. 创建初始森林（就是每个节点都是一个字符，而且这个节点都带权）

3. 构建哈弗曼树（选取最小的两个节点作为子节点，其父节点的权是二者之和）

4. 重复构建直至只剩一棵树

5. 这棵树的左分支标0，右分支标1

用图来说的话就是这样：

哈夫曼树的性质：

• 只存在度为0和2的节点

• 如果一个哈弗曼树有n个叶子结点，那么这棵树中一共有2n-1个节点

这样如果有一个字符串的话就可以根据根节点到对应字符的叶子节点的路径找出对应的哈夫曼编码

图

这玩意第一眼看上去会很抽象，但是理解名词之后就很简单了

基本概念

图由顶点和边组成，图也分为有向图和无向图

有向图：所有的边都有明确的方向

无向图：所有的边都没有方向

边还可以拥有权重

连通性

连通性指的是在一个图中任意两点间是否存在至少一条路径相连。对于无向图来说，如果图中任意两个顶点都可通过某些路径相互到达，则称该图为连通图。而在有向图中，强连通图要求不仅存在从i到j的路径，还必须存在从j返回到i的路径。

环路

从一个顶点出发是否可以回到这个顶点

生成树

一个连通图中包含所有顶点的连通子图，其中所有边权值加起来最小的就是最小生成树

时间复杂度

• 常数阶 O(1)：无论输入数据量有多大，算法执行时间始终保持不变。这类算法具有最高的效率，比如访问数组中的固定位置元素。

• 对数阶 O(log_n)：随着输入规模的指数级增长，算法执行时间仅线性增加。典型的例子是对半查找（Binary Search），每次迭代都能将搜索范围缩小一半。

• 线性阶 O(n)：算法执行时间与输入规模成正比。如遍历列表中的所有元素进行简单操作。

• 线性对数阶 O(nlog_n)：常见于一些高效的排序算法，如快速排序（Quick Sort）或归并排序（Merge Sort）。

• 平方阶O(n^2)：包含嵌套循环结构的算法往往属于此类，像冒泡排序（Bubble Sort）等简单的排序方法。

• 立方阶 O(n^3)：多层嵌套循环会导致更高的时间复杂度，通常出现在矩阵运算等领域。

• 指数阶 O(2^n)：递归求解斐波那契数列等问题可能会产生这种级别的复杂度，意味着每增加一个单位的输入都会使计算量翻倍。

• 阶乘阶O(n!) ：最坏情况下，某些组合优化问题可能达到这样的复杂度，例如旅行商问题（Traveling Salesman Problem）的暴力破解法