在学习链表的时候我们都接触过单链表插入新结点的问题。其中有一类就是在顺序链表中插入新节点,并保持链表的递增或者递减性质。
最近看《C和指针》一书中提到了一种方法,我个人感觉不错,并且思想非常好。
这是最常见的思维:
1 2 3 4 5 6 7
| 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 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 int insertNode2(Node **nextp, int newValue) { Node *newNode; Node *current; current = *nextp; while (current != NULL && current->value < newValue) { nextp = ¤t->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); insertNode2(&head,temp); } Node *p = head->next; while (p != NULL) { printf("%d\n", p->value); p = p->next; } getchar(); getchar(); return 0; }
|
因为我个人没有经过正经的课堂训练,自己考研才接触编程、数据结构之类的。看了很多对自学编程提的建议都是多编写,并且要有抽象的思想,所以将这个方法写了下来,可能对很对科班出身的人不算什么问题了吧。
我感觉这个抽象很好,希望是给自己编程道路的一个好的开端吧:)
同时,因为我在初学时发现测试代码也会花费很多时间,所以将完成的代码都贴了上来,而不仅仅是函数,希望也能帮助到更多的想我这样的初学者吧。