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

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

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

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

C
1#include <stddef.h>
2#include <stdio.h>
3#include <stdlib.h>
4#include <ctype.h>
5#include <string.h>
6
7#define WORDLEN 50
8#define SIZE 32
9
10struct wd {
11    struct wd *next;
12    char *str;
13    int count;
14};
15typedef struct wd WORD;
16
17WORD *word[SIZE];
18
19void init_word();
20WORD *add_word(char *);
21char *getword(char *, int);
22int hash(char *w);
23WORD *merge_list(WORD *w1, WORD *w2);
24WORD *merge_sort(WORD *w);
25
26int main()
27{
28    char w[WORDLEN];
29    WORD *p;
30    int i;
31
32    init_word();
33    while (getword(w, WORDLEN) != NULL) {
34        p = add_word(w);
35        if (p == NULL) {
36            fprintf(stderr, "Too many words\n");
37            exit(1);
38        }
39        p->count++;
40    }
41
42    for (i = 0; i < SIZE; i++) {
43        for (p = word[i]; p != NULL; p = p->next) {
44            printf("%d %s\n", p->count, p->str);
45        }
46    }
47    return 0;
48}
49
50
51void init_word()
52{
53    int i;
54
55    for (i = 0; i < SIZE; i++)
56        word[i] = NULL;
57}
58
59
60WORD *add_word(char *w)
61{
62    char *s;
63    WORD *p;
64    int i;
65
66    i = hash(w);
67    for (p = word[i]; p != NULL; p = p->next) {
68        if (strcmp(w, p->str) == 0)
69            return p;
70    }
71    s = (char *)malloc(strlen(w) + 1);
72    if (s == NULL)
73        return NULL;
74    strcpy(s, w);
75    p = (WORD *)malloc(sizeof(WORD));
76    if (p == NULL)
77        return NULL;
78    p->str   = s;
79    p->count = 0;
80    if (word[i] == NULL && i != SIZE - 1)
81        p->next = word[i + 1];
82    p->next  = word[i];
83    word[i]  = p;
84    return p;
85}
86
87char *getword(char *w, int n)
88{
89    int i = 0;
90    int c;
91
92    if (n <= 0 || feof(stdin))
93	return NULL;
94    c = getchar();
95    while (c != EOF && ! isalpha(c)) {
96	c = getchar();
97    }
98    if (c == EOF)
99	return NULL;
100    while (isalpha(c)) {
101	if (i < n - 1) {
102	    w[i] = toupper(c);
103	    i++;
104	}
105	c = getchar();
106    }
107    w[i] = '\0';
108    return w;
109}
110
111int hash(char *w)
112{
113  int i;
114  unsigned int h = 0;
115
116  for (i = 0; w[i] != '\0'; i++)
117    h = 65599 * h + w[i];
118  return h % SIZE;
119}
120
121WORD *merge_list (WORD *w1,WORD *w2) {
122    WORD out, *w;
123    w = &out;
124
125    while ( w1 != NULL && w2 != NULL ) {
126        if ( w1->str <= w2->str ) {
127            w->next = w1;
128            w = w1;
129            w1 = w1->next;
130        }
131        else {
132            w->next = w2;
133            w = w2;
134            w2 = w2->next;
135        }
136    }
137
138    if ( w1 == NULL ) {
139        w->next = w2;
140    }
141    else {
142        w->next = w1;
143    }
144
145    return out.next;
146}
147
148WORD *merge_sort (WORD *w) {
149    WORD *a, *b, *y;
150
151    if ( w == NULL || w->next == NULL ) return w;
152
153    a = w;
154    b = w->next->next;
155
156    while ( b!=NULL && b->next!=NULL ) {
157        a = a->next;
158        b = b->next->next;
159    }
160
161    y = a->next;
162    a->next = NULL;
163
164    return merge_list( merge_sort(w),merge_sort(y) );
165}
166
167

####実行結果

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

回答1件

ベストアンサー

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

どんなコードを書いたのかわからない

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

デバッグしましょう

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

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

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

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

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

merge_listでのWORDの比較

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

WORDのnextの使い方

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

マージソートの入力を作る

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

c
1WORD *head = NULL;
2for (i = 0; i < SIZE; i++) {
3    p = word[i];
4    if (p != NULL) {
5        while (p->next != NULL)
6            p = p->next;
7        p->next = head;
8        head = word[i];
9    }
10}
11head = merge_sort(head);