当前位置： 首页 > article >正文

12-C语言单向链表

article 2025/3/2 2:10:19

一、链表的概述

1.链表与数组对比

  1. 遍历数组中的数据，查询数据比较方便，但往数组中插入、删除数据需要移动大量数据；
  2. 相反。链表遍历、查询数据不方便，但是插入、删除数据比较方便，不需要移动大量数据，直接在指定位置插入或删除指定节点，这与链表节点的结构有关；
  3. 数组的一个个元素在内存中是连续的，链表的节点间内存不连续。

2.链表节点

2.1链表节点的概念

链表的节点：用来保存数据信息的，分为数据域、指针域两个部分；数据域用来存放核心数据；指针域用来存放下一个节点的地址。

  • 链表一般分为无头链表和有头链表：
    1. 无头链表：即由一个指针变量保存首个节点的起始地址；
    2. 有头链表：由一个节点的指针域保存首节点的起始地址，且该节点没有数据域，只有指针域。

2.2链表节点类型定义

链表节点类型定义和结构体一样，只不过分为了数据域和指针域，指针域是一个结构体指针成员。

  • 代码演示
typedef struct stu
{
    // 定义数据域
    int num;
    char name[32];
    float score;

    // 定义指针域
    struct stu *next;
}STU;

二、单向链表应用

1.单向链表

单向链表又叫静态链表，它是一个接着一个节点依次单向排列分布的，上一个节点的指针域指向下一个节点的起始地址，最后一个节点的指针域指向NULL。

  • 创建一个单向链表
int main()
{
    // 定义5个节点
    STU stu1 = {"小明", 18, 90.0f, NULL};
    STU stu2 = {"小王", 20, 75.5f, NULL};
    STU stu3 = {"小红", 19, 87.0f, NULL};
    STU stu4 = {"小当家", 18, 86.5f, NULL};
    STU stu5 = {"小魔仙", 21, 88.8f, NULL};

    // 定义节点头
    STU *stus = &stu1;
    // 构建链表
    stu1.next = &stu2;
    stu2.next = &stu3;
    stu3.next = &stu4;
    stu4.next = &stu5;

    // 遍历链表
    STU *p = stus;
    while (p != NULL)
    {
        printf("姓名：%-7s，年龄：%-2d，分数：%.2f\n", p->name, p->age, p->score);
        p = p->next;
    }
    return 0;
}
  • 运行结果
姓名：小明   ，年龄：18，分数：90.00
姓名：小王   ，年龄：20，分数：75.50
姓名：小红   ，年龄：19，分数：87.00
姓名：小当家 ，年龄：18，分数：86.50
姓名：小魔仙 ，年龄：21，分数：88.80
  • 说明：
    1. 定义节点和定义结构体变量一样，初始化先将 next 指向 NULL；
    2. 定义一个节点头指针变量指向第一个节点，然后第一个节点的 next 指向下一个节点，反复执行，直到最后一个节点，将最后一个节点的 next 指向NULL；
    3. 在遍历链表的时候，通过一个临时指针变量保存链表头，用这个临时指针变量去遍历，因为链表头不能随意改变指向；
    4. 每遍历一个节点就将临时指针变量指向当前节点的下一个节点的起始位置。

2.单向链表综合案例：简易的学生信息管理系统

项目要求：通过单项链表，开发一个简易的学生管理系统，系统功能包含学生信息的增删改查等基本操作，通过输入关键词命令调用相应的功能函数来满足用户需求。

2.1项目基本框架

在开始具体的功能函数前，先整理思路，理清大致框架，想好需要添加哪些功能，然后再逐一去实现这些功能函数。

  • 菜单界面和主函数框架
// 一个简单的学生管理系统
typedef struct stu {
    // 定义数据域
    int num;
    char name[32];
    float score;

    // 定义指针域
    struct stu *next;
} STU;

// 定义函数，打印菜单界面
void func_list(void) {
    printf("-----------------------------------\n");
    printf("-->insert:插入学生信息            |\n");
    printf("-->print:遍历信息                 |\n");
    printf("-->search:查询某个学生的信息      |\n");
    printf("-->delete:删除某个学生的信息      |\n");
    printf("-->free:删除所有学生              |\n");
    printf("-->reverse:链表逆序               |\n");
    printf("-->sort:链表排序                  |\n");
    printf("-->quit:退出整个程序              |\n");
    printf("-----------------------------------\n");
    return;
}

int main() {
    // 调用函数：打印功能菜单
    func_list();

    // 获取指令
    char cmd[16] = "";
    while(1)
    {
        printf("请输入要操作的指令：");
        scanf("%s", cmd);

        if (strcmp("insert", cmd) == 0)
        {
            printf("插入学生信息\n");
        }
        else if (strcmp("print", cmd) == 0)
        {
            printf("遍历信息\n");
        }
        else if (strcmp("search", cmd) == 0)
        {
            printf("查询某个学生的信息\n");
        }
        else if (strcmp("delete", cmd) == 0)
        {
            printf("删除某个学生的信息\n");
        }
        else if (strcmp("free", cmd) == 0)
        {
            printf("删除所有学生\n");
        }
        else if (strcmp("reverse", cmd) == 0)
        {
            printf("链表逆序\n");
        }
        else if (strcmp("sort", cmd) == 0)
        {
            printf("链表排序\n");
        }
        else if (strcmp("quit", cmd) == 0)
        {
            printf("程序已经退出\n");
            break;
        }
        else
        {
            printf("请输入有效命令\n");
        }
    }
    return 0;
}
  • 运行结果
