質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.46%

  • C

    4685questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

英文ファイルを英単語ごとにハッシュ表に格納してソースを行う

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 3,066

kt3302y

score 19

前回投稿させてもらった件の続きなのですが,英単語を登録して出現回数も記録するハッシュ表を作成しました.今悩んでいますのがlexと入力したら英単語を辞書順にoccと入力したら出現回数を降順に回数が一致するなら辞書順に並べるというプログラムを作成したソースコードが下のものになるのですが,これを実行するとqsortを実行しようとするとアクセス違反が起きてしまいます.何故起きてしまうのか原因と解決方法を教えてくれないでしょうか
hash.c
* hash.c: ハッシュ表の型とその操作用関数の定義
* (ハッシュ表のキー:文字列,値:非負の整数)
*/
#include "hash.h"

#define HASH_SIZE 997 /* ハッシュ表の内部配列のサイズ */
#define HASH_RADIX 97 /* ハッシュ関数用の基数 */

/* ハッシュ表内の連結リストに含まれるノードとそのポインタの型. */
typedef struct hash_node HashNode;
typedef HashNode *HashNodePtr;

/* ハッシュ表内の連結リストに含まれるノードの構造体. */
struct hash_node { /* ハッシュ表内の連結リストのノード */
    char *key; /* キー */
    int value; /* キーに対応する値 */
    int id;    /* キーに付与された通し番号 */
    struct hash_node *next; /* 次のノードへのポインタ */
};

/* ハッシュ表の構造体. */
struct hashtable {
    HashNodePtr *heads; /* 内部配列 */
    int serial_id; /* 通し番号管理用の変数 */
    int size; /* 内部配列のサイズ */
};

/* static 関数のプロトタイプ宣言 */
static unsigned int hash(char *s);
static int get_index(HashTablePtr t, char *key);

/* 文字列 s のハッシュ値を計算する. */
static unsigned int hash(char *s) {
    unsigned int v;

    v = 0;
    while (*s != '\0') {
        v = v * HASH_RADIX + *s;
        s++;
    }

    return v;
}

/* ハッシュ表を一つ生成し,そのポインタを返す.*/
HashTablePtr create_hashtable(void) {
    HashTablePtr t = NULL;
    int i;

    t = malloc(sizeof(HashTable));
    if (t == NULL) {
        fprintf(stderr, "Couldn't allocate memory for a hashtable\n");
        exit(EXIT_FAILURE);
    }

    t->serial_id = 0;
    t->size = HASH_SIZE;
    t->heads = malloc(sizeof(HashNodePtr) * t->size);
    if (t->heads == NULL) {
        fprintf(stderr, "Couldn't allocate memory for a hashtable's header array\n");
        exit(EXIT_FAILURE);
    }

    /* 各連結リストの先頭要素へのポインタは必ず NULL に初期化する */
    for (i = 0; i < t->size; i++) {
        t->heads[i] = NULL;
    }

    return t;
}

/* ハッシュ表の実質的な解放作業を行う.
* (次々と free() するので free() 後の NULL 代入は省略)
*/
void delete_hashtable0(HashTablePtr t) {
    HashNodePtr n = NULL, m = NULL;
    int i;

    /* free() と同様,NULLポインタに対しては何も行わない */
    if (t == NULL) {
        return;
    }

    /* 各連結リストの領域を解放 */
    for (i = 0; i < t->size; i++) {
        n = t->heads[i];
        while (n != NULL) {
            m = n;
            n = n->next;
            free(m);
        }
    }

    /* 最後に連結リストの先頭ポインタの領域を解放 */
    free(t->heads);
    free(t);
}

/* ハッシュ表 t に登録されているキーと値のペアの数を返す.*/
int get_cardinality(HashTablePtr t) {
    assert(t);
    return t->serial_id;
}

/* ハッシュ表 t の内部配列の添え字を返す */
static int get_index(HashTablePtr t, char *key) {
    return hash(key) % t->size;
}

/* ハッシュ表 t にてキー key が登録されていれば1,
* されていなければ0を返す.
*/
int has_key(HashTablePtr t, char *key) {
    assert(t && key);
    return (lookup(t, key) >= 0) ? 1 : 0;
}

/* ハッシュ表 t にてキー key に対応する値を返す.
* 値が見つからなかったら -1 を返す.
* (ハッシュ表の値として登録できるのは非負の整数値と仮定)
*/
int lookup(HashTablePtr t, char *key) {
    HashNodePtr n = NULL;
    int index;

    assert(t && key);

    /* ハッシュ表の内部配列の添え字を計算 */
    index = get_index(t, key);

    /* index 番目の連結リストを先頭から順に走査 */
    n = t->heads[index];
    while (n != NULL) {
        /* 引数で指定された key とハッシュ表内のキーが一致したら
        直ちに対応する値を返す */
        if (strcmp(key, n->key) == 0) {
            return n->value;
        }

        /* 走査を次に進める */
        n = n->next;
    }

    /* キーが見つからなかったので -1 を返す */
    return -1;
}

