編集履歴

質問編集履歴

ソースコード修正しました

2017/01/31 00:49

投稿

退会済みユーザー

スコア0

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -8,79 +8,349 @@
 データ構造を維持してなるべく高速なソートを行いたいのですが実装ができません.
-以下のマージソートで実装してみましたがSegmentation faultが出力されました.
+~~以下のマージソートで実装してみましたがSegmentation faultが出力されました.~~
+以下のソースコードで実行してもソートされません.
 ご教授よろしくお願いします.
+**ソースコード修正しました(getwordは修正できていません).**
+ハッシュテーブルの各セルの末尾を連結して1つのリストとするのが有効だと考えました.
 ```C
+#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 *xs, WORD *ys)
+WORD *merge_list(WORD *w1, WORD *w2);
+WORD *merge_sort(WORD *w);
+int main()
 {
+    char w[WORDLEN];
-  WORD head;
+    WORD *p;
+    int i;
-  WORD *wd = &head;
+    init_word();
-  while (xs != NULL && ys != NULL) {
+    while (getword(w, WORDLEN) != NULL) {
-    if (xs->count <= ys->count) {
-      wd->next = xs;
-      wd = xs;
-      xs = xs->next;
+        p = add_word(w);
-    } else {
-      wd->next = ys;
+        if (p == NULL) {
+            fprintf(stderr, "Too many words\n");
-      wd = ys;
+            exit(1);
-      ys = ys->next;
-    }
+        }
+        p->count++;
-  }
+    }
-  if (xs != NULL)
-    wd->next = xs;
+    for (i = 0; i < SIZE; i++) {
-  else
-    wd->next = ys;
+        for (p = word[i]; p != NULL; p = p->next) {
-  return head.next;
+            printf("%d %s\n", p->count, p->str);
-}
+        }
+    }
+    return 0;
+}
-WORD *merge_sort(WORD *wd, int n)
+void init_word()
 {
-  if (n == 1) {
-    wd->next = NULL;
-    return wd;
-  } else {
-    int m = n / 2;
-    WORD *xs = wd;
-    for (int i = 0; i < m; i++) xs = xs->next;
-    return merge_list(merge_sort(wd, m), merge_sort(xs, n - m));
-  }
+    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) );
 }
@@ -92,312 +362,52 @@
-###該当のソースコード
+####実行結果
-以下はソートせずに出現回数を出力します.
-```C
-#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);
-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;
-    p->next = word[i];
-    word[i] = p;
-    return p;
-}
-// 単語を大文字に変換する
-// n: 変換する単語の最大文字数
-// 戻り値: 格納する単語の先頭ポインタ
-char *getword(char *w, int n)
-{
-  int c;
-  int i = 0;
-  if (n <= 0 || feof(stdin))
-    return NULL;
-  c = getchar();
-  // cがファイルの末尾でなくアルファベットでない限り標準入力から文字をcに格納する
-  while (c != EOF && ! isalpha(c)) {
-    c = getchar();
-  }
-  // ファイルの末尾ならばNULLを返す
-  if (c == EOF)
-    return NULL;
-  // cがアルファベットである限り大文字に変換しwに格納
-  while (isalpha(c)) {
-    if (i < n - 1)
-      // cを大文字に変換したものをw[i]に格納後, インデックスiをインクリメントする
-      w[i++] = toupper(c);
-    // 標準入力からcに文字を格納する
-    c = getchar();
-  }
-  // 末尾にヌル文字を追加
-  if (i < n)
-    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;
-}
 ```
+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
 ```
-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
-```