C语言数据结构——链表

链表包括单链表，双链表，循环链表等。

而今天要说的是单链表，它是一个线性表，它在内存中是无序的，由一个个指针来连接。

图示：

小方块代表的就是存储的数据，箭头就是指向下一个数据存储地的指针，有了这个，数据才可以串联在一起。

一、实现链表

实现链表这个数据本身还是不难的，最重要的是实现各个方法，如排序，增删改查操作等。

C语言实现链表：

/**
 * @brief 手写单链表(有头节点)
 * 
 */
#include <stdio.h>
typedef int bool;//自定义布尔变量，因为C语言没有布尔这个数据类型
#define true 1//使用数字1来表示true，实际上在别的语言中1就是true
#define false 0//同理
typedef struct{
    int value;//当前节点存储的值
    LinckList* next;//指向下一节点的指针
    //int length;//链表长度，总共有多少节点
    //这其实算是偷懒了，不带上也可以遍历单链表来记录长度
    //弊端每个结构体是多占了一个int字节的内存，不建议携带
}LinckList;

value：代表的就是上面图的小方块，存储这int类型的值

next：指向下一个链表的指针、

二、实现一些功能

作为一种数据结构，我们既然实现了它，那么它的功能我们也实现一遍才好。

其实并不难，不要害怕，我会细说的。

1. 初始化

初始化链表，使指针指向null，使数据初始化为0。

/**
 * @brief 初始化单链表
 * 
 * 对节点赋值值，下一节点的指针指向NULL
 * 
 * @param LinckList 
 * @param data 初始化传入的值
 */
void InitLinck(LinckList* LinckList, int data)
{
    LinckList->value = data;//将传入的参数赋值
    LinckList->next = NULL;//默认只有一个节点
}

还是比较简单的。

2. 增

给一个数据，将它添加到链表中。添加方式有很多种，添加到头部，添加到尾部，添加到指定位置。我会一一讲解。

1. 将数据添加到链表尾部（一般人的思路就是这个）

使用遍历的方法，直接遍历到最后一个，然后创建一个链表数据类型，让最后节点的链表指向新链表，并对新链表赋值。

/**
 * @brief 将指定元素插入最后节点
 * 1. 赋值头节点
 * 2. 遍历链表
 * 3. 遍历完声明新节点
 * 4. 新节点值赋值data
 * 5. 最后节点指向新节点
 * 
 * @param linckList 可以传参指针和引用
 * @param data 
 */
void InsertDataLast(LinckList* linckList, int data)
{
    LinckList* p = linckList;//把头链表记录一下，不然直接遍历链表的话，最后链表就是遍历完的样子
    while (p->next)//当括号为p时是遍历所有节点，最后p为NULL
    {
        p = p->next;
    }
    LinckList root;
    root.value = data;
    p->next = &root;
}

2. 将数据添加到链表头部

1. 声明新节点
2. 让新节点的值为头节点的
3. 让新节点的指向针为头节点的
4. 头节点的值为data，指向新节点

/**
 * @brief 将数据插入链表的头部
 * 1. 声明新节点
 * 2. 让新节点的值为头节点的
 * 3. 让新节点的指向针为头节点的
 * 4. 头节点的值为data，指向新节点
 * 
 * @param linckList 可以传参指针和引用
 * @param data 
 */
void InsertDataFirst(LinckList* linckList, int data)
{
    LinckList p;
    p.value = linckList->value;
    p.next = linckList->next;
    linckList->next = &p;
    linckList->value = data;
}

3. 将数据添加到指定位置

1. 找到那个节点
2. 新建一个结构体
3. 将data值传入结构体
4. 将第index个节点的next的值指向结构体
5. 将结构体的next的值指向原链表第index+1个节点

/**
 * @brief 向链表中的指定节点插入指定元素
 * 
 * 大致的思路就是：
 * 1. 找到那个节点
 * 2. 新建一个结构体
 * 3. 将data值传入结构体
 * 4. 将第index个节点的next的值指向结构体
 * 5. 将结构体的next的值指向原链表第index+1个节点
 * 
 * @param linckList 
 * @param data 
 */
