本笔记中的代码大部分来自01大学皮皮学长（ C语言版 ），图形大部分由我绘画，画工有限请见谅。
01星球：https://space.bilibili.com/1653229811
温馨提示：由于笔记的图床位于github，若是想查看图片需要魔法上网。

线性表

基本数据类型 ：数据类型反映了数据的取值范围以及对这类数据可以施加的运算。（ 如整数型、浮点型等 ）

抽象数据类型 ：只是⼀个数学模型以及定义在模型上的⼀组操作。通常是对数据的抽象，定义了数据的取值范围以及对数据操作的集合。（ 如数据结构中的链表、栈、队列等 ）

线性表抽象数据类型主要包括两个方面：既数据集合和该数据集合上的操作集合。

线性结构：

1. 除第⼀个和最后⼀个数据元素外，每个数据元素只有⼀个前驱数据元素和⼀个后继数据元素；
2. 第⼀个数据元素没有前驱数据元素；
3. 最后⼀个数据元素没有后继数据元素；

顺序表

顺序表

​ 在计算机内存中，顺序表是以数组的形式保存的线性表。也就是⼀组地址连续的存储单元依次存储数据元素的线性结构。

​ 在数组中，我们会先申请⼀段连续的内存空间，然后把数组以此存⼊内存当中，中间没有⼀点空隙。这就是⼀种顺序表存储数据的方式。对于顺序表的基本操作有：增（add），删（remove），改（set），查（find），插（insert）。

数据集合

#define Size 5 // 初始化以及扩容的长度
#define ElementType int// int 取别名

typedef struct ArrayList {
	ElementType* e;	  // 存放数据元素的数组
	int length;		 // 顺序表中数据的总数量
	int size;        // 当前元素的数量
}MyArray;

操作集合

MyArray initArray();						// 初始化操作
void add(MyArray *arr, ElementType key);	  // 添加一个元素
void del(MyArray *arr, ElementType key);	  // 删除指定的元素
void insert(MyArray *arr, ElementType key, ElementType temp_index);//插入一个元素 
int find(MyArray *arr, ElementType key);	  // 查询指定的元素
void show(MyArray arr);						// 展示当前顺序表的元素，即输出顺序表 
int index(MyArray* arr, ElementType key);	  // 寻找关键字所在的下标

顺序表优势

​ 因为数据在数组中按顺序存储，可以通过数组下标直接访问，因此顺序表的查找定位元素很快。

顺序表劣势

​ 插⼊和删除元素都需要大量的操作。 ​ 因为数组在声明的时候需要确定长度，因此顺序表的长度是确定的。若需要扩大顺序表长度，有需要大量的操作，不够灵活。（要将该数组中的元素全部copy到另外⼀个数组） ​ 由于数据大小的不可测性，有时会浪费掉大量的空间

应用场景

​ 总之，顺序表适⽤于那些不需要对于数据进行大量改动的结构。

顺序表的效率分析

