programming

C语言常见面试题：算法与数据结构

算法与数据结构是C语言面试中的核心内容，考查候选人的编程思维、代码实现能力和算法分析能力。本文将详细介绍常见的算法与数据结构面试题。

排序算法

面试题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
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

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

// 冒泡排序
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = 1;
            }
        }
        // 如果没有交换，说明已经有序
        if (!swapped) {
            break;
        }
    }
}

// 选择排序
void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            swap(&arr[i], &arr[min_idx]);
        }
    }
}

// 插入排序
void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // 将大于key的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// 快速排序的分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;        // 小于基准的元素的索引
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

// 快速排序
void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        
        // 递归排序基准左右两部分
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

// 归并排序的合并函数
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // 创建临时数组
    int *L = (int*)malloc(n1 * sizeof(int));
    int *R = (int*)malloc(n2 * sizeof(int));
    
    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    
    // 合并临时数组回到原数组
    int i = 0, j = 0, k = left;
    
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // 复制剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
    
    free(L);
    free(R);
}

// 归并排序
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        // 递归排序左右两半
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        
        // 合并已排序的两半
        merge(arr, left, mid, right);
    }
}

// 堆化函数
void heapify(int arr[], int n, int i) {
    int largest = i;        // 初始化最大值为根
    int left = 2 * i + 1;   // 左子节点
    int right = 2 * i + 2;  // 右子节点
    
    // 如果左子节点大于根
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // 如果最大值不是根
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        
        // 递归堆化受影响的子树
        heapify(arr, n, largest);
    }
}

// 堆排序
void heap_sort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 逐个从堆中提取元素
    for (int i = n - 1; i > 0; i--) {
        // 将当前根移到末尾
        swap(&arr[0], &arr[i]);
        
        // 对减少的堆调用heapify
        heapify(arr, i, 0);
    }
}

// 打印数组
void print_array(int arr[], int n, const char *name) {
    printf("%s: ", name);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 复制数组
void copy_array(int dest[], int src[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

// 测试排序算法
void test_sorting_algorithms(void) {
    printf("=== 排序算法测试 ===\n");
    
    int original[] = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
    int n = sizeof(original) / sizeof(original[0]);
    int arr[20];
    
    print_array(original, n, "原始数组");
    
    // 测试冒泡排序
    copy_array(arr, original, n);
    bubble_sort(arr, n);
    print_array(arr, n, "冒泡排序");
    
    // 测试选择排序
    copy_array(arr, original, n);
    selection_sort(arr, n);
    print_array(arr, n, "选择排序");
    
    // 测试插入排序
    copy_array(arr, original, n);
    insertion_sort(arr, n);
    print_array(arr, n, "插入排序");
    
    // 测试快速排序
    copy_array(arr, original, n);
    quick_sort(arr, 0, n - 1);
    print_array(arr, n, "快速排序");
    
    // 测试归并排序
    copy_array(arr, original, n);
    merge_sort(arr, 0, n - 1);
    print_array(arr, n, "归并排序");
    
    // 测试堆排序
    copy_array(arr, original, n);
    heap_sort(arr, n);
    print_array(arr, n, "堆排序");
}

搜索算法

面试题2：实现搜索算法

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
// 线性搜索
int linear_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;  // 未找到
}

// 二分搜索（递归版本）
int binary_search_recursive(int arr[], int left, int right, int target) {
    if (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] > target) {
            return binary_search_recursive(arr, left, mid - 1, target);
        }
        
        return binary_search_recursive(arr, mid + 1, right, target);
    }
    
    return -1;  // 未找到
}

// 二分搜索（迭代版本）
int binary_search_iterative(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return -1;  // 未找到
}

