发表于 2022-07-08 更新于 2022-08-06 Valine：本文字数： 49k 阅读时长 ≈ 45 分钟

title: 数据结构与算法

数据结构与算法

¶数据结构

¶基本概念和术语

¶数据

数据：描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合

数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录

数据项：一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位

数据对象：是性质相同的数据元素的集合，是数据的子集

¶结构

不同数据元素之间不是独立的，而是存在特定的关系，而这些关系就是结构

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合

¶逻辑结构与物理结构

逻辑结构是面向问题的，物理结构就是面向计算机的，其基本的目标就是将数据及逻辑关系存储到计算机的内存中

¶逻辑结构

逻辑结构：是指数据对象数据元素之间的相互关系，这也是我们今后需要关注的地方

¶注释

使用示意图表示数据的逻辑结构时，要注意两点：

将每一个数据元素看作一个结点，用圆圈表示
元素之间的逻辑关系用结点之间的连线表示，如果这个给关系是由方向的，那么用带箭头的连线表示

¶集合结构

集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系，类似于数学中的集合

集合结构

¶线性结构

线性结构：线性结构中的数据元素是一对一的关系

线性结构

¶树形结构

树形结构：树形结构中的数据元素之间存在一种一对多的层次关系

树形结构

¶图形结构

图形结构：图形结构的数据元素是多对多的关系

图形结构

¶物理结构——存储结构

物理结构：是指数据的逻辑结构在计算机中的存储形式

数据的存储结构应正确反映数据元素之间的逻辑关系

¶顺序存储结构

顺序存储结构：是把数据元素存放在地址连续的存储单元中，其数据间的逻辑关系和物理关系是一致的

顺序存储结构

¶链式存储结构

链式存储结构：是把数据元素存放在任意的存储单元中，这组存储单元可以是连续的，也可以是不连续的

链式存储结构

此时数据元素的存储关系不能反映其逻辑关系，所以需要一个指针存放数据元素的地址，通过指针可以找到相关联数据元素的地址。相较于顺序存储结构，链式存储结构更为灵活，也更适合处理需要变化的结构，比如排队，当队伍中需要添加或者删去成员时，使用顺序存储结构则需要处理大量数据

¶抽象数据类型

¶数据类型

数据类型：是指一组性质形同的值的集合及定义在此集合上的一些操作的总称

¶抽象数据类型

抽象数据类型：是指一个数据建模及定义在该模型上的一组操作，比如整型

抽象数据类型标准格式

¶算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列。并且每条指令表示一个或多个操作

算法的基本特性：输入、输出、有穷性、确定性、可行性

算法的基本要求：

正确性
可读性：便于阅读、理解和交流
健壮性：当输入数据不合法时算法能做出相关处理
时间效率高和存储量低

¶算法时间和空间复杂度

算法时间复杂度定义
$$
O(1)叫做常数阶、O(n)叫做线性阶、O(n^2)叫做平方阶
$$

¶时间复杂度的计算

推导大O阶：

用常数1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶项存在且不是1，则去除与这个项相乘的常数

//常数阶
int sum=0,n=100;
sum=(1+n)*n/2;
sum=(1+n)*n/2;
sum=(1+n)*n/2;
sum=(1+n)*n/2;
//这里代码的执行次数和问题的大小n无关，所以为常数，也就是O(1)

//线性阶
for(int i=0;i<n;++i)
{
    //时间复杂度为O(1)的程序步骤
}
//以上代码会执行n次，所以位O(n)

//对数阶
int count=1;
while(count<n)
{
    count=count*2;
}
//程序不再执行的条件是2^(count)>=n，也就是count=log2n，所以这个循环的时间复杂度为O(logn)

//平方阶
for(int i=0;i<n;++i)
{
    for(int j=0;j<n;++j)
    {
        //时间复杂度为O(1)的程序步骤
    }
}
//因为上述程序为嵌套循环，所以会执行n*n次，所以时间复杂度为O(n^2)

//对于下述循环嵌套，时间复杂度计算
for(int i=0;i<n;++i)
{
    for(int j=i;j<n;++j)
    {
        //时间复杂度为O(1)的程序步骤
    }
}
//对于上述程序，我们先计算程序的执行次数，因为外层循环执行次数必定为n，主要看内层循环，内层循环执行次数总和为n+(n-1)+(n-2)+……=(n+1)/2，最终得到n^2/2+n/2
//按照上面的大O推导法，1、没有加法常数不予考虑，2、只保留最高阶也就是n^2/2，3、去除这个项的系数，得到n^2，所以时间复杂度为O(n^2)

常见的时间复杂度

¶空间复杂度的计算

算法的空间复杂度通过计算算法所需要的存储空间实现

主要是数组大小，变量只占一个存储单元

¶线性表

线性表：零个或多个数据元素的有限序列，元素之间是有序的线性表的数学语言定义

所以线性表元素的个数n定义为线性表的长度，当n=0时为空表

在较复杂的线性表中，一个数据元素可以由若干个数据项组成

复杂线性表

¶线性表的抽象数据类型

前面说过抽象数据类型分为数据和操作

在这里线性表的抽象数据类型定义如下

ADT 线性表(List)
    DATA
    	线性表的数据对象集合为(a1,a2,a3……，an)，每个元素的类型均为DataType。除了第一个元素a1外，其余元素都有且只有一个直接前驱元素，除最后一个元素外，其余元素都有且只有一个直接后继元素。数据元素之间的关系是一对一的关系
    Operation
    	InitList(*L)	//初始化操作，建立一个空的线性表
    	ListEmpty(*L)	//若线性表为空，返回true，否则返回false
    	ClearList(*L)	//将线性表清空
    	GetElem(L,i,*e)	//将线性表L中的第i个位置元素值返回给e
    	LocateElem(L,e) //在线性表L中查找和e相等的元素，如果查找成功，返回该元素在表中的序号表示成功，否则返回0表示失败
    	ListInsert(*L,i,e)	//在线性表L的第i个位置擦汗如新元素e
    	ListDelete(*L,i,*e)	//删除线性表L中的第i个未知元素，并用e返回其值
    	ListLength(L)	//返回线性表L的元素个数
endADT

以上只是线性表的基础操作，对于复杂的一些操作可以分解为简单的操作，比如求A和B集合的并集这一操作可以分解为遍历B表，将A表中不存在的元素插入到A表中

¶线性表的顺序存储结构

线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素

描述顺序存储结构需要三个特性：

存储空间的起始位置：数组data，他的存储位置就是存储空间的存储位置
线性表的最大存储容量：数组长度MaxSize
线性表的当前长度：length

¶顺序存储结构的插入与删除

这两者其实是比较麻烦的，对于插入数据，插入位置之后的元素都需要后移，删除则为前移。

插入算法的思路：

如果插入位置不合理，抛出异常
如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量
从最后一个元素开始向前遍历到第i个位置，分别将他们往后移动一个位置
将要插入的元素填入位置i处
表长+1

删除算法也是类似的

线性表的优缺点

¶线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，由于是任意的，我们还需要存储当前元素的后继元素地址

单链表的定义

一般会在单链表的第一个结点前附设一个头结点，在其数据域存储线性表的长度，然后让头结点的指针指向第一个结点

头指针与头结点的异同

为了更好地理解，贴出下图

¶单链表的读取、插入和删除

#include<stdio.h>
#include<stdlib.h>
typedef struct Node//类型
{
	int data;//数据域
	struct Node* next;//指针域
}List;//名称

List* InsertNode(List* list)//头插法
{
	for (int i = 0; i < 10; ++i)
	{
		List* tmp = (List*)malloc(sizeof(List));
		tmp->data = i;
		tmp->next = list->next;
		list->next = tmp;
	}
	return list;
}
List* CreateList()
{
	List* Node = (List*)malloc(sizeof(List));
	Node->next = NULL;//创建空的头结点
	return InsertNode(Node);//插入结点
}

void PrintList(List* Linklist)
{
	while (Linklist->next != NULL)//第一个是空结点，所以先指向第一个结点
	{
		Linklist = Linklist->next;//遍历单向链表
		printf("%d\n", Linklist->data);
	}
}

List* DeteleNode(List* Linklist)
{
	int goal = 3;//删除结点需要先记录前一个结点的位置
	List* p = Linklist, * q;//初始化p用于遍历链表
	while (p->next != NULL)
	{
		if (p->next->data == goal)//当前节点下一结点的值为3
		{
			q = p->next;
			p->next = q->next;
			free(q);
			break;
		}
		p = p->next;
	}
	
	return Linklist;//返回的是头节点
}
//尾插法
List* InsertBytail(List* list)
{
	List* tmplist = list;
	for (int i = 0; i < 10; ++i)
	{
		List* tmp = (List*)malloc(sizeof(List));
		tmp->data = i;
		tmp->next = NULL;//创建新节点
		//从尾部插入
		tmplist->next = tmp;
		tmplist = tmplist->next;
	}
	return list;
}

int main()
{
	List* Linklist;
	Linklist= CreateList();
	//PrintList(Linklist);
	Linklist=DeteleNode(Linklist);
	PrintList(Linklist);
	return 0;
}

链表创建时可以使用尾插法和头插法，尾插法就是创建的结点从尾部插入，而头插法则反之

¶静态链表

即使用结构体数组来替代指针来描述单链表

首先让结构体数组拥有两个成员，data和cur。数据域data原来存放数据元素，也就是我们要处理的元素。而游标cur相当于单链表中的next指针，存放该元素的后继元素在数组中的下标，但是为了方便插入数据，通常需要把数组建立得大一些

#define MAXSIZE 1000
typedef struct
{
    ElemType data;
    int cur;//游标Cursor，为0时表示无指向
}Component,StaticLinkList[MAXSIZE];

同时我们需要对第一个元素和最后一个元素进行特殊元素处理，不存放数据。我们通常把未被使用得数组元素称为备用链表

数组第一个元素即下标为0的元素cur就存放备用链表(空位置)的第一个结点的下标。而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表的头结点的作用

¶静态链表的插入和删除操作

前面可知，动态链表结点的申请和释放分别借用malloc和free函数。而在静态链表中，操作的是数组，为了区分哪些数组是被使用过的，我们可以将所有未被使用过的以及已经被删除的分量用游标链成一个备用的链表（使cur指向下一个空位置）

静态链表

¶静态链表插入

首先我们需要在备用链表中找到一个空位置，相当于(malloc)，然后将该位置的元素加入数据链表中此时当前的空位置会被占用，所以list[0]->cur也需要改变。

¶静态链表删除

和插入一样，都需要对备用链和数据链进行更改

#include<stdio.h>
#include<stdlib.h>
#define Maxsize 100
typedef struct Node
{
	int data;
	int cur;
}Component, StaticList[Maxsize];

int Malloc(StaticList list[])
{
	//找到备用链表中的空位置
	int i = list[0]->cur;
	if (list[0]->cur)//如果备用链表已被使用过
	{
		list[0]->cur = list[i]->cur;//因为当前位置被占用，所以从备用链表中解除
		return i;//返回空位置的下标
	}
	return 0;
}

int CreateList(StaticList list[])
{
	for (int i = 0; i < Maxsize - 1; ++i)//初始化备用链表，此时空间都没被使用，所以list[0]->cur为0
	{
		list[i]->cur = i + 1;//cur相当于next，指向下一个结点
	}
	//结尾的结点的cur赋值为0
	list[Maxsize - 1]->cur = 0;
	//从备用链表中获取空结点的位置,从而创建数据链表的头节点
	int k = Malloc(list);
	int head = k;//返回头节点的位置
	for (int i = 0; i < 10; ++i)
	{
		//申请数据结点
		int s = Malloc(list);
		list[s]->data = i;
		k = s;
	}
	list[k]->cur = 0;//数据链表的末尾结尾以0结尾，表示cur指向NULL
	return head;
}

void PrintList(StaticList list[], int head)
{
	head = list[head]->cur;//因为第一个是头结点无数据，所以跳过
	while (list[head]->cur != 0)
	{
		printf("%d\n", list[head]->data);
		head = list[head]->cur;
	}
	printf("%d\n", list[head]->data);
}

