​

# Review

# 前言

一到五是一个复习的状态，着重介绍考点，重点记忆，难点剖析，六七是是笔记，有点乱。

# 一。绪论

# 1.1 数据结构基本术语（期中已考）

# 1.2 数据结构的两个层次和运算

# 1. 逻辑结构（唯一）

线性结构（一对一）：顺序表、栈、队列、表...

非线性结构（一对多，多对一）：图、树、堆...

另外可以像集合、线性结构、树状结构、图结构区分。

经典：有序表可以代表逻辑结构

# 2. 存储结构（不唯一）

1. 顺序存储

2. 链式存储

# 3. 数据的运算

逻辑结构和存储结构都相同，但运算不同，则数据结构不同。例如，栈与队列。

插入、删除、修改、查找、排序

逻辑结构：有序表（线性结构）（一对一，多对一，）

# 1.3 抽象数据类型（ADTs）

# 1.4 算法与算法分析

# 1. 基本特性

事后统计、事前分析估计来看时间效率

# 2. 时间复杂度

时间复杂度是由嵌套最深层语句的频度决定的

# 二。线性表

补充知识：

C 语言开空间：malloc (m),sizeof (x)[数组常用],free (p) 释放节点

1

L.elem=（ElemType*）malloc(MAXSIZE * sizeof(ElemType));

# 2.1 顺序表（随机存取）

# 2.2 链表（顺序存取）

# 敲黑板：头节点的作用

# 1. 单链表（线性链表）

# i. 插入

因为大部分比较容易理解，这里写一下插入和删除

辅助节点 S：先让 S 指向 P 的下一个（防止数据丢失）；再让 P 指向 S；

# ii. 删除（注意内存消除）

** 删除和插入时间复杂度不是 1！！！** 原因是你要找到那个位置，但是线性表也是受到移动元素才是 n

# iii. 生成

# 1. 前插法：（永远插在首元节点前面一个）

# 2. 尾插法：（永远插尾巴后面）

# 2. 循环链表

空表：L->next = L;

# i. 开始和结束

# ii. 合并

A 的尾巴指向 B 的首元节点，B 的尾巴指向 A 的头节点。结束、

# 3. 双链表 (重点)

# i. 插入（防止数据丢失）

1. 记住前面

2. 记住后面

3. 改前面的下一个为 s（必须在记住后面后）

4. 改后面的上一个为 s（必须在记住前面后）

# ii. 删除（注意释放内存）

p 记住要删除的 b，然后记得 free，然后改前面为后面，后面为前面

# 2.3 比较链表和顺序表（重要）

# 2.4 可能考的案例（结合后期做卷子补充）

# 1. 稀疏多项式加法（链式）

# 2.

# 三。栈和队列

# 3.1 栈的定义和注意点

# 1. 定义

# 2. 特点

后进先出

当 s.base=s.top 时，栈空

插入：top 指针指向真正栈顶的下一个位置

# 3. 链栈（会考）

栈的运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针

栈底在单链表尾部，采取前插法。

前插部分代码：

出栈注意拿一个空指针指向栈顶节点，然后要 delete

# 3.2 递归

汉诺塔、多项式、斐波那契数列、树的前序中序后序遍历、图的广度优先遍历等等：一次递归

汉诺塔代码：

1
2
3
4
5
6

void Hanoi(int n,char A,char B,char C)
{ if(n==1) move(A,1,C);
  else
  {Hanoi(n-1,A,C,B); 
   move(A,n,C);
   Hanoi(n-1,B,A,C);  }}

# 分治法思想：

对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解

# 算法分析（要考概念）：

# 练习题目 1：

# 练习题目 2：

# 3.3 队列

# 1. 定义

# 2. 特点

先进先出

# 3. 循环队列（重点）

# 练习题目 3：

4、假设以数组 seqn［m］存放循环队列的元素，设变量 rear 和 quelen 分别指示循环队列中队尾元素的位置和元素的个数。

(1) 写出队满的条件表达式；

(2) 写出队空的条件表达式；

(3) 设 m=40,rear=13,quelen=19, 求队头元素的位置；

(4) 写出一般情况下队头元素位置的表达式。

1. 入队： rear = (rear + 1) % m
2. 出队： front = (front + 1) % m
3. 队空： front = rear
4. 队满： front = (rear + 1) % m
5. 当前队列中的元素数目： n = (rear - front + m) % m

# 4. 链队列

# 四。串、数组和广义表

补充知识点：

