編集履歴

質問編集履歴

投稿の疑似削除

2020/07/08 06:52

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -1,317 +1 @@
-チェイン法について質問です。二つ以上のハッシュ値が一致してしまった場合、それを避けるためにリスト構造を用いて、最初はリストの末尾にNULLを生成します。その後、新たなハッシュ値が出た場合にNULLの前に新たなリストを作り、衝突を避けるようにしたいです。
-今find関数を作り、今までのリストを結合した中から、同じ文字列のawayとhomeが見つかるまでループさせ、見つかったら、今現在生成されているリストを結合させないようにしたいです。つまり、違うaway homeのリストをそれぞれのハッシュテーブルに入れるようにしたいです
-例えばハッシュ値が3の場合に、０番目に清水エスパルスvsガンバ大阪のリスト、一番目には鹿島アントラーズvs柏レイソルのリストはそれぞれ違うhomeとawayで且つ同じハッシュ値なので結合できます。しかし１００番目に同じ清水エスパルスvsガンバ大阪の場合は今までのリストに同じ対戦相手があるので結合できなくなります。つまり衝突にカウントを加えないようになっている状態です。
-```ここに言語を入力
-#define _CRT_SECURE_NO_WARNINGS
-#define HASHSIZE 17
-#include <stdio.h>
-#include <stdlib.h>
-#include<string.h>
-struct match* hashtable[HASHSIZE];
-int HASH[HASHSIZE];
-struct match_score {
-    int year;
-    int month;
-    int day;
-    int home_score;
-    int away_score;
-    struct match_score* next;
-};
-struct match {
-    char *home;
-    char *away;
-    struct match *next;
-    struct match_score* r;
-};
-int hash(char *home,char *away) {
-    int hashval = 0;//ハッシュ値の値を初期化
-    while (*home != '\0'|| *away!='\0') {//homeとawayの値がどちらも\0になるまでループする
-        hashval += *home+*away;//アスキーコードの和を足す
-        if(*home!= '\0')//どちらかが\0になっても全てムラなく足せるようにする
-        home++;
-        if (*away != '\0')
-        away++;
-    }
-    return hashval % HASHSIZE;//ハッシュ値を返す。
-}
-struct match* find(char* home, char* away) {
-    struct match* p;//match構造体のポインタ変数
-    int hashval;
-    hashval = hash(home, away);//ハッシュ値を返す。
-    p = hashtable[hashval];//全体のリスト結合をpに代入させる
-    while (p != NULL) {//pがNULLになるまでループさせる
-        if ((strcmp(home, p->home) == 0) && (strcmp(away, p->away) == 0)) {//今のリストが探索して今までのリストのhome,awayが同じリストがあるならば今ののリストは結合させないようにしたい。
-            printf("%s %s\n", p->home, p->away);//同じアスキーコードがあるならばその値を返す。
-            return  p;
-        }
-        p = p->next;//同じ、homeとawayが見つかるまで次のリストに移動させる。
-    }
-}
-void ListKeyWord(struct match *p ,char * home,char *away,int Hash)
-{
-    struct match* ptr=hashtable[Hash];
-           // printf("home:%s away:%s ハッシュ値:%d:\n", (*p).home, (*p).away,hash((*p).home,(*p).away));
-         //   printf("home:%s away:%s ハッシュ値:%d:\n", (*ptr).home, (*ptr).away, hash((*ptr).home, (*ptr).away));
-}
-void add(int year, int month, int day, char* home_team, int home_score, int away_score, char* away_team) {
-    int hashval;
-    struct match* ptr;
-    int i;
-    hashval = hash(home_team, away_team);//homeとawayのアスキーコードの和とそれを割る素数からハッシュ値を返す。
-    ptr = (struct match*)malloc(sizeof(struct match));//ptrの領域を確保する
-    ptr->home = (char*)malloc(strlen(home_team) + 1);//homeの文字列+\0の長さを求める。
-    strcpy(ptr->home, home_team);//文字列のコピー
-    ptr->away = (char*)malloc(strlen(away_team) + 1);
-    strcpy(ptr->away, away_team);
-    if (hashtable[hashval] == NULL){//ハッシュ値が未登録ならば
-        hashtable[hashval] = ptr;//最初にアドレスを登録
-        ptr->next = NULL;//次の指すアドレスをNULLにする。
-       }
-    else {//ハッシュ値の中の値がNULLでなければNULLの後ろに新たなリストを生成する。
-        struct match* ptr2;//次のリストを指定
-        struct match* ptr3;//find関数のアドレスを返す。
-        ptr2 = hashtable[hashval];//今現在のリストをptr2に代入する
-        ptr3 = find(home_team, away_team);//find関数で探索をし、もし同じhomeとawayの値が見つかったらアドレスを返す
-        while (ptr2->next != NULL ) {
-            if ((strcmp(ptr2->home, ptr3->home) != 0) && (strcmp(ptr2->home, ptr3->home) != 0)) {//find関数で見つかったhomeとawayが今のptr2が同じならば、
-                //同じ名前のhomeとawayはリスト結合をしないようにしたい。
+ハッシュ法を用いる質問をしましたが都合により削除することになりました。コードは載せないようにしたいと思います。
-                ptr->next = NULL;
-                break;
-            }
-            else {
-                ptr2 = ptr2->next;
-                HASH[hashval]++;//同じハッシュ値がぶつかった回数だけ足していきたい。ただし同じhome,awayのリストは足さないようにしたい。
-            }
-        }
-        ptr2->next = ptr;//違うチーム同士をリスト結合でつないでいきたい
-        ptr->next = NULL;//リスとの末尾にNULLを返す。リストが終わるまで、何度もNULLの値が入れ替わる。
-    }
-    ListKeyWord(ptr,home_team, away_team, hashval);//ハッシュ値がどうなっているか確かめる
-}
-int main() {
-    char home_team[256], away_team[256];
-    int home_score, away_score;
-    int year, month, day, i, f;
-    struct match* ptr;
-    ptr = NULL;
-   const  char* filename = "jleague.txt";//Jリーグの過去の対戦結果のファイル
-    FILE* fp;
-    for (i = 0; i < HASHSIZE; i++) {
-        hashtable[i] = NULL;//初期値をNULLにさせる。
-    }
-    fp = fopen(filename, "r");
-    while ((f = fscanf(fp, "%d %d %d %s %d %d %s", &year, &month, &day, home_team, &home_score, &away_score, away_team)) != EOF) {
-        add(year, month, day, home_team, home_score, away_score, away_team);
-    }
-    for(i=0;i<HASHSIZE;i++)
-    printf("%d\n", HASH[i]);    //ハッシュ値が偏りなくなっているか確かめる
-}
-```

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

