（C语言）Map数组的实现（数据结构）（链表）（指针）-EW帮帮网

源代码：

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

// 键值对节点
typedef struct Node {
    char* key;
    int value;
    struct Node* next;
} Node;

// Map结构
typedef struct {
    Node* buckets[100];  // 固定大小的哈希桶（简化版）
    int size;            // 元素数量
} Map;

// 简单哈希函数（字符串转索引）
int hash(const char* key) {
    int hash = 0;
    while (*key) {
        hash += (*key++);
    }
    return hash % 100;  // 对应buckets大小
}

// 初始化Map
void initMap(Map* map) {
    memset(map->buckets, 0, sizeof(map->buckets));
    map->size = 0;
}

// 插入或更新键值对
void put(Map* map, const char* key, int value) {
    if (!key) return;
    
    int index = hash(key);
    Node* curr = map->buckets[index];
    
    // 查找是否已存在键
    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            curr->value = value;  // 更新值
            return;
        }
        curr = curr->next;
    }
    
    // 不存在则创建新节点（头插法）
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) return;
    
    newNode->key = strdup(key);
    if (!newNode->key) {
        free(newNode);
        return;
    }
    
    newNode->value = value;
    newNode->next = map->buckets[index];
    map->buckets[index] = newNode;
    map->size++;
}

// 根据键获取值
int get(Map* map, const char* key, int* result) {
    if (!key || !result) return 0;
    
    int index = hash(key);
    Node* curr = map->buckets[index];
    
    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            *result = curr->value;
            return 1;  // 找到
        }
        curr = curr->next;
    }
    return 0;  // 未找到
}

// 删除键值对
int removeKey(Map* map, const char* key) {
    if (!key) return 0;
    
    int index = hash(key);
    Node* curr = map->buckets[index];
    Node* prev = NULL;
    
    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            if (prev) {
                prev->next = curr->next;
            } else {
                map->buckets[index] = curr->next;
            }
            free(curr->key);
            free(curr);
            map->size--;
            return 1;
        }
        prev = curr;
        curr = curr->next;
    }
    return 0;
}

// 获取元素数量
int size(Map* map) {
    return map->size;
}

// 清空Map
void clear(Map* map) {
    for (int i = 0; i < 100; i++) {
        Node* curr = map->buckets[i];
        while (curr) {
            Node* next = curr->next;
            free(curr->key);
            free(curr);
            curr = next;
        }
        map->buckets[i] = NULL;
    }
    map->size = 0;
}

// 测试函数
int main() {
    Map map;
    initMap(&map);
    
    // 插入数据
    put(&map, "apple", 10);
    put(&map, "banana", 5);
    put(&map, "orange", 8);
    
    // 获取数据
    int val;
    if (get(&map, "banana", &val)) {
        printf("banana: %d\n", val);  // 输出：banana: 5
    }
    
    // 更新数据
    put(&map, "banana", 15);
    get(&map, "banana", &val);
    printf("updated banana: %d\n", val);  // 输出：updated banana: 15
    
    // 删除数据
    removeKey(&map, "orange");
    printf("size after remove: %d\n", size(&map));  // 输出：size after remove: 2
    
    // 清空Map
    clear(&map);
    printf("final size: %d\n", size(&map));  // 输出：final size: 0
    
    return 0;
}

代码详解：

这个代码实现了一个简单的 哈希表（Hash Map） 数据结构，用于存储键值对（key-value pairs）。下面将详细解释代码的每一部分及其功能：

1. 数据结构设计

节点结构 `Node`

typedef struct Node {
    char* key;          // 字符串键
    int value;          // 整数值
    struct Node* next;  // 指向下一个节点的指针（处理哈希冲突）
} Node;

作用：存储键值对的基本单元
关键点：
- key 使用 strdup 动态分配内存存储字符串
- next 指针用于解决哈希冲突（链地址法）

哈希表结构 `Map`

typedef struct {
    Node* buckets[100];  // 哈希桶数组（固定大小100）
    int size;            // 当前存储的元素数量
} Map;

作用：管理整个哈希表
关键点：
- buckets 是长度为 100 的指针数组，每个桶对应一个链表
- size 记录当前存储的键值对数量

2. 核心功能实现

哈希函数 `hash()`

int hash(const char* key) {
    int hash = 0;
    while (*key) {
        hash += (*key++);  // 简单累加ASCII值
    }
    return hash % 100;     // 映射到0-99的桶索引
}

作用：将任意字符串键映射到固定范围的索引
特点：
- 简单但容易产生冲突（如 "ab" 和 "ba" 哈希值相同）
- 使用取模运算确保结果在桶数组范围内

初始化函数 `initMap()`

void initMap(Map* map) {
    memset(map->buckets, 0, sizeof(map->buckets));
    map->size = 0;
}

作用：初始化哈希表状态
关键操作：
- 将所有桶指针设为 NULL
- 元素计数器 size 归零

插入/更新函数 `put()`

void put(Map* map, const char* key, int value) {
    // 1. 计算哈希索引
    int index = hash(key);
    
    // 2. 检查键是否已存在（更新值）
    Node* curr = map->buckets[index];
    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            curr->value = value;
            return;
        }
        curr = curr->next;
    }
    
    // 3. 创建新节点（头插法）
    Node* newNode = malloc(sizeof(Node));
    newNode->key = strdup(key);  // 复制键字符串
    newNode->value = value;
    newNode->next = map->buckets[index];
    map->buckets[index] = newNode;
    map->size++;
}

