王道-数据结构

王道考研数据结构

绪论

考纲

易混淆的概念

数据结构，逻辑结构,存储结构

数据结构三要素：数据的逻辑结构，数据的存储结构和数据的运算

• 即数据结构种定义了逻辑结构，存储结构

逻辑结构与存储结构之间的关系：存储结构不能独立于逻辑结构，存储结构是逻辑结构再计算机上的映射

名词	例子
数据结构	顺序表，哈希表，单链表
逻辑结构	有序表
物理结构

数据结构的基本概念

基本概念和术语

数据

数据是信息的载体，是描述客观事物属性的数、字符及$\color{yellow}{\text{所有能输入到计算机中}}$并被计算机程序识别和处理的$\color{green}{\text{符号}}$的$\color{green}{\text{集合}}$。数据是计算机程序加工的原料。

是对客观事物的符号表示。

数据元素

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。$\color{yellow}{\text{一个数据元素可由若干数据项组成}}$，$\color{green}{\text{数据项}}$是构成数据元素的不可分割的$\color{red}{\text{最小单位}}$。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象

数据对象是具有相同性质的数据元素的集合，是$\color{green}{\text{数据}}$的一个$\color{green}{\text{子集}}$。例如，整数数据对象是集合$N= \lbrace \pm 0,\pm 1,\pm 2, \cdots \rbrace$。

• 可以理解为数据的一个$\color{green}{\text{实例化对象}}$

数据类型

数据类型是一个$\color{green}{\text{值的集合}}$和定义在此集合上的$\color{green}{\text{一组操作}}$的总称。

1）原子类型。其值不可再分的数据类型。

2）结构类型。其值可以再分解为若干成分（分量）的数据类型。

3）抽象数据类型。抽象数据组织及与之相关的操作。 一个数学模型以及定义在该模型上的一组操作。

数据结构

数据结构是相互之间存在一种或多种特定关系的$\color{red}{\text{数据元素}}$的$\color{red}{\text{集合}}$。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为结构(Structure)。数据结构包括三方面的内容:逻辑结构、存储结构和数据的运算。

数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

数据结构的形式定义

数据结构三要素

数据的逻辑结构

• 线性结构
  • 一般线性表
  • 受限线性表
    • 栈和队列
    • 串
  • 线性表推广
    • 数组
    • 广义表
• 非线性结构
  • 集合
  • 树形结构
    • 一般树
    • 二叉树
  • 图状结构
    • 有向图
    • 无向图

数据的存储结构

顺序结构

链式结构

索引结构

散列存储

数据的运算

• 运算的定义是针对逻辑结构的
• 运算的实现是针对存储结构的

算法和算法评价

算法的基本概念

算法(Algorithm）是对特定问题求解步骤的一种描述，它是指令的$\color{green}{有限}$序列，其中的每条指令表示一个或多个操作。此外，一个算法还具有下列5个重要特性:

• 1）有穷性。
• 2）确定性。
• 3）可行性。
• 4）输入。
• 5）输出。

算法效率的度量

关于时间复杂度的补充，去阅读了算法导论，发现书中的定义更为严谨，比较适合我这种转牛角尖的憨憨,总结：

基本上强调时间复杂度，没有代码就不要提，题目中会预设某些代码逻辑，你可能需要去猜题目的算法是啥：比如为什么关键路径和拓扑排序的时间复杂度是O(n + e)，书中没有细讲，就直接出现了题目

线性表

p24

链表的单双：指的是节点中有$\color{red}{\text{一个(单)}}$指针域，$\color{red}{\text{两个(双)}}$指针域，

线性表的定义和基本操作

线性表的定义

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

$$L=(a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n)$$

式中，$a_1$是唯一的“第一个”数据元素，又称$\color{green}{\text{表头元素}}$;$a_n$是唯一的“最后一个”数据元素，又称$\color{green}{\text{表尾元素}}$。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。以上就是线性表的$\color{green}{\text{逻辑特性}}$，这种线性有序的逻辑结构正是线性表名字的由来。

由此，我们得出线性表的特点如下。

• 表中元素的个数有限。
• 表中元素具有逻辑上的顺序性，表中元素有其先后次序。表中元素都是数据元素，每个元素都是单个元素。
• 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
• 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注意:$\color{green}{\text{线性表}}$是一种$\color{green}{\text{逻辑结构}}$，表示元素之间一对一的相邻关系。$\color{green}{\text{顺序表}}$和$\color{green}{\text{链表}}$是指$\color{green}{\text{存储结构}}$，两者属于不同层面的概念，因此不要将其混淆。

线性表的基本操作

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

线性表的顺序表示

顺序表的定义

线性表的顺序存储又称$\color{green}{\text{顺序表}}$。它是用一组地址连续的存储单元一次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在下你星标的起始位置,第$i$个元素的存储位置后面紧接着存储的是第$i+1$个元素，称$i$为元素$a_i$在线性表中的$\color{green}{\text{位序}}$，顺序表的特点是表中元素的$\color{yellow}{\text{逻辑顺序与其物理顺序相同}}$。

假设线性表$L$存储的起始位置为$\text{LOC(A)}$，$\text{sizeof(ElemType)}$是每个数据元素所占用存储空间的大小,则表L所对应的顺序存储如图2.1所示。

每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数，因此，线性表中的任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种$\color{red}{\text{随机存取}}$的存储结构。通常用高级程序设计语言中的$\color{green}{\text{数组}}$来描述线性表的顺序存储结构。

• 注：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的

假定线性表的元素类型为ElemType，则线性表的顺序存储类型描述为

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

而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的,而不需要为线性表一次性地划分所有空间。

#define Initsize 100//表长度的初始定义
typedef struct{
ElemType *data;//指示动态分配数组的指针
int MaxSize, length;//数组的最大容量和当前个数
}SeqList;//动态分配数组顺序表的类型定义

C的初始动态分配语句为

L.data= (ElemType* ) malloc (sizeof (ElemType ) *Initsize) ;

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

L.data=new ElemType [ Initsize];

顺序表最主要的特点是$\color{green}{\text{随机访问}}$，即通过首地址和元素序号可在时间O(1)内找到指定的元素。

顺序表的$\color{green}{\text{存储密度高}}$，每个结点只存储数据元素。

顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

顺序表上基本操作的实现

插入操作

bool ListInsert (SqList &L,int i,ElemType e){
if(i<1 || i>L.length+1) //判断i的范围是否有效
  return false;
if(L.length >= MaxSize) //当前存储空间已满,不能插入
  return false;
for(int j=L.length;j>=i;j--)//将第i个元素及之后的元素后移
  L.data[j]=L.data [j-1];
L.data [i-1]=e; //在位置i处放入e
L.length++; //线性表长度加1
return true;

最好情况:在表尾插入(即$i=n+ 1$)，元素后移语句将不执行，时间复杂度为$O(1)$。

最坏情况:在表头插入(即$i= 1$)，元素后移语句将执行$n$次，时间复杂度为$O(n)$。

平均情况:假设$p_i (p_i = \dfrac{1}{n+1}$是在第$i$个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时，所需移动结点的平均次数为

$$\displaystyle \sum_{i=1}^{n+1}p_i(n-i+1) = \displaystyle \sum_{i=1}^{n+1}\dfrac{1}{n+1}(n-i+1) = \dfrac{1}{n+1}\displaystyle \sum_{i=1}^{n+1}(n-i+1)=\dfrac{1}{n+1}\dfrac{n(n+1)}{2}=\dfrac{n}{2}$$

因此，线性表插入算法的平均时间复杂度为O(n)。

删除操作

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

最好情况:删除表尾元素（即$i=n$)，无须移动元素，时间复杂度为$O(1)$。

最坏情况:删除表头元素(即$i=1$)，需移动除表头元素外的所有元素，时间复杂度为$O(n)$。

平均情况:假设$p_i(p_i = \dfrac{1}{n})$是删除第$i$个位置上结点的概率，则在长度为$n$的线性表中删除一个结点时，所需移动结点的平均次数为

$$\displaystyle \sum_i^n p_i(n-i) = \displaystyle \sum_i^n \dfrac{1}{n}(n-i)=\dfrac{1}{n} \displaystyle \sum_i^n (n-i)=\dfrac{1}{n}\dfrac{n(n-1)}{2}=\dfrac{n-1}{2}$$

因此,线性表删除算法的平均时间复杂度为$O(n)$。

按值查找(顺序查找)

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

平均情况:假设$p_i(p_i = \dfrac{1}{n})$是查找的元素在第i(1<=i<=L.length)个位置上的概率，则在长度为n的线性表中查找值为e的元素所需比较的平均次数为

$$\displaystyle \sum_i^n p_i \times i = \displaystyle \sum_i^n \dfrac{1}{n} \times i =\dfrac{1}{n}\dfrac{n(n+1)}{2}=\dfrac{n+1}{2}$$

因此，线性表按值查找算法的平均时间复杂度为$O(n)$。

线性表的链式表示

单链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。其中 data为$\color{green}{\text{数据域}}$，存放数据元素。next为$\color{green}{\text{指针域}}$，存放其后继节点的的地址。

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

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

通常用头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为$\color{green}{\text{头结点}}$。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点，如图2.4所示。

头结点和头指针的区分:不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点,结点内通常不存储信息。

引入头结点后，可以带来两个优点:

• 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。(增删改查)
• 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空)，因此空表和非空表的处理也就得到了统一。($\blacktriangleright$(自己的理解) Q：会对空列表和非空列表那些操作有影响)

单链表上基本操作的实现

采用头插法建立单链表

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

LinkList List HeadInsert (LinkList &){//逆向建立单链表
  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", &×);
  }
  return L;

$\color{red}{\text{若没有设立头结点}}$：因为在头部插入新结点，每次插入新结点后，需要将它的地址赋值给头指针L。

总的时间复杂度是$O(n)$

采用尾插法建立单链表

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

LinkList List_TailInsert (LinkList &L){//正向建立单链表
  int x;
  //设元素类型为整型
  L=(LinkList) malloc(sizeof (LNode));
  LNode *s,*r=L;
  //r为表尾指针
  scanf ("Sd", &X);
  //输入结点的值
  while(x!=9999){
    //输入9999表示结束
    s=(LNode *) mal1oc (sizeof (LNode)) ;
    s->data=x;
    r->next=s;
    r=s;
    //r指向新的表尾结点
    scanf("%d", &x);
  }
  r->next=NULL;//尾结点指针置空
  return L;
}

总的时间复杂度是$O(n)$

按序号查找节点值

LNode *GetElem (LinkList L, int i){
int j=1; //计数,初始为1
LNode *p=L->next; //头结点指针赋给p
if(i==0)
  return L; //若i等于0,则返回头结点
if(i<1)
  return NULL; //若i无效，则返回NULL
while(p&&j<i){ //从第1个结点开始找,查找第i个结点
  p=p->next;
  j++;
}
return p; //返回第i个结点的指针,若i大于表长,则返回NULL
}

Q：若i等于0,则返回的就是第一个节点才对？

时间复杂度$O(n)$

按值查找表结点

LNode *LocateElem(LinkList L, ElemType e){
  LNode *p=L->next;
  while(p!=NULL&&p->data!=e)//从第1个结点开始查找data域为e的结点
    p=p->next;  
  return p; //找到后返回该结点指针,否则返回NULL
}

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

插入结点操作

p=GetElem(L,i-1); //查找插入位置的前驱结点
s->next=p->next;//图2.7中操作步骤1
p->next=s;//图2.7中操作步骤2

查找的时间复杂度$O(n)$，插入的时间复杂度为$O(1)$

拓展：对某一结点进行前插操作

如果已知待查节点的指针，可以实现$O(1)$操作：修改指针域，交换数据域

//将*s结点插入到*p之前的主要代码片段
s->next=p->next;//修改指针域,不能颠倒
p->next=s;
temp=p->data; //交换数据域部分
p->data=s->data;
s->data=temp;

删除结点操作

p=GetElem (L,i-1) ;//查找删除位置的前驱结点
q=p->next;//令q指向被删除结点
p->next=q->next//将*q结点从链中“断开”
free (q);//释放结点的存储空间

时间复杂度$O(n)$

拓展：删除节点*p
如果已知待删节点的指针，可以实现$O(1)$操作：修改指针域，交换数据域

q=p->next;//令q指向*p的后继结点
p->data=p->next->data;//和后继结点交换数据域
p->next=q->next;//将*q结点从链中“断开”
free(q);//释放后继结点的存储空间

求表长操作

从第一个节点开始，直到访问到空姐点为止。算法的时间复杂度为$O(n)$

• 求表长的时候单链表需要单独处理

双链表

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入、删除操作时)，只能从头开始遍历，访问后继结点的时间复杂度为$O(1)$，访问前驱结点的时间复杂度为$O(n)$。

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点，如图2.9所示。

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

双链表在单链表的结点中增加了一个指向其前驱的prior 指针，因此双链表中的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。

这是因为“链”变化时也需要对prior 指针做出修改，其关键是保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除操作的时间复杂度仅为$O(1)$。

双链表的插入操作

在双链表中p所指的结点之后插入结点*s，其指针的变化过程如图2.10所示。

s->next=p->next;//将结点*s插入到结点*p之后
p->next->prior=s;
s->prior=p;
p->next=s;

Q：在前方插入节点

双链表的删除操作

删除双链表中结点*p的后继结点*q,

p->next=q->next;
q->next->prior=p;
free(q);

Q：删除前驱节点

循环链表

循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环，如图2.12所示。

在循环单链表中，表尾结点*r的next 域指向L，故表中没有指针域为NULL的结点，因此，循环单链表的$\color{red}{\text{判空条件}}$不是头结点的指针是否为空，而是它是否等于头指针。

循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作是在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。当然，正是因为循环单链表是一个“环”，因此在任何一个位置上的插入和删除操作都是等价的，无须判断是否是表尾。

在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任意一个结点开始遍历整个链表。有时对单链表常做的操作是在表头和表尾进行的，此时对循环单链表不设头指针而仅$\color{red}{\text{设尾指针}}$，从而使得操作效率更高。其原因是，若设的是头指针，对表尾进行操作需要$O(n)$的时间复杂度，而若设的是尾指针r，r->next即为头指针，对表头与表尾进行操作都只需要$O(1)$的时间复杂度。

循环双链表

由循环单链表的定义不难推出循环双链表。不同的是在循环双链表中，头结点的 prior指针还要指向表尾结点，如图2.13所示。

在循环双链表L中，某结点*p为尾结点时，p->next==L;当循环双链表为空表时，其头结点的prior域和next域都等于L。

静态链表

静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next,与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标)，又称游标。和顺序表一样,静态链表也要预先分配一块连续的内存空间。静态链表和单链表的对应关系如图2.14所示。

静态链表结构类型的描述如下:

#define MaxSize 50 //静态链表的最大长度
typedef struct { //静态链表结构类型的定义
  ElemType data; //存储数据元素
  int next; //下一个元素的数组下标
}SLinkList [Maxsize];

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

顺序表和链表的比较

比较点	顺序表	链表
存取（读写）方式	顺序表可以顺序存取，也可以随机存取	链表只能从表头顺序存取元素
逻辑结构与物理结构	采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。	而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。
按值查找	无序:$O(n)$ 有序:折半查找$O(log_2(n))$	$O(n)$
按序查找	$O(1)$	$O(n)$
插入删除	$O(n)$(平均需移动半个表长的元素)	$O(1)$
空间分配	固定分配	节点只需申请时分配
基于存储考虑存储结构的选择	难以估计长度或存储规模时，不宜采用顺序表	链表不用事先估计存储规模，但链表的存储密度较低，显然链式存储结构的存储密度是小于1的。
基于运算考虑存储结构的选择	按序号访问，顺序表优于链表	插入删除，链表由于顺序表
基于环境考虑存储结构的选择	容易实现，基本高级语言都有实现	频繁动态的插入删除

栈和队列

知识框架

• 线性表
  • 操作受限
    • 栈
      • 顺序栈
      • 链栈
      • 共享栈
    • 队列
      • 循环队列
      • 链式队列
      • 双端队列
  • 推广
    • 数组
      • 一维数组
      • 多维数组：压缩存储，稀疏矩阵

栈的应用(摘自清华大学数据结构c语言版)

• 进制转换
• 括号匹配的检验
• 行编辑程序
• 迷宫求解
• 表达式求解:(中缀表达式转后缀表达式,后缀转中缀，从左往右看，后出为左，表达式树的建立)，前缀转中缀，从右往左看，先出为左,后缀表达式的计算,前缀表达式的计算
  • 中缀转前后缀：括号法
  • 1栈中缀转后缀vs2栈计算中缀$\color{yellow}{\text{p103,t11和课本不一致}}$
    • 弹出表达式的时候会弹出两个数

循环队列长度的计算

• 取余的理解参考文献1
• 错误文献，参考文献2
• 分两种情况，明确Q.rear指向的元素为空，Q.front指向的元素不为空：
• Q.rear > Q.front: Q.rear - Q.front ${\textstyle\unicode{x2460}}$ < maxSize
• Q.rear < Q.front: maxSize - (Q.front - Q.rear) = maxSize + Q.rear - Q.front < maxSize ${\textstyle\unicode{x2461}}$
• ${\textstyle\unicode{x2460}}$ = ${\textstyle\unicode{x2461}}$ = (maxSize + Q.rear - Q.front) % maxSize

拓展：循环栈

栈（Stack）

栈的基本概念

栈的定义

• 栈( Stack）是只允许在一端进行插入或删除操作的线性表。首先栈是一种$\color{red}{\text{线性表}}$，但限定这种线性表只能在某一端进行插入和删除操作。
• 栈顶(Top)：线性表允许进行插入删除的那一端。
• 栈底(Bottom)。固定的,不允许进行插入和删除的另一端。
• 空栈。不含任何元素的空表。
• $n$ 个不同元素进栈，出栈元素不同排列的个数为$\dfrac{1}{n+1}C_{2n}^n$($\color{red}{\text{卡特兰数}}$(Catalan))。

栈的基本操作

InitStack ( &S):初始化一个空栈s。
StackEmpty(S):判断一个栈是否为空，若栈s为空则返回true，否则返回false。
Push ( &S, x):进栈，若栈s未满，则将x加入使之成为新栈顶。
Pop ( &S, &x):出栈，若栈s非空，则弹出栈顶元素，并用x返回。
GetTop(S,&x):读栈顶元素，若栈s非空，则用x返回栈顶元素。
DestroyStack (&S):销毁栈，并释放栈s 占用的存储空间(“&”表示引用调用)。

栈的顺序存储结构

顺序栈的实现

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

#define MaxSize 50 //定义栈中元素的最大个数
typedef struct{
  Elentype data [MaxSize];//存放栈中元素
  int top; //栈顶指针
} SqStack ;

• 栈顶指针:s.top，初始时设置s.top=-1;栈顶元素: s.data[s.top] 。
  • 有的教辅可能初始时将(清华c语言版)s.top定义为0，相当于规定top 指向栈顶元素的下一个存储单元。
• 进栈操作:栈不满时，栈顶指针先加1，再送值到栈顶元素。
• 出栈操作:栈非空时，先取栈顶元素值，再将栈顶指针减1。
• 栈空条件: s.top==-1;栈满条件: s.top==MaxSize-1;栈长:s.top+1。

顺序栈的基本运算

初始化

void InitStack(sqStack &S){
  S.top=-l; //初始化栈顶指针
}

判栈空

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; //指针先加1,再入栈
  return true;
}

出栈

bool Pop (SqStack &S,ElemType &x){
  if (S.top==-1)  //栈空,报错
  return false;
  x=S.data [S.top--];//先出栈,指针再减1
  return true;
}

读栈顶元素

bool GetTop (SqStack S，ElemType &x){
  if(s.top==-1)//栈空,报错
  return false;
  x=s.data[s.top] ;//x记录栈顶元素
  return true;
}

共享栈

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

栈的链式存储结构

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

typedef struct Linknode{
  ElemType data; //数据域
  struct Linknode *next; //指针域
}*LiStack; //栈类型定义

队列

队列的基本概念

队列的定义

• 队列(Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。
• 队头(Front)。允许删除的一端，又称队首。
• 队尾(Rear)。允许插入的一端。
• 空队列。不含任何元素的空表。

队列常见的基本操作

• InitQueue ( &Q):初始化队列，构造一个空队列Q。
• QueueEmpty(Q):判队列空，若队列Q为空返回true，否则返回false。
• EnQueue ( &Q,x):入队，若队列Q未满，将x加入，使之成为新的队尾。
• DeQueue (&Q,&x):出队，若队列Q非空，删除队头元素，并用x返回。
• GetHead (Q,&x):读队头元素，若队列Q非空，则将队头元素赋值给x。

队列的顺序存储结构

队列的顺序存储

#define MaxSize 50 //定义队列中元素的最大个数
typedef struct{
  ElemType data [Maxsize];//存放队列元素
  int front, rear;//队头指针和队尾指针
} SqQueue;

• 初始状态（队空条件): Q.front==Q.rear==O。
• 进队操作:队不满时，先送值到队尾元素，再将队尾指针加1。
• 出队操作:队不空时，先取队头元素值，再将队头指针加1。

循环队列

• 进和出都是+1
• 初始时: Q.front=Q.rear=O。
• 队首指针进1: Q.front=(Q.front+1) %MaxSize。
• 队尾指针进1: Q.rear=(Q.rear+1)%MaxSize。
• 队列长度:(Q.rear+MaxSize-Q.front)%Maxsize。
• 出队入队时:指针都按顺时针方向进1（如图3.7所示)。
• 为了区分队空还是队满的情况，有三种处理方式:
  • 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法,约定以“队头指针在队尾指针的下一位置作为队满的标志”
    • 队满条件:(Q.rear+1)%MaxSize==Q.front。
    • 队空条件仍: Q.front==Q.rear。
    • 队列中元素的个数: (Q.rear-Q.front+MaxSize) % MaxSize
  • 类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size==0;队满的条件为Q.size==MaxSize。这两种情况都有Q.front==Q.rear。
  • 类型中增设tag 数据成员，以区分是队满还是队空。tag 等于0时，若因删除导致Q.front==Q.rear，则为队空; tag等于1时，若因插入导致Q.front==Q.rear，则为队满。

循环队列的操作

初始化

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

判队空

bool isEmpty (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;//队尾指针加1取模
  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; //队头指针加1取模
  return true;
}

队列的链式存储结构

队列的链式存储

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意与顺序存储的不同)。

typedef struct {//链式队列结点
  ElemType data;
  struct LinkNode *next;
}LinkNode ;

