【数据结构】期末速通！

1. 绪论

1. 与数据元素本身的形式、内容、大小个数等无关的是数据的(B)
   A.存储结构B.逻辑结构C.存储实现D.运算实现

2. 从逻辑上可以把数据结构分成（C）
   A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D. 内部结构和外部结构

3. 下面哪个是非线性数据结构（A）
   A.树B.字符串C.队列D.栈

逻辑结构描述的的是关系，与数据元素本身特点以及计算机参数等没有关系。

算法的五个特性：有穷，确定，可行，输入和输出。

算法的四个评价准则：正确性，可读性，健壮性，高效性。

分析时间复杂度，直接考虑最坏的情况。

1. 算法的输入范围为[0，1000]，因此 0 和 1000 是该算法输入的边界情况，而超出边界将出现死循环，说明该算法在处理边界情况的时候不够仔细,导致出错,术语上称这种情况为不够健壮或不够鲁棒(robust)。

2. 逻辑结构只描述数据元素之间的逻辑关系,在数据结构上发生的实际操作效率受到其存储结构的影响,如用通过下标访问线性表元素这一操作在顺序表实现的复杂度为。如用通过下标访问线性表元素这一操作在顺序表实现的复杂度为 O(1)，但在链表实现的复杂度则为 O(n)。

• 逻辑结构：线性，树形（层次），图形，集合（无序）

• 存储结构：顺序，链式

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。

一个数据元素有若干个数据项组成，数据项是数据的不可分割的最小单元。

2. 线性表

线性表具有以下特征：

1. 有序性：线性表中的元素是有序的，每个元素都有一个确定的位置。通常使用下标来表示元素的位置，从0开始递增。

2. 一对一关系：线性表中的每个元素都只有唯一的后继和前驱元素，除了第一个元素没有前驱元素，最后一个元素没有后继元素。

3. 可变长度：线性表的长度是可变的，可以动态地添加或删除元素。

4. 同类型：线性表中的元素类型通常是相同的，所有元素都属于同一种类型。

5. 存储区间连续性：数组连续，链表不连续。

线性表的常见实现方式有数组和链表。

顺序表中有n个数组元素，读取第i个数组元素的平均时间复杂度为O(1)。

顺序表可以近似看做是数组，增删元素会引发很多元素的移动。

单链表的存储密度 < 1。（存储密度 = （结点数据本身所占的存储量）/（结点结构所占的存储总量））

顺序表，单链表插入删除元素的空间复杂度 O(1)，时间复杂度为 O(n)。

顺序表n个元素，插入或者删除一个元素，平均要移动元素个数是 n/2 。如果n为127，则平均63.5（可以为小数）。

单链表增加和删除元素虽然不用移动元素，但需先找到其前驱结点，复杂度为(n)。

若线性表需要频繁更新元素，选择顺序表。若需要频繁插入删除元素，选择链表。但是二者的定位元素效率接近，都需要挨个查找。

线性表的集合式合并，时间复杂度O(mn)，空间复杂度：1. 顺序表O(m+n) 2. 链表 O(1)

合并两个有序表为一个有序顺序表，时间复杂度和空间复杂度都是 O(m+n)

合并两个有序单链表：时间复杂度O(m+n)，空间复杂度O(1)

时间复杂度不含有常数。

链式存取，先查后存取。

无论两个链表多长，合并他们只需要额外开辟一个头节点，空间复杂度为O(1)。

使用头结点实现单链表课降低增删代码的编写难度。

寻址公式：

1. 线性寻址公式：
   目标地址 = 基地址 + 偏移量
   这种寻址方式常用于数组、矩阵等连续内存结构，其中基地址是起始地址，偏移量是元素相对于起始地址的偏移量。
2. 哈希寻址公式：
   目标地址 = 哈希函数（关键字）
   哈希寻址公式使用哈希函数将给定的关键字映射到内存地址上，通常用于哈希表等数据结构，能够快速的进行查找、插入和删除操作。

3. 栈和队列

顺序栈top=base表示空栈，base指向栈底，top指向栈顶元素的后一个元素，随着元素入栈自增。

