双向链表操作

/*******************************双链表**************************/

#include<stdio.h>

#include<stdlib.h>

#include<assert.h>



#define  FALSE    0

#define  TRUE     1

// 双链表声明

typedef struct NODE

{

   struct  NODE  *fwd;

   struct  NODE  *bwd;

   int     value;

}Node;



// 双链表的创建，返回头指针

Node *CreatList(int n)

{

    Node *head,*pNode,*sNode;

    int i;

    head=(Node *)malloc(sizeof(Node));

        head->bwd=NULL;

        head->fwd=NULL;

    pNode=head;

    for(i=1;i<=n;i++)

    {

        sNode=(Node *)malloc(sizeof(Node));

                sNode->value=i;

                sNode->bwd = NULL;

                sNode->fwd = NULL;



                pNode->fwd=sNode;

                sNode->bwd=pNode;

        pNode=sNode;

    }

    return(head);

}



// 打印双链表数据(传递双向链表头head）

void print_link(Node *head)

{

        Node *pNode=head->fwd;

    while(pNode!=NULL)

    {

                printf("%d\n",pNode->value);

                pNode=pNode->fwd;

    } 

}



/*双链表的插入

** 把一个值插入到双链表，rootp是一个指向根节点的指针

** value 是欲插入的新值

** 返回值：如果欲插入的值已存在链表中，函数返回0；

** 如果内存不足导致无法插入，函数返回-1;,如果插入成功，函数返回1;

*/



int dll_insert(Node *rootp,int value)

{

    Node *thist;

        Node *next;

        Node *newnode;

        /*查看value是否存在链表中，有就返回，

        ** 否则为新值创建一个新的节点

        **  thist 指向新节点之前那个节点

        **  next  指向新节点之后那个节点

        */

        for(thist = rootp;(next = thist->fwd) != NULL;thist = 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(thist!=rootp)         //情况1：并非位于链表的起始位置

                   {

                           newnode->fwd = next;

                           thist->fwd = newnode;

                           newnode->bwd = thist;

                           next->bwd = newnode;

                   }

                   else                     //情况2：位于链表的起始位置

                   {

                           newnode->fwd = next;

                           rootp->fwd = newnode;

                           newnode->bwd = NULL;

                           next->bwd = newnode;

                   }

        }

        else    //情况3或者4：位于链表尾部

        {

             if(thist != rootp)   //情况3：并非位于链表的起始位置

                 {

                         newnode->fwd = NULL;

                         thist->fwd = newnode;

                         newnode->bwd = thist;

                         rootp->bwd = newnode;

                 }

                 else                 //情况4：位于链表的起始位置

                 {

                         newnode->fwd = NULL;

                         rootp->fwd = newnode;

                         newnode->bwd = NULL;

                         rootp->bwd = newnode;

                 }

        }

*/



/*

**简化版，对比上面可读性不强，运行速度并不比前面的快。

*/

         newnode->fwd = next;

     thist->fwd = newnode;

        if(thist!=rootp)         

            newnode->bwd = thist;

        else                     

                newnode->bwd = NULL;        

        if(next != NULL)    

            next->bwd = newnode;

        else   

            rootp->bwd = newnode;



  return 1;  

}



/*双链表的删除

** 把一个值插入到双链表，rootp是一个指向根节点的指针

** del 是指向欲移除节点的指针

** 返回值：

** 如果链表不包含移除的节点，函数就返回假，否则返回真。

*/

int dll_remove(Node *rootp, Node *del)

{

    register  Node  *thist;

        assert( del != NULL);

        for(thist=rootp->fwd; thist != NULL; thist = thist->fwd)

            if(thist == del)

                      break;

        if(thist == del)

        { 

                /*

        ** Update fwd pointer of the previous node.

        */

        if( thist->bwd == NULL )

                        rootp->fwd = thist->fwd;

        else

           thist->bwd->fwd = thist->fwd;

         /*

         ** Update bwd pointer of the next node.

         */

        if( thist->fwd == NULL )

            rootp->bwd = thist->bwd;

       else

           thist->fwd->bwd = thist->bwd;

        free( thist );

        return TRUE;

        }

        else

                return FALSE;

        

}