题解 | 合并表记录

#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE (1000) // 500/1000 = 0.5

typedef struct hash_node {
    int index;
    int value;
    struct hash_node* next_node;
} hash_node;

typedef struct {
    int index;
    int value;
} record;

int hash_function(int index) { // 哈希函数
    return index % TABLE_SIZE;
}

void add_new_node(hash_node** table, int hash_value, int index, int value) { // 哈希表更改值/增加节点
    hash_node* current = table[hash_value];
    while (current != NULL) {
        if (current->index == index) {
            current->value += value;
            return;
        }
        current = current->next_node;
    }
    hash_node* new_node = (hash_node*)malloc(sizeof(hash_node));
    new_node->next_node = table[hash_value];
    new_node->value = value;
    new_node->index = index;
    table[hash_value] = new_node;
}

void free_hash_table(hash_node** table, int size) { // 释放哈希表
    for (int i=0; i<size; i++) {
        hash_node* current = table[i];
        while (current != NULL) {
            hash_node* temp = current;
            current = current->next_node;
            free(temp);
        }
    }
}

int compare(const void* a, const void* b) {
    return ((record*)a)->index - ((record*)b)->index;
}

int main() {
    int record_num; // 记录行数
    scanf("%d", &record_num);

    hash_node* hash_table[TABLE_SIZE] = {NULL}; // 储存记录到哈希表
    int index, value;
    for (int i=0; i<record_num; i++) {
        scanf("%d %d", &index, &value);
        int hash_value = hash_function(index);
        add_new_node(hash_table, hash_value, index, value);
    }
    int count = 0; // 计算节点数
    for (int i=0; i<TABLE_SIZE; i++) {
        hash_node* current = hash_table[i];
        while (current != NULL) {
            current = current->next_node;
            count ++;
        }
    }

    record* ordered_records = (record*)malloc(sizeof(record) * count);
    int records_index = 0;
    for (int i=0; i<TABLE_SIZE; i++) {
        hash_node* current = hash_table[i];
        while (current != NULL) {
            ordered_records[records_index].index = current->index;
            ordered_records[records_index].value = current->value;
            current = current->next_node;
            records_index ++;
        }
    }

    qsort(ordered_records, count, sizeof(record), compare);

    for (int i=0; i<count; i++) {
        printf("%d %d\n", ordered_records[i].index, ordered_records[i].value);
    }
    
    free_hash_table(hash_table, TABLE_SIZE);
    free(ordered_records);
    return 0;
}