C 単語の出現頻度を調べる

Question

前提

C言語で文章中の出現頻度を計算、表示しさらに標準入力されたwordの出現頻度を表示するプログラムを作っています。

実現したいこと

, . ' : ; ( ) 　空白（スペース）などの特殊文字で区切る。
大文字は小文字にする
文章中の単語を二分探索木に格納する。
出現頻度の計算、表示、検索

発生している問題・エラーメッセージ

出力結果が想定通りでない
例
89 apple
23 grape
2 lemon
1200種類の単語を登録
としたいです。

該当のソースコード

試したこと

出力結果が想定通りになりません。

補足情報（FW/ツールのバージョンなど）

gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0

Comments

[ambitious]

元のプログラムではファイル名は実在するファイルにしてあり、開くことが出来ます。

[otn]

segmentation fault は、どの行でですか？

[tatsu99]

ファイルの内容を提示すると、良い回答がつきやすくなります。

[melian]

以下の部分で、c がアルファベットの場合は無限ループになって、str[i] = c; で範囲外アクセスが発生しているのでしょう。

while (c != 32 && c != 44 && c != 46 && c != 58 && c != 59 && c != 28 && c != 29)
{
if (65 <= c && c <= 90)
c += 32;
str[i] = c;
i++;
}

[ambitious]

指摘箇所を修正し、faultは出なくなりましたが出力結果が想定通りではありません。

[ambitious]

**************************
入力ファイル名: *.txt

� *** 単語の出現頻度 ***
1 � 0種類の単語を登録

単語, または00を入力して下さい（00なら終了します）:

出力結果です。

[ambitious]

Section 1. Full faith and credit shall be given in each state to the public acts, records, and judicial proceedings of every other state. And the
Congress may by general laws prescribe the manner in which such acts, records, and proceedings shall be proved, and the effect thereof.

Section 2. The citizens of each state shall be entitled to all privileges and immunities of citizens in the several states.

A person charged in any state with treason, felony, or other crime, who shall flee from justice, and be found in another state, shall on demand
of the executive authority of the state from which he fled, be delivered up, to be removed to the state having jurisdiction of the crime.

読み込むファイルの一部です。

[jimbe]

main の最初の(fgetc をしている) while 文の中で、変数 i がどのような変化をするか確認しては如何でしょうか。

なお、ご提示のコードでは何か所かで return が足りません。

Answer 1

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

#define SEPARATORS ",.':;()"

typedef struct cell {
  char key[20]; // 単語
  int count;    // 単語の登録回数（出現頻度）
  struct cell *left, *right;
} CELL;

#define TBRANCH(a,p) ((a) > 0 ? &(p)->right : &(p)->left)

/* 2分探索木に単語を登録する関数 */
CELL* tinsert(CELL *p, char *name) {
  if(p == NULL) {
    p = malloc(sizeof(CELL));
    strcpy(p->key, name);
    p->count = 1;
    p->left = p->right = NULL;
    return p;
  }

  int a = strcmp(name, p->key);
  if(a == 0) {
    p->count ++;
  } else {
    CELL **q = TBRANCH(a, p);
    *q = tinsert(*q, name);
  }
  return p;
}

/* 間順走査を行う関数 */
int inorder(CELL *p) {
  if(p == NULL) return 0;

  int count = inorder(p->left);
  printf("%d %s\n", p->count, p->key);
  return count + 1 + inorder(p->right);
}

/* 2分探索木を探索する関数 */
CELL* tsearch(CELL *p, char *name) {
  if(p == NULL) return NULL;

  int a = strcmp(name, p->key);
  if(a == 0) return p;
  return tsearch(*TBRANCH(a, p), name);
}

