题解 | 设计有setAll功能的哈希表

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

#define SIZE 128

typedef struct Node {
    int key;
    int val[2];
    struct Node* next;
} Node;

typedef struct {
    Node* table[SIZE];
} haxiset;

haxiset* create() {
    haxiset* ht = (haxiset*)malloc(sizeof(haxiset));
    // if (ht == NULL) {
    //     fprintf(stderr, "Memory allocation failed\0");
    //     exit(EXIT_FAILURE);
    // }
    for (int i = 0; i < SIZE; i++) {
        ht->table[i] = NULL;
    }
    return ht;
}

unsigned int haxifunc(int k) {
    return (unsigned int)(k % SIZE + SIZE) % SIZE; // 确保k为非负数
}

void insert(haxiset* ht, int k, int val, int cns) {
    int haxi = haxifunc(k);
    Node* newnode = (Node*)malloc(sizeof(Node));
    // if (newnode == NULL) {
    //     fprintf(stderr, "Memory allocation failed\n");
    //     exit(EXIT_FAILURE);
    // }
    newnode->key = k;
    newnode->val[0] = val;
    newnode->val[1] = cns;
    newnode->next = ht->table[haxi];
    ht->table[haxi] = newnode;
}

int search(haxiset* ht, int k, int setalltime, int setallval) {
    int haxi = haxifunc(k);
    Node* node = ht->table[haxi];
    while (node != NULL) {
        if (node->key == k) {
            if (setalltime > node->val[1]) return setallval;
            return node->val[0];
        }
        node = node->next;
    }
    return -1;
}

void destory(haxiset* ht) {
    for (int i = 0; i < SIZE; i++) {
        Node* node = ht->table[i];
        while (node != NULL) {
            Node* pre = node;
            node = node->next;
            free(pre);
        }
    }
    free(ht);
}

int main() {
    int n = 0;
    scanf("%d", &n);
    haxiset* ht = create();
    int setalltime = -1;
    int setallval;
    for (int choose = 0, cns = 0, k, v, ans; cns < n; cns++) {
        scanf("%d", &choose);
        switch (choose) {
            case 1:
                scanf("%d %d", &k, &v);
                insert(ht, k, v, cns);
                break;
            case 2:
                scanf("%d", &k);
                ans = search(ht, k, setalltime, setallval);
                printf("%d\n", ans);
                break;
            case 3:
                scanf("%d", &setallval);
                setalltime = cns;
                break;
        }
    }
    destory(ht);

    return 0;
}