数据结构打卡

树的应用

二叉树的定义、性质、画图

总结二叉树的度、树高、结点数等属性之间的关系

通过王道书 5.2.3 课后小题来复习“二叉树的性质”

定义顺序存储的二叉树–下标从1开始

二叉树顺序存储的数据结构定义，需要注意以下两点：
1 .二叉树的结点用数组存储，每个结点需要标记“是否为空”
2.各结点的数组下标隐含结点关系，要能根据一个结点的数组下标 i，计算出其父节点、左孩子、右孩子的数组下标

若顺序二叉树从数组下标1开始存储结点，则：

● 结点 i 的父结点编号为 i/2
● 结点 i 的左孩子编号为 i*2
● 结点 i 的右孩子编号为 i*2+1

若顺序二叉树从数组下标0开始存储结点，则：
● 结点 i 的父结点编号为 [(i+1)/2] - 1
● 结点 i 的左孩子编号为 [(i+1)*2] - 1 = 2*i + 1
● 结点 i 的右孩子编号为 [(i+1)*2+1] - 1 = 2*i + 2

typedef struct TreeNode {
	int data; //结点中的数据元素
	bool isEmpty; //结点是否为空
} TreeNode;

//初始化顺序存储的二叉树，所有结点标记为"空"
void InitSqBiTree (TreeNode t[], int length) {
	for (int i=0; i<length; i++){
	   t[i].isEmpty=true;
	}
}

int main(){
	TreeNode t[100]; //定义一棵顺序存储的二叉树
	InitSqBiTree(t, 100); //初始化为空树
//...
}

实现函数，找到结点 i 的父结点、左孩子、右孩子

//判断下标为 index 的结点是否为空
bool isEmpty(TreeNode t[], int length, int index){
	if (index >= length || index < 1) return true; //下标超出合法范围
	return t[index].isEmpty;
}

//找到下标为 index 的结点的左孩子，并返回左孩子的下标，如果没有左孩子，则返回 -1

int getLchild(TreeNode t[], int length, int index){
	int lChild = index * 2; //如果左孩子存在，则左孩子的下标一定是 index * 2
	if (isEmpty(t, length, lChild)) return -1; //左孩子为空
	return lChild;

}

//找到下标为 index 的结点的右孩子，并返回右孩子的下标，如果没有右孩子，则返回 -1

int getRchild(TreeNode t[], int length, int index){
	int rChild = index * 2 + 1; //如果右孩子存在，则右孩子的下标一定是 index * 2 + 1
	if (isEmpty(t, length, rChild)) return -1; //右孩子为空
	return rChild;

}

//找到下标为 index 的结点的父节点，并返回父节点的下标，如果没有父节点，则返回 -1

int getFather(TreeNode t[], int length, int index){
	if (index == 1) return -1; //根节点没有父节点
	int father = index / 2; //如果父节点存在，则父节点的下标一定是 index/2，整数除法会自动向下取整
	if (isEmpty(t, length, father)) return -1;
	return father;

}

利用上述三个函数，实现先/中/后序遍历

//从下标为 index 的结点开始先序遍历

void PreOrderSqTree (TreeNode *t, int length, int index){
	if (isEmpty(t, length, index)) //当前为空节点
		return;
	visitNode(t[index]); //访问结点
	PreOrderSqTree(t, length, getLchild(t, length, index)); //先序遍历左子树
	PreOrderSqTree(t, length, getRchild(t, length, index)); //先序遍历右子树
}


//从下标为 index 的结点开始中序遍历

void InOrderSqTree (TreeNode *t, int length, int index){
	if (isEmpty(t, length, index)) //当前为空节点
		return;
	InOrderSqTree(t, length, getLchild(t, length, index)); //中序遍历左子树
	visitNode(t[index]); //访问结点
	InOrderSqTree(t, length, getRchild(t, length, index)); //中序遍历右子树
}

//从下标为 index 的结点开始后序遍历

void PostOrderSqTree (TreeNode *t, int length, int index){
	if (isEmpty(t, length, index)) //当前为空节点
		return;
	PostOrderSqTree(t, length, getLchild(t, length, index)); //后序遍历左子树
	PostOrderSqTree(t, length, getRchild(t, length, index)); //后序遍历右子树
	visitNode(t[index]); //访问结点
}

