Lesson 24: 简单搜索引擎 CNB

练习任务

本课包含三个递进练习，逐步构建一个简单的 HTML 链接提取器——从网页源码中提取所有 <a href="..."> 链接，相当于一个极简搜索引擎的「爬虫解析」环节：

练习 1（find_istr 大小写不敏感查找）：实现 const char *find_istr(const char *text, const char *pattern) 函数，在 text 中查找 pattern 子串，忽略大小写。找到返回指向匹配位置的指针，未找到返回 NULL。

练习 2（extract_links 链接提取）：实现 int extract_links(const char *html) 函数，用 find_istr 查找所有 href= 出现位置，跳过属性名后提取引号内的 URL 并打印。

练习 3（search 综合程序）：组合 find_istr、extract_links 和 read_all（已提供），实现完整的 main：从 stdin 读取全部输入 → 提取链接 → 打印统计 → 释放内存。

提示：本课的核心是「字符串匹配 + 指针操作」的组合技巧。find_istr 中，你需要用 tolower() 把两边的字符都转成小写再比较；extract_links 中，找到 "href=" 后跳过 5 个字符，然后根据是否有引号来提取 URL。read_all 用 fread + realloc 动态扩容，这是处理未知大小输入的经典模式。回顾 Lesson 16 中 while (*dst++ = *src++) 的指针惯用法，本课的指针递进 (p += 5, p++) 是同一思想在不同场景下的应用。

核心知识点

字符串匹配与指针操作 — const char* 遍历、解引用 *p、指针递进 p++、p += n
大小写不敏感匹配 — tolower() 将字符统一转小写后比较，<ctype.h> 标准库
指针返回值语义 — find_istr 返回匹配位置指针（成功）或 NULL（失败），与 strstr 一致
指针递进与跳转 — p += 5 批量跳过已知前缀，p++ 逐字符推进
引号解析 — 检测 '\"' 和 '\'' 两种引号，根据引号类型决定 URL 结束条件
状态跟踪 — 用局部变量 quote 记录当前处于哪种引号内（或 0 表示无引号）
动态内存分配 — malloc(cap) 初始分配，realloc(buf, cap * 2) 按 2 倍扩容
fread 批量读取 — 一次读取最多 cap - len - 1 字节，比 fgetc 高效
缓冲区安全 — 始终保留 1 字节给 '\0'，防止越界写入
stdin 管道输入 — curl http://example.com | ./search 实现 Unix 管道组合
模块化函数组合 — 将问题拆为 find_istr → extract_links → read_all → main 四个独立模块
字符串解析经典模式 — 查找标记 → 跳过标记 → 提取内容 → 继续查找
搜索爬虫原理 — 提取链接 → 下载 → 再提取，递归遍历网页图

代码框架

练习 1：大小写不敏感子串查找

find_istr.c

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

const char *find_istr(const char *text, const char *pattern)
{
    // 在这里实现大小写不敏感的字符串查找:
    //   1. 计算 pattern 的长度: int plen = strlen(pattern);
    //   2. 外层 while (*text): 遍历 text 的每个起始位置
    //   3. 内层 for 循环: 逐个字符比较 tolower(text[i]) 和 tolower(pattern[i])
    //   4. 如果全部匹配 → return text (当前位置指针)
    //   5. 如果中途不匹配 → break 内层, text++ 继续外层
    //   6. 循环结束未找到 → return NULL
}

int main(void)
{
    char text[1024];
    char pattern[256];

    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = '\0';

    fgets(pattern, sizeof(pattern), stdin);
    pattern[strcspn(pattern, "\n")] = '\0';

    if (find_istr(text, pattern))
        printf("found\n");
    else
        printf("not found\n");

    return 0;
}

练习 2：HTML 链接提取

extract_links.c

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

#define MAX_URL 1024

// find_istr 已实现（来自练习 1）
static const char *find_istr(const char *text, const char *pattern)
{
    int plen = strlen(pattern);
    while (*text) {
        int match = 1;
        for (int i = 0; i < plen && text[i]; i++) {
            if (tolower(text[i]) != tolower(pattern[i])) {
                match = 0;
                break;
            }
        }
        if (match) return text;
        text++;
    }
    return NULL;
}

static int extract_links(const char *html)
{
    // 在这里实现链接提取:
    //   1. const char *p = html; int count = 0;
    //   2. while ((p = find_istr(p, "href=")) != NULL):
    //      a. p += 5;  // 跳过 "href=" 这 5 个字符
    //      b. 检查是否有引号: char quote = (*p == '"' || *p == '\'') ? *p++ : 0;
    //      c. char url[MAX_URL]; int i = 0;
    //      d. while 循环提取 URL 字符直到遇到闭合引号或空格/'>'
    //      e. url[i] = '\0'; printf("[%d] %s\n", ++count, url);
    //   3. return count;
}

int main(void)
{
    char html[4096];
    int total = 0;

    int len = 0;
    int n;
    while ((n = fread(html + len, 1, sizeof(html) - len - 1, stdin)) > 0)
        len += n;
    html[len] = '\0';

    total = extract_links(html);
    printf("\nTotal: %d links found.\n", total);

    return 0;
}

练习 3：综合搜索引擎

search.c

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

#define MAX_URL 1024

// 在这里实现 find_istr 函数

// 在这里实现 extract_links 函数

// read_all 已实现（读取全部 stdin 到动态分配的 buffer）
static char *read_all(FILE *fp)
{
    size_t cap = 4096, len = 0;
    char *buf = malloc(cap);
    if (!buf) return NULL;

    size_t n;
    while ((n = fread(buf + len, 1, cap - len - 1, fp)) > 0) {
        len += n;
        if (len + 1 >= cap) {
            cap *= 2;
            buf = realloc(buf, cap);
            if (!buf) return NULL;
        }
    }
    buf[len] = '\0';
    return buf;
}

int main(void)
{
    // 在这里实现主逻辑:
    //   1. char *html = read_all(stdin);   // 读取全部输入
    //   2. if (!html) return 1;            // 分配失败处理
    //   3. int total = extract_links(html); // 提取所有链接
    //   4. printf("\nTotal: %d links found.\n", total);
    //   5. free(html);                     // 释放内存
    //   6. return 0;
}

填充框架的关键思考：find_istr 返回的指针如何被 extract_links 使用？p += 5 跳过 "href=" 后 p 指向哪里？引号闭合的判断逻辑在单引号和双引号下是否一致？read_all 中为什么需要 cap - len - 1（预留 '\0' 空间）？

TIP

先不要往下翻看参考解答。尝试自己从 find_istr 开始实现——这个函数是后续所有功能的基础。做完后思考：如果 href 和 = 之间有空格（如 href = "..."），程序还能正常工作吗？这个问题会作为课堂讨论展开。

深度讲解

1. 字符串匹配：从精确匹配到大小写不敏感

1.1 回顾 Lesson 16：指针遍历字符串

在 Lesson 16（my_strcpy）中，我们学习了用指针遍历字符串的核心技巧：

pointer_traversal.c

const char *s = "Hello";

// 方式 1: 下标访问
for (int i = 0; s[i] != '\0'; i++)
    printf("%c", s[i]);

// 方式 2: 指针访问
for (const char *p = s; *p != '\0'; p++)
    printf("%c", *p);

两种方式等价——s[i] 就是 *(s + i) 的语法糖。指针版本的优势在于：不需要维护下标变量 i，指针本身的状态就编码了「当前处理到哪」。

