数据结构-全

2. 线性表

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

定义：n（n>=0）个相同数据类型的数据元素构成的有限序列，n=0时，线性表为空表。线性表用L一般表示为：

L = (a1,a2,a3....,ai-1,ai....,an)

几个概念:
ai是线性表中的“第i个”元素线性表中的位序注意:位序从1开始，数组下标从0开始
a1是表头元素; an 是表尾元素。

除第一个元素外，每个元素有且仅有一个直接前驱:除最后一个元素外，每个元素有且仅有一个直接后继

InitList(&L):初始化表。构造一个空的线性表L，分配内存空间。

DestroyList(&():销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

Listnsert(&L,e):插入操作。在表L中的第1个位置上插入指定元素e.

ListDelete(&L,&e):删除操作。删除表l中第1个位置的元素，并用e返回删除元素的值。

LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。

GetElem(Lj):按位查找操作。获取表L中第i个位置的元素的值。其他常用操作:

Length(U:求表长。返回线性表L的长度，即L中数据元素的个数。

PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。.

Empty(L):判空操作。若L为空表，则返回true，否则返回false.

Tips:
①对数据的操作(记忆思路) --创销、增删改查

②C语言函数的定义-- <返回值类型> 函数名(<参数1类型>参数1，<参数2类型>参数2，...)

③实际开发中，可根据实际需求定义其他的基本操作

④函数名和参数的形式、命名都可改变(Reference: 严蔚敏版《数据结构》Key:命名要有可读性

⑤什么时候要传入参数的引用“&”--对参数的修改结果需要“带回来”

2.2 顺序表

2.2.1 顺序表的定义

线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列

线性表L的逻辑结构

线性表的存储结构：顺序表——即在逻辑结构上相邻，在物理（存储）结构上也相邻

顺序表——用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

顺序表的实现——静态分配

#define MaxSize 10  			//定义最大长度
typedef struct{
    //ElemType是需要给定的数据类型
	ElemType data [MaxSize] ;	//用静态的“数组”存放数据元素.
	int length;					//顺序表的当前长度.
}SqList;						//顺序表的类型定义(静态分配方式)

eg:

#include<stido.h>
#define MaxSize 10  			//定义最大长度
typedef struct{
	int data [MaxSize] ;	//用静态的“数组”存放数据元素.
	int length;					//顺序表的当前长度.
}SqList;

void InitList(SqLsit &L){
	for(int i=0; i<MaxSize; i++){
        L.data[i] = 0;		//若不赋值，不能保障之前内存是否留存“脏数据”
    }
    L.length = 0;
}

int main(){
	SqList L; 		//声明一个顺序表
	InitList(L);	//初始化顺序表
	//....
	return 0;
}

静态分配会存在数据存满后就不能存的情况

顺序表的实现——动态分配**

#define InitSize 10 //顺序表的初始长度.
typedef struct{
    ELemType *data;		//指示动态分配数组的指针
    int MaxSize;		//顺序表的最大容量
    int length;			//顺序表的当前长度
} SeqList;			//顺序表的类型定义(动态分配方式)

动态申请和释放空间

C——malloc、free函数
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize)
C++——new、delete

eg：

#include <stdlib.h>
#define InitSize 10 	//默认的最大长度
typedef struct{
    int *data;			//指示动态分配数组的指针
    int MaxSize;		//顺序表的最大容量
    int length;			//顺序表的当前长度
}SeqList;

void InitList(SeqList &L){
    //用mal1oc 函数申请一片连续的存储空间
    L.data=(int * )malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
    int *p=L.data; //让p指向原区域
    L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0; i<L.length; i++){
    	L.data[i]=p[i];			//将数据复制到新区域：时间开销大
	}
    L.MaxSize=L.MaxSize+len;	//顺序表最大长度增加len
    free(p);	//释放原来的内存空间
}

int main(){
	SeqList L;
	InitList(L);
    //....往顺序表中插入几个元素
    IncreaseSize(L,5);
    return 0;
}

顺序表的特点:

①随机访问，即可以在O(1)时间内找到第i个元素。代码实现: data[i-1];静态分配、动态分配都一样

②存储密度高，每个节点只存储数据元素

③拓展容量不方便(即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)

④插入、删除操作不方便，需要移动大量元素

2.2.2 顺序表的基本操作

1. 顺序表的插入和删除

顺序表的基本操作——插入

void ListInsert(SqList &L, int i, int e){	//在L的位序i处插入元素e
    for(int j = L.length;j>i;j--)	//所有i后面的元素往后移一位
        L.data[j] = L.data[j-1]
    L.data[i-1] = e;				//位序i，对应数组i-1
    L.length++;
}

优化代码：

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

好的算法，应该具有“健壮性”。能处理异常情况，并给使用者反馈

顺序表的基本操作——删除

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

2. 顺序表的查找

顺序表按位查找

GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

#define MaxSize 10 				//定义最大长度
typedef struct{
    ElemType data [MaxSize] ;	//用静态的“数组”存放数据元素（静态分配）
    int length;					//顺序表的当前长度:
}SqList;						//顺序表的类型定义(静态分配方式)

ElemType GetElem(SqList L，int i){
	return L.data[i-1];
}

GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

#define InitSize 10 //顺序表的初始长度
typedef struct{
    ElemType *data;		//指示动态分配数组的指针 动态分配
    int MaxSize;		//顺序表的最大容量
    int length;			//顺序表的当前长度
} SeqList;				//顺序表的类型定义(动态分配方式)

时间复杂度：O(1)

由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素——“随机存取”特性

顺序表按值查找

LocateElem(,e):按值查找操作。在表L中查找具有给定关键字值的元素。

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

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

基本数据类型: int、 char、 double、float等可以直接用运算符“==”比较

对于结构体的比较：

需要依次对比各个分量来判断两个结构体是否相等
typedef struct {
 int num;
 int people; 
} Customer;
if (a.num ==: b.num && a.people == b.people) {
	printf("相等");
}else {
	printf( "不相等");
}

2.3 单链表

单链表和顺序表的区别

struct LNode{			//结点
	ElemType data;		//数据域
	struct LNode* p;	//指针域
}

增加一个新的结点:在内存中申请一个结点所需空间，并用指针p指向这个结点

struct LNode* p= (struct LNode* )malloc(sizeof(struct LNode));

typedef关键字一一数据类型重命名

typedef <数据类型> <别名>
typedef struct LNode LNode;
LNode *p= (LNode *)malloc(sizeof(LNode));

代码优化：

typedef struct LNode{ 	//定义单链表结点类型
    ElemType data;			//每个节点存放- -个数据元素
    struct LNode *next ;	//指针指向下一个节点
}LNode, *LinkList;

LNode *p和 LNode L都表示指向结构体的指针

LNode *p 一般表示节点的指针

LNode L 头指针，一般用来表示一个链表

2.3.1 单链表的定义

不带头结点的单链表

bool InitList(LinkList &L){
	L = NULL;			//空表暂时没有任何节点（防止脏数据）
	return ture;
}

void test(){
	LinkList L;		//注意，此处并没有创建个结点
	InitList(L);
}

判空

//判断单链表是否为空
bool Empty(LinkList L) {
	if (L == NULL)
		return true;
	else
		return false;
}
//或者
bool Empty(LinkList L) {
	return (L==NULL); .
}

带头结点的单链表

//初始化-个单链表(带头结点)
bool InitList(LinkList &L) {
    L = (LNode *) malloc(sizeof(LNode)); //分配一个头结点
    if (L==NULL) //内存不足， 分配失败
    	return false;
    L->next = NULL;//头结点之后暂时还没有节点
    return true;
}

判空

//判断单链表是否为空(带头结点)
bool Empty(LinkList L) {
    if (L->next == NULL)
        return true;
    else
    	return false;
}

不带头结点，写代码更麻烦。对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑。对空表和非空表的处理需要用不同的代码逻辑

2.3.2 单链表的基本操作

1. 单链表的插入和删除

按位序插入（带头结点）

//在第i个位置插插入元素e (带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
		return false;
    LNode *p; 	//指针p指向当前扫描到的结点
    int j=0;     //当前p指向的是第几个结点
    p = L;	    //L指向头结点，头结点是第0个结点(不存数据)
    while (p!= NULL && j<i-1) { //循环找到第 i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL) 	//i值不合法
   		return false;
    LNode *s = (LNode *)malloc(sizeof (LNode));
    s->data = e;
    s->next=p->next;	//跟下一句有先后关系
	p->next=s;    //将结点s连到p之后
    return true;    //插入成功.
}

i = 1（插在表头）最好时间复杂度：O(1)

i = n （插在表尾）最坏时间复杂度：O(n)

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

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

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return  false;
    if(i==1){	//插入第1个结点的操作与其他结点操作不同
        LNode *s = (LNode *)malloc (sizeof(LNode));
        s->data = e;
        S->next=L ;
        L=s;        // 头指针指向新结点
        return true;
    }
    LNode *p;
    int j=1; //当前p指向的是第几个结点!
    p=L 	//p指问第1个结点(注意:不是头结点)
    //下面和带头节点逻辑一样
    while (p!= NULL && j<i-1) { //循环找到第 i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL) 	//i值不合法
   		return false;
    LNode *s = (LNode *)malloc(sizeof (LNode));
    s->data = e;
    s->next=p->next;	//跟下一句有先后关系
	p->next=s;    //将结点s连到p之后
    return true;    //插入成功.
}

指定结点的后插操作

相当于按位序插入中查找步骤完成

bool ListInsert(LNode *p,  ElemType e){
	if(p==NULL) 	//i值不合法
   		return false;
    LNode *s = (LNode *)malloc(sizeof (LNode));
    s->data = e;
    s->next=p->next;	//跟下一句有先后关系
	p->next=s;    //将结点s连到p之后
    return true;    //插入成功.
}

时间复杂度：O(1)

指定结点的前插操作

1.循环查找p的前驱q，再对q后插
时间复杂度：O(n)

2.数据替换法

//前插操作:在p结点之前插入元素e
bool InsertPriorNode (LNode *p, ElemType e){
    if (p==NULL)
    	return false;
    LNode *S = (LNode * )malloc(sizeof(LNode));
    if (s==NULL) //内存分配失败
    	return false;
    s->next= p->next ;
    p->next=s;    		//新结点s连到p之后
    s->data=p->data;    //将p中元素复制到s中
    p->data=e;		    //p中元素覆盖为e
    return true ;
}

时间复杂度：O(1)

按位序删除（带头结点）

ListDelete(&L,i,&e)：删除操作。删除表L中第==i个位置==的元素，并用e返回删除元素的值。

找到第 i-1 个结点，将其指针指向第i+1个结点，并释放第i个结点

bool ListDelete(LinkList &L，int i, ElemType &e){
    if(i<1)
	    return false;
    LNode *p; 	// 指针p指向当前扫描到的结点
    int j=0;    //当前p指向的是第几个结点
    p=L;    	//L指向头结点，头结点是第0个结点(不存数据)
    while (p!=NULL && j<i-1) { //循环找到第 i-1 个结点
        p=p->next;
        j++;
    }
    if( p==NULL)    //i值不合法
	    return false;
    if(p->next == NULL)    //第i-1个结点之后已无其他结点
	    return false;
    LNode *q=p->next;    	//令q指向被删除结点
    e = q->data;    		//用e返回元素的值
    p->next=q->next;	    //将*q结点从链中“断开”
    free(q);			    //释放结点的存储空间
    return true;		    //删除成功
}

i = 1（删除在表头）最好时间复杂度：O(1)

i = n （删除在表尾）最坏时间复杂度：O(n)

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

指定结点的删除**

找到其后继节点，将后继节点数据转到当前节点，删除后继节点

bool DeleteNode(LNode *p){
	if( p==NULL)    //i值不合法
	    return false;
     LNode *q=p->next;    	//令q指向*p的后继结点
    p->data = p->next->data;//和后继节点交换数据
    p->next = q->next;	    //将*q结点从链中“断开”
    free(q);			    //释放结点的存储空间
    return true;		    //删除成功
}

注意：

如果p是最后一个节点，则只能从表头开始依次寻找p的前驱，时间复杂度O(n)

2. 单链表的查找

按位查找

//按位查找，返回第i个元素(带头结点)
LNode * GetElem(LinkList L, int i){
    if(i<0)
    	return NULL;
    LNode *p; 	//指针p指向当前扫描到的结点
    int j=0;    //当前p指向的是第几个结点
    p=L;    	//L指向头结点，头结点是第0个结点(不存数据)
    while (p!=NULL && j<i) { //循环找到第 i个结点
        p=p- >next;
        j++;
    }
    return p;
}

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

按值查找

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

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

求表的长度

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

时间复杂度：O(n)

2.3.3 单链表的建立

1. 尾插法

尾插法建立单链表原理

//在第i个位置插插入元素e (带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
		return false;
    LNode *p; 	//指针p指向当 前扫描到的结点
    int j=0;     //当前p指向的是第几个结点
    p = L;	    //L指向头结点，头结点是第0个结点(不存数据)
    while (p!= NULL && j<i-1) { //循环找到第 i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL) 	//i值不合法
   		return false;
    LNode *s = (LNode *)malloc(sizeof (LNode));
    s->data = e;
    s->next=p->next;	//跟下一句有先后关系
	p->next=s;    //将结点s连到p之后
    return true;    //插入成功.
}

尾插法建立链表实现：

LinkList List_Taillinsert(LinkList &L){
	int x;	//设置Element的类型为整型
    L = (LinkList)malloc(sizeof(LNode))	//建立头节点，初始化空表 
    LNode *s,*r = L;	//r为表尾指针
    scanf("%d",&x); 	//输入节点值
    while(x!=9999){		//输入9999表示结束、
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;			//r指向新的尾表节点
        scanf("%d",&x);
    }
    r->next = NULL;		//尾指针置为空
    return L;
}

时间复杂度：O(n)

2. 头插法

头插法建立单链表原理

//后插操作:在p结点之后插入元素e
bool InsertNextNode (LNode *p，ElemType e){
    if (p==NULL)
    	return false;
    LNode *s = (LNode *)malloc (sizeof(LNode));
    if (s==NULL) 	//内存分配失败
    	return false;
    s->data = e;    //用结点s保存数据元素e
    s->next=p->next;
    p->next=s;    	//将结点s连到p之后
    return true;
}

每次都对头节点进行后插操作

头插法建立单链表实现：相当于每次新结点都是作为第一个结点

LinkList List_ HeadInsert(LinkList &L){ //逆向建立单链表
    LNode *s;
    int x; .
    L=(LinkList)malloc(sizeof(LNode)); 	// 创建头结点
    L->next=NULL;						//初始为空链表
    scanf("%d",&x);					    //输入结点的值
    while(x!=9999){					    //输入9999表示结束
        s=(LNode* )malloc(sizeof(LNode)); 	//创建新结点
        s->data=X;
        s->next=L-> next;
        L->next=S; 			    //将新结点插入表中，L为头指针
        scanf("%d" ,&x);
    }
    return L;
}

L->next=NULL;
不能去除，在尾插法中可以去掉，但是还是建议都加上

头插法建立单链的重要应用：==链表的逆置==

2.4 双链表

双链表和单链表的区别

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

相比于单链表，双链表访问前后相邻节点跟方便，同时其存储密度也更低一点

2.4.1 双链表的初始化

双链表的初始化（带头结点）

//初始化双链表
bool InitDLinkList(DLinklist &L){
    L = (DNode *) malloc(sizeof(DNode)); //分配-个头结点
    	if (L==NULL) 		//内存不足， 分配失败
    return false;
    L->prior = NULL;    //头结点的prior永远指向NULL
    L->next = NULL:    //头结点之后暂时还没有节点
    return true ;
}

//判断双链表是否为空(带头结点)
bool Empty(DLinklist L) {
if (L->next == NULL)
	return true;
else
	return false;
}

双链表的插入

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
    if(p=NULL || s=NULL) //非法参数
        return false;
    s->next=p->next;//将结点*s插入到结点*p之后
    if(p->next->prior!=NULL) //为了防止p是最后一个节点
	    p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

位序插入：先遍历，找到对应位序的前一个节点，进行后插操作（O(n)）

前插操作：找到对应节点的前一个节点，进行后插操作（O(1)）

2.3.2 双链表的删除

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if (p==NULL)
        return false;
    DNode *q = p->next; //找到p的后继结点q
    if (q==NULL)
        return false; 	//p没有后继
    p->next=q->next;
    if (q->next !=NULL) //q结点不是最后- 个结点
        q->next->prior=p;
    free(q);		    //释放结点空间
    return true;
}

