C和指针 第12章 使用结构和指针 12.3 双链表

12.3 双链表
    单链表的替代方案就是双链表。在一个双链表中，每个结点都包含两个指针---指向前一个节点的指针和指向后一个节点的指针。这可以使我们以任何方向遍历双链表，甚至可以随意在双链表中访问。
下面是节点类型的声明：
    typedef struct NODE {
        struct NODE *fwd;
        struct NODE *bwd;
        int         value; 
    } Node; 
    现在，存在两个根指针：一个指向链表的第一个节点，另一个指向后一个节点。这两个指针允许从链表的任何一端开始遍历链表。
    我们可能想把两个根指针分开声明为两个变量。但这样一来，我们必须把两个指针都传递给插入函数。为根指针声明一个完整的节点更为方便，只是它的值绝不会被使用。在我们的例子中，这个技巧只是浪费了一个整型值的内存空间。对于值非常大的链表，分开声明两个指针可能更好一些。另外，也可以在根节点的值字段中保存其他一些关于链表的信息，例如链表当前包含的节点数量。
    根节点的fwd字段指向链表的第1个节点，根节点的bwd字段指向链表的最后一个节点。如果链表为空，这两个字段都为NULL。链表第1个节点的bwd字段和最后1个节点的fwd字段都为NULL。在一个有序的链表中，各个节点将根据value字段的值以升序排列。
    12.3.1 在双链表中插入
    要编写一个函数，把一个值插入到一个有序的双链表中。dll_insert函数接受2个参数，一个指向根节点的指针和一个整型值。先前所编写的单链表输入函数把重复的值也添加到链表中。在有些应用中，不插入重复的值可能更为合适。dll_insert函数只有当待插入的值原先不存在于链表中是才将其插入。
    用一种更为规范的方法来编写这个函数。当把一个节点插入到一个链表时，可能出现4中情况：
    1.新值可能必须插入到链表的中间位置； 
    2.新值可能必须插入到链表的起始位置； 
    3.新值可能必须插入到链表的结束位置；
    4.新值可能必须既插入到链表的起始位置，又插入到链表的结束位置（即原链表为空）。
    在每种情况下，有4个指针必须进行修改。
    在情况1和情况2中，新节点的fwd字段必须设置为指向链表的下一个节点，链表下一个节点的bwd字段必须设置为指向这个新节点。
    在情况3和情况4中，新节点的fwd字段必须设置为NULL，根节点的bwd字段必须设置为指向新节点。
    在情况1和情况3中，新节点的bwd字段必须设置为指向链表的前一个节点，而链表前一个节点的fwd字段必须设置为指向新节点。
    在情况2和情况4中，新节点的bwd字段必须设置为NULL，根节点的fwd字段必须设置为指向新节点。
    程序12.4简明的实现方法可以帮助你加深理解。
    /*
    **把一个值插入到一个双链表，rootp是一个指向根节点的指针，
    **value是待插入的新值。
    **返回值：如果欲插值原先已存在于链表中，函数返回0
    **如果内存不足导致无法插入，函数返回-1；如果插入成功，函数返回1 
    */
    #include<stdlib.h>
    #include<stdio.h>
    #include"doubly_linked_list_node.h"
    
    int dll_insert( Node *rootp, int value ){
        Node *this;
        Node *next;
        Node *newnode;
        
        /*
        **查看value是否已经存在于链表中，如果是就返回。
        **否则，为新值创建一个新节点（"newnode"将指向它）
        **"this"将指向应该在新节点之前的那个节点
        **"next"将指向应该在新节点之后的那个节点
        */
        for( this = rootp; (next = this->fwd) != NULL; this = next ){
            if( next->value == value ){
                return 0;
            }
            if( next->value > value ){
                break;
            }
        }
        newnode = (Node *)malloc( sizeof(Node) );
        if( newnode == NULL ){
            return -1;
        }
        newnode->value = value;
        
        /*
        **把新值添加到链表中
        */
        if( next != NULL ){
            /*
            **情况1或2：并未位于链表尾部。 
            */
            if( this != rootp ){ /*情况1：并非位于链表起始位置*/
                newnode->fwd = next;
                this->fwd = newnode;
                newnode->bwd = this;
                next->bwd = newnode; 
            }else{     /*情况2：位于链表起始位置*/ 
                newnode->fwd = next;
                rootp->fwd = newnode;
                newnode->bwd = NULL;
                next->bwd = newnode;
            } 
        }else{
            /*
            **情况3或4：位于链表的尾部
            */
            if( this != rootp ){ /*情况3：并非位于链表的起始位置*/ 
                newnode->fwd = NULL;
                this->fwd = newnode;
                newnode->bwd = this;
                rootp->bwd = newnode;
            }else{
                newnode->fwd = NULL;
                rootp->fwd = newnode;
                newnode->bwd = NULL;
                rootp->bwd = newnode;
            } 
        } 
        return 1;
    }