-----------------------------------
-->insert:插入学生信息            |
-->print:遍历信息                 |
-->search:查询某个学生的信息      |
-->delete:删除某个学生的信息      |
-->free:删除所有学生              |
-->reverse:链表逆序               |
-->sort:链表排序                  |
-->quit:退出整个程序              |
-----------------------------------
请输入要操作的指令：insert
插入学生信息        
请输入要操作的指令：printf
请输入有效命令      
请输入要操作的指令：quit
程序已经退出
  • 说明：
    1. 因为学生信息包含的数据类型多样，因此通过结构体变量来存储学生信息，为了完成增删改查等复杂操作，通过链表的形式实现；
    2. 定义一个函数用来打印功能菜单；
    3. 主函数循环获取用户输入的命令，条件判断调用相应的功能函数。

2.2插入学生信息

2.2.1主函数
  • 主函数部分
int main() {
    // 调用函数：打印功能菜单
    func_list();
    // 定义一个链表头
    STU *head = NULL;

    // 获取指令
    char cmd[16] = "";
    while(1)
    {
        printf("请输入要操作的指令：");
        scanf("%s", cmd);

        if (strcmp("insert", cmd) == 0)
        {
            // 定义临时变量用于接收输入的学生信息
            STU stu_temp;
            int n = 0;
            printf("请输入要添加的学生的个数：");
            scanf("%d", &n);
            printf("请输入学生信息（学号 姓名 分数）：");

            // 调用函数：添加学生信息
            int i = 0;
            for (i = 0; i < n; i++)
            {
                scanf("%d %s %f", &stu_temp.num, stu_temp.name, &stu_temp.score);
                // 调用函数：添加学生信息
                // head = insert_func_head(head, stu_temp); // 头部插入
                // head = insert_func_tail(head, stu_temp); // 尾部插入
                head = insert_func_sequence(head, stu_temp); // 顺序插入
            }
            printf("已添加%d位学生信息\n", n);
        }
        else if (strcmp("print", cmd) == 0)
        {
            // 调用函数：打印学生信息
            print_func(head);
        }
        // .........省略其它功能
    }
}
  • 说明：
    1. 这里主函数部分列出了插入和打印的功能，其它功能代码省略；
    2. 因为很多功能函数都会用到链表头，因此把它定义在主函数最外层作用域下，为所有功能函数公有；
    3. 插入函数只负责插入功能，学生信息的获取在主函数完成，也可以单独封装一个获取学生信息的函数，将获取到的学生信息通过一个临时结构体变量，作为插入函数的实参传入。
2.2.2头部插入学生信息
  • 代码演示
// 定义函数：在头部插入学生信息
STU *insert_func_head(STU *head, STU stu_temp)
{
    // 申请堆区空间，存储一个学生的信息
    STU *new_stu = (STU *)malloc(sizeof(STU));
    if (NULL == new_stu)
    {
        printf("空间申请失败\n");
        return head;
    }

    // 将获取到的学生信息存入申请到的空间
    *new_stu = stu_temp;

    // 将新的学生节点插入链表
    // 链表为空
    if (NULL == head)
    {
        head = new_stu;
        new_stu->next = NULL;
    }
    // 链表不为空
    else
    {
        new_stu->next = head;
        head = new_stu;
    }
    return head;
}
  • 说明：
    1. 因为是插入信息，需要函数内部改变链表结构或者链表头的指向，因此应将 head 的地址传入，为一个二级指针。但为了方便操作，也可以传入一级指针，然后将函数内部的临时局部变量 head 保存的头节点的地址返回，主函数用 head 接收，保存新的链表头节点位置，即使函数调用结束，临时局部变量 head 释放也无所谓，它释放的只是这个变量保存的地址编号，并不会释放地址指向的内存空间，主函数的 head 已经保存了新链表的头节点位置，可以正常访问；
    2. 如果堆区空间申请失败，不要返回 NULL，失败相当于不改变链表结构，直接原样返回就行，否则会将原来的链表丢失，还会造成内存泄漏，堆区空间无法释放的问题；
    3. 链表头为空的话，直接将 head 指向新添加的学生节点就行，再将新学生节点指针域指向 NULL；
    4. 链表头不为空的话，先将新学生节点的指针域指向 head 指向的节点，再将 head 指向新学生节点，这里顺序不能颠倒；
    5. 如果颠倒，head 指向了新学生节点，那之前的链表就丢失了，新学生节点的指针域找不到之前 head 指向的头节点。也可以先定义一个临时指针变量指向 head 指向的头节点，然后顺序可以颠倒了，但感觉多此一举。
2.2.3遍历所有学生信息
  • 代码演示
// 定义函数：打印学生信息
void print_func(STU *head)
{
    // 判断链表是否为空
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return;
    }

    // 链表不为空，遍历学生信息
    STU *p = head;
    printf("---------------学生信息---------------\n");
    while(p != NULL)
    {
        printf("学号：%03d, 姓名：%-6s, 分数：%.2f\n", p->num, p->name, p->score);
        p = p->next;
    }
    printf("---------------末行显示---------------\n");
}

  • 说明：

    1. 遍历所有学生信息，是读操作，不需要返回值；
    2. 遍历前先判断链表是否为空再遍历，否则访问非法内存；
    3. 定义一个临时指针变量，并将 head 赋值给它，因为读操作节点头不能改变，需要一个临时指针变量去改变指向，遍历信息。

  • 头部插入运行结果