void InsertNode(StaticList list[])
{
	//插入的位置，首先在备用链表中获取空结点的下标
	int k = Malloc(list);
	list[k]->data = 10;//给指定位置的元素赋值，下一步将其从中间插入，同时备用链表也需要改变
	list[0]->cur = list[k]->cur;//这样就实现了不移动元素在中间插入数据
	list[4]->cur = k;
	list[k]->cur = 5;
}

void DeleteNode(StaticList list[], int head)
{
	head = list[head]->cur;
	while (list[head]->cur != 0)
	{
		if (list[list[head]->cur]->data == 10)//当前结点的后一个结点数值为10
		{
			//当找到我们刚才插入的结点时，备用链表和数据链表都需要进行做出改变
			//首先改变数据链表
			list[head]->cur = list[list[head]->cur]->cur;//跳过下一结点
			//接下来改变备用链表，将其看作备用链表的结点
			int tmp = list[0]->cur;
			list[0]->cur = list[head]->cur;
			list[list[head]->cur]->cur = tmp;
			break;
		}
		head = list[head]->cur;//后移
	}
}
int main()
{
	StaticList list[100];
	int head = CreateList(list);
	InsertNode(list);
	DeleteNode(list, head);
	PrintList(list, head);
	InsertNode(list);
	PrintList(list, head);
	return 0;
}

静态链表的优缺点

¶循环链表

之前提到的单链表都只存储向后的指针，所以没办法找到他的前驱节点。而我们只要将链表改为一个环就可以解决这样的问题，而这样的链表就是循环链表——解决了一个问题（如何从当中的一个结点出发，访问到链表的全部结点）

将单链表中终端结点的指针由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为但循环链表，简称循环链表

循环链表和单链表的差异

循环链表如下

循环链表

在单链表中，我们有了头结点时，可以用O(1)的时间访问第一个结点，但是要访问到最后一个结点则需要O(n)时间，因为所有结点都要访问一遍。

我们可以改造一下上面的循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表

¶两个循环链表的合并

有了尾结点合并时就会比较简单

流程图

rearA和rearB是两条循环链表的尾指针

p=readA->next;//保存A表的头结点
rearA->next=rearB->next->next;//将B链的第一个结点（不是头结点）赋值给rearA->next
readB->next=p;
free(p)//释放p

¶双向链表

在单向链表中，由于存在next指针，所以我们访问下一节点的时间复杂度为O(1)，而访问前一个结点则需要O(n)，所以设计出了双向链表。

双向链表是在单链表的每个结点中，再设置一个指向其前驱节点的指针域，所以在双向链表中的每个结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

//双向链表的存储结构
typedef struct DulNode
{
	int data;
	struct DulNode*prior;//直接前驱结点
	struct DulNode*next;//直接后继结点
}DulNode,*DuLinkList;

双向链表也可以是循环表

双向循环链表

¶双向链表的查找、插入和删除

查找的话只需要往一个方向遍历即可，不需要使用两个指针。

但是在插入和删除的时候需要同时对两个指针变量作出修改

插入的流程图

在编写代码时一定要注意顺序

双向链表是使用空间换取时间的例子。

¶栈

栈是限定仅在表尾进行插入和删除操作的线性表

栈顶——允许插入和删除，栈顶的另一端就是栈底，不含任何元素的叫空栈。栈又被称为后进先出的线性表，简称LIFO结构

栈的插入操作叫作进栈，也可以叫做压栈、入栈；栈的删除操作叫做出栈

出栈入栈图

相同的元素出栈次序的变化是很多的

出入栈的例子

¶栈的抽象数据类型

对于栈的插入和删除操作，我们改名为push和pop

入栈(push)是先移动栈顶指针再压入元素，出栈(pop)是弹出元素再移动栈顶指针

ADT 栈
DAta
	同线性表，元素具有相同的类型，相邻元素具有前驱和后继关系
Opreation
	InitStack(*S);//初始化操作，建立一个空栈
	DestroyStack(*S);//若栈存在，则销毁他
	ClearStack(*S);//将栈清空
	StackEmpty(S);//判断栈是否为空
	GetTop(S,*e);//若栈不为空，用e返回栈顶元素
	Push(*S,e);//入栈
	Pop(*S,*e);//出栈
	StackLength(S);//返回栈S的元素个数
endADT

因为栈是线性表，所以也具有顺序和链式存储方式

¶栈的顺序存储及实现

栈的顺序存储简称为顺序栈，线性表的顺序存储是用数组表示的，我们将栈底定义在数组下标为0的位置，并且使用top变量来指示栈顶的位置，当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定为top等于-1

//栈的结构体定义
typedef struct
{
	int data[MAXSIZE];
	int top;//用于栈顶指针
}Sqstack;

出栈入栈的代码也是相对简单的

#define MaxSize 100
typedef struct
{
	int data[MaxSize];
	int top;//栈顶指针
}Sqstack;
int Push(Sqstack* stack, int e)
{
	if (stack->top == MaxSize - 1)
	{
		return 0;//判断是否满栈
	}
	else
	{
		//先移动栈顶指针，再压入
		stack->top++;
		stack->data[stack->top] = e;
	}
	return 1;
}

int Pop(Sqstack* stack, int final)
{	//判断是否为空栈
	if (stack->top == -1)
	{
		return 0;
	}
	else
	{
		final = stack->data[stack->top];
		stack->top--;
	}
}

¶两栈共享空间

在前面的例子中存在很大的一个缺陷，那就是需要事先确定数组存储空间大小，对于一个栈我们需要设计出合适大小的数组来处理，但是对于两个相同类型的栈，我们却可以做到最大限度地利用其是先开辟地存储空间来进行操作

我们可以使用一个数组类存储两个栈

数组存储两个栈

此时我们需要两个栈顶指针top1和top2，当top+1==top2时表示两个栈都满了

//两栈共享空间结构
typedef struct
{
	int data[MAXSIZE];
	int top1;
	int top2;
}SqdoubleStack;

对于两栈共享空间的push和pop，还需要有一个用于判断是栈1还是栈2的参数stackNumber

两栈共享空间push操作

两栈共享空间pop操作

¶栈的链式存储结构

栈的链式存储结构，简称为链栈

对于链栈来说不需要头结点，因为已经有栈顶了

对于空栈来说链表的原定义头指针指向NULL，那么链栈的空就是top=NULL

typedef struct StackNode//栈的结点结构
{
	int data;
	struct StackNode* next;//栈的结点
}StackNode, * LinkStackPtr;

typedef struct LinkStack//栈的链表结构
{
	LinkStackPtr top;//栈顶
	int count;
}LinkStack;

¶链栈的入栈和出栈

int Push(LinkStack* S, int e)
{
	//创建一个新结点
	LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
	s->data = e;//结点赋值
	s->next = S->top;//将新结点与原本的栈顶相连
	S->top = s;//栈顶指向新的结点
	S->count++;
	return 1;
}

int Pop(LinkStack* S, int e)
{
	LinkStackPtr p;
	//判断链表是否为空
	if (S->top == NULL)
	{
		return 0;
	}
	e = S->top->data;
	p = S->top;//将栈顶结点赋值给p，待会free掉
	S->top = S->top->next;//使得栈顶指针后移一个结点
	free(p);
	S->count--;
	return 1;

}

顺序栈和链栈的对比

¶栈的作用

¶栈的应用

¶递归

递归一个典型的例子就是斐波那契数列（每一项的元素都是前两项元素之和）

斐波那契数列表达式

这里可以使用递归计算，会比较简单

int Fbi(int n)
{
	if (n < 2)
	{
		return (n == 0) ? 0 : 1;
	}
	return Fbi(n - 1) + Fbi(n - 2);
}
int main()
{
	for (int i = 0; i <= 40; ++i)
	{
		printf("%d\n", Fbi(i));
	}
	return 0;
}

斐波那契数列的执行过程

递归的定义：间接地调用自己的函数，同时我们需要注意要有递归的出口，而对于函数的传参和返回值都是使用栈来实现的

¶四则运算表达式求值

带括号的四则运算

但是光按照括号来判断是不够的，所以采用以下方法

就是遇到数字就入栈，遇到符号就从栈中取出两个元素（注意先后），做运算后再入栈

具体过程

但是上面的方法需要先将中缀表达式先转为后缀表达式

中缀表达式先转为后缀表达式过程

¶队列

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列是一种先进先出的线性表，简称FIFO，运行插入的一端称为队尾，允许删除的一端叫做队头

队列的结构图

¶队列的抽象数据类型

同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾插入，删除数据只能在队头进行

ADT 队列
Data
	同线性表，元素具有相同的类型，相邻元素具有前驱和后继关系
Operation
	InitQueue(*Q);//初始化操作，建立一个空队列Q
	DestroyQueue(*Q);//若队列Q存在，则销毁他
	ClearQueue(*Q);//将队列清空
	QueueEmpty(*Q);//判断队列是否为空
	GetHead(Q,*e);//若队列存在且非空，用e返回队列Q的队头元素
	EnQueue(*Q,e);//若队列Q存在，插入新元素e到队列Q中并成为队尾元素
	DeQueue(*Q,*e);//删除队列Q中队头元素，用e返回其值
	QueueLength(Q);//返回队列Q的元素个数
endADT

¶循环队列

队列作为特殊的线性表也有顺序存储和链式存储

¶队列顺序存储的不足

如果以数组下标为0的位置作为队头，那么入队时只需要在队尾追加元素即可，但是出队的话比较复杂，因为队头之后的所有元素都需要前移，时间复杂度为O(n)

但我们可以不去限制队列的元素必须存储在数组的前n个元素，也就是说队头不需要一定在下标为0的位置

为了避免当只有一个元素时队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时队列为空

队列顺序存储的出队和入队

可以看出当出队后再进行入队时发生了数组越界的情况（无法入队），而数组前两个位置还是空的，这就是假溢出，这时候就需要循环队列了

¶循环队列的定义

队列的头尾相接的顺序存储结构叫做循环队列

按照上面的例子，当入队a5时，可以将rear指向数组下标为0的位置

rear指向0下标处

这样我们就可以继续入队了

此时新的问题出现了，空队列时front等于rear，当队列满的时候也是front=rear，为了区分，有两种方法

设置一个标志量flag，当front==rear，且flag=0时为队列空，当flag=1时为队列满
可以修改队列满的条件，当数组还剩下一个空闲单元时我们就认为队列满了

条件2

下面重点讨论第二种方法

由于rear可能比fornt大，也可能小，所以不能仅凭二者相差1来判断是否为满队列（因为可能相差整整一圈）

设队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1)%QueueSize==front

队列长度计算

//循环队列结构体定义
typedef struct
{
	int Data[MAXSIZE];
	int front;//头指针
	int rear;//尾指针，若队列不空指向队列尾元素的下一个位置
}SqQueue;

//初始化循环队列
int InitQueue(SqQueue *Q)
{
    Q->front=0;
    Q->rear=0;
    return 1;
}

