
#include <stdio.h>
#include <string.h>
 
#define MAX_SIZE 10
 
typedef struct SqList{
	int data[MAX_SIZE];
	int length;
}SqList;
 
//必须初始化
void initList(SqList* L) {
	for (int i = 0; i < MAX_SIZE; i++) {
		L->data[i] = 0;
	}
	L->length = 0;
}
 
int main()
{
	SqList L;
	initList(&L);
	for (int i = 0; i < MAX_SIZE; i++) {
		printf("%d\n", L.data[i]);
	}
	return 0;
}

8.2.2 动态分配


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define INIT_SIZE 10
 
typedef struct SqList{
	int* data;
	int maxSize;
	int length;
}SqList;
 
void initList(SqList* L) {
	//用malloc函数申请一片连续的存储空间
	L->data = (int*)malloc(INIT_SIZE * sizeof(int));
	L->maxSize = INIT_SIZE;
	L->length = 0;
}
 
//增加动态数组的长度
void increaseSize(SqList* L, int len) {
	int* p = L->data;
	L->data = (int*)malloc((L->maxSize + len) * sizeof(int));
	for (int i = 0; i < L->length; i++) {
		L->data[i] = p[i];  //将原来的数据复制道新区域
	}
	L->maxSize += len;
	free(p);  //释放原来的内存空间
}
 
int main()
{
	SqList L;
	initList(&L);
	increaseSize(&L, 5);
	return 0;
}

8.3 特点

1.随机访问，即可以在O(1)时间内找到第 i 个元素。
2.存储密度高，每个节点只存储数据元素。
3.拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）。
4.插入、删除操作不方便，需要移动大量元素。

9 顺序表的插入删除

9.1 插入

9.1.1 代码实现

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。


#include <stdio.h>
 
#define MAX_SIZE 10
#define SERO 3
 
typedef struct SqList {
	int data[MAX_SIZE];
	int length;
}SqList;
 
 
void initList(SqList* L) {
	for (int i = 0; i < MAX_SIZE - SERO; i++) {
		L->data[i] = i;
	}
 
	for (int i = MAX_SIZE - SERO; i < MAX_SIZE; i++) {
		L->data[i] = 0;
	}
 
	L->length = MAX_SIZE - SERO;
}
 
int ListInsert(SqList* L, int i, int e) {
	if (i < 1 || i > L->length + 1) {
		return 0;
	}
 
	if (L->length >= MAX_SIZE) {
		return 0;
	}
 
	for (int j = L->length; j >= i; j--) {
		L->data[j] = L->data[j - 1];
	}
 
	L->data[i - 1] = e;
	L->length++;
	return 1;
}
 
int main()
{
	SqList L;
	initList(&L);
	int result = ListInsert(&L, 1, 3);
 
	if (!result) {
		printf("插入失败\n");
	}
 
	for (int i = 0; i < MAX_SIZE; i++) {
		printf("%d = %d\n", i, L.data[i]);
	}
	return 0;
}

9.1.2 时间复杂度分析

问题规模 n = L.length (表长)

最好情况：新元素插入到表尾，不需要移动元素
i=n+1，循环0次；最好时间复杂度 = O(1)

最坏情况：新元素插入到表头，需要将原有的n个元素全部向后移动
i=1，循环n次；最坏时间复杂度 = O(n)

平均情况：假设新元素插入到任何一个位置的概率相同，即i=1，2，3，...，length+1的概率都是 $p=\frac{1}{n+1}$

i=1，循环n次；i=2时，循环n-1次；i=3，循环n-2次 ...... i=n+1时，循环0次

平均循环次数 = np+(n-1)p+(n-2)p+......+ip = $\frac{n(n+1)}{2}\frac{1}{n+1}=\frac{n}{2}$

平均时间复杂度 = O( $\frac{n}{2}$ ) = O(n)

9.2 删除

9.2.1 代码实现

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


#include <stdio.h>
 
#define MAX_SIZE 10
#define SERO 3
 
typedef struct SqList {
	int data[MAX_SIZE];
	int length;
}SqList;
 
 
void initList(SqList* L) {
	for (int i = 0; i < MAX_SIZE - SERO; i++) {
		L->data[i] = i;
	}
 
	for (int i = MAX_SIZE - SERO; i < MAX_SIZE; i++) {
		L->data[i] = 0;
	}
 
	L->length = MAX_SIZE - SERO;
}
 
int ListDelete(SqList* L, int i, int* e) {
	if (i< 1 || i>L->length) {
		return 0;
	}
 
	*e = L->data[i - 1];
	for (int j = i; j < L->length; j++) {
		L->data[j - 1] = L->data[j];
	}
 
	L->length--;
	return 1;
}
 
int main()
{
	SqList L;
	initList(&L);
 
	int e = -1;
	ListDelete(&L, 3, &e);
 
	printf("%d\n", e);
	for (int i = 0; i < MAX_SIZE; i++) {
		printf("%d = %d\n", i, L.data[i]);
	}
	return 0;
}

9.2.2 时间复杂度分析

问题规模 n = L.length (表长)

最好情况：删除表尾元素，不需要移动其他元素
i=n，循环0次；最好时间复杂度 = O(1)

最坏情况：删除表头元素，需要将后续的n-1个元素全部向前移动
i=1，循环n-1次；最坏时间复杂度 = O(n)

平均情况：假设删除任何一个元素的概率相同，即i=1，2，3，...，length的概率都是 $p=\frac{1}{n}$

i=1，循环n-1次；i=2时，循环n-2次；i=3，循环n-3次 ...... i=n时，循环0次

平均循环次数 = (n-1)p+(n-2)p+......+1*p = $\frac{n(n+1)}{2}\frac{1}{n}=\frac{n-1}{2}$

平均时间复杂度 = O( $\frac{n-1}{2}$ ) = O(n)

10 顺序表的查找

10.1 按位查找

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


#include <stdio.h>
 
#define MAX_SIZE 10
#define SERO 3
 
typedef struct SqList {
	int data[MAX_SIZE];
	int length;
}SqList;
 
 
void initList(SqList* L) {
	for (int i = 0; i < MAX_SIZE - SERO; i++) {
		L->data[i] = i;
	}
 
	for (int i = MAX_SIZE - SERO; i < MAX_SIZE; i++) {
		L->data[i] = 0;
	}
 
	L->length = MAX_SIZE - SERO;
}
 
int GetElem(SqList* L, int i) {
	return L->data[i - 1];
}
 
int main()
{
	SqList L;
	initList(&L);
 
	int elem = GetElem(&L, 2);
	printf("%d\n", elem);
 
	for (int i = 0; i < MAX_SIZE; i++) {
		printf("%d = %d\n", i, L.data[i]);
	}
	return 0;
}

10.1.1 时间复杂度分析

时间复杂度 = O(1)

10.2 按值查找

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


#include <stdio.h>
 
#define MAX_SIZE 10
#define SERO 3
 
typedef struct SqList {
	int data[MAX_SIZE];
	int length;
}SqList;
 
 
void initList(SqList* L) {
	for (int i = 0; i < MAX_SIZE - SERO; i++) {
		L->data[i] = i;
	}
 
	for (int i = MAX_SIZE - SERO; i < MAX_SIZE; i++) {
		L->data[i] = 0;
	}
 
	L->length = MAX_SIZE - SERO;
}
 
int LocateElem(SqList* L, int e) {
	for (int i = 0; i < MAX_SIZE; i++) {
		if (L->data[i] == e) {
			return i + 1;  //返回位序
		}
	}
 
	return -1;
}
 
int main()
{
	SqList L;
	initList(&L);
 
	int elem = LocateElem(&L, 0);
	printf("%d\n", elem);
 
	for (int i = 0; i < MAX_SIZE; i++) {
		printf("%d = %d\n", i, L.data[i]);
	}
	return 0;
}

10.2.1 时间复杂度分析

问题规模 n = L.length (表长)

最好情况：目标元素在表头，循环1次；最好时间复杂度 = O(1)

最坏情况：目标元素在表尾，循环n次；最坏时间复杂度 = O(n)

平均情况：假设目标元素出现在任何一个元素的概率相同，都是 $\frac{1}{n}$

目标元素在第1位，循环1次；在第2位，循环2次；...... ；在第n位，循环n次

平均循环次数 = $1\cdot \frac{1}{n}+2\cdot \frac{1}{n}+3\cdot \frac{1}{n}+......+n\cdot \frac{1}{n}=\frac{n(n+1)}{2}\frac{1}{n}=\frac{n+1}{2}$

平均时间复杂度 = O( $\frac{n+1}{2}$ ) = O(n)

11 单链表的定义

11.1 什么是单链表

每个结点除了存放数据元素外，还要存储指向下一个结点的指针

11.2 用代码定义一个单链表

强调这是一个单链表 ——— 使用LinkList 因为取到头结点就是得到整个链表

强调这是一个结点 ——— 使用LNode*


typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;

11.3 两种实现

11.3.1 带头结点

带头结点，写代码更方便


#include <stdio.h>
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
 
 
// 初始化链表
int InitList(LinkList* L) {
	*L = (LNode*)malloc(sizeof(LNode));
	if (*L == NULL) {
		return 0;
	}
	
    (*L)->data = -1;
	(*L)->next = NULL;
	return 1;
}
 
// 判断链表是否为空
int IsEmpty(LinkList L) {
	return L->next == NULL;
}
 
int main() {
	// 创建一个新的空链表
	LinkList L;
	InitList(&L);
 
	// 判断链表是否为空
	if (IsEmpty(L)) {
		printf("链表为空！\n");
	}
	else {
		printf("链表不为空！\n");
	}
 
	return 0;
}

11.3.2 不带头结点


#include <stdio.h>
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
 
// 初始化链表
int InitList(LinkList* L) {
	*L = NULL;
	return 1;
}
 
// 判断链表是否为空
int IsEmpty(LinkList L) {
	return L == NULL;
}
 
int main() {
	// 创建一个新的空链表
	LinkList L;
	InitList(&L);
 
	// 判断链表是否为空
	if (IsEmpty(L)) {
		printf("链表为空！\n");
	}
	else {
		printf("链表不为空！\n");
	}
 
	return 0;
}

12 单链表的插入删除

12.1 按位序插入

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。

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

最好时间复杂度：O(1)

12.1.1 带头结点


#include <stdio.h>
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
 
 
// 初始化链表
int InitList(LinkList* L) {
	*L = (LNode*)malloc(sizeof(LNode));
	if (*L == NULL) {
		return 0;
	}
 
    (*L)->data = -1;
	(*L)->next = NULL;
	return 1;
}
 
// 判断链表是否为空
int IsEmpty(LinkList L) {
	return L->next == NULL;
}
 
int ListInsert(LinkList L, int i, int e) {
	if (i < 1) {
		return 0;
	}
 
	LNode* p = L;   //L指向头结点，头结点是第0个结点（不存数据）
	int j = 0;     //当前p指向的是第几个结点
 
	while (p != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
 
	if (p == NULL) {  //i超出链表长度
		return 0;
	}
 
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
 
	return 1;
}
 
int main() {
	// 创建一个新的空链表
	LinkList L;
	InitList(&L);
 
	ListInsert(L, 1, 1);
	ListInsert(L, 2, 2);
	ListInsert(L, 3, 3);
 
	// 判断链表是否为空
	if (IsEmpty(L)) {
		printf("链表为空！\n");
	}
	else {
		printf("链表不为空！\n");
	}
 
	// 遍历链表，打印每个结点的值
	LNode* p = L->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
 
	return 0;
}

12.1.2 不带头结点


#include <stdio.h>
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
 
 
// 初始化链表
int InitList(LinkList* L) {
	*L = NULL;
	return 1;
}
 
// 判断链表是否为空
int IsEmpty(LinkList L) {
	return L == NULL;
}
 
int ListInsert(LinkList* L, int i, int e) {
	if (i < 1) {
		return 0;
	}
 
	if (i == 1) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = *L;
		*L = s;
		return 1;
	}
 
	LNode* p = *L;   //L指向头结点，头结点是第0个结点（不存数据）
	int j = 1;     //当前p指向的是第几个结点
 
	while (p != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
 
	if (p == NULL) {  //i超出链表长度
		return 0;
	}
 
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
 
	return 1;
}
 
int main() {
	// 创建一个新的空链表
	LinkList L;
	InitList(&L);
 
	ListInsert(&L, 1, 1);
	ListInsert(&L, 2, 2);
	ListInsert(&L, 3, 3);
 
	// 判断链表是否为空
	if (IsEmpty(L)) {
		printf("链表为空！\n");
	}
	else {
		printf("链表不为空！\n");
	}
 
	// 遍历链表，打印每个结点的值
	LNode* p = L;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
 
	return 0;
}

12.2 指定结点的后插操作


int InsertNextNode(LNode* p, int e) {
	if (p == NULL) {  
		return 0;
	}
 
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL) {
		return 0;
	}
 
	s->data = e;
	s->next = p->next;
	p->next = s;
 
	return 1;
}

12.3 指定结点的前插操作


