数据结构教程（2）

数据结构教程（C语言版）

第四部分：树 (Tree)

4.1 什么是树？

在现实世界中，树有树根、树枝和树叶。计算机科学中的“树”结构是对这种层次关系的一种抽象模拟。它是一种非线性的数据结构，用于表示具有层级关系的数据。

​与每个元素最多只有一个前驱和一个后继的线性结构不同，树中的一个节点可以有多个后继（称为子节点）。

​最常见的例子就是电脑里的文件系统：一个根目录（/ 或 C:）下有多个文件夹（子节点），每个文件夹下又可以有更多的文件夹和文件。

4.2 树的核心术语

• ​节点 (Node): 树的基本组成部分，包含数据和指向其他节点的指针。

​ * ​根 (Root): 树的最顶层节点，一棵树只有一个根节点。

​ * ​边 (Edge):连接两个节点的线。

​ * ​父节点 (Parent): 一个节点的直接上层节点。

​ * ​子节点 (Child): 一个节点的直接下层节点。

​ * ​兄弟节点 (Sibling): 拥有相同父节点的节点。

​ * ​叶节点 (Leaf): 没有任何子节点的节点（度为0的节点）。

​ * ​内部节点 (Internal Node): 至少有一个子节点的节点（非叶节点）。

​ * ​高度 (Height): 从一个节点到其最远叶节点的最长路径上的边的数量。树的高度是根节点的高度。

​ * ​深度 (Depth): 从根节点到一个节点的路径上的边的数量。根节点的深度为0。

​ * ​子树 (Subtree): 树中某个节点及其所有后代组成的结构。

​

4.3 二叉树 (Binary Tree)

在众多树的类型中，二叉树是最基础和最常用的一种。

​定义：二叉树是每个节点最多有两个子节点的树结构。这两个子节点通常被称为“左子节点 (left child)”和“右子节点 (right child)”。

​#### 4.3.1 二叉树的C语言表示

与链表类似，我们使用结构体和指针来表示二叉树的节点。

codeC

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

// 定义二叉树节点
struct TreeNode {
    int data;                   // 节点存储的数据
    struct TreeNode* left;      // 指向左子节点的指针
    struct TreeNode* right;     // 指向右子节点的指针
};

// 创建一个新节点
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

4.3.2 二叉树的遍历 (Traversal)

如何访问树中的每一个节点，并且每个节点只访问一次？这就是树的遍历。主要有两种策略：深度优先搜索 (DFS) 和 广度优先搜索 (BFS)。

1. 深度优先搜索 (DFS)

DFS 会尽可能深地探索树的分支。它有三种常见的遍历顺序，通常用递归实现，非常简洁。

• 前序遍历 (Pre-order): 根 -> 左 -> 右

• 访问根节点。

• 递归地前序遍历左子树。
• 递归地前序遍历右子树。

codeC

void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data); // 访问根
    preorderTraversal(root->left); // 遍历左
    preorderTraversal(root->right); // 遍历右
}

* 中序遍历 (In-order): 左 -> 根 -> 右

• 递归地中序遍历左子树。
• 访问根节点。
• 递归地中序遍历右子树。

codeC

void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left); // 遍历左
    printf("%d ", root->data); // 访问根
    inorderTraversal(root->right); // 遍历右
}

* 后序遍历 (Post-order): 左 -> 右 -> 根

• 递归地后序遍历左子树。
• 递归地后序遍历右子树。
• 访问根节点。 （应用：可以用来释放整棵树的内存，因为可以保证在释放父节点之前，其子节点已经被处理）。

codeC

void postorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    postorderTraversal(root->left); // 遍历左
    postorderTraversal(root->right); // 遍历右
    printf("%d ", root->data); // 访问根
}

2. 广度优先搜索 (BFS) / 层序遍历 (Level-order)

BFS 从根节点开始，逐层地访问节点。它需要借助队列来实现。

• 创建一个队列，并将根节点入队。
• 当队列不为空时，循环执行： a. 将队头节点出队并访问它。 b. 如果该节点有左子节点，则将其左子节点入队。 c. 如果该节点有右子节点，则将其右子节点入队。

4.4 二叉搜索树 (Binary Search Tree - BST)

普通的二叉树没有对节点的数据值做任何限制。而二叉搜索树 (BST) 增加了一个重要的规则，使得查找操作变得极其高效。

