《数据结构》11-散列3 QQ帐户的申请与登陆

短命女 2022-04-14 06:23 152阅读 0赞

# 题目 #

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

**输入格式:**  
输入首先给出一个正整数N（≤10 5 ^5 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][myQQ_qq.com]  
> N 1234567890 [myQQ@qq.com][myQQ_qq.com]  
> N 1234567890 [myQQ@qq.com][myQQ_qq.com]  
> L 1234567890 myQQ@qq  
> L 1234567890 [myQQ@qq.com][myQQ_qq.com]

**输出样例:**

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

# 分析 #

## 解法一：散列表 ##

#include<iostream>
    #include<stdlib.h>
    #include<string>
    #include<cmath>
    #define MAXTABLESIZE 1000000
    using namespace std;
    typedef struct Node Cell;
    struct Node{
        
    	bool exist;
    	string acc;   // 账号
    	string pas;  // 密码 
    };
    
    typedef struct HashTBL *HashTable; 
    struct HashTBL{
        
    	int TableSize;
    	Cell *users;
    };
    
    int Hash(int key,int p){
        
    	return key%p;
    }
    
    int NextPrime(int N){
        
    	int p = N%2?N+2:N+1;
    	int i;
    	while(p <= MAXTABLESIZE) {
          
    		for(i=(int)sqrt(p);i>2;i--)
    			if(!(p%i))
    				break;
    		if(i==2 && p%4==3) // 保证平方探测都能找到 
    			break;
    		p +=2;
    	}
    	return p;
    }
    
    // 初始化 
    HashTable Create(int TableSize){
        
    	HashTable H;
    	H = (HashTable)malloc(sizeof(struct HashTBL));
    	H->TableSize = NextPrime(TableSize);
    	H->users = new Node[H->TableSize];
    	for(int i=0;i<H->TableSize;i++)
    		H->users[i].exist = false;
    	return H;
    }
    
    int Find(HashTable H,string key){
        
    	int NewPos,CurrentPos;
    	int CNum = 0;
    	NewPos = CurrentPos = Hash(atoi(key.c_str()),H->TableSize);
    	while(H->users[NewPos].exist && H->users[NewPos].acc != key){
        
    		if(++CNum %2){
        
    			NewPos =( CurrentPos + (CNum+1)/2*(CNum+1)/2 )%H->TableSize;
    		}else{
        
    			NewPos = CurrentPos - CNum/2*CNum/2;
    			while(NewPos < 0)
    				NewPos += H->TableSize;
    		}
    	}
    	return NewPos;
    }
    
    void Insert(HashTable H,string key,string pas,char flag){
        
    	int pos;
    	pos = Find(H,key);
    	if(H->users[pos].exist){
          // 已经存在 
    		if(flag == 'L'){
           // 登陆 
    			if(pas == H->users[pos].pas)   // 密码正确，登陆成功 
    				cout<<"Login: OK"<<endl;
    			else   // 密码错误，登陆失败 
    				cout<<"ERROR: Wrong PW"<<endl;
    		}else if(flag == 'N'){
          // 注册失败 
    			cout<<"ERROR: Exist"<<endl;
    		} 
    	}else{
          // 不存在 
    		if(flag == 'L')   // 登陆失败 
    			cout<<"ERROR: Not Exist"<<endl;
    		else if(flag == 'N'){
         // 注册成功 
    			cout<<"New: OK"<<endl; 
    			H->users[pos].exist = true;
    			H->users[pos].pas = pas;
    			H->users[pos].acc = key;
    		}
    	}
    }
    
    int main(){
        
    	HashTable H;
    	int N;
    	char command;
    	string account;
    	string password;
    	cin>>N;
    	H = Create(N);
    	for(int i=0;i<N;i++){
        
    		cin>>command>>account>>password;
    		Insert(H,account,password,command);
    	} 
    	return 0;
    }

## 解法二：map容器 ##

#include<cstdio>
    #include<iostream>
    #include<map>
    #include<string>
    using namespace std;
    int main(){
        
    	int N;
    	char command;
    	string qq;
    	string ps;
    	map<string,string> m;
    	scanf("%d",&N);
    	for(int i=0;i<N;i++){
        
    		getchar();
    		scanf("%c",&command);
    		cin>>qq>>ps;
    		if(command == 'N'){
             // 新用户 
    			if(m.find(qq)!=m.end())    // qq号已经存在 
    				printf("ERROR: Exist");
    			else{
            // 注册成功 
    				printf("New: OK");
    				m[qq] = ps;
    			}
    		}else if(command == 'L'){
          // 老用户 
    			if(m.find(qq)==m.end())  // 没找到 
    				printf("ERROR: Not Exist"); 
    			else if(m[qq] == ps)   // 密码正确 
    				printf("Login: OK");
    			else   
    				printf("ERROR: Wrong PW");
    		}
    		printf("\n");
    	} 
    	return 0;
    }

[myQQ_qq.com]: mailto:myQQ@qq.com