LinckList* InsertData(LinckList* linckList, int index, int data)
{
    LinckList* p = linckList;//保存主节点，用于返回
    LinckList linck;//新建单链表节点
    InitLinck(&linck, data);//初始化此单链表节点，将data传入
    // linck.value = data;效果上同
    for (int i = 1; i < index; i++)
    {
        linckList = linckList->next;//将主节点遍历到第index-1个
    }
    linck.next = linckList->next;//将结构体指向节点的第index个节点
    linckList->next = &linck;//将第index-1个节点
    return p;
}

3. 删

删除链表中的元素，就不写删除头部和尾部的了，直接写删除指定元素

1. 遍历链表
2. 遍历到指定元素的上一个节点，将节点指向下下一节点即可

/**
 * @brief 删除指定元素
 * 1. 遍历链表
 * 2. 遍历到指定元素的上一个节点，将节点指向下下一节点即可
 * 
 * @param linckList 
 * @param data 
 */
void DeleteData(LinckList* linckList, int data)
{
    if (linckList->value == data)
    {
        //如果第一个就是，那就直接吧第一个删了
        linckList->value = linckList->next->value;
        linckList = linckList->next;
    }
    LinckList* p = linckList;
    for (int i = 1; i < GetLength(linckList); i++)
    {
        if (linckList->next->value == data)
        {
            linckList->next = linckList->next->next;
            break;
        }
        linckList = linckList->next;
    }
}

哦对了，还有删除整个链表的。

和初始化差不多，将指针指向null，数据改掉就行了。

/**
 * @brief 销毁链表
 * 
 * 和初始化的方法差不多
 * 
 * @param LinckList 
 */
void DestoryLinck(LinckList* LinckList)
{
    LinckList->value = 0;//存储值置0
    LinckList->next = NULL;//下一节点指向NULL
}

4. 改

修改链表中的值。

方法：遍历+判断

/**
 * @brief 修改某个元素为另一个元素
 * 遍历+判断
 * 
 * @param linckList 
 * @param oldData 
 * @param newData 
 */
LinckList* UpdataData(LinckList* linckList, int oldData, int newData)
{
    LinckList* p = linckList;
    while (p)
    {
        if (p->value == oldData)
        {
            p->value = newData;
            break;
        }
    }
    return p;
}

5. 查

查找某个元素，感觉作用不大，所以这个就写成将整个链表输出成一个数组吧。

方法：

1. 遍历输出
2. 因为不需要修改数组，所以直接传linckList。

/**
 * @brief 输出整个链表存储的值
 * 1. 遍历输出
 * 2. 因为不需要修改数组，所以直接传linckList
 * @param linckList 
 */
void PrintLinckList(LinckList linckList)
{
    LinckList*p = &linckList;
    printf("[");
    while (p->next != NULL)//遍历到最后一个是因为要把最后一个的 ”, “去掉
    {
        printf("%d, ", linckList.value);
        p = p->next;
    }
    printf("%d", p->value);
    printf("]\n");
}

输出的形式就是像：[1, 2, 3, 4]这样的

6. 获取长度

这个实现起来也很简单，遍历链表，使用变量记录遍历次数即可。

1. 赋值原来的头节点
2. 定义一个int类型的变量表示长度
3. 遍历链表，长度每次循环+1
4. 返回长度

/**
 * @brief 获取链表的长度
 * 
 * 1. 赋值原来的头节点
 * 2. 定义一个int类型的变量表示长度
 * 3. 遍历链表，长度每次循环+1
 * 4. 返回长度
 * 
 * @param linckList 
 * @return length 数组长度
 */
int GetLength(LinckList* linckList)
{
    int length = 0;
    LinckList* p = linckList;
    while (p)
    {
        p = p->next;
        length++;
    }
    return length;
}

结语

积少成多，聚沙成塔，每天走一点，在长的路也能走完。