int InsertPriorNode(LNode* p, int e) {
	if (p == NULL) {  
		return 0;
	}
 
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL) {
		return 0;
	}
 
	s->next = p->next;
	p->next = s;
	s->data = p->data;   //链表找不到前驱结点，所以替换值，相当于前插
	p->data = e;
 
	return 1;
}

12.4 删除

12.4.1 按位序删除

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

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

最好时间复杂度：O(1)


#include <stdio.h>
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
 
 
// 初始化链表
int InitList(LinkList* L) {
	*L = (LNode*)malloc(sizeof(LNode));
	if (*L == NULL) {
		return 0;
	}
 
	(*L)->data = -1;
	(*L)->next = NULL;
	return 1;
}
 
int ListInsert(LinkList L, int i, int e) {
	if (i < 1) {
		return 0;
	}
 
	LNode* p = L;   //L指向头结点，头结点是第0个结点（不存数据）
	int j = 0;     //当前p指向的是第几个结点
 
	while (p != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
 
	if (p == NULL) {  //i超出链表长度
		return 0;
	}
 
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL) {
		return 0;
	}
 
	s->data = e;
	s->next = p->next;
	p->next = s;
 
	return 1;
}
 
int ListDelete(LinkList L, int i, int* e) {
	if (i < 1) {
		return 0;
	}
 
	LNode* p = L;   //L指向头结点，头结点是第0个结点（不存数据）
	int j = 0;     //当前p指向的是第几个结点
 
	while (p != NULL && j < i-1)  //找到要删除的前一个结点
	{
		p = p->next;
		j++;
	}
 
	if (p == NULL) {  //i超出链表长度
		return 0;
	}
 
	if (p->next == NULL) {  //第i-1个结点之后无其他结点
		return 0;
	}
 
	LNode* q = p->next;
	*e = q->data;
	p->next = q->next;
	free(q);
 
	return 1;
}
 
int main() {
	// 创建一个新的空链表
	LinkList L;
	InitList(&L);
 
	ListInsert(L, 1, 1);
	ListInsert(L, 2, 2);
	ListInsert(L, 3, 3);
 
	int e = -1;
	ListDelete(L, 4, &e);
 
	printf("%d\n", e);
 
	// 遍历链表，打印每个结点的值
	LNode* p = L->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
 
	return 0;
}

12.4.1 指定结点的删除


int DeleteNode(LNode* p) {
	if (p == NULL) {
		return 0;
	}
 
	LNode* q = p->next;
	p->data = q->data;
	p->next = q->next;
	free(q);
	return 1;
}

13 单链表的查找

13.1 按位查找

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

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


#include <stdio.h>
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
 
 
// 初始化链表
int InitList(LinkList* L) {
	*L = (LNode*)malloc(sizeof(LNode));
	if (*L == NULL) {
		return 0;
	}
 
	(*L)->data = -1;
	(*L)->next = NULL;
	return 1;
}
 
int ListInsert(LinkList L, int i, int e) {
	if (i < 1) {
		return 0;
	}
 
	LNode* p = L;   //L指向头结点，头结点是第0个结点（不存数据）
	int j = 0;     //当前p指向的是第几个结点
 
	while (p != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
 
	if (p == NULL) {  //i超出链表长度
		return 0;
	}
 
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL) {
		return 0;
	}
 
	s->data = e;
	s->next = p->next;
	p->next = s;
 
	return 1;
}
 
LNode* GetElem(LinkList L, int i) {
	if (i < 1) {
		return NULL;
	}
 
	LNode* p = L;
	int j = 0;
	while (p != NULL && j < i) {
		p = p->next;
		j++;
	}
 
	return p;
}
 
int main() {
	// 创建一个新的空链表
	LinkList L;
	InitList(&L);
 
	ListInsert(L, 1, 1);
	ListInsert(L, 2, 2);
	ListInsert(L, 3, 3);
 
	LNode* e = GetElem(L, 3);
	if (e != NULL) {
		printf("%d\n", e->data);
	}
	else {
		printf("没找到\n");
	}
	
	// 遍历链表，打印每个结点的值
	LNode* p = L->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
 
	return 0;
}

13.2 按值查找

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

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


#include <stdio.h>
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
 
 
// 初始化链表
int InitList(LinkList* L) {
	*L = (LNode*)malloc(sizeof(LNode));
	if (*L == NULL) {
		return 0;
	}
 
	(*L)->data = -1;
	(*L)->next = NULL;
	return 1;
}
 
int ListInsert(LinkList L, int i, int e) {
	if (i < 1) {
		return 0;
	}
 
	LNode* p = L;   //L指向头结点，头结点是第0个结点（不存数据）
	int j = 0;     //当前p指向的是第几个结点
 
	while (p != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
 
	if (p == NULL) {  //i超出链表长度
		return 0;
	}
 
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL) {
		return 0;
	}
 
	s->data = e;
	s->next = p->next;
	p->next = s;
 
	return 1;
}
 
LNode* LocateElem(LinkList L, int e) {
	LNode* p = L->next;
	
	while (p != NULL && p->data != e) {
		p = p->next;
	}
 
	return p;
}
 
 
 
int main() {
	// 创建一个新的空链表
	LinkList L;
	InitList(&L);
 
	ListInsert(L, 1, 1);
	ListInsert(L, 2, 2);
	ListInsert(L, 3, 3);
 
	LNode* e = LocateElem(L, 3);
	if (e != NULL) {
		printf("%d\n", e->data);
	}
	else {
		printf("没找到\n");
	}
	
	// 遍历链表，打印每个结点的值
	LNode* p = L->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
 
	return 0;
}

13.3 求表长度

时间复杂度：O(n)


int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p->next != NULL)
	{
		p = p->next;
		len++;
	}
 
	return len;
}

14 单链表的建立

14.1 尾插法建立单链表

时间复杂度：O(n)


#include <stdio.h>
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
 
LinkList List_TailInsert(LinkList L) {
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	if (L == NULL)
		return NULL;
    L->next = NULL;
 
	LNode* s, * r = L;
	scanf("%d", &x);
	while (x != 888)
	{
		s = (LNode*)malloc(sizeof(LNode));
		if (s == NULL)
			return NULL;
		s->data = x;
		r->next = s;
		r = s;   //替换s，r成尾结点
		scanf("%d", &x);
	}
 
	r->next = NULL;   //尾结点下一个结点置空
	return L;
}
 
int main() {
	// 创建一个新的空链表
	LinkList L = NULL;
 
	L = List_TailInsert(L);
 
	// 遍历链表，打印每个结点的值
	LNode* p = L->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
 
	return 0;
}

14.2 头插法建立单链表

重点：链表逆置


#include <stdio.h>
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
 
