使用哈希表呢

在 C 语言中使用哈希表对字符串去重可以显著提高效率，尤其是当数据量较大时。虽然 C 标准库中没有内置的哈希表结构，但可以使用第三方库（如 `uthash`）来简化实现。 --- ### ✅ 使用 `uthash` 实现字符串去重 `uthash` 是一个非常流行的 C 语言哈希表库，使用宏定义实现，性能高效，易于集成。 --- ### 📦 示例代码（使用 `uthash`）： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #include "uthash.h" // 需要先下载或包含 uthash.h // 定义用于哈希表的结构体 typedef struct { char *word; // 键（字符串） UT_hash_handle hh; // uthash 需要用到的句柄 } WordHash; int main() { char *words[10000]; // 原始字符串数组 int word_count = 0; // 模拟填充一些字符串（包含重复项） words[word_count++] = strdup("apple"); words[word_count++] = strdup("banana"); words[word_count++] = strdup("apple"); words[word_count++] = strdup("orange"); words[word_count++] = strdup("banana"); WordHash *word_map = NULL; // 哈希表 WordHash *current_word, *tmp; printf("去重后的单词：\n"); for (int i = 0; i < word_count; i++) { HASH_FIND_STR(word_map, words[i], current_word); // 查找是否已存在 if (current_word == NULL) { current_word = (WordHash *)malloc(sizeof(WordHash)); current_word->word = strdup(words[i]); HASH_ADD_KEYPTR(hh, word_map, current_word->word, strlen(current_word->word), current_word); printf("%s\n", words[i]); // 打印首次出现的单词 } } // 清理哈希表内存 HASH_ITER(hh, word_map, current_word, tmp) { HASH_DEL(word_map, current_word); free(current_word->word); free(current_word); } // 清理原始数组内存 for (int i = 0; i < word_count; i++) { free(words[i]); } return 0; } ``` --- ### 📌 说明： - `HASH_FIND_STR`：查找当前字符串是否已经在哈希表中。 - `HASH_ADD_KEYPTR`：将字符串添加到哈希表中。 - `strdup`：复制字符串以避免指针指向局部变量。 - `HASH_ITER`：安全地遍历并删除哈希表中的所有项。 --- ### 🧠 优点： | 方法 | 时间复杂度 | 说明 | |------|------------|------| | 暴力比较 | O(n²) | 简单但效率低 | | 哈希表（uthash） | O(n) | 高效，适合大数据量 | --- ### 📦 准备工作： 你需要下载 `uthash.h` 文件，可以从其官网获取： 🔗 [https://troydhanson.github.io/uthash/](https://troydhanson.github.io/uthash/) 然后将其放在项目目录中，并确保代码中包含： ```c #include "uthash.h" ``` --- ### ✅ 总结： 使用哈希表去重字符串的核心步骤是： 1. 定义结构体用于哈希键值。 2. 使用 `HASH_FIND_STR` 检查是否已存在。 3. 使用 `HASH_ADD_KEYPTR` 添加新字符串。 4. 最后释放所有内存。 ---