链表构建头插法和尾插法(C语言实现)

喜欢ヅ旅行 2022-12-06 12:39 191阅读 0赞

### 头插法 ###

实际上，头插法是将要插入的结点，插入到表头结点和已插入结点的中间,核心实现看第三步。

头插法的步骤如下:

1.  构建链表，实际上是为构建一个表头结点，并让其next为NULL；
2.  构建要插入的结点 s
3.  让`s->next = L->next;` 再让`L->next = s;`需要特别注意的是，第一次的时候实际上是让s结点的next域指向了NULL;，这得益于我们构建表头结点时，让表头结点的next域初始化为NULL；

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {
        
    
        int data;
        struct node *next;
    
    } node,*LNodeList;
    int main()
    {
        
        LNodeList L = (LNodeList)malloc(sizeof(node));
        // 一定要初始化next为null;
        L->next =NULL;
    
        int input_data = 0;
        node *s;
        scanf("%d",&input_data);
        while(input_data!=-999)
        {
        
            s = (node*)malloc(sizeof(node));
            s->data = input_data;
            // 如果是第一个插入的结点，实际上这里让其等于NULL，正好便于后面遍历
            s->next = L->next;
            L->next = s;
            scanf("%d",&input_data);
        }
        //用于遍历的指针p
        node *p = L;
        while(p->next!=NULL)
        {
        
            p = p->next;
            printf("%d ",p->data);
        }
    
        return 0;
    }

![在这里插入图片描述][20200913095404708.png_pic_center]

### 尾插法 ###

通过头插法的过程和输出结果，我们可以发现**头插法实际构造的链表与用户输入数据的顺序是相反的**，如果想要根据用户输入数据的顺序来构造链表可以使用尾插法，但是与头插法不同的是，**需要多加一个指向尾部结点的尾指针**。

1.  构建带头节点的链表，并让尾指针 r 指向该头节点
2.  构建要插入的结点s
3.  `r-> next = s`,`r = s`
4.  若没有需要插入的结点，将尾指针的next置NULL，这是为了方便后面的遍历。

#include <stdio.h>
    #include <stdlib.h>
    typedef struct node
    {
        
        struct node *next;
        int data;
    }node,*LNodeList;
    
    int main()
    {
        
        // 用户输入的data
        int input_data = 0;
        // 初始化链表,带头节点
        LNodeList L=(LNodeList*)malloc(sizeof(node));
        // 要插入结点的指针和尾指针
        node *s,*r=L;
         scanf("%d",&input_data);
        while(input_data!=-999)
        {
        
            s = (node*)malloc(sizeof(node));
            s->data=input_data;
    
            r->next = s;
            r = s;
            scanf("%d",&input_data);
    
        }
        // 尾结点置空
        r->next = NULL;
        node *p = L;
        while(p->next!=NULL)
        {
        
            p = p->next;
            printf("%d ",p->data);
        }
    
        return 0;
    }

![在这里插入图片描述][20200913095709736.png_pic_center]

[20200913095404708.png_pic_center]: /images/20221123/52ec9a7192c04372b451c49564357b55.png
[20200913095709736.png_pic_center]: /images/20221123/5568f5e6af2c494e80d0af3d1f0142bd.png