双方向リストの課題

[初心者]

学校でこのような課題が出されました。
自分でこの課題に取り組んでみたところ、構造体の基本的な使い方(値や文字列を入れること等)と自己参照構造体の使い方がよく分からなく、うまく単語別に分けることができなかったので質問させていただきました。

他のサイトでも調べたのですがよく分りません。
ご指導よろしくお願いします。

「問題文」
キーボードから英文(単語数120個以内)を入力し、その英文に含まれる単語を個数と共に出力しなさい。ただし、アルファベット順（辞書順）とする。
　単語と単語の間には、空白、コンマ（,）、ピリオド(.)があり、入力英文は複数のセンテンスから構成されているものとする。
　なお、a,an,andは別の単語とする。単数形と複数形を別の単語として区別してよい。
また、大文字と小文字は区別しない。
　英文の入力は、一度に全英文を入力しても、センテンスごとに区切って入力してもよい。
　各単語は、双方向リストに格納すること。左ポインタはアルファベット順でその単語より小さい単語を、右ポインタは大きい単語を示すようにする。なお、そのような単語がない場合はNULLポインタとする。

以下の構造体を用いて作成すること。

struct data{
char *word; /*単語*/
　　 int cnt; /*個数*/
struct data *left /*左ポインタ*/
　　 struct data *right /*右ポインタ*/
}tango[120];

[non]

>うまく単語別に分けることができなかったので質問させていただきました。

うまく、単語別に分けるというのはアルファベット順に繋ぐことでしょうか？
それ以外の部分（例えば、リストの先頭か最後尾につなぐ）のプログラムを添付して
ください。一から作るのは面倒なので。

[初心者]

英大文字をすべて英小文字に変換してから、単語に分けるとは思ったのですが、入力した英文を単語に分けるという部分からよく分らなくなってしまいました。
そして、その単語を構造体に格納するという書き方がわかりません。格納したあとの表示の仕方も教えていただけたらありがたいです…
アルファベット順にはリストのポインタを入れ換えればいいとは思っていますが、よく分かりません。
初歩の部分ですが、よろしくお願いします。

//自分で作ったのはここまでです。

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

struct data{
char *word;
int cnt;
struct data *left;
struct data *right;
}tango[120];

int main(void)
{
char buf1[256],buf2[256][256],w;
int i,j,sum,l=0,k=0,mojisu=0,a;
/*struct data *head,*free; 使い方が不明*/


while(1){
printf("英文 を入力して下さい.-999で終了：");
gets(buf1);
if(!strcmp(buf1, "-999")){
break;
}
else{ //?
sum+=strlen(buf1);
if(k>255){
k++;
sum=sum-256;
}
strcat(buf2[k], buf1);
}
}

printf("[入力英文]\n"); //そのまま変換なしで出力
for(i=0;i<=k;i++){
printf("%s",buf2);
}
/*ここからよく分らないです…*/
for(i=0;i<=k;i++){
for(a=0;a<256;a++){
buf1[a]='\0';
}
for(j=0;j<256 && buf2[j]!='\0';j++){
if(buf2[j]>='A' && buf2[j]<='Z'){ //英大文字だったら英小文字へ
buf2[j]+=32;
}
w=buf2[j];
if((mojisu==0) && !(islower(w))){ //初めの英小文字が来るまで
continue;
}
else if((islower(w))){ //英小文字だったら
buf1[l++]=w;
mojisu++;
}
//特にこの部分
else if(!(islower(w))){ //英小文字ではなかったら



}
}
}

printf("\n\n[英文の中の英単語別出力]\n");
/*～
* a・・・7
* an・・・3
* and・・・5 などの出力～*/
return(0);
}

[non]

もっと、前の段階からみたいですね。ちょっと、そこからだと私に時間がないので、
ここでも読んで勉強してみてください。

単語への分解はここを参考に
http://www005.upp.so-net.ne.jp/h-masuda ... lex01.html

リスト構造は
http://www005.upp.so-net.ne.jp/h-masuda ... lex01.html

>アルファベット順にはリストのポインタを入れ換えればいいとは思っていますが
ノードを追加するときにアルファベット順になるようにします。
後で、繋ぎ変えるのは面倒です。

[box]

双方向リストの配列というデータ構造が、何だかユニークに思えます。

入力した英単語を辞書順に並べ替えて出力したいのであれば、
　・リスト構造を使うなら、リストに挿入するときに辞書順にしておく
　・配列を使うなら、ランダムに並んでいる要素を後からソートする
という方法があります。

リスト構造を使う（配列は使わない）か、
配列を使う（リスト構造にはしない）かの
どちらかだろうと思うのです。

出題されたかたがどういうお考えでそのデータ構造を使うように
指示されたのか、聞いてみたい気がします。

[初心者]

nonさん、ありがとうございます。
今の自分では、この課題は出来そうもないので、勉強し直してきます。
リンクをよく見ましたが、まだよく分かりません…

単語分解プログラム、作れる方いましたら、是非書きよろしくお願いします。

[Ace]

つくってみた。

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

#define MAX_WORD_NUM (120)
#define MAX_WORD_LEN (20)

struct data {
	char* word; // これやめませんかね…
	//char word[MAX_WORD_LEN];
	int cnt;
	struct data* left;
	struct data* right;
} tango[120];


