数据结构学习笔记（王道）-慈云数据

数据结构学习笔记（王道）

PS：本文章部分内容参考自王道考研数据结构笔记

文章目录

数据结构学习笔记（王道）

一、绪论

1.1. 数据结构
1.2. 算法

1.2.1. 算法的基本概念
1.2.2. 算法的时间复杂度
1.2.3. 算法的空间复杂度
二、线性表

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. 特殊矩阵的压缩存储
四、串

4.1. 串的基本概念
4.2. 串的基本操作
4.3. 串的存储实现
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.2.1. 顺序查找
7.2.2. 折半查找
7.2.3. 分块查找
7.3. B树、B+树

7.3.1. B树
7.3.2. B树的基本操作
7.3.3. B+树
7.4. 散列查找及其性能分析

7.4.1. 散列表的基本概念
7.4.2. 散列函数的构造方法
7.4.3. 处理冲突的方法
7.4.4. 散列查找及性能分析
八、排序

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.5.1. 归并排序
8.5.2. 基数排序
8.6. 内部排序算法总结

8.6.1. 内部排序算法比较
8.6.2. 内部排序算法的应用
8.7. 外部排序

8.7.1. 外部排序的基本概念和方法
8.7.2. 败者树
8.7.3. 置换-选择排序（生成初始归并段）

8.7.4. 最佳归并树

一、绪论

1.1. 数据结构

数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素：数据的基本单位，一个数据元素可由若干数据项组成。
数据项：数据的不可分割的最小单位。
数据对象：性质相同的数据元素的集合，是数据的一个子集。
数据结构：指互相之间存在着一种或多种特定关系的数据元素的集合，包括逻辑结构，存储结构和对数据的运算。（数据元素都不是孤立存在的）。
抽象数据类型（ADT）：指一个数学模型以及定义在该模型上的一组操作，只取决于它的一组逻辑特性，用一个三元组表示（D, S, P）。
数据类型：是程序设计语言中的一个概念，它是一个值的集合和操作的集合。
逻辑结构：是指数据之间关系的描述，与数据的存储结构无关。分为线性结构和非线性结构，通常分为四类结构：
1. 集合：结构中的数据元素除了同属于一种类型外，别无其它关系。
2. 线性结构：结构中的数据元素之间存在一对一的关系。
3. 树型结构：结构中的数据元素之间存在一对多的关系。
4. 图状结构（网状结构）：结构中的数据元素之间存在多对多的关系。
存储结构：是指数据结构在计算机中的表示，又称为数据的物理结构。它包括数据元素的表示和关系的表示，通常由四种基本的存储方法实现：
1. 顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素，存储位置反映数据元素间的逻辑关系，存储密度大。有些操作（如插入、删除）效率较差。
2. 链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针，指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），且不能折半查找。
3. 索引存储方式。除数据元素存储在一组地址连续的内存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。
4. 散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。

1.2. 算法

1.2.1. 算法的基本概念

算法：是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。
算法的特性：有穷性、确定性、可行性、输入、输出。
算法的设计目标：正确性，可读性，健壮性，高效率与低存储量需求。

算法和程序十分相似，但又有区别。程序不一定具有有穷性，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。

1.2.2. 算法的时间复杂度

如何计算：
1. 找到一个基本操作（最深层循环)
2. 分析该基本操作的执行次数x与问题规模n的关系 x = f ( n ) x=f(n) x=f(n)
3. x的数量级 O ( x ) O(x) O(x)就是算法时间复杂度 T ( n ) T(n) T(n)： O ( x ) = T ( n ) O(x)=T(n) O(x)=T(n)

常用技巧：

加法规则： O ( f ( n ) ) + O ( g ( n ) ) = O ( m a x ( f ( n ) , g ( n ) ) ) O(f(n))+O(g(n))=O(max(f(n), g(n))) O(f(n))+O(g(n))=O(max(f(n),g(n)))
乘法规则： O ( f ( n ) ) × O ( g ( n ) ) = O ( f ( n ) × g ( n ) ) O(f(n))×O(g(n))=O(f(n)×g(n)) O(f(n))×O(g(n))=O(f(n)×g(n))

“常对幂指阶”

O ( 1 ) next = s; return true; }

时间复杂度：

最好时间复杂度： O ( 1 ) O(1) O(1)
最坏时间复杂度： O ( n ) O(n) O(n)

平均时间复杂度： O ( n ) O(n) O(n)

除非特别声明，否则之后的代码都默认为带头结点！

指定结点的后插操作：

typedef struct LNode{        
    ElemType data;        
    struct LNode *next;
}LNode, *LinkList;
// 在结点p后插入元素e
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->next = p->next;  
    p->next = s;     
    return true;
}
// 按位序插入的函数中可以直接调用后插操作
bool ListInsert(LinkList &L, int i, ElemType e){  
    if(i 
        //如果ilengh, p最后会等于NULL   
        p = p-next;        
        j++;       
    }       
    return InsertNextNode(p, e)
}

时间复杂度： O ( 1 ) O(1) O(1)

指定结点的前插操作：

如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对q进行后插操作；

如果不传入头指针，可以在指定结点p后插入一个结点s，并交换两个结点所保存的数据，从而变相实现指定结点的前插操作。

typedef struct LNode{     
    ElemType data;      
    struct LNode *next;
}LNode, *LinkList;
// 在结点p前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){  
    if(p==NULL)      
        return false;  
    LNode *s = (LNode *)malloc(sizeof(LNode));  
    // 内存不足分配失败       
    if(s==NULL)       
        return false;    
    // 将s插入结点p之后    
    s->next = p->next;   
    p->next = s;       
    // 交换两个结点中的数据  
    s->data = p->data;   
    p->data = e;       
    return true;
}

时间复杂度： O ( 1 ) O(1) O(1)

2.3.4. 单链表的删除

按位序删除：

typedef struct LNode{       
    ElemType data;    
    struct LNode *next;}LNode, *LinkList;
// 删除第i个结点并将其所保存的数据存入e
bool ListDelete(LinkList &L, int i, ElemType &e){      
    if(i   
        //如果ilengh，p和p的后继结点会等于NULL        
        p = p-next;            
        j++;      
    }       
    if(p==NULL)       
        return false;    
    if(p->next == NULL)        
        return false;    	   
    //令q暂时保存被删除的结点   
    LNode *q = p->next;    
    e = q->data;     
    p->next = q->next;      
    free(q)     
    return true;
}