LinkList List_HeadInsert(LinkList L) {
	L = (LinkList)malloc(sizeof(LNode));
	if (L == NULL)
		return NULL;
	L->next = NULL;
 
	LNode* s;
	int x;
	scanf("%d", &x);
	while (x != 888)
	{
		s = (LNode*)malloc(sizeof(LNode));
		if (s == NULL)
			return NULL;
 
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
 
	return L;
}
 
int main() {
	// 创建一个新的空链表
	LinkList L = NULL;
 
	L = List_HeadInsert(L);
 
	// 遍历链表，打印每个结点的值
	LNode* p = L->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
 
	return 0;
}

15 双链表

15.1 初始化


//初始化
int InitDLinkList(DLinkList* L) {
	*L = (DNode*)malloc(sizeof(DNode));
	if (*L == NULL)
		return 0;
	(*L)->data = -1;
	(*L)->prior = NULL;
	(*L)->next = NULL;
	return 1;
}

15.2 插入（后插）


//在p结点之后插入s结点
int InsertNextDNode(DNode* p, DNode* s) {
	if (p == NULL || s == NULL)
		return 0;
	s->next = p->next;
	if (p->next != NULL)  //如果p是最后一个结点，前驱结点空指针
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return 1;
}

15.3 删除（后插）


//删除p结点的后继结点
int DeleteNextDNode(DNode* p) {
	if (p == NULL)
		return 0;
	DNode* q = p->next;  //找到p的后继结点q
	if (q == NULL)
		return 0;
 
	p->next = q->next;
	if (q->next != NULL)  //如果q是最后一个结点，前驱结点空指针
		q->next->prior = p;
 
	free(q);
    q = NULL;
	return 1;
}

15.4 遍历


//后向遍历
void PrintDLinkList(DLinkList L) {
	DNode* p = L->next;
	while(p != NULL) {
		printf("%d\n", p->data);
		p = p->next;
	}
}

16 循环链表

17 静态链表

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

静态链表：分配一整片连续的内存空间，各个结点集中安置

17.1 定义链表

第一种方法：


#include <stdio.h>
 
#define MaxSize 10
 
struct Node {
	int data;
	int next;  //下一个元素的下标
};
 
int main()
{
	struct Node a[MaxSize];
	return 0;
}

第二种方法：


#include <stdio.h>
 
#define MaxSize 10
 
typedef struct Node {
	int data;
	int next;
}SLinkList[MaxSize];   //等价于 typedef struct Node SLinkList[MaxSize];
 
int main()
{
	SLinkList a;
	return 0;
}

18 顺序表和链表的比较

	顺序表	链表
逻辑结构	都属于线性表，都是线性结构
存储结构	顺序存储优点：支持随机存取、存储密度高缺点：大片连续空间分配不方便，改变容量不方便	链式存储优点：离散的小空间分配方便，改变容量方便缺点：不可随机存取，存储密度低
基本操作/创	需要预分配大小连续的空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。静态分配：静态数组（容量不可改变）动态分配：动态数组（malloc、free）(容量可改变，但需要移动大量元素，时间代价高)	只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展
基本操作/销	修改length = 0 静态分配：静态数组（系统自动回收空间）动态分配：动态数组（需要手动free）	依次删除各个结点（free）
基本操作/增、删	插入/删除元素要将后续元素都后移/前移时间复杂度O(n)，时间开销主要来自移动元素若数据元素很大，则移动的时间代价很高	插入/删除元素只需修改指针即可时间复杂度O(n)，时间开销主要来自查找目标元素查找元素的时间代价更低
基本操作/查	按位查找：O(1) 按值查找：O(n)，若表内元素有序，可在O( $\log _{2}n$ )时间内找到	按位查找：O(n) 按值查找：O(n)
应用场景	表长可预估、查询（搜索）操作较多	表长难以预估、经常要增加/删除元素

19 栈

19.1 定义

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

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

19.2 基本操作

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

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

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

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

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

其他常用操作：

StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false。

20 栈的顺序存储实现

20.1 基本操作（top == -1）


#include <stdio.h>
 
#define MaxSize 10
 
typedef struct Stack {
	int data[MaxSize];
	int top;  //栈顶指针
}SqStack;
 
void InitStack(SqStack* s) {
	s->top = -1;
}
 
int StackEmpty(SqStack s) {
	return s.top == -1;
}
 
int Push(SqStack* s, int x) {
	if (s->top == MaxSize - 1)
		return 0;
	s->data[++s->top] = x;
	return 1;
}
 
int Pop(SqStack* s, int* x) {
	if (s->top == -1)
		return 0;
	*x = s->data[s->top--];
	return 1;
}
 
int GetTop(SqStack s, int* x) {
	if (s.top == -1)
		return 0;
	*x = s.data[s.top];
	return 1;
}
 
int main()
{
	SqStack s;
	InitStack(&s);
	Push(&s, 1);
	Push(&s, 2);
	Push(&s, 3);
	int a = 0;
	int b = 0;
	Pop(&s, &a);
	GetTop(s, &b);
 
	printf("%d\n", a);      //3
	printf("%d\n", b);      //2
	printf("%d\n", s.top);  //1
 
	return 0;
}

20.2 基本操作（top == 0）


#include <stdio.h>
 
#define MaxSize 10
 
typedef struct Stack {
	int data[MaxSize];
	int top;  //栈顶指针
}SqStack;
 
void InitStack(SqStack* s) {
	s->top = 0;
}
 
int StackEmpty(SqStack s) {
	return s.top == 0;
}
 
int Push(SqStack* s, int x) {
	if (s->top == MaxSize)
		return 0;
	s->data[s->top++] = x;
	return 1;
}
 
int Pop(SqStack* s, int* x) {
	if (s->top == 0)
		return 0;
	*x = s->data[--s->top];
	return 1;
}
 
int GetTop(SqStack s, int* x) {
	if (s.top == 0)
		return 0;
	*x = s.data[--s.top];
	return 1;
}
 
int main()
{
	SqStack s;
	InitStack(&s);
	Push(&s, 1);
	Push(&s, 2);
	Push(&s, 3);
	int a = 0;
	int b = 0;
	Pop(&s, &a);
	GetTop(s, &b);
 
	printf("%d\n", a);      //3
	printf("%d\n", b);      //2
	printf("%d\n", s.top);  //2
 
	return 0;
}

21 栈的链式存储实现

21.1 基本操作（不带头结点）


#include <stdio.h>
 
typedef struct Linknode {
	int data;
	struct Linknode* next;
}*Linknode;
 
void InitStack(Linknode* L) {
	*L = NULL;
}
 
int StackEmpty(Linknode L) {
	return L == NULL;
}
 
int Push(Linknode* L, int x) {
	Linknode n = (Linknode)malloc(sizeof(struct Linknode));
	if (n == NULL)
		return 0;
 
	n->data = x;
	n->next = *L;
	*L = n;
	return 1;
}
 
int Pop(Linknode* L, int* x) {
	if (*L == NULL)
		return 0;
 
	Linknode temp = *L;
	*x = temp->data;
	*L = (*L)->next;
	free(temp);
	return 1;
}
 
int GetTop(Linknode L, int* x) {
	if (L == NULL)
		return 0;
 
	*x = L->data;
	return 1;
}
 
int main()
{
	Linknode stack;
	InitStack(&stack);
	Push(&stack, 1);
	Push(&stack, 2);
	Push(&stack, 3);
	Push(&stack, 4);
	Push(&stack, 5);
	
	int pop = 0;
	Pop(&stack, &pop);
	Pop(&stack, &pop);
	Pop(&stack, &pop);
	Pop(&stack, &pop);
	//Pop(&stack, &pop);
 
	int top = 0;
	GetTop(stack, &top);
	printf("%d\n", top);
 
	if (StackEmpty(stack))
		printf("NULL\n");
	else
		printf("NOT NULL\n");
	return 0;
}

22 队列的基本概念

22.1 队列的定义

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

重要术语：队头、队尾、空队列

队列的特点：先进先出 First In First Out（FIFO）

22.2 队列的基本操作

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

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

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

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

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

其他常用操作：

QueueEmpty(Q):判队列空，若队列Q为空返回true，否则返回false。

23 队列的顺序实现

23.1 方案一

23.1.1 初始化操作


#include <stdio.h>
 
#define MaxSize 10
typedef struct SqQueue {
	int dada[MaxSize];
	int front, rear;
}SqQueue;
 
void InitQueue(SqQueue* Q) {
	Q->front = Q->rear = 0;
}
 
int QueueEmpty(SqQueue Q) {
	return Q.front == Q.rear;
}
 
int main()
{
	SqQueue Q;
	InitQueue(&Q);
 
	if (QueueEmpty(Q))
		printf("NULL\n");
	else
		printf("NOT NULL\n");
	return 0;
}

23.1.2 入队操作(rear指向队尾元素后一个位置)

a%b 模运算将无限的整数域映射到有限的整数集合{0,1,2,...,b-1}上。

列如：1%10 只能得到 [0，9] 的数

队列元素个数：（rear+MaxSize-front）%MaxSize


int EnQueue(SqQueue* Q, int x) {
	if ((Q->rear + 1) % MaxSize == Q->front)
		return 0;
 
	Q->data[Q->rear] = x;
	Q->rear = (Q->rear + 1) % MaxSize;
	return 1;
}

23.1.3 出队操作(rear指向队尾元素后一个位置)


int DeQueue(SqQueue* Q, int* x) {
	if (Q->front == Q->rear)
		return 0;
 
	*x = Q->data[Q->front];
	Q->front = (Q->front + 1) % MaxSize;
	return 1;
}
 
int GetHead(SqQueue Q, int* x) {
	if (Q.front == Q.rear)
		return 0;
 
	*x = Q.data[Q.front];
	return 1;
}

23.2 方案二

23.2.1 初始化操作

队满条件：size==MaxSize


#define MaxSize 10
typedef struct SqQueue {
	int data[MaxSize];
	int front, rear;
	int size;   //队列当前长度
}SqQueue;
 
void InitQueue(SqQueue* Q) {
	Q->front = Q->rear = Q->size = 0;
}
 
int QueueEmpty(SqQueue Q) {
	return Q.size==0;
}

23.3 方案三

23.3.1 初始化操作

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


#define MaxSize 10
typedef struct SqQueue {
	int data[MaxSize];
	int front, rear;
	//每次删除操作成功时，都令tag=0
	//每次插入操作成功时，都令tag=1
	int tag;   //最近进行的是删除/插入
}SqQueue;
 
void InitQueue(SqQueue* Q) {
	Q->front = Q->rear = Q->tag = 0;
}
 
int QueueEmpty(SqQueue Q) {
	return Q.front == Q.rear && Q.tag == 0;
}

24 队列的链式实现

24.1 初始化

24.1.1 带头结点


typedef struct LinkNode {
	int data;
	struct LinkNode* next;
}LinkNode;
 
typedef struct LinkQueue {
	LinkNode* front, * rear;
}LinkQueue;
 
void InitQueue(LinkQueue* Q) {
	Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q->front = NULL;
}
 
int IsEmpty(LinkQueue Q) {
	return Q.front == Q.rear;
}

24.1.2 不带头结点


void InitQueue(LinkQueue* Q) {
	Q->front = NULL;
	Q->rear = NULL;
}
 
int IsEmpty(LinkQueue Q) {
	return Q.front == NULL;
}

24.2 入队

24.2.1 带头结点


void EnQueue(LinkQueue* Q, int x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q->rear->next = s;
	Q->rear = s;
}

24.2.2 不带头结点


void EnQueue(LinkQueue* Q, int x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
 
	if (Q->front == NULL) {
		Q->front = s;
		Q->rear = s;
	}
	else
	{
		Q->rear->next = s;
		Q->rear = s;
	}
}

24.3 出队

24.3.1 带头结点


int DeQueue(LinkQueue* Q, int* x) {
	if (Q->front == Q->rear)
		return 0;
 
	LinkNode* p = Q->front->next;
	*x = p->data;
	Q->front->next = p->next;
 
	if (Q->rear == p)   //此时是最后一个结点出队
		Q->rear = Q->front;
 
	free(p);
	return 1;
}

24.3.2 不带头结点


int DeQueue(LinkQueue* Q, int* x) {
	if (Q->front == NULL)
		return 0;
 
	LinkNode* p = Q->front;
	*x = p->data;
	Q->front = p->next;
 
	if (Q->rear == p) {   //此时是最后一个结点出队
		Q->front = NULL;
		Q->rear = NULL;
	}
 
	free(p);
	return 1;
}

25 双端队列

双端队列：只允许从两端插入、两端删除的线性表

输入受限的双端队列：只允许从一端插入、两端删除的线性表

输出受限的双端队列：只允许从两端插入、一端删除的线性表

26 栈在括号匹配中的应用

用栈实现括号匹配：
依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。

匹配失败情况：
1、左括号单身
2、右括号单身
3、左右括号不匹配

26.1 算法实现


#include <stdio.h>
 
#define MaxSize 10
typedef struct Stack {
	char data[MaxSize];
	int top;
}SqStack;
 
void InitStack(SqStack* S) {
	S->top = -1;
}
 
int StackEmpty(SqStack S) {
	return S.top == -1;
}
 
int Push(SqStack* S, char x) {
	if (S->top == MaxSize - 1)
		return 0;
 
	S->data[++S->top] = x;
	return 1;
}
 
int Pop(SqStack* S, char* x) {
	if (S->top == -1)
		return 0;
 
	*x = S->data[S->top--];
	return 1;
}
 
int braketCheck(char str[], int length) {
	SqStack S;
	InitStack(&S);
	for (int i = 0; i < length; i++) {
		if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
			Push(&S, str[i]);
		}
		else
		{
			if (StackEmpty(S)) {
				return 0;
			}
 
			char topElem;
			Pop(&S, &topElem);
			if (str[i] == ')' && topElem != '(')
				return 0;
			if (str[i] == ']' && topElem != '[')
				return 0;
			if (str[i] == '}' && topElem != '{')
				return 0;
		} 
	}
 
	return StackEmpty(S);
}
 
int main()
{
	char str[] = { '(','(','(',')',')',')' };
	int length = sizeof(str) / sizeof(str[0]);
	if (braketCheck(str, length))
		printf("匹配成功\n");
	else
		printf("匹配失败\n");
	return 0;
}

27 栈在表达式求值中的应用（上）

27.1 中缀、后缀、前缀表达式

中缀表达式：运算符在两个操作数中间 a+b

后缀表达式：运算符在两个操作数后面 ab+

前缀表达式：运算符在两个操作数前面 +ab

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

中缀转后缀的手算方法：

1.确定中缀表达式中各个运算符的运算顺序

2.选择下一个运算符，按照 [左操作数右操作数运算符] 的方式组合成一个新的操作数

3.如果还有运算符没被处理，就继续2

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

27.3 后缀表达式的计算（手算）

后缀表达式的手算方法：

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数

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

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

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

1.从左往右扫描下一个元素，直到处理完所有元素

2.若扫描到操作数则压入栈，并回到1；否则执行3

3.若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到1

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

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

中缀转前缀的手算方法：

1.确定中缀表达式中各个运算符的运算顺序

2.选择下一个运算符，按照 [运算符左操作数右操作数] 的方式组合成一个新的操作数

3.如果还有运算符没被处理，就继续2

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

27.6 前缀表达式的计算

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

1.从右往左扫描下一个元素，直到处理完所有元素

2.若扫描到操作数则压入栈，并回到1；否则执行3

3.若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到1

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

28 栈在表达式求值中的应用（下）

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

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。

从左往右处理各个元素，直到末尾。可能遇到三种情况：
1.遇到操作数。直接加入后缀表达式。
2.遇到界限符。遇到 “（” 直接入栈；遇到 “）” 则依次弹出栈内运算符并加入后缀表达式，直到弹出 “（” 为止。注意：“（” 不能加入后缀表达式。
3.遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 “（” 或栈空则停止。之后再把当前运算符入栈。

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

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

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

初始化两个栈，操作数栈和运算符栈

若扫描到操作数，压入操作数栈

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

29 栈在递归中的应用

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

函数调用时，需要用一个栈存储：
1.调用返回地址
2.实参
3.局部变量

适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题

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

缺点：效率低，太多层递归可能会导致栈溢出，可能包含很多重复计算

30 队列的应用

树的层次遍历、图的广度优先遍历

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

31 特殊矩阵的压缩存储

31.1 一维数组的存储结构

起始地址：LOC

各数组元素大小相同，且物理上连续存放。

数组元素a[i]的存放地址 = LOC + i*sizeof(ElemType)

注：除非题目特别说明，否则数组下标默从0开始

31.2 二维数组的存储结构

起始地址：LOC

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

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

31.3 普通矩阵的存储

描述矩阵元素时，行、列号通常从1开始；而描述数组时通常下标从0开始（具体看题目给的条件，注意审题！）

31.4 对称矩阵的压缩存储

若n阶方阵中任意一个元素ai,j都有ai,j=aj,i 则该矩阵为对称矩阵

普通存储：n*n二维数组

压缩存储策略：只存储主对角线+下三角区（或主对角线+上三角区）
上三角区：i<j
下三角区：i>j

策略：只存储主对角线+下三角区

按行优先原则将各元素存入一维数组中。

数组大小：n(1+n)/2

矩阵下标 ——> 一维数组下标

ai,j ——> B[k]

k = i(i-1)/2 + j-1 i>=j（下三角区和主对角线元素）

k = j(j-1)/2 + i-1 i<j（上三角区元素 aij = aji ）

31.5 三角矩阵的压缩存储

下三角矩阵：除了主对角线和下三角区，其余的元素都相同

下三角矩阵压缩存储策略：按行优先原则将主对角线和下三角区元素存入一维数组中，并在最后一个位置存储常量C

矩阵下标 ——> 一维数组下标

ai,j （i>=j）——> B[k]

k = i(i-1)/2 + j-1 i>=j（下三角区和主对角线元素）

k = n(1+n)/2 i<j（上三角区元素）

上三角矩阵：除了主对角线和上三角区，其余的元素都相同

下三角矩阵压缩存储策略：按行优先原则将主对角线和上三角区元素存入一维数组中，并在最后一个位置存储常量C

矩阵下标 ——> 一维数组下标

ai,j （i<=j）——> B[k]

k = (i-1)(2n-i+2)/2 + (j-i) i<=j（上三角区和主对角线元素）

k = n(1+n)/2 i>j（下三角区元素）

31.6 三对角矩阵的压缩存储

三对角矩阵，又称带状矩阵，当 [i-j]>1 时，有 ai,j=0（i<=i，j<=n）

压缩存储策略：按行优先（或列优先）原则，只存储带状部分

矩阵下标 ——> 一维数组下标

ai,j （ |i-j| <= 1 ）——> B[k]

k = 2i+j-3

一维数组下标——>矩阵下标

B[k] ——> ai,j （ |i-j| <= 1 ）

3(i-1)-1 <= k < 3i-1

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

31.7 稀疏矩阵的压缩存储

稀疏矩阵：非零元素远远少于矩阵元素的个数

压缩存储策略一：顺序存储——三元组<行，列，值>

压缩存储策略二：链式存储——十字链表法

32 串的定义和基本操作

32.1 串的定义

串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为S=' $a_{1}a_{2}......a_{n}$ '（n>=0）

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

字串：串中任意个连续的字符组成的子序列。

主串：包含子串的串。

字符在主串中的位置：字符在串中的序号。

子串在主串中的位置：字串的第一个字符在主串中的位置。

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

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

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）

串的基本操作，如增删改查等通常以字串为操作对象

