|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第５６０回 テンプレート木構造３ 追加など 発行 ２００５年５月１３日（金曜日） 発行数 約２６００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンは、主にまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・横６０文字で作成し、インデントは大抵半角スペース４つです。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、メルマガのホームページでお願いします。 ・過去ログはバックナンバー（下欄参照）を活用して下さい。 ・内容は私が感じたもので、最新の技術も、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 先日、ダイレクトメールでVisualStudio2005日本語ベータ版の 案内が来ました。 まだ、ベータ版なのですねぇ。 今使っているのは2003で、少し古いのですが一応動きます。 2005は製品版が出るまで待つことにします。 {magclick} /*========================================================*/ 今回のお題 ＜＜ テンプレート木構造３ 追加など ＞＞ /*========================================================*/ 引き続き、テンプレートのお話です。 前回までに、木構造クラスの形を決定しました。 今回は追加関数などの中身について考えをまとめます。 その前に、前回忘れていたメンバ変数dataについて。 Data* data; と定義されています。 これが木構造のトップになります。 コンストラクタなどにより、NULLが設定されます。 デストラクタなどにより、メモリが開放されます。 /*========================================================*/ それを踏まえて、追加を行う関数です。 template <class KeyType = CString, class DataType = CObject> DataType* CTree::add( KeyType& key ) { Data** ppt = _find( &data, key ); if( ! *ppt ) *ppt = new Data(); return ( DataType* )*ppt; } 検索と追加は同じロジックを使うので、共通の関数を呼び出し ます。 _find は木構造であるData型のポインタのポインタをとり、 ・一致するデータを見つけた場合は木構造データのポインタ、 ・見つからない場合は追加するべき場所をポインタで返す、 としましょう。 検索結果が「見つからなかった」場合、newします。 /*========================================================*/ 続いて、検索の共通処理。プライベート関数です。 template <class KeyType = CString, class DataType = CObject> DataType** CTree::_find( Data**ppt, KeyType& key ) const { while( *ppt ) { DataType* pt = *ppt; if( pt->key == key ) break; if( pt->key < key ) ppt = &pt->left; else ppt = &pt->right; } return ppt; } 検索内部にはループがあり、 ・一致する場合はブレイク、 ・検索データより小さい場合は左、 ・検索データより大きい場合は右、 を検索し続けます。 strcmpのように、比較が１回ですめばよいのですが、DataTypeに 指定されるすべての型に同じような機構、もしくは引き算の実装を 強制するのは、理不尽です。 というわけで、単純に比較を２回行っています。 まぁ、いいでしょう。 /*========================================================*/ また、ユーザプログラムから呼び出す検索は、 template <class KeyType = CString, class DataType = CObject> DataType* CTree::find( KeyType& key ) const { Data** ppt = _find( &data, key ); return ( DataType* )*ppt; } と、_findを呼び出すだけです。簡単ですね。 {magclick} /*========================================================*/ さいごに /*========================================================*/ 今後の予定表です。 済 CImageサンプルの説明（していなかった？） 済 ヒステリシス１ ヒステリシスとは座標変換 済 ヒステリシス２ ヒステリシスとは状態遷移 済 ヒステリシス３ ヒステリシスとはファジィ 済 ヒステリシス４ テンプレートで作成しよう 済 ヒステリシス５ 名前空間にまとめよう 済 テンプレート木構造１ TreeMasterをテンプレートに 済 テンプレート木構造２ クラス設計 済 テンプレート木構造３ 追加、検索 第５６１回 テンプレート木構造４ ソート 第５６２回 テンプレート木構造５ 第５６３回 ガベージコレクタ１ テンプレートの隠蔽 第５６４回 ガベージコレクタ２ ユーザ設計 第５６５回 ガベージコレクタ３ クラス設計 第５６６回 ガベージコレクタ４ 登録、削除処理 第５６７回 ガベージコレクタ５ Attach、Detachの処理 第５６８回 キャラエディッタ１ ソフトの説明 あくまでも予定ですが、なんだか順調に話が進んでいます。 {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は５月１６日（月曜日）に、第５６１回をお送りします。 お題は「テンプレート木構造４ ソート」 マクロ版木構造のように、ループをまわすための仕組みを 考えましょう。 ただし、イテレータは使いません。あれは駄目です。 お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されていますか？ このメールマガジンの内容に文面の引用はありませんか？ めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容の、転用、流用、宣伝、リンク、 GW中にやせました。 なんて大歓迎です。 {magclick} /*========================================================*/ /*========================================================*/ 発行者 あゆしゃ ホームページ::あゆしゃの世界 http://ayusya.hp.infoseek.co.jp/ ご意見・ご感想・ご質問メール mailto:ayusya@flamenco.plala.or.jp まぐまぐ::アイディー 0000020674 まぐまぐ::登録と解除 http://www.mag2.com/m/0000020674.htm まぐまぐ::バックナンバー http://jazz.tegami.com/backnumber/frame.cgi?id=0000020674 めーらっくす::アイディー MM3E1AEE285AB4F めーらっくす::登録と解除 http://www.mailux.com/mm_dsp.php?mm_id=MM3E1AEE285AB4F めーらっくす::バックナンバー★最近のものならこちらが便利★ http://www.mailux.com/mm_bno_list.php?mm_id=MM3E1AEE285AB4F |