程序12.4 简明的双链表插入函数    dll_ins1.c

/*
** doubly_linked_list_node.h
*/ 
#ifndef DOUBLY_LINKED_LIST_NODE_H
#define DOUBLY_LINKED_LIST_NODE_H 
typedef struct NODE {
    struct NODE *fwd;
    struct NODE *bwd;
    int         value; 
} Node; 

extern int dll_insert( Node *rootp, int value );

#endif

/*
**把一个值插入到一个双链表，rootp是一个指向根节点的指针，
**value是待插入的新值。
**返回值：如果欲插值原先已存在于链表中，函数返回0； 
**如果内存不足导致无法插入，函数返回-1；如果插入成功，函数返回1。 
**dll_insert.cpp
*/
#include<stdlib.h>
#include<stdio.h>
#include"doubly_linked_list_node.h"

int dll_insert( Node *rootp, int value ){
    Node *this2;
    Node *next;
    Node *newnode;
    
    /*
    **查看value是否已经存在于链表中，如果是就返回。
    **否则，为新值创建一个新节点（"newnode"将指向它）。 
    **"this2"将指向应该在新节点之前的那个节点， 
    **"next"将指向应该在新节点之后的那个节点。 
    */
    for( this2 = rootp; (next = this2->fwd) != NULL; this2 = next ){
        if( next->value == value ){
            return 0;
        }
        if( next->value > value ){
            break;
        }
    }
    newnode = (Node *)malloc( sizeof(Node) );
    if( newnode == NULL ){
        return -1;
    }
    newnode->value = value;
    
    /*
    **把新值添加到链表中。 
    */
    if( next != NULL ){
        /*
        **情况1或2：并未位于链表尾部。 
        */
        if( this2 != rootp ){ /*情况1：并非位于链表起始位置。*/
            newnode->fwd = next;
            this2->fwd = newnode;
            newnode->bwd = this2;
            next->bwd = newnode; 
        }else{     /*情况2：位于链表起始位置。*/ 
            newnode->fwd = next;
            rootp->fwd = newnode;
            newnode->bwd = NULL;
            next->bwd = newnode;
        } 
    }else{
        /*
        **情况3或4：位于链表的尾部。 
        */
        if( this2 != rootp ){ /*情况3：并非位于链表的起始位置。*/ 
            newnode->fwd = NULL;
            this2->fwd = newnode;
            newnode->bwd = this2;
            rootp->bwd = newnode;
        }else{                /*情况3：位于链表的起始位置。*/
            newnode->fwd = NULL;
            rootp->fwd = newnode;
            newnode->bwd = NULL;
            rootp->bwd = newnode;
        } 
    } 
    return 1;
}

/*
**main.cpp。 latter four insertion files use the same main.cpp file, so all omit latter main.cpp.
*/
#include <stdio.h>
#include <stdlib.h>
#include "doubly_linked_list_node.h"
 
