题解 | #记票统计#

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


//{name,couny}结构体数组，结构体在数组中的索引=f(name)
//大数据时，地址范围<<key范围，不可能为每一个数据，预留存储地址，需要处理冲突，溢出？
//小数据时，key和地址可以一一对应
//某张投票是否是有效的票，需要和候选人行一系列比较，散列是为了避免比较
typedef struct node {
    int cnt;
    char name[20];
    int flag;//0未使用，1使用，2删除,暂不考虑删除
} NODE;
//插入index=node.name[0]*4%99，冲突时，顺序往后找，一定能找到位置存放候选人
//搜索时，从算出的index一直往后，找到node.name=NULL，或者node.name=下一个计算的地址值
NODE hashTable[120]; 

int main() {
    int n1 = 0, n2 = 0, i = 0, j = 0, index = 0, invalid=0;
    char tempName[20];
    int indexNum = 0;
    int* indexBak = NULL;
    if (scanf("%d", &n1) != EOF) {
        indexBak = (int*)malloc(n1 * sizeof(int));
        for (i = 0; i < n1; i++) {
            scanf("%s", tempName);
            index = (tempName[0]-'A') * 4%120; //所有候选人均匀分布在100个地址上
            while (hashTable[index].flag)
                index++;
            hashTable[index].flag = 1;
            strcpy(hashTable[index].name, tempName);
            indexBak[indexNum++] = index;
        }
        scanf("%d", &n2);
        for (i = 0; i < n2; i++) {
            scanf("%s", tempName);
            index = (tempName[0]-'A')  * 4%120;
            while (hashTable[index].flag) {
                if (strcmp(hashTable[index].name, tempName)==0) {
                    hashTable[index].cnt++;
                    break;
                }
                index++;
            }
            if(!hashTable[index].flag)
                invalid++;
        }
        for (i = 0; i < n1; i++) {
            printf("%s : %d\n", hashTable[indexBak[i]].name, hashTable[indexBak[i]].cnt);
        }
        free(indexBak);
        printf("Invalid : %d",invalid);
    }
    return 0;
}