//销毁链表
void DestoryList(DLinklist &L){
    //循环释放各个数据结点
    while (L->next != NULL)
        DeleteNextDNode(L); //上面定义的方法
    free(L); //释放头结点
    L=NULL; //头指针指向NULL
}

2.3.3 双链表的遍历

//后向遍历
while(p!=NULL){
    //....对节点p的相关操作
	p = p->next;
}

//前向遍历
while(p!=NULL){
    //....对节点p的相关操作
	p = p->prior;
}

//前向遍历（跳过头节点）
while(p->prior!=NULL){
    //....对节点p的相关操作
	p = p->prior;
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度O(n)

2.5 循环链表

2.5.1 循环单链表

typedef struct LNode{	//定义单链表结点类型
    ElemType data;		//每个节点存放-个数据元素
    struct LNode *next;	//指针指向下一个节点
}LNode, *LinkList;		//初始化一 个循环单链表

bool InitList(LinkList &L) {
    L = (LNode *) malloc(sizeof(LNode)); //分配-个头结点
    if (L==NULL)	 //内存不足，分配失败
        return false;
    L->next = L;	//头结点next指向头结点
    return true;
}

//判断循环单链表是否为空
bool Empty(LinkList L) {
    if (L->next ==L)
        return true;
    else
        return false;
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L，LNode *p){
    if (p->next==L)]
        return true ;
    else
        return false;
}

单链表：从一个结点出发只能找到后续的各个结点

循环单链表：从一个结点出发可以找到其他任何一个结点

常对链表的头部或尾部进行操作时，可以让L指向表尾元素(插入、删除时可能需要修改)，即用一个不带头结点且有尾指针的单循环链表

2.5.2 循环双链表

//初始化空的循环双链表
bool InitDLinkL ist (DLinklist &L){
    L = (DNode *) malloc(sizeof (DNode)); //分配-个头结点
    if (L==NULL) 	//内存不足，分配失败
        return false;
    L->prior = L;	//头结点的prior指向头结点（特性：prior指向尾节点）
    L->next = L;	//头结点的next 指向头结点
    return true;
}

