C语言单链表插入
程序员文章站
2024-02-29 11:57:22
...
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 = ¤t->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都是指向节点的指针,所以传入参数由头指针变为指向头指针的指针,在程序中对指向节点的指针的指针进行操作