这是当时写的第一版本，插入函数修改指针部分，可以很大程度的精简，但是现在这样也有好处，易读。

顺带说一个笑话：刚写这代码的时候，我给两个指针命名为left,rigth。然后left实际指向的是右边，而right实际指向的是左边。
当然郁闷了半天，结果一看，我他娘的画的图上面的指针就画反了。

#include <stdio.h>
#include "Doubly_Linked_List.c"//这是为了测试偷懒，实际写代码别这么干

int main( void )
{
    Node *RootP;
    Node root;
    int value;

    root.Lprev = NULL;
    root.Lnext = NULL;
    root.Value = 0;
    RootP = &root;

    while( 1 == scanf("%d",&value) )
        if ( InsertList( RootP, value ) )
            root.Value++;

    PrintList( RootP );
    printf("%d\n",root.Value);
    getchar();

    while( 1 == scanf("%d",&value) )
        if( Delete( RootP, value) )
            root.Value--;
    printf("\n");
    PrintList( RootP );
    printf("\n%d\n",root.Value);
    DelList( RootP );
    printf("\n");

    PrintList( RootP );
    printf("\n%d\n",root.Value);

    return 0;
}

typedef struct NODE {
    int Value;
    struct NODE *Lprev;
    struct NODE *Lnext;
}Node;
enum{ False = 0, True };
int InsertList( Node *RootP, int value );//将元素插入有序的双链表，成功返回1，否则返回0
                                         //不会插入重复的元素
void PrintList( Node *RootP );//打印双链表中的元素
int Delete( Node *RootP, int value );//删除双链表中的一个元素，成功返回1，否则返回0
void DelList( Node *RootP);//删除双链表
/*

 * 未实现查找

 */

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

int InsertList( Node *RootP, int value )
{
    Node *This;
    Node *Next;
    Node *NewCell;

    for( This = RootP; NULL != ( Next = This->Lprev ); This = Next )
    {
        if( value == Next->Value )
            return False;
        if( value < Next->Value )
            break;
    }
    
    NewCell = ( Node * )malloc( sizeof( Node ) );
    if( NULL == NewCell )
        return False;
    NewCell->Value = value;

    if( NULL != Next )//如果Next不为NULL，则表示不在链表尾部
    {
        if( This != RootP )//如果This 不等于RootP，则表示不在链表头部
        {
            This->Lprev = NewCell;
            Next->Lnext = NewCell;
            NewCell->Lprev = Next;
            NewCell->Lnext = This;
        }
        else
        {//如果插入点在链表头部，那么RootP应该指向新的节点
            RootP->Lprev = NewCell;
            Next->Lnext = NewCell;
            NewCell->Lprev = Next;
            NewCell->Lnext = NULL;
        }
    }
    else
    {//如果在链表尾部
        if( This != RootP )
        {//如果在链表的尾部，哑节点的Lnext应该指向新的节点
            This->Lprev = NewCell;
            RootP->Lnext = NewCell;
            NewCell->Lprev = NULL;
            NewCell->Lnext = This;
        }
        else
        {//如果是空表,哑节点应该指向新的节点
            RootP->Lprev = NewCell;
            RootP->Lnext = NewCell;
            NewCell->Lprev = NULL;
            NewCell->Lnext = NULL;
        }

    }

    return True;
}


void PrintList( Node *RootP )
{
    Node *This;

    for( This = RootP->Lprev; NULL != This; This = This->Lprev )
        printf("%d ",This->Value);
}


int Delete( Node *RootP, int value )//删除节点，需要修改两个指针，被删除的节点之前的节点的Lnext指针，以及被删除节点之后的Lperv指针。
{
    Node *This;
    Node *Next;

    for( This = RootP; NULL != ( Next = This->Lprev ) && value != Next->Value;
            This = Next )
        ;

    if( NULL == Next )
        return False;
    
    if( NULL != Next->Lprev )
    {
            This->Lprev = Next->Lprev;
            Next->Lprev->Lnext = This;
            free( Next );
    }
    else
    {
        This->Lprev = NULL;
        This->Lnext = RootP;
        free( Next );
    }

    return True;

}


void DelList( Node *RootP )
{
    Node *Temp;
    Node *This;

    This = RootP->Lprev;

    while( NULL != ( Temp = This ) )
    {
        This = Temp->Lprev;
        free( Temp );
    }

    RootP->Lprev = NULL;
    RootP->Lnext = NULL;
}

[此贴子已经被作者于2017-3-23 21:10编辑过]

头节点不可用？我没说过呀。
你是不是弄错了。

双链表的头节点是一个哑节点，需要用的是它的两个指针，但是它的值不会被使用。

创建一个哑节点的目的，是为了简化向函数传递双链表，因为双链表有2个指针。

另外一个，我在主楼中的main()函数中在调用InsertList函数的时候，有一个错误的示范。

    Node *RootP;//这个指针是多余的。
    Node root;
    int value;

    root.Lprev = NULL;
    root.Lnext = NULL;
    root.Value = 0;
    RootP = &root;//这里也是多余的。

    while( 1 == scanf("%d",&value) )
        if ( InsertList( RootP, value ) )//这里应该写成 if( InsertList( &root， value ) )
            root.Value++;//因为哑节点的值不会被使用，所以这里我它来记录双链表中节点的数量。

[此贴子已经被作者于2017-4-12 19:17编辑过]

不用分辨啊。
比如RootP就是传递给函数的哑节点地址。
Next是遍历指针。

Next 的初始值为 RootP->prev 这样不就避开了哑节点的值了吗？

[此贴子已经被作者于2017-4-12 19:44编辑过]

终止条件难道不应该就是根指针吗？否则……这遍历不就无休无止了?

[此贴子已经被作者于2017-4-12 20:32编辑过]

for( next = RootP->next; next != Root; next = next->next )
      ;

哑节点之后的那个节点的next指针，指向的是哑节点，所以可以作为判断循环结束的条件。

如果你把一个双链表画出来会更容易理解一点儿prev和next指针为什么取这两个名字，一个前向，一个后向。

[此贴子已经被作者于2017-4-12 20:37编辑过]

前向指针的名字是prev，所以正向遍历是next = next->prev;
next是后向指针，所以逆序遍历是 next= next->next;

所以我建议你画一个，随手就行。这两个指针的名字你就会很直观了。

好吧，也许我的这个遍历指针next让你会困扰，所以，换成this会不会更好？

我换一个名字：
前向指针的名字是prev，所以正向遍历是this = this->prev;
next是后向指针，所以逆序遍历是 this= this->next;

如果双向链表是一个循环链表的话，那么正向遍历的终止条件也将是: this != RootP;

[此贴子已经被作者于2017-4-12 20:43编辑过]

链表的指针是有几乎约定成俗的名字的：

单链表是next 或link；
双链表是prev 和 next；

那就不知道为什么了。我是从一个职业程序员哪里获得这些信息的。以前我取变量名也乱来的。

另外，你发的图片里的资料并不好。

你的图片的意思是双向链表的结构应该是这样的：

struct XXX {
        struct XXX *Prior;
        int value;
        struct XXX *next;
};

如果value的类型是double，那么这个结构在某些系统上会占用24个字节，但如果按下面这样写，就只占16个字节。

struct XXX {
        int value;
        struct XXX *prior;
        struct XXX *next;
};

不，对字节有严格要求的类型一定要放在最前面，按占用字节数，应该从大到小。这个你用自己的编译器做一下sizeof的测试就可以知道了。

当然节省的内存会根据系统不同而有所不同，但不会出现占用更大的可能性。

[此贴子已经被作者于2017-4-12 21:16编辑过]