目录

一、前言 : 

二、线性结构

        1.介绍

        2.分类

        3.数组和链表的区别 : 

三、链表 [离散存储] 

        1.定义

        2.相关概念

        3.如何确定一个链表？

        4.如何表示链表中的一个结点？

        5.链表的分类

四、链表的相关算法

        1.链表的创建和遍历

                ①准备工作 : 

                ②创建链表 : 

                ③遍历链表 : 

        2. 获取链表的有效长度

        3.判断链表是否为空

        4.链表的排序

        5.链表元素的插入和删除

                ①插入元素 : 

                ②删除元素 : 

        6.代码演示

五、完结撒❀

---

一、前言 : 

        大家好，今天为大家带来的是数据结构与算法中单链表的内容分享，博文内容包括但不限于线性结构介绍，链表介绍，链表相关算法的讲解及演示。（以单链表为例）本篇博文属于《数据结构与算法入门》专栏，主要是为了将来的《数据结构与算法进阶》以及算法题做铺垫。

        注意 : ①代码中的注释也很重要；②不要眼高手低，自己动手跟着过一遍才能真正有收获；③可以点击文章侧边栏或者文章前面的目录进行跳转。良工不示人以朴，所有文章都会适时补充完善。感谢阅读！

---

二、线性结构

        1.介绍

        线性结构，即用一根直线把所有的结点穿起来，使得多个数据呈现有序的排列。

        2.分类

        常见的线性结构有链表，数组，栈，队列等。

        3.数组和链表的区别 : 

        ①从线性结构的角度来看，二者的区别在于——数组是连续存储的线性结构；而链表是离散存储的线性结构。

        ②数组的优缺点 : 

                优点 :  存取速度快；改查效率高。

                缺点 :  需要一个连续的较大的内存空间；进行元素的增删操作时效率很低。

        ③链表的优缺点 : 

                优点 :  插入和删除元素时效率高；不需要一个连续的较大的内存。

                缺点 :  查找某个位置的元素时效率低。

---

三、链表 [离散存储] 

        1.定义

        ①多个结点呈离散分配的状态。（不连续）

        ②每个结点之间通过指针彼此相连。

        ③每个结点都只有唯一前驱结点，和唯一后继结点。特殊的是，首节点没有前驱结点，尾节点没有后继结点。

        ④每个结点都分为两部分，一部分是数据域，用于保存数据；另一部分是指针域，用于指向下一个结点。（单链表）

        2.相关概念

        ①首结点 : 存放链表第一个有效数据的结点。

        ②尾结点 : 存放链表最后一个有效数据的结点。

        ③头结点 : 首结点前面的结点，是真正意义上的链表的第一个结点，数据类型与首结点一致，但并不存放有效数据。头结点本身无实际意义，添加头结点的原因是为了更好地对链表相关的算法进行操作。（即方便链表的操作）

        ④头指针 : 存放头结点地址的指针变量。（即指向头结点的指针）

        ⑤尾指针 : 存放尾结点地址的指针变量。（即指向尾结点的指针）

        Δ示意图如下 : 

        3.如何确定一个链表？

        要确定一个链表实际只需要一个参数——头指针。由于头指针保存的头结点的地址，所以通过头指针，我们可以找到头结点；接着，又通过头结点找到首结点；以此类推，直到尾结点，当发现某个结点的指针域为空时，它就是尾结点了。

        因此，如果想通过一个函数对链表进行操作，该函数至少需要获取链表的一个参数，那就是头结点。因为我们可以通过头指针递推出链表的其他所有参数。

        4.如何表示链表中的一个结点？

                可通过定义Node结构体类型来表示结点，（Node就是结点的意思）。如下所示 : 

    struct Node {
        int data;                //数据域 —— 用于保存数据
        struct Node * pNext;     //指针域 —— 用于保存下一个结点的地址（指向下一个结点）
    };

                也可通过typedef关键字进行优化，如下所示 : 

    typedef struct Node {
        int data;
        struct Node * pNext;
    } NODE, * PNODE;            //NODE 和 * PNODE无顺序要求

        5.链表的分类

        ①单链表 :  以上内容均以单链表为例。

        ②双链表 :  每个结点分为了三部分，除了一个数据域外，还有两个指针域。其中，一个指针域指向前一个结点，另一个指针域指向后一个结点。

        ③循环链表 :  字面意思，链表通过结点的指针域实现了串联，可以通过任意一个结点找到其他所有的结点。

        ④非循环链表 : 字面意思，与循环链表相对。

