devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：小惠珠哦 | 2024-07-30 14:06:55

赞

踩

王道数据结构笔记

一、绪论

本章内容只是数据结构概述，并不在考研大纲范围内。

1.1 数据结构的基本概念

  1. 数据：是信息的载体，是描述客观事物属性的数、字符以及所有输入到计算机中并被计算机程序识别和处理的符号的集合。（计算机程序加工的原料）
  2. 数据元素：数据的基本单位，由若干数据项组成。
  3. 数据项：构成数据元素的不可分割的最小单位。
  4. 数据对象：具有相同性质的数据元素的集合，是数据的一个子集。
  5. 数据类型：是一个值的集合和定义在此集合上的一组操作的总称。
    1. 原子类型：其值不可再分的数据类型
    2. 结构类型：其值可以再分解为若干成分（分量）的数据类型
    3. 抽象数据类型（ADT）：指一个数学模型以及定义在该模型上的一组操作，只取决于它的一组逻辑特性，用一个三元组表示（D, S, P）。它通常是对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。
  6. 数据结构：指互相之间存在着一种或多种特定关系的数据元素的集合，包括逻辑结构，存储结构和对数据的运算。（数据元素都不是孤立存在的）。
  7. 逻辑结构：是指数据元素之间的逻辑关系，与数据的存储无关。分为线性结构和非线性结构，通常有线性表、集合、树和图。（后三者都是非线性结构）
  8. 存储结构（物理结构）：是指数据结构在计算机中的表示（又称为映像）。包括数据元素的表示和关系的表示，通常由四种基本的存储方法实现：
    1. 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
    2. 链式存储：不要求逻辑上相邻的元素在物理位置也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系，其优点是不会出现碎片现象，能充分利用所有的存储单元；缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存储。
    3. 索引存储：在存储元素信息的同时还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。其优点是检索速度快；缺点是附加的索引表额外占用存储空间。另外增加和删除数据时也要修改索引表，因而又会花费较多的时间。
    4. 散列存储（Hash）：根据元素的关键字直接计算出该元素的存储地址，其优点是检索、增加和删除结点的操作都很快；缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
  9. 数据的运算：包括运算的定义和实现。
    1. 运算的定义是针对逻辑结构的，指出运算的功能；
    2. 运算的实现是针对存储结构的，指出运算的具体操作步骤。

1.2 算法和算法评价

1.2.1 算法的基本概念

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

1.2.2 算法效率的度量

1、时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。

  1. 先找一个基本操作（最底层循环）
  2. 该基本操作的执行次数的数量级即该算法的时间复杂度