时间复杂度：

最好时间复杂度： O ( 1 ) O(1) O(1)
最坏时间复杂度： O ( n ) O(n) O(n)

平均时间复杂度： O ( n ) O(n) O(n)

删除指定结点：

如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对p进行删除操作；

如果不传入头指针，可以把指定结点p的后继结点q删除，并使结点p保存结点q存储的数据，从而变相实现删除指定结点的操作。但是如果指定结点p没有后继结点，这么做会报错。

// 删除指定结点p
bool DeleteNode(LNode *p){   
    if(p==NULL)           
        return false;     
    LNode *q = p->next; // 令q指向p的后继结点  
    // 如果p是最后一个结点，则q指向NULL，继续执行就会报错  
    p->data = q->data;  
    p->next = q->next;   
    free(q);    
    return true;
}

时间复杂度： O ( 1 ) O(1) O(1)

2.3.5. 单链表的查找

按位查找：

typedef struct LNode{  
    ElemType data;    
    struct LNode *next;
}LNode, *LinkList;
// 查找指定位序i的结点并返回
LNode * GetElem(LinkList L, int i){   
    if(i   
        p = p-next;     
        j++;      
    }        
    return p;
}
// 封装后的插入操作，在第i个位置插入元素e，可以调用查询操作和后插操作
bool ListInsert(LinkList &L, int i, ElemType e){  
    if(idata != e){   
        p = p->next;     
    }     
    return p;
}

时间复杂度：

最好时间复杂度： O ( 1 ) O(1) O(1)
最坏时间复杂度： O ( n ) O(n) O(n)

平均时间复杂度： O ( n ) O(n) O(n)

计算单链表长度：

// 计算单链表的长度
int Length(LinkList L){      
    int len=0;       //统计表长  
    LNode *p = L;
    while(p->next != NULL){ 
        p = p->next;      
        len++;       
    }      
    return len;
}

时间复杂度： O ( n ) O(n) O(n)

2.3.6. 单链表的建立

尾插法建立单链表：

// 使用尾插法建立单链表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;
}

时间复杂度： O ( n ) O(n) O(n)

头插法建立单链表：

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;
}

头插法实现链表的逆置：

// 将链表L中的数据逆置并返回
LNode *Inverse(LNode *L){	
    LNode *p, *q;	  
    p = L->next;     //p指针指向第一个结点	  
    L->next = NULL;  //头结点置空       
    // 依次判断p结点中的数据并采用头插法插到L链表中	
    while (p != NULL){		   
        q = p;		  
        p = p->next;	
        q->next = L->next;  
        L->next = q;	
    }	   
    return L;
}

具体解释详见【数据结构】单链表逆置：头插法图解

2.3.7. 双链表

See the source image

**双链表的定义：**双链表也是链表的一种。双链表的每个数据节点中都有两个指针，分别指向前驱节点和后继结点。

双链表的实现：

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;       
    InitDLinkList(L);       
    ...
}
// 判断双链表是否为空
bool Empty(DLinklist L){   
    if(L->next == NULL)   
        return true;      
    else             
        return false;
}

双链表的后插操作：

typedef struct DNode{     
    ElemType data;       
    struct DNode *prior, *next;
}DNode, *DLinklist;
// 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){ 
    if(p==NULL || s==NULL)  
        return false;         
    s->next = p->next;      
    // 判断结点p之后是否有后继结点  
    if (p->next != NULL)   
        p->next->prior = s; 
    s->prior = p;   
    p->next = s;     
    return true;
}

双链表的前插操作、按位序插入操作都可以转换成后插操作

双链表的删除操作：

// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){   
    if(p==NULL)           
        return false;   
    // 找到p的后继结点q    
    DNode *q =p->next;   
    if(q==NULL)          
        return false;    
    p->next = q->next;   
    if(q->next != NULL) 
        q->next->prior=p;  
    free(q);     
    return true;
}
// 销毁一个双链表
bool DestoryList(DLinklist &L){ 
    // 循环释放各个数据结点   
    while(L->next != NULL){    
        DeletNextDNode(L);      
        free(L);        
        // 头指针置空  
        L=NULL;     
    }
}

双链表的遍历：

// 向后遍历
while(p!=NULL){    
    // 对结点p做相应处理    
    p = p->next;
}
// 向前遍历
while(p!=NULL){    
    // 对结点p做相应处理 
    p = p->prior;
}
// 跳过头结点的遍历
while(p->prior!=NULL){ 
    //对结点p做相应处理    
    p = p->prior;
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。

2.3.8. 循环链表

**循环链表的定义：**循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

循环单链表的实现：

typedef struct LNode{           
    ElemType data;                  
    struct LNode *next; 
}DNode, *Linklist;
// 初始化循环单链表
bool InitList(LinkList &L){    
    L = (LNode *)malloc(sizeof(LNode));  
    if(L==NULL)             
        return false;    
    // 最后一个结点的next指针指向头结点    
    L->next = L;       
    return true;
}
// 判断循环单链表是否为空
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;
}

循环双链表的实现：

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;    
    // 头结点的prior指针指向最后一个结点，最后一个结点的next指针指向头结点 
    L->prior = L;      
    L->next = 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;
}

循环双链表的插入和删除操作：

// 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){  
    s->next = p->next;   
    //循环双链表不用担心p结点的下一个结点为空   
    p->next->prior = s;  
    s->prior = p;     
    p->next = s;
}
// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){  
    // 找到p的后继结点q       
    DNode *q =p->next;        
    //循环双链表不用担心q结点的下一个结点为空  
    p->next = q->next;    
    q->next->prior=p;    
    free(q);      
    return true;
}

2.3.9. 静态链表

静态链表的定义：用数组的方式实现的链表。分配一整片连续的内存空间，各个结点集中安置，每个结点包括了数据元素和下一个结点的数组下标。

特点：
- 优点：增、删操作不需要大量移动元素。
- 缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！
- 静态链表的定义：
```
#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;
}
```
  第一种是我们更加熟悉的写法，第二种写法则更加侧重于强调 a 是一个静态链表而非数组。
- 静态链表的注意点：
  1. 初始化静态链表时，需要把a[0]的next设为-1，并将空闲结点的next设置为某个特殊值，比如-2。
  2. 按位序查找结点时，从头结点出发挨个往后遍历结点，时间复杂度 O = ( n ) O=(n) O=(n)。
  3. 按位序插入结点的步骤：①找到一个空的结点，存入数据元素；②从头结点出发找到位序为 i-1 的结点；③修改新结点的next 为 -1；④修改 i-1 号结点的next为新结点的下标；

