数据结构基础：链表——单向链表

m0_74317917

973人浏览 · 2025-08-02 21:06:23

m0_74317917 · 2025-08-02 21:06:23 发布

从本篇开始将记录一些数据结构的学习，C语言阶段已经结束，本文主要认识了链表的相关概念和单向链表的一些相关操作，以及工程管理工具makefile，便于工程项目的创建，建议使用VS Code来进行程序编写

一、数据结构相关概念

1 概念

程序 == 数据结构 + 算法

描述数据存储和操作的结果
操作数据对象的方法

2 衡量代码的质量和效率

写程序的初衷：

1.无论代码操作数据量多大，希望程序代码的运行时间保持恒定

2.随着数据量的增长，程序运行时间缓慢增长；

随着数据量的增长，程序运行时间快速增长（不希望）

1.2.1 时间复杂度

定义：

数据量的增长与程序运行时间的增长所呈现的比例函数关系，称为时间渐进复杂度函数，也简称为时间复杂度

常见的时间复杂度：

常见的时间复杂度(由低到高)

O(1) ：程序运行时间维持恒定
O(logn) ：程序刚开始运行时间可能增长较快，但经过一定数据量后，程序运行时间趋于恒定
O(n) ：程序运行时间随数据量增长呈现固定的比例关系
O(nlogn)
O(n ^ 2)
O(n ^ 3)
O(2 ^ n)

1.2.2 空间复杂度

定义：

数据量的增长与程序所占空间的增长所呈现的比例函数关系，称为空间复杂度

通常情况下更二者比较更倾向时间复杂度更好

3 数据结构

1. 逻辑结构

线性结构：表（描述一对一的关系）
非线性结构：树（描述一对多的关系）、图（描述多对多的关系）【在接下来的学习中主要学习表和树两部分】

2. 存储结构

顺序存储
链式存储
散列存储
索引存储

3.常见的数据结构

顺序表
链式表
顺序栈
链式栈
顺序队列
链式队列
二叉树
邻接表（描述图形结构）
邻接矩阵（描述图形结构）

二、链表

1 链表

顺序表（数组）特点：

存储空间连续，方便了元素的访问，但无法利用很小的空间，必须是连续的大空间，导致空间利用率较低

顺序表元素必须为有限的（不存在无限连续的空间）

插入和删除的效率较低

链表（前存数据，后存下一个节点的地址）特点：时间复杂度为O（1）

存储空间不需要连续，可以利用一些小的存储空间，但不方便访问元素

链表元素可以没有上限

链表的插入和删除效率较高

2 链表的分类

1.单向链表

只能从链表节点向后一个节点找，最后一个节点地址置为NULL

访问链表元素的方向是单向的

2.双向链表

能够通过前一个链表节点找到后一个链表节点

3.循环链表

能够通过第一个链表节点快速找到最后一个链表节点，能够通过最后一个链表节点快速找到第一个链表节点

4.内核链表

Linux内核所采用的一种通用的链表结构

3 单向链表（有头链表）

对链表的操作：创建、销毁、插入、删除、修改、查找

1. 定义链表节点的类型（VS Code中ctrl+s保存）


Typedef int datatype;    //int , char , double , float等类型可替换


//定义结构体

/*链表节点的类型*/
struct node{
      datatype data;       //链表中存放数据的类型（空间）  “数据域”
      struct node *pnext;        //存放下一个节点的地址//指针本身具有8个字节，可以用本身       “地址域”

}linknode;

2. 空链表的创建

步骤：

创建一个空的链表节点
data不需要赋值（最好赋值），空白节点不存放数据，主要为了保证链表操作的便利性
pnext必须赋值为NULL，表示该节点为最后一个节点
将节点地址返回

/* 创建一个空链表 */
linknode *create_empty_linklist(void)
{
    linknode *ptmpnode = NULL;
    
    ptmpnode = malloc(sizeof(linknode));
    if (NULL == ptmpnode)
    {
        perror("fail to malloc");
        return NULL;
    }
    
    ptmpnode->pnext = NULL;
    return ptmpnode;
}

4 链表的头插法

在链表开头插入一个元素

步骤：

申请新的节点空间
将存放的数据让入新申请的数据空间中
将新申请节点的pnext赋值为空白节点的pnext
将空白节点pnext赋值为新申请节点

