1時間ごとに更新!Amazon.co.jpで今売れている本トップ100   ショッピングモール


掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板1

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.5426

2分探索木について
投稿者---MoriMori(2006/02/17 14:08:53)


学校の課題で、
2分探索木を用いて、適当な英文ファイルを開いて単語を重複を省いて抽出し、それぞれの出現頻度を数えるプログラム
の作成を課されたのですが、

テキストを単語に分解して、抽出する
というところがわかりません。
なにか参考になるプログラムを教えてください。


また、いまいちわからないのですが、2分探索木とは何なのでしょうか。これを使うことによってどんな利点があるのですか?


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> 2分探索木について 5427 MoriMori 2006/02/17 14:40:36
<子記事> Re:2分探索木について 5429 Blue 2006/02/17 15:00:31
<子記事> Re:2分探索木について 5433 επιστημη 2006/02/18 21:04:58


No.5427

2分探索木について
投稿者---MoriMori(2006/02/17 14:40:36)


すみません。一応自分で作成したプログラムを載せときます。
コンパイルはできるようにはしたのですが、中身はできてません。
(すみませんタグのの使い方がわかりません)

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

#define WORD 500    /*総単語数を500*/

struct tree {
char *word;
int count;
struct tree *left, *right;
};

struct tree *insertcount(struct tree *ptree, char *word);
struct tree *creatnode(char *word);
int getword(char *word, int limit);
void printtree(struct tree *p);

main(){
struct tree *ptree;
char word[WORD];
ptree = NULL;
while(getword(word, WORD) != EOF){
ptree = insertcount(ptree, word);

}printtree(ptree);
}

struct tree *insertcount(struct tree *ptree, char *word){
int cond;
cond = strcmp(ptree->word, word);
if(ptree == NULL){
ptree = creatnode(word);
}else if(cond > 0){
ptree->left = insertcount(ptree->left, word);
}else if(cond == 0){
ptree->count++;
}else if(cond < 0){
ptree->right = insertcount(ptree->right, word);
}
return ptree;
}

struct tree *creatnode(char *word){
struct tree *p;
p = (struct tree *)malloc(sizeof(struct tree));
p->word = (char *)malloc(strlen(word) + 1);
if(p->word != NULL){
strcpy(p->word, word);

p->count = 1;

p->left = p->right = NULL;
return p;
}
}

int getword(char *word, int limit){ /*とりあえず一番の問題となってい                    /*る部分がここです。*/
int c, n;
n = 0;
FILE *fp;
fp = fopen("report2.txt", "r");
if(fp != NULL){
while(c = getc(fp) != EOF){
if(!n && !isalpha(c)){
;
}else if(n && !isalpha(c)){
word[n] = '\0';
}else if(isalpha(c)){     
word[n] = (char)c;
n++;
}
}
}
}

void printtree(struct tree *p){
if(p != NULL){

printf("%s %d\n", p->word, p->count);/*どういう風に表示したら*/                        /*よいかわかりません*/
}
}




この投稿にコメントする

削除パスワード

No.5428

Re:2分探索木について
投稿者---あかま(2006/02/17 14:59:43)


>適当な英文ファイルを開いて単語を重複を省いて抽出し、それぞれの出現頻度を数えるプログラム
このサイトの過去ログに同じようなプログラムがいくつかあります。
「単語」とかで調べればでてきますよ。参考にしてください。
それでも分からない部分があればまた質問をどうぞ。

>いまいちわからないのですが、2分探索木とは何なのでしょうか
検索エンジンで調べればすぐでます。

>(すみませんタグのの使い方がわかりません)
1.掲示板利用宣言の「HTML変換ツール」をクリック。
2.Deleteボタンを押してデモプログラムを消す。
3.自分のプログラムを貼り付ける
4.ConvHTMLボタンを押す
5.変換されたプログラムをコピーして、それを投稿。


この投稿にコメントする

削除パスワード

No.5430

Re:2分探索木について
投稿者---かずま(2006/02/17 22:13:28)


getword の代わりに、fscanf を使ってみてはいかがでしょうか?
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct tree {
    char *word;
    int count;
    struct tree *left, *right;
};

