LV03-06-数据结构-线性表-单链表基本操作

发表于 分类于 ， ， 本文字数： 7.7k 阅读时长 ≈ 28 分钟

本文主要是数据结构——单链表基本操作的相关笔记，若笔记中有错误或者不合适的地方，欢迎批评指正😃。

点击查看使用工具及版本
Windows windows11
Ubuntu Ubuntu16.04的64位版本
VMware® Workstation 16 Pro 16.2.3 build-19376536
SecureCRT Version 8.7.2 (x64 build 2214) - 正式版-2020年5月14日
开发板 正点原子 i.MX6ULL Linux阿尔法开发板
uboot NXP官方提供的uboot，NXP提供的版本为uboot-imx-rel_imx_4.1.15_2.1.0_ga(使用的uboot版本为U-Boot 2016.03)
linux内核 linux-4.15(NXP官方提供)
STM32开发板 正点原子战舰V3(STM32F103ZET6)
点击查看本文参考资料
参考方向 参考原文
------
点击查看相关文件下载
--- ---

一、单链表创建

1.创建步骤

image-20221021081407738

【注意】这里用到了 malloc 内存申请函数，注意加上头文件 stdlib.h 。

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
/**
 * @Function   : slinkedlist_create
 * @brief      : 单链表创建
 * @param arg  : none
 * @return     : _slinkedlink类型，NULL,内存申请失败;H,单链表地址
 * @Description: 其实就是创建一个节点
 */
_slinkedlink slinkedlist_create(void)
{
    /* 1.定义一个单链表结构体指针变量 */
    _slinkedlink H;
    /* 2.申请内存空间 */
    H = (_slinkedlink)malloc(sizeof(_slinkednode));
    /* 3.判断是否申请成功 */
    if (H == NULL)
    {
        printf("[ERROR]Single linked list malloc failed!\n");
        return H;
    }
    /* 4.初始化内存空间 */
    H->data = 0;
    H->next = NULL;

    return H;
}

二、单链表释放

1.释放步骤

【注意】

（1） H 指向下一个节点的时候，为什么不用 H++ ？

如果说，节点是连续存放的，那可以像之前学习数组的时候一样进行 ++ 操作，但是这里是链表，各个节点的存储空间并非连续，所以 ++ 操作并没有任何意义，反而还可能会把后边的链表搞丢，链表的指针域就是指向下一个节点的，所以直接进行赋值才是正确的。即

1
H = H->next;

（2）此种释放方式可以直接释放掉头节点。

（3）临时指针 p 和 头部指针 H 是指向同一个节点的，释放的时候一定要先移动头节点 H 到下一个节点，保证释放后的链表地址不丢失。

image-20221021091359094

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
/**
 * @Function   : slinkedlist_free
 * @brief      : 单链表空间释放（释放整个单链表占用的内存空间）
 * @param H    : _slinkedlink类型，表示要释放的单链表的地址
 * @return     : _slinkedlink 类型，NULL,表示释放完成
 * @Description:
 */
_slinkedlink slinkedlist_free(_slinkedlink H)
{
    /* 定义一个单链表结构体指针变量 */
    _slinkedlink p;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return NULL;
    }
    /* 2. 开始释放内存 */
    p = H;
    printf("Single linked list free:");
    while (H != NULL)
    {
        p = H;
        printf("%d ", p->data);
        /* p 和 H指向同一个地址空间，要先移动 H， 再释放，否则后边的节点地址就丢掉了 */
        H = H->next;
        free(p);
    }
    puts(""); /* 自带换行 */

    return NULL;
}

三、单链表数据显示

1.数据显示步骤

image-20221021092056093

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
/**
 * @Function   : slinkedlist_show
 * @brief      : 单链表数据显示
 * @param H    : _slinkedlink类型，表示要释放的单链表的地址
 * @return     : int类型，0,显示成功;-1,单链表不存在
 * @Description:
 */
