C语言中如何编写Map数据结构的实用指南

引言

在C言语中，map 数据构造并不是内置的，但我们可能经由过程构造体、数组、链表或哈希表等基本数据构造来模仿 map 的功能。本文将具体介绍如何在C言语中实现 map 数据构造，包含其不雅点、实现方法以及与其他数据构造的差别。

Map的不雅点

map 是一种键值对（key-value）存储的数据构造，可能根据键疾速查找对应的值。罕见操纵包含：

• 拔出：拔出一个键值对。
• 删除：删除一个键值对。
• 查找：根据键查找对应的值。

C言语中实现Map的方法

利用数组模仿简单的键值对映射

这种方法实用于小范围数据，键可能用整数或简单字符表示。

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

typedef struct {
    char key[20];
    int value;
} Map;

int main() {
    Map map[3] = {
        {"apple", 1},
        {"banana", 2},
        {"cherry", 3}
    };

    // 查找键为 "banana" 的值
    for (int i = 0; i < 3; i++) {
        if (strcmp(map[i].key, "banana") == 0) {
            printf("Key: %s, Value: %d\n", map[i].key, map[i].value);
            break;
        }
    }

    return 0;
}

利用链表实现静态Map

这种方法实用于须要静态扩大年夜的键值对凑集。

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

typedef struct Node {
    char key[20];
    int value;
    struct Node* next;
} Node;

Node* createNode(const char* key, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        return NULL;
    }
    strcpy(newNode->key, key);
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

int main() {
    // 创建节点
    Node* head = createNode("apple", 1);
    head->next = createNode("banana", 2);
    head->next->next = createNode("cherry", 3);

    // 查找键为 "banana" 的值
    Node* current = head;
    while (current != NULL) {
        if (strcmp(current->key, "banana") == 0) {
            printf("Key: %s, Value: %d\n", current->key, current->value);
            break;
        }
        current = current->next;
    }

    // 开释内存
    while (head != NULL) {
        Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

利用哈希表实现Map

哈希表是一种高效的查找数据构造，它经由过程哈希函数将键映射到数组中的一个地位，从而实现疾速查找。

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

#define TABLE_SIZE 10

typedef struct Node {
    char key[20];
    int value;
    struct Node* next;
} Node;

unsigned int hash(const char* key) {
    unsigned int hash = 0;
    while (*key) {
        hash = 31 * hash + *key++;
    }
    return hash % TABLE_SIZE;
}

Node* createNode(const char* key, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        return NULL;
    }
    strcpy(newNode->key, key);
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

void insert(Node** table, const char* key, int value) {
    unsigned int index = hash(key);
    Node* newNode = createNode(key, value);
    newNode->next = table[index];
    table[index] = newNode;
}

int main() {
    Node* table[TABLE_SIZE] = {NULL};

    // 拔出数据
    insert(table, "apple", 1);
    insert(table, "banana", 2);
    insert(table, "cherry", 3);

    // 查找键为 "banana" 的值
    unsigned int index = hash("banana");
    Node* current = table[index];
    while (current != NULL) {
        if (strcmp(current->key, "banana") == 0) {
            printf("Key: %s, Value: %d\n", current->key, current->value);
            break;
        }
        current = current->next;
    }

    // 开释内存
    for (int i = 0; i < TABLE_SIZE; i++) {
        Node* current = table[i];
        while (current != NULL) {
            Node* temp = current;
            current = current->next;
            free(temp);
        }
    }

    return 0;
}

总结

经由过程以上方法，我们可能在C言语中实现 map 数据构造。在现实利用中，可能根据具体须要抉择合适的实现方法。盼望本文能帮助你更好地懂得C言语中的 map 数据构造。