CELL *tread(char *filename) {
  printf("\n**************************\n");
  printf("入力ファイル名: %s\n\n", filename);

  FILE *fp;
  if((fp = fopen(filename, "r")) == NULL) {
    printf("File open error \n");
    return NULL;
  }

  CELL *root = NULL;
  int c, i = 0;
  char str[256];
  while((c = fgetc(fp)) != EOF) {
    if(c > ' ' && !strchr(SEPARATORS, c)) {
      str[i++] = tolower(c);
      str[i] = '\0';
      continue;
    }
    if(i == 0) continue;

    printf("%s\n", str);
    root = tinsert(root, str);
    i = 0;
  }
  fclose(fp);

  return root;
}

void tfree(CELL *p) {
  if(p == NULL) return;

  tfree(p->right);
  tfree(p->left);
  free(p);
}

int input(char *buf) {
  printf("\n単語, または00を入力して下さい（00なら終了します）:  ");
  scanf("%s", buf);
  return strcmp(buf, "00") != 0;
}

int main(void) {
  CELL *root = tread("test.txt");
  if(root == NULL) exit(1);

  printf("*** 単語の出現頻度 ***\n");
  printf("%d種類の単語を登録\n", inorder(root));

  for(char name[256]; input(name); ) {
    CELL *p = tsearch(root, name);
    if(p == NULL) printf("%sの単語は登録されていません!\n", name);
    else printf("%sの出現頻度: %d\n", name, p->count);
  }
  printf("終了します．\n");

  tfree(root);
  exit(0);
}

実行結果

**************************
入力ファイル名: test.txt

section
1
full
faith
and
credit
shall
be
given
in
 :
(中略)
 :
be
removed
to
the
state
having
jurisdiction
of
the
crime
*** 単語の出現頻度 ***
1 1
1 2
1 a
2 acts
1 all
7 and
1 another
1 any
1 authority
6 be
 :
(中略)
 :
1 states
1 such
10 the
1 thereof
4 to
1 treason
1 up
2 which
1 who
1 with
68種類の単語を登録

単語, または00を入力して下さい（00なら終了します）:  the
theの出現頻度: 10

単語, または00を入力して下さい（00なら終了します）:  abc
abcの単語は登録されていません!

単語, または00を入力して下さい（00なら終了します）:  00
終了します．

Answer 2

1.ファイル名(sfn)が".txt"担っているが、C言語ではワイルドカードを指定して読み込むことはできません。
具体的な実際に存在するファイル名を指定しなければいけません。（word.txtとしました）
それともファイル名を公開したくなくて.txtとしたのでしょうか。
いずれにせよ、*.txtではエラーになります。

２．char c は一般論として、int型で確保したほうが良いです。
（getcの戻り値がint型のためです。EOFの場合、-1が返り、文字を読み込んだ場合は0～255の値が返ります）
ファイル内の文字が全てASCII(7ビット)なら、問題ありませんが、漢字を含む場合、0x80以上の文字が返り
char 型で扱うと、0x80以上の場合対応できなくなります。
（今回の場合はファイル内の文字が全てASCII(7ビット)なのでchar型でも対応は可能です）

３．char str[256]の初期化が行われていません。

４．特殊文字が出現した場合を判定するのではなく、A-Z,a-z以外の文字が出現した場合を、
区切り文字として扱うべきです。いくつか区切り文字をならべてますが、タブキー、改行コード等がいろいろ
漏れています。
従って、
①A-Z,a-zの場合、単語としてstrに格納
②上記以外の場合、strが空でなければ、tinsertを呼び出して単語登録
のようにすべきです。

５．tinsertで、p->right,p->leftがNULLの時、mallocして単語を登録しますが、
そのmallocしたアドレスが設定されていません。

６．inorderのカウントの方法がおかしいので修正しました。

以上を反映すると以下のようになります。

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

struct node
{
    char key[20]; // 単語を格納
    int count;    // 単語の登録回数（出現頻度）を格納
    struct node *left, *right;
};
typedef struct node CELL;

CELL *tinsert(CELL *, char *); /* 2分探索木に単語を登録する関数 */
int inorder(CELL *);           /* 間順走査を行う関数 */
CELL *tsearch(CELL *, char *); /* 2分探索木を探索する関数 */