typedef struct { //链式队列
  LinkNode *front, *rear; //队列的队头和队尾指针
}LinkQueue;

链式队列的基本操作

初始化

void InitQueue(LinkQueue &Q){
  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;
  if(0.rear==p)
    Q.rear=Q.front;//若原队列中只有一个结点，删除后变空
  free(p);
  return true;
}

双端队列

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

栈和队列的应用

栈在括号匹配中的应用

初始设置一个空栈，顺序读入括号。

若是右括号，则或者使置于栈顶的最急迫期待得以消解，或者是不合法的情况（括号序列不匹配，退出程序)。

若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性降了一级。算法结束时，栈为空，否则括号序列不匹配。

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

中缀表达式转化为后缀表达式的过程，见本章3.3.6节的习题11的解析，这里不再赘述。

栈在递归中的应用

• 简单地说，若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。
• 递归必须满足的条件
  • 递归表达式（递归体)。
  • 边界条件（递归出口)。
• 可以将递归算法转换为非递归算法，通常需要借助栈来实现这种转换。
• 递归的效率低下，优点是代码简单，容易理解

队列在层次遍历中的应用

• ①根结点入队。
• ②若队空（所有结点都已处理完毕)，则结束遍历;否则重复③操作。
• ③队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队;若其有右孩子，则将右孩子入队，返回②。

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

第一个方面是解决主机与外部设备之间$\color{red}{\text{速度不匹配}}$的问题。

对于第一个方面，仅以主机和打印机之间速度不匹配的问题为例做简要说明。主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，由于速度不匹配，若直接把输出的数据送给打印机打印显然是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确，又使主机提高了效率。由此可见，打印数据缓冲区中所存储的数据就是一个队列。

第二个方面是解决由多用户引起的$\color{red}{\text{资源竞争}}$问题。

对于第二个方面，CPU(即中央处理器，它包括运算器和控制器）资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要CPU各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把 CPU分配给新的队首请求的用户使用。这样既能满足每个用户的请求，又使CPU能够正常运行。

特殊矩阵的压缩存储

数组的定义

• 数组是由n (n>1) 个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
• 数组是$\color{red}{\text{线性表的推广}}$。
  • 一维数组可视为一个线性表;二维数组可视为其元素也是定长线性表的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变。因此,除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

数组的存储结构

• 逻辑意义上的数组可采用计算机语言中的数组数据类型进行存储，一个数组的所有元素在内存中占用一段连续的存储空间。

矩阵的压缩存储

• 压缩存储:指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是为了节省存储空间。
• 特殊矩阵:指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上(下）三角矩阵、对角矩阵等。
• 特殊矩阵的压缩存储方法:找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

对称矩阵

为此将对称矩阵A[ 1…n ] [ 1…n]存放在一维数组B[ n (n+1)/2]中，即元素$a_{i,j}$(i行j列), 存放在$b_k$中。只存放下三角部分(含主对角）的元素。（由下三角的轮换对称性得到上三角元素的公式）（首项+末项=i，项数=i-1，坐标为j，-1是因为数组从零开始数）

$$k = \begin{cases} \dfrac{i(i-1)}{2} + j - 1 & i \geq j (下三角区和主对角线元素) \cr \dfrac{j(j-1)}{2} + i - 1 & i < j(上三角区元素a_{ij} = a_{ji}) \end{cases}$$

三角矩阵

• 下三角矩阵（上三角为常量），i行j列（推导：等差数列求和）

  $$k = \begin{cases} \dfrac{i(i-1)}{2} + j - 1 & i \geq j (下三角区和主对角线元素) \cr \dfrac{n(n+1)}{2} & i < j(上三角区元素) \end{cases}$$

  

• 上三角矩阵，i行j列( 项数=i-1,首项加末项=($\color{green}{\text{n}}$ + $\color{green}{\text{(n-(i-1)+1)}}$) ),第i行的第j个加的偏置为(j-(i-1))，数组是从零开始数的再-1为j-i

  $$k = \begin{cases} \dfrac{(i-1)(2n-i+2)}{2} + j - i & i \geq j (上三角区和主对角线元素) \cr \dfrac{n(n+1)}{2} & i < j(下三角区元素) \end{cases}$$

三对角矩阵

• 对角矩阵也称带状矩阵。对于n阶方阵A中的任一元素 $a{i,j} ，\text{当}\lvert i –j\rvert>1 \text{时，有}a{i,j}= 0 (1< i, j \text{\textless} n)$，则称为三对角矩阵，如图3.25所示。前$i-1$行共$3(i-1)-1$个元素，$a{i,j}$是第$i$行第$j-i+2$个元素，$a{i,j}$是第$2i+j-2$个元素，$k=2i+j-3$

$$k = 2i + j- 3$$

已知三对角矩阵中某元素$a_{i,j}$存放于一维数组B的第$k$个位置，则可得$i=\lfloor \dfrac{k+1}{3}+1 \rfloor$,$j=k-2j+3$ (i很好理解，因为可以理解为每行三个元素$i=\lceil \dfrac{k+1}{3} \rceil$)

稀疏矩阵

• 矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少，即$s \gg t$的矩阵称为稀疏矩阵。例如，一个矩阵的阶为100×100，该矩阵中只有少于100个非零元素。

• 稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储。

串

知识框架

• 基本概念:主串、子串、串长
• 存储结构
  • 定长顺序存储
  • 堆分配存储
  • 块链存储
• 模式匹配算法
  • 暴力匹配法
  • KMP算法
    • 部分匹配值表
    • next数组
    • next函数的推理过程
  • KMP算法的进一步改进——nextval数组

串的实现和定义

串的定义

串(string）是由零个或多个字符组成的有限序列。一般记为

$$S='a_1a_2\cdots a_n' \quad (n \geq 0)$$

其中，$S$是串名，单引号括起来的字符序列是串的值;$a_i$可以是字母、数字或其他字符;串中字符的个数n称为串的长度。$n=0$时的串称为空串（用$\emptyset$表示)。

串中任意多个连续的字符组成的子序列称为该串的$\color{green}{\text{子串}}$，相应地，包含子串的串称为$\color{green}{\text{主串}}$。某个字符在串中的序号称为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。当两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。

例如，有串A=’China Beijing’，B= ‘Beijing’，C=’China’，则它们的长度分别为13,7和5。B和C是A的子串，B在A中的位置是7，C在A中的位置是1。

需要注意的是，由一个或多个空格（空格是特殊字符）组成的串称为$\color{green}{\text{空格串}}$(注意，空格串不是空串)，其长度为串中空格字符的个数。

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为$\color{green}{\text{字符集}}$。在基本操作上，串和线性表有很大差别。线性表的基本操作主要以单个元素作为操作对象，如查找、插入或删除某个元素等;而串的基本操作通常以子串作为操作对象，如查找、插入或删除一个子串等。

串的存储结构

定长顺序存储表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。

#define MAXLEN 255//预定义最大串长为255
typedef struct {
char ch [MAXLEN] ;//每个分量存储一个字符
int length;//串的实际长度
}SString;

串的实际长度只能小于等于MAXLEN，超过预定义长度的串值会被舍去，称为$\color{green}{\text{截断}}$。串长有两种表示方法:一是如上述定义描述的那样，用一个额外的变量len来存放串的长度;二是在串值后面加一个不计入串长的结束标记字符“\0”，此时的串长为隐含值。

在一些串的操作（如插入、联接等）中，若串值序列的长度超过上界MAXLEN，约定用“截断”法处理，要克服这种弊端，只能不限定串长的最大长度，即采用动态分配的方式。

堆分配存储表示

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

typedef struct{
char *ch;//按串长分配存储区,ch指向串的基地址
int length;//串的长度
} HString;

在C语言中，存在一个称之为“堆”的自由存储区，并用malloc()和free ()函数来完成动态存储管理。利用malloc ()为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基地址，这个串由ch 指针来指示;若分配失败，则返回NULL。已分配的空间可用free ()释放掉。

块链存储表示

类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性（每个元素只有一个字符)，在具体实现时，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。图4.1(a)是结点大小为4(即每个结点存放4个字符）的链表，最后一个结点占不满时通常用“#”补上;图4.1(b)是结点大小为1的链表。

串的基本操作

StrAssign ( &T , chars):赋值操作。把串T赋值为chars。. StrCopy ( &T , S):复制操作。由串s复制得到串T。
StrEmpty(S):判空操作。若s为空串，则返回 TRUE，否则返回FALSE。
StrCompare (S,T):比较操作。若s>T，则返回值>0;若S=T，则返回值=0﹔若则返回值<0。
StrLength(s):求串长。返回串S的元素个数。
SubString ( &Sub,s, pos,len):求子串。用sub返回串s 的第pos个字符起长度为len的子串。
Concat (&T ,s1,s2):串联接。用T返回由s1和s2联接而成的新串。
Index (S,T):定位操作。若主串s中存在与串T值相同的子串，则返回它在主串s 中第一次出现的位置;否则函数值为0。
clearString ( &S):清空操作。将s清为空串。DestroyString (&S):销毁串。将串s销毁。

不同的高级语言对串的基本操作集可以有不同的定义方法。在上述定义的操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat 及求子串SubString五种操作构成串类型的最小操作子集，即这些操作不可能利用其他串操作来实现;反之，其他串操作（除串清除clearstring和串销毁Destroystring外)均可在该最小操作子集上实现。
例如，可利用判等、求串长和求子串等操作实现定位函数Index(S,T)。算法思想为:在主串S中取从第一个字符起、长度和串T相等的子串，与串T比较，若相等则求得函数值为i，否则i值增1，直至串S中不存在和串T相等的子串为止。

int Index(String S,String T){
  int i=1,n=StrLength(s), m=StrLength (T);
  while(i<-n-m+1){
    SubString(sub, s,i, m);
    if (StrCompare (sub, T)!=0)++i;
    else return i;//返回子串在主串中的位置
  }
  return 0; //S中不存在与T相等的子串
}

串的模式匹配

简单的模式匹配算法

子串的定位操作通常称为串的模式匹配，它求的是子串（常称$\color{green}{\text{模式串}}$）在主串中的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法。

int Index (sString s, sstring T){
  int i=1,j=1;
  while(i<-s.length && j<-T .length){
    if(S.ch[i]==T.ch [j]){
      ++i; ++j;//继续比较后继字符
    }
    else{
      i=i-j+2; j-1;//指针后退重新开始匹配
    }
  if(j>T.length) return i-T.length;
  else return 0;
}

图4.2展示了模式T= ‘ abcac’和主串s的匹配过程，每次匹配失败后，都把模式T后移一位。

改进的模式匹配算法——KMP算法

图4.2的匹配过程,在第三趟匹配中，i=7、j=5的字符比较不等，于是又从i=4、j=1重新开始比较。然而，仔细观察会发现，i=4和j=1，i=5和i=1及i=6和j=1这三次比较都是不必进行的。从第三趟部分匹配的结果可知，主串中第4、5和6个字符是’b’、’c’和’a’(即模式中第2、3和4个字符)，因为模式中第一个字符是’ a ‘，因此它无须再和这3个字符进行比较，而仅需将模式向右滑动3个字符的位置，继续进行i=7、j=2时的比较即可。

在暴力匹配中，每趟匹配失败都是模式后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较，这就是其低效率的根源。因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i指针无须回溯，并从该位置开始继续比较。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关（这里理解起来会比较困难，没关系，带着这个问题继续往后看)。

字符串的前缀、后缀和部分匹配值

KMP算法的原理是什么?

KMP算法的进一步优化

树与二叉树(Binary tree)

• 树形结构
  • 二叉树
    • 概念：定义
      • 存储结构：顺序存储，链式存储
    • 操作
      • 三种遍历
      • 线索二叉树
    • 应用
      • 排序二叉树————平衡二叉树
      • 哈夫曼树
  • 树和森林
    • 概念：定义
      • 存储结构：
        • 树：双亲表示法(顺序存储结构),孩子表示法(链式存储结构),孩子兄弟表示法(左孩子右兄弟)
    • 操作
      • 与二叉树的转换
      • 遍历:先根遍历,后根遍历
    • 应用
      • 并查集

$\color{red}{\text{森林的遍历}}$

树的意义

树家族是为了实现方便快捷的$\color{red}{\text{查找}}$而存在的。树的高度是命中查找的一个不可抗拒的时间下限。在一定的数据条件下，树的高度和宽度是互相制约的。（就像一定面积下，矩形的长和宽是互相制约的）而树家族中最简单的二叉树，尽管易于实现，却不能有实际的价值。其最最令人发指的是二叉树的高度太高。n叉树的提出和实现解决了二叉树的不足，典型的n叉树有：2-3-4树/红黑树和B树。

满m叉树的性质

• 第$i$层的节点数是多少？：$m^{i-1}(i \leq i \leq h)$
• 编号为$i$的节点的双亲结点(若存在)的编号是多少？：$\lfloor \dfrac{i-2}{m} \rfloor + 1(i>1)$
• 编号为$i$的结点的第$k$个孩子结点（若存在）的编号是多少?
  : $(i-1)m+k+1(1 \leq k \leq m)$
• 编号为$i$的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?$\color{green}{\text{条件}}$：结点$i$不是其双亲的第$m$个子女时才有右兄弟。右兄弟结点的$\color{green}{\text{编号}}$：$i+1$

$\color{red}{\text{Q：}}$ $\mho$(要补充的内容) 森林和树的遍历的关系

• 红黑树和平衡二叉树的区别
  • 参考文献
  • 红黑树的理解
  • 各种树

树的基本概念

树的定义

• 树是$n(n \geq 0)$个节点的有限集。
• 当$n=0$时，称为空树。
• 在任意一颗非空树中应满足:
  • 有且仅有一个特定的称为根的节点。
  • 当$n>1$时，其余节点可分为$m(m>0)$个互不相交的有限集$T_1,T_2,\cdots,T_m$,其中每个集合本身又是一颗树，并且称为根的子树
• 树是一种分层的逻辑结构。
  • 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
  • 树中所有结点可以有零个或多个后继。
• 树适合于表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和上一层的一个结点(即其父结点)有直接关系，根结点没有直接上层结点，因此在$n$个结点的树中有$n-1$条边。而树中每个结点与其下一层的零个或多个结点（即其子女结点）有直接关系。

基本术语

• 祖先:根A到结点K的唯一路径上的任意结点，称为结点K的祖先。
• 双亲:如结点B是结点K的$\color{green}{\text{祖先}}$，而结点K是结点B的$\color{green}{\text{子孙}}$。路径上最接近结点K的结点E称为K的$\color{green}{\text{双亲}}$，而K为结点E的$\color{green}{\text{孩子}}$。根A是树中唯一没有双亲的结点。有相同双亲的结点称为$\color{green}{\text{兄弟}}$，如结点K和结点L有相同的双亲E，即K和L为兄弟。
  • 树中节点最大的度称为树的度
• 分支节点：度大于0的结点称为分支结点(又称非终端结点);
• 终端节点：度为0（没有子女结点）的结点称为叶子结点(又称终端结点)。在分支结点中，每个结点的分支数就是该结点的度。
• 深度：结点的深度是从根结点开始自顶向$\color{red}{\text{下}}$逐层累加的。
• 高度，结点的高度是从叶结点开始自底向$\color{red}{\text{上}}$逐层累加的。
• 有序树和无序树
• 路径和路径长度：路径和路径长度。树中两个结点之间的$\color{green}{\text{路径}}$是由这两个结点之间所经过的结点序列构成的，而$\color{green}{\text{路径长度}}$是路径上所经过的边的个数。
  • 两个孩子之间不存在路径
• 森林

树的性质

树中的节点数等于所有节点的度加1

度为m的树中第i层上至多有$m^{i-1}$个节点($i \geq 1$)

高度为h的m叉树至多有$ \dfrac{m^h-1}{m-1}$个节点

具有n个结点的m叉树的最小高度为$\lceil log_m(n(m-1)+1) \rceil$

树节点与度的关系

• 总结点数 = $n_0 + n_1 + n_2 + \cdots + n_m$
• 总分支数 = $1n_1 + 2n_2 + \cdots + mn_m $(度为$m$节点引出$m$条分支)
• 总节点数 = 总分支数 + 1

二叉树的概念

二叉树的定义及主要特性

使用$\color{red}{\text{L，N，R法}}$来理解节点出现的先后顺序

二叉树的定义

• 度为2，子树有左右之分，不能任意颠倒
  • $\color{red}{\text{Q}}$：度为2，且有序的=二叉树？
  • $\color{green}{\text{A}}$：不是，1.度为2的有序树至少有3个节点,二叉树可以为空 2.度为2的有序树某节点只有一个孩子，该孩子的时候无需区分左右，但是二叉树需要区分子树
• 5种基本形态
  • 空二叉树
  • 只有根节点
  • 只有左子树
  • 左右子树都有
  • 只有右子树

性质

• 任何一棵二叉树，叶子结点个数为度为2的结点数减1，即$n_0=n_2+1$(记忆口诀：0比2多1)

几种特殊的二叉树

满二叉树

一棵高度为h，且含有$2^h-1$个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点

完全二叉树

高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应。

二叉排序树

左子树上所有结点的关键字均小于根结点的关键字;右子树上的所有结点的关键字均大于根结点的关键字;左子树和右子树又各是一棵二叉排序树。

平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。

二叉树的存储结构

顺序存储结构

顺序存储结构示意图

链式存储结构

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含3个域:数据域data、左指针域lchild和右指针域rchild，如图5.5所示。

• 含有n个节点的二叉链表中，含有$n+1$个空链域
  • 证明：$n$个节点出度和为$n-1$(树的性质),一个$2n$个指针域，被使用的指针域即是出度和,即空指针域为$2n-(n-1)=n+1$

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

二叉树的遍历

• 根节点N,左子树L，右子树R，
• 前中后序遍历序列的$\color{red}{\text{人工求法}}$：
  • 

先序遍历(PreOrder)(NLR)

若二叉树为空，则什么也不做；否则，

访问根节点

先序遍历左子树

先序遍历右子树

void PreOrder (BiTree T){
    if(T!=NULL){
        visit(T);//访问根结点
        PreOrder (T->lchild);//递归遍历左子树
        PreOrder (T->rchild); //递归遍历右子树
    }
}

例图的先序遍历结果：124635

中序遍历(InOrder)(LNR)

若二叉树为空，则什么也不做；否则，

中序遍历左子树

访问根节点

中序遍历右子树

void InOrder (BiTree T){
    if(T!=NULL){
        InOrder (T->lchild);//递归遍历左子树
        visit(T);//访问根结点
        InOrder (T->rchild); //递归遍历右子树
    }
}

例图的中序遍历结果：264135

后序遍历(PostOrder)(LRN)

若二叉树为空，则什么也不做；否则，

后序遍历左子树

后序遍历右子树

根节点

void PostOrder (BiTree T){
    if(T!=NULL){
        PostOrder (T->lchild);//递归遍历左子树
        PostOrder (T->rchild); //递归遍历右子树
        visit(T);//访问根结点
    }
}

例图的后序遍历结果：642531 642153

• 快速方法，左右中打印

以上三种方法的负责度分析

时间复杂度都是$O(n)$

空间复杂度是$O(n)$

递归工作栈的深度恰好为树的深度

递归算法和非递归算法的转换

在上节介绍的3种遍历算法中，暂时抹去和递归无关的visit语句，则3个遍历算法完全相同，因此，从递归执行过程的角度看先序、中序和后序遍历也是完全相同的。

图5.7用带箭头的虚线表示了这3种遍历算法的递归执行过程。其中，向下的箭头表示更深一层的递归调用，向上的箭头表示从递归调用退出返回;虚线旁的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历的过程中访问结点时输出的信息。例如，由于中序遍历中访问结点是在遍历左子树之后、遍历右子树之前进行的，则带圆形的字符标在向左递归返回和向右递归调用之间。由此，只要沿虚线从1出发到2结束，将沿途所见的三角形（或圆形或方形)内的字符记下，便得到遍历二叉树的先序（或中序或后序）序列。例如在图5.7中，沿虚线游走可以分别得到先序序列为ABDEC、中序序列为DBEAC、后序序列为DEBCA。

借助栈，来分析中序遍历的访问过程:

沿着根的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的结点，此时栈内元素依次为AB D。②栈顶元素出栈并访问:若其右孩子为空，继续执行②;若其右孩子不空，将右子树转执行①。栈顶D出栈并访问，它是中序序列的第一个结点;D右孩子为空，栈顶B出栈并访问;B右孩子不空，将其右孩子E入栈，E左孩子为空，栈顶E出栈并访问;E右孩子为空，栈顶A出栈并访问;A右孩子不空，将其右孩子C入栈，C左孩子为空，栈顶C出栈并访问。由此得到中序序列DBEAC。

根据分析可以写出中序遍历的非递归算法如下:

void Inorder2 (BiTree T){
  InitStack(S);BiTree p=T;//初始化栈s;p是遍历指针
  while(plI!ISEmpty (S)){//栈不空或p不空时循环
    if(p){//一路向左
      Push (S,p);//当前结点入栈
      p-p->lchild;//左孩子不空,一直向左走
    }
    else{//出栈,并转向出栈结点的右子树
      Pop (s,p);//栈顶元素出栈,访问出栈结点p-p->rchild;
      visit(p) ;//向右子树走,p赋值为当前结点的右孩子
    }//返回while循环继续进入if-else语句
  }
}

先序遍历和中序遍历的基本思想是类似的，只需把访问结点操作放在入栈操作的前面，可以参考中序遍历的过程说明自行模拟出入栈示意图。先序遍历的非递归算法如下:

void PreOrder2(BiTree T){
  InitStack(S); BiTree p=T;//初始化栈S;p是遍历指针
  while(p || !IsEmpty(S)){//栈不空或p不空时循环
    if(p){//一路向左
      visit(p);Push (s,p);//访问当前结点,并入栈p=p->lchild;
      p=p->lchild; //左孩子不空,一直向左走
    }
    else{//出栈,并转向出栈结点的右子树
      Pop (s,p);//栈顶元素出栈
      p=p->rchild;//向右子树走，p赋值为当前结点的右孩子
    }//返回while循环继续进入if-else语句
  }

后序遍历的非递归实现是三种遍历方法中最难的。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。

后序非递归遍历算法的思路分析:从根结点开始,将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，但是此时不能出栈并访问，因为如果其有右子树，还需按相同的规则对其右子树进行处理。直至上述操作进行不下去，若栈顶元素想要出栈被访问，要么右子树为空，要么右子树刚被访问完（此时左子树早已访问完)，这样就保证了正确的访问顺序。

后序遍历的非递归算法见本节综合题3的解析部分。

按后序非递归算法遍历图5.7(a)中的二叉树，当访问到E时，A,B,D都已入过栈，对于后序非递归遍历，当一个结点的左右子树都被访问后才会出栈，图中D已出栈，此时栈内还有A和B,这是E的全部祖先。实际上，访问一个结点p时，栈中结点恰好是p结点的所有祖先，从栈底到栈顶结点再加上p结点，刚好构成从根结点到p结点的一条路径。在很多算法设计中都可以利用这一思路来求解，如求根到某结点的路径、求两个结点的最近公共祖先等。

层次遍历

图5.8所示为二叉树的层次遍历，即按照箭头所指方向，按照1,2,3,4的层次顺序，对二叉树中的各个结点进行访问。

要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队;若它有右子树，则将右子树根结点入队。然后出队，访问出队结点$\cdots$如此反复，直至队列为空。

二叉树的层次遍历算法如下:

void Levelorder(BiTree T){
  InitQueue (Q);//初始化辅助队列
  BiTree p;
  EnQueue (Q, T);//将根结点入队
  while(!IsEmpty (Q)){//队列不空则循环
    DeQueue(o,p);//队头结点出队
    visit (p);//访问出队结点
    if(p->lchild!-NULL)
      EnQueue(o,p->lchild);//左子树不空,则左子树根结点入队if(p->rchild!-NULL)
    if(p->rchild!-NULL)
      EnQueue(Q,p->rchild);//右子树不空，则右子树根结点入队
  }
}

上述二叉树层次遍历的算法，读者在复习过程中应将其作为一个模板，在熟练掌握其执行过程的基础上来记忆，并达到熟练手写的程度。这样才能将层次遍历模板应用于各种题目之中。

注意:遍历是二叉树各种操作的基础，可以在遍历的过程中对结点进行各种操作，例如，对于一棵已知树求结点的双亲、求结点的孩子结点、求二叉树的深度、求二叉树的叶子结点个数、判断两棵二叉树是否相同等。所有这些操作都建立在二叉树遍历的基础上，因此必须掌握二叉树的各种遍历过程，并能灵活运用以解决各种问题。

由遍历序列构造二叉树

由二叉树的$\color{green}{\text{先序序列}}$和$\color{green}{\text{中序序列}}$可以$\color{red}{\text{唯一地}}$确定一棵二叉树。

在先序遍历序列中，第一个结点一定是二叉树的根结点;而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这棵二叉树。

同理，由二叉树的$\color{green}{\text{后序序列}}$和$\color{green}{\text{中序序列}}$也可以唯一地确定一棵二叉树。

因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，进而得到一棵二叉树。

由二叉树的$\color{green}{\text{层序序列}}$和$\color{green}{\text{中序序列}}$也可以$\color{red}{\text{唯一地}}$确定一棵二叉树，实现方法留给读者思考。需要注意的是，若只知道二叉树的先序序列和后序序列，则无法唯一确定一棵二叉树。

例如，求先序序列（ABCDEFGHI）和中序序列(BCAEDGHFI)所确定的二叉树。

首先，由先序序列可知A为二叉树的根结点。中序序列中A之前的BC为左子树的中序序列，EDGHFI为右子树的中序序列。然后由先序序列可知B是左子树的根结点,D是右子树的根结点。以此类推，就能将剩下的结点继续分解下去，最后得到的二叉树如图5.9(c)所示。

线索二叉树

• 应用：利用二叉链表中的空指针域，方便求前驱和后继
• 线索化（左前右后）
  • 若无左子树，则将左指针指向其前驱节点
  • 若无右子树，则将右指针指向其后继节点
• 优劣
  • 一般常用的是中序线索二叉树
  • 先序线索二叉树寻找前驱结点的过程是非常繁琐的
  • 后序线索二叉树寻找前驱和后继节点的过程都是非常繁琐的
• 中序线索二叉树（下面的性质感觉都是L，N，R的应用）
  • 视频中的前驱和后继节点的求法感觉很绕
  • 前驱节点
    • 若左指针为线索，则其指向节点为前驱节点
    • 若左指针为左孩子，则其左子树的最右侧节点为前驱节点
  • 后驱节点
    • 若右指针为线索，则其指向节点为后驱节点
    • 若右指针为右孩子，则其右子树的最左侧节点为后驱节点

线索二叉树的基本概念

人工算线索二叉树最快的方法直接求出来$\color{red}{\text{*序遍历的序列}}$

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。前面提到，在含$n$个结点的二叉树中，有$n +1$个空指针。这是因为每个叶结点有$2$个空指针，每个度为$1$的结点有$1$个空指针，空指针总数为$2n_0+n_1$，又$n_0=n_2+1$，所以空指针总数为$n_0 + n_1 + n_2 +1 =n+1$。由此设想能否利用这些空指针来存放指向其前驱或后继的指针﹖这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。

规定:若无左子树，令lchild指向其前驱结点;若无右子树，令rchild指向其后继结点。如图5.10所示，还需增加两个标志域标识指针域是指向左（右）孩子还是指向前驱（后继)。($\color{red}{\text{口诀}}$：左前右后,0孩子1标记)

