teratail
回答率
85.30%
teratail header banner
teratail header banner
質問するログイン新規登録
トップに関する質問ハッシュ(チェイン法について)

編集履歴

質問編集履歴

3

投稿の疑似削除

2020/07/08 06:52

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -1,159 +1,1 @@
1
- チェイン法について質問です。二つ以上のハッシュ値が一致してしまった場合、それを避けるためにリスト構造を用いて、最初はリストの末尾にNULLを生成します。その後、新たなハッシュ値が出た場合にNULLの前に新たなリストを作り、衝突を避けるようにしたいです。
2
- 今find関数を作り、今までのリストを結合した中から、同じ文字列のawayとhomeが見つかるまでループさせ、見つかったら、今現在生成されているリストを結合させないようにしたいです。つまり、違うaway homeのリストをそれぞれのハッシュテーブルに入れるようにしたいです
3
- 例えばハッシュ値が3の場合に、０番目に清水エスパルスvsガンバ大阪のリスト、一番目には鹿島アントラーズvs柏レイソルのリストはそれぞれ違うhomeとawayで且つ同じハッシュ値なので結合できます。しかし１００番目に同じ清水エスパルスvsガンバ大阪の場合は今までのリストに同じ対戦相手があるので結合できなくなります。つまり衝突にカウントを加えないようになっている状態です。
4
- ```ここに言語を入力
5
- #define _CRT_SECURE_NO_WARNINGS
6
- #define HASHSIZE 17
7
- #include <stdio.h>
8
- #include <stdlib.h>
9
- #include<string.h>
10
-
11
- struct match* hashtable[HASHSIZE];
12
- int HASH[HASHSIZE];
13
- struct match_score {
14
- int year;
15
- int month;
16
- int day;
17
- int home_score;
18
- int away_score;
19
- struct match_score* next;
20
- };
21
- struct match {
22
- char *home;
23
- char *away;
24
-
25
- struct match *next;
26
- struct match_score* r;
27
- };
28
-
29
- int hash(char *home,char *away) {
30
- int hashval = 0;//ハッシュ値の値を初期化
31
-
32
- while (*home != '\0'|| *away!='\0') {//homeとawayの値がどちらも\0になるまでループする
33
-
34
- hashval += *home+*away;//アスキーコードの和を足す
35
- if(*home!= '\0')//どちらかが\0になっても全てムラなく足せるようにする
36
- home++;
37
- if (*away != '\0')
38
- away++;
39
-
40
- }
41
- return hashval % HASHSIZE;//ハッシュ値を返す。
42
-
43
-
44
- }
45
-
46
- struct match* find(char* home, char* away) {
47
- struct match* p;//match構造体のポインタ変数
48
- int hashval;
49
- hashval = hash(home, away);//ハッシュ値を返す。
50
- p = hashtable[hashval];//全体のリスト結合をpに代入させる
51
- while (p != NULL) {//pがNULLになるまでループさせる
52
- if ((strcmp(home, p->home) == 0) && (strcmp(away, p->away) == 0)) {//今のリストが探索して今までのリストのhome,awayが同じリストがあるならば今ののリストは結合させないようにしたい。
53
- printf("%s %s\n", p->home, p->away);//同じアスキーコードがあるならばその値を返す。
54
- return p;
55
-
56
- }
57
- p = p->next;//同じ、homeとawayが見つかるまで次のリストに移動させる。
58
-
59
-
60
- }
61
- }
62
-
63
-
64
-
65
-
66
-
67
- void ListKeyWord(struct match *p ,char * home,char *away,int Hash)
68
- {
69
-
70
- struct match* ptr=hashtable[Hash];
71
-
72
-
73
- // printf("home:%s away:%s ハッシュ値:%d:\n", (*p).home, (*p).away,hash((*p).home,(*p).away));
74
- // printf("home:%s away:%s ハッシュ値:%d:\n", (*ptr).home, (*ptr).away, hash((*ptr).home, (*ptr).away));
75
- }
76
-
77
-
78
-
79
-
80
- void add(int year, int month, int day, char* home_team, int home_score, int away_score, char* away_team) {
81
- int hashval;
82
- struct match* ptr;
83
- int i;
84
- hashval = hash(home_team, away_team);//homeとawayのアスキーコードの和とそれを割る素数からハッシュ値を返す。
85
-
86
- ptr = (struct match*)malloc(sizeof(struct match));//ptrの領域を確保する
87
- ptr->home = (char*)malloc(strlen(home_team) + 1);//homeの文字列+\0の長さを求める。
88
- strcpy(ptr->home, home_team);//文字列のコピー
89
- ptr->away = (char*)malloc(strlen(away_team) + 1);
90
- strcpy(ptr->away, away_team);
91
-
92
-
93
- if (hashtable[hashval] == NULL){//ハッシュ値が未登録ならば
94
- hashtable[hashval] = ptr;//最初にアドレスを登録
95
- ptr->next = NULL;//次の指すアドレスをNULLにする。
96
-
97
- }
98
-
99
- else {//ハッシュ値の中の値がNULLでなければNULLの後ろに新たなリストを生成する。
100
- struct match* ptr2;//次のリストを指定
101
- struct match* ptr3;//find関数のアドレスを返す。
102
-
103
- ptr2 = hashtable[hashval];//今現在のリストをptr2に代入する
104
- ptr3 = find(home_team, away_team);//find関数で探索をし、もし同じhomeとawayの値が見つかったらアドレスを返す
105
- while (ptr2->next != NULL ) {
106
- if ((strcmp(ptr2->home, ptr3->home) != 0) && (strcmp(ptr2->home, ptr3->home) != 0)) {//find関数で見つかったhomeとawayが今のptr2が同じならば、
107
- //同じ名前のhomeとawayはリスト結合をしないようにしたい。
1
+ ハッシュ法を用いる質問をしましたが都合により削除することになりました。コードは載せないようにしたいと思います。
108
- ptr->next = NULL;
109
- break;
110
- }
111
- else {
112
- ptr2 = ptr2->next;
113
- HASH[hashval]++;//同じハッシュ値がぶつかった回数だけ足していきたい。ただし同じhome,awayのリストは足さないようにしたい。
114
- }
115
-
116
- }
117
- ptr2->next = ptr;//違うチーム同士をリスト結合でつないでいきたい
118
- ptr->next = NULL;//リスとの末尾にNULLを返す。リストが終わるまで、何度もNULLの値が入れ替わる。
119
-
120
-
121
-
122
- }
123
-
124
- ListKeyWord(ptr,home_team, away_team, hashval);//ハッシュ値がどうなっているか確かめる
125
-
126
-
127
-
128
-
129
- }
130
-
131
- int main() {
132
- char home_team[256], away_team[256];
133
- int home_score, away_score;
134
- int year, month, day, i, f;
135
- struct match* ptr;
136
- ptr = NULL;
137
- const char* filename = "jleague.txt";//Jリーグの過去の対戦結果のファイル
138
- FILE* fp;
139
-
140
- for (i = 0; i < HASHSIZE; i++) {
141
- hashtable[i] = NULL;//初期値をNULLにさせる。
142
- }
143
-
144
- fp = fopen(filename, "r");
145
- while ((f = fscanf(fp, "%d %d %d %s %d %d %s", &year, &month, &day, home_team, &home_score, &away_score, away_team)) != EOF) {
146
- add(year, month, day, home_team, home_score, away_score, away_team);
147
-
148
-
149
- }
150
- for(i=0;i<HASHSIZE;i++)
151
- printf("%d\n", HASH[i]); //ハッシュ値が偏りなくなっているか確かめる
152
-
153
-
154
-
155
- }
156
-
157
-
158
-
159
- ```