2020/07/08 06:52

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -1,8 +1,8 @@
 チェイン法について質問です。二つ以上のハッシュ値が一致してしまった場合、それを避けるためにリスト構造を用いて、最初はリストの末尾にNULLを生成します。その後、新たなハッシュ値が出た場合にNULLの前に新たなリストを作り、衝突を避けるようにしたいです。
-そのためにadd関数内にあるelseの後の条件whileの内容を満たすようにするにはどうすればよいのでしょうか。また、同じチームのアスキーコードが同じなのにハッシュ値が異なる値が表示される場合があるのはどうしてでしょうか。
-例えばhome:Sanfrecce_Hiroshima_F.C away:Urawa_Red_Diamondsとした場合にハッシュ値が一回目が１１二回目が１６と異なる値が表示されることがあります。何度もコンパイルした結果そうなります。ご協力お願いします。
+今find関数を作り、今までのリストを結合した中から、同じ文字列のawayとhomeが見つかるまでループさせ、見つかったら、今現在生成されているリストを結合させないようにしたいです。つまり、違うaway homeのリストをそれぞれのハッシュテーブルに入れるようにしたいです
+例えばハッシュ値が3の場合に、０番目に清水エスパルスvsガンバ大阪のリスト、一番目には鹿島アントラーズvs柏レイソルのリストはそれぞれ違うhomeとawayで且つ同じハッシュ値なので結合できます。しかし１００番目に同じ清水エスパルスvsガンバ大阪の場合は今までのリストに同じ対戦相手があるので結合できなくなります。つまり衝突にカウントを加えないようになっている状態です。
 ```ここに言語を入力
@@ -20,6 +20,8 @@
 struct match* hashtable[HASHSIZE];
+int HASH[HASHSIZE];
 struct match_score {
     int year;
@@ -52,21 +54,19 @@
 int hash(char *home,char *away) {
-    int hashval = 0;
+    int hashval = 0;//ハッシュ値の値を初期化
-    while (*home != '\0'|| *away!='\0') {
+    while (*home != '\0'|| *away!='\0') {//homeとawayの値がどちらも\0になるまでループする
-        hashval += *home+*away;
+        hashval += *home+*away;//アスキーコードの和を足す
-        if(*home!= '\0')
+        if(*home!= '\0')//どちらかが\0になっても全てムラなく足せるようにする
         home++;
@@ -78,29 +78,81 @@
     }
-    return hashval % HASHSIZE;
+    return hashval % HASHSIZE;//ハッシュ値を返す。
-}
+}
+struct match* find(char* home, char* away) {
+    struct match* p;//match構造体のポインタ変数
+    int hashval;
+    hashval = hash(home, away);//ハッシュ値を返す。
+    p = hashtable[hashval];//全体のリスト結合をpに代入させる
+    while (p != NULL) {//pがNULLになるまでループさせる
+        if ((strcmp(home, p->home) == 0) && (strcmp(away, p->away) == 0)) {//今のリストが探索して今までのリストのhome,awayが同じリストがあるならば今ののリストは結合させないようにしたい。
+            printf("%s %s\n", p->home, p->away);//同じアスキーコードがあるならばその値を返す。
+            return  p;
+        }
+        p = p->next;//同じ、homeとawayが見つかるまで次のリストに移動させる。
+    }
+}
-void ListKeyWord(char * home,char *away,int Hash)
+void ListKeyWord(struct match *p ,char * home,char *away,int Hash)
 {
-    struct match* p=hashtable[Hash];
+    struct match* ptr=hashtable[Hash];
-            printf("home:%s away:%s ハッシュ値:%d:\n", (*p).home, (*p).away,hash((*p).home,away));
+           // printf("home:%s away:%s ハッシュ値:%d:\n", (*p).home, (*p).away,hash((*p).home,(*p).away));
+         //   printf("home:%s away:%s ハッシュ値:%d:\n", (*ptr).home, (*ptr).away, hash((*ptr).home, (*ptr).away));
-}
+}
@@ -110,59 +162,95 @@
     struct match* ptr;
+    int i;
-    hashval = hash(home_team, away_team);
+    hashval = hash(home_team, away_team);//homeとawayのアスキーコードの和とそれを割る素数からハッシュ値を返す。
-    ptr = (struct match*)malloc(sizeof(struct match));
+    ptr = (struct match*)malloc(sizeof(struct match));//ptrの領域を確保する
-    ptr->home = (char*)malloc(strlen(home_team) + 1);
+    ptr->home = (char*)malloc(strlen(home_team) + 1);//homeの文字列+\0の長さを求める。
-    strcpy(ptr->home, home_team);
+    strcpy(ptr->home, home_team);//文字列のコピー
     ptr->away = (char*)malloc(strlen(away_team) + 1);
     strcpy(ptr->away, away_team);
-    if (hashtable[hashval] == NULL){
+    if (hashtable[hashval] == NULL){//ハッシュ値が未登録ならば
-        hashtable[hashval] = ptr;
+        hashtable[hashval] = ptr;//最初にアドレスを登録
-        ptr->next = NULL;
+        ptr->next = NULL;//次の指すアドレスをNULLにする。
-}
+       }
+    else {//ハッシュ値の中の値がNULLでなければNULLの後ろに新たなリストを生成する。
+        struct match* ptr2;//次のリストを指定
+        struct match* ptr3;//find関数のアドレスを返す。
+        ptr2 = hashtable[hashval];//今現在のリストをptr2に代入する
+        ptr3 = find(home_team, away_team);//find関数で探索をし、もし同じhomeとawayの値が見つかったらアドレスを返す
+        while (ptr2->next != NULL ) {
+            if ((strcmp(ptr2->home, ptr3->home) != 0) && (strcmp(ptr2->home, ptr3->home) != 0)) {//find関数で見つかったhomeとawayが今のptr2が同じならば、
+                //同じ名前のhomeとawayはリスト結合をしないようにしたい。
+                ptr->next = NULL;
+                break;
+            }
-    else {
+            else {
-        struct match* ptr2 = hashtable[hashval];
-        while (ptr2->next!= NULL ) {
-            ptr2 = ptr2->next;
+                ptr2 = ptr2->next;
-            ptr2->next = ptr;
+                HASH[hashval]++;//同じハッシュ値がぶつかった回数だけ足していきたい。ただし同じhome,awayのリストは足さないようにしたい。
-            ptr->next = NULL;
-    }
+            }
-    }
+        }
+        ptr2->next = ptr;//違うチーム同士をリスト結合でつないでいきたい
+        ptr->next = NULL;//リスとの末尾にNULLを返す。リストが終わるまで、何度もNULLの値が入れ替わる。
+    }
-    ListKeyWord(home_team,away_team,hashval);
+    ListKeyWord(ptr,home_team, away_team, hashval);//ハッシュ値がどうなっているか確かめる
@@ -182,39 +270,47 @@
     ptr = NULL;
-   const  char* filename = "jleague.txt";
+   const  char* filename = "jleague.txt";//Jリーグの過去の対戦結果のファイル
     FILE* fp;
     for (i = 0; i < HASHSIZE; i++) {
-        hashtable[i] = NULL;
+        hashtable[i] = NULL;//初期値をNULLにさせる。
-    }
+    }
     fp = fopen(filename, "r");
-    while ((f = fscanf(fp, "%d %d %d %s %d %d %s", year, month, day, home_team, home_score, away_score, away_team)) != EOF) {
+    while ((f = fscanf(fp, "%d %d %d %s %d %d %s", &year, &month, &day, home_team, &home_score, &away_score, away_team)) != EOF) {
         add(year, month, day, home_team, home_score, away_score, away_team);
-    }
+    }
+    for(i=0;i<HASHSIZE;i++)
+    printf("%d\n", HASH[i]);    //ハッシュ値が偏りなくなっているか確かめる
-}
+}

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

2020/06/15 13:38

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -1,34 +1,8 @@
-チェイン法についての質問です。与えられた、ファイルデータ対戦相手、試合結果などを用いてデータを作成するといった内容です。
-まず、ハッシュのチェイン法で探索をする前に、ハッシュ関数でできた分布に偏りがないようにしたいです。
-### ハッシュ法についての考え方
-１初期値にhashtableをそれぞれNULLにする
-２home_teamとaway_teamを固定して、アスキーコードで文字列の合計の割る１７でハッシュテーブル０から17の中に割り当てる。
-３push関数を用いて、最初はNULLのリストをmallocで次のリスト領域を格納する。
-４リスト構造ができるごとに、それぞれのhashtableの値をインクリメントさせて、０から17の間にハッシュが偏りなく割り当てられているのか確認する
-今やりたいことは、新たなホームとアウェイチームが別々にもかかわらず、ハッシュ値が同じで衝突するのを避けるためにリスト構造を用いて、先頭のリストを出すような形でやりたいと思っております。
+チェイン法について質問です。二つ以上のハッシュ値が一致してしまった場合、それを避けるためにリスト構造を用いて、最初はリストの末尾にNULLを生成します。その後、新たなハッシュ値が出た場合にNULLの前に新たなリストを作り、衝突を避けるようにしたいです。
-リスト内ごとに、ホームとアウェイチームの内容を格納させて、数珠つなぎのようにつなげていくようにする
-例えば野球チームだと
-hashtable[0]->[ジャイアンツ、ロッテ]->[タイガース、中日]->[NULL] 合計２
+そのためにadd関数内にあるelseの後の条件whileの内容を満たすようにするにはどうすればよいのでしょうか。また、同じチームのアスキーコードが同じなのにハッシュ値が異なる値が表示される場合があるのはどうしてでしょうか。
-hashtable[1]->[DeNA、カープ]->[NULL]　　　　　　　　　　　　　　合計１
-といった最初はNULL内から、push関数でタイガース、中日の組のリストを生成し、次のチームのハッシュ値が１となり、DenA,カープの組がハッシュ値１のリストを生成することが目的です。最初の内容に戻ってしまいますが、この合計が偏りなくなるアルゴリズムを教えて欲しいです。
+例えばhome:Sanfrecce_Hiroshima_F.C away:Urawa_Red_Diamondsとした場合にハッシュ値が一回目が１１二回目が１６と異なる値が表示されることがあります。何度もコンパイルした結果そうなります。ご協力お願いします。
-そこにコードのヒントも下さると助かります。中途半端なので何も完成していないです。
 ```ここに言語を入力
