单向链表学习（尾插法）含简单的增，删，查，排序；

约定不等于承诺〃 2022-06-01 08:53 86阅读 0赞

## 序言 ##

下学期学数据结构，这学期老师让复习C语言，先练练单链表.。方便理解起见，设为int类型的单链表,

## 代码正文（包含了链表的初始化，查询，尾部新增，插入，删除，排序） ##

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {
        int data;
        struct node *next;
    }node;
    node *creatLink()
    {
        printf("开始创建 int 类型的链表,请输入您要存放到链表中的值：(输入 0 为结束的标志)\n");
        node *head = malloc(sizeof(node));          //1. 申请一块头结点内存.
        head->next = NULL;                  //将头结点的指针先置为NULL，
                                    //如果用户不输入的话，头节点一个节点就是一整个链表(有空头结点，为节点的指针为NULL)
        //使用尾插法，所以命名为  *rear
        node *rear = head;      //尾插指针rear 首先指向链表最尾端：head；
        int temp;
        while(scanf("%d",&temp), temp!=0)
        {
            node *t = malloc(sizeof(node));     //开辟新空间
            t->data = temp;   //将输入值赋予新空间的data
            rear->next = t;     //rear 的 next 指针指向新空间
            rear = t;       //rear 后移到 t 上.
        }
        rear->next = NULL;
        return head;                //将头结点指针返回给主函数
    }
    void printList(node *head)
    {
        node *cur=head->next;
        while(cur != NULL)
        {
            printf("%d ", cur->data);
            cur = cur->next;
        }
    }
    int query(node *head)
    {
        int num_query,i;
        printf("输入您要查询的值:\n");
        scanf("%d",&num_query);
        node *pointer = head->next; //直接跳过传入的空节点指针.
        for(i = 1; pointer != NULL; i++)
        {
            if(pointer->data == num_query)
            {
                printf("您要查询的值在链表中的第%d个节点\n",i);
                return i;
            }
            pointer = pointer->next;
        }
        printf("抱歉，没查到.\n");
        return -1;
    }
    void insert(node *head)
    {
        printf("请输入您想要在第___个节点后插入:");
        int num, i = 1, newData;
        node *temp = head->next;
        scanf("%d",&num);
        printf("请输入您想要插入的数值");
        scanf("%d", &newData);
        while(temp != NULL)
        {
            if(i==num)          //得到节点数,在这个节点后进行插入.
            {
                node *newNode = malloc(sizeof(node));
                newNode->data = newData;
                newNode->next = temp->next;
                temp->next = newNode;
                return ;
            }
            i++;
            temp=temp->next;
        }
        printf("您输入的节点数过大，大于了链表的节点数:%d",i);
    }
    void deleteNode(node *head)
    {
        int num_delNode, i = 1;
        printf("请输入您要删除的节点的位置：");
        scanf("%d",&num_delNode);
        node *cur=head->next, *pre = head;
        while(cur != NULL)
        {
            if(i==num_delNode)          //得到节点数,对这个节点进行删除.
            {
                pre->next = cur->next;
                free(cur);
                return ;
            }
            i++;
            pre = cur;
            cur = cur->next;
        }
        printf("您输入的节点数过大，大于了链表的节点数:%d",i);
    }
    void swap(node *node1, node *node2)
    {
        int temp = node1->data;
        node1->data = node2->data;
        node2->data = temp;
    }
    void linkSort(node* head)
    {
        //使用冒泡排序
        node *node1,*node2;
        for(node1 = head->next; node1 != NULL; node1 = node1->next)
        {
            for(node2 = node1->next; node2 != NULL; node2 = node2->next )
            {
                if(node1->data > node2->data)
                {
                    swap(node1,node2);
                }
            }
        }
    }
    int main()
    {
        node *head;  //创建头节点指针
        head = creatLink();     //进行创建并初始化链表
        //printList(head);        //输出测试
        //query(head);        //查询操作.
        //insert(head);
        //deleteNode(head);
        linkSort(head);
        printList(head);
        return 0;
    }

运行效果如下:

![Center][]

## 什么是单链表?为什么使用它？ ##

.(图盗百度百科的，先有个印象，再看解释，看不懂图完全没问题)

![b2de9c82d158ccbfebe4998510d8bc3eb1354130.jpg][]