将一个递归函数实现的算法改为非递归函数实现需要利用栈。 函数调用的本质就是将被调函数压入调用栈使其成为当前栈顶,以优先处理被调函数,再其结束后弹出，让原函数重回栈顶继续执行。

循环队列的好处是避免假溢出现象。而非共享数据空间。

栈（Stack）：

1. 后进先出（Last-In-First-Out，LIFO）的数据结构。
2. 只能在一端进行插入和删除操作，该端被称为栈顶。
3. 从栈顶插入新元素称为入栈（Push），从栈顶删除元素称为出栈（Pop）。
4. 栈的基本操作包括入栈、出栈和获取栈顶元素。
5. 常见的应用有表达式求值、函数调用和递归等。

队列（Queue）：

1. 先进先出（First-In-First-Out，FIFO）的数据结构。
2. 可以在一端进行插入操作，称为队尾，另一端进行删除操作，称为队首。
3. 从队尾插入新元素称为入队（Enqueue），从队首删除元素称为出队（Dequeue）。
4. 队列的基本操作包括入队、出队和获取队首元素。
5. 常见的应用有任务调度、缓冲区管理和广度优先搜索等。

循环队列：

1. 判断队空 Q.rear == Q.front
2. 队尾指针的后一个位置为队头指针，即队满 (Q.rear + 1) % MaxSize == Q.front，队尾指针指向队尾元素的后一个位置

4. 树和二叉树

4.1 度

节点的度（Degree）是指一个节点拥有的子树的数量，也即该节点的子节点数目。对于二叉树来说，节点的度最多为2，因为每个节点最多只能有左右两个子节点。

树的度（Degree）是指树中节点的最大子树度。换句话说，树的度是树中各个节点的度的最大值。

4.2 一些概念

二叉树：

• 满二叉树：装满的二叉树。

• 完全二叉树：可能会在右下角有空缺的二叉树。

• 二叉树中，节点的度指的是结点拥有的子树的数目。

• 将森林转化为二叉树：

• 森林转化为二叉树是确定且唯一的。一棵树转化为二叉树形态唯一。

线索二叉树利用了二叉树中部分空指针域的空间来存储指向前驱节点或后继节点的线索（thread），从而实现快速遍历和查找。在线索二叉树中，指针域原本用于指向左子节点和右子节点的空指针被利用起来，分别指向遍历中的前驱节点和后继节点。这样在进行遍历时，可以不必使用递归或栈来保存遍历路径，不用使用递归，而是用前驱和后继指针快速定位下一个访问的节点。

顺序存储二叉树：

• 顺序树中结点 i（顺序索引） 的左右孩子分别是 2i+1 和 2i+2 (i从0开始计数)

先中后序遍历二叉树，层序遍历。

可以通过 中序 + 先序 / 后序 / 层序 来还原二叉树结构。

4.1 哈夫曼树

哈夫曼树（Huffman Tree），也称为最优二叉树（Optimal Binary Tree），是一种特殊的二叉树，它是用于实现数据压缩算法中的一种重要数据结构。

哈夫曼树的特点是，权值较小的节点在树中的深度较大，权值较大的节点在树中的深度较小，这样可以使得权值较大的节点距离根节点较近，从而在编码时生成较短的编码，实现数据的高效压缩。

哈夫曼树的构建过程如下：

1. 给定一组权值，每个权值代表一种字符或数据。将每个权值看作是一个树种的一个节点。
2. 从这些节点中选择两个权值最小的节点作为左右子节点，构建一个新的父节点，并将父节点的权值设为左右子节点的权值之和。
3. 将构建的父节点作为新的节点，加入到剩余节点中。
4. 重复步骤2和步骤3，直到所有节点都合并为一个根节点为止，构建完成的二叉树即为哈夫曼树。

构建完成的哈夫曼树具有一个重要特性：权值较小的节点离根节点较远，权值较大的节点离根节点较近。

在数据压缩中，哈夫曼树常被用于生成哈夫曼编码（Huffman Coding）来实现数据的压缩和解压缩。哈夫曼编码是一种可变长度编码，将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示，从而节省了存储空间。

为什么只依靠 先序 + 后序 不可以还原二叉树的结构？因为中序遍历提供了左右子树如何划分的信息，而仅依靠先+后无法划分左右子树。