BST 属性: 对于树中的任意一个节点：

• 其左子树中所有节点的值都小于该节点的值。
• 其右子树中所有节点的值都大于该节点的值。
• 它的左、右子树也分别是二叉搜索树。

​​重要特性：对一个二叉搜索树进行中序遍历，会得到一个有序的元素序列。

​​#### 4.4.1 BST 的核心操作

1. 查找 (Search)

利用BST属性，查找过程非常快。

• 从根节点开始。
• 如果要查找的值等于当前节点的值，则查找成功。
• 如果要查找的值小于当前节点的值，则在左子树中继续查找。
• 如果要查找的值大于当前节点的值，则在右子树中继续查找。
• 如果遇到 NULL，则说明树中不存在该值。

codeC

struct TreeNode* search(struct TreeNode* root, int key) {
    if (root == NULL || root->data == key) {
       return root;
    }
    if (key < root->data) {
       return search(root->left, key);
    }
    return search(root->right, key);
}```

**2. 插入 (Insertion)**

插入操作与查找类似。我们首先查找到新元素应该被插入的位置（即查找到一个 `NULL` 链接），然后将新节点插入到该位置。

```c
struct TreeNode* insert(struct TreeNode* root, int data) {
    // 如果树为空，则返回一个新节点
    if (root == NULL) {
        return createNode(data);
    }
    // 否则，在树中递归地向下查找
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    // 返回（可能未被修改的）节点指针
    return root;
}

3. 删除 (Deletion)

删除是BST中最复杂的操作，需要分三种情况讨论：

• Case 1: 要删除的节点是叶节点 (无子节点) 直接释放该节点，并将其父节点的对应链接（左或右）设为 NULL。
• Case 2: 要删除的节点只有一个子节点 用其子节点替代它。即将该节点的父节点直接链接到该节点的子节点上，然后释放该节点。

• Case 3: 要删除的节点有两个子节点 这是最复杂的情况。为了维持BST的属性，我们不能简单地删除它。

• ​​找到该节点的中序后继（In-order Successor），即其右子树中的最小节点。

  ​​ * 将中序后继节点的值复制到要删除的节点上。 * ​递归地删除那个中序后继节点（此时问题被转化为删除一个最多只有一个子节点的节点）。

  ​

4.5 总结

• 树是一种表示层级关系的强大非线性数据结构。
• 二叉树是每个节点最多有两个子节点的特殊树。
• 树的遍历是基础操作，分为深度优先 (前序、中序、后序) 和广度优先 (层序)。
• ​二叉搜索树 (BST) 增加了值的排序规则，使得查找、插入、删除操作的平均时间复杂度都为 O(h)，其中 h 是树的高度。

​ * 对于一个平衡的BST（左右子树高度差不大），其高度约为 log(n)，因此操作非常高效，接近 O(log n)。但如果BST变得极不平衡（例如退化成一条链表），其性能会下降到 O(n)。这也引出了更高级的自平衡二叉搜索树，如 AVL 树和红黑树。

第五部分：哈希表 (Hash Table)

5.1 什么是哈希表？

​哈希表，又称散列表，是一种通过键 (Key) 来直接访问其对应值 (Value) 的数据结构。它建立了一种键值对 (Key-Value Pair) 的映射关系。

​​想象一下一本英文字典。如果你想查找单词 "apple"，你不会从第一页的 "abandon" 开始一页一页地翻。你会直接翻到字母 'A' 的部分，然后快速定位到 "apple"。哈希表的工作原理与此类似，但更进一步。它试图通过一个“魔法函数”直接计算出任何一个键应该存放的精确位置。

​​这个“魔法函数”就是哈希函数，它将任意长度的输入（键）转换成一个固定长度的输出（数组的索引）。

​#### 5.2 哈希表的核心组成

一个哈希表主要由两个核心部分组成：

• ​​数组 (Array): 这是哈希表的底层存储结构，通常被称为桶数组 (Bucket Array)。数组中的每一个位置就是一个“桶 (Bucket)”。

​​ * ​哈希函数 (Hash Function): 这是一个函数，它的职责是接收一个键作为输入，并返回一个整数，这个整数就是该键在桶数组中对应的索引。

​

理想过程：

• ​插入: insert("apple", "A round fruit")

