|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第４７８回 新型木構造 発行 ２００４年７月２３日（金曜日） 発行数 約２８００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンは、主にまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・横６０文字で作成し、インデントは大抵半角スペース４つです。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、メルマガのホームページでお願いします。 ・過去ログはバックナンバー（下欄参照）を活用して下さい。 ・内容は私が感じたもので、最新の技術も、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 ファントム、２度目のクリアをしました。 その時間をページにまとめました。 http://ayusya.hp.infoseek.co.jp/GamePhantom.html クリアタイムは１３時間１７分。 世界記録は１２時間３０分。 ・・・届くぞ！ /*========================================================*/ 株日記 /*========================================================*/ 野村のバーチャル株式投資倶楽部 http://www2.nomura.co.jp/vstock/VirtualServlet? （ゲストでログインして Ayusya を探せば成績を参照できます） ★ここ一週間の Ayusya の成績 火曜日 1,009,650円 27,809番 水曜日 1,005,528円 30,458番 木曜日 996,284円 64,399番 土曜日 988,185円 68,938番 月曜日 988,185円 69,599番 火曜日 988,185円 69,953番 木曜日 990,122円 69,384番 {magclick} /*========================================================*/ 今回のお題 ＜＜ 新型木構造 ＞＞ /*========================================================*/ 以前、木構造をクラスで実装しようとして、大失敗しました。 今回はその反省を持って、木構造処理はべたな関数にします。 また、再起を使わない木構造の追加処理を思いつき、それを 実装しましょう。 それから、文字列も一緒にメモリ取得する方法を思いつき、 それも実装しましょう。 struct tree_t { tree_t* left; tree_t* right; char key[ 1 ]; } *tree = NULL; 左右の枝とキーがある、基本的な木構造の構造ですが、 文字列の宣言が少し変です。 これは、可変長の文字列配列であり、サイズは１とありますが、 サイズを無視した文字列配列として扱おう、という方法です。 構造体のメモリ取得と文字列のメモリ取得が一度に行えて、 便利です。 この可変長文字列は、必ず構造体の最後に宣言します。 WindowsAPI が、たまにやっている裏技です。 tree_t* new_tree( char* key, int len ) { tree_t* pt = ( tree_t* )calloc( 1, sizeof( tree_t ) + len ); if( pt ) { memcpy( pt->key, key, len ); } return pt; } メモリの取得処理です。 取得サイズは、構造体のサイズ＋文字列長となります。 tree_t* find_tree( char* key, int len ) { tree_t* pt = tree; while( pt ) { int c = strncmp( pt->key, key, len ); if( ! c ) c = pt->key[ len ]; if( ! c ) break; if( c > 0 ) pt = pt->left; else pt = pt->right; } return pt; } 単純に探すだけの処理です。 コンペアの結果が０になったとき、長さの位置の文字を比較結果 とするところがポイントです。これがないと死にます。 比較結果が正のとき、探すべき文字列が小さいので、左に分岐 します。 tree_t* add_tree( char* key, int len ) { tree_t** ppt = &tree; while( *ppt ) { tree_t* pt = *ppt; int c = strncmp( pt->key, key, len ); if( ! c ) c = pt->key[ len ]; if( ! c ) break; if( c > 0 ) ppt = &pt->left; else ppt = &pt->right; } if( ! *ppt ) *ppt = new_tree( key, len ); return *ppt; } いままで再起を使っていた追加処理ですが、 ポインタのポインタを使うことによって、検索の処理と同じ ような感じで処理が走ります。 最後、あるべき場所にない場合、メモリ取得処理を発動します。 {magclick} /*========================================================*/ さいごに /*========================================================*/ {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は７月２６日（月曜日）に、第４７９回をお送りします。 お題は「木構造マクロ」 いつでもどこでも簡単木構造！ お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されていますか？ このメールマガジンの内容に文面の引用はありませんか？ めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容の、転用、流用、宣伝、リンク、 PreTranslateで操作系も向上しようかな なんて大歓迎です。 {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 |