２分探索木を用いた探索

[マサキ]

タイトルの通り、２分探索木を用いた探索のプログラムを作っています。
これは、あるテキストファイルに入っている単語の数を調べるものです。
プログラムは添付しておきました。また、使うテキストファイルも添付しておきます。
ここで条件として、

「文章には, ; : ( )などの記号が入っているのでそれらを取り除いてから格納すること。また、数字が含まれている単語は格納せず、文章中にある大文字は小文字に変換してから格納すること」

という条件があるのですが。これのやり方がわかりませんでした。
無能な私は、元のテキストファイルをいじって記号を消し、大文字を小文字に変えようとしてました。
このような作業をプログラムとして作るためには、どのようにすればいいのでしょうか？
教えていただけると助かります。　宜しくお願いします。

[box]

> 「文章には, ; : ( )などの記号が入っているのでそれらを取り除いてから格納すること。
> また、数字が含まれている単語は格納せず、文章中にある大文字は小文字に変換してから格納すること」

scanf関数を使い、"00"で終了するのは必須条件ですか？
もし必須ではないなら、改行が見つかるまで1行分を読み込むfgets関数を
使ってみてはいかがでしょうか。

fgets関数を使って1行分を読み込んだとします。
そのデータから単語群を切り出すためには、strtok関数を使うとよいでしょう。
strtok関数の第2引数には、単語の区切りを表わす文字群（空白も可）を指定します。

切り出した単語に'0'～'9'の数字を含んでいるかどうかを調べるには、
isdigit関数を使うとよいでしょう。

英字だけを含む単語を取得したら、tolower関数を使って小文字に変換すればよいでしょう。

isdigit関数とtolower関数は1文字ずつ扱いますので、1つの単語全体を扱うには
その単語の文字数を求める関数が必要です。それはstrlen関数です。

fgets, strtok, isdigit, tolowerおよびstrlenは、すべて標準関数です。
各関数の引数の指定方法については、書籍やネットなどで調べてみてください。

[マサキ]

残念ながら00の入力で終了というのは必須条件なんですよ.....
その場合だとやり方が変わってくるのでしょうか？？

とりあえずは、fgets, strtok, isdigitおよびtolowerについて調べてみます。

[box]

では、scanf()は"00"入力による終了時だけに使うようにして、
テキストファイルからの入力についてはfgets()を使うようにするとよいでしょう。

なお、"00"をscanf()で標準入力から受け取りますので、
fgets()の第3引数に指定するファイルハンドルは標準入力（stdin）以外に
する方がよいでしょう。
その場合、単語群を格納したテキストファイルの読み込み用の
ファイルハンドルを用意することになります。
したがって、fopen(), fclose()という標準関数も必要です。

[マサキ]

boxさん、せっかくアドバイスくれたのに返事が遅くなって大変申し訳ございません。他の教科の課題に追われていたので........

教えていただいたことを参考に先ほどのプログラムを書き換えてみました。まぁ書き換えたといっても、文字を変換させる部分だけですが。
しかし、まだわからないことがあります。添付したファイルを見ていただければわかると思いますが、文字が数値だったり記号だった場合の処理が未完成です。これらの文字を取り除きたい場合は、どのようにすればいのでしょうか？
宜しくおねがいします。

[box]

テキストファイルから1行分読み取れる間
　　1行分に含んでいる単語の候補（ここでは、まだ候補の段階）を取り出せる間、
　　　　単語候補の内容をチェックする
　　　　　　1文字でも数字を含んでいたら候補から除外する
　　　　　　すべてが英数字から成っていたら
　　　　　　　　単語を小文字に変換する→この時点で、候補から登録対象に昇格
　　　　　　　　二分探索木の中の登録すべき場所を見つける
　　　　　　　　二分探索木に登録する


という処理を、単語群を含むテキストファイルのデータがある間、繰り返します。
初めの2行は「～できる間」という表現をしています。
C言語のwhile文によるループに相当します。

「1行分を読み取る」というループがあって、その中には
「1行分に含んでいる（複数の）単語を切り出す」というループがあります。