//判断循环双链表是否为空
bool Emptv(DL inklist L){
    if(L->next ==L）
       return true;
     else
       return false;
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(DLinklist L, DNode *p){
    if
        (p->next==L)|
        return true;
    eLse
        return false;
}

循环双链表插入

//在p结点之后插入s结点
bool InsertNextDNode (DNode *p, DNode *s){
    s->next=p->next; //将结点*s插入到结点和之后
    p->next->prior=s; //普通双链表在此处需判断p是否尾节点
    s->prior=p;
    p->next=s;
}

循环双链表的删除

从删除p的后继结点q
p->next=q->next;
q->next->prior=p;	//普通双链表在此处需判断p是否尾节点
free(q);

2.6 静态链表

2.6.1 静态链表定义

单链表：各个结点在内存中星罗棋布、散落天涯。

静态链表：分配一整片连续的内存空间，各个结点集中安置。每个数据元素 4B，每个游标4B（每个结点共 8B）设起始地址为 addre

定义一个静态链表

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

void testSLinkL ist() {
    struct Node a[MaxSize]; //数组a作为静态链表
    //......后续代码
}

等价于：

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

void testSLinkList() {
    SLinkList a;
    //.....后续代码
}

在代码阅读感知方面：

//a是一个Node型数组
struct Node a[MaxSize]; //数组a作为静态链表

//a是一个静态链表
SLinkList a;

2.6.1 基本操作实现

初始化静态链表：把 a[0] 的 next 设为 -1 把其他结点的 next 设为一个特殊值用来表示结点空闲，如 -2
查找：从头结点出发挨个往后遍历结点（O(n)）
插入位序为 i 的结点：
1. 找到一个空的结点，存入数据元素
2. 从头结点出发找到位序为 i-1 的结点
3. 修改新结点的 next
4. 修改 i-1 号结点的 next
删除某个结点：
1. 从头结点出发找到前驱结点
2. 修改前驱结点的游标
3. 被删除结点 next 设为特殊值（如-2）

2.7 顺序表vs链表

特性	顺序表	链表
逻辑结构	线性结构	线性结构
存储结构	顺序存储	链式存储

存储结构：

顺序存储：

优点：支持随机存取、存储密度高

缺点：大片连续空间分配不方便，改变容量不方便

链式存储：

优点：离散的小空间分配方便，改变容量方便

缺点：不可随机存取，存储密度低

基本操作比较

创建

销毁

增、删

查找

基于基本操作，选取上的优先级

特性	顺序表	链表
弹性（可扩容）	✗	✔
增、删	✗	✔
查	✔	✗

表长难以预估、经常要增加/删除元素 ——链表

表长可预估、查询（搜索）操作较多 ——顺序表

3. 栈和队列

3.1 栈

3.1.1 栈的基本概念

栈的定义：线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表。若用L命名线性表，则其一般表示为

L = (a1, a2, … , ai, ai+1, … , an)

栈（Stack）是只允许在一端进行插入或删除操作的线性表

逻辑结构：与普通线性表相同

数据的运算：插入、删除操作有区别

栈顶：允许插入和删除的一端

栈底：不允许插入和删除的一端

特点：后进先出 Last In First Out （LIFO）

栈的基本操作

InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。

DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。

Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。

Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。

GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素

其他常用操作： StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false。

3.1.2 顺序栈的实现

顺序栈的定义

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

初始化操作

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

栈空判断：

//判断栈空
bool StackEmpty(SqStack S){
    if(S.top== -1)		//栈空
        return true;
    else				//不空
        false;
}

进栈操作

//新元素进栈
bool Push(SqStack &S , ElemType x){
    if(S.top=MaxSize-1){
        return false; //栈满
    }
    S.data[++S.top] = x; //先加再存
}

出栈操作

//出栈操作
bool Push(SqStack &S , ElemType x){
    if(S.top=-1){
        return false; //栈空
    }
    x = S.data[S.top--] ; //先存再减
}

读栈顶元素操作

//和出栈操作类似，但是指针不用移动
bool Push(SqStack &S , ElemType x){
    if(S.top=-1){
        return false; //栈空
    }
    x = S.data[S.top] ; //只存栈顶元素
}

另一种方式

初始时让指针指向0
void InitStack(SqStack &S){
	S.top= 0;	//初始化栈顶指针
}
则其进栈和出栈分别为：
//进栈
S.data[S.top++] = x; //先存再加
//出栈
x = S.data[--S.top] ; //先减再存
其判空和栈满判断：
//判空
S.top == 0
//栈满
S.top == MaxSize

3.1.3 共享栈

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

#define MaxSize 10	//定义栈中元素的最大个数
typedef struct{
    ElemType data [MaxSize];	//静态数组存放栈中元素
    int top0;	//0号栈顶指针
    int top1; 	//11号栈顶指针
} ShStack;

//初始化栈
void InitStack(ShStack &S){
    S.top0=-1;	//初始化栈顶指针
    S.top1=MaxSize; 
}

栈满条件
S.top0 + 1 == S.top1

3.1.4 链栈的实现

头插法建立单链表——对应：进栈

//后插操作:在p结点之后插入元素e
bool InsertNextNode (LNode *p，ElemType e){
    if (p==NULL)
    	return false;
    LNode *s = (LNode *)malloc (sizeof(LNode));
    if (s==NULL) 	//内存分配失败
    	return false;
    s->data = e;    //用结点s保存数据元素e
    s->next=p->next;
    p->next=s;    	//将结点s连到p之后
    return true;
}

链栈的定义

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

3.2 队列

3.2.1 队列的基本概念

队列（Queue）是只允许在一端进行插入，在另一端删除的线性表

特点：先进先出（FIFO）

队列的基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。

DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。

EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。

GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

其他常用操作： QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false

3.2.2 队列的顺序实现

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

1. 队尾指针指向队尾元素的后一个位置（下一个应该插入的位置）

队列初始化

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

队列判空

bool QueueEmpty ( SqQueue Q){
    if(Q.rear==Q.front)	//队空条件
        return true;
    else
        return false;
}

入队操作：只能从队尾入队（插入）

//入队
bool EnQueue(SqQueue &Q, ElemType x){
    if (队列已满)
        return false; 		//队满则报错
    Q.data[Q.rear]=x; 	//将x插入队尾
    Q.rear=(Q.rear+1)%MaxSize;	//队尾指针后移
    return true;
}

出队操作：只能让队头元素出队

//出队(删除一个队头元素， 并用x返回)
bool DeQueue (SqQueue &Q, ElemType &x){
    if(Q.rear==Q.front)	//判断队空
        return false; 	//队空则报错
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize
    return true;
}

获取队头元素

//获得队头元素的值，用x返回
bool GetHead (SqQueue Q, ElemType &x){
    if(Q. rear==Q.front)
        return false;    //队空则报错
    x=Q.data [Q.front] ;
   		return true ;
}

注意：队列已满的条件： rear==MaxSize ???

队列需要循环利用，当尾指针移到尾部时，前面若是有出队后留下的空位，尾指针需要重新移到前面，固有
Q. rear=(Q.rear+1)%MaxSize;	//队尾指针后移
尾指针移动后对MaxSize取模操作

队满的判断（3种情况）：

牺牲一个内存单元：即尾指针指向最后一个空内存单元时（下一个就是队头），则就认为此时队满
```
(Q.rear + 1)%MaxSize == Q.front
```
增加size变量记录队列长度
```
//初始化队列
void InitQueue (SqQueue &Q) {
    Q.rear=Q.front=0;
    int size; //队列当前长度
}
```
插入成功 size++；删除成功 size--;

队满条件： size==MaxSize

队空条件：size == 0
增加tag变量记录当前操作的类型
```
//初始化队列
void InitQueue (SqQueue &Q) {
    Q.rear=Q.front=0;
    int tag; //操作的类型 0是删除 1是插入
}
```
只有删除操作，才可能导致队空只有插入操作，才可能导致队满

队满条件： front==rear && tag == 1

队空条件： front==rear && tag == 0

队列元素个数

(rear+MaxSize-front)%MaxSize

2. 队尾指针指向队尾元素的位置（当前插入元素的位置）

入队操作

Q.rear=(Q.rear+1 )%MaxSize ; //先后移
Q.data[Q.rear]=x;			//再存入

因为上述入队操作是先移动再存入，所以初始化的时候可以让队尾指针指向队头的前一个内存单元即

font = 0 时 rear = n-1（n为队列长度）

队列判空

(Q.rear+1)%MaxSize==Q.front

队满判断（3种情况）：

牺牲一个内存单元：即尾指针指向最后一个空内存单元时（下一个就是队头），则就认为此时队满
```
(Q.rear + 2)%MaxSize == Q.front //此时尾指针指向当前插入元素，应该+2才能到头指针
```
增加size变量记录队列长度
```
//初始化队列
void InitQueue (SqQueue &Q) {
    Q.rear=Q.front=0;
    int size; //队列当前长度
}
```
插入成功 size++；删除成功 size--;

队满条件： size==MaxSize

队空条件：size == 0
增加tag变量记录当前操作的类型
```
//初始化队列
void InitQueue (SqQueue &Q) {
    Q.rear=Q.front=0;
    int tag; //操作的类型 0是删除 1是插入
}
```
只有删除操作，才可能导致队空只有插入操作，才可能导致队满

队满条件： front==rear && tag == 1

队空条件： front==rear && tag == 0

3.2.3 队列的链式实现

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

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

队列初始化

//初始化队列(带头结点)
void InitQueue(LinkQueue &Q) {
    //初始时 front、 rear都指向头结点
    Q.front=Q.rear=(LinkNode* )malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

//初始化队列(不带头结点)
void InitQueue(LinkQueue &Q) {
    //初始时 front、 rear都指向NULL
    Q.front=NULL;
    Q.rear=NULL;
}

队列判空

//判断队列是否为空（带头结点）
bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear) //if（Q.front->next == NULL）
        return true;
    else
        return false;
}

//判断队列是否为空（不带头结点）
bool IsEmpty(LinkQueue Q){
    if(Q.front== NULL) 
        return true;
    else
        return false;
}

入队

//新元素入队(带头结点)
void EnQueue(L inkQueue &Q, ElemType x){
    L inkNode *s= (LinkNode *)malloc(sizeof(LinkNode) )
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;		//新结点插入到rear之后
    Q.rear=s;			//修改表尾指针
}

//新元素入队(不带头结点)
void EnQueuelLinkQueue &Q, ElemType x){
    LinkNode *s=(LinkNode *)malloc( sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    //不带头结点的队列，第一个元素入队时需要特别处理
    if (Q.front == NULL){	//在空队列中插入第一个元素
        Q.front = s;		//修改队头队尾指针
        Q.rear=s;	
    } else {	
        Q.rear->next=s;	//新结点插入到rear结点之后
        Q.rear=s;			//修改rear指针
    }
}

出队

//队头元素出队(带头结点)
bool DeQueue (LinkQueue &Q, ElemType &x){
    if(Q.front==Q. rear)
        return false;//空队
    LinkNode *p=Q.front->next;
    x=p->data;				//用变量x返回队头元素
    Q.front->next=p->next; //修改头结点的 next指针
    if(Q.rear==p) 			//此次是最后-个结点出队
        Q.rear=Q.front;	//修改rear 指针
    free(p);//释放结点空间
    return true;
}

//队头元素出队(不带头结点)
bool DeQueue (LinkQueue &Q, ElemType &x){
    if(Q.front==Q. rear)
        return false;//空队
    LinkNode *p=Q.front;
    x=p->data;				//用变量x返回队头元素
    Q.front = p->next; //修改头结点的 next指针
    if(Q. rear==p) 	{	//此次是最后-个结点出队
        Q.front = NULL;
        Q.rear = NULL;	
    }		    
    free(p);//释放结点空间
    return true;
}

队满条件：链式存储一般不会队满，除非内存不足

3.2.4 双端队列

3.3 常见考点

3.3.1 栈的应用——括号匹配

(  (  ( (  )  )  ) )
① ② ③ ④ ④ ③ ② ①

最后出现的左括号最先被匹配（LIFO）

每出现一个右括号，就 “消耗”一个左括号——出栈

可用“栈” 实现该特性

3.3.2 栈的应用——表达式求值1

中缀、后缀、前缀表达式

中缀表达式：运算符在两个操作数中间，如 a + b - c * d

后缀表达式（逆波兰表达式）：运算符在两个操作数后面，如 a b + c d * -

前缀表达式（波兰表达式）：运算符在两个操作数前面，如- + a b * c d

中缀转后缀的手算方法：

确定中缀表达式中各个运算符的运算顺序
选择下一个运算符，按照「左操作数右操作数运算符」的方式组合成一个新的操作数
如果还有运算符没被处理，就继续 ②

确定中缀表达式中各个运算符的运算顺序时采用**“左优先”原则**：只要左边的运算符能先计算，就优先算左边的

A + B - C * D / E + F
  ①  ④   ②  ③  ⑤
A B + C D * E / - F +
   ①     ②  ③ ④  ⑤

后缀表达式的手算方法：从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数

注意：两个操作数的左右顺序

后缀表达式的计算（机算）

用栈实现后缀表达式的计算：

从左往右扫描下一个元素，直到处理完所有元素
若扫描到操作数则压入栈，并回到①；否则执行③
若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

注意：先出栈的是“右操作数”

若表达式合法，则最后栈中只会留下一个元素，就是最终结果

中缀表达式转前缀表达式（手算）

中缀转前缀的手算方法：

确定中缀表达式中各个运算符的运算顺序
选择下一个运算符，按照「运算符左操作数右操作数」的方式组合成一个新的操作数
如果还有运算符没被处理，就继续 ②

“右优先”原则：只要右边的运算符能先计算，就优先算右边

A + B * (C - D) – E / F
  ⑤  ③    ②   ④  ①
+ A - * B - C D / E F
⑤  ④ ③  ②    ①

前缀表达式的计算（机算）

用栈实现前缀表达式的计算：

右往左扫描下一个元素，直到处理完所有元素
若扫描到操作数则压入栈，并回到①；否则执行③
若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

注意：先出栈的是“左操作数”

3.3.3 栈的应用——表达式求值2

中缀表达式转后缀表达式（手算）

中缀转后缀的手算方法：

确定中缀表达式中各个运算符的运算顺序
选择下一个运算符，按照「左操作数右操作数运算符」的方式组合成一个新的操作数
如果还有运算符没被处理，就继续 ②

**“左优先”**原则：只要左边的运算符能先计算，就优先算左边的

A + B - C * D / E + F
  ①  ④   ②  ③  ⑤
A B + C D * E / - F +
   ①     ②  ③ ④  ⑤

中缀表达式转后缀表达式（机算）

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况：

遇到操作数。直接加入后缀表达式。
遇到界限符。遇到"(" 直接入栈；遇到")"则依次弹出栈内运算符并加入后缀表达式，直到弹出"(" 止。注意："("不加入后缀表达式。
遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到"("或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

中缀表达式的计算（用栈实现）

中缀转后缀 + 后缀表达式求值两个算法的结合

用栈实现中缀表达式的计算：

初始化两个栈，操作数栈和运算符栈
若扫描到操作数，压入操作数栈
若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

3.3.4 栈的应用 ——递归

函数调用的特点：最后被调用的函数最先执行结束（LIFO）

函数调用时，需要用一个栈存储： ① 调用返回地址 ② 实参 ③ 局部变量

递归调用时，函数调用栈可称为“递归工作栈” 每进入一层递归，就将递归调用所需信息压入栈顶每退出一层递归，就从栈顶弹出相应信息

缺点：太多层递归可能会导致栈溢出

3.3.5 队列的应用

队列应用——树的层次遍历

队列应用——图的广度优先遍历

队列在操作系统中的应用

多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service，先来先服务）是一种常用策略。

3.3.6 特殊矩阵压缩存储

M行N列的二维数组 b[M][N] 中，若按行优先存储，则 b[i][j] 的存储地址 = LOC + (i*N + j) * sizeof(ElemType)

M行N列的二维数组 b[M][N] 中，若按列优先存储，则 b[i][j] 的存储地址 = LOC + ( j*M+ i ) * sizeof(ElemType)

4. 串

4.1 串的定义和基本操作

串，即字符串（String）是由零个或多个字符组成的有限序列。

一般记为 S = ‘a1a2······an' （n ≥0）

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

子串：串中任意个连续的字符组成的子序列。 Eg：’iPhone’，’Pro M’ 是串T 的子串

主串：包含子串的串。 Eg：T 是子串’iPhone’的主串

字符在主串中的位置：字符在串中的序号。 Eg：’1’在T中的位置是8(第一次出现)

子串在主串中的位置：子串的第一个字符在主串中的位置。 Eg：’11 Pro’在 T 中的位置为8

注意：位序从1开始而不是从0开始

串是一种特殊的线性表，数据元素之间呈线性关系

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）串的基本操作，如增删改查等通常以子串为操作对象

假设有串T=“”，S=”iPhone 11 Pro Max?”，W=“Pro”

StrAssign(&T,chars)：赋值操作。把串T赋值为chars。

StrCopy(&T,S)：复制操作。由串S复制得到串T。

StrEmpty(S)：判空操作。若S为空串，则返回TRUE，否则返回FALSE。

StrLength(S)：求串长。返回串S的元素个数。

ClearString(&S)：清空操作。将S清为空串。

DestroyString(&S)：销毁串。将串S销毁（回收存储空间）。

Concat(&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串 SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串。

Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。

StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0

串的比较操作

StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回<0

从第一个字符开始往后依次对比，先出现更大字符的串就更大

长串的前缀与短串相同时，长串更大

只有两个串完全相同时，才相等

4.2 串的存储结构

串的顺序存储

//静态数组实现分配(定长顺序存储)
#define MAXLEN 255 	//预定义最大串长为255
typedef struct{
    char ch[MAXLEN];	//每个分量存储一个字符
    int length;		//串的实际长度
}SString;

typedef struct{
    char *ch;		//按串长分配存储区，ch指向串的基地址
    int length;		//串的长度
}HString;		//动态数组实现(堆分配存储)

HString S;	
S.ch = (char *) malloc (MAXLEN * sizeof(char));	//用完需要手动free
S. length = 0;

接下来对方案四进行讨论

StrAssign(&T,chars)：赋值操作。把串T赋值为chars。

StrCopy(&T,S)：复制操作。由串S复制得到串T。

StrEmpty(S)：判空操作。若S为空串，则返回TRUE，否则返回FALSE。

StrLength(S)：求串长。返回串S的元素个数。

ClearString(&S)：清空操作。将S清为空串。

DestroyString(&S)：销毁串。将串S销毁（回收存储空间）。

Concat(&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串

SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串。

//求子串
bool SubString(SString &Sub，SString S, int pos, int len){
    //子串范围越界
    if (pos+1en-1 > S.length)
        return false;
    for (int i=pos; i<pos+len; i++)
        Sub.ch[i-pos+1] = s.ch[i];
    Sub.length = Len;
    return true;
}

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

StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0

int StrCompare(SString S, SString T) {
    for (int i=1; i<=S.length && i<=T.length; i++){
        if (S.ch[i]!=T.ch[i] )
            return s.ch[i]-T.ch[i];
    }
    //扫描过的所有字符都相同，则长度长的串更
    return S.length-T.length; 
}

Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。

int Index(SString S, SString T){
    int i=1, n=StrLength(S)， m=StrLength(T);
    SString sub; 		//用于暂存子串
    while(i<=n-m+1){    //此条件后的长度小于m
        SubString(sub,S,i,m);
        if(StrCompare(sub，T)!=0) ++i;
        else return i; //返回子 串在主串中的位置
    }
    return 0; 	//S中不存在与T相等的子串.
}

定位子串操作，其实就是将取子串和字符比较结合在一起，对主串从第一个位置开始，取出与给定串相同长度的子串，进行比较

4.3 朴素模式匹配算法

什么是模式匹配

主串：S=‘wangdao’

子串：’wang’、’ang’、’ao’ ……

模式串：’gda’、’bao’

串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S 中第一次出现的位置；否则函数值为0。

与上面的串的定位是一样的

下面将不借助取字符和字符串比较这两个方法，直接使用两个指针实现朴素模式匹配算法

方法一：i是指向主串的指针，j是指向模式串的指针，两者都是从第一个位置开始

int Index(SString S,SString T){
    int k=1;	//用于将主串的指针移向下一个位置，和返回成功匹配的位序
    int i=k, j=1;
    while(i<=S.length && j<=T.length){
        if(s.ch[i]==T.ch[j]){
            ++i;
            ++j;	//继续比较后继字符
        } else{
            k++;	//检查下一个子串
            i=k;
            j=1;
        }
        if(j>T.length)
            return k;
        else
            return 0;
    }

方法二：下面的主串指针移动有所不同和成功匹配后返回位序不同（不借助变量k）

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;	//在匹配成功后，i，j会继续移动一个单位才跳出上述循环
    else
        return 0;
}

朴素模式匹配算法性能分析

若模式串长度为m，主串长度为n，则

匹配成功的最好时间复杂度：O(m)

匹配失败的最好时间复杂度：O(n-m+1) = O(n-m)≈O(n) [主串中有n-m+1个，每一次都在第一个字符就发现不匹配]

匹配成功/匹配失败最多需要 (n-m+1)*m 次比较，最坏时间复杂度：O((n-m+1)*m)≈O(nm) [一般情况下m<<n]

4.4 KMP算法

朴素模式匹配算法的缺点：当某些子串与模式串能部分匹配时，主串的扫描指针 i 经常回溯，导致时间开销增加

KMP算法就是在此基础上对已经确认好了的部分进行忽略，直接调整模式串的指针到正确位置（注：模式串回溯指针的位置由模式串本身和主串失配位置决定）

比如对模式串T=abaabc，主串S=abaabaaabc....来分析

当第6个元素匹配失败时，可令主串指针i不变，模式串指针j=3

当第5个元素匹配失败时，可令主串指针1不变，模式串指针j=2

当第4个元素匹配失败时，可令主串指针1不变，模式串指针j=2

当第3个元素匹配失败时，可令主串指针i不变，模式串指针j=1

当第2个元素匹配失败时，可令主串指针i不变，模式串指针j=1

当第1个元素匹配失败时，模式串指针j=0，i++，j++

可用一个next数组来存取这两者（模式串指针回溯的位置和主串失配位置）间的关系）

注：next数组只和模式串有关，和主串无关

根据模式串T，求出next数组——>利用next数组进行匹配(主串指针不回溯)

//KMP算法模式匹配
int Index_JKMP(SString S, SString T,int next[]){
    int i=1, j=1;
    while(i<=S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){
            ++i;
            ++j;	//继续比较后继字符
        }
        else
            j=next[j];		//模式串向右移动
    }
    if(j>T.length)
        return i-T.length;		//匹配成功
    else
        return 0; 
}

朴素模式匹配算法，最坏时间复杂度0(mn)

KMP算法，最坏时间复杂度0(m+n) （next数组时间复杂度0(m) + 模式匹配过程最坏时间复杂度0(n)）

4.4.1 求next数组

next[1]都无脑写0
next[2]都无脑写1
其他next:在不匹配的位置前，划一根美丽的分界线，模式串-步一步往后退，直到分界线之前“能对上”，或模式串完全跨过分界线为止。此时i指向哪儿，next数组值就是多少

eg：

此时串T往后移，到线后依旧没找到，故 j=1 即next[j] = 1

此时串T往后移，可以对应，故 j=2 即next[j] = 2

此时串T往后移，可以对应，故 j=3 即next[j] = 2

看竖线前要对应，竖线后的第一个元素对应在串中的位置即为 j 指针的回溯位置，即next[j] 的值

4.4.2 KMP算法的优化

模式串中存在相同字符，采用之前的next数组可能导致多做无意义的匹配，比如上述例子中，主串S的3处失配，则把 j=1 但是 j = 1 时模式串的字符还是a，一定会失配，使用可以进行优化

对KMP算法的优化即对 next[j] 数组的优化，优化为nextval[j]

优化后对KMP算法的逻辑代码不会改变，只是将next[j]换为nextval[j]

//KMP算法模式匹配
int Index_JKMP(SString S, SString T,int nextval[]){
    int i=1, j=1;
    while(i<=S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){
            ++i;
            ++j;	//继续比较后继字符
        }
        else
            j=nextval[j];		//模式串向右移动
    }
    if(j>T. length)
        return i-T.length;		//匹配成功
    else
        return 0; 
}

对于next数组的优化：

先求出next[j]
nextval[1]默认写0
序号大于2时，先看对应序号的next[j]，比如 j=2 的next[j]为1，然后找模式串中 j=1 的字符（a），比较其（a）和 j =2 时模式串中对应的字符（b），相等则将 j=2 的nextval[2]改为 j=1 的nextval[1]，即为0，不等则nextval[2]等于next[2]

序号j	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4
nextval[j]	0	1	0	1	0	4

//next数组转nextval数组的代码实现
nextval[1]=0;
for (int j=2; j<=T.length; j++) {
    if(T.ch[next[j]]==T.ch[j] )
        nextval[j] =nextval[next [j ] ] ;
    else
        nextval[j]=next[ j ] ;
}

5.树与二叉树

5.1 树

5.1.1 定义和基本术语

空树——结点数为0的树

非空树的特性：

有且仅有一个根节点
没有后继的结点称为“叶子结点”（或终端结点）
有后继的结点称为“分支结点”（或非终端结点）
除了根节点外，任何一个结点都有且仅有一个前驱
每个结点可以有0个或多个后继

树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

1）有且仅有一个特定的称为根的结点。

2）当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

属性：

结点的层次（深度）——从上往下数

结点的高度——从下往上数

树的高度（深度）——总共多少层

结点的度——有几个孩子（分支）

树的度——各结点的度的最大值

路径（从上向下）和路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。

有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

森林：森林是m（m≥0）棵互不相交的树的集合

5.1.2 树的性质

度为m的树	m叉树
任意结点的度 ≤ m（最多m个孩子）	任意结点的度 ≤ m（最多m个孩子）
至少有一个结点度 = m（有m个孩子）	允许所有结点的度都＜ m
一定是非空树，少有m+1个结点	可以是空树

度为m的树第 i 层至多有 m^i-1^ 个结点（i≥1）

m叉树第 i 层至多有 m^i-1^ 个结点（i≥1）

具有如下最基本的性质：
1）树中的结点数等于所有结点的度数之和加1。
2）度为m的树中第i层上至多有 m^(i-1)^ 个结点（i≥1）。
3）高度为h的m叉树至多有 (m^h^-1)/(m-1) 个结点。（等比数列求和）
4）具有n个结点的m叉树的最小高度为 $\lceil log~m~(n(m-1)+1) \rceil$ 。

**结点个数 n 与边数e 满足关系：n = e+1 ** 分支边数又节点引出，1度节点引出1条边，2度节点引入2条边，0度节点引出0条边，那么总的边数 e 可以表达为： e = 0× n0 +1× n1 +2×n2 = n1 +2n2

$\lceil x \rceil$ 表示向上取整

$\lfloor x \rfloor$ 表示向下取整

eg:

【2010统考真题】在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是

设树中度为i（i=0,1,2,3,4）的结点数分别为m：树中结点总数为n，则n分支数+1，而分支数又等于树中各结点的之和，即n=1+n1+2n2+3n3+4n4=n0+n1+n2+n3+n4依题意，n1+2n2+3n3+4n4=10+2+30+80=122，n0+n1+n2+n3+n4=10+1+10+20=41，可得出n0=82，即树T的叶结点的个数是82。

注意：综合以上几题，常用于求解树结点与度之间关系的有：

①总结点数=n0+n1+n2+n3+....+nm

②总分支数=1n1+2n2+3n3+4n4+....+mnm（度为m的结点引出m条分支）

⑧总结点数=总分支数+1。

5.2 二叉树

5.2.1 二叉树的基本概念

二叉树是n（n≥0）个结点的有限集合：

① 或者为空二叉树，即n = 0。

② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

特点：①每个结点至多只有两棵子树 ②左右子树不能颠倒（二叉树是有序树）

注意区别：度为2的有序树

几个特殊的二叉树：

满二叉树。一棵高度为h，且含有2^h^ - 1个结点的二叉树

特点：

①只有最后一层有叶子结点

②不存在度为 1 的结点

③按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为 $\lfloor i/2 \rfloor$ （如果有的话）

完全二叉树。当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树

特点：

①只有最后两层可能有叶子结点

②最多只有一个度为1的结点，且该节点只有左孩子没有右孩子

③按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为 $\lfloor i/2 \rfloor$ （如果有的话）

④ i≤ $\lfloor i/2 \rfloor$ 为分支结点， i> $\lfloor i/2 \rfloor$ 为叶子结点

⑤总结数为n，n为奇数，每个分支节点都有左孩子和右孩子；n为偶数，从n/2 开始，其后节点均为叶节点

二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

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

二叉排序树可用于元素的排序、搜索

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

平衡二叉树能有更高的搜索效率

5.2.2 二叉树的性质

常见考点1：

设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则 n0 = n2 + 1 （叶子结点比二分支结点多一个）

假设树中结点总数为 n，则

① n = n0 + n1 + n2

② n = n1 + 2n2+1 （树的结点数=总度数+1）

$\Longrightarrow$ n0 = n2 + 1

常见考点2：

二叉树第 i 层至多有 2^i-1^ 个结点（i≥1），树最多有（满二叉树）2^i^-1个结点

m叉树第 i 层至多有 m^i-1^个结点（i≥1），树最多有(m^i^-1)/(m-1)

此时的 i 层相当于高度 h

常见考点3：

高度为h的二叉树至多有 2^ℎ^ − 1个结点（满二叉树）

高度为h的m叉树至多有 (m^h^-1)/(m-1) 个结点

等比数列求和公式：a + aq + aq^2^ + ……+aq^n-1^ = a(1-q^n^)/1-q

完全二叉树的常考性质

常见考点1：

具有n个（n > 0）结点的完全二叉树的高度h为 $\lceil log~2~(n+1) \rceil$ 或 $\lfloor log~2~n \rfloor$ +1

证明：

常见考点2：

对于完全二叉树，可以由的结点数 n 推出度为0、1和2的结点个数为n0、n1和n2

完全二叉树最多只有一个度为1的结点，即 n1=0或1

n0 = n2 + 1 $\Rightarrow$ n0 + n2 一定是奇数

若完全二叉树有2k个（偶数）个结点，则必有 n1=1， n0 = k， n2 = k-1

若完全二叉树有2k-1个（奇数）个结点，则必有 n1=0， n0 = k， n2 = k-1

5.2.3 二叉树的存储结构

顺序存储

#define MaxSize 100
struct TreeNode {
    ElemType value; //结点中的数据元素
    bool isEmpty;	//结点是否为空
};
TreeNode t [MaxSize] ;
//定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点
//初始化时所有结点标记为空
for (int i=0; i<MaxSize; i++){
t[i].isEmpty=true;
}

几个重要常考的基本操作：

i 的左孩子：2i

i 的右孩子：2i+1

i 的父节点： $\lfloor i/2 \rfloor$

i 所在的层次： $\lceil log~2~(n+1) \rceil$ 或 $\lfloor log~2~n \rfloor$ +1

若完全二叉树中共有n个结点，则

判断 i 是否有左孩子？ 2i ≤ n

判断 i 是否有右孩子？ 2i+1 ≤ n

判断 i 是否是叶子/分支结点？i > $\lfloor n/2 \rfloor$ ?

如果不是完全二叉树，依然按层序将各节点顺序存储，那么…将无法从结点编号反映出结点间的逻辑关系

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来

最坏情况：高度为 h 且只有 h 个结点的单支树（所有结点只有右孩子），也至少需要 2h-1 个存储单元

结论：二叉树的顺序存储结构，只适合存储完全二叉树

链式存储

//二叉树的结点(链式存储)
typedef struct BiTNode{
EtemType data;		//数据域
struct BiTNode *lchild,*rchild;	//左、右孩子指针
}BiTNode ,*BiTree;

n个结点的二叉链表共有 n+1 个空链域——可以用于构造线索二叉树

struct ElemType{
    int value;
};

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild , *rchild;
}BiTNode ,*BiTree;