指针遍历的内存视角:
  p ──→ ┌───┬───┬───┬───┬───┬───┐
        │ H │ e │ l │ l │ o │\0 │
        └───┴───┴───┴───┴───┴───┘
        *p = 'H'          当 *p == '\0' 时停止

  p++ 之后:
        ┌───┬───┬───┬───┬───┬───┐
        │ H │ e │ l │ l │ o │\0 │
        └───┴───┴───┴───┴───┴───┘
             p ──→ *p = 'e'

1.2 朴素子串匹配算法

子串查找的核心思想是「滑动窗口」：在文本 text 的每个位置，检查从该位置开始是否与模式串 pattern 完全匹配。

naive_search.c

const char *my_strstr(const char *text, const char *pattern)
{
    int plen = strlen(pattern);

    // 外层: 遍历 text 的每个起始位置
    while (*text) {
        int match = 1;

        // 内层: 从当前位置开始，逐个字符比较
        for (int i = 0; i < plen; i++) {
            if (text[i] != pattern[i]) {
                match = 0;
                break;          // 有一个不匹配就放弃这个位置
            }
        }

        if (match)
            return text;        // 找到！返回匹配起始位置

        text++;                 // 滑动窗口：尝试下一个位置
    }

    return NULL;                // 遍历完所有位置都未找到
}

滑动窗口示意 (text = "abcde", pattern = "cd"):

位置 0:  a b c d e
         c d
         ↑ 不匹配 (a≠c)

位置 1:  a b c d e
           c d
           ↑ 不匹配 (b≠c)

位置 2:  a b c d e
             c d
             ↑ ↑ 全部匹配! → 返回 text+2

NOTE

这个朴素算法的时间复杂度是 O(n × m)，其中 n 是 text 长度，m 是 pattern 长度。KMP、Boyer-Moore 等高级算法能将复杂度降至 O(n + m)，但朴素算法足够理解本课的核心概念。实际上，对于本课涉及的短模式串（"href=" 仅 5 个字符），朴素算法已经足够高效。

1.3 引入大小写不敏感：tolower()

HTML 中的属性名不区分大小写——href、HREF、Href 都表示同一个属性。我们需要在比较时将两边字符统一转成小写：

case_insensitive_comparison.c

#include <ctype.h>

// tolower('A') → 'a'
// tolower('Z') → 'z'
// tolower('a') → 'a'  (已经小写，不变)
// tolower('9') → '9'  (数字不变)
// tolower('=') → '='  (符号不变)

tolower() 来自 <ctype.h>，它只对大写字母 A-Z 做转换，其他字符保持不变。这让我们可以安全地对任意字符调用它。

find_istr_implementation.c

const char *find_istr(const char *text, const char *pattern)
{
    int plen = strlen(pattern);

    while (*text) {
        int match = 1;
        for (int i = 0; i < plen && text[i]; i++) {
            if (tolower(text[i]) != tolower(pattern[i])) {
                match = 0;
                break;
            }
        }
        if (match) return text;
        text++;
    }
    return NULL;
}

关键改动只有一行：将 text[i] != pattern[i] 改为 tolower(text[i]) != tolower(pattern[i])。其他逻辑与精确匹配完全相同。

find_istr_demo.c

#include <stdio.h>

int main(void)
{
    // 大小写混合测试
    printf("%s\n", find_istr("Hello World", "WORLD") ? "found" : "not found");
    // → found

    printf("%s\n", find_istr("<a HREF='...'>", "href") ? "found" : "not found");
    // → found

    printf("%s\n", find_istr("abc", "xyz") ? "found" : "not found");
    // → not found
    return 0;
}

tolower 转换示意:
  text:    "Hello World"
  pattern: "WORLD"

  比较 text[i] vs pattern[i]:
  H(72) vs W(87) → 不匹配 → break

  text++ 后:
  text+6:  "World"
  pattern: "WORLD"

  比较 tolower('W')='w' vs tolower('W')='w' ✓
        tolower('o')='o' vs tolower('O')='o' ✓
        tolower('r')='r' vs tolower('R')='r' ✓
        tolower('l')='l' vs tolower('L')='l' ✓
        tolower('d')='d' vs tolower('D')='d' ✓
  → 全部匹配! return text+6

NOTE

tolower() 接受 int 参数并返回 int，但实际使用时传入 char 值（会被隐式提升为 int）。对于 ASCII 字符（0-127），tolower() 的行为在所有平台上一致。

1.4 指针返回值的语义

find_istr 返回 const char* 而不是 int 索引，这遵循了 C 标准库的惯例。与标准库的 strstr、strchr 一致：成功返回匹配位置指针，失败返回 NULL。返回指针可以直接作为新的搜索起点（find_istr(pos + 1, "href=")），而返回索引则需要额外做 text + idx 转换。

2. HTML 链接提取：指针操作与引号解析

2.1 问题建模：从 HTML 到链接列表

HTML 中的链接形如：

html

<a href="https://example.com">点击这里</a>
<a href='https://other.com'>另一个</a>

我们需要从这段文本中提取出 https://example.com 和 https://other.com。问题的核心是：

定位：找到 href= 这个标记
跳过：越过 href= 本身（5 个字符）
识别：判断 URL 用什么引号包围（" 或 ' 或无引号）
提取：从引号后开始读取，直到遇到闭合引号
循环：从当前位置继续查找下一个 href=

解析过程示意:

HTML: <a href="https://x.com"><a HREF='https://y.org'>

步骤 1: find_istr(html, "href=") → 指向 'h' 在 "href=" 处
        <a href="https://x.com"><a HREF='https://y.org'>
           ^
步骤 2: p += 5 → 跳过 "href="
        <a href="https://x.com"><a HREF='https://y.org'>
                ^
步骤 3: *p == '"' → quote = '"', p++
        <a href="https://x.com"><a HREF='https://y.org'>
                 ^
步骤 4: 读取 URL 字符直到遇到闭合引号 '"'
        → url = "https://x.com"
步骤 5: 从 p 继续 find_istr(p, "href=") → 找到 "HREF="
        <a href="https://x.com"><a HREF='https://y.org'>
                                   ^

2.2 指针递进：p += n 的跳转技巧

p += 5 是本课中最关键的指针操作之一。它不是逐字符移动，而是一次性跳过 5 个已知字符：

skip_href_equals.c

p = find_istr(p, "href=");    // p 指向匹配位置的 'h'
p += 5;                       // 跳过 'h','r','e','f','=' → 指向引号或 URL 首字符

p 的变化:
  找到后: ...href="...
          ^
          p (find_istr 返回)

  p+=5:  ...href="...
               ^
               p (现在指向引号)

IMPORTANT

指针加法 p += n 的前提是 p 指向的内存后面至少有 n 个可读字节。在本课中，find_istr 保证了 p 指向的匹配位置之后至少有 strlen("href=") 个字符，所以 p += 5 是安全的。

2.3 引号解析：状态跟踪

HTML 中的属性值可以用双引号、单引号包围，也可以不加引号（如果值不含空格）。我们需要根据第一个字符判断：

quote_detection.c

char quote = 0;                     // 0 表示无引号

if (*p == '"' || *p == '\'') {      // 检测引号
    quote = *p;                     // 记录引号类型
    p++;                            // 跳过开始的引号
}
// 现在 p 指向 URL 的第一个字符

之后提取 URL 时，结束条件取决于 quote：

url_extraction_loop.c

char url[MAX_URL];
int i = 0;