​ 哈希函数计算 hash("apple") -> 得到索引 4*。

• 将 "A round fruit" 这个值存放到数组的第 4 个位置。
• ​查找: search("apple")

​ 哈希函数再次计算 hash("apple") -> 得到索引 4*。

• 直接去数组的第 4 个位置取出值，操作完成。

这个过程非常快，因为只涉及一次函数计算和一次数组访问，时间复杂度为 O(1)。

5.3 哈希冲突 (Hash Collision)

​​理想是美好的，但现实是骨感的。由于桶数组的大小是有限的，而键的可能取值是近乎无限的，不可避免地会出现这样一种情况：两个不同的键，经过哈希函数计算后，得到了相同的索引。这种情况被称为哈希冲突。

​​例如，hash("apple") -> 4，同时 hash("banana") -> 4。当我们要把 "banana" 存入时，发现第 4 个桶已经被 "apple" 占用了。

​解决哈希冲突是设计哈希表的关键所在。最常用的一种策略是拉链法 (Separate Chaining)。

​#### 5.4 冲突解决方法：拉链法 (Separate Chaining)

​拉链法的思想很简单：数组的每个桶不再是直接存储一个元素，而是存储一个指向链表头的指针。

​ 当一个新元素被哈希到某个索引时，我们检查该索引处的链表。*

• 如果发生冲突，这个新元素就被简单地添加到这个链表的末尾（或开头）。
• 当查找一个元素时，我们先通过哈希函数找到对应的桶（链表），然后遍历这个短小的链表来找到我们需要的键。

5.5 哈希表的 C 语言实现 (拉链法)

1. 定义数据结构

我们需要两个结构体：一个用于表示链表节点（存储键值对），另一个用于表示整个哈希表。

codeC

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

#define TABLE_SIZE 10 // 定义哈希表的大小

// 链表节点，用于存储键值对
struct HashNode {
    char* key;
    int value;
    struct HashNode* next;
};

// 哈希表结构
struct HashTable {
    int size;
    struct HashNode** table; // 指向 HashNode 指针数组的指针
};

2. 哈希函数

这里我们实现一个简单的哈希函数，它将字符串中所有字符的ASCII码值相加，然后对表的大小取模。 (注意：在实际应用中，会使用更复杂的哈希函数以获得更好的分布效果，如 djb2, sdbm 等)

codeC

// 简单的哈希函数
unsigned int hashFunction(char* key, int size) {
    unsigned long int hash = 0;
    int c;
    while ((c = *key++)) {
        hash += c;
    }
    return hash % size;
}

3. 核心操作

codeC

// 创建哈希表
struct HashTable* createHashTable(int size) {
    struct HashTable* ht = (struct HashTable*)malloc(sizeof(struct HashTable));
    ht->size = size;
    ht->table = (struct HashNode**)malloc(sizeof(struct HashNode*) * size);

    // 初始化所有桶（链表头）为 NULL
    for (int i = 0; i < size; i++) {
        ht->table[i] = NULL;
    }
    return ht;
}

// 插入操作
void insert(struct HashTable* ht, char* key, int value) {
    unsigned int index = hashFunction(key, ht->size);
    struct HashNode* current = ht->table[index];

    // 检查键是否已存在，如果存在则更新值
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            current->value = value;
            return;
        }
        current = current->next;
    }

    // 如果键不存在，则在链表头部插入新节点
    struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
    newNode->key = strdup(key); // 复制字符串
    newNode->value = value;
    newNode->next = ht->table[index];
    ht->table[index] = newNode;
}

// 查找操作
int search(struct HashTable* ht, char* key) {
    unsigned int index = hashFunction(key, ht->size);
    struct HashNode* current = ht->table[index];

    // 遍历对应索引的链表
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value; // 找到了
        }
        current = current->next;
    }
    return -1; // 未找到，返回一个特殊值
}

// 删除操作 (篇幅原因，此处省略，其逻辑为：先查找，找到后执行标准链表删除)
// 释放哈希表 (非常重要，防止内存泄漏)
void freeHashTable(struct HashTable* ht) {
    for (int i = 0; i < ht->size; i++) {
        struct HashNode* current = ht->table[i];
        while (current != NULL) {
            struct HashNode* temp = current;
            current = current->next;
            free(temp->key);
            free(temp);
        }
    }
    free(ht->table);
    free(ht);
}