//循环队列求长度
int QueueLength(SqQueue Q)
{
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

//循环队列的入队操作，首先判断是否为满队列
int EnQueue(SqQueue *Q,int e)
{
    if((Q->rear+1)%MAXSIZE==Q->front)
    {
        return 0;
    }
    Q->data[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAXSIZE;//尾指针后移，如果为最后则转到数组头部
    return 1;
}

//循环队列的出队操作，队头出队
int DeQueue(SqQueue *Q,int e)
{
    //判断队列是否为空
    if(Q->front==Q->rear)
        return 0;
    e=Q->data[Q->front];
    //队头后移
    Q->front=(Q->front+1)%MAXSIZE;
    return 1;
}

¶队列的链式存储结构

队列的链式存储结构其实就是线性表的单链表，只不过他只能尾进头出而已。我们称之为链队列

为了操作方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。

链队列

typedef struct QNode//结点结构
{
	int data;
	struct QNode* next;
}QNode,*QueuePtr;

typedef struct
{//队列的链表结构
	QueuePtr front, rear;//队头和队尾指针
}LinkQueue;

¶链队列的入队和出队操作

int EnQueue(LinkQueue* Q, int e)
{
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	s->data = e;
	s->next = NULL;//初始化结点
	//链接上队列，队尾插入
	Q->rear->next = s;
	Q->rear = s;//把当前结点设置为队尾结点
	return 1;
}

int DeQueue(LinkQueue* Q, int e)
{
	QueuePtr p;
	if (Q->front == Q->rear)
	{
		return 0;
	}
	//使用变量p暂时存储需要删除的结点
	p = Q->front->next;
	e = p->data;
	Q->front->next = p->next;//队头指针后移
	if (Q->rear == p)//如果队尾指向第一个数据结点，则删除之后恢复空队列
	{
		Q->rear = Q->front;
	}
	free(p);
	return 1;

}

——————下划线——————

刷题巩固一下我的🐖脑

¶串

串是由零个或者多个字符组成的有限序列，又名叫字符串

¶串的抽象数据类型

相较于线性表的更关注单个元素的操作，比如查找删除插入一个元素，但串中更多的是查找子串的位置、得到指定位置的子串替换子串等操作

ADT 串
Data
	串中的一个元素仅由一个字符组成
Operation
    StrAssion(T,*chars);//生成一个其值等于字符串常量chars的串T
    StrCopy(T,S);//串S存在，由串S复制得到串T
    ClearString(S);//串S存在，将该串清空
    StringEmpty(S);//判断串是否为空
	StrLength(S);//返回串S的元素个数，即串的长度
	StrCompare(S,T);//字符串比较，若S>T则返回值>0,S=T,返回值=0，S<T,返回值<0，
	Concat(T,S1,S2);//用T返回由S1和S2连接而成的新串
	SubString(Sub,pos,len);//用Sub返回串S的第pos个字符串起长度为len的子串
	Index(S,T,pos);//若主串S中存在和串T值相同的子串，则返回他在主串S中第pos个字符之后第一次出现的位置，否则则返回0
	Replace(S,T,V);//用V替换主串S中出现的所有与T相等的不重叠的子串
	StrInsert(S,pos,T);//在串S的第pos个字符之前插入串T
	StrDelete(S,pos,len);//从串S中删除第pos个字符起长度为len的子串
endADT

¶串的存储结构

¶串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的，顺序存储结构需要规定数组的大小，但是涉及两串的连接，新串的插入以及字符串的替换都会超过数组的最大长度Maxsize，于是对于串的顺序存储，串值的存储空间可在程序执行过程中动态分配而得，也就是使用堆

¶串的链式存储结构

对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个数据元素是一个字符，如果仍使用一个结点来存储一个字符，会造成大量的空间浪费。因此一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以使用其他非串值字符进行补齐，由于链式存储结构需要确定一个结点存储多少个字符，比较麻烦，所以一般使用顺序存储结构

¶朴素的模式匹配算法

也就是BF算法

子串的定位操作通常称作串的模式匹配

就是对主串的每一个字母作为子串的开头，与要匹配的字符串进行匹配。

int Index(string S, string T, int pos)
{
	int i = pos;
	int j = 0;
	while (i <strlen(S) && j <strlen(T))//下标小于子串和主串长度
	{
		if (S[i] == T[j])//当前位置的字符串匹配成功则继续往后匹配
		{
			++i;
			++j;
		}
		else//
		{
			i = i - j + 1;//i返回上次匹配首位的下一位
			j = 1;//重新回到子串首位进行匹配
		}
	}
	if (j > strlen(T))
	{
		return i - strlen(T);
	}
	else
		return 0;
}

当每次不成功的匹配都发生在串T的最后一个字符，此时时间复杂度会非常大，可见这种匹配方式较为低效

¶KMP模式匹配算法

KMP常用于相同字符较少的字符串中，效率较高

可以看到由于望江楼前三个不同且成功匹配，那么第一个红框内的判断是多余的，我们可以直接进行回溯进行比较，而i都是往后的所以不需要回溯，只需要回溯j指针

下图就是KMP算法的匹配流程

我们把T串每个位置的j值的变化定义为一个数组next

上面的是针对子串T中无重复元素的，下面我们来看一下T串中含有重复串如何使用KMP算法

首先需要计算未匹配位置前字符串的前缀和后缀，其最长前缀、后缀有共同元素"望江"，长度为2，所以j指针回溯为2，也就是将"楼"字（下标为2）对应上次未成功匹配的位置。

这是因为由于前缀和后缀具有相同的元素的话，j指针移动相同元素对应长度就可以做到匹配。（看图就可以理解了）

接下来我们可以看一下一段快完善的KMP算法代码

int IndexKmp(char* S, char* T)
{
	int* next = genNext(T);//生成next表
	int i = 0, j = 0;
	while (i < strlen(S) && j < strlen(T))
	{
		if (S[i] == T[j])
		{
			i++;
			j++;//匹配的话，模式串和原串指针都后移
		}
		else {
			j = next[j];//j指针回溯
		}
	}
	return j = strlen(T) ? i - j : 1;//有无匹配的字符串
}

¶next的手动计算

计算next数组前，我们首先要先知道前后缀是什么，举个例子就能明白了，假如字符串S为"abcdef"，那么S的前缀集合为{a,ab,abc,abcd,abcde}，后缀集合为{f,ef,def,cdef,bcdef}

接下来我们手动计算next数组

对于下标为5的字符"江"，其前面的字符串是"望江楼上望"，前后缀相同的元素为"望"，长度为1，所以该位置的next数组元素为1，也就是说下次匹配时将从下标为1的位置进行匹配。

从这里可以看出，如果第一个模式串元素不匹配，那么next[0]=0，由于串S的i指针不会移动，此时会陷入while的死循环。

所以对next数组进行改进，且修改KMP算法的代码（其实多加一个特判即可）

我们在0下标前添加一个万能字符，表示可以和所有字符进行匹配，然后改next[0]=-1，这样的话当第一个元素不匹配时，d=next[0]=-1，因为-1下标处为万能字符，所以必定匹配，进入if条件中

代码修改为

int IndexKmp(char* S, char* T)
{
	int* next = genNext(T);//生成next表
	int i = 0, j = 0;
	while (i < strlen(S) && j < strlen(T))
	{
		if (j == -1 || S[i] == T[j])
		{
			i++;
			j++;//匹配的话，模式串和原串指针都后移
		}
		else {
			j = next[j];//j指针回溯
		}
	}
	return j = strlen(T) ? i - j : 1;//有无匹配的字符串
}

¶next的代码计算

就是计算出相同的最长前后缀的长度，这个过程和我们进行子串匹配极为类似，所以也可以采用类似的思想

先贴代码

int* genNext(char* T)
{
	int* next = (int*)calloc(strlen(T),sizeof(int));
	next[0] = -1;
	int i = 0, j = -1;//此时比较的母串和模式串都是其本身
	while (i < (int)strlen(T) - 1)
	{
		if (i == -1 || T[i] == T[j])
		{
			i++;
			j++;//因为已经++，所以接下来作比较就是下一个字符了
			next[i] = (T[i] != T[j] ? j : next[j]);
		}
		else {
			j = next[j];
		}
	}
	return next;
}

接下来我们看看是如何得到这段代码的

分为两种情况

匹配：next[i+1]=next[i]+1=j+1;
失配：j=next[j];

将其自身与自身进行匹配，找到相同的字符就相当于找到了相同的真前缀和真后缀，画个图进行理解

当我们成功匹配时，由于是自身进行匹配，那么两个位置处的字符相等，而这两个字符分别是前后缀。（此时next为1）在此基础上，长串指针和短串指针都后移继续进行匹配，若仍匹配成功

由于前一个匹配成功，后一位置也匹配成功，所以next的值为前一位next+1，也就是next[i+1]=next[i]+1;

当失配时，j指针需要回溯

假如在当前位置失配，d指针回溯的位置应该是d位置处的next值，即下图

这样即可继续往后匹配

¶例子

从当前位置红色区域开始，若下标为10的位置成功匹配，那么"流"位置的next值为4+1

但当前位置的字符失配，所以j指针需要回溯，回溯的距离为相同最大真后前缀长度，也就是"望江"的长度，代码表示为j=next[j]，如下图所示**

然后接着进行匹配，还是失配，j指针继续回溯，此时无相同真前缀和真后缀，所以回溯到0位置，"江"和"望"依旧无法匹配，所以"流"位置的next值为0

¶改进

在开始讲之前我们先来看一个KMP的匹配

可以看到如果子串为"望江楼望江流"时，红框中第一次是"望"和","作比较，第二次也是，这样子是重复的。于是需要对next表进行改进，如果当前两字符相等，该位置回溯的值（也就是next数组中的值）需要继续往前找相同前后缀

原来的next表为

由于下标为4的"望"的next为0，而T[0]=“望”，所以修改为T[0]处的next值，下标为5的"江"同理改为0

修改之后的next表为

¶树

之前接触的一对一的线性结构，但是我们会遇到很多一对多的问题，这时候就需要研究这种数据结构——树

树是n(n>=0)个结点的有限集，n=0时为空树。在任意一棵非空树中：1、有且仅有一个特定的称为根的结点；2、当n>1时，其余结点可分为m个互不相交的有限集T1、T2、……，其中每一个集合本身又是一棵树，并称为根的子树

树的结构图

在上图中，有左子树T1和右子树T2

对于树的定义需要注意两点

根节点是唯一的
子树的个数没有限制，但他们一定是互不相交的

不符合树的定义

¶结点分类

结点拥有的子树数称为结点的度，度为0的结点称为叶结点或者终端结点，其他结点称为非终端结点或者分支结点。根结点和分支结点都被称为内部结点。树的度是树内各结点的度的最大值

树的结点分类

¶结点间的关系

结点的子树的根称为该结点的孩子，该结点即为孩子的双亲。同一双亲的孩子之间互称兄弟，结点的祖先是从根到该结点所经分支上的所有结点

树的关系图

¶树的其他相关概念

¶结点的层次

¶有序与无序

¶森林

¶树结构

根结点：无双亲，唯一
叶结点：无孩子，可以多个
中间节点，一个双亲多个孩子

¶树的抽象数据类型

相较于线性结构，树的操作有很大的变化

ADT 树
Data
	树是由一个根节点和若干棵子树构成，树中结点具有相同的数据类型和层次关系
Operation
	InitTree(*T);//构造空树
	DestroyTree(*T);//销毁树
    CreationTree(*T,definition);//按definition中给出树的定义来构造树
	ClearTree(*T);//若树T存在，则将树T清为空树
	TreeEmpty(*T);//判断树是否为空
	TreeDepth(*T);//计算树的深度
	Root(T);//返回T的根结点
	Value(T,cur_e);//返回树T中cur_e的值
	Assign(T,cur_e,value);//赋值
	Parent(T,cur_e);//返回其双亲，根节点除外
	LeftChild(T,cur_e);//若cur_e为树的非叶结点，则返回它的最左孩子，否则返回空
	RightSibling(T,cur_e);//返回该结点的右兄弟
	InsertChild(*T,*p,i,c);//p指向树T的某个结点，i为所指结点p的度加上1，非空树c与T不相交，操作结果为插入c为树T中p指结点的第i棵子树
	DeleteChile(*T,*p,i);//删除T中p所指结点的第i棵子树
endADT

¶树的存储结构

由于树的某个结点可以有多个孩子，所以我们无论以何种顺序将树中所有结点存储到数组中，结点的存储位置都无法直接反映逻辑关系

所以需要充分利用顺序存储和链式存储的特点实现对树的存储结构的表示，有三种表示法

双亲表示法
孩子表示法
孩子兄弟表示法

¶双亲表示法

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置，也就是说每个结点除了知道自己是谁以外，还知道它的双亲在哪

结点结构

其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。

//树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100
typedef struct PTNode
{//结点数据
    int data;//结点数据
    int parent;//双亲位置
}PTNode;

typedef struct
{//树结构
    PTNode nodes[MAX_TREE_SIZE];//结点数组
    int r,n;//根的位置和结点数
}pTree;

由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，这就意味着我们所有的结点都存有它双亲的位置

树结构和树双亲表示

这样我们可以根据结点的parent指针很容易找到它的双亲结点，时间复杂度为O(1)，直到当parent=-1，表示此时找到了树结点的根。但如果我们想知道结点的孩子是什么，则需要遍历树。

我们可以增加一个结点最左边孩子的域，也就是长子域，这样就可以很容易得到结点的孩子下标。对于没有孩子的结点，长子域设置为-1

如图所示

如此一来，对于有0、1、2个孩子的节点来说，这样的结构解决了要找结点孩子的问题。

如果更关注兄弟之间的关系，双亲表示法无法体现，此时需要增加一个右兄弟域，也就是说，每一个结点如果它存在右兄弟，则记录下右兄弟的下标，不存在右兄弟则为-1

我们需要根据不同的情况来选择存储结构

¶孩子表示法

换一种考虑方式，由于树中的每个结点可能有多棵子树，，可以使用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的结点，这就是多重链表表示法。不过树的每个结点的度，也就是他的孩子个数是不同的，下面设计两种方案

¶方案一

指针域的个数等于树的度

结构链表

可以看到A结点存储两个指针，分别指向其子树B和C，其他也是这样

由于每个结点都需要存储度个数的指针，所以对于空间浪费较大，但当树中各结点的度相距较小时，这样反而是优点（因为存储的空间被充分利用了）

¶方案二

每个结点指针域的个数等于该结点的度，同时我们专门取一个位置来存储结点指针域的个数

方案二结构流程图

这种方法克服了浪费空间的缺点，但由于各个结点的链表是不同的结构，加上要计算结点的度的数值，会消耗较多时间。

¶孩子表示法

把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中

为此我们设计两种结点结构，一种是孩子链表的孩子结点

孩子结点

其中child是数据域，用于存储某个结点在表头数组中的下标，next是指针域，用于存储某结点的下一个孩子结点的指针

另一种是表头数组的表头结点

表头结点

孩子表示法的结构定义代码

//树的孩子表示法结构定义
#define MAX_TREE_SIZE 100
typedef struct CTNode
{
    int child;//孩子结点的下标
    struct CTNode*next;//next指针
}*ChildPtr;

typedef struct
{//表头结构
    int data;
    ChildPtr firstchild;
}CTBox;

typedef struct//树结构
{
    CTBox nodes[MAX_TREE_SIZE];//结点数组
    int r,n;//根的位置和结点数
}CTree;

这样查找某个结点的孩子或者兄弟，只需要查找这个结点的孩子单链表即可。当我们需要遍历整棵树也只需要对头结点的数据进行循环即可

但是当我们想要知道某个结点的双亲是谁时需要整棵树遍历才行。所以可以将双亲表示法和孩子表示法结合一下

双亲孩子表示法

¶孩子兄弟表示法

刚才我们分别从双亲的角度和孩子的角度研究树的存储结构，接下来我们从树结点的兄弟角度来看，但是对于树这种层级结构，之研究结点的兄弟是不行的。这是因为任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟

结点结构

代码如下

//树的孩子兄弟表示法结构定义
typedef struct CSNode
{
    int data;
    struct CSNode*firstchild,*rightsib;
}CSNOde,*CSTree;

对于图6-4-1的树来说，孩子兄弟表示法结构实现的示意图如下

数据后跟的分别是第一个孩子结点的指针和第一个孩子结点的右兄弟结点指针。

这种表示法，给查找某个结点的某个孩子带来了方便，只需要通过firstchild找到此结点的长子，然后再通过长子结点的rightsib找到它的二弟，接着一直下去，直到找到具体的孩子，当然如果想找到某个结点的双亲，该表示法是有缺陷的。所以可以再增加一个parent指针域来解决快速查找双亲的问题

将孩子兄弟表示法的结构体变形一下就成了这个样子，也就是二叉树

¶二叉树

对于在某个阶段都是两种结果的情形，比如开和关、0和1、真和假等，都适合用树状结构来建模，而这种树是一种特殊的树状结构——二叉树

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成

二叉树结构图

¶二叉树特点

每个结点最多有两棵子树，所以二叉树综不存在度大于2的结点
左子树和右子树是有顺序的，次序不能颠倒
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

二叉树具有五种基本情况

¶特殊二叉树

¶斜树

所有的结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树，两者统称为斜树

¶满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树

满二叉树

满二叉树的特点

叶子只能出现在最下一层，出现在其他层就不可能达成平衡
非叶子结点的度一定是2
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多

¶完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树

满二叉树一定是一棵完全二叉树，而完全二叉树不一定是满的

完全二叉树

下面给出判断的例子来增进理解

完全二叉树的特点

叶子结点只能出现在最下两层
最下层的叶子一定集中在左部连续位置
倒数二层，若有叶子结点，一定都在右部连续位置
如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况（因为这样必定空出一个位置）
同样结点数的二叉树，完全二叉树的深度最小

完全二叉树判断

¶二叉树性质

¶性质1

在二叉树的第i层上至多有2^(i-1)个结点

¶性质2

深度为k的二叉树至多有2^k-1个结点

¶性质3

对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，那么n0=n2+1

由分支数和结点个数可以进行推导

¶性质4

具有n个结点的完全二叉树深度为[log2(n)]+1（[x]表示不大于x的最大整数）

由满二叉树的定义，深度为k的满二叉树结点数一定为2^k-1，因为这是最多的节点个数，然后倒推回去就可以得到公式k=log2(n+1)

而根据完全二叉树的定义

¶性质5

性质5的例子

¶二叉树的存储结构

¶二叉树的顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系

顺序存储结构一般只用于完全二叉树，这是因为对于普通的二叉树，可以将其按照安全二叉树编号，把不存在的结点设置为空

如下图

但是这种情况仍需要分配2^k-1的空间，浪费了空间

¶二叉链表

顺序结构的适用性不强，所以考虑链式结构。

二叉树每个结点最多有两个孩子，所以为他设计一个数据域和两个指针域，这样的链表叫做二叉链表

//二叉链表的结构体定义
typedef struct BitNode
{
    int data;
    struct BitNode*lchild,rchild;//左右孩子指针
}BitNode,*BitTree;

二叉链表结构示意图

¶遍历二叉树

对于二叉树的遍历来说，次序较为重要

二叉树的遍历是指从根结点开始，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次

¶前序遍历

根结点->左子树->右子树

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

先前序遍历根结点的左子树，从B结点开始，到D结点，再到G，此时对于D的左子树已经遍历完成，接下来前序遍历D的右子树，再之后A的左子树遍历完成，就到C，E，I，F

¶中序遍历

左子树->根->右子树

若二叉树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树

先从根结点开始，中序遍历左子树，也就是B的那一部分，把B看作B子树的根结点，然后按照中序遍历左子树D，还是按照中序遍历，G是D的左孩子，先对其遍历，再到G的根结点D，再到右子树H，往上层回溯，此时B的左子树遍历完成，到B，而B无右子树，跳过对B右子树的遍历，再到A，最后对A的右子树遍历。（这里对于E，只有右子树，没有左子树，所以访问顺序先E再I）

¶后序遍历

左子树->右子树->根结点

若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点

也可以根据左子树->右子树->根结点依次进行后序遍历的方式进行

先对左子树B开始，B有左子树，对其进行后序遍历，D的左孩子为G，先对其访问，然后是右孩子H，再到根结点D，B的左子树遍历完成，无右子树，直接访问B，再到根结点的右子树进行后序遍历。

¶层序遍历

层序遍历结构图

¶多种遍历方法的意义

¶前中后序遍历算法

其实就是上面说的遍历顺序的不同

前序：根->左子树->右子树
中序：左子树->根->右子树
后序：左子树->右子树->根

前序遍历算法

其他都差不多，而对于遍历过程也已经在上面提及了，就不赘述了

¶推导遍历结果

和离散数学中的推导一致，只需要知道各种遍历的遍历特点，再根据递归即可根据遍历结果即可还原出原本的二叉树

二叉树遍历的性质

¶二叉树的建立

如果我们要在内存中建立一个如图6-9-1左图这样的树，为了能让每个结点确认是否有左右孩子，我们对他进行了扩展，变成右图的样子，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值，比如’#'，我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树可以做到：如果已知一个遍历序列就可以确定一棵二叉树，这也是为什么我们先对二叉树进行扩展，比如左图的前序遍历序列为AB#D##C##

有了此准备，我们可以看看如何生成一棵二叉树

//按前序输入二叉树中结点的值（一个字符）
//#表示空树，构造二叉链表示二叉树T

typedef struct BitNode
{
    int data;
    struct BitNode*lchild,rchild;//左右孩子指针
}BitNode,*BitTree;

void CreateBitTree(BitTree*T)
{
    int ch;
    scanf("%C",&ch);
    if(ch=='#')
    {
        *T=NULL;//表示结点为空
    }
    else
    {
        *T=(BitTree)malloc(sizeof(BitNode));
        if(!*T)
        {
            exit(0);//开辟失败
        }
        (*T)->data=ch;
        CreateBitTree(&(*T)->lchild);//构造左子树
        CreateBitTree(&(*T)->rchild);//构造右子树
    }
}

生成二叉树的原理

中序后续构造二叉树

¶线索二叉树

对于二叉链表，我们可以看到有许多空指针的存在，浪费了大量的空间

另一方面我们在遍历完二叉树后知道每个结点的前驱和后继结点是哪个，可是这是建立在遍历过的基础之上。在二叉链表上，我们只知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱或后驱结点是谁。要是想知道，必须遍历一次，且以后每次需要知道时，都必须先遍历一次。那么我们可以考虑子啊创建时就记住前驱和后继结点，这将会节省时间

所以我们可以考虑利用那些空地址，存放指向结点在某种遍历次序下的前驱和后继结点

我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树

¶例子

如下图我们对这棵树进行中序遍历之后，将所有的空指针域中的rchild改为指向它的后继结点

于是我们可以通过指针知道H的后继节点是D（图中的1），I的后继是B，J的后继是E，E的后继是A，F的后继是C，G的后继因为不存在而指向NULL，此时有6个空指针域被利用

再如下图将这棵二叉树的所有空指针域中的lchild改为指向当前结点的前驱，H的前驱是NULL，I的前驱是D，J的前驱是B，F的前驱是A，G的前驱是C，一共5个空指针域被利用。结合前面，总共11个空指针域被利用。

通过下图更容易看出(空心箭头实现为前驱，虚线黑箭头为后继)：其实线索二叉树相当于把一棵二叉树转为了一个双向链表，这样对于我们查找、插入、删除结点都带来了便利。我们把对二叉树以某种次序遍历使其成为线索二叉树的过程称为线索化

但仍然有问题需要解决，那就是我们如何知道某一结点的lchild是指向它的左孩子还是指向前驱？rchild是指向右孩子还是后继？比如E结点的lchild是指向它的左孩子J，而rchild却是指向它的后继A。因此，我们在每个结点再增设两个标志域ltag和ratg，注意ltag和rtag只是存放0或1数字的布尔变量，其占用的内存空间要小于像lchild和rchild指针变量。

结点结构体如下

因此对于二叉链表图可以修改为下图的样子

¶线索二叉树结构实现

//二叉树的二叉线索存储结构定义
typedef enum {Link,Thread} PointerTag;//Link==0表示指向左右孩子指针，Thread==1表示指向前驱或者后缀的线索
typedef struct BitThrNode
{
    int data;//结点数据
    struct BitThrNode*lchild,*rchild;//左右孩子指针
    PointerTag LTag;
    PoniterTag RTag;//左右标志
}BitThrNode,*BitThrTree;

线索化的实质就是将二叉链表中的空指针改为指向前驱或者后继的线索，由于前驱和后继的信息只有在遍历该二叉树才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程

中序遍历线索化的递归函数代码如下

BitThrThree pre;//全局变量
void InThreading(BitThrTree p)
{
    if(p)
    {
        InThreading(p->lchild);//递归左子树线索化
    }
    if(!p->lchild)//如果没有左孩子
    {
        p->LTag=Thread;//前驱线索
        p->lchild=pre;//左孩子指针指向前驱
    }
    if(!p->rchild)//前驱没有右孩子
    {
        pre->RTag=Thread;//后驱线索
        pre->rchild=p;//前驱右孩子指针指向后继(当前结点p)
    }
    pre=p;//保持pre指向p的前驱
    InThreading(p->rchild);//递归右子树线索化
}

线索化的思路

有了线索二叉树之后，我们对其遍历时发现，其实就相当于是操作一个双向链表

双向链表遍历

遍历的代码如下

//T指向头结点，头结点左链lchild指向根结点，头结点右链指向中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T
Status InOrderTraverse_Thr(BitThrTree T)
{
    BItThrTree p;
    p=T->lchild;//p指向根结点
    while(p!=T)//空树或遍历结束时，p==T（头结点）
    {
        while(p->LTag==Link)//当LTag==0时，表示其没有左孩子，循环到中序序列的第一个结点
        {
            p=p->lchild;
        }
        printf("%c",p->data);//打印结点数据
        while(p->RTag==Thread&&p->rchild!=T)
        {//存在后继结点，不存在右孩子且不指向头结点
            p=p->rchild;
            printf("%c",p->data);//D因为存在右孩子，所以不进入循环
        }
        p=p->rchild;//指向结点D的右孩子I
    }
    return 1;
}

代码解释

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构是不错的选择

¶树、森林与二叉树的转换

在将树的存储结构时，我们提到了树的孩子兄弟法可以将一棵树用二叉链表进行存储，所以借助二叉链表，树和二叉树可以相互进行转换

¶树转换为二叉树

加线。在所有兄弟结点之间加一条连线
去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线
层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子

¶森林转换为二叉树

森林是由若干棵树组成的，所以完全可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作，步骤如下

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

森林转为二叉树

¶二叉树转换为树

也就是树转换为二叉树的逆过程，步骤如下

加线。若某结点的左孩子存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点……与该结点连线。
去线。删除二叉树中所有结点与其右孩子结点的连线
层次调整

¶二叉树转换为森林

判断一棵二叉树能够转换为一棵树还是森林，只需要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树，如果是转换成森林，步骤如下

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

¶树与森林的遍历

树的遍历方式分为两种方式

一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树
另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点

森林的遍历也分为两种方式

前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样的方式白遍历除去第一棵树的剩余数构成的森林，比如前面一张图中的森林按照前序遍历序列的结果是ABCDEFGHJI
后序遍历：先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次以同样的方式遍历除去第一棵树的剩余树构成的森林，还是以上面的森林图为例，按照后序遍历的结果就是BCDAFEJHIG

我们可以发现，森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同。

这就告诉我们，当以二叉链表作为书的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现

¶赫夫曼树及其应用——最优二叉树

赫夫曼编码是最基本的压缩编码方式，在编码中用到的特殊的二叉树称之为赫夫曼树

¶引例

首先举一个例子

我们用上面这一段代码来判断学僧的五级分制等级，其对应的流程图如下

但是在实际生活中，每个分数段占比是不同的，分布规律如下

分布规律

那么对于70分以上大约占总数的80%的成绩都需要经过3次以上的判断才能得到结果，所以对其进行优化，得到下面的二叉树

¶赫夫曼树定义与原理

我们先把这两棵二叉树简化成叶子结点带权的二叉树，如下图所示，其中A表示不及格、B表示及格、C表示中等、D表示良好、E表示优秀。每个叶子的分支线上的数字就是刚才我们提到的五级分制的成绩所占比例数

从树中的一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度，如二叉树a中，根结点到结点D的路径长度就为4，二叉树b中根结点到D结点的路径长度为2。树的路径长度就是从树根到每一结点的路径长度之和。二叉树a的路径长度为1+1+2+2+3+3+4+4=20，二叉树b的路径长度为1+2+3+3+2+1+2+2=16

如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和

假设有n个权值(w1,w2,w3……,wn)，构造一棵有n个结点的二叉树，每个叶子结点带权wk，每个叶子的路径长度为lk，我们通常记作，则其中带权路径长度WPL最小的二叉树称为赫夫曼树，也叫做最优二叉树

有了上述定义，我们可以计算上面两棵树的WPL值

二叉树a的WPL=5×1+15×2+40×3+30×4+10×4=315

注意：这里5是A叶子的权，1是A叶子的路径长度，其他同理

二叉树b的WPL=5×3+15×3+40×2+30×2+10×2=220

WPL值的用处

那么这样的二叉树是如何构造出来的，这样的二叉树是不是就是最优的赫夫曼树呢

下面给出解决办法

先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即A5，E10，B15，D30，C40。
取头两个最小权值的结点作为一个新节点N1的两个子结点，注意相对较小的作为左孩子，这里就是A为N1的左孩子，E为N1的右孩子，此时新结点的权值为15
将N1替换A和E，插入有序序列中，保持从小到大排列，即N1结点15，B15，D20，C40
重复步骤2，将N1与B作为新节点N2的两个子节点，N2的权值为30
接下来就是重复上述步骤

上图即为流程图，此时二叉树的带权路径长度WPL为205小于二叉树b的WPL220，显然此时构造的二叉树才是最优的赫夫曼树

赫夫曼树的算法描述

¶赫夫曼编码

赫夫曼树主要适用于解决数据传输的最优化问题

由于在各种语言中，字母或者汉字的出现频率是不同的

¶例子

假设要传输一段文字内容为"BADCADFEED"，我们会想到用二进制0和1来表示

我们假设六个字母的频率为A 27，B 8，C 15，D 15，E 30，F 5，合起来正好是100%，所以我们可以重新按照赫夫曼树来规划它们

构造后的赫夫曼树

此时我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，可以得到如下定义

可以看到使用赫夫曼树节约了存储和传输的成本

当我们接收到赫夫曼树压缩过后的新编码时，该如何进行解码是一个问题

由于每个字符的编码长度不等，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符编码的前缀，这种编码称作前缀编码

我们可以发现赫夫曼树对于字母的编码不存在容易与1001、1000混淆的"10"和"100"编码

但是我们在解码的时候还是需要约定好同样的赫夫曼编码规则

¶赫夫曼编码定义

¶树的总结

¶图

¶图的定义

在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继元素。在树状结构中，数据元素之间有着明显的层次关系西，并且每一层上的数据元素可能和下一层中的多个元素相关，但只能和上一层中一个元素相关（就好比一对父母可以有多个孩子，但是一个孩纸只有一对父母）。

图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关

图是由顶点的有穷非空集合和顶点之间变得集合组成的，通常表示为：G(V,E)。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合

对于图的定义，我们需要明确几点

线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素叫做顶点
在线性表可以有空表，在树中可以有空树。但是在图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶级集合V有穷非空
在图中，任何两个顶点之间都可能有关系，顶点之间的逻辑关系用边表示

¶各种图定义

无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi,Vj)来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图

无向图

无向图的定义

有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也成为弧，用有序偶<Vi,Vj>，Vi称为弧尾，Vj称为弧头。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图

有向图

需要注意弧头和弧尾的位置

注意无向边是用()表示的，有向边是用<>表示的

在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图

非简单图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个结点的无向完全图有n×(n-1)/2条边

因为对于无向完全图，任意两个结点都需要存在边，那么任选一个结点，其连接的边数为n-1，有n个结点，乘以n即可，又因为是无向的，所以有重复的，需要除以2

无向完全图

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n×(n-1)条边（推导方法同上）

有向图和无向图边数范围

有很多条边或弧的图称为稀疏图，反之称之为稠密图。这里的稀释和稠密都是相对概念

有些图的边或弧具有与他相关的数字，这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或者耗费。这种带权的图通常称之为网

下面是子图的定义

¶图的顶点与边间的关系

无向图顶点的度和邻接点、关联

有向图顶点的邻接、出入度

无向图顶点之间的路径表示

无向图顶点路径

上图即为顶点B到顶点D的四种不同

有向图间顶点路径表示

树中根结点到任意结点的路径是唯一的，但是图中顶点与顶点之间的路径却是不唯一的

路径的长度是路径上的边或弧的数目，上图左侧路径长度为2，右侧长度为3

第一个顶点到最后一个顶点相同的路径称为回路或环，序列中顶点不重复出现的路径称之为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称之为简单回路或者简单环

环与简单环的区分

¶连通图相关术语

连通图的定义

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

是子图
子图是连通的
连通子图含有极大顶点数
具有极大顶点数的连通子图包含依附于这些顶点的所有边

上图蓝色和黄色环都是连通分量

图1是一个无向非连通图，但是他有两个连通分量，即图2和图3，而图4尽管是图1的子图，但它却不满足连通子图的极大顶点数

强连通图的定义

连通图的生成树定义

所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边

如果一个图有n个顶点和小于n-1条边，则是非连通图，如果它多于n-1条边，一定会构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。不过有n-1条边并不一定是生成树

如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。对于有向树的理解，可以把入度为0的顶点看作树中的根结点，其余顶点入度为1表明树中非根结点的双亲只有一个

一个有向图的生成森林由若干棵有向树组成，含有图中的全部顶点，但只有足以构成若干棵不相交的有向树的弧

有向树和生成森林

¶图的定义与术语总结

先前也有介绍，这里是汇总

¶图的抽象数据类型

图作为一种数据结构，它的抽象数据类型带有自己特点，不同应用需要不同的运算集合，构造不同的抽象数据操作

¶图的存储结构

从图的逻辑结构定义来看，图上任意一个顶点都可以被看成是第一个顶点，任一顶点的邻接点之间也不存在次序关系

以下四张图片其实都是一个图，只不过顶点的位置不同

由于任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系

先前的存储方式来存储图结构的不可行性

¶邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图，一个一维数组存储图中结点信息，一个二维数组(称为邻接矩阵)促成农户图中的边或弧的信息

下面是邻接矩阵存储图结构的一个例子

知道邻接矩阵之后，我们可以获取如下信息

可以判定任意两顶点是否有边无边
要知道某个顶点的度，其实就是这个元素Vi在邻接矩阵中第i行或第i列的元素之和（这是因为无向图的边数组是个对称矩阵）。对于顶点V1的度就是1+0+1+0=2
求顶点Vi的所有邻接点就是将矩阵中第i行元素扫描一遍，该处位置值为1则表示是邻接点

下面是有向图的邻接矩阵

有向图中由于存在出度入度，顶点V1的入度为1，是第V1列各数之和，顶点V1的出度为2，即第V1行的各数之和

对于网来说，每条边上都带有权，接下来使用邻接矩阵来表示网

此时边数组中的元素为权值，无法到达使用无穷符号来表示，自身到自身权值为0

邻接矩阵实现图的结构定义和代码实现如下

¶邻接表

对于边数相对顶点较少的稀疏图，邻接矩阵是对存储空间的极大浪费。如下图

为了解决顺序存储结构预先分配内存造成的空间浪费问题，我们引出了链式存储的结构。所以我们也可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。

类比树中孩子表示法将结点存入数组，并对结点的孩子进行链式存储。我们把这种数组与链表相结合的存储方法称为邻接表

邻接表的处理方法如下

图中顶点用一个一维数组存储，使用数组可以较容易地读取顶点信息。此外，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息
图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以用单链表存储，无向图称为顶点Vi的边表，有向图则称为顶点Vi作为弧尾的出边表

无向图邻接表

当我们想知道某个顶点的度时，就去查找这个顶点的边表中结点的个数。若要判断顶点Vi到Vj是否存在边，只需要测试顶点Vi的边表adjvex是否存在结点Vj的下标j就行了。若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的adjvex域对应的顶点就是邻接点

若是有向图，邻接表的结构是类似的。要注意的是有向图由于有方向，我们是以顶点为弧尾(起点)来存储边表的，这样很容易得到每个顶点的出度。但有时为了便于确定顶点的入度或以顶点尾弧头的弧，我们可以建立一个有向图的逆邻接表，即对每个顶点Vi都建立一个链接为Vi为弧头的表

逆邻接表只需要按照求有向图的邻接表逆向求得即可

此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权信息即可

结构定义和代码实现如下

¶十字链表

十字链表的存储结构代码实现

http://data.biancheng.net/view/323.html

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。而十字链表就是解决这种问题的——将出边表与入边表结合起来，也就是每个顶点具有两条链表，一条是入边链表，另一条则是出边链表

对于顶点表和边表的结点结构重新定义

以下图为例，总共有六条弧，我们根据其起点和终点画出边表的结构(结点前两个位置是起点和终点，后两个位置是指向终点相同的下一条边和指向起点相同的下一条边)，然后进行连接。

对于A0顶点，后两个位置分别为入边表指针和出边表指针，黑线是出边表，对于A0，出边即以0为起点，此时只有01这个结点，所以指向01结点，而因为此时没有以0为起点的结点，所以01结点后两个位置设置为NULL。A1、A2、A3同理。

对于A4，43结点链接到出边表之后，还有一个42起点也是由4为起点的结点，所以43结点的第四个位置(也就是起点相同的下一条边)

对于入边表也是同理

¶邻接多重表

邻接多重表代码实现

http://data.biancheng.net/view/324.html

十字链表是用于有向图的，而邻接多重表则适用于无向图，由于无向图不考虑方向，此时使用邻接表则会出现重复的情况

在邻接表中，同样是将顶点存储于顺序表中，然后为每一个顶点配备一条链表，链表的每个结点存储的都是和当前顶点有直接关联的边

顶点的定义和邻接表的相同

边表的结点结构体定义如下

下面简单看个例子

由于是无向边，所以ivex和jvex的位置可以互换，但是为了方便画图还是将与当前顶点相关的放在前面。

总共有01、02、12、23、30结点，开始进行连线，和当前顶点有关则链入链表中

对于V0，首先和01结点相连，接下来ilnk指向下一个与当前顶点相关的边，也就是5号路径，同理进行6号路径（此时没有与0相关的边，所以将ilink设置为NULL）。对于1，和当前V0结点无关，其下一边暂时标记为NULL。对于V1，则有关，所以使用7号路径进行连接。其他也是同理

¶边集数组

¶图的遍历

图的遍历，即从图中某一顶点出发访问图中其余顶点，使得每一个顶点被访问且仅访问一次

其实对于两种遍历方式的不同，举个例子就可以进行理解

以上述无向图的遍历为例，对两种遍历方式进行区分

深度遍历和广度遍历的代码

http://data.biancheng.net/view/326.html

¶深度优先遍历——DFS

所谓深度优先搜索，就是从图中的某个顶点出发，不停的寻找相邻的、尚未访问的顶点：图的深度优先遍历类似树的前序遍历

如果找到多个，则任选一个顶点，然后继续从该顶点出发；
如果一个都没有找到，则回退到之前访问过的顶点，看看是否有漏掉的；

对于上述无向图的遍历过程

V1与V2和V3相邻，且这两个结点都没被访问过，任选一个，我们先选V2
对于V2同理，V2和未被访问过的V4和V5相邻，选择V4
V4和未被访问的V8相邻，选择V8，然后再到V5
到V5时，此时和V5相邻的V8和V5都已经被访问过，需要回退到V8，对V8进行该过程，直到V1
此时对V3那边重复上述过程进行遍历

顶点访问顺序

¶广度优先遍历——BFS

所谓广度优先搜索，就是从图中的某个顶点出发，寻找紧邻的、尚未访问的顶点，找到多少就访问多少，然后分别从找到的这些顶点出发，继续寻找紧邻的、尚未访问的顶点。 图的广度优先遍历类似树的层序遍历

步骤

首先访问V1结点，此时有两个未被访问的与V1相邻的V2和V3结点，对他们两个结点进行访问（先后顺序自己决定）
然后再进行V2这边的遍历，V4和V5都是未被访问的与V2相邻的结点，对其进行访问，接着就是V8**，自 V8 之后，访问序列中再无其它顶点，意味着从 V1 顶点出发，无法再找到尚未访问的顶点。这种情况下，广度优先搜索算法会从图的所有顶点中重新选择一个尚未访问的顶点，然后从此顶点出发，以同样的思路继续寻找其它尚未访问的顶点。**
对于V3这一边的也是同理

访问顺序

对于上述过程使用队列来实现较为方便

过程

首先将第一个访问的顶点入队
然后队头A出队，将与A结点相邻且未被访问的顶点从左至右入队
接着队头B出队，将与B相邻且未被访问的顶点入队，也就是CIG
接着就是队头F出队，将与F相邻且未被访问的顶点出队，因为G被访问过，所以只有E入队
后面也是相同的，直到队列为空

使用队列的入队出队正好满足先对一个顶点的相邻且未被访问的顶点进行访问

代码如下

¶邻接矩阵的深度优先遍历和广度优先遍历

我们知道对于图是可以用邻接矩阵进行存储的，也就是通过0和1来表示两顶点之间的关系

对于上面的邻接矩阵，我们分别进行深度优先遍历和广度优先遍历

¶深度优先遍历

我们假设从0结点开始，然后在第0行寻找值为1的位置，表示两个结点间具有边，此时有1、2、3、4、6，我们选取1结点进行深度遍历。因为要回溯，我们还需要存储前一个结点的位置
对第1行寻找值为1且未被遍历过的位置，也就是3，回溯的结点为0
接下来对结点3所在行进行查找，也就是2，回溯的结点是3
重复上述步骤，直到所有结点都被遍历完成

遍历的顺序

图中上面一行存储的是回溯的位置（因为第二行中所有有边的结点都已经被遍历，回溯到4结点，所以2下一个是5）

代码

邻接表的深度优先遍历代码

¶广度优先遍历

先对与0结点有边的进行遍历，有1、2、3、4、6
接着分别对1、2、3、4、6结点重复上述操作，直到所有结点都被遍历
最终在3结点发现其与5结点有边

箭头表示从该结点出发进行遍历

邻接表的广度优先算法

¶最小生成树

我们曾经提到过，一个连通图的生成树是一个极小的连通子图，它含有图中全部的结点，但只有足以构成一棵树的n-1条边（也就是说在生成树任意链接两个结点都会形成环）

我们把构造连通网的最小代价生成树（即每条边的权值和最小）称为最小生成树

下面两种算法都是求最小生成树的算法，其本质都是贪心算法，但是贪心的策略不同

最小生成树算法讲解

¶普里姆(Prim)算法

Prim算法的定义

也就是说先创建一个只有初始结点的点集和空的边集，然后在找到与点集中相关的边，然后比较权值选出权最小的边，且边的另一顶点不在点集中(否则会形成环)，此时将该边加入到边集中，将另一顶点加入到点集中

例子如下

对于上面这个连通图

首先初始化已生成的点集为{1}，边集为空
找到和点集相关的边，其中17边权最小，且顶点7不在已生成边的点集中，所以将17边加入边集，顶点7加入点集，此时点集为{1,7}
然后重复上面的过程，和顶点1、7相邻的权最小的边是边76，顶点6不在点集中，则76边加入边集，顶点6加入点集
和上面一样，但是这里出现了一个问题，边16的权最小，但是由于6已经在点集中，所以边16不能加入边集，否则会形成环。所以选择边13
接下来就是重复上面的步骤，直至所有顶点都加入边集中

而代码实现，是基于邻接矩阵的，所系需要先创建邻接矩阵

Prim算法代码讲解

下面的代码求得最小生成树的权值和

#define INF 65537
void Prim(int n, float MGraph[][n], int v0, float  sum)
{
	int lowCost[n], vSet[n];
	int v, k, min;
	for (int i = 0; i < n; ++i)
	{
		lowCost[i] = MGraph[v0][i];//权值赋值
		vSet[i] = 0;//设置为未在树中
	}

	v = v0;
	vSet[v] = 1;//表示v0结点已经被访问
	sum = 0;//初始化最小生成树的权值为0
	for (int i = 0; i < n - 1; ++i)//将剩余顶点加入树中
	{
		min = INF;//初始化设置一个较大的数
		for (int j = 0; j < n; ++j)
		{//遍历树中顶点到树外顶点的权
			if (vSet[j] == 0 && lowCost[j] < min)
			{
				min = lowCost[j];//如果不在树中
				k = j;
			}
		}
		vSet[k] = 1;//设置该顶点已经在树中
		v = k;
		sum += min;
		for (int j = 0; j < n; ++j)
		{
			if (vSet[j] == 0 && MGraph[v][j] < lowCost[j])//更新未加入树顶点的权值
			{
				lowCost[j] = MGraph[v][j];
			}
		}
	}
}

在开始讲解代码之前，我们先来看一下代码中的变量，V0表示生成树的初始顶点，lowCost数组当前生成树到图中其余顶点的边的最小权值，vSet数组存储各顶点被加入生成树的状态，1表示已经加入，0表示未加入，n表示顶点个数，MGraph数组是邻接矩阵，min表示最小权值，V始终指向刚并入树中的顶点（注意：顶点到顶点自身的权值在这里设置为无穷大）

for (int i = 0; i < n; ++i)
	{
		lowCost[i] = MGraph[v0][i];//权值赋值
		vSet[i] = 0;//设置为未在树中
	}

	v = v0;
	vSet[v] = 1;//表示v0结点已经被访问
	sum = 0;//初始化最小生成树的权值为0

表示并入树的第一个顶点为V0

对于图中的图最小生成树初始化如上图

for (int i = 0; i < n - 1; ++i)//将剩余顶点加入树中
	{
		min = INF;//初始化设置一个较大的数
		for (int j = 0; j < n; ++j)
		{//遍历树中顶点到树外顶点的权
			if (vSet[j] == 0 && lowCost[j] < min)
			{
				min = lowCost[j];//如果不在树中
				k = j;
			}
		}
		vSet[k] = 1;//设置该顶点已经在树中
		v = k;
		sum += min;
		for (int j = 0; j < n; ++j)
		{
			if (vSet[j] == 0 && MGraph[v][j] < lowCost[j])//更新权值
			{
				lowCost[j] = MGraph[v][j];
			}
		}
	}
}