请输入要操作的指令：insert
请输入要添加的学生的个数：3
请输入学生信息(学号 姓名 分数):101 小明 88.8
102 小红 85
103 王天霸 65.5
已添加3位学生信息   
请输入要操作的指令：print
---------------学生信息---------------
学号：103, 姓名：王天霸, 分数：65.50  
学号：102, 姓名：小红  , 分数：85.00  
学号：101, 姓名：小明  , 分数：88.80  
---------------末行显示---------------
请输入要操作的指令：quit              
程序已经退出
  • 说明：从输出结果可以看出，头部插入去遍历的时候，类似于先入后出。
2.2.4尾部插入学生信息
  • 代码演示
// 定义函数：在尾部插入学生信息
STU *insert_func_tail(STU *head, STU stu_temp)
{
    // 申请堆区空间，存储一个学生的信息
    STU *new_stu = (STU *)malloc(sizeof(STU));
    if (NULL == new_stu)
    {
        printf("空间申请失败\n");
        return head;
    }

    // 将获取到的学生信息存入申请到的空间
    *new_stu = stu_temp;
    new_stu->next = NULL;

    // 将新的学生节点插入链表
    // 链表为空
    if (NULL == head)
    {
        head = new_stu;
    }
        // 链表不为空
    else
    {
        STU *p = head;
        while(p->next != NULL)
        {
            p = p->next;
        }
        p->next = new_stu;
    }
    return head;
}

  • 说明：

    1. 参数传递，返回值等操作同头部插入；
    2. 因为是尾部插入，新学生节点的指针域一定指向 NULL，因此在判断链表是否为空前就可以将指针域指向空new_stu->next = NULL;，减少重复代码；
    3. 链表不为空时，定义一个临时指针变量用于定位到链表的最后一个节点，然后将最后一个节点的 next 指向新学生节点即可。

  • 尾部插入运行结果

请输入要操作的指令：insert
请输入要添加的学生的个数：3
请输入学生信息(学号 姓名 分数):101 小明 88.8
102 小红 85
103 王天霸 65.5     
已添加3位学生信息   
请输入要操作的指令：print
---------------学生信息---------------
学号：101, 姓名：小明  , 分数：88.80  
学号：102, 姓名：小红  , 分数：85.00  
学号：103, 姓名：王天霸, 分数：65.50  
---------------末行显示---------------
  • 说明：从运行结果可以看出，尾部插入学生，遍历结果类似于先入先出。
2.2.5有序插入学生信息

这里按照学生学号从小到大的顺序排序。

  • 代码演示
// 定义函数：按照学号顺序插入
STU *insert_func_sequence(STU *head, STU stu_temp)
{
    // 申请堆区空间，存储一个学生的信息
    STU *new_stu = (STU *)malloc(sizeof(STU));
    if (NULL == new_stu)
    {
        printf("空间申请失败\n");
        return head;
    }

    // 将获取到的学生信息存入申请到的空间
    *new_stu = stu_temp;
    new_stu->next = NULL;

    // 将新的学生节点插入链表
    // 链表为空
    if (NULL == head)
    {
        head = new_stu;
    }
    // 链表不为空
    else
    {
        // 定义两个指针：pa用于寻找插入位置（定位指针），pb用于保存pa的上一个节点位置
        STU *pa = head, *pb = head;
        while((pa != NULL) && (pa->num < new_stu->num))
        {
            pb = pa;
            pa = pa->next;
        }
        // 插入链表最后一个
        if (NULL == pa)
        {
            pb->next = new_stu;
            // new_stu = pb->next; // 错误写法
        }
        // 插入链表第一个
        else if(pa == head)
        {
            new_stu->next = head;
            head = new_stu;
        }
        // 插入到链表的中间
        else
        {
            pb->next = new_stu;
            new_stu->next = pa;
        }
    }
    return head;
}

  • 说明：

    1. 顺序插入除了链表不为空的情况，其它同前面两种方式；
    2. 需要依次比较新学生的学号与链表中其它学生学号的大小确定插入点的位置，因此需要定义一个临时指针变量定位，考虑到如果是插入的话，需要截断以前的链表，将截断位置的上一个节点的 next 指向新节点，新节点的 next 指向下一个节点，下一个节点就是定位指针当前指向的位置，但上一个节点不知道，因此需要定义另外一个临时指针变量保存定位指针的上一个节点位置；
    3. 通过条件循环定位插入位置，当新节点的学号大于当前定位节点的学号且当前节点的next不指向NULL时指针继续后移，知道其中一个不满足，退出循环；
    4. 循环结束，如果NULL == pa，说明新节点num值最大，插入到末尾，注意：while((pa != NULL) && (pa->num < new_stu->num))必须先判断pa != NULL，否则当pa指向NULL时，先判断pa->num < new_stu->num会访问非法内存；
    5. 注意：pb->next = new_stu;与new_stu = pb->next;是有区别的，前者是将pb的 next 指向new_stu，后者是将new_stu指向pb的 next 指向的节点，注意区分；
    6. 如果循环因为条件pa->num < new_stu->num不满足退出，当pa == head时说明新节点的 num 值最小，插入到头部，让新节点的 next 指向 head 指向的节点，再用 head 指向新节点；
    7. 如果上面情况都不是，那插入到中间位置，让新节点指向定位指针指向的节点，再让定位指针前一个节点的 next 指向新节点，这两步位置可调换。

  • 运行结果

请输入要操作的指令：insert
请输入要添加的学生的个数：3
请输入学生信息(学号 姓名 分数):105 张大炮 85
101 吕小布 83.5
103 王刚 75
已添加3位学生信息   
请输入要操作的指令：print
---------------学生信息---------------
学号：101, 姓名：吕小布, 分数：83.50  
学号：103, 姓名：王刚  , 分数：75.00  
学号：105, 姓名：张大炮, 分数：85.00  
---------------末行显示---------------
  • 说明：有序插入不管输入数据的先后，结果都是按照规定的顺序插入的。