$$\text{ltag}\begin{cases} 0, &\text{lchild域指示结点的左孩子} \cr 1, &\text{lchild域指示结点的前驱} \end{cases}$$ $$\text{rtag}\begin{cases} 0, &\text{rchild域指示结点的右孩子} \cr 1, &\text{1，rchild域指示结点的后继} \end{cases}$$

中序线索二叉树的构造

• 思路：首先要遍历整颗二叉树，找到对应的空指针位，让他们指向正确的位置

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

以中序线索二叉树的建立为例。附设指针pre 指向刚刚访问过的结点，指针p 指向正在访问的结点，即 pre指向 p 的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre;检查pre 的右指针是否为空，若为空就将它指向p，如图5.11所示。

// 中序遍历对二叉树线索化的递归算法
void InThread(ThreadTree &p, ThreadTree &pre)i
  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); //递归,线索化右子树
  }//if(p !-NULL)
}

// 中序遍历的主过程
void createInThread ( ThreadTree T){
  ThreadTree pre = NULL;
  if(T!=NULL){//非空二叉树,线索化
    InThread(T,pre) ;// 线索化二叉树
    pre->rchild=NULL;//处理遍历的最后一个结点
    pre->rtag=1 ;
  }
}

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

下面的性质感觉都是L，N，R的应用

如何找中序遍历序列的第一个结点

一直往左走，最后一个节点就是中序遍历的第一个结点

如何找中序遍历序列的最后一个结点

一直往右走

找后继结点

如果右指针是线索那么右指针所指向的结点就是后继结点；
如果不是线索，那么往右走一步，再往左走

找前驱结点

如果有前驱结点，且左指针是线索，那么左指针指向的结点就是前驱结点；
如果不是线索，那么往左走一步，再一直往右走

中序线索二叉树的遍历

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

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

ThreadNode *Firstnode (ThreadNode *p){
while(p->ltag==0) p=p->lchild;//最左下结点(不一定是叶结点)return p;
}

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

ThreadNode *Nextnode(ThreadNode *p){
  if(P->rtag-=0) return Firstnode (p->rchild);
  else return p->rchild; //rtag==1直接返回后继线索
}

请读者自行分析并完成求中序线索二叉树的最后一个结点和结点p前驱的运算。

将程序1中的ltag和lchild换成rtag和rchild,即为求中序线索二叉树的最后一个结点;将程序2中的rtag和rchild换成ltag和 lchild，即为求中序线索二叉树中结点p的前驱。

3)利用上面两个算法，可以写出不含头结点的中序线索二叉树的中序遍历的算法:

void Inorder (ThreadNode *T){
  for (ThreadNode *p=Firstnode(T);p!=NULL; p=Nextnode (p))
    visit (p);
}

先序线索二叉树和后序线索二叉树

上面给出了建立中序线索二叉树的代码，建立先序线索二叉树和后序线索二叉树的代码类似，只需变动线索化改造的代码段与调用线索化左右子树递归函数的位置。

以图5.13(a)的二叉树为例给出手动求先序线索二叉树的过程:先序序列为ABCDF，然后依次判断每个结点的左右链域，如果为空则将其改造为线索。结点4.B均有左右孩丁将右链域指左孩子，将左链域指向前驱B，无右孩子，将右链域指向后继D;结点D无左孩子，将左链域指
向前驱C，无右孩子，将右链域指向后继F;结点F无左孩子，将左链域指问前的驱D，后序序列也无后继故置空，得到的先序线索二叉树如图5.13(b)所示。求后序线索二叉树的过程:后序序列为CD BFA，结点C无左孩子，也无前驱故置空，无右孩子，将右链域指向后继D;结点D无左孩子，将左链域指向前驱C，无右孩子，将右链域指向后继B;结点F无左孩子，将左链域指向前驱B，无右孩子，将右链域指向后继A，得到的后序线索二叉树如图5.13(c)所示。

如何在先序线索二叉树中找结点的后继?如果有左孩子，则左孩子就是其后继;如果无左孩子但有右孩子，则右孩子就是其后继;如果为叶结点，则右链域直接指示了结点的后继。

在后序线索二叉树中找结点的后继较为复杂，可分3种情况:①若结点x是二叉树的根，则其后继为空;②若结点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有石于树，则具后继即为双亲;③若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的石丁树上孩后序遍历列出的第一个结点。图5.13(c)中找结点B的后继无法通过链域找到，可见在后序线索二叉树上找后继时需知道结点双亲，即需采用带标志域的三叉链表作为存储结构。

树、森林

树的存储结构

双亲表示法

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

• 伪指针域为-1
• 区别树的顺序存储结构与二叉树的顺序存储结构
  • 在树的顺序存储结构中，数组下标代表结点的编号，下标中所存的内容指示了结点之间的关系。而在二叉树的顺序存储结构中，数组下标既代表了结点的编号，又指示了二叉树中各结点之间的关系。当然，二叉树属于树，因此二叉树都可以用树的存储结构来存储，但树却不都能用二叉树的存储结构来存储。

双亲表示法的存储结构描述如下:

#define MAX_TREE_SIZE 100//树中最多结点数
typedef struct{//树的结点定义
  ElemType data;//数据元素
  int parent;//双亲位置域
}PTNode;
typedef struct {//树的类型定义
  PTNode nodes [MAX_TREE_SIZE];//双亲表示
  int n;//结点数
}PTree;

孩子表示法

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时$n$个结点就有$n$个孩子链表（叶子结点的孩子链表为空表)，如图5.15(a)所示。

这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历$n$个结点中孩子链表指针域所指向的$n$个孩子链表。

孩子兄弟表示法

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容:$\color{green}{\text{结点值}}$、$\color{green}{\text{指向结点第一个孩子结点的指针}}$，及指向结点$\color{green}{\text{下一个兄弟结点的指针}}$（沿此域可以找到结点的所有兄弟结点)，如图5.15(b)所示。

孩子兄弟表示法的存储结构描述如下:

typedef struct CSNode{
ElemType data;//数据域
struct CSNode *firstchi1d, *nextsibling;//第一个孩子和右兄弟指针
}CSNode, *CSTree;

这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，$\color{green}{\text{易于查找结点的孩子等}}$,但缺点是从当前结点查找其$\color{green}{\text{双亲结点比较麻烦}}$。若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。

树，森林与二叉树的转换

树和二叉树

• [树]转换为[二叉树]规则：左孩子右兄弟
  • ①在兄弟结点之间加一连线
  • ②对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉
  • ③以树根为轴心，顺时针旋转45°。
• 

森林和二叉树

• [森林]转换成[二叉树]的画法
  • ①将森林中的每棵树转换成相应的二叉树
  • ②每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线
  • ③以第一棵树的根为轴心顺时针旋转45°。
• 

树和森林的遍历

树的遍历

图5.16

用某种方式访问树中的每个结点，且仅访问一次

先根遍历

• 若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。
• 其遍历序列与这棵树相应二叉树的先序序列相同。
  • 方法：先转换为二叉树，再进行先序遍历

后根遍历

• 若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的规则。
• 其遍历序列与这棵树相应二叉树的中序序列相同。
  • 方法：先转换为二叉树，再进行中序遍历

图5.16的树的先根遍历序列为ABEFCDG，后根遍历序列为EFBCGDA。

森林的遍历

图5.17

图5.17的森林的先序遍历序列为ABCDEFGHI，中序遍历序列为BCDAFEHIG。

先序遍历森林

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

中序遍历森林

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

树的应用————并查集

并查集是一种简单的集合表示，它支持以下3种操作:

1 ) Union(S,Root1,Root2):把集合s 中的子集合Root2并入子集合Root1。要求Root1和 Root2互不相交，否则不执行合并。

2) Find(S,x):查找集合s中单元素x所在的子集合，并返回该子集合的名字。

3 ) Initial(S):将集合s 中的每个元素都初始化为只有一个单元素的子集合。

通常用$\color{red}{\text{树（森林）的双亲}}$表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。

例如,若设有一个全集合为S= {0,1,2,3,4,5,6,7,8,9}，初始化时每个元素自成一个单元素子集合，每个子集合的数组值为-1，如图5.18所示。

经过一段时间的计算，这些子集合合并为3个更大的子集合S= {0,6,7,8}，S={1,4,9}，S,={2,3，5},此时并查集的树形表示和存储结构如图5.19所示。

为了得到两个子集合的并，只需将其中一个子集合根结点的双亲指针指向另一个集合的根结点。因此，S1US2可以具有如图5.20所示的表示。

在采用树的双亲指针数组表示作为并查集的存储表示时，集合元素的编号从0到size-1。其中size是最大元素的个数。下面是并查集主要运算的实现。

并查集的结构定义如下:

#define SIZE 100
int UFSets [SIZE];//集合元素数组（双亲指针数组)

并查集的初始化操作（s即为并查集):

void Initial(int S[]){
  for (int i-0;i<size;i++)//每个自成单元素集合
  S[i]--1;
}

Find操作（函数在并查集s中查找并返回包含元素x的树的根)（$\color{red}{\text{解释}}$：根据初始化，根节点的下标对应的数值值为$\color{red}{\text{-1}}$）:

int Find(int S[],int ×){
while (S[×]>=0)//循环寻找x的根
  x=S[x];
return x;//根的s[]小于0
}

Union操作(函数求两个不相交子集合的并集):

void Union (int S[],int Root1,int Root2){//要求Root1与Root2是不同的,且表示子集合的名字
S[Ro0t2]  = Rootl;//将根Root2连接到另一根Root1下面
}

树与二叉树的应用

二叉排序树(BST,Binary Sort Tree)

• 性质
  • 动态树表。结构不是一次性生成，而是在查找过程中，当树中不存在关键字值等于给定值的结点时再进行插入的。

定义

1. 空树
2. 1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
   2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
   3. 左、右子树也分别是一棵二叉排序树。

二叉排序树的查找

非递归实现

BSTNode *BSTSearch (BiTree T, ElemType key){
  while(T!=NULL&&key!=T->data){//若树空或等于根结点值，则结束循环
  if(key<T->data) T=T->lchild;//小于,则在左子树上查找
  else T=T->rchild;
  //大于,则在右子树上查找
  }
  return T;
}

递归实现

• 实现简单但是效率比较低

TODO

二叉排序树的插入

• 插入的结点一定是一个叶子节点

int BSTInsert (BiTree &T, KeyType k){
  if(T==NULL){//原树为空,新插入的记录为根结点
    T=(BiTree)malloc(sizeof(BSTNode));
    T->key=k;
    T->lchild=T->rchild=NULL;
    return 1;//返回1,插入成功
  }
  else if (k==T->key) //树中存在相同关键字的结点,插入失败
    return 0;
  else if(k<T->key)//插入到T的左子树
    return BST_Insert(T->lchild,k);
  else//插入到T的右子树
  return BSTInsert(T->rchild, k);
}

二叉排序树的构造

void Creat_ BST (BiTree &T, KeyType str[],int n) {
  T=NULL;
  //初始时T为空树
  int i=0 ;
  while (1<n){//依次将每个关键字插入到二叉排序树中
    BST_Insert(T, str[i]);
    i++;
  }
}

二叉排序树的删除

三种情况
①若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
②若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
③若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱)，这样就转换成了第一或第二种情况。

二叉排序树的查找效率分析

• 若是平衡二叉树，它的平均查找长度为$O(log_2n)$
• 若是单支树，平均查找长度为$O(n)$
• 二叉排序树与二分查找
  • 从查找过程看，二叉排序树与二分查找相似。就平均时间性能而言，二叉排序树上的查找和二分查找差不多。但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树。
    • $\blacktriangleright$ 判定树是什么？
  • 就维护表的有序性而言，二叉排序树无须移动结点,只需修改指针即可完成插入和删除操作，平均执行时间为$O(log_2n)$。二分查找的对象是有序顺序表，若有插入和删除结点的操作，所花的代价是$O(n)$。当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其查找操作;若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

平衡二叉树(AVL,Adelson-Velsky and Landis Tree)

平衡二叉树和AVL树的区别

百度出来的一堆答案的都是错的。。「每次插入新节点之后需要旋转的次数不能预知」明明可以实现只需要一次旋转

平衡二叉树可以后序遍历查找

void Judge_AVL(BiTree bt, int &balance, int &h) {
  int bl = 0, br = 0,hl = 0, hr = 0 ;
  if (bt ==NULL){
    h = 0;
    balance = 1;
  }
  else if (bt->lchild==NULL&&bt->rchild==NULL){
    h = 1;
    balance =1;
  }
  else{
    Judge_AVL (bt->lchild,bl, hl) ;Judge_AVL (bt->rchild, br, hr) ;if(hl > hr)
    h = hl+1;else
    h = hr+1;
    if(abs (hl-hr) <2&&bl==1&&br==1)
      balance=1;
    else
      balance=0 ;
  }
}

严书pr.235

因此,当平衡的二叉排序树因插人结点而失去平衡时,仅需对最小不平衡子树进行平衡旋转处理即可。因为经过旋转处理之后的子树深度和插人之前相同,因而不影响插入路径上所有祖先结点的平衡度。

严书代码pp.236(看代码会递归的检查调整每一层)

Q:会有出现多次旋转的情况吗(即：会出现插入路径上的祖先节点也需要更新吗)
A：不需要。只会调整一次，后面退出递归其实都在更新每一个节点树的高度

平衡二叉树的定义(Balanced Binary Tree)

• 平衡二叉树:在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过1
• 平衡因子:结点左子树与右子树的高度差，

平衡二叉树的插入

每次调整的对象都是最小不平衡子树
假设关键字序列为{15,3,7，10,9,8}（$\blacktriangleright$ 不是很能理解？ ）

• 其实这个操作本质上就是矩阵转置和恒等变形(弹幕)

LL平衡旋转(右单旋转)

由于在结点A的左孩子(L)的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点,将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。
如图5.28所示，结点旁的数值代表结点的平衡因子，而用方块表示相应结点的子树，下方数值代表该子树的高度。

RR平衡旋转（左单旋转）

由于在结点A的右孩子(R）的右子树(R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树，如图5.29所示。

LR平衡旋转（先左后右双旋转）

由于在A的左孩子(L)的右子树(R)上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置，如图5.30所示。

• 个人理解：先旋B（往左旋）再选A

RL平衡旋转（先右后左双旋转）

由于在A的右孩子(R)的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置，如图5.31所示。

平衡二叉树的查找

平均查找长度为$log_2n$

哈夫曼树和哈夫曼编码

• 哈夫曼树的性质
  1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
  2. 构造过程中共新建了n-1个结点（双分支结点)，因此哈夫曼树的结点总数为2n一1。
  3. 每次构造都选择⒉棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点。

哈夫曼树的定义

• $\color{red}{\text{带权路径长度}}$:从树的根到任意结点的路径长度(经过的边数)与该节点上权值的乘积。
  • $w_i$是第i个叶节点的权值，$l_i$是该叶结点到根结点的路径长度
  • 记为$WPL=\sum_{i=1}^{n}w_il_i$
• 哈夫曼树：在含有n个带权叶结点的二叉树中，其中带权路径长度最小的二叉树

哈夫曼树的构造

给定n个权值分别为$w1,w,\cdots,w_n$的结点，构造哈夫曼树的算法描述如下:

将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。

构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且.将新结点的权值置为左、右子树上根结点的权值之和。

从F中删除刚才选出的两棵树，同时将新得到的树加入F中。

重复步骤2）和3)，直至F中只剩下一棵树为止。

哈夫曼编码

• 固定长度编码：每个字符用相等长度的二进制位表示
• 可变长度编码:允许对不同字符用不等长的二进制位表示
• 前缀编码:没有一个编码是另一个编码的前缀
• 利用哈夫曼树可以设计出总长度最最短的二进制前缀编码

习题

武功门派

有一些古老悠久的历史门派，经久不衰，在任何战争中都能发挥非常大的作用

枚举法

特殊值法

题目种类归纳（不限于本章）

性质题

• p148 t24：性质题
  • 基本上所有的题目都可以是LNR的运用

概念题

• p148 t25：概念题

纯知识点运用题

• p148 t25：知识点运用题（单纯求先序，中序，后序）
• p148 t28：定义运用(就算不知道很详尽的知识点，通过定义，也能够求解)
• 公式运用

综合运用题（题目给的条件犹抱琵琶半遮面）

• p148 t14-16：综合运用题（题目给的条件犹抱琵琶半遮面）

做题方法的评价指标

时间复杂度（越快做出来越好）

准确率(Accuracy)（这个方法的准确率越高越好）

• 影响准确率的因素
  • 计算(Timu Accuracy 1：TA1)
  • 因素考虑完全（枚举）（TA2）
  • 步骤太多（TA3）
  • 题目看错（TA4）
    • 计算题
  • 答案看错(TA5)
    • 概念描述题

几乎没有空间复杂度（草稿纸无限，墨水无限）

• 使用草稿纸的面积大小（步骤多）会影响准确率，嵌套多，难以维护

图

知识结构

• 图的定义
• 图结构的存储
  • 顺序存储结构：
    • 邻接矩阵法(有向图，无向图)
  • 链式存储结构：
    • 邻接表法（树的孩子表示法）、邻接多重表(无向图)、十字链表(有向图)
• 图的遍历
  • 深度优先遍历
  • 广度优先遍历
• 图的相关应用
  • 最小生成树:Prim算法、Kruskal 算法
  • 最短路径:Dijkstra算法、Floyd 算法
  • 拓扑排序:AOV网
  • 关键路径:AOE 网

存储结构	优势
邻接矩阵法
邻接表法
邻接多重表
十字链表

