【王道考研】王道数据结构与算法详细笔记（全）

第一章数据结构绪论

1.1 数据结构的基本概念

1.2 数据结构的三要素

1.2.1. 数据的逻辑结构

1.2.2. 数据的存储结构（物理结构）

1.2.3. 数据的运算

1.2.4. 数据类型和抽线数据类型

1.3 算法的基本概念

1.4 算法的时间复杂度

1.5 算法的空间复杂度

第二章线性表

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

2.1.2 线性表的基础操作

2.2 顺序表

2.2.1 顺序表的概念

2.2.2. 顺序表的实现编辑

2.2.3 顺序表的基本操作

2.3 线性表的链式表示

2.3.1. 单链表的基本概念

2.3.2. 单链表的实现

2.3.3. 单链表的插入

2.3.4. 单链表的删除

2.3.5. 单链表的查找

2.3.6. 单链表的建立

2.3.7. 双链表

2.3.8. 循环链表

2.3.9. 静态链表

2.3.10. 顺序表和链表的比较

第三章栈和队列

3.1. 栈

3.1.1. 栈的基本概念

3.1.2. 栈的基本操作

3.1.3. 栈的顺序存储实现

3.1.4. 栈的链式存储

3.2. 队列

3.2.1. 队列的基本概念

3.2.2. 队列的基本操作

3.2.3. 队列的顺序存储实现

3.2.4. 队列的链式存储实现

3.2.5. 双端队列

3.3. 栈与队列的应用

3.3.1 栈在括号匹配中的应用

3.3.2. 栈在表达式求值中的应用

3.3.3. 栈在递归中的应用

3.3.4. 队列的应用

3.4. 特殊矩阵的压缩存储

3.4.1 数组的存储

3.4.2 对称矩阵的压缩存储

3.4.3 三角矩阵的压缩存储

3.4.4 三对角矩阵的压缩存储

3.4.5 稀疏矩阵的压缩存储

第四章串

4.1. 串的基本概念

4.2. 串的基本操作

4.3. 串的存储实现

4.3.1 静态数组实现

4.3.2 基本操作的实现

4.4. 串的朴素模式匹配

4.5. KPM算法

第五章图

5.1. 树的概念

5.1.1. 树的基本定义

5.1.2. 树的常考性质

5.2. 二叉树

5.2.1. 二叉树的定义

5.2.2. 特殊二叉树

5.2.3. 二叉树的性质

5.2.4. 二叉树存储实现

5.3. 二叉树的遍历和线索二叉树

5.3.1. 二叉树的先中后序遍历

5.3.2. 二叉树的层序遍历

5.3.3. 由遍历序列构造二叉树

5.3.4. 线索二叉树的概念

5.3.5. 二叉树的线索化

5.3.6. 在线索二叉树中找前驱/后继

5.4. 树和森林

5.4.1. 树的存储结构

5.4.2. 树和森林的遍历

5.5. 应用

5.5.1. 二叉排序树

5.5.2. 平衡二叉树

5.5.3. 哈夫曼树

第六章图

6.1. 图的基本概念

6.2. 图的存储

6.2.1. 邻接矩阵

6.2.2. 邻接表

6.2.3. 十字链表、临接多重表

6.2.4. 图的基本操作

6.3. 图的遍历

6.3.1. 广度优先遍历

6.3.2. 深度优先遍历

6.4. 图的应用

6.4.1. 最小生成树

6.4.2. 无权图的单源最短路径问题——BFS算法

6.4.3. 单源最短路径问题——Dijkstra算法

6.4.4. 各顶点间的最短路径问题——Floyd算法

6.4.5. 有向⽆环图描述表达式

6.4.6. 拓扑排序

6.4.7. 关键路径

第七章查找

7.1 查找概念

7.2 顺序查找

7.3 折半查找

7.4 分块查找

7.5 红黑树

7.5.1 为什么要发明红黑树？

7.5.2 红黑树的定义

7.5.3 红黑树的插入

7.6 B树和B+树

7.6.1 B树

7.6.2 B树的基本操作

7.6.3 B+树

7.6.4 B树和B+树的比较

7.7 散列查找及其性能分析

7.7.1 散列表的基本概念

7.7.2 散列查找及性能分析

第八章排序

8.1. 排序的基本概念

8.2. 插入排序

8.2.1. 直接插入排序

8.2.2. 折半插入排序

8.2.3. 希尔排序

8.3. 交换排序

8.3.1. 冒泡排序

8.3.2. 快速排序

