回答編集履歴
2
ハッシュ化
test
CHANGED
|
@@ -357,3 +357,73 @@
|
|
|
357
357
|
xxx
|
|
358
358
|
|
|
359
359
|
```
|
|
360
|
+
|
|
361
|
+
|
|
362
|
+
|
|
363
|
+
----
|
|
364
|
+
|
|
365
|
+
|
|
366
|
+
|
|
367
|
+
煽てられて調子に乗って、マップのハッシュ化をしてみます（＾＾
|
|
368
|
+
|
|
369
|
+
以下のコードを追加しまして
|
|
370
|
+
|
|
371
|
+
```c
|
|
372
|
+
|
|
373
|
+
//calcHash() 用グローバル変数
|
|
374
|
+
|
|
375
|
+
int _hashfirst = 0;
|
|
376
|
+
|
|
377
|
+
int _hashcount = 0;
|
|
378
|
+
|
|
379
|
+
|
|
380
|
+
|
|
381
|
+
//strtok 同様、key を指定すると最初の値を返し、以降 key=NULLとすると次の値を返す
|
|
382
|
+
|
|
383
|
+
int calcHash(char *key, int hashmax) {
|
|
384
|
+
|
|
385
|
+
if(key != NULL) {
|
|
386
|
+
|
|
387
|
+
long hash = 0;
|
|
388
|
+
|
|
389
|
+
for(int i=0; i<strlen(key); i++) {
|
|
390
|
+
|
|
391
|
+
hash += (int)key[i] << ((i%8)*4);
|
|
392
|
+
|
|
393
|
+
}
|
|
394
|
+
|
|
395
|
+
_hashfirst = (int)(hash % hashmax);
|
|
396
|
+
|
|
397
|
+
_hashcount = 0;
|
|
398
|
+
|
|
399
|
+
return _hashfirst;
|
|
400
|
+
|
|
401
|
+
}
|
|
402
|
+
|
|
403
|
+
//ReHash
|
|
404
|
+
|
|
405
|
+
if(++_hashcount > hashmax/2) return -1;
|
|
406
|
+
|
|
407
|
+
return (_hashfirst + _hashcount * _hashcount) % hashmax;
|
|
408
|
+
|
|
409
|
+
}
|
|
410
|
+
|
|
411
|
+
```
|
|
412
|
+
|
|
413
|
+
put()/get() にある for ループ
|
|
414
|
+
|
|
415
|
+
```c
|
|
416
|
+
|
|
417
|
+
for(int i=0; i<map->size; i++) {
|
|
418
|
+
|
|
419
|
+
```
|
|
420
|
+
|
|
421
|
+
を書き換えます。
|
|
422
|
+
|
|
423
|
+
```c
|
|
424
|
+
|
|
425
|
+
for(int i=calcHash(key,map->size); i>=0; i=calcHash(NULL,map->size)) {
|
|
426
|
+
|
|
427
|
+
```
|
|
428
|
+
|
|
429
|
+
これでオリジナル通りのハッシュ仕様のマップ…となっていますかね。
|
1
条件に合わせて文字配列長さ等最適化
test
CHANGED
|
@@ -4,6 +4,38 @@
|
|
|
4
4
|
|
|
5
5
|
```c
|
|
6
6
|
|
|
7
|
+
/**
|
|
8
|
+
|
|
9
|
+
* https://paiza.jp/works/mondai/prob60/fortune_telling_4
|
|
10
|
+
|
|
11
|
+
*
|
|
12
|
+
|
|
13
|
+
* すべてのテストケースにおいて、以下の条件をみたします。
|
|
14
|
+
|
|
15
|
+
|
|
16
|
+
|
|
17
|
+
・Uは、半角英数字からなる1から20文字までの文字列
|
|
18
|
+
|
|
19
|
+
・1 ≦ n ≦100
|
|
20
|
+
|
|
21
|
+
・1 ≦ m ≦100
|
|
22
|
+
|
|
23
|
+
・(ユーザー_i)は、半角英数字からなる1から20文字までの文字列
|
|
24
|
+
|
|
25
|
+
・(血液型_j)は、半角英数字からなる1から20文字までの文字列
|
|
26
|
+
|
|
27
|
+
・(血液型_jの占い結果)は、半角英数字からなる1から20文字までの文字列
|
|
28
|
+
|
|
29
|
+
・(ユーザー_iの血液型)と等しい、(血液型_j)が必ず存在
|
|
30
|
+
|
|
31
|
+
・i ≠kのとき、(ユーザー_i)と(ユーザー_k)は異なる文字列
|
|
32
|
+
|
|
33
|
+
・j ≠kのとき、(血液型_j)と(血液型_k)は異なる文字列
|
|
34
|
+
|
|
35
|
+
*/
|
|
36
|
+
|
|
37
|
+
|
|
38
|
+
|
|
7
39
|
#include <stdio.h>
|
|
8
40
|
|
|
9
41
|
#include <string.h>
|
|
@@ -22,13 +54,23 @@
|
|
|
22
54
|
|
|
23
55
|
|
|
24
56
|
|
|
57
|
+
//扱う文字列の最大長(バイト数)
|
|
58
|
+
|
|
59
|
+
#define STRLEN_MAX 20
|
|
60
|
+
|
|
61
|
+
//組み合わせデータ(Map)の最大件数
|
|
62
|
+
|
|
63
|
+
#define ENTRY_MAX 100
|
|
64
|
+
|
|
65
|
+
|
|
66
|
+
|
|
25
67
|
//マップエントリ
|
|
26
68
|
|
|
27
69
|
typedef struct {
|
|
28
70
|
|
|
29
|
-
char key[1
|
|
71
|
+
char key[STRLEN_MAX+1];
|
|
30
|
-
|
|
72
|
+
|
|
31
|
-
char value[1
|
|
73
|
+
char value[STRLEN_MAX+1];
|
|
32
74
|
|
|
33
75
|
} MAP_ENTRY;
|
|
34
76
|
|
|
@@ -50,7 +92,7 @@
|
|
|
50
92
|
|
|
51
93
|
void initialize(MAP *map) {
|
|
52
94
|
|
|
53
|
-
int size =
|
|
95
|
+
int size = ENTRY_MAX;
|
|
54
96
|
|
|
55
97
|
map->entries = (MAP_ENTRY **) malloc(sizeof(MAP_ENTRY*) * size);
|
|
56
98
|
|
|
@@ -188,7 +230,7 @@
|
|
|
188
230
|
|
|
189
231
|
char buf[1000];
|
|
190
232
|
|
|
191
|
-
char key[1
|
|
233
|
+
char key[STRLEN_MAX+1], value[STRLEN_MAX+1];
|
|
192
234
|
|
|
193
235
|
|
|
194
236
|
|
|
@@ -212,7 +254,7 @@
|
|
|
212
254
|
|
|
213
255
|
int main(void) {
|
|
214
256
|
|
|
215
|
-
char keyA[1
|
|
257
|
+
char keyA[STRLEN_MAX+1];
|
|
216
258
|
|
|
217
259
|
MAP mapA, mapB;
|
|
218
260
|
|
|
@@ -254,6 +296,8 @@
|
|
|
254
296
|
|
|
255
297
|
}
|
|
256
298
|
|
|
299
|
+
|
|
300
|
+
|
|
257
301
|
```
|
|
258
302
|
|
|
259
303
|
```plain
|