typedef struct tagData{
	// 大きな勘違いをしていたためこうなってしまった。
	// でもまぁそれならそれでいっかーという感じ。
	char* word;
	int len;
} Data;

// qsortで使用
int word_cmp(const Data* a, const Data* b) {	
	int len = a->len > b->len ? b->len : a->len;
	int ret = memcmp(a->word, b->word, len);
	if (ret > 0) {
		return 1;
	} else if (ret == 0) {
		// 文字数多い方が後
		return a->len > b->len ? 1 : -1;
	} else {
		return -1;
	}
}

int main(int argc, char* argv[/url])
{
	int i, k; 
	int wordNum = 0;
	Data words[MAX_WORD_NUM] = {0};
	int tangoNum = 0;
	
	if (argc < 2) return 0; // 一応

	// wordsにひたすら突っ込む
	for (i = 0; i < MAX_WORD_NUM * MAX_WORD_LEN; ++i) {
		char* t = &argv[1]; // 一々打つの面倒なので
		if (*t == '\0') break;
		// 一文字目発見
		if ('A' <= *t && *t <= 'z') {
			words[wordNum].word = t;
			// 終端の探索
			for (k = 1; k < MAX_WORD_LEN; ++k) {
				char* t2 = t + k; // さらに面倒なので
				if (*t2 == ' ' || *t2 == ',' || *t2 == '.') {
					words[wordNum].len = k;
					++wordNum;
					i += k;
					break;
				}
			}
		}
	}

#ifdef _DEBUG
	for (i = 0; i < wordNum; ++i) {
		char t[20] = {0};
		sprintf(t, "%%.%ds\n", words.len);
		printf(t, words.word);
	}
	printf("-------------------------------------------\n");
#endif
	
	// 大文字を抹殺する
	for (i = 0; i < wordNum; ++i) {
		for (k = 0; k < words.len; ++k) {
			char* t = &words.word[k];
			if ('A' <= *t && *t <= 'Z') {
				*t += 0x20; // ANCII
			}
		}
	}

	// まぁとにかくソート
	qsort(words, wordNum, sizeof(words[0]), (int (*)(const void*, const void*))word_cmp);

	// 適当に双方向リストに入れる
	for (i = 0; i < wordNum; ++i) {
		struct data* t = &tango[tangoNum]; // 相変わらず面倒なので
		for (k = 1; k < MAX_WORD_LEN; ++k) {
			if (words.len == words[i + k].len) {
				if (!memcmp(words.word, words[i + k].word, words.len)) {
					// 一致してた
					++i;
				} else break;
			} else break;
		}
		// しょうがないのでmalloc
		t->word = (char*)malloc(sizeof(char) * (words.len + 1));
		if (!t->word) return -1;
		memcpy(t->word, words.word, sizeof(char) * words[i].len);
		t->word[words[i].len] = '\0'; // これ入れなきゃいけないの忘れてた
		t->cnt = k;
		++tangoNum;
	}
	
#ifdef _DEBUG
	// 結果
	printf("単語\t: 個数\n");
	for (i = 0; i < tangoNum; ++i) {
		printf("%s\t: %d\n", tango[i].word, tango[i].cnt);
	}
	printf("-------------------------------------------\n");
#endif

	// さて、双方向にするか。
	for (i = 0; i < tangoNum; ++i) {
		if (i == 0) {
			tango[i].left = 0;
			tango[i].right = &tango[i + 1];
		} else if (i == tangoNum - 1) {
			tango[i].left = &tango[i - 1];
			tango[i].right = 0;
		} else {
			tango[i].left = &tango[i - 1];
			tango[i].right = &tango[i + 1];
		}
	}
	
	printf("単語\t: 個数\n");
	// 一応双方向で実験。一応この結果が本命で。
	{
		struct data* next = tango;
		while (1) {
			printf("%s\t: %d\n", next->word, next->cnt);
			next = next->right;
			if (!next) break;
		}
	}

	// フリー
	for (i = 0; i < tangoNum; ++i) free(tango[i].word);
	
	return 0;
}

ふぅ。いい勉強になりました(私が勉強になってもしょうがないですが(笑))。
しかし、関数に分割もしてないし、双方向リスト？だから？
という出来になってますので、微妙かもですね。

せっかくリストなので(何故、双方向なのか分かりませんが…)、リストで作った後に、色々いじろうかとも思ったのですが、結局かぶった単語を消さないといけないので、リストにしても面倒くさいだけなような気がしてきて、こんな感じになっちゃったという感じです。

まぁ参考になればいいですが、超汚いので。
そんなに自信ないので、もし間違ってたらすみません。
おつかれさま、私。

[初心者]

Aceさん、ありがとうございます。

勉強になります。
ソートの部分ですが、辞書順にすることはできますか？
ソートの部分、どのようにして辞書順にするのか、よく分かりません…

単語分解プログラム、作れる方まだまだいましたら、是非書きよろしくお願いします。

[初心者]

nonさん、Aceさん
ありがとうございました。

無事に英文の単語分けのプログラムできました。
わからないことが出てきたら、また質問をすると思いますが、その時はよろしくお願いします。

本当にありがとうございました。