/* 插入一个节点 */
int insert_head_linklist(linknode *phead, datatype tmpdata)
{
    linknode *ptmpnode = NULL;
    
    //申请空间 
    ptmpnode = malloc(sizeof(linknode));
    if (NULL == ptmpnode)
    {
        perror("fail to malloc");
        return -1;
    }

    //存放数据
    ptmpnode->data = tmpdata;

    //存放下一个节点地址
    ptmpnode->pnext = phead->pnext;
    
    //更新空白的节点的pnext
    phead->pnext = ptmpnode;

    return 0;
}

5 链表的遍历

访问链表中每个节点元素

方法一：多用于遍历链表中所有节点元素
方法二：多用于找到链表最后一个节点

void show_linklist(linknode *phead)
{
    linknode *ptmpnode = NULL;

    ptmpnode = phead->pnext;
    while (ptmpnode != NULL)
    {
        printf("%d ", ptmpnode->data);
        ptmpnode = ptmpnode->pnext;
    }
    printf("\n");

    return;
}

6 链表元素删除

从链表中删除指定的元素

步骤：

定义两个指针ptmpnode用来遍历链表查找要删除的节点元素，pprenode永远只想ptmpnode的前一个节点
当ptmpnode找到要删除的节点元素，让pprenode->pnext赋值为ptmpnode->pnext 将要删除的节点元素释放
让ptmpnode判断下一个节点元素是否要删除，直到该指针指向NULL为止

/* 删除指定的链表节点元素 */

int delete_linklist(linknode *phead, datatype tmpdata)
{
    linknode *pprenode = NULL;
    linknode *ptmpnode = NULL;

    pprenode = phead;
    ptmpnode = phead->pnext;
    while (ptmpnode != NULL)
    {
        if (ptmpnode->data == tmpdata)
        {
            pprenode->pnext = ptmpnode->pnext;
            free(ptmpnode);
            ptmpnode = pprenode->pnext;
        }
        else
        {
            ptmpnode = ptmpnode->pnext;
            pprenode = pprenode->pnext;
        }
        }

    return 0;
}

7 链表的查找

在链表中找到指定的第一个元素

步骤：

沿用遍历思想，每次访问一个节点元素判断是否为要找的节点
符合条件返回该节点地址
到最后依旧没有找到符合条件的节点，返回NULL

/* 找到符合要求的第一个元素节点地址 */
linknode *find_linklist(linknode *phead, datatype tmpdata)
{
    linknode *ptmpnode = NULL;
    ptmpnode = phead->pnext;
    while (ptmpnode != NULL)
    {
        if (ptmpnode->data == tmpdata)
        {
            return ptmpnode;
        }
        ptmpnode = ptmpnode->pnext;
    }
    return NULL;
}

8 链表的修改

沿用遍历思想，找到符合条件的元素修改为新的值

/* 将符合条件的旧值修改为新值 */
int update_linklist(linknode *phead, datatype olddata, datatype newdata)
{
    linknode *ptmpnode = NULL;
    ptmpnode = phead->pnext;
    while (ptmpnode != NULL)
    {
        if (ptmpnode->data == olddata)
        {
            ptmpnode->data = newdata;
        }
        ptmpnode = ptmpnode->pnext;
    }
    return 0;
}

9 链表的尾插

步骤：

申请节点空间
将数据存放到节点中
将节点中地址赋值为NULL
找到最后一个节点
最后一个节点的pnext赋值为新申请节点

/* 尾插法插入节点元素 */
int insert_tail_linklist(linknode *phead, datatype tmpdata)
{
    linknode *ptmpnode = NULL;
    linknode *plastnode = NULL;
  
    //申请节点
    ptmpnode = malloc(sizeof(linknode));
    if (NULL == ptmpnode)
    {
        perror("fail to malloc");
        return -1;
    }

    //将节点空间中的元素赋值
    ptmpnode->data = tmpdata;
    ptmpnode->pnext = NULL;

    //找到最后一个节点元素
    plastnode = phead;
    while (plastnode->pnext != NULL)
    {
        plastnode = plastnode->pnext;
    }

    //将最后一个节点的pnext指向新申请节点
    plastnode->pnext = ptmpnode;
    
    return 0;
}

10 链表的销毁

将所有的链表节点空间都释放掉

步骤：

定义两个指针pfreenode和ptmpnode都指向头结点
ptmpnode向后走
再释放pfreenode指向的节点
再将pfreenode指向ptmpnode指向的空间