$\color{red}{\text{注意}}$:图的顺序存储和图的链式存储中指的$\color{green}{\text{稀疏图}}$和$\color{green}{\text{稠密图}}$是对于边而言的，边稠密，边稀疏
拓扑排序是关键路径的前提，时间复杂度为什么是O（n+e）

• $\mho$(要补充的内容) $\color{red}{\text{Q}}$：图的广度优先搜索和深度优先搜索的优劣，同理树
• $\color{red}{\text{Q}}$:邻接矩阵中没有边应该用0还是无穷表示
• 很喜欢考$\color{red}{\text{所有}}$，$\color{red}{\text{总数}}$

单词	含义
Directed Acyclic Graph	有向无环图
Critical Path	关键路径

图的基本概念

图的定义

图$G$由顶点集$V$和边集$E$组成，记为$G=(V,E)$，其中$V(G)$表示图$G$中顶点的有限非空集;$E(G)$表示图$G$中顶点之间的关系(边）集合。若$V=\lbrace v_1,v_2,\cdots, v_n \rbrace$，则用$\lvert V \rvert$表示图$G$中顶点的个数，$E= \lbrace (u, v) \vert u \in V,v \in V$，用$\lvert E \rvert$表示图$G$中边的条数。

注意:线性表可以是空表，树可以是空树，但$\color{red}{\text{图不可以是空图}}$。就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边。

有向图

若$E$是$\color{red}{\text{有向边}}$(也称$\color{green}{\text{弧}}$）的有限集合时，则图$G$为有向图。弧是顶点的$\color{green}{\text{有序对}}$，记为$< v, w >$，其中$v$, $w$是顶点，$v$称为$\color{green}{\text{弧尾}}$，$w$称为$\color{green}{\text{弧头}}$，$< v, w >$称为从$v$到$w$的弧，也称$v$邻接到$w$。

图6.1(a)所示的有向图G可表示为

$$\begin{cases} G_1=(V_1, E_1) , \cr V= \lbrace 1,2,3 \rbrace , \cr E = \lbrace <1,2>,<2,1>,<2,3>\rbrace \end{cases}$$

无向图

若$E$是$\color{green}{\text{无向边}}$（简称边）的有限集合时，则图$G$为无向图。边是顶点的无序对，记为$(v, w)$或$(w, v)$。可以说$w$和$v$互为邻接点。边$(v, w)$依附于$w$和$v$，或称边$(v, w)$和 $v, w$相关联。

图6.1(b)所示的无向图$G_1$,可表示为

$$\begin{cases} G_1=(V_2, E_2) , \cr V= \lbrace 1,2,3,4 \rbrace , \cr E = \lbrace (1,2), (1,3), (1,4), (2,3), (2,4),(3,4)\rbrace \end{cases}$$

简单图、多重图

一个图$G_2$如果满足:①不存在重复边;②不存在顶点到自身的边，那么称图G为简单图。图6.1中$G$和 $G$均为$\color{green}{\text{简单图}}$。若图$G$中某两个顶点之间的边数大于1条，又允许顶点通过一条边和自身关联，则称图$G$为$\color{green}{\text{多重图}}$。多重图和简单图的定义是相对的。数据结构中仅讨论简单图。

完全图(也称简单完全图)

对于无向图，$\lvert E \rvert$的取值范围为0到$n(n -1)/2$，有$n(n -1)/2$条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，$\lvert E \rvert$的取值范围为0到$n(n-1)$，有$n(n -1)$条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。图6.1中$G$,为无向完全图，而$G$为有向完全图。

子图

设有两个图$G=(V, E)$和$G’=(V’,E’)$，若$V’$是$V$的子集，且$E’$是$E$的子集，则称$G’$是$G$的子图。若有满足$V(G’)=V(G)$的子图$G’$，则称其为$G$的生成子图。图6.1中$G_3$为$G_1$的子图。

注意:并非$V$和$E$的任何子集都能构成$G$的子图，因为这样的子集可能不是图，即$E$的子集中的某些边关联的顶点可能不在这个$V$的子集中。

$\color{red}{\text{必须是真子集吗}}$

连通、连通图和连通分量

在无向图中，若从顶点$v$到顶点$w$有路径存在，则称$v$和$w$是$\color{green}{\text{连通}}$的。若图$G$中任意两个顶点都是连通的，则称图$G$为$\color{green}{\text{连通图}}$，否则称为$\color{green}{\text{非连通图}}$。无向图中的$\color{green}{\text{极大连通子图}}$称为$\color{green}{\text{连通分量}}$，在图6.2(a)中，图$G_4$有3个连通分量如图6.2(b)所示。假设一个图有n个顶点，如果边数小于$n -1$，那么此图必是$\color{green}{\text{非连通图}}$;思考，如果图是非连通图，那么最多可以有多少条边?$\color{green}{\text{n-2}}$(考虑图是一个树)

非连通情况下边最多的情况:由$n-1$个顶点构成一个完全图，此时再任意加入一条边则变成连通图。

极大连通子图：点和边尽可能多

顶点的度、入度和出度

在无向图中，顶点$v$的度是指依附于顶点$v$的边的条数，记为$TD(v)$。在图6.1(b)中，每个顶点的度均为3。对于具有$n$个顶点、$e$条边的无向图，$\color{red}{\displaystyle \sum_{i=1}^n TD(v,)=2e}$，即无向图的全部顶点的度$i=1$的和等于边数的2倍，因为每条边和两个顶点相关联。

在有向图中,顶点$v$的度分为入度和出度,入度是以顶点v为终点的有向边的数目,记为ID(v);而出度是以顶点v为起点的有向边的数目，记为OD(v)。在图6.1(a)中，顶点2的出度为2、入度为1。顶点v的度等于其入度与出度之和，即TD(v)= ID(v)+OD(v)。对于具有n个顶点、e条边的有向图，艺ID(y)=>oD(v,)=e，即有向图的全部顶点的入度之和与出度之和相等，并且等
i=1
于边数，这是因为每条有向边都有一个起点和终点。

边的权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为$\color{green}{\text{带权图}}$，也称$\color{green}{\text{网}}$。

稠密图、稀疏图

边数很少的图称为$\color{green}{\text{稀疏图}}$，反之称为$\color{green}{\text{稠密图}}$。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图$G$满足$\lvert E \rvert < \lvert V \rvert log\lvert V \rvert$时，可以将$G$视为稀疏图。

路径、路径长度和回路

顶点$v$,到顶点 $v$之间的一条路径是指顶点序列$vp,v{i1},v{i2},\cdots,v{i_m},v_q$,，当然关联的边也可理解为路径的构成要素。路径上边的数目称为$\color{green}{\text{路径长度}}$。第一个顶点和最后一个顶点相同的路径称为$\color{green}{\text{回路}}$或$\color{green}{\text{环}}$。若一个图有n个顶点，并且有大于n-1条边，则此图$\color{red}{\text{一定有环}}$。

简单路径、简单回路

在路径序列中，顶点不重复出现的路径称为$\color{green}{\text{简单路径}}$。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为$\color{green}{\text{简单回路}}$。

距离

从顶点$u$出发到顶点$v$的最短路径若存在，则此路径的长度称为从$u$到$v$的$\color{green}{\text{距离}}$。若从$u$到$v$根本不存在路径，则记该距离为无穷($\infty$)。

有向树

一个顶点的入度为0、其余顶点的入度均为1的有向图，称为$\color{green}{\text{有向树}}$。

图的存储及基本操作

邻接矩阵法:稠密图

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。

结点数为$n$的图$G=(V, E)$的邻接矩阵$A$是$n \times n$的。将$G$的顶点编号为$v_1,v_2, \cdots, v_n$。若$(v_i, v_j) \in E$,$A[i][j]=1$，否则$A[i][j]=0$。

无权图

$$A[i][j] = \begin{cases} 1, & \text{若}(v_i,v_j) \text{或} <v_i, v_j>\text{是}E(G)\text{中的边} \cr 0, &\text{或}\infty,\text{若}(v_i,v_j) \text{或} <v_i, v_j>\text{不是}E(G)\text{中的边} \end{cases}$$

带权图的表示，用$\infty$来表示两个顶点之间不存在边

$$A[i][j] = \begin{cases} w_{ij}, & \text{若}(v_i,v_j) \text{或} <v_i, v_j>\text{是}E(G)\text{中的边} \cr 0\text{或}\infty, &\text{或}\infty,\text{若}(v_i,v_j) \text{或} <v_i, v_j>\text{不是}E(G)\text{中的边} \end{cases}$$

图的邻接矩阵存储结构定义如下:

#define MaxvertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
  VertexType Vex [MaxVertexNum];//顶点表
  EdgeType Edge[MaxVertexNum] [MaxVertexNum];//邻接矩阵,边表
  int vexnum, arcnum;//图的当前顶点数和弧数
}MGraph;

在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略)。
当邻接矩阵的元素仅表示相应边是否存在时，EdgeType可采用值为0和1的枚举类型。
无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。
邻接矩阵表示法的空间复杂度为$O(n^2)$，其中$n$为图的顶点数$\lvert V \rvert$。

图的邻接矩阵存储表示法具有以下特点:

①无向图的邻接矩阵一定是一个对称矩阵（并且唯一)。因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
②对于无向图，邻接矩阵的第$i$行（或第$i$列）非零元素(或非元素）的个数正好是顶点$i$的度 $TD(v)$。对于有向图,邻接矩阵的第$i$行非零元素(或非$\infty$元素)的个数正好是顶点$i$的出度$OD(v_i)$;第$i$列非零元素（或非元素）的个数正好是顶点$i$的入度$ID(v_i)$。(口诀：行出列入)
④用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图
中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。$\color{red}{\text{稠密图适合使用邻接矩阵的存储表示}}$。
⑥设图$G$的邻接矩阵为$A$，$A^n$的元素$A[i][j]$等于由顶点$i$到顶点$j$的长度为$n$的路径的数目。该结论了解即可，证明方法请参考离散数学教材。

邻接表法:稀疏图

相当于树的孩子表示法，一个数组下标表示$\color{green}{\text{对应顶点}}$顶点编号，内容是一个链表，内容是$\color{green}{\text{其}}$指向的顶点编号（邻接表），逆邻接表:指向$\color{green}{\text{其}}$的定点编号

所谓邻接表，是指对图G中的每个顶点$v_i$建立一个单链表，第$i$个单链表中的结点表示依附于顶点$v_i$的边（对于有向图则是以顶点$v_i$为尾的弧)，这个单链表就称为顶点$v_i$的$\color{green}{\text{边表}}$（(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表)，所以在邻接表中存在两种结点:顶点表结点和边表结点，如图6.6所示。

顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc)构成，边表（邻接表）结点由邻接点域(adjvex）和指向下一条邻接边的指针域(nextarc)构成。

$\color{red}{\text{有趣的是}}$，虽然$\color{green}{\text{顶点表}}$叫顶点$\color{yellow}{\text{表}}$，但他其实“本质”只是个一维数组，$\color{red}{\text{边表}}$里面名字中又有$\color{green}{\text{边}}$，又有$\color{green}{\text{表}}$，但其实要么只记录$\color{green}{\text{入点}}$（指向对应顶点表的点），或者$\color{green}{\text{出点}}$（顶点表中的点指向的点），而$\color{green}{\text{表}}$，也“无从谈起”，他其实是散落着的一种状态，靠指针连接起来（中文的日常用语中的表有有列是一个二维的“excel”），这里取其英文名的直译无论从编程上还是理解上都更直观，adjacency list（邻接点的清单）

无向图和有向图的邻接表的实例分别如图6.7和图6.8所示。

图的邻接表存储结构定义如下:

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

图的邻接表存储方法具有以下特点:

若$G$为无向图，则所需的存储空间为$O(\lvert V \rvert +2 \lvert E \rvert )$;若$G$为有向图，则所需的存储空间为$O(\lvert V \rvert +\lvert E \rvert )$。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。
对于稀疏图,采用邻接表表示将极大地节省存储空间。
在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为$O(n)$。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。(总结：查某顶点的边效率高，查顶点间是否存在边效率低)
在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数;但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。
图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

十字链表:有向图

十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。这些结点的结构如下图所示。

弧结点中有5个域:尾域(tailvex）和头域(headvex）分别指示弧尾和弧头这两个顶点在图中的位置;链域hlink指向弧头相同的下一条弧;链域tlink 指向弧尾相同的下一条弧;info域指向该弧的相关信息。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上。

顶点结点中有 3个域: data域存放顶点相关的数据信息，如顶点名称;firstin和firstout两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。图6.9为有向图的十字链表表示法。注意，顶点结点之间是顺序存储的。

顶点结点中有3个域: data域存放顶点相关的数据信息，如顶点名称;firstin和firstout两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。

$\color{red}{\text{有趣的是}}$，如何$\color{green}{\text{理解}}$中文翻译中的十字呢？如果将边（弧）节点的nextIn(hlink)和nextOut(tlink)域看成两个轴的话，那么确实相当于一个十字穿过了边（弧）节点，又有$\color{green}{\text{链}}$(指针)，这名字到有几分合理。如何快速找到一个顶点节点的所有的nextOut弧节点(tailvex）呢？看弧节点的tailvex就行了，

图6.9为有向图的十字链表表示法。注意，顶点结点之间是顺序存储的。

在十字链表中，既容易找到$V$为尾的弧，又容易找到$V$为头的弧，因而$\color{red}{\text{容易求得顶点的出度和入度}}$。图的十字链表表示是不唯一的，但一个十字链表表示确定一个图。

邻接多重表：无向图

实际上相当于压缩无向图$\color{green}{\text{邻接表}}$的压缩存储方式，一条边仅由一个节点表示

邻接多重表是$\color{green}{\text{无向图}}$的另一种链式存储结构。

在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行$\color{green}{\text{删除}}$等操作时，需要分别在两个顶点的边表中遍历，效率较低。

与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构如下所示。

其中，$\text{mark}$为标志域，可用以标记该条边是否被搜索过;$\text{ivex}$和$\text{jvex}$为该边依附的两个顶点在图中的位置; $\text{ilink}$ 指向下一条依附于顶点$\text{ivex}$的边; $\text{jlink}$指向下一条依附于顶点$\text{jvex}$的边，$\text{info}$为指向和边相关的各种信息的指针域。

每个顶点也用一个结点表示，它由如下所示的两个域组成。

其中，data域存储该顶点的相关信息，firstedge域指示第一条依附于该顶点的边。

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

图6.10为无向图的邻接多重表表示法。邻接多重表的各种基本操作的实现和邻接表类似。

图的基本操作

Adjacent(G, x, y):判断图G是否存在边<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>不存在，则向图G中添加该边。
RemoveEdge(G,x, y):若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。. 
FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
Get_edge_value(G,x,y):获取图G中边(x,y)或<x, y>对应的权值。
Set_edge_value(G,x,y,v):设置图G中边(x, y)或<x, y>对应的权值为v。

图的遍历

为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组$\text{visited[ ]}$来标记顶点是否被访问过。

广度优先搜索

广度优先搜索（Breadth-First-Search, BFS）类似于二叉树的$\color{red}{\text{层序遍历算法}}$。基本思想是:首先访问起始顶点$v$，接着由$v$出发，依次访问$v$的各个未访问过的邻接顶点$w_i, w_2,\cdots, w_i$，然后依次访问$w_i, w_2,\cdots, w_i$的所有未被访问过的邻接顶点;再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。Dijkstra单源最短路径算法和 Prim最小生成树算法也应用了类似的思想。

换句话说，广度优先搜索遍历图的过程是以$v$为起始点，由近至远依次访问和$v$有路径相通且路径长度为$1，2，\cdots$的顶点。广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它$\color{red}{\text{不是}}$一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

广度优先搜索算法的伪代码如下:

bool visited [MAX VERTEX NUM];//访问标记数组
void BFSTraverse (Graph G){ //对图G进行广度优先遍历
  for(i=0;i<G.vexnum;++i)
    visited[i]=FALSE; //访问标记数组初始化
  InitQueue (Q);//初始化辅助队列o
  for(i=0;i<G.vexnum;++i) //从0号顶点开始遍历
  if(!visited[ i])//对每个连通分量调用一次BFS
    BFS(G,i);//v，未访问过，从Vi开始 BFS
}
//从顶点v出发，广度优先遍历图G
void BFS(Graph G,int v){
visit(v); //访问初始顶点v
visited[v]=TRUE; //对v做已访问标记
Enqueue (Q,v);//顶点v入队列O
while(!isEmpty(Q)){
  DeQueue (o,v);//顶点v出队列
for (w=FirstNeighbor(G,V);w>=0;w=NextNeighbor(G,v, w)) //检测v所有邻接点
    if(!visited [w]){//w为v的尚未访问的邻接顶点
      visit(w);//访问顶点w
      visited[w]=TRUE;//对w做已访问标记EnQueue(O,w);//顶点w入队列
    }//if
}//while

下面通过实例演示广度优先搜索的过程,给定图G如图6.11所示。

假设从a结点开始访问，a先入队。此时队列非空，取出队头元素a,由于b,c与a邻接且未被访问过，于是依次访问b,c，并将b, c依次入队。队列非空，取出队头元素b，依次访问与b邻接且未被访问的顶点d, e，并将d, e入队（注意: a与b也邻接，但a已置访问标记，故不再重复访问)。此时队列非空，取出队头元素c，访问与c邻接且未被访问的顶点f,g，并将f, g入队。此时，取出队头元素d，但与d邻接且未被访问的顶点为空，故不进行任何操作。继续取出队头元素e，将h入队列$\cdots$最终取出队头元素h后，队列为空，从而循环自动跳出。遍历结果为abcdefgh。
从上例不难看出，图的广度优先搜索的过程与二叉树的层序遍历是完全一致的，这也说明了图的广度优先搜索遍历算法是二叉树的层次遍历算法的扩展。

BFS 算法的性能分析

无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列$Q$，$n$个顶点均需入队一次，在最坏的情况下，空间复杂度为$O(\lvert V \rvert )$。

采用邻接表存储方式时，每个顶点均需搜索一次(或入队一次)，故时间复杂度为$O(\lvert V \rvert )$,在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为$O(\lvert E \rvert )$，算法总的时间复杂度为$O(\lvert V \rvert + \lvert E \rvert )$。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为$O(\lvert V \rvert )$，故算法总的时间复杂度为$O(\lvert V \rvert^2 )$。

BFS算法求解单源最短路径问题

若图G=(V, E)为非带权图，定义从顶点u到顶点v的最短路径d(u,v)为从u到v的任何路径中最少的边数;若从u到v没有通路，则d(u, v)= co。
使用BFS，我们可以求解一个满足上述定义的非带权图的单源最短路径问题，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。
BFS 算法求解单源最短路径问题的算法如下:

void BFS MIN Distance (Graph G, int u){//d[i]表示从u到i结点的最短路径
for(i-0;i<G.vexnum;++i)
  d[i]=-1;//初始化路径长度
visited[u]-TRUE;d[u]-0;
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]){//w为u的尚未访问的邻接顶点
      visited[w]=TRUE;//设已访问标记
      d[w]=d[u]+1;//路径长度加1
      EnQueue(o, w); //顶点w入队
    }//if
  }//while
}

广度优先生成树

在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树，如图6.12所示。需要注意的是，一给定图的邻接矩阵存储表示是唯一的，故其$\color{green}{\text{广度优先生成树}}$也是$\color{green}{\text{唯一}}$的，但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。

广度优先也会生成森林：参考文献

深度优先搜索

与广度优先搜索不同，深度优先搜索（Depth-First-Search，DFS）类似于树的$\color{red}{\text{先序遍历}}$。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。

它的基本思想如下:首先访问图中某一起始顶点$v$，然后由$v$出发，访问与$v$邻接且未被访问的任一顶点$w_1$，再访问与$w_1$,邻接且未被访问的任一顶点$w_2\cdots$重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

一般情况下，其递归形式的算法十分简洁，算法过程如下:

bool visited[MAX VERTEXNUM];//访问标记数组

void DFSTraverse(Graph G){//对图G进行深度优先遍历
for (v=0;v<G.vexnum;++v)//初始化已访问标记数据
  visited[v]=FALSE;
for(v=0;v<G. vexnum;++V)//本代码中是从V=0开始遍历
if(!visited[v])
  DFS (G, v);
void DFS (Graph G,int v){//从顶点v出发,深度优先遍历图G
  visit (v);//访问顶点V
  visited[v]=TRUE;
  //设已访问标记
  for(w=FirstNeighbor (G,V);w>=0; w=NextNeighbor(G,v,w))
    if(!visited[w]){//w为v的尚未访问的邻接顶点
    DFS(G,w);
  } //if
}

以图6.11的无向图为例，深度优先搜索的过程:首先访问a，并置a访问标记;然后访问与a邻接且未被访问的顶点b，置b访问标记;然后访问与b邻按且不ovP的-控日d油v记。此时d已没有未被访问过的邻接点，故返回上一个切问过的明点 b，vP马只*孜工个B以问的顶点e，置e访问标记$\cdots$以此类推，直至图中所有的顶点都被访问一次。遍历结果为abdehcfg。

注意:图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和 BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和 BFS序列是不唯一的。

DFS算法的性能分析

DFS 算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为$O(\lvert V \rvert )$。

遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所用的存储结构。以邻接矩阵表示时,查找每个顶点的邻接点所需的时间为$O(\lvert V \rvert )$,故总的时间复杂度为$O(\lvert V \rvert^2 )$。以邻接表表示时，查找所有顶点的邻接点所需的时间为$O(\lvert V \rvert )$，访问顶点所需的时间为$O(\lvert E \rvert )$，此时，总的时间复杂度为$O(\lvert V \rvert +\lvert E \rvert )$。

深度优先的生成树和生成森林

与广度优先搜索一样,深度优先搜索也会产生一棵深度优先生成树。当然，这是有条件的，即对连通图调用DFS才能产生深度优先生成树，否则产生的将是深度优先生成森林，如图6.13所示。与 BFS类似，基于邻接表存储的深度优先生成树是不唯一的。

图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。
对于无向图来说，若无向图是连通的，则从任一结点出发，仅需一次遍历就能够访问图中的所有顶点;若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。
故在BFSTraverse ()或DFSTraverse ()中添加了第二个for循环，再选取初始点，继续进行遍历,以防止一次无法遍历图的所有顶点。对于$\color{red}{\text{无向图}}$,上述两个函数调用BFS(G,i)或DFS(G,i)的次数等于该图的$\color{green}{\text{连通分量数}}$;而对于有向图则不是这样，因为一个连通的有向图分为强连通的和非强连通的，它的连通子图也分为强连通分量和非强连通分量，$\color{green}{\text{非强连通分量}}$一次调用BFS(G,i)或DFS (G,i)无法访问到该连通分量的所有顶点，如图6.14所示。

图的应用

最小生成树

最小生成树的代码和应用，更清晰的算法版本，

• 代码思路总结：prim：有一个距离列表信息，每加一个就更新距离列表信息，储存最短的路径
  • memset(dist, 0x3f, sizeof dist);，其中0x3f相当于设为infinity

prim算法

// [来源](https://blog.csdn.net/esjiang/article/details/114481882?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-8.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-8.no_search_link)

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int w[N][N], dist[N];
int n, m;
bool st[N];

int prim(){
  // 将所有的距离都设置为无限大
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int res = 0;
    
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            // t == -1 || 保证t不等于-1
            if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        // 设置为已访问
        st[t] = true;
        // 更新最小生成树的距离的和
        res += dist[t];
        // 更新距离列表信息
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], w[t][j]);
    }
    return res;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];
    
    int t = prim();
    cout << t << endl;
    return 0;
}

