严蔚敏《数据结构》源代码详解与应用

技术文档

本文还有配套的精品资源，点击获取

简介：《严蔚敏《数据结构》源代码》是一份针对严蔚敏教授编著的《数据结构》一书的学习资源，提供了书中提及的各种数据结构的源代码实现。数据结构是计算机科学的核心课程之一，对设计高效算法至关重要。该资源有助于深入理解数据结构的工作原理，并通过实践加强编程技能。源代码涵盖数组、链表、栈和队列、树、图、散列表、排序和查找算法以及递归和分治策略等主题，旨在帮助学习者在理论和实践上均有提升。

1. 数据结构基础理论与源代码实践

数据结构是计算机存储、组织数据的方式，使数据可以高效地被访问和修改。一个良好的数据结构选择能够提升算法性能，优化资源使用。本章将带领读者从基础理论出发，深入探讨数据结构的多种实现，并通过源代码形式加深理解。我们从数组和链表等基础结构开始，逐步深入到更高级的数据结构如栈、队列、树和图等，讲解它们的理论基础和实践方法。这将为掌握数据结构在实际问题中的应用打下坚实的基础。

1.1 数据结构概述

数据结构涉及的范围广泛，它包括了数据的逻辑结构、存储结构以及相关的操作算法。逻辑结构决定了数据元素间的逻辑关系，如线性结构、树形结构等；存储结构定义了数据在计算机中的物理存储方式，常见的有顺序存储、链式存储等；而操作算法则是对数据结构进行各种操作的步骤和方法。

1.2 基本数据结构

基础数据结构包含数组、链表、栈、队列等。它们是构建更复杂数据结构的基石。例如，数组是一种简单的数据结构，提供了通过索引快速访问数据的能力；链表则是一种动态的、以节点为单位存储数据的结构，每个节点包含数据和指向下个节点的指针。通过这些基础结构，我们能有效组织和管理数据，为解决问题提供支持。

在本章的后续内容中，我们将详细探讨这些基础数据结构的理论和实现细节，并通过实例代码加深理解。我们将展示如何在不同的编程语言中实现它们，并讨论各自的优势和局限性。通过这种方式，读者不仅可以学习到数据结构的理论知识，还能获得实践操作的能力。

2. 动态数组和一维数组的实现

2.1 动态数组的理论基础

2.1.1 动态数组的概念与特性

动态数组是一种能够存储多个元素的数据结构，它的容量可以动态调整，以适应不同数量的数据存储需求。与静态数组相比，动态数组在运行时可以通过分配新的内存空间来改变其大小。这种灵活性使得动态数组成为处理大量数据时的理想选择。

动态数组的主要特性包括：
- 动态大小调整 ：允许在程序运行时扩展或缩减数组大小。
- 内存效率 ：相比链表等其他动态数据结构，动态数组通常具有更好的缓存局部性，因为它们在内存中是连续存储的。
- 随机访问 ：可以通过索引直接访问数组中的任何元素，访问时间复杂度为O(1)。

2.1.2 动态数组与静态数组的区别

静态数组的大小在声明时就被固定下来，无法进行动态调整。静态数组的元素通常在栈上分配，这意味着它的生命周期仅限于它所在的函数执行期间。静态数组的优点是访问速度快，但缺点是不够灵活，无法存储未知数量的数据。

动态数组则不同，它在堆上分配，通常通过指向首元素的指针来管理。程序员可以根据需要在运行时增加或减少数组的容量。动态数组的优点是具有高度的灵活性和可扩展性，但它需要额外的内存分配和可能的内存复制操作，这在大数组操作时可能会带来额外的性能开销。

2.2 动态数组的源代码实现

2.2.1 动态数组的内存分配与管理

在C++中，动态数组可以通过指针和内存分配函数（如 new 和 delete ）来实现。下面是一个简单的动态数组实现示例：

