授業終了直後♪
グローバル変数かよ。
とか思わずツッコミ。
模範解答のfind_maxに思いっきりグローバル変数使ってて吹いた。
いや、何もグローバル変数は悪だ、とまではいいませんが、やっぱ使わなくていいグローバル変数は使いたくない。
ということでプログラミング序論、俺的find_max
/*
* そういや前回検索いらないとかいっちゃったね。一応いるわ。検索
* まぁ、微妙に毛色違う検索なので...。
*/
7struct node* find_max( struct node* root, struct node* max ) { if( root->count > max->count ) { max = root; } if( root->left != NULL ) { max = find_max( root->left, max ); } if( root->right != NULL ) { max = find_max( root->right, max ); } return max; }
まぁ、こんな感じで前回のエントリで書いたfindは格納されてる文字列で検索したので、二分探索*1が使えましたが、今回はcountで検索しているので全部検索しています。
で、仮引数*2のmaxはそれまでの暫定一位を入れておきます。
main関数ではfind_max( root, root )の様に暫定一位のmaxとしてrootをいれてやればおっけーです。
あと、課題4-3。
模範解答だとwordの最大長をNと決め打ちしてますので、
for( j = 1; isalpha( ch = getc( fp ); j++ ) {
だと結構危険です。
まぁ、課題ですし、細かいことはいいかな?とは思いますが、
for( j = 1; j < (N - 1) && isalpha( ch = getc( fp ); j++ ) {
とかしてやるべきですな。せめて。
ちなみに理想で言えば可変長*3な文字列にしてやるとなおよし。
具体的にはこんな感じ?
char* getWord( FILE* fp ) { size_t length = 256; //最初に確保する文字列の大きさ。size_tじゃなくてintでもいいけどできればsize_tで。 size_t readed = 0; //実際に読み込んだ文字列の長さ。これがlengthをこしちゃあかん。 char* word = (char*)calloc( sizeof( char ), length ); //malloc( sizeof( char ) * length )でもいいけど、その場合は最後に'\0'をいれてやらんとあかん。 char ch; while( ( c =fgetc( fp ) != EOF && ( isalpha( ch ) || readed == 0 ) ) { //条件が難解ですが、 //EOF((ファイルの末尾 End-Of-Fileのこと))に達していない //かつ //英字であるかまだ何も読んでいない (英字以外の読み飛ばし) //状態の時ループします。 //最初に英字が来るまでは読み飛ばし、英字が来てからその後に英字以外が来たときはそこでとめて単語の区切りと考えるのだ。 if( isalpha( ch ) ) { //最初に英字が来ない場合は読み飛ばす if( readed >= length ) { //読み込んだ文字数がlengthを越してしまう!! //ということで文字列を再び確保。 //たしかreallocってのがあったようななかったような...。 char* swap = (char*)calloc( sizeof( char ), length * 2 ); //2倍の長さを確保する。 memcpy( swap, word, length ); //もともとの文字列wordから新しく作ったswapへコピーする。 free( word ); //古いのは開放してしまう。 word = swap; //新しく確保したのを正式採用。 length *= 2; //長さは二倍になった!! } *(word + readed) = tolower( ch ); //文字列の末尾に文字をくっつける。あ、word[readed]=ch;でもよかったか。 readed++; } } if( readed == 0 ) { //何も読み込んでない。 free( word ); //余分な物は解法 return NULL; //単語なかったよ。 } else { return word; } }
こんな感じか?
なんかミスがありそ...。気がついた方がいたらコメントお願いします。あと無駄が多いのは仕様です。(文字列以外の読み飛ばしを別ループにやらせると多分もっとすっきりします。はい。
まぁ、わざわざRe-allocするのもコスト高いですし、模範解答ので十分おっけーだと思います。
あ、あと、getWordの中でallocしてますので、呼び出し元(個の場合では多分main)で開放するのをお忘れなく。
俺は開放してませんが(ぉ
まぁ、プログラムが終了まで達すれば勝手に消えてくれますし、なにより課題だし(マテ
というわけで、授業でてるとプログラムの大半が板書されるので真面目にノートとってればラクショーなはずですが、多少のつけたしというか、蛇足というか...。でした。
今日の課題。
半分自分用の備忘録なんで正確じゃないこともあるので注意。
ちゃんと授業にはでまShow(情報学類じゃあるまいしだいじょぶか。
課題5-1
% ./a.out word1 word2 ...
の時、wordをアルファベット順に出力するプログラムを作る
ソートアルゴリズムは問わず
課題5-2
% ./a.out word1 word2 ...
の時、wordの出現回数順に出力するプログラムを作る。
データ構造は問わず。
課題5-3
課題5-2と同様
ただし、木構造を用いて出現回数を数え、その木構造を用いてheap sortを行うこと。
せっかく木構造作ったのでそれでheap sortを行う。
