实现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）