0. 串的存储方法可以是顺序表或者链表

# 4.1 串的模式匹配算法

# 1.BF 算法

暴力搜索，两个指针回溯，，一个主串的 i-j+2, 模式串直接将 j 置为 1。

# 算法评价：

# 2.KMP 算法（对模式串本身提前计算）（重要死了）

# 设计思想：

主串的指针一直正常往下走为 O（m），让模式串的指针回溯有一定 “头脑”（让部分已经匹配上的我就不管它了，从下一个开始匹配）滑动尽可能大的距离

# 解析：

其中已知 1：模式串的 p1p2...pk-1 与主串的 si-k+1si-k+2...si-1 匹配上了

2：在字符匹配的时候，模式串那部分也和主串的 si-k+2... 匹配，

3：由 1，2，那么模式串内部存在相同字符串，

# 代码：与 BF 很像，只是指针回溯，用到了 next 数组且主串没有回溯

# Next 数组：

内部最大匹配字符串的前后缀

首先把自己看成主串，也看成模式串，自己匹配自己，看扫过去的最大匹配长度就是 next 数组的值

解析：以当前为一个点，（不包括自己），去看前面那个串的最长前后缀长度 l, 然后回溯的位置就是 l+1

1
2
3
4
5
6
7

a默认为0；
b前有0个匹配：1    
c前有0个匹配：1
a前有0个匹配：1
a前有1个匹配：2
...
15：d前有6个匹配：7

# 4.2 数组

二维数组（计算题），按行序，还是列序。

三维数组

# 练习题目 4

# 1. 特殊矩阵的压缩存储（需要了解）

# 1）对称矩阵

# 2）三角矩阵

# 3）带状矩阵（对角矩阵）

就是主对角线成条状分布元素

# 2. 稀疏矩阵的存储方法（考）

# 1）三元组顺序表（[i,j] 下标，m 值）

# 快速矩阵转置

如果直接交换行列值，会出现错乱：就是行大的比行小的先出现

1. 首先确定每一列的第一个非零元素在三元组的位置

2. 第一列第一个非 0 元素肯定存放在第一个位置，第二列第一个非 0 元素的位置 = 第一列存放的起始位置 + 第一列的非 0 元素个数，以此类推。

就是 Cpot 是现在想返回的下标，然后 num 是这一列有元素的个数。

# 伪代码（看）：

# 行逻辑链接顺序表 - 矩阵乘法

# 2) 十字链表

# 4.3 广义表（重点）

# 1. 定义

几点注意：

# 2. 主要操作

# 练习题目 5：

# 五。树和二叉树

# 六。图

# 6.1 图的基本术语

# 1. 图的基本区分

** 无向图：任意两个节点之间的 “边”** 没有方向，可以用（a，b）表示

** 无向图：** 任意两个节点之间的 “弧” 都有方向，可以用 <a,b> 表示，表示 a 到 b 的弧

# 2. 图的基本概念

学习图的算法前，这之前先学习图的几种存储方式

# 6.2. 图的存储方式

# 1. 邻接矩阵

# 2. 邻接表

# 七。查找

数据结构：查找 (Search)【详解】_index.search 返回什么结构_UniqueUnit 的博客 - CSDN 博客

# 7.1 查找的基本概念

​ Pi 查找第 i 个元素的概率（1/n） Ci 是查第 i 个元素要的时间

# 7.2 线性表的查找

# 1. 顺序查找

# 2. 折半查找（重点！！！）

折半查找 (Binary Search) 也称二分查找，它是一种效率较高的查找方法。

# 2.1 查找算法

1
2
3
4
5
6
7
8
9
10

int Search_Bin (SSTable ST, keyType key, int low, int high)
{
	if (low>high) return 0; //查找不到时返回0
	mid = (low + high)/2;
	if (key==ST.elem[mid].key) return mid;
	else if (key<=ST.elem[mid].key)
	return Search_Bin(ST, key, low, mid - 1); //递归
	else
	return Search_Bin(ST, key, mid + 1, high);
}

# 2.2 性能分析（判定树（要考））

# 3. 分块查找

# 7.3 树表的查找

# 1. 前言

・折半查找效率较高，但要求表中记录按关键字有序排列，且不能用链表做存储结构。
・当表的插入或删除操作频繁时，为维护表的有序性， 需要移动表中很多记录。
・线性表的查找更适用于静态查找表 (查找的同时对查找表不做修改操作)。
・对动态查找表进行高效率的查找，可采用几种特殊的二叉树作为查找表的组织形式，在此将它们统称为树表。