Kruskal算法

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 220;
struct Edge{
    int a, b, w;
    bool operator < (const Edge &W) const {
        return w < W.w;
    }
}edge[M];
int n, m;
int p[N];

int find(int x){
    // 路径压缩
    // 《算法笔记.胡凡》 pp.330
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ){
        scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].w);
    }
    
    sort(edge, edge + m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    int res = 0;
    
    for (int i = 0; i < m; i ++ ){
        int a = edge[i].a, b = edge[i].b, c = edge[i].w;
        a = find(a), b = find(b);
        // 下标为a的节点，认下标为b的节点做爸爸
        // 加入到最小生成树中
        // 通过并查集看是不是同一个集合中
        if (a != b) {
          p[a] = b;
          res += c;
        }
    }
    
    cout << res << endl;
    
    return 0;
}

一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图;若给它增加一条边，则会形成图中的一条回路。

证明是生成树：没有回路

对于一个带权连通无向图G=(V, E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设$\Re$为G的所有生成树的集合，若T为$\Re$中边的权值之和最小的那棵生成树,则T称为G的最小生成树（Minimum-Spanning-Tree, MST)。

不难看出，最小生成树具有如下性质:
1）最小生成树不是唯一的，即最小生成树的树形不唯一，$\Re$中可能有多个最小生成树。当图G中的各边权值互不相等时，G的最小生成树是唯一的;若无向连通图G的边数比顶点数少1，即G本身是一棵树时，则G的最小生成树就是它本身。

2）最小生成树的边的权值之和总是唯一的，虽然最小生成树不唯一，但其对应的边的$\color{green}{\text{权值之和}}$总是$\color{green}{\text{唯一}}$的，而且是最小的。

3）最小生成树的边数为顶点数减1。

构造最小生成树有多种算法，但大多数算法都利用了最小生成树的下列性质:假设$\text{G}=(\text{V},\text{E})$是一个带权连通无向图，$\text{U}$是顶点集$\text{V}$的一个非空子集。若$(u,v)$是一条具有最小权值的边，其中$u\in U,v \in \text{V}-\text{U}$，则必存在一棵包含边$(u, v)$的最小生成树。

基于该性质的最小生成树算法主要有Prim算法和Kruskal算法,它们都基于贪心算法的策略。对这两种算法应主要掌握算法的本质含义和基本思想，并能够手工模拟算法的实现步骤。

下面介绍一个通用的最小生成树算法:

GENERIC MST(G){
  T=NULL;
  while T未形成一棵生成树;
    do 找到一条最小代价边(u,v)并且加入T后不会产生回路;
    T=T U (u, v):
}

通用算法每次加入一条边以逐渐形成一棵生成树，下面介绍两种实现上述通用算法的途径。

Prim算法

Prim（普里姆）算法的执行非常类似于寻找图的最短路径的$\color{green}{\text{Dijkstra算法}}$。

Prim算法构造最小生成树的过程如图6.15所示。初始时从图中任取一顶点(如顶点1)加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1。以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。此时T中必然有n-1条边。

Prim算法的步骤如下:

假设$G=\lbrace V,E \rbrace$是连通图，其最小生成树$T=(U, E_T)$，$E_T$是最小生成树中边的集合。

初始化:向空树$T=(U,E_T)$中添加图$G=(V, E)$的任一顶点$u_0$，使$U=\lbrace u_0 \rbrace，E_T=\emptyset$。
循环(重复下列操作直至U=V):从图G中选择满足$\lbrace (u, v) \vert u \in U,v \in V-U \rbrace$且具有最小权值的边$(u, v)$，加入树T，置$U=U \cup \lbrace v \rbrace$，$E_T=E_T \cup u \lbrace (u, v) \rbrace$。

Prim算法的时间复杂度为$O(\lvert V \rvert^2 )$，不依赖于$O(\lvert E \rvert )$因此它适用于求解$\color{green}{\text{边稠密的图}}$的最小生成树。

Kruskal算法

与Prim 算法从顶点开始扩展最小生成树不同，Kruskal（克鲁斯卡尔）算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

Kruskal算法构造最小生成树的过程如图6.16所示。初始时为只有n个顶点而无边的非连通图$T=\lbrace V,\lbrace \rbrace \rbrace$，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边。以此类推，直至T中所有顶点都在一个连通分量上。

假设$G=(V,E)$是连通图，其最小生成树$T=(U, E_T)$。

初始化:$U=V, E_T=\emptyset$。即每个顶点构成一棵独立的树，$T$此时是一个仅含$\lvert V \rvert$个顶点的森林。循环（重复下列操作直至T是一棵树):按G的边的权值递增顺序依次从$E-E_T$中选择一条边，若这条边加入T后$\color{green}{\text{不构成回路}}$，则将其加入$E_T$,否则舍弃，直到$E_T$中含有$n-1$条边。

Kruskal 算法的简单实现如下:

void Kruskal (V,T){
  T=V;//初始化树T,仅含顶点
  nums=n;//连通分量数
  while (numS>1){//若连通分量数大于1
    // 从E中取出权值最小的边(v,u);
    if(v和u属于T中不同的连通分量){
      T=TU{(v,u)};//将此边加入生成树中
      numS--;//连通分量数减1
    }
}

根据图的相关性质，若一条边连接了两棵不同树中的顶点，则对这两棵树来说，它必定是连通的，将这条边加入森林中，完成两棵树的合并，直到整个森林合并成一棵树。

通常在Kruskal算法中，采用堆（见第7章）来存放边的集合，因此每次选择最小权值的边只需$O(log \lvert E \rvert)$的时间。此外，由于生成树T中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集的数据结构来描述T，从而构造T的时间复杂度为$O(\lvert E \rvert log\lvert E \rvert)$。

Floyd 算法的时间复杂度为$O(\lvert V \rvert^2)$。不过由于其代码很紧凑，且并不包含其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的。

Floyd算法允许图中有带$\color{green}{\text{负权值}}$的边，但不允许有包含带负权值的边组成的回路。Floyd算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。

因此，Kruskal算法适合于边稀疏而顶点较多的图。

也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点，并且在所有边权值均非负时，运行一次 Dijkstra算法，其时间复杂度为$O(\lvert V \rvert^2)\lvert V \rvert$=$O(\lvert V \rvert^3)$。

最短路径:DP思想,贪心

6.3节所述的广度优先搜索查找最短路径只是对无权图而言的。当图是带权图时，把从一个顶点v到图中其余任意一个顶点v;的一条路径(可能不止一条）所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径。

求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。带权有向图G的最短路径问题一般可分为两类:一是单源最短路径，即求图中某一顶点到其他各顶点的最短路径，可通过经典的 Dijkstra(迪杰斯特拉）算法求解;二是求每对顶点间的最短路径，可通过Floyd（弗洛伊德）算法来求解。

Dijkstra算法求单源最短路径问题

使用邻接矩阵表示时，时间复杂度为$O(\lvert V \rvert^2 )$。使用带权的邻接表表示时，虽然修改$\text{dist [ ]}$的时间可以减少，但由于在$\text{dist[ ]}$中选择最小分量的时间不变，时间复杂度仍为$O(\lvert V \rvert )$。

人们可能只希望找到从源点到某个特定顶点的最短路径，但这个问题和求解源点到其他所有顶点的最短路径一样复杂，时间复杂度也为O(\lvert V \rvert^2)。

每个节点有三个节点信息，节点是否被访问，到起点的距离，被访问节点的父亲节点的信息

• update，每加入一个节点，更新所有与该节点$\color{green}{\text{相邻的节点}}$的信息，该$\color{green}{\text{加入节点}}$加边的权值小于$\color{green}{\text{相邻的节点}}$当前距离时，$\color{red}{\text{更新}}$节点距离，将父亲变成$\color{green}{\text{加入节点}}$
• scan：$\color{red}{\text{扫描}}$距离列表信息，找到未选顶点中$\color{green}{\text{距离最短的节点}}$
• add：添加$\color{green}{\text{距离最短的节点}}$到已选节点集合中，

Floyd算法求各顶点之间最短路径问题

代码简洁优雅著称，三个循环即可，$\color{red}{\text{动态规划的思想}}$

$\color{red}{\text{Q：}}$中间点在不断的变化，他怎么能保证一定挂载到最短路径上？某个中间点一开始是无穷，那么第一次循环他必不可能挂载到中间路径上，后面会变成更小的，万一此时有节点经过他最短他好像也挂不上去最短路径上了了？

视频1：天勤

视频2，可视化

参考文献1：知乎

有向无环图描述表达式

有向无环图:若一个有向图中不存在环，则称为有向无环图，$\color{green}{\text{简称DAG图}}$。

有向无环图是描述含有公共子式的表达式的有效工具。例如表达式

((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

可以用上一章描述的二叉树来表示，如图6.20所示。仔细观察该表达式，可发现有一些相同的子表达式(c+d)和(c + d)*e，而在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间，图6.21所示为该表达式的有向无环图表示。

拓扑排序

$\text{AOV}$网:若用$\text{DAG}$图表示一个工程，其顶点表示活动，用有向边$< V_i，V_j >$表示活动$V_i$必须先于活动$V_j$进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为AOV网。在AOV网中，活动V是活动V的直接前驱，活动V是活动的直接后继，这种前驱和后继关系具有传递性，且任何活动V不能以它自己作为自己的前驱或后继。

拓扑排序:在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序:

${\textstyle\unicode{x2460}}$ 每个顶点出现且只出现一次。

${\textstyle\unicode{x2461}}$ 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

或定义为:拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤;

${\textstyle\unicode{x2460}}$ 从AOV网中选择一个没有前驱的顶点并输出。

${\textstyle\unicode{x2461}}$ 从网中删除该顶点和所有以它为起点的有向边。

${\textstyle\unicode{x2462}}$ 重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

图6.22所示为拓扑排序过程的示例。每轮选择一个入度为0的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为{1,2,4,3,5}。

拓扑排序算法的实现如下:

bool TopologicalSort (Graph G){
  InitStack (S);//初始化栈,存储入度为0的顶点
  for(int i=0;i<G.vexnum;i++)
    if (indegree [i]==0)
      Push (S,i); //将所有入度为0的顶点进栈
  int count-0;//计数,记录当前已经输出的顶点数
  while(!IsEmpty (S)){//栈不空,则存在入度为0的顶点
    Pop (s,i);//栈顶元素出栈
    print [count++]=i;//输出顶点i
    for (P=G.vertices[i].firstarc;p;P=p->nextarc){ //将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
      V=p->adjvex;
      if(!(--indegree [v]))
        Push (S,v);//入度为0，则入栈
    }
  } //while
  if(count<G.vexnum)//排序失败,有向图中有回路
    return false;
  else
    return:true;//拓扑排序成功
}

由于输出每个顶点的同时还要删除以它为起点的边,故拓扑排序的时间复杂度为O(IV+ |E)此外，利用上一节的$\color{green}{\text{深度优先遍历}}$也可实现拓扑排序，请读者仔细思考其原因及实现方法。

对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序:

${\textstyle\unicode{x2460}}$ 从AOV网中选择一个没有后继（出度为0）的顶点并输出。

${\textstyle\unicode{x2461}}$ 从网中删除该顶点和所有以它为终点的有向边。

${\textstyle\unicode{x2462}}$ 重复①和②直到当前的AOV网为空。

用拓扑排序算法处理AOV网时，应注意以下问题;

${\textstyle\unicode{x2460}}$入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动$\color{green}{\text{开始}}$或$\color{green}{\text{继续}}$。

${\textstyle\unicode{x2461}}$ 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一;但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。

${\textstyle\unicode{x2462}}$ 由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成AOV网的新的邻接存储矩阵，这种$\color{green}{\text{邻接矩阵}}$可以是$\color{green}{\text{三角矩阵}}$;但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列;反之则不一定成立。

拓扑排序大话数据结构中的代码描述

p300

关键路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网。AOE网和AOV网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE网中的边有权值;而AOV网中的边无权值,仅表示顶点之间的前后关系。

AOE网具有以下两个性质:

只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始;
只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

在AOE网中仅有一个入度为0的顶点，称为$\color{green}{\text{开始顶点（源点)}}$，它表示整个工程的开始;网中也仅存在一个出度为0的顶点，称为$\color{green}{\text{结束顶点（汇点)}}$，它表示整个工程的结束。

在AOE 网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为$\color{green}{\text{关键路径}}$，而把关键路径上的活动称为$\color{green}{\text{关键活动}}$。

完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。

下面给出在寻找关键活动时所用到的几个参量的定义。

事件$v_k$的最早发生时间$ve(k)$

公式中的max:某个事件节点有多个前驱来算最早发生时间，要等其最晚的前驱完成
ve(k),vertex early k

它是指从源点v到顶点v的最长路径长度。事件v的最早发生时间决定了所有从v开始的活动能够开工的最早时间。可用下面的递推公式来计算:

$ve$(源点)=0

$ve(k) = Max \lbrace ve(j) + Weight(v_j, v_k) \rbrace$,$v_k$为$v_j$的任意后继，$Weight (v_j, v_k)$表示$$上的权值

计算 $ve()$值时，按从前往后的顺序进行，可以在拓扑排序的基础上计算:

${\textstyle\unicode{x2460}}$ 初始时，令$ve[1…n]$=0。

${\textstyle\unicode{x2460}}$ 输出一个入度为$0$的顶点$v_j$时，计算它所有直接后继顶点v的最早发生时间，若$ve[j]+Weight(v, v)>ve[k]，\text{则}ve[k]=ve[j] + Weight(v_j, v_k)$。以此类推，直至输出全部顶点。

事件v的最迟发生时间vl(k)

公式中的min：某个事件节点有多个后继用来算最迟发生时间，为了保证最迟发生时间不会发生改变，选由后继算出来的最小的最迟发生时间
vl(k),vertex late k

它是指在不推迟整个工程完成的前提下，即保证它的后继事件$v_j$,在其最迟发生时间$vl(j)$能够发生时，该事件最迟必须发生的时间。可用下面的递推公式来计算:

vl(汇点)= ve(汇点)

$vl(k)= Min\lbrace vl(j) -Weight(v_k, v_j) \rbrace$, $v_k$为$v_j$的任意前驱

$\color{red}{\text{注意:}}$在计算vl(k)时，按从后往前的顺序进行，可以在逆拓扑排序的基础上计算。

计算 $vl()$值时，按从后往前的顺序进行，在上述拓扑排序中，增设一个栈以记录拓扑序列，拓扑排序结束后从栈顶至栈底便为逆拓扑有序序列。过程如下:

${\textstyle\unicode{x2460}}$ 初始时，令$vl[1…n]=ve[n]$。

${\textstyle\unicode{x2461}}$ 栈顶顶点v出栈，计算其所有直接前驱顶点v的最迟发生时间，若$vl[j]- Weight(v_k,v_j) < vl[k]，\text{则}vl[k] = vl[v]- Weight(v_k, v_j)$。以此类推，直至输出全部栈中顶点。

活动$a_i$的最早开始时间e(i)

它是指该活动弧的起点所表示的事件的最早发生时间。若边$< v_k, v_j >$表示活动$a_i$,则有e(i)=ve(k)。

活动$a_i$的最迟开始时间l(i)

它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。若边$< v_k,v_j >$表示活动$a_i$，则有$l(i)=vl(j) - Weight(v_k, v_j)$。

一个活动$a_i$的最迟开始时间$l(i)$和其最早开始时间e(i)的差额d(i)=l(i)-e(i)

关键路径是活动最早开始时间和最迟开始时间相等的边组成的：很容易理解，相等代表不能更晚也不能更早，所以关键

它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动$a_i$可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称l(i)-e(i)=0即l(i)= e(i)的活动$a_i$是关键活动。

求关键路径的算法步骤如下:

1)从源点出发，令ve(源点)=0，按拓扑有序求其余顶点的最早发生时间ve()。

2)从汇点出发，令v(汇点)= ve(汇点)，按逆拓扑有序求其余顶点的最迟发生时间vl()。3）根据各顶点的ve()值求所有弧的最早开始时间e()。

4)根据各顶点的vl(值求所有弧的最迟开始时间l()。

5）求AOE网中所有活动的差额d()，找出所有d()=0的活动构成关键路径。

图6.23所示为求解关键路径的过程,简单说明如下:

1）求ve():初始ve(1)=0，在拓扑排序输出顶点过程中，求得ve(2)= 3，ve(3)= 2，ve(4) =max {ve(2)+ 2, ve(3)+ 4} = max {5,6} =6, ve(5) = 6, ve(6) = max {ve(5)+ 1, ve(4)+2,ve(3)+3}= max {7,8,5} = 8。

如果这是一道选择题，根据上述求ve()的过程就已经能知道关键路径。

2)求v():初始vl(6)=8，在逆拓扑排序出栈过程中，求得vl(5)=7，vl(4)=6，vl(3)= min{vl(4)-4, vl(6)- 3} = min{2,5}=2，vl(2) = min{vl(5)- 3,vl(4)- 2} = min{4,4} =4，vl(1)必然为0而无须再求。

3）弧的最早开始时间e()等于该弧的起点的顶点的ve()，求得结果如下表所示。

4）弧的最迟开始时间 l(i)等于该弧的终点的顶点的vl()减去该弧持续的时间，求得结果如下表所示。

5）根据l(i)- e(i)=0的关键活动，得到的关键路径为$(v_1,v_3, v_4, v_6)$。

对于关键路径，需要注意以下几点:

1）关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。

$\color{red}{\text{Q：}}$ ????还不能缩短到一定程度，工程上肯定不能这样解决问题的吧？？？？

2）网中的关键路径并$\color{red}{\text{不唯一}}$，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在$\color{red}{\text{所有关键路径上}}$的关键活动才能达到缩短工期的目的。

手工求关键路径的方法

• 按照层次遍历的思想给边标序号，边的序号用字母表示
  • 把事件的最晚发生时间，标记在节点的旁边
• 建立两个二维数组

关键路径大话数据结构中的代码描述

etv(earliest time of vertex):顶点事件最早发生的时间点
ltv(latest time of vertex):顶点事件最晚发生的时间点，最晚需要开始的时间，超过此时间将会延误工期
ete(earliest time of edge):活动最早发生的时间点
lte(latest time of edge):活动最晚发生的时间点，不推迟工期的最晚开工时间

p309

查找

p270

【考纲内容】