int main( void ){
    Node *root;
    Node *pt;
    Node *node, *node2, *node3;
    int result;
    
    node = (Node *)malloc( sizeof(Node) );
    node2 = (Node *)malloc( sizeof(Node) );
    node3 = (Node *)malloc( sizeof(Node) );
    if( node && node2 && node3 ){
        root = node;
        node->value = 5;
        node->fwd = node2;
        node->bwd = NULL;
        node2->value = 10;
        node2->fwd = node3;
        node2->bwd = node;
        node3->value = 15;
        node3->fwd = NULL;
        node3->bwd = node2;
    }
    printf( "print original elements in linked list from left to right:\n" );
    pt = root;
    while( pt ){
        printf( "%d ", pt->value );
        pt = pt->fwd;
    }
    printf( "\n" );
    printf( "print original elements in linked list from right to left:\n" );
    pt = node3;
    while( pt ){
        printf( "%d ", pt->value );
        pt = pt->bwd;
    }
    printf( "\n" );
    /*
    ** the second version of insert.
    ** right version.
    */
    result = dll_insert( root, 12 );
    printf( "after result = dll_insert( root, 12 ), result = %d\n", result );
    printf( "print elements in linked list:\n" );
    pt = root;
    while( pt ){
        printf( "%d ", pt->value );
        pt = pt->fwd;
    }
    printf( "\n" );
    result = dll_insert( root, 20 );
    printf( "after result = dll_insert( root, 20 ), result = %d\n", result );
    printf( "print elements in linked list:\n" );
    pt = root;
    while( pt ){
        printf( "%d ", pt->value );
        pt = pt->fwd;
    }
    printf( "\n" );
    result = dll_insert( root, 4 );
    printf( "after result = dll_insert( root, 4 ), result = %d\n", result );
    printf( "print elements in linked list:\n" );
    pt = root;
    while( pt ){
        printf( "%d ", pt->value );
        pt = pt->fwd;
    }
    printf( "\n" );
    
    return EXIT_SUCCESS;
}
/* 输出：

*/ 

    一开始，函数使this指向根节点。next指针始终指向this之后的那个节点。它的思路是这两个指针同步前进，直到新节点应该插入到这两者之间。for循环检查next所指节点的值，判断是否达到需要插入的位置。
    如果在链表中找到新值，函数就简单地返回；否则，当到达链表尾部或找到适当的插入位置时循环终止。在任何一种情况下，新节点都应该插入到this所指的节点后面。注意，在决定新值是否应该插入到链表之前，并不为它分配内存。如果实现分配内存，但发现新值原先已经存在于链表中，就有可能发生内存泄漏。
    4种情况是分开实现的。让我们通过把12插入到链表中来观察情况1。
    然后，函数为新节点分配内存。
    newnode->fwd = next;
    this->fwd = newnode;
    然后，执行下列语句：
    newnode->bwd = this;
    next->bwd = newnode;
    这就完成了把新值插入到链表的过程。
    请研究一下代码，确定应该如何处理剩余的几种情况，确保它们都能正确工作。
    简化插入函数
    提示：
    细心的程序员会发现，在函数中各个嵌套的if语句群存在大量的相似之处，而优秀的程序员会对程序员出现这么多的重复代码感到厌烦。所以，我们现在将使用两个技巧消除这些重复的代码。第1个技巧是语句提炼（statement factoring），如下面的例子所示：
    if( x == 3 ){
        i = 1;
        something;
        j = 2;
    }else{
        i = 1;
        something different;
        j = 2;
    }
    注意，不管表达式x==3的值是真还是假，语句i=1和j=2都将执行。在if之前执行i=1不会影响x==3的测试结果，所以这两条语句都可以被提炼出来，这样就产生了更为简单但同样完整的语句：
    i = 1;
    if( x == 3 ){
        something;
    } else{
        something different;
    }
    j = 2;
    警告：
    如果if之前的语句会对测试的结果产生影响，则千万不要把它提炼出来。例如，在下面的例子中：
    if( x == 3 ){
        x = 0;
        something;
    } else{
        x = 0;
        something different;
    }
    语句x=0不能被提炼出来，因为它会影响比较的结果。
    把程序12.4最内层嵌套的if语句进行提炼，就产生了程序12.5的代码段。请将这段代码和前面的函数进行比较，确认它们是等价的。 
    /*
    **把新值添加到链表中。 
    */
    if( next != NULL ){
        /*
        **情况1或2：并未位于链表尾部。 
        */
        newnode->fwd = next;
        if( this != rootp ){ /*情况1：并非位于链表起始位置*/
            this->fwd = newnode;
            newnode->bwd = this;    
        }else{     /*情况2：位于链表起始位置*/ 
            rootp->fwd = newnode;
            newnode->bwd = NULL;
        } 
        next->bwd = newnode; 
    }else{
        /*
        **情况3或4：位于链表的尾部
        */
        newnode->fwd = NULL;
        if( this != rootp ){ /*情况3：并非位于链表的起始位置*/     
            this->fwd = newnode;
            newnode->bwd = this;
        }else{   /*情况4：位于链表起始位置*/ 
            rootp->fwd = newnode;
            newnode->bwd = NULL;
        } 
        rootp->bwd = newnode;
    } 