# 2. 二叉排序树

中序遍历后从小到大排序，右子树群永远大于 根，左子树群永远小于 根

# 2.1 查找思想

若查找的关键字等于根结点， 成功
否则：
若小于根结点，查其左子树
若大于根结点，查其右子树
在左右子树上的操作类似

代码：

# 二叉排序树比较折半查找

二叉排序树上的查找和折半查找相差不大！
・二叉排序树的平均查找长度仍然和 log2n 是同数量级的。
・但就维护表的有序性而言，二叉排序树更加有效，因为无需
移动记录，只需修改指针即可完成对结点的插入和删除操作
・对于需要经常进行插入、删除和查找运算的表（动态查找表）， 采用二叉排序树比较好！

# 2.2 插入思想

若二叉排序树为空，则插入结点应为根结点； 否则，继续在其左、右子树上查找。
树中已有， 不再插入
树中没有， 查找直至某个叶子结点的左子树或右子树为空为止， 则插入结点应为该叶子结点的左孩子或右孩子

二叉排序树插入的基本过程是查找时间复杂度同查找一样，是 O (log2n）

代码：

# 2.3 由空树生成二叉排序树

查找 + 插入；另外，插入次序不一样，那么生成的树也不一样。

# 2.4 删除思想（会考）

就是要保证删除前后排序仍然在，主要可以考虑中序遍历之后的数组，用被删除的后元素来补上来。

・删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。
・被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。
・被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。
・被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点 (关键码最小), 用它的值填补到被删结点中，再来处理这个结点的删除问题。

# 3. 平衡二叉树 AVL（重点！！！）

本身是二叉排序树

平衡因子：该结点左子树与右子树的高度差

任一结点的平衡因子只能取： -1、 0 或 1；如果树中任意一个结点的平衡因子的绝对值大于 1，则这棵二叉树就失去平衡， 不再是 AVL 树；

对于一棵有 n 个结点的 AVL 树，其高度保持在 O (log2n) 数量级， ASL 也保持在 O (log2n) 量级 ！！！

# 3.1 插入（常考）

当向一棵 AVL 树中插入一个新的结点，有可能会破坏树的平衡，这时就需要调整这棵树，根据不同的插入位置，一共有四种调整方法，在调整的过程中要注意，一定要满足二叉搜索树的性质。

注意：发现者是第一个不满足这棵树是平衡二叉树的结点，如果有多个结点同时不满足，就选最靠近下面的那个结点作为发现者

1. 插入结点在发现者右子树的右边 RR----> 右单旋 中为支，高右旋 发现者 - 1 -----> -2

2. 插入结点在发现者左子树的左边 LL----> 左单旋 中为支，高左旋 发现者 - 1 -----> -2

3. 插入结点在发现者左子树的右边 LR----> 左右双旋 下二整体先左转，然后和 LL 一样

4. 插入结点在发现者右子树的左边 RL----> 右左双旋 下二整体先右转，然后和 RR 一样

# 3.2 拓展：红黑树

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于 1978 年发明，在当时被称为平衡二叉 B 树 (symmetric binary B-trees)。后来，在 1978 年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O (logN) 时间内完成查找、增加、删除等操作。

.........

学习链接：https://blog.csdn.net/cy973071263/article/details/122543826

# 7.4 哈希查找

・线性表和树表的查找以关键字比较为基础，查找过程考虑关键字之间的相对大小，记录在存储结构中的位置与关键字无直接关系，查找时间与表长（元素 / 节点个数）有关。

・在元素的存储位置和关键字本身建立联系，查找时就无需比较或较少比较 ------> 哈希查找

・这就是散列查找法的思想：通过对元素的关键字值进行某种运算， 直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较。

・散列查找法又叫杂凑法或散列法。

# 1. 基本思想

基本思想： 记录的存储位置与关键字之间存在对应关系， Loc (i)=H (key-i)-----> 哈希函数

用关键字和存储建立联系，查找效率与元素 n 无关

# 2. 哈希函数的构造

# 2.1 直接定址法

# 2.2 除留余数法（重要！！！）

# 2.3 构造时考虑

# 3. 哈希表查找冲突处理方法

冲突是指，比如，22 模 11 等于 0，11 也是，但 11 和 22 要存在另一个地方。

# 3.1 开放地址法（开地址）

基本思想： 有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。

Hi =(Hash(key)+di) mod m (1≤ i < m)

1）线性探测法 di = 1、2、3......

2）二次探测法 di = 1,-1、4,-4、9,-9......

3）伪随机探测法 di = x.....

2) 和 3）可以避免二次聚集，但找不到完美的

