paizaの「レベルアップ問題集」の「1人の占い結果」で入力データによって出力結果が出ない。（マップとハッシュ）

前提・実現したいこと

どんな入力データを入力しても出力されるようにしたいです。
https://paiza.jp/works/mondai/prob60/fortune_telling_4

出力されない入力データ（２つ）
（１つ目）
CCC
3
AAA aaa111
BBB bbb222
CCC ccc333
5
aaa111 zzz
bbb222 yyy
ccc333 xxx
ddd444 www
eee555 vvv

（２つ目）
x
100
FTENQ 4l3AIz3Wz
kv5U hf9iuGifMQ1Y7
9f3yq WFCd
6e 4l3AIz3Wz
AGqZRzuAXDIuYUe EQKjgXYQ9
yvT18uHsaHrOyFDUm8 Un
ZMbluwvUXFoi8 zjsUsGxnFygfRBBMi
x rUW1ZgksZXq5pZey
・・・

発生している問題・エラーメッセージ

Main.c:103:29: warning: incompatible pointer to integer conversion passing 'void *' to parameter of type 'int' [-Wint-conversion]
    memset(hashtable->data, NULL, sizeof(User*) * size);
                            ^~~~
/usr/lib/llvm-10/lib/clang/10.0.0/include/stddef.h:89:16: note: expanded from macro 'NULL'
#  define NULL ((void*)0)
               ^~~~~~~~~~
/usr/include/string.h:61:37: note: passing argument to parameter '__c' here
extern void *memset (void *__s, int __c, size_t __n) __THROW __nonnull ((1));
                                    ^
1 warning generated.

該当のソースコード

C
1
2#include <stdio.h>
3#include <string.h>
4#include <stdlib.h>
5#include <stddef.h>
6
7typedef struct {
8    char user[100];
9    char blood[100];
10    char blood2[100];
11    char fortune[100];
12} User;
13
14//ハッシュ表
15typedef struct {
16    User **data;
17    unsigned int size;
18} HASHTABLE;
19
20unsigned int MakeHash2(char* str, unsigned int hashmax)
21{
22    unsigned int n, length, hash, weight;
23    
24    length = strlen(str);
25    for (n = weight = hash = 0; n < length; n++, weight++) {
26        if (weight > 7) {
27            weight = 0;
28        }
29        hash += (int)str[n] << (4 * weight);
30    }
31    return hash % hashmax;
32}
33
34unsigned int ReHash(HASHTABLE *hashtable, unsigned int firsthash)
35{
36    unsigned int hashval, k;
37    
38    for (k = 1; k <= hashtable->size / 2; k++) {
39        hashval = (firsthash + k * k) % hashtable -> size;
40        if (hashtable->data[hashval] == NULL) {
41            return hashval;
42        }
43    }
44    return -1;
45}
46
47void AddDataToMap(HASHTABLE *hashtable, User *newdata)
48{
49    unsigned int hashval;
50    
51    hashval = MakeHash2(newdata->user, hashtable->size);
52    
53    if (hashtable->data[hashval] != NULL) {
54        hashval = ReHash(hashtable, hashval);
55        if (hashval == -1) {
56            return;
57        }
58    }
59    hashtable->data[hashval] = newdata;
60}
61
62char *GetDataFromMap(HASHTABLE *hashtable, char *key)
63{
64    unsigned int hashval, k;
65    User *word;
66    
67    hashval = MakeHash2(key, hashtable->size);
68    
69    for (k = 0; k <= hashtable->size / 2; k++) {
70        word = hashtable->data[(hashval + k * k) % hashtable->size];
71        if (word != NULL) {
72            if (strcmp(key, word->user) == 0) {
73                return word->blood;
74            }
75        }
76    }
77    return NULL;
78}
79
80char *GetDataFromMap2(HASHTABLE *hashtable, char *key)
81{
82    unsigned int hashval, k;
83    User *word;
84    
85    hashval = MakeHash2(key, hashtable->size);
86    
87    for (k = 0; k <= hashtable->size / 2; k++) {
88        word = hashtable->data[(hashval + k * k) % hashtable->size];
89        if (word != NULL) {
90            if (strcmp(key, word->blood2) == 0) {
91                return word->fortune;
92            }
93        }
94    }
95    return NULL;
96}
97
98
99
100void IniHashTable(HASHTABLE *hashtable, unsigned int size)
101{
102    hashtable->data = (User**)malloc(sizeof(User*) * size);
103    
104    memset(hashtable->data, NULL, sizeof(User*) * size);
105    hashtable->size = size;
106}
107
108void CleanupHashTable(HASHTABLE *hashtable)
109{
110    free(hashtable->data);
111    hashtable->size = 0;
112}
113
114void PrintAllData(HASHTABLE *hashtable)
115{
116    unsigned int n;
117    for (n = 0; n < hashtable->size; n++) {
118        if (hashtable->data[n] != NULL) {
119            printf("%s\n", hashtable->data[n]->fortune);
120        }
121    }
122}
123
124int main(void)
125{
126    char *blood, *blood2;
127    HASHTABLE hashtable;
128    
129    IniHashTable(&hashtable, 503);
130   
131    char target[100];
132    scanf("%s", target);
133    
134    int n;
135    scanf("%d", &n);
136    
137    User u[n];
138    for (int i = 0; i < n; i++) {
139        scanf("%s%s", u[i].user, u[i].blood);
140    }
141    
142    int m;
143    scanf("%d", &m);
144    for (int i = 0; i < m; i++) {
145        scanf("%s%s", u[i].blood2, u[i].fortune);
146    }
147    
148    for (int i = 0; i < n; i++) {
149        AddDataToMap(&hashtable, &u[i]);
150    }
151    
152    blood = GetDataFromMap(&hashtable, target);
153    
154    blood2 = GetDataFromMap2(&hashtable, blood);
155    if (blood2 != NULL) {
156        printf("%s\n", blood2);
157    }
158    
159    CleanupHashTable(&hashtable);
160    
161    return 0;
162    
163}

