链表

Abstract: 本章导览 链表是 C 语言中最重要的动态数据结构之一。与数组的连续存储不同，链表通过指针将散落在内存各处的结点串联起来，可以在运行时灵活地增删数据。

本章涵盖：链表基本概念 → 静态链表 → 动态链表的创建 → 链表的遍历输出 → 综合练习

相关基础：c-pointers、c-custom-types

---

4.1 什么是链表

链表的定义

链表（Linked List）是一种常见的、重要的动态数据结构。它是动态地进行存储分配的一种结构——各个数据元素在内存中的地址不一定连续，通过指针将它们前后相连。

Tip: 对比数组

• 数组：编译时确定大小，元素在内存中连续存放，访问快但增删慢。
• 链表：运行时按需分配，元素在内存中不连续，通过指针链接，增删快但随机访问慢。

链表的结构

一个链表由若干个结点（Node）组成。每个结点包含两个部分：

部分	说明
数据域	存储实际的数据（如学号、成绩等）
指针域	存储下一个结点的地址（next 指针）

head
  │
  ▼
┌────────┬──────┐    ┌────────┬──────┐    ┌────────┬──────┐
│ 数据 A │ next─┼───>│ 数据 B │ next─┼───>│ 数据 C │ NULL │
└────────┴──────┘    └────────┴──────┘    └────────┴──────┘
  结点1                 结点2                 结点3（表尾）

关键概念

• 头指针（head）：指向链表第一个结点的指针。通过头指针可以找到整条链表。
• 表尾：最后一个结点的 next 指针值为 NULL，标志链表结束。
• 各结点地址不连续：每个结点由 malloc 动态分配，地址由系统决定。

结点的结构体定义

链表的结点用结构体来描述。结构体中必须包含一个指向自身类型的指针成员：

struct Student {
    int num;                   // 数据域：学号
    float score;               // 数据域：成绩
    struct Student *next;      // 指针域：指向下一个结点
};

Important: 自引用结构体 struct Student *next; 是一个指向自身类型的指针，这是链表结点的核心。通过它，每个结点都能“记住”下一个结点在哪里。

---

4.2 建立简单的静态链表

什么是静态链表

静态链表是指所有结点都是在编译时已定义好的变量，不是运行时用 malloc 动态开辟的。我们手动用指针把这些变量串联起来。

Note: 适用场景 静态链表适合结点数量已知且固定的情况。实际开发中更常用动态链表。

例题 8：建立并输出 3 个结点的静态链表

题目：建立一个如图所示的简单链表，它由 3 个学生数据的结点组成，要求输出各结点中的数据。

head
  │
  ▼
┌───────────┬──────┐    ┌───────────┬──────┐    ┌───────────┬──────┐
│ 10101     │ next─┼───>│ 10103     │ next─┼───>│ 10107     │ NULL │
│ 85      │      │    │ 90.0      │      │    │ 85.0      │      │
└───────────┴──────┘    └───────────┴──────┘    └───────────┴──────┘
     a                       b                       c

解题思路

1. 定义 3 个 struct Student 变量 a、b、c
2. 分别给它们的数据域赋值
3. 用指针将它们链接起来：
   • head = &a; — 头指针指向第一个结点
   • a.next = &b; — 第一个结点指向第二个
   • b.next = &c; — 第二个结点指向第三个
   • c.next = NULL; — 第三个结点为表尾
4. 用指针 p 从头遍历链表，逐个输出

完整代码

#include <stdio.h>

struct Student {
    int num;
    float score;
    struct Student *next;
};

int main()
{
    struct Student a, b, c, *head, *p;

    // 给各结点赋值
    a.num = 10101;  a.score = 85;
    b.num = 10103;  b.score = 90;
    c.num = 10107;  c.score = 85;

    // 建立链接关系
    head = &a;             // 头指针指向a
    a.next = &b;           // a → b
    b.next = &c;           // b → c
    c.next = NULL;         // c 是表尾

    // 遍历输出
    p = head;
    do {
        printf("%ld %5.1f\n", p->num, p->score);
        p = p->next;       // p 后移到下一个结点
    } while (p != NULL);

    return 0;
}

遍历过程详解

遍历是链表最基本的操作，核心是 “输出当前结点，然后移动到下一个”：

步骤	p 指向	输出	p = p->next 后
1	a（地址 = head）	10101 85	p 指向 b
2	b	10103 90.0	p 指向 c
3	c	10107 85.0	p = NULL
4	循环条件 p != NULL 不满足，退出	—	—

Tip: p = p->next 的本质 p->next 存储的是下一个结点的地址，将它赋给 p，就等于让 p “跳”到下一个结点。这是链表遍历的核心语句。

---

4.3 建立动态链表

什么是动态链表

所谓建立动态链表，是指在程序执行过程中从无到有地建立起一个链表——即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。

Important: 与静态链表的区别

• 静态链表：结点是编译时就存在的变量，个数固定。
• 动态链表：结点通过 malloc 在运行时动态分配，个数可变。

例题 9：创建含 3 个学生数据的动态链表

前置知识：malloc 函数

#include <stdlib.h>