2

また、何度も編集したいから

2020/07/08 06:52

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -1,6 +1,6 @@
1
1
  チェイン法について質問です。二つ以上のハッシュ値が一致してしまった場合、それを避けるためにリスト構造を用いて、最初はリストの末尾にNULLを生成します。その後、新たなハッシュ値が出た場合にNULLの前に新たなリストを作り、衝突を避けるようにしたいです。
2
- そのためにadd関数内にあるelseの後の条件whileの内容を満たすようにするにはどうすればよいのでしょうか。また、同じチームのアスキーコードが同じなのにハッシュ値が異なる値が表示される場合があるのはどうしてでしょうか。
3
- 例えばhome:Sanfrecce_Hiroshima_F.C away:Urawa_Red_Diamondsとした場合にハッシュ値が一回目が１１二回目が１６と異なる値が表示されることがあります。何度もコンパイルした結果そうなります。ご協力お願いします。
2
+ 今find関数を作り、今までのリストを結合した中から、同じ文字列のawayとhomeが見つかるまでループさせ、見つかったら、今現在生成されているリストを結合させないようにしたいです。つまり、違うaway homeのリストをそれぞれのハッシュテーブルに入れるようにしたいです
3
+ 例えばハッシュ値が3の場合に、０番目に清水エスパルスvsガンバ大阪のリスト、一番目には鹿島アントラーズvs柏レイソルのリストはそれぞれ違うhomeとawayで且つ同じハッシュ値なので結合できます。しかし１００番目に同じ清水エスパルスvsガンバ大阪の場合は今までのリストに同じ対戦相手があるので結合できなくなります。つまり衝突にカウントを加えないようになっている状態です。
4
4
  ```ここに言語を入力
5
5
  #define _CRT_SECURE_NO_WARNINGS
6
6
  #define HASHSIZE 17
@@ -9,6 +9,7 @@
9
9
  #include<string.h>
10
10
 
11
11
  struct match* hashtable[HASHSIZE];
12
+ int HASH[HASHSIZE];
12
13
  struct match_score {
13
14
  int year;
14
15
  int month;
@@ -25,63 +26,106 @@
25
26
  struct match_score* r;
26
27
  };
27
28
 
28
-
29
29
  int hash(char *home,char *away) {
30
- int hashval = 0;
30
+ int hashval = 0;//ハッシュ値の値を初期化
31
31
 
32
- while (*home != '\0'|| *away!='\0') {
32
+ while (*home != '\0'|| *away!='\0') {//homeとawayの値がどちらも\0になるまでループする
33
33
 
34
- hashval += *home+*away;
34
+ hashval += *home+*away;//アスキーコードの和を足す
35
- if(*home!= '\0')
35
+ if(*home!= '\0')//どちらかが\0になっても全てムラなく足せるようにする
36
36
  home++;
37
37
  if (*away != '\0')
38
38
  away++;
39
39
 
40
40
  }
41
- return hashval % HASHSIZE;
41
+ return hashval % HASHSIZE;//ハッシュ値を返す。
42
42
 
43
43
 
44
44
  }
45
+
46
+ struct match* find(char* home, char* away) {
47
+ struct match* p;//match構造体のポインタ変数
48
+ int hashval;
49
+ hashval = hash(home, away);//ハッシュ値を返す。
50
+ p = hashtable[hashval];//全体のリスト結合をpに代入させる
51
+ while (p != NULL) {//pがNULLになるまでループさせる
52
+ if ((strcmp(home, p->home) == 0) && (strcmp(away, p->away) == 0)) {//今のリストが探索して今までのリストのhome,awayが同じリストがあるならば今ののリストは結合させないようにしたい。
53
+ printf("%s %s\n", p->home, p->away);//同じアスキーコードがあるならばその値を返す。
54
+ return p;
55
+
56
+ }
57
+ p = p->next;//同じ、homeとawayが見つかるまで次のリストに移動させる。
58
+
59
+
60
+ }
61
+ }
62
+
63
+
64
+
65
+
66
+
45
- void ListKeyWord(char * home,char *away,int Hash)
67
+ void ListKeyWord(struct match *p ,char * home,char *away,int Hash)
46
68
  {
47
69
 
48
- struct match* p=hashtable[Hash];
70
+ struct match* ptr=hashtable[Hash];
49
71
 
50
72
 
51
- printf("home:%s away:%s ハッシュ値:%d:\n", (*p).home, (*p).away,hash((*p).home,away));
73
+ // printf("home:%s away:%s ハッシュ値:%d:\n", (*p).home, (*p).away,hash((*p).home,(*p).away));
74
+ // printf("home:%s away:%s ハッシュ値:%d:\n", (*ptr).home, (*ptr).away, hash((*ptr).home, (*ptr).away));
52
75
  }
53
76
 
77
+
78
+
79
+
54
80
  void add(int year, int month, int day, char* home_team, int home_score, int away_score, char* away_team) {
55
81
  int hashval;
56
82
  struct match* ptr;
57
-
83
+ int i;
58
- hashval = hash(home_team, away_team);
84
+ hashval = hash(home_team, away_team);//homeとawayのアスキーコードの和とそれを割る素数からハッシュ値を返す。
59
-
85
+
60
- ptr = (struct match*)malloc(sizeof(struct match));
86
+ ptr = (struct match*)malloc(sizeof(struct match));//ptrの領域を確保する
61
- ptr->home = (char*)malloc(strlen(home_team) + 1);
87
+ ptr->home = (char*)malloc(strlen(home_team) + 1);//homeの文字列+\0の長さを求める。
62
- strcpy(ptr->home, home_team);
88
+ strcpy(ptr->home, home_team);//文字列のコピー
63
89
  ptr->away = (char*)malloc(strlen(away_team) + 1);
64
90
  strcpy(ptr->away, away_team);
65
-
66
91
 
92
+
67
- if (hashtable[hashval] == NULL){
93
+ if (hashtable[hashval] == NULL){//ハッシュ値が未登録ならば
68
- hashtable[hashval] = ptr;
94
+ hashtable[hashval] = ptr;//最初にアドレスを登録
69
- ptr->next = NULL;
95
+ ptr->next = NULL;//次の指すアドレスをNULLにする。
70
96
 
71
- }
97
+ }
98
+
99
+ else {//ハッシュ値の中の値がNULLでなければNULLの後ろに新たなリストを生成する。
100
+ struct match* ptr2;//次のリストを指定
101
+ struct match* ptr3;//find関数のアドレスを返す。
102
+
103
+ ptr2 = hashtable[hashval];//今現在のリストをptr2に代入する
104
+ ptr3 = find(home_team, away_team);//find関数で探索をし、もし同じhomeとawayの値が見つかったらアドレスを返す
105
+ while (ptr2->next != NULL ) {
106
+ if ((strcmp(ptr2->home, ptr3->home) != 0) && (strcmp(ptr2->home, ptr3->home) != 0)) {//find関数で見つかったhomeとawayが今のptr2が同じならば、
107
+ //同じ名前のhomeとawayはリスト結合をしないようにしたい。
108
+ ptr->next = NULL;
109
+ break;
110
+ }
72
- else {
111
+ else {
73
- struct match* ptr2 = hashtable[hashval];
74
-
75
- while (ptr2->next!= NULL ) {
76
- ptr2 = ptr2->next;
112
+ ptr2 = ptr2->next;
113
+ HASH[hashval]++;//同じハッシュ値がぶつかった回数だけ足していきたい。ただし同じhome,awayのリストは足さないようにしたい。
114
+ }
115
+
116
+ }
77
- ptr2->next = ptr;
117
+ ptr2->next = ptr;//違うチーム同士をリスト結合でつないでいきたい
78
- ptr->next = NULL;
118
+ ptr->next = NULL;//リスとの末尾にNULLを返す。リストが終わるまで、何度もNULLの値が入れ替わる。
119
+
120
+
121
+
79
122
  }
80
-
81
- }
82
123
 
83
- ListKeyWord(home_team,away_team,hashval);
124
+ ListKeyWord(ptr,home_team, away_team, hashval);//ハッシュ値がどうなっているか確かめる
125
+
84
126
 
127
+
128
+
85
129
  }
86
130
 
87
131
  int main() {
@@ -90,22 +134,26 @@
90
134
  int year, month, day, i, f;
91
135
  struct match* ptr;
92
136
  ptr = NULL;
93
- const char* filename = "jleague.txt";
137
+ const char* filename = "jleague.txt";//Jリーグの過去の対戦結果のファイル
94
138
  FILE* fp;
95
-
139
+
96
140
  for (i = 0; i < HASHSIZE; i++) {
97
- hashtable[i] = NULL;
141
+ hashtable[i] = NULL;//初期値をNULLにさせる。
98
142
  }
99
-
143
+
100
144
  fp = fopen(filename, "r");
101
- while ((f = fscanf(fp, "%d %d %d %s %d %d %s", year, month, day, home_team, home_score, away_score, away_team)) != EOF) {
145
+ while ((f = fscanf(fp, "%d %d %d %s %d %d %s", &year, &month, &day, home_team, &home_score, &away_score, away_team)) != EOF) {
102
146
  add(year, month, day, home_team, home_score, away_score, away_team);
147
+
103
148
 
104
149
  }
150
+ for(i=0;i<HASHSIZE;i++)
151
+ printf("%d\n", HASH[i]); //ハッシュ値が偏りなくなっているか確かめる
105
152
 
106
153
 
107
154
 
108
155
  }
109
156
 
157
+
110
158
 
111
159
  ```

