使用结构和指针

本文为《C 与指针读书笔记》，感兴趣的读者可以去看原书。

你可以通过组合使用结构和指针创建强大的数据结构。

链表

链表(linked list)就一些包含数据的独立数据结构（通常称为节点）的集合。链表中的每个节点通过链或指针连接在一起。程序通过指针访问链表中的节点。通常节点是动态分配的，但有时你也能看到由节点数组构建的链表。即使在这种情况下，程序也是通过指针来遍历链表的。

单链表

在单链表中，每个节点包含一个指向链表下一节点的指针。链表最后一个节点的指针字段的值为NULL，提示链表后面不再有其他节点。在你找到链表的第1个节点后，指针就可以带你访问剩余的所有节点。为了记住链表的起始位置，可以使用一个根指针(root pointer)。根指针指向链表的第1个节点。注意根指针只是一个指针，它不包含任何数据。

typedef struct　NODE　 {
　　　　　struct　NODE　 *link;
　　　　　int　　　　　　　value;
} Node;

单链表可以通过链从开始位置遍历链表直到结束位置，但链表无法从相反的方向进行遍历。换句话说，当你的程序到达链表的最后一个节点时，如果你想回到其他任何节点，你只能从根指针从头开始。当然，程序在移动到下一个节点前可以保存一个指向当前位置的指针，甚至可以保存指向前面几个位置的指针。但是，链表是动态分配的，可能增长到几百或几千个节点，所以要保存所有指向前面位置的节点的指针是不可行的。

双链表

单链表的替代方案就是双链表。在一个双链表中，每个节点都包含两个指针——指向前一个节点的指针和指向后一个节点的指针。这可以使我们以任何方向遍历双链表，甚至可以忽前忽后地在双链表中访问。

typedf struct　NODE　 {
　　　　struct　NODE　 *fwd;
　　　　struct　NODE　 *bwd;
　　　　int　　　　　　　value;
} Node;

总结

单链表是一种使用指针来存储值的数据结构。链表中的每个节点包含一个字段，用于指向链表的下一个节点。另外有一个独立的根指针指向链表的第1个节点。由于节点在创建时是采用动态分配内存的方式，所以它们可能分布于内存之中。但是，遍历链表是根据指针进行的，所以节点的物理排列无关紧要。单链表只能以一个方向进行遍历。

为了把一个新值插入到一个有序的单链表中，你首先必须找到链表中合适的插入位置。对于无序单链表，新值可以插入到任何位置。把一个新节点链接到链表中需要两个步骤。首先，新节点的link字段必须设置为指向它的目标后续节点。其次，前一个节点的link字段必须设置为指向这个新节点。在许多其他语言中，插入函数保存一个指向前一个节点的指针来完成第2个步骤。但是，这个技巧使插入到链表的起始位置成为一种特殊情况，需要单独处理。在C语言中，你可以通过保存一个指向必须进行修改的link字段的指针，而不是保存一个指向前一个节点的指针，从而消除了这个特殊情况。

双链表中的每个节点包含两个link字段：其中一个指向链表的下一个节点，另一个指向链表的前一个节点。双链表有两个根指针，分别指向第1个节点和最后一个节点。因此，遍历双链表可以从任何一端开始，而且在遍历过程中可以改变方向。为了把一个新节点插入到双链表中，我们必须修改4个指针。新节点的前向和后向link字段必须被设置，前一个节点的后向link字段和后一个节点的前向link字段也必须进行修改，使它们指向这个新节点。

语句提炼是一种简化程序的技巧，其方法是消除程序中冗余的语句。如果一条if语句的“then”和“else”子句以相同序列的语句结尾，它们可以被一份单独的出现于if语句之后的拷贝代替。相同序列的语句也可以从if语句的起始位置提炼出来，但这种提炼不能改变if的测试结果。如果不同的语句事实上执行相同的功能，你可以把它们写成相同的样子，然后再使用语句提炼简化程序。

编程练习

练习 1

编写一个函数，反序排列一个单链表的所有节点。函数应该具有下面的原型：

　　　struct NODE * sll_reverse( struct NODE *first);

struct NODE {
    int value;            // 假设链表储存的是整数，你可以根据需要调整数据类型
    struct NODE *next;    // 指向下一个节点
};

#include <stdio.h>

struct NODE *sll_reverse(struct NODE *first) {
    struct NODE *prev = NULL;  // 前一个节点
    struct NODE *current = first;  // 当前遍历到的节点
    struct NODE *next = NULL;  // 下一个节点

    while (current != NULL) {
        next = current->next;  // 保存下一个节点
        current->next = prev;  // 反转当前节点的指向
        prev = current;  // 前移节点
        current = next;  // 使用之前保存的下一个节点继续遍历
    }
    first = prev;  // 更新头指针

    return first;  // 返回新的头指针
}

练习 2

编写一个程序，从一个单链表中移除一个节点。函数的原型应该如下：

　　　int sll_remove( struct NODE **rootp, struct NODE *node );

#include <stdlib.h>

int sll_remove(struct NODE **rootp, struct NODE *node) {
    // 检查空指针
    if (rootp == NULL || *rootp == NULL || node == NULL) {
        return 0;
    }

    struct NODE *current = *rootp;
    struct NODE *prev = NULL;

    while (current != NULL) {
        // 找到目标节点
        if (current == node) {
            // 如果目标节点是头节点
            if (prev == NULL) {
                *rootp = current->next;
            } else {
                // 让前驱节点指向目标节点的下一个节点
                prev->next = current->next;
            }
            // 释放目标节点的内存
            free(current);
            return 1;  // 成功移除
        }
        // 移向下一个节点
        prev = current;
        current = current->next;
    }

    return 0;  // 未找到指定节点
}

最后更新: November 17, 2024