3.单链表

3.单链表

明廷盛 嘻嘻😁
  2025-03-24 10:25:35 2025-03-24 10:25:35 Created   2025-03-24 15:40 2025-03-24 15:40 Updated   6.8k Words  36 Mins  

第一章 自测&关键词回顾

单链表(带头)实现: 视频
单链表(不带头)实现: 二级指针 再封装
单链表(相关算法): 视频
多项式实现: 视频

第二章 手撕

第一节 带头单链表

比无头简答, 用的多

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
//  带 头结点的 单链表;
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

typedef struct SingleLinkListNode {
    DataType data;
    struct SingleLinkListNode *next;
} SingleLinkListNode;

// 创建链表
SingleLinkListNode *initSingleLinkList();
// 销毁链表(不是清空,所以头节点也需要free)
void destorySingleLinkList(SingleLinkListNode *list);
// 遍历
void traverseSingleLinkList(SingleLinkListNode *list);
// 插入
void pushBack(SingleLinkListNode *list, DataType data);
void pushFront(SingleLinkListNode *list, DataType data);
void insert(SingleLinkListNode *list, DataType data, int posIndex);
// 删除
void popBack(SingleLinkListNode *list);
void popFront(SingleLinkListNode *list);
void erase(SingleLinkListNode *list, int posIndex);
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
#include "singleLinkList.h"

// 创建链表
SingleLinkListNode *initSingleLinkList() {
    SingleLinkListNode *phead = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    phead->data = 0;  // 头节点的数据域存储=>链表的长度

    SingleLinkListNode *pmove = phead;  // 移动指针

    int input;
    while (scanf("%d", &input) == 1) {  // 按下任意CTRL+英文字母(除C和Z)scanf都会返回0
        SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
        newNode->data = input;
        pmove->next = newNode;

        pmove = pmove->next;
        phead->data++;
    }
    pmove->next = NULL;  // 记得置空
    return phead;
}
// 销毁链表(不是清空,所以头节点也需要free)
void destorySingleLinkList(SingleLinkListNode *list) {
    SingleLinkListNode *pmove = list;
    while (pmove) {
        SingleLinkListNode *temp = pmove->next;
        free(pmove);
        pmove = temp;
    }
}
// 遍历
void traverseSingleLinkList(SingleLinkListNode *list) {
    SingleLinkListNode *pmove = list->next;
    while (pmove) {
        printf("%d->", pmove->data);
        pmove = pmove->next;
    }
    printf("NULL Length:%d\n", list->data);
}
// 插入
void pushBack(SingleLinkListNode *list, DataType data) {
    SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    newNode->data = data;
    newNode->next = NULL;
    SingleLinkListNode *pmove = list;
    while (pmove->next)
        pmove = pmove->next;
    pmove->next = newNode;
    list->data++;
}
void pushFront(SingleLinkListNode *list, DataType data) {
    SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    newNode->data = data;
    newNode->next = list->next;
    list->next = newNode;
    list->data++;
}
void insert(SingleLinkListNode *list, DataType data, int posIndex) {
    // 断言里面一定是非,才会触发
    assert(!(posIndex > list->data || posIndex < 0) && "insert posIndex is illegal!");

    SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    newNode->data = data;

    SingleLinkListNode *cur = list->next;
    SingleLinkListNode *pre = list;
    while (posIndex--) {
        pre = cur;
        cur = cur->next;
    }
    pre->next = newNode;
    newNode->next = cur;
    list->data++;
}
// 删除
void popBack(SingleLinkListNode *list) {
    assert(list->data && "list is empty");

    SingleLinkListNode *pmove = list;
    while (pmove->next->next) {
        pmove = pmove->next;
    }
    free(pmove->next);
    pmove->next = NULL;
    list->data--;
}
void popFront(SingleLinkListNode *list) {
    assert(list->data && "list is empty");
    SingleLinkListNode *temp = list->next;
    list->next = list->next->next;
    free(temp);
    list->data--;
}
void erase(SingleLinkListNode *list, int posIndex) {
    assert(!(posIndex >= list->data || posIndex < 0) && "erase posIndex is illegal!");
    assert(list->data && "list is empty");
    SingleLinkListNode *cur = list->next;
    SingleLinkListNode *pre = list;
    while (posIndex--) {
        pre = cur;
        cur = cur->next;
    }
    pre->next = cur->next;
    free(cur);
    list->data--;
} // 30+30+30+15=1h:45min
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
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
#include <stdbool.h>
#include <string.h>
#include <time.h>
#include <setjmp.h>
#include <signal.h>
#include "singleLinkList.h"

// 辅助函数：创建具有特定内容的链表
SingleLinkListNode* createTestList(int* arr, int size) {
    SingleLinkListNode* list = (SingleLinkListNode*)malloc(sizeof(SingleLinkListNode));
    list->data = 0;
    list->next = NULL;
    
    for (int i = 0; i < size; i++) {
        pushBack(list, arr[i]);
    }
    
    return list;
}