int slinkedlist_show(_slinkedlink H)
{
    /* 定义一个单链表结构体指针变量 */
    _slinkedlink p;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return -1;
    }
    /* 2. 遍历所有节点 */
    p = H;
    printf("Single linked list:");
    while (p->next != NULL)
    {
        printf("%d ", p->next->data);
        p = p->next;
    }
    puts(""); /* 自带换行 */

    return 0;
}

四、单链表节点查找

1.节点查找步骤

image-20221021170714437
点击查看 i、pos 和 p 的变化分析

查找时，i、pos 和 p 的关系分析如下，假设我们现在一共就只有 2 个节点，如下图所示：

image-20221021171039106

（1）我们现在查找 pos = -1 的节点，也就是头节点，毫无疑问，直接返回 H 即可；

（2）我们现在查找 pos = 0 的节点，也就是第 1 个节点：

image-20221021172808330

（3）我们现在查找 pos = 1 的节点，也就是第 2 个节点：

image-20221021173054776

（3）我们现在查找 pos = 5 的节点，也就是第 6 个节点：

image-20221021173054776

用上一次分析的图吧，其实一共就俩节点，当第二次循环结束后，我们会发现若此时再进行一次循环的话，p 会指向 NULL，这已经是单链表结尾了，若是此时还没有循环到要找的节点位置，说明我们输入的参数已经超出了单链表的长度范围，就没有继续循环的意义了，所以此时就需要进行判断，提前退出循环。

经过上边的分析，我们得到了两个结束循环的条件，一个是 i < pos，一个是 p = NULL。

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
/**
 * @Function   : slinkedlist_node_get
 * @brief      : 单链表节点查找（按位置查找）
 * @param H    : _slinkedlink类型，表示要查找的单链表的地址
 * @param pos  : int类型，表示要查找的节点位置，pos 大于等于 -1
 * @return     : _slinkedlink类型，查找成功则返回查找到的节点的地址，否则返回NULL
 * @Description:
 */
_slinkedlink slinkedlist_node_get(_slinkedlink H, int pos)
{
    /* 定一个单链表结构体指针变量 */
    _slinkedlink p;
    int i = 0;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return NULL;
    }
    /* 2. 检查参数是否合法 */
    if (pos == -1) /* pos = -1 表示查找的是头节点 */
    {
        return H;
    }
    /* 这里可以防止参数非法，而返回 H 的情况，可以防止删除节点函数误删 */
    if (pos < -1)
    {
        printf("[ERROR]get pos is invalid\n");
        return NULL;
    }
    /* 3. 开始遍历节点，查找所需节点 */
    p = H;
    i = -1; /* 一共需要循环 pos + 1 次 */
    while (i < pos)
    {
        p = p->next;
        if (p == NULL) /* 已经遍历到单链表尾部了 */
        {
            printf("[ERROR]get pos is invalid\n");
            return NULL;
        }
        i++;
    }

    return p;
}

五、单链表数据插入

1.尾部插入

1.1尾部插入步骤

5-1

具体的步骤如下：

image-20221021180010055

1.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
/**
 * @Function   : slinkedlist_tail_insert
 * @brief      : 单链表尾部插入数据
 * @param H    : _slinkedlink类型，表示要插入节点的单链表的地址
 * @param value: data_t类型，表示要插入的数据
 * @return     : int类型，0,插入成功;-1,插入失败
 * @Description:
 */
int slinkedlist_tail_insert(_slinkedlink H, data_t value)
{
    /* 定义两个个单链表结构体指针变量 */
    _slinkedlink p;
    _slinkedlink q;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return -1;
    }
    /* 2. 创建新节点并初始化 */
    if ((p = (_slinkedlink)malloc(sizeof(_slinkednode))) == NULL)
    {
        printf("[ERROR]The new node malloc failed!\n");
        return -1;
    }
    p->data = value;
    p->next = NULL;
    /* 3. 寻找尾节点 */
    q = H;
    while (q->next != NULL)
    {
        q = q->next;
    }
    /* 3. 插入新节点 */
    q->next = p;

    return 0;
}

2.指定位置插入

2.1指定位置插入步骤

5-2

具体步骤如下：

image-20221022084144365

【注意】

