C언어 맵 구현

1 개요

C언어 맵 구현

2 예시 1

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

typedef struct Node {
    int key;
    int value;
    struct Node *left, *right;
} Node;

Node *_newNode(int key, int value) {
    Node *temp = (Node *)malloc(sizeof(Node));
    temp->key = key;
    temp->value = value;
    temp->left = temp->right = NULL;
    return temp;
}

Node *put(Node *node, int key, int value) {
    if (node == NULL) return _newNode(key, value);
    if (key < node->key) {
        node->left = put(node->left, key, value);
    } else if (key > node->key) {
        node->right = put(node->right, key, value);
    } else {
        node->value = value;
    }
    return node;
}

Node *_findRec(Node *node, int key) {
    if (node == NULL) return NULL;
    if (key == node->key) return node;
    if (key < node->key) return _findRec(node->left, key);
    return _findRec(node->right, key);
}

bool contains(Node *root, int key) {
    return _findRec(root, key) != NULL;
}

int get(Node *root, int key) {
    Node *node = _findRec(root, key);
    return node ? node->value : -1; // Return -1 if key is not found
}

Node *_minValueNode(Node *node) {
    while (node && node->left != NULL) node = node->left;
    return node;
}

Node *del(Node *node, int key) {
    if (node == NULL) return node;
    if (key < node->key) {
        node->left = del(node->left, key);
    } else if (key > node->key) {
        node->right = del(node->right, key);
    } else {
        if (node->left == NULL) {
            Node *temp = node->right;
            free(node);
            return temp;
        }
        if (node->right == NULL) {
            Node *temp = node->left;
            free(node);
            return temp;
        }
        Node* temp = _minValueNode(node->right);
        node->key = temp->key;
        node->value = temp->value;
        node->right = del(node->right, temp->key);
    }
    return node;
}

void _dumpMapRec(Node *node) {
    if (node != NULL) {
        _dumpMapRec(node->left);
        printf("%d:%d ", node->key, node->value);
        _dumpMapRec(node->right);
    }
}

void dumpMap(Node *root) {
    _dumpMapRec(root);
    printf("\n");
}

int main() {
    Node *root = NULL;
    root = put(root, 2, 200);
    root = put(root, 4, 404);
    dumpMap(root); // 2:200 4:404 
    root = del(root, 4);
    dumpMap(root); // 2:200 
    printf("2 => %d\n", get(root, 2)); // 2 => 200
    printf("4 => %d\n", get(root, 4)); // 4 => -1
    printf("%s\n", contains(root, 2) ? "yes" : "no"); // yes
    printf("%s\n", contains(root, 4) ? "yes" : "no"); // no
}

3 예시 2

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

#define TABLE_SIZE 100

typedef struct Entry {
    char *key;
    char *value;
    struct Entry *next;
} Entry;

typedef struct {
    Entry **entries;
} Map;

unsigned int hash(const char *key) {
    unsigned long int value = 0;
    unsigned int i = 0;
    unsigned int key_len = strlen(key);
    for (; i < key_len; ++i) {
        value = value * 37 + key[i];
    }
    return value % TABLE_SIZE;
}

Map *create() {
    Map *map = malloc(sizeof(Map));
    map->entries = malloc(sizeof(Entry*) * TABLE_SIZE);
    for (int i = 0; i < TABLE_SIZE; ++i) {
        map->entries[i] = NULL;
    }
    return map;
}

void put(Map *map, const char *key, const char *value) {
    unsigned int slot = hash(key);
    Entry *entry = malloc(sizeof(Entry));
    entry->key = strdup(key);
    entry->value = strdup(value);
    entry->next = map->entries[slot];
    map->entries[slot] = entry;
}

char* get(Map *map, const char *key) {
    unsigned int slot = hash(key);
    Entry *entry = map->entries[slot];
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
    return NULL;
}

void del(Map *map, const char *key) {
    unsigned int bucket = hash(key);
    Entry *entry = map->entries[bucket];
    Entry *previous = NULL;
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            if (previous == NULL) {
                map->entries[bucket] = entry->next;
            } else {
                previous->next = entry->next;
            }
            free(entry->key);
            free(entry->value);
            free(entry);
            return;
        }
        previous = entry;
        entry = entry->next;
    }
}

void destory(Map *map) {
    for (int i = 0; i < TABLE_SIZE; ++i) {
        Entry *entry = map->entries[i];
        while (entry != NULL) {
            Entry *temp = entry;
            entry = entry->next;
            free(temp->key);
            free(temp->value);
            free(temp);
        }
    }
    free(map->entries);
    free(map);
}

void dumpMap(Map *map) {
    for (int i = 0; i < TABLE_SIZE; ++i) {
        Entry *entry = map->entries[i];
        while (entry != NULL) {
            printf("%s:%s ", entry->key, entry->value);
            entry = entry->next;
        }
    }
    printf("\n");
}


int main() {
    Map *m = create();
    put(m, "hello", "world");
    put(m, "lorem", "ipsum");
    dumpMap(m); // hello:world lorem:ipsum
    del(m, "hello");
    dumpMap(m); // lorem:ipsum
    printf("hello => %s\n", get(m, "hello")); // hello => (null)
    printf("lorem => %s\n", get(m, "lorem")); // lorem => ipsum
    destory(m);
}

4 같이 보기

• C언어 덱 구현
• C언어 집합 구현
• C언어 해시테이블 구현
• C++ 맵