// 创建一个空链表
SingleLinkListNode* createEmptyList() {
    SingleLinkListNode* list = (SingleLinkListNode*)malloc(sizeof(SingleLinkListNode));
    list->data = 0;
    list->next = NULL;
    return list;
}

// 辅助函数：检查链表内容是否与数组匹配
bool checkListContent(SingleLinkListNode* list, int* expected, int size) {
    if (list->data != size) {
        printf("    预期长度: %d, 实际长度: %d\n", size, list->data);
        return false;
    }
    
    SingleLinkListNode* pmove = list->next;
    for (int i = 0; i < size; i++) {
        if (!pmove || pmove->data != expected[i]) {
            printf("    索引 %d 处值不匹配: 预期 %d, 实际 ", i, expected[i]);
            if (!pmove) printf("NULL\n");
            else printf("%d\n", pmove->data);
            return false;
        }
        pmove = pmove->next;
    }
    
    if (pmove != NULL) {
        printf("    链表长度超出预期\n");
        return false;
    }
    
    return true;
}

// 测试函数：基本操作
bool testBasicOperations() {
    printf("测试基本操作:\n");
    bool allPassed = true;
    
    // 测试创建和销毁空链表
    printf("  测试创建和销毁空链表: ");
    SingleLinkListNode* list = createEmptyList();
    bool result = (list->data == 0 && list->next == NULL);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    destorySingleLinkList(list);
    return allPassed;
}

// 测试函数：插入操作
bool testPushOperations() {
    printf("测试插入操作:\n");
    bool allPassed = true;
    
    // 测试向空链表 pushBack
    printf("  测试向空链表 pushBack: ");
    SingleLinkListNode* list = createEmptyList();
    
    pushBack(list, 10);
    
    int expected1[] = {10};
    bool result = checkListContent(list, expected1, 1);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试多次 pushBack
    printf("  测试多次 pushBack: ");
    pushBack(list, 20);
    pushBack(list, 30);
    
    int expected2[] = {10, 20, 30};
    result = checkListContent(list, expected2, 3);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试向空链表 pushFront
    printf("  测试向空链表 pushFront: ");
    SingleLinkListNode* listEmpty = createEmptyList();
    
    pushFront(listEmpty, 5);
    
    int expected3[] = {5};
    result = checkListContent(listEmpty, expected3, 1);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    destorySingleLinkList(listEmpty);
    
    // 测试多次 pushFront
    printf("  测试多次 pushFront: ");
    pushFront(list, 5);
    pushFront(list, 1);
    
    int expected4[] = {1, 5, 10, 20, 30};
    result = checkListContent(list, expected4, 5);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试 insert 在头部
    printf("  测试 insert 在头部: ");
    insert(list, 0, 0);
    
    int expected5[] = {0, 1, 5, 10, 20, 30};
    result = checkListContent(list, expected5, 6);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试 insert 在中间
    printf("  测试 insert 在中间: ");
    insert(list, 15, 4);
    
    int expected6[] = {0, 1, 5, 10, 15, 20, 30};
    result = checkListContent(list, expected6, 7);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试 insert 在尾部
    printf("  测试 insert 在尾部: ");
    insert(list, 40, list->data);
    
    int expected7[] = {0, 1, 5, 10, 15, 20, 30, 40};
    result = checkListContent(list, expected7, 8);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    destorySingleLinkList(list);
    return allPassed;
}

// 测试函数：删除操作
bool testPopOperations() {
    printf("测试删除操作:\n");
    bool allPassed = true;
    
    // 测试单元素链表 popBack
    printf("  测试单元素链表 popBack: ");
    SingleLinkListNode* singleList = createEmptyList();
    pushBack(singleList, 10);
    popBack(singleList);
    
    bool result = (singleList->data == 0 && singleList->next == NULL);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    destorySingleLinkList(singleList);
    
    // 测试单元素链表 popFront
    printf("  测试单元素链表 popFront: ");
    singleList = createEmptyList();
    pushBack(singleList, 10);
    popFront(singleList);
    
    result = (singleList->data == 0 && singleList->next == NULL);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    destorySingleLinkList(singleList);
    
    // 测试多元素链表的删除操作
    int initial[] = {10, 20, 30, 40, 50};
    SingleLinkListNode* list = createTestList(initial, 5);
    
    // 测试 popBack
    printf("  测试多元素链表 popBack: ");
    popBack(list);
    
    int expected1[] = {10, 20, 30, 40};
    result = checkListContent(list, expected1, 4);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试 popFront
    printf("  测试多元素链表 popFront: ");
    popFront(list);
    
    int expected2[] = {20, 30, 40};
    result = checkListContent(list, expected2, 3);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试 erase 头部
    printf("  测试 erase 头部: ");
    list = createTestList(initial, 5); // 重新创建链表
    erase(list, 0);
    
    int expected3[] = {20, 30, 40, 50};
    result = checkListContent(list, expected3, 4);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试 erase 中间
    printf("  测试 erase 中间: ");
    erase(list, 1);
    
    int expected4[] = {20, 40, 50};
    result = checkListContent(list, expected4, 3);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试 erase 尾部
    printf("  测试 erase 尾部: ");
    erase(list, list->data - 1);
    
    int expected5[] = {20, 40};
    result = checkListContent(list, expected5, 2);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    destorySingleLinkList(list);
    return allPassed;
}