2.3.10. 顺序表和链表的比较

逻辑结构：顺序表和链表都属于线性表，都是线性结构。
存储结构：
- 顺序表：顺序存储
  - 优点：支持随机存取，存储密度高。
  - 缺点：大片连续空间分配不方便，改变容量不方便。
  - 链表：链式存储
    - 优点：离散的小空间分配方便，改变容量方便。
    - 缺点：不可随机存取，存储密度低。
    - 基本操作 - 创建：
      - 顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。
        
        静态分配：静态数组，容量不可改变。
        动态分配：动态数组，容量可以改变，但是需要移动大量元素，时间代价高（使用malloc()、free()）。
        
        链表：只需要分配一个头结点或者只声明一个头指针。
        
        基本操作 - 销毁：
        
        顺序表：修改 Length = 0
        
        静态分配：静态数组——系统自动回收空间。
        动态分配：动态数组——需要手动free()。
        
        链表：依次删除各个结点 free()。
        
        基本操作 - 增/删：
        
        顺序表：插入 / 删除元素要将后续元素后移 / 前移；时间复杂度： O ( n ) O(n) O(n)，时间开销主要来自于移动元素。
        链表：插入 / 删除元素只需要修改指针；时间复杂度： O ( n ) O(n) O(n)，时间开销主要来自查找目标元素。
        
        基本操作 - 查找：
        
        顺序表
        按位查找： O ( 1 ) O(1) O(1)
        按值查找： O ( n ) O(n) O(n)，若表内元素有序，可在 O ( l o g 2 n ) O(log2n) O(log2n) 时间内找到（二分法）
        链表：
        按位查找： O ( n ) O(n) O(n)
        按值查找： O ( n ) O(n) O(n)

三、栈与队列

3.1. 栈

3.1.1. 栈的基本概念

栈是特殊的线性表：只允许在一端进行插入或删除操作，其逻辑结构与普通线性表相同。
栈顶：允许进行插入和删除的一端（最上面的为栈顶元素）。
栈底：不允许进行插入和删除的一端（最下面的为栈底元素）。
空栈：不含任何元素的空表。
特点：后进先出（后进栈的元素先出栈）、LIFO（Last In First Out）。
缺点：栈的大小不可变，解决方法：共享栈。

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;       //声明一个顺序栈(分配空间)
}

顺序栈的初始化：

#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; 
}

共享栈（两个栈共享同一片空间）：

#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. 栈的链式存储实现

链栈的定义：

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。
DestroyQueue(&Q)：销毁队列。销毁并释放队列 Q 所占用的内存空间。
EnQueue(&Q, x)：入队。若队列 Q 未满，将 x 加入，使之成为新的队尾。
DeQueue(&Q, &x)：出队。若队列 Q 非空，删除队头元素，并用 x 返回。
GetHead(Q,&x)：读队头元素。若队列 Q 非空，则将队头元素赋值给 x。
QueueEmpty(Q)：判空。若队列 Q 为空，则返回 true。

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;
}
// 判断队列是否为空
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. 输出受限的双端队列：允许两端插入，一端删除的线性表。
考点：判断输出序列的合法化

例：数据元素输入序列为 1，2，3，4，判断 4! = 24 个输出序列的合法性

栈中合法的序列，双端队列中一定也合法ZS

栈	输入受限的双端队列	输出受限的双端队列
14个合法 ( 1 n + 1 C 2 n n \frac{1}{n+1}C^{n}_{2n} n+11C2nn)	只有 4213 和 4231 不合法	只有 4132 和 4231 不合法

3.3. 栈与队列的应用

3.3.1 栈在括号匹配中的应用

用栈实现括号匹配：
1. 最后出现的左括号最先被匹配（栈的特性——LIFO）。
2. 遇到左括号就入栈。
3. 遇到右括号，就“消耗”一个左括号（出栈）。
匹配失败情况：
1. 扫描到右括号且栈空，则该右括号单身。
2. 扫描完所有括号后，栈非空，则该左括号单身。
3. 左右括号不匹配。