struct tree *insertcount(struct tree *ptree, const char *word);
struct tree *creatnode(const char *word);
void printtree(struct tree *p);

int main(void)
{
    struct tree *ptree = NULL;  char word[256];
    FILE *fp = fopen("report2.txt", "r");
    if (!fp) puts("can't open report2.txt"), exit(1);
    while (fscanf(fp, "%*[^a-zA-Z]"), fscanf(fp, "%255[a-zA-Z]", word) == 1)
        ptree = insertcount(ptree, word);
    printtree(ptree);
    return 0;
}

struct tree *insertcount(struct tree *ptree, const char *word)
{
    if (ptree == NULL) ptree = creatnode(word);
    else {
        int cond = strcmp(ptree->word, word);
        if (cond > 0) ptree->left = insertcount(ptree->left, word);
        else if (cond == 0) ptree->count++;
        else ptree->right = insertcount(ptree->right, word);
    }
    return ptree;
}

struct tree *creatnode(const char *word)
{
    struct tree *p = malloc(sizeof(struct tree));
    if (!p || !(p->word = strdup(word))) puts("out of memory"), exit(1);
    p->count = 1;
    p->left = p->right = NULL;
    return p;
}

void printtree(struct tree *p)
{
    if (!p) return;
    printtree(p->left);
    printf("%6d %s\n", p->count, p->word);
    printtree(p->right);
}



この投稿にコメントする

削除パスワード

No.5429

Re:2分探索木について
投稿者---Blue(2006/02/17 15:00:31)


http://www3.realint.com/cgi-bin/tarticles.cgi?pointc2+5380
はどうなったの?

掲示板ご利用上の注意 はよみましたか?
> ソースの添付は「HTML変換ツール」で字下げします。


この投稿にコメントする

削除パスワード

No.5431

2分探索木について
投稿者---MoriMori(2006/02/17 22:57:54)


かずまさんありがとうございます。
あせってたので非常に助かりました。



>http://www3.realint.com/cgi-bin/tarticles.cgi?pointc2+5380
>はどうなったの?
それは調べたら色々出てきたので何とか解決しました。



この投稿にコメントする

削除パスワード

No.5432

Re:2分探索木について
投稿者---Blue(2006/02/18 00:42:53)


>かずまさんありがとうございます。
>あせってたので非常に助かりました。
レスするところが違います。面倒ですが、ちゃんと返信を分けましょう。

>それは調べたら色々出てきたので何とか解決しました。
掲示板を使っている以上、どうやったら解決したかを載せましょう。


Web上のソースを平気でパクってあたかも自分のソースのようにして提出しているような人にいってもしょうがないか、、、
前科→http://www3.realint.com/cgi-bin/tarticles.cgi?pointc2+5392


この投稿にコメントする

削除パスワード

No.5433

Re:2分探索木について
投稿者---επιστημη(2006/02/18 21:04:58)


>2分探索木を用いて、適当な英文ファイルを開いて単語を重複を省いて抽出し、それぞれの出現頻度を数えるプログラム
>の作成を課されたのですが、

重複を省いたら、それぞれの出現頻度はどれも 1 になるんじゃないですか?



この投稿にコメントする

削除パスワード

No.5434

2分探索木について
投稿者---morimori(2006/02/18 23:18:49)


>重複を省いたら、それぞれの出現頻度はどれも 1 になるんじゃないですか?


たぶん、一度抽出したらあとは頻度を増やせ
てことだと思います...



この投稿にコメントする

削除パスワード

No.5435

Re:2分探索木について
投稿者---επιστημη(2006/02/19 00:26:55)


>>重複を省いたら、それぞれの出現頻度はどれも 1 になるんじゃないですか?
>
>たぶん、一度抽出したらあとは頻度を増やせ
>てことだと思います...

でしょうね。では次の質問(確認)。

> テキストを単語に分解して、抽出する
> というところがわかりません。

- テキストファイルを読み、得られた文字列を単語に分解するわけですが、
何をもって「単語」としますか? 単語と単語を分かつのは何ですか?

- .,"? などの記号はどうしますか?

