如何在C语言中去创建一种双向链表呢

• 一、考察知识点
  

1、双向链表结构
2、双向链表的创建
3、双向链表插入节点
4、链表的排序
二、具体实现

1.双向链表的结构

  双向链表从名字上理解双向链表，即链表是 “双向” 的，如图1所示：

双向，指的是各节点之间的逻辑关系是双向的，但通常头指针只设置一个，除非实际情况需要。
从图 1 中可以看到，双向链表中各节点包含以下 3 部分信息（如图 2 所示）：
1、指针域：用于指向当前节点的直接前驱节点；
2、数据域：用于存储数据元素。
3、指针域：用于指向当前节点的直接后继节点；

因此，双向链表的节点结构用 C 语言实现为：
typedef struct DulNode
{
    int data;
    struct DulNode *pre;
    struct DulNode *next;
   
}Node,*List;


2.C语言中创建双向链表

  同单链表相比，双链表仅是各节点多了一个用于指向直接前驱的指针域。因此，我们可以在单链表的基础轻松实现对双链表的创建。
需要注意的是，与单链表不同，双链表创建过程中，每创建一个新节点，都要与其前驱节点建立两次联系，分别是：
将新节点的 pre 指针指向直接前驱节点；
将直接前驱节点的 next 指针指向新节点；
利用尾插法创建双向链表，键盘输入数字按回车结束。
代码如下：
Node *InitList()//尾插法创建双链表
{
    Node *L=(Node*)malloc(sizeof(Node));//创建头节点
    L->pre=NULL;
    L->next=NULL;
    Node *r;//声明一个指针r指向头节点L，用于遍历链表
    r=L;
   
    printf("please enter number:n");
    do{
        Node *p=(Node*)malloc(sizeof(Node));//生成新结点
        p->pre=r;//将新节点*p插到尾节点*r之后
        scanf("%d",&(p->data));
        p->next=NULL;


        r->next=p;//r->next 等价于 L->next
        r=p;//r指向新的尾节点*p
    }while(getchar()!='n');
    return L;
}
可以在在main()函数中输出创建的双向链表，需要一个display函数来打印创建的双向链表，display函数如下：
void display(Node *L)
{
    Node* temp;
    temp=L;//将temp指针指向头结点
    while(temp->next)//尾节点的next为NULL
    {
        temp=temp->next;
        printf("%d ",temp->data);
    }
    printf("n");
}
在mian（）函数中调用：
int main()
{
    Node *L;
    L=InitList();
    printf("the number is:n");
    display(L);
   
    return 0;
}
3.双向链表插入节点

  说明一下，题目为的是实现输入数字的顺序输出，蔚来方便，不考虑表头表尾情况，直接将插入的数放到表中间
添加至表的中间位置
同单链表添加数据类似，双向链表中间位置添加数据需要经过以下 2 个步骤，如图 3 所示：
新节点先与其直接后继节点建立双层逻辑关系；
新节点的直接前驱节点与之建立双层逻辑关系；

这里是将数elem直接插入到链表的add位置处。
双向链表插入节点的代码如下：
Node *Insert(Node *p,int elem,int add)//双向链表插入节点，将值elem插入指定位置add
{
    Node *temp;//新建一个临时节点
    temp=p;
    int i=0;
    while(temp && i     {
        temp=temp->next;
        ++i;
    }


    Node *inser=(Node*)malloc(sizeof(Node));//生成新节点inser
    inser->data=elem;
    inser->next=temp->next;
    inser->pre=temp;
    temp->next->pre=inser;
    temp->next=inser;


    return p;


}
同样可以在main函数中输出显示,代码中直接将数插入链表位置3的节点处：
int main()
{
    Node *L;
    L=InitList();
    printf("the number is:n");
    display(L);


    int elem;
    printf("please enter the number to be inserted:n");
    scanf("%d %d",&num);
    L=Insert(L,num,3);
    display(L);
   
    return 0;
}
4.链表排序

上面已经建立了一个双向链表，并且输入了数据、插入了数据。
下面对其进行排序，从首元节点开始，不断比较相邻两个节点data的大小，按从小到大的顺序对链表进行排序。
代码如下：
Node *compare(Node *L)
{
    Node *p,*q;
    p=L->next;//p指向首元节点，L为头节点所以p不能指向L
    int num;
    while(p)
    {
        q=p->next;//q指向p下一节点，相邻的两个节点的data比较大小
        while(q)
        {
            if(p->data > q->data)
            {
                num=p->data;
                p->data=q->data;
                q->data=num;
            }
            q=q->next;
        }
        p=p->next;
    }
return L;
}
}
同样可以在main函数中输出显示：
int main()
{
    Node *L;
    L=InitList();
    printf("the number is:n");
    display(L);


    int num;
    printf("please enter the number to be inserted:n");
    scanf("%d",&num);
    L=Insert(L,num,3);
    display(L);


    printf("sorted linked list:");
    L=compare(L);
    display(L);


    return 0;
}
运行结果



输入一串数字： 1 2 3 4 6 7 8 9
插入数字：5
结果应为： 1 2 3 4 5 6 7 8 9
结果如下

可知结果是正确。