#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   
        // 扫描到左括号，入栈     
        if(str[i] == '(' || str[i] == '[' || str[i] == '{'){    
            Push(S, str[i]);        
        }else{              
            // 扫描到右括号且栈空直接返回   
            if(StackEmpty(S))      
                return false;       
            char topElem;          
            // 用topElem接收栈顶元素   
            Pop(S, topElem);          
            // 括号不匹配           
            if(str[i] == ')' && topElem != '(' ) 
                return false;           
            if(str[i] == ']' && topElem != '[' )  
                return false;   
            if(str[i] == '}' && topElem != '{' )   
                return false;              }   
    }  
    // 扫描完毕若栈空则说明字符串str中括号匹配    
    return StackEmpty(S);
}
     
    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   
    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                 
            // 当栈非空时，判断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;
}
2i(i−1)+j−1,2j(j−1)+i−1,i≥ji2i(i−1)+j−1,2n(n−1),i≥jiT，则返回值>0；若 S=T，则返回值=0；若 S    
    char ch[MAXLEN];   
    int length;
}SString;
// 串的初始化
bool InitString(SString &S){
    S.length = 0;    
    return true;
}
// 求串的长度
int StrLength(SString S){    
    return S.length;
}
// 求主串由位序pos开始len长度的子串存入到串Sub中
bool SubString(SString &Sub, SString S, int pos, int len){ 
    if(pos+len-1  S.length)        
        return false;    
    for(int i=pos; i    
    for(int i=1; i
        if(S.ch[i]!=T.ch[i])       
            return S.ch[i]-T.ch[i]    
    }    
    // 扫描过的所有字符都相同，则长度长的串更大    
    return S.length-T.length;
}
// 定位串T在串S中的位置，若无法定位则返回0
int Index(SString S, SString T){    
    int i=1, n=StrLength(S), m=StrLength(T);    
    SString sub;   //用于暂存数据    
    while(i        
        SubString(sub, S, i, m);        
        if(StrCompare(sub, T)!=0)            
            ++i;        
        else            
            return i;
    }
    return 0;	
}
void test{    
    SString S;    
    InitString(S);    
    ...
}
  
    char *ch;
    int length;
}HString;
bool InitString(HString &S){ 
    S.ch = (char *)malloc(MAXLEN * sizeof(char)); 
    if(S.ch == NULL)      
        return false;  
    S.length = 0;  
    return true;
}
void test{  
    HString S;  
    InitString(S);  
    ...
}
   
    char ch;	//每个结点存1个字符  
    struct StringNode *next;
}StringNode, *String;
   
    int k=1;    
    int i=k, j=1;  
    while(i    
        if(S.ch[i] == T.ch[j]){     
            ++i; ++j; 
        }else{        
            k++; i=k; j=1; 
        }   
    }   
    if(jT.length) 
        return k;   
    else       
        return 0;
}
 
    int i=1, j=0;  
    next[1]=0;  
    while(i   
        if(j==0 || T.ch[1]==T.ch[j]){ 
            ++i; ++j;      
            next[i]=j;  
        }else      
            j=next[j]; 
    }
}
// KPM算法，求主串S中模式串T的位序，没有则返回0
int Index_KPM(SString S, SString T){   
    int i=1, j=1;  
    int next[T.length+1]; 
    getNext(T, next);  
    while(i  
        if(j==0 || S.ch[i]==T.ch[j]){   
            ++i; ++j;   
        }else   
            j=next[j];   
    }    
    if(jT.length)   
        return i-T.length;  
    else
        return 0;
}
int main() {
	SString S={"ababcabcd", 9};
	SString T={"bcd", 3};
	printf("%d ", Index_KPM(S, T));	//输出9
}

    int i=1,j=0;
    nextval[1]=0;
    while(i
        if(j==0 || T.ch[i]==T.ch[j]){
            ++i; ++j;
            if(T.ch[i]!=T.ch[j])
                nextval[i]=j;
            else
                nextval[i]=nextval[j];
        }else
            j=nextval[j];
    }
}
  
    ElemType value; //结点中的数据元素  
    bool isEmpty;	//结点是否为空
}
//初始化树T
bool initTree(TreeNode T[]){  
    for(int i=0; i  
        T[i].isEmpty=true; 
    }  
    return true;
}
void test(){   
    struct TreeNode T[MaxSize];  
    initTree(T);
}
  
    ElemType data;	
    struct BiTNode *lchild, *rchild;	
}BiTNode, *BiTree;
//初始化
bool initTree(BiTree &root){
    root = (BiTree)malloc(sizeof(BiTNode));   
    if(root == NULL)     
        return false;
    root-lchild = NULL; 
    root-rchild = NULL;
    return true;
}
void test{  
    BiTree root = NULL; 	
    initTree(root);
    ...
}
  
    ElemType data;  
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
// 先序遍历
void PreOrder(BiTree T){  
    if(T!=NULL){     
        PreOrder(T-lchild);   
        PreOrder(T-rchild); 
        visit(T); 
    }
}
// 中序遍历
void InOrder(BiTree T){ 
    if(T!=NULL){      
        InOrder(T->lchild);  
        visit(T);     
        InOrder(T->rchild);    
    }
}
// 后序遍历
void PostOrder(BiTree T){  
    if(T!=NULL){       
        PostOrder(T->lchild);  
        PostOrder(T->rchild);  
        visit(T);  
    }
}
// 应用：求树的深度
int treeDepth(BiTree T){  
    if(T == NULL){  
        return 0;  
    }else{      
        int l = treeDepth(T->lchild); 
        int r = treeDepth(T->rchild); 
        return l>r ? l+1 r+1;  
    }
}

5.3.2. 二叉树的层序遍历

算法思想：

初始化一个辅助队列
根结点入队
若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
重复第三步直至队列为空

代码实现：

// 二叉树结点
typedef struct BiTNode{  
    char data;   
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
// 链式队列结点
typedef struct LinkNode{ 
    BiTNode *data;   
    struct 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. 层序+中序遍历序列
由前序+中序遍历序列构造二叉树：由前序遍历的遍历顺序（根节点、左子树、右子树）可推出根节点，由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。
由后序+中序遍历序列构造二叉树：由后序遍历的遍历顺序（左子树、右子树、根节点）可推出根节点，由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。
由层序+中序遍历序列构造二叉树：由层序遍历的遍历顺序（层级遍历）可推出根节点，由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。

5.3.4. 线索二叉树的概念

使用链式存储二叉树如何找到指定结点 p 在中序遍历序列中的前驱和后继？

答：从根节点出发，重新进行一次中序遍历，指针 q 记录当前访问的结点，指针 pre 记录上一个被访问的结点。当 q = = p q==p q==p 时，pre 为 q 的前驱结点；当 p r e = = p pre==p pre==p 时，q 为 p 的后继结点。

缺点：找前驱、后继很不方便；遍历操作必须从根结点开始。
n 个结点的二叉树，有 n+1 个空链域，可用来记录前驱、后继的信息。指向前驱、后继的指针被称为“线索”，形成的二叉树被称为线索二叉树。

中序线索二叉树

线索二叉树的结点在原本二叉树的基础上，新增了左右线索标志 tag。当 tag == 0 时，表示指针指向孩子；当 tag == 1 时，表示指针是“线索”。
```
// 线索二叉树的结点
typedef struct ThreadNode{ 
    ElemType data;   
    struct ThreadNode *lchild, *rchild; 
    int ltag, rtag;	//左、右线索标志
}
```
中序线索二叉树的存储：

先序线索二叉树的存储：

后序线索二叉树的存储：

5.3.5. 二叉树的线索化

中序线索化：

typedef struct ThreadNode{
    ElemType data;  
    struct ThreadNode *lchild, *rchild;   
    int ltag, rtag;
}ThreadNode, *ThreadTree;
// 中序遍历线索化二叉树
void InThread(ThreadTree &p, ThreadTree &pre) {
	if (p != NULL) {
		InThread(p->lchild, pre);
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL) {
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
		InThread(p->rchild, pre);
	}
}
// 创建线索二叉树T
void CreateInThread(ThreadTree T) {
	ThreadNode *pre = NULL;
	if (T != NULL) {
		InThread(T, pre);
		pre->rchild = NULL;
		pre->rtag = 1;
	}
}

先序线索化：

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree;
// 先序遍历线索化二叉树
void PreThread(ThreadTree &p, ThreadTree &pre){
    if (p != NULL) {
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL) {
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
        PreThread(p->lchild, pre);
		PreThread(p->rchild, pre);
	}
}
// 创建线索二叉树
void CreatePreThread(ThreadTree T){
    ThreadNode *pre = NULL;
	if (T != NULL) {
		PreThread(T, pre);
		pre->rchild = NULL;
		pre->rtag = 1;
	}
}

后序线索化：

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree;
// 后序遍历线索二叉树
void PostThread(ThreadTree &p, ThreadTree &pre){
    PostThread(p->lchild, pre);
	PostThread(p->rchild, pre);
    if (p != NULL) {
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL) {
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
	}
}
// 后序线索化二叉树T
void CreatePostThread(ThreadTree T){
    ThreadNode *pre = NULL;
	if (T != NULL) {
		PostThread(T, pre);
		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：
1. 若 p 有左孩子，则先序后继为左孩子；
2. 若 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：
1. 若 p 有右孩子，则后序前驱为右孩子；
2. 若 p 没有右孩子，则后续前驱为右孩子。

后序线索二叉树找到指定结点 * p 的后序后继 next：

前提：改用三叉链表，可以找到结点 * p 的父节点。
如果能找到 p 的父节点，且 p 是右孩子：p 的父节点即为其后继；
如果能找到 p 的父节点，且 p 是左孩子，其右兄弟为空：p 的父节点即为其后继；
如果能找到 p 的父节点，且 p 是左孩子，其右兄弟非空：p 的后继为右兄弟子树中第一个被后序遍历的结点；
如果 p 是根节点，则 p 没有后序后继。

5.4. 树和森林

5.4.1. 树的存储结构

**双亲表示法（顺序存储）：**每个结点中保存指向双亲的“指针”。

#define MAX_TREE_SIZE 100
// 树的结点
typedef struct{
    ElemType data;
    int parent;
}PTNode;
// 树的类型
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int n;	//结点数量
}PTree;

孩子表示法（顺序+链式存储）：

#define MAX_TREE_SIZE 100
struct CTNode{
    int child;	//孩子结点在数组中的位置
    struct CTNode *next;	//下一个孩子
}
typedef struct{
    ElemType data;
    struct CTNode *firstChild;	//第一个孩子
}CTBox;
typedef struct{
    CTBox node[MAX_TREE_SIZE];
    int n,r;	//结点数和根的位置
}CTree;

**孩子兄弟表示法（链式存储）：**用孩子兄弟表示法可以将树转换为二叉树的形式。

//孩子兄弟表示法结点
typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild, *nextsibling;	//第一个孩子和右兄弟结点
}CSNode, *CSTree;

**森林和二叉树的转换：**森林是m（m≥0）棵互不相交的树的集合，可以将森林中的树看做一棵树中的兄弟结点，再使用孩子兄弟表示法将其转换为二叉树。

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)
            PreOrder(T);
        visit(R);
    }
}

