编辑“︁C 语言字典实现”︁（章节）

== 字典实现步骤 ==
以下是C语言中字典的完整实现步骤。

=== 1. 定义键值对结构 ===
每个键值对包含一个键（key）、一个值（value）和一个指向下一个键值对的指针（用于链地址法）。

<syntaxhighlight lang="c">
typedef struct KeyValuePair {
    char *key;
    int value;
    struct KeyValuePair *next;
} KeyValuePair;
</syntaxhighlight>

=== 2. 定义字典结构 ===
字典包含一个固定大小的数组（哈希表）和一个记录当前元素数量的变量。

<syntaxhighlight lang="c">
#define TABLE_SIZE 100

typedef struct Dictionary {
    KeyValuePair *table[TABLE_SIZE];
    int count;
} Dictionary;
</syntaxhighlight>

=== 3. 哈希函数 ===
哈希函数将字符串键转换为数组索引。这里使用简单的乘法哈希：

<syntaxhighlight lang="c">
unsigned int hash(const char *key) {
    unsigned int hash_value = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        hash_value = (hash_value * 31) + key[i];
    }
    return hash_value % TABLE_SIZE;
}
</syntaxhighlight>

=== 4. 字典初始化 ===
初始化字典时，将所有数组元素设为NULL。

<syntaxhighlight lang="c">
void dictionary_init(Dictionary *dict) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        dict->table[i] = NULL;
    }
    dict->count = 0;
}
</syntaxhighlight>

=== 5. 插入键值对 ===
插入时，先计算哈希值，然后检查是否已存在相同键。若存在则更新值，否则添加到链表头部。

<syntaxhighlight lang="c">
void dictionary_insert(Dictionary *dict, const char *key, int value) {
    unsigned int index = hash(key);
    KeyValuePair *current = dict->table[index];

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

    // 创建新键值对
    KeyValuePair *new_pair = malloc(sizeof(KeyValuePair));
    new_pair->key = strdup(key);
    new_pair->value = value;
    new_pair->next = dict->table[index];
    dict->table[index] = new_pair;
    dict->count++;
}
</syntaxhighlight>

=== 6. 查找键值对 ===
查找时，先计算哈希值，然后遍历链表查找匹配的键。

<syntaxhighlight lang="c">
int dictionary_lookup(Dictionary *dict, const char *key, int *value) {
    unsigned int index = hash(key);
    KeyValuePair *current = dict->table[index];

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            *value = current->value;
            return 1; // 找到
        }
        current = current->next;
    }
    return 0; // 未找到
}
</syntaxhighlight>

=== 7. 删除键值对 ===
删除时，先找到键值对，然后从链表中移除并释放内存。

<syntaxhighlight lang="c">
int dictionary_delete(Dictionary *dict, const char *key) {
    unsigned int index = hash(key);
    KeyValuePair *current = dict->table[index];
    KeyValuePair *prev = NULL;

    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            if (prev == NULL) {
                dict->table[index] = current->next;
            } else {
                prev->next = current->next;
            }
            free(current->key);
            free(current);
            dict->count--;
            return 1; // 删除成功
        }
        prev = current;
        current = current->next;
    }
    return 0; // 未找到键
}
</syntaxhighlight>

=== 8. 清理字典 ===
释放所有动态分配的内存。

<syntaxhighlight lang="c">
void dictionary_free(Dictionary *dict) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        KeyValuePair *current = dict->table[i];
        while (current != NULL) {
            KeyValuePair *temp = current;
            current = current->next;
            free(temp->key);
            free(temp);
        }
    }
    dict->count = 0;
}
</syntaxhighlight>