（1）在指定位置插入节点，关键在于我们要找到插入位置的前一个节点，这里我们调用了上边实现的单链表节点查找函数。

（2）有两种情况是非法的，就是在 -1 位置插入，这意味着在头结点位置插入，这是非法的，所以位置 pos 需要大于等于 0；第二种情况是插入的位置已经大大于了整个链表的长度，这个时候我们是无法查找到前一个节点的，这也是一种非法插入。

（3）一定要注意，先建立新节点与原来链表插入位置处节点的联系，然后再将插入位置的前一个节点的指针域指向新节点，以保证链表完整，如下图所示：

image-20221022084613065

2.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
/**
 * @Function   : slinkedlist_insert
 * @brief      : 单链表在指定位置插入节点
 * @param H    : _slinkedlink类型，表示要插入节点的单链表的地址
 * @param value: data_t类型，彪悍死要插入的数据
 * @param pos  : int类型，表示要插入的节点位置，pos 大于等于 0
 * @return     : int类型，0,插入成功;-1,插入失败
 * @Description:
 */
int slinkedlist_insert(_slinkedlink H, data_t value, int pos)
{
    /* 定义两个单链表结构体指针变量 */
    _slinkedlink p;
    _slinkedlink q;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return -1;
    }
    /* 2. 获取插入位置的前一个节点 */
    p = slinkedlist_node_get(H, pos - 1);
    if (p == NULL)
    {
        printf("[WARN ]pos-1 = %d position is not existed!\n", pos - 1);
        return -1;
    }
    /* 3. 创建新节点并初始化 */
    if ((q = (_slinkedlink)malloc(sizeof(_slinkednode))) == NULL)
    {
        printf("[ERROR]The new node malloc failed\n");
        return -1;
    }
    q->data = value;
    q->next = NULL;
    /* 4. 插入新节点 */
    q->next = p->next;
    p->next = q;

    return 0;
}

六、单链表删除节点

1.删除节点步骤

6

具体步骤：

image-20221022091100368

【注意】

（1）确保删除位置的 pos 参数正确范围，需要在获取节点位置函数中加上小于 -1 时的处理情况，这是因为，原来的获取节点位置函数中当 pos 小于等于 -1 的时候都会返回头节点，这对于获取节点位置函数本身是没有问题的，但是对于删除函数就有问题了，给到一个负值或者 pos-1 小于了 -1 的时候， slinkedlist_node_get 函数都会返回头节点地址，这就意味着，删除函数将会删除链表中头节点后边的哪个节点。

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
/**
 * @Function   : slinkedlist_delete
 * @brief      : 删除指定位置节点
 * @param H    : _slinkedlink类型，表示要删除节点的单链表的地址
 * @param pos  : int类型，要删除的节点位置（pos 大于等于 0）
 * @return     : int类型，0,删除成功;-1,删除失败
 * @Description:
 */
int slinkedlist_delete(_slinkedlink H, int pos)
{
    /* 定义两个单链表结构体指针变量 */
    _slinkedlink p;
    _slinkedlink q;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return -1;
    }
    /* 2. 获取删除位置的前一个节点 */
    /* 注意在这里，不合法的pos范围会在获取节点函数中被处理 */
    p = slinkedlist_node_get(H, pos - 1);
    if (p == NULL)
    {
        printf("[WARN ]pos-1 = %d position is not existed!\n", pos - 1);
        return -1;
    }
    if (p->next == NULL)
    {
        printf("delete pos is invalid!pos-1 = %d position is the last node!\n", pos - 1);
        return -1;
    }

    /* 3. 更新节点 */
    q = p->next;
    p->next = q->next; /* p->next = p->next->next; */

    /* 4.释放删除的节点 */
    printf("Single linked list node free:%d\n", q->data);
    free(q);
    q = NULL;
    return 0;
}

七、更新单链表节点数据

1.更新节点数据步骤

具体步骤：

