回答編集履歴

1

追記

2017/01/31 06:01

投稿

KSwordOfHaste
KSwordOfHaste

スコア18392

test CHANGED
@@ -47,3 +47,65 @@
47
47
  return w;
48
48
 
49
49
  ```
50
+
51
+
52
+
53
+ ---
54
+
55
+ 追記:
56
+
57
+ コードが変更されたので拝見しました。しかし・・・ソート関数を用意したものの肝心のmerge_sortをどう呼び出したかがコードにないです。やってみて異常終了してしまったのでmerge_sortのコール部分をそっくり取ってしまったんだと思いますが、アドバイスする側からいえば例えcore dumpするとしてもあなたがやろうとしたことが盛り込まれたコードを提示してもらったほうがやりやすいです。
58
+
59
+
60
+
61
+ ではありますが・・・一応質問者さんが陥っていると思える間違いを推測してコメントします。
62
+
63
+
64
+
65
+ 1. merge_listでのWORDの比較
66
+
67
+ 出現頻度順にソートしようとしているのにw1->strとw2->strを比較しています。ここは単なる勘違いだと思います。w1->count >= w2->countとすべきですね。
68
+
69
+
70
+
71
+ 2. WORDのnextの使い方
72
+
73
+ このメンバーの目的は「同一ハッシュ値を持つ複数のWORDを繋いでおくこと」です。しかしmerge_xxx関数の実装をみると並べ替えた結果を繋ぐ目的でnextを使用しています。元々の問題設定では「データ構造を維持して」とありますがnextを異なる目的で使っているためマージソートをするとハッシュテーブルの構造は破壊されます。どうしたかったのかはっきりわかりませんが、ハッシュテーブルの構造は全単語を登録し終えたら壊してもよいと仮定して以降を考えました。
74
+
75
+
76
+
77
+ 3. マージソートの入力を作る
78
+
79
+ さて、ハッシュテーブルへ全単語を登録し終えた時点ではnextには全単語は繋がっていませ。前述のようにハッシュ値が衝突しているWORDだけが繋がります。そこでマージソートを呼び出す際にすべきことはwordテーブルに登録された全WORDをnextによって繋げることです。そうしてつなげた上でチェーンの先頭をmerge_sortに渡すようにしてみてください。
80
+
81
+
82
+
83
+ ```c
84
+
85
+ WORD *head = NULL;
86
+
87
+ for (i = 0; i < SIZE; i++) {
88
+
89
+ p = word[i];
90
+
91
+ if (p != NULL) {
92
+
93
+ while (p->next != NULL)
94
+
95
+ p = p->next;
96
+
97
+ p->next = head;
98
+
99
+ head = word[i];
100
+
101
+ }
102
+
103
+ }
104
+
105
+ head = merge_sort(head);
106
+
107
+ ```
108
+
109
+
110
+
111
+ 蛇足ながらハッシュテーブルの構造は壊れてしまうのでソート済みの単語をダンプするにはもはやwordは使えません。上のコード例にあるheadから始めてnextを辿りながらWORDの内容を印字してください。