T(n)=O(f(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(1)<O(log2​n)<O(n)<O(nlog2​n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

判断时间复杂度的方法：

1、循环主体的变量参与循环条件的判断：在用于递推实现的算法中，首先找出基本运算的执行次数x与问题规模n之间的关系式，解得x=f(n)，f(n)最高次幂为k，则算法的时间复杂度为O(n^k)。

2、循环主体中的变量与循环条件无关：此类题可采用数学归纳法或直接累计循环次数。多层循环时从内到外分析，忽略单步语句、条件判断语句、只关注主体语句的执行次数。此类问题又分为递归程序和非递归程序：

  • 递归程序：一般使用公式进行递推。时间复杂度分析如下：
            T(n)=1+T(n-1)=1+1+T(n-2)=...=n-1+T(1)
  • 非递归程序：分析较为简单可以直接累计次数。
2、空间复杂度

算法的空间复杂度S(n)定义为该算法所需的存储空间，它是问题规模n的函数，记为

S(n)=O(g(n))

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。

算法原地工作：是指算法所需的辅助空间为常量，即O(1)

二、线性表

本章很有可能考察算法题哦，但是因为其代码量较小，故而需要追求最优的性能（思想）。

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

2.1.1 线性表的定义

  1. 线性表：是具有相同数据类型的 n 个数据元素的有限序列。
  2. 特点：
    1. 表中元素的个数有限。
    2. 表中元素具有逻辑的顺序性，表中元素有其先后次序。
    3. 表中元素都是数据元素，每个元素都是单个元素。
    4. 表中元素的数据类型相同，这意味着每个元素占有相同大小的存储空间。
    5. 表中元素具有抽象性，即讨论元素间的逻辑关系，而不考虑元素究竟想要表达什么内容。
  3. 线性表的存储结构：
    1. 顺序存储结构：顺序表
    2. 链式存储结构：链表

2.1.2 线性表的基本操作

  • InitList(&L)：初始化表。构造一个空的线性表 L，并分配内存空间。
  • Length(L)：求表长。返回线性表 L 的长度，即L中数据元素的个数。
  • LocateElem(L, e)：按值查找操作。在表 L 中查找具有给定关键字值的元素。
  • GetElem(L, i)：按位查找操作。获取表 L 中第 i 个位置的元素的值。
  • ListInsert(&L, i, &e)：插入操作。在表 L 的第 i 个位置插入指定元素 e 。
  • ListDelete(&L, i, &e)：删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。
  • PrintList(L)：打印表（输出操作）。按顺序输出线性表 L 的所有元素值。
  • Empty(L)：判空操作。若 线性表L为空表，则返回 true，否则返回 false。
  • DestroyList(&L)：销毁操作。销毁线性表，并释放线性表 L 占用的内存空间。

2.2 线性表的顺序表示（顺序表）

2.2.1 顺序表的定义

  1. 顺序表：是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。
  2. 特点：
    1. 逻辑顺序与物理顺序相同。
    2. 随机访问，即可通过首地址和元素序号可以在在O(1) 时间内找到第 i 个元素。
    3. 存储密度高，每个节点只存储数据元素。
    4. 顺序存储分配需要一段连续的存储空间，不够灵活。
    5. 元素的插入和删除需要移动大量的元素，插入操作平均需要移动n/2个元素，删除操作平均需要移动(n-1)/2个元素。
  3. 代码实现

静态实现：

  1. #define MaxSize                //定义线性表的最大长度
  2. typedef struct{
  3.     ElemType data[MaxSize];    //顺序表的元素
  4.     int length;                //顺序表的当前长度
  5. }SqList;                       //顺序表的类型定义

动态实现：

  1. #define InitSize 10    //表长度的初始定义
  2.  
  3. typedef struct {
  4. 	ElemType *data;    //指示动态分配数组的指针 
  5. 	int MaxSize;       //顺序表的最大容量
  6. 	int length;        //顺序表的当前长度 
  7. }SeqList;              //动态分配数组顺序表的类型定义

C++的初始动态分配语句为：

L.data=new ElemType[InitSize];

2.2.2 顺序表上基本操作的实现

1.顺序表的初始化

静态分配和动态分配的初始化操作是不同的，静态分配在声明一个顺序表时，就已经为其分配了数据空间，因此初始化时只需要将顺序表当前的长度设为0。

  1. //SqList L;                //声明一个顺序表
  2. void InitList(SqList &L) {
  3. 	L.length = 0;          //顺序表初始长度为0 
  4. }

动态分配的初始化为顺序表分配一个预定义大小的数组空间，并将顺序表的当前长度设为0。 

  1. void InitList(SqList &L) {
  2. 	L.data = (int *)malloc(InitSize * sizeof(int));//分配存储空间
  3. 	L.length = 0;            //顺序表的初始长度为0
  4. 	L.MaxSize = InitSize;    //初始存储容量
  5. }

2.插入操作

  1. bool ListInsert(SqList &L, int i, int e) {
  2. 	if (i < 1 || i > L.length+1)         //判断i的范围是否有效 
  3. 		return false;
  4. 	if (L.length >= MaxSize)             //判断存储空间是否已满 
  5. 		return false;
  6. 	for (int j = L.length; j >= i; j--)  //将第i个元素之后的元素后移 
  7. 		L.data[j] = L.data[j-1];
  8. 	L.data[i-1] = e;                     //在位置i处放入e 
  9. 	L.length++;                          //线性表长度加1 
  10. 	return true;
  11. }

3.删除操作

  1. bool ListDelete(SqList &L, int i, int &e) {
  2. 	if (i < 1 || i > L.length)           //判断i的范围是否有效
  3. 		return false;
  4. 	e = L.data[i-1];                     //将被删除的元素赋值给e 
  5. 	for (int j = i; j < L.length; j++)   //将第i个位置后的元素前移 
  6. 		L.data[j-1] = L.data[j];
  7. 	L.length--;                          //线性表长度减1
  8. 	return true; 
  9. }

4.按值查找（顺序查找） 

  1. int LocateElem(SqList L, ElemType e) {
  2. 	for (int i = 0; i < L.length; i++)
  3. 		if (L.data[i] == e)
  4. 			return i+1;       //数组下标为i的元素值等于e，返回其位序i+1 
  5. 	return 0;                 //退出循环，说明查找失败
  6. }

（插入、删除、查找）时间复杂度：

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

2.3 线性表的链式表示（单链表）

2.3.1 单链表的定义

是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，除存放自身的信息之外，还需要存放一个指向其后继的指针。

单链表中节点类型的描述如下：

  1. typedef struct LNode{        //定义单链表结点类型
  2.     ElemType data;           //数据域
  3.     struct LNode *next;      //指针域
  4. }LNode, *LinkList;

特点：

  1. 不需要大量连续存储单元，改变容量方便。
  2. 非随机存取。
  3. 需要耗费一定空间存放指针。

实现方式：

  1. 带头结点：写代码更方便。头结点不存储数据，头结点指向的下一个结点才存放实际数据。
  2. 不带头结点：写代码比较麻烦。对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。

2.3.2 单链表上基本操作的实现

1.单链表的初始化

带头结点的单链表在初始化时，需要创建一个头结点，并让头指针指向头结点，头结点的next域初始化为NULL。

  1. //带头结点的单链表的初始化
  2. bool InitList(LinkList &L){      
  3.     L = (LNode *)malloc(sizeof(LNode));//创建头结点 
  4.     if (L == NULL)                     //内存不足，分配失败    
  5.         return false;    
  6.     L->next = NULL;                    //头结点之后暂时还没有结点   
  7.     return true;
  8. }
  9.  
  10. //不带头结点的单链表的初始化
  11. bool InitList(LinkList &L){
  12.     L = NULL;                          //空表，暂时还没有任何结点
  13.     return true;
  14. }
2.求表长操作
  1. int Length(LinkList L){
  2.     int len=0;                //计数变量，初始为0
  3.     LNode *p=L;
  4.     while(p->next!=NULL){
  5.         p=p->next;
  6.         len++;                //每访问一个结点，计数加1
  7.     }
  8.     return len;
  9. }

求表长的时间复杂度是O(n)。另需注意的是，因为单链表的长度是不包括头结点的，因此不带头系结点和带头结点的单链表在求表长操作上会略有不同。 

3.按序号查找结点
  1. LNode * GetElem(LinkList L, int i){   
  2.     if(i<0)            
  3.         return NULL;   
  4.     LNode *p=L;                 //指针p当前扫描的结点
  5.     int j=0;                    //记录当前结点的位序，头结点是第0个结点
  6.     while(p!=NULL && j<i){      //循环找到第i个结点
  7.         p = p->next;     
  8.         j++;      
  9.     }        
  10.     return p;                   //返回第i个结点的指针或NULL
  11. }

该操作的时间复杂度为O(n) 。

4.按值查找结点
  1. LNode * LocateElem(LinkList L, ElemType e){           
  2.     LNode *p = L->next;     
  3.     while(p!=NULL && p->data != e){   //从第一个结点开始查找数据域为e的结点  
  4.         p = p->next;     
  5.     }     
  6.     return p;                         //找到后返回该结点指针，否则返回NULL
  7. }

该操作的时间复杂度为O(n) 。 

5.插入结点操作

1.按位序插入（不带头结点）

  1. bool ListInsert(LinkList &L, int i, ElemType e){          
  2.     if(i<1)//判断i的合法性  
  3.         return false;         
  4.     if(i==1){//需要判断插入的位置是否是第1个
  5.         LNode *s = (LNode *)malloc(size of(LNode));  
  6.         s->data = e;          
  7.         s->next = L;       
  8.         L = s;          //头指针指向新结点   
  9.         return true;      
  10.     }   
  11.     
  12.     //i>1的情况与带头结点一样，唯一区别是j的初始值为1   
  13.     LNode *p = L;       //指针p指向当前扫描到的结点     
  14.     int j = 1;        //当前p指向的是第几个结点   
  15.        
  16.     //循环找到第i-1个结点    
  17.     while(p!=NULL && j<i-1){     //如果i>lengh，p最后会等于NULL    
  18.         p = p->next;             
  19.         j++;      
  20.     }       
  21.  
  22.     if (p == NULL)      //p值为NULL说明i值不合法       
  23.         return false;      
  24.     //在第i-1个结点后插入新结点   
  25.     LNode *s = (LNode *)malloc(sizeof(LNode));  
  26.     s->data = e;      
  27.     s->next = p->next;  
  28.     p->next = s;        
  29.     return true;
  30. }

该操作的时间复杂度为O(n) 。

前插操作是指在某结点的前面插入一个新结点，后插操作的定义刚好与之相反。 

  1.     s->next = p->next;   
  2.     p->next = s;       
  3.     e = p->data;    // 交换两个结点中的数据  
  4.     s->data = p->data;   
  5.     p->data = e;

2.采用头插法建立单链表

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头（头结点之后）。

  1. LinkList List_HeadInsert(LinkList &L){       //逆向建立单链表   
  2.     LNode *s;      
  3.     int x;                                   //设元素类型为整型
  4.     L = (LinkList)malloc(sizeof(LNode));     //创建头结点   
  5.     L->next = NULL;                          //初始为空链表（这步很关键）
  6.     scanf("%d", &x);                         //输入要插入的结点的值（数据域） 
  7.     while(x!=9999){                          //输入9999表示结束     
  8.         s = (LNode *)malloc(sizeof(LNode));  //创建新结点
  9.         s->data = x;                         
  10.         s->next = L->next;      
  11.         L->next = s;                         //将新结点插入表中，L为头指针        
  12.         scanf("%d", &x);                     
  13.     }     
  14.     return L;
  15. }

采用头插法建立单链表时，读入数据的顺序与生成的链表中元素的顺序时相反的。可用来实现链表的逆置。 

  1. // 将链表L中的数据逆置并返回
  2. LNode *List_Inverse(LNode *L){	
  3.     LNode *p, *q;	  
  4.     p = L->next;       //p指针指向第一个结点	  
  5.     L->next = NULL;    //头结点置空       
  6.     while (p != NULL){ //依次判断p结点中的数据并采用头插法插到L链表中	   
  7.         q = p;		  
  8.         p = p->next;	
  9.         q->next = L->next;  
  10.         L->next = q;	
  11.     }	   
  12.     return L;
  13. }

3.采用尾插法建立单链表 

头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一样。若希望两者次序一样，则可以采用尾插法。该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。

  1. LinkList List_TailInsert(LinkList &L){       //正向建立单链表
  2.     int x;			                         //设ElemType为整型int  
  3.     L = (LinkList)malloc(sizeof(LNode));     //建立头结点(初始化空表)     
  4.     LNode *s, *r = L;                        //r为表尾指针    
  5.     scanf("%d", &x);                         //输入要插入的结点的值   
  6.     while(x!=9999){                          //输入9999表示结束     
  7.         s = (LNode *)malloc(sizeof(LNode));    
  8.         s->data = x;           
  9.         r->next = s;           
  10.         r = s;                               //r指针指向新的表尾结点     
  11.         scanf("%d", &x);       
  12.     }    
  13.     r->next = NULL;                          //尾结点指针置空      
  14.     return L;
  15. }
6.删除结点操作

  1. bool ListDelete(LinkList &L, int i, ElemType &e){      
  2.     if(i<1)             
  3.         return false;     
  4.     LNode *p=L;       //指针p指向当前扫描到的结点     
  5.     int j=0;          //记录当前结点的位序，头结点是第0个结点      
  6.          
  7.     while(p!=NULL && j<i-1){  //循环找到第i-1个结点 
  8.         //如果i>lengh，p和p的后继结点会等于NULL        
  9.         p = p->next;            
  10.         j++;      
  11.     }       
  12.     if(p==NULL)       
  13.         return false;    
  14.     if(p->next == NULL)        
  15.         return false;    	   
  16.     
  17.     LNode *q = p->next;    //令q指向被删除的结点（暂时存储）   
  18.     e = q->data;           //用e返回元素的值
  19.     p->next = q->next;     //将*q结点从链中“断开”
  20.     free(q)                //释放结点的存储空间
  21.     return true;
  22. }

同插入算法一样，该算法的主要时间也耗费在查找操作上，时间复杂度为O(n)。当链表不带头结点时，需要判断被删结点是否为首结点，若是，则要做特殊处理，将头指针L指向新的首结点。反之，则是相同的。 

拓展：删除指定结点*p

通常的做法是先从链表的头结点开始顺序查找到其前驱，然后执行删除操作。但其实，删除结点*p的操作可用删除其后继来实现，实质就是将其后继的值赋予其自身，然后再删除后继，也能使时间复杂度为O(1)。

  1. *q = p->next;        //令q指向p的后继结点  
  2. //如果p是最后一个结点，则q指向NULL，继续执行就会报错  
  3. p->data = q->data;   //用后继结点的数据域覆盖
  4. p->next = q->next;   //将*q结点从链中“断开”
  5. free(q);             //释放后继结点的存储空间

注：单链表是整个链表的基础，一定要熟练掌握单链表的基本操作算法。

2.3.3 双链表 

为了克服单链表的缺点（要访问某个结点的前驱（插入、删除操作时），只能从头开始遍历）引入了双链表，双链表结点中有两个指针prior和next，分别指向直接前驱和直接后继。

双链表中结点类型的描述如下：

  1. typedef struct DNode{            //定义双链表结点类型 
  2.     ElemType data;               //数据域    
  3.     struct DNode *prior,*next;  //前驱和后继指针
  4. }DNode, *DLinklist;

双链表再单链表的基础上增加了一个指向其前驱的指针prior，因此双链表的按值查找和按位查找与单链表的相同。但是再插入和删除操作的实现上，与单链表有着较大的差异。这是因为“链”变化时也需要对指针prior做出修改，其关键是保证在修改的过程中不断链。（时间复杂度也仅为O(1)）

1. 双链表的插入操作

  1. s->next = p->next;      //将结点*s插入到结点*p之后
  2. p->next->prior = s; 
  3. s->prior = p;   
  4. p->next = s;

注：上诉代码的语句顺序不是唯一的，但也不是任意的，第一句必须在第四句之前，否则*p的后继结点的指针就会丢掉，导致插入失败。

2. 双链表的删除操作 

  1. p->next = q->next; 
  2. q->next->prior=p; 
  3. free(q);

2.3.4 循环链表 

1. 循环单链表

循环单链表与单链表的区别在于，表中最后一个结点的指针不是NULL，而是改为指向头结点，从而整个链表形成一个环。（故循环单链表的判空条件不是头结点的指针是否为空，而是尾结点的指针是否等于头指针）首尾相等

2. 循环双链表

与循环单链表类似。在循环双链表中就只是把头结点的prior指针还要指向其表尾结点。

2.3.5 静态链表

用数组的方式实现的链表。分配一整片连续的内存空间（与顺序表相同），各个结点集中安置，每个结点包括了数据元素和下一个结点的数组下标。

  1. #define MaxSize 10        //静态链表的最大长度
  2. struct Node{              //静态链表结构类型的定义  
  3.     ElemType data;        //存储数据元素    
  4.     int next;             //下一个元素的数组下标
  5. } SLinkList[MaxSize];

注：静态链表以 next ==-1作为其结束的标志。静态链表的插入、删除操作与动态链表的相同。只需要修改指针，而不需要移动元素。总体来说，静态链表没有单链表使用起来方便，buttt在一些不支持指针的高级语言中，这是一种非常巧妙地设计方法。 

2.3.6 顺序表和链表的比较

1. 存取（读/写）方式

顺序表可以顺序存取，也可也随机存取，链表只能从表头开始依次顺序存取。

2. 逻辑结构与物理结构

采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。

3. 查找、插入和删除操作

查找按位查找按值查找
顺序表O(1)O(n) | O(log2n)若元素有序，（二分法）
链表O(n)O(n)

顺序表的插入、删除操作，平均需要移动半个表长的元素。

链表的插入、删除操作，只需修改相关结点的指针域即可。 

4. 空间分配

顺序表一旦确定了就无法更改。

三、栈、队列和数组

3.1 栈

3.1.1 栈的基本概念

  1. 栈：是一种特殊的线性表（只允许在一端进行插入或删除操作），其逻辑结构与普通线性表相同。
  2. 栈顶（Top）：允许进行插入和删除的一端 。
  3. 栈底（Botton）：不允许进行插入和删除的一端 。
  4. 空栈：不含任何元素的空表。
  5. 特点：
    1. 后进先出LIFO（Last In First Out）。
    2. 栈的大小是不可变（但是共享栈可以解决这个问题）
  6. 基本操作：
    1. InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
    2. StackEmpty(S)：判空。断一个栈 S 是否为空，若 S 为空，则返回 true，否则返回 false。
    3. Push(&S, x)：进栈。若栈 S 未满，则将 x 加入使其成为新的栈顶元素。
    4. Pop(&S, &x)：出栈。若栈 S 非空，则弹出（删除）栈顶元素，并用 x 返回。
    5. GetTop(S, &x)：读取栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。
    6. DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。

3.1.2 栈的顺序存储结构

栈的本质上就是一种受限的线性表，故而它也有两种存储方式。

1. 顺序栈的实现

  1. #define MaxSize 10                //定义栈中元素的最大个数
  2. typedef struct{    
  3.     ElemType data[MaxSize];       //静态数组存放栈中元素    
  4.     int top;                      //栈顶元素
  5. }SqStack;
  • 栈顶指针：S.top，初始时设置为-1；
  • 栈顶元素：S.data[S.top]；
  • 栈空条件：S.top==-1;
  • 栈满条件：S.top==MaxSize-1;
  • 栈长：S.top+1

注：方法不唯一，也可以是初始设置栈顶指针S.top=0；进栈时先将值送到栈顶，栈顶指针再加1；出栈时，栈顶指针先减1，再取栈顶元素；空条件是s.top==0；栈满条件是S.top==MaxSize。

根本区别就在于栈顶指针是否有指向实体元素。

2. 顺序栈的基本操作

  1. // 初始化栈
  2. void InitStack(SqStack &S){ 
  3.     S.top = -1;               //初始化栈顶指针
  4. }
  5.  
  6. // 判断栈是否为空
  7. bool StackEmpty(SqStack S){    
  8.     if(S.top == -1)        
  9.         return true;           
  10.     return false;
  11. }
  12.  
  13. // 进栈
  14. bool Push(SqStack &S, ElemType x){    // 判断栈是否已满    
  15.     if(S.top == MaxSize - 1)        
  16.         return false;    
  17.     S.data[++S.top] = x;        //指针先加1，再入栈
  18.     return true;
  19. }
  20.  
  21. // 出栈
  22. bool Pop(SqStack &x, ElemType &x){    // 判断栈是否为空    
  23.     if(S.top == -1)        
  24.         return false;    
  25.     x = S.data[S.top--];        //先出栈，指针再减1
  26.     return true;
  27. }
  28.  
  29. // 读栈顶元素
  30. bool GetTop(SqStack S, ElemType &x){        
  31.     if(S.top == -1)                
  32.         return false;        
  33.     x = S.data[S.top];          //x记录栈顶元素
  34.     return true; 
  35. }

注（Again）：这里的top指向的是栈顶元素，如果S.top=0，则相对应的栈空、栈满、入栈操作和出栈操作也会发生变化。

3. 共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶相共享空间的中间延伸。

  1. #define MaxSize 10         //定义栈中元素的最大个数
  2. typedef struct{       
  3.     ElemType data[MaxSize];       //静态数组存放栈中元素  
  4.     int top0;                     //0号栈栈顶指针  
  5.     int top1;                     //1号栈栈顶指针
  6. }ShStack;
  7.  
  8. // 初始化栈
  9. void InitSqStack(ShStack &S){    
  10.     S.top0 = -1;      
  11.     S.top1 = MaxSize;   
  12. }

注：两个栈的栈顶指针都指向栈顶元素，top0=-1时为0号栈为空，top1=MaxSize时1号栈为空；当且仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。当0号栈进栈时top0先加1再赋值（1号栈则相反，先减1再赋值）；出栈时则刚好相反。

3.1.3 栈的链式存储结构

采用链式存储，优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。

  1. typedef struct Linknode{        
  2.     ElemType data;        //数据域    
  3.     Linknode *next;       //指针域
  4. }LiStack;

采用链式存储便于结点的插入和删除。操作与链表相似，入栈和出栈的操作都在链表的表头进行。

注：带表头和不带表头的链栈，具体的实现会有所不同。

3.2 队列

3.2.1 队列的基本概念

  1. 队列是操作受限的线性表：只允许在一端进行插入 (入队)，另一端进行删除 (出队)。
  2. 队头：允许删除的一端，又称为队首。
  3. 队尾：允许插入的一端。
  4. 空队列：不含任何元素的空表。
  5. 特点：先进先出FIFO（First In First Out）。

基本操作：

  1. InitQueue(&Q)：初始化队列。构造一个空队列 Q。
  2. DestroyQueue(&Q)：销毁队列。销毁并释放队列 Q 所占用的内存空间。
  3. EnQueue(&Q, x)：入队。若队列 Q 未满，将 x 加入，使之成为新的队尾。
  4. DeQueue(&Q, &x)：出队。若队列 Q 非空，删除队头元素，并用 x 返回。
  5. GetHead(Q,&x)：读队头元素。若队列 Q 非空，则将队头元素赋值给 x。
  6. QueueEmpty(Q)：判空。若队列 Q 为空，则返回 true。

注：栈和队列是受限的线性表，因此不是任何对线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

3.2.2 队列的顺序存储结构

1. 队列的顺序存储

队列的顺序实现是指分配一块连续的存储单元存放队列的元素，并附设了两个指针：队头指针front指向对头元素，队尾指针rear指向队尾元素的下一个位置（这个不一定哦，不同教材可能对这两个指针的定义都不一样，做习题的时候需要擦亮自己的bigeyes）

  1. #define MaxSize 10;     //定义队列中元素的最大个数
  2.  
  3. typedef struct{     
  4.     ElemType data[MaxSize];   //用数组存放队列元素     
  5.     int front, rear;          //队头指针和队尾指针
  6. }SqQueue;

  • 初始时：Q.front=Q.rear=0
  • 进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
  • 出队操作：队不空时，先取队头元素值，再将队头指针加1。
  • 判空：Q.front==Q.rear==0

注：Q.rear==MaxSize不能作为队列满的条件，会产生假溢出。

2. 循环队列

将顺序队列臆造成一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。

当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。

  • 初始时：Q.front=Q.rear=0
  • 队首指针进1：Q.front=(Q.front+1)%MaxSize
  • 队尾指针进1：Q.rear=(Q.rear+1)%MaxSize
  • 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize
  • 出队入队时：指针都按顺时针方向进1

注：循环队列中不能仅仅使用 Q.front==Q.rear 作为判断队空/队满的条件。
故产生了以下三种解决方式。

  • 牺牲一个单元来区分队空和队满，即将  (Q.rear+1)%MaxSize == Q.front) 作为判断队列是否已满的条件。（主流方法）Q.front==Q.rear作为判断队空的条件。
  • 类型中增设size数据成员，表示元素个数。删除成功size减1，插入成功size加1。队空时Q.size==0;队满时Q.size==MaxSize,两种情况都有Q.front==Q.rear。
  • 类型中增设tag数据成员，以区分队满还是队空。删除成功置tag=0，若导致Q.front==Q.rear，则为队空；插入成功置tag=1，若导致Q.front==Q.rear，则为队满。

3. 循环队列的操作

1）初始化

  1. void InitQueue(SqQueue &Q){    
  2.     Q.rear = Q.front = 0;        //初始化队首、队尾指针
  3. }

2）判队空

  1. bool QueueEmpty(SqQueue Q){     
  2.     if(Q.rear == Q.front)            
  3.         return true;   
  4.     else          
  5.         return false;
  6. }

3）入队

  1. bool EnQueue(SqQueue &Q, ElemType x){       
  2.     if((Q.rear+1)%MaxSize == Q.front) 	//牺牲一个单元区分队空和队满   
  3.         return false;    
  4.     Q.data[Q.rear] = x;   
  5.     Q.rear = (Q.rear+1)%MaxSize;        //队尾指针加1取模
  6.     return true;
  7. }

4）出队

  1. bool DeQueue(SqQueue &Q, ElemType &x){    
  2.     if(Q.rear == Q.front)              //队空则报错
  3.         return false;     
  4.     x = Q.data[Q.front];  
  5.     Q.front = (Q.front+1)%MaxSize;     //队头指针加1取模
  6.     return true;
  7. }

3.2.3 队列的链式存储结构

1. 队列的链式存储

队列的链式结构表示称为链队列，它实际上是一个同时有队头指针和队尾指针的单链表，头指针指向对头结点，尾指针指向队尾结点，即单链表的最后一个结点。

  1. // 链式队列结点
  2. typedef struct LinkNode{  
  3.     ElemType data;    
  4.     struct LinkNode *next;
  5. }
  6.  
  7. // 链式队列
  8. typedef struct{       
  9.     // 头指针和尾指针  
  10.     LinkNode *front, *rear;
  11. }LinkQueue;

注：不带头结点时，当 Q.front==NULL 且 Q.rear==NULL 时，链式队列为空。

2. 链式存储的基本操作

1）初始化

  1. void InitQueue(LinkQueue &Q){
  2.     //初始化时，front、rear都指向头结点
  3.     Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
  4.     Q.front -> next = NULL;    //初始为空
  5. }

2）判队空

  1. //判断队列是否为空
  2. bool IsEmpty(LinkQueue Q){
  3.     if(Q.front == Q.rear)     //也可用 Q.front -> next == NULL
  4.         return true;
  5.     else
  6.         return false;
  7. }

3）入队操作

  1. //新元素入队 (表尾进行)
  2. void EnQueue(LinkQueue &Q, ElemType x){
  3.     LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点
  4.     s->data = x;
  5.     s->next = NULL;     //s作为最后一个结点，指针域指向NULL
  6.     Q.rear->next = s;   //新结点插入到当前的rear之后
  7.     Q.rear = s;         //表尾指针指向新的表尾
  8. }

4）出队操作

  1. //队头元素出队
  2. bool DeQueue(LinkQueue &Q, ElemType &x){
  3.     if(Q.front == Q.rear)
  4.         return false;                    //空队
  5.     
  6.     LinkNode *p = Q.front->next;         //p指针指向即将删除的结点 (头结点所指向的结点)
  7.     x = p->data;
  8.     Q.front->next = p->next;             //修改头结点的next指针
  9.     if(Q.rear == p)                      //此次是最后一个结点出队
  10.         Q.rear = Q.front;                //修改rear指针
  11.     free(p);                             //释放结点空间
  12.  
  13.     return true;
  14. }

3.2.4 双端队列

定义：双端队列是指允许两端都可以进行入队和出队操作的队列。

  • 双端队列允许从两端插入、两端删除的线性表；
  • 如果只使用其中一端的插入、删除操作，则等同于栈；
  • 输入受限的双端队列：允许一端插入，两端删除的线性表；
  • 输出受限的双端队列：允许两端插入，一端删除的线性表；

3.3 栈和队列的应用

3.3.1 栈在括号匹配中的应用

  • ((())) 最后出现的左括号最先被匹配 (栈的特性—LIFO);

  • 遇到左括号就入栈;

  • 遇到右括号，就“消耗”一个左括号 (出栈);
    匹配失败情况：

  • 扫描到右括号且栈空，则该右括号单身;

  • 扫描完所有括号后，栈非空，则该左括号单身;

  • 左右括号不匹配;

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

1、算术表达式

  • 中缀表达式其实就是人们常用的算术表达式，运算符在两个操作数中间。
  • 与前缀表达式和后缀表达式不同的就是，中缀表达式的括号是必需的。

2、中缀表达式转后缀表达式

手算方法：

  1. 按照运算符的运算规则对所有的运算单位加括号。
  2. 将运算符移至对应括号的后面，相当于按“左操作数 右操作数 运算符“重新组合。
  3. 去除所有的括号。

计算方法：

        在计算机中，中缀表达式转后缀表达式时需要借助一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右依次扫描中缀表达式中的每一项，具体转化过程如下：

  1. 遇到操作数。直接加入后缀表达式。
  2. 遇到界限符，若为“（”，则直接入栈；若为“）”，则依次弹出栈中的运算符，并加入后缀表达式，直到弹出“（”为止。注意，“（”直接删除，不加入后缀表达式。
  3. 遇到运算符。若其优先级高于除“（”外的栈顶运算符，则直接入栈。否者，从栈顶开始，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，直到遇到一个优先级低于它的运算符或遇到“（”为止，之后将当前运算符入栈。

按上诉方法扫描所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

eg：A+B*(C-D)-E/F（会手算的就行了）

3、后缀表达式求值

通过后缀表示计算表达式的值的过程：

  1. 从左往右依次扫描表达式的每一项，若该项是操作数，则将其压入栈中；
  2. 若该项是操作符<op>，则从栈中退出两个操作数Y和X，形成运算指令X<op>Y，并将计算结果压入栈中。

后缀表达式 ABCD-*+EF 求值过程如下

3.3.3 栈在递归中的应用

  • 函数调用的特点：最后被调用的函数最先执行结束(LIFO)
  • 函数调用时，需要用一个栈存储：
    • 调用返回地址
    • 实参
    • 局部变量
  • 递归调用时，函数调用栈称为 “递归工作栈”:
    • 每进入一层递归，就将递归调用所需信息压入栈顶；
    • 每退出一层递归，就从栈顶弹出相应信息；
  • 缺点：太多层递归可能回导致栈溢出；
  • 适合用“递归”算法解决（递归算法的精髓）：可以把原始问题转换为属性相同，但规模较小的问题；

3.3.4 队列在层次遍历中的应用

在信息处理中有一大类问题需要逐层或逐行处理。这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，等到当前层或当前行处理完毕，就可以处理下一层或下一行。使用队列是为了保存下一步的处理顺序。

3.3.5 队列在计算机系统中的应用

队列在计算机系统中的应用非常广泛，以下仅从两个方面来阐述：第一个方面是解决主机与外部设备之间数度不匹配的问题，第二个方面是解决由多用户引起的资源竞争问题。 

3.4 数组和特殊矩阵

3.4.1 数组的定义

由n（n>=1）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

注：数组和线性表之间的关系：数组是线性表的推广。

3.4.2 数组的存储结构

一维数组：

二维数组：

设二维数组的行下标和列下标的范围分别是[0,h1]与[0,h2]。

  • 行优先

  • 列优先

注：行就找列，列就找行。

3.4.3 特殊矩阵的压缩存储

压缩存储: 多个值相同的元素只分配一个空间，0不分配空间。

特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间内。

1、对称矩阵

注：矩阵元素aij通常是从1开始的。压缩完的尺寸为[n(n+1)/2]。

元素下标之间的关系:

2、三角矩阵

下三角矩阵：

元素下标之间的对应关系为：

下三角矩阵在内存中的压缩形式如下：

注：压缩完的尺寸为[n(n+1)/2+1]

上三角矩阵：

元素下标之间的对应关系为：

上三角矩阵在内存中的压缩形式如下：

注：以上推导均假设数组的下标从0开始。直接记也很困难，最好还是会自己推导。

3、三对角矩阵

对角矩阵也称为带状矩阵。

三对角矩阵A也可以采用压缩存储，将3条对角线上的元素按行优先方式存放在一维数组B中，且a1,1存放与B[0]中，其存储方式如图所示。

k=2i+j-3（三对角矩阵压缩存储的下标对应关系）

i=[(k+1)/3+1]（向下取整）

3.4.4 稀疏矩阵

矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少，即s>>t的矩阵称为稀疏矩阵。

压缩存储策略：

  1. 顺序存储——三元组 <行，列，值>
  2. 链式存储——十字链表法

四、串

*4.1 串的定义和实现

4.1.1 串的定义

  1. 串: 零个或多个字符组成的有限序列，如 S = 'iPhone 15 Pro Max 1TB 暗夜紫'；（单引号包裹的一个字符实际上代表一个整数。
    双引号引起的字符串，代表的是一个指向无名数组起始字符的指针。该数组会被双引号之间的字符以及一个额外的二进制为零的字符 '\0' 初始化。）
  2. 串名：S；
  3. 串的长度：串中字符的个数n；
  4. 空串：n=0（长度为0）时的串；
  5. 子串：串中任意多个连续的字符组成的子序列称为该串的子串；
  6. 主串：包含子串的串；
  7. 字符在主串中的位置：某个字符在串中的序号（从1开始）；
  8. 子串在主串中的位置：子串的第一个字符在主串中的位置；
  9. 空串和空格串的差别：
    1. M = ‘’ 是空串；
    2. N = ’ ’ 是空格串；（空格可以是一个也可以是多个）
  10. 串和线性表的差别：（串的数据对象限定为字符串）
    1. 串是特殊的线性表，数据元素之间呈线性关系（逻辑结构相似）；
    2. 串的数据对象限定为字符集：中文字符、英文字符、数字字符、标点字符…

4.1.2 串的存储结构

1. 定长顺序表示

串的顺序存储结构是用一组地址连续的存储单元来存储字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般用定长数组来定义。

  1. #define MAXLEN 255    //预定义最大串长为255
  2.     typedef struct {
  3.     char ch[MAXLEN];    //每个分量存储一个字符
  4.     //存储串的一维数组，ch[0]~ch[255],共256个；
  5.     //通常情况下ch[0]存放串的长度，或者闲置不用，真正串的类容从ch[1]开始
  6.     int length;    //串的实际长度
  7. }SString;

注：串的实际长度只能小于或等于MAXLEN，超过预定长度的串指会被舍去，称为截断。

串长有两种表示方法：一是如上诉定义描述的那样，用一个额外变量len来存放串的长度；二是在串值后面加一个不计入串长的结束标记字符"\0"，此时串长为隐含值。

为了克服截断，可以采用动态分配的方法。

2. 堆分配存储表示

堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列，但他们的存储空间是在程序执行的过程中动态分配得到的。

  1. typedef struct st {
  2. 	char *ch;  //按串长分配存储区，ch指向串存放的起始地址
  3. 	int length;  //串的长度
  4. }HString;

注：在C语言中存在一个称之为”堆“的自由存储区，并用malloc()和free()函数来完成动态存储管理。 

3. 块链存储表示

串的块链存储，指的是使用链表结构存储字符串。由于串的特殊性（每个元素只有一个字符），在具体实现时，每个结点即可以存放一个字符，也可以存放多个字符。每个结点称为块，故整个链表称为块链结构。

4.1.3 串的基本操作

  • StrAssign(&T, chars): 赋值操作，把串T赋值为chars；
  • StrCopy(&T, S): 复制操作，把串S复制得到串T
  • StrEmpty(S): 判空操作，若S为空串，则返回TRUE，否则返回False；
  • StrCompare(S, T): 比较操作，参照英文词典排序方式；若S > T,返回值>0; S = T,返回值=0 
  • 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；

4.2 串的模式匹配

4.2.1 简单的模式匹配算法

1. 暴力匹配算法

  1. int Index(SString S, SString T){
  2.     int i=1;                //扫描主串S
  3.     int j=1;                //扫描模式串T
  4.     while(i<=S.length && j<=T.length){
  5.         if(S.ch[i] == T.ch[j]){
  6.             ++i;
  7.             ++j;             //继续比较后继字符
  8.         }
  9.         else{
  10.             i = i-j+2;
  11.             j=1;             //指针后退重新开始匹配
  12.         }
  13.     }
  14.     if(j>T.length)
  15.     //匹配成功则返回与模式T中第一个字符相等的字符在主串S中的序号，否则匹配不成功，函数值为0。
  16.         return i-T.length;    
  17.     else
  18.         return 0;
  19. }

注：主串长度为n，模式串长度为m，所以最多会比较n-m+1个子串。
最坏时间复杂度 = O(nm)：每个子串都要对比m个字符(对比到最后一个字符才匹配不上)，共要对比n-m+1个子串，复杂度 = O((n-m+1)m) = O(nm - m^2 + m) = O(nm)
buttttt大多数时候，n>>m
最好时间复杂度 = O(n)：每个子串的第一个字符就匹配失败，共要对比n-m+1个子串，复杂度 = O(n-m+1) = O(n)

4.2.2 串的模式匹配算法——KMP算法

其实很容易从上述的暴力匹配中看出为什么效率较低。
在暴力匹配中，每趟匹配失败都是模式串后移一位再从头开始比较、而某趟已匹配相等的字符串序列是模式串的某个前缀，这种频繁的重复相当于模式串不断的进行自我比较，这也就是低效率的根源。

于是就出现了next数组，原理不过多赘述。

  1. void get_next(SString T,int next[]){
  2.     int i=1,j=0;
  3.     next[1]=0;
  4.     while(i<T.length){
  5.         if(j==0||T.length()){
  6.             ++i;
  7.             ++j;
  8.             next[i]=j;    //若pi=pj，则next[j+1]=next[j]+1
  9.         }
  10.         else{
  11.             j=next[j];    //否则令j=next[j]，循环继续
  12.         }   
  13. }

next数组的求解方法：

  1. next数组第一二位一定分别为0，1，后面求解每一位的next值时，根据前一位进行比较。
  2. 从第三位开始，将前一位与其next值对应的内容进行比较，
    1. 如果相等，则该位的next值就是前一位的next值加上1；
    2. 如果不等，向前继续寻找next值对应的内容来与前一位进行比较，
      1. 直到找到某个位上内容的next值对应的内容与前一位相等为止，
      2. 则这个位对应的值加上1即为需求的next值；
      3. 如果找到第一位都没有找到与前一位相等的内容，那么求解的位上的next值为1

公式：next[i]=匹配字符数+1

巴拉巴拉讲这么多不如直接看样例蛤

next数组第一二位一定分别为0，1：

看第三位，按照next数组求解方法。第三位a的前一位是第二位的b，b的next值是1对应内容是a，b与a不同，则继续向前寻找next值对应的内容与第二位的b进行比较。但是找到第一位都没有找到与第二位的b相等的内容，所以第三位a的next值为1，则：

看第四位的b，b的前一位a的next值1对应内容为a，相同，所以该位b的next值就是前一位a的next（第三位的a）值加上1，即为2：

看第五位a，a的前一位b的next值2对应内容为b，相等，所以第五位a的next值就是其前一位b的next值加上1，即为3：

看第六位a，a的前一位a的next值3对应内容为a，相等，所以该位a的next值就是前一位a的next值加上1，即为4：

看第七位a，a的前一位a的next值4对应内容为b，不相等，向前继续寻找next值对应的内容来与前一位进行比较，b的next值2对应的内容为b，依旧不相等，继续向前寻找，第二位b的next值1对应内容为a，相等。因为是在第二位b处实现的相等，所以第七位a的next值为第二位b的next值上加1，即为2：

后续就都是按照上述的过程，就不多赘述了，让我321直接上成品。

注：值的注意的是有的教材中所写的下标是从0开始的那我们就要整体减1（也就是有的题目要考虑两解）

利用next数组进行模式匹配

  1. int Index_KMP(SString S, SString T, int next[]){
  2.     int i=1;     //主串
  3.     int j=1;     //模式串
  4.     while（i<S.length && j<=T.length){
  5.         if(j==0 || S.ch[i]==T.ch[j]){      //第一个元素匹配失败时
  6.             ++j;
  7.             ++i;         //继续比较后继字符
  8.         }
  9.         else
  10.             j=next[j]   //模式串向右移动
  11.     }
  12.     if(j>T.length)
  13.         return i-T.length; //匹配成功
  14. }

注：尽管普通模式匹配的时间复杂度O(mn)，KMP算法的时间复杂度是O(m+n)，但在一般情况下，普通模式匹配的实际执行时间近似O(m+n)，因此至今还在被采用

KMP算法仅在主串与子串有很多“部分匹配”时才显得比普通算法快得多，其主要优点时主串不回溯。

4.2.3 KMP算法的进一步优化

基本公式

注：本人手瓢上面的next也一样模式串中i均是j，后续也没有改。（imlazyboy)

nextval数组规定的第一项为0。

先将其next[i]所对应的值标在旁边，方便计算。

先找出不相等的（Pj != Pnextval[j]）则nextval数组的值就等于相对应的next数组的值。

那接下来看相等的，nextval数组则等于相对应的next数组所指位置的nextval数组。

  1. void get_nextval(SString T, int nextval []){
  2.     int i = 1;
  3.     nextval[1] = 0;
  4.     int j = 0;
  5.     while(i<T.length){
  6.         if (j == 0 || T.ch[i] == T.ch[j]){
  7.             ++i;  ++j;
  8.             if (T[i] != T[j]){
  9.                 nextval[i] = j
  10.             } else{
  11.                 nextval[i] = nextval[j]
  12.             }
  13.         }else{
  14.             j = nextval[j];
  15.         }
  16.     }
  17. }

五、树与二叉树

5.1 树的基本概念

5.1.1 树的定义

树是n(n>=0)个结点的有限集。

  • 空树：n=0
  • 根结点：有且仅有一个特定的称为根的结点（没有前驱，除了根结点外的的所有结点有且仅有一个结点。）
  • 子树：当n>1时，其余结点可分为m(m>0)个互不相交的有限集。其中每个集合本身又是一棵树，就将其称之为根的子树。
  • 树的所有结点都可以有零个或多个后继。

5.1.2 基本术语

  • 结点之间的关系描述
    • 祖先、子孙、双亲、孩子、兄弟和堂兄弟结点 
    • 路径（方向）、路径长度（经过几条边）
  • 结点、树的属性描述
    • 结点的层次（深度）——从上往下（默认从1开始，but有例外）
    • 结点的高度——从下往上
    • 树的高度——总共多少层
    • 结点的度——该结点有几个孩子（分支）
    • 树的度——各结点的度的最大值
  • 有序树、无序树
  • 森林
    • 删去书的根节点就变为了森林

5.1.3 树的性质

  1. 树中的结点数等于所有结点的度数之和加1。
  2. 度为m（m叉树也一样）的树第i层上至多有m^(i-1)个结点（i>=1）。
  3. 度为m的数、m叉数的区别
  4. 高度为h的m叉树至多有 (m^h-1)/(m-1) 个结点。
  5. 高度为h的m叉树至少有 h 个结点。
  6. 具有n个结点的m叉树的最小高度为 [logm(n(m-1)+1)] 。
  7. 度为m，具有n个结点的树的最大高度 h 为 n-m+1
  8. 高度为h、度为m的树至少有 h+m-1 个结点
  9. m叉树的结点i的第一个子女编号为，反过来，结点i的双亲编号是（i>1）

5.2 二叉树的概念

5.2.1 二叉树的定义及其主要特性

定义：

二叉树是n(n>=0)个结点的有限集，它或者是空集（n=0），或者由一个根结点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。

特点：

  1. 每个结点最多有俩孩子（二叉树中不存在度大于2的结点）。
  2. 二叉树可以是空集合，根可以有空的左子树和空的右子树。
  3. 二叉树有左右之分，次序不能颠倒。

特殊的二叉树：

  1. 满二叉树：一颗高度为h，且含有2^h-1个结点的二叉树。
  2. 完全二叉树：当且仅当每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。
  3. 二叉排序树：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一颗二叉排序树。
  4. 平衡二叉树：树中任意一个结点的左子树和右子树的高度之差的绝对值不超过1。
  5. 正则二叉树：树中每个分支结点都有2个孩子，即树中只有度为0或2的结点。

注：满二叉树是一种特殊的完全二叉树。

二叉树的性质：

  1. 非空二叉树上的叶结点等于度为2的结点数加1，即 n0=n2+1 。
  2. 非空二叉树的第i层上至多有 2^(i-1) 个结点（i>1）。
  3. 深度为h的二叉树至多有 2^h-1 个结点（h>=1）。
  4. 深度为h的二叉树至少有 2^(h-1) 个结点（h>=1）。
  5. 具有n个结点的完全二叉树的深度为 (log2n)+1 or log2(n+1) 。

5.2.2 二叉树的存储结构

1、顺序存储结构

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来。（用一组连续的存储单元依次自上向下、自左向右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中。）

  1. #define MaxSize 100
  2.  
  3. struct TreeNode{
  4.    ElemType value; //结点中的数据元素
  5.    bool isEmpty;   //结点是否为空
  6. }
  7.  
  8. main(){
  9.    TreeNode t[MaxSize];
  10.    for (int i=0; i<MaxSize; i++){
  11.       t[i].isEmpty = true;
  12.    }
  13. }

注：建议从数组下标1开始存储树中的结点，保证数组下标和结点编号一致。 
       依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适。

2、链式存储结构

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储链式存储结构，用链表结点来存储二叉树中的每个结点。二叉链表结构如下。

  1. //二叉树的结点
  2.  
  3. struct ElemType{
  4.    int value;
  5. };
  6.  
  7. typedef struct BiTnode{
  8.    ElemType data;          //数据域
  9.    struct BiTNode *lchild, *rchild; //左、右孩子指针
  10. }BiTNode, *BiTree;
  11.  
  12. //定义一棵空树
  13. BiTree root = NULL;
  14.  
  15. //插入根节点
  16. root = (BiTree) malloc (sizeof(BiTNode));
  17. root -> data = {1};
  18. root -> lchild = NULL;
  19. root -> rchild = NULL;
  20.  
  21. //插入新结点
  22. BiTNode *p = (BiTree) malloc (sizeof(BiTNode));
  23. p -> data = {2};
  24. p -> lchild = NULL;
  25. p -> rchild = NULL;
  26. root -> lchild = p; //作为根节点的左孩子

注：使用不同的存储结构时，实现二叉树操作的算法也会不同，因此要根据实际应用场合（二叉树的形态和需要进行的运算）来选择合适的存储结构。 

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

5.3.1 二叉树的遍历

是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因此需要寻找一种规律，一遍使二叉树上的结点能排列在一个线性结构上，进而便于遍历。

1、先序遍历（PreOrder）
  • 若二叉树为空，不用操作
  • 若二叉树非空：
    • 访问根节点
    • 先序遍历左子树
    • 先序遍历右子树
  1. typedef struct BiTnode{
  2.    ElemType data;          
  3.    struct BiTNode *lchild, *rchild; 
  4. }BiTNode, *BiTree;
  5.  
  6. void PreOrder(BiTree T){
  7.    if(T!=NULL){
  8.       visit(T);                 //访问根结点
  9.       PreOrder(T->lchild);      //递归遍历左子树
  10.       PreOrder(T->rchild);      //递归遍历右子树
  11.    }
  12. }
  13.
2、中序遍历（InOrder）
  • 若二叉树为空，不用操作
  • 若二叉树非空：
    • 先序遍历左子树
    • 访问根节点
    • 先序遍历右子树
  1. typedef struct BiTnode{
  2.    ElemType data;          
  3.    struct BiTNode *lchild, *rchild; 
  4. }BiTNode, *BiTree;
  5.  
  6. void InOrder(BiTree T){
  7.    if(T!=NULL){
  8.       InOrder(T->lchild);       //递归遍历左子树
  9.       visit(T);                 //访问根结点
  10.       InOrder(T->rchild);       //递归遍历右子树
  11.    }
  12. }
  13.
3、后序遍历（PostOrder）
  • 若二叉树为空，不用操作
  • 若二叉树非空：
    • 先序遍历左子树
    • 先序遍历右子树
    • 访问根节点
  1. typedef struct BiTnode{
  2.    ElemType data;          
  3.    struct BiTNode *lchild, *rchild; 
  4. }BiTNode, *BiTree;
  5.  
  6. void PostOrder(BiTree T){
  7.    if(T!=NULL){
  8.       PostOrder(T->lchild);       //递归遍历左子树    
  9.       PostOrder(T->rchild);       //递归遍历右子树
  10.       visit(T);                 //访问根结点
  11.    }
  12. }
  13.

4、层次遍历

算法思想：

  • （需要借助一个辅助队列）
  • 根节点入队
  • 若队列非空，则队头结点出队，访问该结点，依次将其左、右孩子插入队尾（如果有的话）（重复该步骤直至队列为空）
  1. //层序遍历
  2. void LevelOrder(BiTree T){
  3.    LinkQueue Q;
  4.    InitQueue (Q);                //初始化辅助队列
  5.    BiTree p;
  6.    EnQueue(Q,T);                 //将根节点入队
  7.    while(!isEmpty(Q)){           //队列不空则循环
  8.       DeQueue(Q,p);              //队头结点出队
  9.       visit(p);                  //访问出队结点
  10.       if(p->lchild != NULL)
  11.          EnQueue(Q,p->lchild);   //若左孩子不空，左孩子入队
  12.       if(p->rchild != NULL)
  13.          EnQueue(Q,p->rchild);   //若右孩子不空，右孩子入队
  14.    }
  15. }

5、 由遍历序列构造二叉树

若已知中序遍历，再给出其他三种遍历序列中的任意一种，就可以唯一地确定一棵二叉树。

5.3.2 线索二叉树

  • 基本概念：在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。
  • 存储结构：
  1. //线索二叉树结点
  2. typedef struct ThreadNode{
  3.    ElemType data;
  4.    struct ThreadNode *lchild, *rchild;
  5.    int ltag, rtag;                // 左、右线索标志
  6. }ThreadNode, *ThreadTree;
  •  结点结构：
  • 标志域的含义：

中序线索二叉树的构造

二叉树的线索化是将二叉链表中的空指针改为指向前驱或者后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化实际上就是遍历一遍二叉树。

  1. void InThread(ThreadTreeNode p, ThreadTreeNode pre) {
  2. 	if (p!=NULL) {
  3. 		/*递归线索化左子树*/
  4. 		InThread(p->lchild,pre);
  5.  
  6. 		if (p->lchild == NULL) {
  7. 			p->ltag = 1;
  8. 			p->lchild = pre; //指向前驱结点
  9. 		}
  10. 		if (pre!=NULL&&pre->rchild==NULL) {
  11. 			pre->rchild = p; //指向后继结点
  12. 			pre->rtag = 1;
  13. 		}
  14.  
  15. 		/*递归线索化右子树*/
  16. 		InThread(p->rchild, pre);
  17. 	}
  18. }
  19.  
  20. //2.主过程算法
  21. void CreateInThread(ThreadTreeNode T) {
  22. 	ThreadTreeNode pre = NULL;
  23. 	if (T!=NULL) { //非空二叉树，进行线索化
  24. 		InThread(T,pre); //遍历线索化二叉树
  25. 		pre->rchild = NULL; //处理遍历的最后一个结点
  26. 		pre->rtag = 1;
  27. 	}
  28. }

为了方便，可以在二叉树的线索链表上也添加一个头结点，令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域指针均指向头结点。这好比为二叉树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历。 

中序线索二叉树的遍历

中序线索二叉树的结点隐含了线索二叉树的前驱和后继信息。在对其进行遍历时，只要先找到序列中的第一个结点，然后依次找结点的后继，直至其后继为空。在中序线索二叉树中找结点后继的规律是：若其右标志为“1”，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继。

1）求中序线索二叉树的中序序列中的第一个结点：

  1. ThreadNode *Firstnode(ThreadNode *p){
  2.     while (p->ltag==0) { //结点有左树时，寻找最左端的树
  3. 			p = p->lchild;  //找到最左下结点（不一定是叶结点哦）
  4. 		}
  5.     return p;
  6. }

2）求中序线索二叉树结点p在中序序列下的后继：

  1. ThreadNode* Nextnode(ThreadNode *p){
  2.     if(p->rtag==0)
  3.         return Firstnode(p->rchild);
  4.     else
  5.         return p->rchild;
  6. }

 3）不含头结点的中序线索二叉树的中序遍历的算法：

  1. void Inorder(ThreadNode *T){
  2.     for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
  3.         //printf("%c",p->data);
  4.         visit(p);
  5. }

 先序线索二叉树的构造 

先序线索二叉树的构造和中序线索化的构造基本一样，唯一需要注意就是防止出现转圈问题。 

  1. // 通过先序遍历对二叉树线索化
  2. void PreThread(ThreadTree p,ThreadTree &pre){
  3.     if(p!=NULL){
  4.         if(p->lchild==NULL){
  5.             p->lchild = pre;
  6.             p->ltag = 1;
  7.         }
  8.  
  9.         if(pre!=NULL && pre->rchild==NULL){
  10.             pre->rchild = p;
  11.             pre->rtag = 1;
  12.         }
  13.         pre = p;
  14.         if(p->ltag == 0)  // 防止转圈问题
  15.             PreThread(p->lchild,pre);
  16.  
  17.         PreThread(p->rchild,pre);
  18.     }
  19. }
  20.  
  21. void CreatePreThread(ThreadTree T){
  22.     ThreadTree pre = NULL;
  23.     if(T!=NULL){
  24.         PreThread(T,pre);
  25.         if(pre->rchild==NULL){
  26.             pre->rtag = 1;
  27.         }
  28.     }
  29. }

  后序线索二叉树的构造 

  1. // 通过后序遍历对二叉树线索化
  2. void PostThread(ThreadTree p,ThreadTree &pre){
  3.     if(p!=NULL){
  4.         PostThread(p->lchild,pre);
  5.         PostThread(p->rchild,pre);
  6.  
  7.         if(p->lchild == NULL){
  8.             p->lchild = pre;
  9.             p->ltag = 1;
  10.         }
  11.  
  12.         if(pre!=NULL && pre->rchild==NULL){
  13.             pre->rchild = p;
  14.             pre->rtag = 1;
  15.         }
  16.         pre = p;
  17.     }
  18. }
  19.  
  20. void CreatePostThread(ThreadTree T){
  21.     ThreadTree pre = NULL;
  22.     if(T!=NULL){
  23.         PostThread(T,pre);
  24.         if(pre->rchild==NULL){
  25.             pre->rtag = 1;
  26.         }
  27.     }
  28. }

在线索二叉树中找前驱和后继

  • 中序线索二叉树
    • 结点p的中序前驱结点
      • 若p的ltag=1，lchild指向其前驱；
      • 若p的ltag=0，p的前驱是以该结点为根的左子树上按中序遍历的最后一个结点。
    • 结点p的中序后继结点
      • 若p的rtag=1，rchild指向其后继；
      • 若p的rtag=0，p的后继是以该结点为根的右子树上按中序遍历的第一个结点。
  • 后序线索二叉树
    • 查找结点*p的前驱
      • 若结点*p无左子树，则p->lchild指向其前驱
      • 若结点*p有左子树，当其右子树为空时，其左子树的根（即p->lrchild）为其后序前驱。当其右子树非空时，其右子树的根（即p->rchild）为其后序前驱。
    • 查找结点*p的后继
      • 若结点*p为根，则无后继；
      • 若结点*p为其双亲的右孩子，则其后继为其双亲；
      • 若结点*p为其双亲的左孩子，且双亲无右子女，则其后继为其双亲；
      • 若结点*p为其双亲的左孩子，且双亲有右子女，则结点*p的后继是其双亲的右子树中按后序遍历的第一个结点。

所以，求后序线索二叉树中结点的后继要知道其双亲的信息，要使用栈，所以说后序线索二叉树是不完善的。

  • 先序线索二叉树
    • 在先序线索二叉树中查找结点的后继较容易，而查找前驱要知道其双亲的信息，要使用栈，所以说先序线索二叉树也是不完善的。

注：

一、前序与后序

  • 序列相同
    • 空树或者只有根节点的二叉树。
  • 序列相反
    • 当且仅当二叉树中只有一个叶子节点。
    • 二叉树的高度和其节点个数相同。

二、前序与中序

  • 序列相同
    • 空树或缺左子树的单支二叉树。
  • 序列相反
    • 二叉树为空或者只有一个节点。
    • 若二叉树不为空，缺右子树的单支二叉树（则任意节点没有右孩子）。

三、中序与后序

  • 序列相同
    • 空树或者缺右子树的单支二叉树。
  • 序列相反
    • 任意节点没有左孩子节点。

任何一颗二叉树的叶结点在前序、中序、后序遍历序列中的相对次序是不发生改变的。

5.4 树、森林

5.4.1 树存储结构

1. 双亲表示法（顺序存储）

采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。（根结点下标为0，其伪指针域为-1）

  1. #define MAX_TREE_SIZE 100  //树中最多结点数
  2. typedef struct{      //树的结点定义
  3.    ElemType data;    //数据元素（存放结点本身信息。）
  4.    int parent;      //双亲位置域（指示本结点的双亲结点在数组中的位置。）
  5. }PTNode;
  6.  
  7. typedef struct{                   //树的类型定义
  8.    PTNode nodes[MAX_TREE_SIZE];   //双亲表示
  9.    int n;                         //结点数
  10. }PTree;

  Traits：

  1. 查指定结点的双亲很方便；
  2. 查指定结点的孩子只能从头遍历，空数据导致遍历更慢；

2. 孩子表示法

将每个结点的孩子结点视为一个线性表，且以单链表作为存储结构，则n个结点就有n个孩子链表（叶结点的孩子链表为空表）。而n个头结点又组成一个线性表，用顺序表（含n个元素的结构数组）存储。

  1. struct CTNode{
  2.    int child;    //孩子结点在数组中的位置
  3.    struct CTNode *next;    // 下一个孩子
  4. };
  5.  
  6. typedef struct{
  7.    ElemType data;
  8.    struct CTNode *firstChild;    // 第一个孩子
  9. }CTBox;
  10.  
  11. typedef struct{
  12.    CTBox nodes[MAX_TREE_SIZE];
  13.    int n, r;   // 结点数和根的位置
  14. }CTree;

与双亲表示法相反，孩子表示法寻找孩子的操作非常方便，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。 

3. 孩子兄弟表示法（二叉树表示法）

即以二叉链表作为树的存储结构。

  1. typedef struct CSNode{
  2.    ElemType data;                               //数据域
  3.    struct CSNode *firstchild, *nextsibling;     //第一个孩子和右兄弟指针
  4. }CSNode. *CSTree;

5.4.2 树、森林与二叉树的转移

1. 树转换为二叉树

  1. 加线：在兄弟之间加一连线
  2. 抹线：对每个结点去除其与孩子之间的关系（第一孩子除外）
  3. 旋转：以树的根结点为轴心，顺时针转45度

口诀就是：兄弟相连留长子。

注：树的每个分支结点的所有子结点中的最右子结点无右孩子，根节点转换后也没有右孩子，因此对应二叉树中无右孩子的结点个数=分支结点数+1

2. 森林转换为二叉树

  1. 把每棵树转换为二叉树。
  2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一颗二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后，就得到了森林转换来的二叉树

3. 二叉树转为树

  1. 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子等都与该结点的双亲结点用连线连起来
  2. 删除原二叉树中所有双亲结点与右孩子结点之间的连线
  3. 整理由前两步得到的树，即以该结点为轴心，逆时针转动45°。

4. 二叉树转换为森林

  1. 从根结点开始，若右孩子存在，则把右孩子结点的连线删除，在查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有的右孩子连线都删除为止，得到分离后的二叉树。
  2. 在将每棵分离后的二叉树转换为树即可。

注：判断一棵二叉树能够转换成一棵树还是森林，标准很简答，那就是只要这课二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。

5.4.3 树与森林的遍历

1. 树的遍历

  • 先根遍历：若树非空，先访问根结点，再依次对a每棵子树进行先根遍历；（与对应二叉树的先序遍历序列相同）
  • 后根遍历：若树非空，先依次对每棵子树进行后根遍历，最后再返回根节点；（与对应二叉树的中序遍历序列相同）
  • 层次遍历：和二叉树的层次遍历思想基本相同，即按层序依次访问各节点。

2. 森林的遍历

  • 先序遍历：等同于依次对各个树进行先根遍历；也可以先转换成与之对应的二叉树，对二叉树进行先序遍历；
  • 中序遍历：等同于依次对各个树进行后根遍历；也可以先转换成与之对应的二叉树，对二叉树进行中序遍历；

5.5 树与二叉树的应用

5.5.1 哈夫曼树和哈夫曼编码

  1. 带权路径长度：从根节点到该结点之间的路径长度与该节点的权的乘积。（还有一种就是等于所有分支结点之和）。
  2. 哈夫曼树的定义：带权路径最短的树。（最优二叉树）
  3. 哈夫曼树的构造：不断选取当前权重最小的两个结点使之成为兄弟结点，并将其和当作一个新结点。
  4. 哈夫曼编码：由哈夫曼树得到的二进制前缀编码称为哈夫曼编码。（每个结点的哈夫曼编码前缀都不可能相同）
  5. 加权平均长度：  字符位数 * 出现频率

注：有可能会考察定长编码和哈夫曼编码的比较。

5.5.2 并查集（Disjoint Set）

  • 定义：并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。其存储结构采用双亲表示法。
  • 基本实现：
  1. // 并查集的结构定义
  2. #define SIZE  100
  3. int UFset[SIZE];     // 集合元素数组（双亲指针数组）
  4.  
  5. // 初始化（s[] 即为并查集）
  6. void Initial(int s[]){
  7.     for(int i = 0; i < SIZE; i++){    //每个自成单元素集合
  8.         s[i] = -1;
  9.     }
  10. }
  11.  
  12. // Find操作：在s[] 中查找并返回包含元素 x 的树的根
  13. // 最坏时间复杂度：O(n)  （即结点排列形似成竖直状的单链表）
  14. int Find(int s[], int x){
  15.     while(s[x] >= 0)  x = s[x];     // 循环寻找 x 的根
  16.     return x;    // 根的s[] < 0
  17. }
  18.  
  19. // Union操作：求两个不相交子集合的并集
  20. // 时间复杂度：O(1)
  21. void Union(int s[], int Root1, int Root2){
  22.     if(Root1 == Root2) return;     // 要求 Root1 和 Root2 是不同的，且表示子集合的名字
  23.     s[Root2] = Root1;    // 将 Root2 连接到另一根 Root1 下面
  24. }
  • 并查集实现的优化：
  1. // Find操作的优化：
  2. // 压缩路径（先找到根结点，再将查找路径上所有结点都挂到根结点下）
  3. int Find(int s[], int x){
  4.     int root = x;
  5.     while(s[root] >= 0)  root = s[root];    // 循环找到根
  6.     while(x != root){    // 压缩路径
  7.         int t = x;       // t 指向 x 的父结点
  8.         s[x] = root;     // x 直接挂到根结点下
  9.         x = t;      // 继续使 x 的父结点也挂到根结点下
  10.     }
  11.     return root;
  12. }
  13.  
  14. 通过Find操作的“压缩路径”优化后，可使集合树的深度不超过O(a(n))（a(n)是一个增长及其缓慢的函数，对于其常见的正整数n，通常a(n)<=4）
  15.  
  16.  
  17. // Union操作的优化：小树并入大树
  18. void Union(int s[], int Root1, int Root2){
  19.     if(Root1 == Root2) return;
  20.     if(Root2 > Root1){              // Root2 结点数更少
  21.         s[Root1] += s[Root2];   //累加结点总数
  22.         s[Root2] = Root1;        // 小树合并到大树
  23.     }
  24.     else{       // Root1 结点数更少
  25.         s[Root2] += s[Root1];      //累加结点总数
  26.         s[Root1] = Root2;     // 小树合并到大树
  27.     }
  28. }
  29.  
  30. 采用这种方法构造得成的集合树，其深度不超过[log2n]+1（[]向下取整）

六、图

6.1 图的基本概念

  • 定义：图是一种数据元素间存在多对多关系的数据结构加上一组基本操作构成的抽象数据类型。（是一种较线性表和树更加复杂的数据结构。）
     
  • 有向图：若E是有向边（也称弧）的有限集合，则图G为有向图。弧是顶点的有序对，记为<v, w>，其中v，w是顶点，v称为弧尾，w称为弧头，<v，w>称为从顶点v到顶点w的弧，也称v邻接到w。


     
  • 无向图：若E是无向边（简称边）的有限集合，则图G为无向图。边是顶点的无序对，记为（v，w）或（w，v），因为（v，w）=（w，v） 。其中v，w是顶点。可以说顶点w和顶点v互为邻接点。边（v，w）依附于顶点w和v，或者说边（v，w）和顶点v，w相关联。
     
  • 简单图：一个图G若满足：1、不存在重复边;2、不存在顶点到自身的边，则称图G为简单图。（上面两张有向和无向图均为简单图）
     
  • 复杂图：（与简单图的定义相对）若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。
     
  • 完全图（也称简单完全图）：
    • 对于无向图，∣E∣的取值范围是0到n(n−1)/2，有 n(n−1)/2 条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。
    • 对于有向图，∣E∣的取值范围是0到n(n−1)，有 n(n−1) 条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。
       
  • 子图：设有两个图G = ( V , E ) 和G ′ = ( V ′ , E ′ ) ， 若V ′是V的子集，且E ′是E的子集，则称G ′ 是G的子图。
    • 若有满足V ( G ′ ) = V ( G )的子图G ′ ，则称其为G的生成子图。
       
  • 连通、连通图和连通分量（无向图）：

    • 在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。

    • 若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。

    • 无向图中的极大连通子图称为连通分量。若一个图有n个顶点，并且边数小于n−1，则此图必是非连通图。（也有极小连通子图：既要保持图连通又要使得边数最少的子图）
      （左边两张是无向图，右边三张都是左边的连通分量）

  • 强连通图、强连通分量（有向图）：

    • 在有向图中，若从顶点v到顶点w和从顶点w到项点v之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。

    • 有向图中的极大强连通子图称为有向图的强连通分量。
      （右边是左边的强连通分量）

  • 生成树、生成森林：

    • 连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n−1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

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

  • 顶点的度，入度和出度：图中每个顶点的度定义为以该项点为一个端点的边的数目。

    • 无向图的全部顶点的度的和等于边数的2倍。

    • 对于有向图,顶点v的度分为入度和出度,入度是以顶点v为终点的有向边的数目，而出度是以顶点v为起点的有向边的数目。

    • 有向图的全部顶点的入度之和与出度之和相等，并且等于边数。这是因为每条有向边都有一个起点和终点。

  • 边的权和网：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

  • 稠密图、稀疏图：边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。

  • 路径、路径长度和回路：

    • 某个顶点到另一个顶点之间的顶点序列被称为路径。

    • 路径上边的数目称为路径长度。

    • 第一个顶点和最后一个顶点相同的路径称为回路或环。

  • 简单路径、简单回路：

    • 在路径序列中，顶点不重复出现的路径称为简单路径。

    • 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

  • 距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷(∞)。

  • 有向树：一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

6.2 图的存储及基本操作

6.2.1 邻接矩阵法（数组表示法）

是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系）

  1. #define MaxVertexNum 100    //项目数目的最大值
  2. typedef char VertexType;    //顶点对应的数据类型
  3. typedef int EdgeType;    //边对应的数据类型
  4. typedef struct{
  5.     VertexTypr Vex[MaxVertexNum];    //顶点集
  6.     EdgeType Edge[MaxVertexNum][MaxVertexNum];    //邻接矩阵，边表
  7.     int vexnum,arcnum;    //图的当前顶点数和边数
  8. }MGraph;

Traits：

  1. 无向图的邻接矩阵一定是一个对称矩阵（且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素。
  2. 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非无穷元素）的个数正好是顶点i的度。
  3. 对于有向图，邻接矩阵的第 i 行非零元素（或非无穷元素）的个数正好是顶点 i 的出度；第 i 列非零元素（或非无穷元素）的个数正好是顶点 i 的入度。
  4. 用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大
  5. 稠密图适合使用邻接矩阵的存储表示
  6. 设图G的邻接矩阵为A， An 的元素An[i][j]等于由顶点i到顶点j的长度为n的路径的数目。

6.2.2 邻接表法

  • 结合了顺序存储方式和链式存储方式，大大减少了不必要的浪费。
  • 对图中的每个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 vi 的边（对于有向图则是以vi为尾的弧），这个链表称为顶点的边表（有向图则称为出边表）。
  • 边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点。
    • 顶点表结点：由顶点域和指向第一条邻接边的指针构成
    • 边表结点：由邻接点域和指向下一条邻接边的指针构成

  1. #define MaxVertexNum 100    //图中顶点数目的最大值
  2. typedef struct ArcNode{    //边表结点
  3.     int adjvex;    //该弧所指向的顶点的位置
  4.     struct ArcNode *next;    //指向下一条弧的指针
  5.     //InfoType info;    //网的边权值
  6. }ArcNode;
  7. typedef struct VNode{    //顶点表结点
  8.     VertexType data;    //顶点信息
  9.     ArcNode *first;    //指向第一条依附该顶点的弧的指针
  10. }VNode,AdjList[MaxVertexNum];
  11. typedef struct{
  12.     AdjList vertices;    //邻接表
  13.     int vexnum,arcnum;    //图的顶点数和弧数
  14. }ALGraph;    //ALGraph是以邻接表存储的图类型

Traits：

  1. 若G为无向图，则所需要的存储空间为O(|V|+2|E|);
    若G为有向图，则所需要的存储空间为O(|V|+|E|);
    前者的倍数2是因为无向图中，每条边在邻接表中出现两次
  2. 对于稀疏图，采用邻接表表示法将极大地洁身存储空间
  3. 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。
  4. 在有向图的邻接表示中，求一个给定顶点的出度只需要计算其邻接表中的节点个数；但是求其顶点的入度则需要遍历所有的邻接表。（可用逆邻接表，也能直接计算出入度）
  5. 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法和边的输入次序。

注：邻接表：反映的是顶点出度的情况。
       逆邻接表：反映的是顶点的入度情况。

6.2.3 十字链表

有向图的一种链式存储方式，表中对应于有向图的每条弧有一个结点，对应于每个顶点也有一个结点。

  • 弧结点（5个域）：尾域和头域分别指示弧尾和弧头这两个顶点在图中的位置；
                                   链域 hlink 指向弧头相同的下一条弧；
                                   链域 tlink 指向弧尾相同的下一条弧；
                                   info域 指向该弧的相关信息。
  • 顶点结点（3个域）：data域 存放顶点相关的数据信息，如顶点名称；
                                       firstin 和 firstout 两个域分别指向以该点为弧头或弧尾的第一个弧结点。

注：其实就是邻接表和逆邻接表的结合。

画法：先画邻接表，再补全对应结点的域（增加弧结点的域），最后“自己指向自己”。 

6.2.4 邻接多重表

无向图的一种链式存储结构。

（边）

  • mark：标志域，可用于标志该条边是否被搜索过
  • ivex 和 jvex：该边依附的两个结点在图中的位置
  • ilink：指向下一条依附于顶点ivex的边
  • jlink：指向下一条依附于顶点jvex的边
  • info：指向和边相关的各种信息的指针域

（顶点）

  • data域：存储该顶点的相关信息
  • firstedge域：指示第一条依附于该顶点的边

注：编组连 

6.2.4 图的基本结构

  • Adjacent(G,x,y)：判断是否存在边
  • Neighbors(G,x)：列出图中与结点x邻接的边
  • InsertVertex(G,x)：在图中插入顶点x
  • DeleteVertex(G,x)：在图中删除顶点x
  • AddEdge(G,x,y)：若无向边或有向边不存在，则向图中添加该边
  • RemoveEdge(G,x,y)：若无向边或有向边存在，则向图中删除该边
  • NextNeighbor(G,x,y)：假设图中顶点y是顶点x的一个邻接点，返回除y外的顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回1。
  • Get_Edge_Value(G,x,y)：获取图中边对应的权值
  • Set_Edge_Value(G,x,y,v) ：设置图中边对应的权值

6.3 图的遍历

从图的某个顶点出发，依次访问图中所有的顶点，每个顶点被访问一次且仅访问一次。
防止多次访问某一个顶点的思路：设置辅助数组visited[n],用来标记每个被访问的顶点，
初始化状态为visited[n]=0;如果顶点被访问到，则修改辅助数组的值 ：visited[i]=1

6.3.1 广度优先搜索

广度优先搜索（Breadth First Search，BFS）类似于树的按层次遍历的过程。广度优先搜索遍历的过程如下：

  • 从图中某个顶点v出发，访问v。
  • 依次访问v的各个未曾访问过的邻接点。
  • 分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复该步骤，直至图中所有已被访问的顶点的邻接点都被访问到。

Key：

  1. 找到与一个顶点相邻的所有顶点；
  2. 标记哪些顶点被访问过；
  3. 需要一个辅助队列。
  1. //BFS伪代码
  2. bool visited[Max_vertex_num];    //访问标记数组
  3. void BFSTraverse(Graph G) {    
  4.     for (int i = 0; i < G.vexnum; ++i)
  5.         visited[i] = false;     //访问数组初始化
  6.     InitQueue(Q);    //初始化辅助队列Q
  7.     for (int i = 0; i < G.vexnum; ++i){
  8.         if(!visited[i])
  9.             BFS(G, i);         //对每个连通分量调用一次BFS
  10.     }
  11. }
  • 无论采用邻接表还是邻接矩阵，BFS都需要借助一个辅助队列，所有顶点均需入队一次。最坏情况下，空间复杂度为 O(|V|)。
    • 采用邻接表存储时，每个顶点均需被搜索依次，时间复杂度为O(|V|)；在搜索任一顶点的边时，每一条边至少访问依次，总时间复杂度为O(|E|)。算法总的时间复杂度为O(|V|+|E|)
    • 采用邻接矩阵存储时，查找每个顶点的所有邻接点的时间为O(V)，算法总的时间复杂度为O(|V|^2)
  1. //BFS算法求解单源最短路径问题
  2.  
  3. const int Int_max = 0x7fffffff;
  4. void BFS_mindist(Graph G, int u) {
  5.     for (int i = 0; i < G.vexnum; ++i)
  6.         d[i] = Int_max;                 // 初始化初始路径长度
  7.     visited[u] = true;
  8.     d[u] = 0;
  9.     EnQueue(Q, u);
  10.     while(!isEmpty(Q)) {
  11.         DeQueue(Q, u);                  // 队头出列
  12.         for (w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
  13.         {
  14.             if(!visited[w]) {           // 访问尚未访问的邻接顶点
  15.                 visited[w] = true;
  16.                 d[w] = d[u] + 1;        // 路径长度+1
  17.                 EnQueue(Q, w);          // 顶点入队
  18.             } // if
  19.         }// for
  20.     }// while
  21. }
  • 广度优先生成树：广度优先生成树由广度优先遍历过程确定。
    • 由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯⼀。 
    • 邻接矩阵表示是唯一的，所以其广度生成树也唯一。

6.3.2 深度优先搜索

深度优先搜索遍历连通图是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited[n]，其初值为“false”，一旦某个顶点被访问，则其相应的分量置为“true”。

深度优先搜索遍历连通图的算法步骤为：

  • 从图中某个顶点v出发，访问v，并置visited[v]的值为true。
  • 依次检查v的所有邻接点w，如果visited[w]的值为false，则再从w出发进行递归遍历，直到图中所有顶点都被访问过。
  1. bool visited[MAX_VERTEX_NUM];
  2. void DFSTraverse(MGraph G){
  3. 	int v; 
  4. 	for(v=0; v<G.vexnum; ++v){
  5. 		visited[v] = FALSE;	//初始化已访问标记数据
  6. 	}
  7. 	for(v=0; v<G.vexnum; ++v){	//从v=0开始遍历
  8. 		if(!visited[v]){
  9. 			DFS(G, v);
  10. 		}
  11. 	}
  12. }

若是非连通图，上述遍历过程执行之后，图中一定还有顶点未被访问。因此，需要从图中另选一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直到图中所有顶点均被访问过为止。这样，要实现对非连通图的遍历，就需要循环调用上述算法。 

  • 深度优先生成树：深度优先生成树由深度优先遍历过程确定。
    • 由于邻接表的表示方式不唯一，因此基于邻接表的深度优先生成树也不唯⼀。 
    • 邻接矩阵表示是唯一的，所以其深度生成树也唯一。

6.4 图的应用

6.4.1 最小生成树（最小代价（权值）树）

基本概念：

  1. 边的权值之和最小的生成树，称为最小生成树。
  2. 最小生成树不唯一（存在权值相等的边，但对应的边的权值之和是唯一的）。
  3. 连通图本身就是一棵树，则它就是最小生成树。
  4. 最小生成树必须是连通图，而非连通图只能是生成森林。

Prim算法（与点有关）：

  • 从某一个顶点开始构建最小生成树，依次加入当前剩余顶点中代价最小的顶点，直到加入所有顶点
  • 时间复杂度：O(|V^{2}|)
  • 适用：稠密图（E大）
  • 每一轮开始都循环遍历所有节点，找到当前代价最低且并没有加入树的结点，再次遍历，更新各个结点的代价

Kruskal算法（与边有关）：

  • 每次选择代价最小的一条边，使该边的两个顶点相通，但是，如果原本就相通的两个顶点的边就不选，直到所有顶点相通
  • 时间复杂度：O(|E|log_{2}^{}|E|)
  • 适用：稀疏图（E小）
  • 共执行e轮，每轮判断两个结点是否属于同一个结点

6.4.2 最短路径

BFS

用额外两个数组分别存储该顶点的前驱和距离源顶点的距离

  1. #define MaxVertexNum 100
  2.  
  3. void BFS(Graph G, int v){
  4.     Queue Q;
  5.     InitQueue(Q);
  6.     EnQueue(v);
  7.     int q, p;
  8.     //dist数组用来存放当前顶点到源顶点的距离，pre存放当前顶点的前驱顶点
  9.     int dist[MaxVertexNum] = { 0 }, pre[MaxVertexNum] = { 0 };
  10.     bool visited[MaxVertexNum] = { false };
  11.     //源顶点的前驱置为-1
  12.     pre[v] = -1;
  13.     //源顶点标记已访问
  14.     visited[v] = true;
  15.     //cur标记当前距离顶点的距离
  16.     int cur = 0;
  17.     while(!IsEmpty(Q)){
  18.         DeQueue(Q, p);
  19.         cur++;
  20.         for (q = FirstNeighbor(G, p); q >= 0; q = NextNeighbor(G, p, q)){
  21.             if (!visited[q]) {
  22.                 //将q设置为已标记
  23.                 visited[q] = true;
  24.                 //入队q
  25.                 EnQueue(Q, p);
  26.                 //更新q距离源顶点的距离
  27.                 dist[q] = cur;
  28.                 //更新q的前驱
  29.                 pre[q] = p;
  30.             }//if
  31.         }//for
  32.     }//while
  33. }

注：BFS其实就是把无权图当做全部边权为1的带权图来进行处理的。（同样这就是它的局限性） 

Dijkstra算法
  • 顶点集合S：记录已求得的最短路径的顶点
  • final[ ]：记录各顶点是否已找到最短路径（即是否归入集合S）
  • dist[ ]：距离源点的最短距离
  • path[ ]：存储到此点路径的前驱结点
  • 时间复杂度：O()
    • 每轮都需要遍历两边数组（顶点集），第一遍查找当前距离最短且未被标记的顶点，第二遍更新以该顶点为路径的信息，一共要执行n - 1轮，因此，时间复杂度为O(|V|^{2})，即O(n^{2})（与Prim算法的思想很类似）

注：Dijkstra算法并不适用于图中边权为负值的情况。

       Dijkstra算法是贪心算法，因此得到的未必是最优解。

Floyd算法

这其实就是一个递归（贪心））的算法了，也就是把一个大问题先拆分成几个小问题。

需要新建两个二维数组：

  • A：保存当前最短路径长度
  • path：最短路径的前驱
  • 时间复杂度：O(|V|^3)

Core code

  1. for(k=1;k<=n;k++)
  2.     for(i=1;i<=n;i++)
  3.         for(j=1;j<=n;j++) {
  4.             if(d[i][k]+d[k][j]<d[i][j]) {
  5.                 d[i][j]=d[i][k]+d[k][j];
  6.                 path[i][j]=path[i][k];
  7.             }
  8.         }

 注：带负权回路的图很有可能没有最小生成树。

6.4.3 有向无环图描述表达式

DAG(Directed Acyclic Graph)：有向无环图（有向图中不存在回路）

解题方法（咸鱼学长版）：

  1. 把各个操作数不重复地排成一排
  2. 标出各个运算符的生效顺序（先后顺序有点出入无所谓）
  3. 按顺序加入运算符，注意“分层”
  4. 从底向上逐层检查同层的运算符是否可以合体 

6.4.4 拓扑排序

  1. bool TopologicalSort(Graph G)
  2. {
  3.     InitStack(G);
  4.     for(int i=0; i<G.vexnum; ++i)
  5.         if(indegree[i] == 0)
  6.             Push(S,i);         // 将所有入度为0的顶点入队
  7.  
  8.     int count = 0;             // 计数，记录当前已经输出的顶点数 
  9.     while(!IsEmpty())
  10.     {           
  11.         Pop(S,i);        // 从队列中取出一个顶点
  12.         print[count++]=i;     // 输出该顶点
  13.         // 将所有i指向的顶点的入度减1，并将入度减为0的顶点入栈
  14.         for(p=G.vertices[i].firstarc;p;p->nextarc){
  15.             v=p->adjvex;
  16.             if(!(--indegree[v))
  17.                 Push(S,v);    // 若入度为0，则入栈
  18.     }
  19.  
  20.     if(count<G.vexnum)
  21.         return false;           // 没有输出全部顶点，有向图中有回路
  22.     else
  23.         return true;            // 拓扑排序成功
  24. }
  1. //逆拓扑排序
  2. #define MaxVertexNum 100
  3.  
  4. bool visited[MaxVertNum] = {false};
  5.  
  6. void DPS_Init(Graph G){
  7.     for (int i = 0; i < G.verNum; i++){
  8.         if (!visited[i]) DFS(G, i);
  9.     }
  10. }
  11.  
  12. void DFS(Graph G, int v){
  13.     visited[v] = true;
  14.     int w;
  15.     for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w){
  16.         if (!visited[w]) DFS(G, w);
  17.     }
  18.     cout << v << endl;
  19. }

6.4.5 关键路径

AOE网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销。

  • 开始顶点（源点）：在AOE中唯一的一入度为0的顶点，表示整个工程的开始；
  • 结束顶点（汇点）：在AOE中唯一的一出度为0的顶点，表示整个工程的结束；
  • 关键路径：源点到汇点的最大路径长度的路径称为关键路径；
  • 关键活动：关键路径上的活动为关键活动；
  • 事件的最早发生时间 ve(k)：决定了所有从开始的活动能开工的最早时间
  • 活动的最早开始时间 e(i)：指该活动弧的起点所表示的事件的最早发生时间
  • 事件的最晚发生时间 vl(k：在不推迟整个工程完成的情况下，该事件最晚发生时间
  • 活动的最晚开始时间 l(i)：该活动弧的终点所表示的事件的最晚发生时间和该活动所需时间的差值
  • 活动的时间余量d(i) = l(i) - e(i)：表示该活动在不增加整个工程完成时间的情况下，最多可以拖延的时间。特别的，当时间余量为0，即l(i) - e(i) = 0时，该活动为关键活动。

求解方法：

  1. 求所有事件的最早发生时间 ve（）
  2. 求所有事件的最迟发生时间 vl（）
  3. 求所有活动的最早发生时间 e(）
  4. 求所有活动的最迟发生时间 |（）
  5. 求所有活动的时间余量 d（）

特性：

  1. 关键活动时间增加，整个工程时间增加
  2. 关键活动时间降低，整个工期时间降低，但是，关键活动的时间降低到一定程度时，关键活动可能会变成非关键活动
  3. 关键路径可能有多条，只提高一条关键路径上的关键活动可能并不能降低整个工程的时间，但是降低所有关键路径上都存在的关键活动一定能降低整个工程的时间

采用不同存储结构时，各种图算法的时间复杂度：

七、查找

7.1 查找的基本概念

  • 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
  • 查找表(查找结构)：用于查找的。数据集合称为查找表，它由同一类型的数据元素 (或记录)组成。
    • 静态查找表：只需要查找操作
    • 动态查找表：除了查找，还需要考虑增加/删除数据元素的操作。
  • 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
  • 查找长度：在查找运算中，需要对比关键字的次数称为查找长度。
    • 平均查找长度(ASL，Average Search Length)： 所有查找过程中进行关键字的比较次数的平均值。（查找算法的效率评价标准）

7.2 顺序查找和折半查找

7.2.1 顺序查找

又称为线性查找，它对顺序表和链表都是适用的。

基本思想：其实就是挨个找（从头到jio or 反着来都可以）。

代码实现：

  1. typedef struct{				//查找表的数据结构（顺序表）
  2.     ElemType *elem;			//动态数组基址
  3.     int TableLen;			//表的长度
  4. }SSTable;
  5.  
  6. //顺序查找
  7. int Search_Seq(SSTable ST,ElemType key){
  8.     int i;
  9.     for(i=0;i<ST.TableLen && ST.elem[i]!=key;++i);
  10.     // 查找成功返回数组下标，否则返回-1
  11.     	return i=ST.TableLen? -1 : i;
  12. }
  13.  
  14.  
  15. //哨兵版
  16. typedef struct{				//查找表的数据结构（顺序表）
  17.     ElemType *elem;			//动态数组基址
  18.     int TableLen;			//表的长度
  19. }SSTable;
  20.  
  21. //顺序查找
  22. int Search_Seq(SSTable ST,ElemType key){
  23.     ST.elem[0]=key;
  24.     int i;
  25.     for(i=ST.TableLen;ST.elem[i]!=key;--i)
  26.     // 查找成功返回数组下标，否则返回0
  27. 	    return i;
  28. }

注： 

  1. 一个成功结点的查找长度 = 自身所在层数
  2. 一个失败结点的查找长度 = 其父节点所在
  3. 层数默认情况下，各种失败情况或成功情况都等概率发生

7.2.2 折半查找

又称二分查找，它仅适用于有序的顺序表。

基础思想：

  1. 在[low,high]之间寻找目标关键字，每次检查mid=(low,high)/2（向上或者向下取整）。
  2. 根据mid所指元素与目标关键字的大小调整[low,high]的区间。
  3. 若low>high则查找失败。

代码实现：

  1. typedef struct{
  2.     ElemType *elem;
  3.     int TableLen;
  4. }SSTable;
  5.  
  6. // 折半查找
  7. int Binary_Search(SSTable L,ElemType key){
  8.     int low=0,high=L.TableLen,mid;
  9.     while(low<=high){
  10.         mid=(low+high)/2;
  11.         if(L.elem[mid]==key)
  12.             return mid;
  13.         else if(L.elem[mid]>key)
  14.             high=mid-1;					//从前半部分继续查找
  15.         else
  16.             low=mid+1;					//从后半部分继续查找
  17.     }
  18.     return -1;
  19. }

折半查找判定树的构造（爱考）： 取决于mid的取值是向上取整还是向下取整。 

  • 若mid=⌊ (low+high)/2⌋，则对于任何⼀个结点，必有：右⼦树结点数 - 左⼦树结点数 = 0 或 1。
  • 反之向上取整就是：左⼦树结点数 - 右⼦树结点数 = 0 或 1。
  • 折半查找的判定树⼀定是平衡⼆叉树。折半查找的判定树中，只有最下⾯⼀层是不满的。因此，元素个数为 n 时树⾼ h=⌈log2(n+1)⌉ 。
  • 判定树结点关键字：左<中<右，满⾜⼆叉排序树的定义。失败结点：n+1个（等于成功结点的空链域数量）

时间复杂度：O(log2n)

7.2.3 分块查找

又称为“索引顺序查找”，块内⽆序、块间有序。

基础思想:

  1. 索引表记录每个分块的最大关键字、分块的区间
  2. 先查索引表(顺序或折半)、再对分块内进行顺序查找

查找效率分析（ASL）:ASL = 查索引表的平均查找长度+查分块的平均查找长度

(设n个记录均匀分为b块,每块s个记录)

  • 顺序查找索引表
  • 折半查找索引表

注:

  • 若使用折半查找且索引表中不包含⽬标关键字，则最终要停在 low > high，要在 low 所指分块中查找目标关键字。(一定是要在low所指分块中查找)

分块查找的优点：

  • 插入和删除比较容易，无需进行大量移动。
    在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。

分块查找的缺点：

  • 要增加一个索引表的存储空间并对初始索引表进行排序运算。

7.3 树形查找

7.3.1 二叉排序树(BST)

构造一颗二叉排序树的目的并不是排序，而是提高查找、插入和删除关键字的速度，这种非线性结构也有利于插入和删除的实现。

定义：二叉排序树又称为二叉查找树，特点为：左子树节点值<根节点值<右子树节点值（因此对二叉排序树进行中序遍历，可得到一个递增的有序序列。）

查找：从根节点开始，沿某个分支逐层向下比较的过程：若BST非空，则先将给定值与根节点的关键字比较，若相同则成功；若小于根节点关键字则沿其左子树根节点向下进行类似操作；若大于根节点关键字则沿其右子树根节点向下进行类似操作。

  1. typedef struct BSTNode{
  2.     int key;
  3.     struct BSTNode *lchild, *rchild;
  4. }BSTNode, *BSTree;
  5.  
  6. //查找（非递归）
  7. BSTNode *BST_Search(BiTree T, ElemType key)
  8. {
  9.     while(T != NULL && key != T->data)    //若树空或等于根结点数，则结束循环
  10.     {
  11.         if(key<T->data)    //小于，则在左子树上查找
  12.             T = T->lchild;
  13.         eles    //大于，则在右子树查找
  14.             T = T->rchild;
  15.     }
  16.     return T;    //失败会返回NULL
  17. }
  18.  
  19. //查找（递归）
  20. BSTNode *BST_Search(BiTree T, ElemType key)
  21. {
  22.     if(T == NULL)
  23.         return NULL;
  24.     if(key == T->key)
  25.         return T;
  26.     else if(key < T->key)
  27.         return BST_Search(T->lchild, key);
  28.     else if
  29.         return BST_Search(T->rchild, key);
  30. }

BST是一种动态生成的树表，通过查找比较不断生成。

Step：

  1. 若BST为空则直接插入；
  2. 若BST非空，比较待插入数据的值与根节点的值，若小于则下移插入左子树，若大于则下移插入右子树；
  3. 在子树中将节点与子树根节点进行比对，进行类似步骤2的操作，直到节点插入到对应的叶节点位置上（ = 查找失败路径上访问的最后一个节点的孩子）。
  1. //最坏时间复杂度O(h)
  2. int BST_Insert(BiTree &T, KeyType key)
  3. {
  4.     if(T == NULL)
  5.     {
  6.         T = (BiTree)malloc(sizeof(BSTNode));
  7.         T->data = k;
  8.         T->lchild = T->rchild = NULL;
  9.         return 1;
  10.     }
  11.     else if(key == T->data)
  12.         return 0;
  13.     eles if(key<T->data)
  14.         return BST_Insert(T->lchild, key);
  15.     else
  16.         return BST_Insert(T->rchild, key);
  17. }

构造：从空树开始以此输入元素调用插入函数，逐渐构造出一棵树。

  1. void Creat_BST(BiTree &T, KeyType str[], int n)
  2. {
  3.     T = NULL;
  4.     int i = 0;
  5.     while(i<n)
  6.     {
  7.         BST_Insert(T, str[i++]);
  8.     }
  9. }

注： BST的生成与输入的顺序相关，相同数据按不同顺序输入得到的BST树也不同（不同的关键字序列可能得到相同的BST，也可能得到不同的BST）。

删除：

需要保证删除该节点后其左右子树接到原树，且仍保持BST特征。

  1. 若删除的是叶节点，则直接删除，不会破坏BST性质
  2. 若删除节点z只有一棵左子树或右子树，则让子树根节点直接替代节点z的位置
  3. 若删除节点z有左右两棵子树，则令z的直接后继（或前驱）替代z，然后从二叉排序树中删除这个直接后继（或前驱），这样就转换成情况1、2

        注：情况3中的直接后继或前驱为中序遍历中的后继或前驱，可能为左子树最右下节点或右子树最左下节点（值与根节点最接近，不打破大小排序关系）

效率分析：（与树高相关）

  • BST中某个元素的比较次数 = 该节点所在层的层数。
  • 理想状态下树高 = \log_{2}(n+1)（向上取整）——看完全二叉树部分

7.3.2 平衡二叉树（AVL）

定义：在插入和删除节点时保证任意结点的左右子树高度差的绝对值小于1

平衡因子：结点左子树的高 - 右子树的高（只能是 -1，0，1）

插入：为保证树的平衡，在插入节点时需检查插入路径上的节点是否因为此次的插入而出现不平衡，如果发生则找到距离插入节点最近的不平衡节点A（最小不平衡子树），对以A为根的树进行调整使其达到平衡。

Step：

  1. LL型（右单旋——父变爷，爷变右兄）
  2. RR型（左单旋——父变爷，爷变左兄）
  3. LR型（左右双旋——子变爷，父左子，爷右子）
  4. RL型（右左双旋——子变爷，父右子，爷左子）

注：看书上的可能会很绕啊，但其实就是想想怎么凑成“平衡”。

删除：这个就和操作很类似，同样需要进行平衡性的检查。

Step：

  1. 用BST方法对节点X进行删除
  2. 若出现不平衡现象则从节点X向上进行回溯（向上找最小不平衡子树），找到第一个不平衡节点A，B为节点A最近的孩子节点，C是B最近的孩子节点（找“个头”最高的儿孙节点），然后以A为根，利用与插入相同的四种调整方法进行判断调整（LL、RR、LR、RL）
  3. 如果还是不平衡就继续向上，重复第2步

注：删除和插入对结点的调整方式大差不差，buttt插入仅针对最小不平衡子树A，而删除可能要一直“回溯”。

查找：AVL中查找操作与BST相同，因此查找时与给定值比较的关键字个数不超过树高，因此，含n个节点的AVL树的最大深度为O(\log_{2}n)，因此AVL的平均查找长度为O(\log_{2}n)

7.3.3 红黑树（有点点难！！）

红黑树不是AVL喔~是BST（二叉排序树）

  1. 每个结点或是红色或是黑色的。
  2. 根结点是黑色的。
  3. 叶结点（虚构的外部结点、NULL结点）都是黑色的。
  4. 不存在两个相邻的红结点
  5. 对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。

注：根黑叶黑不红红，黑路数同左根右

性质：

  1. 从根节点到叶节点的最长路径不大于最短路径的 2 倍
  2. 有n个内部节点的红黑树的高度 h<=2log2(n+1)
  3. 红黑树的黑高（根节点到叶节点路径上黑色节点数量）至少为 h/2
  4. 红黑树查找操作时间复杂度 = O(log2n)
  5. 若根节点黑高为h，则内部节点最少为 2^h-1

插入（困难点）：新插入红黑树的结点初始着为红色

  1. 若新节点是根节点，染为黑色；
  2. 若插入后仍满足红黑树定义（仅需查看是否满足不红红，其他三条都不会被打破），若满足则插入结束，若不满足，根据其叔叔（父节点的兄弟节点）的颜色进行相应调整：
    1. 黑叔：旋转+染色（染色就是换成和之前不同的颜色）
      1. LL型：右单旋，父换爷+染色（指给父和原爷节点染色）
      2. RR型：左单旋，父换爷+染色
      3. LR型：左右双旋，儿换爷+染色（指给儿和原爷节点染色）
      4. RL型：右左双旋，儿换爷+染色
    2. 红叔：染色+变新——叔父爷染色，爷变成新节点

删除（基本不考）：后面再补！

注：

  • 平衡二叉树：适用于以查找为主、很少插入/删除的场景
  • 红黑树：适用于频繁插入、删除的场景，实用性更强

7.4 B树

7.4.1 B树及其基本操作

所谓m阶B树是所有结点的平衡因子均等于0的m路平衡查找树。（绝对平衡的树）

⼀棵m阶B树或为空树，或为满⾜如下特性的m叉树：

  1. 树中每个结点⾄多有 m 棵⼦树，即⾄多含有 m-1 个关键字。
  2. 若根结点不是终端结点，则⾄少有两棵⼦树。
  3. 除根结点外的所有⾮叶结点⾄少有 ⌈m/2⌉ 棵⼦树，即⾄少含有 ⌈m/2⌉ -1 个关键字。（为了保证查找效率，每个结点的关键字不能太少）
  4. 所有⾮叶结点的结构如下：
  5. 其中，Ki(i = 1, 2,…, n)为结点的关键字，且满⾜K1 < K2 <…< Kn；Pi(i = 0,1,…, n)为指向⼦树根结点的指针，且指针Pi-1所指⼦树中所有结点的关键字均⼩于Ki，Pi所指⼦树中所有结点的关键字均⼤于 Ki， n(⌈m/2⌉-1≤n≤m-1)为结点中关键字的个数。
  6. 所有的叶结点都出现在同⼀层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

注：在408真题中将B树的叶结点定义为最底层的终端结点。（失败结点还要再下一层）

m阶B树的核⼼特性（学长总结）：

  1. 根节点的⼦树数∈[2,m]，关键字数∈[1,m−1]。
  2. 其他结点的⼦树数∈[⌈m/2⌉,m]；关键字数∈[⌈m/2⌉-1,m−1]。
  3. 对任⼀结点，其所有⼦树⾼度都相同。
  4. 关键字的值：⼦树0 < 关键字1 < ⼦树1 < 关键字2 < ⼦树2 <…. (类⽐⼆叉查找树左<中<右)
  5. 含 n 个关键字的 m叉B树，最小高度、最大高度

基本操作：

B树的查找：B树的查找操作与二叉查找树类似。

  1. 在B树中找结点；
  2. 在结点中找关键字。

B树常存储在磁盘上，因此前一个查找操作在磁盘上进行，后一个查找操作在内存中进行。在B树中查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应指针信息到所指的子树中去查找。查找到叶子结点（对应指针为空指针），则说明树中没有对应的关键字，查找失败。

B树的插入：

  • 通过“查找”确定插入位置（一定是在终端结点）
    • 若插入后结点关键字没有超过上限，则无需做其他处理
    • 反之，需要将当前结点的中间元素放到父结点中，当前结点分裂成两个部分；
      • 若导致父结点关键字个数也超过了上限，则需要再向上分裂；

注：根结点的分裂会导致B树高度加1

B树的删除：

  • 非终端结点关键字
    • 用其直接前驱或直接后继代替其位置，转化为对“终端结点”的删除。
      • 直接前驱：当前关键字左边指针所指子树中“最右下”的元素
      • 直接后继：当前关键字右边指针所指子树中“最左下”的元素
  • 终端结点关键字
    • 删除后结点关键字个数没有低于下限
      • 无需任何处理
    • 删除后结点关键字个数低于下限
      • 右兄弟够借，则用当前结点的后继、后继的后继依次顶替空缺
      • 左兄弟够借，则用当前结点的前驱、前驱的前驱依次顶替空缺
      • 兄弟都不够借，则需要与父结点的关键字、兄弟进行合并。（合并后导致父结点关键字数量-1，可能需要继续合并）

注：其实就是在过程中要一直保持核心特性（2 and 4）

7.4.2 B+树的基本概念

B+树是应数据库所需而出现的一种B树的变形树。

一棵m阶的B+树需满足以下条件：

  1. 每个分支节点最多有m棵子树（孩子结点）。
  2. 非叶根结点至少有两颗子树，其他每个分支结点至少有⌈m/2⌉棵子树。
  3. 结点的子树个数与关键字个数相同。
  4. 所有叶子结点包含所有关键字及指向相应记录的指针，叶子结点中将关键字按大小排列，并且相邻叶子结点按大小顺序相互链接起来。（说明B+树支持顺序查找）
  5. 所有分支节点仅包含它的各个节点中关键字的最大值及指向其子节点的指针。

7.5 散列(Hash)表

7.5.1 散列表的基本概念

  • 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记作Hash(key)=Addr。
  • 散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突。发生碰撞的不同关键字称为同义词。
  • 散列表：根据关键字而直接进行访问的数据结构。散列表建立了关键字和存储地址之间的一种直接映射关系。

7.5.2 散列函数的构造方法

常见的几种散列函数：

  1. 直接定址法：直接取关键字的某个线性函数值为散列地址，散列函数为H(key)=key 或H(key)=a×key+b。这种方法计算简单，不会产生冲突。缺点是空位较多，会造成存储空间浪费。
  2. 除留余数法：假定散列表表长 m，取一个不大于但最接近 m 的质数 p，利用散列函数H(key)=key%p 将关键字转换为散列地址。p取质数是因为这样可以使关键字通过散列函数转换后等概率地映射到散列空间上的任一地址。
  3. 数字分析法：假设关键字是 r进制数，而r个数码在个位上出现的频率不一定相同，可能在某些位上分布的均匀一些，而在某些位分布的不均匀。此时应选数码分布均匀的若干位作为散列地址。
  4. 平方取中法：这种方法取关键字平方值的中间几位作为散列地址，具体取多少位视具体情况而定。这种方法得到的散列地址与关键字的每一位都有关系，因此使得散列地址分布比较均匀。适用于关键字每位取值都不够均匀或均小于散列地址所需的位数。

7.5.3 处理冲突的方法

  1. 开放定址法：指可存放新表项的空闲抵制既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为：Hi=(H(key)+di)%m 其中，H(key)为散列函数，i=0,1,2,...,k(k≤m-1)，m表示散列表表长，di为增量序列。增量序列通常有四种取法：
    1. 线性探测法：di=0,1,2,...,m−1。使用方法发生冲突时，顺序查看下一个单元，直到找到一个空闲单元或查遍全表。使用这种方法可能造成大量元素在相邻的散列地址上堆积起来，大大降低了查找效率。使用这种方法删除元素时需要做标记，否则会影响查找元素。
    2. 平方探测法：。其中k≤m/2，散列表长度m必须是一个可以表示为4k+3 的质数（符合这个条件才能够探测到所有位置）。使用这种方法可以避免堆积问题。
    3. 再散列法：di=H2(key)。当通过第一个散列函数H(key) 得到的地址发生冲突时，则利用第二个散列函数H2(key)再次计算该关键字的地址。其散列函数为：Hi=RHi(key)。
    4. 伪随机序列法：di = 伪随机序列。
  2. 拉链法：对于不同的关键字通过散列函数映射到同一地址时，为了与避免非同义词发生冲突，可以把所有的同义词存储到一个线性链表中。拉链法适用于经常进行插入和删除的方法。

7.5.4 散列查找及性能分析

散列查找执行步骤如下：

  1. 初始化：Addr=Hash(key)
  2. 检测查找表中地址为 Addr 的位置上是否有记录，若无记录，返回查找失败；若有记录，比较它和 key 的值，若相等则返回查找成功，否则执行步骤3。
  3. 用给定的处理冲突方式计算“下一个散列表地址”，并把 Addr 置为此地址，转入步骤2。

平均查找长度（ASL）：

  1. 散列表查找成功的平均查找长度即找到表中已有表项的平均比较次数；

  2. 散列表查找失败的平均查找长度即找不到待查的表项但能找到插入位置的平均比较次数。

装填因子：一般计为 α，即一个表的装满程度。α= 散列表长度m/表中记录数n

八、排序

8.1 排序的基本概念

排序：就是重新排列表中的元素，使表中的元素按关键字有序的过程。

8.2 插入排序

8.2.1 直接插入排序

算法思想：每次将一个待排序的记录按其关键字大小，插入到前面已经排好序的子序列中，直到全部记录插入完成。

 实现代码：

  1. // 对A[]数组中共n个元素进行插入排序
  2. void InsertSort(int A[],int n){
  3.     int i,j,temp;
  4.     for(i=1; i<n; i++){
  5.         if(A[i]<A[i-1]){    	//如果A[i]关键字小于前驱
  6.             temp=A[i];  
  7.             for(j=i-1; j>=0 && A[j]>temp; --j)
  8.                 A[j+1]=A[j];    //所有大于temp的元素都向后挪
  9.             A[j+1]=temp;
  10.         }
  11.     }
  12. }
  13.  
  14. //带哨兵
  15. // 对A[]数组中共n个元素进行插入排序
  16. void InsertSort(int A[], int n){
  17.     int i,j;
  18.     for(i=2; i<=n; i++){
  19.         if(A[i]<A[i-1]){
  20.             A[0]=A[i];     	//复制为哨兵，A[0]不放元素
  21.             for(j=i-1; A[0]<A[j]; --j)
  22.                 A[j+1]=A[j];
  23.             A[j+1]=A[0];
  24.         }
  25.     }
  26. }
  27.  
  28. //链表
  29. void InsertSort(LinkList &L){
  30.     LNode *p=L->next, *pre;
  31.     LNode *r=p->next;
  32.     p->next=NULL;
  33.     p=r;
  34.     while(p!=NULL){
  35.         r=p->next;
  36.         pre=L;
  37.         while(pre->next!=NULL && pre->next->data<p->data)
  38.             pre=pre->next;
  39.         p->next=pre->next;
  40.         pre->next=p;
  41.         p=r;
  42.     }
  43. }

算法性能分析：

  • 时间复杂度：
    • 最好情况 O(n)（原始数列有序或接近有序）
    • 最差情况 O(n^2)
    • 平均情况 O(n^2)
  • 空间复杂度：O(1)。
  • 稳定性：稳定
  • 适用性：适用于顺序存储和链式存储的线性表。

8.2.2 折半插入排序

算法思路： 每次将一个待排序的记录按其关键字大小，使用折半查找找到前面子序列中应该插入的位置并插入，直到全部记录插入完成。

实现代码：

  1. //对A[]数组中共n个元素进行折半插入排序
  2. void InsertSort(int A[], int n){ 
  3.     int i,j,low,high,mid;
  4.     for(i=2; i<=n; i++){            //依次将A[2]~A[n]插入前面的已排序序列
  5.         A[0]=A[i];    		     	 //将A[i]暂存到A[0]
  6.             low=1; high=i-1;
  7.         while(low<=high){            //折半查找
  8.             mid=(low+high)/2;        //取中间点
  9.             if(A[mid]>A[0])
  10.                 high=mid-1;
  11.             else
  12.                 low=mid+1;
  13.         }
  14.         for(j=i-1; j>high+1; --j)
  15.             A[j+1]=A[j];            //统一后移元素，空出插入位置
  16.         A[high+1]=A[0];
  17.     }
  18. }

注：为了保证算法的稳定性，当查找到和插入元素关键字一样的元素时，应该在这个元素的右半部分继续查找以确认位置。即当 A[mid] == A[0] 时，应继续在mid所指位置右边寻找插入位置。 

算法性能分析：

  • 时间复杂度：
    • 最好情况 O(n)（原始数列有序或接近有序）
    • 最差情况 O(n^2)
    • 平均情况 O(n^2)
  • 空间复杂度：O(1)。
  • 稳定性：稳定
  • 适用性：适用于顺序存储的线性表。

8.2.3 希尔排序（Shell Sort）

算法思路：先追求表中元素的部分有序，再逐渐逼近全局有序，以减小插入排序算法的时间复杂度。

先将待排序表分割成若干形如L[i,i+d,i+2d,...,i+kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到 d=1 为止。

实现代码：

  1. // 对A[]数组共n个元素进行希尔排序
  2. void ShellSort(ElemType A[], int n){
  3.     int d,i,j;
  4.     for(d=n/2; d>=1; d=d/2){  	//步长d递减（无统一规定）
  5.         for(i=d+1; i<=n; ++i){
  6.             if(A[i]<A[i-d]){
  7.                 A[0]=A[i];		//A[0]做暂存单元，不是哨兵
  8.                 for(j=i-d; j>0 && A[0]<A[j]; j-=d)
  9.                     A[j+d]=A[j];    //记录后移，查找移动的位置
  10.                 A[j+d]=A[0];        //移动
  11.             }
  12. 		}
  13.     }
  14. }

算法性能分析：

  • 时间复杂度：依赖于增量序列的函数
    • n在某个特顶范围时可达O(n^1.3) 
    • 最差情况 O(n^2)
  • 空间复杂度：O(1)。
  • 稳定性：不稳定
  • 适用性：适用于顺序存储的线性表（因为希尔排序需要能够随机访问）。

8.3 交换排序

8.3.1. 冒泡排序

算法思路：从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i−1]>A[i]），则交换它们，直到序列比较完。如此重复最多 n-1 次冒泡就能将所有元素排好序。

注：为保证稳定性，关键字相同的元素不交换。

实现代码：

  1. // 交换a和b的值
  2. void swap(int &a, int &b){
  3.     int temp=a;
  4.     a=b;
  5.     b=temp;
  6. }
  7.  
  8. // 对A[]数组共n个元素进行冒泡排序
  9. void BubbleSort(int A[], int n){
  10.     for(int i=0; i<n-1; i++){
  11.         bool flag = false; 			//标识本趟冒泡是否发生交换
  12.         for(int j=n-1; j>i; j--){
  13.             if(A[j-1]>A[j]){
  14.                 swap(A[j-1],A[j]);
  15.                 flag=true;
  16.             }
  17.         }
  18.         if(flag==false)
  19.             return;       //若本趟遍历没有发生交换，说明已经有序
  20.     }
  21. }

 算法性能分析：

  • 时间复杂度：
    • 最好情况 O(n)（原始数列有序或接近有序）
    • 最差情况 O(n^2)（原始数列逆序）
    • 平均情况 O(n^2)
  • 空间复杂度：O(1)。
  • 稳定性：稳定
  • 适用性：适用于顺序存储和链式存储的线性表。

8.3.2. 快速排序

顾名思义，快速排序是所有内部排序算法中性能最优的排序算法。

算法思路：（分治法）在待排序表 L[1...n] 中任选一个元素 pivot 作为枢轴（通常取首元素），通过一趟排序将待排序表分为独立的两部分 L[1...k−1] 和 L[k−1...n]。使得L[1...k−1] 中的所有元素小于 pivot，L[k−1...n] 中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L[k] 上。重复此过程直到每部分内只有一个元素或空为止。

注：

  1. 在快速排序算法中每一趟都会将枢轴元素放到其最终位置上。（可用来判断进行了几趟快速排序）
  2. 快速排序可以看作数组中n个元素组织成二叉树，每趟处理的枢轴是二叉树的根节点，递归调用的层数是二叉树的层数。

实现代码：

  1. // 用第一个元素将数组A[]划分为两个部分
  2. int Partition(int A[], int low, int high){
  3.     int pivot = A[low];    //用第一个元素作为枢轴
  4.     while(low<high){
  5.         while(low<high && A[high]>=pivot)
  6.             --high;    //比枢轴小的元素移动到左端
  7.         A[low] = A[high];
  8.         while(low<high && A[low]<=pivot) 
  9.             ++low;    //比枢轴大的元素移动到右端
  10.         A[high] = A[low];
  11.     }
  12.     A[low] = pivot;    //枢轴元素存放到最终元素
  13.     return low;    //放回存放枢轴的最终位置
  14. } 
  15.  
  16. // 对A[]数组的low到high进行快速排序
  17. void QuickSort(int A[], int low, int high){
  18.     if(low<high){    //递归跳出的条件
  19.         int pivotpos = Partition(A, low, high);  //划分
  20.         QuickSort(A, low, pivotpos - 1);
  21.         QuickSort(A, pivotpos + 1, high);
  22.     }
  23. }

 算法性能分析：

  • 时间复杂度：O(n * 递归调用的层数)
    • 最好情况：O(nlog2n)
    • 最差情况：O(n^2)
    • 平均情况：O(n^2)
  • 空间复杂度：O(递归调用的层数)
    • 最好情况：O(log2n)
    • 最差情况：O(n^2)
    • 平均情况：O(n^2)
  • 稳定性：不稳定
  • 适用性：仅适用于顺序存储的线性表。

8.4 选择排序

选择排序：每一趟在待排元素中选取关键字最小（或最大）的元素加入有序子序列。

8.4.1 简单选择排序

算法思路：每一趟在待排序元素中选取关键字最小的元素与待排序元素中的第一个元素交换位置。

实现代码：

  1. // 交换a和b的值
  2. void swap(int &a, int &b){
  3.     int temp = a;
  4.     a = b;
  5.     b = temp;
  6. }
  7.  
  8. // 对A[]数组共n个元素进行选择排序
  9. void SelectSort(int A[], int n){
  10.     for(int i=0; i<n-1; i++){          	//一共进行n-1趟，i指向待排序序列中第一个元素
  11.         int min = i;
  12.         for(int j=i+1; j<n; j++){		//在A[i...n-1]中选择最小的元素
  13.             if(A[j]<A[min])
  14.                 min = j;
  15.         }
  16.         if(min!=i)                     
  17.             swap(A[i], A[min]);
  18.     }
  19. }

 算法性能分析：

  • 时间复杂度：无论待排序序列有序、逆序还是乱序，都需要进行 n-1 次处理，总共需要对比关键字(n-1)+(n-2)+...+1= n(n-1)/2(n−1)+(n−2)+...+1=n(n−1)/2 次，因此时间复杂度始终是 O(n^2)（不会因为序列的初始状态不同而发生改变）
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 适用性：仅适用于顺序存储和链式存储的线性表。

 链表的实现代码：

  1. void selectSort(LinkList &L){
  2.     LNode *h=L,*p,*q,*r,*s;
  3.     L=NULL;
  4.     while(h!=NULL){
  5.         p=s=h; q=r=NULL;
  6.         while(p!=NULL){
  7.             if(p->data>s->data){
  8.                 s=p; r=q;
  9.             }
  10.             q=p; p=p->next;
  11.         }
  12.         if(s==h)
  13.             h=h->next;
  14.         else
  15.             r->next=s->next;
  16.         s->next=L; L=s;
  17.     }
  18. }

8.4.2 堆排序

堆的基本概念：

（大根堆）

  • 大根堆：完全二叉树中，根 ≥ 左右，即 L[i]≥L[2i] 且 L[i]≥L[21+1]
  • 小根堆：完全二叉树中，根 ≤ 左右，即 L[i]≤L[2i] 且 L[i]≤L[2i+1]
  • 其实就很像而完全二叉树（只不过多加了几条规则）
  •  堆的删除：被删除的元素用堆底元素替换，然后让该元素不断“下坠”，直到无法下坠为止。
  • 堆的插入：对于大（或小）根堆，要插入的元素放到表尾，然后与父节点对比，若新元素比父节点更大（或小），则将二者互换。新元素就这样一路“上升”，直到无法继续上升为止。
  • 关键词对比次数：
    • 每次上升调整需要对比关键字1次
    • 每次下坠调整可能需要对比关键字2次，也可能只需对比1次。

算法思路：首先将存放在 L[1...n] 中的n个元素建成初始堆，由于堆本身的特点，堆顶元素就是最大值。将堆顶元素与堆底元素交换，这样待排序列的最大元素已经找到了排序后的位置。此时剩下的元素已不满足大根堆的性质，堆被破坏，将堆顶元素下坠使其继续保持大根堆的性质，如此重复直到堆中仅剩一个元素为止。

实现代码（包括堆的初始化）：

  1. // 对初始序列建立大根堆
  2. void BuildMaxHeap(int A[], int len){
  3.     for(int i=len/2; i>0; i--) 		//从后往前调整所有非终端结点
  4.         HeadAdjust(A, i, len);
  5. }
  6.  
  7. // 将以k为根的子树调整为大根堆
  8. void HeadAdjust(int A[], int k, int len){
  9.     A[0] = A[k];    //A[0]暂存子树的根结点
  10.     for(int i=2*k; i<=len; i*=2){	//沿k较大的子结点向下调整
  11.         if(i<len && A[i]<A[i+1])	
  12.             i++;
  13.         if(A[0] >= A[i])        //筛选结束
  14.             break;
  15.         else{
  16.             A[k] = A[i];			//将A[i]调整至双亲结点上
  17.             k=i;					//修改k值，以便继续向下筛选
  18.         }
  19.     }
  20.     A[k] = A[0]    //被筛选结点的值放入最终位置
  21. }
  22.  
  23. // 交换a和b的值
  24. void swap(int &a, int &b){
  25.     int temp = a;
  26.     a = b;
  27.     b = temp;
  28. }
  29.  
  30. // 对长为len的数组A[]进行堆排序
  31. void HeapSort(int A[], int len){
  32.     BuildMaxHeap(A, len);         	//初始建立大根堆
  33.     for(int i=len; i>1; i--){      	//n-1趟的交换和建堆过程
  34.         swap(A[i], A[1]);
  35.         HeadAdjust(A,1,i-1);
  36.     }
  37. }

 算法性能分析：

  • 时间复杂度：O(nlog2n)
    • 时间效率：
      • 建堆时间：O(n)
      • 调整操作：n-1次，每次O(h)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 适用性：仅适用于顺序存储的线性表。

注：

  1. 一个结点，每“下坠”一层，最多只需要比对关键词2次
  2. n个结点的完全二叉树树高h=[log2n]+1（向下取整）

 注：基于大根堆排序得到“递增序列”，基于小根堆的堆排序得到“递减序列”

8.5 归并排序、基数排序和计数排序

8.5.1 归并排序

归并：把两个或多个已经有序的序列合并成一个。

 算法思想：把待排序表看作 n 个有序的长度为1的子表，然后两两合并，得到 ⌈n/2⌉ 个长度为2或1的有序表……如此重复直到合并成一个长度为n的有序表为止。

实现代码：

  1. // 辅助数组B
  2. int *B=(int *)malloc(n*sizeof(int));
  3.  
  4. // A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
  5. void Merge(int A[], int low, int mid, int high){
  6.     int i,j,k;
  7.     for(k=low; k<=high; k++)
  8.         B[k]=A[k];    //将A中所有元素复制到B中
  9.     for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
  10.         if(B[i]<=B[j])    //将较小值复制到A中
  11.             A[k]=B[i++];
  12.         else
  13.             A[k]=B[j++];    
  14.     }
  15.     while(i<=mid)
  16.         A[k++]=B[i++];
  17.     while(j<=high) 
  18.         A[k++]=B[j++];
  19. }
  20.  
  21. // 递归操作
  22. void MergeSort(int A[], int low, int high){
  23.     if(low<high){
  24.         int mid = (low+high)/2;    //从中间划分
  25.         MergeSort(A, low, mid);    //对左半部分归并排序
  26.         MergeSort(A, mid+1, high);    //对右半部分归并排序
  27.         Merge(A,low,mid,high);     //归并
  28.     }
  29. }

 算法性能分析：

  • 时间复杂度：O(nlog2n)
    • 时间效率：
      • 每趟归并的时间复杂度：O(n)
      • 归并趟数[log2n]（向上取整）
  • 空间复杂度：O(n)（来自于辅助数组B）
  • 稳定性：稳定
  • 适用性：仅适用于顺序存储和链式存储的线性表。

8.5.2 基数排序（Radix Sort）

算法思想：把整个关键字拆分为d位，按照各个关键字位权重递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。

  • 分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗O(n)。
  • 收集：把各个队列中的结点依次出队并链接。一趟收集耗时O(r)。
  • 权重：影响力（就比如个位的影响力肯定是不如十位的）

注：应该就只考手算。

 算法性能分析：

  • 时间复杂度：O[d(n+r)]（与序列的初始状态无关）
    • 一共进行d趟分配收集，一趟分配需要O(n)，一趟收集需要O(r)
  • 空间复杂度：O(r)，其中r为辅助队列数量。
  • 稳定性：稳定
  • 适用性：仅适用于顺序存储和链式存储的线性表。

基数排序擅长处理的问题：

  1. 数据元素的关键字可以方便地拆分为d组，且d较小。
  2. 每组关键字的取值范围不大，即r较小。
  3. 数据元素个数n较大。

注：比如身份证号分配和中文名排序，但别教条化如果要给10亿个人的身份证号排序的话，基数排序又会变得合适了。

*8.5.3 计数排序（Counting Sort）

算法思想：通过计数每个元素的出现次数来进行排序，适用于整数或有限范围内的非负整数排序。

  • 计数： 遍历待排序的数组，统计每个元素出现的次数，并将统计结果存储在一个计数数组中。计数数组的索引对应着元素的值，而计数数组中的值表示该元素出现的次数。
  • 累积计数： 对计数数组进行累积计数，即将每个元素的计数值加上前一个元素的计数值，得到每个元素在排序后数组中的位置。这一步确保相同元素的相对顺序不变。
  • 排序： 创建一个与待排序数组大小相同的结果数组，然后遍历待排序数组，根据元素的值在累积计数数组中找到其在结果数组中的位置，将元素放置在结果数组中的正确位置。

 算法性能分析：

  • 时间复杂度：
    • 平均时间复杂度：O(n + k)，其中n是待排序数组的大小，k是整数范围。
    • 最坏时间复杂度：O(n + k)。
    • 最佳时间复杂度：O(n + k)。
  • 空间复杂度：O(n + k)，需要额外的计数数组和结果数组。
  • 稳定性：稳定
  • 适用性：仅适用于顺序存储的线性表。

8.6 各种内部排序算法的比较及应用

8.6.1 内部排序算法比较

注：简选、Shell、Quick、堆排4不稳 

8.6.2. 内部排序算法的应用

  1. 选取排序方法需要考虑的因素：
    1. 待排序的元素数目n。
    2. 待排序元素的初始状态
    3. 关键字的结构及其分布情况。
    4. 稳定性的要求。
    5. 语言工具的条件，存储结构及辅助空间的大小等。
  2. 排序算法的选择（排序算法小结）：
  3. 若n较小，可采用 直接插入排序 或 简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。
  4. 若文件的初始状态已按关键字基本有序，则选用 直接插入排序 或 冒泡排序 为宜。
  5. 若n较大，则应采用时间复杂度为 O(nlog2n) 的排序方法：快速排序、堆排序 或 归并排序。
    1. 快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。
    2. 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。
    3. 若要求排序稳定且时间复杂度为 O(nlog 2n)，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后两两归并。直接插入排序是稳定的，因此改进后的归并排序仍是稳定的。
  6. 在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O(nlog2n) 的时间。
  7. 若n很大，记录的关键字位数较少且可以分解时，采用 基数排序 较好。
  8. 当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。

8.7 外部排序

8.7.1 外部排序的基本概念

外部排序：对大文件进行排序时，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。

8.7.2 外部排序的方法

  1. 外部排序的步骤：
    1. 跟据内存缓冲区大小，将外存上的文件分成 r 个子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存（归并段）。
    2. 对这些归并段进行 S 趟 k 路归并，使归并段（有序子文件)逐渐由小到大，直至得到整个有序文件为止，其中S=⌈logkr⌉。（需要在内存中分配k个输入缓冲区和1个输出缓冲区）
  2. 如何进行 k 路归并：
    1. 把k个归并段的块读入k个输入缓冲区。
    2. 用“归并排序”的方法从k个归并段中选出几个最小记录暂存到输出缓冲区中。
    3. 当输出缓冲区满时，写出外存。
  3. 外部排序时间开销 = 读写外存的时间 + 内部排序所需时间＋内部归并所需时间
  4. 优化：
    1. 增加归并路数k，但是需要增加相应的输入缓冲区，且每次从k个归并段中选出一个最小元素需要对比 (k-1) 次。
    2. 减少初始归并段数量r。

注：

     k路平衡归并：

  1. 最多只能有k个段归并为一个；
  2. 每一趟归并中，若有m个归并段参与归并，则经过处理得到 ⌈m/k⌉（向上取整）个新的归并段。

8.7.3 多路平衡归并与败者树

  • 败者树：是树形选择排序的一种变形，本身是一棵完全二叉树（多了一个头头）。
  • k个叶结点：分别对应k个归并段中当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。（是虚拟的）
  • 败者树解决的问题：使用多路平衡归并可以减少归并趟数，但是从 k 个归并段选出一个最小元素需要对比关键字 (k-1) 次，构造败者树可以使关键字对比次数减少到 ⌈log2k⌉。

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

  1. 置换-选择排序：产生更长的初始归并段，从而减少初始归并段数量。
  2. 设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。
  3. 置换-选择算法的步骤如下：
    1. 从FI输入w个记录到工作区WA。
    2. 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。
    3. 将MINIMAX记录输出到FO中去。
    4. 若FI不空，则从FI输入下一个记录到WA中。
    5. 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。
    6. 重复3~5，直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。
    7. 重复2~6，直至WA为空。由此得到全部初始归并段。

8.7.5 最佳归并树

  • 最佳归并树：调整多个初始归并段进行多路归并时的顺序，从而减少多路归并时I/O次数。
  • 理论基础：每个初始归并段对应一个叶子结点，把归并段的块数作为叶子的权值，归并树的WPL = 树中所有叶结点的带权路径长度之和。
    • 归并过程中的磁盘I/O次数 = 归并树的WPL * 2。

注：k叉归并的最佳归并树一定是严格k叉树，即树中只有度为k、度为0的结点。
       k叉归并和k叉归并平衡树不一样喔。

  • 构造k叉哈夫曼树：每次选择k个根节点权值最小的树合并，并将k个根节点的权值之和作为新的根节点的权值。
    • 补充虚段（结点不够）：
      • 若(初始归并段数量−1)%(k−1)=0，说明刚好可以构成严格k叉树，此时不需要添加虚段。
      • 若(初始归并段数量−1)%(k−1)=u≠0，则需要补充 (k−1)−u 个虚段。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/904030
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号