数据结构与算法

数据结构与算法 - 基础

参考：

https://github.com/callmePicacho/Data-Structres/blob/master/README.md

数据结构层次
逻辑结构&存储结构
数据结构组成
关于分治法的时间复杂度证明：
alt text

[SCU练习平台题解]课堂练习

练习
PTA
2024/09/05:
NO1，最大子列和问题

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;

int Max3(int A,int B,int C)
{
	return A > B ? A > C ? A : C : B > C ? B : C;
}
int DivideAndConquer(int List[],int left ,int right)
{
	int MaxLeftSum,MaxRightSum;
	int MaxLeftBorderSum,MaxRightBorderSum;
	
	int LeftBorderSum,RightBorderSum;
	int center,i;
	
	if(left == right)
	{
		if(List[left] > 0)
		{
			return List[left];
		}else{
			return 0;
		}
	}
	
	center = (left + right) / 2;
	
	MaxLeftSum = DivideAndConquer(List,left,center);
	MaxRightSum = DivideAndConquer(List,center+1,right);
	
	MaxLeftBorderSum = 0,LeftBorderSum = 0;
	for(i = center;i >= left;i --){
		LeftBorderSum += List[i];
		if(LeftBorderSum > MaxLeftBorderSum)
		{
			MaxLeftBorderSum = LeftBorderSum;
		}
	}
	
	MaxRightBorderSum = 0,RightBorderSum = 0;
	for( i = center + 1;i <= right; ++ i)
	{
		RightBorderSum += List[i];
		if(RightBorderSum > MaxRightBorderSum)
		{
			MaxRightBorderSum = RightBorderSum;
		}
	}
	
	return Max3( MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);
}
int MaxSubseqSum3(int List[],int N)
{
	return DivideAndConquer(List,0,N-1);
}

这题非常经典，分治法当然不是最好的。
“在线算法”实际上是贪心的方法，另一种办法是动态规划

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
#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int main()
{
	int t;cin >> t;
	for(int k = 1;k <= t;++ k)
	{
		int n;cin >> n;
		for(int i = 1;i <= n;++ i)cin >> dp[i];
		int start = 1,end = 1,p = 1;
		int maxsum = dp[1];
		for(int i = 2;i <= n;++ i){
			if(dp[i-1] + dp[i] >= dp[i])
				dp[i] = dp[i-1] + dp[i];
			else p = i;
			if(dp[i] > maxsum)
			{
				maxsum = dp[i];start = p;end = i;
			}
		}
		printf("%d\n",maxsum);
	}
	
	
	return 0;
}

但是时间复杂度是O(n*m)肯定会超时，考虑使用单调队列进行优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
deque<int> dq;
int s[100005];
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++ i)scanf("%lld",&s[i]);
	for(int i = 1;i <= n;++ i)s[i] = s[i] + s[i-1];
	int ans = -1e8;
	dq.push_back(0);
	
	for(int i = 1;i <= n;++ i)
	{
		while(!dq.empty()&&dq.front() < i - m)dq.pop_front();
		if(dq.empty())ans = max(ans,s[i]);
		else ans = max(ans,s[i] - s[dq.front()]);
		while(!dq.empty() && s[dq.back()] >= s[i])dq.pop_back();
		dq.push_back(i);
	}
	
	return 0;
}

由此可见，将数据结构与算法结合，威力无穷

alt text

NO2,多项式的加法和乘法

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
int a[maxn+1];
int b[maxn+1];
int c[maxn+1];
int d[maxn+1];
void getmul()
{
	int flag = 0;
	for(int i = 0;i <= maxn;++ i)
	{
		if(a[i] != 0)
		{
			for(int j = 0;j <= maxn;++ j)
			{
				if(b[j] != 0)
				{
					d[i+j] += a[i] * b[j];
				}
			}
		}
	}
	int mark = 0;
	for(int i = 0;i <= maxn;++ i)
	{
		if(d[i] != 0)
		{
			mark = i;
			break;
		}
	}
	for(int i = maxn;i >= 0;i --)
	{
		if(d[i] != 0)
		{
			flag = 1;
			cout << d[i] << " " << i << " \n"[i==mark];	
		}
	}
	if(flag == 0)
	{
		cout << "0 0" << endl;
	}
}
void getsum()
{
	int flag = 0;
	for(int i = 0;i <= maxn;++ i)
	{
		c[i] = a[i] + b[i];
	}
	int mark = 0;
	for(int i = 0;i <= maxn;++ i)
	{
		if(c[i] != 0)
		{
			mark = i;
			break;
		}
	}
	for(int i = maxn;i >= 0;i --)
	{
		if(c[i] != 0)
		{
			flag = 1;
			cout << c[i] << " " << i << " \n"[i == mark];	
		}
	}
	if(flag == 0)
	{
		cout << "0 0" << endl;
	}
}
int main()
{
	int num1,num2;
	cin >> num1;
	while(num1--)
	{
		int x,y;
		cin >> x >> y;
		a[y] = x;
	}
	cin >> num2;
	while(num2--)
	{
		int x,y;
		cin >> x >> y;
		b[y] = x;
	}
	getmul();
	getsum();
	
	return 0;
}

4 数组×40044 字节/数组=160176 字节
这大约是 156.5 KB。
这样虽然过了，但是没考虑过空间浪费。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
typedef struct LNode *List;
struct data{
	int x;
	int y;
};
struct LNode{
	struct data Data[maxn];	
	int Last;
};
List init()
{
	List L = (List)malloc(sizeof(struct LNode));
	L->Last = -1;
	return L;
}
void insert(int x,int y,List L)
{	
	L->Last++;
	L->Data[L->Last].x = x;
	L->Data[L->Last].y = y;
	return ;
}
//int Length(List L){
//	return L->Last+1;
//} 
void getsum(List L1,List L2)
{
	int pointer1 = 0;
	int pointer2 = 0;
	while(pointer1 <= L1->Last && pointer2 <= L2->Last)
	{
		if(L1->Data[pointer1].y > L2->Data[pointer2].y)
		{
			printf("%d %d ",L1->Data[pointer1].x,L1->Data[pointer1].y);
			pointer1++;
		}else if(L1->Data[pointer1].y < L2->Data[pointer2].y)
		{
			printf("%d %d ",L2->Data[pointer2].x,L2->Data[pointer2].y);
			pointer2++;
		}else{
			printf("%d %d ",L1->Data[pointer1].x + L2->Data[pointer2].x,L1->Data[pointer1].y);
			pointer1++;
			pointer2++;
		}
	}
	if(pointer1 <= L1->Last)
	{
		printf("%d %d ",L1->Data[pointer1].x,L1->Data[pointer1].y);
		pointer1++ ;
	}else if(pointer2 <= L2->Last)
	{
		printf("%d %d ",L2->Data[pointer2].x,L2->Data[pointer2].y);
	    pointer2++ ;
	}
}
//void getmul(List L1,List L2)
//{
//	int pointer1 = 0;
//	int pointer2 = 0;
//	for(;pointer1 <= L1->Last;pointer1++ )
//	{
//		for(;pointer2 <= L2->Last;pointer2++ )
//		{
//			
//		}
//	}
//}
int main()
{
	int num1,num2;
	cin >> num1 ;
	List L1 = init();
	while(num1--)
	{
		int x,y;
		cin >> x >> y;
		insert(x,y,L1);
	}
	cin >> num2;
	List L2 = init();
	while(num2--)
	{
		int x,y;
		cin >> x >> y;
		insert(x,y,L2);
	}
//	for(int i=0;i<Length(L1);i++)
//		printf("%d %d ",L1->Data[i].x,L1->Data[i].y);
//	printf("\n");
//	for(int i=0;i<Length(L2);i++)
//		printf("%d %d ",L2->Data[i].x,L2->Data[i].y);
	printf("\n");
	getsum(L1,L2);
//	getmul();
	
	return 0;
}

