CodeResume - 解答例と解説

問題CPP04021の解答例と解説 C++ Lv.3

ツリー構造の末端オブジェクトの取得(30分)

<解答例 1>

F11キーでフルスクリーンモード、Escキーで元に戻ります。

void GetLeafChildren( CRObject* pObject, vector<CRObject*>& leafChildList )
{
	if( NULL == pObject )
		return;

// pObject が末端オブジェクトだったら、これをleafChildList に入れて終了。
	if( pObject->GetNumChildren() == 0 )
	{
		leafChildList.push_back( pObject );
		return;
	}

vector<CRObject*> childList;
    CRObject* pCurrObject = pObject;	// 現在のオブジェクト
    int total = 0;						// childListに入っているオブジェクトの数
    int curr = -1;						// pCurrObjectが格納されている位置。まだ格納していないので、-1にしておく。
    
    do
    {
		// 現在の位置のオブジェクトを取得する。最初は curr は -1 なので、この if 文の中には入らず、引数で渡されたオブジェクトが格納されたままになる。。
		if( 0 <= curr )
	        pCurrObject = childList[ curr ];
			
        int numChildren = pCurrObject->GetNumChildren();
		if( 0 == numChildren )
		{
			// 末端オブジェクトを見つけた。
			leafChildList.push_back( pCurrObject );
		}
		else
		{
			// 子オブジェクトを取得して、chilListに加える。totalも更新する。curr の後ろは、今まで見つけた子オブジェクトが格納される。
	        for( int i = 0; i < numChildren; i++ )
	        {
	            CRObject* pChild = pCurrObject->GetChild( i );
	            childList.push_back( pChild );
	        }
	        total += numChildren;
        }

// 次のインデックスに進めてみる。
        curr++;
    }
    while( curr < total );	// childListの中に、まだ子オブジェクトを取得していないものがある限り、繰り返す。
}

前の問題が解けていれば、この問題は比較的、やりやすくなるよ。
ツリー構造の全オブジェクトの取得問題解答例と解説

<解答例 2>

F11キーでフルスクリーンモード、Escキーで元に戻ります。

前の問題と同じ解説だけど、再帰関数にした例。再帰関数はスタックオーバフローになる可能性があるけれど、1つのスタックが消費するメモリ(つまり、関数の中で定義する変数の大きさや数など)が大きくなかったり、再帰の回数も限られたものだったら、こっちの方がプログラムはシンプルになるね。

初めての方へ：このページは、このサイトで用意しているプログラミング問題の解答と解説のページです。このサイトではブラウザ上からプログラミングができます。会員登録(無料)して、プログラミングしてみませんか？
新規登録

ログイン

パスワード紛失

新規登録