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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

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

アルゴリズム

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

ソート

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

データ構造

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

ハッシュ

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

Q&A

解決済

1回答

3185閲覧

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

退会済みユーザー

退会済みユーザー

総合スコア0

C

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

アルゴリズム

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

ソート

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

データ構造

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

ハッシュ

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

0グッド

0クリップ

投稿2017/01/20 03:45

編集2017/01/31 00:48

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

###発生している問題・試したこと
データ構造を維持してなるべく高速なソートを行いたいのですが実装ができません.
以下のマージソートで実装してみましたが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

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

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

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

  • デバッグしましょう

不当メモリーアクセスは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するとしてもあなたがやろうとしたことが盛り込まれたコードを提示してもらったほうがやりやすいです。

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

  1. merge_listでのWORDの比較

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

  1. WORDのnextの使い方

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

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

さて、ハッシュテーブルへ全単語を登録し終えた時点では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);

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

投稿2017/01/20 06:42

編集2017/01/31 06:01
KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2017/01/31 00:50

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

退会済みユーザー

2017/02/05 02:05

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問