题解 | #合并表记录#

#define _CRT_SECURE_NO_WARNINGS
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>


#define HASHMAP_CAPACITY 10

typedef int KeyType;
typedef int ValueType;

typedef struct node_s {
    int key;
    int val;
    struct node_s* next;
} KeyValueNode;

typedef struct {
    KeyValueNode* buckets[HASHMAP_CAPACITY];
    uint32_t hash_seed;
} HashMap;

int tmp[500] = { 0 };//用于存储哈希表结点的key值
int count = 0; //用于对哈希表结点计数

//哈希函数
static uint32_t hash(const void* key, int len, uint32_t seed) {
    const uint32_t m = 0x5bd1e995;
    const int r = 24;
    uint32_t h = seed ^ len;
    const unsigned char* data = (const unsigned char*)key;

    while (len >= 4) {
        uint32_t k = *(uint32_t*)data;
        k *= m;
        k ^= k >> r;
        k *= m;
        h *= m;
        h ^= k;
        data += 4;
        len -= 4;
    }

    switch (len) {
        case 3:
            h ^= data[2] << 16;
        case 2:
            h ^= data[1] << 8;
        case 1:
            h ^= data[0];
            h *= m;
    };

    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}
//创建哈希表
HashMap* hashmap_create() {
    HashMap* map = calloc(1, sizeof(HashMap));
    if (map == NULL) {
        printf("error: calloc failed in hashmap_create.\n");
        exit(-1);
    }
    map->hash_seed = time(NULL);
    return map;
}
//销毁哈希表
void hashmap_destroy(HashMap* map) {
    for (size_t i = 0; i < HASHMAP_CAPACITY; i++) {
        KeyValueNode* curr = map->buckets[i];
        while (curr != NULL) {
            KeyValueNode* tmp = curr->next;
            free(curr);
            curr = tmp;
        }
    }
    free(map);
}
//插入一个键值对
ValueType hashmap_put(HashMap* map, int key, int val) {
    char key_str[sizeof(int)];
    memcpy(key_str, &key, sizeof(int));
    int idx = hash(key_str, sizeof(int), map->hash_seed) % HASHMAP_CAPACITY;

    KeyValueNode* curr = map->buckets[idx];
    while (curr != NULL) {
        if (curr->key == key) {
            int old_val = curr->val;
            curr->val = old_val + val;
            return old_val;
        }
        curr = curr->next;
    }

    KeyValueNode* new_node = malloc(sizeof(KeyValueNode));
    if (new_node == NULL) {
        printf("Error: malloc failed in hashmap_put.\n");
        exit(1);
    }
    new_node->key = key;
    new_node->val = val;

    new_node->next = map->buckets[idx];
    map->buckets[idx] = new_node;

    return 0;
}

// 查询一个键值对
ValueType hashmap_get(HashMap* map, KeyType key) {
    char key_str[sizeof(int)];
    memcpy(key_str, &key, sizeof(int));
    int idx = hash(key_str, sizeof(int), map->hash_seed) % HASHMAP_CAPACITY;

    KeyValueNode* curr = map->buckets[idx];
    while (curr != NULL) {
        if (curr->key == key) {
            return curr->val;
        }
        curr = curr->next;
    }
    return 0; // 若不存在则返回0
}

// 快速排序的分区函数
static int partition(int arr[], int left, int right) {
    int pivot = arr[left];
    int low = left, high = right;

    while (low < high) {
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] < pivot) {
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

// 递归函数
void quick_sort_recursive(int arr[], int left, int right) {
    if (left < right) {
        int pivot_index = partition(arr, left, right);
        quick_sort_recursive(arr, left, pivot_index - 1);
        quick_sort_recursive(arr, pivot_index + 1, right);
    }
}

// 快速排序
void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

int main(void) {
    HashMap* map = hashmap_create();
    if (map == NULL) {
        printf("哈希表创建失败。\n");
        return 1;
    }

    int sum;
    scanf("%d", &sum);
    int key[500] = { 0 }, value[500] = { 0 };
    for (int i = 0; i < sum; i++) {
        scanf("%d %d", &key[i], &value[i]);
    }

    for (int i = 0; i < sum; i++) {
        hashmap_put(map, key[i], value[i]);
    }

    for (int i = 0; i < HASHMAP_CAPACITY; i++) {
        KeyValueNode* curr = map->buckets[i];
        while (curr != NULL) {
            tmp[count++] = curr->key;
            curr = curr->next;
        }
    }

    quick_sort(tmp, count);
    for (int i = 0; i < count; i++) {
        printf("%d %d\n", tmp[i], hashmap_get(map, tmp[i]));
    }

    hashmap_destroy(map);
    return 0;
}