树的后根遍历序列与这棵树相应二叉树的中序序列相同。

树的层次遍历（用队列实现）：

若树非空，则根节点入队；
若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队；
重复第二步直到队列为空

**森林的先序遍历：**若森林为非空，则按如下规则进行遍历：

访问森林中第一棵树的根结点。
先序遍历第一棵树中根结点的子树森林。
先序遍历除去第一棵树之后剩余的树构成的森林

森林的先序遍历效果等同于依次对各个树进行先根遍历，等同于对二叉树的先序遍历。

**森林的中序遍历：**若森林为非空，则按如下规则进行遍历：

中序遍历森林中第一棵树的根结点的子树森林。
访问第一棵树的根结点。
中序遍历除去第一棵树之后剩余的树构成的森林。

森林的中序遍历效果等同于依次对各个树进行后根遍历，等同于对二叉树的中序遍历。

5.5. 应用

5.5.1. 二叉排序树

二叉排序树，又称二叉查找树（BST，Binary Search Tree）。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
1. 左子树上所有结点的关键字均小于根结点的关键字；
2. 右子树上所有结点的关键字均大于根结点的关键字；
3. 左子树和右子树又各是一棵二叉排序树。
即：左子树结点值
二叉排序树的查找：

// 二叉排序树结点
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
// 在二叉排序树中查找值为key的结点（非递归）
BSTNode *BST_Search(BSTree T, int key){
    while(T!=NULL && key!=T->key){
        if(key key)	T=T->lchild;
        else	T=T->rchild;
    }
    return T;
}
// 在二叉排序树中查找值为key的结点（递归实现）
BSTNode *BST_Search(BSTree T, int key){
    if(T==NULL || T->key==key)
    	return T;
    else if(key key)
        return BSTSearch(T->lchild, key);
    else if(key > T->key)
        return BSTSearch(T->rchild, key);
}

**二叉排序树的插入：**若原二叉排序树为空，则直接插入结点；否则，若关键字 k 小于根结点值，则插入到左子树；若关键字 k 大于根结点值，则插入到右子树。

// 在二叉排序树中插入关键字为k的新节点（递归实现）
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(kkey){
        return BST_Insert(T->lchild, k);
    }else
        return BST_Insert(T->rchild, k);
}

二叉排序树的构造：

// 按照str[]中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T, int str[], int n){
    T=NULL;
    int i=0;
    while(i
        BST_Insert(T,str[i]);
        i++;
    }
}

    int key;
    int balance;	//平衡因子
    struct AVLNode *lchild, *rchild;
}AVLNode, *AVLTree;
v1,v2,…,vn}，则用  
       
        
         
         
           ∣ 
          
         
           V 
          
         
           ∣ 
          
         
        
          |V| 
         
        
      ∣V∣ 表示图 G 中顶点的个数，也称图 G 的阶； 
       
        
         
         
           E 
          
         
           = 
          
         
           { 
          
         
           ( 
          
         
           u 
          
         
           , 
          
         
           v 
          
         
           ) 
          
         
           ∣ 
          
         
           u 
          
         
           ∈ 
          
         
           V 
          
         
           , 
          
         
           v 
          
         
           ∈ 
          
         
           V 
          
         
           } 
          
         
        
          E = \{(u, v) | u\in V, v\in V\} 
         
        
      E={(u,v)∣u∈V,v∈V}，用  
       
        
         
         
           ∣ 
          
         
           E 
          
         
           ∣ 
          
         
        
          |E| 
         
        
      ∣E∣ 表示图 G 中边的条数。p注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集。/p /lili p无向图：若 E 是无向边（也称边）的有限集合时，则图 G 为无向图。边是顶点的无序对，记为  
       
        
         
         
           ( 
          
         
           v 
          
         
           , 
          
         
           w 
          
         
           ) 
          
         
        
          (v, w) 
         
        
      (v,w) 或$ (w, v)$，其中 v、w 是顶点。可以说顶点 w 和顶点 v 互为邻接点，边  
       
        
         
         
           ( 
          
         
           v 
          
         
           , 
          
         
           w 
          
         
           ) 
          
         
        
          (v, w) 
         
        
      (v,w) 依附于顶点 w 和 v；或者说边  
       
        
         
         
           ( 
          
         
           v 
          
         
           , 
          
         
           w 
          
         
           ) 
          
         
        
          (v, w) 
         
        
      (v,w) 和顶点 v、w 相关联。/p /lili p有向图：若 E 是有向边（也称弧）的有限集合时，则图 G 为有向图。 弧是顶点的有序对，记为  
       
        
         
         
            
          
         
        
           
         
        
      ，其中 v、w 是顶点，v 称为弧尾，w 称为弧头，称为从顶点 v 到顶点 w 的弧，也称 v邻接到w，或w邻接自v。 
       
        
         
         
            
          
         
           ≠ 
          
         
            
          
         
        
          \ne  
         
        
      =。