2.3查询某个学生信息

  • 主函数代码
// ......省略部分代码
else if (strcmp("search", cmd) == 0)
        {
            char name[32] = "";
            printf("请输入要查找的学生姓名：");
            scanf("%s", name);

            // 定义一个指针变量保存查找到的值
            STU *ret = search_func(head, name);
            if (ret == NULL)
                printf("未找到该学生信息\n");
            else
            {
                printf("---------------学生信息---------------\n");
                printf("学号：%03d, 姓名：%-6s, 分数：%.2f\n", ret->num, ret->name, ret->score);
                printf("---------------末行提示---------------\n");
            }
        }
// ......省略部分代码
  • 功能函数代码
// 定义函数：查找学生信息
STU *search_func(STU *head, char *name)
{
    STU *p = head;
    // 判断链表是否为空
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return NULL;
    }
    else
    {
        while((strcmp(name, p->name) != 0) && (p->next != NULL))
        {
            p = p->next;
        }
        if (strcmp(name, p->name) == 0)
            return p;
        else
            return NULL;
    }
}
  • 说明：
    1. 通过姓名查找学生信息，返回第一个找到的学生信息。功能函数只负责查找，学生姓名的获取在主函数完成；
    2. 定义一个临时指针变量用于保存找到的节点地址，函数将找到的节点地址通过返回值返回。
请输入要操作的指令：insert
请输入要添加的学生的个数：2
请输入学生信息(学号 姓名 分数):101 小明 88.5
102 小红 85
已添加2位学生信息   
请输入要操作的指令：search
请输入要查找的学生姓名：李华
未找到该学生信息    
请输入要操作的指令：search
请输入要查找的学生姓名：小红
---------------学生信息---------------
学号：102, 姓名：小红  , 分数：85.00  
---------------末行提示---------------

2.4删除某个学生的信息

  • 主函数代码
// ......省略部分代码
else if (strcmp("delete", cmd) == 0)
        {
            int num = 0;
            printf("请输入要删除的学生学号：");
            scanf("%d", &num);

            // 调用函数：删除指定学号信息
            head = delete_func(head, num);
        }
// ......省略部分代码
  • 功能函数代码
// 定义函数：删除指定学号学生信息
STU *delete_func(STU *head, int num)
{
    // 定义两个指针：一个用于查找，另外一个用于
    STU *pa = head, *pb = head;
    // 判断链表是否存在
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return head;
    }
    else
    {
        while ((pa->num != num) && (pa->next != NULL))
        {
            pb = pa;
            pa = pa->next;
        }
        // 如果要删除的信息存在
        if (pa->num == num)
        {
            // 节点在头部
            if (pa == head)
            {
                head = head->next;
                printf("已删除信息：%d\n", pa->num);
                free(pa);
            }
            // 节点在尾部
//            else if (pa->next == NULL)
//            {
//                pb->next == NULL;
//                free(pa);
//            }
            // 节点在中尾部
            else
            {
                pb->next = pa->next;
                printf("已删除信息：%d\n", pa->num);
                free(pa);
            }
        }
        // 信息不存在
        else
            printf("要删除的信息不存在\n");
    }
    return head;
}

  • 说明：

    1. 因为删除要修改链表结构，或者更改 head 头指向，因此需要将处理后的 head 值返回给函数外部 head 变量接收；
    2. 需要定义两个指针变量，一个用于查找定位，一个用于记录定位指针的上一个元素。因为要删除节点，因此需要将被删除节点的上一个节点的 next 指向被删除节点的下一个节点；
    3. 一定要先将被删除节点的上一个节点的 next 指向下一个节点后，再删除该节点，否则该节点以后的链表丢失；
    4. 节点在中间和节点在尾部时的代码是等价的，因此可以合并，减少代码量。

  • 运行结果

请输入要操作的指令：insert
请输入要添加的学生的个数：4
请输入学生信息(学号 姓名 分数):101 小明 88.8
102 小红 85
103 张大炮 83.5
104 王刚 75
已添加4位学生信息   
请输入要操作的指令：print
---------------学生信息---------------
学号：101, 姓名：小明  , 分数：88.80  
学号：102, 姓名：小红  , 分数：85.00  
学号：103, 姓名：张大炮, 分数：83.50  
学号：104, 姓名：王刚  , 分数：75.00  
---------------末行显示---------------
请输入要操作的指令：delete
请输入要删除的学生学号：103 // 删中间
已删除信息：103     
请输入要操作的指令：print
---------------学生信息---------------
学号：101, 姓名：小明  , 分数：88.80  
学号：102, 姓名：小红  , 分数：85.00  
学号：104, 姓名：王刚  , 分数：75.00  
---------------末行显示---------------
请输入要操作的指令：delete
请输入要删除的学生学号：101 //删开头
已删除信息：101
请输入要操作的指令：delete
请输入要删除的学生学号：104
已删除信息：104 // 删末尾
请输入要操作的指令：print
---------------学生信息---------------
学号：102, 姓名：小红  , 分数：85.00
---------------末行显示---------------
请输入要操作的指令：delete
请输入要删除的学生学号：105 // 信息不存在
要删除的信息不存在

2.5清空学生信息

  • 主函数代码
// ......省略部分代码
else if (strcmp("free", cmd) == 0)
        {
            unsigned int password = 0;
            printf("请输入密码验证：");
            scanf("%u", &password);
            if (password == 123456)
                head = free_func(head);
            else
                printf("密码错误，无权操作！\n");
        }
