数据结构Notes

来源：数据结构课程总结

2023.9~2024.1@isSeymour

一、线性表

1.1 顺序表

元素位置从1开始作为参数 i 传入（不是从0开始）。

定义、声明

#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10

typedef int ElemType;	// !!!这里可以把int改成你自己需要的任何类型，结构体也可以

typedef struct {
    ElemType* elem;	// 顺序表元素首地址
    int length;		// 当前顺序表长度
    int listsize;	// 顺序表容量
} sqlist;

typedef int Status;	// 函数返回状态

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

// 初始化、销毁、清空
Status InitList(sqlist* L);
Status DestroyList(sqlist* L);
Status ClearList(sqlist* L);
// 求长度、取元素
int ListLength(sqlist L);
Status GetElem(sqlist L, int i, ElemType* e);
// 插入、删除
Status ListInsert(sqlist* L, int i, ElemType e);
Status ListDelete(sqlist* L, int i, ElemType* e);
// 更多
int LocateElem(sqlist L, ElemType e, Status (*compare)(ElemType e1, ElemType e2));
Status PriorElem(sqlist L, ElemType cur_e, ElemType* pre_e);
Status NextElem(sqlist L, ElemType cur_e, ElemType* next_e);
Status ListTraverse(sqlist L, Status (*visit)(ElemType e));

初始化、销毁、清空

Status InitList(sqlist* L)
{
    L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (L->elem == NULL)
        exit(OVERFLOW);
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
    return OK;
}

Status DestroyList(sqlist* L)
{
    if (L->elem)
        free(L->elem);
    L->length = 0;
    L->listsize = 0;

    return OK;
}

Status ClearList(sqlist* L)
{
    L->length = 0;
    return OK;
}

求长度、取元素

int ListLength(sqlist L)
{
    return L.length;
}

Status GetElem(sqlist L, int i, ElemType* e)
{
    if (i < 1 || i > L.length)
        return ERROR;

    *e = L.elem[i - 1];
    return OK;
}

插入、删除

/**
 * @brief 将元素插入顺序表指定位置
 * @param L 顺序表
 * @param i 指定位置
 * @param e 待插入元素
 * @return Status 
 */
Status ListInsert(sqlist* L, int i, ElemType e)
{
    ElemType *p, *q;

    if (i < 1 || i > L->length + 1)
        return ERROR;

    if (L->length >= L->listsize) {
        ElemType* newbase;
        newbase = (ElemType*)realloc(L->elem, (L->listsize + LIST_INCREMENT) * sizeof(ElemType));
        if (!newbase)
            return OVERFLOW;

        L->elem = newbase;
        L->listsize += LIST_INCREMENT;
    }

    q = &(L->elem[i - 1]);

    for (p = &(L->elem[L->length - 1]); p >= q; --p)
        *(p + 1) = *p;

    *q = e;
    L->length++;

    return OK;
}

Status ListDelete(sqlist* L, int i, ElemType* e)
{
    ElemType *p, *q;

    if (i < 1 || i > L->length)
        return ERROR;

    p = &(L->elem[i - 1]);
    *e = *p;
    q = &(L->elem[L->length - 1]);

    for (++p; p <= q; ++p)
        *(p - 1) = *p;

    L->length--;
    return OK;
}

/**
 * @brief 查找指定元素是否存在于顺序表中，
 *        若存在则返回其位置
 * @param L 顺序表
 * @param e 指定元素
 * @param compare 元素间判断相等的函数
 * @return int 
 */
int LocateElem(sqlist L, ElemType e, Status (*compare)(ElemType e1, ElemType e2))
{
    ElemType* p = L.elem;
    int i = 1;

    while (i <= L.length && (*compare)(*p++, e) == FALSE)
        i++;

    return (i <= L.length) ? i : 0;
}

Status PriorElem(sqlist L, ElemType cur_e, ElemType* pre_e)
{
    ElemType* p = L.elem;
    int i = 1;

    while (i <= L.length && *p != cur_e) {
        i++;
        p++;
    }

    if (i == 1 || i > L.length)
        return ERROR;

    *pre_e = *--p;
    return OK;
}

Status NextElem(sqlist L, ElemType cur_e, ElemType* next_e)
{
    ElemType* p = L.elem;
    int i = 1;

    while (i < L.length && *p != cur_e) {
        i++;
        p++;
    }

    if (i >= L.length)
        return ERROR;

    *next_e = *++p;
    return OK;
}
Status ListTraverse(sqlist L, Status (*visit)(ElemType e))
{
    ElemType* p = L.elem;
    int i = 1;

    while (i <= L.length && (*visit)(*p++) == TRUE)
        i++;

    if (i <= L.length)
        return ERROR;

    printf("\n");
    return OK;
}

main

程序并不完整，这里只是给出在main中使用的一般流程

int main()
{
    sqlist L;
    int n, x;
    InitList(&L);
    
	......
    
    DestroyList(&L);
    return 0;
}

1.2 单链表

定义、声明

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

typedef struct {
	int p;
	int e;
} Equation;

typedef Equation ElemType;	// 指定自己的元素类型 

typedef struct LNode{
	ElemType data;	// 单链表数据域 
	struct LNode *next;	// 单链表指针域 
} LNode, *LinkList;

typedef int Status;	// 函数返回状态 

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

// 初始化（有头结点） 
Status InitLink(LinkList &L);
// 销毁
Status DestroyLink(LinkList &L); 
// 求表长
int ListLength(LinkList &L); 
// 查找第i个元素，返回元素地址 （从i=1作为第一个元素 ） 
LNode* GetElem(LinkList &L, int i); 
// 插入（尾插法）插入成为第i个 
Status ListInsert(LinkList &L, int i, ElemType data); 
// 删除 （删除第i个元素） 
Status ListDelete(LinkList &L, int i);

初始化、销毁

Status InitLink(LinkList &L)
{
	L = (LNode *)malloc(sizeof(LNode));
	L->next = NULL;
	return OK;
}

Status DestroyLink(LinkList &L)
{
	LNode *p = L, *t;
	while(p!=NULL)
	{
		t = p->next;
		free(p);
		p = t;
	 } 
	 return OK;
}

求表长、查找元素


Status ListLength(LinkList &L)
{
	LNode *p = L->next;
	int count = 0;
	while(p)
	{
		count++;
		p = p->next;
	}
	return count;
}

LNode* GetElem(LinkList &L, int i)
{
	
	if(i<0)
	{
		return NULL;
	}
	//printf("a");
	int j=0;
	LNode *p = L;
	while(p!=NULL && j<i)
	{
		p = p->next;
		j++;
		//printf("b");
	}
	
	return p;
 }

插入、删除

Status ListInsert(LinkList &L, int i, ElemType data)
{
	if(i<1) 
	{
		return ERROR;
	}
	LNode *newnode = (LNode *)malloc(sizeof(LNode));
	newnode->data = data;
	newnode->next = NULL;
	LNode *t = GetElem(L, i-1);
	if(t)
	{
		newnode->next = t->next;
		t->next = newnode;
		return OK;
	}
	return ERROR;
}

Status LinkDelete(LinkList &L, int i)
{
	LNode *t1 = GetElem(L, i-1);
	LNode *t2 = GetElem(L, i);
	if(t1 && t2)
	{
		t1->next = t2->next;
		free(t2);
		return OK;
	}
	return ERROR;
 }

main

程序并不完整，这里只是给出在main中使用的一般流程

int main()
{
	LinkList L1, L2, L3, L4;
	InitLink(L1), InitLink(L2), InitLink(L3), InitLink(L4);
    
	......
	
	DestroyLink(L1), DestroyLink(L2), DestroyLink(L3), DestroyLink(L4);
	return 0;
 }

