11-雜湊3 QQ帳戶的申請與登陸   (25分)

NO IMAGE

實現QQ新帳戶申請和老帳戶登陸的簡化版功能。最大挑戰是:據說現在的QQ號碼已經有10位數了。

輸入格式:

輸入首先給出一個正整數NN(≤10^5​​),隨後給出NN行指令。每行指令的格式為:“命令符(空格)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 [email protected]
N 1234567890 [email protected]
N 1234567890 [email protected]
L 1234567890 [email protected]
L 1234567890 [email protected]

輸出樣例:

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

解法一:雜湊表儲存qq賬號和密碼(與電話聊天狂人解法相近)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define KEYLENGTH 10
#define MAXTABLESIZE 100000
typedef char ElementType[KEYLENGTH   1];
typedef char PasswordType[17];
typedef int Index;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
PasswordType Pw;	//增加密碼
};
typedef struct LNode *List;
typedef struct LNode *Position;
typedef struct TblNode *HashTable;
struct TblNode {
int TableSize;
List Heads;
};
int NextPrime ( int n ) {
if ( n == 1 ) 
return 2;
else {
int i, p = n % 2 ? n   2 : n   1;
while ( p <= MAXTABLESIZE ) {
double q = p;
for ( i = sqrt(q); i > 2; i-- )
if ( p % i ) break;
if ( i == 2 ) break;
else p  = 2;
}
return p;
}
}
HashTable CreateTable ( int TableSize ) {
HashTable H;
H = (HashTable)malloc(sizeof(struct TblNode));
H->TableSize = NextPrime( TableSize );
H->Heads = (List)malloc(H->TableSize * sizeof(struct LNode));
for ( int i = 0; i < H->TableSize; i   ) {
H->Heads[i].Data[0] = '\0';
H->Heads[i].Pw[0] = '\0';  //初始化
H->Heads[i].Next = NULL;
}
return H;
}
Index Hash ( const char *key, int TableSize ) {
unsigned int h = 0;
while ( *key != '\0' ) {
h = ( h << 5 )   *key  ;
}
return h % TableSize;
}
Position Find ( HashTable H, ElementType Key ) {
Position P;
Index pos;
pos = Hash( Key   3, H->TableSize );
P = H->Heads[pos].Next;
while ( P && strcmp( P->Data, Key ) ) 
P = P->Next;
return P;
}
bool Insert ( HashTable H, ElementType Key, PasswordType Pw) {
Index pos;
if ( Find( H, Key ) ) 
return false;
else {
Position NewCell = (Position)malloc(sizeof(struct LNode));
strcpy( NewCell->Data, Key );
strcpy( NewCell->Pw, Pw );  //記錄密碼
pos = Hash( Key   3, H->TableSize );
NewCell->Next = H->Heads[pos].Next;
H->Heads[pos].Next = NewCell;
return true;
}
}
void DestroyTable ( HashTable H ) {
int i;
Position Tmp, P;
for ( i = 0; i < H->TableSize; i   ) {
P = H->Heads[i].Next;
while ( P != NULL ) {
Tmp = P;
P = P->Next;
free(Tmp);
}
}
free( H->Heads );
free( H );
}
//檢查密碼是否正確
bool CheckPassword ( Position P, char pw[] ) {
if ( strcmp( pw, P->Pw ) )
return false;
else
return true;
}
//檢查賬戶是否存在
bool FindAccount ( HashTable H, char qq[] ) {
Position P;
Index pos;
pos = Hash( qq   3, H->TableSize );
P = H->Heads[pos].Next;
while ( P != NULL ) {
if ( strcmp( P->Data, qq ) == 0 )
return 1;
P = P->Next;
}
return 0;
}
int main () {
int N;
char c, qq[11], pw[17];
HashTable H;
scanf("%d", &N);
getchar();
H = CreateTable( 2 * N );
while ( N-- ) {
scanf("%c %s %s", &c, qq, pw);
getchar();
if ( c == 'L' ) {
if ( FindAccount( H, qq ) ) {
if ( CheckPassword( Find( H, qq ), pw ) )
printf("Login: OK\n");
else 
printf("ERROR: Wrong PW\n");
}
else 
printf("ERROR: Not Exist\n");
}
else {
if ( FindAccount( H, qq) ) 
printf("ERROR: Exist\n");
else {
printf("New: OK\n");
Insert( H, qq, pw );
}
}
}
DestroyTable( H );
system("pause");
return 0;
}

解法二:排序,利用map容器

#include <cstdio>
#include <string>
#include <map>
#include <cstdlib>
using namespace std;
int main () {
int N;
char c, s1[11], s2[17];
string qq, pw;
map<string, string> m;
scanf("%d", &N);
getchar();
while ( N-- ) {
scanf("%c %s %s", &c, s1, s2);
getchar();
qq = s1; pw = s2;
if ( c == 'N') {
if ( m.find(qq) != m.end() )
printf("ERROR: Exist\n");
else {
printf("New: OK\n");
m[qq] = pw;
}
}
else {
if ( m.find(qq) == m.end() )
printf("ERROR: Not Exist\n");
else if ( m[qq] == pw )
printf("Login: OK\n");
else 
printf("ERROR: Wrong PW\n");
}
}
system("pause");
return 0;
}