数据结构笔记2

标签：结点 遍历 删除 笔记 关键字 二叉树 顶点 数据结构

数据结构

• 第三章 栈
• 第四章 队列
• 第五章 数组和特殊矩阵
• 第六章 串
• 第七章 树与二叉树
• 第八章 图
• 第九章 查找
• 第十章 排序

第三章 栈

1. 栈：只允许一端插入或者删除的线性表。
2. 栈分为顺序栈和链栈。
3. 顺序栈的实现：

#define MaxSize 50
typedef struct {
	ElemType data[MaxSize];			//存放数据元素
	int top;						//定义栈顶指针
}SqStack;
top = -1;

4. 顺序栈的初始化：

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

5. 顺序栈判栈空：

bool StackEmpty(SqStack s){
	if (S.top == -1)
		return true;
	else
		return false;
}

6. 顺序栈进栈：

bool Push(SqStack &s,ElemType x){
	if(S.top == MaxSize - 1)
		return false
	S.data[++top] = x;				//指针＋1入栈
	return true;
}

7. 顺序栈出栈：

bool Pop(SqStack &s,ElemType &x){
	if(S.top == -1)
		return false;
	x = S.data[S.top--];
	return true;
}

8. 顺序表读栈顶元素：

bool GetTop(SqStack S,ElemType &x){
	if(S.top == -1)
		return false;
	x = S.data[S.top];
	return true;
}

9. 共享栈
   
10. 链栈的定义：

typedef struct LinkNode{
   ElemType data;
   struct LinkNode *next;						//指针域
}ListStack;

第四章 队列

1. 队列的定义：允许一端输入，另一端输出的线性表。
2. 队列的定义：

#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
	int front,rear;
}SqQueue;

3. 队头删除，队尾插入
4. 队列初始化操作：

void InitQueue(SqQueue &Q){
	Q.rear = Q.front = 0; 
}

5. 队列判空：

bool QueueEmpty(SqQueue Q){
	if(Q.rear == Q.front)
		return true;
	else
		return false;
}

6. 队列入队：

bool EnQueue(SqQueue &Q,ElenType x){
	if(队列满)
		return false;
	Q.data[Q.rear] = x;			//插入队尾
	Q.rear = Q.rear + 1;
}

循环队列中队列入队操作

if((Q.rear + 1)%MaxSize == Q.front)
	return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1)%MaxSize;
return true;

7. 队列出队

bool DeQueue(SqQueue &Q,ElemType &x){
	if(Q.rear == Q.front)
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1)%MaxSize;	//队头取模加1
	return true;
}

8. 循环队列判断队空/队满条件

1. 牺牲一个单元来区分队空，队满（队头在队尾下一个位置则队满）
   队满：（Q.rear + 1）% MaxSize == Q.front
   队空：Q.front == Q.rear
   队列中元素个数：（Q.rear - Q.front + MaxSize）% MaxSize

2. 增设size变量（删除 size - 1 ,插入 size + 1 ）
   队满：Q.size == MaxSize；
   队空：Q.size == 0;

3. tag变量（删除 tag变量置0，插入 tag变量置1）
   tag == 1 : Q.front 等于 Q.rear -->队满
   tag == 0 : Q.front 等于Q,rear -->队空

9. 队列链式存储

typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct{
	LinkNode *front,*rear;			//队头和队尾
}LinkQueue;

不带头结点时：Q.front == NULL  且 Q.rear == NULL 时，链栈为空

10. 链队结构：
    
11. 带头结点的链队初始化

void InitQueue(LinkQueue &Q){
	Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));		//带头结点
	Q.front ->next = NULL;		//初始化为空
}

12. 带头结点的链队判空

bool IsEmpty(LinkQueue Q){
	if(Q.front == Q.rear)
		return true;
	else
		return false;
}

13. 带头结点链队入队

void EnQueue(LinkQueue &Q,ElemType x){
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
	s->data = x;
	Q.rear ->next = s;	//连接链尾
	s->next = NULL;
	Q.rear  = s;				//修改尾指针
}

14. 带头结点链队出队

bool DeQueue(LinkQueue &Q,ElemType &x){
	if(Q.front == Q.rear)
		return false;
	LinkNode *p = Q.front ->next;
	x = p->next;
	Q.front -> next = p->next;
	if(p  == Q.rear)
		Q.rear = Q.front;
	free(p);
	return true;
}

15. 双端队列：允许两端都可以进行插入和删除操作的线性表。
16. 栈的括号匹配：
    
17. 栈的括号匹配算法实现：

bool bracketCheck(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 false;
			char topElem;
			Pop(S,Stack);
			if(str[i] == ')' && topElem == '(')
				return false;
			if(str[i] == ']' && topElem == '[')
				return false;
			if(str[i] == '}' && topElem == '{')
				return false;
		}
	}
	return StackEmpty(S);			//说明匹配成功
}

