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

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

创始人

2024-11-11 17:34:04

第一章数据结构绪论

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。

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

首先是传值调用：

#include void 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 //请按任意键继续. . .

然后再看传址调用

#include void 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

 顺序表的动态分配
 //顺序表的实现——动态分配 #include #include  //malloc、free函数的头文件  #define InitSize 10 //默认的初始值  typedef struct{ 	int  *data;    //指示动态分配数组的指针 	int MaxSize;   //顺序表的最大容量 	int length;    //顺序表的当前长度  }SeqList;   void InitList(SeqList &L){                 //初始化 	//用malloc 函数申请一片连续的存储空间 	L.data =(int*)malloc(InitSize*sizeof(int)) ; 	L.length=0; 	L.MaxSize=InitSize; }   void IncreaseSize(SeqList &L,int len){  //增加动态数组的长度 	int *p=L.data; 	L.data=(int*)malloc((L.MaxSize+len)*sizeof(int)); 	for(int i=0;i
 2.2.3 顺序表的基本操作
顺序表的插入操作
 ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
 平均时间复杂度 = 
 #define MaxSize 10    //定义最大长度 typedef struct{ 	int data[MaxSize];  //用静态的数组存放数据 	int length;         //顺序表的当前长度 }SqList;                //顺序表的类型定义    bool ListInsert(SqList &L, int i, int e){      if(i<1||i>L.length+1)    //判断i的范围是否有效         return false;     if(L.length>=MaxSize) //当前存储空间已满，不能插入           return false;      for(int j=L.length; j>=i; j--){    //将第i个元素及其之后的元素后移         L.data[j]=L.data[j-1];     }     L.data[i-1]=e;  //在位置i处放入e     L.length++;      //长度加1     return true; }  int main(){  	SqList L;   //声明一个顺序表 	InitList(L);//初始化顺序表 	//...此处省略一些代码；插入几个元素  	ListInsert(L,3,3);   //再顺序表L的第三行插入3  	return 0; } 
 顺序表的删除操作
 ListDelete(&Li,&e): 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
 平均时间复杂度 = 
 #define MaxSize 10  typedef struct { 	int data[MaxSize]; 	int length; } SqList;  // 删除顺序表i位置的数据并存入e bool ListDelete(SqList &L, int i, int &e) { 	if (i < 1 || 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); 	else 		printf("位序i不合法，删除失败\n");  	return 0;  }  
 顺序表的查找
顺序表的按位查找
 GetElem(L,):按位查找操作。获取表L中第i个位置的元素的值
 平均时间复杂度
 // 静态分配的按位查找 #define MaxSize 10  typedef struct { 	ElemType data[MaxSize];  	int length; }SqList;  ElemType GetElem(SqList L, int i) { 	return L.data[i-1]; } 
 // 动态分配的按位查找 #define InitSize 10  typedef struct { 	ElemType *data; 	int MaxSize; 	int length; }SeqList;  ElemType GetElem(SeqList L, int i) { 	return L.data[i-1]; } 
 顺序表的按值查找
 LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素
 平均时间复杂度 =
 #define InitSize 10          //定义最大长度  typedef struct{     ElemTyp *data;           //用静态的“数组”存放数据元素      int Length;              //顺序表的当前长度 }SqList;     //在顺序表L中查找第一个元素值等于e的元素，并返回其位序 int LocateElem(SqList L, ElemType e){     for(int i=0; i
 2.3 线性表的链式表示
 以上我们看完顺序表的物理存储了，然后我们学习单链表
2.3.1. 单链表的基本概念
单链表：用链式存储实现了线性结构。一个结点存储一个数据元素，各结点间的前后关系用一个指针表示。
特点：
 优点：不要求大片连续空间，改变容量方便。
 缺点：不可随机存取，要耗费一定空间存放指针。
