【王道考研】王道数据结构与算法详细笔记（全） |
您所在的位置：网站首页 › 数据结构算法题评分标准 › 【王道考研】王道数据结构与算法详细笔记（全） |
【王道考研】王道数据结构与算法详细笔记（全）
|
目录 第一章 数据结构绪论 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.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 算法的时间复杂度
什么时候要传入参数的引用“&“-- 对参数的修改结果需要“带回来”看下面举例： 首先是传值调用： #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 顺序表
我们看完线性表的逻辑结构和基本运算，现在继续学习物理结构：顺序表
顺序表的静态分配 顺序表的表长刚开始确定后就无法更改(存储空间是静态的)
//顺序表的实现--静态分配
#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);
else
printf("位序i不合法，删除失败\n");
return 0;
}
顺序表的查找
带头结点和不带头结点的比较： 不带头结点：写代码麻烦！对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑; 头指针指向的结点用于存放实际数据;带头结点：头指针指向的头结点不存放实际数据,头结点指向的下一个结点才存放实际数据; 2.3.3. 单链表的插入
后向遍历 while(p!=NULL){ //对结点p做相应处理，eg打印 p = p->next; }注意：双链表不可随机存取，按位查找和按值查找操作都只能用遍历的方式实现，时间复杂度为
单链表和循环单链表的比较：
单链表：各个结点散落在内存中的各个角落，每个结点有指向下一个节点的指针(下一个结点在内存中的地址); 静态链表：用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素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)顺序、链式、静态、动态四种存储方式的比较 顺序存储的固有特点： 逻辑顺序与物理顺序一直，本质上是用数组存储线性表的各个元素（即随机存取）；存储密度大，存储空间利用率高。链式存储的固有特点： 元素之间的关系采用这些元素所在的节点的“指针”信息表示（插、删不需要移动节点）。静态存储的固有特点： 在程序运行的过程中不要考虑追加内存的分配问题。动态存储的固有特点： 可动态分配内存；有效的利用内存资源，使程序具有可扩展性。
【顺序栈的定义】 #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）。
【顺序队列的定义】 #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; itop]; // 如果ch是a~z则返回-1 if(ch >= 'a' && ch = 'a' && ch =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,返回值 S.length) return false; for (int i=pos; i ?
二又树的递归特性: 【1】要么是个空二叉树 【2】要么就是由“根节点+左子树+右子树”组成的二叉树 【二叉树的先中后遍历】 先序遍历:根左右(NLR) typedef struct BiTnode{ ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; void PreOrder(BiTree T){ if(T!=NULL){ visit(T); //访问根结点 PreOrder(T->lchild); //递归遍历左子树 PreOrder(T->rchild); //递归遍历右子树 } } 中序遍历:左根右 (LNR) typedef struct BiTnode{ ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; void InOrder(BiTree T){ if(T!=NULL){ InOrder(T->lchild); //递归遍历左子树 visit(T); //访问根结点 InOrder(T->rchild); //递归遍历右子树 } } 后序遍历:左右根(LRN) typedef struct BiTnode{ ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; void PostOrder(BiTree T){ if(T!=NULL){ PostOrder(T->lchild); //递归遍历左子树 PostOrder(T->rchild); //递归遍历右子树 visit(T); //访问根结点 } } 5.3.2. 二叉树的层序遍历算法思想: 1.初始化一个辅助队列2.根结点入队3.若队列非空，则队头结点出队，访问该结点，并将孩子插入队尾(如果有的话)4.重复3直至队列为空 //二叉树的结点(链式存储) typedef struct BiTnode{ ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; //链式队列结点 typedef struct LinkNode{ BiTNode * data; typedef LinkNode *next; }LinkNode; typedef struct{ LinkNode *front, *rear; }LinkQueue; //层序遍历 void LevelOrder(BiTree T){ LinkQueue Q; InitQueue (Q); //初始化辅助队列 BiTree p; EnQueue(Q,T); //将根节点入队 while(!isEmpty(Q)){ //队列不空则循环 DeQueue(Q,p); //队头结点出队 visit(p); //访问出队结点 if(p->lchild != NULL) EnQueue(Q,p->lchild); //左孩子入队 if(p->rchild != NULL) EnQueue(Q,p->rchild); //右孩子入队 } } 5.3.3. 由遍历序列构造二叉树 一个前序遍历序列可能对应多种二叉树形态。同理，一个后序遍历序列、一个中序遍历序列、一个层序遍历序列也可能对应多种二叉树形态。即：若只给出一棵二叉树的 前/中/后/层序遍历序列 中的一种，不能唯一确定一棵二叉树。由二叉树的遍历序列构造二叉树： 1. 前序+中序遍历序列 2. 后序+中序遍历序列 3. 层序+中序遍历序列 由 前序+中序遍历序列 构造二叉树：由前序遍历的遍历顺序（根节点、左子树、右子树）可推出根节点，由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。由 后序+中序遍历序列 构造二叉树：由后序遍历的遍历顺序（左子树、右子树、根节点）可推出根节点，由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。由 层序+中序遍历序列 构造二叉树：由层序遍历的遍历顺序（层级遍历）可推出根节点，由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。
线索二叉树的概念与作用 n 个结点的二叉树，有 n+1 个空链域，可用来记录前驱、后继的信息。指向前驱、后继的指针被称为“线索”，形成的二叉树被称为线索二叉树。在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。线索二叉树的结点在原本二叉树的基础上，新增了左右线索标志 tag。当 tag == 0 时，表示指针指向孩子；当 tag == 1 时，表示指针是“线索”。 //线索二叉树结点 typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; // 左、右线索标志 }ThreadNode, *ThreadTree;中序线索化的存储
先序线索化的存储
后序线索化的存储
中序线索化： typedef struct ThreadNode{ int data; struct ThreadNode *lchild, *rchild; int ltag, rtag; // 左、右线索标志 }ThreadNode, *ThreadTree; //全局变量pre, 指向当前访问的结点的前驱 TreadNode *pre=NULL; void InThread(ThreadTree T){ if(T!=NULL){ InThread(T->lchild); //中序遍历左子树 visit(T); //访问根节点 InThread(T->rchild); //中序遍历右子树 } } void visit(ThreadNode *q){ if(q->lchid = NULL){ //左子树为空，建立前驱线索 q->lchild = pre; q->ltag = 1; } if(pre!=NULL && pre->rchild = NULL){ pre->rchild = q; //建立前驱结点的后继线索 pre->rtag = 1; } pre = q; } //中序线索化二叉树T void CreateInThread(ThreadTree T){ pre = NULL; //pre初始为NULL if(T!=NULL);{ //非空二叉树才能进行线索化 InThread(T); //中序线索化二叉树 if(pre->rchild == NULL) pre->rtag=1; //处理遍历的最后一个结点 } }先序线索化： typedef struct ThreadNode{ int data; struct ThreadNode *lchild, *rchild; int ltag, rtag; // 左、右线索标志 }ThreadNode, *ThreadTree; //全局变量pre, 指向当前访问的结点的前驱 TreadNode *pre=NULL; //先序遍历二叉树，一边遍历一边线索化 void PreThread(ThreadTree T){ if(T!=NULL){ visit(T); if(T->ltag == 0) //lchild不是前驱线索 PreThread(T->lchild); PreThread(T->rchild); } } void visit(ThreadNode *q){ if(q->lchid = NULL){ //左子树为空，建立前驱线索 q->lchild = pre; q->ltag = 1; } if(pre!=NULL && pre->rchild = NULL){ pre->rchild = q; //建立前驱结点的后继线索 pre->rtag = 1; } pre = q; } //先序线索化二叉树T void CreateInThread(ThreadTree T){ pre = NULL; //pre初始为NULL if(T!=NULL);{ //非空二叉树才能进行线索化 PreThread(T); //先序线索化二叉树 if(pre->rchild == NULL) pre->rtag=1; //处理遍历的最后一个结点 } }后序线索化： typedef struct ThreadNode{ int data; struct ThreadNode *lchild, *rchild; int ltag, rtag; // 左、右线索标志 }ThreadNode, *ThreadTree; //全局变量pre, 指向当前访问的结点的前驱 TreadNode *pre=NULL; //先序遍历二叉树，一边遍历一边线索化 void PostThread(ThreadTree T){ if(T!=NULL){ PostThread(T->lchild); PostThread(T->rchild); visit(T); //访问根节点 } } void visit(ThreadNode *q){ if(q->lchid = NULL){ //左子树为空，建立前驱线索 q->lchild = pre; q->ltag = 1; } if(pre!=NULL && pre->rchild = NULL){ pre->rchild = q; //建立前驱结点的后继线索 pre->rtag = 1; } pre = q; } //先序线索化二叉树T void CreateInThread(ThreadTree T){ pre = NULL; //pre初始为NULL if(T!=NULL);{ //非空二叉树才能进行线索化 PostThread(T); //后序线索化二叉树 if(pre->rchild == NULL) pre->rtag=1; //处理遍历的最后一个结点 } } 5.3.6. 在线索二叉树中找前驱/后继
中序线索二叉树找到指定结点 * p 的中序后继 next： 若p->rtag==1，则next = p->rchild；若p->rtag==0，则 next 为 p 的右子树中最左下结点。 // 找到以p为根的子树中，第一个被中序遍历的结点 ThreadNode *FirstNode(ThreadNode *p){ // 循环找到最左下结点（不一定是叶结点） while(p->ltag==0) p=p->lchild; return p; } // 在中序线索二叉树中找到结点p的后继结点 ThreadNode *NextNode(ThreadNode *p){ // 右子树中最左下的结点 if(p->rtag==0) return FirstNode(p->rchild); else return p->rchild; } // 对中序线索二叉树进行中序循环（非递归方法实现） void InOrder(ThreadNode *T){ for(ThreadNode *p=FirstNode(T); p!=NULL; p=NextNode(p)){ visit(p); } }中序线索二叉树找到指定结点 * p 的中序前驱 pre： 若p->ltag==1，则pre = p->lchild；若p->ltag==0，则 next 为 p 的左子树中最右下结点。 // 找到以p为根的子树中，最后一个被中序遍历的结点 ThreadNode *LastNode(ThreadNode *p){ // 循环找到最右下结点（不一定是叶结点） while(p->rtag==0) p=p->rchild; return p; } // 在中序线索二叉树中找到结点p的前驱结点 ThreadNode *PreNode(ThreadNode *p){ // 左子树中最右下的结点 if(p->ltag==0) return LastNode(p->lchild); else return p->lchild; } // 对中序线索二叉树进行中序循环（非递归方法实现） void RevOrder(ThreadNode *T){ for(ThreadNode *p=LastNode(T); p!=NULL; p=PreNode(p)) visit(p); }先序线索二叉树找到指定结点 * p 的先序后继 next： 若p->rtag==1，则next = p->rchild；若p->rtag==0： 若 p 有左孩子，则先序后继为左孩子；若 p 没有左孩子，则先序后继为右孩子。先序线索二叉树找到指定结点 * p 的先序前驱 pre： 前提：改用三叉链表，可以找到结点 * p 的父节点。如果能找到 p 的父节点，且 p 是左孩子：p 的父节点即为其前驱；如果能找到 p 的父节点，且 p 是右孩子，其左兄弟为空：p 的父节点即为其前驱；如果能找到 p 的父节点，且 p 是右孩子，其左兄弟非空：p 的前驱为左兄弟子树中最后一个被先序遍历的结点；如果 p 是根节点，则 p 没有先序前驱。后序线索二叉树找到指定结点 * p 的后序前驱 pre： 若p->ltag==1，则pre = p->lchild；若p->ltag==0：若 p 有右孩子，则后序前驱为右孩子；若 p 没有右孩子，则后续前驱为右孩子。后序线索二叉树找到指定结点 * p 的后序后继 next： 前提：改用三叉链表，可以找到结点 * p 的父节点。如果能找到 p 的父节点，且 p 是右孩子：p 的父节点即为其后继；如果能找到 p 的父节点，且 p 是左孩子，其右兄弟为空：p 的父节点即为其后继；如果能找到 p 的父节点，且 p 是左孩子，其右兄弟非空：p 的后继为右兄弟子树中第一个被后序遍历的结点；如果 p 是根节点，则 p 没有后序后继。 5.4. 树和森林
双亲表示法（顺序存储）：每个结点中保存指向双亲的“指针”。 //数据域：存放结点本身信息。 //双亲域：指示本结点的双亲结点在数组中的位置。 #define MAX_TREE_SIZE 100 //树中最多结点数 typedef struct{ //树的结点定义 ElemType data; int parent; //双亲位置域 }PTNode; typedef struct{ //树的类型定义 PTNode nodes[MAX_TREE_SIZE]; //双亲表示 int n; //结点数 }PTree;增：新增数据元素，无需按逻辑上的次序存储；（需要更改结点数n） 删：（叶子结点）： ① 将伪指针域设置为-1； ②用后面的数据填补；（需要更改结点数n） 查询： ①优点-查指定结点的双亲很方便； ②缺点-查指定结点的孩子只能从头遍历，空数据导致遍历更慢； 优点: 查指定结点的双亲很方便缺点:查指定结点的孩子只能从头遍历 孩子表示法（顺序+链式存储） 孩子表示法:顺序存储各个节点，每个结点中保存孩子链表头指针。 struct CTNode{ int child; //孩子结点在数组中的位置 struct CTNode *next; // 下一个孩子 }; typedef struct{ ElemType data; struct CTNode *firstChild; // 第一个孩子 }CTBox; typedef struct{ CTBox nodes[MAX_TREE_SIZE]; int n, r; // 结点数和根的位置 }CTree;孩子兄弟表示法（链式存储） 用孩子兄弟表示法可以将树转换为二叉树的形式。 //孩子兄弟表示法结点 typedef struct CSNode{ ElemType data; struct CSNode *firstchild, *nextsibling; //第一个孩子和右兄弟结点 }CSNode, *CSTree; 5.4.2. 树和森林的遍历树的先根遍历 若树非空，先访问根结点，再依次对每棵子树进行先根遍历；（与对应二叉树的先序遍历序列相同） 树的先根遍历序列与这棵树相应二叉树的先序序列相同。 void PreOrder(TreeNode *R){ if(R!=NULL){ visit(R); //访问根节点 while(R还有下一个子树T) PreOrder(T); //先跟遍历下一个子树 } }树的后根遍历 若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。（深度优先遍历） 树的后根遍历序列与这棵树相应二叉树的中序序列相同。 void PostOrder(TreeNode *R){ if(R!=NULL){ while(R还有下一个子树T) PostOrder(T); //后跟遍历下一个子树 visit(R); //访问根节点 } }层序遍历（队列实现） 若树非空，则根结点入队；若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队；重复以上操作直至队尾为空；森林的遍历 先序遍历：等同于依次对各个树进行先根遍历；也可以先转换成与之对应的二叉树，对二叉树进行先序遍历；中序遍历：等同于依次对各个树进行后根遍历；也可以先转换成与之对应的二叉树，对二叉树进行中序遍历； 5.5. 应用
二又排序树，又称二叉查找树(BST，Binary Search Tree)棵二叉树或者是空二叉树，或者是具有如下性质的二叉树: 左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一棵二叉排序树；左子树结点值< 根结点值< 右子树结点值；进行中序遍历，可以得到一个递增的有序序列。【二叉排序树的查找】 若树非空，目标值与根结点的值比较；若相等，则查找成功；若小于根结点，则在左子树上查找；否则在右子树上查找；查找成功，返回结点指针;查找失败返回NULL 。 typedef struct BSTNode{ int key; struct BSTNode *lchild, *rchild; }BSTNode, *BSTree; //在二叉排序树中查找值为key的结点（非递归） //最坏空间复杂度：O(1) BSTNode *BST_Search(BSTree T, int key){ while(T!=NULL && key!=T->key){ //若树空或等于跟结点值，则结束循环 if(keykey) //值小于根结点值，在左子树上查找 T = T->lchild; else //值大于根结点值，在右子树上查找 T = T->rchild; } return T; } //在二叉排序树中查找值为key的结点（递归） //最坏空间复杂度：O(h) BSTNode *BSTSearch(BSTree T, int key){ if(T == NULL) return NULL; if(Kry == T->key) return T; else if(key < T->key) return BSTSearch(T->lchild, key); else return BSTSearch(T->rchild, key); }【二叉排序树的插入操作】 若原二叉排序树为空，则直接插入结点;否则；若关键字k小于根结点值，则插入到左子树；若关键字k大于根结点值，则插入到右子树。 //在二叉排序树中插入关键字为k的新结点（递归） //最坏空间复杂度：O(h) int BST_Insert(BSTree &T, int k){ if(T==NULL){ //原树为空，新插入的结点为根结点 T = (BSTree)malloc(sizeof(BSTNode)); T->key = k; T->lchild = T->rchild = NULL; return 1; //插入成功 } else if(K == T->key) //树中存在相同关键字的结点，插入失败 return 0; else if(k < T->key) return BST_Insert(T->lchild,k); else return BST_Insert(T->rchild,k); }【二叉排序树的构造】 //按照str[]中的关键字序列建立二叉排序树 void Crear_BST(BSTree &T, int str[], int n){ T = NULL; //初始时T为空树 int i=0; while(i 不存在，则向图 G 中添加该边。RemoveEdge(G, x, y)：若无向边 ( x , y ) (x, y)(x,y) 或有向边 < x , y > 存在，则从图 G 中删除该边。FirstNeighbor(G, x)：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 -1。NextNeighbor(G, x, y)：假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，则返回 -1。Get_edge_value(G, x, y)：获取图 G 中边 ( x , y )或 < x , y > 对应的权值。Set_edge_value(G, x, y, v)：设置图 G 中边 ( x , y )或 < x , y >对应的权值为 v。 6.3. 图的遍历
1、广度优先遍历 (Breadth-First-Search,BFS)要点: （1）找到与一个顶点相邻的所有顶点； （2）标记哪些顶点被访问过； （3）需要一个辅助队列。 2、广度优先遍历用到的操作：FirstNeighbor(G, x)：求图 G 中顶点 x 的第⼀个邻接点，若有则返回顶点号；若 x 没有邻接点或图中不存在 x，则返回 -1。NextNeighbor(G, x, y)：假设图 G 中顶点 y 是顶点 x 的⼀个邻接点，返回除 y 之外顶点 x 的下⼀个邻接点的顶点号，若 y 是 x 的最后⼀个邻接点，则返回 -1。 3、广度优先遍历代码实现： /*邻接矩阵的广度遍历算法*/ void BFSTraverse(MGraph G){ int i, j; Queue Q; for(i = 0; i=0; w=NextNeighor(G, v, w)){ if(!visited[w]){ //w为u的尚未访问的邻接顶点 DFS(G, w); } } } /*对图进行深度优先遍历*/ void DFSTraverse(MGraph G){ int v; for(v=0; v |
【本文地址】
今日新闻 |
推荐新闻 |