二、栈和队列

2.1 栈（顺序栈）

定义、声明

#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10 
// 注意：这里define是不能加;的，书上错误了
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define TRUE 1
#define FALSE 0

typedef char SElemType;
// 顺序栈 
typedef struct {
	SElemType *top;		// 栈顶指针 
	SElemType *base;	// 栈底指针 
	int stacksize;		// 当前已分配的存储空间，以元素为单位 
} SqStack;

Status InitStack(SqStack &S);		// 初始化空栈 
Status DestroyStack(SqStack &S);	// 销毁栈  
Status ClearStack(SqStack &S);		// 清空栈 
Status StackEmpty(SqStack S);		// 栈是否为空 
int StackLength(SqStack S);			// 栈长度（元素个数） 
Status GetTop(SqStack S, SElemType &e);// 若栈不空，用e返回S的栈顶元素，返回OK，否则返回ERROR 
Status Push(SqStack &S, SElemType e);	// 插入元素e为新的栈顶元素 
Status Pop(SqStack &S, SElemType &e);	// 若栈不空，删除栈顶元素，用e接住，返回OK，否则返回ERROR
Status StackTraverse(SqStack S, Status (* visit)(SElemType *p));	// 从栈底到栈顶依次对栈中每个元素调用函数visit()

初始化、销毁

// 初始化空栈 
Status InitStack(SqStack &S)
{
	S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if(!S.base)
		exit(OVERFLOW);	// 分配失败 
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
 } 

// 销毁栈 
Status DestroyStack(SqStack &S)
{
	if(S.base)
	{
		free(S.base);
		S.base = S.top = NULL;
		S.stacksize = 0;
	}
	return OK;
 }

清空、查空、长度、顶元素

// 清空栈
Status ClearStack(SqStack &S)
{
	if(S.base)
		S.top = S.base;
	return OK;
 } 
 
// 栈是否为空 
Status StackEmpty(SqStack S)
{
	if(S.top == S.base)
		return TRUE;
	else
		return FALSE;
}
 
// 栈长度
int StackLength(SqStack S)
{
	return S.top - S.base;
 } 

// 获取栈顶元素 
Status GetTop(SqStack S, SElemType &e) 
{
	if(S.top == S.base)
		return ERROR;
	e = *(S.top - 1);
	return OK;
}

入栈、出栈

// 入栈
Status Push(SqStack &S, SElemType e)
{
	// 先看是否栈满
	if(S.top - S.base >= S.stacksize)
	{
		S.base = (SElemType *)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(SElemType));
		if(!S.base)
			exit(OVERFLOW);	// 分配失败 
		S.top = S.base + S.stacksize;
		S.stacksize += STACK_INCREMENT;
	 } 
	*S.top = e;
	S.top++;
	return OK;
 } 
 
// 出栈 
Status Pop(SqStack &S, SElemType &e)
{
	if(S.top == S.base)
		return ERROR;
	S.top--;
	e = *S.top;
	return OK;
 }

// 遍历调用visit
Status StackTraverse(SqStack S, Status (* visit)(SElemType *p))
{
	if(S.base == NULL)
		return ERROR;
	SElemType *p1 = S.top;
	SElemType *p2 = S.base;
	while(p1 > p2)
	{
		visit(p2);
		p2++;
	}
	return OK;
 }

2.2 队列（链式队列）

定义、声明

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

typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define TRUE 1
#define FALSE 0

// 链式队列 
typedef int QElemType;
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;

typedef struct {
	QueuePtr front;	// 队头指针
	QueuePtr rear;	// 队尾指针 
} LinkQueue;

Status InitQueue(LinkQueue &Q);		// 初始化
Status DestroyQueue(LinkQueue &Q);	// 销毁 
Status ClearQueue(LinkQueue &Q);	// 清空
Status QueueEmpty(LinkQueue Q);		// 是否为空 
int QueueLength(LinkQueue Q);		// 队列长度 
Status GetHead(LinkQueue Q, QElemType &e);	// 获取队头元素 
Status EnQueue(LinkQueue &Q, QElemType e);	// e到队尾排队 
Status DeQueue(LinkQueue &Q, QElemType &e);	// 队头e离开

初始化、销毁

// 初始化
Status InitQueue(LinkQueue &Q)
{
	// 申请头结点出来 
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)
		exit(OVERFLOW);
	Q.front->next = NULL;
	return OK;
 } 

// 销毁
Status DestroyQueue(LinkQueue &Q)
{
	// 连带头结点，全部销毁 
	while(Q.front)
	{
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	 } 
	return OK;
 }

清空、为空、长度、队头

// 清空 
Status ClearQueue(LinkQueue &Q)
{
	// 头结点都没有，报错 
	if(!Q.front)
		return ERROR;
	// 清空会留下头结点，置头结点的next为NULL，front/rear指向头结点
	QueuePtr p = Q.front->next, t;
	while(p)
	{
		t = p->next;
		free(p);
		p = t;
	 } 
	Q.rear = Q.front;
	Q.front->next = NULL;
	return OK;
 } 

// 是否为空 
Status QueueEmpty(LinkQueue Q)
{
	if(Q.front == Q.rear)
		return TRUE;
	else
		return FALSE;
 } 

// 队列长度 
int QueueLength(LinkQueue Q)
{
	int len = 0;
	QueuePtr p = Q.front->next;
	while(p)
	{
		p = p->next;
		len++;
	}
	return len;
 } 
 
// 获取队头元素
Status GetHead(LinkQueue Q, QElemType &e)
{
	if(!Q.front)
		return ERROR;	// 没有头结点（未初始化） 
	if(Q.front == Q.rear)
		return ERROR;	// 没有元素 
	e = Q.front->next->data;
	return OK;
 }

队尾排队、队头出队

// e到队尾排队 
Status EnQueue(LinkQueue &Q, QElemType e)
{
	// 申请空间 
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if(!p)
		exit(OVERFLOW);
	// 队尾排队 
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return OK;
 } 
 
// 队头e离开
Status DeQueue(LinkQueue &Q, QElemType &e)
{
	if(!Q.front)
		return ERROR;	// 没有头结点（未初始化）
	if(Q.front == Q.rear)
		return ERROR;	// 没有元素
	// 队头离开 
	QueuePtr p = Q.front->next;
	e = p->data;
	Q.front = p->next;
	// 队头元素同时是队尾元素，那么需要更新队尾指针 
	if(Q.rear == p)
		Q.rear = Q.front;
	free(p);	// 释放空间 
	return OK;
 }

三、树

3.1 二叉树

二叉树的性质

非空二叉树上的叶子结点数等于度为 2 的结点数加 1 。

n0 = n2 +1
非空二叉树上第 k 层上至多有 2^k-1^ 个结点（k>=1)
高度为 h 的二叉树至多有 2^h^ - 1 个结点（k>=1）
对完全二叉树按从上到下、从左到右的顺序依次编号 1,2,…,n，则有以下关系：
1. 当 i>1 时，结点 i 的双亲编号为 floor(i/2)
  
  i 为偶数，双亲编号为 i/2，它为双亲的左孩子；
  
  i 为奇数，双亲编号为 (i-1)/2，它为双亲的右孩子。
2. 当 2i <= n 时，结点 i 的左孩子编号为 2i，否则无左孩子；
  
  当 2i+1 <= n 时，结点 i 的右孩子编号为 2i+1，否则无右孩子。