C
1//エラーはなくなっていませんが100点を取れたコードです。
2#include <stdio.h>
3#include <string.h>
4#include <stdlib.h>
5#include <stddef.h>
6
7typedef struct {
8    char user[100];
9    char blood[100];
10} User;
11
12typedef struct {
13    char blood2[100];
14    char fortune[100];
15} Result;
16
17//ハッシュ表
18typedef struct {
19    User **data;
20    unsigned int size;
21} HASHTABLE;
22    
23typedef struct {
24    Result **data2;
25    unsigned int size2;
26} HASHTABLE2;
27
28unsigned int MakeHash2(char* str, unsigned int hashmax)
29{
30    unsigned int n, length, hash, weight;
31
32    length = strlen(str);
33    for (n = weight = hash = 0; n < length; n++, weight++) {
34        if (weight > 7) {
35            weight = 0;
36        }
37        hash += (int)str[n] << (4 * weight);
38    }
39    return hash % hashmax;
40}
41
42unsigned int ReHash(HASHTABLE *hashtable, unsigned int firsthash)
43{
44    unsigned int hashval, k;
45
46    for (k = 1; k <= hashtable->size / 2; k++) {
47        hashval = (firsthash + k * k) % hashtable -> size;
48        if (hashtable->data[hashval] == NULL) {
49            return hashval;
50        }
51    }
52    return -1;
53}
54
55unsigned int ReHash2(HASHTABLE2 *hashtable, unsigned int firsthash)
56{
57    unsigned int hashval, k;
58
59    for (k = 1; k <= hashtable->size2 / 2; k++) {
60        hashval = (firsthash + k * k) % hashtable -> size2;
61        if (hashtable->data2[hashval] == NULL) {
62            return hashval;
63        }
64    }
65    return -1;
66}
67
68void AddDataToMap(HASHTABLE *hashtable, User *newdata)
69{
70    unsigned int hashval;
71
72    hashval = MakeHash2(newdata->user, hashtable->size);
73
74    if (hashtable->data[hashval] != NULL) {
75        hashval = ReHash(hashtable, hashval);
76        if (hashval == -1) {
77            return;
78        }
79    }
80    hashtable->data[hashval] = newdata;
81}
82
83void AddDataToMap2(HASHTABLE2 *hashtable, Result *newdata)
84{
85    unsigned int hashval;
86
87    hashval = MakeHash2(newdata->blood2, hashtable->size2);
88
89    if (hashtable->data2[hashval] != NULL) {
90        hashval = ReHash(hashtable, hashval);
91        if (hashval == -1) {
92            return;
93        }
94    }
95    hashtable->data2[hashval] = newdata;
96}
97
98char *GetDataFromMap(HASHTABLE *hashtable, char *key)
99{
100    unsigned int hashval, k;
101    User *word;
102
103    hashval = MakeHash2(key, hashtable->size);
104
105    for (k = 0; k <= hashtable->size / 2; k++) {
106        word = hashtable->data[(hashval + k * k) % hashtable->size];
107        if (word != NULL) {
108            if (strcmp(key, word->user) == 0) {
109                return word->blood;
110            }
111        }
112    }
113    return NULL;
114}
115
116char *GetDataFromMap2(HASHTABLE2 *hashtable, char *key)
117{
118    unsigned int hashval, k;
119    Result *word;
120
121    hashval = MakeHash2(key, hashtable->size2);
122
123    for (k = 0; k <= hashtable->size2 / 2; k++) {
124        word = hashtable->data2[(hashval + k * k) % hashtable->size2];
125        if (word != NULL) {
126            if (strcmp(key, word->blood2) == 0) {
127                return word->fortune;
128            }
129        }
130    }
131    return NULL;
132}
133
134
135
136void IniHashTable(HASHTABLE *hashtable, unsigned int size)
137{
138    hashtable->data = (User**)malloc(sizeof(User*) * size);
139
140    memset(hashtable->data, NULL, sizeof(User*) * size);
141    hashtable->size = size;
142}
143
144void IniHashTable2(HASHTABLE2 *hashtable, unsigned int size)
145{
146    hashtable->data2 = (User**)malloc(sizeof(User*) * size);
147
148    memset(hashtable->data2, NULL, sizeof(User*) * size);
149    hashtable->size2 = size;
150}
151
152void CleanupHashTable(HASHTABLE *hashtable)
153{
154    free(hashtable->data);
155    hashtable->size = 0;
156}
157
158void CleanupHashTable2(HASHTABLE2 *hashtable)
159{
160    free(hashtable->data2);
161    hashtable->size2 = 0;
162}
163
164void PrintAllData(HASHTABLE2 *hashtable)
165{
166    unsigned int n;
167    for (n = 0; n < hashtable->size2; n++) {
168        if (hashtable->data2[n] != NULL) {
169            printf("%s\n", hashtable->data2[n]->fortune);
170        }
171    }
172}
173
174int main(void)
175{
176    char *blood, *blood2;
177    HASHTABLE hashtable;
178    HASHTABLE2 hashtable2;
179
180    IniHashTable(&hashtable, 503);
181    IniHashTable2(&hashtable2, 503);
182
183    char target[100];
184    scanf("%s", target);
185
186    int n;
187    scanf("%d", &n);
188
189    User u[n];
190    for (int i = 0; i < n; i++) {
191        scanf("%s%s", u[i].user, u[i].blood);
192    }
193
194    int m;
195    scanf("%d", &m);
196    
197    Result r[m];
198    for (int i = 0; i < m; i++) {
199        scanf("%s%s", r[i].blood2, r[i].fortune);
200    }
201
202    for (int i = 0; i < n; i++) {
203        AddDataToMap(&hashtable, &u[i]);
204        AddDataToMap2(&hashtable2, &r[i]);
205    }
206
207    blood = GetDataFromMap(&hashtable, target);
208
209    blood2 = GetDataFromMap2(&hashtable2, blood);
210    if (blood2 != NULL) {
211        printf("%s\n", blood2);
212    }
213
214    CleanupHashTable(&hashtable);
215    CleanupHashTable2(&hashtable2);
216
217    return 0;
218
219}