5.6 性能分析

• ​加载因子 (Load Factor): 这是衡量哈希表“满”的程度的指标，计算公式为 α = n / m (n = 已存储的元素数量, m = 桶的数量)。加载因子直接影响哈希表的性能。

​ * ​时间复杂度:

​ ​​​平均情况: 查找、插入和删除都是 O(1 + α)。如果哈希函数分布均匀且加载因子 α 是一个较小的常数（通常建议保持在 0.75 以下），那么性能就接近 O(1)*。

​​​

• ​​最坏情况: 如果哈希函数设计得极差，导致所有键都冲突并映射到同一个桶，那么哈希表就退化成了一个链表。此时，所有操作的时间复杂度都将是 O(n)。

  ​​

5.7 总结

• 哈希表是一种以空间换时间的高效数据结构，提供了极快的平均查找、插入和删除速度。
• ​其核心是哈希函数和冲突解决策略。

​ * 拉链法是解决冲突最常用和最稳健的方法之一。 * ​哈希表的性能高度依赖于一个好的哈希函数和一个合适的加载因子。

​ * 它被广泛应用于各种场景，如数据库索引、缓存系统、编程语言中的字典/map/对象实现等。几乎所有需要快速通过键查找值的场景，背后都有哈希表的影子。

第六部分：图 (Graph)

6.1 什么是图？

图是一种非线性数据结构，由一组顶点 (Vertices) 和一组连接顶点的边 (Edges) 组成。形式上，一个图 G 可以表示为 G = (V, E)，其中 V 是顶点集，E 是边集。

与树不同，图的规则要宽松得多：

• ​图不一定有根节点。

​ * 图中的节点可以有任意数量的连接。 * ​图可以包含环路 (Cycle)，即从一个顶点出发，沿着一系列边可以回到该顶点。

​ * ​图可以是不连通的 (Disconnected)，即图中可能存在无法通过边相互到达的顶点组。

​

现实世界的例子：

• ​社交网络: 用户是顶点，好友关系是边。

​ * ​地图系统:城市/交叉路口是顶点，道路是边。

​ * ​万维网: 网页是顶点，超链接是边。

​ * ​航空公司网络: 机场是顶点，航线是边。

​

6.2 图的核心术语

• ​顶点 (Vertex): 也称为节点 (Node)。

​ * ​边 (Edge): 连接两个顶点的线。

​ * ​无向图 (Undirected Graph): 边没有方向。如果顶点 A 和 B 之间有一条边，那么可以从 A 到 B，也可以从 B 到 A。社交网络中的好友关系就是无向的。

​ * ​有向图 (Directed Graph / Digraph): 边有方向。一条从 A 指向 B 的边，表示可以从 A 到 B，但不能从 B 到 A（除非存在另一条反向的边）。网页的超链接就是有向的。

​ * ​​权重 (Weight): 可以给边赋予一个数值，称为权重或成本。例如，在地图中，边的权重可以代表两个城市间的距离或旅行时间。有权重的图称为加权图 (Weighted Graph)。

​​ * ​邻接 (Adjacent): 如果两个顶点之间有一条边直接相连，则称它们是邻接的。

​ * ​​​度 (Degree): 在无向图中，一个顶点的度是指与该顶点相连的边的数量。在有向图中，分为入度 (In-degree)（指向该顶点的边的数量）和出度 (Out-degree)（从该顶点出发的边的数量）。

​​​ * ​路径 (Path): 从一个顶点到另一个顶点经过的边构成的序列。

​ * ​环 (Cycle): 一条起点和终点相同的路径。

​

6.3 图的表示方法

如何在代码中存储一个图？主要有两种标准方法：邻接矩阵和邻接表。

1. 邻接矩阵 (Adjacency Matrix)

一个 V x V 的二维数组（其中 V 是顶点的数量），matrix[i][j] 的值表示顶点 i 和顶点 j 之间的关系。

• ​对于无权图，如果 i 和 j 之间有边，则 matrix[i][j] = 1，否则为 0。

​ * ​对于加权图，matrix[i][j] 存储的是边的权重，没有边则可以用一个特殊值（如无穷大或0）表示。

​ * ​对于无向图，这个矩阵是对称的（matrix[i][j] = matrix[j][i]）。

​

​优点:

​ 检查两个顶点之间是否存在边非常快，时间复杂度为 O(1)。*

• ​实现简单直观。 缺点:

​ * 空间复杂度为 O(V²)，当顶点很多但边很少时（稀疏图），会浪费大量内存。

codeC

// 邻接矩阵表示
#define V 5
int adjMatrix[V][V]; // 初始化为 0
// 添加一条从 0 到 1 的边
adjMatrix[0][1] = 1;
adjMatrix[1][0] = 1; // 如果是无向图

2. 邻接表 (Adjacency List)

一个由 V 个链表组成的数组。数组的第 i 个元素 adjList[i] 是一个链表，存储了所有与顶点 i 相邻接的顶点。

​优点:

​ 空间效率高，特别是对于稀疏图，空间复杂度为 O(V + E)（E是边的数量）。*

• ​遍历一个顶点的所有邻居非常方便。 缺点:

​ * 检查两个顶点 u 和 v 之间是否存在边，需要遍历 adjList[u] 这个链表，时间复杂度为 O(Degree(u))。

这是在实践中最常用的图表示方法。

codeC

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

// 邻接表节点
struct AdjListNode {
    int dest; // 目标顶点
    struct AdjListNode* next;
};

// 邻接表
struct AdjList {
    struct AdjListNode *head; // 指向链表头的指针
};

// 图结构
struct Graph {
    int V; // 顶点数
    struct AdjList* array;
};

// 创建一个图
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;
    return graph;
}

// 添加一条边 (用于无向图)
void addEdge(struct Graph* graph, int src, int dest) {
    // 从 src 到 dest 的边
    struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 从 dest 到 src 的边
    newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = src;
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

6.4 图的遍历

图的遍历是从某个顶点出发，访问图中所有可达顶点的过程，且每个顶点只访问一次。最核心的两种算法是广度优先搜索 (BFS) 和深度优先搜索 (DFS)。

1. 广度优先搜索 (BFS - Breadth-First Search)

BFS 从一个起始顶点开始，逐层向外扩展。它首先访问所有与起始顶点直接相邻的邻居，然后访问这些邻居的邻居，以此类推。这就像在水中投下一颗石子，波纹一圈一圈向外扩散。

BFS 需要使用一个队列 (Queue) 来实现。

算法步骤:

• 创建一个队列和一个 visited 数组（用于标记已访问的顶点）。
• 选择一个起始顶点 s，将其标记为已访问，并将其入队。
• 当队列不为空时，循环执行： a. 将队头顶点 u 出队。 b. 访问 u（例如打印它）。 c. 遍历 u 的所有未被访问过的邻居 v，将它们标记为已访问，并依次入队。

​应用:

​ ​在无权图中寻找两个顶点之间的最短路径。*

​

• 社交网络中寻找“K度好友”。

2. 深度优先搜索 (DFS - Depth-First Search)

DFS 从起始顶点开始，沿着一条路径尽可能深地探索，直到到达一个末端，然后回溯到上一个节点，继续探索其他未被访问的分支。这就像在走迷宫时，沿着一条路走到死胡同，然后返回到上一个路口选择另一条路。

DFS 通常使用递归来实现（隐式地使用了系统调用栈），也可以用一个显式的栈 (Stack) 来实现。

算法步骤 (递归版):

• 创建一个 visited 数组。
• 选择一个起始顶点 u。
• 定义一个递归函数 DFS(u): a. 将 u 标记为已访问并访问它。 b. 对于 u 的每一个未被访问过的邻居 v，递归调用 DFS(v)。

​应用:

​ ​检测图中是否存在环*。

• 拓扑排序（用于有向无环图）。
• 寻找图的连通分量。

6.5 总结

• 图是用于建模网络关系的最通用数据结构，由顶点和边组成。
• 在代码中，图最常用邻接表来表示，因为它对大多数应用场景（特别是稀疏图）来说空间效率更高。
• BFS 和 DFS 是遍历图的两种基本且强大的算法，它们是许多其他复杂图算法的基础。
• ​BFS 使用队列，按层级顺序探索，能找到无权图中的最短路径。

​ * ​DFS 使用栈（或递归），进行深度探索，适合用于检测环或拓扑排序等任务。

​

掌握图是数据结构学习的一个重要里程碑，它为你解决现实世界中更广泛、更复杂的问题打开了大门。