(一）查找的基本概念

(二）顺序查找法

(三）分块查找法

(四）折半查找法

(五）B树及其基本操作、B+树的基本概念

(六）散列表

(七）查找算法的分析及应用

【知识框架】

• 基本概念:静态查找、动态查找
• 线性结构
  • 顺序查找
  • 折半查找
  • 分块查找
• 树形结构
  • 二叉排序树
  • 二叉平衡树
  • B树、B+树
• 散列结构-散列表
  • 性能分析
  • 冲突处理
• 效率指标一平均查找长度
  • 查找成功
  • 查找失败

【复习提示】

本章是考研命题的重点。对于散列查找，应掌握散列表的构造、冲突处理方法(各种方法的处理过程)、查找成功和查找失败的平均查找长度、)列食找的付征D出1的非占对王P城掌握折半查找的过程、构造判定树、分析平均查找长度等。B树和B+树是本章的难点。对于B树，考研大纲要求掌握插入、删除和查找的操作过程;对于B+树，仅要求了解其基本概念和性质。

单词	含义
ASL,Average Search Length	平均查找长度

查找算法的总结

查找方式	$ASL_{\text{成功}}$	$ASL_{\text{不成功}}$	$ASL$	辅助空间	数组	链表	关键字是否要求有序	其他
顺序查找	$\dfrac{n+1}{2}$	$n +1$			$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{red}{\times}$	可使用哨兵
有序表的顺序查找	$\dfrac{n+1}{2}$	$\dfrac{n}{2} + \dfrac{n}{n+1}$			$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$
折半查找(二分查找)	$\dfrac{n+1}{n} log_2(n+1) -1 $，不超过$\lfloor log_2(n) \rfloor + 1$	不超过$\lfloor log_2(n) \rfloor + 1$	$\dfrac{n+1}{n} log_2(n+1) -1 $,n>50近似$log_2(n+1)-1$		$\color{green}{\checkmark}$	$\color{red}{\times}$	$\color{green}{\checkmark}$
分块查找			$ \dfrac{s^2+2s+n}{2s} $ $\lceil log_2(b+1) \rceil + \dfrac{s+1}{2}$					结合了顺序查找和折半查找的优点，既有动态结构 ，又适于快速查找 块内无序，快间有序

• B-树就是b树

$\color{red}{\text{Q}}$：线性探查再散列退化成线性探测的情况

查找的基本概念

1)查找。在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种:一是$\color{green}{\text{查找成功}}$，即在数据集合中找到了满足条件的数掂$\color{green}{\text{元素}}$;二定$\color{green}{\text{查找失败}}$。

2）查找表（查找结构)。用于查找的数据集合称为$\color{green}{\text{查找表}}$，它田同一类型的数据元素（或记录）组成，可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有4种:①查询某个特定的数据元素是否在查找表中;②检索满足条件的某个特定的数据元素的各种属性;③在查找表中插入一个数据元素;④从查找表中删除某个数据元素。

3）静态查找表。若一个查找表的操作只涉及上述操作①和②，则无须动态地修改查找表，此类查找表称为$\color{green}{\text{静态查找表}}$。与此对应，需要动态地插入或删除的查找表称为$\color{green}{\text{动态查找表}}$。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等;适合动于的查找方法有二叉排序树的查找、散列查找等。二叉平衡树和B树都是二叉排序树的改进。二叉排序树与二叉平衡树已在第4章介绍过。

4）关键字。数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找,查找结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中“学号”这一数据项的值唯一地标识一名学生。

5）平均查找长度。在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为

$\color{red}{\text{需要比较的关键字次数}}$,也就是有点像算法的时间复杂度的概念，循环中一段语句如果执行了>,=,<三次比较，那么他就算这一次中的查找长度为1(这段话用来解释有序表的顺序查找的asl)：虽然感觉很莫名奇妙，明明在代码中执行了三次比较
update:还是很奇怪，2010有一道真题，不成功就是按照最后一个成功节点的比较次数来算的（王道所有关于不成功的比较次数的题目都可以看作是2010真题的变种）；关于成功查找所需要的次数，按照严书对于一个判定树第一个节点就算一次比较，王道书在顺序查找时，自己对顺序表造了个比较查找，此时的判定树认为边才是查找长度；如题14，又是按照严书的定义来的(汗。。。)。$\color{red}{\text{结论}}$：定义还是以真题和严的教材为准；不论是严书还是王道，查找所需的次数 = 查找长度，查找失败的分母为失败节点的个数

$$ASL = \displaystyle_{i=1}^n P_iC_i$$

式中，$n$是查找表的长度；$P_i$是查找第$i$个数据元素的概率，一般认为每个数据元素的查找概率相等，即$P_i$找概率相等，即$P_i = 1/n$;$C_i$是找到第i个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

顺序查找和折半查找

顺序查找

作为一种最直观的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置;若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。下面给出其算法，主要是为了说明其中引入的“$\color{red}{\text{哨兵}}$”的作用。

一般线性表的顺序查找

typedef struct { //查找表的数据结构
  ElemType *elem; //元素存储空间基址,建表时按实际长度分配,0号单元留空
  int TableLen; //表的长度
}SSTable;

int Search Seq (SSTable ST, ElemType key){
  ST.elem [0]=key;//“哨兵”
  for(i=ST.TableLen;ST.elem[i]!=key;--i);//从后往前找
    return i;//若表中不存在关键字为key的元素，将查找到1为0时退出for循环
}

在上述算法中，将ST.elem[ 0]称为“$\color{green}{\text{哨兵}}$”。引入它的目的是使得search_Seq内的循环不必判断数组是否会越界，因为满足i==0时，循环一定会跳出。需要说明的是，在程序中引入“哨兵”并不是这个算法独有的。引入“哨兵”可以避免很多不必要的判断语句，从而提高程序效率。

$\color{red}{\text{Q}}$:在什么时候再次使用了“哨兵”？提高程序效率从何谈起？

对于有n个元素的表，给定值key与表中第i个元素相等，即定位第i个元素时，需进行n-i+1次关键字的比较，即$C_i = n - i + 1$。查找成功时，顺序查找的平均长度为

$$ASL_{\text{成功}} = \displaystyle \sum_{i=1}^n P_i(n-i+1)$$

$i$从1开始计数，当$i$=n时(即查找的元素与最后一个元素相等)，显然比较了一次（key与最后一个元素比较）

当每个元素的查找概率相等，即$P_i= 1/n$时，有

$$ASL_{\text{成功}} = \displaystyle \sum_{i=1}^n P_i(n-i+1) = \dfrac{n+1}{2}$$

首项1，加末项n，的和(n+1)，乘以项数(n)，除以2.

查找不成功时，与表中各关键字的比较次数显然是$n+1$次，从而顺序查找不成功的平均查找长度为$ASL_\text{不成功}= n +1$。

通常，查找表中记录的查找概率并不相等。若能预先得知每个记录的查找概率.则应先对记录的查找概率进行排序，使表中记录按查找概率由大至小重新排列。

综上所述，顺序查找的缺点是当n较大时，平均查找长度较大，效率低;优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用。同时还需注意，对线性的链表只能进行顺序查找。

有序表的顺序查找

若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

假设表工是按关键字从小到大排列的,查找的顺序是从前往后,待查找元素的关键字为key,当查找到第i个元素时，发现第i个元素对应的关键字小于key，但第i+1个元素对应的关键字大于key，这时就可返回查找失败的信息，因为第i个元素之后的元素的关键字均大于key，所以表中不存在关键字为key的元素。

可以用如图7.1所示的判定树来描述有序线性表的查找过程。树中的圆形结点表示有序线性表中存在的元素;树中的矩形结点称为失败结点（若有$n$个结点，则相应地有$n +1$个查找失败结点)，它描述的是那些不在表中的数据值的集合。若查找到失败结点，则说明查找不成功。

在有序线性表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时，查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数。查找不成功的平均查找长度在相等查找概率的情形下为

$$ASL_{\text{不成功}} = \displaystyle \sum_{j=1}^n q_j(l_j -1) = \dfrac{1+2+\cdots+n+n}{n+1} = \dfrac{n}{2} + \dfrac{n}{n+1}$$

l:level
???搞笑吗，$n \to \infty$,你这个算法$ASL$比没有没有优化过更差

式中,$qj$是到达第$j$个失败结点的概率，在相等查找概率的情形下，它为$1/(n + 1)$; $l_j$是第$j$个失败结点所在的层数。当n=6时，$ASL{\text{不成功}} =6/2＋6/76=3.8$，比一般的顺序查找算法好一些。

注意，有序线性表的顺序查找和后面的折半查找的思想是不一样的，且有序线性表的顺序查找中的线性表可以是链式存储结构。

折半查找

折半查找又称$\color{green}{\text{二分查找}}$，它仅适用于$\color{red}{\text{有序的顺序表}}$。

折半查找的基本思想:首先将给定值key 与表中中间位置的元素比较,若相等，则查找成功，返回该元素的存储位置;若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如，在查找表升序排列时,若给定值key大于中间元素，则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。算法如下:

折半查找的代码

int Binary Search (SeqList L, ElemType key)i
  int  low=0,high=L.TableLen-1 , mid;
  while (low<=high){
    mid=(int) (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; //查找失败,返回-1
}

n偶数的话，mid选左边的那个数
如果没有元素high=-1,直接跳出循环返回-1
如果有一个$\color{green}{\text{元素}}$，初始mid=low=high=0，${\textstyle\unicode{x2460}}$ $\color{red}{\text{查找的元素}}$就是这个元素，在第六行就返回所查找的元素；${\textstyle\unicode{x2461}}$ 如果$\color{red}{\text{查找的数}}$比这个$\color{green}{\text{元素}}$小的话,第二次执行循环，high=-1，low=0,low>high退出循环；${\textstyle\unicode{x2462}}$ 如果$\color{red}{\text{查找的数}}$比这个$\color{green}{\text{元素}}$大，第二次执行循环，low=1，high=0，low>high退出循环

二分查找的例子

第四次查找，此时子表只含有一个元素，且10≠11，故表中不存在待查元素。

折半查找的过程可用图7.2所示的二叉树来描述，称为$\color{green}{\text{判定树}}$。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值;树中最下面的叶结点都是方形的，它表示查找不成功的情况。从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数;每个结点值均大于其左子结点值，且均小于于其右子结点值。若有序序列有n个元素，则对应的判定树有n个圆形的非叶结点和n+1个方形的叶结点。显然，$\color{green}{\text{判定树是一棵平衡二叉树}}$。

在等概率由上述分析可知，用折半查找法查找到给定值的比较次数最多不会超过树的高度。查找时,查找成功的平均查找长度为

$$ASL = \dfrac{1}{n} \displaystyle \sum_{i=1}^n l_i = \dfrac{1}{n}(1 \times 1 + 2 \times 2 + \cdots + h \times 2^{h-1}) = \dfrac{n+1}{n} log_2(n+1) -1$$

推到方法：乘公比的式子减去原式除以公比-1，参考文献
此推导的的详细证明：严书p221

二分查找更详细的证明


式中，$h$是树的高度，并且元素个数为$n$时树高$h = \lceil log_2(n + 1) \rceil$。所以，折半查找的时间复杂度为$O(log_2n)$，平均情况下比顺序查找的效率高。

在图7.2所示的判定树中，在等概率情况下，查找成功(圆形结点)的ASL=(1×1＋2×2＋3×4+4×4)/11=3，查找不成功（方形结点）的ASL=(3×4＋4×8)/12= 11/3。

因为折半查找需要方便地定位查找区域,所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。

分块查找

分块查找又称$\color{green}{\text{索引顺序查找}}$，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。

分块查找的基本思想:将查找表分为若干子块。块内的元素可以无序，但块之间是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

分块查找的过程分为两步:第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表;第二步是在块内顺序查找。

例如,关键码集合为{88,24,72,61,21,6,32,11,8,31, 22,83,78,54},按照关键码值24,54,78,88，分为4个块和索引表，如图7.3所示。

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均查找长度分别为$L_I, L_S$，则分块查找的平均查找长度为$ASL = L_I + L_S$

将长度为n的查找表均匀地分为b块，每块有s个记录，在等概率情况下，若在块内和索引表中均采用顺序查找，则平均查找长度为

$$ASL = l_I + L_S = \dfrac{b+1}{2} + \dfrac{s+1}{2} = \dfrac{s^2+2s+n}{2s}$$

此时，若$s=\sqrt{n}$，则平均查找长度取最小值$\sqrt{n}+1$;若对索引表采用折半查找时，则平均查找长度为

$$ASL = L_I + L_S = \lceil log_2(b+1) \rceil + \dfrac{s+1}{2}$$

B树和B+树

考研大纲对B树和 B+树的要求各不相同，重点在于考查B树，不仅要求理解B树的基本特点，还要求掌握B树的建立、插入和删除操作，而对B+树则只考查基本概念。

$\color{red}{\text{Q}}$：删除中间节点(分支节点)

• 替换并删除，严书中的描述如下

反之,若在B-树上删除一个关键字,则首先应找到该关键字所在结点,并从中删除之,若该结点为最下层的非终端结点,且其中的关键字数目不少于$\lceil m/2 \rceil$,则删除完成,含则要进行“合并”结点的操作。假若所删关键字为非终端结点中的$K_i$则可以指针$A_i$所指子树中的最小关键字$Y$替代$K_i$,然后在相应的结点中删去$\text{Y}$。例如,在图9.16(a)的B-树上删去45,可以 f结点中的50替代45,然后在 f结点中删去50。因此，下面我们…

$\color{red}{\text{Q}}$: 插入操作一定是在叶子进行吗

• 可以这么理解，严书中的描述如下

每次插入一个关键字不是在树中添加一个叶子结点,而是首先在,若该结点的关键字个数不超过m-1,则插最低层的某个非终端结点中添加一个关键字，入完成,否则要产生结点的“分裂”,如图9.16所示。

B树及其基本操作

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树:

1）树中每个结点至多有 $\color{green}{\text{m}}$ 棵子树，即至多含有 $\color{green}{\text{m-1}}$ 个关键字。

2）若根结点不是终端结点，则至少有两棵子树。

3）除根结点外的所有非叶结点至少有$\lceil m/2 \rceil$棵子树，即至少含有$\lceil m/2- 1 \rceil$ 个关键字

4）所有非叶结点的结构如下:

n是指关键字的个数；B树的深度：严书中只提到了深度，是包含叶子节点的，
在树的基本术语中，高度和深度在值上是相等的
b树的阶数是预设的(天勤看原论文得出的结论)

原论文


其中，$Ki(i= 1,2,\dots, n）$为结点的关键字，且满足$K_1 < K_2 < \cdots <K_n$; $P_i(i=0,1,\cdots, n）$为指向子树根节点的指针，且指针$P{i-1}$所指子树中所有节点的关键字均小于$K_i$,$P_i$所指子树中所有节点的关键字均大于$K_i$,$n(\lceil m/2 \rceil) -1 \leq n \leq m -1$为节点中关键字的个数

5）所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)。

B树是所有结点的平衡因子均等于О的多路平衡查找树。

图7.4所示的B树中所有结点的最大孩子数m = 5，因此它是一棵5阶B树，在m阶B树中结点最多可以有m个孩子。可以借助该实例来分析上述性质:

1）$\color{green}{\text{结点的孩子个数}}$等于该结点中关键字个数加1。

2）如果根结点没有关键字就没有子树，此时B树为空;如果根结点有关键字，则其子树必然大于等于两棵，因为子树个数等于关键字个数加1。

3）除根结点外的所有非终端结点至少有$\lceil m/2 \rceil =\lceil 5/2 \rceil =3$棵子树（即至少有$\lceil m/2 \rceil - 1=\lceil 5/2 \rceil -1=2$个关键字)，至多有5棵子树(即至多有4个关键字)。

4）结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字。或者看成下层结点关键字总是落在由上层结点关键字所划分的区间内，如第二层最左结点的关键字划分成了3个区间:(-$\infty$, 5), (5,11), (11,+$\infty$)，该结点3个指针所指子树的关键字均落在这3个区间内。

5）所有叶结点均在第4层，代表查找失败的位置。

树的高度（磁盘存取次数)

由下一节将得知，B树中的大部分操作所需的磁盘存取次数与B树的高度成正比。

下面来分析B树在不同情况下的高度。当然，首先应该明确B树的高度不包括最后的不带任何信息的叶结点所处的那一层（有些书对B树的高度的定义中，包含最后的那一层)

若$n\geq1$，则对任意一棵包含$n$个关键字、高度为$h$、阶数为$m$的$B$树:

1）因为B树中每个结点最多有m棵子树，m -1个关键字，所以在一棵高度为h的m阶B树中关键字的个数应满足$n≤(m - 1)(1 +m+ m^2+ \cdots+ m^{h-1})=m^h- 1$，因此有

$$h \geq log_m (n+1)$$

2）若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大。由B树的定义:第一层至少有1个结点;第二层至少有2个结点;除根结点外的每个非终端结点至少有$\lceil m/2 \rceil$棵子树，则第三层至少有$2\lceil m/2 \rceil$个结点$\cdots \cdots$第$h +1$层至少有$2(\lceil m/2 \rceil )^{h-1}$个结点，注意到第h＋1层是不包含任何信息的叶结点。对于关键字个数为n的B树，叶结点即查找不成功的结点为$n+1$，由此有$n+1 \geq 2(\lceil m/2 \rceil )^{h-1}$，即$h \leq log\lceil m/2 \rceil((n+1)/2) + 1$

例如，假设一棵3阶B树共有8个关键字，则其高度范围为2≤h≤3.17。

B树的查找

在B树上进行查找与二叉查找树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。

B树的查找包含两个基本操作:①在B树中找结点;②在结点内找关键字。由于$\color{green}{\text{B树常存储在磁盘上}}$，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。

在B树上查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找（例如，在图7.4中查找关键字42，首先从根结点开始，根结点只有一个关键字，且42>22，若存在，必在关键字22的右边子树上，右孩子结点有两个关键字，而36<42<45，则若存在，必在36和45中间的子树上，在该子结点中查到关键字42，查找成功)。查找到叶结点时（对应指针为空指针)，则说明树中没有对应的关键字，查找失败。

B树的插入

与二叉查找树的插入操作相比，B树的插入操作要复杂得多。在二叉查找树中，仅需查找到需插入的终端结点的位置。但是，在B树中找到插入的位置后，并不能简单地将其添加到终端结点中，因为此时可能会导致整棵树不再满足B树定义中的要求。将关键字key插入B树的过程如下:

1）定位。利用前述的B树查找算法，找出插入该关键字的最低层中的某个非叶结点(在B树中查找key时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置。注意:插入位置一定是最低层中的某个非叶结点)。

2）插入。在B树中，每个非失败结点的关键字个数都在区间$[\lceil m/2 \rceil -1,m-1]$内。插入后的结点关键字个数小于$m$，可以直接插入;插入后检查被插入结点内关键字的个数当插入后的结点关键字个数大于$m-1$时，必须对结点进行分裂。

分裂的方法是:取一个新结点，在插入 key后的原结点，从中间位置($\lceil m/2 \rceil$ )将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置($\lceil m/2 \rceil$)的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1。

对于m =3的B树，所有结点中最多有m-1=2个关键字，若某结点中已有两个关键字，则结点已满，如图7.5(a)所示。插入一个关键字60后，结点内的关键字个数超过了m-1，如图7.5(b)所示，此时必须进行结点分裂，分裂的结果如图7.5(c)所示。

B树的删除

B树中的删除操作与插入操作类似，但要稍微复杂一些，即要使得删除后的结点中的关键字个数≥$\lceil m/2 \rceil$-1，因此将涉及结点的“合并”问题。

当被删关键字k不在终端结点（最低层非叶结点）中时，可以用k的前驱（或后继）k’来替代k，然后在相应的结点中删除k’，关键字k必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。在图7.6的4阶B树中，删除关键字80，用其前驱78替代，然后在终端结点中删除78。因此只需讨论删除终端结点中关键字的情形。

当被删关键字在终端结点（最低层非叶结点）中时，有下列三种情况:

1）直接删除关键字。若被删除关键字所在结点的关键字个数≥$\lceil m/2 \rceil$，表明删除该关键字后仍满足B树的定义，则直接删去该关键字。

2）兄弟够借。若被删除关键字所在结点删除前的关键字个数 =$\lceil m/2 \rceil - 1$，且与此结点相邻的右（或左）兄弟结点的关键字个数≥$\lceil m/2 \rceil$，则需要调整该结点、右(或左）兄弟结点及其双亲结点(父子换位法)，以达到新的平衡。在图7.7(a)中删除4阶B树的关键字65，右兄弟关键字个数 >$\lceil m/2 \rceil =2$，将71取代原65的位置，将74调整到71的位置。

3）兄弟不够借。若被删除关键字所在结点删除前的关键字个数=$\lceil m/2 \rceil - 1$，且此时与该结点相邻的左、右兄弟结点的关键字个数均 =$\lceil m/2- 1 \rceil$，则将关键字删除后与左（或右)兄弟结点及双亲结点中的关键字进行合并。在图7.7(b)中删除4阶B树的关键字5，它及其右兄弟结点的关键字个数=$\lceil m/2 \rceil - 1=1$，故在5删除后将60合并到65结点中。

在合并过程中，双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少至0(根结点关键字个数为1时，有2棵子树)，则直接将根结点删除，合并后的新结点成为根;若双亲结点不是根结点，且关键字个数减少到$\lceil m/2 \rceil -2$，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合B树的要求为止。

严书p245页最后一个例子，剩余的可以用天勤的动画理解

严书p245页最后一个例子

</details>

B+树的基本概念

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

一棵m阶的B+树需满足下列条件:

1）每个分支结点最多有m棵子树（孩子结点)。

2）非叶根结点至少有两棵子树，其他每个分支结点至少有$\lceil m/2 \rceil$棵子树。

3）结点的子树个数与关键字个数相等。

4)所有叶结点包含全部关键字及指向相应记录的指针，叶节点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。

5）所有分支结点(可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。

m阶的B+树与m阶的B树的主要差异如下:

1)在B+树中，具有$n$个关键字的结点只含有$n$棵子树，即每个关键字对应一棵子树;而在B树中，具有$n$个关键字的结点含有$n+1$棵子树。

2)在B+树中，每个结点(非根内部结点)的关键字个数n的范围是$\lceil m/2 \rceil$≤n≤m(根结点:1≤n$<m$);在B树中，每个结点（非根内部结点）的关键字个数n的范围是$\lceil m/2 \rceil$ -1≤n$< m -1$（根结点:1≤n≤m- 1)。

3)在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的仔储地址。

4)）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中;而在B树中，叶结点（最外层内部结点）包含的关键字和其他结点包含的关键字是不重复的。

图7.8所示为一棵4阶B+树。可以看出，分支结点的某个关键字是其子树中最大关键字的副本。通常在B+树中有两个头指针:一个指向根结点，另一个指向关键字最小的叶结点。因此可以对B+树进行两种查找运算:一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。

B+树的查找、插入和删除操作和B树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。所以，在 B+树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。

B树和B+树的区别
在$\color{green}{\text{B+}}$树中，具有$\color{green}{\text{n}}$个关键字的结点含有$\color{green}{\text{n}}$个分支;而在$\color{red}{\text{B-}}$树中，具有$\color{red}{\text{n}}$个关键字的结点含有$\color{red}{\text{n+1}}$个分支。
在B+树上有一个指针指向关键字最小的叶子结点，所有叶子结点链接成一个$\color{green}{\text{线性链表}}$,而B-树没有。

散列表

$\color{red}{\text{Q}}$ ：有hash冲突后的查找查找操作是怎么样的；拉链法很好理解，线性探查之后该怎么查找元素呢？

• 使用冲突处理函数继续查找，如果遇到了空位置就证明不存在，如果第二次扫描到了第一次查找冲突时的位置，也代表失败了
• 查找失败：注意空位置算不算一次比较
• 注意:查找不成功的位置是Hash函数所能映射到的位置，而不是表中所有位置!

$\color{red}{\text{Q}}$ ：插入删除操作是怎么样的

$\color{red}{\text{Q}}$ 如果有hash冲突，查找操作还是O(1)?

• 比如拉链法解决冲突的时候，不是要遍历对应的链表？

$\color{red}{\text{Q}}$：什么是同义词

散列表的基本概念

在前面介绍的线性表和树表的查找中，记录在表中的位置与记录的关键字之间不存在确定关系，因此，在这些表中查找记录时需进行一系列的关键字比较。这类查找方法建立在“比较”的基础上，查找的效率取决于比较的次数。

$\color{green}{\text{散列函数}}$:一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr(这里的地址可以是数组下标、索引或内存地址等)。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为$\color{green}{\text{同义词}}$。一方面，设计得好的散列函数应尽量减少这样的冲突;另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

$\color{green}{\text{散列表}}$:根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。

理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素的个数无关。

下面分别介绍常用的散列函数和处理冲突的方法。

散列函数的构造方法

在构造散列函数时，必须注意以下几点:

1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。

2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。

3）散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址。下面介绍常用的散列函数。

下面介绍常用的散列函数。

直接定址法

直接取关键字的某个线性函数值为散列地址，散列函数为

$$H(key) = key \text{或}H(key)= a \times key + b$$

式中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

除留余数法

这是一种最简单、最常用的方法，假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为

$$H(key) = key \quad \\% \quad p$$

除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。

注意，6 % 5 = 1

数字分析法

设关键字是r进制数（如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等;而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

分析：比如电话号码，使用后面几位而不使用前面几位来做key

平方取中法

顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

在不同的情况下，不同的散列函数具有不同的性能，因此不能笼统地说哪种散列函数最好。在实际选择中，采用何种构造散列函数的方法取决于关键字集合的情况，但目标是尽量降低产生冲突的可能性。