程序12.5 双链表插入逻辑的提炼    dll_ins2.c

/*
**把一个值插入到一个双链表，rootp是一个指向根节点的指针，
**value是待插入的新值。
**返回值：如果欲插值原先已存在于链表中，函数返回0； 
**如果内存不足导致无法插入，函数返回-1；如果插入成功，函数返回1。 
**dll_insert_2.cpp
*/
#include<stdlib.h>
#include<stdio.h>
#include"doubly_linked_list_node.h"

int dll_insert( Node *rootp, int value ){
    Node *this2;
    Node *next;
    Node *newnode;
    
    /*
    **查看value是否已经存在于链表中，如果是就返回。
    **否则，为新值创建一个新节点（"newnode"将指向它）。 
    **"this2"将指向应该在新节点之前的那个节点， 
    **"next"将指向应该在新节点之后的那个节点。 
    */
    for( this2 = rootp; (next = this2->fwd) != NULL; this2 = next ){
        if( next->value == value ){
            return 0;
        }
        if( next->value > value ){
            break;
        }
    }
    newnode = (Node *)malloc( sizeof(Node) );
    if( newnode == NULL ){
        return -1;
    }
    newnode->value = value;
    
    /*
    **把新值添加到链表中。 
    */
    if( next != NULL ){
        /*
        **情况1或2：并未位于链表尾部。 
        */
        newnode->fwd = next;
        if( this2 != rootp ){ /*情况1：并非位于链表起始位置*/
            this2->fwd = newnode;
            newnode->bwd = this2;    
        }else{     /*情况2：位于链表起始位置*/ 
            rootp->fwd = newnode;
            newnode->bwd = NULL;
        } 
        next->bwd = newnode; 
    }else{
        /*
        **情况3或4：位于链表的尾部
        */
        newnode->fwd = NULL;
        if( this2 != rootp ){ /*情况3：并非位于链表的起始位置*/     
            this2->fwd = newnode;
            newnode->bwd = this2;
        }else{   /*情况4：位于链表起始位置*/ 
            rootp->fwd = newnode;
            newnode->bwd = NULL;
        } 
        rootp->bwd = newnode;
    } 
    return 1;
}

/* 输出：

*/

    第二个简化技巧很容易用下面这个例子进行说明：
    if( pointer != NULL ){
        field = pointer;
    } else{
        field = NULL;
    }
    这段代码的意图是设置一个和pointer相等的变量，如果pointer未指向任何内容，这个变量就设置为NULL。但是，请看下面这条语句：
    field = pointer; 
    如果pointer的值不是NULL，field就像前面一样获得它的值的一份副本。但是，如果pointer的值是NULL，那么field将获得一份NULL的副本，这和把它赋值为常量NULL的效果是一样的。这条语句所指向的任何和前面那条语句相同，但它明显简单多了。
    在程序12.5中运用这个技巧的关键是找出那些虽然看上去不一样但实际上执行相同任务的语句，然后对它们进行改写，写成同一种形式。我们可以把情况3和情况4的第一条语句改写为：
    newnode->fwd = next;
    由于if语句刚刚判断出next==NULL，这个改动使if语句两边的第一条语句相等，因此可以把它提炼出来。请做好这个修改，然后对剩余的代码进行研究。
    现在两个嵌套的if语句是相等的，所以它们也可以被提炼出来。这些改动的结果显示在程序12.6中。
    我们还可以对代码作进一步的完善。第一条if语句的else子句的第一条语句可以改写为：
    this->fwd = newnode;
    这是因为if语句已经判断出this==rootp。现在，这条改写后的语句以及它的同类也可以被提炼出来。
    程序12.7是实现了所有修改版本的完整版本。它所执行的任务和最初的函数相同，但体积要小得多。局部指针被声明为寄存器变量，进一步改善了代码的体积和执行速度。
    /*
    **把新值添加到链表中。 
    */
    newnode->fwd = next;
    if( this != rootp ){
        this->fwd = newnode;
        newnode->bwd = this;
    } else{
        rootp->fwd = newnode;
        newnode->bwd = NULL;    
    }
    if( next != NULL ){
        next->bwd = newnode;
    } else{
        rootp->bwd = newnode;
    }