// ......省略部分代码
  • 功能函数代码
// d定义函数：清空学生信息
STU *free_func(STU *head)
{
    STU *p = head;
    // 判断链表是否为空
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return head;
    }
    while (p != NULL)
    {
        head = head->next;
        free(p);
        p = head;
    }
    printf("学生信息已清空\n");
    return NULL;
}

  • 说明：

    1. 释放链表从头到尾逐一释放，注意：要先将 head 指向下一个节点，再释放当前节点；
    2. 链表清空以后记得返回 NULL 给外部 head 变量；
    3. 同时可以为该功能添加权限验证，毕竟删除所有学生信息是件很危险的事情。

  • 运行结果

请输入要操作的指令：insert
请输入要添加的学生的个数：4
请输入学生信息(学号 姓名 分数):101 小明 88.8
102 小红 85.5
103 张大炮 75
104 黄天霸 65
已添加4位学生信息   
请输入要操作的指令：print
---------------学生信息---------------
学号：101, 姓名：小明  , 分数：88.80  
学号：102, 姓名：小红  , 分数：85.50  
学号：103, 姓名：张大炮, 分数：75.00  
学号：104, 姓名：黄天霸, 分数：65.00  
---------------末行显示---------------
请输入要操作的指令：free
请输入密码验证：123456
学生信息已清空      
请输入要操作的指令：print
未添加任何学生信息

2.6链表逆序

  • 主函数代码
// ......省略部分代码
else if (strcmp("reverse", cmd) == 0)
        {
            // 调用函数，逆序链表
            head = reverse_func(head);
        }
// ......省略部分代码
  • 功能函数代码
// 定义函数逆序整个链表
STU *reverse_func(STU *head)
{
    // 定义两个指针变量：pa的next用于指向前一个节点，pb指向pa下一个节点
    STU *pa = head, *pb = head;
    // 判断链表是否存在
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return head;
    }
    else
    {
        pa = head->next;
        head->next = NULL;
        while(pa != NULL)
        {
            pb = pa->next;
            pa->next = head;
            head = pa;
            pa = pb;
        }
        printf("链表逆序成功！\n");
    }
    return head;
}

  • 说明：

    1. 这里的逆序，不是按照反向排序，只是将链表整体颠倒，不存在排序的作用；
    2. 逆序链表，即将第一个节点的 next 指向 NULL，将第二个节点的 next 指向第一个节点，第三个节点的 next 指向第二个节点，以此类推，直到最后一个节点的 next 指向倒数第二个节点，将 head 指向最后一个节点；
    3. 由上面推理，需要一个指针变量 pa 指向需要改变 next 的节点，但当这个节点的 next 指向前一个节点时，下一个节点开始就丢失了，因此需要定义另外一个指针 pb 指向下一个节点，并且要在 pa 的 next 指向上一个节点前将 pb 指向 pa 指向的下一个节点；
    4. 当 pa 指向 pb 指向的节点前，先将 head 指向 pa 指向的节点，一直重复上面的操作，直到 pa 指向 NULL时，head 就指向了原始链表的尾部，逆序完成；
    5. 如果链表就一个节点，那 pa 刚开始就指向 NULL，不会进入循环，代码也成立，不需要分情况判断了。

  • 运行结果

请输入要操作的指令：insert
请输入要添加的学生的个数：4
请输入学生信息(学号 姓名 分数):101 小明 88.8
102 小红 85.5
103 张大炮 75
104 黄天霸 65
已添加4位学生信息   
请输入要操作的指令：print
---------------学生信息---------------
学号：101, 姓名：小明  , 分数：88.80  
学号：102, 姓名：小红  , 分数：85.50  
学号：103, 姓名：张大炮, 分数：75.00  
学号：104, 姓名：黄天霸, 分数：65.00  
---------------末行显示---------------
请输入要操作的指令：reverse
链表逆序成功！      
请输入要操作的指令：print
---------------学生信息---------------
学号：104, 姓名：黄天霸, 分数：65.00  
学号：103, 姓名：张大炮, 分数：75.00  
学号：102, 姓名：小红  , 分数：85.50  
学号：101, 姓名：小明  , 分数：88.80  
---------------末行显示---------------

2.7链表排序

先了解排序的算法。

2.7.1数值数组冒泡排序

冒泡排序，正向排序时，前后两两比较，前一个小于后一个保持不变，前一个大于后一个，两两交换，指针后移一位，每循环一次可以将最大的值排到当次排序的末尾。

例如：为数组int nums = {2， 3， 1， 5， 4}排序。

23154
numsnums + 1
  • 正向排序时遵循相邻比较，前小于后不变，前大于后交换位置，步骤如下：

第0轮：i = 0

21345

找到一个最大值 5 放到数组最后，既然 5 已经是本轮最大，就没必要参与下一轮比较了。第0轮进行了4次比较。

第1轮：i = 1

1234

第1轮这里虽然看似已经排序完成了，但为了代码的通用性，我们需要考虑极端的情况，例如：int nums = {5， 4， 3， 2， 1}，可以通过这个例子自行推演。第1轮经历了3次比较。

第2轮：i = 2

123

第2轮经历了2次比较。

第3轮：i = 3

12

第3轮经历1次比较，排序完成。

  • 由上面的推演过程，我们可以总结出规律：假设一个数值数组有 n 个数，会经历 n -1 轮比较，每轮比较会经历 (当前排序的元素个数 - 1) 次比较，轮数从0开始计算，(元素个数 = n - 轮数)，联立可得：(每轮比较次数 = n - i - 1)。
  • 案例：键盘获取10个数为数组赋值，通过冒泡排序法排序，遍历数组
