逆序建链表和顺序建链表

朴灿烈づ我的快乐病毒、 2023-02-28 04:12 2阅读 0赞

本次博客也是我的第一个博客，所以肯定会有不好的地方，希望多多包涵，评论区多提提意见，帮助我改进，大家一起进步，一起努力。

最近也是在学习数据结构，第一个内容就是与链表有关的，对于链表中的一些基础点我这里就不做具体解释了。那么链表首先是得建表，对于建表有两种方式，第一种方式是逆序建立链表，第二种方式就是顺序建立链表，下面我将用两份代码作为讲解，代码中也会有详细的注释。

## 逆序建立链表 ##

**Description:  
输入整数个数N，再输入N个整数，按照这些整数输入的相反顺序建立单链 表，并依次遍历输出单链表的数据。  
Input:  
第一行输入整数N;  
第二行依次输入N个整数，逆序建立单链表。  
Output:  
依次输出单链表所存放的数据。  
Input:  
10  
11 3 5 27 9 12 43 16 84 22  
Output:  
22 84 16 43 12 9 27 5 3 11**

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        
        int data;//数据域
        struct node *next;//地址
    };
    int main()
    {
        
        int i,n;
        struct node *head,*p;
        head=(struct node *)malloc(sizeof(struct node));
        //为头结点分配空间
        head->next=NULL;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
        
             p=(struct node *)malloc(sizeof(struct node));
             //为游动结点分配空间
            scanf("%d",&p->data);
            p->next=head->next;//将该结点顺接到头结点（前一个结点）后面，注意开始是head->next为NULL
            head->next=p;/*将该结点接到头结点后面（即紧接头结
            点），结点内容依次录入。最后一次录入的结点接到头结
            点后面，这样后录入的便在整个链表的前面，逆序建链表
            便完成*/
        }
            while(p)//若p不为空则继续，否则跳出循环，下面的if则同理
            {
        
                if(p->next)
                {
        
                    printf("%d ",p->data);
                }
                else
                {
        
                    printf("%d\n",p->data);//若是最后一个结点则输出换行
                }
                p=p->next;
            }
        return 0;
    }

![在这里插入图片描述][20200719201030216.png]

*如果对于上面的代码不太理解可以借助此图作为辅助*

逆序建立链表就是这样，其实静下心来理解并不难，加油，下面将讲解顺序建立链表。

## 顺序建立链表 ##

**Description:  
输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。  
Input:  
第一行输入整数的个数N；  
第二行依次输入每个整数。  
Output:  
输出这组整数。  
Input：  
8  
12 56 4 6 55 15 33 62  
Output:  
12 56 4 6 55 15 33 62**

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        
        int data;//数据域
        struct node *next;//地址
    };
    int main()
    {
        
        int i,n;
        struct node *head,*p,*tail;/*注意这里多了一个尾结点，始终
        指向尾（每次录入结点都把该结点作为尾结点）*/
        head=(struct node *)malloc(sizeof(struct node));
        //为头结点分配空间
        head->next=NULL;
        tail=head;//开始的时候就一个结点，头即为尾
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
        
             p=(struct node *)malloc(sizeof(struct node));
             //为游动结点分配空间
            scanf("%d",&p->data);
            p->next=NULL;
            tail->next=p;/*将该结点接到头结点后面（即紧接头结
            点），结点内容依次录入。最后一次录入的结点接到头结
            点后面，这样后录入的便在整个链表的前面，顺序建链表
            便完成*/
            tail=p;
        }
             p= head; /*因为链表只能从第一个指针开始查询，
             只有头指针位置可知，所以让游动指针开始为head*/
            while(p->next)//若p->next不为空则继续，否则跳出循环
            {
        
                printf("%d ",p->next->data);
                p=p->next;
            }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODg1MjE5_size_16_color_FFFFFF_t_70]  
*如果对于上面的代码不太理解可以借助此图作为辅助*

建立链表的两种方法，我采用的是用例题作为解释，这种方法我认为会更好的帮助你理解，也会减少从知识到做题应用过程中的“无解bug”，希望你可以喜欢。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODg1MjE5_size_16_color_FFFFFF_t_70 1]

[20200719201030216.png]: /images/20230209/721bc871925b42cea72b51805c99ba96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODg1MjE5_size_16_color_FFFFFF_t_70]: /images/20230209/d440ca42c1694804ae25f001fd32b234.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODg1MjE5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200719201722145.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODg1MjE5,size_16,color_FFFFFF,t_70