简单图：① 不存在重复边； ② 不存在顶点到自身的边。
多重图：图 G 某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 G 为多重图。

度、入度、出度：对于无向图，顶点 v 的度是指依附于该顶点的边的条数，记为 T D ( v ) TD(v) TD(v)。对于有向图，入度是以顶点 v 为终点的有向边的数目，记为 I D ( v ) ID(v) ID(v)；出度是以顶点 v 为起点的有向边的数目，记为 O D ( v ) OD(v) OD(v)。顶点 v 的度等于其入度和出度之和，即 T D ( v ) = I D ( v ) + O D ( v ) TD(v) = ID(v) + OD(v) TD(v)=ID(v)+OD(v)。
路径：顶点 v p v_p vp 到顶点 v q v_q vq 之间的一条路径是指顶点序列 v p v_p vp， v i 1 v_{i1} vi1 ， v i 2 v_{i2} vi2，…， v q v_q vq。
回路：第一个顶点和最后一个顶点相同的路径称为回路或环。
简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度：路径上边的数目。
点到点的距离：从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。
连通、强连通：无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径，则称这两个顶点是强连通的。
连通图：若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。对于 n 个顶点的无向图 G，若 G 是连通图，则最少有 n-1 条边；若G是非连通图，则最多可能有 C n − 1 2 \mathrm{C}_{n-1}^2 Cn−12 条边。
子图、生成子图：设有两个图 G = ( V , E ) G = (V, E) G=(V,E) 和 G ′ = ( V ′ , E ′ ) G'=(V',E') G′=(V′,E′)，若 V ′ V' V′ 是 V V V 的子集，且 E ′ E' E′ 是 E E E 的子集，则称 G ′ G' G′ 是 G G G 的子图。若有满足 V ( G ′ ) = V ( G ) V(G') = V(G) V(G′)=V(G) 的子图 G’，则称其为 G 的生成子图。

连通分量：无向图中的极大连通子图称为连通分量。

强连通分量：有向图中的极大强连通子图称为有向图的强连通分量。

生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。

生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林。

边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图：边上带有权值的图称为带权图，也称网。
带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。
无向完全图：无向图中任意两个顶点之间都存在边。若无向图的顶点数 ∣ V ∣ = n |V|=n ∣V∣=n，则 ∣ E ∣ ∈ [ 0 , C n 2 ] |E|∈[0, \mathrm{C}_n^2] ∣E∣∈[0,Cn2] = [ 0 , n ( n – 1 ) / 2 ] [0, n(n–1)/2] [0,n(n–1)/2]。
有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧。若有向图的顶点数 ∣ V ∣ = n |V|=n ∣V∣=n，则 ∣ E ∣ ∈ [ 0 , 2 C n 2 ] = [ 0 , n ( n – 1 ) ] |E|∈[0, 2\mathrm{C}_n^2]=[0, n(n–1)] ∣E∣∈[0,2Cn2]=[0,n(n–1)]。
稀疏图、稠密图：边数很少的图称为稀疏图，反之称为稠密图。

6.2. 图的存储

6.2.1. 邻接矩阵

邻接矩阵存储无向图、有向图：

#define MaxVertexNum 100	//顶点数目的最大值
typedef struct{
    char Vex[MaxVertexNum];		//顶点表
    int Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵，边表
    int vexnum,arcnum;			//图的顶点数和边数
}MGraph;

度：第 i 个结点的度 = 第 i 行（或第 i 列）的非零元素个数；

出度：第 i 行的非零元素个数；

入度：第 i 列的非零元素个数。

邻接矩阵法存储带权图：

#define MaxVertexNum 100		//顶点数目的最大值
#define INFINITY 2147483647;	//表示“无穷”
typedef char VertexType;	//顶点数据类型
typedef int EdgeType;		//边数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];	//顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];	//边的权值
    int vexnum,arcnum;		//图的当前顶点数和弧数
}MGraph;

性能分析：

空间复杂度： O ( ∣ V ∣ 2 ) O(|V|^2 ) O(∣V∣2) ，只和顶点数相关，和实际的边数无关。
适合用于存储稠密图。
无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区或者下三角区）。

**邻接矩阵的性质：**设图 G 的邻接矩阵为 A（矩阵元素为 0 或 1），则 A n A^n An 的元素 A n [ i ] [ j ] A^n[i][j] An[i][j] 等于由顶点 i 到顶点 j 的长度为 n 的路径的数目。

6.2.2. 邻接表

邻接表存储存储无向图、有向图：

#define MVNum 100							//最大顶点数
typedef struct ArcNode{                		//边/弧 
    int adjvex;                             //邻接点的位置 
    struct ArcNode *next;	      			//指向下一个表结点的指针 
}ArcNode;
typedef struct VNode{ 
    char data;                    	        //顶点信息 
    ArcNode *first;         				//第一条边/弧 
}VNode, AdjList[MVNum];                 	//AdjList表示邻接表类型 
typedef struct{ 
    AdjList vertices;              			//头结点数组
    int vexnum, arcnum;     				//当前的顶点数和边数 
}ALGraph;

对比邻接矩阵：

	邻接表	邻接矩阵
