C语言单向动态链表实战：从数据结构到动态内存管理完整指南

要想掌握链表的应用，我们首先来回顾一下结构体，并以循序渐进的方式引出链表的概念。

例如，我们需要记录10名学生的姓名、年龄和性别信息。最初，我们可能会想到使用数组：

char names[10][20]={"1-zhangsan","2-zhangsan","3-zhangsan",……};
int ages[10]={1,2,3,4,5,6,7,8,9,10};
char gender[10]={"M","M","M","M","M","F","F","F","F","F"}; //M:男 F：女

通过数组记录后会发现，每位学生的各项信息都被分散定义，形成了一堆零散变量。这不仅可读性差、维护困难，也极不便于扩展。因此，我们自然会想到使用结构体来封装学生信息。

结构体作为一个“模板”，能够将相关数据组合在一起，从而显著提升代码的可读性、可维护性和扩展性：

typedef struct
{
    char name[20]; //姓名
    int age; //年龄
    char gender; //性别 M 男 F女
} student;

student stu[10]; //结构体数组
stu[0]={"1-zhangsan", 1, 'M'};
stu[1]={"2-zhangsan", 2, 'M'};
stu[2]={.name="3-zhangsan", .age=3, .gender='M'}; //另一种初始化方法。用“.”来访问及初始化成员
// ……………………

以上我们使用结构体数组记录了10位学生的信息。但这里每个学生的信息在内存中仍然是孤立的。设想一下，如果有100名甚至1000名学生，我们希望能将它们串联起来，从第一个学生开始就能访问到后续的所有学生。

为了解决这个问题，我们需要在结构体内部引入一个指向自身类型的指针，也就是“自引用指针”。

typedef struct student
{
    char name[20]; //姓名
    int age; //年龄
    char gender; //性别 M 男 F女
    struct student *next; //关键：自引用指针，它的类型和当前结构体一致
} student;

void print_info(student *p)
{
    while(p != NULL) // 终止条件：遇到尾节点的NULL
    {
        printf("%s:%d:%c\n", p->name, p->age, p->gender);
        p = p->next; // 指针“向后移动”，指向下一个节点的内存地址，直到遇到 NULL 结束循环。
    }
}

student s1 = {"1-zhangsan", 1, 'M', NULL};
student s2 = {"2-zhangsan", 2, 'M', NULL};
student s3 = {.name="3-zhangsan", .age=3, .gender='M', NULL};
// ……………………
s1.next = &s2;  // s1的next指针指向s2的内存地址
s2.next = &s3;  // s2的next指针指向s3的内存地址
// ……………………
s8.next = &s9;  // s9的next为NULL，代表最后一个节点
print_info(&s1); //遍历函数

链表节点连接示意图：

链接关系： s1 -> s2 -> s3 -> … -> s8 -> s9 -> NULL

头节点： s1 是整个链表的头指针，掌握了 s1 的地址，就掌握了整个链表的访问入口。

以上展示了单向链表的基础原理，它通过指针将栈上定义的结构体变量串联起来。但在实际应用中，学生数量往往在程序运行时才能确定。这就需要我们结合动态内存分配技术，构建一个单向动态链表。

首先，定义相同的结构体类型：

typedef struct student
{
    char name[20]; //姓名
    int age; //年龄
    char gender; //性别 M 男 F女
    struct student *next; //关键：自引用指针
} student;

一个 student 结构体在内存中占据一块连续的存储空间，其布局可简化表示为：

动态链表的构建从申请第一块内存开始：

student *head = malloc(sizeof(student)); //分配了一块结构体大小的内存空间，
                                         //head 指向的是结构体首地址

作为指针变量，访问其成员需要使用 -> 操作符：

//结构体指针变量访问成员时用“->”符号，如下
head->name
head->age
head->gender
head->next

创建第二个节点，并将其链接到第一个节点之后：

head->next = malloc(sizeof(student)); //分配了一块结构体大小的内存空间，
                                      //head->next 指向的是第二个结构体的首地址

如此反复，就可以动态地创建和链接任意多个节点，形成一条“链”。

下面是一个完整的示例：程序允许用户输入不定数量的学生信息（姓名、年龄、性别），当输入“exit”时终止输入，并最终遍历和释放链表。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define Male 0
#define Female 1

typedef struct stu
{
    char name[20];
    int age;
    char gender;
    struct stu *next;
} student;

// 遍历打印链表
void print_students(student *head)
{
    student *p = head;
    int i = 1;
    while (p != NULL)
    {
        printf("第%d个学生：姓名=%s，年龄=%d，性别=%s\n",
               i++, p->name, p->age,
               p->gender == Male ? "男" : "女");
        p = p->next;
    }
}

// 释放链表所有节点的内存
void free_students(student *head)
{
    student *temp;
    while (head != NULL)
    {
        temp = head;       // 保存当前节点地址
        head = head->next; // 指针后移
        free(temp);        // 释放当前节点
    }
}

int main()
{
    student *head = NULL; // 链表头指针
    student *last = NULL; // 链表尾指针
    char input_name[20];
    int input_age;
    int input_gender;

    while (1)
    {
        // 1. 输入姓名（作为终止条件）
        printf("请输入学生姓名（输入exit结束）：");
        scanf("%s", input_name);
        // 终止条件：输入exit则退出循环
        if (strcmp(input_name, "exit") == 0)
        {
            break;
        }
        // 2. 输入年龄
        printf("请输入%s的年龄：", input_name);
        scanf("%d", &input_age);
        // 3. 输入性别
        printf("请输入%s的性别（0=男，1=女）：", input_name);
        scanf("%d", &input_gender);

        // 4. 分配节点内存并赋值
        student *new_node = (student *)malloc(sizeof(student));
        if (new_node == NULL)
        { // 内存分配失败处理
            printf("内存不足，无法添加新学生！\n");
            break;
        }
        // 给节点赋值
        strcpy(new_node->name, input_name);
        new_node->age = input_age;
        new_node->gender = (input_gender == 0) ? Male : Female;
        new_node->next = NULL; // 新节点默认是尾节点

        // 5. 尾插法添加到链表
        if (head == NULL)
        { // 链表为空，第一个节点
            head = new_node;
            last = new_node;
        }
        else
        { // 链表非空，添加到尾部
            last->next = new_node;
            last = new_node;
        }
    }

    // 打印所有学生信息
    printf("\n所有学生信息如下：\n");
    print_students(head);

    // 释放链表内存
    free_students(head);
    printf("内存已释放，程序结束。\n");

    return 0;
}

通过这个完整的例子，我们可以看到如何将数据结构中的链表理论与C语言的动态内存管理实践相结合。掌握这种动态链表的构建、遍历与释放，是理解更复杂数据结构和进行底层系统开发的重要基础。如果你想深入学习更多C语言核心概念或数据结构算法，可以访问云栈社区查看更多专业教程。