//定义一棵空树
BiTree root = NULL ;

//插入根节点
root = (BiTree) malloc(sizeof (BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;

//插入新结点
BiTNode * p = (BiTNode *) malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;	//作为根节点的左孩子

//三叉链表——方便找父结点
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild , *rchild;
    struct BiTNode *parent;
}BiTNode ,*BiTree;

5.3 二叉树的遍历

5.3.1 二叉树的深度优先遍历（DFS）【先/中/后序遍历】

二叉树的递归特性：

①要么是个空二叉树

②要么就是由“根节点+左子树+右子树”组成的二叉树

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild , *rchild;
}BiTNode ,*BiTree;

先序遍历（PreOrder）的操作过程如下：

若二叉树为空，则什么也不做；
若二叉树非空：
1. 访问根结点；
2. 先序遍历左子树；
3. 先序遍历右子树。

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

中序遍历（InOrder）的操作过程如下：

若二叉树为空，则什么也不做；
若二叉树非空：
1. 先序遍历左子树；
2. 访问根结点；
3. 先序遍历右子树。

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

后序遍历（PostOrder）的操作过程如下：

若二叉树为空，则什么也不做；
若二叉树非空：
1. 先序遍历左子树；
2. 先序遍历右子树。
3. 访问根结点；

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

空间复杂度： O(h)

求遍历序列，路线法：

eg：求树的深度（应用）

int treeDepth(BiTree T){
    if (T == NULL) {
        return 0;
    }
    else {
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        //树的深度=Max (左子树深度,右子树深度)+1
        return l>r ? l+1 : r+1;
    }
}

5.3.2 二叉树的广度优先遍历（BFS）【层次遍历】

算法思想：

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

代码实现

//二叉树的结点(链式存储)
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild, *rchild;
}BiTNode ,*BiTree;	

//链式队列结点
typedef struct LinkNode{
    BiTNode * data;	//存指针而不是结点
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *f ront,*rear; //队头队尾
}LinkQueue;

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

结论：一个层序遍历序列可能对应多种二叉树形态

5.3.3 由遍历序列构造二叉树

结论：前序、后序、层序的两两组合无法唯一确定一棵二叉树

只有和中序结合，才能确定唯一的一棵二叉树

5.3.4 线索二叉树

指向前驱、后继的指针称为“线索”

//二叉树的结点(链式存储)  术语: 二叉链表
typedef struct BiTNode{ 
    ElemType data;
    struct BiTNode *Lchild,*rchild;
}BiTNode, *BiTree;

//线索二叉树结点   术语：线索链表
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode * lchild, *rchild;
    int ltag,rtag; //左、 右线索标志
}ThreadNode ,*ThreadTree;

5.3.5 二叉树的线索化

用土办法找到中序前驱

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

//访问结点q
void visit (BiTNode * q){
    if (q==p)		//从当前访问结点刚好是结点p 
        final = pre;	//找到p的前驱
    else
        pre = q;		//pre指向当前访问的结点
}

//辅助全局变量，用于查找结点p的前驱
BiTNode *p;		//p指向目标结点
BiTNode * pre=NULL;	//指向当前访问结点的前驱
BiTNode * final=NULL; //用于记录最终结果

二叉树线索化

//线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode * lchild, *rchild;
    int ltag, rtag;	//左、右线索标志
}ThreadNode ,* ThreadTree ;

初步建成的树， ltag、rtag=0 ——这一步是在建立树的时候完成的

中序线索化（写法一）

//中序遍历土叉树，一边遍历一边线索化
void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);	//中序遍历左子树
        visit(T);	//访问根节点
        InThread(T->rchild); //中序遍历右子树
    }
}

void visit(ThreadNode *q) {
    if(q->lchild==NULL){//左子树为空,建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q; //建立前驱结 点的后继线索
        pre->rtag=1;
    }
    pre=q;     //标记当前节点为刚刚访问过的节点
}

//全局变量，pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;

//中序线索化二叉树T
void CreateInThread(ThreadTree T){
    pre=NULL;	//pre初始为NULL
    if(T!=NULL){	//非空二叉树才能线索化
        InThread(T);	//中序线索化二叉树
        if (pre->rchild==NULL)
            pre->rtag=1;	//处理遍历的最后一个结点
    }
}

上述代码注意要处理最后一个节点的右孩子

中序线索化（写法二）

void InThread(ThreadTree p,ThreadTree &pre){
    InThread(T->lchild);
    //下面的相当于写法一的visit
	if(q->lchild==NULL){//左子树为空,建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q; //建立前驱结 点的后继线索
        pre->rtag=1;
    }
    
    pre=q;
    InThread(p->rchild,pre)
}

//中序线索化二叉树T
void CreateInThread (ThreadTree T){
    ThreadTree pre=NULL;  //与一的区别，此处为局域变量
    if(T!=NULL){	//非空二叉树，线索化
        InThread(T,pre);	//线索化二叉树
        pre->rchild=NULL;		//处理遍历的最后一个结点，此处可以不做判断
        pre->rtag=1;
    }
}

先序线索化（写法一）

//先序遍历土叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
    if(T!=NULL){
        visit(T);	//访问根节点
        if(T->ltag==0) // !lchild不是前驱线索
            PreThread(T->lchild);	//中序遍历左子树
        PreThread(T->rchild); //中序遍历右子树
    }
}

void visit(ThreadNode *q) {
    if(q->lchild==NULL){//左子树为空,建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q; //建立前驱结 点的后继线索
        pre->rtag=1;
    }
    pre=q;
}

//全局变量，pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;

//中序线索化二叉树T
void CreateInThread(ThreadTree T){
    pre=NULL;	//pre初始为NULL
    if(T!=NULL){	//非空二叉树才能线索化
        PreThread(T);	//中序线索化二叉树
        if (pre->rchild= =NULL)
            pre->rtag=1;	//处理遍历的最后一个结点
    }
}

先序线索化（写法二）

void PreThread(ThreadTree p,ThreadTree &pre){
    
    //下面的相当于写法一的visit
	if(q->lchild==NULL){//左子树为空,建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q; //建立前驱结 点的后继线索
        pre->rtag=1;
    }
    if(T->ltag==0)   //!lchild不是前驱线索
	    InThread(T->lchild);
    InThread(p->rchild,pre)
    pre=q;
}

//中序线索化二叉树T
void CreateInThread (ThreadTree T){
    ThreadTree pre=NULL;  //与一的区别，此处为局域变量
    if(T!=NULL){	//非空二叉树，线索化
        PreThread(T,pre);	//线索化二叉树
        if (pre->rchild= =NULL)
            pre->rtag=1;	//处理遍历的最后一个结点
    }
}

注意：前序遍历，需要对遍历左子树时进行判断处理，因为如果左子树为空时，先visit操作会把其左指针改为线索指针（即指向其父节点），这时再直接遍历会出错，通过ltag判断其是否为线索指针

后序线索化：同中序线索化，无特殊要求，只需要将顺序改一下即可

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

中序线索二叉树找中序后继

//找到以P为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode (ThreadNode *p){
    //循环找到最左下结点(不一定是叶结点)
    while(p->ltag==0) p=p->lchild;
    return p; .
}

//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){	//右子树中最左下结点
    if(p->rtag==0) 
        return Firstnode(p->rchild) ;
    else 
        return p->rchild; //rtag==1直接返回后继线索
}

//对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)
void Inorder(ThreadNode *T){	//空间复杂度0(1)
    //不断寻找后继，达到遍历效果
    for (ThreadNode *p=Firstnode(T);p!=NULL; p=Nextnode(p))
        visit(p);
}

中序线索二叉树找中序前驱

//找到以P为根的子树中，最后个被中序遍历的结点
ThreadNode *Lastnode (ThreadNode *p){
    //循环找到最右下结点(不一定是叶结点)
    while(p->rtag==0) p=p->rchild;
    return p; .
}

//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){	//右子树中最左下结点
    if(p->ltag==0) 
        return Lastnode(p->lchild) ;
    else 
        return p->lchild; //rtag==1直接返回前驱线索
}

//对中序线索二叉树进行逆向中序遍历(利用线索实现的非递归算法)
void RevInorder(ThreadNode *T){	//空间复杂度0(1)
    for (ThreadNode *p=Lastnode(T);p!=NULL; p=Prenode(p))
        visit(p);
}

先序线索二叉树找先序后继

//在先序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){	//右子树中最左下结点
    if(p->rtag==0)  //此时要分两种情况：是否有左孩子
        if(p->ltag==0)
	        return p->lchild ;
    	else
            return p->rchild ;
    else 	//rtaag=1代表左后孩子都没有，都线索化了，那么其后继就是右线索
        return p->rchild; //rtag==1直接返回后继线索
}

先序线索二叉树找先序前驱（三叉链表）

//三叉链表
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode * lchild, *rchild;
    struct ThreadNode *parent;
    int ltag,rtag; //左、 右线索标志
}ThreadNode ,*ThreadTree;

//找到以P为根的子树中，最后个被先序遍历的结点
ThreadNode *Lastnode (ThreadNode *p){
    //循环找到最右下结点(不一定是叶结点)
    while(p->ltag==0 || p->rtag==0){
        while(p->rtag==0){
            p=p->rchild;
        } 
        if(p->ltag==0){ //上面循环出来满足 p->rtag==1  
            p=p->lchild;	
        }    
    }
    //if(p->rtag==1 && p->ltag==1)从上述循环出来就已经满足了这个条件了
    return p;
}

//找到以P为孩子的子树中，其前驱
ThreadNode *Parentnode (ThreadNode *p){
    //p为左节点 或 p为右节点且没有其父节点左节点
    if(p->parent!=null){
        if(p->parent->lchild==p)
            return p->parent;
        else if(p->parent->ltag==1 && p->parent->rchild==p)
            return p->parent;
        else if(p->parent->ltag==0 && p->parent->rchild==p){
            Lastnode(p->parent->lchild)
        }    
    }else{
       return null; 
    }   
}