上面就是生成最小生成树的过程

首先整个大循环就是对其余n-1个顶点加入生成树的过程

第一个for循环：遍历当前顶点的lowCost数组，找到其中最小的权值并赋值给min（以便后续计算sum），并且标记最小权值的边的顶点（设置为已加入树中）
第二个for循环：由于树的长大，当前生成树树到其余顶点的权值（lowCost数组的值）也会发生变化，需要使用此for循环进行改变，而由于存储的是最小权值，所以需要小于lowCost对应位置的值。而对于已经并入树的顶点，其权值已经进行了比较，所以只针对那些vSet值为0的顶点

¶克鲁斯卡尔(Kruskal)算法

Kruskal的定义

Kruskal算法直接以边为目标去构建，因为权值是在边上的，直接去找最小权值的边来构建生成树是很自然的想法，不过在构建时需要判断是否会形成环

还是以上面的连通图为例子，使用Kruskal算法进行最小生成树的构造

首先先对每条边的权值进行由小到大的排序，并将每个点各自生成一个集合
权值2最小，我们选取6、7顶点，因为这两者不在同一集合中，不会形成环。接着将6、7顶点各自的集合合并为一个集合，也就是{6,7}。对于4、5也是同理
接着就是权值3，因为{6,7}集合中没有1，所以不会星辰环，合并后的集合为{1,6,7}
下一步为权值4，但是顶点1、6在同一集合中，所以不行
后面的也是同理，接着是权值为6、7的边，在这之后，集合为{1,6,7,3,2}，还有一个{4,5}
对于权值为8，23边显然不行，因为2、3顶点在同一集合中，所以只能是3、4边，此时加入集合的是{4,5}这一含顶点4的整个集合。所以最后结果为{1,6,7,3,2,4,5}