// malloc 分配指定字节数的内存，返回 void* 指针
// 需要强制类型转换为目标类型
struct Student *p = (struct Student *)malloc(sizeof(struct Student));

为了简洁，通常用宏定义结点大小：

#define LEN sizeof(struct Student)

三个关键指针

指针	作用
head	头指针，指向链表的第一个结点
p1	总是指向新开辟的结点（“探路者”）
p2	总是指向当前链表的最后一个结点（“尾巴”）

建表算法思路（逐步图解）

第一步：开辟第一个结点，p1 和 p2 都指向它

p1 = p2 = (struct Student *)malloc(LEN);
scanf("%ld,%f", &p1->num, &p1->score);  // 输入: 10101, 85

p1 ──┐
     ▼
  ┌───────────┐
  │ 10101     │
  │ 85      │
  └───────────┘
     ▲
p2 ──┘
head = NULL（尚未赋值）

第二步：将第一个结点接入链表（head 指向它）

因为是第一个结点（n <mark> 1），所以 head = p1。

head
  │
  ▼
  ┌───────────┐
  │ 10101     │
  │ 85      │
  └───────────┘
  ▲           ▲
  p2          p1（此时 p1 </mark> p2）

第三步：开辟第二个结点，p1 指向新结点

p1 = (struct Student *)malloc(LEN);
scanf("%ld,%f", &p1->num, &p1->score);  // 输入: 10103, 90

head
  │
  ▼
  ┌───────────┐         ┌───────────┐
  │ 10101     │         │ 10103     │
  │ 85      │         │ 90.0      │
  └───────────┘         └───────────┘
       ▲                     ▲
       p2                    p1

第四步：连接！让 p2->next = p1，再让 p2 = p1

p2->next = p1;    // 第一个结点的 next 指向第二个结点
p2 = p1;          // p2 移动到链表尾部

head
  │
  ▼
  ┌───────────┬──────┐    ┌───────────┐
  │ 10101     │ next─┼───>│ 10103     │
  │ 85      │      │    │ 90.0      │
  └───────────┴──────┘    └───────────┘
                               ▲
                          p1, p2

第五步：重复——开辟第三个结点

p1 = (struct Student *)malloc(LEN);
scanf("%ld,%f", &p1->num, &p1->score);  // 输入: 10107, 85

再次连接：p2->next = p1; p2 = p1;

head
  │
  ▼
  ┌───────────┬──────┐    ┌───────────┬──────┐    ┌───────────┐
  │ 10101     │ next─┼───>│ 10103     │ next─┼───>│ 10107     │
  │ 85      │      │    │ 90.0      │      │    │ 85.0      │
  └───────────┴──────┘    └───────────┴──────┘    └───────────┘
                                                       ▲
                                                  p1, p2

第六步：输入学号为 0，结束建表

p1 = (struct Student *)malloc(LEN);
scanf("%ld,%f", &p1->num, &p1->score);  // 输入: 0, 0
// p1->num <mark> 0，不满足 while 条件，退出循环
p2->next = NULL;    // 最后一个结点的 next 设为 NULL
free((void *)p1);   // 释放多余的结点

head
  │
  ▼
  ┌───────────┬──────┐    ┌───────────┬──────┐    ┌───────────┬──────┐
  │ 10101     │ next─┼───>│ 10103     │ next─┼───>│ 10107     │ NULL │
  │ 85      │      │    │ 90.0      │      │    │ 85.0      │      │
  └───────────┴──────┘    └───────────┴──────┘    └───────────┴──────┘

完整代码：创建链表函数 creat

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

#define LEN sizeof(struct Student)

struct Student {
    long num;
    float score;
    struct Student *next;
};

int n;  // 全局变量，记录结点个数

struct Student *creat(void)
{
    struct Student *head, *p1, *p2;
    n = 0;

    // 开辟第一个结点
    p1 = p2 = (struct Student *)malloc(LEN);
    scanf("%ld,%f", &p1->num, &p1->score);

    head = NULL;

    while (p1->num != 0)         // 学号为0时停止
    {
        n = n + 1;
        if (n </mark> 1)
            head = p1;           // 第一个结点：head 指向它
        else
            p2->next = p1;       // 非第一个：接到链表尾部

        p2 = p1;                 // p2 始终指向最后一个结点

        // 开辟下一个新结点
        p1 = (struct Student *)malloc(LEN);
        scanf("%ld,%f", &p1->num, &p1->score);
    }

    p2->next = NULL;             // 表尾置 NULL
    free((void *)p1);            // 释放多余分配的结点
    return head;                 // 返回头指针
}

Tip: 算法核心总结

• p1 总是开辟新结点——它是“探路者”
• p2 总是指向最后结点——它是“连接者”
• 用 p2->next = p1 连接两个结点
• 用 p2 = p1 让 p2 跟进到新尾部
• 学号为 0 时结束，p2->next = NULL 封尾

Caution: 注意事项

• malloc 每次只分配一个结点的空间
• 最后一次 malloc 分配的结点（学号为 0）不应接入链表，需要 free 释放
• creat 函数返回的是 head（头指针），调用者通过它访问整条链表