32.2 串的基本操作

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

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

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

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

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

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

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

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

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

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

33 串的存储结构

33.1 串的顺序存储


#include <stdio.h>
 
//静态数组实现
#define MAXLEN 255
typedef struct SString {
	char ch[MAXLEN];
	int length;
}SString;
 
//动态数组实现
typedef struct HString {
	char* ch;
	int length;
}HString;
 
int main()
{
	HString S;
	S.ch = (char*)malloc(MAXLEN * sizeof(char));
	S.length = 0;
	return 0;
}

33.2 串的链式存储


typedef struct StringNode {
	char ch[4];   //每个结点存多个字符，存储密度高
	struct StringNode* next;
}StringNode, * String;

33.3 基本操作的实现

33.3.1 求子串


#include <stdio.h>
 
//静态数组实现
#define MAXLEN 255
typedef struct SString {
	char ch[MAXLEN];
	int length;
}SString;
 
//ch[0]废弃不用，数组最后一个位置充当length
int SubString(SString* Sub, SString S, int pos, int len) {
	if (pos + len - 1 > S.length)
		return 0;
 
	for (int i = pos; i < pos + len; i++)
		Sub->ch[i - pos + 1] = S.ch[i];
 
	Sub->length = len;
	return 1;
}
 
int main()
{
	SString S, Sub;
 
	// 初始化原始字符串
	S.ch[1] = 'H';
	S.ch[2] = 'e';
	S.ch[3] = 'l';
	S.ch[4] = 'l';
	S.ch[5] = 'o';
	S.ch[6] = ',';
	S.ch[7] = ' ';
	S.ch[8] = 'W';
	S.ch[9] = 'o';
	S.ch[10] = 'r';
	S.ch[11] = 'l';
	S.ch[12] = 'd';
	S.length = 12;
	for (int i = 1; i <= S.length; i++)
		printf("%c", S.ch[i]);
 
	SubString(&Sub, S, 1, 5);
	
	printf("\n");
 
	// 输出子串
	for (int i = 1; i <= Sub.length; i++)
		printf("%c", Sub.ch[i]);
 
	return 0;
}

33.3.2 串的比较


#include <stdio.h>
 
//静态数组实现
#define MAXLEN 255
typedef struct SString {
	char ch[MAXLEN];
	int length;
}SString;
 
//ch[0]废弃不用，数组最后一个位置充当length
int SubString(SString* Sub, SString S, int pos, int len) {
	if (pos + len - 1 > S.length)
		return 0;
 
	for (int i = pos; i < pos + len; i++)
		Sub->ch[i - pos + 1] = S.ch[i];
 
	Sub->length = len;
	return 1;
}
 
int StrCompare(SString S, SString T) {
	for (int i = 1; i < S.length && i < T.length; i++)
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i];
 
	return S.length - T.length;   //所有字符都相同，就比较长度
}
 
int main()
{
	SString S, Sub;
 
	// 初始化原始字符串
	S.ch[1] = 'H';
	S.ch[2] = 'e';
	S.ch[3] = 'l';
	S.ch[4] = 'l';
	S.ch[5] = 'o';
	S.ch[6] = ',';
	S.ch[7] = ' ';
	S.ch[8] = 'W';
	S.ch[9] = 'o';
	S.ch[10] = 'r';
	S.ch[11] = 'l';
	S.ch[12] = 'd';
	S.length = 12;
	for (int i = 1; i <= S.length; i++)
		printf("%c", S.ch[i]);
 
	SubString(&Sub, S, 1, 5);
 
	printf("\n");
 
	// 输出子串
	for (int i = 1; i <= Sub.length; i++)
		printf("%c", Sub.ch[i]);
 
	printf("\n");
 
	if (StrCompare(S, Sub) > 0)
		printf("S>Sub\n");
	else if (StrCompare(S, Sub) == 0)
		printf("S=Sub\n");
	else
		printf("S<Sub\n");
 
	return 0;
}

33.3.3 求串在主串中的位置


#include <stdio.h>
 
//静态数组实现
#define MAXLEN 255
typedef struct SString {
	char ch[MAXLEN];
	int length;
}SString;
 
//ch[0]废弃不用，数组最后一个位置充当length
int SubString(SString* Sub, SString S, int pos, int len) {
	if (pos + len - 1 > S.length)
		return 0;
 
	for (int i = pos; i < pos + len; i++)
		Sub->ch[i - pos + 1] = S.ch[i];
 
	Sub->length = len;
	return 1;
}
 
int StrCompare(SString S, SString T) {
	for (int i = 1; i < S.length && i < T.length; i++)
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i];
 
	return S.length - T.length;   //所有字符都相同，就比较长度
}
 
int Strlength(SString S) {
	return S.length;
}
 
int Index(SString S, SString T) {
	int i = 1, n = Strlength(S), m = Strlength(T);
	SString sub;   //用于暂存子串
 
	while (i < n - m + 1)
	{
		SubString(&sub, S, i, m);
		if (StrCompare(sub, T) != 0)
			i++;
		else
			return i;
	}
 
	return 0;
}
 
int main()
{
	SString S, Sub;
 
	// 初始化原始字符串
	S.ch[1] = 'H';
	S.ch[2] = 'e';
	S.ch[3] = 'l';
	S.ch[4] = 'l';
	S.ch[5] = 'o';
	S.ch[6] = ',';
	S.ch[7] = ' ';
	S.ch[8] = 'W';
	S.ch[9] = 'o';
	S.ch[10] = 'r';
	S.ch[11] = 'l';
	S.ch[12] = 'd';
	S.length = 12;
	for (int i = 1; i <= S.length; i++)
		printf("%c", S.ch[i]);
 
	SubString(&Sub, S, 1, 5);
 
	printf("\n");
 
	// 输出子串
	for (int i = 1; i <= Sub.length; i++)
		printf("%c", Sub.ch[i]);
 
	printf("\n");
 
	if (StrCompare(S, Sub) > 0)
		printf("S>Sub\n");
	else if (StrCompare(S, Sub) == 0)
		printf("S=Sub\n");
	else
		printf("S<Sub\n");
 
	printf("%d\n", Index(S, Sub));
	return 0;
}

34 朴素模式匹配算法

子串——主串的一部分，一定存在

模式串——不一定能在主串中找到

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

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

朴素模式匹配算法：将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

最多对比n-m+1个子串

若当前子串匹配失败，则主串指针i指向下一个子串的第一个位置，模式串指针j回到模式串的第一个位置（ i = i-j+2; j = 1 ）

若j>T.length，则当前子串匹配成功，返回当前子串第一个字符的位置—— i - T.length