image-20221022092259121

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
/**
 * @Function   : slinkedlist_node_update
 * @brief      : 更新指定位置的节点数据
 * @param H    : _slinkedlink类型，表示要更新数据的单链表的地址
 * @param value: data_t类型，表示要更新的数据
 * @param pos  : int类型，要更新的节点位置（pos 大于等于 0）
 * @return     : int类型， 0,更新成功;-1,更新失败
 * @Description:
 */
int slinkedlist_node_update(_slinkedlink H, data_t value, int pos)
{
    /* 定义一个单链表结构体指针变量 */
    _slinkedlink p;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("Single linked list is not existed!\n");
        return -1;
    }
    if (pos < 0)
    {
        printf("update pos is invalid!\n");
        return -1;
    }
    /* 2. 获取更新节点位置 */
    p = slinkedlist_node_get(H, pos);
    if (p == NULL)
    {
        printf("pos position is not existed!\n");
        return -1;
    }

    /* 3. 更新节点 */
    p->data = value;

    return 0;
}

八、求单链表长度

1.求单链表长度步骤

具体步骤：

image-20221022092945403

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
/**
 * @Function   : slinkedlist_length
 * @brief      : 获取单链表长度（不包含头节点）
 * @param H    : _slinkedlink类型，表示要获取长度的单链表的地址
 * @return     : int类型， 链表不存在则返回-1;否则返回单链表长度
 * @Description:
 */
int slinkedlist_length(_slinkedlink H)
{
    /* 定义一个链表结构体指针变量 */
    _slinkedlink p;
    int len = 0;

    /* 1.判断链表是否为存在, 不存在则直接返回 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return -1;
    }

    /* 2.遍历链表 */
    p = H;
    while (p->next != NULL)
    {
        len++;
        p = p->next;
    }
    return (len);
}

九、完整程序

1. slinkedlist.c

点击查看详情 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
/** =====================================================
 * Copyright © hk. 2022-2025. All rights reserved.
 * File name  : slinkedlist.c
 * Author     : qidaink
 * Date       : 2022-10-21
 * Version    :
 * Description:
 * Others     :
 * Log        :
 * ======================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include "slinkedlist.h"

/**
 * @Function   : slinkedlist_create
 * @brief      : 单链表创建
 * @param arg  : none
 * @return     : _slinkedlink类型，NULL,内存申请失败;H,单链表地址
 * @Description: 其实就是创建一个节点
 */
_slinkedlink slinkedlist_create(void)
{
    /* 1.定义一个单链表结构体指针变量 */
    _slinkedlink H;
    /* 2.申请内存空间 */
    H = (_slinkedlink)malloc(sizeof(_slinkednode));
    /* 3.判断是否申请成功 */
    if (H == NULL)
    {
        printf("[ERROR]Single linked list malloc failed!\n");
        return H;
    }
    /* 4.初始化内存空间 */
    H->data = 0;
    H->next = NULL;

    return H;
}

/**
 * @Function   : slinkedlist_free
 * @brief      : 单链表空间释放（释放整个单链表占用的内存空间）
 * @param H    : _slinkedlink类型，表示要释放的单链表的地址
 * @return     : _slinkedlink 类型，NULL,表示释放完成
 * @Description:
 */
_slinkedlink slinkedlist_free(_slinkedlink H)
{
    /* 定义一个单链表结构体指针变量 */
    _slinkedlink p;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return NULL;
    }
    /* 2. 开始释放内存 */
    p = H;
    printf("Single linked list free:");
    while (H != NULL)
    {
        p = H;
        printf("%d ", p->data);
        /* p 和 H指向同一个地址空间，要先移动 H， 再释放，否则后边的节点地址就丢掉了 */
        H = H->next;
        free(p);
    }
    puts(""); /* 自带换行 */

    return NULL;
}

/**
 * @Function   : slinkedlist_show
 * @brief      : 单链表数据显示
 * @param H    : _slinkedlink类型，表示要释放的单链表的地址
 * @return     : int类型，0,显示成功;-1,单链表不存在
 * @Description:
 */