3. 结点 i 所在层次（深度）为 floor( log~2~ i ) + 1 。
具有 n 个结点（n>0）的完全二叉树的高度为 ceiling( log~2~ (n+1) ) 或 floor( log~2~ n ) + 1 。

存储结构若采用顺序存储时，建议下标1开始，否则不满足条件4。

由于顺序存储空间利用率低，因此二叉树一般采用链式存储结构。

定义、声明

#include <stdio.h>
#include <stdlib.h>
//头文件需要添加
#include <stack>
#include <queue>
using namespace std;

// 定义状态码 
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define TRUE 1
#define FALSE 0

// 定义元素数据类型 
typedef char ElemType;

// 二叉链表 
typedef struct BiTNode{
	ElemType data;	// 数据域 
	struct BiTNode *lchild, *rchild;	// 左右孩子指针 
} BiTNode, *BiTree;

含n个结点的二叉链表中，含有n+1个空链域，后续可作线索链表

构造、销毁、树空、访问

// 构造空树
Status InitTree(BiTree &T)
{
	T = NULL;
	return OK;
 }
 
// 销毁树
Status DestroyTree(BiTree &T)
{
	if(T)
	{
		DestroyTree(T->lchild);
		DestroyTree(T->rchild);
		free(T);		
	}
	T = NULL;
	return OK;
}

// 构造树（具体重写）
Status CreateBiTree(BiTree &T)
{
	// 先序输入构造
	char ch;
	scanf("%c", &ch);
	if(ch == '#')	// #表示此处为空 
		T = NULL;
	else
	{
		if(!(T = (BiTNode*)malloc(sizeof(BiTNode))))
			exit(OVERFLOW);
		T->data = ch;				// 根结点 
		CreateBiTree(T->lchild);	// 构造左子树 
		CreateBiTree(T->rchild); 	// 构造右子树 
	}
	return OK;
 } 

// 清空树（与销毁等效）
Status ClearTree(BiTree &T)
{
	if(T)
	{
		ClearTree(T->lchild);
		ClearTree(T->rchild);
		free(T);
	}
	T = NULL;
	return OK;
 } 

// 树空
Status TreeEmpty(BiTree &T)
{
	if(T)
		return FALSE;
	else
		return TRUE;
}

// 访问一个结点 
Status visit(BiTNode* T)
{
	printf("%c ", T->data);
	return OK;
}

递归：先、中、后序遍历