使用代码进行实现时，依旧是邻接矩阵为输入数据的

¶并查集

上面所说的判断是否处于同一集合，正是并查集

并查集视频讲解

并查集的初始情况

2.找到权值最小的边并且判断一条边的两个顶点是否属于一棵树，然后将边的终点作为起点的子树

使用代码判断两个顶点是否属于同一棵树则需要一直往其根结点找，如果两顶点所在树的根结点不同，表示不属于同一棵树，代码如下

int Getroot(int p)
{
	while (p != v[p])
	{
		p = v[p];
	}
	return p;
}

3.最终效果

¶代码详解与分析

Kruskal算法代码讲解

typedef struct
{
	int a, b;//a表示边的起始顶点，b表示边的终点顶点
	int w;//边的权
}Road;
#define maxSize 100
int v[100];//存储并查集的结构，在这里存储其父结点的下标
Road road[maxSize];
int Getroot(int p)
{
	while (p != v[p])//当它的父结点不是本身，往上层找到其根结点，只有根结点才会保证其存储的值和其下标相同
	{
		p = v[p];
	}
	return p;
}

void Kruskal(Road roda[], int n, int e, int sum)
{
	int a, b;
	sum = 0;
	for (int i = 0; i < n; ++i)
	{
		v[i] = i;//初始化并查集数组，将数组下标赋值给下标位置处，表示每个顶点都是根结点
	}
	sort(road, e);//权值排序
	for (int i = 0; i < e; ++i)
	{
		a = Getroot(road[i].a);
		b = Getroot(road[i].b);
		if (a != b)//根结点不同，表示
		{
			v[a] = b;//生成子树
			sum += road[i].w;
		}
	}
}