两种实现方式：
 带头结点，写代码更方便。头结点不存储数据，头结点指向的下一个结点才存放实际数据。
 不带头结点，麻烦。对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。
 typedef struct LNode {                      //定义单链表结点类型     ElemType data;     //数据域     struct LNode *next;//指针域 }LNode, *LinkList;
 强调这是一个单链表--使用 LinkList
强调这是一个结点--使用 LNode* 
2.3.2. 单链表的实现
不带头节点
 typedef struct LNode{     ElemType data;     struct LNode *next; }LNode, *LinkList;  //初始化一个空的单链表 bool InitList(LinkList &L){     L = NULL; //空表，暂时还没有任何结点     return true; }  void test(){     LinkList L;  //声明一个指向单链表的头指针     //初始化一个空表     InitList(L);     ... }  //判断单链表是否为空 bool Empty(LinkList L){     return (L==NULL) } 
 带头节点
 typedef struct LNode {     ElemType data;     struct LNode *next; }LNode, *LinkList;  //初始化一个单链表（带头结点） bool InitList(LinkList &L) {       L = (LNode*) malloc(sizeof(LNode));  //头指针指向的结点——分配一个头结点（不存储数据）     if (L == NULL)          //内存不足，分配失败         return false;     L -> next = NULL;       //头结点之后暂时还没有结点     return true; }  void test() {     LinkList L;  //声明一个指向单链表的指针: 头指针     //初始化一个空表     InitList(L);     //... }  //判断单链表是否为空（带头结点） bool Empty(LinkList L) {     if (L->next == NULL)         return true;     else         return false; } 
 带头结点和不带头结点的比较：
不带头结点：写代码麻烦！对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑; 头指针指向的结点用于存放实际数据;
带头结点：头指针指向的头结点不存放实际数据,头结点指向的下一个结点才存放实际数据;
2.3.3. 单链表的插入
按位序插入（带头结点）
 Listlnsert(&Li,e): 插入操作。在表L中的第i个位置上插入指定元素e
 找到第i-1个结点(前驱结点)，将新结点插入其后；其中头结点可以看作第0个结点，故i=1时也适用。
平均时间复杂度:
 typedef struct LNode {     ElemType data;     struct LNode *next; }LNode, *LinkList;  //在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L, int i, ElemType e) {       //判断i的合法性, i是位序号(从1开始)     if(i<1)         return False;          LNode *p;       //指针p指向当前扫描到的结点      int j=0;        //当前p指向的是第几个结点     p = L;          //L指向头结点，头结点是第0个结点（不存数据）      //循环找到第i-1个结点     while(p!=NULL && jlengh, p最后会等于NULL         p = p->next;             //p指向下一个结点         j++;     }      if (p==NULL)                 //如果p指针知道最后再往后就是NULL         return false;          //在第i-1个结点后插入新结点     LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点     s->data = e;     s->next = p->next;     p->next = s;                 //将结点s连到p后,后两步千万不能颠倒qwq      return true; }
  按位序插入（不带头结点）
 Listlnsert(&L,i,e): 插入操作。在表L中的第i个位置上插入指定元素e。将新结点插入其后;
 因为不带头结点，所以不存在“第0个”结点，因此！i=1 时，需要特殊处理——插入(删除)第1个元素时，需要更改头指针L;
 typedef struct LNode {     ElemType data;     struct LNode *next; }LNode, *LinkList;  bool ListInsert(LinkList &L, int i, ElemType e) {     if(i<1)         return false;          //插入到第1个位置时的操作有所不同！     if(i==1){         LNode *s = (LNode *)malloc(size of(LNode));         s->data =e;         s->next =L;         L=s;          //头指针指向新结点         return true;     }      //i>1的情况与带头结点一样！唯一区别是j的初始值为1     LNode *p;       //指针p指向当前扫描到的结点      int j=1;        //当前p指向的是第几个结点     p = L;          //L指向头结点，头结点是第0个结点（不存数据）      //循环找到第i-1个结点     while(p!=NULL && jlengh, p最后会等于NULL         p = p->next;             //p指向下一个结点         j++;     }      if (p==NULL)                 //i值不合法         return false;          //在第i-1个结点后插入新结点     LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点     s->data = e;     s->next = p->next;     p->next = s;               return true;  }
 指定结点的后插操作
 InsertNextNode(LNode *p, ElemType e)；
 给定一个结点p，在其之后插入元素e; 根据单链表的链接指针只能往后查找，故给定一个结点p，那么p之后的结点我们都可知，但是p结点之前的结点无法得知
 typedef struct LNode {     ElemType data;     struct LNode *next; }LNode, *LinkList;  bool InsertNextNode(LNode *p, ElemType e) {     if(p==NULL){         return false;     }      LNode *s = (LNode *)malloc(sizeof(LNode));     //某些情况下分配失败，比如内存不足     if(s==NULL)         return false;     s->data = e;          //用结点s保存数据元素e      s->next = p->next;     p->next = s;          //将结点s连到p之后      return true; }                         //平均时间复杂度 = O(1)   //有了后插操作，那么在第i个位置上插入指定元素e的代码可以改成： bool ListInsert(LinkList &L, int i, ElemType e) {       if(i<1)         return False;          LNode *p;       //指针p指向当前扫描到的结点      int j=0;        //当前p指向的是第几个结点     p = L;          //L指向头结点，头结点是第0个结点（不存数据）      //循环找到第i-1个结点     while(p!=NULL && jlengh, p最后4鸟会等于NULL         p = p->next;             //p指向下一个结点         j++;     }      return InsertNextNode(p, e) }  
 指定结点的前插操作
 设待插入结点是s，将s插入到p的前面。我们仍然可以将s插入到*p的后面。然后将p->data与s->data交换，这样既能满足了逻辑关系，又能是的时间复杂度为
 //前插操作：在p结点之前插入元素e bool InsertPriorNode(LNode *p, ElenType e){     if(p==NULL)         return false;          LNode *s = (LNode *)malloc(sizeof(LNode));     if(s==NULL) //内存分配失败         return false;      //重点来了！     s->next = p->next;     p->next = s;       //新结点s连到p之后     s->data = p->data; //将p中元素复制到s     p->data = e;       //p中元素覆盖为e      return true； } 
 2.3.4. 单链表的删除
按位序删除节点
 ListDelete(&L, i, &e): 删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值;头结点视为“第0个”结点；
 思路：找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点
 typedef struct LNode{     ElemType data;     struct LNode *next; }LNode, *LinkList;  bool ListDelete(LinkList &L, int i, ElenType &e){     if(i<1) return false;      LNode *p;       //指针p指向当前扫描到的结点      int j=0;        //当前p指向的是第几个结点     p = L;          //L指向头结点，头结点是第0个结点（不存数据）      //循环找到第i-1个结点     while(p!=NULL && jlengh, p最后会等于NULL         p = p->next;             //p指向下一个结点         j++;     }      if(p==NULL)          return false;     if(p->next == NULL) //第i-1个结点之后已无其他结点         return false;      LNode *q = p->next;         //令q指向被删除的结点     e = q->data;                //用e返回被删除元素的值     p->next = q->next;          //将*q结点从链中“断开”     free(q)                     //释放结点的存储空间      return true; }   
  指定结点的删除
 bool DeleteNode(LNode *p){     if(p==NULL)         return false;          LNode *q = p->next;      //令q指向*p的后继结点     p->data = p->next->data; //让p和后继结点交换数据域     p->next = q->next;       //将*q结点从链中“断开”     free(q);     return true; } //时间复杂度 = O(1)  
 2.3.5. 单链表的查找
单链表的按位查找
 GetElem(L, i): 按位查找操作，获取表L中第i个位置的元素的值;
 平均时间复杂度
 LNode * GetElem(LinkList L, int i){     if(i<0) return NULL;          LNode *p;               //指针p指向当前扫描到的结点     int j=0;                //当前p指向的是第几个结点     p = L;                  //L指向头结点,头结点是第0个结点(不存数据)     while(p!=NULL && jnext;         j++;     }      return p;               //返回p指针指向的值 }  
 单链表的按值查找
 LocateElem(L, e):按值查找操作，在表L中查找具有给定关键字值的元素;
 平均时间复杂度:
 LNode * LocateElem(LinkList L, ElemType e){     LNode *P = L->next;    //p指向第一个结点     //从第一个结点开始查找数据域为e的结点     while(p!=NULL && p->data != e){         p = p->next;     }     return p;           //找到后返回该结点指针，否则返回NULL }  
 求单链表的长度
 Length(LinkList L)：计算单链表中数据结点（不含头结点）的个数，需要从第一个结点看是顺序依次访问表中的每个结点。
 算法的时间复杂度为
 int Length(LinkList L){     int len=0;       //统计表长     LNode *p = L;     while(p->next != NULL){         p = p->next;         len++;     }     return len; }
 2.3.6. 单链表的建立
Step 1:初始化一个单链表
Step 2:每次取一个数据元素，插入到表尾/表头
尾插法建立单链表
 平均时间复杂度
 思路：每次将新节点插入到当前链表的表尾，所以必须增加一个尾指针r,使其始终指向当前链表的尾结点。好处：生成的链表中结点的次序和输入数据的顺序会一致。
 // 使用尾插法建立单链表L LinkList List_TailInsert(LinkList &L){        int x;			//设ElemType为整型int       L = (LinkList)malloc(sizeof(LNode));     //建立头结点(初始化空表)          LNode *s, *r = L;                        //r为表尾指针         scanf("%d", &x);                         //输入要插入的结点的值        while(x!=9999){                          //输入9999表示结束              s = (LNode *)malloc(sizeof(LNode));             s->data = x;                    r->next = s;                    r = s;                               //r指针指向新的表尾结点              scanf("%d", &x);            }         r->next = NULL;                          //尾结点指针置空           return L; } 
 头插法建立单链表
 平均时间复杂度
 LinkList List_HeadInsert(LinkList &L){       //逆向建立单链表     LNode *s;     int x;     L = (LinkList)malloc(sizeof(LNode));     //建立头结点     L->next = NULL;                          //初始为空链表,这步不能少！      scanf("%d", &x);                         //输入要插入的结点的值     while(x!=9999){                          //输入9999表结束         s = (LNode *)malloc(sizeof(LNode));  //创建新结点         s->data = x;         s->next = L->next;         L->next = s;                         //将新结点插入表中，L为头指针         scanf("%d", &x);        }     return L;     }  
 链表的逆置
 算法思想：逆置链表初始为空，原表中结点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空；
 LNode *Inverse(LNode *L) { 	LNode *p, *q; 	p = L->next;     //p指针指向第一个结点 	L->next = NULL;  //头结点指向NULL  	while (p != NULL){ 		q = p; 		p = p->next; 		q->next = L->next;   		L->next = q; 	} 	return L; 
 2.3.7. 双链表
双链表中节点类型的描述
 typedef struct DNode{            //定义双链表结点类型     ElemType data;               //数据域     struct DNode *prior, *next;  //前驱和后继指针 }DNode, *DLinklist;  
 双链表的初始化（带头结点）
 typedef struct DNode{            //定义双链表结点类型     ElemType data;               //数据域     struct DNode *prior, *next;  //前驱和后继指针 }DNode, *DLinklist;  //初始化双链表 bool InitDLinkList(Dlinklist &L){     L = (DNode *)malloc(sizeof(DNode));      //分配一个头结点     if(L==NULL)                              //内存不足，分配失败         return false;          L->prior = NULL;   //头结点的prior指针永远指向NULL     L->next = NULL;    //头结点之后暂时还没有结点     return true; }  void testDLinkList(){     //初始化双链表     DLinklist L;         // 定义指向头结点的指针L     InitDLinkList(L);    //申请一片空间用于存放头结点，指针L指向这个头结点     //... }  //判断双链表是否为空 bool Empty(DLinklist L){     if(L->next == NULL)    //判断头结点的next指针是否为空         return true;     else         return false; }
 双链表的插入操作
 后插操作
 InsertNextDNode(p, s): 在p结点后插入s结点
 bool InsertNextDNode(DNode *p, DNode *s){ //将结点 *s 插入到结点 *p之后     if(p==NULL || s==NULL) //非法参数         return false;          s->next = p->next;     if (p->next != NULL)   //p不是最后一个结点=p有后继结点           p->next->prior = s;     s->prior = p;     p->next = s;          return true; }
 双链表的删除操作
 删除p节点的后继节点
 //删除p结点的后继结点 bool DeletNextDNode(DNode *p){     if(p==NULL) return false;     DNode *q =p->next;            //找到p的后继结点q     if(q==NULL) return false;     //p没有后继结点;     p->next = q->next;     if(q->next != NULL)           //q结点不是最后一个结点         q->next->prior=p;     free(q);      return true; }  //销毁一个双链表 bool DestoryList(DLinklist &L){     //循环释放各个数据结点     while(L->next != NULL){         DeletNextDNode(L);  //删除头结点的后继结点     free(L); //释放头结点     L=NULL;  //头指针指向NULL      } }  
 双链表的遍历操作
 前向遍历
 while(p!=NULL){     //对结点p做相应处理，eg打印     p = p->prior; }
 后向遍历
 while(p!=NULL){     //对结点p做相应处理，eg打印     p = p->next; }
 注意：双链表不可随机存取，按位查找和按值查找操作都只能用遍历的方式实现，时间复杂度为
2.3.8. 循环链表
循环单链表
 最后一个结点的指针不是NULL,而是指向头结点
 typedef struct LNode{                 ElemType data;                    struct LNode *next;   }DNode, *Linklist;  /初始化一个循环单链表 bool InitList(LinkList &L){     L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点     if(L==NULL)             //内存不足，分配失败         return false;     L->next = L;            //头结点next指针指向头结点     return true; }  //判断循环单链表是否为空（终止条件为p或p->next是否等于头指针） bool Empty(LinkList L){     if(L->next == L)         return true;    //为空     else         return false; }  //判断结点p是否为循环单链表的表尾结点 bool isTail(LinkList L, LNode *p){     if(p->next == L)         return true;     else         return false; }
 单链表和循环单链表的比较：
单链表：从一个结点出发只能找到该结点后续的各个结点；对链表的操作大多都在头部或者尾部；设立头指针，从头结点找到尾部的时间复杂度=O(n)，即对表尾进行操作需要O(n)的时间复杂度;
循环单链表：从一个结点出发，可以找到其他任何一个结点；设立尾指针，从尾部找到头部的时间复杂度为O(1)，即对表头和表尾进行操作都只需要O(1)的时间复杂度;
循环单链表优点：从表中任一节点出发均可找到表中其他结点。
循环双链表 
 表头结点的prior指向表尾结点，表尾结点的next指向头结点
 typedef struct DNode{               ElemType data;                    struct DNode *prior, *next;   }DNode, *DLinklist;  //初始化空的循环双链表 bool InitDLinkList(DLinklist &L){     L = (DNode *) malloc(sizeof(DNode));    //分配一个头结点     if(L==NULL)            //内存不足，分配失败         return false;       L->prior = L;          //头结点的prior指向头结点     L->next = L;           //头结点的next指向头结点 }  void testDLinkList(){     //初始化循环单链表     DLinklist L;     InitDLinkList(L);     //... }  //判断循环双链表是否为空 bool Empty(DLinklist L){     if(L->next == L)         return true;     else         return false; }  //判断结点p是否为循环双链表的表尾结点 bool isTail(DLinklist L, DNode *p){     if(p->next == L)         return true;     else         return false; }  
 循环链表的插入
 bool InsertNextDNode(DNode *p, DNode *s){      s->next = p->next;     p->next->prior = s;     s->prior = p;     p->next = s;
 循环链表的删除
 //删除p的后继结点q p->next = q->next; q->next->prior = p; free(q);
 2.3.9. 静态链表
单链表：各个结点散落在内存中的各个角落，每个结点有指向下一个节点的指针(下一个结点在内存中的地址);
静态链表：用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素and下一个结点的数组下标(游标)
静态链表用代码表示
 #define MaxSize 10        //静态链表的最大长度  struct Node{              //静态链表结构类型的定义     ElemType data;        //存储数据元素     int next;             //下一个元素的数组下标(游标) };  //用数组定义多个连续存放的结点 void testSLinkList(){     struct Node a[MaxSize];  //数组a作为静态链表, 每一个数组元素的类型都是struct Node     //... }
 或者是：
 #define MaxSize 10        //静态链表的最大长度  typedef struct{           //静态链表结构类型的定义     ELemType data;        //存储数据元素     int next;             //下一个元素的数组下标 }SLinkList[MaxSize];  void testSLinkList(){     SLinkList a; }
 相当于：
 #define MaxSize 10        //静态链表的最大长度  struct Node{              //静态链表结构类型的定义     ElemType data;        //存储数据元素     int next;             //下一个元素的数组下标(游标) };  typedef struct Node SLinkList[MaxSize]; //重命名struct Node，用SLinkList定义“一个长度为MaxSize的Node型数组;   
 2.3.10. 顺序表和链表的比较
【逻辑结构】
顺序表和链表都属于线性表，都是线性结构
【存储结构】
顺序表：顺序存储
优点：支持随机存取，存储密度高
缺点：大片连续空间分配不方便，改变容量不方便
链表：链式存储
优点：离散的小空间分配方便，改变容量方便
缺点：不可随机存取，存储密度低
【基本操作 - 创建】
顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源；
静态分配：静态数组，容量不可改变
动态分配：动态数组，容量可以改变，但是需要移动大量元素，时间代价高（malloc(),free()）
链表：只需要分配一个头结点或者只声明一个头指针
【基本操作 - 销毁】
静态数组——系统自动回收空间
动态分配：动态数组——需要手动free()
【基本操作-增/删】
顺序表：插入/删除元素要将后续元素后移/前移；时间复杂度=O(n)，时间开销主要来自于移动元素；
链表：插入/删除元素只需要修改指针；时间复杂度=O(n)，时间开销主要来自查找目标元素
【基本操作-查】
顺序表
按位查找：O(1)
按值查找：O(n)，若表内元素有序，可在O(log2n)时间内找到
链表
按位查找：O(n)
按值查找：O(n)
顺序、链式、静态、动态四种存储方式的比较
 顺序存储的固有特点：
逻辑顺序与物理顺序一直，本质上是用数组存储线性表的各个元素（即随机存取）；存储密度大，存储空间利用率高。
链式存储的固有特点：
元素之间的关系采用这些元素所在的节点的“指针”信息表示（插、删不需要移动节点）。
静态存储的固有特点：
在程序运行的过程中不要考虑追加内存的分配问题。
动态存储的固有特点：
可动态分配内存；有效的利用内存资源，使程序具有可扩展性。
第三章 栈和队列
3.1. 栈
3.1.1. 栈的基本概念
只允许在一端(栈顶top)进行插入或删除操作的受限的线性表。
后进先出（Last In First Out）LIFO。
进栈顺序：a1 > a2 > a3 > a4 > a5
出栈顺序：a5 > a4 > a3 > a2 > a1 
3.1.2. 栈的基本操作
InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
Push(&S, x)：进栈。若栈 S 未满，则将 x 加入使其成为新的栈顶元素。
Pop(&S, &x)：出栈。若栈 S 非空，则弹出（删除）栈顶元素，并用 x 返回。
GetTop(S, &x)：读取栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。
StackEmpty(S)：判空。断一个栈 S 是否为空，若 S 为空，则返回 true，否则返回 false。
3.1.3. 栈的顺序存储实现
【顺序栈的定义】
 #define MaxSize 10              //定义栈中元素的最大个数  typedef struct{     ElemType data[MaxSize];     //静态数组存放栈中元素     int top;                    //栈顶元素 }SqStack;  void testStack(){     SqStack S;                 //声明一个顺序栈(分配空间)                                //连续的存储空间大小为 MaxSize*sizeof(ElemType) }
 【顺序栈的初始化】
 #define MaxSize 10 typedef struct{    	ElemType data[MaxSize];         int top; }SqStack;  // 初始化栈 void InitStack(SqStack &S){      S.top = -1;                   //初始化栈顶指针 }  // 判断栈是否为空 bool StackEmpty(SqStack S){         if(S.top == -1)                 return true;         else                 return false; } 
 【顺序栈的入栈出栈】
 // 新元素进栈 bool Push(SqStack &S, ElemType x){    // 判断栈是否已满         if(S.top == MaxSize - 1)                 return false;         S.data[++S.top] = x;         return true; }  // 出栈 bool Pop(SqStack &x, ElemType &x){    // 判断栈是否为空         if(S.top == -1)                 return false;         x = S.data[S.top--];         return true; } 
 【读取栈顶元素】 
 // 读栈顶元素 bool GetTop(SqStack S, ElemType &x){             if(S.top == -1)                         return false;             x = S.data[S.top];             return true;  } 
 进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。S.data[++S.top] = x
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。x = S.data[S.top--]
栈空条件：S.top==-
栈满条件：S.top==MaxSize-1
栈长：S.top+1
【共享栈(两个栈共享同一片空间)】
共享栈--特殊的顺序栈
将栈底设计在共享空间的两端，栈顶向中间靠拢
 #define MaxSize 10         //定义栈中元素的最大个数  typedef struct{     ElemType data[MaxSize];       //静态数组存放栈中元素     int top0;                     //0号栈栈顶指针     int top1;                     //1号栈栈顶指针 }ShStack;  //初始化栈 void InitSqStack(ShStack &S){     S.top0 = -1;        //初始化栈顶指针     S.top1 = MaxSize;    }
 3.1.4. 栈的链式存储
【链栈的定义】
定义：采用链式存储的栈称为链栈。
优点：链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。
特点：进栈和出栈都只能在栈顶一端进行(链头作为栈顶)
链表的头部作为栈顶，意味着：
1. 在实现数据"入栈"操作时，需要将数据从链表的头部插入；
2. 在实现数据"出栈"操作时，需要删除链表头部的首元节点；
因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表;
 栈的链式存储结构可描述为：
【链栈的定义】
 typedef struct Linknode{             ElemType data;        //数据域         Linknode *next;       //指针域 }Linknode,*LiStack;  void testStack(){        LiStack L;            //声明一个链栈 } 
 【链栈的初始化】
 typedef struct Linknode{            ElemType data;           Linknode *next; }Linknode,*LiStack;  // 初始化栈 bool InitStack(LiStack &L){         L = (Linknode *)malloc(sizeof(Linknode));        if(L == NULL)                      return false;        L->next = NULL;         return true; }  // 判断栈是否为空 bool isEmpty(LiStack &L){         if(L->next == NULL)               return true;        else                    return false; } 
 【入栈出栈】
 // 新元素入栈 bool pushStack(LiStack &L,ElemType x){       Linknode *s = (Linknode *)malloc(sizeof(Linknode));       if(s == NULL)                  return false;        s->data = x;          // 头插法           s->next = L->next;       L->next = s;          return true; }  // 出栈 bool popStack(LiStack &L, int &x){          // 栈空不能出栈       if(L->next == NULL)              return false;         Linknode *s = L->next;       x = s->data;            L->next = s->next;     free(s);            return true; } 
 3.2. 队列
3.2.1. 队列的基本概念
只允许在表的一端(队尾)插入，表的另一端(队头)进行删除操作的受限的线性表。
特点：先进先出（先入队的元素先出队）、FIFO（First In First Out）。
3.2.2. 队列的基本操作
InitQueue(&Q)：初始化队列，构造一个空队列Q。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Qx)：入队，若队列Q未满，则将x加入使之成为新的队尾。
DeQueue(&Q&x)：出队，若队列Q非空，则删除队头元素，并用x返回。
GetHead(Q&x)：读队头元素，若队列Q非空则用x返回队头元素。
ClearQueue(&Q)：销毁队列，并释放队列Q占用的内存空间。
3.2.3. 队列的顺序存储实现
队头指针：指向队头元素
队尾指针：指向队尾元素的下一个位置
【顺序队列的定义】
 #define MaxSize 10;     //定义队列中元素的最大个数  typedef struct{          ElemType data[MaxSize];   //用静态数组存放队列元素          int front, rear;          //队头指针和队尾指针 }SqQueue;  void test{          SqQueue Q;                //声明一个队列 } 
  【顺序队列的初始化】
 #define MaxSize 10;  typedef struct{        ElemType data[MaxSize];       int front, rear; }SqQueue;  // 初始化队列 void InitQueue(SqQueue &Q){         // 初始化时，队头、队尾指针指向0        // 队尾指针指向的是即将插入数据的数组下标       // 队头指针指向的是队头元素的数组下标     Q.rear = Q.front = 0; }  // 判断队列是否为空 bool QueueEmpty(SqQueue Q){          if(Q.rear == Q.front)                     return true;        else                   return false; } 
 【入队出队（循环队列）】
 // 新元素入队 bool EnQueue(SqQueue &Q, ElemType x){            // 如果队列已满直接返回     if((Q.rear+1)%MaxSize == Q.front) 	//牺牲一个单元区分队空和队满            return false;         Q.data[Q.rear] = x;        Q.rear = (Q.rear+1)%MaxSize;      return true; }  // 出队 bool DeQueue(SqQueue &Q, ElemType &x){         // 如果队列为空直接返回         if(Q.rear == Q.front)           return false;          x = Q.data[Q.front];       Q.front = (Q.front+1)%MaxSize;     return true; } 
  【获得队头元素】
 // 获取队头元素并存入x bool GetHead(SqQueue &Q, ElemType &x){     if(Q.rear == Q.front)               return false;     x = Q.data[Q.front];       return true; } 
 循环队列不能使用Q.rear == Q.front作为判空的条件，因为当队列已满时也符合该条件，会与判空发生冲突！
解决方法一：牺牲一个单元来区分队空和队满，即将(Q.rear+1)%MaxSize == Q.front作为判断队列是否已满的条件。（主流方法）
解决方法二：设置 size 变量记录队列长度。
 #define MaxSize 10;   typedef struct{        ElemType data[MaxSize];      int front, rear;         int size; }SqQueue;  // 初始化队列 void InitQueue(SqQueue &Q){      Q.rear = Q.front = 0;        Q.size = 0; }  // 判断队列是否为空 bool QueueEmpty(SqQueue 0){          if(Q.size == 0)               return true;        else                return false; }  // 新元素入队 bool EnQueue(SqQueue &Q, ElemType x){      if(Q.size == MaxSize)             return false;     Q.size++;      Q.data[Q.rear] = x;      Q.rear = (Q.rear+1)%MaxSize;       return true; }  // 出队 bool DeQueue(SqQueue &Q, ElemType &x){        if(Q.size == 0)                 return false;     Q.size--;     x = Q.data[Q.front];      Q.front = (Q.front+1)%MaxSize;      return true; } 
  解决方法三：设置 tag 变量记录队列最近的操作。（tag=0：最近进行的是删除操作；tag=1 ：最近进行的是插入操作）
 #define MaxSize 10;     typedef struct{         ElemType data[MaxSize];      int front, rear;             int tag; }SqQueue;  // 初始化队列 void InitQueue(SqQueue &Q){         Q.rear = Q.front = 0;        Q.tag = 0; }  // 判断队列是否为空，只有tag==0即出队的时候才可能为空 bool QueueEmpty(SqQueue 0){       if(Q.front == Q.rear && Q.tag == 0)             return true;        else                return false; }  // 新元素入队 bool EnQueue(SqQueue &Q, ElemType x){     if(Q.rear == Q.front && tag == 1)              return false;          Q.data[Q.rear] = x;      Q.rear = (Q.rear+1)%MaxSize;       Q.tag = 1;       return true; }  // 出队 bool DeQueue(SqQueue &Q, ElemType &x){     if(Q.rear == Q.front && tag == 0)           return false;        x = Q.data[Q.front];     Q.front = (Q.front+1)%MaxSize;      Q.tag = 0;          return true; } 
 3.2.4. 队列的链式存储实现
【链队列的定义】
 // 链式队列结点 typedef struct LinkNode{       ElemType data;         struct LinkNode *next; }  // 链式队列 typedef struct{            // 头指针和尾指针       LinkNode *front, *rear; }LinkQueue; 
 【 链队列的初始化（带头结点）】
 typedef struct LinkNode{         ElemType data;          struct LinkNode *next; }LinkNode;  typedef struct{         LinkNode *front, *rear; }LinkQueue;  // 初始化队列 void InitQueue(LinkQueue &Q){        // 初始化时，front、rear都指向头结点      Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));       Q.front -> next = NULL; }  // 判断队列是否为空 bool IsEmpty(LinkQueue Q){      if(Q.front == Q.rear)              return true;           else                  return false; } 
 【入队出队（带头结点）】
 // 新元素入队 void EnQueue(LinkQueue &Q, ElemType x){      LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));      s->data = x;       s->next = NULL;      Q.rear->next = s;       Q.rear = s; }  // 队头元素出队 bool DeQueue(LinkQueue &Q, ElemType &x){        if(Q.front == Q.rear)                  return false;         LinkNode *p = Q.front->next;      x = p->data;        Q.front->next = p->next;      // 如果p是最后一个结点，则将队头指针也指向NULL       if(Q.rear == p)                   Q.rear = Q.front;        free(p);          return true; } 
 【不带头结点的链队列操作】
 typedef struct LinkNode{        ElemType data;       struct LinkNode *next; }LinkNode;  typedef struct{        LinkNode *front, *rear; }LinkQueue;  // 初始化队列 void InitQueue(LinkQueue &Q){      // 不带头结点的链队列初始化，头指针和尾指针都指向NULL     Q.front = NULL;        Q.rear = NULL; }  // 判断队列是否为空 bool IsEmpty(LinkQueue Q){      if(Q.front == NULL)            return true;           else                      return false; }  // 新元素入队 void EnQueue(LinkQueue &Q, ElemType x){      LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));       s->data = x;        s->next = NULL;      // 第一个元素入队时需要特别处理        if(Q.front == NULL){         Q.front = s;             Q.rear = s;      }else{         Q.rear->next = s;         Q.rear = s;     } }  //队头元素出队 bool DeQueue(LinkQueue &Q, ElemType &x){     if(Q.front == NULL)         return false;     LinkNode *s = Q.front;     x = s->data;     if(Q.front == Q.rear){         Q.front = Q.rear = NULL;     }else{         Q.front = Q.front->next;     }     free(s);     return true; } 
 3.2.5. 双端队列
双端队列定义 
双端队列是允许从两端插入、两端删除的线性表。
如果只使用其中一端的插入、删除操作，则等同于栈。
输入受限的双端队列：允许一端插入，两端删除的线性表。
输出受限的双端队列：允许两端插入，一端删除的线性表。
双端队列考点：判断输出序列的合法化
例：数据元素输入序列为 1，2，3，4，判断 4! = 24 个输出序列的合法性
        输入受限的双端队列：只有 4213 和 4231 不合法
        输出受限的双端队列：只有 4132 和 4231 不合法
3.3. 栈与队列的应用
3.3.1 栈在括号匹配中的应用
用栈实现括号匹配：最后出现的左括号最先被匹配 （栈的特性——LIFO）。
遇到左括号就入栈。
遇到右括号，就“消耗”一个左括号（出栈）。
匹配失败情况：扫描到右括号且栈空，则该右括号单身。
扫描完所有括号后，栈非空，则该左括号单身。
左右括号不匹配。
 #define MaxSize 10  typedef struct{         char data[MaxSize];        int top; }SqStack;  void InitStack(SqStack &S); bool StackEmpty(SqStack &S); bool Push(SqStack &S, char x); bool Pop(SqStack &S, char &x);  // 判断长度为length的字符串str中的括号是否匹配 bool bracketCheck(char str[], int length){      SqStack S;           InitStack(S);      // 遍历str         for(int i=0; i
 3.3.2. 栈在表达式求值中的应用 
中缀表达式：中缀表达式是一种通用的算术或逻辑公式表示方法，运算符以中缀形式处于操作数的中间。对于计算机来说中缀表达式是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。
前缀表达式（波兰表达式）：前缀表达式的运算符位于两个操作数之前。
后缀表达式（逆波兰表达式）：后缀表达式的运算符位于两个操作数之后。
中缀表达式转后缀表达式-手算
步骤1： 确定中缀表达式中各个运算符的运算顺序
步骤2： 选择下一个运算符，按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数
步骤3： 如果还有运算符没被处理，继续步骤2
“左优先”原则: 只要左边的运算符能先计算，就优先算左边的 (保证运算顺序唯一)；
 中缀：A + B - C * D / E + F        ①   ④   ②   ③   ⑤      后缀：A B + C D * E / - F + 
 后缀表达式的计算—手算:
 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数
后缀表达式的计算—机算
 用栈实现后缀表达式的计算（栈用来存放当前暂时不能确定运算次序的操作数）
步骤1: 从左往后扫描下一个元素，直到处理完所有元素;
步骤2: 若扫描到操作数，则压入栈，并回到步骤1;否则执行步骤3;
步骤3: 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到步骤1;
中缀表达式转后缀表达式(机算) 
 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符从左到右处理各个元素，直到末尾。可能遇到三种情况:
 1.遇到操作数：直接加入后缀表达式。
 2.遇到界限符：遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到 弹出“(”为止。注意：“(”不加入后缀表达式。
 3.遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式， 若碰到“(” 或栈空则停止。之后再把当前运算符入栈。
 #define MaxSize 40  typedef struct{          char data[MaxSize];        int top; }SqStack;  typedef struct{       char data[MaxSize];       int front,rear; }SqQueue;  void InitStack(SqStack &S); bool StackEmpty(SqStack S); bool Push(SqStack &S, char x); bool Pop(SqStack &S, char &x); void InitQueue(SqQueue &Q); bool EnQueue(LQueue &Q, char x); bool DeQueue(LQueue &Q, char &x); bool QueueEmpty(SqQueue Q);  // 判断元素ch是否入栈 int JudgeEnStack(SqStack &S, char ch){     char tp = S.data[S->top];        // 如果ch是a~z则返回-1         if(ch >= 'a' && ch <= 'z')            return -1;         // 如果ch是+、-、*、/且栈顶元素优先级大于等于ch则返回0       else if(ch == '+' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))            return 0;          else if(ch == '-' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))            return 0;       else if(ch == '*' && (tp == '*' || tp == '/'))           return 0;         else if(ch == '/' && (tp == '*' || tp == '/'))              return 0;         // 如果ch是右括号则返回2        else if(ch == ')')               return 2;          // 其他情况ch入栈，返回1        else return 1; }  // 中缀表达式转后缀表达式 int main(int argc, char const *argv[]) {       SqStack S;          SqQueue Q;	      InitStack(S);      InitQueue(Q);       char ch;	       printf("请输入表达式，以“#”结束：");       scanf("%c", &ch);        while (ch != '#'){           // 当栈为空时              if(StackEmpty(&S)){              // 如果输入的是数即a~z，直接入队              if(ch >= 'a' && ch <= 'z')                                EnQueue(Q, ch);      	             // 如果输入的是运算符，直接入栈                 else                                       Puch(S, ch);                }else{                             // 当栈非空时，判断ch是否需要入栈              int n = JudgeEnStack(S, ch);                  // 当输入是数字时直接入队      	             if(n == -1){        	                     EnQueue(Q, ch);                     }else if(n == 0){                        // 当输入是运算符且运算符优先级不高于栈顶元素时                     while (1){                              // 取栈顶元素入队                         char tp;                             Pop(S, tp);                           EnQueue(Q, tp);                              // 再次判断是否需要入栈                          n = JudgeEnStack(S, ch);                     // 当栈头优先级低于输入运算符或者栈头为‘)’时，入栈并跳出循环                       if(n != 0){                                    EnStack(S, ch);                                    break;                                   }                                    }                         }else if(n == 2){                   // 当出现‘)’时 将()中间的运算符全部出栈入队                    while(1){                                     char tp;                                     Pop(S, tp);                                  if(tp == '(')                                   break;                             else                                     EnQueue(Q, tp);                     }                          }else{                         // 当运算符优先级高于栈顶元素或出现‘(’时直接入栈                      Push(S, ch);                      }                   }                  scanf("%c", &ch);        }          // 将最后栈中剩余的运算符出栈入队      while (!StackEmpty(S)){	           char tp;                     Pop(S, tp);               EnQueue(Q, tp);       }           // 输出队中元素      while (!QueueEmpety(Q)){             printf("%c ", DeQueue(Q));       }         return 0; } 
 用栈实现中缀表达式的计算:
      1.初始化两个栈，操作数栈和运算符栈；
      2.若扫描到操作数，压入操作数栈；
      3.若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈(期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈) 
3.3.3. 栈在递归中的应用
函数调用的特点：最后被调用的函数最先执行结束(LIFO)
函数调用时，需要用一个栈存储：
调用返回地址
实参
局部变量
递归调用时，函数调用栈称为 “递归工作栈”:
每进入一层递归，就将递归调用所需信息压入栈顶；
每退出一层递归，就从栈顶弹出相应信息；
缺点：太多层递归可能回导致栈溢出；适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题
3.3.4. 队列的应用
队列应用：树的层次遍历
队列应用：图的广度优先遍历
队列应用：操作系统中多个进程争抢着使用有限的系统资源时，先来先服务算法（First Come First Service）是是一种常用策略。
3.4. 特殊矩阵的压缩存储 
3.4.1 数组的存储
一维数组的存储：各数组元素大小相同，且物理上连续存放。设起始地址为LOC，则数组元素的存放地址 = LOC + i * sizeof(ElemType) (0≤i<10)
二维数组的存储 ：
        1. M行N列的二维数组中，设起始地址为LOC，若按行优先存储，则的存储地址 =
        2. M行N列的二维数组中，设起始地址为 LOC，若按列优先存储，则的存储地址 = 
 
3.4.2 对称矩阵的压缩存储
         对称矩阵的压缩存储：若n阶方阵中任意一个元素,都有则该矩阵为对称矩阵，对于对称矩阵，只需存储主对角线+下三角区。若按照行优先原则将各元素存入一维数组中，即存入到数组中，那么数组共有个元素。对于k，有：
3.4.3 三角矩阵的压缩存储
下三角矩阵：除了主对角线和下三角区，其余的元素都相同。
上三角矩阵：除了主对角线和上三角区，其余的元素都相同。
压缩存储策略：按行优先原则将主对角线+下三角区存入一维数组中，并在最后一个位置存储常量。即存入到数组中，那么数组共有个元素。对于k，有：
 
 
3.4.4 三对角矩阵的压缩存储
三对角矩阵，又称带状矩阵: 当时，有。对于三对角矩阵，按行优先原则，只存储带状部分，即存入到数组中，那么。若已知数组下标k，则 。
3.4.5 稀疏矩阵的压缩存储
稀疏矩阵的非零元素远远少于矩阵元素的个数。压缩存储策略：
顺序存储：三元组 <行，列，值>
链式存储：十字链表法 
第四章 串
4.1. 串的基本概念
串，即字符串 (String) 是由零个或多个字符组成的有限序列。一般记为S='a1a2.....·an'(n>=0)
其中，S是串名，单引号括起来的字符序列是串的值;a;可以是字母、数字或其他字符;串中字符的个数n称为串的长度。n =0时的串称为空串 。
例:
 S="HelloWorld!" T='iPhone 11 Pro Max?'
 子串:串中任意个连续的字符组成的子序列。
主串:包含子串的串。
字符在主串中的位置:字符在串中的序号。子串在主串中的位置:子串的第一个字符在主串中的位置。
串是一种特殊的线性表，数据元素之间呈线性关系
串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）
串的基本操作，如增删改查等通常以子串为操作对象。
4.2. 串的基本操作
假设有串 T = '', S = 'iPhone 11 Pro Max?', W = 'Pro'
StrAssign(&T, chars)： 赋值操作，把串T赋值为chars。
StrCopy(&T, S):：复制操作，把串S复制得到串T。
StrEmpty(S)：判空操作，若S为空串，则返回TRUE，否则返回False。
StrLength(S)：求串长，返回串S的元素个数。
ClearString(&S)：清空操作，将S清为空串。
DestroyString(&S)：销毁串，将串S销毁（回收存储空间）。
Concat(&T, S1, S2)：串联接，用T返回由S1和S2联接而成的新串。
SubString(&Sub, S, pos, len)求子串，用Sub返回串S的第pos个字符起长度为len的子串.
Index(S, T)：定位操作，若主串S中存在与串T值相同的子串，则返回它再主串S中第一次出现的位置，否则函数值为0.
StrCompare(S, T)：串的比较操作，参照英文词典排序方式；若S > T,返回值>0; S = T,返回值=0 (需要两个串完全相同) ; S < T,返回值<0.
4.3. 串的存储实现
4.3.1 静态数组实现
静态数组实现(定长顺序存储) 
 #define MAXLEN 255   //预定义最大串长为255  typedef struct{     char ch[MAXLEN];   //静态数组实现（定长顺序存储）                        //每个分量存储一个字符                        //每个char字符占1B     int length;        //串的实际长度 }SString; 
  动态数组实现( 堆分配存储)
 typedef struct{     char *ch;          //按串长分配存储区，ch指向串的基地址     int length;        //串的实际长度 }HString; HString S; S.ch = (char*)malloc(MAXLEN *sizeof(char)); S.length = 0;
 4.3.2 基本操作的实现
 #define MAXLEN 255  typedef struct{     char ch[MAXLEN];        int length;        %7


            
            
                
               
            
            
                
                    上一篇：详解IIC通信协议以及FPGA实现

                
                
                    下一篇：使用团结引擎创世版导出OpenHarmony应用                
            
            
            
                
                相关内容


    

    
    
        
        
            
            
                
                
                    
                    
                        
                        热门资讯
                        
                    
                    
                
                
            
            
            
            

                                
                
                    
                    
                    
                    
                    
                        裸辞做“一人公司”，我后悔了
                        去年这个时候，一位以色列程序员正在东南亚旅行。他顺手把一个在脑子里转了很久的想法做成了产品，一个让任...
                    
                    
                
                                
                
                    
                    
                    
                    
                    
                        南京建成国内首个Pre-6G试...
                        4月21日，2026全球6G技术与产业生态大会在南京开幕。全息互动技术展台前，一名远在北京的工作人员...
                    
                    
                
                                
                
                    
                    
                    
                    
                    
                        超梵求职受邀参加“2025抖音...
                        超梵求职受邀参加“2025抖音巨量引擎成人教育行业生态大会”，探讨分享优质内容传播，服务万千学员。 ...
                    
                    
                
                                
                
                    
                    
                    
                    
                    
                        摩托罗拉Razr 2026（R...
                        IT之家 4 月 22 日消息，摩托罗拉宣布新一代 Razr 折叠手机将于 4 月 29 日在美国发...
                    
                    
                
                                
                
                    
                    
                    
                    
                    
                        库克卸任，特纳斯领航：苹果新纪...
                        苹果首席执行官蒂姆·库克将卸任，硬件工程主管约翰·特纳斯将接任，苹果公司今天宣布此事。 库克将在夏季...





    
    
        
        
            2026 ©
            泰达科技网财丁探索汉高教育网比特空间太卓网能源100易库网汇川网电池功率网太卓IC网土豆游戏网        
        
        
        
                        
                科技资讯
            
                        
                电脑知识

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

第一章 数据结构绪论

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 基本操作的实现

相关内容

热门资讯

第一章数据结构绪论

第二章线性表

第三章栈和队列

第四章串