int slinkedlist_show(_slinkedlink H)
{
    /* 定义一个单链表结构体指针变量 */
    _slinkedlink p;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return -1;
    }
    /* 2. 遍历所有节点 */
    p = H;
    printf("Single linked list:");
    while (p->next != NULL)
    {
        printf("%d ", p->next->data);
        p = p->next;
    }
    puts(""); /* 自带换行 */

    return 0;
}

/**
 * @Function   : slinkedlist_node_get
 * @brief      : 单链表节点查找（按位置查找）
 * @param H    : _slinkedlink类型，表示要查找的单链表的地址
 * @param pos  : int类型，表示要查找的节点位置，pos 大于等于 -1
 * @return     : _slinkedlink类型，查找成功则返回查找到的节点的地址，否则返回NULL
 * @Description:
 */
_slinkedlink slinkedlist_node_get(_slinkedlink H, int pos)
{
    /* 定一个单链表结构体指针变量 */
    _slinkedlink p;
    int i = 0;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return NULL;
    }
    /* 2. 检查参数是否合法 */
    if (pos == -1) /* pos = -1 表示查找的是头节点 */
    {
        return H;
    }
    /* 这里可以防止参数非法，而返回 H 的情况，可以防止删除节点函数误删 */
    if (pos < -1)
    {
        printf("[ERROR]get pos is invalid\n");
        return NULL;
    }
    /* 3. 开始遍历节点，查找所需节点 */
    p = H;
    i = -1; /* 一共需要循环 pos + 1 次 */
    while (i < pos)
    {
        p = p->next;
        if (p == NULL) /* 已经遍历到单链表尾部了 */
        {
            printf("[ERROR]get pos is invalid\n");
            return NULL;
        }
        i++;
    }

    return p;
}

/**
 * @Function   : slinkedlist_tail_insert
 * @brief      : 单链表尾部插入数据
 * @param H    : _slinkedlink类型，表示要插入节点的单链表的地址
 * @param value: data_t类型，表示要插入的数据
 * @return     : int类型，0,插入成功;-1,插入失败
 * @Description:
 */
int slinkedlist_tail_insert(_slinkedlink H, data_t value)
{
    /* 定义两个个单链表结构体指针变量 */
    _slinkedlink p;
    _slinkedlink q;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return -1;
    }
    /* 2. 创建新节点并初始化 */
    if ((p = (_slinkedlink)malloc(sizeof(_slinkednode))) == NULL)
    {
        printf("[ERROR]The new node malloc failed!\n");
        return -1;
    }
    p->data = value;
    p->next = NULL;
    /* 3. 寻找尾节点 */
    q = H;
    while (q->next != NULL)
    {
        q = q->next;
    }
    /* 3. 插入新节点 */
    q->next = p;

    return 0;
}

/**
 * @Function   : slinkedlist_insert
 * @brief      : 单链表在指定位置插入节点
 * @param H    : _slinkedlink类型，表示要插入节点的单链表的地址
 * @param value: data_t类型，彪悍死要插入的数据
 * @param pos  : int类型，表示要插入的节点位置，pos 大于等于 0
 * @return     : int类型，0,插入成功;-1,插入失败
 * @Description:
 */
int slinkedlist_insert(_slinkedlink H, data_t value, int pos)
{
    /* 定义两个单链表结构体指针变量 */
    _slinkedlink p;
    _slinkedlink q;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return -1;
    }
    /* 2. 获取插入位置的前一个节点 */
    p = slinkedlist_node_get(H, pos - 1);
    if (p == NULL)
    {
        printf("[WARN ]pos-1 = %d position is not existed!\n", pos - 1);
        return -1;
    }
    /* 3. 创建新节点并初始化 */
    if ((q = (_slinkedlink)malloc(sizeof(_slinkednode))) == NULL)
    {
        printf("[ERROR]The new node malloc failed\n");
        return -1;
    }
    q->data = value;
    q->next = NULL;
    /* 4. 插入新节点 */
    q->next = p->next;
    p->next = q;

    return 0;
}

/**
 * @Function   : slinkedlist_delete
 * @brief      : 删除指定位置节点
 * @param H    : _slinkedlink类型，表示要删除节点的单链表的地址
 * @param pos  : int类型，要删除的节点位置（pos 大于等于 0）
 * @return     : int类型，0,删除成功;-1,删除失败
 * @Description:
 */