[マサキ]

while( fscanf(sfp,"%s",name) != EOF ){
l=strlen(name);

for(i=0 ; i<=l-1 ; i++){
if(isalnum(name)==0 || isdigit(name)!=0){
for(n=i ; n<=l-1 ; n++){
name[n]=name[n+1];
}
}
else{
name=tolower(name);
}
}

root = tinsert(root,name);
}

このようにしたら、上手く作動しました。アドバイスありがとうございました。
とても助かりました。
あと最後に質問なのですが、登録した単語の種類の数を表示させるにはどのようにすればいいのでしょう？
私は木構造に登録するときにカウンターを一つずつ増やして、最後にその数を表示させたのですが、それではダブった単語も数に含まれてしまうため、上手くできませんでした。

[フリオ]

　
　ソースは、読みやすいように"pre"タグで字下げしてほしい。


　提示のコードだと、"foo-bar"は"foobar"、"foo--bar"は"foo-bar"、
"foo2nd"は"foond"、"foo22nd"は"foo2nd"として登録されてしまいますが、
課題の条件は、
"foo-bar"や"foo--bar"は"foo"と"bar"として登録し、
"foo2nd"や"foo22nd"は登録しない。
ということではないのでしょうか。


> 登録した単語の種類の数を表示させるにはどのようにすればいいのでしょう？

　単語を、新しく登録したときにカウンターをひとつ進め、
それ以外は何もしなければ、総登録語数が出ます。
　

[マサキ]

フリオさん、ありがとうございます。
たしかにそうですね....すっかり完成したと勘違いしてました。
では、どのようにすれば良いのでしょうか？＾＾；
私の力でこれ以上は思い付きませんでした.....

[box]

入力ファイルを１行分読んだ後、strtok関数を使って
単語群を切り出していけばよいと思います。

[マサキ]

色んなサイトを見て標準関数について調べたのですが、最終的に混乱してしまい何が何だかわからなくなってしまいました↓
文字を操作する部分だけ、プログラム貼っておきます。一応コンパイルはできたのですが、セグメントエラーです。
間違いだらけのプログラムだと思いますが、アドバイス宜しくお願いします。

[box]

例題の一節をお借りして、こんなコードを書いてみました。
参考になるでしょうか。

単語の途中に、わざと数字を含めているところがあります。
また、入力用ファイルをfgets()で読むことを想定して、
各行の末尾に相当する箇所に'\n'を入れてあります。

出力結果のカッコ内の数値はその単語の文字数で、
矢印の後ろに小文字変換後の単語を出力していれば二分探索木に登録する必要があり、
×印が付いていれば登録する必要がありません。

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

int main(void)
{
	char *str[/url]= {
		"Before he enter on the exe7cution of his office, he shall take the follow8ing\n",
		"oath or affirmation:--\"I4 d2o solemnly swear (or affirm) that I will\n",
		"faithfully execu5te the office of President of the United States, a9nd will\n",
		"to the be0st of my ability, preserve, protect and defend the Constitution\n",
		"3of the United States.\"\n",
	};
	char dlm[/url] = " .,():-\n\"";
	char *token;
	int valid, i, j;
	
	for (i = 0; i < sizeof(str) / sizeof(str[0]); i++) {
		token = strtok(str, dlm);
		valid = 1;
		while (token) {
			printf("%s(%d)→", token, strlen(token));
			for (j = 0; j < strlen(token) && valid; j++) {
				token[j] = tolower(token[j]);
				if (isdigit(token[j]))
					valid = 0;
			}
			printf("%s\n", valid ? token : "×");
			token = strtok(NULL, dlm);
			valid = 1;
		}
	}
	return 0;
}

[Justy]

　えーと、横槍ですみません。
　strtokが ROM領域にある文字列を破壊しているようにみえます。

[box]

もしかすると、*str[/url]ではなく、例えばstr[/url][256]でなければならなかったのでしょうか？
何年C言語に携わっていてもまだまだ未熟ですみません。

[Justy]

