（C語言）Map數組的實現（數據結構）（鏈表）（指針）

源代碼：

#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// 清空Mapclear(&map);printf("final size: %d\n", size(&map));  // 輸出：final size: 0return 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));  // 輸出: 0return 0;
}

4. 代碼功能總結

核心數據結構：
- 實現了一個基于鏈地址法的哈希表
- 支持字符串鍵（key）和整數值（value）的存儲
支持操作：
- put(): 插入/更新鍵值對
- get(): 查找鍵對應的值
- removeKey(): 刪除指定鍵
- size(): 獲取元素數量
- clear(): 清空整個哈希表
沖突解決：
- 使用鏈表解決哈希沖突（鏈地址法）
- 每個桶是一個鏈表頭節點
內存管理：
- 動態分配節點內存
- 使用?strdup?復制鍵字符串
- 刪除/清空時釋放所有內存