/* キー key と値 value のペアをハッシュ表 t に登録し,その通し番号を返す.
* (値 value は非負であると仮定)
*/
int enter(HashTablePtr t, char *key, int value) {
    HashNodePtr n = NULL, m = NULL;
    int index;

    assert(t && key);

    /* 仕様上のエラーなので非負の値が渡されたときはメッセージを出す */
    if (value < 0) {
        fprintf(stderr, "Invalid value %d for key %s\n", value, key);
        exit(EXIT_FAILURE);
    }

    /* 内部配列の添え字を計算 */
    index = get_index(t, key);

    /* キー key が既に登録されているか探し,
    * 登録されている場合は値を value に更新する.
    */
    n = t->heads[index]; /* index 番目の head を出発点とする */
    if (n != NULL) {
        while (n != NULL) {
            if (strcmp(key, n->key) == 0) { /* 登録されていた */
                n->value += 1; /* 値を更新 */
                return n->id;
            }
            n = n->next;
        }
    }

    /* 新しいノードを生成 */
    m = malloc(sizeof(HashNode));
    if (m == NULL) {
        fprintf(stderr, "Couldn't allocate memory for a hash node\n");
        exit(EXIT_FAILURE);
    }

    m->key = _strdup(key);
    m->id = t->serial_id;
    m->value = value;

    /* 新しいノードを先頭に挿入 */
    m->next = t->heads[index];
    t->heads[index] = m;

    t->serial_id++; /* 次の通し番号に更新 */

    return m->id; /* 登録したキーと値のペアに付与された通し番号を返す */
}

/*
* ハッシュ表 t に登録されるキーの配列を返す.
*(この配列のサイズは get_hash_cardinality() で取得可能)
*/
char **get_keys(HashTablePtr t) {
    char **keys = NULL;
    HashNodePtr n;
    int i;

    assert(t);

    keys = malloc(sizeof(char *) * t->serial_id);
    if (keys == NULL) {
        fprintf(stderr, "Couldn't allocate memory for hashtable keys\n");
        exit(EXIT_FAILURE);
    }

    /* 各連結リストを走査し,配列に詰め込む */
    for (i = 0; i < t->size; i++) {
        n = t->heads[i];
        while (n != NULL) {
            keys[n->id] = n->key; /* 通し番号を配列添え字に */
            n = n->next;
        }
    }

    return keys; /* 後で free() する必要あり */
}

/* ハッシュ表の内容を表示する.*/
void print_hashtable(HashTablePtr t, FILE *fp) {
    HashNodePtr n = NULL;
    int i;

    assert(t);

    for (i = 0; i < t->size; i++) {
        n = t->heads[i];
        while (n != NULL) {
            fprintf(fp, "%s => %d\n", n->key, n->value);
            n = n->next;
        }
    }
}

void sort1(HashTablePtr t)
{
    qsort(t->heads, t->size, sizeof(HashNodePtr), compare1);
}

void sort2(HashTablePtr t)
{
    qsort(t->heads, t->size, sizeof(HashNodePtr), compare2);
}

/*qsortの比較関数*/
int compare1(const void *p, const void *q)
{
    HashNodePtr u = NULL;
    HashNodePtr v = NULL;

    u = (HashNodePtr )p;
    v = (HashNodePtr )q;

    return strcmp(u->key, v->key);
}

int compare2(const void *p, const void *q)
{
    HashNodePtr u = NULL;
    HashNodePtr v = NULL;

    u = (HashNodePtr)p;
    v = (HashNodePtr)q;

    if (u->value < v->value)return 1;
    if (u->value > v->value)return -1;
    if (u == v)return strcmp(u->key, v->key);
}
main.c
#define _CRT_SECURE_NO_WARNINGS
#include "hash.h"
#include "vector.h"
#include "etc.h"

#define MAX 256