​ 综上所述，可以得出。顺序表对于插入、删除⼀个元素的时间复杂度是O(n)。 ​ 因为顺序表支持随机访问，顺序表读取⼀个元素的时间复杂度为O(1）。因为我们是通过下标访问的，所以时间复杂度是固定的，和问题的规模无关。 ​ 最⼤的优点是空间利用率高。最大的缺点是大小固定。

顺序表之初始化操作

​ 初始化顺序表MyArray，向内存申请连续的大小为5*32（ 64位系统下 ）的空间。并且初始化数据集合中的各个变量。

​ 时间复杂度为O(1)

​ 空间复杂度为O(Size)

MyArray initArray()
{
	MyArray array;

	array.e = (ElementType*)malloc(Size * sizeof(int));
	if (!array.e) {
		printf("初始化失败");
		exit(0);
	}
	array.length = 5;
	array.size = 0;

	return array;
}

顺序表之增加操作

​ 向顺序表中添加数据，传入待添加元素的数组与待添加的关键字，在添加前要先判断顺序表是否已经满了。满了需要扩容（ 这里没有演示和初始化的操作类似 ），若顺序表没满，那就在顺序表的末尾添加数据，并将size++。

​ 时间复杂度为O(1)

​ 空间复杂度为O(1)

/*
MyArray* arr :待添加元素的数组
ElementType key : 待添加的关键字
*/
void add(MyArray *arr, ElementType key)
{
	if (arr->size < arr->length)
	{
		arr->e[arr->size] = key;
		arr->size++;
	}
	else
	{
		printf("元素已满");
		// 顺序表满之后，要扩容
	}
}

顺序表之删除操作

​ 删除操作建立在查找上面。需要先查找到需要删除数据的下标。若查找到元素则将这个元素后面的元素全部前移一格，并且将size--。

​ 时间复杂度O(n)

​ 空间复杂度O(1)

int index(MyArray* arr, ElementType key) // 找到关键字所在的下标
{
	int i = 0;// 数组下标变量 从0开始
	while (i < arr->size)
	{
		// 如果第i个元素和关键字相等 返回下标i
		if (arr->e[i] == key) {
			return i;
		}
		// 下标+1
		i++;
	}
	return -1;// 没有找到下标
}

void del(MyArray* arr, ElementType key)
{
	// 找到关键字所在的下标
	int temp_index = index(arr, key);
	// 判断关键字是否存在
	if (temp_index != -1)
	{
		// 待删除的关键字存在 移动
		while(temp_index < arr -> size)
		{
			arr->e[temp_index] = arr->e[temp_index + 1];
			temp_index++;
		}
		// 移动完 数组元素 - 1
		arr->size--;
	}
	else
	{
		printf("没有该元素");
	}
}

顺序表之修改操作

​ 修改操作就是删除操作的简化（ 代码不再给出 ）

​ 时间复杂度O(n)

​ 空间复杂度O(1)

顺序表之查询操作

​ 这个和删除操作中的查询下标十分的相似，不再赘述。

​ 时间复杂度O(N)

​ 空间复杂度O(1)

int find(MyArray *arr, ElementType key)
{
	if (arr->size == 0)
	{
		printf("当前没有元素");
	}
	else
	{
		int i = 0;
		while (i < arr->size)
		{
			if (arr->e[i] == key)
			{
				return 1;
			}
		}
	}

	return 0;
}

顺序表之插入操作

​ 插入操作和删除操作十分的相似，只是一个是将数据向前覆盖（ 删除操作 ），一个是将数据向后覆盖（ 插入操作 ）。同时对于size进行改变的时机也不同。

​ 时间复杂度O(N)

​ 空间复杂度O(1)

/* ElementType temp_index 插入位置的下标 */
void insert(MyArray *arr, ElementType key, ElementType temp_index)
{
	
	if(arr->size >= 5)
	{
		printf("元素已满，插入失败");	
	} 
	// 数组元素 + 1
	arr->size++;
	
	int size = arr->size;// 用来存储待顺序表当前的元素数量 
	
	// 待插入的关键字存在 移动
	while(size > temp_index)
	{
		arr->e[size] = arr->e[size-1];
		size--;
	}
    // 修改索引位置的值
	arr->e[temp_index] = key; 
		
	
}

顺序表总代码

#include <stdio.h>
#include <stdlib.h>
#define Size 5 //初始化以及扩容的长度
#define ElementType int//int 取别名

//数据集合 
typedef struct ArrayList {
	ElementType* e;//存放数据元素的数组
	int length;//顺序表中数据的总数量
	int size;//当前元素的数量
}MyArray;

//操作集合 
MyArray initArray();//初始化操作
void add(MyArray *arr, ElementType key);//添加一个元素
void del(MyArray *arr, ElementType key);//删除指定的元素
void insert(MyArray *arr, ElementType key, ElementType temp_index);//插入一个元素 
int find(MyArray *arr, ElementType key);//查询指定的元素
void show(MyArray arr);//展示当前顺序表的元素，即输出顺序表 
int index(MyArray* arr, ElementType key);//寻找关键字所在的下标


int main()
{
	MyArray a;
	a = initArray();
	add(&a, 1);
	add(&a, 2);
	show(a);
	del(&a, 2);
	show(a);
	printf("\n");
	add(&a, 1);
	add(&a, 2);	
	insert(&a, 3, 1);
	show(a);
}

MyArray initArray()
{
	MyArray array;

	array.e = (ElementType*)malloc(Size * sizeof(int));
	if (!array.e) {
		printf("初始化失败");
		exit(0);
	}
	array.length = 5;
	array.size = 0;

	return array;
}



/*
MyArray* arr :待添加元素的数组
ElementType key : 待添加的关键字
*/
void add(MyArray *arr, ElementType key)
{
	if (arr->size < arr->length)
	{
		arr->e[arr->size] = key;
		arr->size++;
	}
	else
	{
		printf("元素已满");
		//顺序表满之后，要扩容
	}
}

void del(MyArray* arr, ElementType key)
{
	//找到关键字所在的下标
	int temp_index = index(arr, key);
	//判断关键字是否存在
	if (temp_index != -1)
	{
		//待删除的关键字存在 移动
		while(temp_index < arr -> size)
		{
			arr->e[temp_index] = arr->e[temp_index + 1];
			temp_index++;
		}
		//移动完 数组元素 - 1
		arr->size--;
	}
	else
	{
		printf("没有该元素");
	}
}

int index(MyArray* arr, ElementType key)
{
	int i = 0;//数组下标变量 从0开始
	while (i < arr->size)
	{
		//如果第i个元素和关键字相等 返回下标i
		if (arr->e[i] == key) {
			return i;
		}
		//下标+1
		i++;
	}
	return -1;//没有找到下标
}

void insert(MyArray *arr, ElementType key, ElementType temp_index)
{
	
	if(arr->size >= 5)
	{
		printf("元素已满，插入失败");	
	} 
	// 数组元素 + 1
	arr->size++;
	
	int size = arr->size;// 用来存储待顺序表当前的元素数量 
	
	// 待插入的关键字存在 移动
	while(size > temp_index)
	{
		arr->e[size] = arr->e[size-1];
		size--;
	}
	arr->e[temp_index] = key; 
	
	
	
}


int find(MyArray *arr, ElementType key)
{
	if (arr->size == 0)
	{
		printf("当前没有元素");
	}
	else
	{
		int i = 0;
		while (i < arr->size)
		{
			if (arr->e[i] == key)
			{
				return 1;
			}
		}
	}

	return 0;
}

void show(MyArray arr)
{
	if (arr.size == 0)
	{
		printf("当前没有元素");
	}
	else
	{
		int i = 0;
		while (i < arr.size)
		{
			printf("%d ",arr.e[i]);
			i++;
		}
	}
}

链表

​ 为了避免插入和删除的线性开销，我们允许表可以不连续存储，否则表的部分或全部需要整体移动。而且大小无法改变。为了应对顺序表的缺陷，链表就此诞⽣。链表也是继数组之后第⼆种使⽤的最⼴泛的通⽤数据结构

链表结构：在物理上不连续，在逻辑上连续，大小不固定。

链式存储结构：数据域 + 指针域

数据域：存数据元素的区域

指针域：存储直接后继位置的区域

链式存储分类：单向链表，单向循环链表，双向链表，双向循环链表

单向链表

​ 链表的每个节点只包含⼀个指针域。叫做单链表（即构成链表的每个节点只有⼀个指向后继节点的指针）

​ 单向链表有带头节点和不带头节点两种结构。（ 下面展示的都是带头节点的单向链表 ）

​ 链表中，第⼀个结点存储的位置叫头指针，如果链表有头结点，那么头指针就是指向头结点的指针。

​ 头指针所指的不存在数据元素的第⼀个结点就叫做头结点（而头结点又指向首元结点）。头结点⼀般不放数据（有的时候也是放的，比如链表的长度，用做监视）。

属性集合

​ 每个节点包含数据域element和指针域next。

​ 解释一下结构体中定义节点命名相关的知识

• 等同于： typedef struct NodeList* linklist;
• linklist与node*等价，都是用来声明结构体指针变量的
• linklist强调该指针标记标记了一个单链表
• node* 强调该指针标记了一个结点

// 带头结点单链表
typedef struct NodeList{// 属性集合（结点） 
	// 数据
	int element;
	// 指向下一个结点指针 
	struct NodeList* next; 
}node,*linklist;

操作集合

linklist initlist();// 初始化链表
void head_insert(int,linklist);// 头插法添加数据
void tail_insert(int,linklist);// 尾插法添加数据
void delete_node(int,linklist);// 删除操作
void modify_node(int,linklist);// 修改操作
node* find(int,linklist);// 查找操作
void mid_insert(int,linklist,int);// 在数据为i的结点后插入数据域为k的新结点
void i_insert(int,linklist,int);// 在第i个位置插入数据域为k的新结点
void printff(linklist)// 打印链表

单向链表之初始化操作

​ 初始化一个带头节点的单链表。首先初始化一个头节点，并使用头指针head指向头节点。用malloc出来的空间都要进行判断，内存是否分配成功。分配成功，补充节点的指针域。由于时初始化，所以指向NULL。

​ 稍微提一下malloc。malloc的返回值为void*，所有当用malloc申请一个空间时，往往使用强制转换，初始化操作中(linklist)就是强制转为节点结构体类型。同时要指明分配空间的大小，初始化中的sizeof(node)就是告诉了大小。

linklist initlist()
{// 初始化带头结点的单链表 
	linklist head=(linklist)malloc(sizeof(node));// head指向头结点 
	if(head==NULL)// malloc 需要判断 内存分配是否成功
	{
		printf("内存分配不成功\n");// 内存分配不成功 
	 } 
	 else{// 分配成功 
		head->next=NULL;
	 } 
	return head; 
 } 

单向链表之增加操作

​ 单链表中添加数据有两种写法，一种是头插法添加数据，一种是尾插法添加数据。

头插法添加数据

​ 头插法增加数据的顺序是反的。

1. 先分配一个节点（ 其实这边是需要判断是否成功，懒！！），将数据写入节点。

2. 将新节点的后继指向头节点的后继

3. 将头节点的后继指向新节点

   时间复杂度O(1)

   空间复杂度O(1) （ 节点除外 ）

void head_insert(int k,linklist head)// 头插法添加元素
{
	node* newNode = (node*)malloc(sizeof(node));
	newNode->element=k;// 数据写入结点 
    
	newNode->next=head->next;
	head->next=newNode;

}

尾插法添加数据

​ 尾插法增加数据的顺序是正的。

1. 先分配一个节点，将数据写入节点。

2. 创造一个临时指针指向头节点

3. 遍历到链表末尾

4. 此时临时节点的后继指向新节点

   时间复杂度O(n)

   空间复杂度O(1) （ 节点除外 ）

void tail_insert(int k,linklist head)// 尾插法添加数据
{
	node* newNode=(node*)malloc(sizeof(node));
	newNode->element=k;// 数据写入结点
    
	node* temp = head; // 临时指针指向头节点
    while (temp->next != NULL) { // 遍历到链表末尾
        temp = temp->next;
    }
    temp->next = newNode; // 将新节点连接到链表末尾
}

单向链表之删除操作

​ 删除分为查找和删除操作，即先找到这个结点，再删除。

1. 先要判定链表是否存在,以及链表是否还存在节点（ 头节点一般不作为增删改查的对象 ）。

2. 确定链表中是否存在目标节点（ 详细代码详看单链表之查询操作 ），且将指针p指向目标节点。

3. 新建指针q移动到想要删除目标的前一个节点。

4. 将q的后继指向p的后继

5. 释放掉目标节点的空间

   时间复杂度O(n)

   空间复杂度O(1)

void delete_node(int k,linklist head)
{
	// 这个链表是否存在，还能否继续删除 
    if(head==NULL||head->next==NULL)
    {
    	printf("空链表\n");// 返回是空链表 
    	// 要先判断这个链表是不是空的，也就是还能不能删
		return ;
	}
	node* p=find(k,l);
	if(p==NULL)
	{
		printf("未找到删除结点\n");// k不在链表中 
	 } else{// 要删除第i个结点，要先找到第i-1个 
	 	node *q=head;
		while(q!=NULL&&q->next!=p )// 找到第i-1个 
		{
			q=q->next;
		}   
		q->next =p->next;
		free(p); 
	 }
}

单向链表之修改操作

​ 单链表的修改操作和删除操作十分的相似

1. 先要判定链表是否存在,以及链表是否还存在节点（ 头节点一般不作为增删改查的对象 ）。

2. 确定链表中是否存在目标节点（ 详细代码详看单链表之查询操作 ），且将指针p指向目标节点。

3. 将p->element的值修改。

   时间复杂度：O(n)

   空间复杂度：O(1)

void modify_node(int k,linklist head)
{
    // 这个链表是否存在，还能否继续删除 
    if(head==NULL||head->next==NULL)
    {
    	printf("空链表\n");// 返回是空链表 
    	// 要先判断这个链表是不是空的，也就是还能不能删
		return ;
	}
    node* p=find(k,head);
	if(p==NULL)
	{
		printf("未找到删除结点\n");// k不在链表中 
	 } else{
        p->element = k;
    }
}

单向链表之查找操作

​ 查询k所在的结点，查询有两种，一种是找到这个结点。另一种是找到这个结点在链表中的哪个位置

1. 创造一个新指针p。

2. 寻找到该节点，返回节点。

   时间复杂度：O(n)

   空间复杂度：O(1)

node* find(int k,linklist head)
{
	node* p = head->next;//第一个元素 
	while(p!=NULL&&p->element !=k)
	{
		p=p->next;
	 } 
	 return p;//若没找到，则p=NULL,用查询结果的时候判断有没有找到 
}

单向链表之插入节点

​ 插入节点相比于单链表的其他操作较为复杂。插入节点分为两种情况。第一种情况是在i节点后插入一个节点，另一种情况是在i位置插入一个节点。

第一种情况

​ 在数据为i的结点后插入数据域为k的新结点

1. 创造一个新节点s，并赋值。

2. 寻找到数据为i的结点p。

3. 将s的后继指向p的后继

4. 将p的后继指向s

   时间复杂度：O(n)

   空间复杂度：O(1)

void mid_insert(int k,linklist head,int i)
{
	node* s=(node*)malloc(sizeof(node));
	s->element=k;// 数据写入结点 
	
	node* p=find(i,head);// 找到P结点 
	
	s->next=p->next;// 插入 
	p->next=s;
	
}

第二种情况

​ 在第i个位置插入数据域为k的新结点

1. 创造一个新节点s，并赋值。

2. 寻找到位置为i-1的结点p。

3. 将s的后继指向p的后继

4. 将p的后继指向s

   时间复杂度：O(n)

   空间复杂度：O(1)

void i_insert(int k,linklist head,int i)
{
	node* s=(node*)malloc(sizeof(node));
	s->element=k;// 数据写入结点
	node *p=head;// 找第i-1个结点
	int j=0;
	while(j<i-1)
	{
		p=p->next;
		j++;
	}
	s->next=p->next;
	p->next=s;
	// 注意：不带头结点时的代码：分i=1时的特判和i！=1	
}

单向链表总代码

#include <stdio.h>
#include <stdlib.h>
// 带头结点单链表
typedef struct NodeList {// 属性集合（结点） 
    // 数据
    int element;
    // 指向下一个结点指针 
    struct NodeList* next;
}node, * linklist;

linklist initlist();// 初始化链表
void head_insert(int, linklist);// 头插法添加数据
void tail_insert(int, linklist);// 尾插法添加数据
void delete_node(int, linklist);// 删除操作
void modify_node(int, linklist);// 修改操作
node* find(int, linklist);// 查找操作
void mid_insert(int, linklist, int);// 在数据为i的结点后插入数据域为k的新结点
void i_insert(int, linklist, int);// 在第i个位置插入数据域为k的新结点
void printff(linklist);// 打印链表

int main()
{
    linklist head = initlist();
    head_insert(1, head);
    head_insert(2, head);
    tail_insert(3, head);
    tail_insert(4, head);
    printff(head);
    delete_node(2, head);
    delete_node(4, head);
    printff(head);
    mid_insert(2, head, 3);
    mid_insert(5, head, 2);
    printff(head);
    i_insert(6, head, 1);
    i_insert(7, head, 3);
    printff(head);
    return 0;

}

linklist initlist()
{// 初始化带头结点的单链表 
    linklist head = (linklist)malloc(sizeof(node));// head指向头结点 
    if (head == NULL)// malloc 需要判断 内存分配是否成功
    {
        printf("内存分配不成功\n");// 内存分配不成功 
    }
    else {// 分配成功 
        head->next = NULL;
    }
    return head;
}

void head_insert(int k, linklist head)// 头插法添加元素
{
    node* newNode = (node*)malloc(sizeof(node));
    newNode->element = k;// 数据写入结点 

    newNode->next = head->next;
    head->next = newNode;

}

void tail_insert(int k, linklist head)// 尾插法添加数据
{
    node* newNode = (node*)malloc(sizeof(node)); // 为新节点分配内存

    newNode->element = k; // 数据写入节点
    newNode->next = NULL; // 新节点的 next 指针初始化为 NULL

    node* temp = head; // 临时指针指向头节点
    while (temp->next != NULL) { // 遍历到链表末尾
        temp = temp->next;
    }
    temp->next = newNode; // 将新节点连接到链表末尾
}

void delete_node(int k, linklist head)
{
    // 这个链表是否存在，还能否继续删除 
    if (head == NULL || head->next == NULL)
    {
        printf("空链表\n");// 返回是空链表 
        // 要先判断这个链表是不是空的，也就是还能不能删
        return;
    }
    node* p = find(k, head);
    if (p == NULL)
    {
        printf("未找到删除结点\n");// k不在链表中 
    }
    else {// 要删除第i个结点，要先找到第i-1个 
        node* q = head;
        while (q != NULL && q->next != p)// 找到第i-1个 
        {
            q = q->next;
        }
        q->next = p->next;
        free(p);
    }
}

void modify_node(int k, linklist head)
{
    // 这个链表是否存在，还能否继续删除 
    if (head == NULL || head->next == NULL)
    {
        printf("空链表\n");// 返回是空链表 
        // 要先判断这个链表是不是空的，也就是还能不能删
        return;
    }
    node* p = find(k, head);
    if (p == NULL)
    {
        printf("未找到删除结点\n");// k不在链表中 
    }
    else {
        p->element = k;
    }
}


node* find(int k, linklist head)
{
    node* p = head->next;//第一个元素 
    while (p != NULL && p->element != k)
    {
        p = p->next;
    }
    return p;//若没找到，则p=NULL,用查询结果的时候判断有没有找到 
}

void mid_insert(int k, linklist head, int i)
{
    node* s = (node*)malloc(sizeof(node));
    s->element = k;// 数据写入结点 

    node* p = find(i, head);// 找到P结点 

    s->next = p->next;// 插入 
    p->next = s;

}

void i_insert(int k, linklist head, int i)
{
    node* s = (node*)malloc(sizeof(node));
    s->element = k;// 数据写入结点
    node* p = head;// 找第i-1个结点
    int j = 0;
    while (j < i - 1)
    {
        p = p->next;
        j++;
    }
    s->next = p->next;
    p->next = s;
    // 注意：不带头结点时的代码：分i=1时的特判和i！=1	
}

void printff(linklist head)
{
    node* p;
    p = head->next;

    while (p != NULL)
    {
        printf("%d ", p->element);
        p = p->next;
    }
    printf("\n");
}

双向链表

​ 有时候以倒序扫描链表很方便。标准实现方法此时无能为力，然而解决方法却很简单。只要在数据结构上附加一个域使它包含指向前一个单元的指针即可。其开销是一个附加的链，它增加了空间的需求，同时也使得插入和删除的开销增加一倍，因为有更多的指针需要定位。另外，它简化了删除操作，因为你不再被迫使用一个指向前驱元的指针来访问一个关键字，这个信息是现成的。

// 双向链表 //
typedef struct NodeList{// 属性集合（结点） 
    // 数据
    int element;

    // 指向下一个结点指针 
    struct NodeList* next; 
    // 指向前一个结点指针 
    struct NodeList* pr;
}node,*linklist;

linklist initlist()// 初始化带头结点的双链表 
{
    linklist head=(linklist)malloc(sizeof(node));// head指向头结点 
    if(head==NULL)// malloc 需要判断 内存分配是否成功
    {
        // 内存分配不成功 
    } 
    else{// 分配成功 
        head->next=NULL;
        head->pr =NULL; 
    } 
    return head; 
} 
// 增删改查时多一个对前驱指针的处理 
// 插入及删除注意代码顺序 

循环链表

​ 让最后的单元反过来直指第一个单元是一种流行的做法。它可以有表头，也可以没有表头(若有表头，则最后的单元就指向它)。这无疑会影响某些测试，不过这种结构在某些应用程序中却很流行。

// 只需要在初始化时，让头结点自己指向自己，循环起来即可，
// 其他操作同单链表 
linklist initlist() // 初始化带头结点的循环单链表 
{
    linklist head=(linklist)malloc(sizeof(node));// head指向头结点 
    if(head==NULL)// malloc 需要判断 内存分配是否成功
    {
        // 内存分配不成功 
    } 
    else{// 分配成功 
        /*更改：head->next=NULL;*/
        head->next=head;// 自己指向自己
    } 
    return head; 
} 

循环双向链表

​ 循环双向链表(第一个单元的前驱元指针指向最后的单元)。

// 循环双向链表 //
linklist initlist()
{ 
	linklist head=(linklist)malloc(sizeof(node));// head指向头结点 
	if(head==NULL)// malloc 需要判断 内存分配是否成功
	{
		// 内存分配不成功 
	 } 
	 else{// 分配成功 
	 	head->next=head;
	 	head->pr =head; 
	 } 
	return head; 
 } 

栈

​ 栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶（ top ）。对栈的基本操作有进栈（ push ）和出栈（ pop ）操作，前者相当于插入，后者相当于删除。

​ 栈又叫做LIFO（ 后进先出 ），这就是栈的最主要特点。

​ 栈有两种实现方式，一种是顺序存储结构、链式存储结构 。

​ 栈的所有操作的时空复杂度都为O(1) （ 出去开辟栈空间的内存损耗 ），后面不再赘述。

顺序栈

​ 顺序栈是比较流行的实现栈的方式。这种策略的唯一潜在危害是我们需要先声明一个固定大小的数组。当然在这边演示我使用的指针来表示栈中元素。注释掉的是没使用指针，直接用来数组来表示。

属性集合

#define maxsize 10
///顺序栈///
/*typedef struct{
	int date[maxsize];//栈中元素 
	int top;// 栈顶指针 	
}sstack;*/ 

typedef struct{
	int *date;//栈中元素 
	int top;// 栈顶指针 	
}sstack;

操作集合

//栈操作：初始化，判空，入栈（push),出栈（pop),读取栈顶元素（top）
sstack initstack();// 初始化栈
void Pushh(sstack*,int);// 入栈操作
void Popp(sstack*);// 出栈操作
void gettop(sstack);// 读取栈顶操作

顺序栈之初始化操作

​ 顺序栈初始化时，先申请10个单位的int型的空间。接着初始化top指针为-1。（ 这里栈顶指针的叫法是象征意义，这个top实际上不是指针，只是象征性的指向栈顶而已 ）。对top的初始化有差异，这边是把栈顶指针初始化为-1当然可以初始化为0，两者在后续操作中具体的操作顺序会进行改变。

//初始化 
sstack initstack()
{
    sstack s;
    s.date =(int*)malloc(sizeof(int)*maxsize);
    s.top=-1;//初始化栈顶指针
    //也有 s.top=0
    // =-1,先加后赋值，指针指向栈顶元素
    //=0，先赋值再加，指针指向 栈顶元素的下一个存储单元 
    return s;
} 

顺序栈之入栈操作

​ 顺序栈的入栈操作，由于我们对栈中的元素进行了更改，所以我们要通过指针转递（ 整个数据结构我们使用的C语言，而不是C++所以我们不使用引用 ）。要先对栈进行判断，栈是否满。

//入栈--对栈进行了修改，指针传递 
void Pushh(sstack *s,int k)
{
    //栈空间固定，加入一个元素要先判断是否满了，还能不能加入 
    if(s->top==maxsize-1)// 由于我们设的top是-1，所以判断时用maxsize-1
    {
        printf("栈满\n");//栈满报错，不能加入 
    }
    else{
        s->top++;
        s->date [s->top]=k;
        // s.date [++s.top]=k;//（ date[maxsize]形式 ）
    } 
}

顺序栈之出栈操作

​ 出栈操作同样是对栈的内容进行了更改，所以我们使用指针来传递栈。在出栈操作前我们要先判断栈是否为空，接着我们只需要将栈顶指针减一即可。（ 栈顶指针以上的数据，我们叫做垃圾值， 当有新的值入栈时，会直接覆盖到哪些值 ）

//出栈
void Popp(sstack *s)
{
    //删除之前判空，还有没有的删
    if(s->top==-1)
    {
        printf("栈空\n");//栈空报错，不能删除 
    } 
    else{
        s->top--;
    } 
}

顺序栈之读取栈顶操作

​ 只读取栈顶，不需要改变栈，所以只要传形参就行。在读取操作前同样要进行判空。

//读取栈顶元素
void gettop(sstack s)
{
    //判空，还有没有的读取 
    if(s.top==-1)
    {
        printf("栈空\n");//栈空报错，不能删除 
    } 
    else{
        printf("%d\n",s.date[s.top]);
    } 

} 

顺序栈总代码

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10

///顺序栈///
/*typedef struct{
	int date[maxsize];//栈中元素 
	int top;// 栈顶指针 	
}sstack;*/ 

typedef struct{
    int *date;//栈中元素 
    int top;// 栈顶指针 	
}sstack;


//栈操作：初始化，判空，入栈（push),出栈（pop),读取栈顶元素（top）
sstack initstack();// 初始化栈
void Pushh(sstack*,int);// 入栈操作
void Popp(sstack*);// 出栈操作
void gettop(sstack);// 读取栈顶操作

//--------------------------------------------------------------------- 
//初始化 
sstack initstack()
{
    sstack s;
    s.date =(int*)malloc(sizeof(int)*maxsize);
    s.top=-1;//初始化栈顶指针
    //也有 s.top=0
    // =-1,先加后赋值，指针指向栈顶元素
    //=0，先赋值再加，指针指向 栈顶元素的下一个存储单元 
    return s;
} 

//入栈--对栈进行了修改，指针传递 
void Pushh(sstack *s,int k)
{
    //栈空间固定，加入一个元素要先判断是否满了，还能不能加入 
    if(s->top==maxsize-1)// 由于我们设的top是-1，所以判断时用maxsize-1
    {
        printf("栈满\n");//栈满报错，不能加入 
    }
    else{
        s->top++;
        s->date [s->top]=k;
        // s.date [++s.top]=k;//（ date[maxsize]形式 ）
    } 
}

//出栈
void Popp(sstack *s)
{
    //删除之前判空，还有没有的删
    if(s->top==-1)
    {
        printf("栈空\n");//栈空报错，不能删除 
    } 
    else{
        s->top--;
    } 
}

//读取栈顶元素
void gettop(sstack s)
{
    //判空，还有没有的读取 
    if(s.top==-1)
    {
        printf("栈空\n");//栈空报错，不能删除 
    } 
    else{
        printf("%d\n",s.date[s.top]);
    } 

} 
int main()
{
    int x;
    sstack s=initstack();
    Pushh(&s,1);
    Pushh(&s,2);
    Pushh(&s,3);
    gettop(s);

    Popp(&s);
    gettop(s);

    Popp(&s);
    gettop(s);
    Pushh(&s,4);
    gettop(s);
    return 0; 

} 

链栈

​ 链栈的实现依托于单链表，所以要先清楚单链表的内容。链栈延续了单链表的有点，不用担心爆栈，当然由于大量的指针操作也带来了压力。

属性集合

///链栈--单链表实现栈///
typedef struct listackNode{// 链栈结点 
	int date;// 链栈结点中元素 
	struct listackNode* next;// 指针 	
}sstack,*listack;
// 此处的listack与链表代码中的 linklist类似
// listack==sstack *;
// 使用 listack 声明链栈中的结点指针，意在强调操作对象是栈； 
// 使用 sstack* 声明链栈中的结点指针，意在强调操作对象是栈中的某个结点 

// 链栈中无栈顶指针，如何实现在栈顶操作，实现先进后出
// 直接在链表表头进行操作，链表表头相当于栈顶
// 入栈:头插。 出栈：删除首元结点 

操作集合

// 栈操作：初始化，判空，入栈（push),出栈（pop),读取栈顶元素（top）
sstack initstack();// 初始化栈
void Pushh(sstack*,int);// 入栈操作
void Popp(sstack*);// 出栈操作
void gettop(sstack);// 读取栈顶操作

链栈之初始化操作

​ 先申请内存空间，并且初始化链栈。如果从链表的角度出发，其实s是这个单链表的头节点。

//初始化 
listack initstack()
{
    listack s=(listack)malloc(sizeof(sstack));
    s->next=NULL;
    return s;
} 

链栈之入栈操作

​ 在链栈属性集合中已经说明，由于单链表的特性，链栈没有所谓的栈顶指针，且要使用头插法来进行节点的添加。链栈的栈顶元素是s->next。

//入栈--对栈进行了修改，指针传递 
void Pushh(listack s,int k)
{
    //链表结点个数可以动态调整，无需判满
    //头插法插入结点，实现入栈 
    sstack *p=(sstack*)malloc(sizeof(sstack));//p是待插入的新结点 
    p->date =k;
    //头插法 插入p 
    p->next =s->next;
    s->next =p;  
}

链栈之出栈操作

​ 在出栈操作前要先判断栈是否为空，接着定义一个指针p指向要出栈的节点，将头节点s的后继指向p的后继，接着释放掉p指向的节点。

//出栈
void Popp(listack s)
{
    // 删除之前判空
    if(s->next==NULL)
    {
        printf("栈空\n");// 栈空报错，不能删除 
    } 
    else
    {
        sstack *p=s->next ;// 让p指向待删除的首元结点

        s->next =p->next ;
        free(p); 
    } 
} 

链栈之读取栈顶操作

​ 读取要判空，接着直接读取就行

// 读取栈顶元素
void gettop(listack s)
{
    // 判空
    if(s->next==NULL)
    {
        printf("栈空\n");// 栈空报错，不能删除	 
    } 
    else
    {
        printf("%d\n",s->next->date); 
    } 

} 

链栈总代码

#include<stdio.h>
#include<stdlib.h>
///链栈--单链表实现栈///
typedef struct listackNode{//链栈结点 
    int date;//链栈结点中元素 
    struct listackNode* next;//指针 	
}sstack,*listack;
//此处的listack与链表代码中的 linklist类似
//listack==sstack *;
//使用 listack 声明链栈中的结点指针，意在强调操作对象是栈； 
//使用 sstack* 声明链栈中的结点指针，意在强调操作对象是栈中的某个结点 


//链栈中无栈顶指针，如何实现在栈顶操作，实现先进后出
//直接在链表表头进行操作，链表表头相当于栈顶
//入栈:头插。 出栈：删除首元结点 

//--------------------------------------------------------------------- 
//栈操作：初始化，判空，入栈（push),出栈（pop),读取栈顶元素（top）
//以顺序栈为例子 
//初始化 
listack initstack()
{
    listack s=(listack)malloc(sizeof(sstack));
    s->next=NULL;
    return s;
} 

//入栈--对栈进行了修改，指针传递 
void Pushh(listack s,int k)
{
    //链表结点个数可以动态调整，无需判满
    //头插法插入结点，实现入栈 
    sstack *p=(sstack*)malloc(sizeof(sstack));//p是待插入的新结点 
    p->date =k;
    //头插法 插入p 
    p->next =s->next;
    s->next =p;  

} 
//出栈
void Popp(listack s)
{
    // 删除之前判空
    if(s->next==NULL)
    {
        printf("栈空\n");// 栈空报错，不能删除 
    } 
    else
    {
        sstack *p=s->next ;// 让p指向待删除的首元结点

        s->next =p->next ;
        free(p); 
    } 
} 
// 读取栈顶元素
void gettop(listack s)
{
    // 判空
    if(s->next==NULL)
    {
        printf("栈空\n");// 栈空报错，不能删除	 
    } 
    else
    {
        printf("%d\n",s->next->date); 
    } 

} 
int main()
{
    int x;
    listack s=initstack();
    Pushh(s,1);
    Pushh(s,2);
    Pushh(s,3);
    gettop(s);

    Popp(s);
    gettop(s);
    return 0; 
} 

栈的应用

​ 栈在平时在很多地方有所体现。下面举例四种情况。

栈应用之平衡符号

​ 我们使用的编译器就用栈来判断我们的语法错误。我们在使用C语言时有很高的自由度，甚至出现隔行书写语句的情况（ 当然这不是一个好的习惯 ）。这就是由于栈的特性所决定的。

这个简单的算法用到一个栈，叙述如下:

​ 做一个空栈。读入字符直到文件尾。如果字符是一个开放符号，则将其推入栈中如果字符是一个封闭符号，则当栈空时报错;否则，将栈元素弹出。如果弹出的符号不是对应的开放符号，则报错。在文件尾，如果栈非空则报错。

栈应用之后缀表达式

​ 由于我们在算数加减乘除过程中会有先后顺序，而较为老的计算器并不能完成顺序的排列。解决这种情况较为简单的方法是使用后缀表达式（ 如何从普通表达式转化为后缀表达式稍后再讲，推荐先看后面那个 ）。

​ 下面我使用6 5 2 3 + 8 * + 3 + *做例子来演示后缀表达式的过程中栈的变化情况。

​ 计算一个后缀表达式花费的时间是O(n)。用该算法计算是十分简单，而在计算过程中，无需知道优先规则，直接计算即可。

代码实现

​ 需要注意的是，下面的代码只适用于整数的加减乘除的计算，若想进行浮点数的计算要更改数据类型。此外，下述代码我用数组来模拟栈，从而简化操作。由于测试的数据量较小，所以我开辟的空间也较小，若想测试大数据，请自行更改数据量。

​ 该代码没有添加异常数据的检验，所以在使用时请确定输入的是正确的后缀表达式。

#include <stdio.h>
#include <string.h>
int suffixExpression(char arr[]) {
    int stack[50]; // 使用整数数组作为栈
    int top = -1;
    int n = strlen(arr);
    int x1 = 0;
    int x2 = 0;

    for (int i = 0; i < n; i++) {
        // 检查当前字符是否是操作数
        if (arr[i] >= '0' && arr[i] <= '9') {
            // 将字符转换为整数并压入栈
            stack[++top] = arr[i] - '0';
        } else {
            x1 = stack[top--]; // 弹出栈顶元素为第一个操作数
            x2 = stack[top--]; // 弹出栈顶元素为第二个操作数

            if (arr[i] == '+') {
                stack[++top] = x2 + x1;
            } else if (arr[i] == '-') {
                stack[++top] = x2 - x1;
            } else if (arr[i] == '*') {
                stack[++top] = x2 * x1;
            } else if (arr[i] == '/') {
                stack[++top] = x2 / x1;
            }
        }
    }

    return stack[top];
}

int main() {
    char arr[] = "6523+8*+3+*";
    int ans = suffixExpression(arr);
    printf("%d\n", ans); // 输出结果
    return 0;
}

栈应用之中缀到后缀转换

​ 在日常生活中，我们一般不会用后缀表达式来表示算数，我们一般使用中缀表达式（ 即标准的算数形式 ）。那么就要求我们要将中缀表达式转化为后缀表示。

​ 对栈的维护简单点来说就是：栈中只能进入运算符，当发现入栈元素的优先级大于等于栈顶元素，则栈顶元素出栈。当遇到")"入栈，则栈中到"("的所有元素全部输出。若输入为空且栈不为空，则输出栈中所有的元素。需要注意的是后缀表达式不包含括号，所以在栈顶弹出括号时不用输出。

​ 下面我使用a + b *c + ( d * e + f ) * g做例子来演示从中缀到后缀变化过程中栈的变化情况。

代码表示

​ 需要注意的是，下述代码我用数组来模拟栈，从而简化操作。由于测试的数据量较小，所以我开辟的空间也较小，若想测试大数据，请自行更改数据量。

​ 该代码没有添加异常数据的检验，所以在使用时请确定输入的是正确的中缀表达式。

#include <stdio.h>
#include <string.h>

// 判断运算符的优先级
int precedence(char op) {
    if (op == '+' || op == '-') 
        return 1;
    if (op == '*' || op == '/') 
        return 2;
    return 0;
}

void infixToSuffix(char infix[],char suffix[]) {
    int n = strlen(infix);
    // 模拟栈 
    char st[10];
    int top = -1;
    // 用来完成后缀表达式 
    int k = 0;
    for (int i = 0; i < n; i++) {
        char c = infix[i];
        
        if (c != '+' && c != '-' && c != '*' && c != '/' && c != '(' && c != ')'){
        	suffix[k++] = c; 
		}else if(c == '('){
			st[++top] = c;
		}else if (c == ')') {
			 while (top != -1 && st[top] !=  '(') {
	            suffix[k++] = st[top--];
			}
			top--;// 去除'(' 
    	}else{
    		 while (top != -1 && precedence(st[top]) >= precedence(c)) {
                suffix[k++] = st[top--];
            }
            st[++top] = c;
		}  	    
	}
	
	// 输出剩余的运算符
    while (top != -1) {
        suffix[k++] = st[top--];
    }

    suffix[k] = '\0'; // 添加字符串结束符
	
    return;
}

int main() {
    char infix[] = "a+b*c+(d*e+f)*g";
    char suffix[50];
    infixToSuffix(infix,suffix);
    int n = strlen(suffix);
    for(int i = 0; i < n; i++)
    {
    	printf("%c",suffix[i]);// 输出结果
	}
    return 0;
}

栈应用之函数调用

​ 函数调用就是由栈来完成。在平时用dev`写代码时，在函数调用时要求调用的函数在主函数之前实现或者声明，这就是由于调用函数是由栈实现的。

队列

​ 队列是⼀种特殊的线性表，特殊之处就在于它只允许在表的前端进行删除操作，在表的后端进行插入操作。和栈⼀样，队列也是⼀种操作受到限制的线性表。进行插入操作的端称之为队尾( rear )，进行删除操作的端称之为队头( front )。队列中没有队列的时候，称之为空队列。队列的数据元素，又叫做队列元素。在队列中插入⼀个队列元素称之为入队( Enqueue )，在队列中删除⼀个队列元素，称之为出队( Dequeue )。因为队列只允许在⼀端插入，在另⼀端删除，所以只有最早进入的队列元素才可以从队列中删除，故队列又称为先进先出线性表。

​ 与链表和栈相同的是，队列有两种实现方式，一种是顺序存储结构、链式存储结构 。（ 单向队列我会用链式存储来实现，循环队列使用顺序表的形式来实现，双端队列两种都会实现 ）

单项队列

​ 单向队列是最为简单的一种队列，接下来具体讲解一下具体的实现过程，以及代码的实现。

属性集合

///链式队列//
typedef struct qnode{//链式队列结点 
    int data;//队列元素
    struct qnode *next;//指向下一个结点的指针 
}qnode,*lqueue; 
// qnode,*lqueue的具体含义和区别在链表和栈以及说的很清楚了，这里不再赘述

typedef struct linkqueue{//链式队列---可选，不写结构体，直接定义对头队尾指针也可 
    lqueue front,rear;//队头队尾指针,队首指针是链表头结点 
}linkqueue;

操作集合

void initqueue(linkqueue *q)；// 初始化
void enqueue(linkqueue* q,int x);// 入队
void dequeue(linkqueue* q);  // 出队

单向队列之初始化操作

	先初始化队列的头节点与头尾指针，这里由于在定义属性进行了结构体的定义，所以就可以直接定义。如果没有定义结构体，那就指定两个指针作为头尾指针，并且定义头节点。内存分配成功后，将头节点的后继置空。

​ 这边解释一下结构体指针q，这个q可能不太好理解。q是一个结构体指针，这个结构体种包含两个指针，分别表示头尾指针。

//初始化
void initqueue(linkqueue *q)
{   
    // 需要正确理解下面这条语句，只定义了一个节点，但是有两个指针指向这个节点。
    q->rear=q->front=(lqueue)malloc(sizeof(qnode));
    if(q->front==NULL)
    {
        printf("分配失败\n");
    }
    else{
        q->front->next=NULL;
    }
} 

单向队列之入队操作

​ 若对链表熟悉的话，下面的这些操作很好理解。定义一个节点，给节点的数据域赋值。再通过链表的操作将新节点插入到队尾。

//入队 
void enqueue(linkqueue* q,int x)
{
    lqueue s=(lqueue )malloc(sizeof(qnode));
    s->data =x;
    s->next =NULL;// 新节点插入到链尾
    q->rear->next=s;
    q->rear =s; 
} 

单向队列之出队操作

​ 和栈相同的是再出队前要先判断队列是否为空。这里和栈不同的在删除时要判断是否只存在一个节点，若是只存在一个节点，那要对尾指针进行处理（ 尾指针指向头节点），不然尾指针为空，在后续的入队操作中会报错。

//出队，队首指针是链表头结点 ，删除的是队首指针的下一个，即front->next 
void dequeue(linkqueue* q) 
{
    int x;//保存出队元素 
    //先判空，不空才能出 
    if(q->front->next==NULL)
    {
        printf("空\n");//队空，报错 
    } 
    else{
        lqueue p=q->front->next; 
        x=p->data;
        q->front ->next=p->next ;
        printf("%d\n",x);
        //若原队列只有一个结点了，则删除边空，需要处理尾指针 
        if(q->rear =p)
            q->rear =q->front;
        free(p); 
    }
}

单向队列总代码

#include<stdio.h>
#include<stdlib.h>

///链式队列//
typedef struct qnode{//链式队列结点 
	int data;//队列元素
	struct qnode *next;//指向下一个结点的指针 
}qnode,*lqueue; 

typedef struct linkqueue{//链式队列---可选，不写结构体，直接定义对头队尾指针也可 
	lqueue front,rear;//队头队尾指针,队首指针是链表头结点 
}linkqueue;

//初始化
void initqueue(linkqueue *q)
{   
    // 需要正确理解下面这条语句，只定义了一个节点，但是有两个指针指向这个节点。
    q->rear=q->front=(lqueue)malloc(sizeof(qnode));
    if(q->front==NULL)
    {
        printf("分配失败\n");
    }
    else{
        q->front->next=NULL;
    }
} 

//入队 
void enqueue(linkqueue* q,int x)
{
	lqueue s=(lqueue )malloc(sizeof(qnode));
	s->data =x;
	s->next =NULL;//新节点插入到链尾
	q->rear->next=s;
	q->rear =s; 
 } 
 //出队，队首指针是链表头结点 ，删除的是队首指针的下一个，即front->next 
void dequeue(linkqueue* q) 
{
	int x;//保存出队元素 
	//先判空，不空才能出 
	if(q->front->next==NULL)
	{
		printf("空\n");//队空，报错 
	 } 
	else{
		lqueue p=q->front->next; 
		x=p->data;
		q->front ->next=p->next ;
		printf("%d\n",x);
		//若原队列只有一个结点了，则删除边空，需要处理尾指针 
		if(q->rear =p)
		q->rear =q->front;
		free(p); 
	}
}
int main()
{
	linkqueue* q;
	q=(linkqueue*)malloc(sizeof(linkqueue));
	initqueue(q);
	enqueue(q,1);
	enqueue(q,2);
	enqueue(q,3);
	dequeue(q);
	dequeue(q);
	dequeue(q);
	dequeue(q);
	enqueue(q,4);
    dequeue(q);
	dequeue(q);
	return 0;
 } 

循环队列

​ 队列的移除分为真溢出和假溢出（ 由于在实现单向队列时，使用的是链式存储，所以不存在溢出问题）。真溢出是队列中装满元素导致溢出。假溢出是指由于出队要使头指针向后移动，导致队列存储空间变小，最终导致溢出，事实上数值中并没真正装满。

​ 平时我们在自己定义队列时，一般会使用链式队列或者顺序表循环队列。

​ 那么循环队列是如何定位数据的方法是通过取余操作。比如数组的最大容量是10，而尾指针已经到了11，那就代表尾指针指向的实际队列第一个位置（ rear % maxSize = 1 )。

属性集合

#define maxsize 10
///顺序循环队列/// 
typedef struct{
	int date[maxsize];//队列中数据元素
	int front,rear;//对头队尾指针（以索引下标形式表示指针） 
}sqqueue; 
//实现一个循环队列 
//牺牲一个单元来区分头尾

操作集合

void initqueue(linkqueue *q)；// 初始化
void enqueue(linkqueue* q,int x);// 入队
void dequeue(linkqueue* q);  // 出队

循环队列之初始化操作

//初始化
void initqueue(sqqueue *q)
{
    q->rear=q->front =0;//初始首尾指针 
} 

循环队列之入队操作

​ 循环队列同样会出现溢出的情况，也就是所谓的真溢出的情况。所以在入队时要进行判断队列是否被装满。判满的方法是使用rear+1取余的值的位置是否为front。同样我们在移动尾指针的时候也需要进行取余操作。

//入队
void enqueue(sqqueue *q,int x)
{
	//先判满，不满才能装
	if((q->rear +1)%maxsize==q->front )
	{
		printf("队满");//队满，报错 
	 } 
	else
	{
		q->date[q->rear]=x;
		q->rear =(q->rear +1)%maxsize;//队尾指针加1取模 
	 } 	 
 } 

循环队列之出队操作

​ 出队同样需要进行判断队列是否为空。剩余的队首操作和入队的队尾操作相同。

//出队
void dequeue(sqqueue *q)
{
    int x;//保存出队元素 
    //先判空，不空才能出 
    if(q->front ==q->rear)
    {
        printf("队空");//队空，报错 
    } 
    else
    {
        x=q->date [q->front];
        q->front =(q->front +1)%maxsize;//队首指针加1取模 
        printf("%d\n",x);
    } 	 
}  

循环队列总代码

#include<stdio.h>
#include<stdlib.h>
#define maxsize 10
///顺序循环队列/// 
typedef struct{
    int date[maxsize];//队列中数据元素
    int front,rear;//对头队尾指针（以索引下标形式表示指针） 
}sqqueue; 
//实现一个循环队列 
//牺牲一个单元来区分头尾

//初始化
void initqueue(sqqueue *q)
{
    q->rear=q->front =0;//初始首尾指针 
} 


//入队
void enqueue(sqqueue *q,int x)
{
    //先判满，不满才能装
    if((q->rear +1)%maxsize==q->front )
    {
        printf("队满");//队满，报错 
    } 
    else
    {
        q->date [q->rear]=x;
        q->rear =(q->rear +1)%maxsize;//队尾指针加1取模 
    } 	 
} 
//出队
void dequeue(sqqueue *q)
{
    int x;//保存出队元素 
    //先判空，不空才能出 
    if(q->front ==q->rear)
    {
        printf("队空");//队空，报错 
    } 
    else
    {
        x=q->date [q->front];
        q->front =(q->front +1)%maxsize;//队首指针加1取模 
        printf("%d\n",x);
    } 	 
}  
int main()
{
    sqqueue q;

    initqueue(&q);
    enqueue(&q,1);
    enqueue(&q,2);
    enqueue(&q,3);
    enqueue(&q,4);
    dequeue(&q);
    dequeue(&q);
    dequeue(&q);
    enqueue(&q,3);
    enqueue(&q,2);
    dequeue(&q);
    dequeue(&q);
    dequeue(&q);
    dequeue(&q);
    return 0;
} 

双端队列

​ 双端队列简单点来说就是两个队列合在一张表里。

​ 对于双端队列来说，就是两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。相对于普通队列。双端队列的入队和出队操作在两端都可以进进行。

​ 这种数据结构的特性，使得他更加的实用和方便。当你只允许使用一端出队、入队操作的时候，他等价于一个栈。当限制一端只能出队，另一端只能入队，他就等价于一个普通队列。

属性集合

// 链表实现的属性集合
#define msize 10
typedef struct linkqueue{
	int date;//数据元素
	struct linkqueue *pre;
	struct linkqueue *next; 
	//int size;元素个数 
}node; 
//全局变量；
node *mid;//中间结点,标记中间位置类似链表头结点作用,实际上我们用不到 
//但是中间结点也存数据。避免从左删到右边时，空的中间结点出问题
node *left;
node *right;//左右两端 
//----------------------------------------------------------------------------------------------
///双端队列的顺序表实现///
//双端队列用循环数组来实现
//属性集合
int *queue;//数组放元素 
int left,right;//分左右端指针 
int maxsize;//当前最大数组尺寸
int size;//当前元素个数 

​ 这里需要说明一下的是链式存储的mid指针的说明。其实双端队列就没有头节点的双向链表加了约束，由于没有头节点，所以我们需要一个指针指向中间的那个节点，这个中间不是绝对的是会相对移动的。特别是当队列为空时，三个指针都指向同一节点。（ 需要注意的是，mid指针指向的值依然需要存储数据 ）。

​ 再说明一下双端队列的顺序表实现，我们为了解决在一个单向数组内是实现双端队列的问题，我们采用的循环数组。头尾两个指针，一个顺时针走，一个逆时针走。（ 所谓的循环数组，只是名义上的，内存中依然是线性存储，我们通过取余来实现 ）

画图能力有限，请见谅

双端队列链式存储实现总代码

#include<stdio.h>
#include<stdlib.h>

#define msize 10

typedef struct linkqueue{
    int date;//数据元素
    struct linkqueue *pre;
    struct linkqueue *next; 
    //int size;元素个数 
}node; 
//全局变量；
node *mid;//中间结点,标记中间位置类似链表头结点作用,实际上我们用不到 
//但是中间结点也存数据。避免从左删到右边时，空的中间结点出问题
node *left;
node *right;//左右两端 
//初始化
void initqueue()
{
    left=right=(node* )malloc(sizeof(node));
    left->pre=right->next=NULL;

} 

//左边
void insert_left(int k)
{
    node *s=(node* )malloc(sizeof(node));
    s->date =k;
    //插入 
    s->pre =NULL;
    s->next =left;
    left->pre =s;

    left=s;
} 
void delete_left()
{
    if(left==NULL||left==right)
    {
        printf("空表\n");//空，报错处理
        return ; 
    } 
    node *s;
    s=left;
    left=left->next;
    s->next=NULL;
    left->pre=NULL;
    //int x=s->data;
    free(s);

} 
//右边 
void insert_right(int k)
{//right指向队尾的下一个元素 
    node *s=(node* )malloc(sizeof(node));
    s->next =NULL;
    right->date =k;
    right->next =s;
    s->pre =right;

    right=s;

}
void delete_right()
{//注意删的是right->pre ,right->pre才是真正的最后一个
    //实际操作时只需要把right删掉，即可

    if(right->pre==NULL)
    {
        printf("空表\n");//空，报错处理
        return ; 
    }
    node *s;
    s=right;
    right=right->pre; 
    //int x=right->date;
    s->pre=NULL;
    right->next=NULL; 
    free(s);

} 
void printff()
{
    node *s;
    s=left;
    while(s!=right&&s!=NULL)
    {
        printf("%d ",s->date); 
        s=s->next; 
    }
    printf("\n");
}
int main()
{
    initqueue();
    insert_left(1);
    insert_left(2);
    insert_left(3);
    insert_right(4);
    insert_right(5);
    printff();


    //delete_right();
    //printff();
    insert_right(6);
    delete_left();
    delete_left();
    delete_left();
    delete_left();
    printff();


} 

双端队列顺序表实现总代码

#include<stdio.h>
#include<stdlib.h>

#define msize 10
///双端队列的顺序表实现///
//双端队列用循环数组来实现。
//属性集合
int *queue;//数组放元素 
int left,right;//分左右端指针 
int maxsize;//当前最大数组尺寸
int size;//当前元素个数 

void initqueue()
{//初始化 
    queue=(int* )malloc(sizeof(int)*msize);
    maxsize=msize;
    size=0;
    left=right=0; 

}

//操作4种：左边插入删除，右边插入删除 
//左边 
void insert_left(int k)
{
    if(size==maxsize)
    {
        printf("满\n");//报错队满，失败或扩容 
    } 
    else
    {
        left--;//相当于前端延长
        left=(left+maxsize)%maxsize;//防止出界 
        queue[left]=k; 
        size++; 
    } 
}
void delete_left() 
{
    int x;
    if(size==0)
    {
        printf("空\n");//空，报错 
    }
    else{
        x=queue[left];
        left=(left+1)%maxsize;
        size--;
    } 

}
//右边 
void insert_right(int k)
{
    if(size==maxsize)
    {
        printf("满\n");//报错队满，失败或扩容 
    } 
    else
    {
        queue[right]=k;//先放入，再移动指针
        right=(right+1) %maxsize;//right指向最右端元素的下一个位置 
        size++;
    } 
}
void delete_right() 
{
    int x;
    if(size==0)
    {
        printf("空\n");//空，报错 
    }
    else{
        right--;
        right=(right+maxsize)%maxsize;
        size--;
        x=queue[right];
    } 

}
void printff()
{
    int x=left;
    int y=right;
    //printf("%d\n",x);
    if(x!=0)
    {

        for(int i=x;i < maxsize;i++)
        {
            printf("%d ",queue[i]);
        }
    }
    for(int i=0;i<y;i++)
    {
        printf("%d ",queue[i]);
    }
    printf("\n");	
}
int main()
{
    initqueue();
    insert_left(1);
    insert_left(2);
    insert_left(3);
    insert_right(4);
    insert_right(5);
    printff();


    //delete_right();
    //
    insert_right(6);
    printff();
    delete_left();
    delete_left();
    //delete_left();
    //delete_right();
    delete_right();
    delete_right();
    printff();
    return 0;
}

树

​ 之前的全部都是线性结构，相对来说较为简单，接下来是非线性结构。首先要提到的是树。树是一种非线性结构，存储的是具有⼀对多的关系的数据元素的集合。

普通树

​ 树中有很多特殊的情况，而这些特殊情况都摆脱不了树的一些基本定义和树的一些命名规则。

树的性质

树(Tree)是n(n≧0)个结点的有限集合T，若n=0时称为空树，否则：

⑴ 有且只有一个特殊的称为树的根(Root)结点；

⑵ 若n>1时，其余的结点被分为m(m>0)个互不相交的子集T~1~, T~2~, T~3~…T~m~，其中每个子集本身又是一棵树，称其为根的子树(Subtree)。

特征：树中各子树是互不相交的集合，树中至少有一个结点——根。

树的基本术语

⑴结点(node)：一个数据元素及其若干指向其子树的分支。

⑵结点的度(degree 、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。

⑶叶子(left)结点、非叶子结点：树中度为0的结点称为叶子结点(或终端结点)。相对应地，度不为0的结点称为非叶子结点(或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。

⑷孩子结点、双亲结点、兄弟结点：一个结点的子树的根称为该结点的孩子结点(child)或子结点；相应地，该结点是其孩子结点的双亲结点(parent或父结点。同一双亲结点的所有子结点互称为兄弟结点。

⑸层次、堂兄弟结点规定树中根结点的层次为1，其余结点的层次等于其双亲结点的层次加1。双亲结点在同一层上的所有结点互称为堂兄弟结点。

(6)结点的层次路径、祖先、子孙从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径(有且只有一条)。结点p的层次路径上的所有结点（p除外）称为p的祖先(ancester) 。以某一结点为根的子树中的任意结点称为该结点的子孙结点(descent)。

(7)有序树和无序树：对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为有序树，否则称为无序树。

(8)森林(forest)**：**是m(m≧0)棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。

(9)树的深度(depth)：树中结点的最大层次值，又称为树的高度，

树的存储之双亲表示法

（1） 顺序存储---基于数组（一维的结构体数组） （2） 思想： 顺序存储各结点的同时， 把各结点父亲的下标也存储下来 优点： 找父亲方便， 一次就能找到 缺点： 找孩子不方便， 遍历整个数组

属性集合

typedef struct TreeNode {
    int data;//树中存放的真实的数据
    int parent;//父节点 -1代表没有父节点
}Node;

/*全局变量*/
Node* node[5];//父亲表示法的顺序表表示
int size= 0;//当前元素的个数
int maxSize = 5;//元素的总个数

操作集合

void insert_root(int);//建立根节点
void insert_child(int,int);//插入元素
int find_parent(int);// 寻找父节点

建立根节点

​ 创造一个根节点，将根节点的数据和父亲节点赋值给根节点。（ 父亲节点是-1，说明该节点没有父亲节点）并将该节点存放进数组中。

/*
创建根节点
key 根节点的关键字
*/
void insert_root(int key) 
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = key;
    new_node->parent = -1;
    node[size] = new_node;
    size++;
}

插入元素

​ 用顺序表存储的结构在插入时都要进行判满。双亲表示法也不例外。若顺序表没满则要判断在顺序表中是否存在这个父节点。余下操作和建立根节点的操作相同。

/*
插入元素
int key 关键字
int parent 父节点的值
*/
void insert_child(int key, int parent)
{
    if (size == maxSize)
    {
        //元素已满 要么提示 要么扩容
        printf("已满");
    }
    else 
    {
        //判断一下 是否有这个父节点
        int parent_index = find_parent(parent);
        if (parent_index == -1)
        {
            //没有该父节点
            printf("没有该父节点");
        }
        else
        {
            Node* new_node = (Node*)malloc(sizeof(Node));
            new_node->data = key;
            new_node->parent = parent_index;
            node[size] = new_node;
            size++;
        }
    }
}

双亲表示法的全部代码

#include<stdio.h>
#include<stdlib.h>

typedef struct TreeNode {
    int data;//树中存放的真实的数据
    int parent;//父节点 -1代表没有父节点
}Node;

/*全局变量*/
Node* node[5];//父亲表示法的顺序表表示
int size= 0;//当前元素的个数
int maxSize = 5;//元素的总个数

void insert_root(int);//建立根节点
void insert_child(int,int);//插入元素
int find_parent(int);

/*
创建根节点
key 根节点的关键字
*/
void insert_root(int key) 
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = key;
    new_node->parent = -1;
    node[size] = new_node;
    size++;
}

/*
插入元素
int key 关键字
int parent 父节点的值
*/
void insert_child(int key, int parent)
{
    if (size == maxSize)
    {
        //元素已满 要么提示 要么扩容
        printf("已满");
    }
    else 
    {
        //判断一下 是否有这个父节点
        int parent_index = find_parent(parent);
        if (parent_index == -1)
        {
            //没有该父节点
            printf("没有该父节点");
        }
        else
        {
            Node* new_node = (Node*)malloc(sizeof(Node));
            new_node->data = key;
            new_node->parent = parent_index;
            node[size] = new_node;
            size++;
        }
    }
}

/*
找到父节点的下标 返回-1代表没找到
*/
int find_parent(int parent)
{
    for (int i = 0; i < size; i++) {
        if (parent == node[i]->data)
        {
            return i;
        }
    }
    return -1;
}

树的存储之孩子表示法

(1)”顺序存储+链式存储”---基于数组+链表 (2)思想:存储各结点的同时，把孩子结点挂到自己的孩子链表里面去。

优点： 找孩子方便， 缺点： 找父亲不方便，

属性集合

typedef struct LinkList {
    int data;//存放数据
    struct LinkList* next;
}Node;

Node* node_array[100];//存储结点的数组
int size;//数组中元素的个数

操作集合

void Init(int);//初始化操作
void creat_tree(int, int);//构建树
int find_parent(int);//找到父节点

初始化

​ 创立节点添加入数组中，并将该节点赋值作为后续孩子节点的父亲节点节点。

/*初始化 并且建立根节点*/
void Init(int key)
{
    size = 0;
    //将新的结点添加到数组当中
    node_array[size] = (Node*)malloc(sizeof(Node));
    //给新节点赋值
    node_array[size]->data = key;
    node_array[size]->next = NULL;
    size++;
}

构建树

​ 首先把孩子节点添加进数组中，并给节点赋值。判定是否存在父亲节点。若存在则创建一个节点，并把这个节点连接在父节点后面。（ 这里是头插法添加的节点 ）

/*
int parent 父节点的值
int key  孩子结点的值
*/
void creat_tree(int parent, int key) 
{
    //先将孩子结点添加到数组当中
    node_array[size] = (Node*)malloc(sizeof(Node));
    //给新节点赋值
    node_array[size]->data = key;
    node_array[size]->next = NULL;
    size++;
    //找到父节点
    int index = find_parent(parent);
    if (index == -1)
    {
		printf("没有找到父亲节点");
    }
    else 
    {
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->data = key;
        new_node->next = node_array[index]->next;
        node_array[index]->next = new_node;
    }

}

孩子表示法的全部代码

#include<stdio.h>
#include<stdlib.h>

typedef struct LinkList {
    int data;//存放数据
    struct LinkList* next;
}Node;

Node* node_array[100];//存储结点的数组
int size;//数组中元素的个数

void Init(int);//初始化操作
void creat_tree(int, int);//构建树
int find_parent(int);//找到父节点

int main()
{
    Init(1);
    creat_tree(1, 2);
    creat_tree(1, 3);
    creat_tree(1, 4);
    creat_tree(2, 5);
    creat_tree(2, 6);
    creat_tree(3, 7);
    for (int i = 0; i < size; i++)
    {
        printf("父节点为%d", node_array[i]->data);
        Node* temp = node_array[i]->next;
        while (temp != NULL)
        {
            printf("孩子结点为%d", temp->data);
            temp = temp->next;
        }
        printf("\n");
    }
}
/*初始化 并且建立根节点*/
void Init(int key)
{
    size = 0;
    //将新的结点添加到数组当中
    node_array[size] = (Node*)malloc(sizeof(Node));
    //给新节点赋值
    node_array[size]->data = key;
    node_array[size]->next = NULL;
    size++;
}

/*
int parent 父节点的值
int key  孩子结点的值
*/
void creat_tree(int parent, int key) 
{
    //先将孩子结点添加到数组当中
    node_array[size] = (Node*)malloc(sizeof(Node));
    //给新节点赋值
    node_array[size]->data = key;
    node_array[size]->next = NULL;
    size++;
    //找到父节点
    int index = find_parent(parent);
    if (index == -1)
    {
        printf("没有找到父亲节点");
    }
    else 
    {
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->data = key;
        new_node->next = node_array[index]->next;
        node_array[index]->next = new_node;
    }

}

int find_parent(int parent)
{
    for (int i = 0; i < size; i++)
    {
        if (node_array[i]->data == parent) {
            return i;
        }
    }
    return -1;
}

树的存储的孩子兄弟表示法

​ 将整棵树用二叉链表存储起来： 从根节点开始， 依次去存储各个节点的孩子以及兄弟

优点： 找孩子方便， 缺点： 找父亲不方便

属性集合

//二叉链表的结点结构
typedef struct ChildSibling{
	int data;//数据	
	struct ChildSibling* child;// 第一个孩子指针域
	struct ChildSibling* sibling;//兄弟指针域
}Node; 
Node* root;//指向根节点的指针，同时也标记整棵树
Node* t;//临时指针 

操作集合

void Init(int);// 初始化
Node* getNode(Node*,int);// 查找数据为parent的节点
void insert(int,int);// 插入

初始化

​ 初始化就是创立一个节点。并将这个节点初始化。

//初始化，建立根节点
void Init(int key)
{
	root=(Node*)malloc(sizeof(Node));
	root->data =key;
	root->child =NULL;
	root->sibling =NULL;	
 } 

插入

​ 我们需要一个临时指针来存储找到父亲节点。然后创建一个新的节点。如果这个新节点不是父亲节点的第一个孩子，那就就要进入兄弟的那一个分支，通过头插进行添加。若是第一个孩子那就直接插入在孩子的指针域即可。

//插入 :key是插入的数据，parent是key的父亲结点的数据 
void insert(int key,int parent)
{
	t=getNode(root,parent); 
	if(t!=NULL)
	{
		Node* p=(Node*)malloc(sizeof(Node));
		p->data=key;
	
		if(t->child !=NULL)//key 不是parent的第一个孩子 
	   {
	   	    t=t->child ;
	   	    p->sibling =t->sibling;
	   	    t->sibling =p;
	   	    p->child =NULL;
	   }
		else{//key 是parent的第一个孩
			t->child =p;
			p->child =NULL;
			p->sibling=NULL;
			
		} 
	 } 
	
	else{
		//
	}
	
}

查找父节点 查找操作是为了能方便在插入的时候找到父亲节点。每次查找父亲节点都要遍历整一个树。通过递归遍历，递归的出口就是找到父亲节点并返回，或没有找到返回空。有两个递归的入口，一个是通过孩子指针域去找，一个是通过兄弟指针域去寻找。

//在以r为根的树中，查找数据为parent的结点
//递归 
Node* getNode(Node* r,int parent)
{
    if(r->data ==parent)//1
    {
        return r;
    }
    if(r->child !=NULL)//2
    {
        Node* x=getNode(r->child,parent);//调1 
        if(x!=NULL&&x->data ==parent)
        {
            return x;
        }


    }
    if(r->sibling !=NULL)//3 
    {

        Node* x=getNode(r->sibling ,parent);//调2 
        if(x!=NULL&&x->data ==parent)
        {
            return x;
        }	
    }
    return NULL;

} 

孩子兄弟表示法的全部代码

#include<stdio.h>
#include<stdlib.h>
//二叉链表的结点结构
typedef struct ChildSibling{
    int data;//数据	
    struct ChildSibling* child;// 第一个孩子指针域
    struct ChildSibling* sibling;//兄弟指针域
}Node; 
Node* root;//指向根节点的指针，同时也标记整棵树
Node* t;//临时指针 

//初始化，建立根节点
void Init(int key)
{
    root=(Node*)malloc(sizeof(Node));
    root->data =key;
    root->child =NULL;
    root->sibling =NULL;	
} 
//在以r为根的树中，查找数据为parent的结点
//递归 
Node* getNode(Node* r,int parent)
{
    if(r->data ==parent)//1
    {
        return r;
    }
    if(r->child !=NULL)//2
    {
        Node* x=getNode(r->child,parent);//调1 
        if(x!=NULL&&x->data ==parent)
        {
            return x;
        }


    }
    if(r->sibling !=NULL)//3 
    {

        Node* x=getNode(r->sibling ,parent);//调2 
        if(x!=NULL&&x->data ==parent)
        {
            return x;
        }	
    }
    return NULL;

} 
//插入 :key是插入的数据，parent是key的父亲结点的数据 
void insert(int key,int parent)
{
    t=getNode(root,parent); 
    if(t!=NULL)
    {
        Node* p=(Node*)malloc(sizeof(Node));
        p->data=key;

        if(t->child !=NULL)//key 不是parent的第一个孩子 
        {
            t=t->child ;
            p->sibling =t->sibling;
            t->sibling =p;
            p->child =NULL;
        }
        else{//key 是parent的第一个孩
            t->child =p;
            p->child =NULL;
            p->sibling=NULL;

        } 
    } 

    else{
        //
    }

}
//主函数自行写出 

二叉树

​ 二叉树是每个结点最多有两个子树的树结构。也就是说二叉树不允许存在度大于2的树。它有五种最基本的形态：二叉树可以是空集。根可以有空的左子树或者右子树；或者左右⼦树都是空。其中只有左子树或者右子树的叫做斜树。

二叉树的性质

性 质	内容
性 质 ⼀	在⼆叉树的 i 层上至多有2^i-1^个结点（i>=1）
性 质 ⼆	深度为 k 的⼆叉树至多有 2^k^ -1个结点（k>=1）
性 质 三	在⼀棵⼆叉树中，除了叶子结点（度为0）之外，就剩下度为2(n~2~)和1(n~1~)的结点了。则树的 结点总数为T = n~0~+n~1~+n~2~;在⼆叉树中结点总数为T，而连线数为T-1.所以有： n~0~+n~1~+n~2~ -1 = 2*n~2~ +n~1~;最后得到 n~0~ = n~2~+1;
性 质 四	具有 n 个结点的完全⼆叉树的深度为 [log~2~n] + 1 向下取整
性 质 五	如果有⼀棵有 n 个结点的完全⼆叉树(其深度为 [log~2~n] + 1，向下取整)的结点按层次序编号 (从第 1 层到第 [log~2~n] + 1，向下取整层，每层从左到右)，则对任⼀结点 i（1 <= i <= n）有 1.如果 i = 1，则结点 i 是⼆叉树的根，无双亲；如果 i > 1，则其双亲是结点 [i / 2]，向下取 整 2.如果 2i > n 则结点 i 无左孩子，否则其左孩子是结点 2i 3.如果 2i + 1 > n 则结点无右孩子，否则其右孩子是结点 2i + 1

满⼆叉树

​ 满⼆叉树要求所有的分支结点都存在左右子树，并且所有的叶结点都在同⼀层上，若满⼆叉树的层数为 n，则结点数量为 2n-1 个结点，子叶只能出现在最后⼀层，内部结点的度都为 2，如图所示。

完全⼆叉树

​ 从定义上来说，完全⼆叉树是满足若对⼀棵具有 n 个结点的⼆叉树按层序编号，如果编号为 i 的结点 (1 ≤ i ≤ n)于同样深度的满⼆叉树中编号为 i 的结点在⼆叉树的位置相同的⼆叉树。这样讲有些繁琐，可以理解为完全⼆叉树⽣成结点的顺序必须严格按照从上到下，从左往右的顺序来生成结点，如图所示。

​ 因此我们就不难观察出完全⼆叉树的特点，完全⼆叉树的叶结点只能存在于最下两层，其中最下层的叶结点只集中在树结构的左侧，而倒数第⼆层的叶结点集中于树结构的右侧。当结点的度为 1 时，该结点只能拥有左子树。

二叉树的存储

​ 二叉树的存储同样有两种方式。

顺序存储

​ 由于二叉树的结点至多为2，因此这种性质使得二叉树是可以使用顺序存储结构来描述的。在使用顺序存储结构时我们需要令数组的下标体现结点之间的逻辑关系。

​ 假设一颗树如下图所示。如果要将其存储下来，我们可以拿一个数组来存储，由于每一个节点最多只有两个孩子，在数组中每三个为一组来存储数据。如下图所示：

​ 如果是⼀个最特殊的⼆叉树，对于一颗斜树，我们开辟的空间数远超过实际使用的空间（ 毕竟如果孩子为空的话依然要占用空间，这样空间就被浪费了。因此顺序存储结构可行，但是不合适。 所以我们在二叉树的内容中一般采用的都是链式存储。

链式存储

​ 由于⼆叉树的每个结点最多只能有两个子树，因此我们就不需要使用上述的3种表达法来做。可以直接设置⼀个结点具有两个指针域与⼀个数据域，那么这样就可以建好⼆叉树链表。

属性集合

typedef struct BTNode { //二叉树结点     
    char show;         // 节点中存放的内容
    struct BTNode* left;
    struct BTNode* right;
}BTNode;

typedef struct {//二叉树 
    BTNode *root;
    int count;//结点数目 
}BinaryTree;

操作集合

BTNode *createBTNode(char);
void initBTreeRoot(BinaryTree, BTNode*);
BinaryTree *createBTree(BTNode*);
void insertBTNode(BinaryTree*, BTNode*, BTNode*, int);

二叉树链式存储之创造节点

​ 先申请一个一块内存来存放节点。然后通过memset函数来将节点中的指针都置空。将节点内容赋值给节点。

//创建结点 
BTNode *createBTNode(char show) {
    BTNode *node = (BTNode *) malloc(sizeof(BTNode));
    memset(node, 0, sizeof(BTNode));
    node->show = show;
    return node;
}

二叉树链式存储之初始化根节点

//初始化树根结点 
void initBTreeRoot(BinaryTree *tree, BTNode *node) {
	tree->count = 1;
	tree->root = node;
}

二叉树链式存储之创建树

​ 先申请一片空间来存放树，判断传进来的节点是否为空，若该节点不为空，则将其作为树根节点。若为空，则说明这棵树是一个空树，所以将其根节点指向空。

//创建树（初始化一个根节点） 
BinaryTree *createBTree(BTNode *root) {
	BinaryTree *tree = (BinaryTree *) malloc(sizeof(BinaryTree));
	if (root) {//非空 
		initBTreeRoot(tree, root);
	} 
	else {//空树 
		tree->root = NULL;
		tree->count = 0;
	}
	return tree;
}

二叉树链式存储之插入操作

​ 若想插入节点，需要传入整个树、该孩子的父节点、该节点、为父节点的左孩子还是右孩子。将节点绑定在指定位置，树的节点树增加。

//插入结点  在树中插入newNode结点，该结点的双亲结点为parent， 
//flag==1该结点为左孩子， flag==0该结点为右孩子 
void insertBTNode(BinaryTree *tree, BTNode *parent, BTNode *newNode, int flag) {
	if (flag == 1) {
		parent->left = newNode;
	} else {
		parent->right = newNode;
	}
	tree->count++;
}

二叉树的遍历

​ 二叉树的基本遍历分为四种，分别是先序遍历、中序遍历、后续遍历、层次遍历。其中"序"其实就是根节点的位置。

• DLR--前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）
• LDR--中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）
• LRD--后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）
• 层序遍历（ 按照树的层级，一层层从上到下，从左到右层次遍历 ）

二叉树遍历之先序遍历

​ 先中后序的差别其实就是递归调用的顺序区别。拿先序举例，就是先访问根节点的值，然后访问左右子树的值。

//先序遍历 
void perOrder(BTNode *node) {
    if (node) {
        visitBTNode(node);// visitBTNode是访问当前节点
        perOrder(node->left);
        perOrder(node->right);
    }
}
void perOrderBTree(BinaryTree *tree) {
    if (tree->root) {
        perOrder(tree->root);
    }
}

二叉树遍历之中序遍历

//中序遍历 
void inOrder(BTNode *node) {
    if (node) {
        inOrder(node->left);
        visitBTNode(node);
        inOrder(node->right);
    }
}
void inOrderBTree(BinaryTree *tree) {
    if (tree->root) {
        inOrder(tree->root);
    }
}

二叉树遍历之后序遍历

//后序遍历 
void postOrder(BTNode *node) {
    if (node) {
        postOrder(node->left);
        postOrder(node->right);
        visitBTNode(node);
    }
}
void postOrderBTree(BinaryTree *tree) {
    if (tree->root) {
        postOrder(tree->root);
    }
}

二叉树遍历之层次遍历

​ 层次遍历用到了队列（ 当然可以使用递归 ）。队列的具体代码和上述队列的代码相同，这里直接拿来用即可。先创建一个队列，然后将根节点入队。接着以队列是否为空作为循环条件。在循环中取出队首节点，然后检查其是否有左右孩子，若是有则将左右孩子存入队列中。

//	层次遍历 
void levelOrderBTree(BinaryTree *tree) {
	linkqueue *que = initqueue();
	enqueue(que, tree->root);//树根结点入队

	while(empty(que)==1)
	 {	 	
		BTNode * node=dequeue(que);//取队首结点，出队
		visitBTNode(node);//访问该节点 
		if (node->left!=NULL) {
			enqueue(que, node->left);//该节点左孩子入队
		}
		if (node->right!=NULL) {
		
		enqueue(que, node->right);//该节点左孩子入队
		}
			
	}
    
}

二叉树的总代码

#include <stdlib.h>
#include <stdio.h>
# include <string.h>
typedef struct BTNode { //二叉树结点     
    char show;         
    struct BTNode* left;
    struct BTNode* right;
}BTNode;

typedef struct {//二叉树 
    BTNode *root;
    int count;//结点数目 
}BinaryTree;

//创建结点 
BTNode *createBTNode(char show) {
    BTNode *node = (BTNode *) malloc(sizeof(BTNode));
    memset(node, 0, sizeof(BTNode));
    node->show = show;
    return node;
}
//初始化树根结点 
void initBTreeRoot(BinaryTree *tree, BTNode *node) {
    tree->count = 1;
    tree->root = node;
}
//创建树 
BinaryTree *createBTree(BTNode *root) {
    BinaryTree *tree = (BinaryTree *) malloc(sizeof(BinaryTree));
    if (root) {//非空 
        initBTreeRoot(tree, root);
    } 
    else {//空树 
        tree->root = NULL;
        tree->count = 0;
    }
    return tree;
}

//插入结点  在树中插入newNode结点，该结点的双亲结点为parent， 
//flag==1该结点为左孩子， flag==0该结点为右孩子 
void insertBTNode(BinaryTree *tree, BTNode *parent, BTNode *newNode, int flag) {
    if (flag == 1) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }
    tree->count++;
}

//访问一个结点
void visitBTNode(BTNode *node) {
    if (node) {
        printf("%c ", node->show);
    }
}

//声明队列及其操作函数
///链式队列//
typedef struct qnode{//链式队列结点 
    BTNode* data;//队列元素是树中的结点 
    struct qnode *next;//指向下一个结点的指针 
}qnode,*lqueue; 
typedef struct linkqueue{//链式队列---可选，不写结构体，直接定义对头队尾指针也可 
    lqueue front,rear;//对头队尾指针,队首指针是链表头结点 
}linkqueue;
//初始化
linkqueue* initqueue()
{   
    linkqueue *q=(linkqueue *)malloc(sizeof(linkqueue));
    q->front=q->rear=(lqueue)malloc(sizeof(qnode));
    if(q->front==NULL)
    {
        printf("分配失败\n");
    }
    else{
        q->front->next=NULL;
    }
    return q;
} 
//入队 
void enqueue(linkqueue* q,BTNode* x)
{
    lqueue s=(lqueue )malloc(sizeof(qnode));
    s->data =x;
    s->next =NULL;//新节点插入到链尾
    q->rear->next=s;
    q->rear =s; 


} 
//出队，队首指针是链表头结点 ，删除的是队首指针的下一个，即front->next 
BTNode* dequeue(linkqueue* q) 
{
    BTNode* x;//保存出队元素 
    //先判空，不空才能出 
    if(q->front->next==NULL)
    {
        printf("空\n");//队空，报错 
    } 
    else{
        lqueue p=q->front->next; 
        x=p->data;
        q->front->next=p->next ;
        //若原队列只有一个结点了，则删除边空，需要处理尾指针 
        if(q->rear ==p)
            q->rear =q->front;
        free(p); 
        return x; 
    }
}
int empty(linkqueue* q)
{
    if(q->front->next==NULL)
    {
        return 0;//队空 
    } 	
    else return 1;//非空 
}
//	层次遍历 
void levelOrderBTree(BinaryTree *tree) {
    linkqueue *que = initqueue();
    enqueue(que, tree->root);//树根结点入队

    while(empty(que)==1)
    {

        BTNode * node=dequeue(que);//取队首结点，出队
        visitBTNode(node);//访问该节点 
        if (node->left!=NULL) {
            enqueue(que, node->left);//该节点左孩子入队
        }
        if (node->right!=NULL) {

            enqueue(que, node->right);//该节点左孩子入队
        }

    }

}

//先序遍历 
void perOrder(BTNode *node) {
    if (node) {
        visitBTNode(node);
        perOrder(node->left);
        perOrder(node->right);
    }
}

void perOrderBTree(BinaryTree *tree) {
    if (tree->root) {
        perOrder(tree->root);
    }
}
//中序遍历 
void inOrder(BTNode *node) {
    if (node) {
        inOrder(node->left);
        visitBTNode(node);
        inOrder(node->right);
    }
}
void inOrderBTree(BinaryTree *tree) {
    if (tree->root) {
        inOrder(tree->root);
    }
}
//后序遍历 
void postOrder(BTNode *node) {
    if (node) {
        postOrder(node->left);
        postOrder(node->right);
        visitBTNode(node);
    }
}
void postOrderBTree(BinaryTree *tree) {
    if (tree->root) {
        postOrder(tree->root);
    }
}
//初始化一棵具体的树 
BinaryTree *initBTree() {
    BTNode *a = createBTNode('A');
    BTNode *b = createBTNode('B');
    BTNode *c = createBTNode('C');
    BTNode *d = createBTNode('D');
    BTNode *e = createBTNode('E');
    BTNode *f = createBTNode('F');
    BTNode *g = createBTNode('G');
    BTNode *h = createBTNode('H');
    BTNode *k = createBTNode('K');

    BinaryTree *tree = createBTree(a);

    insertBTNode(tree, a, b, 1);
    insertBTNode(tree, a, e, 0);
    insertBTNode(tree, b, c, 0);
    insertBTNode(tree, c, d, 1);
    insertBTNode(tree, e, f, 0);
    insertBTNode(tree, f, g, 1);
    insertBTNode(tree, g, h, 1);
    insertBTNode(tree, g, k, 0);
    return tree;
}
int main() {
    BinaryTree *tree = initBTree();

    levelOrderBTree(tree);
    printf("\n");

    printf("\n前:\n");
    perOrderBTree(tree);
    printf("\n中:\n");
    inOrderBTree(tree);
    printf("\n后\n");
    postOrderBTree(tree);


    return 0;
}

树、二叉树和森林的转换

普通树转为二叉树

1. 加线，在所有兄弟结点之间加⼀条连线。
2. 去线，对树中每个结点，只保留它与第⼀孩子结点的连线，删除它与其他孩子结点之间的连线。
3. 层次调整，以树为根结点为轴心，将整棵树顺时针旋转⼀定的角度，使之结构层次分明。

森林转换为二叉树

1. 把每棵树都转换为二叉树。
2. 第⼀棵二叉树不动，从第二棵二叉树开始，依次把后⼀棵二叉树的根结点作为前⼀棵二叉树的根结点 的右孩子，用线连起来。
3. 层次调整，以树的根结点为轴心，将整棵树顺时针旋转⼀定的角度，使之结构层次分明。

线索二叉树

线索二叉树的由来

为了解决两个问题：

1. 解决一棵树大量空指针浪费空间的问题
2. 想知道某个节点某个次序的前驱或者后继

线索二叉树的定义

将某结点的空指针域指向该结点的前驱后继，定义规则如下：

• 若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。
• 若结点的右子树为空，则该结点的右孩子指针指向其后继结点。

​ 这种指向前驱和后继的指针称为线索。将⼀棵普通⼆叉树以某种次序遍历，并添加线索的过程称为线索 化。

​ 可以将⼀棵⼆叉树线索化为⼀棵线索⼆叉树，那么新的问题产生了。我们如何区分⼀个结点的lchild指针是指向左孩子还是前驱结点呢？

为了解决这⼀问题，现需要添加标志位ltag， rtag。并定义规则如下：

• ltag为0时，指向左孩子，为1时指向前驱
• rtag为0时，指向右孩子，为1时指向后继

属性集合

typedef struct BTNode { //二叉树结点     
    char show;         
    struct BTNode* left;
    struct BTNode* right;
    int ltag;
    int rtag;
}BTNode;

typedef struct {//二叉树 
    BTNode *root;
    int count;//结点数目 
}BinaryTree;
BTNode* pre=NULL;

将一棵二叉树进行线索化

​ 其余的操作都是和二叉的建立和存储都是一样的，这里单独列出的都是线索化的内容。

​ 理解代码的内容，首先要理解上面的概念。当一个节点的左右孩子有为空时，优先线索化指向前驱。这也是代码中if(pre!=NULL&&pre->right ==NULL)的原因。

//访问一个结点
//进行线索化 
void visitBTNode(BTNode *node) {

	if(node->left ==NULL)
	{
	  node->left =pre;
	  node->ltag =1;//指向前驱线索	
	 } 
	 if(pre!=NULL&&pre->right ==NULL)
	 {
	 	pre->right =node;
	 	pre->rtag =1;//指向后继线索 
	  } 
	pre=node; //
	
}

中序遍历找前驱

​ 若是传入节点的左子树的标记为1，那该节点的前驱就是左子树指向的位置。否则该节点的前驱就是左子树中最右边的结点。

//找前驱节点 
BTNode* nextNode(BTNode* x)
{
    if(x->ltag ==1)
    {
        return x->right;

    } 
    else
    {
        BTNode* p=x->right;
        while(p->rtag ==0)
        {
            p=p->right;
        }
        return p;

    }
} 

中序遍历找后继

​ 若是传入节点的右子树的标记为1，那该节点的后继就是右子树指向的位置。否则该节点的后继就是右子树中最左边的结点。

//找中序遍历的后继节点
BTNode* nextNode(BTNode* x)
{
    if(x->rtag ==1)
    {
        return x->right;

    } 
    else
    {
        BTNode* p=x->right;
        while(p->ltag ==0)
        {
            p=p->left;
        }
        return p;

    }
} 

二叉查找树（BST树）

​ 二叉查找树又名二叉排序树、二叉搜索树。

二叉排序树的性质

1. 如果他的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
3. 它的左、右树又分为⼆叉排序树。

简单点来说，树中的值以中序遍历来看就是升序的。（ 下图中只有左边的树是查找树 ）

属性集合

/*数据结构*/
typedef struct SortTree {
    struct SortTree* left, * right;
    int key;//存放数据
}Node;
/*全局变量*/
Node* root=NULL; 

操作集合

void Init(int);// 初始化根节点
void insert(int);// 插入节点
void show(Node*);// 中序遍历树
void delet(int);// 删除节点

二叉查找树之初始化

/*初始化一个根节点*/
void Init(int key)
{
    root = (Node*)malloc(sizeof(Node));
    root->key = key;
    root->left = NULL;
    root->right = NULL;
}

二叉查找树之插入节点

​ 二叉排序树的插入 永远是插入在叶子要先找到应该在哪个结点的孩子进行插入然后判断是这个结点的左孩子还是右孩子。

​ 定义两个指针，一前一后方便操作。第一个while循环是为了找到合适的位置。接着对这个位置的父亲节点的key和传进来的key进行比较。若前者大于后者，就插入在左子树，否则插入在右子树。

void insert(int key)
{
    Node* temp = root;//定义一个临时指针 方便移动
    Node* prev = NULL;//指向temp的前一个结点
    while (temp != NULL)
    {
        prev = temp;
        if (key < temp->key) {
            temp = temp->left;
        }else if (key > temp->key) {
            temp = temp->right;
        }

    }

    if (key < prev->key)
    {
        prev->left = (Node*)malloc(sizeof(Node));
        prev->left->key = key;
        prev->left->left = NULL;
        prev->left->right = NULL;
    }
    else
    {
        prev->right = (Node*)malloc(sizeof(Node));
        prev->right->key = key;
        prev->right->left = NULL;
        prev->right->right = NULL;
    }

}

二叉查找树之删除节点

情况一：node没有孩子，是叶子结点

1. node 不是根节点，直接把node删除，把node父亲对应的孩子指针置空
2. node是根节点，直接删除，把根指针置空

情况二：node只有一个孩子结点

1. ​ node不是根节点，并且node只有一个孩子，就让这个孩子结点顶替node的位置，也就是node的parent的指向node的指针，要去指向该孩子（写代码时要注意区分左右）
2. ​ node是根节点，让根指针直接指向node的唯一的孩子即可

情况三：node有两个孩子。

​ 这种情况简单点来说就是将node节点在中序遍历中的左边位置的元素或右边元素代替这个值就可。

​ 法1：让node结点的左子树中的值最大的x结点来替换node结点的值，转化为删除x：如果x是叶子结点转化为情况一，如果x不是叶子结点转化为情况二（x只有左孩子） x是最node左子树靠右边的结点

​ 法2：让node结点的右子树中的值最小的x结点来替换node结点的值，转化为删除x：如果x是叶子结点转化为情况一，如果x不是叶子结点转化为情况二(x只有右孩子) x是最node右子树靠左边的结点

​

void delet(int k)
{
    Node* node = root;//去找k所在的结点node 
    Node* prev = NULL;//找node的父亲结点 
    while (node->key !=k) // 寻找到要删除点的位置
    {
        prev = node;
        if (k < node->key)
        {
            node = node->left;
        }
        else if (k > node->key)
        {
            node = node->right;
        }
    }
    
    if(node->left ==NULL&&node->right ==NULL)
    {//情况一 node没有孩子 
        if(prev==NULL)//node的父亲为空 ，node为根节点 
        {
            root=NULL;
            free(node);
            node=NULL; 
        }
        else// node不为空节点
        {
            if(prev->left ==node)// 看看这个节点是父节点的左孩子还是右孩子
            {
                prev->left =NULL;
                free(node);
                node=NULL; 
            }
            else
            {
                prev->right =NULL;
                free(node);
                node=NULL; 	
            }	
        }

    }
    else if(node->left !=NULL&&node->right ==NULL)
    {// 情况二：node只有左孩子
        if(prev==NULL)// 此时是根节点的情况
        {
            root=node->left;
            node->left =NULL;
            free(node);
            node=NULL; 
        } 
        else{
            if(prev->left ==node)// 看看这个节点是父节点的左孩子还是右孩子
            {
                prev->left =node->left ;// 进行左孩子的替换
                node->left =NULL;
                free(node);
                node=NULL; 
            }
            else
            {
                prev->right =node->left;
                node->left =NULL;
                free(node);
                node=NULL; 	
            }	

        }


    }
    else if(node->left ==NULL&&node->right !=NULL)// 和同理
    {//情况二：node只有右孩子
        if(prev==NULL)
        {
            root=node->right  ;
            node->right =NULL;
            free(node);
            node=NULL; 
        } 
        else{

            if(prev->left ==node)
            {
                prev->left =node->right  ;
                node->right  =NULL;
                free(node);
                node=NULL; 
            }
            else
            {
                prev->right =node->right  ;
                node->right  =NULL;
                free(node);
                node=NULL; 	
            }	

        }
    }
    else{
        //情况三：node有两个孩子（左右孩子都有） 
        Node* x=node->left;// 由于用的是法1，所以我们需要找到左子树中最右边的节点
        Node* prex=node;// prex是x的父亲 
        while(x->right!=NULL)// 找到左子树中最靠右的节点
        {
            prex=x;
            x=x->right;// 用x指向这个节点
        } 
        node->key =x->key; // 将要删除的节点值改为x的值
        if(prex==node)// 判断x节点是要删除的节点是第一种情况，还是第二种情况
        {
            node->left =x->left ;
            free(x);
            x=NULL;
        }
        else
        {
            prex->right =NULL;
            free(x);
            x=NULL;	
        }
    }
} 

平衡二叉树（AVL树）

​ 在AVL树中，任⼀节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn）。平衡二叉树的出现解决了左右子树差距过大而出现的搜索效率降低的问题。

二叉平衡树的定义

​ 平衡⼆叉查找树：简称平衡⼆叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的⼆叉树，根据科学家的英文名也称为 AVL 树。它具有如下几个性质：

1. 可以是空树。
2. 假如不是空树，任何⼀个节点的左子树与右子树都是平衡⼆叉树，并且高度之差的绝对值不超过 1。

用公式来表达就是(左子树高度-右子树高度)的绝对值<=1

平衡因子

​ 某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于 1 的节点。在⼀棵平衡⼆叉树中，节点的平衡因⼦只能取 0 、 1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。

平衡二叉树的旋转

左旋

​ 左旋就是当有节点失衡时，将节点右旋。接着对孩子进行处理。口诀为冲突的左孩为右孩。画图展示

右旋

​ 右旋就是当有节点失衡时，将节点左旋。接着对孩子进行处理。口诀为冲突的右孩变左孩。画图展示

平衡二叉树四种插入节点的方式

插入方式	描述	旋转方式
LL	在A结点的左子树根结点的左子树上插入结点而破坏平衡	右旋转
RR	在A结点的右子树根结点的右子树上插入结点而破坏平衡	左旋转
LR	在A的左子树根结点的右子树上插入结点而破坏平衡	先左旋再右旋
RL	在A的右子树根结点的左子树上插入结点而破坏平衡	先右旋再左旋

判断使用哪种插入方法

插入方式	失衡节点	失衡节点的左/右孩子
LL	平衡因子 = 2	左孩子平衡因子 = 1
RR	平衡因子 = -2	右孩子平衡因子 = -1
LR	平衡因子 = 2	左孩子平衡因子 = -1
RL	平衡因子 = -2	右孩子平衡因子 = 1

判断的口诀：左正右负，正负不同

LL和RR不再赘述，就是上面的左右旋转。接下来讨论一下LR与RL的旋转

LR

​ 先对自己的左孩子进行左旋，然后再对本身进行右旋

RL

​ 先对自己的右孩子进行右旋，然后再对本身进行左旋

平衡二叉树之属性结合

属性结合

​ 定义了两个宏，第一个宏是为了获取当前节点的高度，第二个宏是两个数谁较大。

#define HEIGHT(node) ((node == NULL)? 0 : (((avlnode*)(node))->height ))
#define MAX(a,b) ((a > b) ? (a) : (b))
typedef struct node {
    int data;//存储结点的值
    struct node* left;
    struct node* right;
    int height;//当前结点的深度
}avlnode, * avltree;

平衡二叉树之创造节点操作

avlnode* creata_node(int key, avlnode* left, avlnode* right)
{
    avlnode* node = (avlnode*)malloc(sizeof(avlnode));
    //判断一下是否创建成功
    node->data = key;
    node->left = left;
    node->right = right;
    node->height = 0;
    return node;
}

平衡二叉树之插入操作

插入操作的前置

//获取长度
int get_height(avlnode* node)
{
    return HEIGHT(node);
}
/*左孩子的左子树（ LL的情况 ）*/
avltree left_left_rotation(avltree tree)
{//传入的tree为子树根节点，同时也是失衡结点 
    // k就是我最终需 同时作为最后的根节点
    avlnode* k = tree->left;
    tree->left = k->right; // 冲突的右孩变左孩
    k->right = tree;
    //切记一点 所有旋转操作以后 需要调整树的高度 
    //这里是深度 一颗子树的深度 从这个结点的左右子树来判断他的深度
    tree->height = MAX(get_height(tree->left), get_height(tree->right)) + 1;
    k->height = MAX(get_height(k->left), get_height(k->right)) + 1;
    return k;//此时k为根节点 
}
/*右孩子的右子树（ RR的情况 ）*/
avltree right_right_rotation(avltree tree)
{//传入的tree为子树根节点，同时也是失衡结点 
    avlnode* k = tree->right;
    tree->right = k->left;
    k->left = tree;
    //切记一点 所有旋转操作以后 需要调整树的高度
    //这里是深度 一颗子树的深度 从这个结点的左右子树来判断他的深度
    tree->height = MAX(get_height(tree->left), get_height(tree->right)) + 1;
    k->height = MAX(get_height(k->left), get_height(k->right)) + 1;
    return k;//此时k为根节点 

}
/*左孩子得右子树的调整（ LR的情况 ）*/
avltree left_right_rotation(avltree tree)
{
    tree->left = right_right_rotation(tree->left);// 将失衡节点的左孩子传入进行左旋
    tree = left_left_rotation(tree);// 将失衡节点进行右旋
    return tree;
}

/*右孩子的左子树的情况（ RL的情况 ）*/
avltree right_left_rotation(avltree tree)
{
    tree->right = left_left_rotation(tree->right);// 将失衡节点的右孩子传入进行右旋
    tree = right_right_rotation(tree);// 将失衡节点进行左旋
    return tree;
}

插入操作

avltree avltree_insertNode(avltree tree, int key) 
{
    if (tree == NULL)
    {
        avlnode* node = creata_node(key, NULL, NULL);
        tree = node;
    }
    else if (key < tree->data)//往tree的左子树插入 
    {
        //递归寻找插入结点的位置
        tree->left = avltree_insertNode(tree->left, key);
        if (get_height(tree->left) - get_height(tree->right) == 2)
        {
            //在这里判断是LL还是LR
            if (key < tree->left->data)
            {
                // LL旋转
                tree = left_left_rotation(tree);
            }
            else
            {
                //LR旋转
                tree = left_right_rotation(tree);
            }
        }
    }
    else if (key > tree->data) //往tree的右子树插入 
    {
        tree->right = avltree_insertNode(tree->right, key);
        if (get_height(tree->right) - get_height(tree->left) == 2)
        {
            //RR
            if (key > tree->right->data)
            {
                tree = right_right_rotation(tree);
            }
            else
            {
                //RL
                tree = right_left_rotation(tree);
            }
        }
    }
    else
    {
        //报错，不允许插入相同的值
    }

    // 重新调整二叉树的深度（ 由于是遍历，所有会调整递归进来的所有节点 ）
    tree->height = MAX(get_height(tree->left), get_height(tree->right)) + 1;

    return tree;

}

平衡二叉树之删除操作

​ 删除平衡二叉树的节点分为两种情况，一种是删除的节点只有一个孩子，以及删除的节点右两个孩子。删除操作的过程中我们可以理解为，当我们删除一个左子树的节点导致失衡时，其实就是我们在右子树添加一个数导致的失衡，右子树同理。即删除导致的失衡 可以转化为在另一棵子树添加一个节点导致的失衡。

只有一个孩子

处理步骤：

1. 将左子树（右子树）替代原有节点 C 的位置；
2. 节点 C 被删除后，则以 C 的父节点 B 为起始推算点，依此向上检索推算各节点（父、祖先）是否失 衡；
3. 如果其父节点未失衡，则继续向上检索推算其父节点 的父节点 是否失衡…如此反复 2 的判断，直到 根节点 ；如果向上推算过程中发现了失衡的现象，则进行4 的处理；
4. 如果其父节点失衡，则判断是哪种失衡类型 [LL、 LR、 RR、 RL] ，并对其进行相应的平衡化处理。如 果平衡化处理结束后，发现与原来以父节点为根节点的树的⾼度发⽣变化，则继续进行2 的检索推算； 如果与原来以父节点为根节点的高度⼀致时，则可说明父节点的父节点及祖先节点的平衡因⼦将不会有 变化，因此可以退出处理；

两个孩子

处理步骤：

1. 找到被删节点 B 和替代节点 BLR (节点 B 的前继节点或后继节点 —— 在此选择 前继)；
2. 将替代节点 BLR 的值赋给节点 B ，再把替代节点 BLR 的左孩子 BLRL 替换替代节点 BLR 的位置；
3. 以 BLR 的父节点 BL 为起始推算点，依此向上检索推算父节点或祖先节点是否失衡；
4. 如果其父节点未失衡，则继续向上检索推算其父节点的父节点是否失衡…如此反复3的判断，直到根 节点；如果向上推算过程中发现了失衡的现象，则进行5的处理；
5. 如果其父节点失衡，则判断是哪种失衡类型 [LL、 LR、 RR、 RL] ，并对其进行相应的平衡化处理。 如果平衡化处理结束后，发现与原来以父节点为根节点的树的高度发生变化，则继续进行 2 的检索推 算；如果与原来以父节点为根节点的⾼度⼀致时，则可说明父节点的父节点及祖先节点的平衡因⼦将不 会有变化，因此可以退出处理

删除节点的前置

/*查找结点*/
avlnode* search_node(avltree tree, int key)
{
	if (tree ==NULL || tree->data == key)
	{
		return tree;
	}
	else if (key < tree->data) 
	{
		search_node(tree->left, key);
	}
	else
	{
		search_node(tree->right, key);
	}
}

avlnode* maxinum_node(avltree tree)
{
	if (tree == NULL)
	{
		return NULL;
	}
	while (tree->right)
	{
		tree = tree->right;
	}

	return tree;
}


avlnode* mininum_node(avltree tree)
{
	if (tree == NULL)
	{
		return NULL;
	}
	while (tree->left)
	{
		tree = tree->left;
	}

	return tree;
}

删除操作

avltree avltree_deleteNode(avltree tree, int key)
{

    if (tree == NULL )
    {
        return tree;
    }
    if (key < tree->data)//要删除的是在左子树
    {
        //先递归找要删除的结点
        tree->left = avltree_deleteNode(tree->left, key);
        // 在这下面的操作其实都是对父节点是否失衡进行判断
        //删完以后 要检查平衡性
        if (get_height(tree->right) - get_height(tree->left) == 2)
        {
            //要如何判断RL,RR;
            avlnode* tmp=tree->right;
            if (get_height(tmp->left) - get_height(tmp->right) >0)
            {//RL
                tree = right_left_rotation(tree);

            }
            else
            {//RR
                tree = right_right_rotation(tree);
            }
        }

    }
    else if (key > tree->data)//要删除的在右子树
    {
        tree->right = avltree_deleteNode(tree->right, key);
        //删完以后 要检查平衡性
        if (get_height(tree->left) - get_height(tree->right) == 2)
        {
            //要如何判断LL,LR
            avlnode* tmp=tree->left;
            if (get_height(tmp->left) - get_height(tmp->right) >=0)
            {//LL
                tree = left_left_rotation(tree);

            }
            else
            {//LR
                tree = left_right_rotation(tree);
            }
        }
    }
    else //找到要删除的结点 先按照二叉排序树的方式进行删除
    {
        if (tree->left && tree->right) // 这边使用的是法2进行删除，即用右子树的最小节点来代替删除节点
        {
            avlnode* min_node = mininum_node(tree->right);
            tree->data = min_node->data;
            //删除 最小值结点
            tree->right = avltree_deleteNode(tree->right, min_node->data);
        }
        else// 这里是把无孩子和一个孩子合在一起写了 
        {
            //独子或者无子的情况结点
            avlnode* n=tree;
            if(tree->left !=NULL)
            {
                tree=tree->left ;
            }
            else{
                tree=tree->right;
            }
            free(n);
            n=NULL;
            return tree;	

        }

    }

    //调整高度
    if (tree)
    {
        tree->height = MAX(get_height(tree->left), get_height(tree->right)) + 1;
    }

    return tree;
}

二叉排序树之全部代码

#include<stdio.h>
#include<stdlib.h>

#define HEIGHT(node) ((node == NULL)? 0 : (((avlnode*)(node))->height ))
#define MAX(a,b) ((a > b) ? (a) : (b))
typedef struct node {
    int data;//存储结点的值
    struct node* left;
    struct node* right;
    int height;//当前结点的深度
}avlnode, * avltree;

avlnode* creata_node(int key, avlnode* left, avlnode* right)
{
    avlnode* node = (avlnode*)malloc(sizeof(avlnode));
    //判断一下是否创建成功
    node->data = key;
    node->left = left;
    node->right = right;
    node->height = 0;
    return node;
}

//获取长度
int get_height(avlnode* node)
{
    return HEIGHT(node);
}
/*左孩子的左子树*/
avltree left_left_rotation(avltree tree)
{//传入的tree为子树根节点，同时也是失衡结点 
    //k就是我最终需
    avlnode* k = tree->left;
    tree->left = k->right;
    k->right = tree;
    //切记一点 所有旋转操作以后 需要调整树的高度 
    //这里是深度 一颗子树的深度 从这个结点的左右子树来判断他的深度
    tree->height = MAX(get_height(tree->left), get_height(tree->right)) + 1;
    k->height = MAX(get_height(k->left), get_height(k->right)) + 1;
    return k;//此时k为根节点 
}
/*右孩子的右子树*/
avltree right_right_rotation(avltree tree)
{//传入的tree为子树根节点，同时也是失衡结点 
    avlnode* k = tree->right;
    tree->right = k->left;
    k->left = tree;
    //切记一点 所有旋转操作以后 需要调整树的高度
    //这里是深度 一颗子树的深度 从这个结点的左右子树来判断他的深度
    tree->height = MAX(get_height(tree->left), get_height(tree->right)) + 1;
    k->height = MAX(get_height(k->left), get_height(k->right)) + 1;
    return k;//此时k为根节点 

}
/*左孩子得右子树的调整*/
avltree left_right_rotation(avltree tree)
{
    tree->left = right_right_rotation(tree->left);
    tree = left_left_rotation(tree);
    return tree;
}

/*右孩子的左子树的情况*/
avltree right_left_rotation(avltree tree)
{
    tree->right = left_left_rotation(tree->right);
    tree = right_right_rotation(tree);
    return tree;
}


avltree avltree_insertNode(avltree tree, int key) 
{
    if (tree == NULL)
    {
        avlnode* node = creata_node(key, NULL, NULL);
        tree = node;
    }
    else if (key < tree->data)//往tree的左子树插入 
    {
        //递归寻找插入结点的位置
        tree->left = avltree_insertNode(tree->left, key);
        if (get_height(tree->left) - get_height(tree->right) == 2)
        {
            //在这里判断是LL还是LR
            if (key < tree->left->data)
            {
                tree = left_left_rotation(tree);
            }
            else
            {
                //LR旋转
                tree = left_right_rotation(tree);
            }
        }
    }
    else if (key > tree->data) //往tree的右子树插入 
    {
        tree->right = avltree_insertNode(tree->right, key);
        if (get_height(tree->right) - get_height(tree->left) == 2)
        {
            //RR
            if (key > tree->right->data)
            {
                tree = right_right_rotation(tree);
            }
            else
            {
                //RL
                tree = right_left_rotation(tree);
            }
        }
    }
    else
    {
        //报错，不允许插入相同的值
    }

    //重新调整二叉树的深度
    tree->height = MAX(get_height(tree->left), get_height(tree->right)) + 1;

    return tree;

}

/*查找结点*/
avlnode* search_node(avltree tree, int key)
{
    if (tree ==NULL || tree->data == key)
    {
        return tree;
    }
    else if (key < tree->data) 
    {
        search_node(tree->left, key);
    }
    else
    {
        search_node(tree->right, key);
    }
}

avlnode* maxinum_node(avltree tree)
{
    if (tree == NULL)
    {
        return NULL;
    }
    while (tree->right)
    {
        tree = tree->right;
    }

    return tree;
}


avlnode* mininum_node(avltree tree)
{
    if (tree == NULL)
    {
        return NULL;
    }
    while (tree->left)
    {
        tree = tree->left;
    }

    return tree;
}
avltree avltree_deleteNode(avltree tree, int key)
{

    if (tree == NULL )
    {
        return tree;
    }
    if (key < tree->data)//要删除的是在左子树
    {
        //先递归找要删除的结点
        tree->left = avltree_deleteNode(tree->left, key);
        //删完以后 要检查平衡性
        if (get_height(tree->right) - get_height(tree->left) == 2)
        {
            //要如何判断RL,RR;
            avlnode* tmp=tree->right;
            if (get_height(tmp->left) - get_height(tmp->right) >0)
            {//RL
                tree = right_left_rotation(tree);

            }
            else
            {//RR
                tree = right_right_rotation(tree);
            }
        }

    }
    else if (key > tree->data)//要删除的在右子树
    {
        tree->right = avltree_deleteNode(tree->right, key);
        //删完以后 要检查平衡性
        if (get_height(tree->left) - get_height(tree->right) == 2)
        {
            //要如何判断LL,LR
            avlnode* tmp=tree->left;
            if (get_height(tmp->left) - get_height(tmp->right) >=0)
            {//LL
                tree = left_left_rotation(tree);

            }
            else
            {//LR
                tree = left_right_rotation(tree);
            }
        }
    }
    else //找到要删除的结点 先按照二叉排序树的方式进行删除
    {
        if (tree->left && tree->right) // 这边使用的是法2进行删除，即用右子树的最小节点来代替删除节点
        {
            avlnode* min_node = mininum_node(tree->right);
            tree->data = min_node->data;
            //删除 最小值结点
            tree->right = avltree_deleteNode(tree->right, min_node->data);
        }
        else// 这里是把无孩子和一个孩子合在一起写了 
        {
            //独子或者无子的情况结点
            avlnode* n=tree;
            if(tree->left !=NULL)
            {
                tree=tree->left ;
            }
            else{
                tree=tree->right;
            }
            free(n);
            n=NULL;
            return tree;	

        }

    }

    //调整高度
    if (tree)
    {
        tree->height = MAX(get_height(tree->left), get_height(tree->right)) + 1;
    }


    return tree;
}


void pre_order(avltree tree)
{//中序遍历输出 
    if (tree)
    {

        pre_order(tree->left);
        printf("%d   ", tree->data);
        pre_order(tree->right);
    }
}


int main()
{
    avltree tree = NULL;
    int a[] = { 1,2,3,4,5,6,7,8,9 };
    //int length = sizeof(a) / sizeof(a[0]);
    for (int i = 0; i < 9; i++)
    {
        tree = avltree_insertNode(tree, a[i]);
    }

    pre_order(tree);
    printf("\n");
    //	in_order(tree);
    printf("\n");
    tree = avltree_deleteNode(tree,7);
    tree = avltree_deleteNode(tree, 2);
    tree = avltree_deleteNode(tree, 4);
    pre_order(tree);
    printf("\n");
    //in_order(tree);

}

并查集

​ 并查集是⼀种非常精巧而实用的树形数据结构，他主要是处理⼀些不相交集合的合并和查询的问题。并查集的意思我们用现实生活中的班级列子来举例。比如有两个新生学生A和B，他们两者不认识，但是当他们报出自己的班级就能知道他们是不是同班同学。

并查集的操作

1. 建立一个新的并查集，所有的元素都是各自的集合
2. 根据要求进行建立集合，两者相交就将集合合并
3. 若想查看两个元素是否在同一个集合中就比较各自的祖先，就能确定两个是否在同一个集合中。

并查集的初始化

void init(int n)
{

    for(int i=1;i<=n;i++)
    {
        f[i]=i;//建立起了n个单元数集合 
    }
    return;	
}

并查集的查找

​ 并查集的查找和建立关系有关。查找的方式决定了时间复杂度。如果我们用线性的方式来查找那时间复杂度为O(n)，但是如果我们使用树形来存储时间复杂能降低到O(1)。画图演示

//查找祖先  
int find(int x)
{
    //非递归
    while(f[x]!=x)
    {
        x=f[x];

    } 
    return x;

}
//查找祖先 O(n) 
int find1(int x)
{
    //递归
    if(f[x]!=x)
    {
        return find1(f[x]);
    }
    return x;
}
//优化 路径压缩 --O(1)
int find2(int x)
{
    //递归
    if(f[x]!=x)
    {
        return f[x]=find2(f[x]);      
    }
    return x;
}

并查集的合并

//建立x y的关系--通过合并两者所在的集合 
void unionn(int x,int y)
{
    int ax=find2(x);
    int ay=find2(y);

    f[ay]=ax;//合并	

    //f[find2(x)]=find2(y); 


}

并查集的总代码

#include<stdio.h>
#include<stdlib.h>
/*1 2 3 4 5 6 
关系：  （4.3） （3 2） （ 2 1） 
查询： （4.1） （4.6）； 
-
 */  

int f[10];

void init(int n)
{

    for(int i=1;i<=n;i++)
    {
        f[i]=i;//建立起了n个单元数集合 
    }
    return;	
}
//查找祖先  
int find(int x)
{
    //非递归
    while(f[x]!=x)
    {
        x=f[x];

    } 
    return x;

}
//查找祖先 O(n) 
int find1(int x)
{
    //递归
    if(f[x]!=x)
    {
        return find1(f[x]);
    }
    return x;
}
//优化 路径压缩 --O(1)
int find2(int x)
{
    //递归
    if(f[x]!=x)
    {
        return f[x]=find2(f[x]);      
    }
    return x;
}
//建立x y的关系--通过合并两者所在的集合 
void unionn(int x,int y)
{
    int ax=find2(x);
    int ay=find2(y);

    f[ay]=ax;//合并	

    //f[find2(x)]=find2(y); 


}
int main()
{
    init(6);
    int m,x,y;
    scanf("%d",&m);//有m对关系
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        unionn(x,y);//建立起关系； 

    } 
    scanf("%d",&m);//有m个查询
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        int ax=find2(x);
        int ay=find2(y);
        if(ax==ay)
        {
            printf("YES\n");//x和y有关系 
        } 
        else{
            printf("No\n");//x和没有关系 
        } 

    } 	
} 

哈夫曼树

在学习哈夫曼树前要先理解四个概念

节点的路径长度：从根结点到该节点的路径上的连接数。

树的路径长度：就是树的每个叶子节点的路径长度之和。

节点的带权路径长度：节点的路径长度与节点权值的乘积。

树的带权路径长度 WPL：就是树的所有叶子节点的带权路径长度之和。

哈夫曼树的拼接过程

​ 简单来说就是从一片森林中重复的选择根节点最小的两棵树进行拼接。

哈夫曼编码

​ 哈夫曼编码是哈夫曼树的主要应用场景。在平时生活中基本分为两个编码方式，一种为定长编码如ASCII编码、 Unicode编码等，还有一种是变长编码。哈夫曼编码就是一种变长编码。变长编码的出现解决了定长编码空间浪费的缺点。但是由于是变长编码，所以要保证编码的前缀码不重合，哈夫曼编码的前缀码就是不重合的。

哈夫曼编码的过程

属性集合

// 用数组模拟树，标记清楚每个结点孩子及双亲结点的下标 
typedef struct 
{
    int weight;// 权值				
    int lChild, rChild;		
    int parent;				
}HuffmanNode, *HuffmanTree;

typedef char *HuffmanCode;// 编码：0/1字符表示

哈夫曼编码树之创立哈夫曼树

挑选出哈夫曼树中的最小节点

static void selectNode(HuffmanTree tree, int n, int *s1, int *s2) 
{

    int min = 0;
    //找两个根节点 
    for (int i = 1; i <= n; ++i) 
    {
        //先找没双亲结点的那个
        if (tree[i].parent == 0) 
        {
            min = i;
            break;
        }
    }
    //遍历全部的结点
    for (int i = 1; i <= n; ++i)
    {
        //先找最小的根节点 
        if (tree[i].parent == 0) 
        {
            if (tree[i].weight < tree[min].weight) 
            {
                min = i;
            }
        }
    }

    *s1 =  min;// 和下面那个s2相同，由于传进来的是实参，所以能对实际值进行更改
    //找第二小的根节点 
    for (int i = 1; i <= n; ++i) 
    {
        if (tree[i].parent == 0 && i != *s1) 
        {	
            min = i;
            break;
        }
    }
    for (int i = 1; i <= n; ++i) 
    {
        if (tree[i].parent == 0 && i != *s1) 
        {
            if (tree[i].weight < tree[min].weight) 
            {
                min = i;
            }
        }
    }
    *s2 = min;
}

创立哈夫曼树

HuffmanTree createHuffmanTree(const int *w, int n) 
{
    HuffmanTree tree;
    int m = 2 * n - 1;// 这样赋值的原因是由于哈夫曼树的叶子节点是n，所有节点就为2n-1
    //叶子结点n个，木有度为1的结点，度为2的结点n-1(规律：n0=n2+1) 
    tree = (HuffmanTree) malloc(sizeof(HuffmanNode) * (m + 1));//下标0位置不用，多开一个内存 
    //初始化树中结点 
    for (int i = 1; i <= m; ++i) 
    {
        tree[i].parent = tree[i].lChild = tree[i].rChild = 0;
        tree[i].weight = 0;
    }

    for (int i = 1; i <= n; ++i) 
    {
        tree[i].weight = w[i - 1];//权值 
    }

    int s1, s2;
    //建树 
    for (int i = n + 1; i <= m; ++i) 
    {
        selectNode(tree, i - 1, &s1, &s2);//指针传递 找最小的两个根节点，则第i个结点是他俩的父亲 
        tree[s1].parent = tree[s2].parent = i;
        tree[i].lChild = s1;	
        tree[i].rChild = s2;
        tree[i].weight = tree[s1].weight + tree[s2].weight;
    }
    return tree;
}

哈夫曼编码树之求每个字母的编码

//以树为基础构建编码 从叶子结点到根节点 逆向求每个叶子的编码
HuffmanCode *createHuffmanCode(HuffmanTree tree, int n) 
{
    //具体的编码的工作空间--把编码放temp数组中 
    char *temp = (char *) malloc(sizeof(char) * n);//一维数组 
    //分配 n个编码的头指针
    HuffmanCode *codes = (HuffmanCode *) malloc(sizeof(HuffmanCode) * n);//此时codes为一维数组 

    memset(codes, 0, sizeof(HuffmanCode) * n);

    //编码空间的起始位置
    int start;							
    int p;								
    int pos;

    for (int i = 1; i <= n; ++i) 
    {		
        start = n - 1;//因为最多就是一条链，编码长度为n（下标0____n-1） 

        temp[start] = '\0';//字符串的结束符 \0，右往左逐位存放编码 首先就先放结束符

        pos = i;//i结点 

        p = tree[i].parent;//i结点的双亲结点 

        while (p) 
        {
            --start;
            temp[start] = ( (tree[p].lChild == pos) ? '0' : '1');
            pos = p;
            p = tree[p].parent;
        }

        codes[i - 1] = (HuffmanCode) malloc(sizeof(char) * (n - start));//(n - start)编码长度 

        strcpy(codes[i - 1], &temp[start]);//此时codes为二维数组 
    }
    free(temp);
    return codes;
}

哈夫曼树的总代码

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
//用数组模拟树，标记清楚每个结点孩子及双亲结点的下标 
typedef struct 
{
    int weight;//权值				
    int lChild, rChild;		
    int parent;				
}HuffmanNode, *HuffmanTree;

typedef char *HuffmanCode;//编码：0/1字符表示

static void selectNode(HuffmanTree tree, int n, int *s1, int *s2) 
{

    int min = 0;
    //找两个根节点 
    for (int i = 1; i <= n; ++i) 
    {
        //先找没双亲结点的那个
        if (tree[i].parent == 0) 
        {
            min = i;
            break;
        }
    }
    //遍历全部的结点
    for (int i = 1; i <= n; ++i)
    {
        //先找最小的根节点 
        if (tree[i].parent == 0) 
        {
            if (tree[i].weight < tree[min].weight) 
            {
                min = i;
            }
        }
    }

    *s1 =  min;
    //找第二小的根节点 
    for (int i = 1; i <= n; ++i) 
    {
        if (tree[i].parent == 0 && i != *s1) 
        {	
            min = i;
            break;
        }
    }
    for (int i = 1; i <= n; ++i) 
    {
        if (tree[i].parent == 0 && i != *s1) 
        {
            if (tree[i].weight < tree[min].weight) 
            {
                min = i;
            }
        }
    }
    *s2 = min;
}

HuffmanTree createHuffmanTree(const int *w, int n) 
{
    HuffmanTree tree;
    int m = 2 * n - 1;
    //叶子结点n个，木有度为1的结点，度为2的结点n-1(规律：n0=n2+1) 
    tree = (HuffmanTree) malloc(sizeof(HuffmanNode) * (m + 1));//下标0位置不用，多开一个内存 
    //初始化树中结点 
    for (int i = 1; i <= m; ++i) 
    {
        tree[i].parent = tree[i].lChild = tree[i].rChild = 0;
        tree[i].weight = 0;
    }

    for (int i = 1; i <= n; ++i) 
    {
        tree[i].weight = w[i - 1];//权值 
    }

    int s1, s2;
    //建树 
    for (int i = n + 1; i <= m; ++i) 
    {
        selectNode(tree, i - 1, &s1, &s2);//指针传递 找最小的两个根节点，则第i个结点是他俩的父亲 
        tree[s1].parent = tree[s2].parent = i;
        tree[i].lChild = s1;	
        tree[i].rChild = s2;
        tree[i].weight = tree[s1].weight + tree[s2].weight;
    }
    return tree;
}


//以树为基础构建编码 从叶子结点到根节点 逆向求每个叶子的编码
HuffmanCode *createHuffmanCode(HuffmanTree tree, int n) 
{
    //具体的编码的工作空间--把编码放temp数组中 
    char *temp = (char *) malloc(sizeof(char) * n);//一维数组 
    //分配 n个编码的头指针
    HuffmanCode *codes = (HuffmanCode *) malloc(sizeof(HuffmanCode) * n);//此时codes为一维数组 

    memset(codes, 0, sizeof(HuffmanCode) * n);

    //编码空间的起始位置
    int start;							
    int p;								
    int pos;

    for (int i = 1; i <= n; ++i) 
    {		
        start = n - 1;//因为最多就是一条链，编码长度为n（下标0____n-1） 

        temp[start] = '\0';//字符串的结束符 \0，右往左逐位存放编码 首先就先放结束符

        pos = i;//i结点 

        p = tree[i].parent;//i结点的双亲结点 

        while (p) 
        {
            --start;
            temp[start] = ( (tree[p].lChild == pos) ? '0' : '1');
            pos = p;
            p = tree[p].parent;
        }

        codes[i - 1] = (HuffmanCode) malloc(sizeof(char) * (n - start));//(n - start)编码长度 

        strcpy(codes[i - 1], &temp[start]);//此时codes为二维数组 
    }
    free(temp);
    return codes;
}


int main() 
{
    int w[] = {5, 29, 7, 8,14, 23, 3, 11};
    char show[] = {'A', 'B', 'C', 'D','E', 'F', 'G', 'H'};
    HuffmanTree tree = createHuffmanTree(w, sizeof(w) / sizeof(w[0]));

    HuffmanCode *code = createHuffmanCode(tree, sizeof(w) / sizeof(w[0]));
    for (int i = 0; i < sizeof(w) / sizeof(w[0]); ++i) 
    {
        printf("%c: %s\n", show[i], code[i]);
    }

    return 0;
}

图

​ 图G是由两个集合V和E组成，记为G = （V， E），其中V是顶点的有限非空集合， E是V中顶点偶对的有限集，这些顶点偶对称之为边（弧）。

图的相关概念

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

无向图：在图G中，如果代表边的顶点偶对是无序的，则称G为无向图。

有向图：在图G中，如果表示边的顶点偶对是有序的，则称G为有向图。⼀个图要么为无向图，要么为有向 图。不存在部分有向或者部分无向的情况。 、

完全图：如果图中的每两个顶点之间，都存在⼀条边，我们就称这个图为完全图。

完全有向图：有n(n-1)条边

完全无向图：有n(n-1)/2条边

端点和邻接点

• 在⼀个无向图中，若存在⼀条边（i， j），则称顶点i和顶点j为该边的两个端点。并称它们互为邻接点。
• 在⼀个有向图中，若存在⼀条边<i， j>，则称顶点i和顶点j为该边的两个端点。它们互为邻接点。此时，顶点i为起点。顶点j为终点。

顶点的度、入度和出度

• 在无向图中，顶点所具有的边的数目称为该顶点的度。
• 在有向图中，顶点v的度就分为入度和出度，以顶点v为终点的入边的数目。称为该顶点的入度。以顶点v为起点的出边的数目，称为该顶点的出度。⼀个顶点的入度和出度的和称为该顶点的度。在⼀个具有e条边的图中：度之和为2e。

子图：设有两个图G = （V， E）和G‘ = （V’， E'），若V‘是V的子集。则称G’是G的子图。

路径和路径长度：

​ 在⼀个图G=(V, E)中，从顶点i到顶点j的一路径是一个顶点序列(i, i1, i2, ..., im, j)，若此图G是无向图，则边(i, i1), (i1, i2), ...(im, j) 属于E(G)；若此图是有向图，则<i, i1>, <i1, i2>, ...<im, j> 属于E(G)。路径长度是指⼀条路径上经过的边的数目。若⼀条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。

回路或环

​ 如果一条路径上的开始点与结束点为同一个顶点，则称此路为回路或者为环。开始点和结束点相同的简单路径被称为简单回路或者简单环。如果经过图中各边一次且恰好⼀次的环路，称之为欧拉环路，也就是其长度恰好等于图中边的总数， { C， A， B， A， D， C， D， B， C}就是⼀条欧拉环路。如果是经过图中的各顶点⼀次且恰好⼀次的环路，称作哈密尔顿环路，其⻓度等于构成环路的边数。 { C, A，D B C}就是⼀条哈密尔顿环路。

连通、连通图和连通分量

​ 在无向图G中，若从顶点i到顶点j有路径，则称这两个顶点时连通的。如果图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G中的极大连通子图称为G的连通分量。对于连通图只有⼀个极大连通子图，就是它本身（是唯⼀的）。非连通图有多个极大连通子图。（非连通图的极大连通子图叫做连通分量，每个分量都是⼀个连通图）。之所以称为极大是因为如果此时加入一个不在图的点集中的点都会导致它不再连通。

​ 至于极小连通⼦图，首先只有连通图才有极小连通子图这个概念。就像⼀个四边形，四个节点四条边，其实三条边就能连通了，所以四个节点三条边，就OK了，就是在能连通的前提下，把多余的边去掉。

强连通图和强连通分量

​ 在有向图G中，若从顶点i到顶点j有路径，则称从顶点i到顶点j是连通的。若图G中的任意两个顶点i和顶点j都连通，即从顶点i到顶点j和从顶点j到顶点i都存在路径，则称图G是强连通图。有向图G中的极大强连通子图称为G的强连通分量。显然，强连通图只有⼀个强连通分量，即自身，非强连通图有多个强连通分量。

稠密图、稀疏图

• 当⼀个图接近完全图的时候，称之为疏密图；相反，当⼀个图含有较少的边数，则称之为稀疏图。
• ⼀般对于这个边的个数，说法比较多，通常认为边小于nlogn（n是顶点的个数）的图称之为稀疏图，反之称为稠密图。

权和网

​ 图中的每⼀条边都可以附有⼀个对应的数，这种与边相关的数称为权。权可以表示从⼀个顶点到另⼀个顶点的距离或者花费的代价。边上带有权的图称为带权图，也称之为网。

连通图的生成树

所谓连通图的生成树是⼀个极小的连通⼦图，它含有图中全部的n个结点，但是只有构成树的n-1条边。

图的存储

图在内存中存储方式有很多种，最经典的包括邻接矩阵、邻接表、逆邻接表和十字链表。

邻接矩阵

​ 图的邻接矩阵是用两个数组来表示，一个一位数组存储图中的顶点信息，一个二维数组（我们将这个数组称之为邻接矩阵）存储图中的边的信息。

无向图邻接矩阵

​ 我们可以设置两个数组，顶点数组为vertex[4]={V0,V1,V2,V3}，边数组arc[4] [4]为对称矩阵(0表示不存在顶点间的边， 1表示顶点间存在边)。

对称矩阵

​ 所谓对称矩阵就是n阶矩阵的元素满足a[i] [j]=a[j] [i] (0<=i,j<=n)。即从矩阵的左上⻆到右下⻆的主对角线为轴，右上角的元与左下角相对应的元全都是相等的。

有了这个⼆维数组组成的对称矩阵，我们就可以很容易地知道图中的信息：

• 判定任意两顶点是否有边无边；
• 可以轻松知道某个顶点的度，其实就是这个顶点Vi在邻接矩阵中第i行(或第i列)的元素之和；
• 求顶点Vi的所有邻接点就是将矩阵中第i行元素扫描⼀遍， arc[i] [j]为1就是邻接点。

有向图邻接矩阵

​ 可见顶点数组vertex[4]={V0,V1,V2,V3}，弧数组arc[4] [4]也是⼀个矩阵，但因为是有向图，所以这个矩阵并不对称，例如由V0到V3有弧，得到arc[0] [3]=1，而V3到V0没有弧，因此arc[3] [0]=0。

​ 另外有向图是有讲究的，要考虑入度和出度，顶点V1的入度为1，正好是第V1列的各数之和，顶点V1的出度为2，正好是第V1行的各数之和。

带权图的邻接矩阵

​ 带权图中的每⼀条边上带有权值，邻接矩阵中的值则为权值，当两个顶点之间没有弧时，则用无穷大表示。

这⾥“∞”表示⼀个计算机允许的、大于所有边上权值的值。

​ 这个时候我们会发现⼀个问题，就是空间浪费问题。尤其是面对边数相对比较少的稀疏图来说，这种结构无疑是存在对存储空间的极大浪费。

​ 因此我们可以考虑另外⼀种存储结构方式，例如把数组与链表结合在⼀起来存储，这种方式在图结构也适用，我们称为邻接表(Adjacency List)。

邻接矩阵代码实现

//一个数组代表顶点集合
//一个二维数组来代表边集
#define MaxVertices 100
#define MaxWeight 32767 //带权图 点不邻接的时候 无穷大（16位int范围-32768~+32767） 
typedef struct {
    int Vertices[MaxVertices];//顶点的数组信息
    int Edge[MaxVertices][MaxVertices];//边的信息
    int numV;//顶点的个数
    int numE;//边的个数
}AdjMatrix;

void CreateGraph(AdjMatrix* G)
{
    int n, e;
    int vi, vj, w;
    //先输入图的顶点的个数和边的个数
    scanf("%d,%d", &n, &e);
    G->numV = n; G->numE = e;
    for (int i = 0; i < n; i++) {// 将图继续初始化（ 有边连接填入0，无边连接填入1 ）
        for (int j = 0; j < n; j++)
        {
            if (i == j)
            {
                G->Edge[i][j] = 0;
            }
            else
            {
                G->Edge[i][j] = MaxWeight;
            }
        }
    }
    //把顶点放到数组当中
    for (int i = 0; i < G->numV; i++)
    {
        //开始输入顶点的信息
        scanf("%d", &G->Vertices[i]);
    }

    //输入边的信息
    for (int i = 0; i < G->numE; i++)
    {
        //输入边的信息 邻接点的两端 如果是带权图 输入边的权值
        scanf("%d%d%d", &vi, &vj, &w);
        //还要在查找 找到对应的下标
        G->Edge[vi][vj] = w;
        //如果是无向图 是个对称矩阵
        G->Edge[vj][vi] = w;
    }
}

邻接表

邻接表的处理方法是这样：

• 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。
• 图中每个顶点Vi的所有邻接点构成⼀个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。

无向邻接表

有向邻接表

​ 若是有向图，邻接表结构也是类似的，我们先来看下把顶点当弧尾建立的邻接表，这样很容易就可以得到每个顶点的出度：

但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立⼀个有向图的逆邻接表：

带权网络的邻接表

邻接表的代码实现

#include<stdio.h>
//邻接表
//边表结点
typedef struct EdgeNode
{
    int adjvex;//邻接的结点
    struct EdgeNode* next;
    int weight;//如果是个带权图 要有权值
}EdgeNode;
//z顶点信息
typedef struct VertexNode
{
    char data;//基本的数据 顶点域存放顶点信息
    struct EdgeNode* firstedge;
}VertexNode;
//邻接表的结构
typedef struct GraphadjList
{
    VertexNode adjList[100];//顶点表的结点数组
    int numV, numE;//顶点个数和边的个数
}GraphadjList;
//无向图的邻接表的创建
void CreatALGraph(GraphadjList* G)
{
    int vi, vj;
    EdgeNode* e;
    //先输入顶点信息和边的信息
    scanf("%d%d", &G->numV, &G->numE);
    //初始化结点信息
    for (int i = 0; i < G->numV; i++)
    {
        scanf("%c", &G->adjList[i].data);// 先将顶点存入到表中
        getchar();
        G->adjList[i].firstedge = NULL;
    }
    //建立边表
    for (int i = 0; i < G->numE; i++)// 进行连接
    {
        //输入每条边邻接的两个顶点
        scanf("%d%d", &vi, &vj);
        //如果输入的是真实的数据 还是要去找下标
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = vj;
        e->next = G->adjList[vi].firstedge;
        G->adjList[vi].firstedge = e;
		
        // 无向图需要以下操作，因为要反向的连接
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = vi;
        e->next = G->adjList[vj].firstedge;
        G->adjList[vj].firstedge = e;
    }
}

十字链表

十字链表表示

顶点集：

边集：

​ 其中的tailVex表示该弧的弧尾顶点在顶点数组中的位置， headVex表示该弧的弧头顶点在顶点数组中的位置。 headLink则表示指向弧头相同的下⼀条弧， teadLink则表示指向弧尾相同的下⼀条弧。

#include<stdio.h>
#include<stdlib.h>
//边集的数据
typedef struct ArcBox
{
    int tailvex, headvex;//弧尾、弧头所在的位置
    struct ArcBox* hlink, tlink;//弧尾相同、弧头相同的下一个弧
    int weight;
}ArcBox;
//顶点的数据
typedef struct VexNode
{
    int data;//真实的数据
    ArcBox* firstin, * firstout;//出度指针 入度指针
}VexNode;

typedef struct{
    VexNode xlist[20];
    int numV, numE;
}OLGraph;

void CreateDG(OLGraph* G)
{
    //输入顶点数和边数
    scanf("%d%d", &(G->numV), &(G->numE));
    for (int i = 0; i < G->numV; i++)
    {
        scanf("%d", &(G->xlist[i].data));
        G->xlist[i].firstin = NULL;
        G->xlist[i].firstout = NULL;
    }
    //构建十字链表
    for (int i = 0; i < G->numE; i++)
    {
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        //查找相对应的下标
        ArcBox* p = (ArcBox*)malloc(sizeof(ArcBox));
        p->tailvex = v1;
        p->headvex = v2;
        //采用头插法插入新的p结点
        p->hlink = G->xlist[v2].firstin;
        p->tlink = G->xlist[v1].firstout;
        G->xlist[v2].firstin = G->xlist[v1].firstout = p;
    }
}

邻接多重表

​ 邻接表对边的操作显然很不方便，因此，我们可以仿照十字链表的方式，对边表结构进行改装，重新定义的边表结构如下：

​ 其中iVex和jVex是与某条边依附的两个顶点在顶点表中的下标。 iLink指向依附顶点iVex的下⼀条边， jLink指向依附顶点jVex的下⼀条边。

#include<stdio.h>
//邻接多重表
//边表集合
typedef struct node
{
    int ivex, jvex;
    struct node* vi, *vj;
}ArcNode;
//结点
typedef struct
{
    char vertex;

    ArcNode* firstEdge;
}VNode;

typedef struct
{
    VNode Dvex[50];
    int numV, numE;
}Graph;

void creat(Graph* G)
{
    //先输入顶点数和边数
    scanf("%d%d", &(G->numV), &(G->numE));
    ArcNode* new_node;
    for (int i = 0; i < G->numV; i++)
    {
        scanf("%d", &G->Dvex[i].vertex);
        G->Dvex[i].firstEdge = NULL;
    }
    for (int i = 0; i < G->numE; i++)
    {
        //输入边对应的下标
        int vi, vj;
        new_node = (ArcNode*)malloc(sizeof(ArcNode));
        new_node->ivex = vi;
        new_node->jvex = vj;
        new_node->vi = G->Dvex[vi].firstEdge;
        G->Dvex[vi].firstEdge = new_node;
        new_node->vj = G->Dvex[vj].firstEdge;
        G->Dvex[vj].firstEdge = new_node;
    }
}

图的遍历

深度优先搜索（DFS）

​ 深度优化遍历( Depth First Search )，也有称为 深度优化搜索 ，简称为 DFS 。事实上，我们在树的遍历中早已涉及DFS，层序遍历、中序遍历和后序遍历都属于深度优先遍历的方式，因为这些遍历方式本质上都归结于栈

右手原则 在没有碰到重复顶点的情况下，分叉路口始终是向右手边走，每路过⼀个顶点就做⼀个记号。

左手原则 在没有碰到重复顶点的情况下，分叉路口始终是向左手边走，每路过⼀个顶点就做⼀个记号。

画图展示深度优先遍历，使用右手原则

代码

/*
创建无权无向图并深度优先搜索--基于邻接矩阵存图 
*/

#include <stdio.h>
#include <stdlib.h>
#define MAXN 100
typedef struct ArcCell {
    char vexnum[MAXN];         //顶点
    int arcnum[MAXN][MAXN];    //弧
    int n, e;                  //顶点数， 弧数
}Graph;
int Visit[MAXN];         //定义Visit来判断顶点是否被访问，并初始化（全局变量默认为0） 



void CreateGraph(Graph* G) {        //创建图 ，此处注意&G 
    int s, t;
    scanf("%d %d", &G->n, &G->e);
    getchar();//读掉回车 
    for (int i = 0; i < G->n; i++) {
        scanf("%c", &G->vexnum[i]);

    }
    for (int i = 0; i < G->n; i++) {              //初始化数据 
        for (int j = 0; j < G->n; j++) {
            G->arcnum[i][j] = 0;
        }
    }
    for (int i = 0; i < G->e; i++) {              //创建图的邻接矩阵
        scanf("%d %d", &s, &t);
        G->arcnum[s][t] = 1;
        G->arcnum[t][s] = 1;
    }
}

//开始搜索 找一个开始结点
/*
开始结点是人定义的
Graph G 需要遍历哪一个图
int i 遍历的起始结点从哪里开始
标记结点
1、遍历未被标记的结点
2、如果遍历到某一个邻接点是已被标记 我要继续找和我相邻的另外一个结点

*/
void DFSTraverse(Graph G, int i)//找邻接点
{
    printf("%c", G.vexnum[i]);// 打印遍历的节点

    for (int j = 0; j < G.n; j++)
    {
        if (G.arcnum[i][j] && !Visit[j])// 如果点与点之间存在连接，且没有访问过
        {
            Visit[j] = 1;
            DFSTraverse(G, j);
        }

    }

}

void DFS(Graph G)//遍历
// 这里需要注意，由于图不一定是连通图，所以会有这个函数
{
    for (int i = 0; i < G.n; i++)//对整个图的结点进行深搜
    {
        if (!Visit[i])
        {
            Visit[i] = 1;
            DFSTraverse(G, i);
        }
    }
}

int main()
{
    Graph G;
    CreateGraph(&G);
    DFS(G);
    return 0;

}
/*
测试用例：
9
15
ABCDEFGHI 
0 1
0 5
1 6
5 6
2 1
1 8
2 8
6 7
2 3
3 8
3 7
3 4
4 7
4 5
3 6
*/

广度优先搜索（BFS）

​ 广度优先遍历（Breadth First Search），又称为广度优先搜索，简称BFS。树的层序遍历方式便是⼀种广度优先搜索方式。为了清晰地理解广度优先搜索，我们同样以深度优先搜索的例子一起走一遍，这不过，我们对图中顶点的位置做了调整，这样看起来更清楚

画图演示广度优先遍历

代码

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX 100
#define inf 65535  //表示两点之间没有边相连
typedef enum {false, true }bool;//c语言没有bool，要自己声明 
int visit[100];   //标记顶点是否被访问

/**带权无向图的邻接链表的建立--基于邻接表**/
//边表结点数据结构
typedef struct EdgeNode
{
    int adjvex;  //存储该顶点对应的下标
    int weight;
    struct EdgeNode *next; //指向下一个邻接点
}EdgeNode;

//顶点表结点数据结构
typedef struct VertexNode
{
    char Vertex;  //存储顶点信息
    EdgeNode *FistEdge; //边表头指针
}VertexNode;

//邻接链表图的数据结构
typedef struct
{
    VertexNode adjList[100];
    int VertexNumber,EdgeNumber; //顶点数和边数
}GraphAdjList;


/**无向图邻接链表的建立**/
void Create_no_direction_LinkList_Graph(GraphAdjList *G)
{
    int i,j,w,k;
    // printf("请输入无向图邻接链表的顶点数和边数：\n");
    scanf("%d %d",&G->VertexNumber,&G->EdgeNumber);

    //输入顶点信息，建立顶点表
    //printf("顶点表的建立：输入顶点信息，如ABCDEF.....\n");
    //char ch;
    //while( ( ch = getchar()  != '\n' ) );
    getchar();
    for(i=0;i<G->VertexNumber;i++)
    {
        scanf("%c",&G->adjList[i].Vertex);
        G->adjList[i].FistEdge = NULL;

    }
    // printf("边表的建立：输入边（vi,vj）的顶点下标，权值统一为1，如：0 1 1(权值)\n");

    for(k=0;k<G->EdgeNumber;k++)
    {
        scanf("%d %d %d",&i,&j,&w);

        EdgeNode *e;
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->weight = w;
        e->adjvex = j;
        e->next = G->adjList[i].FistEdge;   //头插法将下标为j的顶点插入与之相连的下标为i的结点链表中
        G->adjList[i].FistEdge = e;

        //无向图，因此是对称的，同样的操作将下标为i的顶点插入与之相连的下标为j的结点的链表中
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->weight = w;
        e->adjvex = i;
        e->next = G->adjList[j].FistEdge;
        G->adjList[j].FistEdge = e;
    }


    //    打印检查
    /*    printf("---------------------构造出来的无向图邻接链表的边信息如下---------------------\n");
    for(i=0;i<G->VertexNumber;i++)
    {
        EdgeNode *p;
        p = G->adjList[i].FistEdge;
        printf("%d\t",i);
        while(p != NULL)
        {
            printf("%d ",p->adjvex);
            p = p->next;
        }
        printf("\n");
    }*/
}
/**BFS会用到队列这个数据结构**/
/**顺序表实现循环队列**/
typedef struct
{
    char data[MAX_VERTEX];
    int front;  //头指针
    int rear;   //尾指针，队列非空则指向队尾最后一个元素后一个位置
}SqQueue;

//队列初始化
void InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
}
//入队
bool EnQueue(SqQueue *Q, char e)
{
    //判断队列是否满
    if( ( Q->rear+1 ) % MAX_VERTEX == Q->front )
        return false;
    Q->data[Q->rear]=e;
    Q->rear = (Q->rear+1)%MAX_VERTEX;
    return true;
}
//出队---删除队首元素，并赋给e
char* DeQueue(SqQueue *Q, char *e)
{
    //判断队列是否为空
    if( Q->front == Q->rear )
        return NULL;
    *e = Q->data[Q->front];
    Q->front = (Q->front+1)%MAX_VERTEX;
    return e;
}
//队列判空
bool isEmptyQueue(SqQueue *Q)
{
    return Q->front == Q->rear?true:false;
}

//----------------------------以上是队列操作------------------------------------

//无向图邻接链表BFS
void BFS_Travel(GraphAdjList G)
{
    int i,j,mark;
    char data;
    SqQueue Q;
    EdgeNode *p;
    //初始化visit数组
    for(i=0;i<G.VertexNumber;i++)
        visit[i] = false;

    //初始化队列
    InitQueue(&Q);

    //对每个顶点进行BFS
    //printf("此无向图邻接链表BFS结果为：\n");
    for(i=0;i<G.VertexNumber;i++)
    {
        if(!visit[i]) // 如果节点没有被访问过
        {
            visit[i] = true;// 标记节点被访问过

            EnQueue(&Q,G.adjList[i].Vertex);// 将该节点入队

            while(!isEmptyQueue(&Q))// 如果队非空
            {
                DeQueue(&Q,&data); // 出队
                printf("%c ",data);// 打印节点值

                //根据删除顶点实时更新追踪该顶点下标，以便正确找到与之相连的其他顶点
                for(j=0;j<G.VertexNumber;j++)
                    if(G.adjList[j].Vertex==data)
                        mark = j;
                // 找到这个p是为了遍历接着节点连接的所有节点
                p = G.adjList[mark].FistEdge;

                //找寻与此顶点相连且没访问过的其他顶点
                while(p)
                {
                    if(!visit[p->adjvex])
                    {
                        visit[p->adjvex] = true;
                        EnQueue(&Q,G.adjList[p->adjvex].Vertex);
                    }
                    p = p->next;
                }
            }
        }
    }

}


int main()
{

    GraphAdjList G;
    Create_no_direction_LinkList_Graph(&G);
    BFS_Travel(G);
    return 0;
}

/*
测试用例：
9
15
ABCDEFGHI 
0 1 1
0 5 1
1 6 1
5 6 1
2 1 1
1 8 1
2 8 1
6 7 1
2 3 1
3 8 1
3 7 1
3 4 1
4 7 1
4 5 1
3 6 1
*/

最小生成树

生成树

​ ⼀个连通图的生成树是⼀个极小的连通子图，它包含图中全部的n个顶点，但只有构成⼀棵树的n-1条边。

生成树的性质

• 一个连通图可以有多个生成树；
• 一个连通图的所有生成树都包含相同的顶点个数和边数；
• 生成树当中不存在环；
• 移除生成树中的任意⼀条边都会导致图的不连通， 生成树的边最少特性；
• 在生成树中添加⼀条边会构成环。
• 对于包含n个顶点的连通图，生成树包含n个顶点和n-1条边；
• 对于包含n个顶点的无向完全图最多包含 n^n-2^颗生成树。

最小生成树

​ 所谓⼀个 带权图 的最小生成树，就是原图中边的权值最小的生成树 ，所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。

克鲁斯卡尔（Kruskal）算法

​ 克鲁斯卡尔算法又叫做加边法。顾名思义这种算法的核心时增加边来构建最小生成树。克鲁斯卡尔算法的两个核心点为

1. 选取尽量小的边加入
2. 加入边后不允许存在换（ 并查集实现 ）

​ 时间复杂度为O(nlogn)其中n为边的数量，所有克鲁斯卡尔算法适合稀疏图的情况。

画图演示过程

代码

​ 克鲁斯卡尔算法实现的顺序就是先将所有的边进行排序，然后再随着排序的顺序进行加入并通过并查集的方法判断是否加入边。

#include <stdio.h>
#include <stdlib.h>
#define INF 65535
/*找最小生成树---->选出n-1条边：

1.选出n-1条权值尽量小的边： 每次都选新的最小的边E---基于贪心 
2. 其中不能出现环 ：   采用并查集，判断一下 E的两个端点是不是属于同一个连通集合：(1)yes,说明E不能选  (2)no, 说明要选E 

Kruskal的思路 ---贪心（贪婪）思想 ：趋利避害   目光短浅 

时间复杂度：在并查集采用路径压缩的基础上 O(eloge) ----适合 稀疏图 
*/ 

//邻接矩阵存图--带权无向图 
int g[105][105];//假设最多有100个点
int nv,ne;
typedef struct{
    int u,v;//端点 
    int w;//权值 	
}Edge;
Edge e[5005];
void sorte(int l,int r)
{
    //选择
    int minn;
    Edge tmp;
    for(int i=l;i<r;i++)// 选择排序，通过权值来升序排序
    {
        minn=i;
        for(int j=i+1;j<r;j++)
        {
            if(e[minn].w >e[j].w )
            {
                minn=j;
            }
        } 
        tmp=e[i];
        e[i]=e[minn];
        e[minn]=tmp;
    } 
    //输出排序之后的结果；
    printf("按权值升序排列：\n");
    for(int i=0;i<r;i++)
    {
        printf("(%d %d) %d\n",e[i].v,e[i].u,e[i].w);
    }  
}
int find(int* f,int z)// 去判断是否为环，也就是并查集中查找方法
{
    while(z!=f[z])
    {
        z=f[z];
    }
    return z;
}
void Kruskal()
{
    int f[105];
    for(int i=0;i<nv;i++)
    {
        f[i]=i;
    }
    printf("以下是最小生成树的边：\n");
    for(int i=0;i<ne;i++)
    {
        int fu=find(f,e[i].u);
        int fv=find(f,e[i].v);

        if(fu!=fv)
        {
            f[fv]=fu;// 并查集中的合并操作  
            printf("(%d %d) %d\n",e[i].v,e[i].u,e[i].w);
        }
    }

}
int main()
{
    scanf("%d %d",&nv,&ne);
    for(int i=0;i<nv;i++) // 初始化图
        for(int j=0;j<nv;j++)
        {
            if(i==j)
            {
                g[i][j]=g[j][i]=0;
            }	
            else{
                g[i][j]=g[j][i]=INF;
            }
        }
    int x,y,wi;
    int k=0;//边数组下标 
    for(int i=0;i<ne;i++)
    {
        scanf("%d %d %d",&x,&y,&wi);
        g[x][y]=g[y][x]=wi;
        e[k].v =x;
        e[k].u =y;
        e[k].w =wi;
        k++; 
    }
    sorte(0,k);
    Kruskal();

    return 0;

}

/*
9 15
0 1 3
0 5 4
1 6 6
6 5 7
1 2 8
1 8 5
2 8 2
2 3 12
8 3 11
6 3 14
6 7 9
5 4 18
3 7 6
7 4 1
3 4 10
*/ 

普里姆（Prim） 算法

​ 普里姆算法又称加点法。故名思普里姆算法就是通过在与一个节点连通的点上选择权值最小的一个点。

​ 时间复杂度为O(n^2^)

画图演示过程

​ 这里展示的是构图过程，笔试计算过程可以参考迪杰斯特拉算法。

代码

​ 普里姆算法简单点来说就是维护dist数组，一开始的时候选择一个点（下面的代码选择的是0点）作为其实顶点。先将0和其他所有点之间的距离置为无穷大，接着更新dist数组，将和0相连接的点的距离加入到dist之中。接着再通过新的点能对dist继续更新，即选择路径最小的距离。重复以上过程。核心就是要选择到初始点的最短的路径。

#include <stdio.h>
#include <stdlib.h>
#define INF 65535
/* 
最小生成树---prim算法：选点，也在选边 
维护一个dist[]，点到生成树的距离，初始化无穷
1.选起点加到生成树中 
2。用起点去更新 与起点直接相连，并且还未加入到生成树中的点的dist 
3.n-1次循环：（1）选dist值最小的点（p点）加入生成树，用p点更新 与p点直接相连，并且还未加入到生成树中的点的dist
时间复杂度： O(V^2) ----适合 稠密图  
*/ 
//邻接矩阵存图--带权无向图 
int g[105][105];//假设最多有100个点
int dist[105];//记录点到点的距离 
int vi[105]; //0 代表没有加入到生成树 
int nv,ne;
int min(int x,int y)
{
    if(x<y)return x;
    else return y; 
}
void prim()
{
    dist[0]=0;
    vi[0]=1;//表示0已经加入到生成数中 
    for(int i=1;i<nv;i++)// 更新dist将和初试点连接的路径存入到dist中
    {
        dist[i]=min(dist[i],g[0][i]);//在dist数组中储存0到各点的距离
    } 
    int minn;
    int tmpd;
    for(int i=1;i<nv;i++)//循环nv-1次 
    {
        minn=-1;//保存 p点的编号 
        tmpd=INF;//保存dist值 
        for(int j=0;j<nv;j++)//找到最小的点 
        {
            if(vi[j]==0&&dist[j]<tmpd)//如果有点未被访问过且有更小的权值边
            {
                minn=j;
                tmpd=dist[j];

            } 
        }
        if(minn==-1)
        {
            return ;
        }
        printf("本次把点%d，通过边权为 %d的边加入到生成树中\n",minn,tmpd); 
        vi[minn]=1;//表示minn点已经加入生成树中 
        for(int j=1;j<nv;j++)//通过minn的值来更新到其他点的距离 
        {
            dist[j]=min(dist[j],g[minn][j]);
        }

    }	

}
int main()
{
    scanf("%d %d",&nv,&ne);//输入顶点数和边数 

    for(int i=0;i<nv;i++)//初始化邻接表 
        for(int j=0;j<nv;j++)
        {
            if(i==j)
            {
                g[i][j]=g[j][i]=0;
            }	
            else{
                g[i][j]=g[j][i]=INF;
            }
        }
    for(int i=0;i<nv;i++)//初始化dist数组 
    {
        dist[i]=INF;
    }
    int x,y,wi; 
    for(int i=0;i<ne;i++)
    {
        scanf("%d %d %d",&x,&y,&wi);
        g[x][y]=g[y][x]=wi;
    }
    prim();


    return 0;

}
/*
9 15
0 1 3
0 5 4
1 6 6
6 5 7
1 2 8
1 8 5
2 8 2
2 3 12
8 3 11
6 3 14
6 7 9
5 4 18
3 7 6
7 4 1
3 4 10
*/ 

最短路径

源点：路径起始的第⼀个顶点。

终点：最后⼀个顶点称为终点。

迪杰斯特拉（Dijkstra）算法

​ 迪杰斯特拉算法和普里姆算法很想，都是应用了贪心的思想。简单点来说就是每次都选择离源点最近的路径。普里姆已经展示了图的建立过程，接下来画一个解题的思路。

​ 时间复杂度为O(n^2^),需要注意的是迪杰斯特拉是只算一个点到各点之间的距离，若要算每个点到每个点之间的最短距离，时间复杂度会上升到O(n^3^)

画图演示过程

​ 下图中的原图中，用颜色从浅到深表示进入终点集的顺序。而旁边的表格中加深颜色的表示选择它。INF表示无穷大，及暂时不能通过中间节点到达。

​ 显然可见的是每列选择的都是一列值最小的，而后一列更新数据也是在前一列选择的基础进行更新。

代码

int g[105][105];// 这里是邻接表的简单表示
int nv,ne,v;//v是源点
int dist[105],path[105];// dist就是上述图中的第1次、第2次...... path是上述图中终点集
int ch[105];// 标记节点是否加入终点集
void dijkstra(){
    for(int i=0;i<ne;i++)// 根据源点进行更新
    {
        dist[i]=g[v][i];
        if(g[v][i]!=INF)
        {
            path[i]=v;// 将源点加入终点集
        }
    }
    int minn;//最小的dist 
    int k;//最小dist值是k点 
    for(int i=1;i<nv;i++)
    {
        minn=INF;
        for(int j=0;j<nv;j++)//找最小的dist 
        {
            if(ch[j]==0&&dist[j]<minn) 
            {
                minn=dist[j];
                k=j;
            } 

        } 
        ch[k]=1;
        for(int j=0;j<nv;j++)// 根据新的节点更新路径
        {
            if(ch[j]==0&&dist[k]+g[k][j]<dist[j])
            {
                dist[j]=dist[k]+g[k][j];
                path[j]=k;
            }
        }

    }

}

int main()
{
    int x,y,w;
    scanf("%d %d",&nv,&ne);
    for(int i=0;i<nv;i++)
    {
        for(int j=0;j<nv;j++)
        {
            if(i==j)g[i][j]=g[j][i]=0;
            else
                g[i][j]=g[j][i]=INF;
        }
    }
    for(int i=0;i<ne;i++)
    {
        scanf("%d %d %d",&x,&y,&w);
        g[x][y]=g[y][x]=w;
    }
    scanf("%d",&v);//输入起点
    for(int i=0;i<nv;i++)
    {
        dist[i]=INF;
    }

    dist[v]=0;
    ch[v]=1;
    path[v]=v;

    dijkstra();

    for(int i=0;i<nv;i++)// 形象的打印路径
    {
        printf("源点%d到%d的最短路径长度是:%d----",v,i,dist[i]);
        //倒序输出最短路径
        int j=i;
        printf("%d->",i);
        while(path[j]!=j)
        {
            printf("%d->",path[j]);
            j=path[j];	
        }
        printf("\n"); 

    }

    return 0; 	

}
/*
9 16
0 1 1
0 2 5
1 2 3
1 3 7
1 4 5
2 4 1
2 5 7
3 4 2
3 6 3
4 5 3
4 6 6
4 7 9
5 7 5
6 7 2
6 8 7
7 8 4
0
*/

弗洛伊德算法（Floyd） 算法

​ 弗洛伊德算法简单点来说就是对两种表格进行维护，一种表是点到点之间的最短距离，另一张表是到达点的前驱点。依次通过中间点来对表格进行更新。

画图演示过程

图-最短路径-Floyd(弗洛伊德)算法_哔哩哔哩_bilibili (opens new window)

核心代码

//k为中间点 
for(k = 0; k < G.vexnum; k++){
    //v为起点 
    for(v = 0 ; v < G.vexnum; v++){
        //w为终点 
        for(w =0; w < G.vexnum; w++){
            if(D[v][w] > (D[v][k] + D[k][w])){
                D[v][w] = D[v][k] + D[k][w];//更新最小路径 
                Path[v][w] = Path[v][k];//更新最小路径中间顶点 
            }
        }
    }
}

拓扑排序

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

活动：所有的工程或者某种流程都可以分为若干个小的工程或者阶段，我们称这些小的工程或阶段为“活 动”。

AOV网：在⼀个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系的有向图称为顶点 表示活动的网。

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

拓扑排序：由某个集合上的⼀个偏序得到该集合上的⼀个全序的操作过程称为拓扑排序。简单点来说就是⼀个有向⽆环图构造拓扑序列的过程。

拓扑排序的算法步骤

1. 在有向图中选一个没有前驱的顶点且输出。

2. 从图中删除该顶点和所有以它为尾的弧。

3. 重复上述两步，直至全部顶点均已输出，或者当前图不存在无前驱的顶点为止

   值得说明的是拓扑排序是有向图判断成环的方法，无向图是并查集。

画图演示过程

代码实现

​ 存储方式使用邻接表存储图，代码中使用到了栈，要记录入度为0的点，因为同一时刻可能会有不知一个入度为0的点，所以要用栈将这一时刻的点都保存下来（用数组或者队列都可）。在建图过程中使用到了indegree，是为了存储每个点的入度来方便寻找入度为0的节点。

#include <stdio.h>
#include <stdlib.h> 
#define OK 1
#define ERROR 0
#define MVNum 100
typedef int Status;
typedef char VerTexType;
typedef char OtherInfo;
int indegree[MVNum] = { 0 };//结点的入度个数

//创建栈 
typedef struct StackNode {
    int data;
    struct StackNode* next;
}StackNode, * StackList;
//出栈函数 
StackList Pop(StackList S, int* e)
{
    StackList p;
    p = S;
    if (!p)
        return ERROR;
    *e = p->data;
    S = S->next;
    free(p);
    return S;
}
//入栈函数： 
StackList Push(StackList S, int e)
{
    StackList p;
    p = (StackNode*)malloc(sizeof(StackNode));
    p->data = e;
    p->next = S;
    S = p;
    return S;
}

//邻接表创建有向图的实现
//边结点 
typedef struct ArcNode {    //链表结点
    int adjvex;           //邻接表创建无向网的实现
    struct ArcNode* nextarc;    //指向下一条边的指针
    //OtherInfo info;       //和边相关的信息
}ArcNode;

//顶点信息 
typedef struct VNode {   //头结点
    VerTexType data;   //顶点信息
    ArcNode* firstarc;//指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];//AdjList 表示邻接表类型

typedef struct {
    AdjList vertices;     //邻接表头结点数组
    int vexnum, arcnum;   //图的顶点数和弧数
}ALGraph;

//创建有向图：
int LocateVex(ALGraph* G, VerTexType v)  //G带操作的图；v要在图中定位的顶点
{
    int i;
    for (i = 0; i < (G->vexnum); i++)
    {
        if (v == G->vertices[i].data)
            return i;               //顶点存在则返回在头结点数组中的下标；否则返回
    }
}

void CreateUDG(ALGraph* G)
{
    int i, j, k;
    VerTexType v1, v2;
    ArcNode* p1;
    printf("输入总节点数和弧数：\n"); //G带操作的图；v要在图中定位的顶点
    scanf("%d %d", &G->vexnum, &G->arcnum);
    fflush(stdin);    //是清空输入缓冲区的
    printf("输入各个节点的值：\n");
    for (i = 0; i < G->vexnum; i++)   //邻接表初始化

    {
        scanf("%c", &G->vertices[i].data);
        getchar();
        G->vertices[i].firstarc = NULL;
    }

    for (k = 0; k < G->arcnum; k++)
    {
        //fflush(stdin);   //是清空输入缓冲区的
        scanf("%c", &v1);
        getchar();
        scanf("%c", &v2);
        getchar();
        i = LocateVex(G, v1);   //返回这两个顶点在顶点数组中的位置
        j = LocateVex(G, v2);
        p1 = (ArcNode*)malloc(sizeof(ArcNode));   //给邻接表指针分配空间
        p1->adjvex = j;                          //赋值给p->adjvex指向的顶点域
        p1->nextarc = G->vertices[i].firstarc; //nextarc指针域指向i结点的firstarc指针域  
        G->vertices[i].firstarc = p1;    //将点i的第一条指针指向
        indegree[j]++; // 计算每个点的入度
    }
}

int TopoSort(ALGraph G, int* topo)
{
    StackList S;//声明一个栈指针
    ArcNode* p;
    int index;
    int m = 0;//下标 用于存储拓扑序列
    S = NULL;
    for (int i = 0; i < G.vexnum; i++)
    {
        if (indegree[i] == 0) 
        {
            S = Push(S, i);
        }

    }
	// 这个栈没有头指针，所以当栈指针指向空时栈为空
    while (S)//栈不为空 就继续跑
    {
        S = Pop(S, &index);
        topo[m] = index;
        m++;
        //删边 index相邻的点的入度-1
        p = G.vertices[index].firstarc;
        while (p != NULL)
        {
            --indegree[p->adjvex];
            if (indegree[p->adjvex] == 0)
            {
                S = Push(S, p->adjvex);
            }
            p = p->nextarc;

        }

    }
    topo[m] = -1;//-1代表结尾
    //判断一下是否成环
    if (m < G.vexnum)
    {
        //成环
        return 0;
    }
    else
    {
        //不成环
        return 1;
    }
}

int main()
{
    ALGraph G;
    int topo[99] = { 0 };
    CreateUDG(&G);
    if (TopoSort(G,topo))
    {
        for (int i = 0; topo[i] != -1; i++)
        {
            printf("%c ", G.vertices[topo[i]].data);
        }
    }

    return 0;
}
/*
6 8

A B C D E F

A B
A C
A D
C B
C E
D E
F D
F E
*/

关键路径

AOE网：边表示活动的网，是⼀个带权的有向无环图，其中顶点表示事件（Event），弧表示活动，权表示活动持续的时间。

源点和汇点 ：将AOE网中入度为零的点称为源点，将出度为零的点称为汇点。

关键路径：完成工程的最短时间是从源点到汇点的最长路径的长度。路径长度最长的路径就叫做关键路径。用形象一点的例子来说就是，唐僧师傅四人去西天取经，孙悟空只要一个精斗云，但是唐僧需要14年。四人取得真经的关键是唐僧到达西天。所以唐僧走到西天所需的时间就是关键路径。

活动： 一个完整的流程， 可能由很多事件组成（ 在图中就是弧的权值 ）

事件： 瞬时间/刹那间 发生的一件事（ 在图中就是点 ）

ETV（Earliest Time Of Vertex) ：事件最早发生时间，就是顶点的最早发生时间

LTV（Latest Time Of Vertex)：事件最晚发生时间，就是每个顶点对应的事件最晚需要开始的时间，如果超出时间将会延误整个工期。

ETE(Earliest Time Of Edge)：活动的最早开工时间，就是弧的最早发生时间。

LTE(Lastest Time of Edge)：活动的最晚开工时间，就是不推迟工期的最晚开工时间。

画图演示过程

代码实现

#include <stdio.h>
#include <stdlib.h> 
#define OK 1
#define ERROR 0
#define MVNum 100
typedef int Status;
typedef char VerTexType;
typedef char OtherInfo;
int indegree[MVNum] = { 0 };//结点的入度个数
int m;//************逆序拓扑用(局部变量变全局） 
//创建栈 
typedef struct StackNode {
    int data;
    struct StackNode* next;
}StackNode, * StackList;
//出栈函数 
StackList Pop(StackList S, int* e)
{
    StackList p;
    p = S;
    if (!p)
        return ERROR;
    *e = p->data;
    S = S->next;
    free(p);
    return S;
}
//入栈函数： 
StackList Push(StackList S, int e)
{
    StackList p;
    p = (StackNode*)malloc(sizeof(StackNode));
    p->data = e;
    p->next = S;
    S = p;
    return S;
}

//邻接表创建有向图的实现
//边结点 
typedef struct ArcNode {    //链表结点
    int adjvex;           //邻接表创建无向网的实现
    struct ArcNode* nextarc;    //指向下一条边的指针
    int info;       //*****和边相关的信息--权值*****
}ArcNode;

//顶点信息 
typedef struct VNode {   //头结点
    VerTexType data;   //顶点信息
    ArcNode* firstarc;//指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];//AdjList 表示邻接表类型

typedef struct {
    AdjList vertices;     //邻接表头结点数组
    int vexnum, arcnum;   //图的顶点数和弧数
}ALGraph;

//创建有向图：
int LocateVex(ALGraph* G, VerTexType v)  //G带操作的图；v要在图中定位的顶点
{
    int i;
    for (i = 0; i < (G->vexnum); i++)
    {
        if (v == G->vertices[i].data)
            return i;               //顶点存在则返回在头结点数组中的下标；否则返回
    }
}

void CreateUDG(ALGraph* G)
{
    int i, j, k;
    VerTexType v1, v2;
    ArcNode* p1;
    int w;//*****权值***** 
    printf("输入总节点数和弧数：\n"); //G带操作的图；v要在图中定位的顶点
    scanf("%d %d", &G->vexnum, &G->arcnum);
    fflush(stdin);    //是清空输入缓冲区的
    printf("输入各个节点的值：\n");
    for (i = 0; i < G->vexnum; i++)   //邻接表初始化

    {
        scanf("%c", &G->vertices[i].data);
        getchar();
        G->vertices[i].firstarc = NULL;
    }
    printf("输入各条边的数据：\n");//*********
    fflush(stdin);   //*********是清空输入缓冲区的
    for (k = 0; k < G->arcnum; k++)
    {

        scanf("%c", &v1);
        getchar();
        scanf("%c", &v2);
        getchar();
        scanf("%d", &w);//**********
        getchar();//************
        i = LocateVex(G, v1);   //返回这两个顶点在顶点数组中的位置
        j = LocateVex(G, v2);
        p1 = (ArcNode*)malloc(sizeof(ArcNode));   //给邻接表指针分配空间
        p1->adjvex = j;   
        p1->info=w;                       //赋值给p->adjvex指向的顶点域
        p1->nextarc = G->vertices[i].firstarc; //nextarc指针域指向i结点的firstarc指针域  
        G->vertices[i].firstarc = p1;    //将点i的第一条指针指向
        indegree[j]++;
    }
}

int TopoSort(ALGraph G, int* etv,int* topo)
{
    StackList S;//声明一个栈指针
    ArcNode* p;
    int index;
    m = 0;//***********下标 用于存储拓扑序列
    S = NULL;

    for (int i = 0; i < G.vexnum; i++)
    {
        etv[i]=0;//*********初始化etv数组 
    }

    for (int i = 0; i < G.vexnum; i++)
    {
        if (indegree[i] == 0) 
        {
            S = Push(S, i);
        }

    }
    int k;//******下面循环中 index的邻接点 
    while (S)//栈不为空 就继续跑
    {
        S = Pop(S, &index);
        topo[m] = index;
        m++;
        //删边 index相邻的点的入度-1
        p = G.vertices[index].firstarc;
        while (p != NULL)
        {
            k=p->adjvex;//********
            --indegree[k];//********
            if (indegree[k] == 0)//********
            {
                S = Push(S, k);//********
            }
            //********求顶点K最早发生时间
            if(etv[index]+(p->info)>etv[k])
            {
                etv[k]=etv[index]+(p->info);
            } 

            p = p->nextarc;

        }

    }
    topo[m] = -1;//-1代表结尾
    //判断一下是否成环
    if (m < G.vexnum)
    {
        //成环
        return 0;
    }
    else
    {
        //不成环
        return 1;
    }
}
//求关键路径 
void CriticalPath(ALGraph G, int* etv, int* ltv)
{
    int topo[99] = { 0 };
    ArcNode* p;
    int ete, lte;//此处其实没必要用数组
    if(TopoSort(G,etv,topo))
    {
        //初始化事件最晚发生时间
        int x=topo[m-1];//x是拓扑序列的终点，也是图汇点 
        for(int i=0;i<G.vexnum;i++)
        {
            ltv[i]=etv[x];
        } 
        //逆拓扑 求事件最晚发生时间
        while(m!=0)
        {
            m--;
            int gettop=topo[m];
            for (p = G.vertices[gettop].firstarc;p;p = p->nextarc)
            {
                int k = p->adjvex;
                if (ltv[k] - p->info < ltv[gettop])
                {
                    ltv[gettop] = ltv[k] - p->info;
                }
            }

        }
        //求活动的最早和最晚,顺便输出关键路径，通过点遍历所有的边，时间复杂度O（E） 
        printf("以下是关键路径：\n");
        for (int i = 0; i < G.vexnum; i++)
        {
            for (p = G.vertices[i].firstarc; p; p = p->nextarc)
            {
                int k = p->adjvex;
                ete = etv[i];
                lte = ltv[k] - p->info;
                if (ete == lte)//输出关键路径的边 
                {
                    printf("%c %c : %d\n", G.vertices[i].data, G.vertices[k].data, p->info);
                }
            }
        }

    } 

}
int main()
{
    ALGraph G;
    CreateUDG(&G);
    int* ltv = (int*)malloc(G.vexnum * sizeof(int));
    int * etv = (int*)malloc(G.vexnum * sizeof(int));
    CriticalPath(G, etv, ltv);

    return 0;
}
/*
9 11
A B C D E F G H I
A B 6
A C 4
A D 5
B E 1
C E 1
D F 2
E G 9
E H 7
F H 4
G I 2
H I 4
*/

排序

就地排序：⼀个就地排序算法使用恒定的的额外空间来产生输出（仅修改给定的数组），它仅通过修改线性 表中元素的顺序来对线性表进行排序。例如，插入排序（Insertion Sort）和选择排序（Selection Sort）是就地排序算法，因为它们不使用任何额外的空间来对线性表进行排序。

内部排序：当所有待排序记录可以⼀次载入内存时，则称为内部排序。

外部排序：当所有待排序记录不能被⼀次载入内存进行处理时，这样的排序就被称为外部排序。

稳定排序：如果两个具有相等关键字的对象在排序前后的相对位置没有发生变化，则认为排序算法是稳定的（ 简单点来说就是数组中存在相同元素，当进行排序时相同的元素相对位置不会发生改变 ）当我们对可能存在重复键的键值对（例如，人名作为键，其详细信息作为值）按照键对这些对象进行排序时，稳定性就显得至关重要。

插入排序

直接插入排序

​ 将待排序序列分成两个序列，前面的序列保持有序，依次选取后面的序列的元素，在前面的序列中进行插入。初始时，有序序列的长度为1。

• 时间复杂度为O(n^2^)
• 空间复杂度为O(1)
• 是一个稳定排序

画图演示过程

代码实现

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
int a[maxx],n;
int main()
{

    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);    
    }

    for(int i=1;i<n;i++)//从第2个数开始，取出当前数作为待排序数
    {
        int k,temp=a[i];
        for(k=i;k>=0;k--)   
        {
            if(a[i]>a[k])//找到小的数代表结束 
                break;
        }
        for(int c=i;c>k+1;c--)//大的数都往后面移动一位ie 
        {
            a[c]=a[c-1];
        }
        a[k+1]=temp;//将a[i]放入正确的位置 
    }


    for(int i=0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}
//--------------------------------------------------------------------
// 上面的直接插入有点蠢 但是是最能体现插入算法的
#include<stdio.h>
#include<stdlib.h>
#define maxx 100
int n;//元素个数
int a[maxx];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    //改良后的直接插入排序 

    for(int i=2;i<=n;i++)
    {
        int t=a[i];// t作为哨兵，也可以用a[0]最为哨兵，这样做的话就不能再a[0]中存放数据
        // a[0] = a[i];
        int j; 
        for(j=i;j>1;j--) 
        {
            if(t<a[j-1])
            {
                a[j]=a[j-1];
            }
            else {
                break;
            }

        }
        a[j]=t;
        // a[j]=a[0]
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }

    return 0;
}

折半插入排序

​ 折半插入排序和直接插入排序的唯一差别就是再寻找插入位置时使用了折半查找，加快了位置的寻找，实在优化直接插入排序背景下的进一步优化。

• 时间复杂度为O(n^2^)
• 空间复杂度为O(1)
• 是一个稳定排序

代码实现

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
int n;//元素个数
int a[maxx];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    for(int i=2;i<=n;i++)
    {
        int t=a[i];
        int left = 1;
        int right = i - 1;
        while(left<=right)
        {
            int mid = (left+right)/2;
            if(a[mid]>t)
                right = mid-1;
            else
                left = mid+1;
        }
        for(int j = i-1; j >= right+1; j--)
            a[j+1]=a[j]; 
        a[right+1]=t;
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }

    return 0;
}

希尔排序

​ 希尔排序也是⼀种插⼊排序，它是简单插入排序经过改进之后的⼀个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2^）的第⼀批算法之一。

​ 希尔排序的进行是先确定一个增量，下面画图中采用的是最常见的一种增量选择——首次为数组的长度的一半，后续增量都是前一次排序的一半（ 向下取整 ）。增量的作用是进行分组，如增量为5，数组长度为11，则下标为0、5、10为一组进行排序，其他的元素同理。

• 时间复杂度最好情况为O(n)，最坏情况为O(n^2^)
• 空间复杂度为O(1)
• 是一个不稳定排序

画图演示过程

代码实现

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
int n;//元素个数
int a[maxx];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int k=0;//趟数 
    //希尔排序 
    for(int d=n/2;d>0;d/=2)
    { 
        k++; 
        for(int i=1+d;i<=n;i++)
        {
            int t=a[i];
            int j; 
            for(j=i;j>=d;j-=d) // 组内排序
            {
                if(t<a[j-d])
                {
                    a[j]=a[j-d];
                }
                else
                {
                    break;
                }

            }
            a[j]=t;
        }
        printf("第%d趟，增量为%d ：",k,d); 
        for(int i=1;i<=n;i++)
        {
            printf("%d ",a[i]);
        }
        printf("\n");		
    } 
    return 0;
}
/*
10
9 13 8 2 5 13 7 1 15 11
*/

交换排序

冒泡排序

​ 交换排序中最经典的就是冒泡排序，这个一般来说接触的最早的排序的算法。过于经典不多做解释，直接给出代码。

• 时间复杂度最好情况为O(n)，最坏情况为O(n^2^)
• 空间复杂度为O(1)
• 是一个稳定排序

代码实现

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
/*所谓交换,是指根据序列中两个关键字比较的结果来对换这两个关键字在序列中的位置。*/
int a[maxx],n,t;
int v;//标记 

int main()
{

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    //冒泡排序
    //外层循环控制 排序的趟数 n个元素排序需要循环n-1次 【1】
    for(int i=1;i<=n-1;i++) 
    {
        v=0;
        //内层循环控制比较的次数 n个元素第i趟比较n-i次 【2】
        for(int j=1;j<n-i+1;j++) 
        {
            //比较相邻的元素大小 目的：将最大的元素选出到移动到最后 
            if(a[j]>a[j+1])
            {
                v=1;
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
        if(v==0)//v仍然等0，说明没交换，说明完全有序 
        {
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

快速排序

​ 快速排序首先选⼀个基准（你也可以认为是要放到排序后数组正确位置的元素） pivot，然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有很多种，所以快速排序具有很多版本。

总是选择第⼀个元素作为基准 pivot；（以这个举例） 总是选择最后⼀个元素作为基准； 随机的选择⼀个元素作为基准； 选择最中间的元素作为基准；

​ 快速排序的关键是划分 partion() 。每⼀趟划分，我们就可以将作为 pivot 的值 x 放到排序数组的正确位置，并且将所有比 x 小的放到 x 的左边，所有比 x 大的元素放到 x 的右边。而且划分操作的时间复杂度是线性的奥，即O（n）量级！

​ 快速排序是双指针的一种应用，其实不用特意去判断到底左右指针那根要动，两根指针是前后交替进行移动的。

• 时间复杂度最好情况为O(nlogn)，最坏情况为O(n^2^)，平均复杂度O(nlogn)
• 空间复杂度为O (logn)
• 是一个不稳定排序

画图演示过程

​ 由于快速排序的操作过多，这里只演示一次根据基准数的排序。

代码实现

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
//快速排序：是就地排序,是不稳定的排序 时间复杂度O（nlogn） 
//选取第一个元素做基准数 
void Quick_Sort1(int a[], int l, int r) 
{
    if (l < r) {
        int i, j, x;
        i = l;
        j = r;
        x = a[i];
        while(i<j) {
            while (i<j && a[j]>x) {
                j--; // 从右向左找第一个小于x的数
            }
            if (i < j) {
                a[i++] = a[j]; // 将小于x的值放在左边
            }
            while (i < j && a[i] < x) {
                i++; // 从左向右找第一个大于x的数
            }
            if (i < j) {
                a[j--] = a[i]; // 将大于x的值放在右边
            }
        }
        a[i] = x;
        Quick_Sort1(a, l, i - 1);
        Quick_Sort1(a, i+1, r);
    }
}
//选取中间的元素做基准数 
void Quick_Sort2(int a[], int l, int r) 
{
    int i=l;
    int j=r;
    int mid=a[(l+r+1)/2];

    while(i<=j)//必须带等号，避免死循环，
    {
        while(a[i]<mid)i++;
        while(a[j]>mid)j--;
        if(i<=j) 
        {
            int t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;
            j--;
        }
    }
    if(l<j)Quick_Sort2(a,l,j);
    if(i<r)Quick_Sort2(a,i,r);

}

int main()
{
    int n;//元素个数
    int a[maxx];
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    Quick_Sort1(a,1,n); 

    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }

    return 0;
}

选择排序

简单的选择排序

​ 简单选择排序就是重复遍历数组找出最小的值，然后进行交换从而实现排序，由于实现简单，有之前排序的铺垫理解也简单。同样不再画图。

• 时间复杂度为O(n^2^)
• 空间复杂度为O(1)
• 是一个不稳定排序

代码实现

#include<stdio.h>
#include<stdlib.h>
#define maxx 100

int a[maxx],n,t;
int minn; 

int main()
{
    int minn;//最小元素的下标 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    //简单选择排序:就地排序， 时间复杂度O(n^2) ,不稳定的排序 
    //简单选择排序:进行n-1趟排序，每次都在乱序区中选择一个最小的元素，放在乱序的第一个位置，此时有序区+1，乱序区-1 
    for(int i=1;i<=n-1;i++)//控制循环趟数
    {
        minn=i; 
        for(int j=i+1;j<=n;j++)//控制乱序区，去找最小的元素的位置
        {
            if(a[j]<a[minn])
            {
                minn=j;
            }
        }
        //把minn位置的元素放在乱序区的第一个位置，即i位置
        if(minn!=i)
        {
            int t=a[i];
            a[i]=a[minn];
            a[minn]=t; 
        }

    } 

    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}

堆排序

堆（Heap）是⼀类基于完全⼆叉树的特殊数据结构。通常将堆分为两种类型：

1. 大顶堆（Max Heap）：在大顶堆中，根结点的值必须大于他的孩子结点的值，对于二叉树 中所有子树都满足此规律
2. 小顶堆（Min Heap）：在小顶堆中，根结点的值必须小于他的孩子结点的值，对于二叉树 中所有子树都满足此规律

二叉堆是满足下面属性的一颗二叉树：

1. 二叉堆必定是一颗完全二叉树。二叉堆的此属性也决定了他们适合存储在数组当中。
2. 二叉堆要么是小顶堆，要么是大顶堆。小顶二叉堆中的根结点的值是整棵树中的最小值，而且二叉树中的所有顶点及其子树均满足这⼀特性。大顶堆与小顶堆类似，大顶堆的根结点的值是整棵树中的最大值，而且二叉树中所有结点的值也均大于等于其子树结点。

• 时间复杂度为O(nlogn)
• 空间复杂度为O(1)
• 是一个不稳定排序

二叉堆的存储结构

​ ⼆叉堆是⼀颗完全⼆叉树，⼀般用数组表示。其中根元素用 arr[0] 表示，而其他结点（第 i个结点的存储位置）满足下表中的特性：

数组表示	含义
arr[(i-1)/2]	第 i 个结点的父结点
arr[2*i + 1]	第 i 个结点的左孩子结点
arr[2*i + 2]	第 i 个结点的右孩子结点

代码实现

#include<stdio.h>
#include<stdlib.h>
#define maxx 100

/*升序排列 
选择排序：基于选择的排序。 ---每次从乱序区选择一个最小的排列（输出） 
   堆排序:就地排序，不稳定 ，时间复杂度O(nlogn) 
   n个元素，保存在a数组中，直接在a数组中
1.初始化成一个小顶堆：
  下标最大的内部节点的下标是几？最后一个内部节点的下标是几？
        n/2
（1）找到最后一个内部节点（n/2）,依次调整每棵子树
        调整过程：依次向下比较调整：若该节点比左右孩子节点中的最小值大，进行交换，直到不满足该条件位置
2.在小顶堆的基础上，进行堆排序
   循环n-1次：
  （1）输出（删除）根节点；
   （2）最后一个位置的节点代替根节点
（3）向下调整
---输入最后一个元素
3.堆中插入一个元素：
（1）把元素放到数组最后
（2）向上和父亲节点比较进行调整

 */
void downAdjust(int a[],int i,int m)//对以 下标i的元素 为根节点的子树进行向下调整 
{//now是当前调整的节点，next是now的孩子，也是下一次要调整的节点 
    int now=i;
    int next;
    int t;
    while(now*2<=m)
    {
        next=now*2;//now的左孩子
        if(next+1<=m&&a[next+1]<a[next])
        {
            next=next+1;//now的右孩子 
        }
        if(a[now]<=a[next])
        {
            break;
        } 
        else{
            t=a[now];
            a[now]=a[next];
            a[next]=t;
            now=next;
        }
    } 

}
void upAdjust(int a[],int n)
{//now是当前调整的节点，next是now的父亲，也是下一次要调整的节点
    int now=n;
    int next; 
    int t;
    while(now>1)
    {
        next=now/2;// now的父亲
        if(a[next]<=a[now])//父亲节点比当前节点大 
        {
            break;
        }
        else
        {
            t=a[now];
            a[now]=a[next];
            a[next]=t;
            now=next;
        }
    } 

} 

int main()
{
    int n;//元素个数
    int a[maxx];// 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    //把a数组初始化成小顶堆
    for(int i=n/2;i>=1;i--)
    {
        downAdjust(a,i,n);
    } 
    //堆排序
    int m=n;
    int t;
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[1]);
        t=a[1];
        a[1]=a[m];
        a[m]=t;
        m--;
        downAdjust(a,1,m);
    } 
    printf("\n");
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    //在堆中插入一个元素；
    n++;
    scanf("%d",&a[n]);
    upAdjust(a,n);

    return 0;
}

归并排序

​ 归并排序采用了分治的思想。所谓分支就是分而治之的意思。所有采用归并排序时首先要将数组分开来。每次分开是数组数量除以2。

​ 不断的进行分裂，直到数组的元素数量只有一个。接着就是归并的过程，之前如何分裂的现在就是如何合并的。要注意的是在合并的时候要进行排序。在合并的时候我们只要两个指针，分别指向要合并的两个数组的首元素，然后进行比较，由于带合并数组是有序的，所以只需要比较指针所指向的大小即可。

• 时间复杂度为O(nlogn)
• 空间复杂度为O(n)
• 是一个稳定排序

画图演示过程

代码实现

#include<stdio.h>
#include<stdlib.h>
#define maxx 100
void merge(int a[],int l,int mid,int r)
{
    //l~mid
    //mid+1~r
    int t[maxx];
    int k=0;//t数组的下标 
    int i=l;
    int j=mid+1;
    while(i<=mid&&j<=r)// 比较两元素的大小
    {
        if(a[i]<a[j])
        {
            t[k]=a[i]; 
            k++;
            i++;
        }
        else{
            t[k]=a[j];
            k++;
            j++;
        }
    }
    while(i<=mid)// mid前元素剩余
    {
        t[k]=a[i]; 
        k++;
        i++;
    }
    while(j<=r)// mid后元素剩余
    {
        t[k]=a[j]; 
        k++;
        j++;
    }
    for(int i=0;i<k;i++)// 复制辅助数组到原数组中
    {
        a[l+i]=t[i];
    }

}

void merge_sort(int a[],int l,int r)
{
    int mid;
    if(l<r)
    {
        mid=(l+r)/2;
        //l~mid
        merge_sort(a,l,mid);
        //mid+1~r
        merge_sort(a,mid+1,r);
        merge(a,l,mid,r);
    }

}
int main()
{
    int n;//元素个数
    int a[maxx];// 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    merge_sort(a,1,n);

    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");


    return 0;
}

统计排序

计数排序

​ 计数排序是创建一个排序数组中最大值+1，然后统计排序数组中每个元素的出现顺序，接着在根据每个元素出现的顺序进行输出。

• 时间复杂度为O(n+m)
• 空间复杂度为O(n+m)
• 是一个稳定排序

画图演示过程

桶排序

​ 桶排序是合理的创建几个桶，然后将待排数据根据数据量存放入桶中并进行排序。（ 桶中排序可以使用任意方法进行 ）然后输出桶中元素即可。

• 时间复杂度为O(n)
• 空间复杂度为O(m)
• 是一个稳定排序

画图演示过程

基数排序

​ 基数排序是将所有的数的位数都补充到集合中的最大数的位数，接着从最高位开始对每一位进行排序。

• 时间复杂度为O(n * k)
• 空间复杂度为O(n + k)
• 是一个稳定排序

画图演示过程

排序总览

查找

顺序查找

​ 顺序查找就是从线性表中从头到尾进行遍历，若是找到则返回值。

代码实现

typedef struct{
    ElemType *elem; // 存放查找表中数据元素的数组
    int length; // 记录查找表中数据的总数量
}SSTable;
// 初始化查找表
SSTable *initTable(int length) {
    SSTable *table = (SSTable *)malloc(sizeof(SSTable));
    table->length = length;
    table->elem = (ElemType *)malloc(sizeof(ElemType) * (length + 1));
    memset(table->elem, 0, sizeof(ElemType) * (length + 1));
    return table;
}
//查找表查找的功能函数，其中key为关键字
int search_seq(SSTable *st, keyType key){
    // 将关键字作为⼀个数据元素存放到查找表的第⼀个位置，起监视哨的作⽤
    st->elem[0].key = key;
    int i = st->length;
    // 从查找表的最后⼀个数据元素依次遍历，⼀直遍历到数组下标为0
    while (st->elem[i].key!=key) {
    	i--;
    }
    // 如果 i=0，说明查找失败；反之，返回的是含有关键字key的数据元素在查找表中的位置
    return i;
}

折半查找

​ 折半查找，也称二分查找，在某些情况下相比于顺序查找，使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。

画图演示过程

代码演示过程

#include <stdio.h>
int main() {	
	int nums[8] = {3,6,9,24,25,45,67,89};
	int target = 30;
    int left = 0, right = 7,mid = 0; // 闭区间 [left, right]
    while (left <= right) { 
        // 循环不变量：
        // nums[left-1] < target
        // nums[right+1] >= target
        mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1; // 范围缩小到 [mid+1, right]
        } else {
            right = mid - 1; // 范围缩小到 [left, mid-1]
        }
    }
    if(nums[mid] == target)
    	printf("这个数下标为%d",mid);
    else
    	printf("没有这个数");
    return 0;
}

红黑树

​ 红黑树可以说是整本数据结构中最为复杂的结构，同时也是408统考中最新增加的内容之一。

红黑树的定义

1. 每一个结点都有一个颜色，要么是红色，要么是黑色。
2. 树的根结点为黑色
3. 树中不存在两个相邻的红色节点（红色节点的父结点和孩子结点均不为黑色）
4. 从任意⼀个结点出发，包括根结点，到其任何后代NULL结点（默认都是黑色啊）的每条路径都具有相同数量的黑色结点。

记住这些定义有一个常用的口诀( 这个口诀很重要 )

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

• 结论1： 从根节点到叶子节点的最长路径不大于（<=） 最短路径的2倍 最短路径长度： bh 最长路径： h h<=2bh ===> h/2<=bh;
• 结论2： 有n个内部结点的红黑树的高度 h<=2log(n+1); 红黑树操作时间复杂度都O(logn)

红黑树的插入

​ 首先需要清楚的是插入节点一定是红色的，红黑树插入有三种情况。

根节点

​ 若插入的是根节点，那就直接让根节点变黑即可。

叔叔节点为红色时

​ 若插入节点的叔叔是红色节点，那么要先将插入节点的叔父爷进行变色，再将爷爷节点变为插入节点继续进行判断红黑树是否失衡。

叔叔节点为黑色时

​ 若插入节点的叔叔节点为黑色时，那要先判断是四种旋转的哪一种。旋转后要改变旋转点和被旋转点的颜色。（ LL型和RR型是父亲节点和爷爷节点变色，LR型和RL型是插入节点和爷爷节点变色 ）

红黑树的构建画图演示

红黑树的删除

​ 红黑树的删除操作是红黑树中最为复杂的一步。其中分成了很多的情况。由于红黑树是二叉平衡树的扩张，所以二叉平衡树的删除在红黑树这里仍然适用。简单来说，红黑树的节点删除分为三种情况，有两个孩子、一个孩子和没有孩子。有两个孩子转化为只有一个孩子或是没有孩子的情况（ 即用右子树的最小值来代替或是用左子树的最大值来代替，需要注意的是代替仅仅是值代替，颜色不用代替）。

只有一个孩子

​ 若删除节点只有一个孩子，那么只有可能是黑+红的组合（ 红为黑的子节点，不能调换位置 ），其他情况都不可能存在。由于黑路同的性质，所以只需要用红孩子代替删除节点，并变色即可完成删除。

没有孩子的红色节点

​ 若删除的节点是没有孩子的红色节点，那么节点将这个红色节点删除即可。

没有孩子的黑色节点，兄弟是黑色且至少有一个红孩

​ 若删除节点没有孩子的黑色节点，它兄弟是黑色且至少有一个红孩。那么就要先进行变色+旋转处理。这里变色的情况不同。LL型和RR型变色时是下图中son变sibling、sibling变parent、parent变成黑色。LR型和RL型是直接son变parent、parent变黑即可。

没有孩子的黑色节点，兄弟是黑色且孩子都是黑色

​ 若删除节点是没有孩子的黑色节点且它的兄弟节点是黑色，孩子也都为黑色。那么就是将兄弟变红，并将双黑节点上移。

• 第一种情况，若双黑节点上移遇到根节点，那么就直接将双黑节点变成单黑节点即可。
• 第二种情况，若双黑节点上移遇到红节点，那么就直接将双黑节点变成单黑即可。
• 第三种情况，双黑节点上移遇到黑色节点，那么就继续为这个黑色节点为双黑节点进行调整。

没有孩子的黑色节点，兄弟是红色

​ 若删除节点是没有孩子的黑色节点且它的兄弟节点是红色，将删除节点的兄父变色，让父亲节点向双黑节点旋转，将双黑节点上移并进一步的进行判断。

红黑树删除画图演示

红黑树代码

​ 408不做要求，兴趣研究（ 代码量在400行左右 ）。

#include<stdio.h>
#include<stdlib.h>
#define RED 0//红色结点
#define BLACK 1//黑色结点

typedef struct RBTreeNode{
    int data;
    int color;
    struct RBTreeNode* l;
    struct RBTreeNode* r;
    struct RBTreeNode* parent;
}Node,*RBTree;



Node* creatRoot(int key)
{
    Node* root=(Node*)malloc(sizeof(Node));
    root->data =key;
    root->color =BLACK;
    root->parent=root->l =root->r =NULL;
    return root;
}
Node* craetNode(int key,Node* parent,Node*left,Node* right) 
{
    Node* n=(Node*)malloc(sizeof(Node));
    n->data =key;
    n->color=RED;
    n->parent =parent;
    n->l =left;
    n->r =right;
    return n;
}
//以 红黑树的 x结点为中心左旋
Node* left_rotate(RBTree root,Node* x)
{
    //y指向x的右孩子 
    Node* y=x->r ;
    //将y的左孩子变成x的右孩子,
    x->r =y->l ; 
    //如果y->l非空，x变成y->l的父亲 
    if(y->l !=NULL)
    {
        y->l->parent =x;
    } 

    //处理y和x-》parent的关系	
    y->parent =x->parent;
    if(x->parent ==NULL)
    {
        root=y;
    } 
    else{
        if(x==x->parent->l )
        {
            x->parent->l=y;
        } 
        else{
            x->parent->r=y;
        }

    }
    y->l =x;
    x->parent =y;
    return root;	  
} 
//以 红黑树的 x结点为中心右旋
Node* right_rotate(RBTree root,Node* x)
{
    //y指向x的左孩子 
    Node* y=x->l ;
    //将y的右孩子变成x的左孩子,
    x->l =y->r ; 
    //如果y->r非空，x变成y->r的父亲 
    if(y->r !=NULL)
    {
        y->r->parent =x;
    } 

    //处理y和x-》parent的关系	
    y->parent =x->parent;
    if(x->parent ==NULL)
    {
        root=y;
    } 
    else{
        if(x==x->parent->l )
        {
            x->parent->l=y;
        } 
        else{
            x->parent->r=y;
        }

    }
    y->r =x;
    x->parent =y;
    return root;
} 

Node* fixup(RBTree root,Node* node)
{
    Node* parent;
    Node* gparent;//爷爷
    Node* uncle;
    parent=node->parent;
    while(parent!=NULL&&parent->color ==RED)
    {//父亲红，爷爷黑色

        gparent=parent->parent;
        //父亲结点是爷爷结点的右孩子（RR/RL）
        if(parent==gparent->r)
        {
            uncle=gparent->l;
            //1.叔叔是红色
            if(uncle!=NULL&&uncle->color ==RED)
            {
                uncle->color=BLACK;
                parent->color =BLACK;
                gparent->color =RED;
                node=gparent;
                parent=node->parent;
                continue;
            }
            //叔叔是黑色的->RR,RL
            else{
                if(node==parent->l) 
                {
                    //RL
                    root=right_rotate(root,parent);
                    Node* t;
                    t=node;
                    node=parent;
                    parent=t; 
                }
                //RR;
                parent->color =BLACK;
                gparent->color =RED;
                root=left_rotate(root,gparent);
            }			
        } 
        //父亲结点是爷爷结点的左孩子（LL/LR）
        if(parent==gparent->l)
        {
            uncle=gparent->r;
            //1.叔叔是红色
            if(uncle!=NULL&&uncle->color==RED)
            {
                uncle->color=BLACK;
                parent->color =BLACK;
                gparent->color =RED;
                node=gparent;
                parent=node->parent;
                continue;
            }
            //叔叔是黑色的->LR,LL
            else{
                if(node==parent->r) 
                {
                    //LR
                    root=left_rotate(root,parent);
                    Node* t;
                    t=node;
                    node=parent;
                    parent=t;
                }
                //LL;
                parent->color =BLACK;
                gparent->color =RED;
                root=right_rotate(root,gparent);
            }			
        }

    } 
    //重新给根节点变黑色 
    root->color=BLACK;
    return root;	
}


RBTree insert(RBTree root,int key)
{
    //判断树是否为空
    if(root==NULL)
    {
        root=creatRoot(key);

        return root ;
    } 

    Node* x=root;//遍历找key插入的位置 
    Node* xp=NULL;//x的父亲 
    //根据BST找插入的位置
    while(x!=NULL)
    {
        xp=x;
        if(key<x->data )
        {
            x=x->l;
        }
        else{
            x=x->r;
        }
    } 
    Node* n=craetNode(key,xp,NULL,NULL);

    if(key<xp->data )
    {
        xp->l =n;
    } 
    else{
        xp->r =n;
    }
    root=fixup(root,n); 
    return root;
}
//////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////
//删除：在根为root的红黑树中，删除值为key的节点
Node* search(RBTree root,int key)
{  
    if(root==NULL||root->data ==key)
    {
        return root;
    }
    if(key<root->data )
    {
        return search(root->l ,key);
    }
    else{
        return search(root->r ,key);
    }	
}

//删除后调整：
RBTree delete_fixup(RBTree root,Node* x,Node* parent)
{
    Node* bro;//x的兄弟 
    while(((x!=NULL&&x->color==BLACK)||x==NULL)&&x!=root)
    {
        if(x==parent->r )//2.1
        {	   	
            bro=parent->l;
            //(c)bro是红色，转化成黑色
            if(bro->color==RED)
            {
                bro->color=BLACK;
                parent->color=RED;
                root=right_rotate(root,parent);
                //旋转之后x的兄弟发生变化 
                bro=parent->l;
            } 
            //此时bro一定是黑色的，写（b）和（a） 
            //(b)bro是黑的，bro的两个孩子是黑的
            if((bro->l==NULL||(bro->l!=NULL&&bro->l->color==BLACK))&&(bro->r==NULL||(bro->r!=NULL&&bro->r->color==BLACK))) 
            {
                bro->color=RED;
                x=parent;
                parent=x->parent;	
            }
            else
            {//（a） 
                //(a.2)bro的左孩子为黑，右为红 
                if(bro->l==NULL||(bro->l!=NULL&&bro->l->color==BLACK))
                {
                    bro->color =RED;
                    bro->r->color =BLACK;
                    root=left_rotate(root,bro);
                    bro=parent->l;

                } 
                //(a.1)
                bro->color=parent->color;
                parent->color=BLACK;
                bro->l->color=BLACK;
                root=right_rotate(root,parent);
                break;
            }


        }
        else//2.2
        {
            bro=parent->r;
            //(c)bro是红色，转化成黑色
            if(bro->color==RED)
            {
                bro->color=BLACK;
                parent->color=RED;
                root=left_rotate(root,parent);
                //旋转之后x的兄弟发生变化 
                bro=parent->r;
            } 
            //此时bro一定是黑色的，写（b）和（a） 
            //(b)bro是黑的，bro的两个孩子是黑的

            if((bro->r==NULL||(bro->r!=NULL&&bro->r->color==BLACK))&&(bro->l==NULL||(bro->l!=NULL&&bro->l->color==BLACK))) 
            {
                bro->color=RED;
                x=parent;
                parent=x->parent;	
            }
            else
            {//（a） 
                //(a.2)
                if(bro->r==NULL||(bro->r !=NULL&&bro->r->color==BLACK))
                {
                    bro->color =RED;
                    bro->l->color =BLACK;
                    root=right_rotate(root,bro);
                    bro=parent->r;

                } 
                //(a.1)
                bro->color=parent->color;
                parent->color=BLACK;
                bro->r->color=BLACK;
                root=left_rotate(root,parent);
                break;
            }
        }	

    }
    /////////////////////////bug:上课时没有写返回以及赋值黑色，也就是少了331---336的代码 
    //x为红色，直接赋值为黑色 
    if(x!=NULL)
    {
        x->color=BLACK;
    }
    return root; 


} 

//在以root为根的树中，删除节点node
RBTree delete_rbtNode(RBTree root,Node* node)
{
    if(node->l!=NULL&&node->r!=NULL)
    {
        Node* replace=node->r;
        while(replace->l!=NULL)
        {
            replace=replace->l;
        } 
        node->data =replace->data;  
        node=replace;
    }
    //删除度为1/0的node
    Node* child;//Node的孩子
    Node* parent=node->parent;
    int ncolor=node->color;
    if(node->l!=NULL)
    {
        child=node->l; 
    }
    else{
        child=node->r; 
    }
    if(child!=NULL)
    {
        child->parent =parent;
    } 
    if(parent!=NULL)
    {
        if(node==parent->l )
        {
            parent->l =child;
        }
        else
        {
            parent->r =child;	
        }	
    } 
    else{
        root=child;
    }
    free(node);
    if(ncolor==BLACK)
    {
        root=delete_fixup(root,child,parent);
    } 
    return root;
} 


RBTree delete_rbtree(RBTree root,int key)
{
    Node* k=search(root,key);
    if(k!=NULL)
    {
        root=delete_rbtNode(root,k);
    }
    return root;

} 

//中序遍历输出 
void inorder(Node* tree)
{    

    if (tree != NULL)
    {
        inorder(tree->l); 

        printf("%d %d ", tree->data, tree->color);
        if(tree->parent!=NULL)
        {
            printf("%d\n", tree->parent->data);
        }
        else{
            printf("-1\n");
        }
        inorder(tree->r); 
    }
}

int main()
{
    int a[9] = { 10,40,30,60,90,70,20,50,80 };
    RBTree root=(Node*)malloc(sizeof(Node));
    root=NULL;
    for(int i=0;i<9;i++)
    {
        root=insert(root,a[i]);

    }

    inorder(root);
    printf("\n");
    root=delete_rbtree(root,30);
    inorder(root);
    printf("\n");
    root=delete_rbtree(root, 70);
    inorder(root);
    printf("\n");
    root=delete_rbtree(root, 60);
    inorder(root);
    printf("\n");
    root=delete_rbtree(root, 40);
    inorder(root);
    printf("\n");
    root=delete_rbtree(root, 80);
    inorder(root);
    printf("\n");

    return 0; 
}

B树

​ B树用于减少与硬盘的交互的次数。B树与AVL树和红黑树的最大差距就是AVL树和红黑树常常用来处理存放在内存中数据量比较少的数据，而B树常用于与数量大存放在硬盘中情况。

B树的特性

1. 所有的叶子结点都出现在同一层上，并且不带信息(可以看做是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。
2. 每个结点包含的关键字个数有上界和下界。用一个被称为 B-树的 最小度数 的固定整数 t >= 2来表示这些界 ，其中t取决于磁盘块的大小： 2.1、除根结点以外的每个结点必须至少有t - 1个关键字。因此，除了根结点以外的每个内部结点有 t 个孩⼦。如果树非空，根结点至少有一个关键字。 2.2、每个结点至多包含2t-1个关键字。
3. 一个包含x个关键字的结点有x + 1个孩子；
4. 一个结点中的所有关键字升序排列，两个关键字k1和k2之间的孩子结点的所有关键字 key 在(k1,k2)的范围之内。
5. 与二叉排序树不同， B-树的搜索是从根结点开始，根据结点的孩⼦树做多路分支选择，而二叉排序树做的是二路分支选择，每一次判断都会进行一次磁盘 I/O操作。
6. 与其他平很二叉树类似， B-树查找、插入和删除操作的时间复杂度为O(logn)量级。

简单来说B树要满足以下性质

• 平衡

  • 所有的叶节点

• 有序

  • 结点内有序
  • 任一元素的左子树都小于它，右子树都大于它

• 多路

  • 最多：m个分支,m -1个元素（ m阶B树 ）
  • 最少
    • 根节点：2个分支，1个元素
    • 其他节点：m/2（向上取整）个分支，m/2-1（向上取整）个元素

B树的插入

​ B树的插入需要注意这棵B树是几阶B树。若是元素数量超过阶数/2-1那么发生了上溢出，要进行分裂，分裂的途中要注意在分裂时，自己的子树也会一起被分裂出去。

B树的构建画图演示

B树的删除

​ B树和AVL树一样，若是删除有多个孩子的节点，则要将删除节点与其直接后继或是直接前驱进行交换，然后进行删除。下列兄弟不够借的情况中，由于出现合并操作，所以父节点也可能出现下溢出情况，要进行进一步的判断。

B树的删除画图演示

B树的代码

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define m 5//B树的阶设为5
#define M (m+1)/2-1//结点中关键字最少有M个 
typedef struct BTNode{
    int key[m+1];//从下标1位置开始存放 
    struct BTNode* ptr[m+1];//从下标0位置开始存放 
    int keynum;
    struct BTNode* parent;
}BTNode,*BTree;
//查找的结果集
typedef struct{
    BTNode* pt;//找到的结点
    int i;//在pt结点中的位置
    int flag;//1:key已经在B树中了，0：key不在B树中， 
}Result; 
void MegerBro(BTree& l,BTree& parent,BTree& r,BTree& t,int& i);
void Restore(BTree& t,BTree& p);

int find(BTNode* p,int k)
{//结点p中找第一个大于等于k的位置
    int i=1;
    while(i<=p->keynum&&k>p->key[i])
    {
        i++;
    }
    return i;
} 
//在B树中查找关键字K，并用r返回查找结果
Result SearchBTree(BTree t,int k)
{   
    Result r;
    int i;
    BTNode* p=t;//遍历节点的指针
    BTNode* q=NULL;//指向p的双亲结点 
    int tag=0;//是否找到k的标记 
    while(p!=NULL&&tag==0)
    {
        i=find(p,k);//在结点p中找第一个大于等于k的位置 
        if(i<=p->keynum&&k==p->key[i])
        {//k已经在B树中了 
            tag=1; 
        }
        else{//继续去p的第i-1个孩子中找 
            q=p;
            p=p->ptr[i-1]; 
        }

    } 
    if(tag==1)
    {//k已经在B树中了 
        r.pt=p;
        r.i=i;
        r.flag=1;
    } 
    else{
        //说明k不在B树中，p指向了外部结点，q指向p的父亲结点（也就是某个终端节点 
        r.pt =q;
        r.i=i;
        r.flag =0; 	
    }
    return r;
} 
//输出B树
void  printfBTree(BTree t, int tab)
{
    if(t==NULL)
    {
        return ;
    }
    int i;
    for(i=1;i<=tab;i++)
    {
        printf("	");
    }
    for(i=1;i<=t->keynum;i++)
    {
        printf("%d ",t->key[i]);
    }
    printf("\n");
    for(i=0;i<=t->keynum;i++)
    {
        printfBTree(t->ptr[i],tab+1);
    }
}

void newRoot(BTree& t,BTNode* p,int k,BTNode* ap)
{
    t=(BTree)malloc(sizeof(BTNode));
    t->key[1]=k;
    t->ptr[0]=p;
    if(p!=NULL)
    {
        p->parent=t;
    } 
    t->ptr[1]=ap;
    if(ap!=NULL)
    {
        ap->parent=t;
    } 
    t->keynum=1;
    t->parent=NULL;	
}
void Insert(BTree& q,int i,int x,BTNode* ap)
{
    int n=q->keynum;
    for(int j=n;j>=i;j--)
    {
        q->key[j+1]=q->key[j];
        q->ptr[j+1]=q->ptr[j];	
    }
    q->key [i]=x;
    q->ptr [i]=ap;
    if(ap!=NULL)
    {
        ap->parent=q;
    }
    q->keynum++;
}
void split(BTree& q,int s,BTree& ap)
{//把q结点从s位置分裂，分裂出一个新结点ap；
    int n=q->keynum;
    ap=(BTree)malloc(sizeof(BTNode));
    ap->ptr[0]=q->ptr[s];
    for(int i=s+1,j=1;i<=n;i++,j++)
    {
        ap->key[j]=q->key[i];
        ap->ptr[j]=q->ptr[i];
    }
    ap->keynum =n-s;
    ap->parent =q->parent;
    for(int i=0;i<=n-s;i++)
    {
        if(ap->ptr[i]!=NULL)
        {
            ap->ptr[i]->parent=ap;
        }
    }
    q->keynum=s-1;
} 
/*
在B树的q节点中的关键字数组的i位置插入k
同时在 q节点中的孩子节点指针数组的i位置插入ap 
*/
void InsertBTree(BTree& t,int k,BTNode* q,int i)
{
    int x;
    int needNewRoot=0;
    int finished=0; 
    BTNode* ap=NULL;
    if(q==NULL)
    {//空树中插入q，新建根节点 
        newRoot(t,NULL,k,NULL);
    }
    else
    {
        //往q结点中插入关键字x已经新的孩子ap 
        x=k;
        while(needNewRoot==0&&finished==0)
        {//执行插入
            Insert(q,i,x,ap);//往q结点中插入关键字x已经新的孩子ap 
            if(q->keynum<=m-1)
            {
                finished=1;
            }
            else{//需要分将q分裂 
                int s=(m+1)/2;//分裂位置
                //1~s-1位置的关键字留着q中，s+1~m-1位置的关键字放到新的结点中中
                // s位置的这个关键字插入到q的父亲中。
                split(q,s,ap);//分裂；
                x=q->key[s];
                if(q->parent !=NULL)
                {
                    q=q->parent;
                    i=find(q,x);
                }
                else
                {
                    needNewRoot=1;
                }

            }	
        }
        if(needNewRoot==1)
        {
            newRoot(t,q,x,ap);
        } 	
    }

}
void insertKeyOperation(BTree &t)
{//引用传递
    Result r;
    while(1)
    {
        int k;
        printf("输入想要插入的关键字：\n");
        scanf("%d",&k);
        r=SearchBTree(t,k);
        if(r.flag==1)
        {
            printf("B树中已经有%d了,无需插入\n",k);

        }
        else
        {
            InsertBTree(t,k,r.pt,r.i);//把k插入到r.pt节点的r.i位置。 
            printf("插入成功，此时B树结构如下：\n");
            printf("-------------------------------------------------------\n");
            printfBTree(t,1); 
            printf("-------------------------------------------------------\n");	
        }
        printf("是否要继续插入？y or n：\n");
        char c;
        getchar();
        scanf("%c",&c);
        if(c!='y')
        {
            break;
        } 
    } 

}
//////////////////////////////////////////////////////
//删除：
//3.找k的中序遍历后继
void  Successor(BTree& p,int i)
{
    BTree leaf=p->ptr[i];
    while(leaf->ptr[0]!=NULL)
    {
        leaf=leaf->ptr[0];
    }
    p->key[i]=leaf->key[1];
    p=leaf;

}
//4 在结点p中删除第i个位置的关键字，同时把第i个位置 的孩子也删掉 
void Remove(BTree& p,int i)
{
    int j;
    for(j=i;j<p->keynum;j++)
    {
        p->key[j]=p->key[j+1];
        p->ptr[j]=p->ptr [j+1];
    }
    p->keynum--;

}
//6.找兄弟借关键字
void  BorrowFromBro(BTree& p,BTree& lbro,BTree& rbro,BTree& parent,int i)
{
    if(lbro!=NULL&&lbro->keynum >M)//找左兄弟借 
    {
        //给新来的关键字和孩子腾位置
        for(int j=p->keynum+1;j>0;j--)
        {
            p->key[j]=p->key[j-1];
            p->ptr[j]=p->ptr[j-1];	
        } 
        //给p加一个关键字和孩子 
        p->key[1]=parent->key[i];
        p->ptr[0]=lbro->ptr[lbro->keynum];
        if(lbro->ptr[lbro->keynum]!=NULL)
        {
            lbro->ptr[lbro->keynum]->parent=p;
        }
        //维护p的父亲 
        parent->key[i]=lbro->key[lbro->keynum]; 

        //左兄弟关键字少一个，p的关键字多一个 
        lbro->keynum--;
        p->keynum++;

    } 
    else
    {//找右边兄弟借 
        p->key[p->keynum+1]=parent->key[i+1];
        p->ptr[p->keynum+1]=rbro->ptr[0];
        if(rbro->ptr[0]!=NULL)
        {
            rbro->ptr[0]->parent =p;
        } 
        p->keynum++;
        //维护父亲结点
        parent->key[i+1]=rbro->key[1]; 
        //维护右兄弟 
        for(int j=0;j<rbro->keynum;j++)
        {
            rbro->key[j]=rbro->key[j+1];
            rbro->ptr[j]=rbro->ptr[j+1];
        } 
        rbro->keynum--;
    } 

}
//7.合并函数，把靠右的结点r，合并到靠左的结点l中r的下标是i
void MegerBro(BTree& l,BTree& parent,BTree& r,BTree& t,int& i)
{
    //把父亲中第i个关键字和r结点中所有的关键字及孩子 放到 l结点中
    l->key[l->keynum+1]=parent->key[i];
    l->ptr[l->keynum+1]=r->ptr[0];
    if(r->ptr[0]!=NULL)
    {
        r->ptr[0]->parent=l;
    }
    l->keynum++;
    //r中剩下的 1---keynum关键字及孩子放到l中 
    for(int j=1;j<=r->keynum;j++)
    {
        l->keynum++;
        l->key[l->keynum]=r->key[j];
        l->ptr[l->keynum]=r->ptr[j];
        if(r->ptr[j]!=NULL)
        {
            r->ptr[j]->parent=l;
        } 
    } 
    //相当于父亲结点中删除了i位置的关键字及孩子 
    Remove(parent,i); 
    //对父亲结点进行调整
    if(parent->parent!=NULL&&parent->keynum<M)
    {
        Restore(t,parent);//5
    } 
    if(parent->parent==NULL&&parent->keynum<1)
    {
        t=l;
    } 
}
//5.调整函数
void Restore(BTree& t,BTree& p)
{
    BTNode* parent=p->parent;
    BTNode* Lbro=NULL;//p的左兄弟 
    BTNode* Rbro=NULL;//p的右兄弟
    //找左右兄弟---先找到p是其父亲的第i个孩子 ，左兄弟就是第i-1个孩子  右兄弟就是第i+1个孩子 
    int i;
    for(i=0;i<=parent->keynum;i++)
    {
        if(parent->ptr[i]==p)
        {
            break;
        }
    } 
    if(i>0)
    {
        Lbro=parent->ptr[i-1];
    }
    if(i<parent->keynum)
    {
        Rbro=parent->ptr[i+1];
    }

    //左兄弟或者右兄弟有没有多余的关键字，借给p
    if((Lbro!=NULL&&Lbro->keynum>M)||(Rbro!=NULL&&Rbro->keynum>M))
    {
        //6.借关键字
        BorrowFromBro(p,Lbro,Rbro,parent,i); 
    } 
    else
    {//如果左右兄弟都不够借，就合并一个兄弟 
        if(Lbro!=NULL)
        {//合并左兄弟，把p合并到左兄弟中 
            MegerBro(Lbro,parent,p,t,i); //7.合并函数，i是靠左的结点的下标 
        }
        else if(Rbro!=NULL)
        {//合并右兄弟，把右兄弟合并到p中 
            i++;
            MegerBro(p,parent,Rbro,t,i);
        } 

    } 
} 
//2在B树中删除节点p的第i个关键字
void  deleteBTree(BTree& t,BTree& p,int i)
{
    if(p->ptr[i]!=NULL)
    {//p的孩子节点不为空，p不是终端节点
        //要转化成在终端节点删除

        //找k的中序遍历后继k1
        Successor(p,i); 
        i=1;
    }
    //p是终端结点   k在i位置
    Remove(p,i);//4在结点p中删除第i个位置的关键字，同时把第i个位置 的孩子也删掉 

    //////调整
    if(p->parent==NULL&&p->keynum<1)
    {//p是根节点，关键字个数小于下限，树就是空树 
        t=NULL; 
    } 
    if(p->parent!=NULL&&p->keynum<M)
    {//p是非根节点，关键字个数小于下限 
        //进行调整 
        Restore(t,p);//5.调整B树（1.2）（1.3） 
    }

}
//1.删除函数 
void deleteKeyOperation(BTree& t)
{
    int k;
    while(1)
    {
        printf("请给出想要删除的关键字：\n");
        scanf("%d",&k);
        Result r=SearchBTree(t,k);

        if(r.flag==1)
        {
            //执行删除操作
            deleteBTree(t,r.pt,r.i);//2
            printf("删除成功，此时B树结构如下：\n");
            printf("-------------------------------------------------------\n");
            printfBTree(t,1); 
            printf("-------------------------------------------------------\n");	 

        }
        else
        {
            printf("想要删除的关键字k不在B树中\n");
            break;
        }
    } 

} 
//////////////////////////////////////////////////////// 

int main()
{
    BTree t=NULL;

    insertKeyOperation(t); 
    deleteKeyOperation(t); 
    return 0;
} 

/*
	9
		12 22
			5 8 9
			13 15
			25 29 35
		53
			41 50
			97	

*/  

B+树

B树和B+树的不同

1. B+树的元素个数最大和分支数是相同的（ B树的元素个数最大要比分支个数小一 ）。
2. 每个元素对应子节点的最大值（ 副本 ）
3. B树所有结点的关键字都有直接指向对应记录的指针，B+树叶结点包含全部关键字及指向相应记录的指针,非叶结点只作索引。

B+树的三种查找

1. 顺序查找：如下图所示，B+树相较于B树在叶子节点上多了一个类似于单链表的结构，这个结构帮助我们可以只对叶子节点进行顺序查找。
2. 随机查找：随机查找就是树型查找，目标树树从根节点出发寻找目标点。
3. 范围查找：最小值根据随机查找到叶子节点中目标值，然后再根据顺序查找到最大值，实现范围查找。

串

​ 串是由零个或者多个字符组成的有限序列。串中字符的个数称为串的长度，含有零个元素的串叫空串。在C语言中，可以用如下语句定义⼀个名为str的串。

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

暴力匹配

• 暴力匹配也称之为朴素模式匹配，其思想如下：

  • 以字符为单位，从左到右移动模式串，直到匹配成功为止。
  • 从左到右进行匹配，如果模式串中的第⼀个字符匹配成功，这继续往后进行匹配，如果匹配失败，则模式串从文本串的下⼀个字符进行匹配，⼀直重复。
  • 直到匹配成功或者匹配完所有的文本串为止。

• 朴素模式匹配算法的缺点：

  • 当某些子串与模式串部分匹配，⼀旦出现失配时，主串的扫描指针i经常回溯，导致时间开销增加。
  • 最坏时间复杂度O(n * m)

KMP算法

• 当子串和模式串不匹配时，主串指针i不回溯，通过改变模式串指针j的值，来确定子串从失配处和模式串的哪个位置进行比较，因为模式串前面的信息我在前面比较的时候已经知道信息了。
• 如果能够存储子串失配后从模式串的哪个位置上进行比较，就可以实现KMP算法，故引入next数组，专门存放这个值。
• 显然，next数组里的值，只跟模式串有关，因为模式串前面已经成功匹配的字符，就表示子串中已经包含了这些字符。

画图演示过程

代码

代码考研不做要求

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void GetNext(char* sub, int* next, int lenSub) {
    next[0] = -1;
    next[1] = 0;
    int j = 1;	// 当前下标
    int k = 0;	// 前一项的k，即前一项回退的下标
    // 此时 j=2 的前一项next数组值为0
    while(j+1 < lenSub) {
        if (k == -1 || sub[j ] == sub[k]) {	// 情况一和数组越界情况：next[j+1] = k+1
            next[j+1] = k+1;	
            j++;	// 求下一个位置
            k++;
        }
        else {
            k = next[k];	// 情况二：不相等则回退
        }
    }
}

int KMP(char* str, char* sub) {
    int lenStr = strlen(str);
    int lenSub = strlen(sub);
    if (lenStr == 0 || lenSub == 0) {
        return -1;
    }

    // 对模式串sub创建next数组
    int* next = (int*)malloc(sizeof(int) * lenSub);
    GetNext(sub, next, lenSub);
    // 进行遍历比较
    int i = 0;	// 遍历主串
    int j = 0;	// 遍历子串
    while (i < lenStr && j < lenSub) {
        if (j == -1 || str[i] == sub[j]) {	// j == -1 时，回退越界，一样进行++处理
            i++; j++;
        }
        else {
            j = next[j];	// 根据next数组进行回退
        }
    }

    // 模式串匹配主串，则会在模式串末尾结束
    if (j >= lenSub) {
        return i-j;
    }
    // 模式串不匹配主串
    return -1;
}
int main()
{
    char str[100];
    char sub[100];
    scanf("%s",str);//主串 
    getchar();
    scanf("%s",sub);//模式串 

    int ans=KMP(str,sub);
    printf("%d\n",ans);	
}