C语言单链表插入

C:

定义一个节点

typedef struct NODE { struct NODE *link; int value; }Node;

向有序链表中插入节点：

/************************************ ** 1、找到应该插入新节点的位置 ** ** 2、为新节点分配内存（创建新节点）** ** 3、把链表连起来 ** *************************************/ #include <stdlib.h> #include <stdio.h> #include "sll_node.h" #define FALSE 0 #define TRUE 1 int sll_insert( Node *current, int new_value) /*第一个参数是指向链表头节点的指针，第二个是要插 入的值*/ { Node *previous; Node *new; /*************************************************************** **寻找正确的插入位置，方法是按顺序访问链表，直到到达其值大于或等去** **新插入值的节点。 ** ***************************************************************/ while(current->value < new_value) { previous = current; /*current节点变成previous节点*/ current = current->link; /*current->link指向的节点变成current节点 */ } /*********************************************************** **为新节点分配内存，并把新值存储到新节点中，如果内存分配失败 ** **则函数返回FALSE ** ***********************************************************/ new = (Node*)malloc(sizeof(Node)); if(new == NULL) return FALSE; new->value = new_value; /* **把新节点插入到链表中，并返回TRUE */ new->llink = current; previous->link = new; return TRUE; }

此函数有两个问题：

1、当向链表尾部插入节点，即插入值大于链表中所有节点的值，current指针最后是NULL，但函数会尝试访问current->valuel；

2、当向链表头部插入节点（即插入值小于所有节点值），需要修改头指针，但函数不能访问头指针；

所以在函数中加入特殊情况的处理：

/************************************ ** 1、找到应该插入新节点的位置 ** ** 2、为新节点分配内存（创建新节点）** ** 3、把链表连起来 ** *************************************/ #include <stdlib.h> #include <stdio.h> #include "sll_node.h" #define FALSE 0 #define TRUE 1 int sll_insert( Node **rootp, int new_value) /*第一个参数是指向链表头节点的指针的指针，第二个是要插 入的值*/ { Node *current; Node *previous; Node *new; /* **得到指向第一个节点的指针； */ current = *rootp; previous = NULL; /*************************************************************** **寻找正确的插入位置，方法是按顺序访问链表，直到到达其值大于或等去** **新插入值的节点。 ** ***************************************************************/ while(current != NULL && current->value < new_value) { previous = current; /*current节点变成previous节点*/ current = current->link; /*current->link指向的节点变成current节点 */ } /*********************************************************** **为新节点分配内存，并把新值存储到新节点中，如果内存分配失败 ** **则函数返回FALSE ** ***********************************************************/ new = (Node*)malloc(sizeof(Node)); if(new == NULL) return FALSE; new->value = new_value; /* **把新节点插入到链表中，并返回TRUE */ new->link = current; if(previous == NULL) *rootp = new; else previous->link = new; return TRUE; }

这个程序可以覆盖所有情况，但需要对特殊情况进行判断和处理，考虑rootp和current->link，都是指向节点的指针，将程序优化：

#include <stdlib.h> #include <stdio.h> #include "sll_node.h" #define FALES 0 #define TRUE 1 int sll_insert(register Node **linkp, int new_value) { register Node *current; register Node *new; /*************************************************************** **寻找正确的插入位置，方法是按顺序访问链表，直到到达其值大于或等去** **新插入值的节点。 ** ***************************************************************/ while((current = *linkp) != NULL && current->value < new_value){ linkp = &current->link; } /*********************************************************** **为新节点分配内存，并把新值存储到新节点中，如果内存分配失败 ** **则函数返回FALSE ** ***********************************************************/ new = (Node*)malloc(sizeof(Node)); if(new == NULL) return FALSE; new->value = new_value; /* **把新节点插入到链表中，并返回TRUE */ new->link = current; *linkp = new; return TRUE; }

头指针和current->link都是指向节点的指针，所以传入参数由头指针变为指向头指针的指针，在程序中对指向节点的指针的指针进行操作