¶存储结构

按照代码最终可得

在v数组中，下标为3位置存储的值为0，表示3下标的顶点其父结点为下标为0的顶点。

¶最短路径

对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点

最短路径：在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径

最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边

¶迪杰斯特拉(Dijkstra)算法

适用于解决单源最短路径

这是一个按照路径长度递增的次序产生最短路径的算法

下面是迪杰斯特拉算法的整个过程

整个过程就是一步步求出他们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径

上面的图可以简化成三个步骤

**初始化：**先找出从源点V0到各终点Vk的直达路径(V0,Vk)，即通过一条弧到达的路径
**选择：**从这些路径中找出一条长度最短的路径（V0,u）
**更新：**然后对其余各条路径进行适当调整，若在图中存在弧(u,Vk)，且(V0,u)+(u,Vk)<(V0,Vk)，则以路径(V0,u,Vk)代替(V0,Vk)

简单点理解就是两条弧的权值之和小于原本一条弧的权值
在调整后的各条路径中，再找长度最短的路径，以此类推

#define MAXVEX 9
#define INFINITY 65535

typedef int Pathmatrix[MAXVEX];//用于存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX];//用于存储到各点最短路径的权值和
/*Dijkstra算法，求有向网G的V0顶点到其余顶点V最短路径P[v]及带权长度D[v]
* P[v]的值为前驱顶点下标，D[v]表示从V0到v的最短路径长度和
*/