18. 栈——中缀表达式转成后缀和前缀表达式

Reverse Polish Natation(逆波兰表达式 == 后缀表达式)
Polish Natation(波兰表达式 = 前缀表达式)

19. 中缀转后缀表达式要遵循左优先原则
20. 中缀转后缀表达式机算(需要借助栈，遵循左优先原则一次扫描中缀表达式每一项)：

1. 遇到操作数直接加入后缀表达式
2. 遇到界限符，若为"("则依次入栈，若为“)”,则依次弹出栈中运算符，并加入后缀表达式，直到弹出“(”为止，注意“(”直接删除，不加入后缀表达式。
3. 遇到运算符，若优先级高于除"("外的栈顶元素，则直接入栈，否则从栈顶开始，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，直到遇到优先级低于她的运算符或者遇到为止，之后将当前运算符入栈。

21. 中缀转前缀表达式要遵循右优先原则
22. 栈的深度为栈中元素个数。
23. 后缀表达式求值：

从左往右依次扫描表达式每一项，遇到操作数则压入栈中，若为操作符则从栈中退出两个操作数X和Y，形成Y操作数X，并将结果压入栈中，最后处理完栈顶就存放结果。

24. 利用中缀表达式求值：中缀转后缀 + 后缀表达式求值 有两个栈：操作数栈和运算符栈。
25. 利用栈的先进后出特性，递归的精髓在于能否将原始问题1转换成属性相同但问题规模较小的问题。

第五章 数组和特殊矩阵

1. 数组：具有一个或多个相同类型数据元素的有限集合。(下标从0开始)
2. 数组的存储分为行优先和列优先。
3. 对称矩阵压缩存储(行优先)：

只存储主对角线+下三角区(存储在一维数组中)

4. 要注意是从a11还是a00开始存储。
5. 稀疏矩阵的压缩存储使用十字链表法。

第六章 串

第七章 树与二叉树

1. 树：具有0个或多个结点（有限集）。存在空树。
2. 结点的度：该结点的孩子个数。
3. 树的度：树中结点的最大度数。
4. 树的高度或者深度是树中结点的最大层数。
5. 结点的高度为以该结点为根的子树高度。（自身结点算一层）。
6. 两结点之间的路径由两节点之间的节点序列构成。
7. 路径长度是路径所经过边的个数。
8. 森林：0或多个互不相交的树的集合。
9. 树的概念：

1. m叉树是每个结点最多拥有m个孩子。
2. 树的结点树n等于所以结点的度数之和加1.
3. 度为m的树中第i层最多拥有m^(i-1)个结点。
4. 高度为h的m叉树最多有(m^h -1)/(m-1) (利用等差数列)
5. 度为m，具有n个结点的树的最小高度h为【logm(n(m-1) + 1)】
6. 度为m，具有n个结点的树的最大高度h为n-m+1。

10. 二叉树的定义：每个结点最多有两个子树。或为空树。
11. 满二叉树：高度为h，具有2^h-1个结点的二叉树。每层具有最多的二叉树。
12. 完全二叉树：高度为h,具有n个结点，其每个结点编号与满二叉树中结点编号相同。
13. 二叉排序树：左子树结点小于根结点，右节点关键字大于根节点。
14. 平衡二叉树：任意子树左右节点高度之差绝对值要小于1.
15. 二叉树性质：

1. 非空二叉树叶子结点树等于度为2的结点数加1，即为n0 = n2 + 1。
2. 非空二叉树的第k层最多有2^(k-1)个结点。
3. 高度为h的二叉树至多有2^h -1个结点。
4. 具有n个结点的完全二叉树的高度为log2(n-1)或log2n+1。

16. 链式存储结构：

typedef struct BiTNode{
	ElemType data;						//数据域
	struct BiTNode *lchild,*rchild;		//左右指针
}BiTNode,*BiTree;

17. 二叉树的遍历：先序遍历，中序遍历，后序遍历。
18. 先序遍历：

void PreOrder(BiTree T){
	if(T != NULL){
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

19. 中序遍历：

void InOrder(BiTree T){
	if(T != NULL){
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

20. 后序遍历：

void PostOrder(BiTree T){
	if(T != NULL){
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

21. 层次遍历：

void LevelOrder(BiTree T){
	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);	//右孩子不空则访问
	}
}

22. 先序序列和中序序列可以确定一颗二叉树。
23. 后序序列和中序序列可以确定一颗二叉树。
24. 线索二叉树： 以一定规则将二叉树中的结点排列成一个线性序列。
25. n个结点的二叉树有n+1个空链域，

若结点有左子树，则其 lchild 域指示其左孩子，否则令 lchild 域指示其前驱。
若结点有右子树，则其 rchild 域指示其右孩子，否则令 rchild 域指示其后继。

26. 线索二叉树的存储结构：

typedef struct ThreadNode{
	ElemType data;				//数据元素
	struct ThreadNode *lchild,*rchild;	//左右孩子指针
	int ltag,rtag;		//左右线索标志。
}ThreadNode,*ThreadTree; 

27. 中序线索二叉树：

设一个指针 pre 始终指向刚刚访问过的结点，而指针p 指向当前访问的结点，由此记录下遍历过程中访问结点的先后关系。结点 p 为根的子树中序线索化的过程
① 如果 p 非空，左子树递归线索化。
② 如果 p 的左孩子为空，则给 p 加上左线索，将其 LTag 置为1，让 p 的左孩子指针指向前驱；否则将 p 的 LTag 置为0。
③ 如果 pre 的右孩子为空，则给 pre 加上右线索，将其 RTag 置为1，让 pre 的右孩子指针为 p (后继)；否则将 pre 的 RTag 置为 0。
④ 将 pre 指向刚访问过的结点 p，即 pre = p。
⑤ 右子树递归线索化。

28. 先序线索二叉树：
    
    
29. 后序线索二叉树：
    
30. 树的存储结构：双亲表示法，孩子表示法，孩子兄弟表示法。
31. 双亲表示法：采用顺序存储数组的方式。
    

定义一个结构体数组，数组的数据域包含树的数据元素，数组的双亲位置域是data数据域的的双亲的位置。
优点：找双亲结点容易，找孩子结点难（需要遍历整个数组）。适用于并查集。

32. 孩子表示法：利用顺序存储和链式存储
    

首先利用CTBox定义一个结构体数组，再定义一个结点,在nodes数组中存储结点信息，其后面链接其直接孩子结点。
优点：找孩子结点很方便，缺点：找双亲结点需要遍历整个数组。

33. 孩子兄弟表示法：采用链式存储。
    
    

首先定义一个结构体来存储数据域和两个指针域，左孩子为指向第一个孩子结点，右孩子为指向右兄弟结点。

34. 利用孩子兄弟表示法来存储森林。
    
35. 树与二叉树之间的转换。
    

利用孩子兄弟表示法，注意同级兄弟之间需要用右指针来进行互联。

36. 森林与二叉树之间的转换。
    

仍然使用孩子兄弟表示法，根节点为同级结点。遵循同级兄弟来进行右子树互联。

37. 二叉树和树之间的转换。
    

其右子树为同级结点

38. 二叉树和森林之间的转换。
    

注意根节点为初始化的森林根节点。

39. 树的遍历：先根遍历，后根遍历，层次遍历。
    先根遍历：
    

先访问根节点，不断递归。

后根遍历：

先遍历其他子树或者结点，最后遍历根结点。

层次遍历：利用队列来进行遍历。

40. 树的先序遍历和中序遍历。
    先序遍历
    

第一棵子树作为根节点来遍历。

中序遍历

第一棵子树的最左边结点为树的根节点。

41. 哈夫曼树：带权二叉树。
42. 结点的权：有某种现实含义的数值（如：表示结点的重要性等）
43. 结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
44. 树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL）

46. 哈夫曼树的构造：

将集合中最小权重的3个结点构成一棵二叉树，其中最大的权重作为根节点，再在集合中寻找最小的2个结点，将其中最大结点作为根节点，不断构造，使得权重最高的结点距离根节点最近。

47. 哈夫曼编码：
    

主要是运用二叉树的左右子树来评判传输数据。

48. 并查集：主要操作是”并“入子树，”查“寻结点属于哪个子树。
    

用不同子树表示不同集合，并操作是将一个子树并入另一个子树，意思为使一个集合并入另一个集合操作范围内，而查操作是查询结点属于哪个集合。

49. 并查集代码实现：

#define SIZE 13
int UFSets[SIZE];

//初始化并查集
//利用数组来存储并查集，数组中数据若大于0则为分支结点，其值为其双亲结点的数组下标，若数组下标小于0.则其为根节点。
void Initial(int S[]){
	for(int i = 0;i < SIZE ;i++){
		S[i] = -1;
	}
}

//查.值大于1为分支节点，小于1为根节点。
void Find(int S[],int x){
	while(S[x] > 0){
		x = S[x];
	}
	return x;
}

//并操作
void Union(int S[],int Root1,int Root2){
	//要求Root1和Root2为不同节点
	if(Root1 == Root2){
		return ;
	}
	//将Root1的根连接到Root2下面
	S[Root1] = Root2;
}

//①用根节点的绝对值表示树的结点总数②Union操作，让小树合并到大树,复杂度：O(log2n)

50. 并查集”查“操作优化：将同一个子树的所有结点挂在所属根结点子树下。

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

int Find(int S[],int x){
	int root = x;
	while(S[root] >0) root = S[root];
	while(x!=root){
	 int t = S[x];			//将t指向x的父节点
	 S[x] = root;			//将x的结点指向根节点
	 x = t;   				//将当前指针指向x的父节点
	}
}

第八章 图

1. 图G由顶点集V和边集E组成。线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集。
2. 图可以只有点，但不可以只有边，每个边的两端必须要有端点。
3. 边无方向为无向边，图为无向图。边有方向为有向边，图为有向图.方向不同的边为不同边，
4. 简单图——①不存在重复边；②不存在顶点到自身的边。
5. 多重图——图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图
6. 对于无向图：顶点v的度是指依附于该顶点的边的条数。即无向图的全部顶点的度的和等于边数的2倍
7. 对于有向图：
   入度是以顶点v为终点的有向边的数目，记为ID(v)；
   出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。
8. 路径——顶点vp到顶点vq之间的一条路径是指顶点序列，
9. 回路——第一个顶点和最后一个顶点相同的路径称为回路或环
10. 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径。
11. 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
12. 路径长度——路径上边的数目
13. 点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。
14. 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
15. 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。

17. 设有两个图G= (V, E)和G¢= (V¢, E¢)，若V¢是V的子集，且E¢是
    E的子集，则称G¢是G的子图。
    若有满足V(G¢) = V(G)的子图G¢，则称其为G的生成子图(包含所有的点，但边可以省略)

23. 无向完全图——无向图中任意两个顶点之间都存在边
24. 有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧
25. 边数很少的图称为稀疏图， 反之称为稠密图

27. 图的存储：邻接矩阵法(使用二维数组存储)

存储有向图和无向图

#define MaxVertexNum 100
typedef struct{
	char Ver[MaxVertexNum];					//顶点表
	int Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵和边表
	int vernum,arenum;			//图的当前顶点和边数
}MGraph;

//存储带权图

#define MaxVertexNum 100
#define INFINITY  最大的int值					//宏定义
typedef char VertexType;					//结点数据类型
typedef int EdgeType;						//权值数据类型
typedef struct{
	char Ver[MaxVertexNum];					//顶点
	int Edge[MaxVertexNum][MaxVertexNum];	//存储权值
	int vernum,arenum;			//图的当前顶点和边数
}MGraph;

28. 邻接矩阵性质：数组实现的顺序存储，空间复杂度高，不适合存储稀疏图

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

29. 邻接表法：顺序+链式存储，
    

//定义边
typedef struct ArcNode{
	int adjvex;				//边指向哪一个结点
	struct ArcNode *next;	//指向下一条边
	//INFOYTYPE info		//边权值
}ArcNode;

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

//定义图
typedef struct{
	AdjList vertices;		
	int vexnum,arcnum;
}ALGraph;

30. 十字链表法和邻接多重表
31. 十字链表法
    

如何找到指定顶点的所有出边？——顺着绿色线路找
如何找到指定顶点的所有入边？——顺着橙色线路找
注意：十字链表只用于存储有向图

32. 邻接多重表存储无向图
    
    

33. 图的基本操作

• Adjacent(G,x,y)：判断图G是否存在边<x, y>或(x, y)。
• Neighbors(G,x)：列出图G中与结点x邻接的边。
• InsertVertex(G,x)：在图G中插入顶点x。
• DeleteVertex(G,x)：从图G中删除顶点x。
• AddEdge(G,x,y)：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。
• RemoveEdge(G,x,y)：若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。
• FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点
或图中不存在x，则返回-1。
• NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一
个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
• Get_edge_value(G,x,y)：获取图G中边(x, y)或<x, y>对应的权值。•Set_edge_value(G,x,y,v)：设置图G中边(x, y)或<x, y>对应的权值为v。

34. Adjacent(G,x,y):判断图是否存在边
    
    

在无向图中，使用使用邻接矩阵存储可直接查询边即可。使用邻接表则最大时间复杂度为点个数。
在有向图中，使用邻接矩阵存储直接查询，使用邻接矩阵也是为点个数。

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

在无向图中，邻接矩阵中查询顶点的边需要遍历矩阵，使用邻接表是顶点个数。
在有向图中，邻接矩阵中为遍历矩阵，使用邻接表法需要根据入边和出边分为相应的个数

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

在有向图和无向图中，在邻接矩阵存储方法中增加一个顶点只需要在矩阵中增加一行一列，在邻接表法中只需要在顶点数组中增加一个顶点即可。

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

在无向图中，使用邻接矩阵法删除一个顶点只需要将该顶点行列置空即可，使用邻接表法则将顶点表中顶点后指针置空，让后在遍历整个数组及其后缀，将含有删除的顶点去除
在有向图中，使用邻接矩阵法需要遍历所有的边将其去除，使用邻接表法分清删入边和出边，

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

在有向图和无向图中，使用邻接矩阵法则直接在表中添加即可，使用邻接表法则是直接在相应顶点后添加相应的指针即可。

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

在有向图和无向图中，使用邻接矩阵法则直接在表中删除数据即可，在邻接表法中需要根据边的数量来确定。

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

在无向图中。使用邻接矩阵则需要遍历数据点，使用邻接表法则直接查找数据顶点即可。
在有向图中，使用邻接矩阵法需要遍历数组，使用邻接表则查看出边邻接点还是入边邻接点，

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

在无向图中，使用邻接矩阵直接遍历数组即可，在邻接表中，直接查找点即可。

找边

43. 图的广度优先遍历BFS

具体代码流程
⼴度优先遍历（Breadth-First-Search, BFS）要点：
1.找到与⼀个顶点相邻的所有顶点
2.标记哪些顶点被访问过
3.需要⼀个辅助队列
4.FirstNeighbor(G,x)：求图G中顶点x的第⼀个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
5.NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的⼀个邻接点，返回除y之外顶点x的下⼀个邻接点的顶点号，若y是x的最后⼀个邻接点，则返回-1。
6.visit()标记结点

同⼀个图的邻接矩阵表示⽅式唯⼀，因此⼴度优先遍历序列唯⼀
同⼀个图邻接表表示⽅式不唯⼀，因此⼴度优先遍历序列不唯⼀
从不同结点开始遍历会导致遍历数列不同
若图为非连通图则代码需要改进

44. BFS的时间复杂度

邻接矩阵存储的图：访问 |V| 个顶点需要O(|V|)的时间查找每个顶点的邻接点都需要O(|V|)的时间，⽽总共有|V|个顶点时间复杂度= O(|V|2)
邻接表存储的图：
访问 |V| 个顶点需要O(|V|)的时间查找各个顶点的邻接点共需要O(|E|)的时间，

45. DFS遍历(深度优先遍历) = 树的先根遍历

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

46. 图的深度优先搜索
    

47. 若图为非连通图则算法需要改进
    

空间复杂度：来⾃函数调⽤栈，最坏情况，递归深度为O(|V|)(所有结点个数)
邻接矩阵存储的图：访问 |V| 个顶点需要O(|V|)的时间查找每个顶点的邻接点都需要O(|V|)的时间，⽽总共有|V|个顶点时间复杂度= O(|V|2)
邻接表存储的图：访问 |V| 个顶点需要O(|V|)的时间查找各个顶点的邻接点共需要O(|E|)的时间，时间复杂度= O(|V|+|E|)
同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀
同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀，深度优先⽣成树也唯⼀同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀，深度优先⽣成树也不唯⼀

48. 最短路径问题——BFS算法
    求无权图单源最短路径
    

在单源最短路径中，求顶点U到其他节点之间的最短距离，首先构建数组d[]和path[]，用来存储距离结点U的距离和最短距离的前驱结点，初始化完成后使用队列将U结点的相邻结点入队，然后将U进行出队。将U相邻结点的相邻节点入队，将U的相邻结点出队，并记录路径值和前驱结点下标。

49. 最短路径问题——Dijkstra算法(用于带权图和无权图)
    

初始化三个数组，用于存储是否找到最短路径，最短路径长度和最短路径长度前驱。
第1轮：循环遍历所有结点，找到还没确定最短路径，且dist 最⼩的顶点Vi，令final[i]=ture。
检查所有邻接⾃ Vi的顶点，若其final 值为false，则更新 dist 和 path 信息

主要过程！！！

50. 最短路径问题——Floyd算法(用于各顶点之间的最短路径)(带权图和无权图)
    
    
    
    

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

51. 最短路径总结
    
52. 有向⽆环图描述表达式
    有向⽆环图：若⼀个有向图中不存在环，则称为有向⽆环图，简称DAG图（Directed Acyclic Graph）
    V0
    用于构建最少顶点的表达式生成树。

根据表达式底部最多变量为一个变量一个。

53. 拓扑排序
    AOV⽹(Activity On Vertex NetWork，⽤顶点表示活动的⽹)：⽤DAG图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边<Vi, Vj>表示活动Vi必须先于活动Vj进⾏
    

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

代码实现：

将图中入度为0的点进行入栈，将栈顶元素出栈，并将栈顶元素指向的结点入栈，并将其入度减一，若入度为0则将其入栈。
时间复杂度：O(|V|+|E|)若采⽤邻接矩阵，则需O(|V|2)

逆拓扑排序

54. 关键路径
    
    在AOE⽹中仅有⼀个⼊度为0的顶点，称为开始顶点（源点），它表示整个⼯程的开始；也仅有⼀个出度为0的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。
    从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径称为关键路径，⽽把关键路径上的活动称为关键活动

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

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

第九章 查找

1. 查找⻓度——在查找运算中，需要对⽐关键字的次数称为查找⻓度
2. 平均查找⻓度（ASL, Average Search Length）—— 所有查找过程中进⾏关键字的⽐较次数的平均值
3. 顺序查找：从头到尾挨个查找

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;
}

//存在哨兵模式
typedef struct{
	ElemType *elem;
	int Tablen;
}SSTable;
int Search_Seq(SSTable ST,ElemType key){
	ST.elem[0] = key;
	int i = 0;
	for(i = ST.Table;elem[i]!= key;--i){
	return i;
	
	}
	
}

时间复杂度为O(n)

4. 折半查找：⼜称“⼆分查找”，仅适⽤于有序的顺序表。
   

只能用顺序表存储，不能用链表存储

折半查找判定树的构造

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

5. 分块查找
   

块内无序，块间有序，索引值为索引表中最大值
分块查找，⼜称索引顺序查找，算法过程如下：
①在索引表中确定待查记录所属的分块（可顺序、可折半）②在块内顺序查找
先折半查找索引表，确定索引表则在表内进行顺序查找

查找到索引表的条件
原因：最终low左边⼀定⼩于⽬标
关键字，high右边⼀定⼤于⽬标
关键字。⽽分块存储的索引表中保存的是各个分块的最⼤关键字
若索引表中不包含⽬标关键字，则折半查找索引表最终停在 low>high，要在low所指分块中查找

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

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

先找到最小不平衡子树。

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

平衡二叉树的删除操作具体步骤：
①删除结点（方法同“二叉排序树”）
• 若删除的结点是叶子，直接删。
• 若删除的结点只有一个子树，用子树顶替删除位置
• 若删除的结点有两棵子树，用前驱（或后继）结点顶替，并转换为对前驱（或后继）结点的删除。
②一路向北找到最小不平衡子树，找不到就完结撒花
③找最小不平衡子树下，“个头”最高的儿子、孙子
④根据孙子的位置，调整平衡（LL/RR/LR/RL）
• 孙子在LL：儿子右单旋
• 孙子在RR：儿子左单旋
• 孙子在LR：孙子先左旋，再右旋
• 孙子在RL：孙子先右旋，再左旋
⑤如果不平衡向上传导，继续②
• 对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传递）

A结点右旋，将A代替A的父亲结点，并将自己的右孩子变成父亲结点的左孩子，并将父亲结点变成自己的右孩子。
A结点左旋，将A替代A的父亲结点，并将自己的左孩子变成父亲结点的右孩子，并将父亲结点变成自己的左孩子。

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

9. 红黑树(Red-BlackTree)RBT)

平衡二叉树和红黑树对比
平衡二叉树AVL：插入/删除很容易破坏“平衡”特性，需要频繁调整树的形态。如：插入操作导致不
平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大），再进行 LL/RR/LR/RL 调整
红黑树 RBT：插入/删除 很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整，一
般都可以在常数级时间内完成
平衡二叉树：适用于以查为主、很少插入/删除的场景红黑树：适用于频繁插入、删除的场景，实用性更强

红黑树定义

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

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

性质1：从根节点到叶结点的最长路径不大于最短路径的2倍
性质2：有n个内部节点的红黑树高度 h ≤ 2log2（n + 1）红黑树查找操作时间复杂度=O(O(log2n))

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

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

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

12. B树
    B树的定义
    多路平衡查找树，B树中所被允许的孩⼦个数的最⼤值称为B树的阶，通常⽤m表示。⼀棵m阶B树
    或为空树，或为满⾜如下特性的m叉树：
    1）树中每个结点⾄多有m棵⼦树，即⾄多含有m-1个关键字。
    2）若根结点不是终端结点，则⾄少有两棵⼦树。
    3）除根结点外的所有⾮叶结点⾄少有 m/2的向上取整棵⼦树，即⾄少含有 m/2的向上取整-1个关键字。
    5）所有的叶结点都出现在同⼀层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。
    
    m阶B树的核⼼特性：
    1） 根节点的⼦树数∈[2, m]，关键字数∈[1, m-1]。
    其他结点的⼦树数∈[ , m]；关键字数∈[ -1, m-1]
    2）对任⼀结点，其所有⼦树⾼度都相同3）关键字的值：⼦树0<关键字1<⼦树1<关键字2<⼦树2<…. (类⽐⼆叉查找树 左<中<右)
    3）关键字的值：⼦树0<关键字1<⼦树1<关键字2<⼦树2<…. (类⽐⼆叉查找树 左<中<右)

B树最右边子树的最右边元素的值是最大的。
最⼩⾼度——让每个结点尽可能的满，有m-1个关键字，m个分叉

13. B树的插入和删除
    5阶B树——结点关键字个数m/2的向上取整 ≤n≤m-1即：2≤n≤4 （注：此处省略失败结点）
    

新元素⼀定是插⼊到最底层“终端节点”，⽤“查找”来确定插⼊位置
注意：B树的失败结点只能出现在最下⾯⼀层\

在插⼊key后，若导致原结点关键字数超过上限，则从中间位置m/2的向上取整将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置m/2的向上取整的结点插⼊原结点的⽗结点




B树插入的核心要求

核⼼要求：
①对m阶B树——除根节点外，结点关键字个数 m/2的向上取整≤n≤m-1
②⼦树0<关键字1<⼦树1<关键字2<⼦树2<…. ⌈m/2⌉ − 1
1.新元素⼀定是插⼊到最底层“终端节点”，⽤“查找”来确定插⼊位置
2.在插⼊key后，若导致原结点关键字数超过上限，则从中间位置m/2的向上取整将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置m/2的向上取整的结点插⼊原结点的⽗结点。若此时导致其⽗结点的关键字个数也超过了上限，则继续进⾏这种分裂操作，直⾄这个过程传到根结点为⽌，进⽽导致B树⾼度增1。

14. B树的删除
    1.若被删除关键字在终端节点，则直接删除该关键字（要注意节点关键字个数是否低于下限 ⌈m/2⌉ − 1）

2.若被删除关键字在⾮终端节点，则⽤直接前驱或直接后继来替代被删除的关键字直接前驱：当前关键字左侧指针所指⼦树中“最右下”的元素

3.直接后继：当前关键字右侧指针所指⼦树中“最左下”的元素

4.兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该结点、右（或左）兄弟结点及其双亲结点（⽗⼦换位法）

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

6.在合并过程中，双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少⾄0（根结点关键
字个数为1时，有2棵⼦树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关
键字个数减少到 ，则⼜要与它⾃⼰的兄弟结点进⾏调整或合并操作，并重复上述步骤，直⾄符合B树的要求为⽌。

15. B+树
    
    m阶B树：1） 结点中的n个关键字对应n+1棵⼦树
    2） 根节点的关键字数n∈[1, m] 其他结点的关键字数n∈[⌈m/2⌉, m]
    3）在B+树中，叶结点包含全部关键字，⾮叶结点中出现过的关键字也会出现在叶结点中
    4）在B+树中，叶结点包含信息，所有⾮叶结点仅起索引作⽤，⾮叶结点中的每个索引项只含有对应⼦树的最⼤关键字和指向该⼦树的指针，不含有该关键字对应记录的存储地址。

16. 散列表
    1.散列表（哈希表，Hash Table）：是⼀种数据结构。特点是：可以根据数据元素的关键字
    计算出它在散列表中的存储地址

2.散列函数（哈希函数）：Addr=H(key) 建⽴了“关键字”→“存储地址”的映射关系。

3.冲突（碰撞）：在散列表中插⼊⼀个数据元素时，需要根据关键字的值确定其存储地址，若
该地址已经存储了其他元素，则称这种情况为“冲突（碰撞）”

4.同义词：若不同的关键字通过散列函数映射到同⼀个存储地址，则称它们为“同义词”

处理冲突的方法：
拉链法（⼜称链接法、链地址法）：把所有“同义词”存储在⼀个链表中
开放定址法：如果发⽣“冲突”，就给新元素找另⼀个空闲位置

17. 散列函数的构造
    设计散列函数时应该注意什么：
    1.定义域必须涵盖所有可能出现的关键字。
    2.值域不能超出散列表的地址范围。
    3.尽可能减少冲突。散列函数计算出来的地
    址应尽可能均匀分布在整个地址空间。
    4.散列函数应尽量简单，能够快速计算出任意⼀个关键字对应的散列地址。

除留余数法 —— H(key) = key % p
散列表表⻓为m，取⼀个不⼤于m但最接近或等于m的质数p
注：质数⼜称素数。指除了1和此整数⾃身外,不能被其他⾃然数整除的数适⽤场景：较为通⽤，只要关键字是整数即可

18. 处理冲突法——拉链法
    拉链法（⼜称链接法、链地址法）：把所有“同义词”存储在⼀个链表中
    如何在散列表（拉链法解决冲突）中插⼊⼀个新元素？
    Step 1：结合散列函数计算新元素的散列地址Step 2：将新元素插⼊散列地址对应的链表（可⽤头插法，也可⽤尾插法）
    

查找⻓度——在查找运算中，需要对⽐关键字的次数称为查找⻓度
新元素插⼊链表时，若能保持链表有序，可以略微提⾼“查找”效率。

19. 处理冲突法——开放定值法
    开放定址法：如果发⽣“冲突”，就给新元素找另⼀个空闲位置。为什么叫“开放定址”？—— ⼀个散列地址，既对同义词开放，也对⾮同义词开放。
    
    
    
    
    
    如何删除⼀个元素：
    Step 1：先根据散列函数算出散列地址，并对⽐关键字是否匹配。若匹配，则“查找成功”
    Step 2：若关键字不匹配，则根据“探测序列”对⽐下⼀个地址的关键字，直到“查找成功”或“查
    找失败”Step 3：若“查找成功”，则删除找到的元素

意：采⽤“开放定址法”时，删除元素不能简单地将被删元素的空间置为空，否则将截断在它之后的探测路径，可以做⼀个“已删除”标记，进⾏逻辑删除。⽆论线性探测法、平⽅探测法、双散列法、伪随机序列法原理都⼀样。删除元素时，只能逻辑删除

1.线性探测法的“探测覆盖率”
理想情况下，若散列表表⻓=m，则最多发⽣ m-1 次冲突即可“探测”完整个散列表。

2.平⽅探测法的“探测覆盖率”
采⽤平⽅探测法，⾄少可以探测到散列表中⼀半的位置这意味着，即便散列表中有空闲位置，也未必能插⼊成功。若散列表⻓度 m 是⼀个可以表示成4j + 3的素数(如 7、11、19)，平⽅探测法就能探测到所有位置

3.双散列法的“探测覆盖率”
双散列法未必能探测到散列表的所有位置。
双散列法的探测覆盖率取决于第⼆个散列函数 hash2(key) 设计的是否合理。若hash2(key) 计算得到的值与散列表表⻓m互质，就能保证双散列发可以探测所有单元

4.伪随机序列法的“探测覆盖率”
采⽤伪随机序列法，是否能探测到散列表中全部位置，取决于伪随机序列的设计是否合理

第十章 排序

1. 排序概念
   是重新排列表中的元素，使表中的元素满⾜按关键字有序的过程。
   
2. 插入排序
   每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯已排好序的⼦序列中，直到全部记录插⼊完成。
   
   

优化——折半插⼊排序
思路：先⽤折半查找找到应该插⼊的位置，再移动元素

3. 希尔排序
   希尔排序：先将待排序表分割成若⼲形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”⼦表，对各个⼦表分别进⾏直接插⼊排序。缩⼩增量d，重复上述过程，直到d=1为⽌。
   
   
   
   
   
4. 冒泡排序
   1.根据序列中两个元素关键字的⽐较结果来对换这两个记录在序列中的位置
   2.从后往前（或从前往后）两两⽐较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列⽐较完。称这样过程为“⼀趟”冒泡排序。
   3.若某⼀趟排序没有发⽣“交换”，说明此时已经整体有序。
   
5. 快速排序
   算法思想：在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为⼀次“划分”。然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
   
   算法实现
   
   时间复杂度=O(n*递归层数)
   空间复杂度=O(递归层数)

最好时间复杂度=O(nlog2n)
最坏时间复杂度=O(n2)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

平均时间复杂度=O(nlog2n)

6. 简单快速排序：每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列
   

7. 堆排序:每⼀趟在待排序元素中选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列
   
   
   

查当前结点是否满⾜ 根≥左、右若不满⾜，将当前结点与更⼤的⼀个孩⼦互换
若元素互换破坏了下⼀级的堆，则采⽤相同的⽅法继续往下调整（⼩元素不断“下坠”）

选择排序：每⼀趟在待排序元素中选取关键字最⼤的元素加⼊有序⼦序列
堆排序：每⼀趟将堆顶元素加⼊有序⼦序列（与待排序序列中的最后⼀个元素交换）并将待排序元素序列再次调整为⼤根堆（⼩元素不断“下坠”）
注意：基于“⼤根堆”的堆排序得到“递增序列”

时间复杂度 = O(nlog2n)

8. 堆的插入和删除
   

对于⼩根堆，新元素放到表尾，与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。新元素就这样⼀路“上升”，直到⽆法继续上升为⽌

被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌

9. 归并排序
   归并：把两个或多个已经有序的序列合并成⼀个(注意是有序序列合并)
   

对⽐ i、j 所指元素，选择更⼩的⼀个放⼊ k 所指位置
剩⼀个⼦表未合并时，可以将该表中剩余元素全部加到总表
归并：把两个或多个已经有序的序列合并成⼀个

代码实现

10. 基数排序

第⼀趟：以“个位”进⾏“分配”,将其插入表尾

第⼆趟：以“⼗位”进⾏“分配”

第三趟：以“百位”进⾏“分配”

排序过程

11. 外部排序
    磁盘的读/写以“块”为单位，数据读⼊内存后才能被修改修改完了还要写回磁盘

标签：结点,遍历,删除,笔记,关键字,二叉树,顶点,数据结构
From： https://blog.csdn.net/hellow_xqs/article/details/141688169