試したこと

MakeHash2関数とReHash関数で衝突が起こっているのかなと考え、特にMakeHash2関数の
hash += (int)str[n] << (4 * weight);の数字の部分を変えてみたりしましたが上手くいきませんでした。

補足情報（FW/ツールのバージョンなど）

paiza.ioを使用。
「プログラミングの宝箱　アルゴリズムとデータ構造」をもとに少しコードを加えて改造しました。加えた個所はGetDataFromMap2関数です。

maisumakun

2021/08/20 22:32

ワーニングが出ていても、コンパイル・実行までは進むかと思うのですが、その結果はどのようになっていますか？

whitehorse85921

2021/08/20 23:07

maisumakun様、ありがとうございます。出力されない入力データ2つを除けば、８割がた出力結果が正しく出ます。

kazuma-s

2021/08/21 00:25

マップを使うことは必須なんですか？ループ n回で CCC が出てきたら、ccc333 を憶えておく。ループm回で ccc333 が出てきたら、xxx を表示して終了。これだけのことではないのですか？

whitehorse85921

2021/08/21 01:22

kazuma-s様、ありがとうございます。 kazuma-s様が仰って下さったような実装方法が出来ず、苦し紛れでアルゴリズムの本を頼りに解いてしまいました。でも、できればマップを使った実装をしたいです。

