链表（二）C 实现与头部插入

p5（13 分钟）、p6（12 分钟）

前置知识#

需要实用层面的 C/C++ 指针知识 + 动态内存分配概念。

建一个节点#

这一段的链表逻辑视图：3 个节点，地址分别是 200 / 100 / 300。

分配给每个节点的内存块地址完全是随机的，彼此没有关系，不能保证按升序降序排列或相邻，正因如此才需要保留链接。

NULL 是什么#

NULL 是「地址零的同义词或宏定义」，零是无效地址。

一个等于零或空值的指针变量，意味着该指针变量不指向有效的内存位置。

C 结构体定义#

1
struct node {
2
    int data;
3
    struct node *link;      /* 也可叫 next */
4
};

C 风格必须写 struct node *；C++ 直接写 node *。C++ 的写法看起来更干净。

链表的标识#

始终持有一个「指向节点的指针」变量，存第一个节点（头节点）地址。示例变量名 A。

这个指向头节点或第一个节点的特定指针变量的名称，也可理解为链表的名称。

建空表两步#

1
struct node *A;    /* 声明一个指向节点的指针 */
2
A = NULL;          /* 未指向任何地方 */

创建并插入第一个节点（顺序必须对）#

1
/* ① malloc 创建内存块（运行期分配的动态内存） */
2
temp = (struct node *)malloc(sizeof(struct node));
3

4
/* ② 填数据、调链接 */
5
(*temp).data = 2;
6
(*temp).link = NULL;
7

8
/* ③ 最后一步：让头指针指向它 */
9
A = temp;

几个要点：

malloc 返回的是 void 指针，必须做类型转换（因为 temp 是 node *）
处理动态内存的唯一方式是通过指针来引用此内存位置
temp 的作用是暂时存储节点的地址，直到我们恰当地固定所有的链接；之后 temp 可以挪作他用

箭头语法#

1
(*temp).data   等价于   temp->data

箭头 = 一个连字符 + 一个右尖括号。箭头写法更为常见。

C++ 建节点#

1
node *temp = new node;      /* 也可用 malloc */

new 操作符总是比 malloc 更受青睐，用 C++ 推荐 new。

遍历到链表末尾的通用逻辑#

这是全课出现频率最高的一段代码：

1
temp1 = head;
2
while (temp1->link != NULL)     /* 对最后一个节点，link == NULL 为假 → 退出 */
3
    temp1 = temp1->link;
4
temp1->link = temp;             /* 挂上新节点 */

打印元素只需把循环体换成 printf("%d ", temp1->data);。

一条核心纪律#

我们没有直接用变量 A 本身去遍历链表，因为如果修改 A 就会丢失头节点的地址。

A 永远不会被修改，无论哪个变量存储着头节点的地址都绝不会被修改，只有这些临时变量会被修改以便遍历链表。

所有链表代码都遵守这条纪律。

头部插入#

这一段是一个可运行的完整 C 程序。

节点定义与全局 head#

1
struct node {
2
    int data;
3
    struct node *link;
4
};
5

6
struct node *head;      /* 声明在所有函数之外（全局） */

main 流程#

1
head = NULL;
2
打印「多少个数字」→ 读入 N
3
循环 N 次：
4
    读入 X
5
    insert(X)
6
    print()

insert 实现顺序#

1
/* ① malloc 创建节点，用 temp 接收（假定地址 100） */
2
temp = (struct node *)malloc(sizeof(struct node));
3

4
/* ② 填数据 */
5
temp->data = x;
6

7
/* ③ 链接字段先置空 */
8
temp->next = NULL;
9

10
/* ④ 分两种情况 */
11
if (head == NULL) {
12
    head = temp;                    /* 链表为空：头指针指向新节点 */
13
} else {
14
    temp->next = head;              /* 先让新节点指向原头节点 */
15
    head = temp;                    /* 再让头指针指向新节点 */
16
}

一个重要简化#

第 ③ 行的 temp->next = NULL 只有当链表为空时才用得到。

因为空表时 head 本身就是 NULL，所以只写 temp->next = head 这一条语句就已经涵盖了链表为空的情形，从而避免写两条语句。

1
/* 简化版：一条语句覆盖两种情况 */
2
temp->next = head;
3
head = temp;

print 实现#

1
void print() {
2
    struct node *temp;              /* C 里必须写 struct node * */
3
    temp = head;
4
    while (temp != NULL) {
5
        printf("%d ", temp->data);
6
        temp = temp->next;
7
    }
8
}

为什么要用临时变量：不想修改头指针，否则会丢失第一个节点的引用。

在 C 里老是容易漏掉 struct node * 的写法。

运行结果#

输入 5 个数，依次插入 2、5、8、1、10，每次插入后打印：

插入	列表
2	`2`
5	`5 2`
8	`8 5 2`
1	`1 8 5 2`
10	`10 1 8 5 2`

这似乎能行得通。

head 不是全局时会怎样#

若 head 在 main 内声明为局部变量，其他函数访问不到 head，必须把首节点地址作为参数传进去。

print 函数#

参数命名为 head（也可以是 A、temp 等）。

这个参数 head 是 print 的局部变量，与 main 里的 head 是两个不同的变量；main 调用时是把值复制过去。

因此在 print 里可以不用临时变量，直接用这个参数 head 遍历——这里并没有修改这个 head。

insert 函数#

head 参数只是一份副本，但修改链表后 main 里的 head 也应当被修改。两种处理办法：

路线一：返回指针

1
struct node *insert(struct node *head, int x) {
2
    ...
3
    return head;        /* 返回修改后的 head */
4
}
5

6
/* main 里： */
7
head = insert(head, x);

路线二：按引用传递（双重指针）

1
void insert(struct node **head, int x) {
2
    ...
3
}
4

5
/* main 里： */
6
insert(&head, x);

因为 head 本身就是「指向节点的指针」，所以插入函数要接收指向指针节点的双重指针（struct node **head），函数内到处要写解引用，返回类型为 void。

两条路线都实际跑通并展示过。

坑#

绝不修改 head / A 本身，只用临时变量遍历；丢了头指针整条链就找不回来了。
malloc 必须做类型转换（C 里），否则编译器警告；C 里声明指针必须写 struct node *。
temp->next = NULL 在链表非空时是多余的，只写 temp->next = head 就能覆盖两种情况。
head 放全局还是传参要提前想清楚；传参就必须用「返回指针」或「双重指针」之一。
传参时 head 是副本，函数内改了不影响 main 里的；NULL 就是地址 0，不是随便一个特殊值。