11-散列3 QQ帐户的申请与登陆 (25 分)

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

输入格式:

输入首先给出一个正整数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
  1 #include "cstdio"
  2 #include <stdlib.h>
  3 #include <cstring>
  4 #include <math.h>
  5 #define KEYLENGTH 15 /* 关键词字符串的最大长度 */
  6 #define UPPERBOUND 1e6
  7 typedef struct Accounts {char ID[KEYLENGTH]; char PW[KEYLENGTH]; } ElementType;
  8 
  9 typedef int Index;                     /* 散列地址类型 */
 10 
 11 /******** 以下是单链表的定义 ********/
 12 typedef struct LNode *PtrToLNode;
 13 struct LNode {
 14     ElementType Data;
 15     PtrToLNode Next;
 16 };
 17 typedef PtrToLNode Position;
 18 typedef PtrToLNode List;
 19 /******** 以上是单链表的定义 ********/
 20 
 21 
 22 
 23 typedef struct TblNode *HashTable; /* 散列表类型 */
 24 struct TblNode {   /* 散列表结点定义 */
 25     int TableSize; /* 表的最大长度 */
 26     List Heads;    /* 指向链表头结点的数组 */
 27 };
 28 
 29 bool isPrime( int N )
 30 {
 31     if (N == 1) {
 32         return false;
 33     }
 34     
 35     int i;
 36     for ( i=(int) sqrt(N); i>=2; i--) {
 37         if (N % i == 0) {
 38             break;
 39         }
 40     }
 41     if( i == 1) return true;
 42     else return false;
 43 }
 44 int NextPrime( int N )
 45 {
 46     int P;
 47     P = N % 2 ? N + 2: N + 1;
 48     
 49     while (P < UPPERBOUND) {
 50         if( isPrime(P) ) break;
 51         P += 2;
 52     }
 53     
 54     return P;
 55 }
 56 int Hash( ElementType Key, int P )
 57 {
 58     return atoi(Key.ID+5) % P;
 59     
 60 }
 61 HashTable CreateTable( int TableSize )
 62 {
 63     HashTable H;
 64     int i;
 65     
 66     H = (HashTable)malloc( sizeof(struct TblNode) );
 67     /* 保证散列表最大长度是素数,具体见代码5.3 */
 68     H->TableSize = NextPrime(TableSize);
 69     
 70     /* 以下分配链表头结点数组 */
 71     H->Heads = (List)malloc(H->TableSize*sizeof(struct LNode));
 72     /* 初始化表头结点 */
 73     for( i=0; i<H->TableSize; i++ ) {
 74         H->Heads[i].Data.ID[0] = '\0';
 75         H->Heads[i].Next = NULL;
 76         
 77     }
 78     
 79     return H;
 80 }
 81 
 82 Position Find( HashTable H, ElementType Key )
 83 {
 84     Position P;
 85     Index Pos;
 86     
 87     Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */
 88     P = H->Heads[Pos].Next; /* 从该链表的第1个结点开始 */
 89     /* 当未到表尾,并且Key未找到时 */
 90     while( P && strcmp(P->Data.ID, Key.ID) )
 91         P = P->Next;
 92     
 93     return P; /* 此时P或者指向找到的结点,或者为NULL */
 94 }
 95 
 96 bool Insert( HashTable H, ElementType Key )
 97 {
 98     Position P, NewCell;
 99     Index Pos;
100     
101     P = Find( H, Key );
102     if ( !P ) { /* 关键词未找到,可以插入 */
103         NewCell = (Position)malloc(sizeof(struct LNode));
104         strcpy(NewCell->Data.ID, Key.ID);
105         strcpy(NewCell->Data.PW, Key.PW);
106         
107         Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */
108         /* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
109         NewCell->Next = H->Heads[Pos].Next;
110         H->Heads[Pos].Next = NewCell;
111         return true;
112     }
113     else { /* 关键词已存在 */
114         
115         return false;
116     }
117 }
118 
119 void DestroyTable( HashTable H )
120 {
121     int i;
122     Position P, Tmp;
123     
124     /* 释放每个链表的结点 */
125     for( i=0; i<H->TableSize; i++ ) {
126         P = H->Heads[i].Next;
127         while( P ) {
128             Tmp = P->Next;
129             free( P );
130             P = Tmp;
131         }
132     }
133     free( H->Heads ); /* 释放头结点数组 */
134     free( H );        /* 释放散列表结点 */
135 }
136 
137 /*void ScanAndOutput( HashTable H )
138 {
139     int i, MaxCnt, Pct;
140     ElementType MinPhone;
141     LNode * Ptr;
142     
143     Pct = MaxCnt = 0;
144     MinPhone[0] = 0;
145     
146     for (i = 0 ; i<H->TableSize; i++) {
147         Ptr = H->Heads[i].Next;
148         
149         while (Ptr) {
150             if (Ptr->Count > MaxCnt) {
151                 MaxCnt  = Ptr->Count;
152                 strcpy(MinPhone, Ptr->Data);
153                 Pct = 1;
154             }
155             else if (Ptr->Count == MaxCnt) {
156                 Pct++;
157                 if ( strcmp(Ptr->Data, MinPhone) < 0 ) {
158                     strcpy(MinPhone, Ptr->Data);
159                 }
160                 
161             }
162             
163             
164             Ptr = Ptr->Next;
165         }
166     }
167     
168     printf("%s %d", MinPhone, MaxCnt);
169     if (Pct > 1) {
170         printf(" %d", Pct);
171     }
172     
173     printf("\n");
174     
175     
176     
177 }
178  */
179 
180 
181 
182 
183 int main()
184 {
185     int N;
186     ElementType UserInfo;
187     char Instruction;
188     Position P;
189     HashTable H;
190     
191     scanf("%d", &N);
192     H = CreateTable( N );
193     
194     
195     for (int i=0; i<N; i++) {
196         getchar();
197         scanf("%c %s %s", &Instruction, UserInfo.ID, UserInfo.PW);
198         if (Instruction == 'N') {
199             if (Insert(H, UserInfo)) {
200                 printf("New: OK\n");
201             }
202             else printf("ERROR: Exist\n");
203         }
204         else {
205             P = Find(H, UserInfo);
206             if (P) {
207                 if ( strcmp(P->Data.PW, UserInfo.PW) == 0 ) {
208                     printf("Login: OK\n");
209                 }
210                 else printf("ERROR: Wrong PW\n");
211             }
212             else {
213                 printf("ERROR: Not Exist\n");
214             }
215         }
216         
217     }
218     
219     
220     
221     
222     
223     
224     return 0;
225 }

思路

用动态链接法散列QQ账号与密码

细节处理:

ElementType 设为 struct 型变量同时维护ID和PASSWORD;

命令符N对应的是插入操作,如果账号已存在,对应insertion函数的false返回值。

命令符L对应查找操作,如果账号(1)存在,核对密码;(2)不存在P(NULL)

 




上一篇:git命令行(3)之远程版本库


下一篇:Adobe Premiere Pro 2020安装教程【附安装包】