jimbe

2021/08/21 03:20

ご提示されている入力データの一つ目と二つ目もそれぞれ ``` に入れたほうが良いように思います。(特に二つ目のランダムぽい英数字は、全体が見えても意味が無さそうですし。)

whitehorse85921

2021/08/21 04:12

jimbe様、ありがとうございます。二つ目の入力データは少し削ります。

kazuma-s

2021/08/21 22:08

「``` に入れたほうが良い」というのは、ソースコードが「```C」と「```」にはさまれて、四角い枠の中に少ない行数で表示され、見たければ「ｖ」をクリックすればよいようになっているのと同じことをしてください、という意味です。「・・・」で省略しろという意味ではありません。省略すると検証ができなくなります。

行動規範の内容に同意します

回答3件

解決できたようですが、そのコードを質問に追記してもらえないでしょうか？

質問のエラーメッセージは、
memset の第2引数は int なのに NULL というポインタを渡しているのは問題だ、
と言っています。どう解決しましたか？

さて、マップを使わなければ、これだけですよ。

C
1#include <stdio.h>   // scanf, puts
2#include <string.h>  // strcmp, strcpy
3
4#define N 21
5
6int main(void)
7{
8	char name[N], type[N], user[N], blood[N], fortune[N];
9	int n, m;
10
11	scanf("%s", name);
12
13	scanf("%d", &n);
14	for (int i = 0; i < n; i++) {
15		scanf("%s%s", user, blood);
16		if (strcmp(user, name) == 0) strcpy(type, blood);
17	}
18
19	scanf("%d", &m);
20	for (int i = 0; i < m; i++) {
21		scanf("%s%s", blood, fortune);
22		if (strcmp(blood, type) == 0) break;
23	}
24
25	puts(fortune);
26}

ハッシュを使ったマップなら、

