在学习链表的时候我们都接触过单链表插入新结点的问题。其中有一类就是在顺序链表中插入新节点,并保持链表的递增或者递减性质。

最近看《C和指针》一书中提到了一种方法,我个人感觉不错,并且思想非常好。

这是最常见的思维:

1
2
3
4
5
6
7
//sll_node.h
typedef struct Node
{
int value;
Node *next;
} Node;
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
#include "sll_node.h"
#include <stdio.h>
#define TRUE 1
#define FALSE 0
// insertNode:把newValue的值插入到递增排序的链表中,正确返回TRUE,错误返回FALSE
// rootp是链表的头指针。
int insertNode(Node **rootp, int newValue)
{
Node *newNode; // 新节点的指针
Node *previous; // 当前指针的前一个指针
Node *current; // 当前指针
current = *rootp; // 初始化
previous = NULL;
// 查找插入的位置
while (current != NULL && current->value < newValue)
{
previous = current;
current = current->next;
}
// 给新节点分配空间
newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL)
return FALSE;
newNode->value = newValue;
// 更改新节点的前驱和后继节点
newNode->next = current;
if (previous == NULL) // 此时插入节点的为链表中第一个节点,修改头指针
*rootp = newNode;
else
previous->next = newNode;
return TRUE;
}

我以前编写的时候也会用这样的方法:一个当前指针和指向当前指针之前的指针,这样需要讨论原链表是否为空。书中提到了一种抽象,每次插入新的节点,都是改变一个指向这个新节点的指针以及指向下一个节点,这样可以省略讨论插入的节点是否为第一个节点的步骤。代码如下:

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
#include "sll_node.h"
#include <stdio.h>
#define FALSE 0
#define TRUE 1
// insertNode2:把newValue的值插入到递增排序的链表中,正确返回TRUE,错误返回FALSE
// nextp是指向当前节点的指针,最初是头指针
int insertNode2(Node **nextp, int newValue)
{
Node *newNode; // 新节点指针
Node *current; // 当前节点指针
current = *nextp; // 最初当前节点为nextp指针指向的节点
// 查找新插入节点的位置
while (current != NULL && current->value < newValue)
{
nextp = &current->next;
current = current->next;
}
// 为新节点分配内存
newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL)
return FALSE;
newNode->value = newValue;
// 统一了插入的步骤。即:每次插入,都是前一个指针指向新节点,新节点指向下一个节点
*nextp = newNode;
newNode->next = current;
return TRUE;
}

main函数

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sll_node.h"
int insertNode(Node **rootp, int newValue);
int insertNode2(Node **nextp, int newValue);
int main()
{
srand(time(0));
Node *head = (Node *)malloc(sizeof(Node));
head->next = NULL;
for (int i = 0; i < 5; i++)
{
int temp = rand() % 50;
printf("%d\n", temp);
//insertNode(&head,temp);
insertNode2(&head,temp);
}
Node *p = head->next;
while (p != NULL)
{
printf("%d\n", p->value);
p = p->next;
}
getchar();
getchar();
return 0;
}

因为我个人没有经过正经的课堂训练,自己考研才接触编程、数据结构之类的。看了很多对自学编程提的建议都是多编写,并且要有抽象的思想,所以将这个方法写了下来,可能对很对科班出身的人不算什么问题了吧。

我感觉这个抽象很好,希望是给自己编程道路的一个好的开端吧:)

同时,因为我在初学时发现测试代码也会花费很多时间,所以将完成的代码都贴了上来,而不仅仅是函数,希望也能帮助到更多的想我这样的初学者吧。