这段中尝试使用了动态数组实现顺序表的办法，完成了多项式加法

  • 优势：相比上一份静态数组，处理数据时拿多少用多少。比如同样一组输入，空间占用从165kB降至不到100B。
  • 缺点：虽然实现，但是代码中有几个问题：
  • 1.在线算法，算一条输出一条，不灵活，这也解释了为什么乘法部分没有继续写。更好的做法是再开一个数组存答案。
  • 2.输出部分未封装，题目部分有格式要求，较复杂的输出适合单独封装一个函数做输出。
  • 3.空间连续，这是开数组和开链表的重要区别：数组空间必须物理上连续，而实际上计算机内存物理上并不连续，你以为的连续实际上是操作系统给出的抽象层，造成了空间连续的假象（逻辑上连续），这就会在要求比较苛刻的情况中浪费空间。

Tips：看懂一份代码不难，重要的是如何独立写出来。一个好办法是阅读注释，注释和编写过程中的调试遗迹是好东西，编写边调试即可化难为简。
可惜的是，大多数题解将调试遗迹删去。

最优解法：链表

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<stdio.h>
#include<stdlib.h>
typedef struct Node *List;
struct Node{
	List Next;
	int z;   // 指数 
	int x;  // 系数 
};

// 读入链表 
List Read(){
	List L = (List)malloc(sizeof(struct Node));
	List head = L;
	int n;
	int i=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		int x;
		int z;
		List t = (List)malloc(sizeof(struct Node));
		scanf("%d %d",&x,&z);
		t->x = x;
		t->z = z;
		L->Next = t;
		L = L->Next;
	}
	L->Next = NULL;
	return head->Next;
}

// 实现加法运算 
List addition(List L1,List L2){
	List tmpL1 = L1;
	List tmpL2 = L2;
	List add=(List)malloc(sizeof(struct Node));
	add->Next = NULL;
	List head = add;
	List t;
	while(tmpL1 && tmpL2){
		t = (List)malloc(sizeof(struct Node));
		if(tmpL1->z == tmpL2->z){  //指数相等，系数相加  
			t->x = tmpL1->x + tmpL2->x;
			t->z = tmpL1->z;
			tmpL1 = tmpL1->Next;
			tmpL2 = tmpL2->Next;
		}else if(tmpL1->z < tmpL2->z){   // L2 结点指数更大，把 L2 结点加入链表 
			t->x = tmpL2->x;
			t->z = tmpL2->z;
			tmpL2 = tmpL2->Next;
		}else if(tmpL2->z < tmpL1->z){   // L1 结点指数更大，把 L1 结点加入链表 
			t->x = tmpL1->x;
			t->z = tmpL1->z;
			tmpL1 = tmpL1->Next;
		}
		add->Next = t;
		add = add->Next; 
	}
	if(tmpL1)   // 若 L1 不等于 NULL，将剩下结点加入其后 
		add->Next = tmpL1;
	else if(tmpL2)  // 同理 
		add->Next = tmpL2;
	return head->Next; // head 结点只有指针域存值 
}

// 实现乘法运算 
List multiplication(List L1,List L2){
	List tmpL1 = L1;
	List tmpL2 = L2;
	List mul=(List)malloc(sizeof(struct Node));
	mul->Next = NULL;
	List head = mul;
	List t;
	for(;tmpL1;tmpL1=tmpL1->Next)
		for(tmpL2 = L2;tmpL2;tmpL2=tmpL2->Next){
			t = (List)malloc(sizeof(struct Node));
			t->x = tmpL1->x * tmpL2->x;  // 系数相乘
			t->z = tmpL1->z + tmpL2->z;  // 指数相加
			t->Next = NULL;
			head = addition(t,mul);  // 将新增结点和之前已经排好序的结点排序 
			mul = head; // 重新确定开头 
		}
	return head;
}
void Print(List L){
	List t = L;
	int flag = 1;
	for(;t;t = t->Next){
		if(!flag && t->x)   //控制空格输出
			printf(" ");
		if(t->x){   // 如果系数为 0，不输出 
			printf("%d %d",t->x,t->z);
			flag =0;		
		}
	}
	if(flag)
		printf("0 0");
	printf("\n");
}
int main(){
	List L1,L2,add,mul;
	L1 = Read();
	L2 = Read();
	add = addition(L1,L2);
	mul = multiplication(L1,L2);
	Print(mul);
	Print(add);
	return 0;
}