处理冲突的方法

应该注意到，任何设计出来的散列函数都不可能绝对地避免冲突。为此，必须考虑在发生冲突时应该如何处理，即为产生冲突的关键字寻找下一个“空”的Hash地址。用$H_i$表示处理冲突中第i次探测得到的散列地址，假设得到的另一个散列地址$H_1$仍然发生冲突，只得继续求下一个地址$H_2$，以此类推，直到$H_k$不发生冲突为止，则$H_k$为关键字在表中的地址。

开放定址法

所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为

$$H_i= (H(key) + d_i) \% m$$

取定某一增量序列后，对应的处理方法就是确定的。通常有以下4种取法:

1）$\color{green}{\text{线性探测法}}$。当$d_i$=0,1,2,…, m -1时，称为线性探测法。这种方法的特点是:冲突发生时,顺序查看表中下一个单元(探测到表尾地址m-1时，下一个探测地址是表首地址0)，直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。

线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元素的地址……从而造成大量元素在相邻的散列地址上$\color{red}{\text{“聚集”(或堆积)起来}}$，大大降低了查找效率。

堆积现象示意

意思是从冲突位一个一个往后面找

2)平方探测法。当$d_i=0^2,1^2,-1^2,2^2,-2^2,\cdots,k^2,-k^2$时，称为平方探测法，其中$k \leq m/2$散列表长度m必须是一个可以表示成4k＋3的素数，又称$\color{green}{\text{二次探测法}}$。

平方探测法是一种处理冲突的较好方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

3)再散列法。当$d_i=Hash_2(key)$时，称为再散列法，又称双散列法。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时,则利用第.二个散列函数$Hash_2(key)$计算该关键字的地址增量。它的具体散列函数形式如下:

$$H_i= (H(key)+ ixHash_2(key)) \% m$$

初始探测位置$H_0$= H(key)% m。i是冲突的次数，初始为0。在再散列法中，最多经过m-1次探测就会遍历表中所有位置，回到$H_0$位置。

跳着来选key的，所以不容易出现堆积。

4）伪随机序列法。当$d_i=$伪随机数序列时，称为伪随机序列法。

注意:在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此，要删除一个元素时，可给它做一个删除标记,进行逻辑删除。但这样做的副作用是:执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。

拉链法(链接法，chaining)

显然,对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。假设散列地址为i的同义词链表的头指针存放在散列表的第i个单元中，因而查找、插入和删除操作主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况。

例如，关键字序列为{19,14,23,01,68,20,84,27,55,11,10,79}，散列函数H ( key) =key%13，用拉链法处理冲突，建立的表如图7.9所示

例子：redis的dict的实现
查找成功时对空指针的比较一般不算做一次比较

散列查找及性能分析

散列表的查找过程与构造散列表的过程基本一致。对于一个给定的关键字key，根据散列函数可以计算出其散列地址,执行步骤如下:
初始化: Addr=Hash (key) ;

①检测查找表中地址为Addr的位置上是否有记录，若无记录，返回查找失败;若有记录，比较它与key的值，若相等，则返回查找成功标志，否则执行步骤②。用给定的处理冲突方法计算“下一个散列地址”，并把 Addr置为此地址，转入步骤

①。例如，关键字序列{19,14,23,01,68,20,84,27,55,11,10,79}按散列函数H(key)=key%13和线性探测处理冲突构造所得的散列表工如图7.10所示。

给定值84的查找过程为:首先求得散列地址H(84)=6，因$L [ 6]$不空且$L[6]$≠84，则找第一次冲突处理后的地址$H_1$=(6+1)%16=7，而$L[7]$不空且$L[7]$≠84，则找第二次冲突处理后的地址H2=(6+2)%16=8，L[ 8]不空且L[ 8]=84，查找成功，返回记录在表中的序号
给定值38的查找过程为:先求散列地址H(38)=12，$L [12]$不空且$L[12]\neq$ 38，则找下一地址H=(12+1)%16=13，由于$L[13]$是空记录，故表中不存在关键字为38的记录

查找各关键字的比较次数如图7.11所示。

平均查找长度ASL为:ASL= (1×6+2+3×3+4+9)/12= 2.5

对同一组关键字，设定相同的散列函数，则不同的处理冲突的方法得到的散列表不同，它们的平均查找长度也不同，本例与上节采用拉链法的平均查找长度不同。
从散列表的查找过程可见:

(1）虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的度量。

(2）散列表的查找效率取决于三个因素:散列函数、处理冲突的方法和装填因子装填因子。散列表的装填因子一般记为c，定义为一个表的装满程度，即

$$α = \dfrac{表中记录数n}{散列表长度m}$$

散列表的平均查找长度依赖于散列表的装填因子a，而不直接依赖于n或m。直观地看，α越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小。

读者应能在给出散列表的长度、元素个数及散列函数和解决冲突的方法后，在求出散列表的基础上计算出查找成功时的平均查找长度和查找不成功的平均查找长度。

排序

p306

【考纲内容】

(一）排序的基本概念

(二）插入排序
直接插入排序;折半插入排序;希尔排序（shell sort)

(三）交换排序
冒泡排序（ bubble sort);快速排序

(四）选择排序
简单选择排序;堆排序

(五)2路归并排序（merge sort)

(六）基数排序

(七）外部排序

(八）各种排序算法的比较

(九）排序算法的应用

【知识框架】

• 基本概念
  • 稳定性
  • 衡量标准:时、空复杂度
• 内部排序
  • 插入排序
    • 直接插入排序
    • 折半插入排序
    • 希尔排序
  • 交换排序
    • 冒泡排序
    • 快速排序
  • 选择排序
    • 简单选择排序
    • 堆排序
  • 归并排序
  • 基数排序
• 外部排序——多路归并排序

【复习提示】

堆排序、快速排序和归并排序是本章的重难点。读者应深入掌握各种排序算法的思想、排序过程（能动手模拟）和特征（初态的影响、复杂度、稳足性、道用性等)，避吊以远开越的1八考查不同算法之间的对比。此外，对于一些常用排序算法的天键代码，要达到热练绸与的住度;看到某特定序列，读者应具有选择最优排序算法（根据排序算法特征）的能力。

单词	含义
LSD,Least Significant Digit first	最低位优先
MSD,Most Significant Digit first	最高位优先

$\color{red}{\text{Q}}$：总结每种排序算法的特点

排序的基本概念

排序的定义

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便，通常希望计算机中的表是按关键字有序的。排序的确切定义如下:

输入:$n$个记录$R_1, R_2, R_n，$对应的关键字为$k_1, k_2,\cdots, k_n$。

输出:输入序列的一个重排$R_1’，R_2’,\cdots,R_n’$，使得$k_1’ \leq k_2’ \leq \cdots \leq k_n’$(其中“$\leq$”可以换成其他的比较大小的符号)。

算法的稳定性。若待排序表中有两个元素$R_i$和$R_j$，其对应的关键字相同即$key_i= key_j$，且在排序前$R_i$,在$R_j$的前面，若使用某一排序算法排序后，$R_i$仍然在$R_j$的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。需要注意的是，算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。

注意:对于不稳定的排序算法，只需举出一组关键字的实例，说明它的不稳定性即可。

在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类:①内部排序，是指在排序期间元素全部存放在内存中的排序;②外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

一般情况下，内部排序算法在执行过程中都要进行两种操作:比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。当然，并非所有的内部排序算法都要基于比较操作，事实上，基数排序就不基于比较。

每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性能而言，很难提出一种被认为是最好的算法。通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序和基数排序五大类，后面几节会分别进行详细介绍。内部排序算法的性能取决于算法的时间复杂度和空间复杂度，而时间复杂度一般是由比较和移动的次数决定的。

插入排序

插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法:直接插入排序、折半插入排序和希尔排序。

直接插入排序

根据上面的插入排序思想，不难得出一种最简单也最直观的直接插入排序算法。假设在排序过程中，待排序表$L \lbrack 1\cdots n \rbrack$在某次排序过程中的某一时刻状态如下:

要将元素L(i)插入己有序的子序列$L\lbrack 1\cdots i-1 \rbrack$，需要执行以下操作（为避免混淆，下面用$L\lbrack \rbrack$表示一个表，而用L()表示一个元素):

1)查找出L(i)在$L \lbrack 1\cdots i-1 \rbrack$中的插入位置k。

2）将$L \lbrack k\cdots i-1 \rbrack$中的所有元素依次后移一个位置。

3）将L(i)复制到L(k)。

为了实现对$L\lbrack 1\cdots n \rbrack$的排序,可以将L(2)~L(n)依次插入前面已排好序的子序列,初始$L\lbrack 1 \rbrack$可以视为是一个已排好序的子序列。上述操作执行n -1次就能得到一个有序的表。插入排序在实现上通常采用就地排序（空间复杂度为O(1))，因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

下面是直接插入排序的代码，其中再次用到了我们前面提到的“哨兵”(作用相同)。

王道书中关于直接插入排序的代码

 // 王道辅导书的代码
void InsertSort(ElemType A[], int n){
  int i,j;
  for(i=2;i<n;i++)//依次将A[2]～A[n]插入前面已排序序列
  if(A[i]<A[i-1])(  //若A[i]关键码小于其前驱,将A[i]插入有序表
    A[0] = A[i];//复制为哨兵，A[0]不存放元素
    for(j=i-1;A[0]<A[j];--j)//从后往前查找待插入位置 
      A[j+1]=A[j];//向后挪位
    A[j+1]=A[0];//复制到插入位置
}

严书中关于直接插入排序的代码

void InsertSort(SqList &L){
  // 对顺序表L作直接插入排序
  for(i=2; i <= L.length; ++i)
    if(LT(L.r[i].key, L.r[i-1].key)){  // "<",需将L.r[i]插入有序子表
      L.r[0] = L.r[i];  // 复制为哨兵
      L.r[i] = L.r[i-1];
      for(j=i-2; LT(L.r[0].key, L.r[j].key); --j)
        L.r[j+1] = L.r[j];  // 记录后移
      L.r[j+1] = L.r[0]; // 插入到正确的位置
    }
} // InsertSort

哨兵：有和没有都是常熟个辅助单元啊
这个算法非常的魔怔
更魔怔的是，王道，严，天勤上写的都不一样，版本乱天飞,严的代码也很魔怔，if(LT(L.r[i].key, L.r[i-1].key)){ // "<",需将L.r[i]插入有序子表为什么要省花括号呢？？第7行写成j=i-1就没有第6行的事了，真的绝了；
再次更新，第六行还是有作用的，第六行可以减少一次比较！

直接插入排序算法的性能分析如下:

空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)。

时间效率:在排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟,每趟都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。

在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n)。

在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反（逆序)，总的比较次数达到最大，为$\displaystyle \sum{i=2}^n i$，总的移动次数也达到最大，为$\displaystyle \sum{i=2}^n (i+1)$

$\color{red}{\text{Q}}$：为什么最坏的情况，比较次数不是1次？

平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为$n^2/4$。

因此，直接插入排序算法的时间复杂度为O($n^2$)。

稳定性:由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

适用性:直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

注意:大部分排序算法都仅适用于顺序存储的线性表。

折半插入排序

从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作: ${\textstyle\unicode{x2460}}$ 从前面的有序子表中查找出待插入元素应该被插入的位置; ${\textstyle\unicode{x2461}}$ 给抽入位置腾出空间，将待插入元素复制到表中的插入位置。注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时，可以对直接插入排序算法做如下改进:由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素。算法代码如下:

void InsertSort (ElemType A[] ,int n){
  int i,j,low, high, mid;
  for (i=2;i<=n;i++){ //依次将A[2]～A[n]插入前面的已排序序列
  A[0]=A[i];//将A[i]暂存到A[0]
  low=1;high=i-1;//设置折半查找的范围
  while(low<=high){//折半查找(默认递增有序)
    mid=(low+high) /2;//取中间点
  if(A[mid] >A[0]) high-mid-1;//查找左半子表
    else low=mid+1;//查找右半子表
  }
  for(j-i-1;j>=high+1;--j)
    A[j+1]=A[j];//统一后移元素,空出插入位置
  A[high+1]=A[0]; //插入操作
}

严书关于折半插入排序的代码

从上述算法中，不难看出折半插入排序仅减少了比较元素的次数，约为$O(nlog_2n)$，该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数$n$;而元素的移动次数并未改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍为$O(n^2)$，但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。

希尔排序

从前面的分析可知，直接插入排序算法的时间复杂度为$O(n^2)$，但若待排序列为“正序”时，其时间复杂度可提高至$O(n)$，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。

所谓增量就是增加的量，所以算的时候,比如$\color{green}{\text{1}}$,2,$\color{green}{\text{3}}$，1，3被分到了一组，那么增量就是2，下划线的长度为2

希尔排序的基本思想是:先将待排序表分割成若干形如$L\lbrack i, i + d, i+ 2d,\cdots, i + kd \rbrack$的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

希尔排序的过程如下:先取一个小于$n$的步长$d_1$，把表中的全部记录分成$d_1$ 组，所有距离为$d_1$的倍数的记录放在同一组，在各组内进行直接插入排序;然后取第二个步长$d_2 < d_1$过程，直到所取到的$d_t = 1$，即所有记录已放在同一组中，再进行直接插入排序，由于此已经具有较好的局部有序性，故可以很快得到最终结果。到目前为止，尚未求得一个最好的增量序列,

希尔提出的方法是$d1=n/2，d{i+1} = \lfloor d_i /2 \rfloor$，并且最后一个增量等于1。仍以8.2.1节的关键字为例，

第一趟取增量$d_1 = 5$，将该序列分成5个子序列，即图中第2行至第6行，分别对各子序列进行直接插入排序，结果如第7行所示;第二趟取增量$d_2=3$，分别对3个子序列进行直接插入排序，结果如第11行所示;最后对整个序列进行一趟直接插入排序，整个排序过程如图8.2所示。

希尔排序算法的代码如下:

void ShellSort(El emType A[I],int n){
//A[0]只是暂存单元，不是哨兵,当j<=0时，插入位置已到
for (dk=n /2;dk>=1;dk=dk /2)//步长变化
  for(i-dk+1;i<-n;++i)
  if(A[i]<A[i-dk]){//需将A[i]插入有序增量子表
    A [O]=A[i];//暂存在A[0]
    for(j-i-dk;j>0&&A[O]<A[j];j--dk)
      A[j+dk]=A[j]; //记录后移,查找插入的位置
    A[j+dk]=A[0];//插入
  }//if
}

严书希尔排序的过程

图片详情

$\color{red}{\text{Q}}$:暂存元素和哨兵的区别

希尔排序算法的性能分析如下:

空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)。

时间效率:由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为$O(n^{1.3}$。在最坏情况下希尔排序的时间复杂度为$O(n^2)$。

跟增量的选取有关，某个特定的增量的时间复杂度为$O(n^{3/2})$

稳定性:当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。例如，图8.2中49与$\bar{49}$的相对次序已发生了变化

适用性:希尔排序算法仅适用于线性表为$\color{red}{\text{顺序存储}}$的情况。

交换排序

所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法很多，本书主要介绍冒泡排序和快速排序，其中冒泡排序算法比较简单，一般不会单独考查，通常会重点考查快速排序算法的相关内容。

冒泡排序

严书冒泡排序的描述

冒泡排序的基本思想是:从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即$A[i-1]>A[i]$)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做$n-1$趟冒泡就能把所有元素排好序。

图8.3所示为冒泡排序的过程，第一趟冒泡时:27<$\bar{49}$，不交换;13<27，不交换;76>13，交换;97>13，交换;65>13，交换;38>13，交换;49>13，交换。通过第一趟冒泡后，最小元素已交换到第一个位置，也是它的最终位置。第二趟冒泡时对剩余子序列采用同样方法进行排序，以此类推，到第五趟结束后没有发生交换，说明表已有序，冒泡排序结束。

冒泡排序算法的代码如下:

void Bubblesort (ElemType A[], int n){
  for(i-0;i<n-1;i++){
    flag=false;//表示本趟冒泡是否发生交换的标志
    for(j=n-1;j>i;j--)//一趟冒泡过程
    if(A[j-1]>A[j]){//若为逆序
      swap(A[j-1],A[j]);//交换
      flag=true;
    }
    if(flag==false)
    return;
    //本趟遍历后没有发生交换，说明表已经有序
  } 
}

冒泡排序的性能分析如下:

空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)。

时间效率:当初始序列有序时，显然第一趟冒泡后flag依然为false(本趟冒泡没有元素交换)，从而直接跳出循环，比较次数为n-1，移动次数为0，从而最好情况下的时间复杂度为$O(n)$;当初始序列为逆序时，需要进行n-1趟排序，第i趟排序要进行n-i次关键字的比较，而且每次比较后都必须移动元素三次来交换元素位置，这种情况下，

比较次数=$\displaystyle \sum{i=1}^{n-1}=\dfrac{n(n-1)}{2}$,移动次数=$\displaystyle \sum{i=1}^{n-1}3(n-i)=\dfrac{3n(n-1)}{2}$

从而，最坏情况下的时间复杂度为$O(n^2)$,其平均时间复杂度也为$O(n^2)$

稳定性:由于i>j且$A\lbrack i \rbrack = A\lbrack j \rbrack$时，不会发生交换，因此冒泡排序是一种稳定的排序方法。

注意:冒泡排序中所产生的有序子序列一定是全局有序的.(不同于直接插入排序)，也就是说，有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。
为什么要强调这个

快速排序

严书快速排序的代码pp.286

严书快速排序的代码pp.287

快速排序之所以叫快速排序就是因为他是最快的算法（笑

快速排序的基本思想是基于分治法的:在待排序表$L \lbrack 1\cdots n \rbrack$中任取一个元素 pivot 作为枢轴（或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分 L[ 1…k-1]和[ k+1…n]，使得L[ 1…k-1]中的所有元素小于 pivot，L[ k+1..n ]中的所有元素大于等于pivot，则 pivot放在了其最终位置L(k)上，这个过程称为一趟快速排序（或一次划分)。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍，附设两个指针i和j，初值分别为low和 high，取第一个元素49为枢轴赋值到变量pivot。

对算法的最好理解方式是手动地模拟一遍这些算法。

假设划分算法已知，记为Partition ( )，返回的是上述的k，注意到工(k)已在最终的位置，因此可以先对表进行划分，而后对两个表调用同样的排序操作。因此可以递归地调用快速排序算法进行排序，具体的程序结构如下:

void QuickSort (ElemType A[],int low,int high) l
  if (low<high){//递归跳出的条件
  //Partition()就是划分操作，将表A[low…high]划分为满足上述条件的两个子表
    int pivotpos-Partition (A,low, high);//划分
    QuickSort (A, low, pivotpos-1);//依次对两个子表进行递归排序
    Quicksort (A, pivotpos+1, high);
  }

从上面的代码不难看出快速排序算法的关键在于划分操作，同时快速排序算法的性能也主要取决于划分操作的好坏。从快速排序算法提出至今，巴有叶多个P的刘万你1I以队半丰中第一个查的快速排序的划分操作基本以严蔚敏的教材《数据结构》为土。假仅母队芯以表衣动元素作为枢轴来对表进行划分，则将表中比枢轴大的元素向右移动,将比枢轴小的元素向左移动,使得一趟Partition ()操作后，表中的元素被枢轴值一分为二。代码如下:

int Partition (ElemType A[], int low,int high)(//一趟划分
ElemType pivot=A[low];//将当前表中第一个元素设为枢轴,对表进行划分
  while(low<high){
    //循环跳出条件
    while( low<high& &A [high] >=pivot) --high;
    A[low]=A [high];//将比枢轴小的元素移动到左端
    while(low<high && A[low]<=pivot) ++low;
    A[high] =A[low];//将比枢轴大的元素移动到右端
  }
  A[low]=pivot;//枢轴元素存放到最终位置
  return 1ow;//返回存放枢轴的最终位置
}

快速排序算法的性能分析如下:

空间效率:由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。$\color{green}{\text{最好情况}}$下为$O(log_2n)$;$\color{green}{\text{最坏情况}}$下，因为要进行$n—1$次递归调用，所以栈的深度为O(n);平均情况下，栈的深度为$O(log_2n)$。

时间效率:快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含$n-1$个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为$O(n^2)$。

Q：为什么有序不是$O(0)$,不会发生交换啊，虽然这时候比较的次数是$O(n^2)$:第一个工作栈第一个while执行了n次，第二个while不执行，第一个工作栈第一个while执行了n-1次，第二个while不执行….
A：每次递归栈都是n次比较，但是枢纽越中心，递归栈越短，总的比较次数越小
参考文献

有很多方法可以提高算法的效率:-一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素;或者随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。

在最理想的状态下，即 Partition ()可能做到最平衡的划分，得到的两个子问题的大小都不可能大于n/2,在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为$O(nlog_2n)$。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。

快排最优

稳定性:在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录则在交到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。{3,2,2}，经过一趟排序后L={2,2,3}，最终排序序列也是L={2,2,3}，显然，2与2的相对次序已发生了变化。

注意:在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴（基准)元素放到其最终的位置上。

选择排序

p313

选择排序的基本思想是:每一趟（如第i趟）在后$n-i+1(i=1, 2,\cdots,n-1)$个待排序元素中选取关键字最小的元素，作为有序子序列的第$i$个元素，直到第$n-1$趟做完，待排序元素只剩下1个，就不用再选了。选择排序中的堆排序算法是历年考查的重点。

简单选择排序

严书中关于简单选择排序的描述

根据上面选择排序的思想，可以很直观地得出简单选择排序算法的思想:假设排序表为L[ 1…n]，第i趟排序即从L[ i…n ]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。

简单选择排序算法的代码如下:

void SelectSort (ElemType A[] ,int n){
  for(i=0;i<n-1;i++){//一共进行n-1趟
    min=i;//记录最小元素位置
    for(j-i+1;j<n;j++)//在A[i...n-1]中选择最小的元素
      if(A[j]<A[min])min=j;//更新最小元素位置
    if(min!=i) swap (A[i],A[min]);//封装的swap()函数共移动元素3次
  }
}

简单选择排序算法的性能分析如下:

空间效率:仅使用常数个辅助单元，故空间效率为O(1)。

时间效率:从上述伪码中不难看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过3(n-1)次，最好的情况是移动О次，此时对应的表已经有序;但元素间比较的次数与序列的初始状态无关，始终是n(n- 1)/2 次，因此时间复杂度始终是$O(n^2)$。