//在先序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){	//右子树中最左下结点
    if(p->ltag==0) 
        return Parentnode(p) ;
    else 
        return p->lchild; //ltag==1直接返回前驱线索
}

后序线索二叉树找后序后继（三叉链表）

//三叉链表
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode * lchild, *rchild;
    struct ThreadNode *parent;
    int ltag,rtag; //左、 右线索标志
}ThreadNode ,*ThreadTree;

//找到以P为根的子树中，第一个被后序遍历的结点
ThreadNode *Lastnode (ThreadNode *p){
    //循环找到最左下结点(不一定是叶结点)
    while(p->ltag==0 || p->rtag==0){
        //有左孩子就一直向左，没有就检查右孩子，同时没有才能算找到
        while(p->ltag==0){
            p=p->lchild;
        } 
        if(p->rtag==0){ //上面循环出来满足 p->rtag==1  
            p=p->rchild;	
        }    
    }
    //if(p->rtag==1 && p->ltag==1)从上述循环出来就已经满足了这个条件了
    return p;
}

//找到以P为孩子的子树中，其后继
ThreadNode *Parentnode (ThreadNode *p){
    //p为左节点 或 p为右节点且没有其父节点左节点
    if(p->parent!=null){
        if(p->parent->rchild==p)
            return p->parent;
        else if(p->parent->rtag==1 && p->parent->lchild==p)
            return p->parent;
        else if(p->parent->rtag==0 && p->parent->lchild==p){
            Lastnode(p->parent->rchild)
        }    
    }else{
       return null; 
    }   
}

//在后序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){	
    if(p->rtag==0) 
        return Parentnode(p) ;
    else 
        return p->rchild; //rtag==1直接返回后继线索
}

后序线索二叉树找后序前驱

//在后序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){	//右子树中最左下结点
    if(p->ltag==0)  //此时要分两种情况：是否有左孩子
        if(p->rtag==0)
	        return p->rchild ;
    	else
            return p->lchild ;
    else 	//rtaag=1代表左后孩子都没有，都线索化了，那么其后继就是右线索
        return p->lchild; //rtag==1直接返回后继线索
}

5.4 树和森林

5.4.1 树的存储结构

树的逻辑结构

树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

1）有且仅有一个特定的称为根的结点。

2）当n > 1时，其余结点可分为m（m > 0）个==互不相交的有限集合==T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

树是一种递归定义的数据结构

双亲表示法（顺序存储）

//双亲表示法：每个结点中保存指向双亲的“指针”
#define MAX_ TREE_ SIZE 100		//树中最多结点数
typedef struct{		//树的结点定义
    ElemType data;		//数据元素
    int parent;			//双亲位置域
}PTNode; 

typedef struct{		//树的类型定义
    PTNode nodes [MAX_ TREE_ SIZE] ;	//双亲表示
    int n;		//结点数
}PTree;

新增数据元素，无需按逻辑上的次序存储

删除节点：

方案一：将parent指针改为-1（空数据导致遍历更慢）

方案二：将后面节点全部往前移

优点：查指定结点的双亲很方便

缺点：查指定结点的孩子只能从头遍历

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

//孩子表示法：顺序存储各个节点，每个结点中保存孩子链表头指针
struct CTNode {
    int child; //孩子结点在数组中的位置
    struct CTNode *next; //下一个孩子
};
typedef struct {
    ElemType data;
    struct CTNode *firstChild; //第一 个孩子
} CTBox;
typedef struct {
    CTBox nodes [MAX_TREE_SIZE] ;
    int n, r; //结点数和根的位置
} CTree;

孩子兄弟表示法（链式存储）

//树的存储一-孩子 兄弟表示法
typedef struct CSNode{
    ElemType data; //数据域
    struct CSNode *firstchild, *nextsibling; //第一个孩子和右兄弟指针
}CSNode, *CSTree;

对于有n个结点的树，其含有m个终端结点（叶结点），则其转化为对应的二叉树后，二叉树中无右孩子的结点（右指针域为空）数为：n-m+1 （非终端结点数加1）

将森林转F化为对应的二叉树T，森林F中的叶结点个数为二叉树T中不含左孩（左孩子指针为空）的结点个数

5.4.2 树、森林的遍历

树的先根遍历

树的后根遍历

森林的先序遍历

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

5.5 二叉排序（查找）树（BST）

5.5.1 二叉排序树的定义

二叉排序树，又称二叉查找树（BST，Binary Search Tree）一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

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

左子树结点值 < 根结点值 < 右子树结点值

进行中序遍历，可以得到一个递增的有序序列

5.5.2 二叉排序树的查找

左子树结点值 < 根结点值 < 右子树结点值

若树非空，目标值与根结点的值比较：

若相等，则查找成功；

若小于根结点，则在左子树上查找，否则在右子树上查找。

查找成功，返回结点指针；查找失败返回NULL

//二叉排序树结点
typedef struct BSTNode{
    int key;
    struct BSTNode *Lchild, *rchild;
}BSTNode , *BSTree;

//在二叉排序树中查找值为key, 的结点
//最坏空间复杂度0(1)
BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL&key!=T->key){ 	//若树空或等 于根结点值，则结束循环
        if(key < T->key)
            T=T->lchild; 	//小于， 则在左子树上查找
        else 
            T=T->rchild;	//大于，则在右子树.上查找
    }
    return T;
}

//在二叉排序树中查找值为key 的结点(递归实现)
//最坏空间复杂度0(h)
    BSTNode *BSTSearch(BSTree T,int key){
    if (T==NULL)
        return NULL;    //查找失败
    if (key==T->key)
        return T;    //查找成功
    else if (key < T->key)
        return BSTSearch(T->lchild, key); //在左子树中找
    else
        return BSTSearch(T->rchild, Key); //在右子树中找
}

5.5.3 二叉排序树的插入

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

//在二叉排序树插入关键字为k的新结点(递归实现).
//最坏空间复杂度0(h)
//新插入的结点一定是叶子
int BST_ Insert(BSTree &T, int k){
    if(T==NULL){ //原树为空, 新插入的结点为根结点
        T=(BSTree)malloc(sizeof(BSTNode));
        T->key=k; 
        T->lchild=T->rchild=NULL;
        return 1;	//返回1,插入成功
    }
    else if(k==T->key)	//树中存在相同关键字的结点，插入失败:
        return 0;
    else if(k<T->key)	//插入到T的左子树
        return, BST_ Insert(T->lchild,k);
    else	//插入到T的右子树
        return
        BST_Insert(T->rchild,k);
}

5.5.4 二叉排序树的构造

例1：按照序列str={50, 66, 60, 26, 21, 30, 70, 68}建立BST

例2：按照序列str={50, 26, 21, 30, 66, 60, 70, 68}建立BST

不同的关键字序列可能得到同款二叉排序树，也可能得到不同款二叉排序树

//按照str[] 中的关键字序列建立二叉排序树
void Creat_ _BST(BSTree &T,int str[] , intn){
    T=NULL ;
    //初始时T为空树 ( 
    int i=0;
    while(i<n){
        //依次将每个关键字插入到二叉排序树中
        BST_ Insert(T,str[i]);
        i++;
    }
}

5.5.5 二叉排序树的删除

先搜索找到目标结点：

① 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。

② 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。

③ 若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

中序遍历——左根右

左根 (左根右)

左根 ((左根右) 根右)

z的后继：z的右子树中最左下结点（该节点一定没有左子树）

）中序遍历——左根右

(左根右) 根右

(左根 (左根右) ) 根右

z的前驱：z的左子树中最右下结点（该节点一定没有右子树）

5.5.6 查找效率分析

5.6 平衡二叉树(AVL)

5.6.1 平衡二叉树的定义

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）——树上任一结点的左子树和右子树的高度之差不超过1。结点的平衡因子=左子树高-右子树高。

//平衡二叉树结点
typedef struct AVLNode{
    int key;    //数据域
    int balance;    //平衡因子
    struct AVLNode *lchild,*rchild;
}AVLNode, *AVLTree;

5.6.2 平衡二叉树的插入

每次调整的对象都是**“最小不平衡子树”**

5.6.3 平衡二叉树的删除

平衡二叉树的删除操作:

删除结点后，要保持二叉排序树的特性不变(左<中<右 )
若删除结点导致不平衡，则需要调整平衡

平衡二叉树的删除操作具体步骤:

①删除结点(方法同“二叉排序树”)

●若删除的结点是叶子，直接删。
 ●若删除的结点只有一个子树，用子树顶替删除位置
 ●若删除的结点有两棵子树，用前驱(或后继)结点顶替，并转换为对前驱(或后继)结点的删除。

②一路向北找到最小不平衡子树，找不到就完结撒花

③找最小不平衡子树下，“个头” 最高的儿子、孙子

④根据孙子的位置，调整平衡(LL/RR/LR/RL )

●孙子在LL:儿子右单旋
 ●孙子在RR:儿子左单旋
 ●孙子在LR:孙子先左旋，再右旋
 ●孙子在RL:孙子先右旋，再左旋

⑤如果不平衡向上传导，继续②

●对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡(不平衡向上传递)

平衡二叉树删除操作时间复杂度=O(log2n)

5.6.4 调整最小不平衡子树

5.7 红黑树（RBT）

平衡二叉树AVL:插入/删除很容易破坏“平衡”特性，需要频繁调整树的形态。如:插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树(时间开销大)，再进行LL/RR/LR/RL调整
红黑树RBT:插入/删除很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成

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

5.7.1 红黑树的定义

红黑树是二叉排序树 $\longrightarrow$ 左子树结点值≤根结点值≤右子树结点值
与普通BST相比，有什么要求：

每个结点或是红色，或是黑色的
根节点是黑色的
叶结点( 外部结点、NULL结点、失败结点)均是黑色的
不存在两个相邻的红结点(即红结点的父节点和孩子结点均是黑色)
对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

struct RBnode{
    int key;
    RBnode *parent;
    RBnode *lChild;
    RBnode *rChild;
    int color;	//节点颜色，如0/1表示 黑/红，也可用枚举型enum表示颜色
}

左根右，根叶黑，不红红，路黑同

补充概念：节点的“黑高”

结点的黑高bh——从某结点出发(不含该结点)到一空叶结点的路径上黑结点总数

根节点黑高为h的红黑树，内部节点数（关键字）至少有多少个？

内部节点数最少的情况——总共h层黑节点的满树形态

结论：若根结点黑高为h，内部根结点数（关键字）最少有2^h^-1个

5.7.2 红黑树的性质

性质1:从根节点到叶结点的最长路径不大于最短路径的2倍 $\longrightarrow$ 任一节点左子树和右子树高度之差不超过两倍

性质2:有n个内部节点的红黑树高度h ≤ 2log2(n+ 1) $\longrightarrow$ 红黑树查找操作时间复杂度= O(log2n)

性质1证明：任何一.条查找失败路径上黑结点数量都相同，而路径上不能连续出现两个红结点，即红结点只能穿插在各个黑结点中间

性质2证明：若红黑树总高度h，则根黑高≥h/2，因此内部结点树 n ≥ 2^h/2^-1，由此推出h ≤ 2log2(n+1)

查找效率与AVL树同等数量级

5.7.3 红黑树的插入

非根节点的插入只需要检测是否违反“不红红”

演示网站：Red/Black Tree Visualization (usfca.edu)

5.7.4 红黑树的删除（基本不考）

重要考点:
①红黑树删除操作的时间复杂度=O(log2n)
②在红黑树中删除结点的处理方式和“二叉排序树的删除”一样
③按②删除结点后，可能破坏“红黑树特性”，此时需要调整结点颜色、位置，使其再次满
足“红黑树特性。

5.8 B树

5.8.1 B树的定义

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

树中每个结点至多有m棵子树，即至多含有m-1个关键空。
若根结点还是终端结杰、则至少有两棵子树。
除根结点外的所有非叶结点至少有「m/2]棵子树，即至少含有*[m/2]-1个关键字*。
所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)。

其中，Ki (i= 1,2..., n)为结点的关键字，且满足K1<K2<...< Kn；Pi (i = 0,1..， n)为指向子树根结点的指针，且指针Pi-1所指子树中所有结点的关键字均小于Ki，Pi所指子树中所有结点的关键字均大于Ki，n( [m/2]-1≤n≤m -1)为结点中关键字的个数。

m阶B树的核心特性:

根节点的子树数∈[2, m]，关键字数∈[1, m-1]。

其他结点的子树数∈[ [m/2], m];关键字数∈[[m/2]-1, m-1]2)

对任一结点，其所有子树高度都相同

关键字的值:子树O<关键字1<子树1<关键字2<子树2<.....(类比二叉查找树左<中<右)

5.8.2 B树的插入删除

插入

核心要求

对m阶B树——除根节点外，结点关键字个数 $\lceil m/2 \rceil$ -1≤n≤m-1
子树O<关键字1<子树1<关键字2<子树2<....

新元素一定是插入到最底层“终端节点”，用“查找”来确定插入位置
在插入key后，若导致原结点关键字数超过上限，则从中间位置([m/2]）将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（[m/2])的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1。

删除

核心要求：

对m阶B树——除根节点外，关键字节点个数 $\lceil m/2 \rceil$ -1≤n≤m-1

子树0<关键字<子树1<关键字2<子树2<......

5.8.3 B+树

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

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

非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2]棵子树。

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

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

所有分支节点中仅包含它子节点中的关键字的最大值及指向其子节点的指针

可以理解为:要追求“绝对平衡”，即所有子树高度要相同

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

B+树	B树
结点中的n个关键字对应 n 棵树	结点中的n个关键字对应 n+1 棵树
根结点的关键字数n $\in$ [1,m] 其它节点的关键字数n $\in$ [ $\lceil m/2 \rceil$ ,m ]	根结点的关键字数n $\in$ [1,m-1] 其它节点的关键字数n $\in$ [ $\lceil m/2 \rceil$ -1,m-1 ]
叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中	在B树中，各结点中包含的关键字是不重复的
叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。	B树的结点中都包含了关键字对应的记录的存储地址

在B+树中，非叶结点不含有该关键字对应记录的存储地址。

可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，树高更矮，

读磁盘次数更少，查找更快

5.9 哈夫曼树

带权路径长度

结点的权：有某种现实含义的数值（如：表示结点的重要性等）

结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

树的带权路径长度：树中所有叶结点的带权路径长度之和

5.9.1 哈夫曼树的定义

在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树

5.9.2 哈夫曼树的构造

给定n个权值分别为w1, w2,…, wn的结点，构造哈夫曼树的算法描述如下：

将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
重复步骤 2 和 3 ，直至F中只剩下一棵树为止。

每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大

哈夫曼树的结点总数为2n − 1

哈夫曼树中不存在度为1的结点。

哈夫曼树并不唯一，但WPL必然相同且为最优

5.9.3 哈夫曼编码

可变长度编码——允许对不同字符用不等长的二进制位表示

若没有一个编码是另一个编码的前缀，则称这样的编码为 前缀编码

固定长度编码- --每个字符用相等长度的二进制位表示
可变长度编码--允许对不同字符用不等长的二进制位表示
若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码
有哈夫曼树得到哈夫曼编码- --字符集中的每个字符作为-一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树

5.10 并查集

5.10.1 并查集基础

用互不相交的树，表示多个“集合”

对这些“集合”进行查询和合并操作得到的集合：并查集