while (*p && i < MAX_URL - 1) {
    if (quote && *p == quote)       // 有引号：遇到匹配的闭合引号就停
        break;
    if (!quote && (*p == ' ' || *p == '>'))  // 无引号：遇到空格或 '>' 就停
        break;
    url[i++] = *p++;
}
url[i] = '\0';

三种情况对比：

quote_cases.c

// 情况 1: 双引号 — quote = '"'
// <a href="http://a.com">
// 提取: 跳过 '"' → 读取直到下一个 '"' → url = "http://a.com"

// 情况 2: 单引号 — quote = '\''
// <a href='http://b.com'>
// 提取: 跳过 '\'' → 读取直到下一个 '\'' → url = "http://b.com"

// 情况 3: 无引号 — quote = 0
// <a href=http://c.com>
// 提取: 读取直到空格或 '>' → url = "http://c.com"

状态机视角:

      检测到 '"'                    检测到 '\''
  ┌──────────────┐            ┌──────────────┐
  │ 双引号模式    │            │ 单引号模式    │
  │ 读到下一个 '"' │            │ 读到下一个 '\''│
  └──────────────┘            └──────────────┘
       ▲                            ▲
       │ quote = '"'                │ quote = '\''
       │                            │
  ┌────┴────────────────────────────┴────┐
  │           初始状态 (quote = 0)         │
  │     检查 *p 是否为引号字符             │
  └────┬────────────────────────────┬────┘
       │ 不是引号                    │
       ▼                            ▼
  ┌──────────────┐            遇到空格或 '>'
  │ 无引号模式    │──────────▶ 提取结束
  │ 读到空格或'>' │
  └──────────────┘

2.4 完整 extract_links 实现

extract_links_full.c

static int extract_links(const char *html)
{
    const char *p = html;
    int count = 0;

    while ((p = find_istr(p, "href=")) != NULL) {
        p += 5;                         // 跳过 "href="

        // 检测引号
        char quote = (*p == '"' || *p == '\'') ? *p++ : 0;

        // 提取 URL
        char url[MAX_URL];
        int i = 0;
        while (*p && i < MAX_URL - 1) {
            if (quote && *p == quote)   // 遇到闭合引号
                break;
            if (!quote && (*p == ' ' || *p == '>'))  // 无引号时遇空格或 '>'
                break;
            url[i++] = *p++;
        }
        url[i] = '\0';

        if (i > 0)                      // 忽略空 URL
            printf("[%d] %s\n", ++count, url);
    }

    return count;
}

循环流程跟踪（输入 <a href="http://a.com"><a HREF='http://b.org'>）：

迭代	`p` 初始位置	`find_istr` 找到	`p+=5` 后	`quote`	提取结果
1	`html` (偏移 0)	`"href="` (偏移 3)	指向 `"`	`'"'`	`http://a.com`
2	继续从上次 `p`	`"HREF="` (偏移 25)	指向 `'`	`'\''`	`http://b.org`
3	继续	`NULL` (未找到)	—	—	循环结束

WARNING

本课实现的 extract_links 是简化版 HTML 解析器，它有已知的局限性：

如果 href 和 = 之间有空格（href = "..."），find_istr("href=") 不会匹配
如果 URL 中包含转义引号（href="a\"b"），提取结果会提前截断
不处理 href 出现在注释  或 <script> 标签内的情况这些局限性正是课堂讨论中值得探讨的话题。

3. 动态内存与文件读取：read_all

3.1 为什么需要动态内存

前面的练习中，我们用固定大小的数组来存储 HTML：

fixed_buffer_limitation.c

char html[4096];    // 只能容纳最多 4095 个字符的 HTML

但真实的网页可能远超 4KB——一个典型新闻网站首页的 HTML 轻松超过 100KB。固定大小数组有三个问题：

太小：大网页装不下，数据被截断
太大：小网页浪费栈空间（4096 字节全占满）
不可预测：事先不知道输入大小

动态内存解决了这些问题：按需分配，不够就扩容。

3.2 malloc：按需分配

malloc_basics.c

#include <stdlib.h>

char *buf = malloc(4096);       // 从堆上分配 4096 字节
if (buf == NULL) {              // 必须检查分配是否成功
    fprintf(stderr, "malloc failed\n");
    return 1;
}
// 使用 buf...
free(buf);                      // 用完后释放

malloc(n) 从堆（heap）上分配 n 字节连续内存，返回 void* 指针。堆内存的生命周期由程序员控制——直到调用 free() 才归还系统，这与栈上自动释放的局部变量完全不同。

3.3 realloc：动态扩容

当已分配的缓冲区不够用时，realloc 可以在保留原有数据的前提下扩大（或缩小）内存：

realloc_demo.c

char *buf = malloc(4096);       // 初始 4KB

// ... 用了 4000 字节，快满了 ...

char *new_buf = realloc(buf, 8192);  // 尝试扩容到 8KB
if (new_buf == NULL) {
    // 扩容失败，原 buf 仍然有效
    free(buf);
    return 1;
}
buf = new_buf;                  // 更新指针

// 注意: 必须用新指针覆盖旧指针！
// 如果写成 realloc(buf, 8192) 且失败返回 NULL，
// buf 会丢失，造成内存泄漏

realloc 的行为：如果当前块后面有足够空间，原地扩展返回原地址；如果空间不足，分配新块 → 拷贝数据 → 释放旧块 → 返回新地址。

CAUTION

realloc 失败时返回 NULL，但原来的内存不会被释放。正确的写法是先用临时指针接收返回值，检查成功后再覆盖原指针。如果直接写 buf = realloc(buf, new_size)，一旦失败，buf 变成 NULL，原来的内存就永远无法释放了。

3.4 fread：批量读取

fread_basics.c

size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream);
// 从 stream 读取 nmemb 个元素，每个元素 size 字节
// 返回实际读取的元素个数

// 读取最多 4095 字节到 buf:
size_t n = fread(buf, 1, 4095, stdin);
// n = 实际读取的字节数

与 fgetc 逐字节读取相比，fread 一次性读取多个字节，大幅减少函数调用开销。fgetc 读 4096 字节需要 4096 次调用，fread 只需一次。

3.5 read_all 完整剖析

read_all_annotated.c

static char *read_all(FILE *fp)
{
    size_t cap = 4096;              // 初始容量: 4KB
    size_t len = 0;                 // 已读取的字节数
    char *buf = malloc(cap);        // 初始分配
    if (!buf) return NULL;

    size_t n;
    while ((n = fread(buf + len, 1, cap - len - 1, fp)) > 0) {
        //          ↑                ↑
        //    写入位置: buf+len   最多读取字节数: cap-len-1
        //                        (预留 1 字节给 '\0')

        len += n;                   // 更新已读长度

        if (len + 1 >= cap) {       // 快满了？
            cap *= 2;               // 容量翻倍
            buf = realloc(buf, cap);
            if (!buf) return NULL;  // 扩容失败
        }
    }
    buf[len] = '\0';                // 添加字符串终止符
    return buf;
}

扩容策略：2 倍增长

为什么不每次加固定大小（如 4096）？因为 2 倍增长能保证均摊 O(1) 的时间复杂度：

2 倍扩容:                     固定扩容 (+4096):
容量: 4K → 8K → 16K → 32K    容量: 4K → 8K → 12K → 16K
拷贝: 4+8+16 = 28K            拷贝: 4+8+12+16 = 40K
扩容次数: 3 次                 扩容次数: 3 次

