关于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指针,或者第一个结点的指针。 如果不能很好理解这种思路,还是按照自己最熟练,最不容易出错的方式实现吧!! |
|
来自: happy123god > 《读书笔记及小结》