如何“查”到一个元素到底属于哪一个集合?

从指定元素出发，一路向北，找到根节点

如何判断两个元素是否属于同一个集合?

分别查到两个元素的根，判断根节点是否相同即可

如何把两个集合“并”为一一个集合?

让一棵树成为另一棵树的子树即可

为了进行“查询”和“并”操作，这里选择树的存储结构为双亲表示法

//双亲表示法:每个结点中保存指向双亲的“指针”
#define MAX_TREE_SIZE 100	//树中最多结点数
typedef struct{	//树的结点定义
    ElemType data; 	//数据元素
    int parent;	//双亲位置域
}PTNode;

typedef struct{	//树的类型定义
    PTNode nodes [MAX_ TREE_ _SIZE] ;	//双亲表示
    int n;	//结点数
}PTree;

#define SIZE 13
int UFSets[SIZE];//集合元素数组
//初始化并查集
void Initial(int S[ ]){
    for(int i=0;i<SIZE;i++)
        S[i]=-1 ;   //将S[]全部初始化为-1
}

//Find "查"操作， 找x所属集合(返回x所属根结点)
//最坏时间复杂度O(n)
int Find(int S[],int x){
    while(S[x]>=0 )	//循环寻找x的根
        x=S[x];
    return X;	//根的S[ ]小于0
}
//Union "并"操作， 将两个集合合并为-个
//时间复杂度O(1)
void Union(int S[],int Root1, int Root2) {
    //要求Root1与Root2是不同的集合
    if (Root1==Root2) return;
    //将根Root2连接到另一根Root1下面
    S[Root2]=Root1;
}

5.10.2 并查集的优化

//Union“并" 操作，小树合并到大树
//该方法构造的树高不超过[log2n]+ 1
void Union(int S[ ],int Root1, int Root2) {
    if ( Root1==Root2 )
        return;
    if(S[Root2]>S[Root1]) { //Root2结点数更少
        S[Root1] += S[Root2]; //累加结点总数
        S[Root2]=Root1; //小树合并到大树
    } else {
        S[Root2] += S[Root1]; //累加结点总数
        S[Root1]=Root2; / /小树合并到大树
    }
}

Union优化后，find的最坏时间复杂度变为O(log2n)

5.10.3 并查集进一步优化

Find的优化（压缩路径）

压缩路径—— Find 操作，先找到根节点，再将查找路径上所有结点都挂到根结点下

//Find“查"操作优化，(先找到根节点再进行“压缩路径”
int Find(int S[],int x){
    int root = x;
    while(S[root]>=0)
        root=S[root]; //循环找到根
    while(x!=root){ //压缩路径
        int t=S[x];	// t指向x的父节点
        S[x]=root ;	//x直接挂到根节点下
        x=t;
    }
    return root ;//返回根节点编号
}

每次Find操作，先找根，再“压缩路径”，可使树的高度不超过0(a(n))。a(n)是一个增长很缓慢的函数，对于常见的n值，通常a(n)S4，因此优化后并查集的Find、Union操作时间开销都很低

6. 图

6.1 图的基本概念

6.1.1 基本概念

图G由顶点集V和边集E组成，记为G = (V, E)，其中V(G)表示图G中顶点的有限非空集；E(G) 表示图G中顶点之间的关系（边）集合。若V = {v1, v2, … , vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E = {(u, v) | uÎV, vÎV}，用|E|表示图G中边的条数。

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

无向图、有向图

若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为**(v, w)或(w, v)，因为(v, w) = (w, v)**，其中v、w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w) 依附于顶点w和v，或者说边(v, w)和顶点v、w相关联。 G2 = (V2, E2) V2 = {A, B, C, D, E} E2 = {(A, B), (B, D), (B, E), (C, D), (C, E), (D, E)}

若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v,w>，其中v、w是顶点，v称为弧尾，w称为弧头，称为从顶点v到顶点w的弧，也称 v邻接到w，或w邻接自v。 <v,w>≠<w,v> G1 = (V1, E1) V1 = {A, B, C, D, E} E1={<A, B>, <A, C>, <A,D>, <A, E>, <B, A>, <B,C>,<B,E>, <C, D>}

完全图

对于无向图E的取值范围是0~n(n-1)/2，完全图的边则是n(n-1)/2最大，其特点是图中任意两点都有直接相连的边，同时在完全图的基础上加一个点和一条边必定为连通图

简单图、多重图

简单图——① 不存在重复边； ② 不存在顶点到自身的边

多重图——图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图

顶点的度、入度、出度

对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。

在具有n个顶点、e条边的无向图中， $\sum_{i=1}^n$ TD(vi) = 2e

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

对于有向图：

入度是以顶点v为终点的有向边的数目，记为ID(v)；

出度是以顶点v为起点的有向边的数目，记为OD(v)。

顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

在具有n个顶点、e条边的有向图中， $\sum_{i=1}^n$ ID(vi) = $\sum_{i=1}^n$ TD(vi) = e

顶点-顶点的关系描述

路径——顶点vp到顶点vq之间的一条路径是指顶点序列
回路——第一个顶点和最后一个顶点相同的路径称为回路或环
简路径——在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度——路径上边的数目
点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。
无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

连通图、强连通图

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

若图中任何一对顶点都是强连通的，则称此图为强连通图。

常见考点：

对于n个顶点的无向图G，若G是连通图，则最少有 n-1 条边；若G是非连通图，则最多可能有**C~~n-1~~^2^**条边

对于n个顶点的有向图G，若G是强连通图，则最少有 n条边（形成回路）

研究图的局部——子图

连通分量

无向图中的极大连通子图称为连通分量。（子图必须连通，且包含尽可能多的顶点和边）

强连通分量

有向图中的极大强连通子图称为有向图的强连通分量（子图必须强连通，同时保留尽可能多的边）

生成树

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

若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。（边尽可能的少，但要保持连通）

生成森林

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

边的权、带权图/网

边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。

带权图/网——边上带有权值的图称为带权图，也称网。

带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

6.1.2 几种特殊形态的图

无向完全图——无向图中任意两个顶点之间都存在边

若无向图的顶点数|V|=n，则 |E| ∈ [0, Cn^2^] = [0, n(n–1)/2]

有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧

若有向图的顶点数|V|=n，则 |E| ∈ 0, 2Cn^2^] = [0, n(n–1)]

6.2 图的存储结构

6.2.1 邻接矩阵法

#define MaxVertexNum 100	//顶点数目的最大值
typedef struct{
    char Vex[MaxVertexNum] ;	//顶点表.（顶点中可以存更复杂的信息）
    int Edge [MaxVertexNum] [MaxVertexNum];	//邻接矩阵，边表（可以用 bool型或枚举型变量表示边）
    int vexnum, arcnum;		//图的当前顶点数和边数/弧数
} MGraph;

邻接矩阵法存储带权图（网）

#define MaxVertexNum 100	//顶点数目的最大值
#define INFINITY 最大的int值 //宏定义常量"无穷"
typedef char VertexType; 	//顶点的数据类型
typedef int EdgeType;		//带权图中边上权值的数据类型
typedef struct{
    VertexType Vex [MaxVertexNum];	//顶点
    EdgeType Edge [MaxVertexNum] [MaxVertexNum]; //边的权
    int vexnum, arcnum;		// 图的当前顶点数和弧数
}MGraph;

有时也会将同顶点的路径权值改为0

邻接矩阵法的性能分析

空间复杂度：O(|V|^2^ ) ——只和顶点数相关，和实际的边数无关

顶点数为n，则其空间复杂度为O(n) + O(n^2^) ，即为 O(n^2^)

适合用于存储稠密图

无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）

邻接矩阵法的性质

比如A^2^[1][4]就表示从A到D，长度为2的路径数目

其中 a1,1 a1,4表示A——>A(0) 和 A——>D(0) 路径的合并，0*0 = 0 故没有这样的路径

再如a1,2 a2,4表示A——>B(1) 和 B——>D(1) 路径的合并，1*1 = 1 故有一条A——>B——>D的路径

A^3^ 和上述法则相同，表示X——>X路径长度为3的路径的数量

6.2.2 邻接表法

邻接表法（顺序+链式存储）