C
1#include <stdio.h>   // scanf, puts
2#include <string.h>  // strcpy, strcmp
3#include <stdlib.h>  // malloc, free
4
5#define N 21
6
7typedef struct { char key[N], value[N]; } Pair;
8typedef struct { Pair **pair; int size; } Map;
9
10int hash(const char *s, int size)
11{
12	unsigned int val = 0;
13	for (int n = 0; *s; n = (n < 28) ? n + 4 : 0)
14		val += *s++ << n;
15	return val % size;
16}
17
18void map_init(Map *map, int size)
19{
20	map->pair = malloc(sizeof(Pair *) * size);
21	for (int i = 0; i < size; i++) map->pair[i] = NULL;
22	map->size = size;
23}
24
25int map_add(Map *map, const char *key, const char *value)
26{
27	int hashval = hash(key, map->size), i = hashval;
28	do {
29		if (map->pair[i] == NULL) {
30			Pair *p = malloc(sizeof(Pair));
31			strcpy(p->key, key);
32			strcpy(p->value, value);
33			map->pair[i] = p;
34			return 0;
35		}
36		if (++i == map->size) i = 0;
37	} while (i != hashval);
38	return 1;
39}
40
41const char *map_get(Map *map, const char *key)
42{
43	int hashval = hash(key, map->size), i = hashval;
44	do {
45		Pair *p = map->pair[i];
46		if (!p) return NULL;
47		if (strcmp(p->key, key) == 0) return p->value;
48		if (++i == map->size) i = 0;
49	} while (i != hashval);
50	return NULL;
51}
52
53void map_free(Map *map)
54{
55	for (int i = 0; i < map->size; i++)
56		if (map->pair[i]) free(map->pair[i]);
57	free(map->pair);
58}
59
60int main(void)
61{
62    char user[N];
63    scanf("%s", user);
64
65    int n;
66    scanf("%d", &n);
67	Map user_blood;
68	map_init(&user_blood, 503);
69    for (int i = 0; i < n; i++) {
70		char user[N], blood[N];
71        scanf("%s%s", user, blood);
72		map_add(&user_blood, user, blood);
73    }
74    int m;
75    scanf("%d", &m);
76	Map blood_fortune;
77	map_init(&blood_fortune, 503);
78    for (int i = 0; i < m; i++) {
79		char blood[N], fortune[N];
80        scanf("%s%s", blood, fortune);
81		map_add(&blood_fortune, blood, fortune);
82    }
83    const char *blood = map_get(&user_blood, user);
84	const char *fortune = map_get(&blood_fortune, blood);
85	puts(fortune);
86
87	map_free(&user_blood);
88	map_free(&blood_fortune);
89}

理解できますか？

投稿2021/08/21 06:12

kazuma-s

総合スコア8224

whitehorse85921

2021/08/21 17:49

kazuma-s様、ありがとうございます。「そのコードを質問に追記してもらえないでしょうか？」の「そのコード」とはどのコードかお教えして頂けないでしょうか？すみません。あと、マップを使わないコードとハッシュを使ったマップをご提示してくださりありがとうございました。大変勉強になります。「ループ n回で CCC が出てきたら、ccc333 を憶えておく。ループm回で ccc333 が出てきたら、xxx を表示して終了。」の「ccc333 を憶えておく」はstrcpyを使うと覚えておけるのですね。私は「type = blood」のようにしてしまったので上手くいきませんでした。ハッシュを使ったマップのほうは、関数の名前からどんなことがなされているか推測できました。私のような者に丁寧に教えてくださり誠にありがとうございます。

kazuma-s

2021/08/21 21:52

「100点を取らせていただいた私の改造したコード」です。エラーメッセージが出なくなったコードです。

whitehorse85921

2021/08/22 09:25

kazuma-s様、エラーメッセージは出ますが100点を取れたコードを載せました。よろしくお願いいたします。

jimbe

2021/08/22 11:22 編集

paiza は warning は点数に影響しないんですかね ^^;

kazuma-s

2021/08/22 12:42

ccc333 xxx　と　ddd444 www　を入れ替えた次のデータが入力だとだめです。 --- CCC 3 AAA aaa111 BBB bbb222 CCC ccc333 5 aaa111 zzz bbb222 yyy ddd444 www ccc333 xxx eee555 vvv --- これはｎ＜ m の例ですが、逆に n > m のとき、要素数が m個である Result の要素を n 回 AddDataToMap2 していいわけがありません。

whitehorse85921

2021/08/22 13:33

jimbe様、ありがとうございます。 warningは点数に影響しませんでした。。。

whitehorse85921

2021/08/22 13:34

kazuma-s様、ありがとうございます。お二方がご提示してくださったコードをもとになぜダメだったか検証したいと思います。

行動規範の内容に同意します

ベストアンサー

100点取れたということで、おめでとうございます。
で、ハッシュとマップが混ざっているようなので、ハッシュを使わないでマップ仕様として以下を作ってみました。

