pta-HASH--QQ账号与密码注册和登录

输入格式:

输入首先给出一个正整数$N$（≤），随后给出$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

这道题实际上O（n√￣n），688ms左右，hash表传言O（1）查找，实际上不够稳定，我写的hash运行时间和map差不多。。。

1.线性表：平方探测处理冲突

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxm=99997;//比表长10^5小的质数 const int maxn=110000;//平方探测法n太小容易找不到 ！！！！一定要覆盖全部数，大于n也要大于999999999%99997char op;//操作 struct p {ll qq;char ma[20];}; p hash1[maxn];//hash表 int DealConflict(p t,int index)//平方探测法处理冲突 {int temp;for(int i=0;i<=sqrt(maxn)+1;i++){if(i%2==1)//奇数加 {temp=index+(i/2+1)*(i/2+1);if(temp<maxn)//不越界 {if(hash1[temp].qq==0){return temp;}}}else//偶数减 {temp=index-(i/2)*(i/2);if(temp>=0)//不越界 {if(hash1[temp].qq==0){return temp;}} }}}void CreateHash(p t)//取模法建立hash {int temp=t.qq%maxm;int set=DealConflict(t,temp);hash1[set].qq=t.qq;strcpy(hash1[set].ma,t.ma);}int SearchHash(p t)//查找qq号 密码匹配 {ll index=t.qq%maxm;int cur;for(int i=0;i<=sqrt(maxn)+1;i++){if(i%2==1)//奇数加 {cur=index+(i/2+1)*(i/2+1);if(cur<maxn)//不越界 {if(hash1[cur].qq==t.qq){if(strcmp(hash1[cur].ma,t.ma)==0)return 2;elsereturn 1;}}}else//偶数减 {cur=index-(i/2)*(i/2);if(cur>=0)//不越界 {if(hash1[cur].qq==t.qq){if(strcmp(hash1[cur].ma,t.ma)==0)return 2;elsereturn 1;}} }}return 0; }int main() { int n; cin>>n; p temp; while(n--) {cin>>op>>temp.qq>>temp.ma;if(op=='N'){if(SearchHash(temp)==1||SearchHash(temp)==2){cout<<"ERROR: Exist"<<endl;}else{cout<<"New: OK"<<endl;CreateHash(temp);}}else{if(SearchHash(temp)==0){cout<<"ERROR: Not Exist"<<endl;}else{if(SearchHash(temp)==1){cout<<"ERROR: Wrong PW"<<endl;}//elsecout<<"Login: OK"<<endl;}}}}

2.链表：类似邻接表的结构（但不带头结点，因为初始化头结点需要时间）

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxm=99997;//比表长10^5小的质数  const int maxn=110000; vector<int>p; char op; struct q1 {ll qq;char ma[20];};struct q2 {ll qq;char ma[20];q2 *next;}Q; q2 *hash1[maxn];//void Init() //{ // hash1[cur]=new q2;//  hash1[cur]->next=NULL; //} void Insert(q1 t)  {int cur=t.qq%maxm;q2 *s;s=new q2;s->qq=t.qq;strcpy(s->ma,t.ma);s->next=NULL;s->next=hash1[cur];hash1[cur]=s;}int Search(q1 t) {int cur=t.qq%maxm;if(hash1[cur]==NULL)//带头结点的话，初始化全部时间耗费大，所以不带头节点 return 0;q2 *s;s=hash1[cur];while(s!=NULL){if(s->qq==t.qq){if(strcmp(s->ma,t.ma)==0)return 2;elsereturn 1;}s=s->next;}//if(s==NULL)//空要马上跳出，不然下面报错  // return -1;return 0; }int main() {int n;cin>>n;q1 temp;for(int i=0;i<n;i++){cin>>op>>temp.qq>>temp.ma;if(op=='N'){if(Search(temp)==1||Search(temp)==2)cout<<"ERROR: Exist"<<endl;else {cout<<"New: OK"<<endl;if(Search(temp)==0)Insert(temp);}}else{if(Search(temp)==0)cout<<"ERROR: Not Exist"<<endl;else if(Search(temp)==2)cout<<"Login: OK"<<endl;elsecout<<"ERROR: Wrong PW"<<endl;}}}

总结

以上是生活随笔为你收集整理的pta-HASH--QQ账号与密码注册和登录的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。