- 大文字/小文字を区別しますか? what と What は別の単語ですか?

…などなど、隠れた仕様を明らかに。




この投稿にコメントする

削除パスワード

No.5437

:2分探索木について
投稿者---MoriMori(2006/02/19 14:15:37)


>> テキストを単語に分解して、抽出する
>> というところがわかりません。
>
>- テキストファイルを読み、得られた文字列を単語に分解するわけですが、
>何をもって「単語」としますか? 単語と単語を分かつのは何ですか?
>
>- .,"? などの記号はどうしますか?
>
>- 大文字/小文字を区別しますか? what と What は別の単語ですか?
>
>…などなど、隠れた仕様を明らかに。
>


それは任意とのことです。
とりあえず記号も単語として抽出し、大文字と小文字は区別するようにしたいと思います。

isspaceで記号は抽出できると思うのですが大文字と小文字はどのようにしたらよいでしょうか?


この投稿にコメントする

削除パスワード

No.5438

Re::2分探索木について
投稿者---επιστημη(2006/02/19 14:23:50)


>...
>それは任意とのことです。
>とりあえず記号も単語として抽出し、大文字と小文字は区別するようにしたいと思います。
>
>isspaceで記号は抽出できると思うのですが大文字と小文字はどのようにしたらよいでしょうか?

質問に答えていません。
何をもって「単語」としますか? 単語と単語を分かつのは何ですか?

"Which do you like, coffe or tea?"

を「単語」に分かつとどうなりますか?



この投稿にコメントする

削除パスワード

No.5439

2分探索木について
投稿者---MoriMori(2006/02/19 16:05:06)


>"Which do you like, coffe or tea?"
>
>を「単語」に分かつとどうなりますか?

| " | Which | do | you | like | , | coffe | or | tea | ? | " |


Which-1, do-1, you-1, like-1, coffe-1, or-1, tea-1, ?-1, "-2

総単語数10、9種類

です。




この投稿にコメントする

削除パスワード

No.5443

Re:2分探索木について
投稿者---επιστημη(2006/02/19 19:19:02)


>>"Which do you like, coffe or tea?"
>>
>>を「単語」に分かつとどうなりますか?
>
> | " | Which | do | you | like | , | coffe | or | tea | ? | " |
>
>
>Which-1, do-1, you-1, like-1, coffe-1, or-1, tea-1, ?-1, "-2
>
>総単語数10、9種類
>
>です。

どうやって切り分けたか、そのアルゴリズムをコードに落とせばできあがりです。





この投稿にコメントする

削除パスワード

No.5440

Re::2分探索木について
投稿者---kz3(2006/02/19 16:48:28)


>isspaceで記号は抽出できると思うのですが大文字と小文字はどのようにしたらよいでしょうか?

isspace() はホワイトスペースかどうかを調べる関数であって
記号( @\~<>$ など )かどうかは調べられませんよ。



この投稿にコメントする

削除パスワード

No.5441

2分探索木について
投稿者---MoriMori(2006/02/19 17:00:08)


そうでしたか勉強不足でした。
ではif文で指定すればできますか?




この投稿にコメントする

削除パスワード

No.5442

Re:2分探索木について
投稿者---kz3(2006/02/19 17:35:15)


> そうでしたか勉強不足でした。
> ではif文で指定すればできますか?

ん?何を指定するのですか?
if文で記号を一文字一文字チェックする?(・・)

if( c == '@' ){ /* 記号です */ } else if( c == '?' ){ /* 記号です */ } else if( c == '$' ){ /* 記号です */ } else{ /* 記号でない */ }
とすればいいのかどうかを聞いているのかな・・・。 「もしかしたらこうすればできるかな?」と思ったことは すぐコードを書いてコンパイル・実行すればすぐ結果が分かります。 でそれで動いて「こう書きました」と出されたコードが冗長なら 「そこはこう書けば済みます」と回答がもらえると思います。 で、何を"記号"とするかもまたプログラムの仕様だと思いますが、 ASCII文字では一般に印字可能な文字のうち英数字以外を"記号"としているようです。





この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧




掲示板提供:Real Integrity