ページ 11

2分探索木

Posted: 2011年7月18日(月) 13:04
by may
英文テキスト(小文字)を読んで、そこに出現する単語とその出現回数を2分探索木に登録するプログラムを作りたいのですが、「//ココ」と書いてある場所がわからないので教えてください。

・長さ1の単語は2分木のノードとしない

よろしくお願いします。

コード:

#include <stdio.h>
#include <stdlib.h>  
#include <string.h>  
#include <ctype.h>  
#define MAXWORD 100

struct tnode {
   char    *word;
   int     count;
   struct tnode *left;
   struct tnode *right;
};

struct tnode *addtree(struct tnode *, char *);
int getword(FILE *, char *, int);
void treeprint(struct tnode *, int);
void freetree(struct tnode *p);
int searchtree(struct tnode *, char *);

int main(int argc, char *argv[])
{
   char word[MAXWORD];
   int i, freq;
   struct tnode *root;
   FILE *fp;
   fp = fopen("ENGLISH.txt", "r");
   root = NULL;
   while (getword(fp, word, MAXWORD) != EOF ) {
     if (word[1] == '\0')
        continue; //
     for (i = 0; word[i] != '\0'; i++)
        word[i] = tolower(word[i]);
     root = addtree(root, word);
   }
   freq = atoi(argv[1]);
   printf("%d回以上出現した単語\n", freq);
   treeprint(root, freq); // freq
   while (scanf("%s", word) != EOF) {
     if ((freq = searchtree(root, word)) == 0)
        printf("単語\"%s\"は登録されていませんs\n" , word);
     else
        printf("単語\"%s\"は回出現していますn", word, freq);
   }
   freetree(root);
   return 0;
}
struct tnode *addtree(struct tnode *p, char *w)
{
   int cond;
   if (p == NULL) {
     p = (struct tnode *) malloc(sizeof(struct tnode));
//ココ(単語とカウントの設定)
     p->left = p->right = NULL;
   }
   else if ((cond = strcmp(w, p->word)) == 0)
//ココあってますか?(カウントを増やす)
    count++;
   else if (cond < 0)
     p->left = addtree(p->left, w);
   else
     p->right = addtree(p->right, w);
   return p;
}

int searchtree(struct tnode *p, char *w){

   int cond, frequency;
   if (p == NULL)
     frequency = 0;

//ココ( 2分探索木の上で単語を探す。再帰的な関数として作る。 )
}
void treeprint(struct tnode *p, int n)
{
//ココ(n回以上出現したものを出力
}
int getword(FILE *f, char *word, int lim)
{
   char *w = word;
   int c;

   while (!isalpha(c = fgetc(f)) && c != EOF)
     ;
   if (c == EOF) // EOF
     return c;
   else
     *w++ = c;
   for ( ; --lim > 0; w++)
     if (!isalpha(*w = fgetc(f)))
        break;
   *w = '\0';
   return word[0];
}
void freetree(struct tnode *p)
{
   if (p != NULL) {
     freetree(p->left);
     freetree(p->right);
     free(p);
   }
}

Re: 2分探索木

Posted: 2011年7月18日(月) 14:24
by non
未完成のプログラムを完成させよという問題で、結局は丸投げなのでしょうか?

まず、全部のプログラムを一度に完成させようとせず、少しづつ完成させてはいかがでしょうか。

mainで、無駄なものを除いて試しましょう。

コード:

	fp = fopen("ENGLISH.txt", "r");
	root = NULL;
	while (getword(fp, word, MAXWORD) != EOF ) {
		if (word[1] == '\0')
			continue; //
		for (i = 0; word[i] != '\0'; i++)
			word[i] = tolower(word[i]);
		root = addtree(root, word);
		puts(word);
	}
	treeprint(root, 1);
この部分ぐらいでしょうか。
まず、addtreeですが、

コード:

		//ココ(単語とカウントの設定)
		p->left = p->right = NULL;
このあとに、countと、wordをセットします。
今のままでは、wordはポインタだけで実体がありませんので、wの文字数の領域をmallocで確保します。

コード:

		//ココあってますか?(カウントを増やす)
		count++;
もちろん、あってません。このままではエラーになるはず。

次にtreeprintですが、出現回数のnはとりあえず無視して、すべての単語と回数を表示するように
作りましょう。ネットで検索すれば、参考になるプログラムがいくらでもあるはずです。
それくらい調べましょう。

それでは、そこまでできたら、そこまでのリストを添付してください。