＞もしかすると、*str[/url]ではなく、例えばstr[/url][256]でなければならなかったのでしょうか？
　そうですね、それなら大丈夫だと思います。

　文字リテラルへの書き込みは未定義な動作になりますんで、文字通りプログラムが
ROMに焼かれていたりすると、リテラルが ROM側にあったりするので、非常にまずいことに・・・。

[フリオ]

　
　テキストから単語を取り出し、数字が含まれていれば()でくくって
表示します。サンプルのテキストは、boxさんのをお借りしました。

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

#define MAXLEN 256
#define TOKEN " "

void Func(char *str)
{
	char *sptr;
	
	for(sptr = str; *sptr != '\0'; sptr ++){
		if(isalnum(*sptr)) *sptr = tolower(*sptr);
		else *sptr = TOKEN[0];
	}
	for(sptr = strtok(str, TOKEN); sptr != NULL; sptr = strtok(NULL, TOKEN)){
		if(strcspn(sptr, "0123456789") < strlen(sptr)) printf("(%s)  ", sptr);
		else printf("%s  ", sptr);
	}
	return;
}

int main(void)
{
	FILE *fp = fopen("test.txt", "r");
	char str[MAXLEN];
	
	if(!fp){
		puts("Error : File not Opened");
		return 1;
	}
	while(fgets(str, MAXLEN, fp) != NULL) Func(str);
	fclose(fp);
	return 0;
}

　
test.txt

Before he enter on the exe7cution of his office, he shall take the follow8ing
oath or affirmation:--\"I4 d2o solemnly swear (or affirm) that I will
faithfully execu5te the office of President of the United States, a9nd will
to the be0st of my ability, preserve, protect and defend the Constitution\n
3of the United States.\"

[マサキ]

boxさんJustyさんフリオさんありがとうございました。また、返事が遅くなって申し訳ありません。
掲載して頂いたプログラムを参考に少し書き直したのですが、やはりセグメントエラーになってしまいます。
やはり、文字列を読みこみ、単語ごとに区切り、それぞれの単語を判定する部分が上手く作動していないのだと思います。
プログラム貼っておきます。もしよろしければ、おかしな点を教えてください。

ちなみに、文字列読みこみ→単語の判定の部分は45～55行目くらいです。
宜しくお願いします

[box]