int main(void)
{
    char buf[MAX] = { 0 };
    char *copy, *s,*b;
    char *str = "occ";
    VectorPtr v = NULL;
    HashTablePtr t = NULL;
    FILE *fp1,*fp2;
    fp1 = fopen("input1.txt", "r");
    fp2 = fopen("write.txt", "w");

    t = create_hashtable();

    /*全行文の文字列を格納する*/
    while (fgets(buf, sizeof(buf), fp1) != NULL)
    {
        *buf = *Strtolower(buf);
        s = copy = _strdup(buf);
        while (b = strtok(s, "(), .;'![]?\n\""))
        {
            enter(t, b, 1);
            s = NULL;
        }
        free(copy);
    }
    if (strcmp(str, "lex")==0)sort1(t);
    else if (strcmp(str,"occ")==0)sort2(t);
    print_hashtable(t, fp2);
    fclose(fp1);
    fclose(fp2);

    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

0

    if (str == "lex")sort1(t);
    else if (str =="occ")sort2(t);

ここで文字列を==で比較していますが、
strcmpstrncmpなどを使うべきと思います。

このままではメモリアドレスの比較になって、
どちらも通らないため、ハッシュ表が作成されず、
結果としてアクセス違反になっているのだと思います。

 訂正

上の記述は、「このままでは………なっているのだと思います。」
という部分が誤っていました。
また、この問題の原因でもなさそうです。

sort(t, sizeof(t), sizeof(t), compare1);
がおかしいと思います。

void * data:ソート対象データ
size_t data_cnt:ソート対象データ件数
size_t data_size:ソート対象データ1件当りのサイズ
int func:int型の比較関数(プログラマが作成する関数)

なので、

sort(t->heads, t->size, sizeof(HashNodePtr), compare1);

ではないかと思うのですが、どうでしょうか?

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/07/18 22:41

    それはそれとして、前の質問の回答のどれかをベストアンサーにして
    質問を締めた方が良いのではと思います。

    キャンセル

  • 2015/07/18 22:46

    すみません。
    よく見ると初期化の流れは別だったのでこの回答は取り下げます。

    キャンセル

  • 2015/07/18 22:48

    解答ありがとうございます.
    おっしゃられたとおりに
    if (strcmp(str,"lex")==0)としてみましたがアクセス違反が起きてしまいました.
    この表記では違いますか?

    キャンセル

  • 2015/07/18 23:10

    上のコメントでも書きましたが、私の回答が間違っていました。
    すみません。

    別の原因を見つけて訂正した回答を投稿し直しました。

    キャンセル

  • 2015/07/18 23:33

    してみましたがうまくいきませんでした
    nextポインタがつながってないんですかね

    キャンセル

  • 2015/07/18 23:36 編集

    うーん、そうですか。
    sort1、sort2を呼び出さなければ、
    print_hashtableは正常動作するのでしょうか?

    それと、sort1についてしか記述しませんでしたが、
    sort2についても同様の修正が必要ですが、
    実施されたでしょうか?

    キャンセル

  • 2015/07/18 23:54

    sortを呼び出さなければ正常に起動します.
    あと、このqsort条件に変更した場合,そのqsortのところでアクセス違反が起きていました
    sort1,2両方行いましたがエラーが起こりました

    キャンセル

  • 2015/07/19 00:10 編集

    よく見ると、compare1、compare2で、
    引数がNULLのケースが想定されていませんね。

    NULLチェックして、NULLの要素が前か後ろかになるようにすれば、
    アクセス違反は出なくなるのではと思います。

    キャンセル

  • 2015/07/19 00:17

    ただ、それだけでは意図したコードにはならなそうです。
    ハッシュ表の内容を配列に格納し直して、
    それからソートするなど、直さなければならないと思います。

    キャンセル

  • 2015/07/19 09:03

    keyのソートの場合、get_keys関数を使用してkeyを配列に格納してqsortを使用すればよいのでしょうか

    キャンセル

  • 2015/07/19 09:10

    keyのソートならそれで良いですが、
    valueもソートに使うなら、
    HashNodePtr *get_entries(HashTablePtr t)というような関数を作って、
    その結果をcompare1やcompare2でqsortすれば良いと思います。

    キャンセル

  • 2015/07/19 19:03 編集

    そのkeyとvalueの値を格納する配列というのはどのようにすればよいのでしょうか.
    あと、別の配列に入れてその配列をソートを行ったとしてもハッシュ表の内容を表示するため、結局ソートしたことにならないと思うのですが違うのですか?
    すいません、初心者のため初歩的な質問をしてしまい

    キャンセル

  • 2015/07/20 00:02

    まず、ハッシュ表をハッシュ表のままソートする、
    ということはできません。
    ハッシュ表はハッシュの順になっていて、
    別の順序にしては、ハッシュ表でなくなってしまうためです。

    ソートしたい場合は、
    ソートしたい要素を配列などにする必要があります。
    配列であれば、順序が変わっても問題ないためです。
    表示も、ハッシュ表を表示する処理を使うのではなく、
    配列に格納した内容を表示する処理が必要になります。

    今回の場合、全てのHashNodePtrを配列を作れば、
    それをソートすることができます。
    注意点としては、HashNodePtrはnextでつながっているものもあるので、
    それもは配列の一要素として格納する必要があることです

    この全てのHashNodePtrの配列を作る処理によく似た処理があります。
    それは、get_keys関数です。
    これをほぼそのままコピーして、HashNodePtr *get_entries(HashTablePtr t)という関数を作り、mallocをHashNodePtrのサイズで行い、keyでなくHashNodePtrを配列に格納すれば、期待する関数になるはずです。

    この説明でどうでしょうか?

    キャンセル

  • 2015/07/21 14:25

    とても詳しい説明ありがとうございました.うまく作成することができました.
    qsortがこの方法でできない原因も知ることができましたし,本当にありがとうございました

    キャンセル

-1

上のコメントでも書きましたが、私の回答が間違っていました。
別の原因を見つけて訂正した回答を投稿し直しました。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/07/18 23:09

    コメントと間違って投稿したので、この回答は無視してください。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.46%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • C

    4685questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。