22. 链表的应用：图的邻接表表示、哈希表中的链地址法

链表这东西，说白了就是一根绳子串起一堆珠子。但你别小看它，在真实项目中，链表往往是解决复杂问题的关键。今天咱们就聊聊链表在两大经典场景中的应用：图的邻接表表示，以及哈希表中的链地址法。

我个人习惯把链表看作一种“动态的容器”，它不像数组那样需要提前划好地盘。你想想看，在嵌入式系统里，内存就那么点，用数组动不动就溢出，链表反而灵活得多。

一、图的邻接表表示

图是什么？图就是一堆节点（顶点）和它们之间的连线（边）。比如城市之间的航班网络，每个城市是一个节点，航线就是边。那怎么在程序里存这个图呢？

最直接的想法是用二维数组，也就是邻接矩阵。但问题来了——如果图里有1000个节点，但每个节点只连了3、5个邻居，那矩阵里大部分都是0，浪费啊！

这时候，邻接表就派上用场了。

1. 邻接表的结构

邻接表的思路很简单：每个顶点都拉一个链表，链表里存的是它所有邻居的编号。这样，有多少条边，就存多少数据，一点不浪费。

我在项目中遇到过这样一个场景：一个传感器网络，每个传感器只跟附近的几个传感器通信。如果用邻接矩阵，100个传感器就得开100x100的数组，太奢侈了。换成邻接表，每个传感器只存它实际连接的几个邻居，内存直接省了80%。

2. 代码实现

咱们直接上代码。先定义顶点和边的结构：

// 邻接表中的边节点
typedef struct EdgeNode {
    int adjvex;             // 邻接点编号
    struct EdgeNode *next;  // 指向下一条边
} EdgeNode;

// 顶点节点
typedef struct VertexNode {
    int data;               // 顶点数据
    EdgeNode *firstedge;    // 指向第一条边
} VertexNode;

// 图结构
typedef struct {
    VertexNode adjlist[MAXV];  // 邻接表数组
    int n, e;                  // 顶点数、边数
} ALGraph;

创建图的函数也很直接：

void CreateALGraph(ALGraph *G) {
    int i, u, v;
    EdgeNode *e;
    
    printf("输入顶点数和边数：");
    scanf("%d%d", &G->n, &G->e);
    
    // 初始化顶点
    for (i = 0; i < G->n; i++) {
        G->adjlist[i].data = i;
        G->adjlist[i].firstedge = NULL;
    }
    
    // 建立邻接表
    for (i = 0; i < G->e; i++) {
        printf("输入边(u, v)：");
        scanf("%d%d", &u, &v);
        
        // 头插法插入边节点
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = v;
        e->next = G->adjlist[u].firstedge;
        G->adjlist[u].firstedge = e;
        
        // 无向图需要对称插入
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = u;
        e->next = G->adjlist[v].firstedge;
        G->adjlist[v].firstedge = e;
    }
}

3. 邻接表的遍历

有了邻接表，遍历图就方便了。比如深度优先遍历（DFS），其实就是沿着链表一直往下走：

void DFS(ALGraph *G, int v, int visited[]) {
    EdgeNode *p;
    visited[v] = 1;
    printf("%d ", v);
    
    p = G->adjlist[v].firstedge;
    while (p != NULL) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

嗯，这里要注意：递归深度可能很大。如果图有几千个节点，递归调用栈可能会溢出。我建议在嵌入式系统里用栈模拟递归，或者直接用广度优先遍历（BFS）。

二、哈希表中的链地址法

哈希表大家都熟悉，通过哈希函数把键映射到数组下标，实现O(1)的查找。但哈希冲突怎么办？

常见的解决方法有两种：开放地址法和链地址法。我个人更偏爱链地址法，原因很简单——它把冲突的元素用链表串起来，实现起来清晰，而且删除操作也方便。

1. 链地址法的结构

链地址法的思路是：哈希表的每个槽位不再是一个元素，而是一个链表的头指针。所有哈希到同一个槽位的元素，都挂在这个链表上。

我曾经在一个项目里用链地址法实现了一个设备ID查找表。设备ID是32位的整数，哈希到128个槽位里。刚开始我担心链表太长影响性能，后来实测发现，只要哈希函数设计得好，每个链表平均长度不超过2，查找效率依然很高。

2. 代码实现

先定义哈希表的结构：

#define HASHSIZE 128

// 哈希表节点
typedef struct HashNode {
    int key;
    int value;
    struct HashNode *next;
} HashNode;

// 哈希表
typedef struct {
    HashNode *slot[HASHSIZE];  // 每个槽位是一个链表头
} HashTable;

哈希函数和基本操作：

// 简单的哈希函数
int Hash(int key) {
    return key % HASHSIZE;
}

// 插入
void Insert(HashTable *ht, int key, int value) {
    int index = Hash(key);
    HashNode *node = (HashNode *)malloc(sizeof(HashNode));
    node->key = key;
    node->value = value;
    
    // 头插法插入链表
    node->next = ht->slot[index];
    ht->slot[index] = node;
}

// 查找
int Search(HashTable *ht, int key) {
    int index = Hash(key);
    HashNode *p = ht->slot[index];
    
    while (p != NULL) {
        if (p->key == key) {
            return p->value;
        }
        p = p->next;
    }
    return -1;  // 没找到
}

// 删除
void Delete(HashTable *ht, int key) {
    int index = Hash(key);
    HashNode *p = ht->slot[index];
    HashNode *prev = NULL;
    
    while (p != NULL) {
        if (p->key == key) {
            if (prev == NULL) {
                ht->slot[index] = p->next;
            } else {
                prev->next = p->next;
            }
            free(p);
            return;
        }
        prev = p;
        p = p->next;
    }
}

三、两种应用的核心对比

咱们把这两种应用放在一起对比一下，你会发现它们其实有共通之处：

对比项	图的邻接表	哈希表的链地址法
数据结构	数组 + 链表	数组 + 链表
链表作用	存储邻接点	存储冲突元素
查找效率	O(度数)	O(链表长度)
空间效率	O(V+E)	O(n)
典型场景	稀疏图	哈希冲突处理

说白了，这两种应用都是“数组+链表”的经典组合。数组提供快速定位，链表提供动态扩展。你想想看，如果没有链表，邻接表就得用固定大小的数组，哈希冲突就得用开放地址法，那灵活性就差多了。

四、知识结构图

下面这张图帮你理清本章的知识脉络：

五、避坑指南

最后，分享几个我踩过的坑：

• 内存泄漏：链表的节点都是动态分配的，用完后一定要释放。我曾经在删除哈希表时忘了释放链表节点，结果内存越用越多，最后系统崩了。
• 头插法与尾插法：头插法简单高效，但会改变元素顺序。如果你需要保持插入顺序，用尾插法，但记得维护一个尾指针。
• 哈希函数的选择：别用太简单的取模，尤其是当键值有规律时。比如键都是偶数，取模后全落在偶数槽位，链表就偏了。
• 图的遍历：递归DFS在深度大的时候容易栈溢出。我建议在嵌入式系统里用迭代方式实现，或者限制递归深度。

好了，关于链表的这两个经典应用，咱们就聊到这儿。记住，链表不是万能的，但在处理动态数据、稀疏结构时，它确实是最趁手的工具。

---