> char name[20];
> while( fgets(name,1000,sfp) != NULL ){ //ファイルから文字列を１行分読み込み、nameに格納//

name[/url]の実際の大きさと、読み込んでいる領域の大きさが
食い違っています。

[マサキ]

boxさん、ありがとうございます。こんな基本的なところで間違えていた自分が恥ずかしいです。
おかげでちゃんと作動するようになりました！

しかし...........まだどこかおかしいようです。
実行結果のヒントとして　
americaの出現頻度：４　
yearの出現頻度:１１
というものが与えられています。
しかし、このプログラムを実行させてみるとこのような出現頻度にはなりません。
どうやら、本来の頻度よりも少なくなってしまっているようです。
これは、本来登録するべき単語が木に登録されていないということですよね？
やはり「ファイルから読み取り→単語を切り出し→木に登録する」という部分が何処か間違っているのでしょうか？

　

[box]

strtok()の戻り値がNULLになる（つまり、その行にある単語をすべて取得し終わった）場合のことを
考慮していませんね。
例えば、私が2007/07/02(月) 23:37に投稿したサンプルコードと見比べてみてください。

[マサキ]

boxさんが乗せてくれたプログラムに習って作ったのですが、駄目でした↓
見比べてみても何処が違うのかわかりません。

[フリオ]

　
　一度に解決しようとせず、
"プログラムにさせたいこと" と "プログラムがしていること" が
一致しているかどうか、一つずつ確認しながら進んだほうが
いいんじゃないでしょうか。
　

[box]

> boxさんが乗せてくれたプログラムに習って作ったのですが、駄目でした↓
> 見比べてみても何処が違うのかわかりません。

どんな風にだめなのでしょうか？
fgets()で読み込む長さは20バイトでよいのでしょうか？
入力用のテキストファイルの１行の長さは、もっと長いのではありませんか？

[マサキ]

フリオさんに言われたとおり、簡単なテキストを適当に作りプログラムを実行させてみました。
そうすることで、、自分のプログラムが明らかに間違っていることに気づきました。

a.tex
dog,cat,fish,rat,ca2,fd2

このようなテキストに対して実行させたところ実行結果が
ca
cat
dog
fish
rat
のようになりました。
数字が含まれている単語の処理がちゃんと行われていないのだと思いました。
しかし数字が含まれている文字は ca2 fd2　と二つあるのに、fd2の方はちゃんと処理されています。
何故このような結果になってしまうのでしょうか？

[マサキ]

boxさん
2007/07/03(火) 22:11 に
　name[/url]の実際の大きさと、読み込んでいる領域の大きさが食い違っています。
といわれたので20にしたのですが........
実際の大きさと、読み込んでいる領域の大きさが食い違っているとはこのよな意味ではないのでしょうか？

あと、どのように間違っていたかというと
①実行結果にところどころ空行が混じっている。
②たとえばzensといったように、実際のテキストに含まれていない単語が出てきてしまう。

単語の切り出し方にどこか間違いがあるため、②番のようなミスが起こっているのだと思うのですが、①についてはなんでこのようになるのかわかりません。
boxさんに掲載して頂いたプログラムを参考に作ったのですが、どこか誤りがあるでしょうか？
宜しくお願いいたします。

[box]

> 　name[/url]の実際の大きさと、読み込んでいる領域の大きさが食い違っています。
> といわれたので20にしたのですが........

20という数値の根拠は何でしょうか？
入力用テキストファイルの１行は、何バイトありますか？
fgets()で１行分丸ごと読むのであれば、そのための領域の大きさは、
入力用テキストファイルの１行の最大長以上でなければなりません。
入力用テキストファイルを見る限り、20では明らかに不足しています。

> ①実行結果にところどころ空行が混じっている。
> ②たとえばzensといったように、実際のテキストに含まれていない単語が出てきてしまう。

zensは、citizensという単語の一部です。
これらの原因は、ひとえにfgets()の第２引数の大きさによります。
入力用テキストファイルの１行は明らかに20バイト以上であるにもかかわらず、
fgets()で20バイトずつ読み込むと、単語の途中で区切られてしまいます。

[box]

> ①実行結果にところどころ空行が混じっている。

fgets()は、行末の'\n'を含めて読み取ります。
今回のプログラムの仕様では、おそらく'\n'は単語を構成する文字の対象外でありましょう。
そこで、strtok()の第２引数で指定している
単語区切り文字に'\n'を含める必要があります。

[マサキ]

では、少し改良を加えてみます。
まず、
strtok()の第２引数に'\n'を加えてみました。
そうしたところ、ところどころの改行はなくなりました。
ありがとうございます。
次に
fgets()の第2引数を変えてみます。
fgets()の第2引数は読み込む文字数の最大値ですよね？
なので、１００としてみます。
そうしたところ、セグメントエラーになってしまいました。

fgets()の第2引数が20のときはちゃんと動くのに、100にするとセグメントエラー.........
これはどういうことでしょう？＾＾；

[box]

> fgets()の第2引数が20のときはちゃんと動くのに、100にするとセグメントエラー.........

name[/url]の定義も100にしましたね？

[マサキ]

nameとstrtokを両方とも100にしたら上手く作動しました。
boxさん、ありがとうございました。
しかし、最後の最後でもう一つエラーを発見してしまいました。
゛を単語を切り出す条件にいれてませんでした。
゛をstrtok関数の第２引数に追加した所、エラーになってしまいます。
strtok関数で第２引数に゛を追加するにはどのようにすればいいのでしょうか？

[box]

\"
です。

[マサキ]

おかげさまでプログラムが完成しました。ありがとうございました。
まだまだ未熟者ですが、これからも頑張っていきたいと思います。
また何かあった時は、よろしくお願いします。