稳定性:在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。例如，表L= {$\color{green}{\text{2}}$,$\color{red}{\text{2}}$,1}，经过一趟排序后L= {1,$\color{red}{\text{2}}$,$\color{green}{\text{2}}$}，最终排序序列也是L= {1,$\color{red}{\text{2}}$,$\color{green}{\text{2}}$}，显然，$\color{red}{\text{2}}$与$\color{green}{\text{2}}$的相对次序已发生变化。因此，简单选择排序是一种不稳定的排序方法。

堆排序

Q：堆和平衡二叉树的区别
A：堆只保证父子(两层)之间的大小关系，而平衡二叉树需要保证所有层间的大小关系，而且大顶堆一定不是平衡二叉树

堆的定义如下，n个关键字序列L[ 1…n]称为堆，当且仅当该序列满足:

${\textstyle\unicode{x2460}}$ L(i) >=L(2i)且L(i) >=L (2i+1)或

${\textstyle\unicode{x2461}}$ L(i)<=L(2i)且L(i)<=L(2i+1)（$1\leq i \leq \lfloor n/2 \rfloor$)

可以将该一维数组视为一棵完全二叉树，满足条件①的堆称为大根堆（大顶堆)，大根堆的最大元素存放在根结点，且其任一非根结点的值小于等于其双亲结点值。满足条件②的堆称为小根堆（小顶堆)，小根堆的定义刚好相反，根结点是最小元素。图8.4所示为一个大根堆。

堆排序的思路很简单:首先将存放在L[ 1…n ]中的n个元素建成初始堆,由于堆本身的特点(以大顶堆为例)，堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。可见堆排序需要解决$\color{green}{\text{两个问题}}$:

①如何将无序序列构造成初始堆?
②输出堆顶元素后，如何将剩余元素调整成新的堆?

堆排序的关键是构造初始堆。n 个结点的完全二叉树，最后一个结点是第$\lfloor n/2 \rfloor$个结点的孩子。对第$\lfloor n/2 \rfloor$个结点为根的子树筛选（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换)，使该子树成为堆。之后向前依次对各结点$(\lfloor n/2 \rfloor -1\backsim 1)$为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。

如图8.5所示，初始时调整L(4)子树，09< 32，交换，交换后满足堆的定义;向前继续调整L(3)子树，78<左右孩子的较大者87，交换，交换后满足堆的定义;向前调整L(2)子树，17<左右孩子的较大者45，交换后满足堆的定义;向前调整至根结点L(1)，53<左右孩子的较大者87，交换，交换后破坏了L(3)子树的堆，采用上述方法对L(3)进行调整，53<左右孩子的较大者78，交换，至此该完全二叉树满足堆的定义。

输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。将09和左右孩子的较大者78交换，交换后破坏了L(3)子树的堆，继续对L(3)子树向下筛选，将09和左右孩子的较大者65交换，交换后得到了新堆，调整过程如图8.6所示。

下面是建立大根堆的算法:

void BuildMaxHeap (ElemType A[] ,int len){
  for(int i=len/2;i>0;i--) //从 i-[n/2]～1,反复调整堆
    HeadAdjust(A,i,len);
}


void HeadAdjust (ElemType A[],int k,int len){
  //函数HeadAdjust将元素k为根的子树进行调整
  A[0]=A[k]; //A[0]暂存子树的根结点
  for(i=2*k;i<=len;i*=2){ //沿key较大的子结点向下筛选
    if(i<len& &A[i]<A[i+1])
      i++;//取key 较大的子结点的下标
    if(A[0]>=A[i]) break;//筛选结束
    else{
      A[k]=A[i];//将A[i]调整到双亲结点上
      k=i;//修改k值,以便继续向下筛选
    }
  }
  A[k]=A[0];//被筛选结点的值放入最终位置
}

调整的时间与树高有关，为O(h)。在建含n个元素的堆时，关键字的比较总次数不超过4n，时间复杂度为O(n)，这说明可以在线性时间内将一个无序数组建成一个堆。

关键字比较次数的推导，$\color{red}{\text{Q}}$：为什么是4n，还是没搞明白

严书关键字比较次数的推导

严书堆排序的算法

代码详情:严书堆排序的算法

通过对堆排序的基本了解，首先发现堆排序有两个过程刚开始得到一个待排序序列时候的$\color{green}{\text{建堆}}$和输出了一个元素之后的$\color{green}{\text{堆重建}}$

这两个步骤，都有一个$\color{green}{\text{共同的步骤}}$，「需要为$\color{red}{\text{工作指针}}$指向的元素的找到正确位置」 ，我们把这步叫做$\color{yellow}{\text{调整元素}}$

这个共同步骤的核心是按照大根堆还是小根堆(热知识：想得到一个升序序列那么使用大根堆，降序用小根堆)的需求，将$\color{red}{\text{工作指针}}$指向的元素“$\color{green}{\text{不断}}$向下层调整”,直到满足堆的定义

$\color{green}{\text{建堆}}$的关键:$\color{red}{\text{工作指针}}$从$\lfloor n/2 \rfloor$开始不断往前$\color{yellow}{\text{调整元素}}$

$\color{green}{\text{堆重建}}$的关键:将对堆顶元素输出（就是和最后一个元素交换），之后对堆顶元素进行$\color{yellow}{\text{调整元素}}$

下面是堆排序算法:

// 王道
void HeapSort (ElemType A[] ,int len){
  BuildMaxHeap (A,len);//初始建堆
  for(i=len;i>1;i--){//n-1趟的交换和建堆过程
    Swap (A[i],A[1]);//输出堆顶元素（和堆底元素交换)
    HeadAdjust(A, 1,i-1);//调整，把剩余的i-1个元素整理成堆
  }
}

同时，堆也支持插入操作。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作。大根堆的插入操作示例如图8.7所示。

堆排序适合关键字较多的情况。例如，在1亿个数中选出前100个最大值?首先使用一个大小为100的数组，读入前100个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中100个数即为所求。

堆排序算法的性能分析如下:

空间效率:仅使用了常数个辅助单元，所以空间复杂度为O(1)。

时间效率:建堆时间为O(n)，之后有n-1次向下调整操作，每次调整的时间复杂度为O(h),故在最好、最坏和平均情况下，堆排序的时间复杂度为$O(nlog_2n)$。

稳定性:进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法。例如,表L={1,$\color{green}{\text{2}}$,$\color{red}{\text{2}}$}，构造初始堆时可能将$\color{green}{\text{2}}$交换到堆顶，此时L={$\color{green}{\text{2}}$,1,$\color{red}{\text{2}}$}，最终排序序列为L={1,$\color{red}{\text{2}}$,$\color{green}{\text{2}}$}，显然，$\color{red}{\text{2}}$与$\color{green}{\text{2}}$的相对次序已发生变化。

归并排序和基数排序

归并排序

严书中归并排序的代码pp.296

归并排序与上述基于交换、选择等排序的思想不一样，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。假定待排序表含有$n$个记录，则可将其视为$n$个有序的子表，每个子表的长度为1，然后两两归并，得到$\lceil n/2 \rceil$个长度为2或1的有序表;继续两两归并……如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2路归并排序。

图8.8所示为2路归并排序的一个例子，经过三趟归并后合并成了有序序列。

Merge()的功能是将前后相邻的两个有序表归并为一个有序表。设两段有序表A[ low..mid ]、A[ mid+1…high ]存放在同一顺序表中的相邻位置，先将它们复制到辅助数组B中。每次从对应B中的两个段取出一个记录进行关键字的比较，将较小者放入A中，当数组B中有一段的下标超出其对应的表长(即该段的所有元素都已复制到A中）时，将另一段中的剩余部分直接复制到A中。算法如下:

ElemType *B=(Elemype *)malloc((n+1)*sizeof (ElemType));//辅助数组B
void Merge (ElemtType A[],int low,int mid,int high){
  //表A的两段A[low..mid]和A[mid+1..high]各自有序,将它们合并成一个有序表
  for (int k=low;k<=high;k++)
    B[k]=A[k];//将A中所有元素复制到B中
  for(i=low,j=mid+1,k=i;i<=mid&&j<=high; k++){
    if(B[i]<=B[j)//比较B的左右两段中的元素
      A[k]=B[i++];//将较小值复制到A中
    else
      A[k]=B[j++];
  }//for
  while (i<=mid) A[k++]=B[i++];//若第一个表未检测完，复制
  while(j<=high) A[k++]=B[j++];//若第二个表未检测完，复制
}

注意:上面的代码中，最后两个while循环只有一个会执行。

一趟归并排序的操作是，调用$\lceil n/2h \rceil$次算法merge ()，将L[ 1…n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，整个归并排序需要进行$log_2n$趟。

递归形式的2路归并排序算法是基于分治的,其过程如下。

分解:将含有n个元素的待排序表分成各含n/2个元素的子表，采用2路归并排序算法对两个子表递归地进行排序。

void MergeSort (ElemType A[],int low,int high){
  if(low<high){
  int mid=(low+high) /2;//从中间划分两个子序列
  MergeSort (A,low, mid);//对左侧子序列进行递归排序
  MergeSort (A, mid+l,high);//对右侧子序列进行递归排序
  Merge (A, low,mid,high);//归并
  }//if
}

2路归并排序算法的性能分析如下:

空间效率:Merge ()操作中，辅助空间刚好为n个单元，所以算法的空间复杂度为O(n)。时间效率:每趟归并的时间复杂度为O(n)，共需进行$\lceil log_2n \rceil$趟归并，所以算法的时间复杂度为$O(nlog_2n)$。

为什么每趟归并的时间复杂度是$O(n)$

稳定性:由于 Merge ()操作不会改变相同关键字记录的相对次序，所以2路归并排序算法是一种稳定的排序方法。

注意:一般而言，对于$N$个元素进行$k$路归并排序时，排序的趟数m满足$k^m=N$，从而$m =log_kN$，又考虑到$m$为整数，所以$m =\lceil log_k N \rceil$。这和前面的2路归并是一致的。

基数排序

严书中基数排序的数据结构

严书中基数排序的代码

基数排序是一种很特别的排序方法，它不基于比较和移动进行排序，而基于关键字各位的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

假设长度为$n$的线性表中每个结点$a_j$的关键字由$d$元组$(k_j^{d-1} , k_j^{d-2} ,\cdots ,k_j^{1},k_j^{0}$组成,满足$0 \leq k_j^i \leq r-1(0\leq j < n, 0 \leq i \leq d-1)$。其中$k_j^{d-1}$为最主位关键字，$k_j^0$为最次位关键字

为实现多关键字排序，通常有两种方法:第一种是最高位优先($\color{green}{\text{MSD}}$）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（$\color{green}{\text{LSD}}$）法，按关键字权重递增依次进行排序，最后形成一个有序序列。

下面描述以r为基数的最低位优先基数排序的过程，在排序过程中，使用r个队列$Q0，Q_1,\cdots,Q{r-1}$。基数排序的过程如下：

对$i=0,1,\cdots,d-1$,一次做一次“分配”和“收集”（其实是一次稳定的排序过程）

分配：开始时，把$Q0，Q_1,\cdots,Q{r-1}$各个队列置成空队列，然后一次考察线性表中的每个节点$a_j(j=0,1,\cdots,n-1)$，若$a_j$的关键字$k_j^i=k$，就把$a_j$放进$Q_k$队列中

通常采用链式基数排序，假设对如下10个记录进行排序:

每个关键字是1000以下的正整数，基数r= 10，在排序过程中需要借助10个链队列，每个关键字由3位子关键字构成$K^1K^2K^3$，分别代表百位、十位和个位，一共需要进行三趟“分配”和“收集”操作。第一趟分配用最低位子关键字$K^3$进行，将所有最低位子关键字（个位)相等的记录分配到同一个队列，如图 8.9(a)所示，然后进行收集操作，第一趟收集后的结果如图8.9(b)所示。

第二趟分配用次低位子关键字$K^2$进行，将所有次低位子关键字(十位）相等的记录分配到同一个队列，如图8.10(a)所示，第二趟收集后的结果如图8.10(b)所示。

第三趟分配用最高位子关键字$K^1$进行，将所有最高位子关键字（百位）相等的记录分配到同一个队列，如图8.11(a)所示，第三趟收集后的结果如图8.11(b)所示，至此整个排序结束

基数排序算法的性能分析如下。
空间效率:一趟排序需要的辅助存储空间为r(r个队列:r个队头指针和r个队尾指针)，但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为O(r)。

时间效率:基数排序需要进行d趟分配和收集，一趟分配需要O(n)，一趟收集需要O(r)，所以基数排序的时间复杂度为O(d(n +r))，它与序列的初始状态无关。

稳定性:对于基数排序算法而言，很重要一点就是按位排序时必须是稳定的。因此.这也保证了基数排序的稳定性。

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

内部排序算法的比较

前面讨论的排序算法很多，对各算法的比较是考研中必考的内容。一般基于三个因素进行对比:时空复杂度、算法的稳定性、算法的过程特征。

从时间复杂度看:简单选择排序、直接插入排序和冒泡排序平均情况下的时间复杂度都为$O(n^2)$,且实现过程也较简单,但直接插入排序和冒泡排序最好情况下的时间复杂度可以达到O(n)，而简单选择排序则与序列的初始状态无关。希尔排序作为插入排序的拓展，对较大规模的排序都可以达到很高的效率，但目前未得出其精确的渐近时间。堆排序利用了一种称为堆的数据结构，可在线性时间内完成建堆，且在$O(nlog_2n)$内完成排序过程。快速排序基于分治的思想，虽然最坏的情况下快速排序时间会达到$O(n^2)$，但快速排序平均性能可以达到$O(nlog_2n)$与初始序列的排列无关，优于其他排序算法。归并排序同样基于分治的思想，但由于其分割子序列与初始序列的排序无关，因此它的最好、最坏和平均时间复杂度均为$O(nlog_2n)$。

从空间复杂度看:简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需要常数个辅助空间。快速排序在空间上只使用一个小的辅助栈，用于实现递归，平均情况下大小位$O(log_2n)$，当然在最坏情况下可能会增长到$O(n)$。2路归并排序在合并操作中需要借助较多的空间用于元素复制，大小为$O(n)$，虽然有方法能克服这个缺点，但其代价是算法会很复杂而且时间复杂度会增加。

从稳定性看:插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法，而简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序方法。对于排序方法的稳定性，读者应能从算法本身的原理上去理解，而不应拘泥于死记硬背。

从过程特征看:采用不同的排序算法，在一次循环或几次循环后的排序结果可能是不同的，考研题中经常出现给出一个待排序的初始序列和已经部分排序的序列，问其采用何种排序算法。这就要对各类排序算法的过程特征十分熟悉，如冒泡排序和堆排序在每趟处理后都能产生当前的最大值或最小值，而快速排序一趟处理就能确定一个元素的最终位置等。

表8.1列出了各种排序算法的时空复杂度和稳定性情况，其中空间复杂度仅列举了平均情况的复杂度，由于希尔排序的时间复杂度依赖于增量函数，所以无法准确给出其时间复杂度。

数组排序的方式：

排序方式	时间复杂度(最好/平均/最坏)	空间复杂度(最好/平均/最坏)	稳定性	数组	链表
直接插入排序	$O(n)$/$O(n^2)$/$O(n^2)$	$O(1)$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$
希尔排序	$O(nlogn), O(n^{1.3})$/None/$O(n^2)$	$O(1)$	$\color{red}{\times}$	$\color{green}{\checkmark}$	$\color{red}{\times}$
冒泡排序	$O(n)$/$O(n^2)$/$O(n^2)$	$O(1)$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$
快速排序	$O(nlogn)$/$O(nlogn)$/$O(n^2)$	$O(logn) \backsim O(n)$	$\color{red}{\times}$	$\color{green}{\checkmark}$	$\color{red}{\times}$
简单选择选择排序	$O(n^2)$/$O(n^2)$/$O(n^2)$	$O(1)$	$\color{red}{\times}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$
堆排序	$O(nlogn)$/$O(nlogn)$/$O(nlogn)$	$O(1)$	$\color{red}{\times}$	$\color{green}{\checkmark}$	$\color{red}{\times}$
归并排序	$O(nlogn)$/$O(nlogn)$/$O(nlogn)$	$O(n)$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$
基数排序	$O(d(n+r))$/$O(d(n+r))$/$O(d(n+r))$	$O(r)$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$

• 关于为什么$\color{green}{\text{直接插入排序}}$可以用于$\color{green}{\text{链表}}$,直接插入排序将遍历有序表的插入位置变成指针的移动实现和for i一样的操作

可视化参考文献

三种方法解决链表排序问题

内部排序算法的应用

通常情况，对排序算法的比较和应用应考虑以下情况。

1）选取排序方法需要考虑的因素

${\textstyle\unicode{x2460}}$ 待排序的元素数目n。

${\textstyle\unicode{x2461}}$元素本身信息量的大小。

${\textstyle\unicode{x2462}}$ 关键字的结构及其分布情况。

${\textstyle\unicode{x2463}}$ 稳定性的要求。

${\textstyle\unicode{x2464}}$ 语言工具的条件,存储结构及辅助空间的大小等。

2）排序算法小结

${\textstyle\unicode{x2460}}$ 若n较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。

②若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

③若n较大，则应采用时间复杂度为$O(nlog_2n)$的排序方法:快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助全间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为$O(nlog_2n)$，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用，利用直接插入排序求得较长的有序子文件，然后两两归并。直接插入排序是稳定的，因此改进后的归并排序仍是稳定的。

④在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明:当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要$O(nlog_2n)$的时间。

⑤若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。

⑥当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。

外部排序

外部排序可能会考查相关概念、方法和排序过程，外部排序的算法比较复杂,不会在算法去设计上进行考查。本节的主要内容有:

${\textstyle\unicode{x2460}}$ 外部排序指待排序文件较大，内存一次放不下，需存放在外存的文件的排序

②为减少平衡归并中外存读写次数所采取的方法:增大归并路数和减少归并段个数。

③利用败者树增大归并路数。

④利用置换-选择排序增大归并段长度来减少归并段个数。

${\textstyle\unicode{x2464}}$ 由长度不等的归并段，进行多路平衡归并，需要构造最佳归并树。

外部排序的基本概念

前面介绍过的排序方法都是在内存中进行的（称为内部排序)。而在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。这种排序方法就称为外部排序。

外部排序的方法

文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读/写的机械动作所需的时间远远超过内存运算的时间（相比而言可以忽略不计)，因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。

外部排序通常采用归并排序法。它包括两个相对独立的阶段:①根据内存缓冲区大小，将外存上的文件分成若干长度为$\ell$的子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串;②对这些归并段进行逐趟归并，使归并段（有序子文件）逐渐由小到大，直至得到整个有序文件为止。

例如，一个含有2000个记录的文件，每个磁盘块可容纳125个记录，首先通过8次内部排序得到8个初始归并段R1~R8，每个段都含250个记录。然后对该文件做如图8.7所示的两两归并，直至得到一个有序文件。

把内存工作区等分为3个缓冲区，如图8.6所示，其中的两个为输入缓冲区，一个为输出缓冲区。首先，从两个输入归并段R1和R2中分别读入一个块，放在输入缓冲区1和输入缓冲区2中。然后，在内存中进行2路归并，归并后的对象顺序存放在输出缓冲区中。若输出缓冲区中对象存满，则将其顺序写到输出归并段(R1’)中，再清空输出缓冲区，继续存放归并后的对象。若某个输入缓冲区中的对象取空，则从对应的输入归并段中再读取下一块，继续参加归并。如此继续，直到两个输入归并段中的对象全部读入内存并都归并完成为止。当R1和R2归并完后，再归并R3和R4、R5和R6、最后归并R7和R8，这是一趟归并。再把上趟的结果R1’和R2’、R3’和R4’两两归并，这又是一趟归并。最后把R1”和R2”两个归并段归并，结果得到最终的有序文件，一共进行了3趟归并。

在外部排序中实现两两归并时，由于不可能将两个有序段及归并结果段同时存放在内存中，因此需要不停地将数据读出、写入磁盘，而这会耗费大量的时间。一般情况下:

外部排序的总时间=内部排序所需的时间＋外存信息读写的时间＋内部归并所需的时间

显然，外存信息读写的时间远大于内部排序和内部归并的时间，因此应着力减少I/O次数。由于外存信息的读/写是以“磁盘块”为单位的，可知每一趟归并需进行16次“读”和16次“写”,3趟归并加上内部排序时所需进行的读/写，使得总共需进行32x3＋32=128次读写。

$\color{red}{\text{Q}}$:为什么是16次读，16次写？
$\color{red}{\text{A}}$:2000/125=16

若改用4路归并排序，则只需⒉趟归并，外部排序时的总读/写次数便减至32×2 + 32 = 96。因此，增大归并路数，可减少归并趟数，进而减少总的磁盘IO次数，如图8.8所示。

一般地，对r个初始归并段，做k路平衡归并，归并树可用严格k叉树（即只有度为k与度为0的结点的k叉树）来表示。第一趟可将r个初始归并段归并为$\lceil r/k \rceil$个归并段，以后每趟归并将m个归并段归并成$\lceil m/k \rceil$ 个归并段，直至最后形成一个大的归并段为止。树的高度=$\lceil log_kr \rceil$= 归并趟数$S$。可见，只要增大归并路数$k$，或减少初始归并段个数$r$，都能减少归并趟数$S$，进而减少读写磁盘的次数，达到提高外部排序速度的目的。

多路平衡归并与败者树

上节讨论过，增加归并路数k能减少归并趟数S，进而减少I/O次数。然而，增加归并路数k时，内部归并的时间将增加。做内部归并时，在k个元素中选择关键字最小的记录需要比较k-1次。每趟归并n个元素需要做(n-1)(k-1)次比较，S趟归并总共需要的比较次数为

S(n- 1)(k- 1)=$\lceil log_k r \rceil$ (n - 1)(k - 1)=$\lceil log_k r \rceil$ (n - 1)(k - 1)/$\lceil log_2k \rceil$

式中，$(k-1)/log_2k$随k增长而增长，因此内部归并时间亦随k的增长而增长。这将抵消由于增大k而减少外存访问次数所得到的效益。因此，不能使用普通的内部归并排序算法。

为了使内部归并不受$k$的增大的影响，引入了败者树。败者树是树形选择排序的一种变体，可视为一棵完全二叉树。$k$个叶结点分别存放$k$个归并段在归并过程中当前参加比较的记录，内部结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。若比较两个数，大的为失败者、小的为胜利者，则根结点指向的数为最小数。

S趟归并总共需要的比较次数怎么来的
外部归并的时候每一次要从内存中选出最小的值，最原始的算法就是遍历内存中的所有值

构建败者树的参考文献

构建败者树的过程

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

最佳归并树