特点：
- 键存在时更新值
- 键不存在时使用头插法添加新节点
- 使用 strdup 深拷贝键字符串

查找函数 `get()`

int get(Map* map, const char* key, int* result) {
    int index = hash(key);
    Node* curr = map->buckets[index];
    
    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            *result = curr->value;  // 通过指针返回结果
            return 1;  // 成功找到
        }
        curr = curr->next;
    }
    return 0;  // 未找到
}

特点：
- 返回查找状态（1成功/0失败）
- 通过指针参数 result 返回查找到的值

删除函数 `removeKey()`

int removeKey(Map* map, const char* key) {
    int index = hash(key);
    Node* curr = map->buckets[index];
    Node* prev = NULL;
    
    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            // 从链表中删除节点
            if (prev) prev->next = curr->next;
            else map->buckets[index] = curr->next;
            
            // 释放内存
            free(curr->key);
            free(curr);
            map->size--;
            return 1;  // 删除成功
        }
        prev = curr;
        curr = curr->next;
    }
    return 0;  // 键不存在
}

关键操作：
- 处理链表中间/头部节点的删除
- 释放键字符串和节点本身的内存

辅助函数

int size(Map* map) { return map->size; }  // 返回元素数量

void clear(Map* map) {                   // 清空整个哈希表
    for (int i = 0; i < 100; i++) {
        Node* curr = map->buckets[i];
        while (curr) {
            Node* next = curr->next;
            free(curr->key);
            free(curr);
            curr = next;
        }
        map->buckets[i] = NULL;
    }
    map->size = 0;
}

3. 测试逻辑（main函数）

int main() {
    Map map;
    initMap(&map);  // 初始化
    
    // 插入测试
    put(&map, "apple", 10);
    put(&map, "banana", 5);
    put(&map, "orange", 8);
    
    // 查找测试
    int val;
    get(&map, "banana", &val);  // 输出: banana: 5
    
    // 更新测试
    put(&map, "banana", 15);    // 更新值
    get(&map, "banana", &val);  // 输出: updated banana: 15
    
    // 删除测试
    removeKey(&map, "orange");
    printf("size after remove: %d\n", size(&map));  // 输出: 2
    
    // 清空测试
    clear(&map);
    printf("final size: %d\n", size(&map));  // 输出: 0
    
    return 0;
}

4. 代码功能总结

核心数据结构：
- 实现了一个基于链地址法的哈希表
- 支持字符串键（key）和整数值（value）的存储
支持操作：
- put(): 插入/更新键值对
- get(): 查找键对应的值
- removeKey(): 删除指定键
- size(): 获取元素数量
- clear(): 清空整个哈希表
冲突解决：
- 使用链表解决哈希冲突（链地址法）
- 每个桶是一个链表头节点
内存管理：
- 动态分配节点内存
- 使用 strdup 复制键字符串
- 删除/清空时释放所有内存

5. 局限性及改进建议

固定桶大小：
- 桶数组固定为100，可能导致冲突率高
- 改进：实现动态扩容（如负载因子>0.75时扩容）
简单哈希函数：
- 当前哈希函数易产生冲突
- 改进：使用更复杂的哈希算法（如djb2）
键类型限制：
- 仅支持字符串键
- 改进：使用泛型支持多种键类型
线程安全：
- 非线程安全
- 改进：添加互斥锁实现线程安全
错误处理：
- 未处理内存分配失败情况
- 改进：添加NULL指针检查

6. 实际应用场景

配置存储：存储程序配置参数（键值对）
缓存系统：实现简单的内存缓存
词频统计：统计文本中单词出现次数
符号表：编译器中的变量管理
路由表：网络设备中的IP路由查找

注：该代码是本人自己所写，可能不够好，不够简便，欢迎大家指出我的不足之处。如果遇见看不懂的地方，可以在评论区打出来，进行讨论，或者联系我。上述内容全是我自己理解的，如果你有别的想法，或者认为我的理解不对，欢迎指出！！！如果可以，可以点一个免费的赞支持一下吗？谢谢各位彦祖亦菲！！！！！

（C语言）Map数组的实现（数据结构）（链表）（指针）

源代码：

代码详解：

1. 数据结构设计

节点结构 `Node`

哈希表结构 `Map`

2. 核心功能实现

哈希函数 `hash()`

初始化函数 `initMap()`

插入/更新函数 `put()`

查找函数 `get()`

删除函数 `removeKey()`

辅助函数

3. 测试逻辑（main函数）

4. 代码功能总结

5. 局限性及改进建议

6. 实际应用场景

网站公告

今日签到

热门文章

最新发布

（C语言）Map数组的实现（数据结构）（链表）（指针）

源代码：

代码详解：

1. 数据结构设计

节点结构 Node

哈希表结构 Map

2. 核心功能实现

哈希函数 hash()

初始化函数 initMap()

插入/更新函数 put()

查找函数 get()

删除函数 removeKey()

辅助函数

3. 测试逻辑（main函数）

4. 代码功能总结

5. 局限性及改进建议

6. 实际应用场景

网站公告

今日签到

热门文章

最新发布

节点结构 `Node`

哈希表结构 `Map`

哈希函数 `hash()`

初始化函数 `initMap()`

插入/更新函数 `put()`

查找函数 `get()`

删除函数 `removeKey()`