数据结构算法——1030. 方言翻译

本文主要是介绍数据结构算法——1030. 方言翻译，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

思路

利用哈希搜寻
（这里的哈希寻址我用了字符串每个字符相乘mod maxn得到对应的哈希码）
用链表避免冲突
只要maxn开的够大1e4应该都可以过（别开太大就行

代码

#include<iostream>
using namespace std;
#include<iostream>
const int maxn = 100000;
struct dot
{
    string dialect = "";
    string mandarin = "";
    dot* next = NULL;
};
struct HASH
{
    dot* head = NULL;
    dot* tail = NULL;
};

HASH d[maxn];
//
int main()
{
    string line;
    while(getline(cin,line))
    {
        if(line.length() == 0)
            break;
        string s, mandarin;
        int i = 0;
        while(line[i] != ' ')
            mandarin += line[i++];
        
        int len = line.length();
        i++;

        int hash_num = 1;

        while(i < len)
        {
            hash_num *= line[i];
            hash_num %= maxn;
            s += line[i++];
        }


        if(d[hash_num].head == NULL)
        {
            d[hash_num].head = d[hash_num].tail = new dot;
            d[hash_num].tail->dialect = s;
            d[hash_num].tail->mandarin = mandarin;
        }
        else
        {
            d[hash_num].tail->next = new dot;
            d[hash_num].tail->next->dialect = s;
            d[hash_num].tail->next->mandarin = mandarin;
            d[hash_num].tail = d[hash_num].tail->next;
        }
    }
    // for(int i = 0; i < 128; i++)
    // {

    //     if(d[i].head != NULL)
    //     {
    //         dot* record = d[i].head;
    //         while(record->next != NULL)
    //         {
    //             cout << record->dialect << " ok " << record->mandarin <<" ok" << endl;
    //             record = record->next;
    //         }
    //         cout << (char)i;
    //         std::cout << record->dialect << " ok " << record->mandarin << endl;
    //         cout << endl;
    //     }
    // }
    // cout << "--------"<<endl;

    string dialect;
    while(getline(cin,dialect))
    {
        if(dialect.length() == 0)
            break;

        int flag = 1;
        int hash_num = 1;
        int len = dialect.length();

        for(int i = 0; i < len; i++)
        {
            hash_num *= dialect[i];
            hash_num %= maxn;
        }
        
        if(d[hash_num].head != NULL)
        {
            dot* record = d[hash_num].head;
            while(record->next != NULL)
            {
                if(record->dialect == dialect)
                {
                    flag = 0;
                    cout << record->mandarin << endl;
                    goto FLAG;
                }
                record = record->next;
            }
            if(record->dialect == dialect)
            {
                flag = 0;
                cout << record->mandarin << endl;
            }
        }
        FLAG:
        if(flag)
            cout << "eh" << endl;

    }
}

这篇关于数据结构算法——1030. 方言翻译的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！