// 定义函数，用于给数组排序
void sort_func(int *nums, int n)
{
    int i = 0;
    for (i = 0; i < n - 1; i++) // 每循环一次是一轮
    {
        int j = 0;
        for (j = 0; j < n - i - 1; j++) // 每轮比较的次数
        {
            if(nums[j] > nums[j + 1])
            {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

int main()
{
    // 定义一个数值数组
    int nums[10] = {0};
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("请输入10个整数：");
    int i = 0;
    for (i = 1; i < n; i++)
    {
        scanf("%d", &nums[i]);
    }

    // 调用函数为数组排序
    sort_func(nums, n);

    // 遍历数组
    for (i = 1; i < n; i++)
    {
        printf("%d ", nums[i]);
    }
    printf("\n");
    return 0;
}
  • 运行结果
请输入10个整数：21 35 12 5 89 74 36 92 9 16
5 9 12 21 35 36 74 89 92
2.7.2数值数组选择排序

前面的冒泡排序，每轮能找出一个最大值，这里的选择排序则是每轮找出一个最小值。定义一个最小值变量，假设每轮第一个值最小，然后第一个数与后面其它数比较，小于就继续与下一个比较，大于就将 min 指向较小的那一个，比较结束，如果 min 已经不是第一个元素，那么与第一个元素交换位置。

例如：为数组int nums = {2， 3， 1， 5， 4}排序。

23154
numsnums + 1

第0轮：i = 0

13254

第1轮：i = 1

2354

第2轮：i = 2

354

第3轮：i = 3

45

  • 由上面的推演过程，我们可以总结出规律：假设一个数值数组有 n 个数，会经历 n -1 轮比较，轮数从0开始计算，每轮会进行n - i - 1次比较。

  • 代码演示

// 定义函数，用于给数组排序
void sort_func(int *nums, int n)
{
    int i = 0;
    for (i = 0; i < n - 1; i++)
    {
        // 定义一个最小值索引，并假设第一个元素值最小
        int min = 0, j = 0;
        for (min = i, j = i + 1; j < n; j++)
        {
            // 依次比较，如果min不是最小，就定位到最小
            if (nums[min] > nums[j])
                min = j;
        }
        // 每轮比较完，如果不是假设的第一个值，那么就交换两个的值
        if (min != i)
        {
            int temp = nums[min];
            nums[min] = nums[i];
            nums[i] = temp;
        }
    }
}
  • 运行结果
请输入10个整数：21 35 12 5 89 74 36 92 9 16
5 9 12 21 35 36 74 89 92
  • 说明：相比于冒泡排序，选择排序交换的次数更少。
2.7.3链表排序实现

链表排序最麻烦的步骤就是两个节点的交换了，由上面两种排序方式对比，选择排序交换次数较少，这里选用选择排序演示。

  • 代码演示
// 定义函数：为链表排序
void sort_func(STU *head)
{
    // 判断链表是否存在
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return;
    }
    else
    {
        STU *p_i = NULL;
        for (p_i = head; p_i->next != NULL; p_i = p_i->next)
        {
            STU *p_min = NULL, *p_j = NULL;
            for (p_min = p_i, p_j = p_i->next; p_j != NULL; p_j = p_j->next)
            {
                if (p_min->num > p_j->num)
                    p_min = p_j;
            }
            if (p_min != p_i)
            {
                // 整体交换节点成员
                STU temp = *p_min;
                *p_min = *p_i;
                *p_i = temp;
                // 将指针域恢复原样
                temp.next = p_min->next;
                p_min->next = p_i->next;
                p_i->next = temp.next;
            }
        }
        printf("排序完成\n");
    }
}
  • 运行结果
请输入要操作的指令：insert
请输入要添加的学生的个数：4
请输入学生信息(学号 姓名 分数):105 小明 88.8
101 小红 85.5
103 张伟 90  
102 张大炮 65
已添加4位学生信息   
请输入要操作的指令：print
---------------学生信息---------------
学号：105, 姓名：小明  , 分数：88.80  
学号：101, 姓名：小红  , 分数：85.50  
学号：103, 姓名：张伟  , 分数：90.00  
学号：102, 姓名：张大炮, 分数：65.00  
---------------末行显示---------------
请输入要操作的指令：sort
排序完成
请输入要操作的指令：print
---------------学生信息---------------
学号：101, 姓名：小红  , 分数：85.50  
学号：102, 姓名：张大炮, 分数：65.00  
学号：103, 姓名：张伟  , 分数：90.00  
学号：105, 姓名：小明  , 分数：88.80  
---------------末行显示---------------
请输入要操作的指令：reverse
链表逆序成功！
请输入要操作的指令：print
---------------学生信息---------------
学号：105, 姓名：小明  , 分数：88.80
学号：103, 姓名：张伟  , 分数：90.00
学号：102, 姓名：张大炮, 分数：65.00
学号：101, 姓名：小红  , 分数：85.50
---------------末行显示---------------
请输入要操作的指令：quit
程序已经退出
  • 说明：
    1. 链表排序和数组排序原理一样，只不过把数组是通过下标索引定位具体的元素，链表换成了指针变量定位节点；
    2. 数组排序是i++操作，在链表里换成了p_i -> next操作；
    3. 数组的i < n换成了链表的p_i -> next != NULL；
    4. 数组的位置交换，换成了节点数据域交换（注意：只是节点数据域交换，不是节点交换位置），为方便操作先将节点数据整体交换，再复原指针域。

三、完整代码演示（单文件版）

  • 代码演示
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 一个简单的学生管理系统
typedef struct stu {
    // 定义数据域
    int num;
    char name[32];
    float score;

    // 定义指针域
    struct stu *next;
} STU;

// 定义函数，打印菜单界面
void func_list(void) {
    printf("-----------------------------------\n");
    printf("-->insert:插入学生信息            |\n");
    printf("-->print:遍历信息                 |\n");
    printf("-->search:查询某个学生的信息      |\n");
    printf("-->delete:删除某个学生的信息      |\n");
    printf("-->free:删除所有学生              |\n");
    printf("-->reverse:链表逆序               |\n");
    printf("-->sort:链表排序                  |\n");
    printf("-->quit:退出整个程序              |\n");
    printf("-----------------------------------\n");
    return;
}

// 定义函数：在头部插入学生信息
STU *insert_func_head(STU *head, STU stu_temp)
{
    // 申请堆区空间，存储一个学生的信息
    STU *new_stu = (STU *)malloc(sizeof(STU));
    if (NULL == new_stu)
    {
        printf("空间申请失败\n");
        return head;
    }

    // 将获取到的学生信息存入申请到的空间
    *new_stu = stu_temp;

    // 将新的学生节点插入链表
    // 链表为空
    if (NULL == head)
    {
        head = new_stu;
        new_stu->next = NULL;
    }
    // 链表不为空
    else
    {
        new_stu->next = head;
        head = new_stu;
    }
    return head;
}

// 定义函数：打印学生信息
void print_func(STU *head)
{
    // 判断链表是否为空
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return;
    }

    // 链表不为空，遍历学生信息
    STU *p = head;
    printf("---------------学生信息---------------\n");
    while(p != NULL)
    {
        printf("学号：%03d, 姓名：%-6s, 分数：%.2f\n", p->num, p->name, p->score);
        p = p->next;
    }
    printf("---------------末行显示---------------\n");
}

// 定义函数：在尾部插入学生信息
STU *insert_func_tail(STU *head, STU stu_temp)
{
    // 申请堆区空间，存储一个学生的信息
    STU *new_stu = (STU *)malloc(sizeof(STU));
    if (NULL == new_stu)
    {
        printf("空间申请失败\n");
        return head;
    }

    // 将获取到的学生信息存入申请到的空间
    *new_stu = stu_temp;
    new_stu->next = NULL;

    // 将新的学生节点插入链表
    // 链表为空
    if (NULL == head)
    {
        head = new_stu;
    }
        // 链表不为空
    else
    {
        STU *p = head;
        while(p->next != NULL)
        {
            p = p->next;
        }
        p->next = new_stu;
    }
    return head;
}

// 定义函数：按照学号顺序插入
STU *insert_func_sequence(STU *head, STU stu_temp)
{
    // 申请堆区空间，存储一个学生的信息
    STU *new_stu = (STU *)malloc(sizeof(STU));
    if (NULL == new_stu)
    {
        printf("空间申请失败\n");
        return head;
    }

    // 将获取到的学生信息存入申请到的空间
    *new_stu = stu_temp;
    new_stu->next = NULL;

    // 将新的学生节点插入链表
    // 链表为空
    if (NULL == head)
    {
        head = new_stu;
    }
    // 链表不为空
    else
    {
        // 定义两个指针：pa用于寻找插入位置，pb用于保存pa的上一个节点位置
        STU *pa = head, *pb = head;
        while((pa != NULL) && (pa->num < new_stu->num))
        {
            pb = pa;
            pa = pa->next;
        }
        // 插入链表最后一个
        if (NULL == pa)
        {
            pb->next = new_stu;
            // new_stu = pb->next;
        }
        // 插入链表第一个
        else if(pa == head)
        {
            new_stu->next = head;
            head = new_stu;
        }
        // 插入到链表的中间
        else
        {
            pb->next = new_stu;
            new_stu->next = pa;
        }
    }
    return head;
}

// 定义函数：查找学生信息
STU *search_func(STU *head, char *name)
{
    STU *p = head;
    // 判断链表是否为空
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return NULL;
    }
    else
    {
        while((strcmp(name, p->name) != 0) && (p->next != NULL))
        {
            p = p->next;
        }
        if (strcmp(name, p->name) == 0)
            return p;
        else
            return NULL;
    }
}

// 定义函数：删除指定学号学生信息
STU *delete_func(STU *head, int num)
{
    // 定义两个指针：一个用于查找，另外一个用于
    STU *pa = head, *pb = head;
    // 判断链表是否存在
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return head;
    }
    else
    {
        while ((pa->num != num) && (pa->next != NULL))
        {
            pb = pa;
            pa = pa->next;
        }
        // 如果要删除的信息存在
        if (pa->num == num)
        {
            // 节点在头部
            if (pa == head)
            {
                head = head->next;
                printf("已删除信息：%d\n", pa->num);
                free(pa);
            }
            // 节点在尾部
//            else if (pa->next == NULL)
//            {
//                pb->next == NULL;
//                free(pa);
//            }
            // 节点在中尾部
            else
            {
                pb->next = pa->next;
                printf("已删除信息：%d\n", pa->num);
                free(pa);
            }
        }
        // 信息不存在
        else
            printf("要删除的信息不存在\n");
    }
    return head;
}

