号码算法 关于快速查找与匹配

关于快速查找与匹配

寒假进行了数日的集训，感觉收获颇丰，虽然中间由于生病耽误了几天的训练，但后期又跟进进行了补充，仍然获得了许多宝贵的经验以及认识到了自身的不足，这一次先进行一种常见题型的总结，并列出两道典型例题，给出一些个人见解，不保证为最优解法，但至少为AC代码，如有不足，还望指出。

### 例题一：7-14 QQ帐户的申请与登陆（25 分）

7-15 QQ帐户的申请与登陆（25 分）

实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。

输入格式:

输入首先给出一个正整数N（≤10

??5

???? ），随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。号码算法QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。

输出格式:

针对每条指令，给出相应的信息：

1）若新申请帐户成功，则输出“New: OK”；
2）若新申请的号码已经存在，则输出“ERROR: Exist”；
3）若老帐户登陆成功，则输出“Login: OK”；
4）若老帐户QQ号码不存在，则输出“ERROR: Not Exist”；
5）若老帐户密码错误，则输出“ERROR: Wrong PW”。

输入样例:

5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com
输出样例:

ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK

原题地址：https://pintia.cn/problem-sets/15/problems/723

一道典型的数据结构题，主要考察快速查找以及重复的判断，难度一般，此题个人有两种解法，第一种是建立哈希表，可以用C语言实现。笔者通过阅读他人的解法受到了启发，给出原博地址，https://www.cnblogs.com/joeylee97/p/6628506.html；

第二种是利用C++STL中的map，较为简便，下面先给出C语言哈希表的实现：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef long long Datatype_account;         //由于账户可能大于int型的最大值，因此定义为LL型 
typedef char Datatype_password;             //定义char型变量来标识密码 
typedef struct List List;                   //声明链表的节点类型 
typedef struct Hashlist Hashlist;           //声明哈希表的节点类型 
struct List                                 //定义链表 
{
    Datatype_account id;
    Datatype_password pa[20];
    List *next;
};
struct Hashlist                              //定义哈希表 
{
    int size;
    List *table;
};
Hashlist *creat(int n);                      //定义一个创建哈希表的函数，返回值为哈希表的首地址 
int nextprime(int n);                        //采用除留余数法，因此需要找到大于总数据规模的最小素数 
int Hash(Hashlist *H,Datatype_account key);  //定义散列函数 
List *find(Hashlist *H,Datatype_account key);//定义查找函数 
void Login(Hashlist *H,Datatype_account key,Datatype_password *p);//定义登录函数 
void Apply(Hashlist *H,Datatype_account key,Datatype_password *p);//定义申请函数 
Hashlist *creat(int n)
{
    Hashlist *H = (Hashlist*)malloc(sizeof(Hashlist));  //首先为散列表首地址分配空间 
    H -> size = nextprime(n);                           //利用除留余数法，得到散列表的大小 
    int i = 0;
    H -> table = (List*)malloc(H -> size * sizeof(List));//为散列表分配空间 
    for(i = 0;i < H -> size;i++)                         //散列表的初始化 
    {
        H -> table[i].next = NULL;
        H -> table[i].id = 0;
        H -> table[i].pa[0] = '\0';
    }
    return H;
}
int nextprime(int n)                                     //寻找素数 
{
    int i,flag;
    while(1)
    {
        flag = 1;
        for(i = 2;i < n;i++)
        {
            if(n % i == 0)
            {
                flag = 0;
            }
        }
        if(flag)
        {
            break;
        }
        else
        {
            n++;
        }
    }
    return n;
}
int Hash(Hashlist *H,Datatype_account key) 
{
    long long index = key % H -> size;            //直接使用除留余数法得到散列函数对应的函数值 
    return index;
}
List *find(Hashlist *H,Datatype_account key) 
{
    long long index = Hash(H,key);                //得到键值对应的函数值 
    List *p = H -> table[index].next;             //将函数值映射到散列表中 
    while(p && key != p -> id)                    //若该节点存在且键值不等于列表中的值，则继续向下查找 
    {
        p = p -> next;
    }
    return p;                                     //返回该节点 
}
void Login(Hashlist *H,Datatype_account key,Datatype_password *p)
{
    List *f = find(H,key);                 //定义一个List型节点并按键值查找 
    if(f && !strcmp(f -> pa,p))            //若该节点存在且密码相符则输出登录成功 
    {
        printf("Login: OK");
    }
    else if(f && strcmp(f -> pa,p))        //若节点存在但密码不符 
    {
        printf("ERROR: Wrong PW");
    }
    else if(!f)                            //若节点不存在 
    {
        printf("ERROR: Not Exist");
    }
}
void Apply(Hashlist *H,Datatype_account key,Datatype_password *p)
{
    List *f = find(H,key);                 //仍然是先进行查找 
    if(f)                                  //若节点已存在，则提示错误信息 
    {
        printf("ERROR: Exist");
    }
    else                                   //若不存在，则建立节点，加入到散列中 
    {
        f = (List*)malloc(sizeof(List));
        long long index = Hash(H,key);
        f -> next = H -> table[index].next;
        H -> table[index].next = f;
        f -> id = key;
        strcpy(f -> pa,p);
        printf("New: OK");
    }
}
int main(void)
{
    int n = 0;
    Datatype_account acc;
    Datatype_password pa[20];
    char choose = '\0';
    scanf("%d",&n);
    Hashlist *H = creat(n);                 //预先分配空间 
    while(n--)
    {
        getchar();
        scanf("%c%lld%s",&choose,&acc,&pa);
        if(choose == 'L')
        {
            Login(H,acc,pa);
        }
        else
        {
            Apply(H,acc,pa);
        }
        printf("\n");
    }
    return 0;
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-86698-1.html