C语言学习笔记(第二章 基础算法及数据结构)

第二章 基础算法及数据结构

选择排序

项目
时间复杂度 o(n$^{2}$)
空间复杂度 o(1)
最佳情况
最坏情况 全部情况都是最坏,o(n$^{2}$)
1
2
3
4
5
6
7
8
9
10
11
void SelectionSort(int array[], int size) {
for (int i=0; i<size-1; i++) {
int min = i;
for (int j=i+1; j<size; j++) {
if (array[j]<array[min]) {
min = j;
}
}
swap(&array[min], &array[i]);
}
}

思路:还是划分有序区和无序区,只是这次从无序区里面直接挑最大(最小)的一个元素,直接放在有序区的最后。这里要注意的是,排序是从大到小还是从小到大:由于每次交换是交换无序区边界上的一位和无序区当中的最大(小)值,所以从大到小就是无序区里面挑出最大的往后续上,从小到大就是从无序区里面挑出最小的往后续上,第一次写的时候我就弄反了。

应用:据我所知没什么应用,打这个主要是为了从头练练思维过程了。

插入排序

项目
时间复杂度 o(n$^{2}$)
空间复杂度 o(1)
最佳情况 顺序,o(n)
最坏情况 逆序,o(n$^{2}$)
1
2
3
4
5
6
7
8
9
void InsertSort(int array[], int size) {
for (int i=1; i<size; i++) {
for (int j=i-1; j>=0; j--) {
if (array[j] > array[j+1]) {
swap(&array[j], &array[j+1]);
}
}
}
}

思路:一般的算法书上都说插入排序是把数列分成有序区和无序区,每次循环从无序区里取出一个元素插入有序区中合适的位置。但是数列不能像链表一样插入,所以这个算法总是给我一种这样的感觉:把数列分成有序区和无序区,每次从无序区取一个数,往有序区上冒泡,冒到冒不动时,有序区侵占无序区一个元素的范围,然后重复循环。