c
1/**
2 * https://paiza.jp/works/mondai/prob60/fortune_telling_4
3 *
4 * すべてのテストケースにおいて、以下の条件をみたします。
5
6・Uは、半角英数字からなる1から20文字までの文字列
7・1 ≦ n ≦100
8・1 ≦ m ≦100
9・(ユーザー_i)は、半角英数字からなる1から20文字までの文字列
10・(血液型_j)は、半角英数字からなる1から20文字までの文字列
11・(血液型_jの占い結果)は、半角英数字からなる1から20文字までの文字列
12・(ユーザー_iの血液型)と等しい、(血液型_j)が必ず存在
13・i ≠kのとき、(ユーザー_i)と(ユーザー_k)は異なる文字列
14・j ≠kのとき、(血液型_j)と(血液型_k)は異なる文字列
15*/
16
17#include <stdio.h>
18#include <string.h>
19#include <stdlib.h>
20//#include <stddef.h>
21
22#ifndef NULL
23#define NULL ((void*)0)
24#endif
25
26//扱う文字列の最大長(バイト数)
27#define STRLEN_MAX 20
28//組み合わせデータ(Map)の最大件数
29#define ENTRY_MAX 100
30
31//マップエントリ
32typedef struct {
33  char key[STRLEN_MAX+1];
34  char value[STRLEN_MAX+1];
35} MAP_ENTRY;
36
37//マップ
38typedef struct {
39  MAP_ENTRY **entries;
40  int size;
41} MAP;
42
43//初期化
44void initialize(MAP *map) {
45  int size = ENTRY_MAX;
46  map->entries = (MAP_ENTRY **) malloc(sizeof(MAP_ENTRY*) * size);
47  map->size = size;
48  memset(map->entries, 0, sizeof(MAP_ENTRY*) * size);
49}
50
51//クリア
52void cleanup(MAP *map) {
53  for(int i=0; i<map->size; i++) {
54    if(map->entries[i] != NULL) {
55      free(map->entries[i]);
56    }
57  }
58  free(map->entries);
59  map->entries = NULL;
60  map->size = 0;
61}
62
63// return -1=入れられなかった, 0以上=新しく入れたor置き換えた
64int put(MAP *map, char *key, char *value) {
65  for(int i=0; i<map->size; i++) {
66    if(map->entries[i] == NULL) {
67      MAP_ENTRY *entry = (MAP_ENTRY*)malloc(sizeof(MAP_ENTRY));
68      strcpy(entry->key, key);
69      strcpy(entry->value, value);
70      map->entries[i] = entry;
71      return i;
72    }
73    if(!strcmp(map->entries[i]->key, key)) {
74      strcpy(map->entries[i]->value, value);
75      return i;
76    }
77  }
78  return -1; //入れられなかった
79}
80
81//return NULL以外=keyに対応する値, NULL=無かった
82char* get(MAP *map, char *key) {
83  for(int i=0; i<map->size; i++) {
84    if(map->entries[i] != NULL) {
85      if(!strcmp(map->entries[i]->key, key)) {
86        return map->entries[i]->value;
87      }
88    }
89  }
90  return NULL; //無かった
91}
92
93//デバッグ用？
94void printAll(MAP *map) {
95  for(int i=0; i<map->size; i++) {
96    if(map->entries[i] != NULL) {
97      printf("[%s,%s]\n", map->entries[i]->key, map->entries[i]->value);
98    }
99  }
100}
101
102//(paizaっぽくしてみた)
103void inputTarget(char *target) {
104  char buf[1000];
105
106  fgets(buf, sizeof(buf), stdin);
107  sscanf(buf, "%s\n", target);
108}
109
110//https://paiza.jp/guide/samplecode.html より
111void inputMap(MAP *map) {
112  int n;
113  char buf[1000];
114  char key[STRLEN_MAX+1], value[STRLEN_MAX+1];
115
116  fgets(buf, sizeof(buf), stdin);
117  sscanf(buf, "%d\n", &n);
118  for(int i=0; i<n; i++) {
119    fgets(buf, sizeof(buf), stdin);
120    sscanf(buf, "%s %s\n", key, value);
121    put(map, key, value);
122  }
123}
124
125int main(void) {
126  char keyA[STRLEN_MAX+1];
127  MAP mapA, mapB;
128
129  initialize(&mapA);
130  initialize(&mapB);
131
132  inputTarget(keyA);
133  inputMap(&mapA);
134  inputMap(&mapB);
135
136  char *valueA_keyB = get(&mapA, keyA);
137  char *valueB = get(&mapB, valueA_keyB);
138  if(valueB != NULL) {
139    printf("%s\n", valueB);
140  }
141
142  cleanup(&mapA);
143  cleanup(&mapB);
144
145  return 0;
146}
147