// 先序遍历（递归）
Status PreOrder(BiTree T)
{
	if(T)
	{
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
	return OK;
 } 
 
// 中序遍历（递归）
Status InOrder(BiTree T)
{
	if(T)
	{
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
	return OK;
 } 

// 后序遍历（递归）
Status PostOrder(BiTree T)
{
	if(T)
	{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
	return OK;
 }

非递归：先、中、后序遍历

// 先序遍历（非递归）
Status PreOrder2(BiTree &T)
{
	stack<BiTree> S;
	BiTree p = T;
	while(p || !S.empty())	// p不空或栈不空 
	{
		if(p)	// 一路向左 
		{
			visit(p);		// 先序 
			S.push(p);		
			p = p->lchild;
		}
		else	// 出栈，转向右子树 
		{
			p = S.top();
			S.pop();
			p = p->rchild;
		}
	}
	return OK;
 } 

// 中序遍历（非递归）
Status InOrder2(BiTree &T)
{
	stack<BiTree> S;
	BiTree p = T;
	while(p || !S.empty())	// p不空或栈不空 
	{
		if(p)	// 一路向左 
		{
			S.push(p);
			p = p->lchild;
		}
		else	// 出栈，转向右子树 
		{
			p = S.top();
			S.pop();
			visit(p);		// 中序
			p = p->rchild;
		}
	}
	return OK;
 } 

// 后序遍历（非递归）
Status PostOrder2(BiTree &T)
{
	stack<BiTree> S;
	BiTree p = T;
	BiTree r = NULL;	// 辅助指针r 用于指向最近访问过的结点（为分清返回时是从左子树返回的还是从右子树返回的） 
	while(p || !S.empty())	// p不空或栈不空 
	{
		if(p)	// 一路向左 
		{
			S.push(p);
			p = p->lchild;
		}
		else	// 出栈，向右转 
		{
			p = S.top();	// 读栈顶，但不出栈 
			if(p->rchild && p->rchild != r)
				p = p->rchild;
			else
			{
				p = S.top();
				S.pop();
				visit(p);
				r = p;	// 记录最近访问过的结点 
				p = NULL;	// 访问完后，重置p指针 
			} 
		 } 
	 } 
	return OK;
 }

层次遍历

// 层次遍历
Status LevelOrder(BiTree T)
{
	// 默认树至少有一个根结点
	queue<BiTree> Q;
	BiTNode *p = T;
	Q.push(p);
	while(!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p);
		if(p->lchild)
			Q.push(p->lchild);
		if(p->rchild)
			Q.push(p->rchild);
	}
	return OK;
 }

示例

// 示例：abc##d##ef### 
int main()
{
	// 构造空树
	BiTree T = NULL;
	CreateBiTree(T);
	
	// 层次遍历
	LevelOrder(T);
	
	// 销毁
	DestroyTree(T); 
	return 0;
 }

3.2 线索二叉树

很少用

四、图

4.0 知识框架

图的定义
图结构的存储
- 邻接矩阵法、邻接表法
- 邻接多重表、十字表
图的遍历
- DFS 深度优先遍历
- BFS 广度优先遍历
图的相关应用
- 最小生成树：Prim 算法、Kruskal 算法
- 最短路径：Dijkstra 算法、Floyd 算法
- 拓扑排序：AOV 网
- 关键路径：AOE 网

4.1 图的基本概念

图

图 G 由顶点集 V 和边集 E 组成，记为 G = (V, E)。
1
2
3
G = (V, E)
V = {1, 2, 3}
E = {<1,2>, <2,1>, <2,3>}
注：线性表可以是空表，树可以是空树，但图不可以是空图。

就是说，图中不能一个顶点也没有，图的顶点集 V 一定非空，但边集 E 可以为空，此时图中只有顶点而没有边。

基本概念与术语

方向性
- 有向图
  
  边是顶点的有序对。（弧）
- 无向图
  
  边是顶点的无序对。（边）
复杂度
- 简单图
  1. 不存在重复边
  2. 不存在顶点到自身的边
- 多重图
注：学习中，只讨论简单图。
完全图（简单完全图）
- 无向图：任意两个顶点之间都存在边。
- 有向图：任意两个顶点之间都存在方向相反的弧。

子图与生成子图

G = (V, E)
G' = (V', E')

子图：
V‘ 是 V 的子集，E' 是 E 的子集，则 G’ 是 G 的子图。
生成子图：
且满足 V(G') = V(G)。（即，在子图的那些顶点的边是完全的，并不缺边）

注：并非 V 和 E 的任何子集都能构成 G 的子图。因为可能这样的子集可能不是图。

连通

在无向图中讨论连通性，

在有向图中讨论强连通性。
1. 无向图
  - 连通
    
    在无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。
  - 连通图
    
    若图 G 中任意两个顶点都是连通的
  - 连通分量（极大连通子图）
    
    无向图中的极大连通子图，称为连通分量。
2. 有向图
  - 强连通
    
    在有向图中，一对顶点v, w之间有相反的路径，则这两个顶点是强连通的。
  - 强连通图
    
    任何一对顶点都是强连通的
  - 强连通分量（极大强连通子图）
    
    有向图中的极大强连通子图，称为强连通分量。
生成树（连通图才有）

连通图的生成树，是包含图中全部顶点的一个极小连通子图。
- 极大连通子图
  
  要求包含所有边
- 极小连通子图
  
  既要图连通，又要边数最少。
生成森林（非连通图可以）

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

4.2 图的存储及基本操作

4.2.1 邻接矩阵法（稠密图）

介绍

用一个一维数组存储图中顶点的信息，

用一个二维数组存储图中边的信息（各顶点的邻接关系，该二维矩阵是邻接矩阵）。
适合：稠密图
代码

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

4.2.2 邻接表法（稀疏图）

介绍

对图 G 中的每一个顶点 vi 建立一个单链表。
- 边表（邻接表）：
  
  第 i 个单链表中的结点表示依附于顶点 vi 的边（有向图则是以顶点 vi 为尾的弧），这个单链表就称为顶点 vi 的边表（有向图则是出边表）。
  
  由邻接点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成。
- 顶点表：
  
  边表的头指针和顶点的数据信息采用顺序存储（称为顶点表）。
  
  由顶点域（data）和指向第一条邻接边的指针（firstarc）构成。
适合：稀疏图
代码

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

4.2.3 十字链表（有向图）

介绍

十字链表是有向图的一种链式存储结构。

在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。
- 弧结点：
  
  tailvex 和 headvex 分别指向弧尾和弧头两个顶点的编号；
  
  hlink 指向弧头相同的下一个弧结点；
  
  tlink 指向弧尾相同的下一个弧结点；
  
  info 存放该弧的相关信息。
  
  注：这样做，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上。
- 顶点结点：
  
  data 域存放该顶点的数据信息；
  
  firstin 指向以该顶点为弧头的第一个弧结点；
  
  firstout 指向以该顶点为弧尾的第一个弧结点。
  
  注：顶点之间是顺序存储的。

4.2.4 邻接多重链表（无向图）

介绍

邻接多重链表是无向图的另一种链式存储结构。
- 边结点：
  
  ivex 和 jvex 指示该边依附的两个顶点的编号；
  
  ilink 指向下一个依附于顶点 ivex 的边；
  
  jlink 指向下一个依附于顶点 jvex 的边；
  
  info 存放该边的相关信息。
- 顶点结点：
  
  data 存放该顶点的相关信息；
  
  firstedge 指向第一条依附于该顶点的边。

注：在邻接多重链表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。

对于无向图，其邻接多重链表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重链表中只有一个结点。

4.3 图的遍历

4.3.1 广度优先搜索（BFS）

介绍

广度优先搜索（Breadth-First-Search, BFS）
- 基本思想：分层查找，逐层访问
- 辅助：队列，记录正在访问的顶点的下一层顶点
代码

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

时间复杂度

下面 n 为顶点数 |V| ，m 为边数 |E| 。
- 邻接矩阵：O(n^2^)
- 邻接表：O(n+m)
应用
- 求解单源最短路径问题
- 广度优先生成树

4.3.2 深度优先搜索 DFS

介绍

深度优先搜索（Depth-First-Search, DFS）
- 基本思想：向下深挖，到底回退一步
- 辅助：不需要（但本质上使用了栈，函数本身被压栈）
代码

bool visited[MAX_VERTEX_NUM];	// 访问标记数组
// 对图 G 进行深度优先遍历
Status DFSTraverse(Graph G)
{
    for(int v=0; v<G.vexnum; v++)
        visited[v] = FALSE;	// 初始化
    for(int v=0; v<G.vexnum; v++)
        if(!visited[v])
            DFS(G, v);
    return OK;
}
// 从顶点 v 出发，深度优先遍历图 G
Status DFS(Graph G, int v)
{
    visit(v);
    visited[v] = TRUE;
    for(w=FirstNeighbor(G, V); w>=0; w=NextNeighbor(G, v, w))
        if(!visited[w])
            DFS(G, w);
    return OK;
}

时间复杂度

下面 n 为顶点数 |V| ，m 为边数 |E| 。
- 邻接矩阵：O(n^2^)
- 邻接表：O(n+m)
应用
- 深度优先生成树、生成森林

4.3.3 遍历与连通性

图的遍历算法可以判断图的连通性。
- 无向图
  
  若是连通的，则从任意一个结点出发，仅需一次遍历就能访问图中的所有顶点；
  
  若非连通，则从某个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点。
- 有向图
  
  若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点；
  
  否则，不能访问到所有顶点。
注：故在 BFSTraverse 或 DFSTraverse 中添加了for 循环，再选取初始点，继续进行遍历，以防一次无法遍历图中的所有顶点。
- 无向图
  
  在 BFSTraverse / DFSTraverse 中调用 BFS / DFS 的次数，就是该图的连通分量数。
- 有向图
  
  不能判断。
  
  因为一个连通的有向图分为强连通的、非强连通的，它的连通子图也分强连通分量、非强连通分量。
  
  其中，非强连通分量一次调用 BFS / DFS 也无法访问到该连通分量的所有顶点。

4.4 图的应用

4.4.1 最小生成树

介绍
- 前提：连通图
- 生成树
  
  一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。
  - 砍去一条边，则变成非连通图；增加一条边，则会形成图中的一条回路。
- 最小生成树
  
  对于一个带权连通无向图，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。
  
  设 R 为图 G 的所有生成树的集合，若 T 为 R 中边的权值之和最小的那棵生成树，则称 T 为图 G 的最小生成树（Minimum-Spanning-Tree, MST）
- 最小生成树的性质
  - 最小生成树不唯一，可能多个。
    
    若图 G 中的各边权值互不相等时，G 的最小生成树唯一。
    
    若无向连通图 G 的边数比顶点数少1（即 G 本身是一棵树），则 G 的最小生成树是它本身。
  - 最小生成树的边的权值之和总是唯一的。
  - 最小生成树的边数为顶点数减1。

性质

1
2

假设 G = (V, E) 是一个带权连通无向图，U 是顶点集 V 的一个非空子集。
若 (u, v) 是一条具有最小权值的边，其中 u ∈ U，v ∈ V-U，则必存在一棵包含边 (u, v) 的最小生成树。

基于该性质的最小生成树算法主要有 Prim 算法和 Kruskal 算法（都基于贪心算法的策略）。

通用算法：

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

Prim 算法

从顶点开始扩展最小生成树

核心：选顶点

Status Prim(G, T)
{
    V = GraphAllVertex(G);
    T = 空集;		// 初始化空树
    U = { w };	// 添加任意一个顶点 w
    while((V-U)!=空集)	// 若不含所有顶点
    {
        设(u,v)是使 u ∈ U 与 v ∈ (V-U)，且权值最小的边;
        T = T + (u,v);	// 边归入树
        U = U +v;		// 顶点归入树
    }
    return OK;
}

时间复杂度

下面 n 为顶点数 |V| ，m 为边数 |E| 。

O(n^2^)，不依赖于 m。

适用：边稠密的图

Kruskal 算法

按权值的递增次序选择合适的边来构造最小生成树

核心：选边

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

时间复杂度

下面 n 为顶点数 |V| ，m 为边数 |E| 。

O(m log2 m)，不依赖于 n。

适用：边稀疏而顶点多的图

4.4.2 最短路径

性质

两点之间的最短路径也包含了路径上其他项点间的最短路径。
带权有向图 G 的最短路径
- 单源最短路径：求图中某一顶点到其他各顶点的最短路径——Dijkstra 算法
- 多源最短路径：求顶点间的最短路径——Floyd 算法

单源最短路径——Dijkstra 算法

懂原理即可

多源最短路径——Floyd 算法

懂原理即可

4.4.3 拓扑排序、AOV网

AOV网

若用有向无环图 DAG图表示一个工程，其顶点表示活动，有向边 <vi, vj> 表示活动 vi 必须先于活动 vj 进行的这样一种关系，则将这种有向图称为顶点表示活动的网络（Activity On Vertex, AOV网）。
拓扑排序

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件，称为该图的一个拓扑排序：
1. 每个顶点出现且只出现一次
2. 若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径。
每个 AOV 网都有一个或多个拓扑排序。
常用算法步骤：
1. 从 AOV 网中选择一个没有前驱的顶点并输出。
2. 从网中删除该顶点和所有以它为起点的有向边。
3. 重复步骤1 和步骤2 直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止。（后者说明有向图中存在环）
代码

Status TopologicalSort(Graph G)
{
    InitStack(S);	// 初始化栈，存储入度为0的顶点
    for(int i=0; i<G.vexnum; i++)
        if(indegree[i]==0)
            Push(S, i);	// 将所有入度为0的顶点入栈
    int count = 0;	// 计数，记录的当前已经输出的顶点数
    while(!isEmpty(S))	// 栈不空，则存在入度为0的顶点
    {
        int h;
        Pop(S, h);	// 栈顶出栈
        print[count++] = h;	// 输出顶点 h
        for(p=G.vertices[h].firstarc; p; p=p->nextarc)
        {
            // 将所有 h 指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
            v = p->adjvex;
            if(!(--indegree[v]))
                Push(S, v);	//入度为0，入栈
        }
    }
    if(count<G.vexnum)
        return FALSE;
    else
    	return TRUE;	// 拓扑排序成功
}

时间复杂度

下面 n 为顶点数 |V| ，m 为边数 |E| 。
- 邻接矩阵：O(n^2^)
- 邻接表：O(n+m)

4.4.4 关键路径、AOE网

AOE网

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

注：AOV 网和 AOE 网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，且 AOE 网的边有权值，而 AOV 网的边无权值，仅代表顶点之间的前后关系。
- AOE 网的性质
  1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
  2. 只有在进入某顶点的各有向边所代表的活动都已经结束时，该顶点代表的事件才能发生
工程

工程开始：在 AOE 网中，仅有一个入度为0的顶点，是开始顶点（源点）。

工程结束：在 AOE 网中，仅有一个出度为0的顶点，是结束顶点（汇点）。
在 AOE 网中，一些活动是可以并行的。
关键路径

从源点到汇点的所有路径中，具有最大路径长度的路径，称为关键路径。
- 关键活动：在关键路径上的活动
- 关键路径的长度：完成整个工程的最短时间

概念

ai 活动：vj->vk
    
ve(k)	事件 vk 的最早发生时间 
vl(k)	事件 vk 的最迟发生时间 
v(i)	活动 ai 的最早开始时间 
l(i)	活动 ai 的最迟开始时间 
d(i) = l(i) - e(i)	活动 ai 的差额空闲余量
    
l(i) - e(i) = 0 ,即 l(i) = e(i) 的活动 ai 是 关键活动。

求关键路径的算法
1. 从源点出发，令 ve(源点) = 0，按拓扑有序求其余顶点的最早发生时间 ve()
2. 从汇点出发，令 vl(汇点) = ve(汇点)，按逆拓扑有序求其余顶点的最迟发生时间 vl()
3. 根据各顶点的 ve() 值求所有弧的最早开始时间 e()
4. 根据各顶点的 vl() 值求所有弧的最迟开始时间 l()
5. 求 AOE 网中所有活动的差额 d()
6. 找出所有 d() = 0 的活动，构成关键路径
- 如何求 ve() ？
  
  从 ve(1) = 0 开始按拓扑有序推进
  1
  ve(j) = Max i{ ve(i) + Wij}
  其中，<i, j> ∈ T， 2<=j<=n，T是所有以 j 为头的弧的集合。
- 如何求 vl() ？
  
  从 vl(n) = ve(n) 开始按拓扑有序推进
  1
  vl(i) = Min j{ vl(j) - Wij}
  其中，<i, j> ∈ S， 1<=i<=n-1，S是所有以 i 为尾的弧的集合。
注意：
- 关键路径上的所有活动都是关键活动，因此可以通过加快关键活动来缩短整个工期。
  
  但也不能任意缩短，因为一旦缩短到一定程度，该关键活动就可能变成非关键活动。
- 网中的关键路径并不唯一，对于有多条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期。

五、查找

5.0 知识框架

基本概念
- 静态查找（并不修改）
- 动态查找
效率指标
- ASL平均查找长度
  
  ASL = Σ PiCi
查找
- 线性结构
  - 顺序查找
  - 折半查找
  - 分块查找
- 树形结构
  - 二叉排序树
  - 平衡二叉树
  - 红黑树
  - B树、B+树
- 散列结构
  - 散列表（性能分析、冲突处理）

5.1 线性结构

5.1.1 顺序查找

又称“线性查找”
适用：顺序表、链表
说明：引入“哨兵”

typedef struct {
    Element *elem;
    int TableLen;
}SSTable;
int Search_Seq(SSTable ST, ElemtType key)
{
    ST.elem[0] = key;	// 哨兵
    for(int i=ST.TableLen; ST.elem[i]!=key; --i)
        ;
    return i;	// 无论如何也会在0处退出循环
}

性能分析
- 成功
  
  ASL = (n+1)/2
- 失败
  
  ASL = n+1
优点：对数据元素存储没有要求，顺序存储、链式存储均可，且是无序存储
缺点：当n较大时，ASL较大，效率低

若查找前，已知关键字是有序的。

成功情况相同；失败情况可以提早退出循环。

ASL失败 = n/2 + n/n+1

n为结点数目

5.1.2 折半查找

又称“二分查找”
适用：有序的顺序表！！！
基本思想：

将给定值 key 与表中间位置比较
- 相等，成功
- 不相等，缩小范围到左半部或右半部，继续查找（若已经出现跨越部分的情况，说明找不到，退出）

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;	// 失败
}

性能分析
- 成功
  
  ASL = log2(n+1) - 1
  
  树高：h = log2(n+1) 向上取整
  
  时间复杂度：O(log2 n)
优点：效率比顺序查找高
缺点：只适用于顺序存储，不能链式存储。并且要求元素按关键字有序排列。

5.1.3 分块查找

又称“索引顺序查找”
吸收顺序查找和折半查找的优点，既有动态结构，又有快速查找
基本思想：

分块，块内无序，块间有序。
做法：

建立一个索引表，索引表的每个元素含有各块的最大关键字和各块的第一个元素的地址，索引表按关键字有序排序。
查找：
- 第一步：确定所在块（顺序查找或折半查找均可）
- 第二步：块内顺序查找
性能分析

长度 n 的查找表均匀分为 b 块，每块有 s 个记录，在等概论情况下。

若在块内和索引表中均采用顺序查找，则

ASL = LI + LS = (b+1)/2 + (s+1)/2 = (s2 + 2s + n)/(2s)

5.2 树形结构

5.2.1 二叉排序树 BST

二叉排序树
- 要么是一棵空树
- 要么是一棵满足下列条件的二叉树
  - 若左子树非空，左子树所有结点的值均小于根结点的值
  - 若右子树非空，右子树所有结点的值均大于根结点的值
  - 左右子树也是一棵二叉排序树
效果

左 < 根 < 右

中序遍历，得到递增的有序序列

构造

void Creat_BST(BiTree &T, KeyType str[], int n)
{
    T = NULL;
    int i = 0;
    while(i < n)
    {
        BST_Insert(T, str[i]);
        i++;
    }
}

插入

Status BST_Insert(BiTree &T, KeyType k)
{
    if(T == NULL)			// 不存在，因此插入
    {
        T = (BiTree)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return OK;	// 插入成功
    }
    else if(k == T->data)	// 已存在，不必插入
        return ERROR;
    else if(k < T->data)	// 插入到左子树
        return BST_Insert(T->lchild, k);
    else					// 插入到右子树
        return BST_Insert(T->rchild, k);
}

查找

BSNode *BST_Search(BiTree T, ElemType key)
{
    while(T != NULL && key != T->data)
    {
       if(key < T->data)
           T = T->lchild;
       else 
           T = T->rchild;
    }
    return T;
}

删除

三种情况，被删除结点是结点 Z。

若 Z 是叶结点

直接删除
若 Z 只有一棵左子树或右子树

让 Z 的子树成为 Z 的父结点的子树，替代 Z 的位置
若 Z 同时有左、右子树

让 Z 的直接后继（或直接前驱）替代 Z，然后从二叉排序树中删去这个直接后继（或直接前驱），

由此，就转换成了第一、二种的情况。

注意：删除时特别注意，可能会把 root 根结点都删除了，要随时更新 root 值（传引用）。

// 移除结点
Status Remove(BSTree node, BSTree &root)
{
	// node 待删除结点 root 根（！！！注意若是删除了根，要更改一下！） 
	if(node == NULL)
		return ERROR;
	// 获取node 信息
	BSTree pt = node->parent; 
	BSTree lc = node->lchild;
	BSTree rc = node->rchild;
	// 检测node是parent的左孩子/右孩子 
	int left = (pt && pt->lchild == node)? 1 : 0;	// 注意加一个pt先判断！要不然就可能使用NULL指针 
	// 情况1：node没有孩子（直接删除即可） 
	if(lc == NULL && rc == NULL)
	{
		if(pt)
		{
			if(left)
				pt->lchild = NULL;
			else
				pt->rchild = NULL;
		}
		if(node == root)
			root = NULL;
		delete node;
	}
	// 情况2：node有两个孩子（找到直接前驱front，替代node，删除front，就回到情况1.2了） 
	else if(lc && rc)
	{
		// 1.找到直接前驱front 
		BSTNode *front = FindFront(node);
		
		// 2.替换掉node，成为了front（注意，不可直接node = front，错的！！！） 
		node->data = front->data;
		node->cnt = front->cnt;
		//node->parent = front->parent;	// 不需要更改parent/child！！！ 
		//node->lchild = front->lchild;
		//node->rchild = front->rchild;
		
		// 3.把front删除 
		Remove(front, root);
	} 
	// 情况3：node只有一个孩子（孩子拉上来填补） 
	else
	{
		BSTree c = (lc)? lc : rc;
		if(pt)
		{
			if(left)
				pt->lchild = c;
			else
				pt->rchild = c;
			c->parent = pt;
		}
		if(node == root)
			root = c;
		delete node;
	 } 
	return OK;
 }

5.2.2 平衡二叉树 BBT / AVL

定义

任意结点的左右子树的高度差的绝对值不超过1，这种二叉排序树为平衡二叉树。
平衡因子

每个结点都有平衡因子

平衡因子 = 左子树高度 - 右子树高度

只可能是0、1、-1

平衡调整

（1）LL型

（2）RR型

（3）LR型

（4）RL型

示例

5.2.3 红黑树

辨析

不同的二叉排序树，主要区别在于：维护二叉树平衡的方式不同

所有平衡树的结点旋转算法都是通用的，包括左旋和右旋两种。

结点旋转的目的是，在保持二叉查找树的前提下，使树的结构变得平衡。

右旋

左旋

定义

插入数据

疑问：为什么最初是染红，而不是染黑？

答：因为这样做，可以更少地违背红黑树的性质，更容易恢复红黑树应有的性质。

双红修正

包含两种操作
- 结点左右旋转
- 改变结点颜色
双红修正是一个从底向上的循环过程。
一共包含三种场景：
- 场景1：存在 uncle 结点
- 场景2-1：不存在 uncle 结点，自己是左孩子
- 场景2-2：不存在 uncle 结点，自己是右孩子
注：黑色即被认为不存在。

修正场景分析

场景1：存在 uncle 结点

场景2：不存在 uncle 结点

场景2-1：不存在 uncle 结点，自己是左孩子

场景2-2：不存在 uncle 结点，自己是右孩子

其中，场景2-1 和场景2-2 的结果对比如下：

示例

代码：数据结构

#include <stdio.h>

// 状态码
typedef int Status;
#define OK 1
#define ERROR 0 

// 红黑 
#define BLACK 0
#define RED 1

// 红黑树结点 
struct RBNode{
	int value;	// 保存基本数据信息
	int color;	// 结点颜色，BLACK 和 RED，默认BLACK
	RBNode *left;	// 左子树
	RBNode *right;	// 右子树
	RBNode *parent;	// 父结点
	int size;	// 以该结点为根的树，包含了多少个子节点
	int cnt;	// 相同结点的个数
	// 传入结点保存的数值，并初始化各个变量
	RBNode(int _value)
	{
		value = _value;
		color = BLACK;
		left = NULL;
		right = NULL;
		parent = NULL;
		size = 1;
		cnt = 1;
	 } 
};

代码：左旋、右旋

// 左旋 
// 将传入的 X 结点进行左旋与当前树的根结点，在旋转过程中，更新根结点
Status Left_Rotate(RBNode *x, RBNode *&root)
{
	RBNode *y = x->right;
	x->right = y->left; 
	if(y->left)
		y->left->parent = x;
	y->parent = x->parent;
	
	// 若恰好x就是根结点 
	if(!x->parent)
		root = y;
	else
	{
		if(x == x->parent->left)
			x->parent->left = y;
		else
			x->parent->right = y;
	} 
	x->parent = y;
	y->left = x;
	// 更新信息
	update_node_size(x);
	update_node_size(y); 
	return OK;
}

// 右旋 
// 将传入的 X 结点进行右旋与当前树的根结点，在旋转过程中，更新根结点
Status Right_Rotate(RBNode *x, RBNode *&root)
{
	RBNode *y = x->left;
	x->left = y->right; 
	if(y->right)
		y->right->parent = x;
	y->parent = x->parent;
	
	// 若恰好x就是根结点 
	if(!x->parent)
		root = y;
	else
	{
		if(x == x->parent->left)
			x->parent->left = y;
		else
			x->parent->right = y;
	} 
	x->parent = y;
	y->right = x;
	// 更新信息
	update_node_size(x);
	update_node_size(y); 
	return OK;
}

// 更新信息 
Status update_node_size(RBNode *node)
{
	int size = node->cnt;
	if(node->left)
		size += node->left->size;
	if(node->right)
		size += node->right->size;
	node->size = size;
	return OK;
 } 

// 获取node结点的uncle指针
RBNode *uncle_node(RBNode *node)
{
	RBNode *parent = node->parent;
	RBNode *grandparent = parent->parent;
	if(parent == grandparent->left)
		return grandparent->right;
	else
		return grandparent->left;
 }

代码：双红修正

// 核心：双红修正
Status Fix_Double_Red(RBNode *node, RBNode *&root)
{
	// 从底向上修正的循环
	while(1)
	{
		// 到根，返回 
		if(node == root)
		{
			node->color = BLACK;
			return OK; 
		}
		
		RBNode *parent = node->parent;
		// 完成修正，返回 
		if(parent->color == BLACK)
			return OK;
		RBNode *grandparent = node->parent->parent;
		RBNode *uncle = uncle_node(node);
		
		// 场景1 
		if(uncle && uncle->color == RED)
		{
			parent->color = BLACK;
			uncle->color = BLACK;
			grandparent->color = RED;
			node = grandparent;
		 }
		// 场景2 
		else
		{
			// 场景2-1
			if(parent == grandparent->left)
			{
				if(node == parent->left)
				{
					// 染色 旋转 
					parent->color = BLACK;
					grandparent->color = RED;
					Right_Rotate(grandparent, root);
				}
				else
				{
					// 染色 两次旋转 
					node->color = BLACK;
					grandparent->color = RED;
					Left_Rotate(parent, root); 
					Right_Rotate(grandparent, root);
				}
			}
			// 场景2-2
			else
			{
				if(node == parent->right)
				{
					// 染色 旋转 
					parent->color = BLACK;
					grandparent->color = RED;
					Left_Rotate(grandparent, root);
				}
				else
				{
					// 染色 两次旋转 
					node->color = BLACK;
					grandparent->color = RED;
					Right_Rotate(parent, root); 
					Left_Rotate(grandparent, root);
				}
			}
			// 完成场景2-1或2-2，就算完成了 
			return OK; 
		}
	}
	 
	// 出错 
	return ERROR; 
}

代码：插入操作

// 插入操作
Status Node_Insert(RBNode *&root, RBNode *node)
{
	RBNode *ptr = root;
	while(ptr != node)
	{
		ptr->size++;
		// 如果当前插入结点值已经存在
		if(node->value == ptr->value)
		{
			ptr->cnt++;
			return OK;
		}
		// 若不存在，则继续寻找位置插入
		else if(node->value < ptr->value)
		{
			if(!ptr->left)
			{
				ptr->left = node;
				node->parent = ptr;
			}
			ptr = ptr->left;
		 } 
		else if(node->value > ptr->value)
		{
			if(!ptr->right)
			{
				ptr->right = node;
				node->parent = ptr;
			}
			ptr = ptr->right;
		 } 
	}
	node->color = RED;
	Fix_Double_Red(node, root);
	return OK;
 }

5.2.4 B树、B+树

定义

查找

查找包括两个基本操作
1. 在B树中找结点
2. 在结点内找关键字

插入

将关键字 key 插入 B树的过程：
1. 定位
  
  利用前述的 B树查找算法，找到插入该关键字的最底层的某个非叶结点
2. 插入
  
  在B树中，每个非失败结点的关键字个数都在区间[ m/2向上取整 - 1, m - 1]内。
  - 插入后关键字个数小于 m：可以直接插入
  - 否则：对结点进行分裂（B树高度+1）

删除

三种情况
1. 直接删除关键字（删除后仍然是满足最小关键字个数）
2. 兄弟够借：借、调整
3. 兄弟不够借：合并

B+树

主要差异
1. 在 B+树中，具有 n 个关键字的结点只含有 n 棵子树，即每个关键字对应一棵子树；
  
  而在B树中，具有 n 个关键字的结点含有 n+1 棵子树。
2. 在 B+树中，每个结点（非根内部结点）的关键字个数 n 的范围是 m/2向上取整 <= n <= m
  
  （而根结点是2 <= n <= m）
  
  在 B树中，每个结点（非根内部结点）的关键字个数 n 的范围是 m/2向上取整 <= n <= m-1
  
  （而根结点是1 <= n <= m-1）
3. 在 B+树中，叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中；
  
  而 B树中，最外层的终端结点包含的关键字和其他结点包含的关键字是不重复的。
4. 在 B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

5.3 散列结构

5.3.1 散列表（哈希表）

定义

根据关键字而直接进行访问的数据结构。

散列表建立了关键字和存储地址之间的一种直接映射关系。
时间复杂度

理想情况下，为O(1)，即与表中元素个数无关。
散列函数

一个把查找表中的关键字映射成该关键字对应的地址的函数。

记为 Hash(key) = Addr
冲突

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称为冲突。
常用散列函数
1. 直接定址法
2. 除留余数法
3. 数字分析法
4. 平方取中法
5. 折叠法
6. 伪随机数法

5.3.2 处理冲突

开放定址法

拉链法

拉链法的优点：

非同义词不会冲突，无“聚集”现象

链表上结点空间动态申请，更适合于表长不确定的情况

5.3.3 散列表的查找

流程

示例

效率分析

5.3.4 结论

散列表技术具有很好的平均性能，优于一些传统的技术
链地址法 优于开地址法
除留余数法作散列函数优于其他类型函数

六、排序

6.0 知识框架

基本概念
- 稳定性
- 时间复杂度
- 空间复杂度
- 操作：比较、移动
内部排序
- 插入排序
  - 直接插入排序
  - 折半插入排序
  - 希尔排序
- 交换排序
  - 冒泡排序
  - 快速排序
- 选择排序
  - 简单选择排序
  - 堆排序
- 归并排序
- 基数排序
外部排序
- 多路归并排序

6.1 插入排序

基本思想：

每次将一个待排序的记录按关键字大小插入前面已经排好序的子序列，直到全部记录插入完成。

根据寻找插入位置的不同方法，可以有：

直接插入排序、折半插入排序、希尔排序。

注：A[0]并不存储元素，从A[1]开始存储

6.1.1 直接插入排序

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
适用：顺序存储、链式存储

// 注：A[0]并不存储元素，从A[1]开始存储
Status InsertSort(ElemType A[], int n)
{
    int i, j;
    for(i=2; i<=n; i++)	// 将A[2]-A[n]插入到前面已经排序的序列中
    {
        if(A[i] < A[i-1])
        {
            A[0] = A[i];	// 复制为哨兵
            for(j=i-1; A[0]<A[j]; j--)
                A[j+1] = A[j];	// 逐个后挪
            A[j+1] = A[0];	// 直到找到插入位置，则复制进插入位置
        }
    }
    return OK;
}

6.1.2 折半插入排序

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
适用：仅顺序存储

// 注：A[0]并不存储元素，从A[1]开始存储
Status InsertSort(ElemType A[], int n)
{
    int i, j, low, high, mid;
    for(i=2; i<=n; i++)
    {
        A[0] = A[i];
        // 先找位置
        low = 1, high = i-1;
        while(low <= high)
        {
            mid = (low+high)/2;
            if(A[mid] > A[0])
                high = mid-1;
            else
                low = mid + 1;
        }
        // 移动(应该插入到 high+1 的位置！)
        for(j=i-1; j>=high+1; j--)
            A[j+1] = A[j];
        A[high+1] = A[0];
    }
    return OK;
}

6.1.3 希尔排序

又称“缩小增量排序”
基本思想：先将待排序表按间隔取记录，分割成若干[i, i+d, i+2d, i+3d, ...]的特殊子表，对各个子表分别进行直接插入排序，此时，就会总体呈现“基本有序”，再对全体记录（也相当于d=1）进行直接插入排序。
时间复杂度：O(n^1.3)
空间复杂度：O(1)
稳定性：不稳定
适用：仅顺序存储

// 注：A[0]并不存储元素，从A[1]开始存储
Status ShellSort(ElemType A[], int n)
{
    int dk, i, j;
    for(dk=n/2; dk>=1; dk=dk/2)	// 增量变化，无统一规定
    {
        for(i=dk+1; i<=n; ++i)
        {
            if(A[i] < A[i-dk])
            {
                A[0] = A[i];	// 暂存
                for(j=i-dk; j>0 && A[0]<A[j]; j-=dk)
                    A[j+dk] = A[j];	// 向后挪
                A[j+dk] = A[0];	// 插入
            }
        }
    }
    return OK;
}

6.2 交换排序

基本思想：

根据序列中两个元素关键字的比较结果来对换这两个记录再序列中的位置。

有：

冒泡排序、快速排序

6.2.1 冒泡排序

基本思想：

从后往前，两两比较相邻元素，若是逆序则交换位置，此次结果会把最小的换到第一个位置。而后第一个元素不动，继续…

每一趟冒泡的结果是把序列中最小元素放到了序列的最终位置。下一趟冒泡时，前一趟已经确定的元素不再参与。如此最多做n-1趟就能把所有元素排好序。
优化：

若在某一趟中，没有发生任何交换，说明已经排序好了，可以提前结束。
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定

Status BubbleSort(ElemType A[], int n)
{
    bool flag = true;	// 表示本趟冒泡是否发生交换
    for(int i=0; i<n-1 && flag; i++)
    {
        flag = false;
        for(int j=n-1; j>i; j--)
            if(A[j-1] > A[j])
            	swap(A[j-1], A[j]), flag = true;	// 交换
    }
}

6.2.2 快速排序

基本思想：分治思想

在待排序表L[1...n]中任取一个元素pivot作为枢轴（基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分，前部分L[1...k-1]中元素均小于pivot，后部分L[k+1...n]均大于pivot，而pivot放在L[k]，这就是一次划分。然后分别递归地对两个子表重复上述过程，直到每部分内只有一个元素或空为止。
时间复杂度：O(n log2 n)
空间复杂度：O(log2 n)
稳定性：不稳定

快速排序不是自然排序（自然排序：最初序列越有序，则排序越快）

快速排序在最初序列有序时，反而是更慢！

// 快速排序
Status QuickSort(ElemType A[], int low, int high)
{
    if(low < high)	// 递归跳出的条件
    {
        // 进行划分产生前部分、后部分，并返回 pivot 的位置 k
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos-1);
        QuickSort(A, pivotpos+1, high);
    }
    return OK;
}
// 一趟划分
int Partition(ElemType A[], int low, int high)
{
    ElemType pivot = A[low];	// 取第一个作为划分基准
    while(low < high)
    {
        // low 空出来了，从 high 部找一个小于 pivot 的放到 low 部
        while(low < high && A[high] >= pivot)
            high--;
        A[low] = A[high];
        // high 空出来了，从 low 部找一个小于 pivot 的放到 high 部
        while(low < high && A[low] <= pivot)
            low++;
        A[high] = A[low];
    }
    // high = low = k
    A[low] = pivot;
    return low;
}

6.3 选择排序

基本思想：

每一趟（如第 i 趟）在后面 n-i+1（ i =1,2,3,…,n-1）个排序元素中选取关键字最小的元素，作为有序子序列的第 i 个元素，直到第 n-1 趟做完，待排序元素只剩下 1 个，就排序完成了。

6.3.1 简单选择排序

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定

Status SelectSort(ElemType A[], int n)
{
    for(int i=0; i<n-1; i++)
    {
        int min = i;	// 记录最小元素位置
        for(int j=i+1; j<n; j++)
            if(A[j] < A[min])
                min = j;	// 更新最小元素位置
        if(min != i)
            swap(A[i], A[min]);
    }
    return OK;
}

6.3.2 堆排序

基本思想：

首先把所有元素生成初始调整成有序堆，堆顶必为最值（大根堆最大值，小根堆最小值），输出根，然后重新调整剩余堆，然后再输出堆，再调整堆…直到堆中1个元素也输出结束。
- 问1：如何生成初始有序堆？
- 问2：如何调整剩余为有序堆？
时间复杂度：O(n log2 n)
空间复杂度：O(1)
稳定性：不稳定

注：虽然堆排序的逻辑结构是树形结构，但是存储结构是顺序存储！！！

为什么是“从 i=[n/2] 开始，到 i=1，反复调整堆”？

我们实际上需要从最后一个非叶子结点开始调整。

根据完全二叉树的特点推导！结点序号 n 的双亲一定是 n/2（整除）。

那么最后一个叶子结点应该是 n/2

// 注：A[0] 并不存储元素，从 A[1] 开始存储。下面以大根堆为例。
// 构建大根堆
Status BuildMaxHeap(ElemType A[], int len)
{
    for(int i=len/2; i>0; i--)	// 从 i=[n/2]~1，反复调整堆
        HeadAdjust(A, i, len);
    return OK;
}
// 将元素A[k]为根的子树进行调整
Status HeadAdjust(ElemType A[], int k, int len)
{
    A[0] = A[k];	// 暂存
    for(int i=2*k; i<=len; i*=2)	// 沿 key 较大的子节点向下筛选
    {
        if(i < len && A[i] < A[i+1])
            i++;
        if(A[0] >= A[i])	// 筛选结束
            break;	
        else				// 调整最大的到此次的根上
        {
            A[k] = A[i];
            k = i;
        }
    }
    A[k] = A[0];
    return OK;
}

// 堆排序
Status HeapSort(ElemType A[], int len)
{
    // 初始构建堆
    BuildMaxHeap(A, len);
    // n-1趟的交换和建堆
    for(int i=len; i>1; i--)
    {
        Visit(A[1]);		// 输出堆顶
        swap(A[i], A[1]);		// 把堆底元素元素拉到堆顶，len-1
        HeadAdjust(A, 1, i-1);	// 必然已经乱序，剩余len-1个重新调整堆序
    }
    return OK;
}

6.4 归并排序

基本思想：

将两个或两个以上的有序表合成一个新的有序表。

最初可以视为是 n 个有序子表，每个子表长度为1，两两合并，得到 n/2 向上取整 个长度为2或1的有序表；继续两两合并…直到合成为一个长度为n的有序表。

又称“2 路归并排序”
时间复杂度：O(n log2 n)
空间复杂度：O(n)
稳定性：稳定

// 归并
Status Merge(ElemType A[], int low, int mid, int high)
{
    ElemType *B = (ElemType*)malloc( (n+1) * sizeof(ElemType) );	// 辅助数组 B
    // 表A 的两段 [low...mid] 和 [mid+1...high] 各自有序，将它们合并为一个有序表
    int i, j, k;
    // A 中元素全复制到 B 中
    for(k=low; k<=high; k++)
        B[k] = A[k];	
    // 开始检测依次赋值
    for(i=low, j=mid+1, k=i; i<=mid && j<=high; k++)
    {
        if(B[i] <= B[j])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }
    // 未检测完的部分（下面两个只会有一个成立）
    while(i <= mid)
        A[k++] = B[i++];
    while(j <= high)
        A[k++] = B[j++];
}

// 归并排序
Status MergeSort(ElemType A[], int low, int high)
{
    if(low < high)
    {
        // 从中间划分为两个子序列，并通过归并排序为有序
        int mid = (low+high)/2;
        MergeSort(A, low, mid);	
        MergeSort(A, mid+1, high);
        // 两个有序归并为一个有序
        Merge(A, low, mid, high);
    }
}

6.5 基数排序

基本思想：

借助多关键字排序的思想对单逻辑关键字进行排序。

方法：
- 最高位优先法（ MSD ）
- 最低位优先法（ LSD ）
时间复杂度：O( d*(n + r) )

其中，基数排序需要进行 d 趟分配和收集，每趟分配需要O(n)，收集需要O®。与序列初始状态无关（不是自然排序）。
空间复杂度：O(r)

辅助 r 个队列，r 个队头指针，r 个队尾指针。
稳定性：稳定