程序12.6 双链表插入逻辑的进一步提炼    dll_ins3.c

/*
**把一个值插入到一个双链表，rootp是一个指向根节点的指针，
**value是待插入的新值。
**返回值：如果欲插值原先已存在于链表中，函数返回0； 
**如果内存不足导致无法插入，函数返回-1；如果插入成功，函数返回1。 
**dll_insert_3.cpp
*/
#include<stdlib.h>
#include<stdio.h>
#include"doubly_linked_list_node.h"

int dll_insert( Node *rootp, int value ){
    Node *this2;
    Node *next;
    Node *newnode;
    
    /*
    **查看value是否已经存在于链表中，如果是就返回。
    **否则，为新值创建一个新节点（"newnode"将指向它）。 
    **"this2"将指向应该在新节点之前的那个节点， 
    **"next"将指向应该在新节点之后的那个节点。 
    */
    for( this2 = rootp; (next = this2->fwd) != NULL; this2 = next ){
        if( next->value == value ){
            return 0;
        }
        if( next->value > value ){
            break;
        }
    }
    newnode = (Node *)malloc( sizeof(Node) );
    if( newnode == NULL ){
        return -1;
    }
    newnode->value = value;
    
    /*
    **把新值添加到链表中。 
    */
    newnode->fwd = next;
    if( this2 != rootp ){
        this2->fwd = newnode;
        newnode->bwd = this2;
    } else{
        rootp->fwd = newnode;
        newnode->bwd = NULL;    
    }
    if( next != NULL ){
        next->bwd = newnode;
    } else{
        rootp->bwd = newnode;
    }
    return 1;
}

 /* 输出：

 */

   /*
    **把一个值插入到一个双链表，rootp是一个指向根节点的指针，
    **value是待插入的新值。
    **返回值：如果欲插值原先已存在于链表中，函数返回0； 
    **如果内存不足导致无法插入，函数返回-1；如果插入成功，函数返回1。 
    */
    #include<stdlib.h>
    #include<stdio.h>
    #include"doubly_linked_list_node.h"
    
    int dll_insert( Node *rootp, int value ){
        Node *this;
        Node *next;
        Node *newnode;
        /*
        **查看value是否已经存在于链表中，如果是就返回。
        **否则，为新值创建一个新节点（"newnode"将指向它）
        **"this"将指向应该在新节点之前的那个节点， 
        **"next"将指向应该在新节点之后的那个节点。 
        */
        for( this = rootp; (next = this->fwd) != NULL; this = next ){
            if( next->value == value ){
                return 0;
            }
            if( next->value > value ){
                break;
            }
        }
        newnode = (Node *)malloc( sizeof(Node) );
        if( newnode == NULL ){
            return -1;
        }
        newnode->value = value;
        
        /*
        **把新值添加到链表中。 
        */
        newnode->fwd = next;
        this->fwd = newnode; 
        if( this != rootp ){
            newnode->bwd = this;
        } else{
            newnode->bwd = NULL;    
        }
        if( next != NULL ){
            next->bwd = newnode;
        } else{
            rootp->bwd = newnode;
        }
        return 1;
    } 
程序12.7 双链表插入函数的最终简化版本    dll_ins4.c

/*
**把一个值插入到一个双链表，rootp是一个指向根节点的指针，
**value是待插入的新值。
**返回值：如果欲插值原先已存在于链表中，函数返回0； 
**如果内存不足导致无法插入，函数返回-1；如果插入成功，函数返回1。 
**dll_insert_4.cpp 
*/
#include<stdlib.h>
#include<stdio.h>
#include"doubly_linked_list_node.h"