//用邻接表存储的图
typedef struct{
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

//"边/弧"
typedef struct ArcNode{
    int adivex;		//边/弧指向哪个结点
    struct ArcNode *next ;	//指向下一条弧的指针
    //InfoType. info;	//边权值
}ArcNode;

//"顶点"
typedef struct VNode{
    VertexType data;	//顶点信息
    ArcNode *first;		//第一条边/弧
}VNode,AdjList[MaxVertexNum];

对比：树的孩子表示法

求顶点的度：

无向图：遍历与顶点相关的边链表，有多少边节点就有多少个度

有向图：

出度：遍历与顶点相关的边链表，有多少边节点就有多少个出度

入度：全部进行遍历，找到指向顶点的（时间复杂度高）

图的邻接表表示方式并不唯一

只要确定了顶点编号，图的邻接矩阵表示方式唯一

	邻接表	邻接矩阵
空间复杂度	无向图 O(\|V\| + 2\|E\|）;有向图O(\|V\| + \|E\|)	O(\|V\|^2^)
适存合用于	存储稀疏图	存储稠密图
表示方式	不唯一	唯一
计算度/出度/入度	计算有向图的度、入度不方便，其余很方便	必须遍历对应行或列
找相邻的边	找有向图的入边不方便，其余很方便	必须遍历对应行或列

6.2.3 十字链表、邻接多重表

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

对于邻接表：找有向图的入边不方便 ；对邻接矩阵：空间复杂度高 O(|V|^2^)

十字链表存储有向图

空间复杂度：O(|V|+|E|)

如何找到指定顶点的所有出边？——顺着绿色线路找

如何找到指定顶点的所有入边？——顺着橙色线路找

注意：十字链表只用于存储有向图

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

邻接表：每条边对应两份冗余信息，删除顶点、删除边等操作时间复杂度高

邻接矩阵：空间复杂度高 O(|V|2 )

邻接多重表存储无向图：

空间复杂度：O(|V|+|E|)

删除边、删除节点等操作很方便（每条边只对应一份数据）

注意：邻接多重表只适用于存储无向图

	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	O(\|V\|^2^)	无向图O(\|V\|+2\|E\|) ;有向图O(\|V\|+\|E\|)	O(\|V\|+\|E\|)	O(\|V\|+\|E\|)
找相邻边	遍历对应行或列时间复杂度为O(\|V\|)	找有向图的入边必须遍历整个邻接表	很方便	很方便
删除边或顶点	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点都不方便	很方便	很方便
适用于	稠密图	稀疏图和其他	只能存有向图	只能存无向图
表示方式	唯一	不唯一	不唯一	不唯一

6.2.4 基本操作

图的基本操作：

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)或有向边不存在，则向图G中添加该边。
RemoveEdge(G,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)或对应的权值。
et_edge_value(G,x,y,v)：设置图G中边(x, y)或对应的权值为v。

操作	邻接矩阵	邻接表
判断图G是否存在边<x,y>或(x, y)	无（有）向图：O(1)	无（有）向图：O(1) ~O(\|V\|)
出图G中与结点x邻接的边	无（有）向图：O(\|V\|)	无向图：O(1) ~O(\|V\|)；有向图：出边：O(1) ~O(\|V\|)，入边：O(\|E\|)
图G中插入顶点x	无（有）向图：O(1)	无（有）向图：O(1)
从图G中删除顶点x	无（有）向图：O(\|V\|)	无向图：O(1) ~O(\|E\|) ；有向图：删出边：O(1) ~O(\|V\|)，删入边：O(\|E\|)
添加边（若该边不存在）	无（有）向图：O(1)	无（有）向图：O(1)
删除边（若该边存在）	无（有）向图：O(1)	无（有）向图：O(1) ~O(\|V\|)
找顶点的下一个邻接点	无（有）向图：O(1) ~O(\|V\|)	无向图：O(1) ；有向图：找出边邻接点：O(1)，~~找入边邻接点~~：O(1) ~O(\|E\|)
找顶点的下一个邻接点x外的下一个邻接点	无（有）向图：O(1) ~O(\|V\|)	无向图：O(1) ；有向图：找出边邻接点：O(1)，~~找入边邻接点~~：O(1) ~O(\|E\|)
获取边对应的权值；设置边对应的权值为v；（相当于找边）	无（有）向图：O(1)	无（有）向图：O(1) ~O(

6.3 图的遍历

6.3.1 图的广度优先遍历（BFS）

树 vs 图

⼴度优先遍历（Breadth-First-Search, BFS）要点：

找到与⼀个顶点相邻的所有顶点
标记哪些顶点被访问过
需要⼀个辅助队列

FirstNeighbor(G,x)：求图G中顶点x的第⼀个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。

NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的⼀个邻接点，返回除y之外顶点x的下⼀个邻接点的顶点号，若y是x的最后⼀个邻接点，则返回-1。

bool visited [MAX_VERTEX_NUM]; //访问标记数组 (初始都为false)
//广度优先遍历
void BFS(Graph G,int v){ //从顶点v出发， 广度优先遍历图G
    visit(v);	//访问初始顶点v
    visited [v]=TRUE;	//对v做已访问标记
    Enqueue(Q,v);	//顶点v入队列Q .
    while( !isEmpty(Q)){
        DeQueue(Q,v);	//顶点v出队列
        for(w=FirstNeighbor(G, v) ;W>=0 ;w=NextNeighbor(G,v,W))
            //检测v所有邻接点
            if(!visited [w]){ 	//w为v的尚未访问的邻接顶点
                visit(w);	//访问顶点w
                visited [w]=TRUE;	//对w做已访问标记
                EnQueue(Q,w); 	//顶点w入队列
            }//if
    }//while
}

同⼀个图的邻接矩阵表示⽅式唯⼀，因此⼴度优先遍历序列唯⼀

同⼀个图的邻接表表示⽅式不唯⼀，因此⼴度优先遍历序列不唯⼀

BFS算法（Final版）：解决了非连通图的问题

bool visited [MAX_VERTEX_NUM]; //访问标记数组 (初始都为false)

void BFSTraverse(Graph G){ //对图G进行广度优先遍历
    for(i=0; i<G.vexnum;++i)
        visited[i]=FALSE;	//访问标记数组初始化
    InitQueue(Q);	//初始化辅助队列Q
    for( i=0; i<G.vexnum; ++i)	//从0号顶点开始遍历
        if( !visited[i] )	//对每个连通分量调用一次BFS
            BFS(G,i);	//vi未访问过，从vi开始BFS
}

//广度优先遍历
void BFS(Graph G,int v){ //从顶点v出发， 广度优先遍历图G
    visit(v);	//访问初始顶点v
    visited [v]=TRUE;	//对v做已访问标记
    Enqueue(Q,v);	//顶点v入队列Q .
    while( !isEmpty(Q)){
        DeQueue(Q,v);	//顶点v出队列
        for(w=FirstNeighbor(G, v) ;W>=0 ;w=NextNeighbor(G,v,W))
            //检测v所有邻接点
            if(!visited [w]){ 	//w为v的尚未访问的邻接顶点
                visit(w);	//访问顶点w
                visited [w]=TRUE;	//对w做已访问标记
                EnQueue(Q,w); 	//顶点w入队列
            }//if
    }//while
}

结论：对于⽆向图，调⽤BFS函数的次数=连通分量数

复杂度分析：

空间复杂度：最坏情况，辅助队列⼤⼩为 O(|V|)

邻接矩阵存储的图：

访问 |V| 个顶点需要O(|V|)的时间

查找每个顶点的邻接点都需要O(|V|)的时间，⽽总共有|V|个顶点

时间复杂度= O(|V|) + O(|V|^2^) = O(|V^2^|)

邻接表存储的图：

访问 |V| 个顶点需要O(|V|)的时间

查找各个顶点的邻接点共需要O(|E|)的时间，（其实对于⽆向图来说，应该是O(2|E|) 的时间）

时间复杂度= O(|V|) + O(|E|)

⼴度优先⽣成树

⼴度优先⽣成树由⼴度优先遍历过程确定。由于邻接表的表示⽅式不唯⼀，因此基于邻接表的⼴度优先⽣成树也不唯⼀。

对⾮连通图的⼴度优先遍历，可得到⼴度优先⽣成森林

6.3.2 图的深度优先遍历（DFS）

树的深度优先遍历（先根遍历）

void- PreOrder(TreeNode *R) {
    if (R!=NULL){
        visit(R);        //访问根节点
        while(R还有下一个子树T)//新找到的相邻结点⼀定是没有访问过的
            PreOrder(T); //先根遍历下- -棵子树
    }
}

树的深度优先遍历（先根、后根）：从根节点出发，能往更深处⾛就尽量往深处⾛。每当访问⼀个结点的时候，要检查是否还有与当前结点相邻的且没有被访问过的结点，如果有的话就往下⼀层钻。图的深度优先遍历类似于树的先根遍历。

先根遍历序列：1，2，5，6，3，4，7，8

图的深度优先遍历

bool visited [MAX_ _VERTEX_ NUM] ; //访问标记数组，初始为false
void DFS(Graph G,int v){	//从顶点v出发，深度优先遍历图G
    visit(v);	//访问顶点V
    visited [v]=TRUE;	//设已访问标记
    for (w=F irstNe ighbor(G, v);w>=0;w=NextNeighor(G,v,w)) .
        if( !visited [w]){ 	//w为u的尚未访问的邻接顶点
            DFS(G,w) ;
        } //if
}

DFS算法（Final版）解决非连通图的问题

bool visited [MAX_ _VERTEX_ NUM]; //访问标记数组
void DFSTraverse(Graph G){	// 对图G进行深度优先遍历
    for(v=0;v<G. vexnum; ++v)
        visited[v]=FAL SE;	//初始化已访问标记数据
    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
    vis ited [v]=TRUE;	//设已访问标记
    for(w=FirstNeighbor(G, v) ;W>=0;w=NextNeighor(G,v,W) )
        if(!visited [w]){	//w为u的尚未访问的邻接顶点
            DFS(G,w);
        } //if 
}

复杂度分析

空间复杂度：来⾃函数调⽤栈，最坏情况，递归深度为O(|V|)

空间复杂度：最好情况，O(1)

邻接矩阵存储的图：

访问 |V| 个顶点需要O(|V|)的时间

查找每个顶点的邻接点都需要O(|V|)的时间，⽽总共有|V|个顶点

时间复杂度= O(|V|) + O(|V|^2^) = O(|V^2^|)

邻接表存储的图：

访问 |V| 个顶点需要O(|V|)的时间

查找各个顶点的邻接点共需要O(|E|)的时间，（其实对于⽆向图来说，应该是O(2|E|) 的时间）

时间复杂度= O(|V|) + O(|E|)

时间复杂度=访问各结点所需时间+探索各条边所需时间

同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀

同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀

深度优先生成树和生成森林和广度类似

图的遍历与图的连通性

对⽆向图进⾏BFS/DFS遍历

调⽤BFS/DFS函数的次数=连通分量数

对于连通图，只需调⽤1次 BFS/DFS

对有向图进⾏BFS/DFS遍历

调⽤BFS/DFS函数的次数要具体问题具体分析

若起始顶点到其他各顶点都有路径，则只需调⽤1次 BFS/DFS 函数

对于强连通图，从任⼀结点出发都只需调⽤1次 BFS/DFS

6.4 最⼩⽣成树问题

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

若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

最⼩⽣成树（最⼩代价树）

道路规划要求：所有地⽅都连通，且成本尽可能的低

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

最⼩⽣成树可能有多个，但边的权值之和总是唯⼀且最⼩的
最⼩⽣成树的边数 = 顶点数 - 1。砍掉⼀条则不连通，增加⼀条边则会出现回路
如果⼀个连通图本身就是⼀棵树，则其最⼩⽣成树就是它本身
只有连通图才有⽣成树，⾮连通图只有⽣成森林

6.4.1 Prim 算法（普⾥姆）

Prim 算法（普⾥姆）：从某⼀个顶点开始构建⽣成树；每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。

Prim 算法的实现思想

循环遍历所有个结点，找到lowCost最低的，且还没加⼊树的顶点

再次循环遍历，更新还没加⼊的各个顶点的lowCost值

从V0开始，总共需要 n-1 轮处理

每⼀轮处理：循环遍历所有个结点，找到lowCost最低的，且还没加⼊树的顶点。

再次循环遍历，更新还没加⼊的各个顶点的lowCost值——每⼀轮时间复杂度O(2n)

总时间复杂度 O(n2)，即O(|V|2)

6.4.2 Kruskal 算法（克鲁斯卡尔）

Kruskal 算法（克鲁斯卡尔）：每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通

Kruskal 算法的实现思想

第1轮：检查第1条边的两个顶点是否连通（是否属于同⼀个集合）

第2轮：检查第2条边的两个顶点是否连通（是否属于同⼀个集合）

……

6.5 最短路径问题

6.4.1 BFS—无权图

bool visited [MAX_VERTEX_NUM]; //访问标记数组 (初始都为false)
int d[],path[]; //辅助数组
//广度优先遍历
void BFS(Graph G,int v){ //从顶点v出发， 广度优先遍历图G
	for(i=0;i<G.vexnum;++i){
        d[i]=∞；
        path[i]=-1;
    }
    d[v]=0;
    visited [v]=TRUE;	//对v做已访问标记
    Enqueue(Q,v);	//顶点v入队列Q
    while( !isEmpty(Q)){
        DeQueue(Q,v);	//顶点v出队列
        for(w=FirstNeighbor(G, v) ;W>=0 ;w=NextNeighbor(G,v,W))
            //检测v所有邻接点
            if(!visited [w]){ 	//w为v的尚未访问的邻接顶点
                d[w]=d[u]+1;	//路径长度加1
                path[w]=v		//最短路径应从v到w
                visited [w]=TRUE;	//对w做已访问标记
                EnQueue(Q,w); 	//顶点w入队列
            }//if
    }//while
}

6.4.2 Dĳkstra算法 ——通用

初始：从V0开始，初始化三个数组信息如下

每轮循环：

循环遍历所有结点，找到还没确定最短路径，且dist 最⼩的顶点Vi，令final[i]=ture。

检查所有邻接⾃ Vi 的顶点，若其 final 值为false，则更新 dist 和 path 信息

Dijkstra算法的时间复杂度

初始:

若从Vo开始，令final[0]=ture; dist[0]=0; path[0]=-1。其余顶点final[k]=false; dist[k]=arcs[0][k]; path[k]= (arcs[0][k]==∞)?-1 :0
n-1轮处理:循环遍历所有顶点，找到还没确定最短路径，且dist最小的顶点V，令final[i]=ture。并检查所有邻接自V;的顶点，对于邻接自Vi的顶点Vj，若final[j]==false且dist[i]+arcs[i][j]<dist[j]，则令dist[j]=dist[i]+arcs[i][j]; path[j]=i。(注: arcs[][]表示Vi 到Vj的弧的权值)

时间复杂度: O(n^2^)即O(|V|^2^)

6.4.3 Floyd算法——通用

Floyd算法：求出每⼀对顶点之间的最短路径使⽤动态规划思想，将问题的求解分为多个阶段对于n个顶点的图G，求任意⼀对顶点 Vi —> Vj 之间的最短路径可分为如下⼏个阶段：

0：初始：不允许在其他顶点中转，最短路径是？
1：若允许在 V0 中转，最短路径是？
2：若允许在 V0、V1 中转，最短路径是？
3：若允许在 V0、V1、V2 中转，最短路径是？

…

n-1：若允许在 V0、V1、V2 …… Vn-1 中转，最短路径是？

for(int i=0; i<n; i++) {	//考虑以Vk作为中转点
    for(int i=0; i<n; i++) { //遍历整个矩阵， i为行号，j为列号
        for (int j=0; j<n; j++){
            if (A[i][j]>A[i][k]+A[k][j]){ //以 Vk为中转点的路径更短
                A[i][j]=A[i][k]+A[k][j];            //更新最短路径长度
                path[i][j]=k;            //中转点
            }
        }
    }
}

时间复杂度为O(|V|^3^)，空间复杂度为O(|V|^2^)

Floyd算法可以⽤于负权值带权图

Floyd 算法不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径

	BFS 算法	Dĳkstra 算法	Floyd 算法
⽆权图	✔	✔	✔
带权图	❌	✔	✔
带负权值的图	❌	❌	✔
带负权回路的图	❌	❌	❌
时间复杂度	O(\|V\|^2^)或O(\|E\|+\|V\|)	O(\|V\|^2^)	O(\|V\|^3^)
通常⽤于	求⽆权图的单源最短路径	求带权图的单源最短路径	求带权图中各顶点间的最短路径

注：也可⽤ Dijkstra 算法求所有顶点间的最短路径，重复 |V| 次即可，总的时间复杂度也是O(|V|^3^)

6.6 有向无环图（DAG）

6.6.1 有向⽆环图描述表达式

有向⽆环图：若⼀个有向图中不存在环，则称为有向⽆环图，简称DAG图（Directed Acyclic Graph）

对于以下树结构，将其转化为DAG描述的图为

顶点中不可能出现重复的操作数

6.6.2 拓扑排序

AOV⽹(Activity On Vertex NetWork，⽤顶点表示活动的⽹)：

**⽤DAG图（有向⽆环图）**表示⼀个⼯程。顶点表示活动，有向边 <Vi , Vj> 表示活动 Vi 必须先于活动 Vj 进⾏

拓扑排序：在图论中，由⼀个有向⽆环图的顶点组成的序列，当且仅当满⾜下列条件时，称为该图的⼀个拓扑排序：

① 每个顶点出现且只出现⼀次。

② 若顶点A在序列中排在顶点B的前⾯，则在图中不存在从顶点B到顶点A的路径。

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

拓扑排序的实现：

**① 从AOV⽹中选择⼀个没有前驱（⼊度为0）的顶点并输出。 **

**② 从⽹中删除该顶点和所有以它为起点的有向边。 **

③ 重复①和②直到当前的AOV⽹为空或当前⽹中不存在⽆前驱的顶点为⽌。

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

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(|V|+|E|)

若采⽤邻接矩阵，则需O(|V|2)

逆拓扑排序

若模仿上面的拓扑排序的代码，由于邻接表时间复杂度开销过大，逆拓扑排序需要考虑使用存储为邻接矩阵，而非邻接表，当然也可以用逆邻接表

逆拓扑排序的实现（DFS算法）

逆拓扑排序序列：4 3 1 0 2

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=FirstNe ighbor(G, v) ;W>=0 ;w=NextNeighor(G,V,W))
        if(!visited[w]){ 	//w为u的尚未访问的邻接顶点
            DFS(G,W);
        } //if、
    print(v); //DFS实现逆拓扑排序：在顶点退栈前输出
}

思考：如果存在回路，则不存在逆拓扑排序序列，如何判断回路?

6.6.3 关键路径

AOE⽹

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为⽤边表示活动的⽹络，简称AOE⽹ (Activity On Edge NetWork)

AOE⽹具有以下两个性质：、

① 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；

② 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。另外，有些活动是可以并⾏进⾏的

在AOE⽹中仅有⼀个⼊度为0的顶点，称为开始顶点（源点），它表示整个⼯程的开始；也仅有⼀个出度为0的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。

从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径 称为 关键路径，⽽把关键路径上的活动称为关键活动

完成整个⼯程的最短时间就是关键路径的⻓度，若关键活动不能按时完成，则整个⼯程的完成时间就会延⻓

事件 vk 的最早发⽣时间ve(k)——决定了所有从vk开始的活动能够开⼯的最早时间

活动 ai 的最早开始时间e(i)——指该活动弧的起点所表⽰的事件的最早发⽣时间

事件vk的最迟发⽣时间vl(k)——它是指在不推迟整个⼯程完成的前提下，该事件最迟必须发⽣的时间。

活动ai的最迟开始时间l(i)——它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差。

求关键路径的步骤

① 求所有事件的最早发⽣时间 ve( )

② 求所有事件的最迟发⽣时间 vl( )

③ 求所有活动的最早发⽣时间 e( )

④ 求所有活动的最迟发⽣时间 l( )

⑤ 求所有活动的时间余量 d( ) ——d(i)=0的活动就是关键活动, 由关键活动可得关键路径

关键活动、关键路径的特性：

若关键活动耗时增加，则整个⼯程的⼯期将增⻓
缩短关键活动的时间，可以缩短整个⼯程的⼯期
当缩短到⼀定程度时，关键活动可能会变成⾮关键活动
可能有多条关键路径，只提⾼⼀条关键路径上的关键活动速度并不能缩短整个⼯程的⼯期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短⼯期的⽬的。

7. 查找

7.1 查找的基本概念

基本概念：

查找——在数据集合中寻找满足某种条件的数据元素的过程称为查找
查找表(查找结构)——用于查找的数据集合称为查找表，它由同一类型的数据元素(或记录)组成
关键字一一数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

对查找表的常⻅操作：

①查找符合条件的数据元素

②插⼊、删除某个数据元素

查找算法的评价指标：
查找⻓度——在查找运算中，需要对⽐关键字的次数称为查找⻓度

平均查找⻓度（ASL, Average Search Length）—— 所有查找过程中进⾏关键字的⽐较次数的平均值

7.2 常见查找

7.2.1 顺序查找

顺序查找的算法思想：顺序查找，⼜叫“线性查找”，通常⽤于线性表。算法思想：从头到 jio 挨个找（或者反过来也OK）

typedef struct{	//查找表的数据结构(顺序表)
    ElemType *elem;	//动态数组基址
    int TableLen;	//表的长度
}SSTable;	
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0;i<ST.TableLen && ST.elem[i] !=key; ++i);
    //查找成功，则返回元素下标;查找失败，则返回-1
    return i== =ST.TableLen? -1 : i;
}

顺序查找的实现（哨兵）：从尾到头（在头部设置“哨兵”）

数据从下标1开始存

typedef struct{	//查找表的数据结构(顺序表)
    ElemType *elem;	//动态数组基址
    int TableLen;	//表的长度
}SSTable;	
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;
    int i;
    for(i=ST.TableLen;ST.elem[i] !=key;--i); //从后往前找
    return i;	//查找成功，则返回元素下标;查找失败，则返回04
}

优点：⽆需判断是否越界，效率更⾼；0号位置存 “哨兵”

⼀个成功结点的查找⻓度 = ⾃身所在层数