8.4. 选择排序

8.4.1. 简单选择排序

8.4.2. 堆排序

8.5. 归并排序

8.6. 基数排序

8.7. 内部排序算法总结

8.7.1. 内部排序算法比较

8.7.2. 内部排序算法的应用

8.8. 外部排序

8.8.1. 外部排序的基本概念和方法

8.8.2. 败者树

8.8.3. 置换-选择排序（生成初始归并段）

8.8.4. 最佳归并树

第一章数据结构绪论

1.1 数据结构的基本概念数据：数据是信息的载体，符号的集合、所有能输入到计算机中并能被计算机程序处理的符号的集合，数据是计算机程序加工的原料。数据元素：数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。数据项：构成数据元素的不可分割的最小单位。数据对象：数据对象是具有相同性值的数据元素的集合，是数据的一个子集。数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

举例需要理解几点:

学校里的好多类型的表：数据单独的一张成绩单表：数据对象成绩单中每一行有姓名、课程、班级、成绩：数据元素成绩单中每一行的每一个表格姓名等都是一个个的数据项 1.2 数据结构的三要素 1.2.1. 数据的逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。

逻辑结构包括：

集合结构：结构中的数据元素之间除“同属一个集合”外，别无其它关系（例如：一群羊）。线性结构：结构中的数据元素之间只存在一对一的关系，除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继（例如：排队取号）。树形结构：结构中数据元素之间存在一对多的关系（例如：思维导图）。图状结构：数据元素之间是多对多的关系（例如：道路信息）。 1.2.2. 数据的存储结构（物理结构）

如何用计算机表示数据元素的逻关系?存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。

存储结构包括：

顺序存储：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。索引存储：在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。

需要理解几点:

若采用顺序存储，则各个数据元素在物理上必须是连续的;若采用非顺序存储，则各个数据元素在物理上可以是离散的。数据的存储结构会影响存储空间分配的方便程度。数据的存储结构会影响对数据运算的速度 1.2.3. 数据的运算数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构指出运算的功能。运算的实现是针对存储结构的，指出运算的具体操作步骤。

针对于某种逻辑结构，结合实际需求，定义基本运算。例如:逻辑结构->线性结构

基本运算:1.查找第i个数据元素2.在第i个位置插入新的数据元素3.删除第i个位置的数据元素...... 1.2.4. 数据类型和抽线数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。例如：定义int整形，我们就可以把他们加减乘除等操作。

原子类型。其值不可再分的数据类型。如bool 和int 类型。结构类型。其值可以再分解为若干成分（分量）的数据类型（例如：结构体）。

抽象数据类型（Abstract Data Type，ADT）是抽象数据组织及与之相关的操作。ADT 用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关。

在探讨一种数据结构时理解几点:

定义逻辑结构(数据元素之间的关系)定义数据的运算(针对现实需求应该对这种逻辑结构进行什么样的运算)确定某种存储结构，实现数据结构，并实现一些对数据结构的基本运算 1.3 算法的基本概念

程序 = 数据结构+算法数据结构：如何用数据正确地描述现实世界的问题，并存入计算机。算法：如何高效地处理这些数据，以解决实际问题

算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。算法的特性：

有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。确定性：算法中每条指令必须有确定的含义，对于相同的输入只能得到相同的输出。可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。输出：一个算法有一个多个输出，这些输出是与输入有着某种特定关系的量。

我们可以类比：y = f（x）函数，其中x就是输出，y就是输出，这个函数就是算法。

好的算法达到的目标：

正确性：算法应能够正确的求解问题。可读性：算法应具有良好的可读性，以帮助人们理解。健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名奇妙地输出结果。效率与低存储量需求：花的时间少即：时间复杂度低。不费内存即：空间复杂度低。 1.4 算法的时间复杂度