int Index(SString S, SString T) {
	int i = 1, j = 1;
	while (i <= S.length && j <= T.length)
	{
		if (S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else
		{
			i = i - j + 2;
			j = 1;
		}
	}
 
	if (j > T.length)
		return i - T.length;
	else
		return 0;
}

最坏的情况，每个子串都要对比m个字符，共n-m+1个子串，复杂度 = O((n-m+1)m) = O(nm)

注：很多时候，n >> m

35 KMP算法

例子：

主串：

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
a	b	a	a	c	a	a	b	c	a	b	a	a	b	c

模式串T：

a	b	a	a	b	c
1	2	3	4	5	6

对于模式串T = ‘abaabc’

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

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

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

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

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

当第1个元素匹配失败时，匹配下一个相邻子串，令 j=0,i++,j++;

next数组：

next[0]	next[1]	next[2]	next[3]	next[4]	next[5]	next[6]
	0	1	1	2	2	3

if(S[i] != T[j]) j=next[j];

if(j==0) {i++;j++}

next数组只和短短的模式串有关，和长长的主串无关


int Index_KMP(SString S, SString T, int next[]) {
	int i = 1, j = 1;
	while (i <= S.length && j <= T.length)
	{
		if (j == 0 || S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
 
	if (j > T.length)
		return i - T.length;
	else
		return 0;
}

KMP算法，最坏时间复杂度 O(m+n)

其中，求next数组时间复杂度O(m)，模式匹配过程最坏时间复杂度 O(n)

36 求next数组

next[1]都无脑写0

next[2]都无脑写1

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

37 KMP算法的进一步优化

模式串T

手算解题：先求next数组，再由next数组求nextval数组


	nextval[1] = 0;
	for (int j = 2; j < T.length; j++) {
		if (T.ch(next[j]) == T.ch[j])
			nextval[j] = nextval[next[j]];
		else
			nextval[j] = next[j];
 
	}

38 树的定义和基本术语

38.1 树的基本概念

空树：结点树为0的树

非空树的特点：

有且仅有一个根结点

没有后继的结点称为“叶子结点”（或终端结点）

有后继的结点称为“分支结点”（或非终端结点）

除了根结点外，任何一个结点都有且仅有一个前驱

每个结点可以有0个或多个后继

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

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

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

38.2 基本术语

38.2.1 结点之间的关系描述

父节点（双亲结点）、孩子结点、祖先结点、子孙结点、兄弟结点、堂兄弟结点

路径和路径长度。结点之间的路径是从上往下的。路径长度是路径上所经过的边的个数。

38.2.2 结点、树的属性

属性：
结点的层次（深度）—— 从上往下数
结点的高度 —— 从下往上数
树的高度（深度） —— 总共多少层
结点的度 —— 有几个孩子（分子）
树的度 —— 各结点的度的最大值

38.2.3 有序树VS无序树

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

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

38.2.4 森林

森林。森林是m（m>=0）课互不相交的树的集合

39 树的性质

常见考点1：结点数=总度数+1

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

常见考点2：度为m的数、m叉树的区别

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

m叉树——每个结点最多只能有m个孩子的树

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

常见考点3：度为m的树第i层至多有 $m^{i-1}$ 个结点（i>=1）

m叉树第i层至多有 $m^{i-1}$ 个结点（i>=1）

常见考点4：高度为h的m叉树至多有 $\frac{m^{h}-1}{m-1}$ 个结点。

常见考点5：高度为h的m叉树至少有h个结点。

高度为h、度为m的树至少有h+m-1个结点。

常见考点6：具有n个结点的m叉树的最小高度为 $log_{m}(n(m-1)+1)$

40 二叉树的定义和基本术语

40.1 二叉树的基本概念

二叉树是n（n>=0）个结点的有限集合：
1.或者为空二叉树，即n=0。
2.或者由一个根结点和两个互不相交的称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

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

40.2 几个特殊的二叉树

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

特点：
1.只有最后一层有叶子结点
2.不存在度为1的结点
3.按层序从1开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点i的父节点为 i/2（如果有的话）

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

特点：
1.只有最后两层可能有叶子结点
2.最多只有一个度为1的结点
3.同满二叉树的3
4.i<=n/2为分支结点，i>n/2为叶子结点

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

左子树上所有结点的关键字均小于根结点的关键字；

右子树上所有结点的关键字均大于根结点的关键字。

左子树和右子树又各是一棵二叉排序树。

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

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

41 二叉树的性质

41.1 二叉树的常考性质

常见考点1：设非空二叉树中度为0、1和2的结点个数分别为 $n_{0}$ 、 $n_{1}$ 和 $n_{2}$ ，则 $n_{0}=n_{2}+1$

（叶子结点比二分支结点多一个）

常见考点2：二叉树第i层至多有 $2^{i-1}$ 个结点（i>=1）

m叉树第i层至多有 $m^{i-1}$ 个结点（i>=1）

常见考点3：高度为h的二叉树至多有 $2^{h}-1$ 个结点（满二叉树）

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

41.2 完全二叉树的常考性质

常见考点1：具有n个（n>0）结点的完全二叉树的高度h为 $log_{2}(n+1)$ 或 $log_{2}n+1$

第i个结点所在层次为 $log_{2}(n+1)$ 或 $log_{2}n+1$

常见考点2：对于完全二叉树，可以由结点数n推出度为0、1和2的结点个数为 $n_{0}$ 、 $n_{1}$ 和 $n_{2}$

若完全二叉树有2k个（偶数）个结点，则必有 $n_{1} = 1$ ， $n_{0} = k$ ， $n_{2} = k-1$

若完全二叉树有2k-1个（奇数）个结点，则必有 $n_{1} = 0$ ， $n_{0} = k$ ， $n_{2} = k-1$

42 二叉树的存储结构

42.1 二叉树的顺序存储

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


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

42.2 二叉树的链式存储

n个结点的二叉链表共有n+1个空链域


#include <stdio.h>
 
struct ElemType {
	int value;
};
 
typedef struct BiTNode {
	struct ElemType data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
 
int main()
{
	//定义一棵空树
	BiTree root = NULL;
 
	//插入根结点
	root = (BiTree)malloc(sizeof(BiTNode));
	struct ElemType data = { 1 };
	root->data.value = 1;
	root->lchild = NULL;
	root->rchild = NULL;
 
	//插入新结点
	BiTNode* p = (BiTNode*)malloc(sizeof(BiTNode));
	p->data.value = 2;
	p->lchild = NULL;
	p->rchild = NULL;
	root->lchild = p;   //作为根结点的左孩子
	return 0; 
}

Tips：根据实际需求决定要不要加父结点指针


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

43 二叉树的先中后序遍历

我认为分支结点逐层展开法比较容易懂

空间复杂度都是O(n)

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

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

2.若二叉树非空：访问根结点；先序遍历左子树；先序遍历右子树


typedef struct BiTNode {
	int data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
 
void PreOrder(BiTree T) {
	if (T != NULL) {
		visit(T);   //输出值
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

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

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

2.若二叉树非空：中序遍历左子树；访问根结点；中序遍历右子树


typedef struct BiTNode {
	int data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
 
void InOrder(BiTree T) {
	if (T != NULL) {
		InOrder(T->lchild);
		visit(T);   //输出值
		InOrder(T->rchild);
	}
}

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

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

2.若二叉树非空：后序遍历左子树；后序遍历右子树；访问根结点


typedef struct BiTNode {
	int data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
 
void PostOrder(BiTree T) {
	if (T != NULL) {
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);   //输出值
	}
}

44 二叉树的层次遍历

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


//看看得了
void LevelOrder(BiTree T) {
	LinkQueue Q;
	InitQueue(&Q);
	BiTree p;
	EnQueue(&Q, T);
	while (!IsEmpty(Q))
	{
		DeQueue(&Q, p);
		visit(p);
 
		if (p->lchild != NULL)
			EnQueue(&Q, p->lchild);
 
		if (p->rchild != NULL)
			EnQueue(&Q, p->rchild);
	}
}

45 由遍历序列构造二叉树

看根结点在哪里就推出来了

前序+中序遍历序列

根结点左子树的前序遍历序列右子树的前序遍历序列

左子树的中序遍历序列根结点右子树的中序遍历序列

后序+中序遍历序列

左子树的后序遍历序列右子树的后序遍历序列根结点

左子树的中序遍历序列根结点右子树的中序遍历序列

层序+中序遍历序列

根结点左子树的根右子树的根

左子树的中序遍历序列根结点右子树的中序遍历序列

46 线索二叉树的概念

如何找到指定结点p在中序遍历序列中的中序前驱/中序后继？

思路：从根结点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点
1.当q==p时，pre为前驱
2.当pre==p时，q为后继

缺点：找前驱、后继很不方便，遍历操作必须从根结点开始


#include <stdio.h>
 
typedef struct BiTNode {
	char data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
 
//通过先序和中序遍历序列构建二叉树
BiTree buildTree(char* preorder, char* inorder, int start, int end) {
	static int preIndex = 0;
 
	if (start > end) {
		return NULL;
	}
 
	// 创建当前根节点
	BiTree root = (BiTree)malloc(sizeof(BiTNode));
	root->data = preorder[preIndex++];
	root->lchild = NULL;
	root->rchild = NULL;
 
	if (start == end) {
		return root;
	}
 
	// 在中序序列中找到根节点的索引
	int rootIndex;
	for (int i = start; i <= end; i++) {
		if (inorder[i] == root->data) {
			rootIndex = i;
			break;
		}
	}
 
	// 递归构建左子树和右子树
	root->lchild = buildTree(preorder, inorder, start, rootIndex - 1);
	root->rchild = buildTree(preorder, inorder, rootIndex + 1, end);
 
	return root;
}
 
BiTNode* p = NULL;       //找p结点的前驱
BiTNode* pre = NULL;     //当前结点前驱
BiTNode* final = NULL;   //结果指针
 
void visit(BiTNode* q) {
	if (p == q)
		final = pre;
	else
		pre = q;
}
 
void findPre(BiTree T) {
	if (T != NULL) {
		findPre(T->lchild);
		visit(T);
		findPre(T->rchild);
	}
}
 
int main() {
	char preorder[] = "ABDGECF";
	char inorder[] = "DGBEAFC";
 
	int size = sizeof(preorder) / sizeof(preorder[0]);
 
	// 构建二叉树
	BiTree root = buildTree(preorder, inorder, 0, size - 1);
 
	p = root->rchild->lchild;   //找F点的中序前驱
	findPre(root);
	printf("%c\n", final->data);
 
	return 0;
}

n个结点的二叉树，有n+1个空链域！可用来记录前驱、后继的信息

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

前驱线索（由左孩子指针充当）

后继线索（由右孩子指针充当）


struct ElemType {
	int value;
};
 
//线索链表
typedef struct ThreadNode {
	struct ElemType data;
	struct BiTNode* lchild, * rchild;
 
	//tag==0，表示指针指向孩子
	//tag==1，表示指针是“线索”
	int ltag, rtag;   //左、右线索标志
}ThreadNode, * ThreadTree;

中序线索二叉树——线索指向中序前驱、中序后继

先序线索二叉树——线索指向先序前驱、先序后继

后序线索二叉树——线索指向后序前驱、后序后继

47 二叉树的线索化

47.1 中序线索化


ThreadNode* pre = NULL;   //指向当前结点前驱
void visit(ThreadNode* q) {
	if (q->lchild == NULL) {
		q->lchild = pre;
		q->ltag = 1;
	}
 
	if (pre != NULL && pre->rchild == NULL) {
		pre->rchild = q;
		pre->rtag = 1;
	}
 
	pre = q;
}
 
void InThread(ThreadTree T) {
	if (T != NULL) {
		InThread(T->lchild);
		visit(T);
		InThread(T->rchild);
	}
}
 
void CreateInThread(ThreadTree T) {
	pre = NULL;
	if (T != NULL) {
		InThread(T);
		if (pre->rchild == NULL) {
			pre->rtag = 1;   //处理遍历的最后一个结点
		}
	}
}

47.2 先序线索化


ThreadNode* pre = NULL;   //指向当前结点前驱
void visit(ThreadNode* q) {
	if (q->lchild == NULL) {
		q->lchild = pre;
		q->ltag = 1;
	}
 
	if (pre != NULL && pre->rchild == NULL) {
		pre->rchild = q;
		pre->rtag = 1;
	}
 
	pre = q;
}
 
void PreThread(ThreadTree T) {
	if (T != NULL) {
		visit(T);
 
		if (T->ltag == 0)   //lchild不是前驱线索
			PreThread(T->lchild);
 
		PreThread(T->rchild);
	}
}
 
void CreateInThread(ThreadTree T) {
	pre = NULL;
	if (T != NULL) {
		PreThread(T);
		if (pre->rchild == NULL) {
			pre->rtag = 1;   //处理遍历的最后一个结点
		}
	}
}

47.3 后序线索化


ThreadNode* pre = NULL;   //指向当前结点前驱
void visit(ThreadNode* q) {
	if (q->lchild == NULL) {
		q->lchild = pre;
		q->ltag = 1;
	}
 
	if (pre != NULL && pre->rchild == NULL) {
		pre->rchild = q;
		pre->rtag = 1;
	}
 
	pre = q;
}
 
void PostThread(ThreadTree T) {
	if (T != NULL) {
		PostThread(T->lchild);
		PostThread(T->rchild);
		visit(T);
	}
}
 
void CreateInThread(ThreadTree T) {
	pre = NULL;
	if (T != NULL) {
		PostThread(T);
		if (pre->rchild == NULL) {
			pre->rtag = 1;   //处理遍历的最后一个结点
		}
	}
}

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

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


//找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode* firstNode(ThreadNode* p) {
	while (p->ltag == 0)   //找到最左下结点（第一个被遍历的结点）
		p = p->lchild;
	return p;
}
 
//找结点p的中序后继结点
ThreadNode* nextNode(ThreadNode* p) {
	if (p->rtag == 0)   //右结点不是后继，继续往下找，找到下一个被访问的结点
		return firstNode(p->rchild);
	else
		return p->rchild;
}
 
//对中序线索二叉树进行中序遍历（ 空间复杂度O(1) ）
void InOrder(ThreadNode* T) {
	for (ThreadNode* p = firstNode(T); p != NULL; p = nextNode(p))
		visit(p);
}

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


//找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode* lastNode(ThreadNode* p) {
	while (p->rtag == 0)   //找到最右下结点（最后一个被遍历的结点）
		p = p->rchild;
	return p;
}
 
//找结点p的中序前驱结点
ThreadNode* preNode(ThreadNode* p) {
	if (p->ltag == 0)   //左结点不是前驱，继续往下找，找到最后一个被访问的结点
		return lastNode(p->lchild);
	else
		return p->lchild;
}
 
//对中序线索二叉树进行逆向中序遍历
void RevInOrder(ThreadNode* T) {
	for (ThreadNode* p = lastNode(T); p != NULL; p = preNode(p))
		visit(p);
}

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


//找结点p的先序后继结点
ThreadNode* nextNode(ThreadNode* p) {
	if (p->rtag == 0 && p->ltag == 0)
		return p->lchild;
	else
		return p->rchild;
}

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


//找结点p的后序前驱结点
ThreadNode* preNode(ThreadNode* p) {
	if (p->ltag == 0 && p->rtag == 0)
		return p->rchild;
	else
		return p->lchild;
}

49 树的存储结构

49.1 双亲表示法（顺序存储）

双亲表示法：每个结点中保存指向双亲的“指针”

删除结点：把数组最后一个元素移到要删除结点的位置，结点数n--；

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

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


#define MAX_TREE_SIZE 100
 
typedef struct PTNode {
	int data;
	int parent;   //指向双亲下标，-1表示没有双亲
}PTNode;
 
typedef struct PTree {
	PTNode nodes[MAX_TREE_SIZE];
	int n;   //结点数
};

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

孩子表示法：顺序存储各结点，每个结点中保存孩子链表头指针


#define MAX_TREE_SIZE 100
 
struct CTNode {
	int child;             //孩子结点在数组中的位置
	struct CTNode* next;   //下一个孩子
};
 
typedef struct CTBox {
	int data;
	struct CTNode* firstChild;   //第一个孩子
}CTBox;
 
typedef struct CTree {
	CTBox nodes[MAX_TREE_SIZE];
	int n, r;   //结点数和根的位置
}CTree;

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


typedef struct CSNode {
	int data;
	struct CSNode* firstchild;    //指向左孩子
	struct CSNode* nextsibling;   //指向右兄弟
}CSNode, * CSTree;

49.4 森林和二叉树的转换

1.把各个树用孩子兄弟表示法转换成二叉树

2.再把各个树的根结点视为兄弟关系，用孩子兄弟表示法连接起来

50 树和森林的遍历

50.1 树的先根遍历

先根遍历（深度优先遍历）。若树非空，先访问根结点，再依次对每棵子树进行先根遍历。

树的先根遍历序列与这棵树相应二叉树的先序序列相同。

50.2 树的后根遍历

后根遍历（深度优先遍历）。若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。

树的后根遍历序列与这棵树相应二叉树的中序序列相同。

50.3 树的层次遍历

层次遍历（广度优先遍历）（用队列实现）

1.若树非空，则根结点入队

2.若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

3.重复2直到队列为空

50.4 森林的先序遍历

1.先把森林用孩子兄弟表示法转成二叉树

2.再对二叉树进行先序遍历

50.5 森林的中序遍历

1.先把森林用孩子兄弟表示法转成二叉树

2.再对二叉树进行中序遍历

51 哈夫曼树

51.1 带权路径长度

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

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

树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL，Weighted Path Length）

51.2 哈夫曼树的定义

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

51.3 哈夫曼树的构造

每次选两个根结点权值最小的树合并。并将二者权值之和作为新的根结点的权值

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

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

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

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

51.4 哈夫曼编码

固定长度编码——每个字符用相等长度的二进制表示

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

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

由哈夫曼树得到哈夫曼编码——字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树

52 并查集

52.1 “并查集”的代码实现

用互不相交的树（森林），表示多个“集合”，使用双亲表示法存储各个集合

集合的两个基本操作——“并”和“查”

Find——“查”操作，确定一个指定元素所属集合

Union——“并”操作，将两个不相交的集合合并为一个

若结点树为n：Find最坏时间复杂度为O(n)，Union时间复杂度为O(1)


#define SIZE 13 
int UFSets[SIZE];  //集合元素数组
void initial(int S[]) {
	for (int i = 0; i < SIZE; i++)
		S[i] = -1;
}
 
//Find“查”操作，找x所属集合（返回x所属根结点）
//x   查找元素的下标
int Find(int S[], int x) {
	while (S[x] >= 0)
	{
		x = S[x];
	}
 
	return x;
}
 
//Union“并”操作，将两个集合合并为一个
void Union(int S[], int Root1, int Root2) {
	if (Root1 == Root2)  //要求Root1与Root2是不同的集合
		return;
 
	S[Root2] = Root1;    //将根Root2连接到另一个根Root1下面
}

52.2 Union操作的优化

优化思路：在每次Union操作构建树的时候，尽可能让树不长高。

1.用根结点的绝对值表示树的结点总数

2.Union操作，让小树合并到大树

该方法构造的树高不超过 $[log_{2}n]+1$ ，所以Find最坏时间复杂度 $O(log_{2}n)$


//Union“并”操作，小数合并到大树
void Union(int S[], int Root1, int Root2) {
	if (Root1 == Root2)  //要求Root1与Root2是不同的集合
		return;
 
	if (S[Root2] >= S[Root1]) {  //Root2结点数更少，用负数表示结点总数
		S[Root1] += S[Root2];
		S[Root2] = Root1;
	}
	else
	{
		S[Root2] += S[Root1];
		S[Root1] = Root2;
	}
}

52.3 Find操作的优化（压缩路径）

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

每次Find操作，先找根，再“压缩路径”，可使树的高度不超过O( a(n) )。a(n)是一个增长很缓慢的函数，对于常见的n值，通常a(n)<=4，所以Find的最坏时间复杂度O( a(n) ) <= O(4)


//Find“查”操作，先找到根结点，再进行“压缩路径”
//x   查找元素的下标
int Find(int S[], int x) {
	int root = x;
	while (S[root] >= 0)
	{
		root = S[root];
	}
 
	//压缩路径
	while (x!=root)
	{
		int t = S[x];
		S[x] = root;
		x = t;
	}
 
	return root;
}

408快乐网站：Data Structure Visualization

53 图的基本概念

53.1 图的定义

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

53.2 无向图、有向图

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

G2=(V2,E2)
V2 ={A, B,C,D,E}
E2= {(A, B), (B, D), (B, E),(C, D), (C, E), (D, E)

若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v, w>，其中v、w是顶点，v称为弧尾，w称为弧头，<v, w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。<v, w>≠<w, v>

G1=(V1, E1)
V1={A, B,C,D,E}
E1= {<A, B>,<A,C>,<A,D>,<A, E>,<B,A>,<B,C>,<B,E>,<C, D>}

53.3 简单图、多重图

简单图—―1.不存在重复边；2.不存在顶点到自身的边

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

53.4 顶点的度、入度、出度

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

对于有向图：
入度是以顶点v为终点的有向边的数目，记为ID(v);
出度是以顶点v为起点的有向边的数目，记为OD(v)。
顶点v的度等于其入度和出度之和，即TD(v) = ID(v)+OD(v)。

53.5 顶点-顶点的关系描述

路径――顶点Vp到顶点Vq之间的一条路径是指顶点序列，Vp, Vi1, Vi2,..., Vim, Vq

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

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

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

路径长度――路径上边的数目

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

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

有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

53.6 连通图、强连通图

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

常见考点:
对于n个顶点的无向图G，
若G是连通图，则最少有n-1条边
若G是非连通图，则最多可能有 $C_{n-1}^{2}$ 条边

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

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

53.7 图的局部

设有两个图G = (V，E)和G' = (V'，E')，若V'是V的子集，且E'是E的子集，则称G'是G的子图。

若有满足v(G') = V(G)的子图G'，则称其为G的生成子图

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

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

边尽可能的少，但要保持连通
连通图的生成树是包含图中全部顶点的一个极小连通子图

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

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

边的权――在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图/网――边上带有权值的图称为带权图，也称网。
带权路径长度――当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

53.8 几种特殊形态的图

无向完全图――无向图中任意两个顶点之间都存在边
若无向图的顶点数|V|=n，则|E|∈[0, $C_{n}^{2}$ ] = [0, n(n-1)/2]

有向完全图――有向图中任意两个顶点之间都存在方向相反的两条弧
若有向图的顶点数|V|=n，则|E|∈[0, $2C_{n}^{2}$ ] = [0, n(n-1)]

边数很少的图称为稀疏图，反之称为稠密图
没有绝对的界限，一般来说|E| < |V| log|V|时，可以将G视为稀疏图

树――不存在回路，且连通的无向图
n个顶点的树，必有n-1条边。
常见考点：n个顶点的图，若 |E| > n-1，则一定有回路

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

常见考点：
对于n个顶点的无向图G：

所有顶点的度之和=2|E|

若G是连通图，则最少有n-1条边（树)，若|E|>n-1，则一定有回路

若G是非连通图，则最多可能有 $C_{n-1}^{2}$ 条边

无向完全图共有 $C_{n}^{2}$ 条边

对于n个顶点的有向图G：

所有顶点的出度之和=入度之和=|EI

所有顶点的度之和=2|EI

若G是强连通图，则最少有n条边（形成回路)

有向完全图共有 $2C_{n}^{2}$ 条边

54 邻接矩阵法

结点数为n的图G=(V,E)的邻接矩阵A是nxn的。将G的顶点编号为V1, V2,..., Vn，则
A[i][j]=1，若(Vi,Vj)或<Vi,Vj>是E(G)中的边
A[i][j]=0，若(Vi,Vj)或<Vi,Vj>不是E(G)中的边

无向图：第i个结点的度 = 第i行（或第i列）的非零元素个数

有向图：
第i个结点的出度 = 第i行的非零元素个数
第i个结点的入度 = 第i列的非零元素个数
第i个结点的度 = 第i行、第i列的非零元素个数之和

邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(IVI)

空间复杂度:O( $\left | V\right |^{2}$ )――只和顶点数相关，和实际的边数无关

适合用于存储稠密图

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

设图G的邻接矩阵为A（矩阵元素为0/1），则 $A^{n}$ 的元素 $A^{n}$ [i][j]等于由顶点i到顶点j的长度为n的路径的数目


#define MaxVertexNum 100                    //顶点数目最大值
typedef struct MGraph {
	char Vex[MaxVertexNum];                 //顶点表
	int Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵，边表
	int vexnum, arcnum;                     //图的当前顶点数和边数/弧数
}MGraph;

55 邻接表法

无向图：边结点的数量是2|E|,整体空间复杂度为O(IV| + 2|El)

有向图：边结点的数量是|E|,整体空间复杂度为O(IV| + |El)

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


#define MaxVertexNum 100
 
//“边/弧”
typedef struct ArcNode {
	int adjvex;             //边/弧指向哪个结点下标
	struct ArcNode* next;   //指向下一条弧的指针
	//InfoType info;        //边权值
}ArcNode;
 
//“顶点”
typedef struct VNode {
	char data;       //顶点信息
	ArcNode* first;  //第一条边/弧
}VNode, AdjList[MaxVertexNum];
 
//用邻接表存储的图
typedef struct ALGragh {
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

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

56 十字链表、邻接多重表

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

57 图的基本操作

Adjacent(G,x,y)：判断图G是否存在边<x, y>或(x, y)。

无向图：邻接矩阵O(1) ，邻接表O(1)~O(|V|)

有向图：邻接矩阵O(1) ，邻接表O(1)~O(|V|)

Neighbors(G,x)：列出图G中与结点x邻接的边。

无向图：邻接矩阵O(|V|)，邻接表O(1)~O(|V|)

有向图：邻接矩阵O(|V|)，邻接表出边O(1)~O(|V|)，入边O(|E|)

InsertVertex(G,x)：在图G中插入顶点x。

无向图：邻接矩阵O(1)，邻接表O(1)

有向图：邻接矩阵O(1)，邻接表O(1)

DeleteVertex(G,x)：从图G中删除顶点x。

无向图：邻接矩阵O(|V|)，邻接表O(1)~O(|E|)

有向图：邻接矩阵O(|V|)，邻接表删出边O(1)~O(|V|)，删入边O(|E|)

AddEdge(G,x,y)：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。

无向图：邻接矩阵O(1)，邻接表O(1)

有向图：邻接矩阵O(1)，邻接表O(1)

RemoveEdge(G,x,y)：若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。

无向图：邻接矩阵O(1)，邻接表O(1)

有向图：邻接矩阵O(1)，邻接表O(1)

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

无向图：邻接矩阵O(1)~O(|V|)，邻接表O(1)

有向图：邻接矩阵O(1)~O(|V|)，邻接表找出边邻接点O(1)，~~找入边邻接点~~O(1)~O(|E|)

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

无向图：邻接矩阵O(1)~O(|V|)，邻接表O(1)

Get_edge_value(G,x,y)：获取图G中边(x, y)或<x, y>对应的权值。

Set_edge_value(G,x,y,v)：设置图G中边(x, y)或<x, y>对应的权值为v。

无向图：邻接矩阵O(1)，邻接表O(1)~O(|V|)

58 图的广度优先遍历

58.1 代码实现

广度优先遍历(Breadth-First-Search, BFS)要点：
1．找到与一个顶点相邻的所有顶点
2．标记哪些顶点被访问过
3．需要一个辅助队列

FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。


int visited[MaxVertexNum];  //访问标记数组，初始都为0
 
//如果是非连通图，则无法遍历完所有结点
void BFS(Graph G, int v) {
	visit(v);
	visited[v] = 1;   //对v做已访问标记
	Enqueue(Q, v);
	while (!isEmpty(Q))
	{
		DeQueue(Q, v);
		for (int w = FirstNeighbor(G, v); w >= 0; w = NexNeighbor(G, v, w)) {
			if (!visited[w]) {
				visit(w);
				visited[w] = 1;
				EnQueue(Q, w);
			}
		}
	}
}

58.2 BFS算法（Final版）

对于无向图，调用BFS函数的次数=连通分量数

空间复杂度:最坏情况，辅助队列大小为O(|V|)

邻接矩阵存储的图:
访问 |V| 个顶点需要O(|V|)的时间
查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点
时间复杂度=O( $\left | V^{2} \right |$ )

邻接表存储的图:
访问 |V| 个顶点需要O(|V|)的时间
查找各个顶点的邻接点共需要O(|E|)的时间,
时间复杂度=O(|V|+|E|)


int visited[MaxVertexNum];  //访问标记数组，初始都为0
 
void BFS(Graph G, int v) {
	visit(v);
	visited[v] = 1;   //对v做已访问标记
	Enqueue(Q, v);
	while (!isEmpty(Q))
	{
		DeQueue(Q, v);
		for (int w = FirstNeighbor(G, v); w >= 0; w = NexNeighbor(G, v, w)) {
			if (!visited[w]) {
				visit(w);
				visited[w] = 1;
				EnQueue(Q, w);
			}
		}
	}
}
 
void BFSTraverse(Graph G) {
	for (int i = 0; i < G.vexnum; i++) {
		visited[i] = 0;   //初始化
	}
 
	InitQueue(Q);
	for (int i = 0; i < G.vexnum; i++) {   //从0号顶点开始遍历
		if (!visited[i]) {                 //对每个连通分量调用一次BFS
			BFS(G, i); 
		}
	}
}

58.3 广度优先生成树

广度优先生成树：由广度优先遍历确定的树

邻接表存储的图表示方式不唯一，遍历序列，生成树也不唯一

遍历非连通图可得广度优先生成森林

59 图的深度优先遍历

59.1 代码实现


int visited[MaxVertexNum];  //访问标记数组，初始都为0
 
//如果是非连通图，则无法遍历完所有结点
void DFS(Graph G, int v) {
	visit(v);
	visited[v] = 1;   //对v做已访问标记
 
	for (int w = FirstNeighbor(G, v); w >= 0; w = NexNeighbor(G, v, w)) {
		if (!visited[w]) {
			DFS(G, w);
		}
	}
}

59.2 DFS算法（Final版）

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

时间复杂度=访问各结点所需时间+探索各条边所需时间
邻接矩阵存储的图:
访问 |V| 个顶点需要O(|V|)的时间
查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点
时间复杂度=O( $\left | V^{2} \right |$ )

邻接表存储的图:
访问 |V| 个顶点需要O(|V|)的时间
查找各个顶点的邻接点共需要O(|E|)的时间,
时间复杂度=O(|V|+|E|)


int visited[MaxVertexNum];  //访问标记数组，初始都为0
 
void DFS(Graph G, int v) {
	visit(v);
	visited[v] = 1;   //对v做已访问标记
 
	for (int w = FirstNeighbor(G, v); w >= 0; w = NexNeighbor(G, v, w)) {
		if (!visited[w]) {
			DFS(G, w);
		}
	}
}
 
void DFSTraverse(Graph G) {
	for (int i = 0; i < G.vexnum; i++) {
		visited[i] = 0;   //初始化
	}
 
	for (int i = 0; i < G.vexnum; i++) {   //从0号顶点开始遍历
		if (!visited[i]) {               
			DFS(G, i);
		}
	}
}

59.3 深度优先生成树

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，深度优先生成树也唯一

同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，深度优先生成树也不唯一

59.4 图的遍历与图的连通性

对无向图进行BFS/DFS遍历
调用BFS/DFS函数的次数=连通分量数
对于连通图，只需调用1次BFS/DFS

对有向图进行BFS/DFS遍历
调用BFS/DFS函数的次数要具体问题具体分析；若起始顶点到其他各顶点都有路径，则只需调用1次BFS/DFS函数

60 最小生成树

60.1 最小生成树概念

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

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

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

60.2 Prim算法（普利姆）

Prim算法（普里姆)：
从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

算法的实现思想：从Vo开始，总共需要n-1轮处理
每一轮处理︰循环遍历所有个结点，找到lowCast最低的，且还没加入树的顶点。
再次循环遍历，更新还没加入的各个顶点的lowCast值，每一轮时间复杂度O(2n)

时间复杂度：O( $\left | V^{2} \right |$ )，适合用于边稠密图

60.3 Kruskal算法（克鲁斯卡尔）

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

算法的实现思想：初始：将各条边按权值排序
共执行e轮，每轮判断两个顶点是否属于同一集合，需要O( $log_{2}e$ )

时间复杂度:O( $|E|log_{2}|E|$ )，适合用于边稀疏图

61 最短路径问题_BFS算法


int visited[MaxVertexNum];   //访问标记数组，初始都为0
int d[MaxVertexNum];        //路径长度数组
int path[MaxVertexNum];     //最短路径从哪个顶点过来
 
//BSF求无权图的单源最短路径
void BFS_MIN_Distance(Graph G, int u) {
	for (int i = 0; i < G.vexnum; i++) {
		d[i] = INT_MAX;
		path[i] = -1;
	}
 
	d[u] = 0;
	visited[u] = 1;   
	Enqueue(Q, u);
	while (!isEmpty(Q))
	{
		DeQueue(Q, u);
		for (int w = FirstNeighbor(G, u); w >= 0; w = NexNeighbor(G, u, w)) {
			if (!visited[w]) {
				d[w] = d[u] + 1;   //路径长度加1
				path[w] = u;       //最短路径应从u到w
				visited[w] = 1;
				EnQueue(Q, w);
			}
		}
	}
}

62 最短路径问题_Dijkstra算法

初始：
若从Vo开始，令final[0]=ture; dist[0]=O; path[0]=-1。
其余顶点final[k]=false; dist[k]=arcs[0][k]; path[k]= (arcs[0][k]==INT_MAX) ? -1:0

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

时间复杂度:O( $n^{2}$ )即O( $\left |V \right |^{2}$ )

Dijkstra算法不适用于有负权值的带权图


void Dijkstra(int numNodes, int arcs[MaxVertexNum][MaxVertexNum],
              int start, bool final[], int dist[], int path[]) {
    int i, j;
 
    // 初始化final数组、dist数组和path数组
    for (i = 0; i < numNodes; i++) {
        final[i] = false;
        dist[i] = arcs[start][i];
        path[i] = (arcs[start][i] == INT_MAX) ? -1 : start;
    }
 
    // 设置起点信息
    final[start] = true;
    dist[start] = 0;
 
    for (i = 0; i < numNodes - 1; i++) {
        int minDist = INT_MAX;
        int minIndex = -1;
 
        // 查找最短距离顶点
        for (j = 0; j < numNodes; j++) {
            if (!final[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }
 
        if (minIndex == -1) {
            break;
        }
 
        // 标记最短距离顶点为已访问
        final[minIndex] = true;
 
        // 更新邻接节点的最短距离和路径
        for (j = 0; j < numNodes; j++) {
            if (!final[j] && dist[minIndex] + arcs[minIndex][j] < dist[j]) {
                dist[j] = dist[minIndex] + arcs[minIndex][j];
                path[j] = minIndex;
            }
        }
    }
}

63 最短路径问题_Floyd算法

Floyd算法：求出每一对顶点之间的最短路径
使用动态规划思想，将问题的求解分为多个阶段
对于n个顶点的图G，求任意一对顶点Vi —> Vj之间的最短路径可分为如下几个阶段：
#初始：不允许在其他顶点中转，最短路径是?
#0：若允许在Vo中转，最短路径是?
#1：若允许在Vo、V1中转，最短路径是?
#2：若允许在Vo、V1、V2中转，最短路径是?
......
#n-1：若允许在Vo、V1、V2 ......Vn-1中转，最短路径是?

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

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


//准备工作，根据图的信息初始化矩阵A和path
int A[n];     //矩阵各顶点之间的路径
int path[n];  //中转点
for (int k = 0; k < n; k++) {   //考虑以k为中转点
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (A[i][j] > A[i][k] + A[k][j]) {
				A[i][j] = A[i][k] + A[k][j];
				path[i][j] = k;
			}
		}
	}
}

	BFS算法	Dijkstra算法	Floyd算法
无权图	✔	✔	✔
带权图	×	✔	✔
带负权值的图	×	×	✔
带负权回路的图	×	×	×
时间复杂度	O( $\left \| V \right \|^{2}$ )或O(\|V\|+\|E\|)	O( $\left \| V \right \|^{2}$ )	O( $\left \| V \right \|^{3}$ )
通常用于	求无权图的单源最短路径	求带权图的单源最短路径	求带权图中各顶点间的最短路径

注∶也可用Dijkstra算法求所有顶点间的最短路径，重复|V|次即可，总的时间复杂度也是O( $\left | V \right |^{3}$ )

64 有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph)

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

65 拓扑排序

65.1 AOV网

AOV网(Activity On Vertex Network，用顶点表示活动的网):
用DAG图（有向无环图）表示一个工程。顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行

65.2 拓扑排序的实现

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序:
① 每个顶点出现且只出现一次。
② 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
或定义为︰拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

拓扑排序的实现:
①从AOV网中选择一个没有前驱（入度为0）的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

当前所有顶点入度>0，说明原图存在回路

采用邻接表时间复杂度:O(|V|+|E|)
若采用邻接矩阵，则需O( $\left | V \right |^{2}$ )


#define MaxVertexNum 100
#define VertexNum 5
 
//“边/弧”
typedef struct ArcNode {
	int adjvex;             //边/弧指向哪个结点下标
	struct ArcNode* next;   //指向下一条弧的指针
	//InfoType info;        //边权值
}ArcNode;
 
//“顶点”
typedef struct VNode {
	char data;       //顶点信息
	ArcNode* first;  //第一条边/弧
}VNode, AdjList[MaxVertexNum];
 
//用邻接表存储的图
typedef struct ALGragh {
	AdjList vertices;
	int vexnum, arcnum;
}Graph;
 
 
int indegree[VertexNum];   //顶点的入度数
int print[VertexNum];      //记录拓扑序列
 
bool TopologicalSort(Graph G) {
	InitStack(S);   //初始化栈，存储入度为0的顶点
 
	int i = 0;
	for (i = 0; i < G.vexnum; i++) {
		if (indegree[i] == 0) {
			Push(S, i);
		}
	}
 
	int count = 0;   //记录当前已经输出的顶点数
	int v = 0;       //下一个顶点下标
	while (!isEmpty(S))
	{
		Pop(S, i);
		print[count++] = i;
		for (ArcNode* p = G.vertices[i].first; p; p = p->next) {
			//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
			v = p->adjvex;
			if (!(--indegree[v])) {
				Push(S, v);
			}
		}
	}
 
	if (count < G.vexnum)
		return false;   //排序失败，有向图中有回路
	else
		return true;
}

65.3 逆拓扑排序

对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序∶
①从AOV网中选择一个没有后继（出度为0）的顶点并输出。
②从网中删除该顶点和所有以它为终点的有向边。
③重复①和②直到当前的AOV网为空。

图用逆邻接表存储

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


int visited[MaxVertexNum];  //访问标记数组，初始都为0
 
void DFS(Graph G, int v) {
	visited[v] = 1;   //对v做已访问标记
 
	for (int w = FirstNeighbor(G, v); w >= 0; w = NexNeighbor(G, v, w)) {
		if (!visited[w]) {
			DFS(G, w);
		}
		else
		{
			println("有回路，不存在逆拓扑排序");
			break;
		}
	}
 
	print(v);   //输出顶点，逆拓扑排序序列
}
 
void DFSTraverse(Graph G) {
	for (int i = 0; i < G.vexnum; i++) {
		visited[i] = 0;   //初始化
	}
 
	for (int i = 0; i < G.vexnum; i++) {   //从0号顶点开始遍历
		if (!visited[i]) {
			DFS(G, i);
		}
	}
}

66 关键路径

66.1 AOE网

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

AOE网具有以下两个性质:
①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的

在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始;
也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。

66.2 关键路径

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

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

事件vk的最早发生时间ve(k)——决定了所有从vk开始的活动能够开工的最早时间
活动ai的最早开始时间e(i)——指该活动弧的起点所表示的事件的最早发生时间

事件vk的最迟发生时间vl(k)——它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。
活动ai的最迟开始时间l(i)——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。

活动ai的时间余量d(i)=l(i)-e(i)，表示在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间

若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i)=e(i)的活动ai是关键活动
由关键活动组成的路径就是关键路径

66.3 求关键路径的步骤

① 求所有事件的最早发生时间ve()
② 求所有事件的最迟发生时间vl()
③ 求所有活动的最早发生时间e()
④ 求所有活动的最迟发生时间I()
⑤ 求所有活动的时间余量d()；d(i)=0的活动就是关键活动，由关键活动可得关键路径

66.4 关键活动、关键路径的特征

若关键活动耗时增加，则整个工程的工期将增长
缩短关键活动的时间，可以缩短整个工程的工期
当缩短到一定程度时，关键活动可能会变成非关键活动

可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

67 查找的基本概念

67.1 基本概念

查找 — 在数据集合中寻找满足某种条件的数据元素的过程称为查找

查找表(查找结构) — 用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录〉组成

关键字 — 数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

67.2 对查找表的常见操作

①查找符合条件的数据元素
②插入、删除某个数据元素

只需进行操作① — 静态查找表仅关注查找速度即可

也要进行操作② — 动态查找表除了查找速度，也要关注插/删操作是否方便实现

67.3 查找算法的评价指标

查找长度 —— 在查找运算中，需要对比关键字的次数称为查找长度
平均查找长度(ASL,Average Search Length) —— 所有查找过程中进行关键字的比较次数的平均值

ASL的数量级反应了查找算法时间复杂度

评价一个查找算法的效率时，通常考虑查找成功/查找失败，两种情况的ASL

68 顺序查找

68.1 顺序查找的算法思想

顺序查找，又叫“线性查找”，通常用于线性表。

算法思想∶从头到jio 挨个找(或者反过来也OK)

68.2 顺序查找的实现


typedef struct {      //查找表的数据结构（顺序表）
	ElemType* elem;   //动态数组基址
	int TableLen;     //表的长度
}SSTable;
 
//顺序查找
int Search_Seq(SSTable ST, ElemType key) {
	int i;
	for (i = 0; i < ST.TableLen && ST.elem[i] != key; i++);
	//查找成功，则返回元素下标；查找失败，则返回-1
	return i == ST.TableLen ? -1 : i;
}

68.3 顺序查找的实现（哨兵）


typedef struct {      //查找表的数据结构（顺序表）
	ElemType* elem;   //动态数组基址
	int TableLen;     //表的长度
}SSTable;
 
//顺序查找
int Search_Seq(SSTable ST, ElemType key) {
	ST.elem[0] = key;   //“哨兵”
	int i;
	for (i = ST.TableLen; ST.elem[i] != key; i--);   //从后往前找
	//查找成功，则返回元素下标；查找失败，则返回0
	return i;
}

0号位置存“哨兵”

优点：无需判断是否越界，效率更高

68.4 查找效率分析

$ASL=\sum_{i=1}^{n}P_{i}C_{i}$

ASL成功 = (1+2+3+...+n)/2 = (n+1)/2

ASL失败 = n+1

68.5 顺序查找的优化（对有序表）

ASL失败 = (1+2+3+...+n+n)/n+1 = n/2 + n/n+1

68.6 用查找判定树分析ASL

一个成功结点的查找长度=自身所在层数

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

68.7 顺序查找的优化（被查概率不相等）

ASL成功 = 1*0.15 + 2*0.05 + 3*0.1 + 4*0.4 + 5*0.28 + 6*0.02 = 3.67

ASL成功 = 1*0.4 + 2*0.28 + 3*0.15 + 4*0.1 + 5*0.05 + 6*0.02 = 2.18

69 折半查找

69.1 折半查找的算法思想

折半查找，又称“二分查找”，仅适用于有序的顺序表。

顺序表拥有随机访问的特性，链表没有，所以链表不能进行二分查找

69.2 折半查找的实现


typedef struct {      //查找表的数据结构（顺序表)
	ElemType* elem;   //动态数组基址
	int TableLen;    //表的长度
}SSTable;
 
//折半查找
int Binary_search(SSTable L, ElemType key) {
	int low = 0, high = L.TableLen - 1, mid;
	while (low <= high) {
		mid = (low + high) / 2;   //取中间位置
 
		if (L.elem[mid] == key)   //查找成功则返回所在位置
			return mid;
		else if (L.elem[mid] > key)
			high = mid - 1;   //从前半部分继续查找
		else
			low = mid + 1;   //从后半部分继续查找
	}
	
	return -1;   //查找失败，返回-1
}

69.3 查找效率分析

ASL成功 = (1*1+2*2+3*4+4*4)/11 = 3

ASL失败 = (3*4+4*8)/12 = 11/3

69.4 折半查找判定树的构造

mid = [(low + high)/2]

如果当前low和high之间有奇数个元素，则mid分隔后，左右两部分元素个数相等

mid = [(low + high)/2]

如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分少一个元素

折半查找的判定树中，若mid = [(low + high)/2]，则对于任何一个结点，必有:
右子树结点数-左子树结点数=0或1

折半查找的判定树一定是平衡二叉树

折半查找的判定树中，只有最下面一层是不满的，因此，元素个数为n时树高h = [log (n + 1)]
注：计算方法同“完全二叉树”

判定树结点关键字：左<中<右，满足二叉排序树的定义
失败结点：n+1个（等于成功结点的空链域数量）

69.5 折半查找的查找效率

树高h =「log (n +1)] 注：该树高不包含失败结点

查找成功的ASL <= h
查找失败的ASL <= h

折半查找的时间复杂度 = O(log n)

69.6 扩展思考

折半查找时间复杂度=O(log n)，顺序查找的时间复杂度=O(n)
辣么，折半查找的速度一定比顺序查找更快? 答：不是

如果mid=「(low + high)/2]（向上取整），辣么，判定树是什么亚子?

如果当前low和high之间有奇数个元素，则mid分隔后，左右两部分元素个数相等

如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分多一个元素

折半查找的判定树中，若mid =[(low + high)/2]，则对于任何一个结点，必有:
左子树结点数-右子树结点数=0或1

70 分块查找

70.1 分块查找的算法思想

特点：块内无序、块间有序


// 索引表
typedef struct {
	ElemType maxValue; 
	int low, high;
}Index;
 
//顺序表存储实际元素
ElemType List[100];

分块查找，又称索引顺序查找，算法过程如下：
①在索引表中确定待查记录所属的分块（可顺序、可折半)
②在块内顺序查找

70.2 用折半查找查索引

若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指分块中查找

low超出索引表范围，查找失败

70.3 查找效率分析(ASL)

共有14个元素，各自被查概率为1/14
若索引表采用顺序查找，则7：2次、10：3次、13：3次...
若索引表采用折半查找，则30：4次、27：2次?

查找失败的情况更复杂...一般不考

假设，长度为n的查找表被均匀地分为b块，每块s个元素
设索引查找和块内查找的平均查找长度分别为Li、Ls，则分块查找的平均查找长度为 ASL=Li + Ls

用顺序查找查索引表，则Li = (1+2+...+b)/b = (b+1)/2，Ls = (1+2+...+s)/s = (s+1)/2

则ASL = (b+1)/2 + (s+1)/2 = s^2+2s+n/2s，当 $s=\sqrt{n}$ 时，ASL最小= $\sqrt{n}+1$

70.4 扩展思考

若查找表是“动态查找表”,有木有更好的实现方式? —― 链式存储

71 二叉排序树

71.1 二叉排序树的定义

二叉排序树，又称二叉查找树(BST，Binary Search Tree)
一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
左子树上所有结点的关键字均小于根结点的关键字；
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。

左子树结点值 < 根结点值 < 右子树结点值 ——> 进行中序遍历，可以得到一个递增的有序序列

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

71.2 二叉排序树的查找

若树非空，目标值与根结点的值比较；若相等，则查找成功；若小于根结点，则在左子树上查找，否则在右子树上查找。查找成功，返回结点指针;查找失败返回NULL


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


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

71.3 二叉排序树的插入

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


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

71.4 二叉排序树的构造


// 在二叉排序树插入关键字为k的新结点（递归实现)，最坏环空间复杂度O(h)
int BST_Insert(BSTree& T, int k) {
	if (T == NULL) {        //原树为空，新插入的结点为根结点
		T = (BSTree)malloc(sizeof(BSTNode));
		T->key = k;
		T->lchild = T->rchild = NULL;
		return 1;           //返回1，插入成功
	}
	else if (k == T->key)   //树中存在相同关键字的结点，插入失败
		return 0;
	else if (k < T->key)    // 插入到T的左子树
		return BST_Insert(T->lchild, k);
	else                    //插入到T的右子树
		return BST_Insert(T->rchild, k);
}
 
// 按照str[]中的关键字序列建立二叉排序树
void Creat_BST(BSTree& T, int str[], int n) {
	T = NULL;   // 初始时T为空树
 
	int i = 0;
	while (i < n) {   //依次将每个关键字插入到二叉排序树中
		BST_Insert(T, str[i]);
		i++;
	}
}

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

71.5 二叉排序树的删除

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

71.6 查找效率分析

查找长度――在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度

若树高h，找到最下层的一个结点需要对比h次

最好情况：n个结点的二叉树最小高度为[log n] + 1。平均查找长度=O(log n)

最坏情况：每个结点只有一个分支，树高h=结点数n。平均查找长度=O(n)

所以构建二叉排序树尽量构建成平衡二叉树

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

72 平衡二叉树

72.1 平衡二叉树的定义

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

结点的平衡因子 = 左子树高 - 右子树高。
平衡二叉树结点的平衡因子的值只可能是-1、0或1。
只要有任一结点的平衡因子绝对值大于1,就不是平衡二叉树


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

72.2 平衡二叉树的插入

在二叉排序树中插入新结点后，如何保持平衡?
查找路径上的所有结点都有可能受到影响
从插入点往回找到第一个不平衡结点，调整以该结点为根的子树
每次调整的对象都是“最小不平衡子树”
在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡

72.3 调整最小不平衡子树(LL)

LL平衡旋转（右单旋转）。由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。

代码思路
实现A向右下旋转，B向右上旋转（只有左孩子才能右上旋）：
其中 A是爹，B为左孩子，ga为A他爹
①A->lchild = B->rchild；
②B->rchild = A；
③ga->lchild/rchild = B

72.4 调整最小不平衡子树(RR)

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

代码思路
实现A向左下旋转，B向左上旋转（只有右孩子才能左上旋）：
其中A是爹，B为右孩子，ga为A他爹
①A->rchild = B->lchild；
②B->lchild = A；
③ga->lchild/rchild = B

72.5 调整最小不平衡子树(LR)

LR平衡旋转（先左后右双旋转）。由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置（对于插入的是C的左结点也一样）

72.6 调整最小不平衡子树(RL)

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

72.7 查找效率分析

若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找操作的时间复杂度不可能超过O(h)

平衡二叉树 ―― 树上任一结点的左子树和右子树的高度之差不超过1。
假设以 $n_{h}$ 表示深度为h的平衡树中含有的最少结点数。
则有 $n_{0}=0,n_{1}=1,n_{2}=2$ ，并且有 $n_{h}=n_{h-1}+n_{h-2}+1$
可以证明含有n个结点的平衡二叉树的最大深度为O(log n)，平衡二叉树的平均查找长度为O(log n)

73 平衡二叉树的删除

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

①删除结点（方法同“二叉排序树”)
·若删除的结点是叶子，直接删。
·若删除的结点只有一个子树，用子树顶替删除位置
·若删除的结点有两棵子树，用前驱（或后继）结点顶替，并转换为对前驱（或后继）结点的删除。

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

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

④根据孙子的位置，调整平衡（LL/RR/LR/RL)
平衡二叉树删除操作时间复杂度-o(log2n)
·孙子在LL：儿子右单旋
·孙子在RR：儿子左单旋
·孙子在LR：孙子先左旋，再右旋
·孙子在RL：孙子先右旋，再左旋