// d定义函数：清空学生信息
STU *free_func(STU *head)
{
    STU *p = head;
    // 判断链表是否为空
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return head;
    }
    while (p != NULL)
    {
        head = head->next;
        free(p);
        p = head;
    }
    printf("学生信息已清空\n");
    return NULL;
}

// 定义函数逆序整个链表
STU *reverse_func(STU *head)
{
    // 定义两个指针变量：pa的next用于指向前一个节点，pb指向pa下一个节点
    STU *pa = head, *pb = head;
    // 判断链表是否存在
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return head;
    }
    else
    {
        pa = head->next;
        head->next = NULL;
        while(pa != NULL)
        {
            pb = pa->next;
            pa->next = head;
            head = pa;
            pa = pb;
        }
        printf("链表逆序成功！\n");
    }
    return head;
}

// 定义函数：为链表排序
void sort_func(STU *head)
{
    // 判断链表是否存在
    if (NULL == head)
    {
        printf("未添加任何学生信息\n");
        return;
    }
    else
    {
        STU *p_i = NULL;
        for (p_i = head; p_i->next != NULL; p_i = p_i->next)
        {
            STU *p_min = NULL, *p_j = NULL;
            for (p_min = p_i, p_j = p_i->next; p_j != NULL; p_j = p_j->next)
            {
                if (p_min->num > p_j->num)
                    p_min = p_j;
            }
            if (p_min != p_i)
            {
                // 整体交换节点成员
                STU temp = *p_min;
                *p_min = *p_i;
                *p_i = temp;
                // 将指针域恢复原样
                temp.next = p_min->next;
                p_min->next = p_i->next;
                p_i->next = temp.next;
            }
        }
        printf("排序完成\n");
    }
}