// 测试函数：特殊边界情况
bool testEdgeCases() {
    printf("测试特殊边界情况:\n");
    bool allPassed = true;
    
    // 测试空链表基本属性
    printf("  测试空链表基本属性: ");
    SingleLinkListNode* list = createEmptyList();
    
    bool result = (list->data == 0 && list->next == NULL);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试插入后再全部删除
    printf("  测试插入后全部删除: ");
    pushBack(list, 10);
    pushBack(list, 20);
    pushBack(list, 30);
    popBack(list);
    popBack(list);
    popBack(list);
    
    result = (list->data == 0 && list->next == NULL);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试大量元素操作
    printf("  测试大量元素操作: ");
    const int LARGE_SIZE = 1000;
    for (int i = 0; i < LARGE_SIZE; i++) {
        pushBack(list, i);
    }
    
    result = (list->data == LARGE_SIZE);
    printf("%s (链表长度: %d)\n", result ? "通过" : "失败", list->data);
    allPassed &= result;
    
    destorySingleLinkList(list);
    
    printf("  注意：以下边界情况会触发断言，仅记录不执行：\n");
    printf("    - 对空链表执行删除操作\n");
    printf("    - 插入/删除索引超出范围\n");
    
    return allPassed;
}

// 综合测试
void runAllTests() {
    printf("============== 单链表实现测试 ==============\n");
    
    bool basicTestPassed = testBasicOperations();
    bool pushTestPassed = testPushOperations();
    bool popTestPassed = testPopOperations();
    bool edgeTestPassed = testEdgeCases();
    
    printf("\n============== 测试结果汇总 ==============\n");
    printf("基本操作测试: %s\n", basicTestPassed ? "通过" : "失败");
    printf("插入操作测试: %s\n", pushTestPassed ? "通过" : "失败");
    printf("删除操作测试: %s\n", popTestPassed ? "通过" : "失败");
    printf("边界情况测试: %s\n", edgeTestPassed ? "通过" : "失败");
    printf("总体结果: %s\n", 
           (basicTestPassed && pushTestPassed && popTestPassed && edgeTestPassed) 
           ? "全部通过" : "存在失败");
}

int main() {
    // 设置随机种子
    srand((unsigned int)time(NULL));
    
    // 运行所有测试
    runAllTests();
    
    return 0;
}

第二节 无头单链表

主流的有两种实现①再封装的方式(同时维护一个头节点, 尾节点, size的结构体) ②二级指针(如下实现方式)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

typedef struct SingleLinkListNode {
    DataType data;
    struct SingleLinkListNode *next;
} SingleLinkListNode;

// 创建链表
SingleLinkListNode *initSingleLinkList();
// 销毁链表
void destorySingleLinkList(SingleLinkListNode *list);
// 遍历
void traverseSingleLinkList(SingleLinkListNode *list);
// 插入
void insert(SingleLinkListNode **list, DataType data, int posIndex);
// 删除
void erase(SingleLinkListNode **list, int posIndex);
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
#include "singleLinkList.h"

