C语言中map插入数据时如何避免覆盖已有键值

在C语言中，并没有内置的map数据结构，因此我们需要自己实现或者使用第三方库来创建map。为了避免在插入数据时覆盖已有的键值，我们可以采取以下几种方法：

1. 使用哈希表

哈希表是一种常见的数据结构，它可以用来实现map。在哈希表中，每个键值对都会根据键的值计算出一个哈希码，然后存储在哈希码对应的槽位中。

以下是一个简单的哈希表实现，它可以避免覆盖已有的键值：

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

#define TABLE_SIZE 10

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

Node *hashTable[TABLE_SIZE];

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

void insert(char *key, int value) {
    unsigned int index = hashFunction(key);
    Node *node = hashTable[index];
    Node *prev = NULL;

    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            node->value = value;
            return;
        }
        prev = node;
        node = node->next;
    }

    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = value;
    newNode->next = NULL;

    if (prev == NULL) {
        hashTable[index] = newNode;
    } else {
        prev->next = newNode;
    }
}

int main() {
    insert("apple", 10);
    insert("banana", 20);
    insert("apple", 30); // 更新已有的键值

    printf("apple: %d\n", hashTable[hashFunction("apple")]->value);
    printf("banana: %d\n", hashTable[hashFunction("banana")]->value);

    return 0;
}

2. 使用平衡二叉搜索树（如AVL树或红黑树）

另一种方法是在C语言中使用平衡二叉搜索树（BST）来实现map。BST可以保证键值对的唯一性，并且可以高效地插入和查找。

以下是一个简单的AVL树实现，它可以避免覆盖已有的键值：

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

typedef struct AVLNode {
    char *key;
    int value;
    int height;
    struct AVLNode *left;
    struct AVLNode *right;
} AVLNode;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int height(AVLNode *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

AVLNode* newNode(char *key, int value) {
    AVLNode *node = (AVLNode *)malloc(sizeof(AVLNode));
    node->key = strdup(key);
    node->value = value;
    node->height = 1; // new node is initially added at leaf
    node->left = NULL;
    node->right = NULL;
    return node;
}

int getBalance(AVLNode *N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

AVLNode* rightRotate(AVLNode *y) {
    AVLNode *x = y->left;
    AVLNode *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

AVLNode* leftRotate(AVLNode *x) {
    AVLNode *y = x->right;
    AVLNode *T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

AVLNode* insert(AVLNode* node, char *key, int value) {
    if (node == NULL)
        return(newNode(key, value));

    if (strcmp(key, node->key) < 0)
        node->left = insert(node->left, key, value);
    else if (strcmp(key, node->key) > 0)
        node->right = insert(node->right, key, value);
    else
        node->value = value; // 更新已有的键值

    node->height = 1 + max(height(node->left), height(node->right));

    int balance = getBalance(node);

    if (balance > 1 && strcmp(key, node->left->key) < 0)
        return rightRotate(node);

    if (balance < -1 && strcmp(key, node->right->key) > 0)
        return leftRotate(node);

    if (balance > 1 && strcmp(key, node->left->key) > 0) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (balance < -1 && strcmp(key, node->right->key) < 0) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

int main() {
    AVLNode *root = NULL;
    root = insert(root, "apple", 10);
    root = insert(root, "banana", 20);
    root = insert(root, "apple", 30); // 更新已有的键值

    printf("apple: %d\n", root->right->right->value);
    printf("banana: %d\n", root->left->value);

    return 0;
}

以上两种方法都可以避免在C语言中插入数据时覆盖已有的键值。你可以根据实际需求选择适合的方法。