任何一颗二叉树的叶子结点在其先序/中序/后序遍历结果中的次序相同。

总分支数 = 总度数 = n - 1，总度数 = 10，故 n 为 11。

5. 图

一个无向图中，所有顶点的度数之和为边数量的2倍。

一个有向图中，所有顶点的出度之和等于所有顶点的入度之和。

普里姆算法：

克鲁斯卡尔算法：

拓扑排序（Topological Sort）是对有向无环图（DAG）进行排序的一种算法，它将图中的节点按照一种线性的顺序排列，使得对于图中的任意两个节点 u 和 v，如果存在一条从 u 到 v 的路径，那么 u 在排序中应该在 v 的前面。

拓扑排序的应用场景很多，比如任务调度、依赖关系分析、编译顺序等。在实现拓扑排序时，常用的方法是使用深度优先搜索（DFS）或广度优先搜索（BFS）实现。

拓扑排序的时间复杂度为 O(V + E)，其中 V 表示节点的个数，E 表示边的个数。

需要注意的是，拓扑排序只对有向无环图有效，即图中不能存在环。如果图中存在环，那么不可能找到一个满足条件的排序。

图的深度遍历类似于二叉树的先序遍历，广度遍历类似于层序遍历。

若图中每个顶点之间都没有边连接，那么每个顶点都是一个独立的连通分量，此时最多有n个连通分量。若图中每个顶点都与其他顶点都有边连接，那么整个图是一个强连通图，只有一个连通分量。

6. 串

串也是线性表。

字符串匹配：此时索引从 1 开始。

字符串的数据元素是单个字符。

match(a, b, c) // 子串 b 在主串 a 中出现第 c 的位置索引（从1开始）（没有c默认为第一次）。

KMP 算法提前扫描一趟模式串，计算了模式串各个位置的 next 值，其本质上是一个前后缀部分匹配长度表,其目的是能让匹配过程中遇到不匹配字符时,无需回溯，根据该位置的next 值直接移动子串，从而降低了时间复杂度。

字符串线性结构，支持多种存储结构，包括链式存储。

判断两个串是否相等的时间复杂度取决于长度小的串。O(n)(n为长度更小的串)。

长度为1的串（字符串）作为一种数据结构，支持CRUD，与字符串常量有这本质的区别。

7. 查找

二叉排序树=二叉查找树=二叉搜索树，他们的任何一个结点的所有子树都满足左小右大。

构造二叉查找树，第一步是令第一个元素为根。

平衡二叉树（Balanced Binary Tree），也称为AVL树，是一种特殊的二叉查找树，它的左右子树的高度差不超过1。

二叉查找树的中序遍历就是其所有元素的有序序列。

哈希表在理想情况下可以达到O(1)的查找时间复杂度。

二分查找前提：有序表。

8. 排序

8.1 插入排序和希尔排序

插入排序是稳定的，时间复杂度是O(n^2)，空间复杂度O(1)。

希尔排序的基本思想是通过定义一个增量序列，将待排序序列分割成多个子序列，对每个子序列进行插入排序。随着增量的减小，子序列的长度逐渐变小，当增量减小为1时，整个序列被分割成一个子序列，然后再进行最后一次插入排序，最终完成排序。

具体的希尔排序算法如下：

1. 选择一个增量序列，可以使用不同的增量序列，例如希尔增量（n / 2，n / 4，…，1）。
2. 对于每个增量，将待排序序列分割成若干个子序列，每个子序列的元素下标相差增量。
3. 对每个子序列进行插入排序，将子序列内的元素按照插入排序的方式进行排序。
4. 重复步骤2和步骤3，直到增量减小为1。
5. 最后，使用增量为1进行插入排序，完成整个序列的排序。

希尔排序的时间复杂度与增量序列的选择有关，最坏情况下的时间复杂度为 O(n^2)，但平均情况下的时间复杂度要比普通的插入排序低，可以达到 O(nlogn)。希尔排序的空间复杂度为 O(1)，是一种原地排序算法。

