Neo Sun


What's past is prologue

910数据结构

  • ~23.12K words

青岛大学 计算机科学与技术/软件工程专业专业课

线性表

头插法/尾插法

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
#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
struct Node {
    int data;
    struct Node *next;
};

// 头插法插入新节点
struct Node* insertAtBeginning(struct Node *head, int data) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }

    newNode->data = data;
    newNode->next = head; // 将新节点的next指针指向当前的头节点
    head = newNode; // 更新头节点为新节点

    return head; // 返回新的头节点
}

// 打印链表
void printList(struct Node *head) {
    struct Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node *head = NULL; // 初始化链表为空

    // 使用头插法插入元素
    head = insertAtBeginning(head, 3);
    head = insertAtBeginning(head, 2);
    head = insertAtBeginning(head, 1);

    printf("链表元素：\n");
    printList(head);

    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
#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
struct Node {
    int data;
    struct Node *next;
};

// 创建一个新节点
struct Node* createNode(int data) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }

    newNode->data = data;
    newNode->next = NULL;

    return newNode;
}

// 尾插法插入新节点
void insertAtEnd(struct Node **head, int data) {
    struct Node *newNode = createNode(data);

    if (*head == NULL) {
        // 如果链表为空，将新节点设为头节点
        *head = newNode;
    } else {
        // 否则找到链表末尾，将新节点链接到末尾
        struct Node *current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

// 打印链表
void printList(struct Node *head) {
    struct Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node *head = NULL; // 初始化链表为空

    // 使用尾插法插入元素
    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);

    printf("链表元素：\n");
    printList(head);

    return 0;
}
最好情况 最坏情况 平均情况 平均情况（空间） 最坏情况（空间） 稳定性 适用情况 适合初始序列情况
直接插入排序（Insertion Sort） O(n) O(n^2) O(n^2) O(1) O(1) 稳定 适合小型数据或部分有序的数据 基本有序
折半插入排序（Binary Insertion Sort） O(nlogn) O(n^2) O(n^2) O(1) O(1) 稳定 适合小型数据或部分有序的数据 基本有序
希尔排序（Shell Sort） O(nlogn) O(n^2) O(n^1.3) O(1) O(1) 不稳定 适合中等大小的数据集 乱序合适的间隔序列
冒泡排序（Bubble Sort） O(n) O(n^2) O(n^2) O(1) O(1) 稳定 适合小型数据集，特别是在已经接近有序的情况下 已经接近有序
快速排序（Quick Sort） O(nlogn) O(n^2) O(nlogn) O(logn) O(n) 不稳定 适合大型数据集，性能较好 不适用已经有序或接近有序的序列
简单选择排序（Selection Sort） O(n^2) O(n^2) O(n^2) O(1) O(1) 不稳定 适合小型数据集 不受输入数据的有序性影响
堆排序（Heap Sort） O(nlogn) O(nlogn) O(nlogn) O(1) O(1) 不稳定 适合大型数据集 不受输入数据的有序性影响
二路归并排序（Merge Sort） O(nlogn) O(nlogn) O(nlogn) O(n) O(n) 稳定 适合大型数据集 性能不受影响
基数排序（Radix Sort） O(n*k) O(n*k) O(n*k) O(n+k) O(n+k) 稳定 适合整数或字符串等基于键值的排序，数据集范围不大 适用于非负整数或具有固定位数的字符串

排序

快速排序

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 <stdio.h>

// 交换两个元素的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分割函数，将数组分成两部分，左边小于基准元素，右边大于基准元素
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 初始化小于基准元素的索引

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准元素，交换 arr[i] 和 arr[j]
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    
    // 交换 arr[i+1] 和 arr[high]，将基准元素放到正确的位置
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 划分数组，获取基准元素的索引
        int pi = partition(arr, low, high);

        // 对基准元素的左边和右边子数组进行递归排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quickSort(arr, 0, n - 1);

    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[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
#include <stdio.h>

// 交换两个元素的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = low - 1; // 初始化小于基准元素的索引

        for (int j = low; j <= high - 1; j++) {
            // 如果当前元素小于或等于基准元素，交换 arr[i+1] 和 arr[j]
            if (arr[j] <= pivot) {
                i++;
                swap(&arr[i], &arr[j]);
            }
        }

        // 交换 arr[i+1] 和 arr[high]，将基准元素放到正确的位置
        swap(&arr[i + 1], &arr[high]);
        
        // 对基准元素的左边和右边子数组进行递归排序
        quickSort(arr, low, i);
        quickSort(arr, i + 2, high);
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quickSort(arr, 0, n - 1);

    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[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
#include <stdio.h>
#include <stdlib.h>

// 合并两个子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; // 左子数组的大小
    int n2 = right - mid;    // 右子数组的大小

    // 创建临时数组来存储左右子数组
    int *leftArr = (int *)malloc(n1 * sizeof(int));
    int *rightArr = (int *)malloc(n2 * sizeof(int));

    // 将数据复制到临时数组 leftArr 和 rightArr 中
    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArr[j] = arr[mid + 1 + j];
    }

    // 合并 leftArr 和 rightArr 到 arr
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    // 将任何剩余的元素复制到 arr 中
    while (i < n1) {
        arr[k++] = leftArr[i++];
    }
    while (j < n2) {
        arr[k++] = rightArr[j++];
    }

    // 释放临时数组的内存
    free(leftArr);
    free(rightArr);
}

// 归并排序
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // 找到中间点
        int mid = left + (right - left) / 2;

        // 递归地排序左子数组和右子数组
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并两个子数组
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    mergeSort(arr, 0, n - 1);

    printf("排序后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

历年真题程序题

两个序列存放在同一数组中，写一个算法交换其先后顺序

  1. 定义一个函数，接受数组、两个序列的起始索引和它们的长度作为参数。
  2. 使用一个循环交换元素的方式，将第一个序列的元素与第二个序列的元素交换。
  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
#include <stdio.h>

// 反转数组中的指定范围
void reverseArray(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

// 交换同一数组中两个序列的先后顺序
void swapSubarrays(int arr[], int start1, int len1, int start2, int len2) {
    // 反转前一个序列
    reverseArray(arr, start1, start1 + len1 - 1);

    // 反转后一个序列
    reverseArray(arr, start2, start2 + len2 - 1);

    // 反转整个数组
    reverseArray(arr, 0, start1 + len1 + len2 - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int start1 = 0;  // 第一个序列的起始索引
    int len1 = 7;    // 第一个序列的长度
    int start2 = 7;  // 第二个序列的起始索引
    int len2 = 3;    // 第二个序列的长度

    printf("交换前的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    swapSubarrays(arr, start1, len1, start2, len2);

    printf("交换后的数组：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[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
#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结点结构
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 创建二叉树结点
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 释放叶子结点，并将值存放到数组中
struct TreeNode* releaseLeaves(struct TreeNode* root, int** arr, int* index) {
    if (root == NULL) {
        return NULL;
    }

    // 递归处理右子树
    root->right = releaseLeaves(root->right, arr, index);

    // 递归处理左子树
    root->left = releaseLeaves(root->left, arr, index);

    // 如果是叶子结点
    if (root->left == NULL && root->right == NULL) {
        // 存储结点的值到数组
        (*arr)[(*index)++] = root->data;
        // 释放叶子结点
        free(root);
        return NULL; // 返回NULL表示已释放
    }

    return root;
}

int main() {
    // 创建一个示例二叉树
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    // 数组用于存放叶子结点的值
    int* arr = (int*)malloc(100 * sizeof(int)); // 分配足够的内存
    int index = 0;

    // 释放叶子结点，并将值存放到数组中
    root = releaseLeaves(root, &arr, &index);

    // 打印释放的叶子结点的值
    printf("释放的叶子结点的值：\n");
    for (int i = 0; i < index; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 释放数组内存
    free(arr);

    return 0;
}

PPT练习题

设计一个算法，将一个单链表L（至少含两个数据结点）中所有结点逆置。并分析算法的时间复杂度。

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
#include <stdio.h>
#include <stdlib.h>

// 定义单链表节点结构
struct ListNode {
    int data;
    struct ListNode* next;
};

// 创建新节点
struct ListNode* createNode(int data) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 逆置单链表
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* current = head;
    struct ListNode* next;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    return prev; // 新的头节点
}

// 打印单链表
void printList(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    struct ListNode* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    printf("原始链表：\n");
    printList(head);

    head = reverseList(head);

    printf("逆置后的链表：\n");
    printList(head);

    return 0;
}

时间复杂度是O(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
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
#include <stdio.h>
#include <stdlib.h>

// 定义多项式项的结构
struct Node {
    int coefficient;  // 系数
    int exponent;     // 指数
    struct Node* next;
};

// 创建一个多项式项
struct Node* createNode(int coefficient, int exponent) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->coefficient = coefficient;
    newNode->exponent = exponent;
    newNode->next = NULL;
    return newNode;
}

// 向多项式中插入项
void insertNode(struct Node** poly, int coefficient, int exponent) {
    struct Node* newNode = createNode(coefficient, exponent);
    if (*poly == NULL) {
        *poly = newNode;
    } else {
        struct Node* current = *poly;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

// 打印多项式
void printPolynomial(struct Node* poly) {
    struct Node* current = poly;
    while (current != NULL) {
        printf("%dx^%d", current->coefficient, current->exponent);
        current = current->next;
        if (current != NULL) {
            printf(" + ");
        }
    }
    printf("\n");
}

// 相加两个多项式
struct Node* addPolynomials(struct Node* poly1, struct Node* poly2) {
    struct Node* result = NULL;

    while (poly1 != NULL && poly2 != NULL) {
        if (poly1->exponent == poly2->exponent) {
            insertNode(&result, poly1->coefficient + poly2->coefficient, poly1->exponent);
            poly1 = poly1->next;
            poly2 = poly2->next;
        } else if (poly1->exponent > poly2->exponent) {
            insertNode(&result, poly1->coefficient, poly1->exponent);
            poly1 = poly1->next;
        } else {
            insertNode(&result, poly2->coefficient, poly2->exponent);
            poly2 = poly2->next;
        }
    }

    // 处理剩余的项
    while (poly1 != NULL) {
        insertNode(&result, poly1->coefficient, poly1->exponent);
        poly1 = poly1->next;
    }

    while (poly2 != NULL) {
        insertNode(&result, poly2->coefficient, poly2->exponent);
        poly2 = poly2->next;
    }

    return result;
}

int main() {
    struct Node* poly1 = NULL;
    struct Node* poly2 = NULL;

    // 向多项式1中插入项
    insertNode(&poly1, 5, 3);
    insertNode(&poly1, 4, 2);
    insertNode(&poly1, 3, 1);

    // 向多项式2中插入项
    insertNode(&poly2, 2, 3);
    insertNode(&poly2, 1, 2);
    insertNode(&poly2, 1, 0);

    printf("多项式1: ");
    printPolynomial(poly1);

    printf("多项式2: ");
    printPolynomial(poly2);

    struct Node* sum = addPolynomials(poly1, poly2);

    printf("相加后的多项式: ");
    printPolynomial(sum);

    return 0;
}

这个算法的时间复杂度为O(max(m, n))，其中m和n分别是两个多项式的项数。

假设该单链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正 整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回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
#include <stdio.h>
#include <stdlib.h>

// 定义单链表节点结构
struct ListNode {
    int data;
    struct ListNode* next;
};

// 创建新节点
struct ListNode* createNode(int data) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 查找链表中倒数第k个位置上的结点
int findKthFromEnd(struct ListNode* head, int k) {
    if (head == NULL || k <= 0) {
        return 0; // 链表为空或k不合法，查找失败
    }

    struct ListNode* fast = head;
    struct ListNode* slow = head;

    // 将fast指针向前移动k个节点
    for (int i = 0; i < k; i++) {
        if (fast == NULL) {
            return 0; // k超过链表长度，查找失败
        }
        fast = fast->next;
    }

    // 同时移动fast和slow指针，直到fast到达链表尾部
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    printf("倒数第%d个位置上的结点的data域的值为: %d\n", k, slow->data);
    return 1;
}

int main() {
    struct ListNode* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    int k = 2; // 要查找的倒数第k个位置
    int found = findKthFromEnd(head, k);

    if (found) {
        printf("查找成功\n");
    } else {
        printf("查找失败\n");
    }

    return 0;
}

2024考研题目（答案来源ChatGPT）

1.栈和队列的转换（使用栈表示队列数据结构）

题目较简单，答案略。

2.在这个示例代码中，findKthFromEnd 函数使用两个指针（fast和slow）来查找倒数第k个位置上的节点。它首先将fast指针向前移动k个节点，然后同时移动fast和slow指针，直到fast到达链表尾部。这种方法不需要改变链表的结构，且只需要一次遍历，因此是一种高效的方法。

查找二叉排序树的次大值结点并返回该结点

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
#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 定义计数结构
struct Count {
    int value;
};

// 递归查找次大值节点的函数
void findSecondLargest(struct TreeNode* root, struct Count* count) {
    // 确保节点和计数器都存在
    if (root == NULL || count->value >= 2) {
        return;
    }

    // 递归地遍历右子树
    findSecondLargest(root->right, count);

    // 更新计数器
    count->value++;

    // 如果计数器为2，说明当前节点是次大值节点
    if (count->value == 2) {
        printf("次大值节点: %d\n", root->value);
        return;
    }

    // 递归地遍历左子树
    findSecondLargest(root->left, count);
}

// 创建新节点的函数
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    // 构建一个二叉排序树
    struct TreeNode* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);
    root->left->left = createNode(3);
    root->left->right = createNode(8);
    root->right->right = createNode(20);

    // 初始化计数器
    struct Count count = {0};

    // 查找次大值节点
    findSecondLargest(root, &count);

    // 释放内存
    free(root->left->left);
    free(root->left->right);
    free(root->right->right);
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

算法思想解释：

  1. 定义一个计数器结构 Count 用于在递归过程中跟踪访问的节点数。
  2. 递归地遍历二叉搜索树的右子树。
  3. 在递归的过程中，更新计数器，如果计数器为2，表示当前节点是次大值节点，输出该节点的值。
  4. 继续递归遍历左子树，以确保没有遗漏的次大值节点。

这个算法的时间复杂度是 O(h)，其中 h 是二叉搜索树的高度。在平衡的情况下，h 的值为 log(n)，其中 n 是树中节点的数量。

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
#include <stdio.h>
#include <stdlib.h>

// 定义图的最大节点数
#define MAX_NODES 100

// 定义邻接表节点结构
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

// 定义邻接表结构
struct AdjList {
    struct AdjListNode* head;
};

// 定义图结构
struct Graph {
    int numNodes;
    struct AdjList* array;
};

// 创建图的函数
struct Graph* createGraph(int numNodes) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numNodes = numNodes;
    graph->array = (struct AdjList*)malloc(numNodes * sizeof(struct AdjList));

    for (int i = 0; i < numNodes; ++i) {
        graph->array[i].head = NULL;
    }

    return graph;
}

// 添加边到图的函数
void addEdge(struct Graph* graph, int src, int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = src;
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 深度优先搜索的辅助函数
void DFS(struct Graph* graph, int vertex, int* visited, int componentId) {
    visited[vertex] = componentId;
    printf("%d ", vertex);

    struct AdjListNode* temp = graph->array[vertex].head;
    while (temp != NULL) {
        if (visited[temp->dest] == -1) {
            DFS(graph, temp->dest, visited, componentId);
        }
        temp = temp->next;
    }
}

// 深度优先搜索主函数
void DFS_main(struct Graph* graph, int* visited) {
    int componentId = 0;

    for (int i = 0; i < graph->numNodes; ++i) {
        if (visited[i] == -1) {
            printf("连通分量 %d: ", componentId);
            DFS(graph, i, visited, componentId);
            printf("\n");
            componentId++;
        }
    }
}

int main() {
    // 创建图
    int numNodes = 7;
    struct Graph* graph = createGraph(numNodes);

    // 添加边
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 4, 5);

    // 初始化访问数组
    int* visited = (int*)malloc(numNodes * sizeof(int));
    for (int i = 0; i < numNodes; ++i) {
        visited[i] = -1;
    }

    // 进行深度优先搜索
    DFS_main(graph, visited);

    // 释放内存
    free(visited);
    free(graph->array);
    free(graph);

    return 0;
}

算法思想解释：

  1. 创建一个图数据结构，使用邻接表表示图的连接关系。
  2. 初始化一个数组 visited，用于记录每个节点是否已经被访问过，初始值为 -1 表示未访问。
  3. 使用深度优先搜索遍历图。遍历图的每个节点，如果该节点尚未访问过，则进行深度优先搜索，并将访问到的节点标记为属于当前连通分量。
  4. 在深度优先搜索的过程中，输出每个连通分量的顶点。
  5. 重复步骤3，直到所有节点都被访问过为止。
This work is licensed under Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)