输入一串数字到双向链表中，再将一个数字插入到该双向链表中，最后按从小到大的顺序排列输出——C语言实现

文章目录

- 输入一串数字到双向链表中，再将一个数字插入到该双向链表中，最后按从小到大的顺序排列输出——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<add-1)//寻找第add-1个节点，temp指向add-1节点
    {
        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;
}