便于理解：先于"简单"的 数组 进行比较.

因为数组在内存空间为一整块连续的内存，所以数组可以很快的查询(通过下标或者指针)与尾加入。但是删除，插入时，都非常麻烦（时间复杂度较高）.

举个例子：

**插入：现在有一个长度为N（N>10000）的int 型数组，我要在头部插入多个 1。那么我需要让之后所有的数值都后退多位，且不可保证预申请的内存是否足够.**

**    删除：或者还是这个数组。我要删除前1000位中任意多个，那么后面的大量数据要前移多位。效率及其低下。**

现在来看单向链表，单向链表的基本组成部分为节点(node)。

每个节点包含：一个数值和一个指向下一个节点的节点指针。

当我们插入第 **n** 个节点后插入一个值时，只需要让第 **n** 个节点的 原指向 第  **n+1** 个节点的指针指向我们新申请的节点，新申请节点的指针 指向第n+1个节点的地址即可。

效果如图

插入前的情况

![Center 1][]

开始改变待插入节点的的指针。使其指向 第 n+1 个节点.

*(先改变待插入节点的指针原因为：如果先改变第n个节点的指针，那么程序就失去了第n+1个节点的地址.要么代码量增加，要么内存泄漏)*

![Center 2][]

接着改变第 n 个节点的指针

![Center 3][]

插入完成。整个操作中只对两个节点进行了改动。

删除与插入完全逆序.

## 单链表的几个要点    ##

接下来说一下单链表的几个重点：(懂了思想之后再去写代码，而不是一口气写一大堆，改都不会改.)

1.单链表的头指针一旦指向了链表，请务必不要再进行改动了(唯一的情况是销毁链表，单向链表请务必保证从尾部向头部销毁,不然有可能内存泄漏)

2.单链表尽可能 (请务必这样做) 拥有一个空的头节点，空的头结点的意思是：头结点不存放数值data，只是单纯的指向下一个节点.(好处会在后面的代码中体现，并进行对比.)

3.单链表的尾部节点的指针必须置为NULL，这样不仅有了判断链表是否结束的标志，而且可以防止野指针的出现(只有上帝知道它会不会指向非常重要的地方)

4.单链表的插入，删除固然快，但是查询速度和查询方法以及代码量。。。(后面代码中会详细解释)，

![b2de9c82d158ccbfebe4998510d8bc3eb1354130.jpg][]

现在看这幅图有没有明白一些呢？

## 开始代码施工    ##

再说一次，每个节点应该包含一个数值(data)与一个指向下一节点的节点指针( \*next).

结构体代码如下

typedef struct node    //定义节点类型
    {
        int data;   //一个数值
        struct node *next;  //一个指向下一个节点的节点指针
    }node;

然后，节点与节点之间互相连接起来就是链表。现在开始建立一个新的 Project 测试。

![Center 4][]

测试结果可以.为了方便新手理解，用图来解释一下createLink 的过程吧！

刚开始的

node *head = malloc(sizeof(node));          //1. 申请一块头结点内存.
        head->next = NULL;                  //将头结点的指针先置为NULL，

![SouthEast][]

然后开始新增：

![Center 5][]