// 查找第一个出现的位置
int find_first_occurrence(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  // 继续在左半部分搜索
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

// 查找最后一个出现的位置
int find_last_occurrence(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1;   // 继续在右半部分搜索
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

// 测试搜索算法
void test_search_algorithms(void) {
    printf("\n=== 搜索算法测试 ===\n");
    
    int arr[] = {1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    
    print_array(arr, n, "搜索数组");
    printf("搜索目标：%d\n", target);
    
    // 线性搜索
    int linear_result = linear_search(arr, n, target);
    printf("线性搜索结果：%d\n", linear_result);
    
    // 二分搜索（递归）
    int binary_recursive_result = binary_search_recursive(arr, 0, n - 1, target);
    printf("二分搜索（递归）结果：%d\n", binary_recursive_result);
    
    // 二分搜索（迭代）
    int binary_iterative_result = binary_search_iterative(arr, n, target);
    printf("二分搜索（迭代）结果：%d\n", binary_iterative_result);
    
    // 查找第一个和最后一个出现位置
    int first = find_first_occurrence(arr, n, target);
    int last = find_last_occurrence(arr, n, target);
    printf("第一个出现位置：%d\n", first);
    printf("最后一个出现位置：%d\n", last);
    printf("出现次数：%d\n", last - first + 1);
}

链表操作

面试题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
// 链表节点定义
typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

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

// 在链表头部插入节点
ListNode* insert_at_head(ListNode *head, int data) {
    ListNode *new_node = create_node(data);
    if (new_node == NULL) {
        return head;
    }
    new_node->next = head;
    return new_node;
}

// 在链表尾部插入节点
ListNode* insert_at_tail(ListNode *head, int data) {
    ListNode *new_node = create_node(data);
    if (new_node == NULL) {
        return head;
    }
    
    if (head == NULL) {
        return new_node;
    }
    
    ListNode *current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = new_node;
    return head;
}

// 删除指定值的节点
ListNode* delete_node(ListNode *head, int data) {
    if (head == NULL) {
        return NULL;
    }
    
    // 如果要删除的是头节点
    if (head->data == data) {
        ListNode *temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    
    ListNode *current = head;
    while (current->next != NULL && current->next->data != data) {
        current = current->next;
    }
    
    if (current->next != NULL) {
        ListNode *temp = current->next;
        current->next = current->next->next;
        free(temp);
    }
    
    return head;
}

// 反转链表
ListNode* reverse_list(ListNode *head) {
    ListNode *prev = NULL;
    ListNode *current = head;
    ListNode *next = NULL;
    
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}

// 查找链表中间节点
ListNode* find_middle(ListNode *head) {
    if (head == NULL) {
        return NULL;
    }
    
    ListNode *slow = head;
    ListNode *fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

// 检测链表是否有环
int has_cycle(ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return 0;
    }
    
    ListNode *slow = head;
    ListNode *fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return 1;  // 有环
        }
    }
    
    return 0;  // 无环
}

// 合并两个有序链表
ListNode* merge_sorted_lists(ListNode *list1, ListNode *list2) {
    ListNode dummy = {0, NULL};
    ListNode *tail = &dummy;
    
    while (list1 != NULL && list2 != NULL) {
        if (list1->data <= list2->data) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    
    // 连接剩余节点
    tail->next = (list1 != NULL) ? list1 : list2;
    
    return dummy.next;
}

// 打印链表
void print_list(ListNode *head, const char *name) {
    printf("%s: ", name);
    ListNode *current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 释放链表内存
void free_list(ListNode *head) {
    while (head != NULL) {
        ListNode *temp = head;
        head = head->next;
        free(temp);
    }
}

// 测试链表操作
void test_linked_list_operations(void) {
    printf("\n=== 链表操作测试 ===\n");
    
    ListNode *head = NULL;
    
    // 插入节点
    printf("插入节点：\n");
    head = insert_at_head(head, 3);
    head = insert_at_head(head, 2);
    head = insert_at_head(head, 1);
    print_list(head, "头部插入后");
    
    head = insert_at_tail(head, 4);
    head = insert_at_tail(head, 5);
    print_list(head, "尾部插入后");
    
    // 查找中间节点
    ListNode *middle = find_middle(head);
    if (middle != NULL) {
        printf("中间节点：%d\n", middle->data);
    }
    
    // 反转链表
    head = reverse_list(head);
    print_list(head, "反转后");
    
    // 删除节点
    head = delete_node(head, 3);
    print_list(head, "删除3后");
    
    // 检测环
    printf("是否有环：%s\n", has_cycle(head) ? "是" : "否");
    
    // 创建另一个链表进行合并测试
    ListNode *list2 = NULL;
    list2 = insert_at_tail(list2, 1);
    list2 = insert_at_tail(list2, 3);
    list2 = insert_at_tail(list2, 6);
    print_list(list2, "链表2");
    
    // 先排序两个链表
    head = reverse_list(head);  // 恢复正序
    print_list(head, "链表1（排序）");
    
    // 合并链表
    ListNode *merged = merge_sorted_lists(head, list2);
    print_list(merged, "合并后");
    
    // 释放内存
    free_list(merged);
}

栈的实现

面试题4：实现栈数据结构

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
#define STACK_MAX_SIZE 100

// 栈结构定义
typedef struct {
    int data[STACK_MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void stack_init(Stack *stack) {
    if (stack == NULL) {
        return;
    }
    stack->top = -1;
}

// 检查栈是否为空
int stack_is_empty(Stack *stack) {
    return stack == NULL || stack->top == -1;
}

// 检查栈是否已满
int stack_is_full(Stack *stack) {
    return stack != NULL && stack->top == STACK_MAX_SIZE - 1;
}

// 入栈
int stack_push(Stack *stack, int value) {
    if (stack == NULL || stack_is_full(stack)) {
        printf("栈已满，无法入栈\n");
        return 0;
    }
    
    stack->data[++stack->top] = value;
    return 1;
}

// 出栈
int stack_pop(Stack *stack, int *value) {
    if (stack == NULL || stack_is_empty(stack)) {
        printf("栈为空，无法出栈\n");
        return 0;
    }
    
    if (value != NULL) {
        *value = stack->data[stack->top];
    }
    stack->top--;
    return 1;
}

// 查看栈顶元素
int stack_peek(Stack *stack, int *value) {
    if (stack == NULL || stack_is_empty(stack)) {
        printf("栈为空\n");
        return 0;
    }
    
    if (value != NULL) {
        *value = stack->data[stack->top];
    }
    return 1;
}

// 获取栈大小
int stack_size(Stack *stack) {
    if (stack == NULL) {
        return 0;
    }
    return stack->top + 1;
}

// 打印栈内容
void stack_print(Stack *stack) {
    if (stack == NULL || stack_is_empty(stack)) {
        printf("栈为空\n");
        return;
    }
    
    printf("栈内容（从栈顶到栈底）：");
    for (int i = stack->top; i >= 0; i--) {
        printf("%d ", stack->data[i]);
    }
    printf("\n");
}

// 括号匹配检查
int is_balanced_parentheses(const char *str) {
    Stack stack;
    stack_init(&stack);
    
    for (int i = 0; str[i] != '\0'; i++) {
        char ch = str[i];
        
        // 遇到左括号，入栈
        if (ch == '(' || ch == '[' || ch == '{') {
            stack_push(&stack, ch);
        }
        // 遇到右括号，检查匹配
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (stack_is_empty(&stack)) {
                return 0;  // 没有对应的左括号
            }
            
            int top_char;
            stack_pop(&stack, &top_char);
            
            // 检查括号是否匹配
            if ((ch == ')' && top_char != '(') ||
                (ch == ']' && top_char != '[') ||
                (ch == '}' && top_char != '{')) {
                return 0;  // 括号不匹配
            }
        }
    }
    
    return stack_is_empty(&stack);  // 栈为空说明所有括号都匹配
}

// 测试栈操作
void test_stack_operations(void) {
    printf("\n=== 栈操作测试 ===\n");
    
    Stack stack;
    stack_init(&stack);
    
    // 测试入栈
    printf("入栈操作：\n");
    for (int i = 1; i <= 5; i++) {
        stack_push(&stack, i * 10);
        printf("入栈 %d，栈大小：%d\n", i * 10, stack_size(&stack));
    }
    stack_print(&stack);
    
    // 测试查看栈顶
    int top_value;
    if (stack_peek(&stack, &top_value)) {
        printf("栈顶元素：%d\n", top_value);
    }
    
    // 测试出栈
    printf("\n出栈操作：\n");
    while (!stack_is_empty(&stack)) {
        int value;
        if (stack_pop(&stack, &value)) {
            printf("出栈 %d，栈大小：%d\n", value, stack_size(&stack));
        }
    }
    
    // 测试括号匹配
    printf("\n括号匹配测试：\n");
    const char *test_strings[] = {
        "()",
        "()[]{}",
        "([{}])",
        "((()))",
        "([)]",
        "(((",
        ")))",
        "{[}]"
    };
    
    int num_tests = sizeof(test_strings) / sizeof(test_strings[0]);
    for (int i = 0; i < num_tests; i++) {
        printf("\"%s\" -> %s\n", test_strings[i], 
               is_balanced_parentheses(test_strings[i]) ? "匹配" : "不匹配");
    }
}

队列的实现

面试题5：实现队列数据结构

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
#define QUEUE_MAX_SIZE 100

// 队列结构定义
typedef struct {
    int data[QUEUE_MAX_SIZE];
    int front;
    int rear;
    int size;
} Queue;

// 初始化队列
void queue_init(Queue *queue) {
    if (queue == NULL) {
        return;
    }
    queue->front = 0;
    queue->rear = -1;
    queue->size = 0;
}

// 检查队列是否为空
int queue_is_empty(Queue *queue) {
    return queue == NULL || queue->size == 0;
}

// 检查队列是否已满
int queue_is_full(Queue *queue) {
    return queue != NULL && queue->size == QUEUE_MAX_SIZE;
}

// 入队
int queue_enqueue(Queue *queue, int value) {
    if (queue == NULL || queue_is_full(queue)) {
        printf("队列已满，无法入队\n");
        return 0;
    }
    
    queue->rear = (queue->rear + 1) % QUEUE_MAX_SIZE;
    queue->data[queue->rear] = value;
    queue->size++;
    return 1;
}

// 出队
int queue_dequeue(Queue *queue, int *value) {
    if (queue == NULL || queue_is_empty(queue)) {
        printf("队列为空，无法出队\n");
        return 0;
    }
    
    if (value != NULL) {
        *value = queue->data[queue->front];
    }
    queue->front = (queue->front + 1) % QUEUE_MAX_SIZE;
    queue->size--;
    return 1;
}

// 查看队首元素
int queue_front(Queue *queue, int *value) {
    if (queue == NULL || queue_is_empty(queue)) {
        printf("队列为空\n");
        return 0;
    }
    
    if (value != NULL) {
        *value = queue->data[queue->front];
    }
    return 1;
}

// 获取队列大小
int queue_size(Queue *queue) {
    if (queue == NULL) {
        return 0;
    }
    return queue->size;
}

// 打印队列内容
void queue_print(Queue *queue) {
    if (queue == NULL || queue_is_empty(queue)) {
        printf("队列为空\n");
        return;
    }
    
    printf("队列内容（从队首到队尾）：");
    for (int i = 0; i < queue->size; i++) {
        int index = (queue->front + i) % QUEUE_MAX_SIZE;
        printf("%d ", queue->data[index]);
    }
    printf("\n");
}

// 测试队列操作
void test_queue_operations(void) {
    printf("\n=== 队列操作测试 ===\n");
    
    Queue queue;
    queue_init(&queue);
    
    // 测试入队
    printf("入队操作：\n");
    for (int i = 1; i <= 5; i++) {
        queue_enqueue(&queue, i * 10);
        printf("入队 %d，队列大小：%d\n", i * 10, queue_size(&queue));
    }
    queue_print(&queue);
    
    // 测试查看队首
    int front_value;
    if (queue_front(&queue, &front_value)) {
        printf("队首元素：%d\n", front_value);
    }
    
    // 测试出队
    printf("\n出队操作：\n");
    for (int i = 0; i < 3; i++) {
        int value;
        if (queue_dequeue(&queue, &value)) {
            printf("出队 %d，队列大小：%d\n", value, queue_size(&queue));
        }
    }
    queue_print(&queue);
    
    // 继续入队测试循环
    printf("\n继续入队测试循环：\n");
    for (int i = 6; i <= 8; i++) {
        queue_enqueue(&queue, i * 10);
        printf("入队 %d\n", i * 10);
    }
    queue_print(&queue);
    
    // 清空队列
    printf("\n清空队列：\n");
    while (!queue_is_empty(&queue)) {
        int value;
        if (queue_dequeue(&queue, &value)) {
            printf("出队 %d\n", value);
        }
    }
    printf("队列已清空\n");
}

二叉树操作

面试题6：二叉树的各种操作

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
// 二叉树节点定义
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新的树节点
TreeNode* create_tree_node(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    if (node == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 插入节点到二叉搜索树
TreeNode* bst_insert(TreeNode *root, int data) {
    if (root == NULL) {
        return create_tree_node(data);
    }
    
    if (data < root->data) {
        root->left = bst_insert(root->left, data);
    } else if (data > root->data) {
        root->right = bst_insert(root->right, data);
    }
    // 如果data等于root->data，不插入重复值
    
    return root;
}

// 在二叉搜索树中查找节点
TreeNode* bst_search(TreeNode *root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    
    if (data < root->data) {
        return bst_search(root->left, data);
    } else {
        return bst_search(root->right, data);
    }
}

// 找到最小值节点
TreeNode* find_min(TreeNode *root) {
    if (root == NULL) {
        return NULL;
    }
    
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// 删除二叉搜索树中的节点
TreeNode* bst_delete(TreeNode *root, int data) {
    if (root == NULL) {
        return root;
    }
    
    if (data < root->data) {
        root->left = bst_delete(root->left, data);
    } else if (data > root->data) {
        root->right = bst_delete(root->right, data);
    } else {
        // 找到要删除的节点
        if (root->left == NULL) {
            TreeNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode *temp = root->left;
            free(root);
            return temp;
        }
        
        // 有两个子节点的情况
        TreeNode *temp = find_min(root->right);
        root->data = temp->data;
        root->right = bst_delete(root->right, temp->data);
    }
    
    return root;
}

// 前序遍历
void preorder_traversal(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder_traversal(root->left);
        preorder_traversal(root->right);
    }
}

// 中序遍历
void inorder_traversal(TreeNode *root) {
    if (root != NULL) {
        inorder_traversal(root->left);
        printf("%d ", root->data);
        inorder_traversal(root->right);
    }
}

// 后序遍历
void postorder_traversal(TreeNode *root) {
    if (root != NULL) {
        postorder_traversal(root->left);
        postorder_traversal(root->right);
        printf("%d ", root->data);
    }
}

// 计算树的高度
int tree_height(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    
    int left_height = tree_height(root->left);
    int right_height = tree_height(root->right);
    
    return 1 + (left_height > right_height ? left_height : right_height);
}

// 计算树的节点数
int tree_node_count(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    
    return 1 + tree_node_count(root->left) + tree_node_count(root->right);
}

// 层序遍历（使用队列）
void level_order_traversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    
    // 使用简单的队列实现
    TreeNode *queue[1000];
    int front = 0, rear = 0;
    
    queue[rear++] = root;
    
    while (front < rear) {
        TreeNode *current = queue[front++];
        printf("%d ", current->data);
        
        if (current->left != NULL) {
            queue[rear++] = current->left;
        }
        if (current->right != NULL) {
            queue[rear++] = current->right;
        }
    }
}

// 释放树的内存
void free_tree(TreeNode *root) {
    if (root != NULL) {
        free_tree(root->left);
        free_tree(root->right);
        free(root);
    }
}

// 测试二叉树操作
void test_binary_tree_operations(void) {
    printf("\n=== 二叉树操作测试 ===\n");
    
    TreeNode *root = NULL;
    
    // 插入节点
    int values[] = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45};
    int n = sizeof(values) / sizeof(values[0]);
    
    printf("插入节点：");
    for (int i = 0; i < n; i++) {
        printf("%d ", values[i]);
        root = bst_insert(root, values[i]);
    }
    printf("\n");
    
    // 遍历
    printf("\n遍历结果：\n");
    printf("前序遍历：");
    preorder_traversal(root);
    printf("\n");
    
    printf("中序遍历：");
    inorder_traversal(root);
    printf("\n");
    
    printf("后序遍历：");
    postorder_traversal(root);
    printf("\n");
    
    printf("层序遍历：");
    level_order_traversal(root);
    printf("\n");
    
    // 树的属性
    printf("\n树的属性：\n");
    printf("树的高度：%d\n", tree_height(root));
    printf("节点数量：%d\n", tree_node_count(root));
    
    // 搜索节点
    printf("\n搜索测试：\n");
    int search_values[] = {40, 90, 25};
    for (int i = 0; i < 3; i++) {
        TreeNode *found = bst_search(root, search_values[i]);
        printf("搜索 %d：%s\n", search_values[i], 
               found ? "找到" : "未找到");
    }
    
    // 删除节点
    printf("\n删除节点测试：\n");
    printf("删除 20 前的中序遍历：");
    inorder_traversal(root);
    printf("\n");
    
    root = bst_delete(root, 20);
    printf("删除 20 后的中序遍历：");
    inorder_traversal(root);
    printf("\n");
    
    printf("删除 30 前的中序遍历：");
    inorder_traversal(root);
    printf("\n");
    
    root = bst_delete(root, 30);
    printf("删除 30 后的中序遍历：");
    inorder_traversal(root);
    printf("\n");
    
    // 释放内存
    free_tree(root);
    printf("\n树内存已释放\n");
}

哈希表实现

面试题7：实现简单哈希表

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
#define HASH_TABLE_SIZE 101

// 哈希表节点
typedef struct HashNode {
    int key;
    int value;
    struct HashNode *next;
} HashNode;

// 哈希表
typedef struct {
    HashNode *buckets[HASH_TABLE_SIZE];
    int size;
} HashTable;

// 哈希函数
int hash_function(int key) {
    return abs(key) % HASH_TABLE_SIZE;
}

// 初始化哈希表
void hash_table_init(HashTable *table) {
    if (table == NULL) {
        return;
    }
    
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        table->buckets[i] = NULL;
    }
    table->size = 0;
}

// 创建新节点
HashNode* create_hash_node(int key, int value) {
    HashNode *node = (HashNode*)malloc(sizeof(HashNode));
    if (node == NULL) {
        return NULL;
    }
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}

// 插入键值对
int hash_table_insert(HashTable *table, int key, int value) {
    if (table == NULL) {
        return 0;
    }
    
    int index = hash_function(key);
    HashNode *current = table->buckets[index];
    
    // 检查是否已存在该键
    while (current != NULL) {
        if (current->key == key) {
            current->value = value;  // 更新值
            return 1;
        }
        current = current->next;
    }
    
    // 插入新节点
    HashNode *new_node = create_hash_node(key, value);
    if (new_node == NULL) {
        return 0;
    }
    
    new_node->next = table->buckets[index];
    table->buckets[index] = new_node;
    table->size++;
    return 1;
}

// 查找值
int hash_table_get(HashTable *table, int key, int *value) {
    if (table == NULL) {
        return 0;
    }
    
    int index = hash_function(key);
    HashNode *current = table->buckets[index];
    
    while (current != NULL) {
        if (current->key == key) {
            if (value != NULL) {
                *value = current->value;
            }
            return 1;
        }
        current = current->next;
    }
    
    return 0;  // 未找到
}

// 删除键值对
int hash_table_delete(HashTable *table, int key) {
    if (table == NULL) {
        return 0;
    }
    
    int index = hash_function(key);
    HashNode *current = table->buckets[index];
    HashNode *prev = NULL;
    
    while (current != NULL) {
        if (current->key == key) {
            if (prev == NULL) {
                table->buckets[index] = current->next;
            } else {
                prev->next = current->next;
            }
            free(current);
            table->size--;
            return 1;
        }
        prev = current;
        current = current->next;
    }
    
    return 0;  // 未找到
}

// 打印哈希表
void hash_table_print(HashTable *table) {
    if (table == NULL) {
        return;
    }
    
    printf("哈希表内容（大小：%d）：\n", table->size);
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        if (table->buckets[i] != NULL) {
            printf("桶 %d: ", i);
            HashNode *current = table->buckets[i];
            while (current != NULL) {
                printf("(%d,%d) ", current->key, current->value);
                current = current->next;
            }
            printf("\n");
        }
    }
}

// 释放哈希表内存
void hash_table_free(HashTable *table) {
    if (table == NULL) {
        return;
    }
    
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        HashNode *current = table->buckets[i];
        while (current != NULL) {
            HashNode *temp = current;
            current = current->next;
            free(temp);
        }
    }
    table->size = 0;
}

// 测试哈希表
void test_hash_table(void) {
    printf("\n=== 哈希表测试 ===\n");
    
    HashTable table;
    hash_table_init(&table);
    
    // 插入数据
    printf("插入数据：\n");
    int keys[] = {1, 12, 23, 34, 45, 56, 67, 78, 89, 90};
    int values[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int n = sizeof(keys) / sizeof(keys[0]);
    
    for (int i = 0; i < n; i++) {
        hash_table_insert(&table, keys[i], values[i]);
        printf("插入 (%d,%d)\n", keys[i], values[i]);
    }
    
    hash_table_print(&table);
    
    // 查找数据
    printf("\n查找测试：\n");
    int search_keys[] = {23, 99, 45, 100};
    for (int i = 0; i < 4; i++) {
        int value;
        if (hash_table_get(&table, search_keys[i], &value)) {
            printf("键 %d 的值：%d\n", search_keys[i], value);
        } else {
            printf("键 %d 未找到\n", search_keys[i]);
        }
    }
    
    // 更新数据
    printf("\n更新数据：\n");
    hash_table_insert(&table, 23, 999);
    printf("更新键 23 的值为 999\n");
    
    int value;
    if (hash_table_get(&table, 23, &value)) {
        printf("键 23 的新值：%d\n", value);
    }
    
    // 删除数据
    printf("\n删除测试：\n");
    if (hash_table_delete(&table, 45)) {
        printf("成功删除键 45\n");
    }
    
    if (!hash_table_get(&table, 45, &value)) {
        printf("确认键 45 已被删除\n");
    }
    
    printf("\n删除后的哈希表：\n");
    hash_table_print(&table);
    
    // 释放内存
    hash_table_free(&table);
    printf("\n哈希表内存已释放\n");
}

经典算法题

面试题8：动态规划经典题目

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
// 斐波那契数列（动态规划）
long long fibonacci_dp(int n) {
    if (n <= 1) {
        return n;
    }
    
    long long *dp = (long long*)malloc((n + 1) * sizeof(long long));
    if (dp == NULL) {
        return -1;
    }
    
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    long long result = dp[n];
    free(dp);
    return result;
}

// 最长公共子序列
int longest_common_subsequence(const char *str1, const char *str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    
    // 创建DP表
    int **dp = (int**)malloc((len1 + 1) * sizeof(int*));
    for (int i = 0; i <= len1; i++) {
        dp[i] = (int*)calloc(len2 + 1, sizeof(int));
    }
    
    // 填充DP表
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? 
                           dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }
    
    int result = dp[len1][len2];
    
    // 释放内存
    for (int i = 0; i <= len1; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

// 0-1背包问题
int knapsack_01(int weights[], int values[], int n, int capacity) {
    // 创建DP表
    int **dp = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int*)calloc(capacity + 1, sizeof(int));
    }
    
    // 填充DP表
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                int include = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                int exclude = dp[i - 1][w];
                dp[i][w] = (include > exclude) ? include : exclude;
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    
    int result = dp[n][capacity];
    
    // 释放内存
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

// 最大子数组和（Kadane算法）
int max_subarray_sum(int arr[], int n) {
    if (n == 0) {
        return 0;
    }
    
    int max_so_far = arr[0];
    int max_ending_here = arr[0];
    
    for (int i = 1; i < n; i++) {
        max_ending_here = (arr[i] > max_ending_here + arr[i]) ? 
                          arr[i] : max_ending_here + arr[i];
        max_so_far = (max_so_far > max_ending_here) ? 
                     max_so_far : max_ending_here;
    }
    
    return max_so_far;
}

// 测试动态规划算法
void test_dynamic_programming(void) {
    printf("\n=== 动态规划算法测试 ===\n");
    
    // 测试斐波那契数列
    printf("斐波那契数列：\n");
    for (int i = 0; i <= 10; i++) {
        printf("F(%d) = %lld\n", i, fibonacci_dp(i));
    }
    
    // 测试最长公共子序列
    printf("\n最长公共子序列：\n");
    const char *str1 = "ABCDGH";
    const char *str2 = "AEDFHR";
    int lcs_length = longest_common_subsequence(str1, str2);
    printf("\"%s\" 和 \"%s\" 的LCS长度：%d\n", str1, str2, lcs_length);
    
    // 测试0-1背包
    printf("\n0-1背包问题：\n");
    int weights[] = {10, 20, 30};
    int values[] = {60, 100, 120};
    int n = 3;
    int capacity = 50;
    
    printf("物品重量：");
    for (int i = 0; i < n; i++) {
        printf("%d ", weights[i]);
    }
    printf("\n");
    
    printf("物品价值：");
    for (int i = 0; i < n; i++) {
        printf("%d ", values[i]);
    }
    printf("\n");
    
    printf("背包容量：%d\n", capacity);
    int max_value = knapsack_01(weights, values, n, capacity);
    printf("最大价值：%d\n", max_value);
    
    // 测试最大子数组和
    printf("\n最大子数组和：\n");
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    
    printf("数组：");
    for (int i = 0; i < arr_size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    int max_sum = max_subarray_sum(arr, arr_size);
    printf("最大子数组和：%d\n", max_sum);
}

总结

算法与数据结构是C语言面试的核心内容，主要包括：

排序算法

  • 基础排序：冒泡、选择、插入排序
  • 高级排序：快速、归并、堆排序
  • 时间复杂度：理解各种排序算法的时间和空间复杂度
  • 适用场景：根据数据特点选择合适的排序算法

搜索算法

  • 线性搜索：简单但效率较低
  • 二分搜索：适用于有序数组，效率高
  • 变种应用：查找第一个/最后一个出现位置

数据结构实现

  • 链表：单链表的增删改查、反转、环检测
  • 栈：LIFO特性，括号匹配等应用
  • 队列：FIFO特性，循环队列实现
  • 二叉树：BST的增删改查、遍历算法
  • 哈希表：键值对存储，冲突处理

经典算法

  • 动态规划：斐波那契、LCS、背包问题
  • 贪心算法：局部最优解
  • 分治算法：递归解决问题
  • 图算法：DFS、BFS、最短路径

面试要点

  1. 算法分析：能够分析时间和空间复杂度
  2. 代码实现：熟练编写各种算法和数据结构
  3. 优化思路：能够优化算法性能
  4. 实际应用：理解算法在实际项目中的应用

学习建议

  • 理解算法原理，不要死记硬背
  • 多练习编程实现，提高代码质量
  • 分析复杂度，培养算法思维
  • 学习经典题目，掌握解题模式
  • 关注边界条件和异常处理

掌握这些算法与数据结构知识，能够在面试中展现扎实的计算机基础和编程能力。

完整测试程序

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

// 这里包含上面所有的函数实现...

int main(void) {
    printf("=== C语言算法与数据结构面试题测试 ===\n\n");
    
    // 测试排序算法
    test_sorting_algorithms();
    
    // 测试搜索算法
    test_search_algorithms();
    
    // 测试链表操作
    test_linked_list_operations();
    
    // 测试栈操作
    test_stack_operations();
    
    // 测试队列操作
    test_queue_operations();
    
    // 测试二叉树操作
    test_binary_tree_operations();
    
    // 测试哈希表
    test_hash_table();
    
    // 测试动态规划
    test_dynamic_programming();
    
    printf("\n=== 所有测试完成 ===\n");
    return 0;
}

版权所有，如有侵权请联系我