⑤如果不平衡向上传导，继续②
·对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传递)

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

74 红黑树的定义和性质

74.1 为什么要发明红黑树

平衡二叉树 AVL：插入/删除很容易破坏“平衡”特性，需要频繁调整树的形态。如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大)，再进行LL/RR/LR/RL调整

红黑树 RBT：插入/删除很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成

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

74.2 红黑树大概会怎么考?

红黑树的定义、性质――选择题
红黑树的插入/删除――要能手绘插入过程（不太可能考代码，略复杂），删除操作也比较麻烦，也许不考

74.3 红黑树的定义

红黑树是二叉排序树 ——> 左子树结点值≤根结点值≤右子树结点值

与普通BST相比，有什么要求
①每个结点或是红色，或是黑色的
②根节点是黑色的
③叶结点（外部结点、NULL结点、失败结点）均是黑色的
④不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色）
⑤对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同


struct RBnode {       //红黑树的结点定义
	int key;          //关键字的值
	RBnode* parent;   //父节点指针
	RBnode* lchild;   //左孩子指针
	RBnode* rchild;   //右孩子指针
	int color;       //结点颜色，如:可用0/1表示黑/红，也可使用枚举型enum表示颜色
}

口诀：左根右，根叶黑，不红红，黑路同

74.4 补充概念:结点的“黑高”