int slinkedlist_delete(_slinkedlink H, int pos)
{
    /* 定义两个单链表结构体指针变量 */
    _slinkedlink p;
    _slinkedlink q;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return -1;
    }
    /* 2. 获取删除位置的前一个节点 */
    /* 注意在这里，不合法的pos范围会在获取节点函数中被处理 */
    p = slinkedlist_node_get(H, pos - 1);
    if (p == NULL)
    {
        printf("[WARN ]pos-1 = %d position is not existed!\n", pos - 1);
        return -1;
    }
    if (p->next == NULL)
    {
        printf("delete pos is invalid!pos-1 = %d position is the last node!\n", pos - 1);
        return -1;
    }

    /* 3. 更新节点 */
    q = p->next;
    p->next = q->next; /* p->next = p->next->next; */

    /* 4.释放删除的节点 */
    printf("Single linked list node free:%d\n", q->data);
    free(q);
    q = NULL;
    return 0;
}

/**
 * @Function   : slinkedlist_node_update
 * @brief      : 更新指定位置的节点数据
 * @param H    : _slinkedlink类型，表示要更新数据的单链表的地址
 * @param value: data_t类型，表示要更新的数据
 * @param pos  : int类型，要更新的节点位置（pos 大于等于 0）
 * @return     : int类型， 0,更新成功;-1,更新失败
 * @Description:
 */
int slinkedlist_node_update(_slinkedlink H, data_t value, int pos)
{
    /* 定义一个单链表结构体指针变量 */
    _slinkedlink p;

    /* 1. 判断单链表是否存在 */
    if (H == NULL)
    {
        printf("Single linked list is not existed!\n");
        return -1;
    }
    if (pos < 0)
    {
        printf("update pos is invalid!\n");
        return -1;
    }
    /* 2. 获取更新节点位置 */
    p = slinkedlist_node_get(H, pos);
    if (p == NULL)
    {
        printf("pos position is not existed!\n");
        return -1;
    }

    /* 3. 更新节点 */
    p->data = value;

    return 0;
}

/**
 * @Function   : slinkedlist_length
 * @brief      : 获取单链表长度（不包含头节点）
 * @param H    : _slinkedlink类型，表示要获取长度的单链表的地址
 * @return     : int类型， 链表不存在则返回-1;否则返回单链表长度
 * @Description:
 */
int slinkedlist_length(_slinkedlink H)
{
    /* 定义一个链表结构体指针变量 */
    _slinkedlink p;
    int len = 0;

    /* 1.判断链表是否为存在, 不存在则直接返回 */
    if (H == NULL)
    {
        printf("[WARN ]Single linked list is not existed!\n");
        return -1;
    }

    /* 2.遍历链表 */
    p = H;
    while (p->next != NULL)
    {
        len++;
        p = p->next;
    }
    return (len);
}

/* 测试函数实现 */
int test_slinkedlist_tail_insert()
{
	_slinkedlink H;
	int a[5] = {1,3,4, 5, 6};
	int i = 0;
	H = slinkedlist_create();
	if (H == NULL)
		return -1;
	for(i = 0; i<5; i++)
	{
		slinkedlist_tail_insert(H, a[i]);
	}
	slinkedlist_show(H);
	printf("H=%p\n", H);
	H = slinkedlist_free(H);
	printf("H=%p\n", H);
	return 0;
}

void test_slinkedlist_node_get()
{
	_slinkedlink H;
	_slinkedlink p;
	int a[5] = {1,3,4, 5, 6};
	int i = 0;
	H = slinkedlist_create();
	if (H == NULL)
		return;
	for(i = 0; i<5; i++)
	{
		slinkedlist_tail_insert(H, a[i]);
	}
	slinkedlist_show(H);
	for(i = -2; i<7; i++)
	{
		p = slinkedlist_node_get(H, i);
		if (p != NULL)
			printf("i = %d,value=%d\n", i, p->data);
	}

	printf("H=%p\n", H);
	H = slinkedlist_free(H);
	printf("H=%p\n", H);

}

