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

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

ただいまの
回答率

90.33%

  • C

    3991questions

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

  • アルゴリズム

    427questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • ソート

    71questions

    複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

  • データ構造

    48questions

    データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

  • ハッシュ

    41questions

    ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

ハッシュテーブルのソート

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 781
退会済みユーザー

退会済みユーザー

前提・実現したいこと

入力された英語の文章中に含まれる英単語の出現回数を数え, 多いものから順に表示するプログラムをハッシュテーブルを利用して作成したいです.

発生している問題・試したこと

データ構造を維持してなるべく高速なソートを行いたいのですが実装ができません.
~~以下のマージソートで実装してみましたがSegmentation faultが出力されました.~~
以下のソースコードで実行してもソートされません.
ご教授よろしくお願いします.

ソースコード修正しました(getwordは修正できていません).
ハッシュテーブルの各セルの末尾を連結して1つのリストとするのが有効だと考えました.

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define WORDLEN 50
#define SIZE 32

struct wd {
    struct wd *next;
    char *str;
    int count;
};
typedef struct wd WORD;

WORD *word[SIZE];

void init_word();
WORD *add_word(char *);
char *getword(char *, int);
int hash(char *w);
WORD *merge_list(WORD *w1, WORD *w2);
WORD *merge_sort(WORD *w);

int main()
{
    char w[WORDLEN];
    WORD *p;
    int i;

    init_word();
    while (getword(w, WORDLEN) != NULL) {
        p = add_word(w);
        if (p == NULL) {
            fprintf(stderr, "Too many words\n");
            exit(1);
        }
        p->count++;
    }

    for (i = 0; i < SIZE; i++) {
        for (p = word[i]; p != NULL; p = p->next) {
            printf("%d %s\n", p->count, p->str);
        }
    }
    return 0;
}


void init_word()
{
    int i;

    for (i = 0; i < SIZE; i++)
        word[i] = NULL;
}


WORD *add_word(char *w)
{
    char *s;
    WORD *p;
    int i;

    i = hash(w);
    for (p = word[i]; p != NULL; p = p->next) {
        if (strcmp(w, p->str) == 0)
            return p;
    }
    s = (char *)malloc(strlen(w) + 1);
    if (s == NULL)
        return NULL;
    strcpy(s, w);
    p = (WORD *)malloc(sizeof(WORD));
    if (p == NULL)
        return NULL;
    p->str   = s;
    p->count = 0;
    if (word[i] == NULL && i != SIZE - 1)
        p->next = word[i + 1];
    p->next  = word[i];
    word[i]  = p;
    return p;
}

char *getword(char *w, int n)
{
    int i = 0;
    int c;

    if (n <= 0 || feof(stdin))
    return NULL;
    c = getchar();
    while (c != EOF && ! isalpha(c)) {
    c = getchar();
    }
    if (c == EOF)
    return NULL;
    while (isalpha(c)) {
    if (i < n - 1) {
        w[i] = toupper(c);
        i++;
    }
    c = getchar();
    }
    w[i] = '\0';
    return w;
}

int hash(char *w)
{
  int i;
  unsigned int h = 0;

  for (i = 0; w[i] != '\0'; i++)
    h = 65599 * h + w[i];
  return h % SIZE;
}

WORD *merge_list (WORD *w1,WORD *w2) {
    WORD out, *w;
    w = &out;

    while ( w1 != NULL && w2 != NULL ) {
        if ( w1->str <= w2->str ) {
            w->next = w1;
            w = w1;
            w1 = w1->next;
        }
        else {
            w->next = w2;
            w = w2;
            w2 = w2->next;
        }
    }

    if ( w1 == NULL ) {
        w->next = w2;
    }
    else {
        w->next = w1;
    }

    return out.next;
}

WORD *merge_sort (WORD *w) {
    WORD *a, *b, *y;

    if ( w == NULL || w->next == NULL ) return w;

    a = w;
    b = w->next->next;

    while ( b!=NULL && b->next!=NULL ) {
        a = a->next;
        b = b->next->next;
    }

    y = a->next;
    a->next = NULL;

    return merge_list( merge_sort(w),merge_sort(y) );
}

実行結果

31 INTO
2 MELT
1 ACCORD
9 BREATH
7 DIE
1 PERSONAL
11 BUSINESS
16 BROTHER
6 II
5 GAINST
1 PROBATION
1 CROSS
78 LL
1 COUNTRYMEN
27 HEAD
1 SKIRTS
1 AVOUCH
1 FORTIFIED
15 THEREFORE
33 AGAIN
3 POST
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

checkベストアンサー

+2