/* 链表的销毁 */
int destroy_linklist(linknode **pphead)
{
    linknode *pfreenode = NULL;
    linknode *ptmpnode = NULL;

    ptmpnode = *pphead;
    pfreenode = *pphead;
    while (ptmpnode != NULL)
    {
        ptmpnode = ptmpnode->pnext;
        free(pfreenode);
        pfreenode = ptmpnode;
    }
    *pphead = NULL;

    return 0;
}

11 查找链表中间节点

快指针每次走2步，慢指针每次都1步
快指针走到末尾，慢指针走到中间

/* 查找链表中间节点 */
linknode *find_midnode(linknode *phead)
{
    linknode *pslow = NULL;
    linknode *pfast = NULL;

    pslow = pfast = phead->pnext;
    while (pfast != NULL)
    {
        pfast = pfast->pnext;
        if (NULL == pfast)
        {
            break;
        }
        pfast = pfast->pnext;
        if (NULL == pfast)
        {
            break;
        }
        pslow = pslow->pnext;
    }

    return pslow;
}

12 查找链表倒数第k个节点

快指针先走k步
慢指针和快指针每次走一步
快指针到达末尾，慢指针少走k步，即倒数第k个元素

/* 查找链表倒数第k个节点 */
linknode *find_last_kth_node(linknode *phead, int k)
{
    int i = 0;
    linknode *pfast = NULL;
    linknode *pslow = NULL;
    pfast = phead->pnext;
    
    for (i = 0; i < k && pfast != NULL; i++)
    {
        pfast = pfast->pnext;
    }

    if (NULL == pfast)
    {
        return NULL;
    }

    pslow = phead->pnext;
    while (pfast != NULL)
    {
        pfast = pfast->pnext;
        pslow = pslow->pnext;
    }
    
    return pslow;
}

13 不知道头结点地址如何删除链表中间节点

将指针指向的下一个节点的值覆盖当前节点的值
删除下一个节点

/* 删除指定节点 */
int delete_linknode(linknode *ptmpnode)
{
    linknode *pnextnode = NULL;

    pnextnode = ptmpnode->pnext;
    ptmpnode->data = pnextnode->data;
    ptmpnode->pnext = pnextnode->pnext;
    free(pnextnode);

    return 0;
}

14 链表的倒置

将链表中的所有元素倒置

将原链表断开
将所有的元素依次使用头插法插入

/* 链表倒置 */
int reverse_linklist(linknode *phead)
{
    linknode *pinsertnode = NULL;
    linknode *ptmpnode = NULL;

    //将链表从头结点处断开
    ptmpnode = phead->pnext;
    phead->pnext = NULL;

    //依次将所有元素使用头插法插入链表中
    while (ptmpnode != NULL)
    {
        pinsertnode = ptmpnode;
        ptmpnode = ptmpnode->pnext;
        pinsertnode->pnext = phead->pnext;
        phead->pnext = pinsertnode;
    }

    return 0;
}

15 链表的排序

1. 冒泡排序

步骤：

采用冒泡排序思想，定义两个指针，相邻两个元素比较
指针循环向后走，直到ptmpnode2为NULL，即等于pend，循环停止
pend赋值为tmpnode1的节点地址
下一轮就可以少比1次
循环将所有大的元素找到，剩余一个小的元素即可

/* 链表的冒泡排序 */
int bubble_sort_linklist(linknode *phead)
{
    linknode *ptmpnode1 = NULL;
    linknode *ptmpnode2 = NULL;
    linknode *pend = NULL;
    datatype tmpdata;

    if (NULL == phead->pnext || NULL == phead->pnext->pnext )
    {
        return 0;
    }

    while (1)
    {
        ptmpnode1 = phead->pnext;
        ptmpnode2 = phead->pnext->pnext;
        if (pend == ptmpnode2)
        {
            break;
        }

        while (ptmpnode2 != pend)
        {
            if (ptmpnode1->data > ptmpnode2->data)
            {
                tmpdata = ptmpnode1->data;
                ptmpnode1->data = ptmpnode2->data;
                ptmpnode2->data = tmpdata;
            }
            ptmpnode1 = ptmpnode1->pnext;
            ptmpnode2 = ptmpnode2->pnext;
        }
        pend = ptmpnode1;
    }

    return 0;
}

2. 选择排序

步骤：

pswapnode指向要交换的节点
pminnode假设的最小值
ptmpnode和后续节点比较