---

四、链表的相关算法

        1.链表的创建和遍历

                ①准备工作 : 

                以非循环单链表为例，我们要想创建和遍历链表，首先必须确定链表结点的数据类型；可以定义Node结构体类型配合typedef关键字来确定链表结点的数据类型，如下所示 : 

    typedef struct Node         //定义结点数据类型
    {
        int data;
        struct Node * pNext;
    } NODE, * PNODE;

                注意，此时NODE 等价于 struct Node类型；PNODE 等价于 struct Node *类型。
                此外，我们还需要导入<stdio.h>, <malloc.h>, <stdlib.h>这三个头文件，它们分配包含了"输入输出"，"分配内存"，"退出程序"的函数。 如下所示  :

    # include <stdio.h>        //包含scanf, printf函数
    # include <malloc.h>       //包含malloc函数
    # include <stdlib.h>       //包含exit函数

                对于链表的创建和遍历，我们分别使用create_list() 和 traverse_list() 函数来实现。

                ②创建链表 : 

                1°定义create_list() 函数进行链表的创建工作，并令其最终返回头结点的地址（返回给头指针）。
                2°create_list() 函数中局部变量的定义情况如下 : 

    int length;     //存放链表中有效长度的个数
    int i;          //循环变量
    int value;      //临时存放当前结点的值。

                3°除以上三个局部变量外，还需通过malloc函数为头结点分配内存空间，并令头指针和尾指针同时指向头结点。
                4°令用户输入length的值，根据length的值定义for循环赋值的次数。在for循环中，先令用户输入value的值；然后通过malloc函数为新结点分配内存空间，并将value的值赋值给新结点的数据域；接着，令上一个结点的指针域指向新结点；令新结点的指针域为NULL；最后令尾指针指向新结点。

                ③遍历链表 : 

                1°定义traverse_list() 函数进行链表的遍历操作，需要将链表的头指针传入traverse_list() 函数。
                2°首结点是链表中存放第一个有效数据的结点，因此要用从首结点开始遍历。我们可以在traverse_list() 函数中定义一个新的PNODE类型的指针变量p，并为其赋值为pHead->pNext，即令其指向首结点。
                3°定义while循环，判断首结点是否为空，为空则不进入while循环，不遍历链表。如果不为空，先打印出当前结点数据域中的值，然后令指针p后移一位，使p指向下一个结点。直到p指针保存的值为尾结点的指针域时，退出while循环，遍历结束。

        2. 获取链表的有效长度

                1°在前面代码的基础上，定义size_ofList方法来获取链表的有效长度（即链表中有效元素的个数）。
                2°在size_ofList方法内部定义局部变量cnt，用于存放链表中有效元素的个数，并使size_ofList方法最终能够返回cnt变量（int类型)。
                3°该方法需要传入一个PNODE类型的实参pHead，因为pHead指向的是链表的头结点，不存放有效数据，因此我们还需要在方法内部定义一个临时的PNODE类型变量，假设为p，并令p = pHead->pNext，即令p指向首结点。
                4°利用while循环对链表进行遍历，判断条件为p不等于NULL；然后在while语句内令p = p->pNext，同时让cnt自增1。即，相当于先判断首结点是否为空，如果首结点不为空，再依次循环判断后面的每一个结点是否为空，当p指向尾结点的指针域时，循环结束。

        3.判断链表是否为空

                1°在前面代码的基础上，定义is_empty方法来判断链表是否为空。同样，需要传入要判断链表的头指针pHead。
                2°利用if 条件语句进行判断，如果pHead指向的结点的指针域为空，即如果首结点为空，返回true，否则返回false。
                3°C语言中，如果想返回true或者false，需要导入# include <stdbool.h>头文件。

        4.链表的排序

                1°在前面代码的基础上，定义sort_list方法来对链表进行排序。同样，需要传入要排序链表的头指针pHead。
                2°从狭义上讲，链表的排序和数组的排序算法是不同的，因为二者存储数的方式不一样，数组是连续的，有下标；而链表是不连续的，没有下标。但是，从广义上讲，链表排序的算法与数组是一致的，因为二者同属于线性结构。因此，链表的排序与数组的排序在原理上是一致的。
                3°我们以冒泡算法的排序为例，以往数组的冒泡排序——其大体框架如下 : 

    //以下代码仅作演示用，无实际意义。
    int i,j,t;

    for (i = 0; i < length - 1; ++i)
    {
        for (j = i + 1; j < length; ++j)
        {
            if (array[i] > array[j]) 
            {
                t = array[i];
                array[i] = array[j];
                array[j] = t;
            }
        }
    }

                类似于数组的排序，链表的排序要在上面做一些改动。首先最明显地，链表没有索引，所以有索引的地方必须进行替换。我们可以分别定义PNODE类型的变量p和q，并在外层for循环中，将p初始化为p = pHead->pNext；在内层for循环中将q初始化为q = p->pNext，即令p一开始指向首结点，而令q一开始指向首结点后面的结点。
                4°因为我们最终要比较的是结点内data的值，所以内层for 循环的if 语句中，进行判断和交换的数据就是p->data和q->data；仍然需要定义临时变量t，用于辅助数据的交换。
                5°解决掉索引的问题后，还有一个问题——循环次数的问题 : 
                可以选择保留i 变量和j 变量分别用于控制外层for循环和内层for循环的次数。即类似于数组的排序，内层每排序一次，j自增1；外层每排序一次，i自增1。当i 变量的值达到链表的长度 - 1时，跳出for循环。大体框架如下 : （注意——初始条件语句和循环控制语句都为2条语句）

    //以下代码仅作为演示，无实际意义
    int i,j,t;

    for (i = 0,p = pHead->pNext; i < len - 1; ++i, p = p->pNext)
    {
        for (j = i + 1,q = p->pNext; j < len; ++j,q = q->pNext)
        {
            if (p->data > q->data)
            {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }

        5.链表元素的插入和删除

                ①插入元素 : 

                1°在前面代码的基础上，定义insert_list方法进行链表元素的插入，最终希望达到的效果是——可以将一个新的结点插入到指定位置结点的前面（原先该位置处的结点挂载到新结点的后面）。insert_list方法需要传入三个实参——链表的头指针pHead；插入的新结点的位置pos（即position）；插入的新结点的值val。其中，插入新结点的位置必须从1开始（1表示首结点），即最多只能将新的结点插入到首结点的前面。
                2°显然，我们要对传入的实参进行真实性和有效性的判断。可利用以下代码进行校验 : 

    //以下代码仅作为演示，无实际意义

    int i = 0;
    
    while (NULL != p && i < pos - 1)
    {
        p = p->pNext;
        ++i;
    }

    if (NULL == p || i > pos - 1)
    {
        return false;
    }        

                解读 :
                1>while语句内部，i变量的自增和p指针的后移是同步发生的，而p指针一开始指向的是头结点，第一次进入while循环后，p指向了首结点，而i的值由0自增为1。因此，以此类推，最终i的值是几，p就指向了链表中的第几个结点。（注意，这里的第一个结点从首结点开始，因为首结点是存放链表中第一个有效数据的结点。)
                2>当i变量的值= pos - 1时，即p指向了要插入位置的前一个结点。配合if 条件语句，即可过滤掉插入位置为空的错误情况，比如说，假设目前链表中共4个结点（不包含首结点），那我们最最往后，也只能在第5个位置前加入新结点（即插入到了链表的最后）；如果链表中4个结点，你却想在第10个位置插入新结点，显然是不可能的。
                3>对于if 条件语句的第二个判断，是为了过滤掉实参pos为0或者负数的情况。pos必须从1开始，即最最往前，也只能插入到首结点的前面。如果pos = 0，那就相当于插入到了头结点的前面，而头结点是链表真正意义上的第一个结点，并且不存放有效数据，这么一来不是乱套了吗？
                3°继续，对于为pNew新结点动态分配的新的内存空间，我们要进行判断，如果为空，则退出程序（通过exit语句）。
                4°最后就是执行插入的步骤了，我们要先在方法体内定义一个PNODE类型的q变量，然后配合q变量来完成插入操作——先将val值赋值给新结点的val属性；再令q初始化为p的指针域；接着，p结点的pNext属性指向新结点；新结点pNew的pNext属性指向q。

                ②删除元素 : 

                1°删除元素的过程同插入元素在原理上类似。同样地，在前面代码的基础上，定义delete_list方法进行链表元素的插入。delete_list方法需要传入三个实参——链表的头指针pHead；要删除的结点在链表中的位置pos（即position）；要删除元素的值的地址值&pVal。
                2°对pos实参的校验同上。不一样的是，我们这次要将while 循环的判断语句中的"NULL != p"改为"NULL != p->pNext"，同时将if 条件语句中的"NULL == p"改为"NULL == p->pNext"。（注意，这么改仅仅是更改了要判断的结点，p本身的指针仍然是pos位置的前一个结点，不变）。这么做的目的是因为——原先我们插入元素时，只需要指定插入位置处的前一个结点是否为空；而删除元素时，我们不但需要知道要删除元素的前一个结点是否为空，还需要知道要删除的结点是否为空。
                while循环判断条件的更改，可以使我们直接从头结点开始判断，最后一次进入while循环判断的就是pos位置的前一个结点是否为空，即，p最后还是指向的pos位置的前一个结点，但是判断语句相比插入元素时提前了一个结点。if语句判断条件的更改，可以判断要删除的结点是否为空。
                3°相比插入元素来看，我们不再需要使用malloc函数来动态分配空间，而是直接执行删除操作即可。先令q指向要删除的结点（即p结点的后一个结点）；然后将要删除的结点的值赋给*pVal；接着，令p指向p结点的后两个元素，即q的下一个元素；最后，利用free函数释放q结点的空间，并令其为NULL。

        6.代码演示

                代码如下 : 

# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
# include <stdbool.h>

typedef struct Node         //定义结点数据类型
{
    int data;
    struct Node * pNext;
} NODE, * PNODE;

//函数声明
PNODE create_list(void);                            //链表的创建
void traverse_list(PNODE pHead);                    //链表的遍历
bool is_empty(PNODE pHead);                         //判断链表是否为空
int size_ofList(PNODE pHead);                       //获取链表当前的长度
void sort_list(PNODE pHead);                        //对链表进行排序
bool insert_list(PNODE pHead, int pos, int val);    //在链表指定位置插入指定值的结点
bool delete_list(PNODE pHead, int pos, int * pVal); //

int main(void) 
{
    PNODE pHead = NULL;     //初始化头指针
    int val_0,val_1;
    int pos_0,pos_1;

    pHead = create_list();  //创建链表，并将链表第一个结点的地址返回给头指针。
    traverse_list(pHead);   //遍历链表
    printf("-------------------------------------------------------------\n");

    if (is_empty(pHead))    //判断链表是否为空
        printf("\n链表为空!\n");
    else
        printf("\n链表不为空！\n");

    printf("链表中元素的个数 = %d\n", size_ofList(pHead));  //获取链表的长度
    printf("-------------------------------------------------------------\n");

    sort_list(pHead);       //对链表进行排序
    printf("正向排序后的链表: \n");
    traverse_list(pHead);
    printf("-------------------------------------------------------------\n");

    printf("请输入你要插入的新结点的值：");
    scanf("%d", &val_0);
    printf("你想将新结点插入链表中的哪个位置：");
    scanf("%d", &pos_0);
    insert_list(pHead, pos_0, val_0);   //在链表中的指定位置处插入指定值的新结点
    printf("插入元素后的链表：\n");
    traverse_list(pHead);
    printf("-------------------------------------------------------------\n");

    printf("请输入你要删除的结点的位置：");
    scanf("%d", &pos_1);
    delete_list(pHead, pos_1, &val_1);
    printf("删除元素后的链表：\n");
    traverse_list(pHead);

    return 0;
}

PNODE create_list(void)
{
    int length;     //存放链表中有效长度的个数
    int i;          //循环变量
    int value;      //临时存放当前结点的值。

    /*
        为头结点分配内存空间，并将其地址值返回给头指针，如下。
    */
    PNODE pHead = (PNODE) malloc(sizeof(NODE)); 
    if (NULL == pHead)
    {
        printf("动态分配失败！程序即将终止！");
        exit(-1);   //0表示正常退出，非0表示非正常退出。
    }

    /*
        定义尾指针，初始化并使其指向头结点。
        即此时头指针和尾指针都指向了头结点。如下 : 
    */
    PNODE pTail = pHead;
    pTail->pNext = NULL;    //使头结点的指针域为空，该步骤也可放在头指针的定义之后。


    printf("请确定你要创建的链表结点的个数：length = ");
    scanf("%d", &length);
    
    for (i = 0; i < length; ++i)
    {
        printf("请输入第%d个结点的值：", i + 1);
        scanf("%d", &value);

        PNODE pNew = (PNODE) malloc(sizeof(NODE));
        if (NULL == pNew)
        {
            printf("动态分配失败！程序即将终止！");
            exit(-1); 
        }

        pNew->data = value;     //将输入的值存入新结点的数据域中。
        pTail->pNext = pNew;    //令前一个结点指向新结点。
        pNew->pNext = NULL;     //令新结点的指针域为空。
        pTail = pNew;           //令尾指针后移，尾指针始终指向当前的尾结点。
    }

    return pHead;
}

void traverse_list(PNODE pHead)
{
    PNODE p = pHead->pNext;     //从首结点开始遍历。
    printf("\n=========遍历链表：==========\n");
    while(NULL != p)
    {
        printf("%d", p->data);
        p = p->pNext;
        printf("\t");
    }
    printf("\n=============================\n");

    return;
}

bool is_empty(PNODE pHead)
{
    if (NULL == pHead->pNext)
        return true;
    else
        return false;
}

int size_ofList(PNODE pHead)
{
    PNODE p = pHead->pNext;
    int cnt = 0;            //初始化cnt变量。

    while (NULL != p)
    {
        ++cnt;
        p = p->pNext;
    }

    return cnt;
}

void sort_list(PNODE pHead) 
{
    int len = size_ofList(pHead);
    int i,j,t;
    PNODE p,q;

    for (i = 0,p = pHead->pNext; i < len - 1; ++i, p = p->pNext)
    {
        for (j = i + 1,q = p->pNext; j < len; ++j,q = q->pNext)
        {
            if (p->data > q->data)
            {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
 
    return;
}

bool insert_list(PNODE pHead, int pos, int val) //pos = position
{
    int i = 0;
    PNODE q,p = pHead;
    
    while (NULL != p && i < pos - 1)    //判断要插入位置的前一个结点是否为空
    {
        p = p->pNext;                   //此处i的自增和p指针的后移同时进行
        ++i;                            //即i是几，p就指向链表中第几个结点（从首结点开始算第一个)
    }

    if (NULL == p || i > pos - 1)       //后一个条件用于防止pos为负数和0的情况
        return false;

    PNODE pNew = (PNODE) malloc(sizeof(NODE));  //为新的结点分配内存空间
    if (NULL == pNew)
    {
        printf("为新结点动态分配内存失败！\n");
        exit(-1);
    }

    pNew->data = val;
    q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;

    return true;
}

bool delete_list(PNODE pHead, int pos, int * pVal)
{
    int i = 0;
    PNODE q,p = pHead;
    
    while (NULL != p->pNext && i < pos - 1)    //判断要删除的结点的前一个结点是否为空
    {
        p = p->pNext;                   
        ++i;                            
    }

    if (NULL == p->pNext || i > pos - 1)              //判断要删除的结点是否为空
        return false;

    q = p->pNext;
    *pVal = q->data;
    p->pNext = q->pNext;
    free(q);
    q = NULL;

    return true;
}

                运行效果 : (如下GIF图)

---

五、完结撒❀

        🆗，以上就是关于单链表的全部内容了。链表是数据结构与算法中相当有分量的一部分内容。只有掌握了链表才能更好地学习之后的栈和队列，等等。up之后可能也会出一些算法题的讲解，不过目前在写java的博文，有时间后或许会考虑。今天就先到这里，感谢阅读！