void test_slinkedlist_insert()
{
	_slinkedlink H;
	int a[5] = {1,3,4, 5, 6};
	int i = 0;
	H = slinkedlist_create();
	if (H == NULL)
		return;
	slinkedlist_insert(H, a[0], 0);
	for(i = 1; i<5; i++)
	{
		slinkedlist_insert(H, a[i], 1);
	}
	slinkedlist_show(H);

	slinkedlist_insert(H, 100, 2);
	slinkedlist_insert(H, 200, 50);
	slinkedlist_insert(H, 300, -9);
	slinkedlist_show(H);
	printf("H=%p\n", H);
	H = slinkedlist_free(H);
	printf("H=%p\n", H);
}

void test_slinkedlist_delete()
{
	_slinkedlink H;
	int a[5] = {1,3,4, 5, 6};
	int i = 0;
	H = slinkedlist_create();
	if (H == NULL)
		return;
	for(i = 0; i<5; i++)
	{
		slinkedlist_tail_insert(H, a[i]);
	}
	slinkedlist_show(H);

	slinkedlist_delete(H, -4);
	slinkedlist_delete(H, 50);
	slinkedlist_delete(H, 2);
	slinkedlist_delete(H, 3);
	slinkedlist_delete(H, 3);
	slinkedlist_show(H);
	printf("H=%p\n", H);
	H = slinkedlist_free(H);
	printf("H=%p\n", H);
}

void test_slinkedlist_node_update()
{
	_slinkedlink H;
	int a[5] = {1,3,4, 5, 6};
	int i = 0;
	H = slinkedlist_create();
	if (H == NULL)
		return;
	for(i = 0; i<5; i++)
	{
		slinkedlist_tail_insert(H, a[i]);
	}
	slinkedlist_show(H);
	slinkedlist_node_update(H, 100, 2);
	slinkedlist_show(H);
	slinkedlist_node_update(H, 100, 0);
	slinkedlist_show(H);
	slinkedlist_node_update(H, 100, 4);
	slinkedlist_show(H);
	slinkedlist_node_update(H, 100, 5);
	slinkedlist_show(H);
	slinkedlist_node_update(H, 100, -1);
	slinkedlist_show(H);
	printf("H=%p\n", H);
	H = slinkedlist_free(H);
	printf("H=%p\n", H);
}


void test_slinkedlist_length()
{
	_slinkedlink H;

	int a[6] = {1, 3, 7, 5, 6, 8};
	int i = 0;
	H = slinkedlist_create();
	if (H == NULL)
		return;
	for(i = 0; i<6; i++)
	{
		slinkedlist_tail_insert(H, a[i]);
	}
	slinkedlist_show(H);

	printf("len=%d\n", slinkedlist_length(H));

	printf("H=%p\n", H);
	H = slinkedlist_free(H);
	printf("H=%p\n", H);
}

2. slinkedlist.h

点击查看详情 
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
/** =====================================================
 * Copyright © hk. 2022-2025. All rights reserved.
 * File name  : slinkedlist.h
 * Author     : qidaink
 * Date       : 2022-10-21
 * Version    :
 * Description:
 * Others     :
 * Log        :
 * ======================================================
 */
#ifndef __SLINKEDLIST_H__
#define __SLINKEDLIST_H__

/* 自定义数据类型 */
typedef int data_t;

typedef struct __node
{
    data_t data;
    struct __node *next;
} _slinkednode, *_slinkedlink;

/* 函数声明 */