plain
1Kyoko
25
3Kyoko B
4Rio O
5Tsubame AB
6KurodaSensei A
7NekoSensei A
84
9A red
10B green
11O blue
12AB yellow
13green

plain
1CCC
23
3AAA aaa111
4BBB bbb222
5CCC ccc333
65
7aaa111 zzz
8bbb222 yyy
9ccc333 xxx
10ddd444 www
11eee555 vvv
12xxx

煽てられて調子に乗って、マップのハッシュ化をしてみます（＾＾
以下のコードを追加しまして

c
1//calcHash() 用グローバル変数
2int _hashfirst = 0;
3int _hashcount = 0;
4
5//strtok 同様、key を指定すると最初の値を返し、以降 key=NULLとすると次の値を返す
6int calcHash(char *key, int hashmax) {
7  if(key != NULL) {
8    long hash = 0;
9    for(int i=0; i<strlen(key); i++) {
10      hash += (int)key[i] << ((i%8)*4);
11    }
12    _hashfirst = (int)(hash % hashmax);
13    _hashcount = 0;
14    return _hashfirst;
15  }
16  //ReHash
17  if(++_hashcount > hashmax/2) return -1;
18  return (_hashfirst + _hashcount * _hashcount) % hashmax;
19}

put()/get() にある for ループ

c
1for(int i=0; i<map->size; i++) {

を書き換えます。

c
1for(int i=calcHash(key,map->size); i>=0; i=calcHash(NULL,map->size)) {

これでオリジナル通りのハッシュ仕様のマップ…となっていますかね。

投稿2021/08/21 04:51

編集2021/08/21 07:38

jimbe

総合スコア13209

whitehorse85921

2021/08/21 05:46

jimge様！ありがとうございます！マップ仕様のコードまでご提示していただき感謝です！しかもお人柄も優しく菩薩のようです！

whitehorse85921

2021/08/21 18:23

jimbe様、ありがとうございます。 100点を取らせていただいた私の改造したコードは内容を少しだけ改造したほぼ同じ内容の関数が重複してしまっているので、jimbe様のより洗練されたコードを拝見させていただけるのは本当に有難いです！私もjimbe様のように自力でアルゴリズム組めるようになれるまで頑張ります！

jimbe

2021/08/22 11:32

マップに関するコードが2倍(2つ分)になるだろうことは、episteme さんの回答の流れから想像していました。 paiza としては動作結果が合っていれば問題無いということでしょうけれど、エンジニアからすると(コードが約2倍なので点数は1/2として) 50 点とかになってしまうかもしれません。出来ればそこから「マップに関するコードを一つに纏めましょう」な方向に進むと良いのですが、自動で結果を判定するのは難しいでしょうね…。

whitehorse85921

2021/08/22 13:37

jimbe様、ありがとうございます。プログラミング難しいです（泣）でもプロのエンジニアの方に見て頂けることじたい光栄なことなので、お二方がご提示してくださったコードをもとに勉強しなおします。

行動規範の内容に同意します

1:
「ユーザー」と「血液型」
および
「血液型」と「占い結果」
のふたつのハッシュ表を用意するのが素直かと。

C
1    User u[n];
2    for (int i = 0; i < n; i++) {
3        scanf("%s%s", u[i].user, u[i].blood);
4    }
5
6    int m;
7    scanf("%d", &m);
8    for (int i = 0; i < m; i++) {
9        scanf("%s%s", u[i].blood2, u[i].fortune);
10    }