C语言学习笔记(第三章 初级算法)

第三章 初级算法

字符串匹配

KMP 的原理我就不讲了。网上的资料很多,不会的话可以去搜一下,有字的也有视频的。

这里我补充一个网上提及比较少的地方。用两重循环枚举对比的话,时间复杂度是在 o(m*n) 和 o(m+n) 之间的,极限条件是 Pattern 中不存在任何相同的字符,此时双循环的复杂度也是 o(m+n),因为第一位不对就搜索下一位了。

Pattern 里面的前缀和后缀相同的位数越多,复杂度越接近 o(m*n)。极限条件比如在”aaaaaaab”中搜索”aab”,此时复杂度为 o(m*n)。KMP 的作用就是在 Pattern 有相同的前缀后缀时,通过 next 数组将复杂度降到 o(n)。

然后 KMP 的难点在于所谓 next 数组的算法。坦白说这一块我也没有完全吃透,目前还属于半理解半背诵的状态。首先给出标准作法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void generateNext(char *pattern, int *next) {
int j = 0; //作循环变量用,记下算到了pattern的哪一位
int k = -1; //里面存的是已经匹配的位数
next[0] = -1;
while (j < strlen(pattern) - 1) { //用j计数,循环遍历pattern串
// 第一个条件是当之前最后一次的匹配失败,k退回到-1时,给当前位置的next赋0
// 第二个条件是,如果当前后缀的末一位等于前缀的末一位时,给next加1,即next[j] = next[j-1] + 1
if (k == -1 || pattern[j] == pattern[k]) {
j++;
k++;
next[j] = k;
} else {
// 在这里用一下自己。因为前缀的前k位肯定和后缀的前k位相等
// 所以这一步是让k退回至前缀和后缀不等的第一位
// 设模式串 ABCABD,这一步即为当进行到D,发现不匹配时,退回到C那一位,而不是头
k = next[k];
}
}
}

这一段的解释我都写在注释里面了。对于这种稍显复杂的逻辑,要么用公式严格地讲,然后别人听不进去;要么还是当面讲比较清楚。

求解的过程还可以做一个小优化,优化我还没看懂,等看懂了会更新。