int main() {
    // 调用函数：打印功能菜单
    func_list();
    // 定义一个链表头
    STU *head = NULL;

    // 获取指令
    char cmd[16] = "";
    while(1)
    {
        printf("请输入要操作的指令：");
        scanf("%s", cmd);

        if (strcmp("insert", cmd) == 0)
        {
            // 定义临时变量用于接收输入的学生信息
            STU stu_temp;
            int n = 0;
            printf("请输入要添加的学生的个数：");
            scanf("%d", &n);
            printf("请输入学生信息(学号 姓名 分数):");

            // 调用函数：添加学生信息
            int i = 0;
            for (i = 0; i < n; i++)
            {
                scanf("%d %s %f", &stu_temp.num, stu_temp.name, &stu_temp.score);
                // 调用函数：添加学生信息
                // head = insert_func_head(head, stu_temp); // 头部插入
                head = insert_func_tail(head, stu_temp); // 尾部插入
                // head = insert_func_sequence(head, stu_temp); // 顺序插入
            }
            printf("已添加%d位学生信息\n", n);
        }
        else if (strcmp("print", cmd) == 0)
        {
            // 调用函数：打印学生信息
            print_func(head);
        }
        else if (strcmp("search", cmd) == 0)
        {
            char name[32] = "";
            printf("请输入要查找的学生姓名：");
            scanf("%s", name);

            // 定义一个指针变量保存查找到的值
            STU *ret = search_func(head, name);
            if (ret == NULL)
                printf("未找到该学生信息\n");
            else
            {
                printf("---------------学生信息---------------\n");
                printf("学号：%03d, 姓名：%-6s, 分数：%.2f\n", ret->num, ret->name, ret->score);
                printf("---------------末行提示---------------\n");
            }
        }
        else if (strcmp("delete", cmd) == 0)
        {
            int num = 0;
            printf("请输入要删除的学生学号：");
            scanf("%d", &num);

            // 调用函数：删除指定学号信息
            head = delete_func(head, num);
        }
        else if (strcmp("free", cmd) == 0)
        {
            unsigned int password = 0;
            printf("请输入密码验证：");
            scanf("%u", &password);
            if (password == 123456)
                head = free_func(head);
            else
                printf("密码错误，无权操作！\n");
        }
        else if (strcmp("reverse", cmd) == 0)
        {
            // 调用函数，逆序链表
            head = reverse_func(head);
        }
        else if (strcmp("sort", cmd) == 0)
        {
            // 调用函数：为链表中学生按照学号排序
            sort_func(head);
        }
        else if (strcmp("quit", cmd) == 0)
        {
            printf("程序已经退出\n");
            break;
        }
        else
        {
            printf("请输入有效命令\n");
        }
    }
    return 0;
}
  • 说明：在实际项目中，不会把所有的代码都放入一个文件中，一般都是多文件编程，main.c里面只放主函数代码，其它具体的功能函数会放到某个单独的文件里，实现某一类特定功能，如：func.c，然后创建一个头文件：func.h，将func.c中定义的函数在头文件里声明，最后main.c里包含头文件即可：#include "func.h"。

http://www.kler.cn/a/452583.html

相关文章：

  • git 项目初始化
  • Linux运维常见命令
  • CE第三次作业
  • 挑战一个月基本掌握C++（第十一天）进阶文件，异常处理，动态内存
  • 在算力魔方上运行Genesis：一款颠覆性开源生成式物理引擎!
  • 云途领航：现代应用架构助力企业转型新篇
  • 【区块链】深入理解椭圆曲线密码学(ECC)
  • SVM分类-支持向量机（Support Vector Machine）
  • 飞牛 fnos 使用docker部署 OneNav 书签管理器
  • 12/21java基础
  • VSCode 插件开发实战（九）： 不同插件之间如何通信
  • 在 Ubuntu 下通过 Docker 部署 MySQL 服务器
  • K8S 黑魔法之如何从 Pod 拿到节点的命令行
  • 记录下数仓相关的东西
  • 信息搜集与漏洞扫描
  • C#如何使用Lock
  • vscode python pip : 无法将“pip”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。（）
  • 数据结构经典算法总复习（下卷）
  • 快速掌握Haproxy原理架构
  • Suno Api V4模型无水印开发「综合实战开发自己的音乐网站」 —— 「Suno Api系列」第14篇