7-15 航空公司VIP客户查询 (25分)（哈希，处理冲突，散列函数）（c++）

一时失言乱红尘 2022-12-20 09:05 88阅读 0赞

处理冲突的方法就是 用的链表。  
感觉处理好的话，用线性探测再散列 也可以。

下列代码中，哈希表的结构：每个节点的其实都代表一条链，其中，链的头节点不存放信息，首元素节点及之后存放信息。

#include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    //身份证号长度
    const int ID_LENGTH = 20;
    const int MAXNUM = 1e5 + 5;
    int N, K, M;
    char temp_str[ID_LENGTH];
    int temp_dist;
    
    typedef struct HashNode
    {
        
        char ID_number[ID_LENGTH];
        int total_dist;
        struct HashNode * next;
        HashNode() {
         total_dist = 0; next = NULL;}
    }HashNode;
    
    HashNode HashTable[MAXNUM];
    
    // code maybe ok
    //对身份证号各位求和取余
    int transf(char *str)
    {
        
        int ans = 0;
        for (int i = 0; i < 17; i++)
        {
        
            ans = 10 * ans + (str[i] - '0');
            ans %= MAXNUM;
        }
        if (str[17] == 'x') 
            ans = 10 * ans + 10;
        else 
            ans = 10 * ans + (str[17] - '0');
        ans %= MAXNUM;
        return ans;
    }
    
    void add(int address, char *temp_str, int temp_dist)
    {
        
        
        bool exist = false;
        HashNode * fp = &HashTable[address];
        HashNode * sp = HashTable[address].next;
        while (sp)
        {
        
            if (strcmp(sp->ID_number, temp_str) == 0)
            {
        
                sp->total_dist += temp_dist;
                exist = true;
                break;
            }
            fp = sp;
            sp = sp->next;
        }
        if (exist == false)
        {
        
            fp->next = new HashNode();
            strcpy(fp->next->ID_number, temp_str);
            fp->next->total_dist = temp_dist;
        }
    }
    
    void input()
    {
        
        int address = 0;
        cin >> N >> K;
        for (int i = 0 ; i < N; i++)
        {
        
            scanf("%s %d", temp_str, &temp_dist);
            if (temp_dist < K) temp_dist = K;
            address = transf(temp_str);
            add(address, temp_str, temp_dist);
        }
    }
    
    void find(char *s)
    {
        
        int address = transf(s);
        bool exist = false;
        HashNode * fp = &HashTable[address];
        HashNode * sp = HashTable[address].next;
        while (sp)
        {
        
            if (strcmp(sp->ID_number, temp_str) == 0)
            {
        
                printf("%d\n", sp->total_dist);
                exist = true;
                break;
            }
            fp = sp;
            sp = sp->next;
        }
        if (exist == false)
            printf("No Info\n");
    }
    void solve()
    {
        
        scanf("%d", &M);
        for (int i = 0; i < M; i++)
        {
        
            scanf("%s", temp_str);
            find(temp_str);
        }
    }
    int main()
    {
        
        //ios::sync_with_stdio(false);
        input();
        solve();
        system("pause");
        return 0;
    }