初始化链表已经搞定，开始最简单的查询操作。(限定查询是否在链表中存在某值，存在的话返回这个值所在的节点数.不存在返回-1)；

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {//节省空间，不再重复}node;
    node *creatLink()
    {//节省空间，不再重复}
    void printList(node *head)
    {//节省空间，不再重复}
    int query(node *head)
    {
        int num_query,i;
        printf("输入您要查询的值:\n");
        scanf("%d",&num_query);
        node *pointer = head->next; //直接跳过传入的空节点指针.
        for(i = 1; pointer != NULL; i++)
        {
            if(pointer->data == num_query)
            {
                printf("您要查询的值在链表中的第%d个节点\n",i);
                return i;
            }
            pointer = pointer->next;
        }
        printf("抱歉，没查到.\n");
        return -1;
    }
    int main()
    {
        node *head;  //创建头节点指针
        head = creatLink();     //进行创建并初始化链表
        //printList(head);        //输出测试
        query(head);        //查询操作.
        return 0;
    }

![SouthEast 1][]

插入（传入节点数插入，如传入数值 2 则再第二个节点后插入.）

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {
        //省略
        node *creatLink()
        {
    //省略
        }
        void printList(node *head)
        {
    
    //省略
        }
        int query(node *head)
        {
            int num_query,i;
    
    //省略
        }
        void insert(node *head)
        {
            printf("请输入您想要在第___个节点后插入:");
            int num, i = 1, newData;
            node *temp = head->next;
            scanf("%d",&num);
            printf("请输入您想要插入的数值");
            scanf("%d", &newData);
            while(temp != NULL)
            {
                if(i==num) //得到节点数,在这个节点后进行插入.
                {
                    node *newNode = malloc(sizeof(node));
                    newNode->data = newData;
                    newNode->next = temp->next;
                    temp->next = newNode;
                    return ;
                }
                i++;
                temp=temp->next;
            }
            printf("您输入的节点数过大，大于了链表的节点数：%d",i);
            /**
            试想一下，如果我们不使用头结点，如果我选择 0 节点插入，
            即插入在最前面,不仅主函数中的 head 的值要对应改变
            (需要将这个insert函数返回值更改为node *)
            而且我们要分类去讨论这件事情，如果有了空节点，
            第一个节点数据就是从实际上的 第2个节点开始存储，就化为一般问题了.
            （尾节点与中间节点相同，不必考虑）
            */
        }
        int main()
        {
            node *head; //创建头节点指针
            head = creatLink(); //进行创建并初始化链表
            insert(head); //插入，
            printList(head); //查看链表结果
            return 0;
        }

开始删除操作。选择想要删除的节点的位置

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {
       //省略,有兴趣翻阅最上面的完全体代码;
    void deleteNode(node *head)
    {
        int num_delNode, i = 1;
        printf("请输入您要删除的节点的位置：");
        scanf("%d",&num_delNode);
        node *cur=head->next, *pre = head;
        while(cur != NULL)
        {
            if(i==num_delNode)          //得到节点数,对这个节点进行删除.
            {
                pre->next = cur->next;
                free(cur);
                return ;
            }
            i++;
            pre = cur;
            cur = cur->next;
        }
        printf("您输入的节点数过大，大于了链表的节点数:%d",i);
    }
    int main()
    {
        node *head;  //创建头节点指针
        head = creatLink();     //进行创建并初始化链表
        //printList(head);        //输出测试
        //query(head);        //查询操作.
        //insert(head);
        deleteNode(head);
        printList(head);
        return 0;
    }
     
     
     最后一个排序操作.
    
     
            #include <stdio.h>
     #include <stdlib.h>
    //省略
    void swap(node *node1, node *node2)
    {
        int temp = node1->data;
        node1->data = node2->data;
        node2->data = temp;
    }
    void linkSort(node* head)
    {
        //使用冒泡排序
        node *node1,*node2;
        for(node1 = head->next; node1 != NULL; node1 = node1->next)
        {
            for(node2 = node1->next; node2 != NULL; node2 = node2->next )
            {
                if(node1->data > node2->data)
                {
                    swap(node1,node2);
                }
            }
        }
    }
    int main()
    {
        node *head;  //创建头节点指针
        head = creatLink();     //进行创建并初始化链表
        linkSort(head);
        printList(head);
        return 0;
    }

[Center]: /images/20220601/5d62080595914598ac547028b8f43f42.png
[b2de9c82d158ccbfebe4998510d8bc3eb1354130.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike92%2C5%2C5%2C92%2C30/sign=f56b157cdeca7bcb6976cf7ddf600006/b2de9c82d158ccbfebe4998510d8bc3eb1354130.jpg
[Center 1]: /images/20220601/567339de91754c17b3b4b84fbf01039b.png
[Center 2]: /images/20220601/cc94c94e70ad42998a80f1b0ea750d26.png
[Center 3]: /images/20220601/5a5917296df4459086169580042db535.png
[Center 4]: /images/20220601/856c0f1341fc440ba4da03419861bb9c.png
[SouthEast]: /images/20220601/f39105ad68d2420d993b4d05a669056e.png
[Center 5]: /images/20220601/3346fba9f68f42ae97628ef4fb57f3b2.png
[SouthEast 1]: /images/20220601/5dda65b1afe14409bda6f8cf528fc529.png