// 创建链表
SingleLinkListNode *initSingleLinkList() {

    DataType input;
    if (scanf("%d", &input) == 1) {
        SingleLinkListNode *phead = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
        phead->data = input;
        phead->next = NULL;

        SingleLinkListNode *pmove = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
        pmove = phead;

        while (scanf("%d", &input) == 1) {
            SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
            newNode->data = input;
            pmove->next = newNode;

            pmove = pmove->next;
        }
        pmove->next = NULL;
        return phead;
    } else {
        return NULL;
    }
}
// 销毁链表
void destorySingleLinkList(SingleLinkListNode *list) {
    while (list) {
        SingleLinkListNode *temp = list;
        list = list->next;
        free(list);
    }  // TODO
}
// 遍历
void traverseSingleLinkList(SingleLinkListNode *list) {
    SingleLinkListNode *temp = list;
    while (temp) {
        printf("%d->", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}
// 插入
void insert(SingleLinkListNode **list, DataType data, int posIndex) {
    SingleLinkListNode *newNode = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    newNode->data = data;

    if ((*list) == NULL || !posIndex) {  // 相当于头插
        assert(!posIndex && "insert posIndex is illegal!");
        newNode->next = *list;
        *list = newNode;  // 改变表头
    }
    // 现在就是有头的了
    else {
        SingleLinkListNode *cur = (*list)->next;
        SingleLinkListNode *pre = (*list);
        while (--posIndex > 0) {  // 循环postIndex-1次; 后置的话会循环postIndex次
            pre = cur;
            assert(pre && "insert posIndex out of range");  // 及时断言
            cur = cur->next;
        }
        pre->next = newNode;
        newNode->next = cur;
    }
}
// 删除
void erase(SingleLinkListNode **list, int posIndex) {
    assert(*list && "list is empty!");
    if (!(*list)->next || !posIndex) {  // 相当于头删
        assert(!posIndex && "insert posIndex is illegal!");
        *list = (*list)->next;
    }
    // 现在就是有头的了
    else {
        SingleLinkListNode *cur = (*list)->next;
        SingleLinkListNode *pre = (*list);
        while (--posIndex > 0) {
            pre = cur;
            cur = cur->next;
            assert(cur && "earse posIndex out of range");  // 及时断言
        }
        pre->next = cur->next;
    }
}
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
260
261
262
#include <stdbool.h>
#include <string.h>
#include <time.h>
#include "singleLinkList.h"

// 创建测试链表（手动创建，不使用initSingleLinkList避免需要用户输入）
SingleLinkListNode* createTestList(int* arr, int size) {
    if (size == 0) return NULL;
    
    SingleLinkListNode* head = (SingleLinkListNode*)malloc(sizeof(SingleLinkListNode));
    head->data = arr[0];
    head->next = NULL;
    
    SingleLinkListNode* pmove = head;
    for (int i = 1; i < size; i++) {
        SingleLinkListNode* newNode = (SingleLinkListNode*)malloc(sizeof(SingleLinkListNode));
        newNode->data = arr[i];
        newNode->next = NULL;
        
        pmove->next = newNode;
        pmove = pmove->next;
    }
    
    return head;
}

// 检查链表内容是否与数组匹配
bool checkListContent(SingleLinkListNode* list, int* expected, int size) {
    if ((list == NULL) && (size == 0)) return true;
    if ((list == NULL) || (size == 0)) return false;
    
    SingleLinkListNode* pmove = list;
    for (int i = 0; i < size; i++) {
        if (!pmove || pmove->data != expected[i]) {
            printf("    索引 %d 处值不匹配: 预期 %d, 实际 ", i, expected[i]);
            if (!pmove) printf("NULL\n");
            else printf("%d\n", pmove->data);
            return false;
        }
        pmove = pmove->next;
    }
    
    if (pmove != NULL) {
        printf("    链表长度超出预期\n");
        return false;
    }
    
    return true;
}

// 计算链表长度
int getListLength(SingleLinkListNode* list) {
    int length = 0;
    SingleLinkListNode* pmove = list;
    while (pmove) {
        length++;
        pmove = pmove->next;
    }
    return length;
}

// 测试销毁函数
bool testDestroy() {
    printf("测试销毁链表:\n");
    
    // 创建测试链表
    int arr[] = {1, 2, 3, 4, 5};
    SingleLinkListNode* list = createTestList(arr, 5);
    
    // 调用销毁函数
    printf("  调用destorySingleLinkList: ");
    destorySingleLinkList(list);
    printf("通过 (无法检查内存是否正确释放)\n");
    
    return true;
}

// 测试插入操作
bool testInsert() {
    printf("测试插入操作:\n");
    bool allPassed = true;
    
    // 测试向空链表插入
    printf("  测试向空链表插入: ");
    SingleLinkListNode* emptyList = NULL;
    insert(&emptyList, 100, 0);
    
    int expected1[] = {100};
    bool result = checkListContent(emptyList, expected1, 1);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    destorySingleLinkList(emptyList);
    
    // 测试向链表头插入
    printf("  测试向链表头插入: ");
    int arr[] = {20, 30, 40};
    SingleLinkListNode* list = createTestList(arr, 3);
    
    insert(&list, 10, 0);
    
    int expected2[] = {10, 20, 30, 40};
    result = checkListContent(list, expected2, 4);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试向链表中间插入
    printf("  测试向链表中间插入: ");
    insert(&list, 25, 2);
    
    int expected3[] = {10, 20, 25, 30, 40};
    result = checkListContent(list, expected3, 5);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试向链表尾部插入
    printf("  测试向链表尾部插入: ");
    insert(&list, 50, 5);
    
    int expected4[] = {10, 20, 25, 30, 40, 50};
    result = checkListContent(list, expected4, 6);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    destorySingleLinkList(list);
    return allPassed;
}

// 测试删除操作
bool testErase() {
    printf("测试删除操作:\n");
    bool allPassed = true;
    
    // 测试单节点链表删除
    printf("  测试单节点链表删除: ");
    SingleLinkListNode* singleList = createTestList((int[]){100}, 1);
    erase(&singleList, 0);
    
    bool result = (singleList == NULL);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试删除链表头
    printf("  测试删除链表头: ");
    int arr[] = {10, 20, 30, 40, 50};
    SingleLinkListNode* list = createTestList(arr, 5);
    
    erase(&list, 0);
    
    int expected1[] = {20, 30, 40, 50};
    result = checkListContent(list, expected1, 4);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试删除链表中间节点
    printf("  测试删除链表中间节点: ");
    erase(&list, 1);
    
    int expected2[] = {20, 40, 50};
    result = checkListContent(list, expected2, 3);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试删除链表尾节点
    printf("  测试删除链表尾节点: ");
    erase(&list, 2);
    
    int expected3[] = {20, 40};
    result = checkListContent(list, expected3, 2);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    destorySingleLinkList(list);
    return allPassed;
}

// 测试边界情况
bool testEdgeCases() {
    printf("测试边界情况:\n");
    
    // 测试空链表
    printf("  测试空链表创建和检查: ");
    SingleLinkListNode* emptyList = NULL;
    bool result = (emptyList == NULL);
    printf("%s\n", result ? "通过" : "失败");
    
    printf("  注意：以下边界情况会触发断言，仅记录不执行：\n");
    printf("    - 对空链表执行删除操作\n");
    printf("    - 对空链表非0位置插入\n");
    printf("    - 插入/删除索引超出范围\n");
    
    return true;
}

// 测试链表长度计算
bool testLength() {
    printf("测试链表长度计算:\n");
    bool allPassed = true;
    
    // 测试空链表
    printf("  测试空链表长度: ");
    SingleLinkListNode* emptyList = NULL;
    bool result = (getListLength(emptyList) == 0);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    // 测试单节点链表
    printf("  测试单节点链表长度: ");
    SingleLinkListNode* singleList = createTestList((int[]){100}, 1);
    result = (getListLength(singleList) == 1);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    destorySingleLinkList(singleList);
    
    // 测试多节点链表
    printf("  测试多节点链表长度: ");
    int arr[] = {10, 20, 30, 40, 50};
    SingleLinkListNode* list = createTestList(arr, 5);
    result = (getListLength(list) == 5);
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    destorySingleLinkList(list);
    
    return allPassed;
}

// 运行所有测试
void runAllTests() {
    printf("============== 不带头节点单链表实现测试 ==============\n");
    
    bool lengthTestPassed = testLength();
    bool destroyTestPassed = testDestroy();
    bool insertTestPassed = testInsert();
    bool eraseTestPassed = testErase();
    bool edgeTestPassed = testEdgeCases();
    
    printf("\n============== 测试结果汇总 ==============\n");
    printf("长度计算测试: %s\n", lengthTestPassed ? "通过" : "失败");
    printf("销毁链表测试: %s\n", destroyTestPassed ? "通过" : "失败");
    printf("插入操作测试: %s\n", insertTestPassed ? "通过" : "失败");
    printf("删除操作测试: %s\n", eraseTestPassed ? "通过" : "失败");
    printf("边界情况测试: %s\n", edgeTestPassed ? "通过" : "失败");
    printf("总体结果: %s\n", 
           (lengthTestPassed && destroyTestPassed && insertTestPassed && eraseTestPassed && edgeTestPassed) 
           ? "全部通过" : "存在失败");
}


void test01(void) {
    SingleLinkListNode* list = initSingleLinkList();
    traverseSingleLinkList(list);
    erase(&list, 0);
    traverseSingleLinkList(list);
}

int main() {
    srand((unsigned int)time(NULL));
    runAllTests();
    // test01();
    
    return 0;
}

第三章 相关应用

第一节 有序链表的创建

要求: 输入为无序, 需要找到指定位置插入, 使其变得有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 1.创建有序链表
Node *createSortedLinkList(void) {
    Node *phead = (Node *)malloc(sizeof(Node));
    phead->next = NULL;
    int input;

    while (scanf("%d", &input) == 1 && input != -1) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = input;
        newNode->next = NULL;
        // 找到 xNode->next->data>input;
        Node *pmove = phead;
        while (pmove->next != NULL && pmove->next->data <= input) { pmove = pmove->next; }
        //  插入进去
        newNode->next = pmove->next;
        pmove->next = newNode;
    }
    return phead;
}

第二节 翻转链表

要求: 使用空间复杂度为O(1)的算法; (不能反复头插😅)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 2.翻转链表
void reverseLinkList(Node *phead) {
    if (phead->next == NULL || phead->next->next == NULL)
        return;  // 只有一个元素 or 没有元素, 就直接返回

    Node *pre = NULL;
    Node *cur = phead->next;
    while (cur) {
        Node *temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    phead->next = pre;
}

第三节 链表归并

要求: 两个有序链表, 归并为一个有序链表, 原链表中节点的地址不能变)
提示: 类似”归并排序”;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 3.链表归并
Node *mergeLinkList(Node *phead1, Node *phead2) {
    Node *newHead = (Node *)malloc(sizeof(Node));
    newHead->next = NULL;
    Node *pmove = newHead;

    Node *l = phead1->next, *r = phead2->next;  // 左右指针
    while (l && r) {
        if (l->data < r->data)
            pmove->next = l, l = l->next;
        else
            pmove->next = r, r = r->next;
        pmove = pmove->next;
    }
    while (l) pmove->next = l, l = l->next, pmove = pmove->next;
    while (r) pmove->next = r, r = r->next, pmove = pmove->next;
    return newHead;
}

第四节 链表用冒泡排序

提示: 只用swap值, 不用换地址

1
2
3
4
5
6
7
8
9
10
11
12
// 4.链表冒泡
void bubbleLinkList(Node *list) {
    for (Node *i = list->next; i; i = i->next) {
        for (Node *j = list->next; j; j = j->next) {
            if (j->next && j->data > j->next->data) {
                j->data = j->data ^ j->next->data;
                j->next->data = j->data ^ j->next->data;
                j->data = j->data ^ j->next->data;
            }
        }
    }
}

第五节 多项式的表示和实现❗

注意哟! 西工大的考点哈; ①创建多项式为 “有序链表的创建” ②多项式的相加为 “链表归并”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 单链表实现多项式(带有头节点)
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct LinkListNode {
    int exp;     // 指数
    float coef;  // 系数
    struct LinkListNode *next;
} LinkListNode;

// 创建多项式
LinkListNode *initPolynomial(void);
// 销毁多项式
void destoryPolynomial(LinkListNode *poly);
// 遍历多项式
void traversePolynomial(LinkListNode *poly);
// 多项式相加
LinkListNode *addPoly(LinkListNode *poly1, LinkListNode *poly2);
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
#include "polynomial.h"

// 创建多项式
LinkListNode *initPolynomial(void) {
    // 创建头节点(值域无意义)
    LinkListNode *phead = (LinkListNode *)malloc(sizeof(LinkListNode));
    phead->next = NULL;
    phead->exp = phead->coef = -1;

    float inputCoef;
    int inputExp;
    printf("请输入系数和指数(系数输入-1结束):\n");
    while (scanf("%f %d", &inputCoef, &inputExp) == 2 && inputExp != -1) {
        LinkListNode *newNode = (LinkListNode *)malloc(sizeof(LinkListNode));
        newNode->coef = inputCoef;
        newNode->exp = inputExp;
        //  按照指数(exp)升序插入链表中
        LinkListNode *pmove = phead;
        while (pmove->next != NULL && newNode->exp > pmove->next->exp) pmove = pmove->next;
        // 油饼的用户(x^2 + 2x^2 + 3x^2)这样输入
        if (pmove->next != NULL && newNode->exp == pmove->next->exp) {
            pmove->next->coef += newNode->coef;  // 合并下
        }
        // 否则就正常插入进来
        else {
            newNode->next = pmove->next;
            pmove->next = newNode;
        }
    }
    return phead;
}
// 销毁多项式
void destoryPolynomial(LinkListNode *poly) {
    while (poly) {
        LinkListNode *pre = poly;
        poly = poly->next;
        free(pre);
    }
}

// 遍历多项式
void traversePolynomial(LinkListNode *poly) {
    LinkListNode *pmove = poly->next;
    while (pmove) {
        // 打印符号
        if (pmove->coef >= 0 && pmove != poly->next) { printf("+"); }
        // 打印值
        printf("%.1fx^%d", pmove->coef, pmove->exp);
        pmove = pmove->next;
    }
    puts("");
}

// 多项式相加
LinkListNode *addPoly(LinkListNode *poly1, LinkListNode *poly2) {
    LinkListNode *newPoly = (LinkListNode *)malloc(sizeof(LinkListNode));
    newPoly->coef = newPoly->exp = -1;

    // 创建左右指针(分别指向两个有序链表的第一个元素)
    LinkListNode *l = poly1->next;
    LinkListNode *r = poly2->next;
    LinkListNode *pmove = newPoly;  // 控制newPoly的移动

    while (l && r) {
        if (l->exp < r->exp) {
            pmove->next = l;
            l = l->next;
        }
        // 两个指数相等, 可以合并
        else if (l->exp == r->exp) {
            l->coef += r->coef;  // 合并系数
            pmove->next = l;     // 任意合并一边都可以
            l = l->next;
            r = r->next;
        } else {
            pmove->next = r;
            r = r->next;
        }

        pmove = pmove->next ? pmove->next : pmove;  // 要不为NULL才能移动
    }
    // 处理剩余
    while (l) {
        pmove->next = l;
        // 为什么这里不怕,因为l/r两个while只会进一个,且原先l/r的最后一个->next一定为NULL
        pmove = pmove->next;
        l = l->next;
    }
    while (r) {
        pmove->next = r;
        pmove = pmove->next;
        r = r->next;
    }
    return newPoly;
}
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
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
#include <stdbool.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include "polynomial.h"

// 辅助函数：创建指定系数和指数的多项式
LinkListNode* createTestPoly(float* coefs, int* exps, int size) {
    LinkListNode* head = (LinkListNode*)malloc(sizeof(LinkListNode));
    head->exp = head->coef = -1;
    head->next = NULL;
    
    for (int i = 0; i < size; i++) {
        // 跳过系数为0的项
        if (fabs(coefs[i]) < 1e-6) continue;
        
        LinkListNode* newNode = (LinkListNode*)malloc(sizeof(LinkListNode));
        newNode->coef = coefs[i];
        newNode->exp = exps[i];
        newNode->next = NULL;
        
        // 按指数升序插入
        LinkListNode* pmove = head;
        while (pmove->next && newNode->exp > pmove->next->exp) {
            pmove = pmove->next;
        }
        
        // 合并同类项
        if (pmove->next && newNode->exp == pmove->next->exp) {
            pmove->next->coef += newNode->coef;
            // 如果合并后系数为0，删除该节点
            if (fabs(pmove->next->coef) < 1e-6) {
                LinkListNode* temp = pmove->next;
                pmove->next = temp->next;
                free(temp);
            }
            free(newNode);
        } else {
            newNode->next = pmove->next;
            pmove->next = newNode;
        }
    }
    
    return head;
}

// 辅助函数：检查两个多项式是否相等
bool polyEqual(LinkListNode* poly1, LinkListNode* poly2) {
    LinkListNode* p1 = poly1->next;
    LinkListNode* p2 = poly2->next;
    
    while (p1 && p2) {
        if (p1->exp != p2->exp || fabs(p1->coef - p2->coef) > 1e-6) {
            return false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    
    return p1 == NULL && p2 == NULL;
}

// 辅助函数：打印多项式比较结果
void printPolyComparison(LinkListNode* expected, LinkListNode* actual) {
    printf("  预期结果: ");
    traversePolynomial(expected);
    printf("  实际结果: ");
    traversePolynomial(actual);
}

// 测试创建多项式
bool testInitPolynomial() {
    printf("测试创建多项式:\n");
    bool allPassed = true;
    
    // 测试空多项式
    printf("  测试空多项式: ");
    float coefs1[] = {};
    int exps1[] = {};
    LinkListNode* poly1 = createTestPoly(coefs1, exps1, 0);
    bool result = poly1->next == NULL;
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    destoryPolynomial(poly1);
    
    // 测试单项多项式
    printf("  测试单项多项式: ");
    float coefs2[] = {2.0};
    int exps2[] = {3};
    LinkListNode* poly2 = createTestPoly(coefs2, exps2, 1);
    result = poly2->next && fabs(poly2->next->coef - 2.0) < 1e-6 && poly2->next->exp == 3;
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    destoryPolynomial(poly2);
    
    // 测试多项多项式
    printf("  测试多项多项式: ");
    float coefs3[] = {2.0, 3.0, 1.0};
    int exps3[] = {3, 1, 0};
    LinkListNode* poly3 = createTestPoly(coefs3, exps3, 3);
    LinkListNode* p = poly3->next;
    result = p && fabs(p->coef - 1.0) < 1e-6 && p->exp == 0;
    p = p ? p->next : NULL;
    result &= p && fabs(p->coef - 3.0) < 1e-6 && p->exp == 1;
    p = p ? p->next : NULL;
    result &= p && fabs(p->coef - 2.0) < 1e-6 && p->exp == 3;
    p = p ? p->next : NULL;
    result &= p == NULL;
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    destoryPolynomial(poly3);
    
    // 测试合并同类项
    printf("  测试合并同类项: ");
    float coefs4[] = {2.0, 3.0, 4.0};
    int exps4[] = {2, 2, 2};
    LinkListNode* poly4 = createTestPoly(coefs4, exps4, 3);
    result = poly4->next && fabs(poly4->next->coef - 9.0) < 1e-6 && poly4->next->exp == 2;
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    destoryPolynomial(poly4);
    
    return allPassed;
}

// 测试多项式加法
bool testAddPoly() {
    printf("测试多项式加法:\n");
    bool allPassed = true;
    
    // 测试不同指数项的合并
    printf("  测试不同指数项的合并: ");
    float coefs1[] = {2.0, 3.0};
    int exps1[] = {3, 1};
    float coefs2[] = {4.0, 5.0};
    int exps2[] = {2, 0};
    
    LinkListNode* poly1 = createTestPoly(coefs1, exps1, 2);
    LinkListNode* poly2 = createTestPoly(coefs2, exps2, 2);
    LinkListNode* result = addPoly(poly1, poly2);
    
    float expectedCoefs[] = {5.0, 3.0, 4.0, 2.0};
    int expectedExps[] = {0, 1, 2, 3};
    LinkListNode* expected = createTestPoly(expectedCoefs, expectedExps, 4);
    
    bool testResult = polyEqual(expected, result);
    printf("%s\n", testResult ? "通过" : "失败");
    if (!testResult) {
        printPolyComparison(expected, result);
    }
    allPassed &= testResult;
    
    destoryPolynomial(poly1);
    destoryPolynomial(poly2);
    destoryPolynomial(result);
    destoryPolynomial(expected);
    
    // 测试相同指数项的合并
    printf("  测试相同指数项的合并: ");
    float coefs3[] = {2.0, 3.0};
    int exps3[] = {3, 1};
    float coefs4[] = {4.0, -3.0};
    int exps4[] = {3, 1};
    
    poly1 = createTestPoly(coefs3, exps3, 2);
    poly2 = createTestPoly(coefs4, exps4, 2);
    result = addPoly(poly1, poly2);
    
    float expectedCoefs2[] = {0.0, 6.0};
    int expectedExps2[] = {1, 3};
    expected = createTestPoly(expectedCoefs2, expectedExps2, 2);
    
    testResult = polyEqual(expected, result);
    printf("%s\n", testResult ? "通过" : "失败");
    if (!testResult) {
        printPolyComparison(expected, result);
    }
    allPassed &= testResult;
    
    destoryPolynomial(poly1);
    destoryPolynomial(poly2);
    destoryPolynomial(result);
    destoryPolynomial(expected);
    
    // 测试一个多项式为空的情况
    printf("  测试一个多项式为空: ");
    float coefs5[] = {2.0, 3.0};
    int exps5[] = {3, 1};
    
    poly1 = createTestPoly(coefs5, exps5, 2);
    poly2 = createTestPoly(NULL, NULL, 0);
    result = addPoly(poly1, poly2);
    
    testResult = polyEqual(poly1, result);
    printf("%s\n", testResult ? "通过" : "失败");
    if (!testResult) {
        printPolyComparison(poly1, result);
    }
    allPassed &= testResult;
    
    destoryPolynomial(poly1);
    destoryPolynomial(poly2);
    destoryPolynomial(result);
    
    return allPassed;
}

// 测试边界情况
bool testEdgeCases() {
    printf("测试边界情况:\n");
    bool allPassed = true;
    
    // 测试系数为0的项
    printf("  测试系数为0的项: ");
    float coefs[] = {0.0, 3.0, 0.0};
    int exps[] = {3, 1, 0};
    LinkListNode* poly = createTestPoly(coefs, exps, 3);
    
    bool result = poly->next && fabs(poly->next->coef - 3.0) < 1e-6 && poly->next->exp == 1;
    result &= poly->next->next == NULL; // 系数为0的项应被忽略
    
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    destoryPolynomial(poly);
    
    // 测试大量项
    printf("  测试大量项: ");
    const int SIZE = 100;
    float* largeCoefs = (float*)malloc(SIZE * sizeof(float));
    int* largeExps = (int*)malloc(SIZE * sizeof(int));
    
    for (int i = 0; i < SIZE; i++) {
        largeCoefs[i] = (float)(i + 1);
        largeExps[i] = i;
    }
    
    poly = createTestPoly(largeCoefs, largeExps, SIZE);
    
    // 检查第一项和最后一项
    result = poly->next && fabs(poly->next->coef - 1.0) < 1e-6 && poly->next->exp == 0;
    LinkListNode* p = poly->next;
    for (int i = 0; i < SIZE-1; i++) {
        p = p->next;
    }
    result &= p && fabs(p->coef - 100.0) < 1e-6 && p->exp == 99;
    
    printf("%s\n", result ? "通过" : "失败");
    allPassed &= result;
    
    free(largeCoefs);
    free(largeExps);
    destoryPolynomial(poly);
    
    return allPassed;
}

// 运行所有测试
void runAllTests() {
    printf("============== 多项式实现测试 ==============\n");
    
    bool initTestPassed = testInitPolynomial();
    bool addTestPassed = testAddPoly();
    bool edgeTestPassed = testEdgeCases();
    
    printf("\n============== 测试结果汇总 ==============\n");
    printf("创建多项式测试: %s\n", initTestPassed ? "通过" : "失败");
    printf("多项式加法测试: %s\n", addTestPassed ? "通过" : "失败");
    printf("边界情况测试: %s\n", edgeTestPassed ? "通过" : "失败");
    printf("总体结果: %s\n", 
           (initTestPassed && addTestPassed && edgeTestPassed) 
           ? "全部通过" : "存在失败");
}
void test01(void) {
    LinkListNode* p1= initPolynomial();
    traversePolynomial(p1);
    LinkListNode* p2= initPolynomial();
    traversePolynomial(p2);
    LinkListNode* ans = addPoly(p1, p2);
    traversePolynomial(ans);

    destoryPolynomial(p1);
    destoryPolynomial(p2);
    destoryPolynomial(ans);
}

int main() {
    // test01();
    runAllTests();
    return 0;
}
/*
9 0
6 1
8 9
3 14
-1 -1

7 1
21 7
-8 9
-1 -1

ans=>9.0x^0+13.0x^1+21.0x^7+0.0x^9+3.0x^14
*/

第四章 上手真题

第五章 比赛怎么用

  • Title: 3.单链表
  • Author: 明廷盛
  • Created at : 2025-03-24 10:25:35
  • Updated at : 2025-03-24 15:40:00
  • Link: https://blog.20040424.xyz/2025/03/24/🏫考研/第一部分 数据结构/3.单链表/
  • License: All Rights Reserved © 明廷盛
On this page
3.单链表
  1. 第一章 自测&关键词回顾
  2. 第二章 手撕
    1. 第一节 带头单链表
    2. 第二节 无头单链表
  3. 第三章 相关应用
    1. 第一节 有序链表的创建
    2. 第二节 翻转链表
    3. 第三节 链表归并
    4. 第四节 链表用冒泡排序
    5. 第五节 多项式的表示和实现❗
  4. 第四章 上手真题
  5. 第五章 比赛怎么用