int main(void)
{
    CELL *root, *p, *q;
    char name[20];
    char sfn[] = "word.txt";        //修正
    FILE *sfp;
    int  c;                         //修正
    char str[256];
    int a, i, j = 0;
    if ((sfp = fopen(sfn, "r")) == NULL)
    {
        printf("File open error \n");
        exit(1);
    }

    printf("\n**************************\n");
    printf("入力ファイル名: %s\n\n", sfn);
    //追加開始
    for (i = 0; i < 20; i++)
    {
        str[i] = '\0'; //初期化
    }
    //追加終了
    root = NULL;
    i = 0;
    while ((c = fgetc(sfp)) != EOF)
    {
        //修正開始
        if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))
        {
            if (c >= 'A' && c <= 'Z')
                c += 32;
            str[i] = c;
            i++;
            continue;
        }
        else
        {
            if (strcmp(str,"") == 0) continue;
        }
        //修正終了
        if (j == 0)     //修正
        {
            printf("%s\n", str);        //修正
            root = tinsert(root, str);
            j++;
            for (i = 0; i < 20; i++)
            {
                str[i] = '\0'; //初期化
            }
            i = 0;
        }
        else if (j == 1)
        {
            printf("%s\n", str);        //修正
            q = tinsert(root, str);
            for (i = 0; i < 20; i++)
            {
                str[i] = '\0'; //初期化
            }
            i = 0;
        }
    }

    printf("*** 単語の出現頻度 ***\n");

    a = inorder(root);
    printf("%d種類の単語を登録\n", a);

    while (1)
    {
        printf("\n単語, または00を入力して下さい（00なら終了します）:  "); /*** 00 が入力されるまで繰り返す***/
        scanf("%s", name);
        if (strcmp(name, "00") == 0)
            break;
        else
        {
            q = tsearch(root, name);
            if (q != NULL)
                printf("%sの出現頻度: %d\n", name, q->count);
        }
    }
    printf("終了します．\n");

    fclose(sfp);

    return 0;
}

CELL *tinsert(CELL *p, char *name)
{
    int ind;
    CELL *wp;                               //追加
    if (p == NULL)
    {
        p = (CELL *)malloc(sizeof(CELL));
        strcpy(p->key, name);
        p->count = 1;
        p->left = p->right = NULL;
        return p;
    }
    //修正開始
    else if (strcmp(name, p->key) > 0){
        wp = tinsert(p->right, name);
        if (p->right == NULL){
            p->right = wp;
        }
    }else if (strcmp(name, p->key) < 0){
        wp = tinsert(p->left, name);
        if (p->left == NULL){
            p->left = wp;
        }
    //修正終了
    }else if (strcmp(name, p->key) == 0){
        p->count += 1;
        return p;
    }
}
int inorder(CELL *p)
{
    int count = 0;
    //修正開始
    if (p != NULL)
    {
        count++;
        if (p->left != NULL){
        	count += inorder(p->left);
        }
        if (p->right != NULL){
        	count += inorder(p->right);
        }
    }
    return count;
    //修正終了
}
CELL *tsearch(CELL *p, char *name)
{
    int ind;

    if (p != NULL)
    {
        if (strcmp(name, p->key) > 0)
            tsearch(p->right, name);
        else if (strcmp(name, p->key) < 0)
            tsearch(p->left, name);
        else if (strcmp(name, p->key) == 0)
            return p;
    }

    else
    {
        printf("%sの単語は登録されていません!\n", name);
        return NULL;
    }
}

Answer 3

最初の while文が無限ループになります。

追記
修正版の && 48 > c && c > 57 で、そんな c は存在せず、
str[i] = c; は実行されません。
また、48 や 57 と書かずに '0' や '9' と書いたほうがいいでしょう。

Comments

[ambitious]

ご回答ありがとうございます。
修正版を上げましたので、ご参照よろしくお願いいたします。

Answer 4

まず、

if ((sfp = fopen(sfn, "r")) == NULL)

ファイル名が不正ですね