读取 100KB:
2倍: 4→8→16→32→64→128 (5次扩容, 拷贝 124KB)
固定: 4→8→12→...→100 (24次扩容, 拷贝 ≈ 1250KB!)

cap - len - 1 中的 -1：

// 如果读取 cap - len 字节:
fread(buf + len, 1, cap - len, fp);   // 可能填满整个 buffer
buf[cap] = '\0';                       // ❌ 越界写入!

// 正确: 预留 1 字节给 '\0'
fread(buf + len, 1, cap - len - 1, fp);
buf[len] = '\0';                       // ✅ 安全

缓冲区布局:
┌──────────────────────────────────┬───┐
│     已使用 (len 字节)              │ ? │ ← 预留 '\0' 位置
└──────────────────────────────────┴───┘
  buf                          buf+len  buf+cap-1

fread 写入范围: buf+len ~ buf+cap-2 (最多 cap-len-1 字节)
'\0' 位置:      buf+len (写入数据后)

3.6 stdin 管道与 Unix 哲学

read_all(stdin) 的设计让程序可以与管道无缝配合：

bash

# 方式 1: 从文件读取
./search < page.html

# 方式 2: 从 curl 管道读取
curl -s https://example.com | ./search

# 方式 3: 从 wget 管道读取
wget -q -O - https://example.com | ./search

# 方式 4: 交互输入（Ctrl+D 结束）
./search
<paste HTML here>
Ctrl+D

这体现了 Unix 哲学中的「组合原则」——每个程序做好一件事，通过管道连接。我们的 search 程序只做「提取链接」这一件事，数据来源由调用者决定。

4. 字符串解析的经典模式

4.1 查找-提取-继续模式

extract_links 体现了一个通用的字符串解析模式：

parse_pattern.c

const char *p = text;
while ((p = find_marker(p, "MARKER")) != NULL) {
    p += skip_len;                  // 跳过标记
    extract_content(p, &result);    // 提取内容
    // p 已经被 extract_content 推进到内容之后
}

这个模式适用于许多场景：

场景	标记	提取内容
提取链接	`href=`	URL
提取邮箱	`mailto:`	邮箱地址
提取图片	`src=`	图片 URL
提取标题	`<title>`	标题文本
提取脚本	`<script`	JavaScript 代码

4.2 指针即游标

在 C 语言中，const char *p 不仅是「指向字符的指针」，更是「字符串中的游标」——它标记着当前解析到哪个位置：

pointer_as_cursor.c

const char *p = "<a href='x'><img src='y'>";

// 游标模式: p 始终指向「下一个待处理的字符」
p = find_istr(p, "href=");  // 移动游标到 href=
p += 5;                     // 游标前移到 URL 开始
// ... 提取 URL，游标移到 URL 之后 ...
p = find_istr(p, "src=");   // 从当前游标继续搜索

这种「指针即游标」的风格是 C 语言字符串处理的精髓——不需要额外的索引变量，指针本身就携带了位置信息。

4.3 与 Lesson 16 的联系

Lesson 16 中的 while (*dst++ = *src++) 和本课的 p += 5 以及 url[i++] = *p++，本质上都是同一类操作——通过移动指针来遍历和处理数据：

pointer_patterns.c

// Lesson 16: 逐字符复制（两个指针同步移动）
while ((*dst++ = *src++))
    ;

// 本课: 批量跳过已知内容（单指针跳转）
p += 5;

// 本课: 逐字符提取到缓冲区（读指针 + 写索引）
url[i++] = *p++;

// 共同思想: 指针 = 当前位置，移动指针 = 推进处理进度

5. 从链接提取到搜索引擎

5.1 搜索引擎的工作原理

本课的程序虽然简单，但触及了搜索引擎的核心流程：

真正的搜索引擎:
┌──────────┐    ┌──────────┐    ┌──────────┐    ┌──────────┐
│ 爬虫      │ → │ 解析器    │ → │ 索引器    │ → │ 查询引擎  │
│ 下载网页   │    │ 提取链接   │    │ 建立倒排   │    │ 响应用户   │
│            │    │ 和文本    │    │ 索引       │    │ 搜索       │
└──────────┘    └──────────┘    └──────────┘    └──────────┘
                     ↑
                本课实现的部分

我们实现的 extract_links 是解析器的极简版本——它只提取链接，不提取正文内容。但「查找标记 → 提取内容」的思路是相通的。

5.2 递归爬取的雏形

有了链接列表，下一步自然是从每个链接下载新页面并继续提取：

recursive_crawler_concept.c

// 伪代码：递归爬虫
void crawl(const char *url, int depth)
{
    if (depth > MAX_DEPTH) return;

    char *html = download(url);          // 下载网页
    char **links = extract_links(html);  // 提取所有链接

    for (int i = 0; links[i]; i++) {
        if (!visited(links[i])) {        // 去重
            mark_visited(links[i]);
            crawl(links[i], depth + 1);  // 递归爬取
        }
    }

    free(html);
}

这就是 Google、Baidu 等搜索引擎爬虫的核心逻辑——从一个种子 URL 开始，不断发现新链接，递归爬取整个互联网的网页图。爬虫需要处理去重（同一 URL 不重复下载）、深度控制（避免无限递归）和礼貌性（控制请求频率，遵守 robots.txt）。

6. 常见陷阱与健壮性设计

6.1 空指针与空输入

本课的函数都假设输入是合法的——text 和 pattern 不是 NULL，HTML 是以 '\0' 结尾的有效字符串。但在真实环境中，这些假设不一定成立：

null_safety.c

// 健壮的 find_istr 应该在开头加上:
const char *find_istr(const char *text, const char *pattern)
{
    if (!text || !pattern)          // 防御 NULL 指针
        return NULL;

    int plen = strlen(pattern);
    if (plen == 0)                  // 空 pattern 的语义: 匹配开头
        return text;

    // ... 原有逻辑 ...
}

三条防御性规则：

NULL 检查：外部传入的指针永远不能假设非 NULL
空字符串处理：空 pattern 的语义需要明确定义（strstr 对空 pattern 返回 text 自身）
越界保护：text[i] 访问前确保 i < strlen(text) 或在循环条件中检查 text[i] != '\0'

6.2 经典内存错误

动态内存管理是 C 语言中 bug 最密集的领域。以下错误模式需要警惕：

memory_bugs.c

// 错误 1: malloc 后不检查 NULL
char *buf = malloc(4096);
buf[0] = 'A';                       // 如果 malloc 失败，段错误！

// 错误 2: 内存泄漏 (忘 free 或提前 return)
char *buf = malloc(4096);
if (some_condition) return NULL;    // buf 泄漏了！
free(buf);

// 错误 3: 使用已释放的内存 (use-after-free)
char *buf = malloc(4096);
free(buf);
printf("%s\n", buf);                // 未定义行为！

// 错误 4: 重复释放 (double free)
char *buf = malloc(4096);
free(buf);
free(buf);                          // 未定义行为，可能崩溃

// 正确模式: 在 free 后将指针置为 NULL
char *buf = malloc(4096);
// ... use buf ...
free(buf);
buf = NULL;                         // 安全的习惯: 防止意外重用

CAUTION

使用 valgrind --leak-check=full ./search 可以检测内存泄漏和上述错误。养成在开发过程中定期运行 valgrind 的习惯，它会在程序退出时报告所有尚未释放的内存块。

6.3 realloc 的失效模式

realloc 是最容易被误用的内存函数：

realloc_pitfalls.c