# 3.2 链地址法（考）

有点像简化剩余系，给每一个定一个妈妈，妈妈下面去放崽崽

# 4. 哈希查找的效率（背）

# 7.5 总结

# 八。排序

【数据结构】八大排序 (超详解 + 附动图 + 源码)_文件记录排序 - CSDN 博客

# 8.1 概述

使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

内部排序 和 外部排序：

** 内部排序：** 数据元素全部放在内存中的排序。
** 外部排序：** 数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

这部分主要是内部排序。

# 8.2 插入排序（边查找边插入）

查找（确定插入位置（查几次））-> 移动元素（涉及移动多少次）--> 插入 😭😭😭😭😭😭😭😭😭插个眼：12 月 4 日李老师宣布 21 号机考，还有期末，呜呜

# 1. 直接插入排序

# （1）哨兵的作用（）：（要考）

i>i-1 时，不做操作

i<i-1 时，代表一定会移动元素，交换值时，防止 i 处的值丢失（被覆盖），设置哨兵可以避免

# （2）插入步骤：

# （3）算法效率分析（看看🙌）

注意一些细节，第 i 躺比较 i 次，因为还有哨兵。

# 2. 折半插入排序（考）

一些细节了，每次插入，用那个查找的思想，然后当 low>high 时，就 break，此时的 high 就是它的下标，返回 high。

（1）考虑值可以比较大小

（2）考虑值相等的插入

# （1）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/*
直接插入排序算法，使用折半查找确定待插入元素的位置，并进行相应的后移操作。最后将待插入元素插入到正确的位置上。
*/
void BInsertSort(SqList &L) {
    for (int i = 2; i <= L.length; ++i) {
        L.r[0] = L.r[i]; // 待插入记录暂存监视哨
        int low = 1, high = i - 1; // 置查找区间处置
        while (low <= high) { // 在r[low..high]中折半查找插入的位置
            int m = (low + high) / 2; // 折半
            if (L.r[0].key < L.r[m].key)
                high = m - 1; // 插入点在前一子表
            else
                low = m + 1; // 插入点在后一子表
        }
        for (int j = i - 1; j >= high + 1; --j)
            L.r[j + 1] = L.r[j]; // 记录后移
        L.r[high + 1] = L.r[0]; // r[0]插入到正确位置
    }
}

# （2）算法效率分析（重要）

# 3. 希尔插入（生疏）

其实就是一个合并的思想，几个连在一起，视为同一个元素。

# （1）算法思想

# （2）算法实现

# （3）算法特点（要考）

# 8.3 交换排序（考点）

# 1. 冒泡排序 (n2)

这个我们大一就会嘞，反正暴力循环，每次换前后两个，比较大小来做，这个是我们都会的，上机考试的排序推荐这个。

# 2. 快速排序（nlog2n）（递归实现）

# （1）排序思想

有点像推箱子游戏。

# （2）排序过程（理解）

重点是想清楚两个指针的运作模式和控制权的交接。 从两头向中间交替逼近！

第一种情况：高地址 -> 值 > 枢轴 只执行 high--

第二种情况：高地址 -> 值 < 枢轴 将 high 的值交给 low（low 此时是个空的）, 并将控制权给 low

模式图： 轴心 ----low........high

其实想一下还是比较好理解的。

（我去，还可以插入动图，新功能！！！）

这里就第一趟结束了，但还没有完全排序，需要继续排，有好几趟。

总之每一趟可以区分两个左右表，轴心处的值一定不会变了。

# （3）源代码与算法评价

# 算法评价（不稳定）：

# 代码：

1

# 8.4 选择排序

# 1. 简单选择排序

有点类似于冒泡，算法比较笨拙，在下一次比较中不考虑上一次的比较结果，仍然去继续比较。

# 2. 树型选择排序（锦标赛）（了解）

第一次比较，会经过 n-1 次比较找到较小值

​

# 3. 堆排序（重点 nlog2n）

堆排序原理及其实现 (C++)_堆排序 c++-CSDN 博客

# （1）什么是堆（还原完全二叉树）

补充：

完全二叉树：若设二叉树的深度为 h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。

# （2）堆排序

两步：建立堆 -----> 输出极值

# 1）无序序列建成堆

# 2）堆的重新调整

# （3）代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