问题:时间复杂度这一点我还存有疑问。网上查的最佳情况,时间复杂度是 o(n) ,也就是没有把 if (array[j] > array[j+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
void Merge(int arr[], int low, int mid, int high) {
int *newArr = (int *)malloc(high * sizeof(int));
int pNew = 0, pA = low, pB = mid + 1;
while ((pA <= mid) && (pB <= high)) {
if (arr[pA] < arr[pB]) {
newArr[pNew++] = arr[pA++];
} else {
newArr[pNew++] = arr[pB++];
}
}
while (pA <= mid) {
newArr[pNew++] = arr[pA++];
}
while (pB <= high) {
newArr[pNew++] = arr[pB++];
}
for (int i=low, p=0; p<high-low+1; i++, p++) {
arr[i] = newArr[p];
}
free(newArr);
}

void MergeSort(int arr[], int low, int high) {
if (low < high) {
int mid = (low + high) /2;
MergeSort(arr, low, mid);
MergeSort(arr, mid + 1, high);
Merge(arr, low, mid, high);
}
}

思路:首先是一个合并数组的函数,把两个数组按照大小顺序合并起来。本来我写了一个这样形式的:

1
int* Merge(int arrA[], int sizeA, int arrB[], int sizeB)

但是实现起来有点麻烦,在排序函数里面要有类型强转,并且多了很多 mallocfree ,不如现在这样简洁。虽然用的时候有点违背常理——参见下面的注意事项。然后写一个排序的函数,窍门在 if (low < high) 这个判断,有了这个判断,递归到只剩两个元素时,调用 MergeSort 时就会直接退出,然后用 Merge 合并。就相当于递归的终止条件。

注意:用的时候不要传数组的大小,要传首位和末位。比如一个包含 size 个元素的数组,要这样调:

1
MergeSort(array, 0, size - 1);

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void QuickSort(int arr[], int lo, int hi) {
if (lo < hi) {
int i = lo, j = hi, x = arr[lo];
while (i < j) {
while (i<j && arr[j]<=x) j--;
while (i<j && arr[i]>=x) i++;
if (i < j) swap(&arr[i], &arr[j]);
}
arr[lo] = arr[i];
arr[i] = x;
QuickSort(arr, lo, i-1);
QuickSort(arr, i+1, hi);
}
}

这个没什么可说的,函数的规模不大,背也背下来了。

二分查找

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
int BinarySearch(int *arr, int lo, int hi, int target) {
while (lo < hi) {
int mid = (lo + hi) / 2;
if (target < arr[mid]) {
hi = mid - 1;
} else if (target > arr[mid]) {
lo = mid + 1;
} else {
return mid;
}
}
return -1;
}

int BinarySearchRecursive(int *arr, int lo, int hi, int target) {
if (lo > hi) return -1;
int mid = (lo + hi) / 2;
if (target < arr[mid]) {
return BinarySearchRecursive(arr, lo, mid, target);
} else if (target > arr[mid]){
return BinarySearchRecursive(arr, mid + 1, hi, target);
} else {
return mid;
}
}

循环队列实现

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
typedef struct Queue {
int count;
int head;
int tail;
int data[MAX_SIZE];
} Queue;

Queue* MakeQueue() {
Queue *result = (Queue *)malloc(sizeof(Queue));
result->count = 0;
result->head = 0;
result->tail = -1;
return result;
}

void EnQueue(Queue* queue, int data) {
assert(queue->count < MAX_SIZE);
queue->count++;
queue->tail = (queue->tail + 1) % MAX_SIZE;
queue->data[queue->tail] = data;
}

int DeQueue(Queue* queue) {
assert(queue->count > 0);
queue->count--;
queue->head = (queue->head + 1) % MAX_SIZE;
return queue->data[queue->head - 1];
}

void PrintQueue(Queue* queue) {
printf("queue: ");
for (int i = queue->head; i<(queue->head + queue->count); i++) {
printf("%d ", queue->data[i % MAX_SIZE]);
}
printf("\n");
}

这里使用了计数的方法实现循环队列。除此之外,还可以使用空一个位置的方法。

单链表实现

单链表的构造及插入

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
typedef struct Node
{
int data;
struct Node *next;
} Node;

Node* CreateLinkedList(int array[], int size) {
assert(size > 0);
assert(array != NULL);

Node *head;
Node *temp = (Node *)malloc(sizeof(Node));
head = temp;

for (int i = 0; i < size - 1; i++) {
Node *p = temp;
temp = (Node *)malloc(sizeof(Node));
p->next = temp;
p->data = array[i];
}

temp->data = array[size - 1];
temp->next = NULL;
return head;
}

void InsertNode(Node *head, int position, int data) {
assert(head != NULL);
int length = 0;
Node *p = head;
do {
p = p->next;
length++;
} while (p != NULL);
printf("current length: %d\n", length);
assert(position <= length && position >= 0);
p = head;
// 这里分了两种情况,如果插入的地方在链表的末尾,情况会有所不同。
// 如果有头指针,就不用这样麻烦了。
if (position == length) {
while (p->next != NULL) {
p = p->next;
}
Node *temp = (Node *)malloc(sizeof(Node));
p->next = temp;
temp->data = data;
temp->next = NULL;
} else {
for (int i=0; i<position; i++) {
p = p->next;
}
Node *temp = (Node *)malloc(sizeof(Node));
temp->data = p->data;
temp->next = p->next;
p->data = data;
p->next = temp;
}
}

单链表节点的删除

如果要求在 o(1) 时间内删除节点,可以用数据拷贝的方法。把要删除的节点内容,用下一个结点的内容覆盖掉,再把下一个节点释放。但是这个方法显然不能用来删链表尾。

单链表的转置

1
2
3
4
5
6
7
8
9
10
11
12
Node* ReverseLinkedList(Node *head) {
if (head == NULL || head->next == NULL) { return head; };
Node *pre = NULL;
Node *next = NULL;
while (head != NULL) {
next = head->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}

循环转置不用刻意背,画个图就能马上写出来了。

1
2
3
4
5
6
7
8
9
10
11
12
Node* ReverseLinkedListRecursively(Node *head) {
// 第一种情况是异常,第二种情况是递归的终止条件
if (head == NULL || head->next == NULL) {
return head;
}
Node *newHead = ReverseLinkedListRecursively(head->next);

head->next->next = head;
head->next = NULL;

return newHead;
}

递归版转置。这段程序是我从网上抄来的,我自己写不出。跟着流程走了一遍,觉得巧妙无比。关键点在每次递归调用时,传进去的参数都是head->next,这样一步步推着往前走,到递归终止时,newHead 就是新表的头,然后一步步往回退,head->next->next = head;其实是非常符合自然思维的。希望接下来的一周我可以每天都背一遍,争取能把它吃透。

快慢指针的应用

求倒数第 k 个节点,可以使用快慢指针,快指针比慢指针快 k 步,快指针到表尾时慢指针就在位置上。

求链表中间节点同样使用快慢指针,快指针每次走2步,慢指针走1步。快指针到表尾时,慢指针即在中间。

求链表中是否存在环,可以使用快指针走2步慢指针走1步的方法。写法是while(fast != NULL || fast->next != NULL)就一直绕圈,直到fast走到表尾,或两指针相遇。

找环的入口点:在快慢指针相遇后,将快指针指向链表的头,快慢指针同时一次走一步,当快慢指针再次相遇时,就是环的入口。

判断两个链表是否相交

先判断两个链表是否有环。可以使用快慢指针遍历两个链表:

  • 两个都没环:

    判断两个链表尾节点是否相同。

  • 一个有环,一个没有:

    两链表肯定不相交。

  • 两个都有环:

    若两个有环链表相交,则环必定在公共部分中。所以可记下链表1快慢指针碰撞点,再遍历链表2,判断这个碰撞点是否出现在链表2之中即可。

求两个相交的链表第一个相交点

先判断两个链表是否有环。

  • 无环:

    人为构环,将链表A的尾节点接在链表B的头上,问题转化为求带环链表的环入口。

  • 有环:

    首先计算两个链表长度。计算方法:1.先导长度:使用求环入口的方法可得解。2.环长度:记录下快慢指针碰撞点,从此处出发,再次到达碰撞点后走过的步数即为环长度。
    将两个长度相减得到长度差I,分别创建两个指针,步数相差I步,两指针相遇时即为相交点。

参考及引用

面试精选:链表问题集锦

编程之美:判断两链表是否相交

笔试题:如何判断单链表是否存在环