// 模式 1: 直接覆盖原指针 (失败时泄漏)
buf = realloc(buf, new_size);       // 如果失败，buf 变成 NULL
                                     // 原来的内存丢失了！

// 正确: 用临时指针
char *new_buf = realloc(buf, new_size);
if (new_buf) {
    buf = new_buf;
} else {
    // realloc 失败，buf 仍然有效，可以选择继续用或 free
}

// 模式 2: realloc(NULL, size) 等价于 malloc(size)
char *buf = realloc(NULL, 4096);    // 合法，等于 malloc(4096)

// 模式 3: realloc(ptr, 0) 等价于 free(ptr)
buf = realloc(buf, 0);              // 释放内存，返回 NULL (可能)

6.4 缓冲区溢出的边界保护

buffer_overflow_protection.c

// 脆弱版本: 没有边界保护
while (*p) {
    buf[i++] = *p++;     // 如果输入无限长，buf 会溢出
}

// 安全版本: 始终检查 MAX - 1
while (*p && i < MAX - 1) {
    buf[i++] = *p++;
}
buf[i] = '\0';          // 确保终止符

// 更严格的: 截断后告警
if (*p) {
    fprintf(stderr, "Warning: buffer truncated at %d bytes\n", MAX - 1);
}

7. 性能考量和实际应用扩展

7.1 朴素算法的实际性能

对于本课的典型场景（HTML < 1MB, pattern = "href=" 仅 5 字符），朴素 O(n×m) 算法的实际表现：

输入大小     比较次数      耗时 (现代 CPU)
10 KB        ~50,000       < 1 ms
100 KB       ~500,000      ~1 ms
1 MB         ~5,000,000    ~10 ms
10 MB        ~50,000,000   ~100 ms

结论: 对于日常使用 (< 1MB)，优化不是必须的。

什么时候需要优化？

文本 > 10 MB 且需要多次搜索
Pattern 长度 > 100（KMP/Boyer-Moore 优势明显）
需要搜索多个 pattern（Aho-Corasick 自动机）

7.2 更健壮的 HTML 解析

本课的 extract_links 是教学简化版。真正的 HTML 链接提取需要处理更多情况：

robust_parsing_needs.c

// 需要处理的边缘情况:
// 1. href 和 = 之间有空格:    href = "url"
// 2. 属性值中可能有转义引号:  href="a\"b"
// 3. <script> 标签内的字符串:  var s = "<a href='x'>";
// 4. HTML 注释中的链接:        <!-- <a href="x"> -->
// 5. 实体编码:                 href="page?x=1&amp;y=2" (需要解码 &amp;)
// 6. 大小写混合的标签:         <A HREF="x">
// 7. 多行属性:                 href=
//                              "url"

生产环境使用 libxml2、Gumbo 等成熟的 HTML 解析库，不要重复发明轮子——本课的目的是理解底层原理，而非写出生产级解析器。

7.3 用本课知识构建的完整工具链

本课学到的技术可以组合为一个实用的命令行工具链：

bash

# 下载并提取链接
curl -s https://example.com | ./search | tee links.txt

# 过滤绝对 URL
./search < page.html | grep "^\[" | grep "http" > urls.txt

# 提取域名统计
./search < page.html | ./domain_stats > domains.txt

# 批量下载提取的链接
cat urls.txt | while read url; do curl -s "$url" -o "pages/$(basename $url).html"; done

这就是 Unix 管道的威力——每个程序做一件事，通过管道组合解决复杂问题。

参考解答

练习 1: find_istr 参考解答

find_istr_solution.c

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

const char *find_istr(const char *text, const char *pattern)
{
    int plen = strlen(pattern);

    while (*text) {
        int match = 1;
        for (int i = 0; i < plen && text[i]; i++) {
            if (tolower(text[i]) != tolower(pattern[i])) {
                match = 0;
                break;
            }
        }
        if (match) return text;
        text++;
    }
    return NULL;
}

int main(void)
{
    char text[1024];
    char pattern[256];

    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = '\0';

    fgets(pattern, sizeof(pattern), stdin);
    pattern[strcspn(pattern, "\n")] = '\0';

    if (find_istr(text, pattern))
        printf("found\n");
    else
        printf("not found\n");

    return 0;
}

解析：外层 while (*text) 遍历每个可能的起始位置。内层 for 循环逐一比较 tolower(text[i]) 和 tolower(pattern[i])——这是大小写不敏感的关键。注意 && text[i] 条件防止在 text 剩余长度不足 plen 时越界访问。strcspn(text, "\n") 用于去除 fgets 读取的换行符，这是一种比手动循环更简洁的写法。

练习 2: extract_links 参考解答

extract_links_solution.c

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

#define MAX_URL 1024

static const char *find_istr(const char *text, const char *pattern)
{
    int plen = strlen(pattern);
    while (*text) {
        int match = 1;
        for (int i = 0; i < plen && text[i]; i++) {
            if (tolower(text[i]) != tolower(pattern[i])) {
                match = 0;
                break;
            }
        }
        if (match) return text;
        text++;
    }
    return NULL;
}

static int extract_links(const char *html)
{
    const char *p = html;
    int count = 0;

    while ((p = find_istr(p, "href=")) != NULL) {
        p += 5;

        char quote = (*p == '"' || *p == '\'') ? *p++ : 0;

        char url[MAX_URL];
        int i = 0;
        while (*p && i < MAX_URL - 1) {
            if (quote && *p == quote) break;
            if (!quote && (*p == ' ' || *p == '>')) break;
            url[i++] = *p++;
        }
        url[i] = '\0';

        if (i > 0)
            printf("[%d] %s\n", ++count, url);
    }

    return count;
}

int main(void)
{
    char html[4096];
    int total = 0;

    int len = 0;
    int n;
    while ((n = fread(html + len, 1, sizeof(html) - len - 1, stdin)) > 0)
        len += n;
    html[len] = '\0';

    total = extract_links(html);
    printf("\nTotal: %d links found.\n", total);

    return 0;
}

解析：extract_links 的核心是一个 while ((p = find_istr(p, "href=")) != NULL) 循环——每次找到 href= 后处理，然后从当前位置继续搜索。p += 5 跳过 "href=" 这 5 个字符。引号检测使用三元运算符 (*p == '"' || *p == '\'') ? *p++ : 0，同时完成检测和指针递进。URL 提取循环中 MAX_URL - 1 为 '\0' 预留位置，防止缓冲区溢出。

练习 3: search 参考解答

search_solution.c

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

#define MAX_URL 1024

static const char *find_istr(const char *text, const char *pattern)
{
    int plen = strlen(pattern);
    while (*text) {
        int match = 1;
        for (int i = 0; i < plen && text[i]; i++) {
            if (tolower(text[i]) != tolower(pattern[i])) {
                match = 0;
                break;
            }
        }
        if (match) return text;
        text++;
    }
    return NULL;
}

static int extract_links(const char *html)
{
    const char *p = html;
    int count = 0;
    while ((p = find_istr(p, "href=")) != NULL) {
        p += 5;
        char quote = (*p == '"' || *p == '\'') ? *p++ : 0;
        char url[MAX_URL];
        int i = 0;
        while (*p && i < MAX_URL - 1) {
            if (quote && *p == quote) break;
            if (!quote && (*p == ' ' || *p == '>')) break;
            url[i++] = *p++;
        }
        url[i] = '\0';
        if (i > 0) printf("[%d] %s\n", ++count, url);
    }
    return count;
}