附 KMP 标准过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int KMPSearch(char *text, char *pattern, int *next) {
unsigned long lenText = strlen(text);
unsigned long lenPattern = strlen(pattern);
int i = 0, j = 0;
while (i<lenText) {
if (text[i] == pattern[j]) {
if (j == lenPattern - 1) {
return i-j;
} else {
i++;
j++;
}
} else {
i++;
j = j - next[j];
}
}
return -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
28
29
30
31
typedef struct BiTreeNode {
struct BiTreeNode *lChild;
struct BiTreeNode *rChild;
char data;
} BiTreeNode;

BiTreeNode *CreateBiTree() {
char data;
scanf("%s", &data); // 这里用%s,用回车表示结束
BiTreeNode *temp = (BiTreeNode *)malloc(sizeof(BiTreeNode));
if (temp == NULL) { return NULL; }
if (data != '#') {
temp->data = data; // 前序
temp->lChild = CreateBiTree();
temp->rChild = CreateBiTree();
return temp;
} else {
return NULL;
}
}

void PrintBiTree(BiTreeNode *T, int type) {
assert(type == PRE_ORDER || type == IN_ORDER || type == POST_ORDER);
if (T == NULL) { return; }
if (type == PRE_ORDER) { printf("%c ", T->data); }
PrintBiTree(T->lChild, type);
if (type == IN_ORDER) { printf("%c ", T->data); }
PrintBiTree(T->rChild, type);
if (type == POST_ORDER) { printf("%c ", T->data); }
}

层序遍历稍微麻烦一点,需要用到队列。我把之前第二章里写的队列拿来改了一下,把数据类型改成了 void * ,用在这上面了。思路是先把树根入队,然后只要队列不为空就往外弹,弹出来访问,再把左右孩子入队,接前面继续循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void PrintBiTreeByLevel(BiTreeNode *T) {
if (T == NULL) { return; }
Queue *queue = MakeQueue();
EnQueue(queue, T);
while (queue->count != 0) {
BiTreeNode *node = (BiTreeNode *)DeQueue(queue);
printf("%c", node->data);
if (node->lChild != NULL) {
EnQueue(queue, node->lChild);
}
if (node->rChild != NULL) {
EnQueue(queue, node->rChild);
}
}
}

二叉搜索树转双向链表

下面又是一个令人愉悦的递归,作用是将二叉搜索树转成有序的双向链表。我从网上找了几个实现,有的要用到引用,属于 C++ 的实现。这里我介绍一个纯 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
32
BiTreeNode* ConvertTreeToLinkedList(BiTreeNode *root) {
if (root == NULL) { return NULL; }
if (root->lChild != NULL) {
// 首先走到最左边的叶子
BiTreeNode *left = ConvertTreeToLinkedList(root->lChild);
// 连接时,根不能和自己的孩子连接,要和孩子下面最靠右的叶子连接
while (left->rChild != NULL) {
left = left->rChild;
}
left->rChild = root;
root->lChild = left;
}
if (root->rChild != NULL) {
BiTreeNode *right = ConvertTreeToLinkedList(root->rChild);
while (right->lChild != NULL) {
right = right->lChild;
}
root->rChild = right;
right->lChild = root;
}
return root;
}

BiTreeNode* GetHead(BiTreeNode *T) {
if (T == NULL) { return NULL; }
BiTreeNode *head = T;
while (head->lChild != NULL) {
head = head->lChild;
}
return head;
}

求第 k 层节点个数

1
2
3
4
5
6
7
8
9
10
int GetNodesCountOfLevel(BiTreeNode *T, int level) {
// 递归调用时没有过滤空叶子。如果叶子是空的,则上一行的左孩子/右孩子个数为0
if (T == NULL || level < 1) { return 0; }
// 上一行检查孩子个数,如果左孩子/右孩子不为空,则个数为1
if (level == 1) { return 1; }
// 因为是检查孩子的个数,不是检查孩子的叶子的个数,所以 level 要 -1
int leftCount = GetNodesCountOfLevel(T->lChild, level - 1);
int rightCount = GetNodesCountOfLevel(T->rChild, level - 1);
return leftCount + rightCount;
}

求叶子节点个数

1
2
3
4
5
6
7
int GetLeafCount(BiTreeNode *T) {
if (T == NULL) { return 0; }
if (T->lChild == NULL && T->rChild == NULL) { return 1; }
int lChildCount = GetLeafCount(T->lChild);
int rChildCount = GetLeafCount(T->rChild);
return lChildCount + rChildCount;
}

翻转二叉树

感觉这个一点也不难,我都不太想写这个程序。不知道那个 Homebrew 作者为什么没有写出来,也许是嫌太简单?

1
2
3
4
5
6
7
8
BiTreeNode* ReflectBiTree(BiTreeNode *T) {
if (T == NULL) { return NULL; };
BiTreeNode *left = ReflectBiTree(T->lChild);
BiTreeNode *right = ReflectBiTree(T->rChild);
T->lChild = right;
T->rChild = left;
return T;
}

求距离最远的两个叶子距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int ComputeTreeHeightAndMaxDistance(BiTreeNode *T, int *maxDistance) {
if (T == NULL) { return -1; }
int leftMax = ComputeTreeHeightAndMaxDistance(T->lChild, maxDistance) + 1;
int rightMax = ComputeTreeHeightAndMaxDistance(T->rChild, maxDistance) + 1;
int distance = leftMax + rightMax;
if (*maxDistance < distance) {
*maxDistance = distance;
}
return max(leftMax, rightMax);
}

int GetMaxDistanceBetweenLeaves(BiTreeNode *T) {
int *maxDistance = (int *)malloc(sizeof(int));
*maxDistance = 0;
ComputeTreeHeightAndMaxDistance(T, maxDistance);
int result = *maxDistance;
free(maxDistance);
return result;
}

这一段我还没有彻底理解,而且我觉得这个程序还能再改进一下。

一些思路

求两个节点的最低公共祖先

分别求出从根到节点的路径,再从底至顶寻找第一个重合的点。

由前序遍历序列和中序遍历序列重建二叉树

由于前序遍历第一个节点肯定是二叉树的根,中序遍历序列中根的左右序列分别为树的左右子树,根据这个递归重建二叉树。

同时我觉得,不仅是前序和中序可以构建,前、中、后三种遍历任取两种都可以构建一棵二叉树,有时间我要写一个程序实现一下。

判断是否完全二叉树

按层序遍历二叉树,一旦发现左右子树有一个为空,则该层节点的所有子树都必须为空。

待续…

引用及参考

从头到尾彻底理解KMP(2014年8月22日版)

KMP算法的前缀next数组最通俗的解释,如果看不懂我也没辙了——
这篇文章我没看懂,但是作者提出了一个非常帮助理解的信息:在求 next[j] 时,可以“继承” next[j-1] 的结果

轻松搞定面试中的二叉树题目

二叉树转双链表(微软面试100题001)