0Pricing
C Academy · 课时

遍历与搜索

遍历链表

遍历与搜索 是 CoddyKit 上的免费 C Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

遍历链表

遍历是指按顺序访问每个节点。您从头指针开始，跟随 next 指针，直到到达 NULL。

几乎所有链表算法都建立在这种简单的遍历方式之上。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(10);
    head->next = make(20);
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d ", p->value);
    printf("\n");
    return 0;
}

遍历模式

标准循环使用一个移动指针 p：将它初始化为 head，在 p 不为 NULL 时继续执行，并使用 p = p->next 向前移动。

遍历时切勿修改 head 本身，否则会丢失链表的起点。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    struct Node *p = head;
    while (p) { printf("%d ", p->value); p = p->next; }
    printf("\n");
    return 0;
}

统计节点数量

要找出链表长度，请遍历链表，并为每个节点将计数器加一。

这是一个 O(n) 操作，因为计数值没有存储在任何地方。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int length(struct Node *head) {
    int n = 0;
    for (struct Node *p = head; p; p = p->next) n++;
    return n;
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    printf("length = %d\n", length(head));
    return 0;
}

求值的总和

遍历可以让您聚合数据。在这里，我们将链表中的所有整数值相加。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(5);
    head->next = make(10);
    int sum = 0;
    for (struct Node *p = head; p; p = p->next) sum += p->value;
    printf("sum = %d\n", sum);
    return 0;
}

搜索值

要查找某个值，请遍历链表并逐个比较节点。找到匹配项时返回该节点（或其位置）；如果到达末尾仍未找到，则表示失败。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

struct Node *find(struct Node *head, int v) {
    for (struct Node *p = head; p; p = p->next)
        if (p->value == v) return p;
    return NULL;
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    printf("found 2: %d\n", find(head, 2) != NULL);
    printf("found 9: %d\n", find(head, 9) != NULL);
    return 0;
}

查找位置

有时您需要的是匹配项的索引，而不是节点本身。遍历时维护一个计数器，在找到该值时返回计数器的值。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int index_of(struct Node *head, int v) {
    int i = 0;
    for (struct Node *p = head; p; p = p->next, i++)
        if (p->value == v) return i;
    return -1;
}

int main(void) {
    struct Node *head = make(7);
    head->next = make(8);
    printf("%d\n", index_of(head, 8));
    return 0;
}

访问第 n 个节点

链表不支持直接索引。要到达位置 n，您必须从头指针开始移动 n 次。

因此，与数组的 O(1) 相比，链表的随机访问复杂度是 O(n)。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

struct Node *at(struct Node *head, int n) {
    struct Node *p = head;
    for (int i = 0; i < n && p; i++) p = p->next;
    return p;
}

int main(void) {
    struct Node *head = make(10);
    head->next = make(20);
    head->next->next = make(30);
    printf("%d\n", at(head, 2)->value);
    return 0;
}

查找最后一个节点

要获取尾节点，请遍历链表，直到 p->next 为 NULL。该节点就是最后一个节点。

请注意空链表的情况，此时 head 本身就是 NULL。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    struct Node *p = head;
    while (p->next) p = p->next;
    printf("last = %d\n", p->value);
    return 0;
}

查找最大值

结合搜索和聚合操作，您可以在遍历过程中持续记录当前最佳值，从而找出最大值。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(3);
    head->next = make(9);
    head->next->next = make(5);
    int best = head->value;
    for (struct Node *p = head->next; p; p = p->next)
        if (p->value > best) best = p->value;
    printf("max = %d\n", best);
    return 0;
}

递归遍历

也可以递归遍历链表：先处理当前节点，然后对 next 递归调用。

这种方式很简洁，但使用的栈空间与链表长度成正比，因此对于非常长的链表，迭代更加安全。

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

void print_rec(struct Node *p) {
    if (!p) { printf("\n"); return; }
    printf("%d ", p->value);
    print_rec(p->next);
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    print_rec(head);
    return 0;
}

处理空链表

每个遍历函数都应妥善处理空链表（head == NULL）。

标准循环已经能够做到这一点：条件 p != NULL 会立即为假，因此循环体不会执行。

#include <stdio.h>

struct Node { int value; struct Node *next; };

int length(struct Node *head) {
    int n = 0;
    for (struct Node *p = head; p; p = p->next) n++;
    return n;
}

int main(void) {
    struct Node *head = NULL;
    printf("empty length = %d\n", length(head));
    return 0;
}

快速检查

测试您对链表遍历开销的理解。

回顾

您学习了如何遍历和搜索链表：

  • 遍历模式：从 head 开始，在不等于 NULL 时循环，并使用 p = p->next 向前移动。
  • 统计、求和和查找最大值都建立在遍历之上。
  • 搜索会比较每个节点；按索引访问的复杂度是 O(n)。
  • 遍历可以使用递归实现，但对于较长的链表，迭代更加安全；始终处理空链表的情况。

常见问题解答

「遍历与搜索」课时是免费的吗？

是的 — 「遍历与搜索」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「遍历与搜索」这节课中我会学到什么？

遍历链表 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。

「遍历与搜索」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 单向链表
  2. 插入与删除
  3. 遍历与搜索
  4. 双向链表
← 返回 C Academy