static char *read_all(FILE *fp)
{
    size_t cap = 4096, len = 0;
    char *buf = malloc(cap);
    if (!buf) return NULL;

    size_t n;
    while ((n = fread(buf + len, 1, cap - len - 1, fp)) > 0) {
        len += n;
        if (len + 1 >= cap) {
            cap *= 2;
            buf = realloc(buf, cap);
            if (!buf) return NULL;
        }
    }
    buf[len] = '\0';
    return buf;
}

int main(void)
{
    char *html = read_all(stdin);
    if (!html) {
        fprintf(stderr, "Failed to read input\n");
        return 1;
    }

    int total = extract_links(html);
    printf("\nTotal: %d links found.\n", total);

    free(html);
    return 0;
}

解析：main 函数展示了三个模块的组合方式：read_all 负责输入 → extract_links 负责处理 → free 负责清理。read_all 使用 2 倍扩容策略，cap - len - 1 为 '\0' 预留 1 字节空间。free(html) 在程序结束前释放堆内存——虽然程序退出时操作系统会回收所有内存，但显式 free 是良好的编程习惯，也方便用 Valgrind 等工具检测内存泄漏。

课堂讨论

本课的 find_istr 使用朴素算法（O(n×m)）。如果要搜索很长的 HTML 文件（如 1MB），有什么方法可以提升性能？tolower() 的调用在性能上有什么影响？
extract_links 中，如果 href 和 = 之间有空格（href = "..."），程序还能找到链接吗？如果不能，应该如何修改代码来支持这种情况？
read_all 使用 realloc(buf, cap * 2) 进行 2 倍扩容，而不是每次增加固定大小（如 +4096）。为什么 2 倍扩容更高效？从均摊时间复杂度的角度分析。
如果要支持递归爬取（提取链接 → 下载新页面 → 再提取），现有代码需要做哪些扩展？如何避免重复爬取同一个 URL？
如果 HTML 中包含 href="javascript:void(0)" 或 href="#top" 这类非 HTTP 链接，程序也会提取出来。如何过滤只保留以 http:// 或 https:// 开头的绝对 URL？
本课的程序使用 printf 输出结果到 stdout。如果要让程序成为一个可复用的库函数（返回链接列表而非直接打印），函数签名应该如何设计？返回 char** 有什么挑战？

讨论答案

Q1: find_istr 性能优化与 tolower 的影响

对于长文本搜索，朴素算法 O(n×m) 在 n=1MB、m=5 时约需 500 万次比较，在现代 CPU 上仍然很快。真正的性能瓶颈在于 tolower() 的函数调用开销。

优化方向：

内联 tolower：(c >= 'A' && c <= 'Z') ? c + 32 : c，消除函数调用开销。
Boyer-Moore-Horspool 算法：通过坏字符规则跳过更多字符，减少比较次数。
先精确匹配再验证：先用快速的 strstr 精确匹配 "href="，找到后再用大小写不敏感方式验证。

tolower_inline.c

// 内联版本：避免函数调用
#define TO_LOWER(c) ((c) >= 'A' && (c) <= 'Z' ? (c) + 32 : (c))

对于本课的场景（输入通常不超过几百 KB），朴素算法完全够用。理解算法原理比过早优化更重要。

Q2: href 和 = 之间有空格的处理

当前代码使用 find_istr(p, "href=") 精确查找 "href=" 这 5 个连续字符。如果 HTML 写成 href = "..."（href 和 = 之间有空格），find_istr 不会匹配，程序将漏掉这个链接。

修复方案：

skip_whitespace.c

// 改为先查找 "href"，然后跳过空白再检查 '='
while ((p = find_istr(p, "href")) != NULL) {
    p += 4;                     // 跳过 "href"
    // 跳过空白字符
    while (*p == ' ' || *p == '\t' || *p == '\n') p++;
    if (*p != '=') continue;    // 不是 href=，继续搜索
    p++;                        // 跳过 '='
    // 跳过 '=' 后面的空白
    while (*p == ' ' || *p == '\t' || *p == '\n') p++;
    // 继续原有的引号检测和 URL 提取逻辑...
}

HTML 规范允许属性名和 = 之间、= 和属性值之间有空白字符。真正的 HTML 解析器需要处理这些情况，但本课的简化版本忽略了这种边缘情况，目的是聚焦于指针操作和字符串匹配的核心技巧。

Q3: 2 倍扩容的均摊分析

固定增量扩容（+C）：总拷贝量 ≈ N²/(2C) = O(N²)。对于 N=1MB、C=4KB，需约 250 次扩容，总拷贝约 125MB。

2 倍扩容：总拷贝量 ≈ N = O(N)。对于 N=1MB，需约 8 次扩容，总拷贝约 2MB。

对比 (N=1MB, 初始 C=4KB):
固定 +4KB:  扩容 250 次, 拷贝 ~125MB  ← 糟糕
2 倍增长:   扩容   8 次, 拷贝   ~2MB  ← 高效

2 倍是实践中广泛使用的折衷——C++ std::vector、Java ArrayList、Python list 都使用类似策略（通常 1.5~2 倍）。它保证了均摊 O(1) 的追加操作时间复杂度。

Q4: 递归爬取的扩展方案

将现有程序扩展为递归爬虫需要以下组件：

HTTP 下载模块：用 libcurl 或系统命令 curl/wget 下载网页。
URL 规范化：将相对 URL 转为绝对 URL（如 ../img/logo.png → 完整 URL）。
去重集合：用哈希表记录已访问的 URL。简单实现可用字符串数组 + 线性搜索：

dedup_hash_concept.c

char *visited[1000];
int visited_count = 0;

int is_visited(const char *url) {
    for (int i = 0; i < visited_count; i++)
        if (strcmp(visited[i], url) == 0) return 1;
    return 0;
}

深度限制和礼貌性控制（sleep 在请求之间等待）。

Q5: 过滤非 HTTP 链接

在 extract_links 的输出环节添加前缀检查：

filter_http_urls.c

// 在 printf 之前添加过滤:
if (i > 0) {
    // 只输出以 http:// 或 https:// 开头的 URL
    if (strncmp(url, "http://", 7) == 0 ||
        strncmp(url, "https://", 8) == 0) {
        printf("[%d] %s\n", ++count, url);
    }
    // 或者反过来: 排除 javascript: 和 # 开头的
    // if (strncmp(url, "javascript:", 11) != 0 && url[0] != '#')
}

strncmp 来自 <string.h>，它比较前 n 个字符。对于 http://（7 个字符）和 https://（8 个字符），使用不同的 n 值。更完整的过滤还应排除 mailto:、# 锚点等。

Q6: 返回链接列表的函数签名设计

如果要把 extract_links 改为返回链接列表而非直接打印，有几种设计方案：

方案 A：返回 char**（字符串数组）

return_char_star_star.c

// 挑战: 需要动态分配字符串数组 + 每个字符串
// 调用者负责释放所有内存

char **extract_links(const char *html, int *out_count) {
    char **links = malloc(sizeof(char*) * MAX_LINKS);
    int count = 0;
    // ... 提取过程中:
    links[count] = strdup(url);  // strdup = malloc + strcpy
    count++;
    // ...
    *out_count = count;
    return links;
}

// 调用者:
int count;
char **links = extract_links(html, &count);
for (int i = 0; i < count; i++)
    printf("[%d] %s\n", i + 1, links[i]);
// 释放:
for (int i = 0; i < count; i++) free(links[i]);
free(links);

方案 B：回调函数模式

callback_pattern.c