顺序执行的代码只会影响常数项，可以忽略。只需挑循环中的一个基本操作分析它的执行次数与 n 的关系即可。如果有多层嵌套循环只需关注最深层循环循环了几次。事前预估算法时间开销T(n)与问题规模 n 的关系 (T 表示“time“）

$O\left(1 \right )O(\log_{2}n)O(n)O(n\log_{2}n)O(n^{2})O(n^{3})O(2^{n})O(n!)O(n^{n})$

1.5 算法的空间复杂度指算法消耗的存储空间(即算法除本身所需存储外的辅助空间)算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。记为S(n)=O(g(n))

第二章线性表 2.1 线性表的定义和基本操作

2.1.1 线性表的定义线性表是具有相同数据类型的n(n>0)个数据元素的有限序列。 (其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为)

$\large L=(a_{1},a_{2},...,a_{i},a_{1i+1},a_{n},)$

特点： 1. 存在惟一的第一个元素。 2. 存在惟一的最后一个元素。 3. 除第一个元素之外，每个元素均只有一个直接前驱。 4. 除最后一个元素之外，每个元素均只有一个直接后继几个概念: 1. $a_{i}$ 是线性表中的“第i个”元素线性表中的位序。 2. $a_{1}$ 是表头元素; $a_{n}$ 是表尾元素。 3. 除第一个元素外，每个元素有且仅有一个直接前驱:除最后一个元素外，每个元素有且仅有一个直接后继。存储结构： 1. 顺序存储结构：顺序表 2. 链式存储结构：链表 2.1.2 线性表的基础操作 InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。ListInsert(&L;i,e)：插入操作。在表L中的第i个位置上插入指定元素e。 ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

什么时候要传入参数的引用“&“-- 对参数的修改结果需要“带回来”看下面举例：

首先是传值调用： #includevoid test(int x) //形参是实参的临时拷贝{x = 1024;printf("test函数内部 x=%d\n",x);}int main(){int x = 1;printf("调用test前 x=%d\n",x);test(x);//这里的x改变了并没有传回来printf("调用test后 x=%d\n",x);return 0;}//输出为：//调用test前 x=1//test函数内部 x=1024//调用test后 x=1//请按任意键继续. . . 然后再看传址调用 #includevoid test(int &x) //把x的地址传到函数{x = 1024;printf("test函数内部 x=%d\n",x);}int main(){int x = 1;printf("调用test前 x=%d\n",x);test(x);//这里的x通过函数传回来值改变了printf("调用test后 x=%d\n",x);return 0;}//输出为：//调用test前 x=1//test函数内部 x=1024//调用test后 x=1024//请按任意键继续. . . 2.2 顺序表

我们看完线性表的逻辑结构和基本运算，现在继续学习物理结构：顺序表

2.2.1 顺序表的概念顺序表：用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。顺序表的特点： 1. 随机访问，即可以在 $O(1)$ 时间内找到第 i 个元素。 2. 存储密度高，每个节点只存储数据元素。 3. 拓展容量不方便（即使使用动态分配的方式实现，拓展长度的时间复杂度也比较高，因为需要把数据复制到新的区域）。 5. 插入删除操作不方便，需移动大量元素： $O(n)$ 。

2.2.2. 顺序表的实现

顺序表的静态分配顺序表的表长刚开始确定后就无法更改(存储空间是静态的) //顺序表的实现--静态分配#include#define MaxSize 10 //定义表的最大长度 typedef struct{int data[MaxSize]; //用静态的"数组"存放数据元素int length; //顺序表的当前长度 }SqList;//顺序表的类型定义（静态分配方式） void InitList(SqList &L){ for(int i=0;i L.length) // 判断i的范围是否有效return false;e = L.data[i-1]; // 将被删除的元素赋值给e for (int j = i; j < L.length; j++) //将第i个位置后的元素前移 L.data[j-1] = L.data[j];L.length--;return true; }int main() {SqList L;InitList(L);int e = -1;if (ListDelete(L, 3, e))printf("已删除第3个元素，删除元素值为%d\n", e);elseprintf("位序i不合法，删除失败\n"); return 0; }顺序表的查找

顺序表的按位查找 GetElem(L,):按位查找操作。获取表L中第i个位置的元素的值平均时间复杂度 $O(1)$ // 静态分配的按位查找#define MaxSize 10typedef struct {ElemType data[MaxSize]; int length;}SqList;ElemType GetElem(SqList L, int i) {return L.data[i-1];} // 动态分配的按位查找#define InitSize 10typedef struct {ElemType *data;int MaxSize;int length;}SeqList;ElemType GetElem(SeqList L, int i) {return L.data[i-1];} 顺序表的按值查找 LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素平均时间复杂度 = $O(n)$ #define InitSize 10 //定义最大长度 typedef struct{ElemTyp *data;//用静态的“数组”存放数据元素 int Length; //顺序表的当前长度}SqList;//在顺序表L中查找第一个元素值等于e的元素，并返回其位序int LocateElem(SqList L, ElemType e){for(int i=0; i next = NULL;//头结点之后暂时还没有结点return true;}void test(){LinkList L; //

云奕文章网

【王道考研】王道数据结构与算法详细笔记（全）

相关推荐：