質問内容に対してコメントします

  • どんなコードを書いたのかわからない
    質問にはソートしない版の「完全なプログラム」と「ソートするための関数=プログラムの断片」しか記述されていません。ソートする関数をどのようにメインプログラムに組み込んだか書かれていませんよって「不当メモリーアクセスが発生した」原因もまた曖昧です。マージソートの関数に原因があるのかも知れませんし、あなたがマージソートをメインプログラムからどのように使ったかに原因があるかも知れません。閲覧者にはそれがわからいので曖昧な問題に対して確信を持った回答ができないのです。そうした質問はスルーされる確率が高くなると思います。

  • デバッグしましょう
    不当メモリーアクセスはCをデバッグしている際にままあることですが、それが発生した際にどのようにデバッグを行うかを学ぶほうがよいでしょう。Javaなどですと例外が発生したらスタックダンプがコンソールに出力される仕組みがあったりするのでデバッグはずいぶん楽ですが、Cですとデバッグの仕方はもっと知識が必要になってきます。coreダンプを頼りに「どこでエラーが発生したのかをgdbなどを使って調べる方法」を学ぶとよいと思います。もしくはデバッグプリントをプログラムへ挿入して、プログラムの動きを知る工夫をすることも可能ですね。そういう方法でもよいと思います。またIDEを使えばもっと直感的に分かりやすいデバッグができるでしょう。

以下は蛇足です。
getword関数をみてちょっと気づいたことがあるのでコメントします。
実際の動作は間違ってませんが末尾にNUL文字を格納する余地がない場合に正常終了しようとしているように見えてしまいます。実際はどれだけ長い文字列が入力されてもwhile文の中の条件判定によりバッファー長-1よりも多くの文字を格納しないようになっているのでNUL文字を追加できないような状況になることはありえません。しかしせっかくそうしているのに
if (i < n) w[i++] = '\0';
というコードを書いてしまうと台無しです。念のためここに判定をいれたいのなら「ここでi>=nになることは矛盾と考えて以下のようにしたほうがよいと考えます。

if (i >= n) {
  fprintf(stderr, "unexpected situation");
  abort();
}
/*
 * あるいはassert.hをincludeしておき単に以下のように記述する
 * assert(i < n);
 */
w[i] = '\0';
return w;

追記:
コードが変更されたので拝見しました。しかし・・・ソート関数を用意したものの肝心のmerge_sortをどう呼び出したかがコードにないです。やってみて異常終了してしまったのでmerge_sortのコール部分をそっくり取ってしまったんだと思いますが、アドバイスする側からいえば例えcore dumpするとしてもあなたがやろうとしたことが盛り込まれたコードを提示してもらったほうがやりやすいです。

ではありますが・・・一応質問者さんが陥っていると思える間違いを推測してコメントします。

  1. merge_listでのWORDの比較
    出現頻度順にソートしようとしているのにw1->strとw2->strを比較しています。ここは単なる勘違いだと思います。w1->count >= w2->countとすべきですね。

  2. WORDのnextの使い方
    このメンバーの目的は「同一ハッシュ値を持つ複数のWORDを繋いでおくこと」です。しかしmerge_xxx関数の実装をみると並べ替えた結果を繋ぐ目的でnextを使用しています。元々の問題設定では「データ構造を維持して」とありますがnextを異なる目的で使っているためマージソートをするとハッシュテーブルの構造は破壊されます。どうしたかったのかはっきりわかりませんが、ハッシュテーブルの構造は全単語を登録し終えたら壊してもよいと仮定して以降を考えました。

  3. マージソートの入力を作る
    さて、ハッシュテーブルへ全単語を登録し終えた時点ではnextには全単語は繋がっていませ。前述のようにハッシュ値が衝突しているWORDだけが繋がります。そこでマージソートを呼び出す際にすべきことはwordテーブルに登録された全WORDをnextによって繋げることです。そうしてつなげた上でチェーンの先頭をmerge_sortに渡すようにしてみてください。

WORD *head = NULL;
for (i = 0; i < SIZE; i++) {
    p = word[i];
    if (p != NULL) {
        while (p->next != NULL)
            p = p->next;
        p->next = head;
        head = word[i];
    }
}
head = merge_sort(head);

蛇足ながらハッシュテーブルの構造は壊れてしまうのでソート済みの単語をダンプするにはもはやwordは使えません。上のコード例にあるheadから始めてnextを辿りながらWORDの内容を印字してください。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/01/31 09:50

    色々ご教授ありがとうございます. とても参考になります
    ソースコードをマージソートを含めた1つのものにしたのでよろしくお願いします.

    キャンセル

  • 2017/02/05 11:05

    解決しました! 説明が至らずミスも多くすみませんでした...
    ありがとうございました

    キャンセル

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

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

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

  • C

    3991questions

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

  • アルゴリズム

    427questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • ソート

    71questions

    複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

  • データ構造

    48questions

    データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

  • ハッシュ

    41questions

    ハッシュは、高速にデータ検索を行うアルゴリズムのことです。