int dll_insert( Node *rootp, int value ){
    Node *this2;
    Node *next;
    Node *newnode;
    
    /*
    **查看value是否已经存在于链表中，如果是就返回。
    **否则，为新值创建一个新节点（"newnode"将指向它）
    **"this"将指向应该在新节点之前的那个节点， 
    **"next"将指向应该在新节点之后的那个节点。 
    */
    for( this2 = rootp; (next = this2->fwd) != NULL; this2 = next ){
        if( next->value == value ){
            return 0;
        }
        if( next->value > value ){
            break;
        }
    }
    newnode = (Node *)malloc( sizeof(Node) );
    if( newnode == NULL ){
        return -1;
    }
    newnode->value = value;
    
    /*
    **把新值添加到链表中。 
    */
    newnode->fwd = next;
    this2->fwd = newnode; 
    if( this2 != rootp ){
        newnode->bwd = this2;
    } else{
        newnode->bwd = NULL;    
    }
    if( next != NULL ){
        next->bwd = newnode;
    } else{
        rootp->bwd = newnode;
    }
    return 1;
} 

/* 输出：

*/ 

    这个函数无法再大幅度改善了，但我们可以让源代码更小一些。第一条if语句的目的是判断赋值语句右边一侧的值。我们可以用一个条件表达式来取代if语句。我们也可以用条件表达式取代第二条if语句，但这个修改的意义并不是很大。
    提示：
    程序12.8的代码确实更小一些，但它是不是真的更好？尽管它的语句数量减少了，但必须执行的比较和赋值操作还是和前面一样多，
所以这段代码的运行速度并不比前面的更快。这里存在两个微小的差别：newnode->bwd和->bwd = newnode都只编写了一次而不是两次。这些差别能不能产生更小的目标代码呢？也许会，这取决于你的编译器优化措施是否出色。但是，即使会产生更小的代码，其差别也是很小的，但这段代码的可读性较之前面的代码有所下降，尤其是对于那些缺乏经验的C程序员而言。因此，程序12.8维护起来或许更困难一些。
    如果程序的大小或者执行速度确实至关重要，我们可能只好考虑用汇编语言来编写函数。但即便编码方式上采取如此巨大的变化，也不能保证肯定会有任何重大的改进。另外还要考虑到汇编代码难于编写、难于阅读和难于维护。所以，只有迫不得已的时候，才能求诸于汇编语言。
    /*
    **把新节点添加到链表中。 
    */ 
    newnode->fwd = next;
    this->fwd = newnode;
    newnode->bwd = this != rootp ? this : NULL;
    (next != NULL ? next : rootp)->bwd = newnode;
程序12.8 使用条件表达式实现插入函数    dll_ins5.c

/*
**把一个值插入到一个双链表，rootp是一个指向根节点的指针，
**value是待插入的新值。
**返回值：如果欲插值原先已存在于链表中，函数返回0； 
**如果内存不足导致无法插入，函数返回-1；如果插入成功，函数返回1。 
**dll_insert_4.cpp 
*/
#include<stdlib.h>
#include<stdio.h>
#include"doubly_linked_list_node.h"

int dll_insert( Node *rootp, int value ){
    Node *this2;
    Node *next;
    Node *newnode;
    
    /*
    **查看value是否已经存在于链表中，如果是就返回。
    **否则，为新值创建一个新节点（"newnode"将指向它）
    **"this"将指向应该在新节点之前的那个节点， 
    **"next"将指向应该在新节点之后的那个节点。 
    */
    for( this2 = rootp; (next = this2->fwd) != NULL; this2 = next ){
        if( next->value == value ){
            return 0;
        }
        if( next->value > value ){
            break;
        }
    }
    newnode = (Node *)malloc( sizeof(Node) );
    if( newnode == NULL ){
        return -1;
    }
    newnode->value = value;
    
    /*
    **把新节点添加到链表中。 
    */ 
    newnode->fwd = next;
    this2->fwd = newnode;
    newnode->bwd = this2 != rootp ? this2 : NULL;
    (next != NULL ? next : rootp)->bwd = newnode;
    
    return 1;
} 

/* 输出：

*/