void ShortPath_Dijkstra(MGraph G, int v0, Pathmatrix p, ShortPathTable D)
{
	int v, w, k, min;
	int final[MAXVEX];//final[w]=表示求得顶点V0到Vw的最短路径
	for (v = 0; v < G.numVertexes; v++)//初始化数据
	{
		final[v] = 0;//全部顶点初始化为未知最短路径状态
		D[v] = G.matrix[v0][v];//将与v0有连线的顶点加上权值
		p[v] = 0;//初始化路径数组P为0
	}

	D[v0] = 0;//v0到v0的路径为0
	final[v0] = 1;//v0到v0不需要求路径
	//开始主循环，每次求得V0到某个v顶点的最短路径
	for (v = 1; v < G.numVertexes; ++v)
	{
		min = INFINITY;//当前所指离V0顶点的最近距离
		for (w = 0; w < G.numVertexes; ++w)
		{
			if (!final[w] && D[w] < min)
			{
				k = w;
				min = D[w];//w顶点离v0顶点更近
			}
		}
		final[k] = 1;//将目前找到的最近的顶点置为1
		for (w = 0; w < G.numVertexes; ++w)//修正当前最短路径及距离
		{
			//如果经过v顶点的路径比现在这条路径的长度短的话
			if (!final[w] && (min + G.matrix[k][w]) < D[w])
			{
				//说明找到了更短的路径，修改D[w]和p[w]
				D[w] = min + G.matrix[k][w];//修改当前路径长度
				p[w] = k;
			}
		}
	}
}

结合代码和算法的步骤进行讲解

¶思路和数组说明

首先将顶点分为两组，S集合表示已求出最短路径的顶点的集合，T集合表示尚未确定最短路径的顶点集合，在代码中使用final数组存储各顶点是否被确定最短路径，值为1表示已被确定，在S集合中，0则为未被确定，在T集合中。其中我们需要保证两点：

从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度
每个顶点对应一个距离值：S中顶点对应从V0到此顶点的最短路径，T中顶点对应从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

使用D数组存储该顶点到其他顶点的最短路径，当无法直达的时候，D的值记为无穷大，到自身的值记为0。代码中的G表示图的邻接矩阵，p数组用于存储最短路径的顶点下标，V0表示源点

¶初始化

for (v = 0; v < G.numVertexes; v++)//初始化数据
	{
		final[v] = 0;//全部顶点初始化为未知最短路径状态
		D[v] = G.matrix[v0][v];//将与v0有连线的顶点加上权值
		p[v] = 0;//初始化路径数组P为0
	}

	D[v0] = 0;//v0到v0的路径为0
	final[v0] = 1;//v0到v0不需要求路径

上面这一段代码只将源点V0的final值设置为1，表示已经确定最短路径，其最短路径D的值为0（到自身）

¶选择最短路径

min = INFINITY;//当前所指离V0顶点的最近距离
for (w = 0; w < G.numVertexes; ++w)
{
	if (!final[w] && D[w] < min)
	{
		k = w;
		min = D[w];//w顶点离v0顶点更近
	}
}
final[k] = 1;//将目前找到的最近的顶点置为1

初始化完成后，先遍历与V0相关的邻接矩阵的权值，找到最小的权值的边，将其加入S集合中，如下图所示

¶更新

因为S集合出现新的顶点，到某顶点可以直达，也可以中转，所以要更新最短路径

for (w = 0; w < G.numVertexes; ++w)//修正当前最短路径及距离
{
	//如果经过v顶点的路径比现在这条路径的长度短的话
	if (!final[w] && (min + G.matrix[k][w]) < D[w])
	{
		//说明找到了更短的路径，修改D[w]和p[w]
		D[w] = min + G.matrix[k][w];//修改当前路径长度
		p[w] = k;
	}
}

以上述例子讲解，对D中的所有元素进行修改，如果该顶点未被加入S集合并且源点V0到V2顶点V的最短路径+V2顶点与V3顶点的权值要<从源点直达V3顶点的权值的话，则需要修改V0与V3顶点的最短路径值D，显然这里需要，因为V0与V3无直达路径，所以V0与V3权值为无穷大。并且将k赋值给p数组中V3对应的值，表示V3顶点所在最短路径的前一个顶点是V2

如下图

¶重复

接下来就是重复上述步骤，直至final数组中的值全为1

¶弗洛伊德-Floyd算法

适用于解决所有顶点间的最短路径

在Dijkstra算法中，我们知道了如何计算某个顶点到其余顶点的最短路径，但有时候我们需要求得图中所有顶点到其余顶点的最短路径，此时可以进行n次Dijkstra算法，也可以采用接下来介绍的这种算法

算法思想：

逐个顶点试探
从Vi到Vj的所有可能存在的路径中
选出一条长度最短的路径

求最短路径步骤：

首先画出图的邻接矩阵
接着逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之，否则维持原值。当所有顶点试探完毕，算法结束

整个过程如下图

typedef int Pathmatrix[MAXVEX][MAXVEX];//用于存储中间结点
typedef int ShortPathTable[MAXVEX][MAXVEX];
//Floyd算法，求网图G中各顶点v到其余顶点w最短路径P[v][w]及带权长度D[v][w]
void ShortPath_Floyd(MGraph G, Pathmatrix P, ShortPathTable D)
{
	int v, w, k;
	for (v = 0; v < G.numVertexes; ++v)//初始化D与P
	{
		for (w = 0; w < G.numVertexes; ++w)//D[v][w]值即为对应点间的权值
		{
			D[v][w] = G.matrix[v][w];
			P[v][w] = -1;//初始化P
		}
	}
	for (k = 0; k < G.numVertexes; ++k)
	{
		for (v = 0; v < G.numVertexes; ++v)
		{
			for (w = 0; w < G.numVertexes; ++w)
			{
				if (D[v][w] > D[v][k] + D[k][w])
				{
					//如果经过下标为k顶点路径比原两点间路径更短
					//将当前两点间权值设置为更小的一个
					D[v][w] = D[v][k] + D[k][w];
					P[v][w] = k;//路径设置为下标为k的顶点
				}
			}
		}
	}

}

¶初始化

D数组存储的是顶点之间最短路径的值，P数组存储顶点之间的中间顶点，如果是两顶点直达，则P中的值为-1，表示没有中间顶点

for (v = 0; v < G.numVertexes; ++v)//初始化D与P
{
	for (w = 0; w < G.numVertexes; ++w)//D[v][w]值即为对应点间的权值
	{
		D[v][w] = G.matrix[v][w];
		P[v][w] = -1;//初始化P
	}
}

将邻接矩阵赋值到D数组进行初始化

将P中的值全部赋值为-1，因为开始时没有中间顶点，所以全部为-1

¶遍历修改

for (k = 0; k < G.numVertexes; ++k)
	{
		for (v = 0; v < G.numVertexes; ++v)
		{
			for (w = 0; w < G.numVertexes; ++w)
			{
				if (D[v][w] > D[v][k] + D[k][w])
				{
					//如果经过下标为k顶点路径比原两点间路径更短
					//将当前两点间权值设置为更小的一个
					D[v][w] = D[v][k] + D[k][w];
					P[v][w] = k;//路径设置为下标为k的顶点
				}
			}
		}
	}

接下来的三层循环，就是不断在两顶点直达路径中加入中间顶点，然后与直达的权值进行比较，得到最小的权值。并且将P数组中对应位置的值改为中间顶点k，表示两顶点以该顶点k为中间顶点时路径长度最短

¶求最短路径

经过上述过程，我们得到了P数组，其存储的是中间顶点的信息，我们可以通过P数组打印每个顶点的最短路径

代码如下

void printPath(int u, int v, int path[][MAXVEX])
{
	if (path[u][v] == -1)
	{
		//直接输出
	}
	int mid = path[u][v];
	printPath(u, mid, path);
	printPath(mid, v, path);
}

当path数组的值为-1，表示两顶点可以直达，也就是无中间顶点

u、v表示通过path数组寻找u、v顶点之间的最短路径

以上图为例手动查找从顶点1到顶点0最短路径：

首先看P【1】【0】位置处为3，表示10顶点之间的最短路径存在中间顶点3，1->3->0
首先看P【1】【3】位置处为-1，表示13顶点之间的最短路径是直达的
接着是P【3】【0】位置处为2，表示30顶点之间的最短路径存在中间顶点2，1->3->2->0
首先看P【3】【2】位置处为-1，表示32顶点之间的最短路径是直达的
最后P【2】【0】位置处为-1，表示20顶点之间的最短路径是直达的，此时10顶点最短路径已确定，为1->3->2->0

整个过程就是递归的过程，代入代码中理解即可

¶拓扑排序

主要针对有向无环图

有向无环图：无环的有向图，简称DAG图

有向无环图

有向无环图的实际例子

AOV网：用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网。AOV网中不能存在回路，举个例子：让某个活动的开始要以自己完成作为先决条件，这显然是不可能的

AOV网

拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1，V2，V3……，Vn，满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必须在Vj之前，则我们成这样的顶点序列为一个拓扑序列

拓扑排序其实就是对一个有向图构造拓朴序列的过程。构造时会有两种结果：

此网的全部顶点都被输出，则说明它是不存在环的AOV网
如果输出的定点少了，则说明这个网存在环，不是AOV网

¶拓扑排序算法

对AOV网进行拓朴排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止

在拓扑排序中，由于要删除顶点，所以使用邻接表更为方便

数据结构

其中in表示入度

对于这样的一幅图AOV网，其邻接表如下

¶拓扑排序代码实现

栈只是用于存储入度为0的顶点，只作为容器，也可以使用其他数据结构进行存储

typedef struct EdgeNode//边表结点
{
	int adjvex;//邻接点域，存储该顶点对应的下标
	int weight;//用于存储权值，对于非网图可以不需要
	struct EdgeNode* next;//链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode
{
	int in;//顶点入度
	int data;//顶点域。存储顶点信息
	EdgeNode* firstedge;//边表头指针
}VertexNode,AdjList[MAXVEX];

typedef struct
{
	AdjList adjList;
	int numVertexes, numEdges;//图中当前顶点数和边数
}qraphAdjList,*GraphAdjList;


int TopologicalSort(GraphAdjList GL)
{
	EdgeNode* e;
	int i, k, gettop;
	int top = 0;//用于栈指针下标
	int count = 0;//用于统计输出顶点的个数
	int* stack;//建立栈存储入度为0的顶点
	stack = (int*)malloc(sizeof(int));
	for (i = 0; i < GL->numVertexes; ++i)
	{
		if (GL->adjList[i].in == 0)
		{
			stack[++top] = i;//将入度为0的顶点入栈
		}
	}
	while (top != 0)
	{
		gettop = stack[top--];//出栈
		printf("%d ->", GL->adjList[gettop].data);
		count++;
		for (e = GL->adjList[gettop].firstedge;e; e = e->next)
		{
			//对此顶点弧表遍历
			k = e->adjvex;
			if (!(--GL->adjList[k].in))//将k号顶点邻接点的入度减1
			{
				stack[++top] = k;//若为0则入栈，以便于下次循环输出
			}
		}
	}
	if (count < GL->numVertexes)//如果count小于顶点数，说明存在环
	{
		return 0;
	}
	else
		return 1;
}

我们以上面的AOV网为例，跟着代码走一遍

1.首先初始化一些数据

2.然后将入度为0的顶点入栈

for (i = 0; i < GL->numVertexes; ++i)
{
	if (GL->adjList[i].in == 0)
	{
		stack[++top] = i;//将入度为0的顶点入栈
	}
}

此时stack应该为{0,1,3}

3.while循环，当栈中有数据元素时，始终寻呼那

4.接下来V3出栈，gettop=3，然后count+1表示输出顶点个数+1

1
2
3

gettop = stack[top--];//出栈
printf("%d ->", GL->adjList[gettop].data);
count++;

5.然后对V3顶点对应的弧链表进行遍历，找到V3连接的两个顶点V2和V13，并且将他们的入度减少一位，此时V2和V13的in值都为1.他的目的是为了将V3顶点上的弧删除

	for (e = GL->adjList[gettop].firstedge; e; e = e->next)
	{
		//对此顶点弧表遍历
		k = e->adjvex;
		if (!(--GL->adjList[k].in))//将k号顶点邻接点的入度减1
		{
			stack[++top] = k;//若为0则入栈，以便于下次循环输出
		}
	}
}

6.再次循环，此时处理的是V1顶点。经过出栈、打印、count=2后，我们对V1到V2、V4、V8的弧进行遍历。并同样减少了它们的入度数，此时V2的入度为0，由if语句判断入度是否为0，V2入栈。如果没有在顶点表中加入in这个入度数据域，if的判断则必须是循环（循环遍历找到入度为0的结点），这显然是要消耗时间的。而引入in数据域是利用空间换取了时间

7.接下来就是重复上述步骤

8.最终拓扑排序打印结果为3->1->2->6->0->4->5->7->7->12->9->10->13->11，当然这结果并不是唯一的一种拓扑排序方案

¶逆拓扑排序

逆拓扑排序类似拓扑排序，不过将入度改为出度

可以使用深度优先遍历来进行逆拓扑排序，也可以修改拓扑排序的代码进行逆拓扑排序

对上图进行深搜，先从0开始，接下来是1顶点，由于1顶点有后继顶点，继续进行，访问顶点3，而顶点3无后继顶点，也就是出度为0，输出顶点3，并且删除边13和23，按照深搜此时需要回溯到顶点1，由于删除了边13，所以1的出度为0，符合出度为0的顶点，输出顶点1，并且删除边01，按照深搜，接下来访问2顶点，2顶点出度为0，输出顶点2，最后输出顶点0。上述过程中每次访问顶点都需要修改visit数组中的值为1，表示已经访问

同时，我们也可以在访问的时候入栈，输出时（即出度为0时）出栈

逆拓扑排序：3->1->2->0

void DFS(int  v, AGraph* G)
{
	visit[v] = 1;
	ArcNode* q = G->adjList[v].first;
	while (q != NULL)
	{
		if (visit[q->adjV] == 0)
		{
			DFS(q->adjV, G);
		}
		q = q->next;
	}
}

¶关键路径

主要针对有向无环图

拓扑排序主要是为了解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题

因此我们如果要对一个流程图获得最短时间，就必须要分析它们的拓扑关系，比能找到当中的关键路径，这个流程的时间就是最短时间

AOE网:在表示一个工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网，其中，没有出边的顶点称为终点或汇点，没有入边的顶点称之为始点或源点

AOE网的特点

我们把路径上各个活动所持续的是简直和称为路径长度，从源点到汇点足有最大长度的路径叫关键路径

在上图的AOE网中，开始->发动机完成->部件集中到位->组装完成就是关键路径，路径长度为5.5

关键路径的应用

¶关键路径算法原理

关键路径实例理解

也就是说，我们只需要找到所有活动的最早开始时间和最晚开始时间，并且比较他们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。否则不是

所以我们需要定义如下几个参数

事件既可以表示前一个活动的结束，也可以用于表示下一个活动的开始，如下图，V2既可以表示a1活动的结束，也可以表示a2活动的开始，而只有a1活动完成后a2活动才能开始，所以a2的最早开始事件（也就是V2事件最早发生时间）的值为30

事件的最早发生时间etv(earlist time of vertex)：即顶点Vk的最早发生时间
事件的最晚发生时间ltv(latesttime of vertex)：即顶点Vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的事件，超出此事件将会延误整个工期
活动的最早开工时间ete(earlist time of edge)：即弧ak的最早发生时间
活动的最晚开工时间lte(latest time of edge)：即弧ak的最晚发生时间，也就是不推迟工期的最晚开工时间

我们是由1和2可以求得3和4，然后再根据ete[k]是否与lte[k]相等来判断ak是否为关键活动

¶关键路径算法

关于过程，可以看关键路径讲解

将下图的AOE网转化为邻接表的结构图，与拓扑排序时邻接表结构不同的地方在于，这里的弧链表增加了weight域，用于存储弧的权值

求事件的最早发生时间，也就是顶点的先后次序，就是我们从头到尾找拓扑序列的过程。因此在求关键路径之前，需要先调用依次拓扑序列算法的代码来计算etv和拓扑排序列表

typedef struct EdgeNode//边表结点
{
	int adjvex;//邻接点域，存储该顶点对应的下标
	int weight;//用于存储权值，对于非网图可以不需要
	struct EdgeNode* next;//链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode
{
	int in;//顶点入度
	int data;//顶点域。存储顶点信息
	EdgeNode* firstedge;//边表头指针
}VertexNode,AdjList[MAXVEX];

typedef struct
{
	AdjList adjList;
	int numVertexes, numEdges;//图中当前顶点数和边数
}qraphAdjList,*GraphAdjList;

int* etv, * ltv;//事件最早发生时间和最迟发生时间
int* stack2;//用于存储拓扑序列的栈
int top2;//用于stack2的指针

int TopologicalSort(GraphAdjList GL)
{
	EdgeNode* e;
	int i, k, gettop;
	int top = 0;//用于栈指针下标
	int count = 0;//用于统计输出顶点的个数
	int* stack;//建立栈存储入度为0的顶点
	stack = (int*)malloc(sizeof(int));
	for (i = 0; i < GL->numVertexes; ++i)
	{
		if (GL->adjList[i].in == 0)
		{
			stack[++top] = i;//将入度为0的顶点入栈
		}
	}
	top2 = 0;//初始化栈指针为0
	etv = (int*)malloc(GL->numVertexes * sizeof(int));//事件最早发生时间
	for (i = 0; i < GL->numVertexes; ++i)
	{
		etv[i] = 0;//初始化为0
	}

	stack2 = (int*)malloc(GL->numVertexes * sizeof(int));//初始话

	while (top != 0)
	{
		gettop = stack[top--];//出栈
		count++;
		stack2[++top2] = gettop;//将弹出的顶点序号压入拓扑序列的栈
		for (e = GL->adjList[gettop].firstedge; e; e = e->next)
		{
			//对此顶点弧表遍历
			k = e->adjvex;
			if (!(--GL->adjList[k].in))//将k号顶点邻接点的入度减1
			{
				stack[++top] = k;//若为0则入栈，以便于下次循环输出
			}
			if ((etv[gettop] + e->weight > etv[k]))//求各顶点事件最早发生时间
			{
				etv[k] = etv[gettop] + e->weight;
			}
		}
	}
	if (count < GL->numVertexes)//如果count小于顶点数，说明存在环
	{
		return 0;
	}
	else
		return 1;
}

代码和拓扑排序算法差不多，就是加了一些代码，在讲解这些代码之前，我们先来看看如何计算事件的最早发生时间，也就是etv的值(边是活动，顶点表示事件的开始和结束)。

事件的最早发生时间就是前一事件最早发生时间+活动持续时间的最大值——从源点开始

这是因为需要同时满足四个条件才能到达图中的Vj，所以需要取最大值88，所以V觉得最早发生时间为0+88=88。

事件的最晚发生时间计算：(后一事件的最晚发生时间-活动持续时间)的最小值

因为要保证最后一定保证这四个都完成，所以最晚从3开始

活动的最早发生时间：活动的最早发生时间就是事件的最早发生事件

活动的最晚发生时间：活动的最晚发生时间（边）就是事件的最晚发生时间减去活动的持续时间。

关键路径求解步骤

求关键路径的算法代码

void CriticalPath(GraphAdjList GL)
{
	EdgeNode* e;
	int i, gettop, k, j;
	int ete, lte;//声明活动最早发生时间和最迟发生时间变量
	TopologicalSort(GL);//求拓扑序列，计算数组etv的stack2的值
	ltv = (int*)malloc(GL->numVertexes * sizeof(int));//事件最晚发生时间
	for (i = 0; i < GL->numVertexes; ++i)
	{
		ltv[i] = etv[GL->numVertexes - 1];//初始化ltv
	}
	while (top2 != 0)//计算ltv
	{
		gettop = stack2[top2--];//将拓扑序列出栈，后进先出
		for (e = GL->adjList[gettop].firstedge; e; e = e->next)
		{
			//求各顶点事件的最迟发生时间ltv值
			k = e->adjvex;
			if (ltv[k] - e->weight < ltv[gettop])
			{
				ltv[gettop] = ltv[k] - e->weight;
			}
		}
	}
	for (j = 0; j < GL->numVertexes; ++j)
	{
		for (e = GL->adjList[j].firstedge; e; e = e->next)
		{
			k = e->adjvex;
			ete = etv[j];//活动最早发生时间
			lte = ltv[k] - e->weight;//活动最迟发生时间
			if (ete == lte)//两者相等即在关键路径上
			{
				printf("<v%d,v%d>length:%d,", GL->adjList[j].data, GL->adjList[k].data, e->weight);
			}
		}
	}

}