结点的黑高 bh ―― 从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数

74.5 红黑树的性质

性质1：从根节点到叶结点的最长路径不大于最短路径的2倍
性质2：有n个内部节点的红黑树高度h ≤ 2log (n ＋ 1)

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

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

红黑树查找操作时间复杂度 = O(log n)

74.6 红黑树的查找

与BST、AVL相同，从根出发，左小右大，若查找到一个空叶节点，则查找失败

75 红黑树的插入

先查找，确定插入位置（原理同二叉排序树），插入新结点
新结点是根――染为黑色
新结点非根――染为红色
        若插入新结点后依然满足红黑树定义，则插入结束
        若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义
        如何调整：看新结点叔叔的脸色
                黑叔：旋转+染色
                        LL型：右单旋，父换爷+染色
                        RR型：左单旋，父换爷+染色
                        LR型：左、右双旋，儿换爷+染色
                        RL型：右、左双旋，儿换爷+染色
                红叔：染色+变新
                        叔父爷染色，爷变为新结点

与“黑高”相关的推论

思考：根节点黑高为h的红黑树，内部结点数(关键字）至少有多少个?
回答：内部结点数最少的情况 ―― 总共h层黑结点的满树形态
结论：若根节点黑高为h，内部结点数（关键字）最少有 $2^{h}-1$ 个

76 红黑树的删除

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

77 B树

77.1 5叉查找树


//5叉排序树的结点定义
struct Node {
	ElemType keys[4];         //最多4个关键字
	struct Node* child[5];   //最多5个孩子
	int num;                 //结点中有几个关键字
};

77.2 如何保证查找效率

若每个结点内关键字太少，导致树变高，要查更多层结点，效率低

策略：m叉查找树中，规定除了根节点外，任何结点至少有[m/2]个分叉，即至少含有[m/2]-1个关键字

策略：m叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同。

77.3 定义

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树:
1）树中每个结点至多有m棵子树，即至多含有m-1个关键字。
2）若根结点不是终端结点，则至少有两棵子树。
3）除根结点外的所有非叶结点至少有 [m/2] 棵子树，即至少含有 [m/2]-1 个关键字。
5）所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)
4）所有非叶结点的结构如下：

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