空间复杂度	无向图：$O(	V
适用场景	存储稀疏图	存储稠密图
表示方式	不唯一	唯一
计算度、入度、出度	计算有向图的度、入度不方便，其余很方便	遍历对应行或列
找相邻的边	找有向图的入边不方便，其余很方便	遍历对应行或列

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

十字链表存储有向图：

#define MAX_VERTEX_NUM 20	//最大顶点数量
typedef struct ArcBox{		//弧结点
	int tailvex, headvex;	//弧尾，弧头顶点编号（一维数组下标）
	struct ArcBox *hlink, *tlink;	//弧头相同、弧尾相同的下一条弧的链域
	InfoType info;			//权值
}ArcBox;
typedef struct VexNode{		//顶点结点
	VertexType data;		//顶点数据域
	ArcBox *firstin, *firstout;	//该顶点的第一条入弧和第一条出弧
}VexNode;
typedef struct{				//有向图
	VexNode xlist[MAX_VERTEX_NUM];	//存储顶点的一维数组
	int vexnum, arcnum;	//有向图的当前顶点数和弧数
}OLGraph;

邻接多重表存储无向图：

#define MAX_VERTEX_NUM 20	//最大顶点数量
struct EBox{				//边结点
	int i,j; 				//该边依附的两个顶点的位置（一维数组下标）
	EBox *ilink,*jlink; 	//分别指向依附这两个顶点的下一条边
	InfoType info; 			//边的权值
};
struct VexBox{
	VertexType data;
	EBox *firstedge; 		//指向第一条依附该顶点的边
};
struct AMLGraph{
	VexBox adjmulist[MAX_VERTEX_NUM];
	int vexnum,edgenum; 	//无向图的当前顶点数和边数
};

四种存储方法比较：

	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	$O(	V	^2)$	无向图：$O(
找相邻边	遍历对应行或列	找有向图的入边必须遍历整个邻接表	很方便	很方便
删除顶点或边	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点都不方便	很方便	很方便
适用场景	存储稠密图	存储稀疏图	存储有向图	存储无向图
表示方式	唯一	不唯一	不唯一	不唯一

6.2.4. 图的基本操作

Adjacent(G, x, y)：判断图 G 是否存在边或 ( x , y ) (x, y) (x,y)。
Neighbors(G, x)：列出图 G 中与结点 x 邻接的边。
InsertVertex(G, x)：在图 G 中插入顶点 x 。
DeleteVertex(G, x)：从图 G 中删除顶点 x。
AddEdge(G, x, y)：若无向边 ( x , y ) (x, y) (x,y) 或有向边不存在，则向图 G 中添加该边。
RemoveEdge(G, 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) (x,y) 或对应的权值。
Set_edge_value(G, x, y, v)：设置图 G 中边 ( x , y ) (x, y) (x,y) 或对应的权值为 v。

6.3. 图的遍历

6.3.1. 广度优先遍历

⼴度优先遍历（Breadth-First-Search, BFS）要点：
1. 找到与⼀个顶点相邻的所有顶点；
2. 标记哪些顶点被访问过；
3. 需要⼀个辅助队列。
广度优先遍历用到的操作：
1. FirstNeighbor(G, x)：求图 G 中顶点 x 的第⼀个邻接点，若有则返回顶点号；若 x 没有邻接点或图中不存在 x，则返回 -1。
2. NextNeighbor(G, x, y)：假设图 G 中顶点 y 是顶点 x 的⼀个邻接点，返回除 y 之外顶点 x 的下⼀个邻接点的顶点号，若 y 是 x 的最后⼀个邻接点，则返回 -1。
广度优先遍历伪代码：

bool visited[MAX_VERTEX_NUM];	//访问标记数组
// 对图G进行广度优先遍历
void BFSTraverse(Graph G){
    for(i=0; i
    visit(G,v);					//访问图G的结点v
    visited[v]=TREE;			//标记v已被访问
    EnQueue(Q,v);				//顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);			//队列头节点出队并将头结点的值赋给v
        for(w=FirstNeighbor(G,v); w=0; w=NextNeighbor(G,v,w)){
            //检测v的所有邻结点
            if(!visited[w]){
                visit(w);
                visited[w]=TREE;
                EnQueue(Q,w);
            }
        }
    }
}

    for(v=0; v	//初始化标记数组
        visited[v]=FALSE;
    }
    for(v=0; v
        if(!visited[v])
            DFS(G,v);
    }
}
// 从顶点v出发深度优先遍历图G
void DFS(Graph G,int v){
    visit(G,v);
    visited[v]=TREE;
    for(w=FirstNeighbor(G,v);w=0;w=NextNeighbor(G,v)){
        if(!visited[w])
            DFS(G,v);
    }
}

    for(i=0; i
        visited[i]=FALSE;				//初始化访问标记数组
        d[i]=MAX_LENGTH;				//初始化路径长度
        path[i]=-1;						//初始化最短路径记录
    }
    InitQueue(Q);						//初始化辅助队列
    d[u]=0;
    visites[u]=TREE;
    EnQueue(Q,u);
    while(!isEmpty[Q]){					//BFS算法主过程
        DeQueue(Q,u);					//队头元素出队并赋给u
        for(w=FirstNeighbor(G,u);w=0;w=NextNeighbor(G,u,w)){
            if(!visited[w]){
                d[w]=d[u]+1;
                path[w]=u;
                visited[w]=TREE;
                EnQueue(Q,w);			//顶点w入队
            }
        }
    }
}

    for(int i=0; i		//初始化数组
        final[i]=FALSE;
        dist[i]=G.edge[u][i];
        if(G.edge[u][i]==MAX_LENGTH || G.edge[u][i] == 0)
            path[i]=-1;
        else
            path[i]=u;
        final[u]=TREE;
    }
 
  	for(int i=0; i
        int MIN=MAX_LENGTH;
        int v;
		// 循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点v
        for(int j=0; j
	        if(final[j]!=TREE && dist[j]
 	            MIN = dist[j];
                v = j;
            }
        }
        final[v]=TREE;
        // 检查所有邻接⾃v的顶点路径长度是否最短
        for(int j=0; j
	        if(final[j]!=TREE && dist[j]dist[v]+G.edge[v][j]){
            	dist[j] = dist[v]+G.edge[v][j];
                path[j] = v;
            }
        }
	}
}

	int i,j,k;
    // 初始化部分
	for(i=0;i
		for(j=0;j
			dist[i][j]=G.Edge[i][j];		
			path[i][j]=-1;
		}
	}
    // 算法核心部分
	for(k=0;k
		for(i=0;i
			for(j=0;j
	   	    	if(dist[i][j]dist[i][k]+dist[k][j]){
	   		    	dist[i][j]=dist[i][k]+dist[k][j];
	   		    	path[i][j]=k;
                }
			}
        }
    }
}
				//边表结点
    int adjvex;						//该弧所指向的顶点位置
    struct ArcNode *nextarc;		//指向下一条弧的指针
}ArcNode;
typedef struct VNode{				//顶点表结点
    VertexType data;				//顶点信息
    ArcNode *firstarc;				//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;				//邻接表
    int vexnum,arcnum;				//图的顶点数和弧数
}Graph;								//Graph是以邻接表存储的图类型
// 对图G进行拓扑排序
bool TopologicalSort(Graph G){
    InitStack(S);					//初始化栈，存储入度为0的顶点
    for(int i=0;i
        if(indegree[i]==0)
            Push(S,i);				//将所有入度为0的顶点进栈
    }
    int count=0;					//计数，记录当前已经输出的顶点数
    while(!IsEmpty(S)){				//栈不空，则存入
        Pop(S,i);					//栈顶元素出栈
        print[count++]=i;			//输出顶点i
        for(p=G.vertices[i].firstarc;p;p=p=-nextarc){
            //将所有i指向的顶点的入度减1，并将入度为0的顶点压入栈
            v=p-adjvex;
            if(!(--indegree[v]))
                Push(S,v);			//入度为0，则入栈
        }
    }
    if(countve(j)+Weight(vj,vk)}， 
        
         
          
           
           
             v 
            
           
             j 
            
           
          
         
           v_j 
          
         
       vj 为  
        
         
          
           
           
             v 
            
           
             k 
            
           
          
         
           v_k 
          
         
       vk 的任意前驱。vl(j)−Weight(vk,vj)}， 
        
         
          
           
           
             v 
            
           
             j 
            
           
          
         
           v_j 
          
         
       vj 为  
        
         
          
           
           
             v 
            
           
             k 
            
           
          
         
           v_k 
          
         
       vk 的任意后继。				//查找表的数据结构（顺序表）
    ElemType *elem;			//动态数组基址
    int TableLen;			//表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0;i				//查找表的数据结构（顺序表）
    ElemType *elem;			//动态数组基址
    int TableLen;			//表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;
    int i;
    for(i=ST.TableLen;ST.elem[i]!=key;--i)
    // 查找成功返回数组下标，否则返回0
	    return i;
}

    ElemType *elem;
    int TableLen;
}SSTable;
// 折半查找
int Binary_Search(SSTable L,ElemType key){
    int low=0,high=L.TableLen,mid;
    while(low
        mid=(low+high)/2;
        if(L.elem[mid]==key)
            return mid;
        else if(L.elem[mid]key)
            high=mid-1;					//从前半部分继续查找
        else
            low=mid+1;					//从后半部分继续查找
    }
    return -1;
}

    ElemType maxValue;
    int low,high;
}Index;
// 顺序表存储实际元素
ElemType List[100];

    int i,j,temp;
    for(i=1; i
        if(A[i]    	//如果A[i]关键字小于前驱
            temp=A[i];  
            for(j=i-1; j=0 && A[j]temp; --j)
                A[j+1]=A[j];    //所有大于temp的元素都向后挪
            A[j+1]=temp;
        }
    }
}

    int i,j;
    for(i=2; i
        if(A[i]
            A[0]=A[i];     	//复制为哨兵，A[0]不放元素
            for(j=i-1; A[0]
    LNode *p=L-next, *pre;
    LNode *r=p-next;
    p-next=NULL;
    p=r;
    while(p!=NULL){
        r=p-next;
        pre=L;
        while(pre-next!=NULL && pre-next-data 
    int i,j,low,high,mid;
    for(i=2; i
        A[0]=A[i];    		     	 //将A[i]暂存到A[0]
            low=1; high=i-1;
        while(low            //折半查找
            mid=(low+high)/2;
            if(A[mid]A[0])
                high=mid-1;
            else
                low=mid+1;
        }
        for(j=i-1; jhigh+1; --j)
            A[j+1]=A[j];
        A[high+1]=A[0];
    }
}

    int d,i,j;
    for(d=n/2; d=1; d=d/2){  	//步长d递减
        for(i=d+1; i
            if(A[i]
                A[0]=A[i];		//A[0]做暂存单元，不是哨兵
                for(j=i-d; j0 && A[0]
    int temp=a;
    a=b;
    b=temp;
}
// 对A[]数组共n个元素进行冒泡排序
void BubbleSort(int A[], int n){
    for(int i=0; i
        bool flag = false; 			//标识本趟冒泡是否发生交换
        for(int j=n-1; ji; j--){
            if(A[j-1]A[j]){
                swap(A[j-1],A[j]);
                flag=true;
            }
        }
        if(flag==false)
            return;       //若本趟遍历没有发生交换，说明已经有序
    }
}

    int pivot = A[low];
    while(low
        while(low
    if(low
        int pivotpos = Partition(A, low, high);  //划分
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}

    int temp = a;
    a = b;
    b = temp;
}
// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n){
    for(int i=0; i          	//一共进行n-1趟，i指向待排序序列中第一个元素
        int min = i;
        for(int j=i+1; j		//在A[i...n-1]中选择最小的元素
            if(A[j]
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
        p=s=h; q=r=NULL;
        while(p!=NULL){
            if(p-datas-data){
                s=p; r=q;
            }
            q=p; p=p-next;
        }
        if(s==h)
            h=h-next;
        else
            r-next=s-next;
        s-next=L; L=s;
    }
}

    for(int i=len/2; i0; i--) 		//从后往前调整所有非终端结点
        HeadAdjust(A, i, len);
}
// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
    for(int i=2*k; i	//沿k较大的子结点向下调整
        if(i
            A[k] = A[i];			//将A[i]调整至双亲结点上
            k=i;					//修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0]
}
// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}
// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
    BuildMaxHeap(A, len);         	//初始建立大根堆
    for(int i=len; i1; i--){      	//n-1趟的交换和建堆过程
        swap(A[i], A[1]);
        HeadAdjust(A,1,i-1);
    }
}

    int i,j,k;
    for(k=low; k
        if(B[i]
    if(low
        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A,low,mid,high);     //归并
    }
}