MOOC数据结构5-15 QQ帐户的申请与登陆 (25分)

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

输入格式:

输入首先给出一个正整数$N$（\le 10^5≤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

思路分析：考查散列。链式分离法，因为题目中说QQ号是一个大于1000的数，所以这里取QQ号字符串的前4位作为初始散列地址，时间大约是800MS。（经过测试，取前5位也能AC，而且时间效率提升非常大，约150MS）

#include <cstdio> #include <cstdlib> #include <string.h> typedef struct node { char user[11]; char password[17]; struct node* next; } Node; typedef struct { int TableSize; Node* Table; } HashTable; int nextPrime( int n ) { while( 1 ) { bool flag = true; for( int i = 2; i < n; i++ ) { if( n % i == 0 ) { flag = false; break; } } if( flag ) break; n++; } return n; } HashTable* createHashTable( int n ) { HashTable* H = ( HashTable* )malloc( sizeof( HashTable ) ); H->TableSize = nextPrime( n ); H->Table = ( Node* )malloc( ( H->TableSize ) * sizeof( Node ) ); for( int i = 0; i < H->TableSize; i++ ) { H->Table[i].next = NULL; H->Table[i].user[0] = '\0'; H->Table[i].password[0] = '\0'; } return H; } int Hash( char key[] ) { int index = 0; for( int i = 0; i <= 3; i++ ) { index = index * 10 + key[i] - '0'; } return index; } Node* Find( HashTable* H, char key[] ) { int index = Hash( key ) % ( H->TableSize ); Node* ptr = H->Table[index].next; while( ptr && strcmp( ptr->user, key ) ) { ptr = ptr->next; } return ptr; } void Insert( HashTable* H, char key[], char pass[] ) { int index = Hash( key ) % ( H->TableSize ); Node* newNode = ( Node* )malloc( sizeof( Node ) ); newNode->next = H->Table[index].next; H->Table[index].next = newNode; strcpy( newNode->user, key ); strcpy( newNode->password, pass ); } int main() { //freopen( "123.txt", "r", stdin ); int n; scanf( "%d", &n ); HashTable* H = createHashTable( n ); //printf( "%d\n", H->TableSize ); char op; char account[20]; char key[20]; for( int i = 0; i < n; i++ ) { char ch = getchar(); scanf( "%c %s %s", &op, account, key ); //printf( "%s %s\n", account, key ); if( op == 'L' ) { Node* p = Find( H, account ); if( !p ) printf( "ERROR: Not Exist\n" ); // 老账户号码不存在 else if( strcmp( p->password, key ) ) { // 老账户密码错误 printf( "ERROR: Wrong PW\n" ); } else { // 登录成功 printf( "Login: OK\n" ); } } if( op == 'N' ) { Node* p = Find( H, account ); if( p ) { // 申请的账户已经存在 printf( "ERROR: Exist\n" ); } else { Insert( H, account ,key ); printf( "New: OK\n" ); } } } return 0; }