void adjust(int arr[], int len, int index)
{
    int left = 2*index + 1;
    int right = 2*index + 2;
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;  // maxIdx是3个数中最大数的下标
    if(maxIdx != index)                 // 如果maxIdx的值有更新
    {
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);       // 递归调整其他不满足堆性质的部分
    }

}
void heapSort(int arr[], int size)
{
    for(int i=size/2 - 1; i >= 0; i--)  // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
    {
        adjust(arr, size, i);
    }
    for(int i = size - 1; i >= 1; i--)
    {
        swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
        adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
    }
}

int main()
{
    int array[8] = {8, 1, 14, 3, 21, 5, 7, 10};
    heapSort(array, 8);
    for(auto it: array)
    {
        cout<<it<<endl;
    }
    return 0;
}

# （4）算法分析

# 8.5 归并排序（2 & 有序 > 1 & 有序）

外部排序的重要基础，有多路排序

已知，A，B，合成 C

固定两个指针在 A，B，谁小谁插入 C，然后下移，直到 A，B 都空

# 8.6 基数排序

前面的排序方法主要通过关键字值之间的比较和移动而基数排序不需要关键字之间的比较。

# 1. 多关键字排序

# （1）最高位优先

# （2）最低位优先

# 2. 链式基数排序（O (d (n+rd)),O (n+rd) 稳定）

用链表作存储结构的基数排序

# （1）算法思想

打牌思想，先按花色优先，然后再同花色里面排，再给花色排个序，最后连在一起

# （2）算法步骤

# （3）代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

#include <iostream>
#include <cmath>
using namespace std;
typedef int KeyType;
const int END = -1;
const int Radix = 10;

typedef struct Node
{
	KeyType key;
	struct Node *next;
};

Node *CreateList()
{
	KeyType x;
	Node *q = nullptr;
	cin >> x;
	while (x != END)
	{
		Node *p = new Node;
		p->key = x;
		p->next = q;
		q = p;
		cin >> x;
	}
	return q;
}

int FindDigits(Node *p)
{
	int max = -1;
	while (p)
	{
		if (p->key > max) max = p->key;
		p = p->next;
	}

	int digits = 1;
	while (max / 10 > 0)
	{
		digits++;
		max = max / 10;
	}
	return digits;
}


void Distribute(Node *&p,int digits, Node *f[], Node *r[])
{
	Node *q;
	while (p)
	{
		q = p;
		p = p->next;
		int k = q->key;
		int radix = static_cast<int>(k / pow(10, digits - 1)) % 10;
		if (r[radix] == nullptr)
		{
			r[radix] = q;
			f[radix] = q;
			r[radix]->next = nullptr;
		}
		else
		{
			q->next = r[radix]->next;
			r[radix]->next = q;
			r[radix] = q;
		}
	}
}

void Collect(Node *&p, Node *f[], Node *r[])
{
	p = nullptr;
	for (int i = Radix - 1; i >= 0; i--)
	{
		if (f[i] != nullptr)
		{
			r[i]->next = p;
			p = f[i];
			r[i] = nullptr;//不要忘记这两步!!!
			f[i] = nullptr;
		}
	}
}

void RadixSort(Node *&p)
{
	Node *f[Radix], *r[Radix];
	for (int i = 0; i < Radix; i++)
	{
		f[i] = nullptr;
		r[i] = nullptr;
	}
	int digits = FindDigits(p);
	for (int i = 1; i <= digits; i++)
	{
		Distribute(p, i, f, r);
		Collect(p, f, r);
	}
}

void PrintElem(Node *p)
{
	while (p)
	{
		cout << p->key << " ";
		p = p->next;
	}
	cout << endl;
}

int main()
{
	Node *p;
	p = CreateList();
	PrintElem(p);
	cout << FindDigits(p) << endl;
	RadixSort(p);
	PrintElem(p);
	return 0;
}

# （4）算法分析

# 8.7 外部排序

# 1. 外部排序基本方法

其实就是给了一个内存处理限制，就是本地最多同时跑 n 个记录，但有 10n 个元素要排序，这个意思，然后就会采用先分成 10 个归并段（存在外存）

对 10 个两两进行归并排序，得到 5 个归并段（大小为 2n），以此类推，最后得到一个归并段（10n）

# 2. 多路平衡归并的实现

# （1）性质

# 3. 最佳归并树

目的：减少读存次数

# 8.8 总结

# 1. 各类排序的比较

# 2. 各类排序的选择