0908
NO3,树的同构

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<malloc.h>
#define null -1
using namespace std;
struct TreeNode{
	char data;    // 存值 
	int left;   // 左子树的下标 
	int right;  // 右子树的下标 
}T1[10],T2[10];
// 返回根结点 
int create(struct TreeNode T[]){
	int n;
	int root = 0;
	char left,right;
	cin>>n;
	if(!n)
		return null;
	for(int i=0;i<n;i++){
		cin>>T[i].data>>left>>right;
		if(left=='-')
			T[i].left = null;
		else{
			T[i].left = left-'0';
			root -= T[i].left;
		}
		if(right=='-')
			T[i].right = null;
		else{
			T[i].right = right-'0';
			root -= T[i].right;
		}
		// 0 累加到 n-1 
		root +=i;	
	}
	return root;
}
// 判断是否同构
bool judge(int R1,int R2){
	if(R1 == null && R2 == null)   // 都为空 
		return true;
	if(R1 == null && R2 != null || R1 != null && R2 == null)    // 一个为空，一个不为空
		return false;
	if(T1[R1].data != T2[R2].data)   // 值不同
		return false;
	if((T1[R1].left != null && T2[R2].left != null )&&(T1[T1[R1].left].data == T2[T2[R2].left].data))  // 左儿子不为空且值相等
		return judge(T1[R1].left,T2[R2].left) && judge(T1[R1].right,T2[R2].right);
	else   // 左儿子不为空且值不等  或者 某一个左儿子为空 
		return judge(T1[R1].right,T2[R2].left) && judge(T1[R1].left,T2[R2].right);
} 
int main(){
	int R1,R2;
	R1 = create(T1);
	R2 = create(T2);
	if(judge(R1,R2))
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

之后的笔记就是关于大二下左老师算法设计课程。

Week2:

之前讲了完整的时间复杂度分析理论。这节课承接上文：
算法分析中常用的函数：

  • 幂函数
  • 取整函数
  • 多项式函数
  • 指数函数

我们现代的普通计算机计算能力是每秒1亿次，10^9，当一个问题的计算规模超过10^13，一万亿次时，我们认为一般是不可接受的。
拿斐波那契数列问题举例，2^40接近10^13，O(2^n)的算法时间复杂度对于我们只能算到40项。
而我们手算时间复杂度是O(n)的
通过快速幂方法结合矩阵乘法，这个问题可以使用O(logn)的算法程序来解决，这样计算10^13的问题只需要计算40次，反过来了。
这个例子非常典型，展现了时间复杂度优化对于解决问题的重要性。

要理解为什么排序问题的最优时间复杂度是 ( \Omega(n \log n) )，我们需要考虑基于比较的排序算法的性质。基于比较的排序算法是那些仅通过比较元素来确定它们的顺序的算法。这些算法的最优时间复杂度由决策树模型来确定。

逐步解释：

  1. 决策树模型：

    • 在决策树模型中，每个内部节点代表两个元素之间的比较，每个叶节点代表可能的排序结果。
    • 对于 ( n ) 个元素，有 ( n! )（n的阶乘）种可能的排列。因此，决策树必须至少有 ( n! ) 个叶节点。

  2. 树的高度：

    • 二叉树的高度是最大的路径长度从根到叶。在决策树中，高度代表最坏情况下的比较次数。
    • 一个有 ( n! ) 个叶节点的二叉树的高度至少是 ( \log_2(n!) )。

  3. 斯特林近似：

    • 斯特林近似表明 ( n! \approx \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n )。
    • 使用这个近似，我们可以估计 ( \log_2(n!) \approx \log_2 \left( \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \right) )。

  4. 简化对数：

    • ( \log_2(n!) \approx \log_2 \left( \sqrt{2 \pi n} \right) + \log_2 \left( \left( \frac{n}{e} \right)^n \right) )
    • ( \log_2(n!) \approx \frac{1}{2} \log_2(2 \pi n) + n \log_2 \left( \frac{n}{e} \right) )
    • ( \log_2(n!) \approx \frac{1}{2} \log_2(2 \pi n) + n \log_2(n) - n \log_2(e) )

  5. 主导项：

    • 当 ( n ) 变得很大时，项 ( n \log_2(n) ) 主导表达式。
    • 因此，( \log_2(n!) \approx n \log_2(n) )。

  6. 结论：

    • 由于决策树的高度至少是 ( \log_2(n!) )，并且 ( \log_2(n!) \approx n \log_2(n) )，任何基于比较的排序算法在最坏情况下的比较次数至少是 ( n \log_2(n) )。
    • 这意味着基于比较的排序算法的最优时间复杂度是 ( \Omega(n \log n) )。

之后还讲了递归算法的时间复杂度分析。

“这块东西你们其实以前也见过了，但是没有经过一个系统的学习，产生一个本质的了解。通过这两节课让大家对这个有一个本质的了解。”

递归与其说是一种算法，不如说是一种思维方式。（与数学归纳法类似的想法）
递归的核心要素：自己定义自己——自己调用自己
之后老师从头分析了递归编程解决排列组合问题的每一个细节。
指出设计递归程序的思维方式转变：自顶向下

Week3:

Week4:

Week5:

Week6:

Week7:

Week8:

Week9:

Week10:

矩阵的乘法次数

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
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

int n;
int q[110];
int dp[110][110];

int solve(int i, int j) {
	if (i == j) {
		dp[i][j] = 0;
		return 0;
	}
	if (dp[i][j] != -1) return dp[i][j];
	
	int m = INT_MAX;
	for (int k = i; k < j; k++) {
		int cost = solve(i, k) + solve(k+1, j) + q[i-1] * q[k] * q[j];
		if (cost < m) m = cost;
	}
	dp[i][j] = m;
	for(int s = 1;s <= 10;s ++ ){
		for(int t = 1;t <= 10;t ++){
			cout << dp[s][t] << " \n"[t==10];
		}
	}
	cout << endl;
	return m;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i <= n; i++) {
		cin >> q[i];
	}
	memset(dp, -1, sizeof dp);
	printf("%d", solve(1, n));
	return 0;
}

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
using namespace std;
const int N = 100;
int A[N];//矩阵规模
int m[N][N];//最优解
int s[N][N];
void MatrixChain(int n)
{
	int r, i, j, k;
	for (i = 0; i <= n; i++)//初始化对角线
	{
		m[i][i] = 0;
	}
	for (r = 2; r <= n; r++)//r个矩阵连乘
	{
		for (i = 1; i <= n - r + 1; i++)//r个矩阵的r-1个空隙中依次测试最优点
		{
			j = i + r - 1;
			m[i][j] = m[i][i]+m[i + 1][j] + A[i - 1] * A[i] * A[j];
			s[i][j] = i;
			for (k = i + 1; k < j; k++)//变换分隔位置，逐一测试
			{
				int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];
				if (t < m[i][j])//如果变换后的位置更优，则替换原来的分隔方法。
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}
void print(int i, int j)
{
	if (i == j)
	{
		cout << "A[" << i << "]";
		return;
	}
	cout << "(";
	print(i, s[i][j]);
	print(s[i][j] + 1, j);//递归1到s[1][j]
	cout << ")";
}
int main()
{
	int n;//n个矩阵
	cin >> n;
	int i, j;
	for (i = 0; i <= n; i++)
	{
		cin >> A[i];
	}
	MatrixChain(n);
	cout << "最佳添加括号的方式为：";
	print(1, n);
	cout << "\n最小计算量的值为：" << m[1][n] << endl;
	return 0;
}



Week11:

Week12:

Week13:

Week14:

Week15:

Week16:

KMP算法

为了实现KMP算法，求出的nex数组会出现不同的情况。在我们的算法课中，认为旧教材中规定的nex数组是课程正确答案，而在有的同学的考研教辅中，nex数组不同。本文具体解释了这个问题，并给出了KMP的编程实现。

nex数组是什么？

概括地说，nex数组就是针对模式串p生成的一个数组，记录了公共前后缀长度——border长度，这个信息会被用来完成KMP算法中的回溯步骤，讲字符串匹配算法的时间复杂度降到O(n)

不同版本的nex数组差异在哪里？

  • 旧版本：nex[0]一定等于0
  • 新版本：nex[0]一定等于0
  • 其它情况：旧版nex[i]=新版nex[i]-1
    笔算做题时要注意这种问题，旧版本的nex数组是不会有连续的0出现的，nex[i]=匹配串的最大公共前后缀 + 1

为什么会出现这样的差异？

这里我认为是因为在KMP算法实现中对特殊情况的不同处理办法，下面是旧版中next[j]的定义：

可以发现，当j=1时，nex[j]被强行规定为0，这时为了完成后续的KMP算法，0被赋予了特殊的含义——第一个字符就失配，此时如果回溯到下标为0的地方就会出错，因为在课程教材中，字符串的下标是从1开始的，下标为0的地方存储的是字符串长度。
但是，如果此时回溯到下标为1的地方，就会陷入死循环
为什么会陷入死循环？
我们知道，在KMP算法中，要匹配的字符串s的下标指针i是不会倒退的，那这时如果第一个字符匹配失败还讲j回溯到下标1（当前就在下标1），就会重复这个比较过程一直循环。
这就启发这里的算法实现必须对nex[1]进行特殊处理。书中的KMP实现如下：
注意i++;j++这样的特殊处理

求nex数组(求border)

不同的KMP代码实现对应了不同的nex数组，同时也对应了不同的数组下标使用方式。原理相同，但是不可混用。
教材规定的KMP的nex数组实现：

1
2
3
4
5
6
7
8
9
//另一种
nex[0]=nex[1]=0;//初始化
	for(int i=2,j=0;i<=m;i++)
	{
		while(j&&p[i]!=p[j+1]) j=nex[j];
		if(p[i]==p[j+1]) j++;
		nex[i]=j;
	}
//如果采用这种办法，后续的KMP匹配过程就换用for循环嵌套while循环，对于回溯到nex[j]=0的情况，即使第一个就失配,i还是会++，同样也避免了死循环。

KMP算法模板(C++)

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
30
31
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
char s[N],p[N];
int nex[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> p + 1;int m = strlen(p + 1);
    cin >> s + 1;int n = strlen(s + 1);
    
    nex[0] = nex[1] = 0;
    for(int i = 2,j = 0;i <= m;i ++)
    {
        while(j && p[i] != p[j + 1])j = nex[j];
        if(p[i] == p[j + 1])j ++;
        nex[i] = j;
    }
    
    int ans = 0;
    for(int i = 1,j = 0;i <= n;i ++)
    {
        while(j && s[i] != p[j + 1])j = nex[j];
        if(s[i] == p[i + 1])j ++;
        if(j == m)ans ++;
    }
    
    cout << ans ;
    return 0;
}

2025/1/1：

上述问题其实我没有弄清楚，直到昨天听了数据结构的期末复习讲解。引用ppt，感觉这个解释清楚了。

KMP 的时间复杂度分析

二分法

二分法太常用了，学了又忘，忘了再来吧。

整数集合上二分

二分难在版本太多了，用起来总是让人头晕，比如：
Binary_search1:

又如：

1
2
3
4
5
6
7
8
9
10
int Binary_search2(int l,int r)
{
	while(l <= r)
	{
		int mid=(l+r)/2;
		if(a[mid]>=x) r=mid-1;
		else  l=mid+1;
	}
	return mid;
}

还有：

1
2
3
4
5
6
7
8
9
10
11
int Binary_search3(int l,int r)
{
	while(l < r)
	{
		int mid=(l+r)/2;
		if(a[mid]>x) l=mid+1;
		else if(a[mid] < x)r=mid-1;
		else break;
	}
	return mid;
}

为什么会出现这么多版本方法？
究其原因，是因为：
首先，二分法是一种不断逼近的算法，不断在实数域上逼近一个答案，然而，由于计算机的整除是下取整的，这就会导致这个算法在实现上并不会尽如人意。所有的版本都是在避免一种情况：死循环。
三个版本都是对同一种情况的不同解决办法，下面逐一考虑：

考虑Binary_search1:

这个代码不对称？求大于等于和求小于等于写法不同？为什么？
感觉这个版本是最难的，但是，理解这个代码为什么会这样写，是对彻底理解二分死循环帮助最大的。

自然地，二分，mid=(l+r)/2，要取正中间才对（理论上），可是实际上是这样吗？
考虑这种情况：

1
2
3
4
while(l < r){
	int mid = (l + r) >> 1;
	if(a[mid] <= x)l = mid;else r = mid - 1;
}

l = r - 1
mid = (l + r) / 2
mid = l(下取整)
a[mid] <= x
l = mid = l
mid = (l + r) / 2
a[mid] <= x
l = mid
…………死循环

那怎么改呢，让mid=(l+r+1)/2，变成了上取整，于是就有了Binary_search1

那怎么改呢，让循环条件l<=r，l=mid-1，让两个指针错过后取中间，于是就有了Binary_search2

那怎么改呢，让循环条件不变，单独考虑a[mid]=x时，再加一个else分支判断一下，于是就有了Binary_search3

没明白？

可是现在还是没明白为什么b1要分情况两种写法，而b2,b3只需一种写法即可。
打个比方，三个方法都在设计夹子夹住答案，而b1就是设计了一把不对称的夹子，或左大右小（下取整），或左小右大（上取整）
另外两种夹子写起来是对称的，所以省心些。

还是没明白？

可是现在还没明白为什么一会上取整，一会又下取整？
其实二分法本身就不对称，答案是一个整数，要么从左边趋近它，要么从右边趋近它，这就要考虑不同情况。

就是想用basesearch1？

《算法竞赛-进阶指南》给出了指导意见：

例题：线性表整数二分查找

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

#define MAXSIZE 10
#define NotFound 0

typedef int ElementType;
typedef int Position ;
typedef struct LNode *List;

struct LNode
{
	ElementType Data[MAXSIZE];
	Position Last;
};

List CreatList();
Position BinarySearch(List ,ElementType X);

List CreatList()
{
	List L;
	L = (List)malloc(sizeof(struct LNode));
	L->Last = -1;
	return L;
}
Position BinarySearch(List L,ElementType X)
{
	int left = 1;
	int right = L->Last;
	while(left < right)
	{
		int center = (left+right) / 2;
		if(X > L->Data[center])
		{
			left = center + 1;
		}else if(X < L->Data[center])
		{
			right  = center - 1;
		}else{
			return center;
		}
	}
	return NotFound;
}
int main()
{
	List L;
	ElementType X;
	Position P;
	
	L = CreatList();
	for(int i = 1;i < 4;++ i)
	{
		L->Data[i] = 2 * i - 1;
	}
	L->Last = 3;
	scanf("%d",&X);
	P = BinarySearch(L,X);
	printf("%d\n",P);
	
	return 0;
}

综上所述：

其实二分只有一种，每次写的时候想象你设计的夹子的样子，脑补那个死循环的样子，不变应万变了。

好了，现在理解了整数二分，那么二分答案、实数二分、三分……也就不难了，后续在本文中补齐。

队列

先进先出的数据结构，很常用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<queue>
using namespace std;
int main(){
	queue<int> Q;
	printf("入队5\n"); 
	Q.push(5);
	printf("入队4\n"); 
	Q.push(4);
	printf("入队3\n"); 
	Q.push(3);
	printf("出队%d\n",Q.front());
	Q.pop();
	printf("出队%d\n",Q.front());
	Q.pop();
	printf("出队%d\n",Q.front());
	Q.pop();
	return 0;
}

举个栗子：

https://www.luogu.com.cn/problem/P1540

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
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int m,n;
int countt = 0;
int que[10000];
int head;
int tail;
map<int,int>mapp;
int main()
{
	cin >> m >> n;
	head = tail = 0;
	for(int i = 1;i <= n;++ i)
	{
		int c;cin >> c ;
		if(mapp.count(c))
		{
			continue;
		}
		if(tail - head + 1 <= m)
		{	
			countt ++ ;
			que[tail] = c;
			tail ++ ;
			mapp[c] = 1;
		}else{
			countt ++ ;
			que[tail] = c;
			tail ++ ;
			mapp[c] = 1;
			mapp.erase(que[head]);
			head ++ ;
		}
	}
	cout << countt << endl;
	
	return 0;
}
//数组模拟队列+map实现哈希表
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef int ElementType;
typedef struct QNode *Queue;
struct QNode{
	ElementType Data[MaxSize];
	int front;   // 记录队头 
	int rear;    // 记录队尾 
};
Queue CreateQueue();  // 初始化队列 
void AddQ(Queue Q,ElementType item);  //  入队
int IsFull(Queue Q); // 判断队列是否已满 
ElementType DeleteQ(Queue Q);  // 出队 
int IsEmpty(Queue Q); // 判断队列是否为空 

// 初始化 
Queue CreateQueue(){
	Queue Q;
	Q = (Queue)malloc(sizeof(struct QNode));
	Q->front = -1;
	Q->rear = -1;
	return Q;
} 

// 判断队列是否已满
int IsFull(Queue Q){
 	return ((Q->rear+1) % MaxSize == Q->front);
}

// 入队 
void AddQ(Queue Q,ElementType item){
	if(IsFull(Q)){
		printf("队列满");
		return;
	}else{ 
		Q->rear = (Q->rear+1) % MaxSize;
		Q->Data[Q->rear] = item; 
	}
}

//判断队列是否为空
int IsEmpty(Queue Q){
	return (Q->front == Q->rear);
}
 
// 出队
ElementType DeleteQ(Queue Q){
	if(IsEmpty(Q)){
		printf("队列空");
		return 0;
	}else{
		Q->front = (Q->front+1) % MaxSize;
		return Q->Data[Q->front];
	}
} 

int main(){
	Queue Q;
	Q = CreateQueue();
	AddQ(Q,3);
	printf("3入队\n");
	AddQ(Q,5);
	printf("5入队\n");
	AddQ(Q,11);
	printf("11入队\n");
	printf("%d出队\n",DeleteQ(Q));
	printf("%d出队\n",DeleteQ(Q));
	return 0;
} 

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<stdio.h>
#include<malloc.h>
typedef int ElementType;
typedef struct QNode *Queue;
struct Node{
	ElementType Data;
	struct Node *Next;
};
struct QNode{
	struct Node *rear;    // 指向队尾结点 
	struct Node *front;   // 指向队头结点 
};

Queue CreateQueue();  // 初始化队列 
void AddQ(Queue Q,ElementType item);  //  入队
ElementType DeleteQ(Queue Q);  // 出队 
int IsEmpty(Queue Q); // 判断队列是否为空 

// 初始化 
Queue CreateQueue(){
	Queue Q;
	Q = (Queue)malloc(sizeof(struct QNode));
	Q->front = NULL;
	Q->rear = NULL;
	return Q;
}

// 是否为空 
int IsEmpty(Queue Q){
	return (Q->front == NULL);
}

// 入队
void AddQ(Queue Q,ElementType item){
	struct Node *node;
	node = (struct Node *)malloc(sizeof(struct Node));
	node->Data = item;
	node->Next = NULL;
	if(Q->rear==NULL){  //此时队列空 
		Q->rear = node;
		Q->front = node;
	}else{ //不为空 
		Q->rear->Next = node;  // 将结点入队 
		Q->rear = node;   // rear 仍然保持最后 
	}
} 

// 出队
ElementType DeleteQ(Queue Q){
	struct Node *FrontCell;
	ElementType FrontElem;
	if(IsEmpty(Q)){
		printf("队列空");
		return 0;
	}
	FrontCell = Q->front;
	if(Q->front == Q->rear){ // 队列中只有一个元素 
		Q->front = Q->rear = NULL; 
	}else{
		Q->front = Q->front->Next;
	}
	FrontElem = FrontCell->Data;
	free(FrontCell);
	return FrontElem;
}

int main(){
	Queue Q;
	Q = CreateQueue();
	printf("入队5\n"); 
	AddQ(Q,5);
	printf("入队4\n"); 
	AddQ(Q,4);
	printf("入队3\n"); 
	AddQ(Q,3);
	printf("出队%d\n",DeleteQ(Q));
	printf("出队%d\n",DeleteQ(Q));
	printf("出队%d\n",DeleteQ(Q));
	printf("%d\n",DeleteQ(Q));
	return 0;
}

链表

还记得他怎么说？“更重要的是，知道如何调整这样一种结构”

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node{
	ElementType Data;
	PtrToNode Next;
};
typedef PtrToNode List ;

List Read();
void Print(List L);
List Merge(List L1,List L2);

int main()
{
	List L1,L2,L;
	L1 = Read();
	L2 = Read();
    Print(L1);
    Print(L2);
	L = Merge(L1,L2);
	Print(L);
	Print(L1);
	Print(L2);
	return 0;
}
List Read()
{
	List L = (List)malloc(sizeof(struct Node));
	List head = L;
	int n;cin >> n;
	for(int i = 1;i <= n;++ i)
	{
		int data;
		scanf("%d",&data);
		List X = (List)malloc(sizeof(struct Node));
		X->Data = data;
		L->Next = X;
		L = L->Next;
	}
	L->Next = NULL;
	return head;
}
void Print(List L)
{
	List t = L->Next;
	if(t==NULL)
	{
		printf("NULL");
	}
	for(;t;t=t->Next)
	{
		printf("%d ",t->Data);
	}
	printf("\n");
//	if(L->Next = NULL)
//	{
//		printf("NULL");
//	}
//	while(L->Next!=NULL)
//	{
//		printf("%d",L->Next->Data);
//		L = L->Next;
//	}
}
List Merge(List L1,List L2)
{
	List L = (List)malloc(sizeof(struct Node));
	List head = L;
	List tmpL1 = L1->Next;
	List tmpL2 = L2->Next;
	while(tmpL1 && tmpL2)
	{
		if(tmpL1->Data < tmpL2->Data){
			L->Next = tmpL1;
			tmpL1 = tmpL1->Next;
		}else{
			L->Next = tmpL2;
			tmpL2 = tmpL2->Next;
		}
		L = L->Next;
	}
	if(tmpL1)
	{
		L->Next = tmpL1;
	}
	if(tmpL2)
	{
		L->Next = tmpL2;
	}
	L1->Next = NULL;
	L2->Next = NULL;
	return head;
}
//为什么像注释中那样写就无法输出？
//为什么要专门留一个head结点（哑结点）不存数据？
//如何理解这个合并过程？重组or复制？

树（上）

后来才明白，为什么非要有树这种东西。
树的遍历，前序、中序、后序、层序，非递归，递归

引入：二分查找

alt text

“从这里面我们可以看到，由于我们在数组里面，对于我们要查找的元素，进行了有序化的一种组织，使得我们的查找过程是按照固定的顺序，或者说，是按照事先定义好的顺序来进行的。”
而这个顺序呢，是形成我们所说的类似树这样的一个结构
那反过来说，能不能把数据不一定放在数组？
我就按照这样的一个层次化的结构来存放数据，是不是也会达到二分查找一样的效果？”

这就顺理成章地引入了树这种数据结构，用树的结构存储数据。
使得插入、查找、删除等等操作更加方便。
这样一来，动态查找问题也得到了解决！

树的定义

……

树的表示

Q:每个结点设计几个指针域呢？事先不知道它有几个子节点，那怎么办？
A:每个结点都留5个吧，这就能存下了，但是造成了大量的空间浪费。
A:儿子-兄弟表示法，只用两个指针域！
alt text
alt text

PS：儿子兄弟表示法如何实现呢？

  • 1.链式前向星，即数组模拟链表
  • 2.邻接矩阵，用C++的二维向量实现
  • 3.真链表
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
#include<stdio.h>
#include<malloc.h> 
#include<vector> 
#include<queue>
#include<algorithm>
typedef struct TreeNode *BinTree;
struct TreeNode{
	int Data;  // 存值 
	BinTree Left;    // 左儿子结点 
	BinTree Right;   // 右儿子结点 
};
BinTree CreatBinTree();   // 创建一个二叉树
bool IsEmpty(BinTree BT);  // 判断树 BT 是否为空 
void PreOrderTraversal(BinTree BT);   // 先序遍历，根左右
void InOrderTraversal(BinTree BT);    // 中序遍历，左根右 
void PostOrderTraversal(BinTree BT);  // 后序遍历，左右根 
using namespace std;
typedef struct SNode *Stack;
struct SNode{
	BinTree Data;
	Stack Next;
};


Stack CreateStack();  // 初始化链栈 
int IsEmpty(Stack S);  // 判断链栈是否为空 
void Push(Stack S,BinTree item);  // 入栈 
BinTree Pop(Stack S);  // 出栈
 

// 初始化 
Stack CreateStack(){
	Stack S;
	S = (Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}

// 判断是否为空 
int IsEmpty(Stack S){
	return (S->Next == NULL);
}

// 入栈
void Push(Stack S,BinTree item){
	Stack tmp;
	tmp = (Stack)malloc(sizeof(struct SNode));
	tmp->Data = item;
	// 链栈栈顶元素是链表头结点，新入栈的链表在栈顶元素后面 
	tmp->Next = S->Next;   
	S->Next = tmp;
} 

// 出栈
BinTree Pop(Stack S){
	Stack First;
	BinTree TopVal;
	if(IsEmpty(S)){
		printf("堆栈空");
		return 0;
	}else{
		First = S->Next;   // 出栈第一个元素在栈顶元素后面 
		S->Next = First->Next;  //把第一个元素从链栈删除 
		TopVal = First->Data;   // 取出被删除结点的值 
		free(First);  // 释放空间 
		return TopVal;
	}
} 

BinTree Insert(int Data){
	BinTree BT;
	BT =  (BinTree)malloc(sizeof(struct TreeNode));
	BT->Data = Data;
	BT->Left = NULL;
	BT->Right = NULL;
	return BT;
}

// 初始化二叉树 
BinTree CreatBinTree(){
	BinTree BT;
	BT =  (BinTree)malloc(sizeof(struct TreeNode));
	BT->Data = 1;
	BT->Left = Insert(2);
	BT->Right = Insert(3);
	BT->Left->Left = Insert(4);
	BT->Left->Right = Insert(6);
	BT->Left->Right->Left = Insert(5);
	BT->Right->Left = Insert(7);
	BT->Right->Right = Insert(9);
	BT->Right->Left->Right = Insert(8);
	return BT;
}


// 判断树是否为空
/*bool  IsEmpty(BinTree BT){
}*/

// 先序
/*void  PreOrderTraversal(BinTree BT){
	if(BT){
		printf("%d",BT->Data);  // 打印根 
		PreOrderTraversal(BT->Left);  // 进入左子树 
		PreOrderTraversal(BT->Right);  // 进入右子树 
	}
} */

// 先序非递归 
void PreOrderTraversal(BinTree BT){
	BinTree T = BT;
	Stack S = CreateStack();  // 创建并初始化堆栈 S
	while(T || !IsEmpty(S)){  // 当树不为空或堆栈不空 
		while(T){     
			Push(S,T);    // 压栈，第一次遇到该结点 
			printf("%d",T->Data);  // 访问结点
			T = T->Left;   // 遍历左子树 
		}
		if(!IsEmpty(S)){  // 当堆栈不空 
			T = Pop(S);    // 出栈，第二次遇到该结点 
			T = T->Right;  // 访问右结点 
		}
	} 
} 

// 中序递归 
/*void InOrderTraversal(BinTree BT){
	if(BT){
		InOrderTraversal(BT->Left);  // 进入左子树 
		printf("%d",BT->Data);  // 打印根 
		InOrderTraversal(BT->Right);  // 进入右子树 
	} 
} */

// 中序非递归
void InOrderTraversal(BinTree BT){
	BinTree T = BT;
	Stack S = CreateStack();  // 创建并初始化堆栈 S
	while(T || !IsEmpty(S)){  // 当树不为空或堆栈不空 
		while(T){     
			Push(S,T);    // 压栈
			T = T->Left;   // 遍历左子树 
		}
		if(!IsEmpty(S)){  // 当堆栈不空 
			T = Pop(S);    // 出栈
			printf("%d",T->Data);  // 访问结点
			T = T->Right;  // 访问右结点 
		}
	} 
} 

// 后序
/*void PostOrderTraversal(BinTree BT){
	if(BT){
		PostOrderTraversal(BT->Left);  // 进入左子树 
		PostOrderTraversal(BT->Right);  // 进入右子树 
		printf("%d",BT->Data);  // 打印根 
	} 
} */ 

// 后序遍历 
void PostOrderTraversal(BinTree BT){
	BinTree T = BT;
	Stack S = CreateStack();  // 创建并初始化堆栈 S
	vector<BinTree> v;
	Push(S,T);
	while(!IsEmpty(S)){  // 当树不为空或堆栈不空 
		T = Pop(S);
		v.push_back(T);
		if(T->Left)
			Push(S,T->Left);
		if(T->Right)
			Push(S,T->Right);
	}
	reverse(v.begin(),v.end());  // 逆转 
	for(int i=0;i<v.size();i++)
		printf("%d",v[i]->Data);
} 
/*
  void PostOrderTraversal(Bintree BT) {  //给节点增加访问次数的属性Visit，初始化为0
  Bintree T BT;
  Stack S = CreateStack(Maxsize);
  while (T || !IsEmpty(S)) {
  while (T) {
  if (T->Visit == 0) {//虽然没必要判断，为便于理解
  T->Visit++;
  Push(S, T);  //第一次入栈，不访问
  }
  T = T->left;   //转向左子树
  }
  if (!IsEmpty(S)) {
  T = Pop(s);
  if (T->Visit == 2)    {
  printf("%d", T->Data);//第三次碰到它，访问节点，可以彻底从堆栈弹出了
  T = NULL;//左右子数均已经访问过
  }
  else {
  T->Visit++;
  Push(S, T);  //第二次入栈，不访问，（相当于T没有出栈）
  T = T->Right;  //转向右子树
  }
  }
  }
 */

// 层次遍历
void LevelOrderTraversal(BinTree BT){
	queue<BinTree> q;
	BinTree T;
	if(!BT)
		return;
	q.push(BT);  // BT 入队 
	while(!q.empty()){
		T = q.front();  // 访问队首元素 
		q.pop();  // 出队
		printf("%d",T->Data);
		if(T->Left)
			q.push(T->Left);
	 	if(T->Right)
	 		q.push(T->Right);
	}
}
// 输出叶子结点
void  FindLeaves(BinTree BT){
	if(BT){
		if( !BT->Left && !BT->Right)
			printf("%d",BT->Data);  // 打印叶子结点
		FindLeaves(BT->Left);  // 进入左子树 
		FindLeaves(BT->Right);  // 进入右子树 
	}
} 

// 求树高度
int  GetHeight(BinTree BT){
	int hl,hr,maxh;
	if(BT){
		hl = GetHeight(BT->Left);  // 求左子树高度 
		hr = GetHeight(BT->Right);  // 求右子树高度 
		maxh = (hl>hr)?hl:hr;
		return maxh+1;  // 当前结点高度为左右子树最大的高度+1 
	}else
		return 0;
} 
int main(){
	BinTree BT,ST;
	BT = CreatBinTree();
	printf("先序遍历：");
	PreOrderTraversal(BT);
	printf("\n中序遍历：");
	InOrderTraversal(BT);
	printf("\n后序遍历：");
	PostOrderTraversal(BT);
	printf("\n层次遍历：");
	LevelOrderTraversal(BT);
	printf("\n输出叶子结点:"); 
	FindLeaves(BT);
	printf("\n输出树的高度：%d",GetHeight(BT));
	return 0;
}

树（中）

引例：实现一个按字典序的存着12个月的英文单词的二叉搜索树

1
2
3
4
5
char* months[12] = {  
	"January", "February", "March", "April",    
	"May", "June", "July", "August",    
	"September", "October", "November", "December"    
};

综合了前边所有的前置知识，还用到了C语言相关基础。
避坑！：第一个指针T必须事先赋值为NULL，不然会出现一个segmentation fault-段错误，指到了不该指的地方。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  

// 定义二叉树节点结构体  
typedef struct TreeNode {  
	char *s;  
	struct TreeNode *Left;  
	struct TreeNode *Right;  
} BinTree;  

// 插入函数  
BinTree* TreeInsert(char *s, BinTree *T) {  
	if (T == NULL) {  
		T = (BinTree*)malloc(sizeof(BinTree));  
		if (T == NULL) {  
			printf("Memory allocation failed\n");  
			exit(EXIT_FAILURE);  
		}  
		T->s = strdup(s);  // 复制字符串  
		T->Left = T->Right = NULL;  
	} else if (strcmp(s, T->s) < 0) {  
		T->Left = TreeInsert(s, T->Left);  
	} else if (strcmp(s, T->s) > 0) {  
		T->Right = TreeInsert(s, T->Right);  
	}  
	// 不处理重复项（如果s等于T->s，则不插入）  
	return T;  
}  

// 中序遍历函数  
void InOrderTraversal(BinTree *T) {  
	if (T != NULL) {  
		InOrderTraversal(T->Left);  
		printf("%s\n", T->s);  
		InOrderTraversal(T->Right);  
	}  
}  

// 释放二叉树内存的函数  
void FreeTree(BinTree *T) {  
	if (T != NULL) {  
		FreeTree(T->Left);  
		FreeTree(T->Right);  
		free(T->s);  // 释放字符串内存  
		free(T);     // 释放节点内存  
	}  
}  

int main() {  
	char* months[12] = {  
		"January", "February", "March", "April",    
		"May", "June", "July", "August",    
		"September", "October", "November", "December"    
	};  
	BinTree *T = NULL;  
	
	// 插入月份到BST  
	for (int i = 0; i < 12; i++) {  
		T = TreeInsert(months[i], T);  
	}  
	
	// 中序遍历BST并打印结果  
	printf("Inorder traversal of BST:\n");  
	InOrderTraversal(T);  
	
	// 释放二叉树内存  
	FreeTree(T);  
	
	return 0;  
}

可以试试把递归和非递归的各种遍历都试试。

线性表

线性表的数组和链表实现，以及线性表拓展。

这里第一个难点就是理解指针是什么，指针是什么呢？
线性表，像数组吧，数组和链表是它的两种实现方式。
数组存：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100  // MAXSIZE 定义为 Data 数组的大小
typedef int ElementType;  // ElementType 可定义为任意类型
typedef struct LNode *List; 
struct LNode{
   ElementType Data[MAXSIZE]; 
   int Last;  // Last 定义线性表的最后一个元素
};
List L;
//访问下标为 i 的元素：L->Data[i]
//线性表的长度：L->Last+1
List MakeEmpty(); //初始化顺序表 
int Find(ElementType X,List L); //查找 X 第一次出现的下标 
void Insert(ElementType X,int i,List L); //在下标为 i 的地方插入 X 
void Delete(int i,List L);   //删除下标为 i 的当前值 
ElementType FindKth(int K,List L);  //返回下标为 K 的当前值
int Length(List L);  //返回顺序表的长度 
 
//初始化 
List MakeEmpty(){
    List L;
    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;
    return L;
}

// 按值查找 
int Find(ElementType X,List L){
    int i=0;
    while(i <= L->Last && L->Data[i] != X)  
        i++;
    if(L->Last < i)  //如果没找到，返回 -1
        return -1; 
    else    // 找到后返回下标 
        return i;
}

// 插入
void Insert(ElementType X,int i,List L){
    int j;
    if(L->Last == MAXSIZE-1){  //位置已满 
        printf("表满");
        return;
    }
    if(i < 0 || L->Last+1 < i){  //位置越界，如果将数插入 L->Data[L->Last+1]，下面都不用腾位置了 
        printf("位置不合法");
        return;
    }
    for(j=L->Last;j>=i;j--)   // 从后往前依次向后挪一个，给 a[i]腾出位置     
        L->Data[j+1] = L->Data[j];   
    L->Data[i] = X;    //新元素插入
    L->Last++;    // Last仍然指向最后元素
    return;
} 

//删除
void Delete(int i,List L){
    int j;
    if(i < 0 || L->Last <i){  //位置越界，而删除最多到 L->Data[L->Last]
        printf("L->Data[%d]不存在元素",i);
        return;
    }
    for(j=i+1;j<=L->Last;j++)   // 从前往后依次向前挪一个，将 a[i] 覆盖了 
        L->Data[j-1] = L->Data[j];
    L->Last--;  // Last仍然指向最后元素
    return;
}

// 按序查找
ElementType FindKth(int K,List L){
	if(K < 0 || L->Last < K){  //位置越界
        printf("L->Data[%d]不存在元素",K);
        return;
    }
    return L->Data[K];
}

//表长
int Length(List L){
	return L->Last+1;
} 

int main(){
	int i=0;
	L = MakeEmpty();
	Insert(11,0,L);
	printf("在线性表L-Data[0]插入11\n");
	Insert(25,0,L);
	printf("在线性表L-Data[0]插入25\n");
	Insert(33,0,L);
	printf("在线性表L-Data[0]插入33\n");
	Insert(77,0,L);
	printf("在线性表L-Data[0]插入77\n");
	printf("此时的线性表为："); 
	for(i=0;i<Length(L);i++)
		printf("%d ",L->Data[i]);
	printf("\n");
	printf("查找值为12的下标是：%d\n",Find(12,L));
	printf("下标为3的线性表的值是：%d\n",FindKth(3,L));
	Delete(2,L);
	printf("删除线性表中下标为2的元素\n");
	Delete(2,L);
	printf("删除线性表中下标为2的元素\n");
	printf("此时的线性表为："); 
	for(i=0;i<Length(L);i++)
		printf("%d ",L->Data[i]);
	printf("\n"); 
	return 0;
}

链表：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<stdio.h>
#include<malloc.h>
typedef int ElementType; // ElementType 可定义为任意类型
typedef struct LNode *List;
struct LNode{
	ElementType Data;   //数据域 
	List Next;   // 下一个链表的地址 
}; 
List L;

List MakeEmpty(); //初始化链表 
int Length(List L);  // 以遍历链表的方法求链表长度 
List FindKth(int K,List L);  // 按序号查找 
List Find(ElementType X,List L);  // 按值查找 
List Insert(ElementType X,int i,List L);  //将 X 插入到第 i-1(i>0) 个结点之后 
List Delete(int i,List L); // 删除第 i(i>0) 个结点 
void Print(List L); // 输出链表元素 

// 初始化链表 
List MakeEmpty(){
	List L = (List)malloc(sizeof(struct LNode));
	L = NULL;
	return L;
}

//求表长 
int Length(List L){
	List p = L;
	int len=0;
	while(p){  // 当 p 不为空 
		p = p->Next;
		len++;
	}
	return len;
} 

// 按序查找 
List FindKth(int K,List L){
	List p = L;
	int i = 1;  //从 1 开始 
	while(p && i<K){
		p = p->Next;
		i++;
	}
	if(i == K)    // 找到了 
		return p;
	else    // 未找到 
		return NULL;
} 

// 按值查找  
List Find(ElementType X,List L){
	List p = L;
	while(p && p->Data!=X)
		p = p->Next;
	// 找到了，返回 p
	// 未找到，返回 NULL，此时 p 等于 NULL 
	return p;   
} 

/* 插入
1. 用 s 指向一个新的结点
2. 用 p 指向链表的第 i-1 个结点 
3. s->Next = p->Next，将 s 的下一个结点指向 p 的下一个结点 
4. p->Next = s，将 p 的下一结点改为 s   */
List Insert(ElementType X,int i,List L){
	List p,s;
	if(i == 1){     // 新结点插入在表头 
		s = (List)malloc(sizeof(struct LNode));
		s->Data = X;
		s->Next = L;
		return s;     //插入的结点为头结点 
	}
	p = FindKth(i-1,L);   // 找到第 i-1 个结点
	if(!p){   // 第 i-1 个结点不存在 
		printf("结点错误");
		return NULL;
	}else{
		s = (List)malloc(sizeof(struct LNode));
		s->Data = X;
		s->Next = p->Next;   //将 s 的下一个结点指向 p 的下一个结点 
		p->Next = s;   // 将 p 的下一结点改为 s
		return L;
	}
}

/* 删除
1. 用 p 指向链表的第 i-1 个结点 
2. 用 s 指向要被删除的的第 i 个结点
3. p->Next = s->Next，p 指针指向 s 后面
4. free(s)，释放空间 
*/
List Delete(int i,List L){
	List p,s;
	if(i==1){   //如果要删除头结点 
		s = L;
		if(L)   // 如果不为空 
			L = L->Next;
		else
			return NULL;
		free(s);   // 释放被删除结点 
		return L; 
	}
	p = FindKth(i-1,L);    // 查找第 i-1 个结点
	if(!p || !(p->Next)){     // 第 i-1 个或第 i 个结点不存在 
		printf("结点错误");
		return NULL;
	}else{
		s = p->Next;    // s 指向第 i 个结点 
		p->Next = s->Next;  //从链表删除 
		free(s);  // 释放被删除结点 
		return L;
	}
}

// 输出链表元素 
void Print(List L){
	List t;
	int flag = 1;
	printf("当前链表为：");
	for(t = L;t;t =t->Next){
		printf("%d  ",t->Data);
		flag = 0;
	}
	if(flag)
		printf("NULL");
	printf("\n"); 
}

int main(){
	L = MakeEmpty();
	Print(L);
	L = Insert(11,1,L);
	L = Insert(25,1,L);
	L = Insert(33,2,L);
	L = Insert(77,3,L);
	Print(L);
	printf("当前链表长度为：%d\n",Length(L));
	printf("此时链表中第二个结点的值是：%d\n",FindKth(2,L)->Data);
	printf("查找22是否在该链表中：");
	if(Find(22,L))
		printf("是！\n");
	else
		printf("否！\n");
	printf("查找33是否在该链表中：");
	if(Find(33,L))
		printf("是！\n");
	else
		printf("否！\n");
	L = Delete(1,L);
	L = Delete(3,L);
	printf("----------删除后-----\n"); 
	Print(L);
	return 0;
}

广义表

alt text
alt text

多重链表

alt text
alt text
alt text
另一个例子是链式前向星，存树用。当时就要是知道这个就好了，坡度会小很多。

栈

后进先出的数据结构，很常用

STL中的stack

C++的STL提供了stack，将写好的各种功能封装，通过stack容器，可以很方便地使用栈。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<stack>
using namespace std;
void print(stack<int> k)
{
	stack<int>kk = k; //复制一份出来用于遍历。
	printf("栈中元素有：");
	for(int i = 0;i <= kk.size();++ i)
	{
		printf("%d ",kk.top());
		kk.pop();
	}
	printf("\n");
	printf("\n");
}
int main()
{
	stack<int> k;
	printf("5入栈\n");
	k.push(5);
	print(k);
	
	printf("7入栈\n");
	k.push(7);
	print(k);
	
	printf("66入栈\n");
	k.push(66);
	print(k);
	
	printf("%d出栈\n",k.top());
	k.pop();
	print(k);
	
	printf("%d出栈\n",k.top());
	k.pop();
	print(k);
	
	
	return 0;
}
//思考一下，为什么想要遍历还要复制一份出来。

这种用法在工程中常见。因为STL写好的栈，作为C++的重要工具，经过了高度优化，综合考虑了易用性、性能、安全性、扩展性、还能够自动管理内存，是比较成熟的技术。”因此，在可能的情况下，建议使用STL std::stack。“

数组模拟的stack

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
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
int k[10];
int pointer = -1;
void print()
{
	printf("栈中元素有：");
	for(int i = 0;i <= pointer;++ i)
	{
		printf("%d ",k[i]);
	}
	printf("\n");
	printf("\n");
}
int main()
{
	
	printf("5入栈\n");
	k[++pointer] = 5;
	print();
	
	printf("7入栈\n");
	k[++pointer] = 7;
	print();
	
	printf("66入栈\n");
	k[++pointer] = 66;
	print();
	
	printf("%d出栈\n",k[pointer]);
	pointer--;
	print();
	
	printf("%d出栈\n",k[pointer]);
	pointer--;
	print();
	return 0;
}

这种写法在算法编程中常见，因为算法编程常常是小段程序，一般无需考虑安全性，扩展性，而是追求极致的速度。另一方面，算法编程中也不会在栈中存储太多数据，只是想用到栈这种先入后出的特性。所以，用数组模拟栈是个好办法，灵活，轻便。

栈的顺序表实现

数组实现

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<stdio.h>
#include<stdlib.h>
#define MAXN 1000
#define maxsize 5
typedef int Elementtype;
typedef struct LNode *Stack;
struct LNode{
	Elementtype Data[MAXN];
	int Top;
};

Stack CreateStack();
int Isempty(Stack S);
int IsFull(Stack S);
void Push(Stack S,Elementtype item);
Elementtype Pop(Stack S);
void Print(Stack S);

Stack CreateStack()
{
	Stack S;
	S = (Stack)malloc(sizeof(struct LNode));
	S->Top = -1;
	return S;
}
void Push(Stack S,Elementtype item)
{
	if(IsFull(S)){
		printf("栈满\n");
		return ;
	}
	S->Top ++ ;
	S->Data[S->Top] = item;
}
int IsFull(Stack S)
{
	return (S->Top == maxsize-1);
}
int Isempty(Stack S)
{
	return (S->Top == -1);
}
Elementtype Pop(Stack S)
{
	if(Isempty(S))
	{
		printf("栈空\n");
		return -1;
	}else{
		Elementtype val = S->Data[S->Top];
		S->Top--;
		return val;
	}
}
void Print(Stack S)
{
	int i;  
	printf("栈内元素有: ");
	for (i = S->Top; i >= 0; i--) {  
		printf("%d ", S->Data[i]);  
	}  
	printf("\n");  
}
/*
  void Print(Stack S) {  
	  Stack copy = CopyStack(S);  
	  if (!copy) {  
		  printf("内存分配失败\n");  
		  return;  
	  }  
	  for (int i = copy->Top; i >= 0; i--) {  
		  printf("%d ", copy->Data[i]);  
	  }  
	  printf("\n");  
	  free(copy); // 释放复制栈的内存  
  }  
 */
int main()
{
	Stack S;
	S = CreateStack();
	printf("5入栈\n");
	Push(S,5);
	printf("\n");
	
	Print(S);
	printf("7入栈\n");
	Push(S,7);
	printf("\n");
	
	Print(S);
	printf("66入栈\n");
	Push(S,66);
	printf("\n");
	
	Print(S);
	printf("99入栈\n");
	Push(S,99);
	Print(S);
	printf("\n");
	
	printf("100入栈\n");
	Push(S,100);
	Print(S);
	printf("\n");
	
	printf("110入栈\n");
	Push(S,110);
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	return 0;
}

思考：先入后出怎么被实现的？
思考：被注释掉的那个Print()能起到同样的作用吗，哪个更好？

链表实现

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<stdio.h>
#include<malloc.h>
typedef int ElementType;
typedef struct SNode *Stack;
struct SNode{
	ElementType Data;
	Stack Next;
};


Stack CreateStack();  // 初始化链栈 
int IsEmpty(Stack S);  // 判断链栈是否为空 
void Push(Stack S,ElementType item);  // 入栈 
ElementType Pop(Stack S);  // 出栈
 

// 初始化 
Stack CreateStack(){
	Stack S;
	S = (Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}

// 判断是否为空 
int IsEmpty(Stack S){
	return (S->Next == NULL);
}

// 入栈
void Push(Stack S,ElementType item){
	Stack tmp;
	tmp = (Stack)malloc(sizeof(struct SNode));
	tmp->Data = item;
	// 链栈栈顶元素是链表头结点，新入栈的链表在栈顶元素后面 
	tmp->Next = S->Next;   
	S->Next = tmp;
} 

// 出栈
ElementType Pop(Stack S){
	Stack First;
	ElementType TopVal;
	if(IsEmpty(S)){
		printf("堆栈空");
		return;
	}else{
		First = S->Next;   // 出栈第一个元素在栈顶元素后面 
		S->Next = First->Next;  //把第一个元素从链栈删除 
		TopVal = First->Data;   // 取出被删除结点的值 
		free(First);  // 释放空间 
		return TopVal;
	}
} 

int main(){
	Stack S;
	S = CreateStack();
	printf("5入栈\n");
	Push(S,5);
	printf("7入栈\n");
	Push(S,7);
	printf("66入栈\n");
	Push(S,66);
	printf("%d出栈\n",Pop(S));
	printf("%d出栈\n",Pop(S));
	return 0;
}

思考：这个链表的哑结点怎么不是头指针？
A: 我们知道，链表是可以调整的，让s->Next一直指向栈顶元素，即可实现先入后出

STL源码解析-stack

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
30
31
32
33
template <class T, class Sequence = deque<T> >
class stack {
//__STL_NULL_TMPL_ARGS是定义在 <stl_config.h>中，# define __STL_NULL_TMPL_ARGS <> 
  friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
  friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;
protected:
// 底层容器
  Sequence c;
public:
//stack下面的这些操作都是借助底层容器的操作来完成
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  //两个函数的区别：
  reference top() { return c.back(); } //stack<int> a;a.top();会调用
  const_reference top() const { return c.back(); }  //const stack<int> a;a.top();会调用
  void push(const value_type& x) { c.push_back(x); }
  void pop() { c.pop_back(); }
};
//stack的比较实际上就是底层容器的比较，会调用底层容器的重载操作符==、<
template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  return x.c == y.c;
}

template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  return x.c < y.c;
}

面向对象编程，通过模板类，友元函数，运算符重载等等实现
是不是很短？为什么这点代码就能实现？
把相应的已有的容器作为底部结构，将其接口改变，使之符合stack的特性，就形成一个stack
SGI STL stack默认底层容器是deque。

Theory > 专业课
数据结构与算法
https://47.108.189.123/2024/09/05/课程心得/数据结构与算法/
Author
Dong
Posted on
September 5, 2024
Licensed under