希尔排序在实践中具有较好的性能，尤其适用于中等大小的数据集。它相对简单易实现，且对于较小规模的数据集比其他复杂度为 O(nlogn) 的排序算法具有更好的性能。然而，希尔排序不具备稳定性，可能会打乱相等元素之间的相对顺序。

8.2 选择排序和堆排序

选择排序是不稳定的，因为元素之间会发生位置交换，时间复杂度是O(n^2)，空间复杂度O(1)。

堆排序（Heap Sort）是一种基于比较的排序算法，利用二叉堆这种数据结构来实现排序。堆排序的基本思想是先将待排序的序列构建成一个最大堆（或最小堆），然后依次将堆顶元素（最大值或最小值）与堆的最后一个元素交换，再重新调整堆，重复这个过程直到整个序列排序完成。

堆排序过程的详细步骤如下：

1. 将待排序的序列构建成一个最大堆（或最小堆）。如果要进行升序排序，则构建最大堆；如果要进行降序排序，则构建最小堆。构建堆的过程可以使用下面的操作：
   • 从序列的最后一个非叶子节点开始，依次向上调整每个节点，将当前节点与其子节点进行比较，如果当前节点小于（或大于）其子节点，则交换位置，以保持堆的性质。
   • 重复上述过程，直到根节点。
2. 将堆顶元素与堆的最后一个元素交换位置，这样最大（或最小）的元素就被放在了序列的最后。
3. 由于交换后，堆的性质被破坏，需要将堆进行调整，使其满足堆的性质。
4. 重复步骤2和步骤3，直到堆中只剩下一个元素，此时整个序列已经有序。

堆排序的时间复杂度为 O(nlogn)，其中 n 是序列的长度。堆排序是一种原地排序算法，即不需要额外的空间来存储待排序的数据，所以它的空间复杂度为 O(1)。

堆排序在实践中具有较好的性能，尤其适用于大规模数据集的排序。与其他常见的排序算法相比，堆排序相对复杂一些，需要对堆的构建与调整进行理解和操作。然而，堆排序具有稳定性，可以保留相等元素之间的相对顺序。

冒泡排序是稳定的，因为相邻元素相等不会发生交换，时间复杂度是O(n^2)，空间复杂度O(1)。冒泡排序在初始序列比较有序的情况下，效率较高，如果初始序列是倒序的，效率很低。

2路-归并排序，稳定，时间复杂度O(n*lgn)，空间复杂度O(n)。

8.3 快速排序

快速排序（Quick Sort）是一种常用的基于比较的排序算法，它通过将一个数组分成较小和较大的两个子数组，递归地对子数组进行排序，从而完成整个数组的排序。

快速排序的基本思想是选择一个基准元素（pivot），并将数组中小于基准元素的元素放在它的左边，将大于基准元素的元素放在它的右边，然后对左右两个子数组再进行递归排序。

具体的快速排序算法如下：

1. 选择一个基准元素（pivot），通常选择数组的第一个元素或者随机选择一个元素。
2. 将数组分割成两个子数组，使得左边的子数组中的元素都小于等于基准元素，右边的子数组中的元素都大于基准元素。这一步通常使用两个指针从两端往中间扫描，当左指针指向元素大于等于基准元素时，停止；当右指针指向元素小于等于基准元素时，停止，然后交换左右指针所指向的元素。
3. 递归地对左右两个子数组进行快速排序。
4. 重复步骤2和步骤3，直到子数组的大小为1或者为空，即完成排序。

快速排序的时间复杂度为 O(nlogn)，其中 n 是数组的长度。在最坏情况下，快速排序的时间复杂度为 O(n^2)，但平均情况下的时间复杂度很接近 O(nlogn)。快速排序是一种原地排序算法，空间复杂度为 O(logn)。

快速排序在实践中具有较好的性能，并且很常见。它具有较高的效率和速度，并且相较于其他排序算法，快速排序的实现相对简单。然而，快速排序不具备稳定性，可能会打乱相等元素之间的相对顺序。在处理大规模数据集时，快速排序通常是一个不错的选择。

8.4 基数排序

基数排序，稳定。

如果一颗完全二叉树上每一个结点都比其左右孩子大，称之为大顶堆；反之。

8.5 堆排序