またも締切ギリギリ〜♪

c プログラミング序論

課題はここ

とりあえず二分木の課題なんで二分木の基本だけ書いておけばいいかな。
毎度のことだけど「こんなエントリいらん」な意見は無しで。

ということで二分木。
とりあえずstructを使いましょう。

typedef struct node {
	char* data;
	int count;
	struct node* left;
	struct node* right;
} node;

typedefはしなくてもいいけど、毎回毎回"struct node"と打たないといけない、ので面倒。
まぁ、書いておこう。


で、二分木にルール付けを行う。
つまり、
node.left.data < node.data < node.right.data
あるnodeに対して、小さい物は左、大きい物は右、という風にしていく。
こうすることで(うまくいけば)一回の比較毎に候補が半分になっていくので検索やらが速いと。


で、二分木の扱い方ですが、再起というものを使います。
なんでも工シスではあまりやってないとか...。
ということでこれまた説明。

よく再起の説明で使われるのが"!"つまり階乗。
5! = 5 * 4 * 3 * 2 * 1
ってやつ。
ループで書けるんだけど、再起を使うとこうなる

int fact( int n ) {
	if( n < 2 ) {
		return 1;
	} else {
		return n * fact( n - 1 );
	}
}

と言った感じ。

ある関数の中で、その関数自体を呼び出しているものを再起といいます。
もちろん、それだけでは自分が自分を呼んで、さらに自分をよんで...と無限に続いちゃいますので、条件をつけてやる必要があります。
この場合ではfactの引数n。
nは次々と減っていくはずですので、最終的にはn < 2を満たして、再起が止まります。
メデタシメデタシ。

こいつの動作を脳内シミュレートすると、例えばfact( 5 )は

  • fact( 5 ) = 5 * fact( 5 - 1 )
  • fact( 5 ) = 5 * fact( 4 )
  • fact( 5 ) = 5 * ( 4 * fact( 3 ) )
  • fact( 5 ) = 5 * ( 4 * ( 3 * fact( 2 ) ) )
  • fact( 5 ) = 5 * ( 4 * ( 3 * ( 2 * fact( 1 ) ) ) )
  • fact( 5 ) = 5 * ( 4 * ( 3 * ( 2 * 1 ) ) )

と言った感じ。
まぁ、いじってると慣れます。
再起が得意な場面・ループが得意な場面、色々ありますがまぁ、なれれば分かります。
/* 個人的にhaskellという言語をいじってたりするので再起は結構好きだったり...。 */


閑話休題


二分木の扱いも再起が便利。
木全体を見るとややこしいかもしれないけど、一個のnodeとそのleft,rightだけを見ればずいぶんすっきり。


ということで、基本のキ

二分木の表示

というか要素すべての表示、かな。
とりあえずデバッグにも使えるので最初に説明しちゃいましょう。
まずはソース

void printTree( node* root ) {
	if( root->left != NULL ) {
		//左側の子要素を表示する
		printTree( root->left );
	}
	//自分の要素を表示する
	printf( "%s %d\n", root->data, root->count );
	if( root->right != NULL ) {
		//右側の子要素を表示する
		printTree( root->right );
	}
}

/* えっと、仮引数がrootですが「部分木の」rootということで堪忍してください。 */
左右に関しては、NULLじゃなかったら再起、ということになってます。
図を書き書き、動作を確かめてみて欲しいのですが、それはともかく。
ここで需要なのは、ここで出てくるノード*1はroot自身と、そのleftとrightしかいません。
つまり、木全体を見ていない、ということです。
leftとrightより先のことは「後は任せた」って感じですね。
これが再起の基本になります。

検索

とか書こうかなとか思ったのですが、今回はいらんか。
まぁ、書いてみよう。

node* findTree( node* root, node* item ) {
	if( root == NULL ) {
		return NULL;
	} else {
		int ret = strcmp( item->data, root->data );
		if( ret == 0 ) {
			/* 一致 */
			return root;
		} else if( ret < 0 ) {
			/* rootの方がでかい */
			return findTree( root->left, item );
		} else {
			/* rootの方がちいさい */
			return findTree( root->right, item );
		}
	}
}

コンパイラにとおしてないんでミスってたらすまん。
ソースの説明の前にstrcmpのtips
こいつは

  • 一致したらゼロ
  • 前者の方がおおきければ正の数
  • 後者の方がおおきければ負の数

を返します。
で、おぼえらんねぇよ!!って方のために覚え方。
「strcmpは引き算」
ということ
つまり

strcmp( a, b )

は

a - b

ということ。
a == bならそりゃ当然ゼロが帰ってくるし、a > bなら正の数...と言った感じ。


で、今回はNULLチェックの位置が違います。
printTreeのときは再起で呼ぶ前にNULLかどうかチェックしてましたが、今回は呼ばれてすぐに「自分が」NULLかどうかチェックしてます。

どっちがいいかというと...どっちでもいいんじゃないカナ。


えっと、それっぽいことを書いておくと、呼ぶ前にNULLチェックした方が速いです。わずかですが
というのもNULLかどうかチェックするコストよりも、関数呼び出しの方が遅いので...
まぁ、大した違いはないと思いますが...。


むしろプログラミングの手間を考えてcase by caseで使い分けるとよいかな。
printTreeも「呼ばれてからNULLちぇっく」で構わないと思いますが。


まぁ、いろんな実装見てなれるのもいいかなと思ったのであえて統一させてません。
...嘘です。なんとなくで書いたらブレただけです。


どっちの書き方もある程度決まり文句なので覚えておいてそんはないはずです。


で、やっとソースの説明ですが、retがゼロの時、つまり、rootと探しているデータが一致したらそいつを返します。
printTreeでは返り値がvoidだったのでreturnは気にしていませんでしたが、今回はみつけたノードを返すのがお仕事ですのでreturnした値を常に気にかけておいてください。


retが正/負の時ですが、これは右ないし左に対して再起をかけてやればおっけーです。
というのも、この二分木には「あるノードより小さいものは左、大きいものは右」というルールがあるので、itemのデータとrootのデータの大きさの比較を行ってしまえば、それが(あるとしたら)右、左どちらにあるのか。が分かってしまうのです。
再起では再起先のreturnの結果(つまり関数の戻り値)をそのままreturnします。
こうすることで、これより先のどっかでret==0になってreturnしたされたノードがそのまま、おおもとの呼び出し元(mainとか)に変えされるわけです。


あ、あと、みつかんなかったらNULLってことで

追加とカウントアップ

これは今回のメインなのでソースは無しで。
ただ、大筋はfindTreeと同じです。
異なる点をあげれば

  • ret==0なときはrootをreturnするのでなく、root->countをカウントあっぷしてやる
  • 見つからなかった時にはノードを新しく作成する。
    • ↑に関して
    • 新しく作ったノードは「だれか」から参照されてないとだめ。つまりだれかのrightもしくはleftにいないといけない。
    • ということで、やれば解ると思いますが「呼ぶ前にNULLチェック」の方が都合がいいです。

と言ったところ。good luckです。


当方、明日、体育「柔道」で「寒稽古」たる苦行が06:00から行われますゆえ、もうそろそろおさらばしとう御座います。
つきましてはやや不完全燃焼ぎみなエントリでは御座いますが、これにて失礼させていただきとう存じ上げます。

*1:二分木の要素のこと