template class DynamicArray {private: T* array; // 指向动态分配的数组内存的指针 size_t capacity; // 数组的容量 size_t length; // 数组当前存储元素的数量public: // 构造函数初始化数组 DynamicArray() : array(nullptr), capacity(0), length(0) {} // 构造函数初始化数组，指定初始容量 explicit DynamicArray(size_t initialCapacity) : capacity(initialCapacity), length(0) { array = new T[capacity]; } // 析构函数释放数组内存 ~DynamicArray() { delete[] array; } // 添加元素到数组末尾 void push_back(const T& element) { if (length >= capacity) { resize(); // 如果容量不足，进行扩容操作 } array[length++] = element; } // 获取数组中的元素 T& operator[](size_t index) { if (index >= length) { throw std::out_of_range(\"Index out of range\"); } return array[index]; } // 其他成员函数...};void resize() { // 重新分配更大的内存空间，通常是当前容量的两倍 capacity *= 2; T* newArray = new T[capacity]; // 将旧数组的数据复制到新数组中 for (size_t i = 0; i < length; ++i) { newArray[i] = array[i]; } // 释放旧数组的内存 delete[] array; // 更新数组指针和容量 array = newArray;}

2.2.2 动态数组的基本操作函数实现

动态数组的基本操作包括添加元素、获取元素、删除元素等。在上述代码中， push_back 函数用于向数组末尾添加一个新元素。如果数组已满， push_back 会调用 resize 函数来扩展数组容量。 operator[] 用于通过索引访问数组中的元素。

2.3 一维数组的理论基础与源代码实践

2.3.1 一维数组的基本概念

一维数组是最基础的数据结构之一，由一系列相同类型的数据元素组成，这些元素在内存中连续存储。在许多编程语言中，数组的声明通常需要指定数组的类型和大小。

一维数组的特性包括：
- 连续存储 ：数组中的元素在内存中连续存储，这使得可以通过索引直接访问任意位置的元素。
- 固定大小 ：数组一旦声明，其大小就固定不变，除非重新声明一个新的数组。
- 元素类型相同 ：数组的所有元素必须是相同的数据类型。

2.3.2 一维数组操作的源代码演示

以C++为例，可以创建一个模板类来封装一维数组的操作。这个类提供了初始化、访问元素、修改元素等基本操作。

template class Array {private: T elements[N]; // 存储数组元素public: // 构造函数初始化数组元素为默认值 Array() {} // 构造函数根据提供的初始化列表来初始化数组 Array(std::initializer_list init) { size_t i = 0; for (const auto& value : init) { if (i = N) { throw std::out_of_range(\"Index out of range\"); } return elements[index]; } // 修改数组中指定索引位置的元素值 void set(size_t index, const T& value) { if (index >= N) { throw std::out_of_range(\"Index out of range\"); } elements[index] = value; } // 获取数组的大小 size_t size() const { return N; } // 其他成员函数...};

通过模板和初始化列表，这个 Array 类具有更高的灵活性和可读性。它可以像内置数组一样工作，但提供了一些额外的功能和类型安全。

以上章节展示了动态数组和一维数组的理论基础与源代码实践，包括它们的概念、特性、内存管理、基本操作方法等。在下一章节中，我们将继续深入探讨单链表和双链表的数据结构与操作。

3. 单链表和双链表的操作

3.1 单链表的数据结构与操作

3.1.1 单链表的结构定义

单链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两部分信息：存储数据的域和一个指向下个节点的指针。单链表的特点是节点的存储位置不要求是连续的，节点间的连接是通过指针实现的。

单链表的节点结构可以用如下的C语言结构体表示：

struct ListNode { int val;  // 节点存储的数据 struct ListNode *next; // 指向下一个节点的指针};

3.1.2 单链表基本操作的实现

单链表的基本操作主要包括：创建节点、插入节点、删除节点和遍历链表。接下来我们将分别介绍这些操作的实现方法。

创建节点 ：

struct ListNode* createNode(int value) { struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode)); if (newNode == NULL) { exit(1); // 分配内存失败，退出程序 } newNode->val = value; newNode->next = NULL; return newNode;}

插入节点 ：

void insertNode(struct ListNode** head, int value, int position) { struct ListNode* newNode = createNode(value); if (position == 0) { newNode->next = *head; *head = newNode; } else { struct ListNode* current = *head; for (int i = 0; current != NULL && i next; } if (current != NULL) { newNode->next = current->next; current->next = newNode; } else { free(newNode); // 插入位置无效，释放内存 } }}

删除节点 ：

void deleteNode(struct ListNode** head, int position) { if (*head == NULL) return; // 链表为空，直接返回 struct ListNode* temp = *head; if (position == 0) { *head = temp->next; free(temp); } else { for (int i = 0; temp != NULL && i next; } if (temp == NULL || temp->next == NULL) return; // 位置无效，直接返回 struct ListNode* next = temp->next->next; free(temp->next); temp->next = next; }}

遍历链表 ：

void traverseList(struct ListNode* head) { struct ListNode* current = head; while (current != NULL) { printf(\"%d -> \", current->val); current = current->next; } printf(\"NULL\\n\");}

通过以上代码，我们实现了单链表的基本操作。单链表的插入和删除操作相对高效，因为不需要移动大量元素，只需要修改节点指针即可。但单链表也有其缺点，例如不能进行高效的随机访问，只能从头开始遍历链表。这些特性使得单链表在数据结构应用中有着特定的优势和局限性。

3.2 双链表的扩展功能与应用

3.2.1 双链表的结构特点

双链表是一种更高级的线性数据结构，与单链表相比，它不仅有指向下一个节点的指针，还有一个指向前一个节点的指针。这种结构使得双链表可以方便地在任意位置进行插入和删除操作，双向遍历也成为可能。

双链表节点的结构用C语言表示如下：

struct DoublyListNode { int val;  // 节点存储的数据 struct DoublyListNode *prev; // 指向前一个节点的指针 struct DoublyListNode *next; // 指向下一个节点的指针};

3.2.2 双链表操作的源代码实现

双链表的基本操作包括创建节点、插入节点、删除节点、遍历链表等，其原理与单链表类似，但因为增加了前驱指针，操作过程中需要额外考虑前驱节点的连接。

创建节点 ：

struct DoublyListNode* createDoublyNode(int value) { struct DoublyListNode* newNode = (struct DoublyListNode*)malloc(sizeof(struct DoublyListNode)); if (newNode == NULL) { exit(1); // 分配内存失败，退出程序 } newNode->val = value; newNode->prev = NULL; newNode->next = NULL; return newNode;}

插入节点（双向链表的插入操作稍微复杂，需要处理两个指针） ：

void insertDoublyNode(struct DoublyListNode** head, int value, int position) { // 此处省略具体实现，原理与单链表类似，但需要额外处理prev指针 // ...}

删除节点 ：

void deleteDoublyNode(struct DoublyListNode** head, int position) { // 此处省略具体实现，原理与单链表类似，但需要额外处理prev指针 // ...}

遍历链表（双向链表可以正向和反向遍历） ：

void traverseDoublyList(struct DoublyListNode* head) { struct DoublyListNode* current = head; while (current != NULL) { printf(\"%d \", current->val); current = current->next; } printf(\"\\n\");}

双链表在实际应用中有着其优势，比如在需要频繁删除和插入操作的场景，或者需要双向遍历的时候。然而，由于双链表结构更加复杂，因此它在内存开销上会略高于单链表。

通过本章节的介绍，我们了解了单链表和双链表的理论基础及其基本操作的实现。这些基本操作是链表数据结构运用的关键，掌握它们对于进一步学习更复杂的数据结构和算法具有重要作用。

4. 栈和队列的应用场景

4.1 栈的理论与应用

4.1.1 栈的数据结构描述

栈是一种后进先出（Last In First Out, LIFO）的数据结构。它允许插入和删除操作仅在栈顶进行，这意味着最新添加的元素将是最先被删除的。栈的这种特性使得它非常适合解决一些特定类型的问题，如表达式求值、括号匹配、深度优先搜索（DFS）等。

栈的操作主要包括压栈（push）和出栈（pop），其中压栈是将一个元素添加到栈顶，而出栈是移除并返回栈顶元素。栈通常有两种实现方式，一种是基于数组，另一种是基于链表。

// 基于数组的栈实现示例#define MAXSIZE 10 // 定义栈的最大容量typedef struct { int data[MAXSIZE]; // 存储栈元素的数组 int top; // 栈顶指针} ArrayStack;// 初始化栈void InitStack(ArrayStack *s) { s->top = -1;}// 压栈操作int Push(ArrayStack *s, int element) { if (s->top == MAXSIZE - 1) { return 0; // 栈满，无法压栈 } s->data[++s->top] = element; return 1;}// 出栈操作int Pop(ArrayStack *s, int *element) { if (s->top == -1) { return 0; // 栈空，无法出栈 } *element = s->data[s->top--]; return 1;}

4.1.2 栈在算法中的应用实例

栈的一个典型应用场景是在算法中实现括号匹配。给定一个字符串，包含多种类型的括号，如何判断这些括号是否正确匹配？下面是一个使用栈进行括号匹配的算法实现：

// 括号匹配算法int isBalanced(const char *str) { ArrayStack stack; InitStack(&stack); int i = 0; while (str[i]) { if (str[i] == \'(\' || str[i] == \'[\' || str[i] == \'{\') { Push(&stack, str[i]); } else if (str[i] == \')\' || str[i] == \']\' || str[i] == \'}\') { int top; if (!Pop(&stack, &top)) { return 0; // 括号不匹配 } if ((str[i] == \')\' && top != \'(\') || (str[i] == \']\' && top != \'[\') || (str[i] == \'}\' && top != \'{\')) { return 0; // 括号不匹配 } } i++; } return stack.top == -1; // 如果栈为空，则匹配成功}

4.2 队列的基本原理与实现

4.2.1 队列的性质和基本操作

队列是一种先进先出（First In First Out, FIFO）的数据结构，用于存储按顺序排列的数据。在队列中，元素的添加（入队）总是在队尾进行，而元素的移除（出队）则总是在队头进行。队列的基本操作包括入队（enqueue）、出队（dequeue）和查看队头元素（front）。

队列同样可以通过数组或链表来实现。下面是基于数组的队列实现示例：

#define QUEUESIZE 10 // 定义队列的最大容量typedef struct { int data[QUEUESIZE]; // 存储队列元素的数组 int front; // 队头指针 int rear; // 队尾指针} ArrayQueue;// 初始化队列void InitQueue(ArrayQueue *q) { q->front = q->rear = 0;}// 入队操作int Enqueue(ArrayQueue *q, int element) { if ((q->rear + 1) % QUEUESIZE == q->front) { return 0; // 队满，无法入队 } q->data[q->rear] = element; q->rear = (q->rear + 1) % QUEUESIZE; return 1;}// 出队操作int Dequeue(ArrayQueue *q, int *element) { if (q->front == q->rear) { return 0; // 队空，无法出队 } *element = q->data[q->front]; q->front = (q->front + 1) % QUEUESIZE; return 1;}

4.2.2 队列实现的源代码分析

队列的实现需要处理循环队列的情况，以便高效利用数组空间。下面的代码段中，我们通过取模运算来确保队尾指针在到达数组末尾时能够循环回到数组的开始位置。

// 查看队头元素int Front(const ArrayQueue *q) { if (q->front == q->rear) { return -1; // 队空，返回-1 } return q->data[q->front];}

队列在算法和程序设计中有着广泛的应用，如任务调度、缓冲处理等。通过队列我们可以确保按照元素进入队列的顺序来处理它们，这对于保证程序的公平性和顺序性至关重要。

// 示例：任务调度器void TaskScheduler(ArrayQueue *taskQueue) { while (1) { int task; if (Dequeue(taskQueue, &task)) { ProcessTask(task); // 处理队头任务 } }}

总结以上所述，栈和队列在算法与程序设计中扮演着重要的角色。它们解决特定类型的问题，并以不同的方式管理数据集合的访问顺序。理解这些数据结构的原理和实现对于任何试图提高其算法技能的开发者来说都是必须的。在处理诸如括号匹配、任务调度等实际问题时，熟练应用这些数据结构可以显著提高代码的效率和清晰度。

5. 二叉树、AVL树、红黑树、堆的结构和应用

5.1 二叉树的结构特性与遍历算法

5.1.1 二叉树的定义和分类

二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。二叉树的定义从根节点开始，根节点可以为空（空二叉树），也可以拥有左右子树，子树本身也是二叉树。根据子节点的不同特点，二叉树可以分为多种类型：

完全二叉树（Complete Binary Tree）：除了最后一层外，每一层都被完全填满，并且所有节点都向左排列。
满二叉树（Full Binary Tree）：每一个节点都有0个或者2个子节点。
平衡二叉树（Balanced Binary Tree）：任何两个叶子节点之间的高度差不会超过1。
二叉搜索树（Binary Search Tree, BST）：对于树中每个节点X，其左子树中所有项的值都小于X的值，右子树中所有项的值都大于X的值。
AVL树：一种自平衡的二叉搜索树，任何节点的两个子树的高度最大差别为1。
红黑树：一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。通过对任何一条从根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因而是近似平衡的。

5.1.2 二叉树遍历算法的实现

遍历是访问树中每个节点恰好一次的过程。二叉树的遍历算法主要有三种：前序遍历（Pre-order）、中序遍历（In-order）和后序遍历（Post-order）。另外，广为人知的层序遍历（Level-order）是通过按层次访问节点的方式实现遍历。

以下是前序遍历的递归实现方法，前序遍历的顺序是“根-左-右”：

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef preorderTraversal(root): if root is None: return [] return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)# 示例调用# root = TreeNode(1)# root.left = TreeNode(2)# root.right = TreeNode(3)# print(preorderTraversal(root)) # 输出: [1, 2, 3]

在这个示例中，我们定义了一个简单的二叉树节点类 TreeNode ，然后通过递归方式实现了前序遍历。每个节点首先被访问，然后是它的左子树，最后是它的右子树。递归调用会持续进行直到遇到叶子节点。

为了保证内容的深度和丰富性，接下来我们将深入探讨平衡二叉树（AVL树和红黑树）的原理与应用，并在后续小节中讨论堆的构造和应用。

6. 图的邻接矩阵和邻接表表示

6.1 图的表示方法

6.1.1 邻接矩阵的优缺点分析

邻接矩阵是图的一种矩阵表示方法，其中每个元素表示图中两个顶点之间的边。如果顶点i和顶点j之间存在边，则矩阵中的 matrix[i][j] 和 matrix[j][i] 一般设为1或其他非零值；如果不存在，则设为0。当图是无向图时，邻接矩阵是对称的；有向图则不一定。

优点：
- 简单直观： 邻接矩阵的结构简单，易于理解，特别是对于稠密图而言。
- 快速判断： 可以快速判断任意两点之间是否有边相连，即通过查询 matrix[i][j] 和 matrix[j][i] 来完成。

缺点：
- 空间复杂度高： 对于稀疏图，邻接矩阵会浪费大量空间，因为它要存储所有的 V^2 个可能的边，其中 V 是顶点数。
- 动态扩展困难： 在动态图中（即图的结构会变化），使用邻接矩阵进行边的添加和删除效率较低，因为每次修改都可能导致矩阵中很多元素的变动。

6.1.2 邻接表的数据结构与实现

邻接表是另一种图的表示方法，它使用链表来表示每个顶点的邻接点。每个顶点都有一个链表，链表中的每个节点存储了与该顶点相邻的顶点信息。

邻接表的优点：
- 空间效率高： 对于稀疏图来说，邻接表比邻接矩阵使用更少的空间。
- 动态性好： 增加或删除边都较为容易，只需对链表进行相应的操作。

邻接表的缺点：
- 实现复杂： 相较于邻接矩阵，邻接表的实现要复杂一些，编程时要处理指针或引用来维护链表。
- 查询效率稍低： 判断两个顶点是否相邻需要遍历链表，对于稠密图来说效率较低。

以下是一个简单的邻接表的C++实现示例：

#include #include class Graph { int V; // 顶点数目 std::list *adj; // 邻接表public: Graph(int V); // 构造函数 void addEdge(int v, int w); // 添加边 void printGraph(); // 打印图};Graph::Graph(int V) { this->V = V; adj = new std::list[V];}void Graph::addEdge(int v, int w) { adj[v].push_back(w); // 添加v到w的边 adj[w].push_back(v); // 对于无向图，添加w到v的边}void Graph::printGraph() { for (int v = 0; v < V; ++v) { std::cout << v << \"：\"; for (auto i = adj[v].begin(); i != adj[v].end(); ++i) std::cout < \" << *i; std::cout << std::endl; }}

在此代码中， Graph 类使用了一个 list 的数组来作为邻接表，每个 list 存储了与顶点 v 相邻的顶点。 addEdge 方法添加一条边，同时更新了两个顶点的邻接列表。 printGraph 方法遍历并打印出图的结构。

邻接表更加适合用于表示稀疏图，而邻接矩阵更适合表示稠密图或需要频繁查询边信息的场景。

6.2 图的搜索算法

6.2.1 深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索树或图的算法。其核心思想是从一个顶点开始，沿着一条路径进行搜索，直到路径的末端，然后回溯到前一个分叉点继续搜索，直至所有的顶点都被访问过。

以下是DFS的伪代码：

DFS(v): if v is unmarked mark v for each neighbor n of v DFS(n)

在实际应用中，通常需要额外的数据结构来追踪访问状态，比如使用布尔数组 visited ，标记节点是否被访问过。

6.2.2 广度优先搜索（BFS）

广度优先搜索则从一个顶点开始，先访问它的所有邻点，然后再从这些邻点出发，访问它们未被访问的邻点，直到所有的顶点都被访问过。

以下是BFS的伪代码：

BFS(v): Queue Q; Q.enqueue(v); while Q is not empty v = Q.dequeue() if v is unvisited mark v as visited for each neighbor n of v Q.enqueue(n)

BFS使用队列来保证在搜索过程中能按照从近到远的顺序访问顶点，通常用于寻找最短路径问题。

在图的数据结构和搜索算法部分，我们详细介绍了邻接矩阵和邻接表的优缺点，以及两种基本的图搜索算法：深度优先搜索（DFS）和广度优先搜索（BFS）。这些内容对于理解图的实现和操作非常关键，是数据结构学习中的基础和重点。

7. 散列表（哈希表）的高效操作

7.1 散列表的基本概念与原理

散列表（Hash table），又称哈希表，是一种利用哈希函数（Hash Function）来快速访问数据集合中元素的数据结构。散列表通过一个散列函数将待存储的键（key）映射为表中一个位置来访问记录，以加快查找速度。在理想情况下，这个函数能将键均匀地分布在整个数组中，从而使得查找操作的时间复杂度接近O(1)。

7.1.1 哈希函数的设计

哈希函数的设计至关重要，它直接决定了散列表的性能。一个好的哈希函数需要满足以下条件：

均匀分布 ：不同键计算出的索引值尽可能不冲突，即要尽量均匀地分布在哈希表中。
快速计算 ：计算哈希值的过程应尽可能快速。
确定性 ：相同的输入应产生相同的输出。
敏感性 ：输入的小变化应引起输出的显著变化，即避免产生过多的碰撞。

7.1.2 冲突解决策略

由于哈希函数将可能无限的键映射到有限的空间内，因此碰撞（两个不同的键计算出相同的索引）是不可避免的。解决冲突的常见策略有：

开放寻址法 ：在发生冲突时，顺序寻找下一个空槽。
链地址法（拉链法） ：将所有冲突的键存储在一个链表中。

7.2 散列表的操作与应用

散列表在实际编程中有着广泛的应用，从简单的查找和存储到复杂的数据处理，散列表都展现出了高效的性能。

7.2.1 散列表的增删查操作

增删查操作是散列表的基本操作，它们的效率直接决定了散列表的应用价值。

插入：计算待插入键的哈希值，放到哈希表对应位置。
删除：找到待删除键的哈希值对应的位置，进行删除操作。
查找：计算待查找键的哈希值，直接访问对应的槽。

7.2.2 散列表在实际问题中的应用案例

散列表在许多实际问题中扮演着重要角色。例如，在数据库索引中，散列表可以实现快速的数据检索；在网络路由器中，哈希表能够高效地进行数据包的转发决策；在缓存机制中，散列表用来快速判断缓存中是否含有特定数据。

代码示例：

// C语言实现的简单散列表#include #include #include #define TABLE_SIZE 100struct HashTableEntry { char *key; int value; struct HashTableEntry *next;};struct HashTableEntry *table[TABLE_SIZE];unsigned int hash(const char *key) { unsigned long int value = 0; unsigned int i = 0; unsigned int key_len = strlen(key); // 将key中的每个字符的ASCII值相加 for (; i key, key) == 0) { entry->value = value; return; } entry = entry->next; } // 创建新的哈希表条目 entry = (struct HashTableEntry *)malloc(sizeof(struct HashTableEntry)); entry->key = strdup(key); entry->value = value; entry->next = table[index]; table[index] = entry;}int search(char *key) { int index = hash(key); struct HashTableEntry *entry = table[index]; while (entry != NULL) { if (strcmp(entry->key, key) == 0) { return entry->value; } entry = entry->next; } return -1;}int main() { // 示例：插入键值对并进行查找 insert(\"key1\", 123); int value = search(\"key1\"); printf(\"The value for \'key1\' is: %d\\n\", value); return 0;}

本章节通过理论阐述了散列表的基础概念和原理，并通过代码示例具体展示了散列表的增删查操作。在后续的章节中，我们将探讨散列表在解决具体问题中的应用，例如在缓存系统中的应用等。