主函数调用示例

int main()
{
    struct Student *pt;
    pt = creat();       // 调用 creat 函数建立链表
    printf("\nnum:%ld\nscore:%5.1f\n", pt->num, pt->score);
    return 0;
}

---

4.4 输出链表

例题 10：编写输出链表的函数 print

题目：编写一个函数 print，将链表中所有结点的数据依次输出。

解题思路

输出链表的本质就是遍历——从头指针开始，逐个访问每个结点，直到遇到 NULL：

1. 让指针 p 指向链表第一个结点
2. 输出 p 所指结点的数据
3. 让 p 移向下一个结点（p = p->next）
4. 重复步骤 2-3，直到 p <mark> NULL

遍历过程图解

初始: p = head
     ↓
  ┌───────┬──────┐    ┌───────┬──────┐    ┌───────┬──────┐
  │ 1001  │ next─┼───>│ 1003  │ next─┼───>│ 1005  │ NULL │
  │ 67.5  │      │    │ 87.0  │      │    │ 90  │      │
  └───────┴──────┘    └───────┴──────┘    └───────┴──────┘

第1轮: 输出 1001 67.5，p = p->next → p 指向第2个结点
第2轮: 输出 1003 87.0，p = p->next → p 指向第3个结点
第3轮: 输出 1005 90，p = p->next → p = NULL
循环结束。

完整代码

void print(struct Student *p)
{
    printf("\nThese %d records are:\n", n);
    if (p != NULL)
        do {
            printf("%ld %5.1f\n", p->num, p->score);
            p = p->next;
        } while (p != NULL);
}

Attention: 空链表保护 函数开头先判断 p != NULL，避免对空链表执行 do-while 导致访问空指针崩溃。

完整主程序（创建 + 输出）

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

#define LEN sizeof(struct Student)

struct Student {
    long num;
    float score;
    struct Student *next;
};

int n;

// 创建链表
struct Student *creat(void)
{
    struct Student *head, *p1, *p2;
    n = 0;
    p1 = p2 = (struct Student *)malloc(LEN);
    scanf("%ld,%f", &p1->num, &p1->score);
    head = NULL;

    while (p1->num != 0)
    {
        n = n + 1;
        if (n </mark> 1)
            head = p1;
        else
            p2->next = p1;
        p2 = p1;
        p1 = (struct Student *)malloc(LEN);
        scanf("%ld,%f", &p1->num, &p1->score);
    }

    p2->next = NULL;
    free((void *)p1);
    return head;
}

// 输出链表
void print(struct Student *p)
{
    printf("\nThese %d records are:\n", n);
    if (p != NULL)
        do {
            printf("%ld %5.1f\n", p->num, p->score);
            p = p->next;
        } while (p != NULL);
}

int main()
{
    struct Student *pt;
    pt = creat();      // 建立链表
    print(pt);         // 输出链表
    return 0;
}

---

链表操作总结

核心操作一览

操作	关键语句	说明
创建结点	p = (struct Student *)malloc(LEN);	动态分配一个结点的内存
连接结点	p2->next = p1;	让前一个结点的 next 指向后一个
遍历链表	p = p->next;	指针后移，访问下一个结点
封闭表尾	p->next = NULL;	最后一个结点的 next 置空
释放结点	free(p);	释放不再需要的结点内存

链表 vs 数组

特性	数组	链表
内存分配	编译时，连续	运行时，不连续
大小	固定	可变
随机访问	O(1)（下标直接访问）	O(n)（需从头遍历）
插入/删除	O(n)（需移动元素）	O(1)（修改指针即可）
内存利用	可能浪费（预分配）	按需分配，无浪费

常见易错点

Danger: 易错警示

1. 忘记 p2->next = NULL：链表没有正确结尾，遍历时会访问野指针导致崩溃
2. 忘记 free：动态分配的内存不释放会导致内存泄漏
3. 混淆 p 和 *p：p 是指针（地址），*p 是指针所指的结点（数据）
4. p->next vs (*p).next：两者等价，-> 是结构体指针访问成员的语法糖
5. 空链表未判断：遍历前务必检查 head != NULL

---

课后练习

读程序题

阅读以下程序，写出输出结果：

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

struct NODE {
    int num;
    struct NODE *next;
};

void main()
{
    struct NODE *p, *q, *r;
    p = (struct NODE *)malloc(sizeof(struct NODE));
    q = (struct NODE *)malloc(sizeof(struct NODE));
    r = (struct NODE *)malloc(sizeof(struct NODE));

    p->num = 10;   q->num = 20;   r->num = 30;
    p->next = q;   q->next = r;

    printf("%d\n", p->num + q->next->num);
}

Question: 点击查看答案 输出：40

分析：

• p->num = 10
• q->next 指向 r，所以 q->next->num = r->num = 30
• 10 + 30 = 40

p ──> [10 | next] ──> q ──> [20 | next] ──> r ──> [30 | next]
       ↑                                     ↑
    p->num = 10                        q->next->num = 30

相关笔记

• c-pointers
• c-custom-types
• c-file-operations