int main(){
    TreeNode t[100]; //定义一棵顺序存储的二叉树
	InitSqBiTree(t, 100); //初始化为空树
//...在空二叉树中插入数据
//...略
	InOrderSqTree (t, 100, 1); //从根节点1出发，进行中序遍历

}

定义顺序存储的二叉树（从数组下标0开始存储）

与 上面思路相同，只不过结点编号的计算有些区别而已
若顺序二叉树从数组下标0开始存储结点，则：
● 结点 i 的父结点编号为 [(i+1)/2] - 1
● 结点 i 的左孩子编号为 [(i+1)*2] - 1 = 2*i + 1
● 结点 i 的右孩子编号为 [(i+1)*2+1] - 1 = 2*i + 2

定义链式存储的二叉树

//二叉树的链表结点
typedef struct TNode{  
    ElenType c;//数据域  
    struct TNode *lift,*right;//指针域:左指针、右指针  
}BiTNode,*BiTree;


##  树的定义、性质、画图

### *用双亲表示法定义顺序存储的树*
![image.png](https://cdn.jsdelivr.net/gh/whu1233334/picgo-picture3/picture/202308231706440.png)
###  使用“孩子表示法”，定义链式存储的树（以及森林）
![image.png](https://cdn.jsdelivr.net/gh/whu1233334/picgo-picture3/picture/202308231733631.png)

```c
//Child表示下一个孩子的信息
typedef struct Child{
	int index; //孩子编号
	struct Child * next; //下一个孩子
} Child;

//TreeNode用于保存结点信息

typedef struct TreeNode {
	char data; //结点信息
    Child * firstChild; //指向第一个孩子
} TreeNode;

TreeNode tree[10]; //定义一棵拥有10个结点的树（孩子表示法）

使用“孩子兄弟表示法”，定义链式存储的树（以及森林）

typedef struct CSNode{
	ElemType data;     //数据域
	struct CSNode *firstchild,*nextsibling; //第一个孩子和右兄弟指针
}CSNode,*CSTree;

树的性质

总结树的度、树高、结点数等属性之间的关系

通过王道书 5.1.4、5.4.4 课后小题来复习“树和森林的性质”

树的定义、性质、画图

并查集的应用

实现并查集的数据结构定义，并实现 Union、Find 两个基本操作

#define SIZE 13
int UFSets[SIZE]; //用一个数组表示并查集

//初始化并查集
void Initial(int S[]){
	for(int i=0;i<SIZE;i++)
        S[i]=-1;
}

//Find “查”操作，找x所属集合（返回x所属根结点）
int Find(int S[],int x){
	while(S[x]>=0) //循环寻找x的根
        x=S[x];
	return x; //根的S[]小于0
}

//Union “并”操作，将两个集合合并为一个
void Union(int S[],int Root1,int Root2){
   //要求Root1与Root2是不同的集合
   if(Root1==Root2) return;
   //将根Root2连接到另一根Root1下面
    S[Root2]=Root1;

}

可采取“小树合并到大树”的策略优化 Union操作

//Union “并”操作，小树合并到大树

void Union(int S[],int Root1,int Root2){
	if(Root1==Root2) return;
	if(S[Root2]>S[Root1]) { //Root2结点数更少
       S[Root1] += S[Root2]; //累加结点总数
       S[Root2]=Root1; //小树合并到大树
	}else{
		S[Root2] += S[Root1]; //累加结点总数
        S[Root1]=Root2; //小树合并到大树      
	}
}

可采取“路径压缩”的策略优化 Find 操作

//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;
	}
	return root; //返回根节点编号
}

设计一个例子，对10个元素 Union

假设初始长度为 10 （ 0 ～ 9 ）的并查集，按 1-2、3-4、5-6、7-8、 0-5 、1-9、9-3、8-0、4-6 的顺序进行Union操作

基于上述例子，进行若干次 Find，并完成“压缩路径”

图的应用

图数据结构的定义

写代码：定义一个顺序存储的图（邻接矩阵实现）

#define MaxVertexNum 100                  //顶点最大数目
typedef struct{
	char Vex[MaxVertexNum];               //顶点
	int Edge[MaxVertexNum][MaxVertexNum]; //边
	int vexnum,arcnum;                    //顶点数和边数
}MGraph;

写代码：定义一个链式存储的图（邻接表实现）

#define N 8
//边结构体
typedef struct ArcNode{
	int vexIndex;            //边指向顶点位置(下标)
	int weight;            //该弧的权值
	struct ArcNode *next;  //指向下一条边的指针
}ArcNode;

//顶点结构体
typedef struct VNode{
	char data;       //顶点信息
	ArcNode *first;  //第一条边
} VNode

//邻接表存储的图
typedef struct { 
	VNode vex[N]       //N个顶点
	int vexnum,arcnum; //顶点的数量，边得数量 
}ALGraph;              //ALGraph是以邻接表存储的图类型

自己设计一个不少于6个结点的带权无向图，并画出其邻接矩阵、邻接表的样子

自己设计一个不少于6个结点的带权有向图，并画出其邻接矩阵、邻接表的样子

图的应用：最小生成树

自己设计一个不少于6个结点的带权无向连通图，并画出其邻接矩阵、邻接表的样子

基于上述无向连通图，使用Prim算法生成MST，画出算法执行过程的示意图，并计算MST的总代价

从顶点0开始，运行 Prim 算法的过程如下：

从顶点7开始，运行 Prim 算法的过程如下。这里想强调的是：当同时有两个代价相同的顶点时，优先将编号小的顶点加入MST。如：第 1 轮从顶点7出发，与其相连的顶点3、顶点5代价都是最小的，优先选择编号更小的顶点3。

基于上述无向连通图，使用Kruskal算法生成MST，画出算法执行过程的示意图，并计算MST的总代价

Kruskal 算法的执行过程是：先将各条边按照权值递减的排序，再按顺序依次检查是否将这些边加入MST。各条边排序结果如下：

( 2 ,4 ) ——权值 1

( 2, 5 ) ——权值 3

( 3, 7 ) ——权值 3

( 5, 7 ) ——权值 3

( 0, 3 ) ——权值 5

( 6, 7 ) ——权值 5

( 5, 6 ) ——权值 6

( 1, 2 ) ——权值 9

可见，当多条边的权值相同时，“起点”编号更小的边排在前面。因此，在Kruskal算法的第2轮中，虽然有3条边 (2,5) (3,7) (5,7) 的权值都是最小的，但算法会优先选择将排序靠前的 (2,5) 加入MST。

图的应用：最短路径

基于你设计的带权有向图，从某一结点出发，执行Dijkstra算法求单源最短路径。用文字描述每一轮执行的过程

下面将从顶点1出发，执行 Dijkstra 算法

注1：如果题目让你描述迪杰斯特拉算法的执行过程，可以试着模仿王道书画一张表。如下所示。你会发现这个表画起来很崩溃，复杂的飞起。相信我，老师改卷也不愿意改这么复杂的答案。因此，考场上不太可能让你画这么复杂的表。

顶点（这一列不包含起点）	第 1 轮	第 2 轮	第 3 轮	第 4 轮	第 5 轮	第 6 轮	第 7 轮
0	∞	∞	∞	∞	∞	∞	∞
2	4 1→2	已完成	已完成	已完成	已完成	已完成	已完成
3	∞	∞	7 1→5→3	7 1→5→3	已完成	已完成	已完成
4	∞	13 1→2→4	13 1→2→4	13 1→2→4	13 1→2→4	已完成	已完成
5	5 1→5	5 1→5	已完成	已完成	已完成	已完成	已完成
6	5 1→6	5 1→6	5 1→6	已完成	已完成	已完成	已完成
7	∞	∞	∞	∞	∞	14 1→2→4→7	已完成
集合S	{1, 2}	{1,2,5}	{1,2,5,6}	{1,2,5,6,3}	{1,2,5,6,3,4}	{1,2,5,6,3,4,7}	{1,2,5,6,3,4,7,0}
注2：以下是一种更适合考试的“简洁答题方法”。自己打草稿，快速确定每一轮Dijkstra算法的运行结果，然后按下面这种方式答题到试卷上。

答：
从顶点1出发，运行迪杰斯特拉算法的过程如下：
第一轮：顶点1到2的最短路径为 1→2，距离为4
第二轮：顶点1到5的最短路径为 1→5，距离为5
第三轮：顶点1到6的最短路径为 1→6，距离为5
第四轮：顶点1到3的最短路径为 1→5→3，距离为7
第五轮：顶点1到4的最短路径为 1→2→4，距离为13
第六轮：顶点1到7的最短路径为 1→2→4→7，距离为14
第七轮：不存在顶点1到0的路径，距离为∞

图的应用：拓扑排序

自己设计一个不少于6个结点的带权有向无环图，并画出其邻接矩阵的样子

用一维数组将你设计的有向无环图的邻接矩阵进行压缩存储

注：有向无环图，一定可以转化为一个上三角或下三角矩阵。但是需要调整顶点的编号。
如果要用上三角矩阵表示有向无环图的邻接矩阵，可以对图进行拓扑排序，按照拓扑排序序列，重新调整各个顶点的编号。这样可以确保，所有的弧都是从小编号顶点指向大编号顶点，从而也就保证了邻接矩阵可以转化为“上三角矩阵”

“上三角矩阵”可以按行优先压缩存储，如下所示：

基于你设计的带权有向无环图，写出所有合法的拓扑排序序列

拓扑排序序列1：0,1,2,3,4,5,6,7

拓扑排序序列2：0,1,2,3,5,4,6,7

拓扑排序序列3：0,1,2,4,3,5,6,7

拓扑排序序列4：0,1,4,2,3,5,6,7

文字描述：拓扑排序的过程

图的应用：关键路径

基于你设计的带权有向无环图，写出所有合法的关键路径，并算出关键路径总长度

用手算的方式求关键路径，就是要找到从起点到终点的所有路径中最长的那条。

在上面这个图中，起点是0，终点是7，从0到7最长的路径是 0→1→2→3→5→6→7，关键路径总长度为 25

文字描述：关键路径总长度的现实意义是什么？

AOE网可以表示一个项目，每个顶点表示事件，每个有向边表示活动。关键路径的总长度为25，意味着从启动项目到完成该项目，时间开销至少需要25。

查找算法的分析和应用

考研大纲中，要求我们掌握的查找算法是：

1. 顺序查找
2. 分块查找
3. 折半查找
4. 树形查找（二叉查找树、平衡二叉树、红黑树）
5. B树
6. 散列查找
7. 字符串的模式匹配

其中，顺序查找过于简单，不可能在应用题中专门考察；红黑树、B树难度较大，也不太可能在应用题中专门考察；字符串的模式匹配通常以小题考察为主。因此，在应用题中最有可能专门考察的是 分块查找、折半查找、二叉查找树、平衡二叉树、散列查找。其中，二叉查找树、平衡二叉树的可能考法已在本文档的 3.6 有详细介绍。接下来我们主要训练 分块查找、折半查找、散列查找在应用题中的可能考法

分块查找

自己设计一个分块查找的例子，不少于15个数据元素，并建立分块查找的索引

基于上述例子，计算查找成功的ASL、查找失败的ASL

上图中，共有15个元素，计算查找成功时的平均查找长度ASL，每个元素被查找的概率相同，都是 1/15。每个元素的查找都需要先查分块索引，再顺序查找分块内各个元素。
查找元素9时，查找长度为 1+1

查找元素7时，查找长度为 1+2

查找元素10时，查找长度为 1+3

查找元素2时，查找长度为 1+4

查找元素19时，查找长度为 2+1

查找元素14时，查找长度为 2+2

查找元素15时，查找长度为 2+3

查找元素20时，查找长度为 3+1

查找元素25时，查找长度为 3+2

查找元素22时，查找长度为 3+3

查找元素30时，查找长度为 3+4

查找元素43时，查找长度为 4+1

查找元素36时，查找长度为 4+2

查找元素55时，查找长度为 4+3

查找元素40时，查找长度为 4+4

综上，查找成功的ASL=(2+3+4+5+3+4+5+4+5+6+7+5+6+7+8)×1/15=4.933

对于查找失败的情况，题目不太可能让你分析查找失败的平均查找长度ASL（因为查找失败的情形很多，我们无法预估出现每一种失败情形的概率）。
因此，如果分块查找要考察“查找失败”的情形，很有可能是给你一个特定的关键字，让你分析该关键字查找失败时的查找长度。

例：如下图所示，查找元素 29（查找失败）时，首先顺序查找分块索引；确认元素29属于第三个分块，该分块在数组中下标范围是 7-10；紧接着在数组中查找下标为 7-10 的几个元素，所有元素和目标关键字都不匹配，最终可确定查找失败。
综上，查找元素 29（查找失败）时，总计对比关键字7次。

折半查找

自己设计一个折半查找的例子，不少于10个数据元素，画出对应的查找分析树

基于上述例子，计算查找成功的ASL、查找失败的ASL

散列查找

自己设计一个散列表，总长度由你决定，并设计一个合理的散列函数，使用线性探测法解决冲突

设散列表长度为16，采用线性探测法解决冲突，从空表开始，依次插入关键字 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数 H(key)=key%13
注：散列表的长度可以比散列函数的映射范围更大，散列函数的映射范围是 0-12，散列表的后面几个位置 13-15 不可能被散列函数直接映射，但是在线性探测法处理冲突时，可能被使用到

基于上述例子，计算查找成功的ASL、查找失败ASL

考虑查找成功的所有情况。各元素查找成功时的查找长度如下：

考虑查找失败的所有情况。若目标元素的散列值为0，则只需对比位置0的关键字即可确定查找失败，查找长度为1；若目标元素的散列值为1，采用线性探测法，需对比位置#1-#13，才能确定查找失败，查找长度是13；若目标元素的散列值为2，采用线性探测法，需对比位置#2-#13，才能确定查找失败，查找长度是12；其他散列值同理。

基于上述散列表，设计不少于10个元素的插入序列，依次插入散列表，画出散列表最终的样子（插入过程至少发生4次冲突）

基于上述例子，计算查找成功的ASL、查找失败的ASL

考虑查找成功的所有情况。元素 14、68、19、29、23、11 的查找长度为1；元素1、55、84、10 的查找长度为2；元素27的查找长度为3；元素79的查找长度为4，因此：

考虑查找失败的所有情况。若目标元素的散列值为0，则无需对比任何关键字即可确定查找失败，查找长度为0；若目标元素的散列值为1，则需要依次对比关键字14、1、27、79才能确定查找失败，查找长度为4；其他散列值同理。

排序算法的分析和应用

希尔排序

自己设计一个长度不小于10的乱序数组，用希尔排序，自己设定希尔排序参数画出每一轮希尔排序的状态

堆排序

自己设计一个长度不小于10的乱序数组，用堆排序，最终要生成升序数组，画出建堆后的状态

假设乱序数组的初始状态如下，元素从0开始存储👇：

若顺序二叉树从数组下标1开始存储结点，则：
● 结点 i 的父结点编号为 i/2
● 结点 i 的左孩子编号为 i*2
● 结点 i 的右孩子编号为 i*2+1
若顺序二叉树从数组下标0开始存储结点，则：
● 结点 i 的父结点编号为 [(i+1)/2] - 1
● 结点 i 的左孩子编号为 [(i+1)*2] - 1 = 2*i + 1
● 结点 i 的右孩子编号为 [(i+1)*2+1] - 1 = 2*i + 2

在本例中，元素从数组下标0开始存储，因此，0号元素是根节点，1号元素是其左孩子，2号元素是其右孩子。其他元素间的关系如下：

由于最终要生成升序数组，因此需要建立大根堆，从最后一个分支（即6号结点）开始调整，即依次调整结点 6、5、4、3、2、1、0。建立好的大根堆如下：

注：如果应用题让你画出一个乱序数组建堆后的样子，只需要画出数组形式的图示即可，不用画二叉树形态的图示。如下👇

给定一组无序的数，需要依次加入大根堆，给出建立大根堆完整过程

假设乱序数组的初始状态如下，元素从0开始存储👇：

完整建立大根堆过程👇：

快速排序

自己设计一个长度不小于10的乱序数组，用快速排序，最终要生成升序数组画出每一轮快速排序的状态

基数排序

自己设计一个长度不小于15的乱序链表，每个数据元素取值范围0~99，用基数排序，最终要生成升序链，画出每一轮基数排序的状态表

外部排序

选择-置换算法

败者树

败者树可以保留比较的结果记录，使得挑选出最小元素后，新增一个元素进入时,再次挑选最小时，可以根据之前比较的结果，减少比较的次数

最佳归并树

归并段，使得比较次数最少->归并段的比较构造成哈夫曼树->每次都选择最小的段归并->这就是最佳归并树(比较次数最少即IO磁盘次数最少)

真题训练-应用题

5.5.3-2

答案👇

5.4.4-7

答案👇

总结点：km+1
叶结点：km+1-m = (k-1)m + 1

.6.4.6-8

答案👇

6.4.6-9

答案👇

6.4.6-10

答案👇

答案不唯一，但是分析思路相通

6.4.6-11

答案👇

6.4.6-12

答案👇

2020-42

答案👇

7.2.4-7

答案👇

7.5.5-6

答案👇

• 装填因子: a=n/m 其中n 为关键字个数，m为表长。
• 散列函数的含义
• 散列存储冲突解决方法之一–线性探测法：冲突，往后跳一格

3.2.5-4

答案👇

1. 选择链式存储，采用循环链表
2. 队空，rear==front；队满，rear->next=front;

2023-42

答案👇

外部排序——置换-选择排序生成初始归并段

1. 按照工作区大小m将n个数据分为n/m组
2. 工作区初始填装第一组数据，并选择其中最小的加入归并段并设置minMax=当前加入的数据
3. 然后依次往右扫描用剩余的填补空缺的工作区，再次从中选择大于minMax的最小数据加入归并段。
4. 重复2,3.直至工作区均小于minMax

真题训练-算法题

算法题型

1. 顺序表、链表
2. 树和二叉树
3. 图
4. 查找
5. 排序

算法专项总结

1. 不要过度追求最优解，除了树/图只有一种解
2. 掌握快速排序(背诵)
3. 空间换时间——辅助数组
4. 双指针(快满指针)
5. 树——掌握遍历
6. 图——掌握存储结构
7. 查找——折半查找
8. 排序——快排、归并

常用的快速排序代码

• 假如每次快速排序数组都被平均地一分为二，那么可以得出QuickSort递归的次数是Iog₂n,第一次partition遍历次数为n,分成两个数组后，每个数组遍历n/2次，加起来还是n,因此时间复杂度是O(nlog₂n);

• 快排的空间复杂度是O(log₂n),因为递归的次数是log₂n,而每次递归的形参都是需要占用栈空间的。

int partition(int A[],int low,int high）{ //一趟划分
	int pivot=A[low]：//将当前表中第一个元素设为枢轴，对表进行划分
	while（low<high）{ //循环跳出条件
		while(low<high&&A[high]>=pivot)
			--high；
		A[low]=A[high]； //将比框轴小的元素移动到左端
		while(low<high&&A[low]<=pivot)
			++1ow；
		A[high]=A[low] //将比框轴大的元素移动到右端
	}
	A[low]=pivot //框轴元素存放到最终位置
	return low； //返回存放枢轴的最终位置

//快速排序方法  
void Q_sort(int *str,int low,int high){  
    if(low<high) {//low high用来限定分割的范围  
        int postion = partition(str, low, high);
        //partition方法是核心方法，每一次分割的方法  
        Q_sort(str, low, postion - 1);//递归左边的数组  
        Q_sort(str, postion + 1, high);//递归数组右边  
    }  
    return;
}  

顺序表

2010-42

#define Maxsize 100
typedef struct{
	int data[Maxsize];
	int length;
}Sqlist

void Exchange(sqlist &L,int p){
	int *s=(int*)malloc(sizeof(int)*p);
	for(int i=0;i<p,i++){//将原数组中前p个元素放到新的数组中
		s[i]=L.data[i];
	}
	for(int i=p;i<L.length;i++){//将数组后n-p个元素往前移动p个位置
		L.data[i-p]=L.data[i];
	}
	for(int i=L.length-p,int j=0;j<p;j++,i++){//进数组s中保留的放到原数组后p个位置
		L.data[i]=s[j]
	}
}

2013-41

//思想，申请一个数组B，记录遍历数组A时，不同数据的出现次数。同时一边记录一边检查次数是否超过n/2。时间复杂度O(n),空间复杂度(n)

int find(int A[],int n){
	int* B=(int*)malloc(sizeof(int)*n);//申请数组空间
	for(int i=0;i<n;i++){//数组初始化
		B[i]=0;
	}
	for(int j=0;j<n;j++){
		B[A[j]]++;
		if(B[A[j]]>n/2){ //一边判断
			free(B);
			return A[j];
		}
	}
	free(B);
	return -1;
}

链表

预测

typedef struct LNode{
	int data;
	struct Lnode *next;
}LNode,*Linklist;

void Merge(Linklist &la,Linklist &lb){
	pa=la->next;
	while(la->next!=NULL){
		pb=hb->next;
		while(lb->next!=NULL&&pa->data>pb->next){
			pa
			lb=lb->next;
			if(pre->data=la->data){
				delete pre;
			}else{
				
			}
		}
	}

}

树和二叉树

强化试卷-2

答案👇

1）算法思想：
由题⽬已知⼆叉树⾼度为H，因此可设置⽤于统计的数组 width[H]，其中，width[i] 表示第 i 层共有⼏个结点（不妨规定层数从0开始）；
使⽤⼆叉前序遍历的思想，遍历的同时，判断结点所处层数 i，令 width[i]++；
遍历完所有结点后，找到 width 数组中最⼤的值，即为⼆叉树的宽度。

void PreOrder(int width[],int deep,BiTree T){
	width[deep]++;
	PreOrder(width,deep+1;T->lchild);
	PreOrder(width,deep+1,T->rchild);
}

int treeWidth(BiTree T){
	int width[H];
	for(int i=0,i<H,i++){
		width[i]=0;//数组初始化
	}
	PreOrder(width,0,T);
	int maxwidth=0;
	for(int i=0,i<H,i++){
		if(width[i]>maxwidth){
			maxwidth=width[i];
		}
	}
	return maxwidth;
}

预测–层次遍历

//思路：使用广度优先搜索(BFS), 难点在于如何识别遍历的是同一层的结点 
//使用队列来缓存下一层结点指针，每轮循环，访问一整层的结点 
//需要在循环开始前，计算队列的长度，这样就不会混乱 
//本题很重要，建议牢记代码模板

typedef struct BiTNode{
	struct BiTNode *left,*right;
	int data;
}BiTNode,*BiTree;

int formula(BiTree T){
	if(T==NULL){
		return 0;
	}
	Queue q;
	Enqueue(q,T);
	int res=T->data;
	while(!Isempty(q)){
		int sum=0;
		int size=q.size;
		for(int i=0;i<size;i++){
			BiTree node=Outqueue(q);
			int sum+=node->data;
			if(node->left!=NULL){
				Enqueue(q,node->left);
			}
			if(node->right!=NULL){
				Enqueue(q,node->right);
			}
		}
		res=max(res,sum);
	}

}

预测

//day23解析，难度：适中 
//思路：使用分治法，递归判断左右子数是否等价 
//然后判断根节点data是否相同

typedef struct BiTNode{
	int data;
	struct BiTNode *left,*right;
}BiTNode,*BiTree;

int judge(BiTree A,BiTree B){

	//递归到最底下出口
	if(A == NULL && B==NULL){
		return 1;
	}
	if(A ==NULL || B==NULL){
		return 0;
	}
	
	//判断根节点,递归目的
	if(A->data!=B->data){
		return 0;
	}
	//递归左子树
	if(judge(A->left,B->left) ==0){
		return 0;
	}
	if(judge(A->right,B->right)==0){
		return 0;
	}
	return 1;
	//递归右子树
}

2017

//设计思想：中序遍历序列就是中序表达式序列；括号碰到非根节点和叶子结点需要添加括号

void func(BTree* T,int deep=1){
	if(T==NULL){
		return;
	}else if(T->left==NULL&&T->right==NULL){
		printf("%c",T->data);
	}else{
		if(deep>1){
			printf("(");
		}
		func(T->left,deep+1);// deep+1 这里不会改变deep，只是给形参赋值
		printf("%c",T->data);
		func(T->right,deep+1);
		if(deep>1){
			printf(")");
		}
	}
	return;
}

2014

//递归实现，从根节点开始，深度优先遍历(先序遍历)，设置一个int变量记录深度，遍历到叶子结点时，WPL+=deep*weight

typedef struct BTNode{
	int weight;
	struct BTNode *left;
	struct BTNode *right;
}BTNode,*BTree

int WPL=0;//定义为全局变量，实际上定义为局部变量更合适
int func(BTree T,int deep=0){
	if(T==NULL){
		return 0;
	}else{
		if(T->left==NULL&&T->right==NULL){
			return deep*T->weight;
		}
		WPL+=func(T->left,deep+1);
		WPL+=func(T->right,deep+1);
	}
	return WPL;
}

查找

2022

//(1).顺序存储的二叉树，下标k的左右子树下标分别为2k+1 ,2k+2;根据二叉排序树的性质，中序遍历后，其遍历结果是升序，所以可以对树进行递归的中序遍历，将遍历结果用数组存储，然后对数组进行遍历看是否是升序。

int temp[T.ElemNum];
int j=0;
void Inorder(SqBiTree* T,int i,int temp[]){
	if(i>T->ElemNum||T->ElemNum[i]==-1){ //越界/空
		return;
	}
	Inorder(T,2*i+1,temp);
	temp[j]=T->SqBiTNode[i];
	j++;
	Inorder(T,2*i+2,temp);
}
bool judgeBST(SqBiTree* T){
	Inorder(T,0,temp);
	for(int i=1;T->ElemNum>i;i++){
		if(temp[i-1]>temp[i]){
			return false;
		}
	}
	return true;
}

图

2021

int Is ExistEL(MGraph G){
	int count=0;
	for(int i=0;i<numVertices;i++){//行
		int degree=0;
		for(int j=0;j<numVertices;j++){//列
			if(G.Edge[i][j]=1){
				degree++;
			}
		}
		if(degree%2!=0){
			count++;
		}
	}
	if(count=1){
		return 0;
	}
	return 1;
}

2023

int printVertices(MGraph G){
	int count=0;
	for(int i=0;i<G.numVertex;i++){//行
		int indegree=0;
		int outdegree=0;
		for(int j=0;j<G.numVertex;j++){//列
			if(G.Edge[i][j]=1){
				outdegree++;
			}
			if(G.Edge[j][i]=1){
				indegree++;
			}
		}
		if(outdegree>indegree){
			count++;
			printf("%c\n",char[i]);
		}
	}
	return count;
}

排序

2016

//先排序，后从中间划分
//快速排序
int partition(int A[],int low,int high){
	int pivot=A[low];
	while(low<high){
		while(low<high&&A[high]>=pivot){
			high--;
		}
		A[low]=A[high];
		while(low<high&&A[low]<=pivot){
			low++;
		}
		A[high]=A[low];
	}
	A[low]=pivot;
	return low;
}
void Q_sort(int A[],int low,int high){
	if(low<high){
		int mid = partition(A,low,high);
		Q_sort(A,low,mid-1);
		Q_sort(A,mid+1,high);
	}
	return;
}

//时间复杂度：O(nlogn)
//空间复杂度：O(logn)

考点

1. 时间复杂度与空间复杂度
2. 线性表的顺序存储
3. 线性表的链式存储
4. 栈和队列的基本性质
5. 栈和队列的存储结构
6. 双端队列
7. 栈和队列的应用
8. 特殊矩阵的压缩存储+多为数组存储
9. 串的模式匹配算法
10. 树的基本性质
11. 二叉树的定义与性质
12. 二叉树的遍历
13. 树森林二叉树的转换
14. 线索二叉树的基本概念和构造
15. 哈夫曼树和哈夫曼编码
16. 并查集
17. 图的基本概念
18. 图的存储结构与基本操作
19. 图的遍历
20. 最小生成树
21. 最短路径
22. 拓扑排序
23. 关键路劲
24. 有向无环图存储算数表达式
25. 顺序查找、折半查找
26. 二叉排序树
27. 二叉平衡树
28. 红黑树
29. B树和B+树
30. 散列表
31. 插入排序
32. 交换排序
33. 选择排序
34. 二路归并排序
35. 基数排序
36. 各种内部排序算法的比较
37. 外部排序思想