分享

(原创)C语言单链表插入(分享)

 happy123god 2012-03-31
关于C语言单链表插入的程序,想必大家再熟悉不过了,所涉及的逻辑非常简单,
但是要将这个程序完整无误的写好,可不是那么容易。

因为涉及到:
1. 循环结束的判断:
    A。 找到了比插入结点数值大的结点,说明要插入的位置找到了,就在这个数值更大的结点之前
    B。 当前链表中没有比这个结点数值更大的,那么我们要将待插入结点放到链表结尾。
          之时,我们循环结束的条件就是当前遍历链表的指针是否为NULL。
    C。如果待插入结点数值比所有结点数值都小(我们判断时只需要判断比第一个结点小),
          我们需要将此结点插入到链表头,并且修改链表头指针。
 
对于A,是大多数情况,也就是我们程序的基本流程,而对于B,C,我们可以视为特殊情况,在
处理时单独处理。事实上,如果我们使用“头结点”的方式,可以不必特殊处理C。此时,头结点
只是一个空结点,里面的link指针,指向我们真正要使用的结点所在链表的第一个结点。那么,
即使出现情况C,我们只需要将新插入结点的next指针指向第一个结点,即头结点所指向的结点,
而将head->next指向新插入的结点,如果开始扫描前,用prev指向头结点,pcur指向当前扫描结点,
pnew_node ->link = pcur;
prev->link = pnew_node ;
就可以对A,C统一处理了。

当然,我这里想要介绍的可不是这样的方法。在《pointer on C》这本书里面,讲述了另外一个巧妙
的理解。此理解基于"当移动到下一个结点时,我们保存一个指向下一个结点的next指针“,而不是保存
指向前一个结点的指针,也就是不再需要prev指针。除了第一个结点,其他位置的插入,实际修改的是
前一个结点的link 字段。

我们”聚焦“ link字段,而非结点指针。

示例程序如下:
#if 1

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

#define  INSERT_OK   0
#define  INSERT_ERR  -1

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


int list_insert( Node **linkp, int node_val)
{
Node *pcur;
Node *pnew_node;
/*
寻找正确的插入位置,方法是按序访问链表,直到
找到一个其值大于或等于新值的节点 
*/ 
while((pcur = *linkp) != NULL && 
     pcur->value < node_val)
{
   linkp = &pcur->link;
}
pnew_node = (Node *)malloc(sizeof(Node));
if(pnew_node == NULL)
{
   return INSERT_ERR;
}
pnew_node->value = node_val;
pnew_node->link = pcur;
*linkp = pnew_node;
return INSERT_OK;
}

void print_link_list(Node *proot)
{
    Node *p = proot;
    printf(" data in link list are : \n");
    while(p != NULL)
    {
        printf(" Node_val = %d \n", p->value);
        p = p->link;
    } 

}

int main()
{
    Node *phead = NULL;
    int  i4_ret  = 0;
    
    i4_ret = list_insert(&phead,5);
    if(i4_ret < 0)
    {
        printf("list insert fail : node_val = 5 \n");
    }
    i4_ret = list_insert(&phead,10);
    if(i4_ret < 0)
    {
        printf("list insert fail : node_val = 10 \n");
    }
    i4_ret = list_insert(&phead,15);
    if(i4_ret < 0)
    {
        printf("list insert fail : node_val = 15 \n");
    }
    print_link_list(phead);
    printf(" Test Insert_list function with  3,12,20 \n");
    printf(" Now try to insert  3  : \n");
    i4_ret = list_insert(&phead,3);
    if(i4_ret < 0)
    {
        printf("list insert fail : node_val = 3 \n");
    }
    printf(" Now try to insert 12  : \n");
    i4_ret = list_insert(&phead,12);
    if(i4_ret < 0)
    {
        printf("list insert fail : node_val = 12 \n");
    }
    printf(" Now try to insert 20  : \n");
    i4_ret = list_insert(&phead,20);
    if(i4_ret < 0)
    {
        printf("list insert fail : node_val = 20 \n");
    }
    print_link_list(phead);
    system("PAUSE");
    
    return 0;
}

#endif 


传参时,linkp被赋值为&phead,也就是说我们可以在函数里面修改phead (传递的是地址),
如果插入位置为第一个结点之前,那么寻找插入位置的循环将直接退出,此时pcur == *linkp,
于是pnew_node应该指向pcur,并且*linkp应该指向待插入结点;
如果插入位置为其他位置,那么通过循环查找,linkp将指向一个指向pcur所指向结点的下一个
结点的指针。找到插入位置时,pcur将指向待插入结点的下一个结点,而前一个结点里面的
link成员将由linkp所指向。

于是,pnew_node->link = pcur; 而前面一个结点的link指针有linkp所指向,于是,
表达式pnew_node->link = pcur; 和 *linkp = pnew_node; 能兼顾情况 A和 C 了。

p->link实际所指向的是下一个结点,那么pcur = pcur->link这个语句,就可以通过使用
pcur = *linkp 来消除,因为后者已经是pcur->link所指向的结点了。

不得不提出的是,*linkp与linkp的使用,不得有误。因为如果linkp还指向第一个结点,而
对*linkp进行赋值的话,就会修改这个结点了,请确保你的赋值是正确的。

本例中linkp是指向待插入结点的link指针,或者第一个结点的指针。


如果不能很好理解这种思路,还是按照自己最熟练,最不容易出错的方式实现吧!!





     

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多