⼀个失败结点的查找⻓度 = 其⽗节点所在层数

默认情况下，各种失败情况或成功情况都等概率发⽣

7.2.2 折半查找

折半查找，⼜称“⼆分查找”，仅适⽤于有序的顺序表。

mid为中间指针，其值为low和heigh的指针除2向下取整（也可向上取整，在后面提到）

typedef struct{	//查找表的数据结构(顺序表)
    ElemType *elem;	//动态数组基址
    int TableLen;	//表的长度
}SSTable;

//折半查找
int Binary_Search(SSTable L, ElemType key){
    int low=0, high=L. TableLen-1, mid;
    while( low<=high){
        mid=( low+high)/2;	//取中间位置
        if(L.elem[mid]==key) 
            return mid;	//查找成功则返回所在位置
        else if(L.elem [mid]>key)
            high=mid-1;	//从前半部分继续查找
        else
            low=mid+1;//从后半部分继续查找
    }return- 1 ;//查找失败，返回-1 
}

折半查找判定树的构造

7.2.3 分块查找

分块查找，⼜称索引顺序查找，算法过程如下：

①在索引表中确定待查记录所属的分块（可顺序、可折半）

②在块内顺序查找

若超出分块范围，则查找失败

7.3 散列查找

7.3.1 散列表（Hash Table）

散列表（Hash Table），⼜称哈希表。是⼀种数据结构，特点是：数据元素的关键字与其存储地址直接相关

⽤拉链法（⼜称链接法、链地址法）处理“冲突”：把所有“同义词”存储在⼀个链表中

有的教材也会把“空指针” 的判定算作⼀次⽐较

7.3.2 常见散列函数

7.3.3 散列查找

8. 排序

8.1 排序的基本概念

排序（Sort），就是重新排列表中的元素，使表中的元素满⾜按关键字有序的过程。

输⼊：n个记录R1, R2,…, Rn，对应的关键字为k1, k2,…, kn。输出：输⼊序列的⼀个重排R1ʹ, R2ʹ,…, Rnʹ，使得有k1ʹ≤k2ʹ≤…≤knʹ（也可递减）

排序算法的评价指标

算法的稳定性。若待排序表中有两个元素Ri和Rj，其对应的关键字相同即keyi = keyj，且在排序前Ri在Rj的前⾯，若使⽤某⼀排序算法排序后，Ri仍然在Rj的前⾯，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

排序算法的分类

⼀个神奇的学习⽹站

8.2 插入排序

8.2.1 直接插入排序

算法思想：每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯已排好序的⼦序列中，直到全部记录插⼊完成。

//直接插入排序
void InsertSort(int A[] ,int n){
    int i,j,temp;
    for( i=1; i<n; i++)	//将各元素插入已排好序的序列中
        if(A[i]<A[i-1]){	//若A[i]关键字小于前驱
            temp=A[i];	//用temp暂存A[i]
            for(j=i-1;j>=O && A[j]>temp;--j)	//检查所有前面已排好序的元素
                A[j+1]=A[j];	//所有大于temp的元素都向后挪位
            A[j+1]=temp;	//复制到插入位置
        }
}

算法实现（带哨兵）

//直接插入排序（带哨兵)
void InsertSort(int 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[O]<A[j];--j)	//从后往前查找待插入位置
                A[j+1]=A[j];	//向后挪位
            A[j+1]=A[0];	//复制到插入位置
        }
}

空间复杂度：O(1)

时间复杂度：主要来⾃对⽐关键字、移动元素若有 n 个元素，则需要 n-1 趟处理

最好情况：共n-1趟处理，每⼀趟只需要对⽐关键字1次，不⽤移动元素 最好时间复杂度—— O(n)

最坏情况：第1趟：对⽐关键字2次，移动元素3次第2趟：对⽐关键字3次，移动元素4次 … 第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次 …

最坏时间复杂度——O(n^2^)

总结：

空间复杂度：O(1)

最好时间复杂度（全部有序）：O(n)

最坏时间复杂度（全部逆序）：O(n^2^)

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

算法稳定性：稳定

优化——折半插⼊排序

思路：先⽤折半查找找到应该插⼊的位置，再移动元素

当 low>high 时折半查找停⽌，应将 [low, i-1] 内的元素全部右移，并将 A[0] 复制到 low 所指位置

当 A[mid]==A[0]时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插⼊位置

当 low>high 时折半查找停⽌，应将 [low, i-1] （也可以写为 [high+1,i-1]） 内的元素全部右移，并将 A[0] 复制到 low 所指位置，当 A[mid]==A[0] 时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插⼊位置

//折半插入排序
void InsertSort(int 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(n^2^)

8.2.2 希尔排序

希尔排序：先将待排序表分割成若⼲形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”⼦表，对各个⼦表分别进⾏直接插⼊排序。缩⼩增量d，重复上述过程，直到d=1为⽌。

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

算法性能分析

空间复杂度：O(1)

时间复杂度：和增量序列 d1, d2, d3… 的选择有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度

最坏时间复杂度为 O(n^2^)，当n在某个范围内时，可达O(n^1.3^)

稳定性：不稳定！

适⽤性：仅适⽤于顺序表，不适⽤于链表

8.3 交换排序

8.3.1 冒泡排序

从后往前（或从前往后）两两⽐较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列⽐较完。称这样过程为“⼀趟”冒泡排序。

从后往前（或从前往后）两两⽐较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列⽐较完。称这样过程为“⼀趟”冒泡排序。总共需进⾏ n-1 趟冒泡。

//交换
void swap(int &a,int &b){
    int temp = a;
    a= b;
    b = temp;
}

//冒泡排序
void BubbleSort(int A[] ,int n){
    for(int i=0; i<n-1;i++){
        bool flag=false;	//表示本趟冒泡是否发生交换的标志
        for(int j=n-1; j>i;j--)	//一趟冒泡过程
            if(A[j-1]>A[j]){	//若为逆序
                swap(A[j-1],A[j]);	//交换
                flag=true;
            }
        if(flag==false)
            return;	//本趟遍历后没有发生交换，说明表已经有序
    }
}

只有A[ j -1]>A[ j ]时才交换，因此算法是稳定的

算法性能分析

冒泡排序同样适⽤于链表

8.3.2 快速排序

算法思想：在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于 pivot，则pivot放在了其最终位置L(k)上，这个过程称为⼀次“划分”。然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

总结：取出一个元素（这个元素一般去low所指的，即第一个元素）做为枢轴，用一个变量存放，high向左移动直到找到比枢轴更小的元素，将这个元素放入low的位置，low开始向右移动直到找到一个比枢轴大的元素，放到heigh所指位置，heigh开始移动……循环直到low和high指向同一个位置，最后将枢轴元素放到这个位置

//快速排序
void QuickSort(int A[ ] ,int low,int high){
    if(low<high){//递归跳出的条件
        int pivotpos=Partition(A,low, high); //划分
        QuickSort(A, low, pivotpos-1);//划分左子表
        QuickSort(A, pivotpos+1,high);//划分右子表
    }
}

//用第一个元素将待排序序列划分成左右两个部分
int Partition( int A[] ,int low,int high){
    int pivot=A[low];	//第一个元素作为枢轴
    while( low<high){	//用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 low;		//返回存放枢轴的最终位置
}

8.4 选择排序

8.4.1 简单选择排序

每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列

//简单选择排序
void SelectSort(int A[],int n){
    for(int i=0; i<n-1;i++){	//一共进行n-1趟
        int min=i;	//记录最小元素位置
        for(int 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次
    }
}

//交换
vodi swap(int &a,int &b){
	int temp  = a;
	a = b;
	b = temo;
}

8.4.2 堆排序

思路：把所有⾮终端结点都检查⼀遍，是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整

在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤ $\lfloor n/2 \rfloor$

建⽴⼤根堆（代码）

//建立大根堆
void BuildMaxHeap( int A[] ,int len){
    for(int i=len/2; i>0; i--)//从后往前调整所有非终端结点
        HeadAdjust(A, i,len);
}

//将以k 为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k]; 	//A[0]暂存子树的根结点
    for(int 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];	//被筛选结点的值放入最终位置
}

基于⼤根堆进⾏排序（代码）

//建立大根堆
void BuildMaxHeap(int A[ ],int len)

//将以k为根的子树调整为大根堆
void HeadAdjust(int A[] ,int k,int len)

//堆排序的完整逻辑
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);	//初始建堆
    for(int i=len; i>1;i--){	// n-1趟的交换和建堆过程
        swap(A[i],A[1]); 	//堆顶元素和堆底元素交换
        HeadAdjust(A,1,i-1);	//把剩余的待排序元素整理成堆
    }
}

结论：堆排序是不稳定的

8.4.3 堆的插入和删除

对于⼩根堆，新元素放到表尾，与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌

8.5 归并排序

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

代码实现

int *B=(int *)malloc(n*sizeof(int));//辅助数组B
//A[low...mid]和A[mid+...high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(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])
            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++] ;
}

void MergeSort(int A[] ,int low,int high){
    if ( low<high){
        int mid=( low+high)/2;	//从中间划分
        MergeSort(A,low,mid);	//对左半部分归并排序
        MergeSort(A,mid+1,high);//对右半部分归并排序
        Merge(A,low,mid,high);//归并
    }	//if
}

注意递归调用

8.6 基数排序

基数排序不是基于 “⽐较”的排序算法

基数排序是稳定的

基数排序擅⻓解决的问题：

数据元素的关键字可以⽅便地拆分为 d 组，且 d 较⼩
每组关键字的取值范围不⼤，即 r 较⼩
数据元素个数 n 较⼤

8.7 外部排序

8.7.1 外部排序

数据存放在外存中，需要拿到内存中进行数据操作

构造初始“归并段”：”要求各个⼦序列有序，每次读⼊两个块的内容，进⾏内部排序后写回磁盘

循环往复，16段变为8段，8段变为4段，4变为2段，最终形成一个有序序列

注意：当某一缓冲区数据清空后，要立即将其对应的归并段数据进行填充，然后才能继续进行归并操作

输出缓冲区的数据会放到外存的一个新的位置，不会使用旧的存储位置，当旧的存储数据完成归并后会释放其内存地址

8.7.2 败者树

8.7.3 置换选择排序

首先取满内存工作区，将其中最小的元素放入归并段1，并记录此元素大小，内存工作区少了一个后就立即传入一个新的数据，再进行比较，重复上述操作。如果传入的新数据比记录的minmax小也不用管他，最后直到工作区所有的数据都比minmax小，则说明第一个归并段的构造结束。进行第二个归并段的构造，重复上述操作。

知识回顾与重要考点

设初始待排⽂件为FI，初始归并段输出⽂件为FO，内存⼯作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。置换-选择算法的步骤如下：

从FI输⼊w个记录到⼯作区WA。
从WA中选出其中关键字取最⼩值的记录，记为MINIMAX记录。
将MINIMAX记录输出到FO中去。
若FI不空，则从FI输⼊下⼀个记录到WA中。
从WA中所有关键字⽐MINIMAX记录的关键字⼤的记录中选出最⼩关键字记录，作为新的 MINIMAX记录。
重复③~⑤，直⾄在WA中选不出新的MINIMAX记录为⽌，由此得到⼀个初始归并段，输出⼀个归并段的结束标志到FO中去。
重复②~⑥，直⾄WA为空。由此得到全部初始归并段。

8.7.4 最佳归并树

注意：对于k叉归并，若初始归并段的数量⽆法构成严格的 k 叉归并树，则需要补充⼏个⻓度为 0 的“虚段”，再进⾏ k 叉哈夫曼树的构造。

添加虚段的数量

若（初始归并段数量 -1）% （k-1）= 0，说明刚好可以构成严格k叉树，此时不需要添加虚段

若（初始归并段数量 -1）% （k-1）= u ≠ 0，则需要补充 (k-1) - u 个虚段

结语

该笔记为2024年考研所写，参考王道所写，奈何本人贪玩误事，未能如愿，若有来者见此文章，望再接再厉，莫要半途而废！

如果觉得文章对你有用，请随意赞赏

数据结构-全

http://localhost:8090/archives/86281b69-0628-4f67-86a5-fc60de343e4a

作者

Administrator

发布于

2025-01-03

更新于

2025-01-03

许可协议

CC BY 4.0

数据结构-全

2. 线性表

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

2.2 顺序表

2.2.1 顺序表的定义

2.2.2 顺序表的基本操作

1. 顺序表的插入和删除

2. 顺序表的查找

2.3 单链表

2.3.1 单链表的定义

2.3.2 单链表的基本操作

1. 单链表的插入和删除

2. 单链表的查找

2.3.3 单链表的建立

1. 尾插法

2. 头插法

2.4 双链表

2.4.1 双链表的初始化

2.3.2 双链表的删除

2.3.3 双链表的遍历

2.5 循环链表

2.5.1 循环单链表

2.5.2 循环双链表

2.6 静态链表

2.6.1 静态链表定义

2.6.1 基本操作实现

2.7 顺序表vs链表

3. 栈和队列

3.1 栈

3.1.1 栈的基本概念

3.1.2 顺序栈的实现

3.1.3 共享栈

3.1.4 链栈的实现

3.2 队列

3.2.1 队列的基本概念

3.2.2 队列的顺序实现

1. 队尾指针指向队尾元素的后一个位置 （下一个应该插入的位置）

2. 队尾指针指向队尾元素的位置 （当前插入元素的位置）

3.2.3 队列的链式实现

3.2.4 双端队列

3.3 常见考点

3.3.1 栈的应用——括号匹配

3.3.2 栈的应用——表达式求值1

3.3.3 栈的应用——表达式求值2

3.3.4 栈的应用 ——递归

3.3.5 队列 的应用

3.3.6 特殊矩阵 压缩存储

4. 串

4.1 串的定义和基本操作

4.2 串的存储结构

4.3 朴素模式匹配算法

4.4 KMP算法

4.4.1 求next数组

4.4.2 KMP算法的优化

5.树与二叉树

5.1 树

5.1.1 定义和基本术语

5.1.2 树的性质

5.2 二叉树

5.2.1 二叉树的基本概念

5.2.2 二叉树的性质

5.2.3 二叉树的存储结构

5.3 二叉树的遍历

5.3.1 二叉树的深度优先遍历（DFS）【先/中/后序遍历】

5.3.2 二叉树的广度优先遍历（BFS）【层次遍历】

5.3.3 由遍历序列构造二叉树

5.3.4 线索二叉树

5.3.5 二叉树的线索化

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

中序线索二叉树找中序后继

中序线索二叉树找中序前驱

先序线索二叉树找先序后继

先序线索二叉树找先序前驱（三叉链表）

后序线索二叉树找后序后继（三叉链表）

后序线索二叉树找后序前驱

5.4 树和森林

5.4.1 树的存储结构

5.4.2 树、森林的遍历

5.5 二叉排序（查找）树（BST）

5.5.1 二叉排序树的定义

1. 队尾指针指向队尾元素的后一个位置（下一个应该插入的位置）

2. 队尾指针指向队尾元素的位置（当前插入元素的位置）

3.3.5 队列的应用

3.3.6 特殊矩阵压缩存储

6.2.3 十字链表、邻接多重表

6.6.1 有向⽆环图描述表达式

拓扑排序的实现：