// 每找到一个链接就调用回调函数，不持有数据
typedef void (*link_callback)(const char *url, void *userdata);

int extract_links(const char *html, link_callback cb, void *userdata) {
    // ... 提取 url 后:
    cb(url, userdata);  // 交给调用者处理
    // ...
}

// 调用者:
void print_link(const char *url, void *data) {
    int *count = (int*)data;
    printf("[%d] %s\n", ++(*count), url);
}

int count = 0;
extract_links(html, print_link, &count);

回调模式更灵活——调用者自由决定如何处理每个链接（打印、存储、过滤等），且无需管理内存。对于本课的教学目标，直接 printf 输出是最简单清晰的方式。

课后练习

练习 1：测试真实网页

用命令行工具下载真实网页并测试你的程序：

bash

curl -s https://example.com | ./search
# 或
wget -q -O - https://example.com | ./search

观察输出：提取到了多少个链接？这些链接中有多少是绝对 URL（以 http 开头）？有多少是相对 URL？

知识点提示：curl -s 的 -s 是 silent 模式（不显示进度条）。管道 | 将 curl 的标准输出连接到 ./search 的标准输入。这是 Unix 管道哲学的实际应用。

参考解答

这个练习不需要编写代码，重点是体验管道组合的工作方式。可以尝试不同的网站：

bash

# 简单网站
curl -s https://example.com | ./search

# 较复杂网站
curl -s https://en.wikipedia.org/wiki/C_(programming_language) | ./search | head -20

# 观察相对链接 vs 绝对链接
curl -s https://example.com | ./search | grep -c "http"

注意：有些网站可能返回压缩内容或重定向，curl 默认不处理这些情况。可以用 curl -sL 跟随重定向。

练习 2：过滤绝对 URL

修改 extract_links，添加过滤功能：只输出以 http:// 或 https:// 开头的绝对 URL。

期望行为：

http://example.com → 输出
https://example.com → 输出
/path/to/page → 跳过（相对 URL）
#section → 跳过（锚点）
javascript:void(0) → 跳过

知识点提示：使用 strncmp(url, "http://", 7) 和 strncmp(url, "https://", 8) 检查前缀。注意 strncmp 比较前 n 个字符，https:// 比 http:// 多一个字符（8 vs 7）。

参考解答

filter_absolute_urls.c

// 在 extract_links 中，printf 之前添加过滤:
if (i > 0) {
    // 只输出以 http:// 或 https:// 开头的绝对 URL
    if (strncmp(url, "http://", 7) == 0 ||
        strncmp(url, "https://", 8) == 0) {
        printf("[%d] %s\n", ++count, url);
    }
}

strncmp 比较前 n 个字符，返回 0 表示相等。对于 https://，比较前 8 个字符（h-t-t-p-s-😕-/），比 http:// 多一个 s。

注意：这也会把以 http 开头的相对路径（如 http-info.html）误判为绝对 URL。更严格的检查应该要求 :// 在 http 之后：

stricter_filter.c

// 更严格的检查: 要求 "://" 在 http/https 之后
if ((strncmp(url, "http://", 7) == 0) ||
    (strncmp(url, "https://", 8) == 0))
    printf("[%d] %s\n", ++count, url);

由于 strncmp("http://", ...) 已经包含了 ://，所以上面的代码已经足够严格。http-info.html 不会匹配 http://。

练习 3：添加去重功能

修改程序，用数组记录已见过的 URL，如果同一个 URL 出现多次，只输出第一次。

实现思路：

定义一个二维字符数组 char seen[100][MAX_URL] 来存储已见过的 URL
每次提取到新 URL 时，遍历 seen 检查是否已存在
如果不存在，加入 seen 并输出；如果已存在，跳过

知识点提示：二维字符数组 char seen[N][MAX_URL] 可以理解为一个「字符串列表」——每一行存储一个 URL。回顾 Lesson 14（迷宫）中二维数组的行优先存储和 Lesson 09（itoa）中的字符数组操作。对于少量 URL（< 100），线性搜索足够；如果 URL 数量很大，可以用哈希表提升效率。

参考解答

dedup_extract_links.c

#include <string.h>

#define MAX_URL 1024
#define MAX_SEEN 100

static int extract_links_dedup(const char *html)
{
    const char *p = html;
    int count = 0;
    char seen[MAX_SEEN][MAX_URL];   // 已见过的 URL 列表
    int seen_count = 0;

    while ((p = find_istr(p, "href=")) != NULL) {
        p += 5;
        char quote = (*p == '"' || *p == '\'') ? *p++ : 0;
        char url[MAX_URL];
        int i = 0;
        while (*p && i < MAX_URL - 1) {
            if (quote && *p == quote) break;
            if (!quote && (*p == ' ' || *p == '>')) break;
            url[i++] = *p++;
        }
        url[i] = '\0';

        if (i > 0) {
            // 去重检查
            int dup = 0;
            for (int j = 0; j < seen_count; j++) {
                if (strcmp(seen[j], url) == 0) {
                    dup = 1;
                    break;
                }
            }
            if (!dup && seen_count < MAX_SEEN) {
                strcpy(seen[seen_count++], url);
                printf("[%d] %s\n", ++count, url);
            }
        }
    }

    return count;
}

关键点：

seen[MAX_SEEN][MAX_URL] 是一个二维数组，seen[j] 是第 j 个 URL 字符串
strcmp(seen[j], url) 比较两个字符串是否相同
strcpy(seen[seen_count++], url) 将新 URL 复制到 seen 中并递增计数
线性搜索 O(n) 对于少量 URL 足够；超过几百个建议使用哈希表

练习 4：统计域名分布

扩展程序，统计提取到的链接中各域名出现的次数。例如：

https://example.com → example.com 计数 +1
https://github.com/user → github.com 计数 +1
https://github.com/repo → github.com 计数 +1

输出格式：

example.com: 1
github.com: 2

实现思路：

从 URL 中提取域名部分（:// 之后到下一个 / 之前）
用类似练习 3 的二维数组存储域名和对应的计数
遍历所有链接，累加域名计数

知识点提示：域名提取本质上是字符串解析——在 URL 中找到 :// 标记，然后提取直到 / 或字符串结束的内容。这与 extract_links 中提取 URL 的思路完全一致，只是标记和结束条件不同。可以用两个数组 domains[N][MAX_URL] 和 counts[N] 分别存储域名和计数。

参考解答

domain_stats.c

#include <string.h>

#define MAX_DOMAIN 256
#define MAX_DOMAINS 50

// 从 URL 中提取域名
static void extract_domain(const char *url, char *domain)
{
    // 找到 "://" 
    const char *start = strstr(url, "://");
    if (!start) {
        domain[0] = '\0';
        return;
    }
    start += 3;  // 跳过 "://"

    // 提取到 '/' 或字符串末尾
    const char *end = strchr(start, '/');
    int len = end ? (end - start) : strlen(start);

    strncpy(domain, start, len);
    domain[len] = '\0';
}