@@ -46,7 +20,21 @@
 struct match* hashtable[HASHSIZE];
+struct match_score {
+    int year;
+    int month;
+    int day;
+    int home_score;
+    int away_score;
+    struct match_score* next;
+};
 struct match {
@@ -54,31 +42,17 @@
     char *away;
+    struct match *next;
     struct match_score* r;
-    struct match *next;
 };
-struct match * push( struct match * key,char*home,char *away) {
-    struct match * tmp;
-    tmp = (struct match*)malloc(sizeof(struct match ));
-    tmp->home=home;
-    tmp->away=away;
-    tmp->next = tmp;
-    return(tmp);
-}
 int hash(char *home,char *away) {
@@ -106,6 +80,26 @@
     return hashval % HASHSIZE;
+}
+void ListKeyWord(char * home,char *away,int Hash)
+{
+    struct match* p=hashtable[Hash];
+            printf("home:%s away:%s ハッシュ値:%d:\n", (*p).home, (*p).away,hash((*p).home,away));
 }
@@ -116,23 +110,61 @@
     struct match* ptr;
-    hashval=hash(home_team, away_team);
+    hashval = hash(home_team, away_team);
-    hashtable[hashval]++;
     ptr = (struct match*)malloc(sizeof(struct match));
-    ptr->next = hashtable[hashval];
+    ptr->home = (char*)malloc(strlen(home_team) + 1);
-    ptr->home = home_team;
+    strcpy(ptr->home, home_team);
+    ptr->away = (char*)malloc(strlen(away_team) + 1);
-    ptr->away = away_team;
+    strcpy(ptr->away, away_team);
-    ptr->next = hashtable[hashval];
+    if (hashtable[hashval] == NULL){
-    hashtable[hashval] = ptr;
+        hashtable[hashval] = ptr;
+        ptr->next = NULL;
+}
+    else {
+        struct match* ptr2 = hashtable[hashval];
+        while (ptr2->next!= NULL ) {
+            ptr2 = ptr2->next;
+            ptr2->next = ptr;
+            ptr->next = NULL;
+    }
+    }
+    ListKeyWord(home_team,away_team,hashval);
 }
@@ -166,25 +198,23 @@
     fp = fopen(filename, "r");
-    while ((f = fscanf(fp, "%d %d %d %s %d %d %s", &year, &month, &day, home_team, &home_score, &away_score, away_team)) != EOF) {
+    while ((f = fscanf(fp, "%d %d %d %s %d %d %s", year, month, day, home_team, home_score, away_score, away_team)) != EOF) {
         add(year, month, day, home_team, home_score, away_score, away_team);
-        ptr = push(ptr, home_team, away_team);
-    }
+    }
-    for (i = 0; i < HASHSIZE; i++) {
-        printf("%d\n", hashtable[i]);
-    }
+}
-}