1

プログラムの説明が足りなかったこと。

2020/06/15 13:38

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -1,19 +1,6 @@
1
- チェイン法についての質問です。与えられた、ファイルデータ対戦相手、試合結果などを用いてデータを作成するといった内容です。
2
- まず、ハッシュのチェイン法で探索をする前に、ハッシュ関数でできた分布に偏りがないようにしたいです。
3
- ### ハッシュ法についての考え方
4
- １初期値にhashtableをそれぞれNULLにする
5
- ２home_teamとaway_teamを固定して、アスキーコードで文字列の合計の割る１７でハッシュテーブル０から17の中に割り当てる。
6
- ３push関数を用いて、最初はNULLのリストをmallocで次のリスト領域を格納する。
7
- ４リスト構造ができるごとに、それぞれのhashtableの値をインクリメントさせて、０から17の間にハッシュが偏りなく割り当てられているのか確認する
8
-
9
- 今やりたいことは、新たなホームとアウェイチームが別々にもかかわらず、ハッシュ値が同じで衝突するのを避けるためにリスト構造を用いて、先頭のリストを出すような形でやりたいと思っております。
1
+ チェイン法について質問です。二つ以上のハッシュ値が一致してしまった場合、それを避けるためにリスト構造を用いて、最初はリストの末尾にNULLを生成します。その後、新たなハッシュ値が出た場合にNULLの前に新たなリストを作り、衝突を避けるようにしたいです。
10
- リスト内ごとに、ホームとアウェイチームの内容を格納させて、数珠つなぎのようにつなげていくようにする
11
- 例えば野球チームだと
12
- hashtable[0]->[ジャイアンツ、ロッテ]->[タイガース、中日]->[NULL] 合計２
2
+ そのためにadd関数内にあるelseの後の条件whileの内容を満たすようにするにはどうすればよいのでしょうか。また、同じチームのアスキーコードが同じなのにハッシュ値が異なる値が表示される場合があるのはどうしてでしょうか。
13
- hashtable[1]->[DeNA、カープ]->[NULL]　　　　　　　　　　　　　　合計１
14
- といった最初はNULL内から、push関数でタイガース、中日の組のリストを生成し、次のチームのハッシュ値が１となり、DenA,カープの組がハッシュ値１のリストを生成することが目的です。最初の内容に戻ってしまいますが、この合計が偏りなくなるアルゴリズムを教えて欲しいです。
3
+ 例えばhome:Sanfrecce_Hiroshima_F.C away:Urawa_Red_Diamondsとした場合にハッシュ値が一回目が１１二回目が１６と異なる値が表示されることがあります。何度もコンパイルした結果そうなります。ご協力お願いします。
15
- そこにコードのヒントも下さると助かります。中途半端なので何も完成していないです。
16
-
17
4
  ```ここに言語を入力
18
5
  #define _CRT_SECURE_NO_WARNINGS
19
6
  #define HASHSIZE 17
@@ -22,23 +9,23 @@
22
9
  #include<string.h>
23
10
 
24
11
  struct match* hashtable[HASHSIZE];
25
-
12
+ struct match_score {
13
+ int year;
14
+ int month;
15
+ int day;
16
+ int home_score;
17
+ int away_score;
18
+ struct match_score* next;
19
+ };
26
20
  struct match {
27
21
  char *home;
28
22
  char *away;
23
+
24
+ struct match *next;
29
25
  struct match_score* r;
30
- struct match *next;
31
26
  };
32
27
 
33
- struct match * push( struct match * key,char*home,char *away) {
34
- struct match * tmp;
35
28
 
36
- tmp = (struct match*)malloc(sizeof(struct match ));
37
- tmp->home=home;
38
- tmp->away=away;
39
- tmp->next = tmp;
40
- return(tmp);
41
- }
42
29
  int hash(char *home,char *away) {
43
30
  int hashval = 0;
44
31
 
@@ -52,22 +39,51 @@
52
39
 
53
40
  }
54
41
  return hashval % HASHSIZE;
42
+
43
+
55
44
  }
45
+ void ListKeyWord(char * home,char *away,int Hash)
46
+ {
47
+
48
+ struct match* p=hashtable[Hash];
56
49
 
50
+
51
+ printf("home:%s away:%s ハッシュ値:%d:\n", (*p).home, (*p).away,hash((*p).home,away));
52
+ }
53
+
57
54
  void add(int year, int month, int day, char* home_team, int home_score, int away_score, char* away_team) {
58
55
  int hashval;
59
56
  struct match* ptr;
60
-
57
+
61
- hashval=hash(home_team, away_team);
58
+ hashval = hash(home_team, away_team);
62
- hashtable[hashval]++;
59
+
63
60
  ptr = (struct match*)malloc(sizeof(struct match));
64
- ptr->next = hashtable[hashval];
61
+ ptr->home = (char*)malloc(strlen(home_team) + 1);
65
- ptr->home = home_team;
62
+ strcpy(ptr->home, home_team);
63
+ ptr->away = (char*)malloc(strlen(away_team) + 1);
66
- ptr->away = away_team;
64
+ strcpy(ptr->away, away_team);
65
+
66
+
67
- ptr->next = hashtable[hashval];
67
+ if (hashtable[hashval] == NULL){
68
- hashtable[hashval] = ptr;
68
+ hashtable[hashval] = ptr;
69
+ ptr->next = NULL;
70
+
69
71
  }
72
+ else {
73
+ struct match* ptr2 = hashtable[hashval];
70
74
 
75
+ while (ptr2->next!= NULL ) {
76
+ ptr2 = ptr2->next;
77
+ ptr2->next = ptr;
78
+ ptr->next = NULL;
79
+ }
80
+
81
+ }
82
+
83
+ ListKeyWord(home_team,away_team,hashval);
84
+
85
+ }
86
+
71
87
  int main() {
72
88
  char home_team[256], away_team[256];
73
89
  int home_score, away_score;
@@ -82,15 +98,14 @@
82
98
  }
83
99
 
84
100
  fp = fopen(filename, "r");
85
- while ((f = fscanf(fp, "%d %d %d %s %d %d %s", &year, &month, &day, home_team, &home_score, &away_score, away_team)) != EOF) {
101
+ while ((f = fscanf(fp, "%d %d %d %s %d %d %s", year, month, day, home_team, home_score, away_score, away_team)) != EOF) {
86
102
  add(year, month, day, home_team, home_score, away_score, away_team);
87
- ptr = push(ptr, home_team, away_team);
103
+
88
104
  }
89
- for (i = 0; i < HASHSIZE; i++) {
105
+
90
- printf("%d\n", hashtable[i]);
91
- }
92
106
 
93
107
 
94
108
  }
95
109
 
110
+
96
111
  ```