// 域名统计
static void print_domain_stats(const char *html)
{
    char domains[MAX_DOMAINS][MAX_DOMAIN];
    int counts[MAX_DOMAINS] = {0};
    int domain_count = 0;

    const char *p = html;
    while ((p = find_istr(p, "href=")) != NULL) {
        p += 5;
        char quote = (*p == '"' || *p == '\'') ? *p++ : 0;
        char url[MAX_URL];
        int i = 0;
        while (*p && i < MAX_URL - 1) {
            if (quote && *p == quote) break;
            if (!quote && (*p == ' ' || *p == '>')) break;
            url[i++] = *p++;
        }
        url[i] = '\0';

        if (i == 0) continue;

        char domain[MAX_DOMAIN];
        extract_domain(url, domain);
        if (domain[0] == '\0') continue;

        // 查找或添加域名
        int found = 0;
        for (int j = 0; j < domain_count; j++) {
            if (strcmp(domains[j], domain) == 0) {
                counts[j]++;
                found = 1;
                break;
            }
        }
        if (!found && domain_count < MAX_DOMAINS) {
            strcpy(domains[domain_count], domain);
            counts[domain_count] = 1;
            domain_count++;
        }
    }

    // 输出统计结果
    for (int j = 0; j < domain_count; j++)
        printf("%s: %d\n", domains[j], counts[j]);
}

解析：extract_domain 使用 strstr（精确匹配，不是大小写不敏感）查找 ://，因为 URL 的协议部分总是小写。strchr(start, '/') 查找域名结束位置。域名统计使用「查找-累加」模式：遍历已有域名列表，找到匹配的累加计数，找不到则添加新域名。

练习 5：挑战 — 提取链接文本

扩展程序，不仅提取链接 URL，还提取链接的显示文本。对于 <a href="url">显示文本</a>，输出格式：

[1] url → 显示文本

实现思路：

找到 href="..." 后，继续查找 >（标签结束）
从 > 之后开始，读取直到 <（下一个标签开始）
中间的内容就是链接文本

知识点提示：这需要两个步骤的字符串解析——先提取 URL，再提取文本。注意处理嵌套标签（如 <a href="...">粗体文本</a>）会导致文本提取不完整，但作为简化练习，忽略嵌套标签是可以接受的。核心技巧仍然是「查找标记 → 提取内容」。

参考解答

extract_link_text.c

// 在找到 URL 之后继续提取链接文本
static void extract_link_with_text(const char *html)
{
    const char *p = html;
    int count = 0;

    while ((p = find_istr(p, "href=")) != NULL) {
        p += 5;
        char quote = (*p == '"' || *p == '\'') ? *p++ : 0;
        char url[MAX_URL];
        int i = 0;
        while (*p && i < MAX_URL - 1) {
            if (quote && *p == quote) break;
            if (!quote && (*p == ' ' || *p == '>')) break;
            url[i++] = *p++;
        }
        url[i] = '\0';

        if (i == 0) continue;

        // 跳过闭合引号（如果之前检测到了引号）
        if (quote && *p == quote) p++;

        // 找到 '>' — 标签结束
        const char *tag_end = strchr(p, '>');
        if (!tag_end) continue;
        p = tag_end + 1;  // 跳过 '>'

        // 提取链接文本：从 p 开始到下一个 '<'
        char text[MAX_URL];
        int ti = 0;
        while (*p && *p != '<' && ti < MAX_URL - 1)
            text[ti++] = *p++;
        text[ti] = '\0';

        // 去除首尾空白（简化处理）
        if (ti > 0)
            printf("[%d] %s → %s\n", ++count, url, text);
    }
}

解析：在提取 URL 后，strchr(p, '>') 找到标签结束位置，然后提取直到 < 的文本。这个简化版本不处理嵌套标签（如 <a>text</a> 会得到 text），但在大多数简单网页中效果良好。

参考资料

cppreference: tolower — C 标准库 tolower 函数的官方文档，包含 locale 相关注意事项
cppreference: malloc / realloc / free — C 动态内存管理函数的详细说明，包括 realloc 的失效模式
cppreference: fread — fread 函数文档，包含返回值语义和错误处理
cppreference: strstr / strchr / strncmp — C 字符串操作函数族，本课中用到的 strlen、strncmp、strchr、strstr 等
HTML Living Standard: Attributes — HTML 规范中属性值的语法定义（引号、空白、转义），了解真正的 HTML 解析器需要处理的复杂性

"The computer was born to solve problems that did not exist before." — Bill Gates

Lesson 24: 简单搜索引擎 ​CNB

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 字符串匹配：从精确匹配到大小写不敏感 ​

1.1 回顾 Lesson 16：指针遍历字符串 ​

1.2 朴素子串匹配算法 ​

1.3 引入大小写不敏感：tolower() ​

1.4 指针返回值的语义 ​

2. HTML 链接提取：指针操作与引号解析 ​

2.1 问题建模：从 HTML 到链接列表 ​

2.2 指针递进：p += n 的跳转技巧 ​

2.3 引号解析：状态跟踪 ​

2.4 完整 extract_links 实现 ​

3. 动态内存与文件读取：read_all ​

3.1 为什么需要动态内存 ​

3.2 malloc：按需分配 ​

3.3 realloc：动态扩容 ​

3.4 fread：批量读取 ​

3.5 read_all 完整剖析 ​

3.6 stdin 管道与 Unix 哲学 ​

4. 字符串解析的经典模式 ​

4.1 查找-提取-继续 模式 ​

4.2 指针即游标 ​

4.3 与 Lesson 16 的联系 ​

5. 从链接提取到搜索引擎 ​

5.1 搜索引擎的工作原理 ​

5.2 递归爬取的雏形 ​

6. 常见陷阱与健壮性设计 ​

6.1 空指针与空输入 ​

6.2 经典内存错误 ​

6.3 realloc 的失效模式 ​

6.4 缓冲区溢出的边界保护 ​

7. 性能考量和实际应用扩展 ​

7.1 朴素算法的实际性能 ​

7.2 更健壮的 HTML 解析 ​

7.3 用本课知识构建的完整工具链 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

练习 1：测试真实网页 ​

练习 2：过滤绝对 URL ​

练习 3：添加去重功能 ​

练习 4：统计域名分布 ​

练习 5：挑战 — 提取链接文本 ​

参考资料 ​

Lesson 24: 简单搜索引擎 CNB

练习任务

核心知识点

代码框架

深度讲解

1. 字符串匹配：从精确匹配到大小写不敏感

1.1 回顾 Lesson 16：指针遍历字符串

1.2 朴素子串匹配算法

1.3 引入大小写不敏感：tolower()

1.4 指针返回值的语义

2. HTML 链接提取：指针操作与引号解析

2.1 问题建模：从 HTML 到链接列表

2.2 指针递进：p += n 的跳转技巧

2.3 引号解析：状态跟踪

2.4 完整 extract_links 实现

3. 动态内存与文件读取：read_all

3.1 为什么需要动态内存

3.2 malloc：按需分配

3.3 realloc：动态扩容

3.4 fread：批量读取

3.5 read_all 完整剖析

3.6 stdin 管道与 Unix 哲学

4. 字符串解析的经典模式

4.1 查找-提取-继续模式

4.2 指针即游标

4.3 与 Lesson 16 的联系

5. 从链接提取到搜索引擎

5.1 搜索引擎的工作原理

5.2 递归爬取的雏形

6. 常见陷阱与健壮性设计

6.1 空指针与空输入

6.2 经典内存错误

6.3 realloc 的失效模式

6.4 缓冲区溢出的边界保护

7. 性能考量和实际应用扩展

7.1 朴素算法的实际性能

7.2 更健壮的 HTML 解析

7.3 用本课知识构建的完整工具链

参考解答

课堂讨论

讨论答案

课后练习

练习 1：测试真实网页

练习 2：过滤绝对 URL

练习 3：添加去重功能

练习 4：统计域名分布

练习 5：挑战 — 提取链接文本

参考资料