_slinkedlink slinkedlist_create(void);                              /* 单链表创建 */
_slinkedlink slinkedlist_free(_slinkedlink H);                      /* 单链表空间释放（释放整个单链表占用的内存空间） */
int slinkedlist_show(_slinkedlink H);                               /* 单链表数据显示 */
_slinkedlink slinkedlist_node_get(_slinkedlink H, int pos);         /* 单链表节点查找（按位置查找） */
int slinkedlist_tail_insert(_slinkedlink H, data_t value);          /* 单链表尾部插入数据 */
int slinkedlist_insert(_slinkedlink H, data_t value, int pos);      /* 单链表在指定位置插入节点 */
int slinkedlist_delete(_slinkedlink H, int pos);                    /* 删除指定位置节点 */
int slinkedlist_node_update(_slinkedlink H, data_t value, int pos); /* 更新指定位置的节点数据 */
int slinkedlist_length(_slinkedlink H);                             /* 获取单链表长度（不包含头节点） */

int test_slinkedlist_tail_insert();/* 单链表尾部插入测试 */
void test_slinkedlist_node_get();/* 节点查找测试 */
void test_slinkedlist_insert();/* 指定位置插入测试 */
void test_slinkedlist_delete();/* 按位置删除节点测试 */
void test_slinkedlist_node_update();/* 更新节点数据测试 */
void test_slinkedlist_length();/* 获取链表长度测试 */

#endif

3. main.c

点击查看详情 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include "slinkedlist.h"

int main(int argc, char *argv[])
{
	// test_slinkedlist_tail_insert();
	// test_slinkedlist_node_get();
	// test_slinkedlist_insert();
	test_slinkedlist_delete();
	// test_slinkedlist_node_update();
	// test_slinkedlist_length();

	return 0;
}

4. Makefile

点击查看详情 
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
##============================================================================#
# Copyright © hk. 2022-2025. All rights reserved.
# File name  : Makefile
# Author     : qidaink
# Date       : 2022-09-29
# Version    : 
# Description: 
# Others     : 
# Log        : 
##============================================================================#
##

TARGET          := main
#============================================================================#
## 工具设置
# 设置交叉编译器名称
CROSS_COMPILE   :=
# 设置交叉编译器
CC              := $(CROSS_COMPILE)gcc
# 编译选项
CFLAGS          += -g -Wall
#============================================================================#
## 目录路径设置
# 头文件路径设置(.h)
INCDIRS 		:= .

# 源文件路径设置(.S .C)
SRCDIRS			:= .

# 生成的中间 .o 文件的位置
OBJDIRS         := .
#============================================================================#
# 生成编译器的 -I dir_path 参数 
INCLUDE			:= $(patsubst %, -I %, $(INCDIRS))

# 获取所有的 .C 文件名称(包含路径)
CFILES			:= $(foreach dir, $(SRCDIRS), $(wildcard $(dir)/*.c))

# 获取所有的 .C 文件名称(不包含路径)
CFILENDIR		:= $(notdir  $(CFILES))

# 指定所有的 .C 生成的 .o 文件名(包含将要存放的路径)
COBJS			:= $(patsubst %, $(OBJDIRS)/%, $(CFILENDIR:.c=.o))

# 将所有要生成的 .o 文件合并到一个变量中(都包含路径)
OBJS			:= $(COBJS)

# 设置源文件路径
VPATH			:= $(SRCDIRS)

#============================================================================#			
# 生成目标文件	   
$(TARGET): $(OBJS)
	$(CC) $(CFLAGS) $^ -o $(TARGET)

# 隐含规则推导相关中间文件
$(COBJS) : $(OBJDIRS)/%.o : %.c
	$(CC) $(CFLAGS) -c $(INCLUDE) $<  -o $@ 
	
#============================================================================#	
.PHONY: clean clean_o
# 删除所有编译链接生成的文件命令
clean: clean_o
	@rm -vf $(TARGET)

# 删除所有的 .o 文件命令
clean_o:
	@rm -vf $(COBJS)

printf:
	@echo "CFLAGS    = $(CFLAGS)"
	@echo "INCDIRS   = $(INCDIRS)"
	@echo "SRCDIRS   = $(SRCDIRS)"
	@echo "INCLUDE   = $(INCLUDE)"
	@echo "CFILES    = $(CFILES)"
	@echo "CFILENDIR = $(CFILENDIR)"
	@echo "COBJS     = $(COBJS)"
	@echo "OBJS      = $(OBJS)"
	@echo "VPATH     = $(VPATH)"