/* 链表的选择排序 */
int select_sort_linklist(linknode *phead)
{
    linknode *pswapnode = NULL;
    linknode *ptmpnode = NULL;
    linknode *pminnode = NULL;
    datatype tmpdata;

    if (NULL == phead->pnext || NULL == phead->pnext->pnext)
    {
        return 0;
    }

    pswapnode = phead->pnext;
    while (pswapnode->pnext != NULL)
    {
        pminnode = pswapnode;
        ptmpnode = pswapnode->pnext;
        while (ptmpnode != NULL)
        {
            if (ptmpnode->data < pminnode->data)
            {
                pminnode = ptmpnode;
            }
            ptmpnode = ptmpnode->pnext;
        }
        if (pswapnode != pminnode)
        {
            tmpdata = pswapnode->data;
            pswapnode->data = pminnode->data;
            pminnode->data = tmpdata;
        }
        pswapnode = pswapnode->pnext;
    }

    return 0;
}

16 判断链表是否有环

主要解决以下三个问题：

判断链表是否有环
计算环的环长
找到环入口的位置

解决方法：

1. 链表是否有环：

定义两个指针：快指针（每次走2步）和慢指针（每次走1步）
快指针 - 慢指针 == 环长即相遇，快指针和慢指针相等即为链表有环

2. 计算环长：

定义一个指针从环相遇点开始走一圈，直到走该该节点为止
没走一个节点计数，最终可得到环长

3. 获得环的入口位置：

需要公式推导：

a：起始点到环入口的距离 b：环入口到相遇点的距离 c：相遇点到环入口的距离

l：环长 s：慢指针走的步数

l = b + c; s = a + b;

2*s = a + b + n*l;

2(a+b) = a + b + n*l

a + b = n*l

a + (l-c) = n*l;

a + l - c = n*l;

a - c = (n-1)*l;

a = c + (n-1)*l;

定义一个指针从相遇点开始每次走一步，定义一个指针从开头每次走一步
两个指针相遇的位置即为环入口位置

/*  1.判断链表是否有环
    2.计算环长
    3.找到环的入口位置
*/
int circle_linklist(linknode *phead, int *pis_circle, int *pcirlen, linknode
**ppnode)
{
    linknode *pfast = NULL;
    linknode *pslow = NULL;
    linknode *ptmpnode = NULL;
    linknode *pstartnode = NULL;
    int cnt = 1;

    /* 判断是否有环 */
    pfast = phead->pnext;
    pslow = phead->pnext;
    while (1)
    {
        pfast = pfast->pnext;
        if (NULL == pfast)
        {
            break;
        }
        pfast = pfast->pnext;
        if (NULL == pfast)
        {
            break;
        }
        pslow = pslow->pnext;
        if (pfast == pslow)
        {
            break;
        }
    }

    if (NULL == pfast)
    {
        *pis_circle = 0;
        return 0;
    }
    else
    {
        *pis_circle = 1;
    }

    /* 统计环长 */
    ptmpnode = pslow->pnext;
    while (ptmpnode != pslow)
    {
        cnt++;
        ptmpnode = ptmpnode->pnext;
    }
    *pcirlen = cnt;

    /* 找到环入口 */
    pstartnode = phead->pnext;
    ptmpnode = pslow;
    while (pstartnode != ptmpnode)
    {
        pstartnode = pstartnode->pnext;
        ptmpnode = ptmpnode->pnext;
    }
    *ppnode = ptmpnode;

    return 0;
}

三、Makefile

1 Makefile

工程管理工具，主要用于管理代码的编译

Makefile可以根据文件中的规则来选择符合条件的代码完成编译
Mekefile能够根据依赖关系和文件修改的时间戳来决定哪些代码需要编译，哪些代码不需要编译

2 Makefile使用规则

在工程目录下，创建一个Makefile或makefile的文件
在makefiel中编写对应的文件编译规则
在工程目录中使用make来调用makefile的规则来完成代码编译
```
make      //直接make编译代码
```
编译代码成功后，即可运行可执行程序

3 makefile语法规则

要生成的文件：依赖的所有文件

生成命令方式

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

小参数・大码力・易部署 | Qwen3.6-27B上线魔乐社区，基于昇腾的部署教程来了

继一周前模型开源发布后，千问再度开源Qwen3.6-27B —— 一个拥有270亿参数的稠密多模态模型，也是社区呼声最高的模型规格。Qwen3.6-27B 依然支持多模态思考与非思考模式，在智能体编程方面达到了旗舰级表现，全面超越前代开源旗舰 Qwen3.5-397B-A17B（总参数397B / 激活参数17B的MoE模型）。作为稠密架构，它无需MoE路由即可部署，是开发者在实用、可广泛部署规模