m阶B树的核心特性:
1）根节点的子树数∈[2, m]，关键字数∈[1, m-1]。
其他结点的子树数∈[[m/2], m]；关键字数=[ [m/2]-1, m-1]2]
2）对任一结点，其所有子树高度都相同
3）关键字的值：子树O<关键字1<子树1<关键字2<子树2<....(类比二叉查找树左<中<右)

77.4 B树的高度

注：大部分学校算B树的高度不包括叶子结点（失败结点)
问题：含n个关键字的m阶B树，最小高度、最大高度是多少?
$\log _{m}(n+1)\leq h\leqslant \log _{m/2}\frac{n+1}{2}+1$

最小高度——让每个结点尽可能的满，有m-1个关键字，m个分叉，则有
$n\leqslant (m-1)(1+m+m^{2}+m^{3}+...+m^{h-1})= m^{h}-1$ ，因此有 $h\geq \log _{m}(n+1)$

方法一：最大高度—让各层的分叉尽可能的少，即根节点只有2个分叉，其他结点只有[m/2]个分叉
各层结点至少有：第一层 1、第二层 2、第三层 2[m/2] ...第h层 $2([m/2])^{h-2}$
第h+1层共有叶子结点（失败结点） $2([m/2])^{h-1}$ 个
n个关键字的B树必有n+1个叶子结点，则 $n+1\geq 2([m/2])^{h-1}$ ，即 $h\leqslant \log _{m/2}\frac{n+1}{2}+1$

方法二：最大高度——让每个结点包含的关键字、分叉尽可能的少。记k=[m/2]

h层的m阶B树至少包含关键字总数 $1+2(k-1)(k^{0}+k^{1}+k^{2}+...+k^{h-2})= 1+2(k^{h-1}-1)$
若关键字总数少于这个值，则高度一定小于h，因此 $n\geq 1+2(k^{h-1}-1)$ ，得 $h\leqslant \log _{k}\frac{n+1}{2}+1= log _{m/2}\frac{n+1}{2}+1$

78 B树的插入删除

78.1 B树的插入

核心要求：
①对m阶B树——除根节点外，结点关键字个数 [m/2]- 1≤n≤m-1
②子树0<关键字1<子树1<关键字2<子树2<....

新元素一定是插入到最底层“终端节点”，用“查找”来确定插入位置

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

78.2 B树的删除

5阶B树——结点关键字个数「m/2] - 1≤n≤m-1
即：2≤n≤4(注：此处省略失败结点)

若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字
（对非终端结点关键字的删除，必然可以转化为对终端结点的删除操作）
直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
直接后继：当前关键字右侧指针所指子树中“最左下”的元素

若被删除关键字在终端节点，则直接删除该关键字(要注意节点关键字个数是否低于下限 [m/2]- 1)

1、兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该结点、右(或左)兄弟结点及其双亲结点父子换位法）
1.1 说白了，当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺
1.2 当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺
本质：要永远保证子树O<关键字1<子树<关键字2<子树2<....

2、兄弟不够借。若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=[m/2]-1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/654556