五ロ はしめて学ぶプロクラー ニンク だけなのて、 , プログラムのある部分だけを マクロにすることがて、きます。 無限ループのマクロ化 たとえば無限ループを表すマクロを Fig. 10 ー①のように定義し , Fig. 10 ー②のように 使用すれば , このプロックが無限ループだ ということがよくわかるかと思います。 引数つき main 関数定義部のマクロ化 引数つきの mai n 関数のお決まりの書式 Fig. 1 ト①もマクロにて、きます 0Fig. 11 ー② のように定義すれば Fig. 1 ト③のように簡潔 に表現て、きます。 arg_main( ) は Fig. 11 ー④ のように展開されます。 ファイルオープンのマクロ化 ファイルのオープンやクローズなどもお る部分を意味がよくわかるように名づけた るという規則があるのて、 , Fig. 9 ー④のよう マクロにすることが , 基本的な技法だと思 決まりのパターンなのて、 , マクロにしたほ になります。 List 8 を実行して確かめてくだ うがよいて、しよう。たとえば Fig. 12- ー①のよ います。マクロは関数と違い置換している Fig. 10 無限ループのマクロ #define LOOP fO 「 ( : : ) LOOP { ひととおりプリプロセッサの文法の説明 をしたのて、 , 実際の応用について簡単に説 明しましよう。 何度も強調しますが , マクロは置換をし ているにすぎないのて、 , かなり柔軟な , あ るいはトリッキーな記法がて、きます。した がって , その使い方はプログラマの趣味に よるところが大きいものて、す。これから紹 介することも , 自分が納得するものだけを 採用して , 自分専用のマクロを集めたヘッ ダファイルを作ればよいて、しよう。 バターンが決まった表現のマクロ化 いつもパターンが決まった記述をしてい Fig. 9 マクロの使用例と展開例② #define ロ「 int_data(data) p 「 intf( #data " : %d*n"' data) data_print(x) ; ①②③④ 引数つきのマクロの例 List 8 1 : #include く stdio. h> 2 : 3 : #define print-data( data ) 4 : 5 : i nt ma i n ( VO i d ) 7 : i nt X 8 : print-data( 9 : print_data( return 0 : 13 : } data printf( #data " = %d%n" / * 変数 x の出力 * / / * 変数 y の出力 * / b 「 eak: Fig. 1 1 引数っき main 関数定義部のマクロ ① int main(int a 「 gc, cha 「 *a 「 gv [ ] ) #define a 「 g_main( ) int main(int a 「 gc, cha 「 *a 「 gv [ ] ) a 「 g_main( ) int main(int a 「 gc, Cha 「 *a 「 gv ロ はしめて学ぶ C プログラミング 125

C プロクラマのための 更新されておらず , ファイルをクローズし 実際のディスク入出力はこのバッフアの大 て、しようが , 残りの たときにディレクトリエントリが更新され きさの漿位て、行います。したがって fclose 関 ( 2 ) ( 4 ) ( 7 ) ています。 て、はディレクトリエントリが更新される可 数て、ファイルをクローズするときにファイ 能性があります。この問題の解決の手掛か 次に Fig. 6 を見てください。これは Fig. 5 ルポインタ用のノヾッフアにデータが残って いる可能性があり , ファイルをクローズす と比べて りはふたつあります。 MS ー DOS の内部ディスクバッファ る前にディスクに書き込まれる可能性があ ・ファイルオープン時にすでに同名のフ (a) (b) コンバイラのライプラリの内部デ ァイルが存在している ります (Fig. 3 , 4 ) 。 この 2 点を考慮するとプログラムの流れと ・ファイルクローズの直前に日付を強制 イスク / ヾッファ M S ー D O S て、は C O N F I G. S Y S て、 的に設定している 実際のディスクの状態はバッフアがからむ BUFFERS を設定することにより ,MS-DOS の 2 点が違っています。 Fig. 6 を見れば書き 分だけ異なることが予測て、きます。 のディスクバッフアの容量を指定て、きます。 それて、はちょっとしたテストをしてみま 込み用のオープンて、あっても , すて、に同名 このディスクノヾッフアの容量によりディス のファイルが存在していれば日付は更新さ しよう。 testdate. c ( 付録ディスク収録 ) はフ クのアクセス速度がかなり違ってきて , れていないことがわかります。もっとも注 ァイルを書き込み中の日付を調べるテスト 種のディスクキャッシュの働きをします。 目すべき点は , ファイルクローズの直前に プログラムて、す。この実行結果 ( Fig. 5 ) を見 設定している日付がファイルをクローズす また , C 言語て、は , ファイルポインタによ てください。新規作成のファイルオープン るディスク操作て、はディスクの入出力速度 時にはディレクトリエントリが新たに作成 ることにより再度そのときの時刻に更新さ を速くするため一定のバッフアを用意し , れている点て、す。 されますが , データの書き込み中は日付が このことは Fig. 7 を見るとよりはっきりし Fig. 4 書き込みファイルのクローズ ます。①て、強制的に設定した日付は②て、確 認て、きますが , 実際のディレクトリエント fcl ose ()p ) リは史新されていないことが③て、わかりま す。これは①て、設定した日付は MS-DOS の 内部バッフアを更新しているだけてディス クのディレクトリエントリは史新していな いということて、す。 さらにディレクトリエントリの実際の更 新はファイルをクローズするときに行われ ていることが④⑤⑥によりわかります (Fig. 8 ) 。 Fig. 7 からわかることは書き込み中は C 言語のライプラリの内部バッファ , または MS ー DOS の内部バッフアを更新しているだ けて、ファイルをクローズするときに内部バ ッフアに残っているデータをディスクに書 き込むために , 再度更新が行われて実際の ディスクのディレクトリエントリに書き込 まれるということてす (Fig. 4 ) 。 それて、は ,testdate. c をファイルポインタ て、はなく , ファイルハンドルを用いたプロ グラムに書き直して , 再度テストしてみれ ばどうなるてしようか。ファイルハンドル を用いたファイル操作ては , テキストモー ドのとき , 内部バッフアフラッシュ fflush (fp) ↓ close (fileno (fp) ) ラ イ ラ の : ロ 言 ↓ DOS ファンクション 3 Eh ( 八ンドルのクローズ ) MS-DOS の内部ディスク バッフアをティスクにフラッシュ ↓ ティレクトリエントリ ( 日付 , 時刻 , サイズ ) の変更 ファイルポインタ用の fclose 関数でファイルをクローズするときにはファイルポインタ用 のバッフアに残っているテータをフラッシュしてからクローズする 新 MS-DOS プログラミング入門 95

また , 市街地は青系統の色て、表示される ( Fig. 合成カラー表示する画像て、 , 自然の色に近 自然色画像 6 ) 。 く , 森林や草地は緑て、表示され , 陸域と海 (True CO 「 image) TM の場合 : バンド 4 → R , バンド 3 → G , 域の区別がはっきりする (Fig. 5 ) 。 バンド 2 → B TM の場合 : バンド 4 → G , バンド 3 → R , TM の可視域のバンド 3 , 2 , 1 に各バンド MSS の場合 : バンド 6 , またはバンド 7 → / ヾンド 2 → B の波長帯の色て、ある赤 , 緑 , を割り当て , R, バンド 5 → G , バンド 4 → B MSS の場合 : バンド 6 , またはバンド 7 → 合成カラー表示した画像て、 , 人間が実際に MESSR の場合 : バンド 4 → R , バンド 2 → G, バンド 5 → R , バンド 4 → B Ⅱて、見ている色に近い色て、表示され , 道路 G, バンド 1 → B MESSR の場合 : バンド 4 → G , バンド 2 → や人 I. 構造物が判別て、き , 河川や海域の現 R, バンド 1 → B 象を観察するのに適している ( Fig. 4 ) 。 中間赤外カラー画像 TM の場合 . バンド 3 → R , バンド 2 → G , (Middle infra-red color image) 赤外カラー画像 バンド 1 → B (FaIse color image) 中間赤外域の波長帯て、ある TM のバンド 7 擬似自然色画像 に赤 , バンド 5 に緑を割り当て , バンド 3 ま 可視域のバンドふたつに緑とを割り当 (NaturaI color image) たはバンド 1 に青を割り当て , 合成カラー表 て , 近赤外のバンドに赤を割り当て , 合成 示した画像て、 , バンド 1 に青を割り当てた場 可視域のバンドふたつに赤と青を割り当 カラー表示した画像て、 , 活力ある植物ほど 合は水域がよくわかる ( Fig. 7 ) 。 て , 近赤外のバンドひとつに緑を割り当て 赤く表示され , 植生の識別に適している。 5 擬似自然色像 ( TM4 ー G , 3 ー R , 2 ー B ) 4 自然色画像 ( TM3 -R,2-G,1-B) Fig. Fig. 6 7 中間赤外カラー画像 ( TM ・ 7 ー R , 5 ー G , 3 ー B ) Fig. 赤外カラー画像 ( TM4- R , 3- G , 2 ー B ) Fig. Conference Room 147

カンマ演算子で記述した場合 List 7 10 : { 5 : char -tmpC MAXTMP ] : / * 作業領域 * / 4 : #define MAXTMP 80 2 : #include く stdlib. h> # i ncl ude く std i 0. h 〉 1 : 3 : 6 : 7 : 9 : #define input_int( msg, i ) #define output-int( msg, i ) printf("%s" msg printf("%s%dYn" atOi ( gets( _tmp msg, i nt ma i n ( VO i d ) i nt X : wh i I e ( i nput- i nt ( " I nput X ニ output-int( "X = return 0 : のような計算をしたとします。 プリプロセッサは , 2 十 3 * 2 十 3 ; Y この場合 , と展開してしまいます。これて、は正しい値 が求まりませんね。この場合 , 最初のよう #define square(x) (x) * (x) とするとプリプロセッサは , ( 2 + 3 ) * ( 2 十 3 ) : Y と展開し , 正しい式になります。このよう 124 CMAGAZINE 1991 1 グラマが注意してマクロを正しく使用する な問題なのて、す。この問題は , 私たちプロ いう性質のものて、はなく , マクロの本質的 上手に書き換えれば避けることがて、きると て、きないことがあります。これはマクロを 義てはインクリメントなどを行う式が代入 されてしまいますね。このようにマクロ定 これて、は , y の値も x の値もまちがえて計算 Y ( 十十 x) * ( 十十 x) ; に展開します。 この場合 , プリプロセッサは , 以下のよう Y square( 十十 x ) : うなときにはどうなるて、しようか。 の使い方が正しかったとしても , 以下のよ 十分気をつけてくださいね。また , カッコ 要になってきます。プログラムをするとき に関数マクロを使うとカッコの使い方が重 / * 入力部 * / / * 出力部 * / ほか , 避けることがて、きません。 List 6 の動 作を確認してください ためて、す。このような配慮も行うようにし は , ほかの変数名と衝突しないようにする のようにアンダースコア、、〃をつけているの tmp 変数名に , ボラリ用の変数を使うということをします。 なマクロを定義する場合 , このようにテン 用の配列を用意しています。ちょっと複雑 この例て、は , まず tmp というテンボラリ int を定義してみましよう (Fig. 7 ) 。 るマクロ input int と , 出力するマクロ output プロンプトを出力して int 型の値を入力す てください こて、重要なことはカンマ演 算子の働きて、す。カンマ演算子によって , ふたつの式をひとつの文にまとめることが て、きるのて、す。たとえばマクロ input int を Fig. 8 ー①のように使用したとします。これは , Fig. 8 ー②のように展開されます。 カンマ演算子て複数式を並べて記述した 場合 , 式は左から右に評価されていきます。 そして結果の型と値は , 最後の式のものに なります。したがってこの wh ⅱ e 文の条件式 は , 正しく記述されていることになります。 List 7 を実行して動作を確認してください もしマクロ定義て、カンマて、はなくセミコ ロンを用いていたらどうなるて、しようか ? れます。 C 言語は隣あった文字列は連結され す。このマクロは Fig. 9 ー③のように展開さ したとし , Fig. 9 ー②のように使ったとしま たとえば , Fig. 9 ー①のようにマクロを定義 の引用符つき文字列に置き換えるのて、す。 ていればその引数を実引数て、置き換える形 換テキストの中て、仮引数の前に # 記号がつい の置換を行うことがて、きます。マクロの置 引数っきのマクロて、は , 引用符っき文字列 数マクロて、はて、きませんてしたね。しかし , 引用符つき文字列の中の置換は , 記号定 文字列へのマクロ とつの文にしたほうがよいて、しよう。 ください 一般的にはカンマて、区切ってひ コロンて、区切るか , よく考えてから行って を記述する場合 , カンマて、区切るか , セミ をお勧めします。ひとつのマクロて複数式 使う場合は中力ッコと一緒に使用すること しよう。少し入り組んだところて、マクロを を使ってプロック文にしてしまえばよいて、 このようなバグ、を防ぐには中力ッコ { } なバグが起こってしまいます。 て別々の文にしたいときこのような潜在的 どうしても式と式とをセミコロンて、区切っ は発見て、きないバグになってしまいます。 的なエラーて、はありません。コンパイラて、 結果は得られませんね。しかしこれは文法 の関数 p 「 intf のみになってしまい , 意図した 開されます。これて、は if 文の制御範囲は初め うなるて、しようか ? Fig. & - ⑥のように展 もしカンマて、はなくセミコロンだったらど は , もちろん正しくコンパイルされます。 きは Fig. 8 ー⑤のように展開されます。これ します。 Fig. 8 ー④のような使い方をしたと もうひとつマクロの使用例と展開例を示 すね。 るのて、明かにシンタックスエラーになりま て、は w e 文の条件式の中にセミコロンがあ Fig. 8-- ③にその展開結果を示します。これ

と , List 2 をコンパイルするたびに List 2 の 中に List 1 を取り込み展開するのて、 , List 1 の内容はつねにコンパイルされてしまいま す。このような短いプログラムて、はあまり 影響しませんが , たくさんのソースファイ ルをインクルードするようなプログラムや 大きなプログラムを開発している場合など て、は , ムダな処理をしてコンパイル時間が 長くなってしまいます。 結局インクルードするファイルは , 関数 プロトタイプ宣言やグローバル変数をまと めたヘッダファイルにするのが一般的て、す。 ヘッダファイルをインクルードすることに より , 共通の関数プロトタイプ宣言やグロ ーバル変数を使うことがて、きるのて、 , ファ イル間の不整合による悪質なバグを追放て、 きるのて、す。 次に条件っきコンパイルについて考えて みましよう。プリプロセッサにはプリプロ Fig. 2 条件っきコンノヾイルの例 #if 定数整数式 1 定数整数式 1 が真のときにコンバイル #elif 定数整数式 2 定数整数式 2 が真のときにコンノヾイル #elif 定数整数式 3 定数整数式 3 が真のときにコンノヾイル #else 定数整数式 1 , 2 , 3 が偽のときにコンバイル #endif #ifdef トークン セスそのものを制御する機能が備わってい ます。プリプロセスを制御する機能を使う ことにより , 処理系の違いを吸収させたり , デバッグ用の処理を行わせたりする条件っ きコンパイルが可能になります。 Fig. 2 て、は定数整数式を評価し , 真 ( 定数 整数式の値が ! 0 ) ならばその部分をコンパ イルします。このとき #if 行または # e ⅱ f 行の定 数整数式には , sizeof, 型変換 , enum 定数 を含んて、はいけません。この評価は C 言語の else if 文と似ているのて、すぐ理解て、きると思 います。 て、は , 異なる処理系によって使用するヘ ッダファイルが違うときに , SYSTEM とい う名前を使って識別する例を Fig. 3 に示しま す。 Fig. 3 を記述する前に #define SYSTEM TURBOC と記述すると turboc. h だけがインクルードさ れます。このような手法を用いると処理系 による違いを吸収するプログラムを容易に 記述て、きます。 次に , あるトークンが定義されているか 定義されていないかにより , どのように処 理するかを説明しましよう。あるトークン が定義されているときに処理を行う書式を Fig. 4 に示します。 ここて、 #if 行の中の defined( トークン ) とい う式は , その名前が定義されていれば IL , 定義されていなければ 0L になります。ある トークンが定義されていないときに処理を 行う書式は Fig. 5 のようになります。 それて、は List 3 を見てください。このプロ グラムは引数が doub 型て、 , dou e 型の値 を返す関数 func て、返される値の標準偏差を 求めるプログラムて、す。 1 , 2 行目て、ヘッダ ファイル stdio. h と math. h をインクルードし ています。 5 行目て、関数 fu n c のプロトタイプ 宣言を行っています。 8 ~ 10 行目は M 曰が定 義されていない場合に M 曰を定義していま す。 M 曰とは円周率を現す記号定数マクロ のことて、 , 処理系によっては math. h て、定義 されています。 8 ~ 10 行目のように記述すれ ば M 曰を確実に定義することがて、きます。 12 行目は MAXDATA というトークンを M 曰 に置換しています。このように #defile 文は 定義を 2 重 3 重・・・・・・と行うことがて、きます。 あるトークンが定義されているときに処理を行う書式 トークンが定義されているときにコンバイル または #endif Fig . 4 120 CMAGAZINE 1991 1 #endif トークンが定義されているときにコンノヾイル #if defined( トークン ) Fig. 3 SYSTEM という名前を使って識別する例 #if SYSTEM = MSC #include <msc. h> #elif SYSTEM = TURBOC #include く tu 「 boc. h> #elif SYSTEM = LATTICEC #include <latticec. h> #elif SYSTEM = POWE 日 C #include <powe 「 C. h> #else #include く default.h> #endif Fig. 5 あるトークンが定義されていないときに処理を行う書式 #ifndef トークン トークンが定義されているときにコンパイル #endif または #if ldefined( トークン ) トークンが定義されているときにコンノヾイル #endif

ときのように , ファイルのクローズにあた く動作するといいましたが , 前述の説明て、 CR, LF ←→ LF って , C 言語のライプラリの内部バッフアの は C 言語のライプラリの内部ディスクノヾッフ という変換は行われますが ( バイナリモード 残りが書き込まれることがないため , ①て、 アの関係て、正常に動作するとは思えないの て、はこの変換は行われない ) , C 言語のライ 強制的に設定した日付が実際のディスクの にどうして正常に動作するのて、しようか。 プラリて、はバッファリングを行っていない 筆者が確認したときに ディレクトリエントリに書き込まれるわけ ため MS ー DOS の内部ディスクバッフアのみ , たまたまうまく動 作しただけなのて、しようか。 て、す。したがって , fc 叩 y0. c を改めるとす を考慮すればよくなります。 実は fcopyO. c が正常に動作したのには理 れば , testdate. c をファイルハンドルに書き直し 由があります。それはファイルをオープン ・ディスクバッフアをフラッシュしてか たプログラムが tstdate2. c ( 付録ディスク収 ら日付を設定する ( fcopyl. c ( 付録ディ する前に memmax 関数や coreleft 関数 録 ) て、す。この実行例が Fig. 9 て、す。この Fig. (TabIe 13 ) を使用して未使用のメモリをす スク収録 ) ) 9 と Fig. 7 を比べれば⑤⑥の部分の動作が違 ・ファイルハンドルを用いたファイル操 うことがわかります 0Fig. 9 て、は①て、強制的 べてファイルコピー用のバッフアとして獲 作に書き換える ( fcopy2. c ( 付録ディスク 得したからて、す。 に設定した日付は MS ー DOS の内部バッファ 収録 ) ) ファイルポインタを使用したディスク入 を更新するだけて、実際のディスクのディレ 出力て、は通常 , ディスクバッフアが確保さ のいずれかの方法を用いればよいことがわ クトリエントリは更新していないことが② れますが確保する時点て、未使用メモリがた かります。 ③からわかります。 りなかったらどうなるて、しようか c 旨衄の また , ④⑤⑥からファイルのクローズに fc YO. c はなせ 0 に 1 ロロ ライプラリて、はこのようなときは当然ディ より MS ー DOS の内部バッフアの内容がディ 正吊に動作するのか スクバッフアを使用せず 1 バイトご スクのディレクトリエントリに書き込まれ 先ほど fcopy0. c は実行させてみるとうま スク入出力します ( Fig. 10 ) 。したがってデ ることがわかります。ファイルポインタの Fig. 5 testdate の結果 Fig. 6 testdate ー d の結果 新規オープン No. 0 : 1 四 0-07 ー 1 5 20 : 25 : 1 0 No. 1 : 1 990-0 た 1 5 20 : 25 : 1 0 No. 2 : 1 990-07 ヨ 5 20 : 25 : 1 0 No. 3 : 1990 ー 07 ー 1520 : 25 : 10 No. 4 : 1 990-0 た 1 5 20 : 25 : 1 0 No. 5 : 1 四 0-07 ヨ 5 20 : 25 : 1 0 No. 6 : 1 四 0-07 ー 1 5 20 : 25 : 1 0 No. 7 : 1 99 07 ー 1 5 20 : 25 : 1 0 No. 8 : 1 99 0 た 1 5 20 : 25 : 1 0 No. 9 : 1990-07-1520 : 25 : 10 No. 10 : 1 四 0-07-1520 : 25 : 10 No.11 : 1990 ー 07 ヨ 520 : 25 : 10 No. 1 2 : 1 990-07 ヨ 5 20 : 25 : 1 0 No. 1 3 : 1 07-15 20 : 25 : 1 0 No. 1 4 : 1 99 07-15 20 : 25 : 1 0 No. 1 5 : 1 99 07 ー 1 5 20 : 25 : 1 0 No. 1 6 : 1 990 ー 07 ー 1 5 20 : 25 : 1 0 No. 17 : 1 99 07 ヨ 5 20 : 25 : 1 0 No. 18 : 1990-07-1520 : 25 : 10 No. 1 9 : 1 990-0 た 1 5 20 : 25 : 1 0 No. 20 ・ 1990 ー 0 た 15 20 : 25 : 10 No. 21 . 1990 ー 07-15 20 : 25 : 10 No. 22 : 1 四 0-07-1520 : 25 : 10 No. 23 : 1990 ー 0 た 1520 : 25 : 10 No. 24 : 1990 ー 07-15 20 : 25 : 10 No. 25 : 1990-07 ー 15 20 : 25 : 10 No. 27 : 1990 ー 07 ー 15 20 : 25 : 18 りしりしりし Cu Cu Cu Cu C ′」 Cu Cu りし cu りし 0 Cu Cu Cu Cu Cu Cu り . 」 Cu Cu Cu cu cu cu cu 四四 9 012 4 LD 6 7 8 9 012 3 4-5 6 7 8 9 012 3 4 5 ( 0 7 1111 1 1 ー 1 1 1 1 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ← Fig. 5 の最後と同じ ( 既に存在する場合は 更新されない ) 書き込み中は 更新されない ←ファイルクローズ時に MS ー DOS が日付を設定 ←強制的に日付を設定 ←ファイルクローズ時に MS ー DOS が日付を設定 96 CMAGAZINE 1991 1

アルゴリズム ァータ構造入門 Fig. 9 子をひとつもつ節の削除 「 00t 肖」除のプロク、ラム 削除を行う関数 delete を List 3 に示しま す。この関数は , いましがた説明した削除 の手順をそのままコーディングしたものて、 す。挿入の関数 inse 「 t と同様に , 注目してい る節へのポインタて、はなく , その親へのポ インタを使っています。 NODE * * 型の変 数 p が , この役目をはたしています。 6 行目 ( a ) から要素 9 を削除すると ( b ) になる の wh ⅱ e ループて、削除対象となる要素を探索 ( a ) ては変数 p は変数 root を指していることに注意 ( これは境界条件になっている ) します。実際の削除の処理は 8 ~ 21 行目て、行 の操作と , Fig. 10 の① ~ ③のポインタが対 は木の枝ぶりによって大きく変化します。 っています。 応しています。また , 20 行目て、は , 標準ラ 直感的に考えて , 木が低くて枝分かれして 8 行目を実行した時点て、は , 変数 p は削除 イプラリ関数 f 「 ee によって取り除いた節をシ いるほうが探素は高速になります。 Fig. 11 される節の親 ( のメンノヾ left または right) を , ステムに返しています。 (a), ( b ) のふたっ二分探索木を比較してみま 変数 x は削除される節そのものを指していま す。 9 行目はひとつも子をもっていない ( 葉 しよう。どちらの木も , 1 から 7 まて、の 7 つの 要素をもっています。 て、ある ) 場合て、す。実際には Fig. 8 のように Fig. 11 ( a ) のように , 根からすべての葉ま ポインタが書き換えられます。 12 行目は右 二分探索木の特長について考察してみま て、の経路の長さが等しいような二分木を完 の子のみを , 14 行目は左の子のみをもつ場 しよう。二分探索木て、は , 探索 , 挿入 , 削 全ニ分木 ( comp 厄 te binary tree) と呼びま 合て、す ( Fig. 9 ) 。最後に , 16 ~ 18 行目が , 左 除の 3 つのどの操作についても , 根から始め す。実際には , 完全二分木を作ることがて、 右ふたつの子をもっ場合の処理て、す ( Fig. て木をたどって , しかるべき位置を探し出 きるのは , 節の数が 2 1 個 ( n : 自然数 ) て、ある こて、 , 関数 de 回 emin を呼び出して 10 ) 。 します。つまり , 挿入 , 削除を行うにも , ときに限られていますが , 制限をゆるめて , いますが , これは「部分木から最小の要素を 探索を行って挿入する位置 , 削除の対象を 根からもっとも遠い節まて、の経路の長さと , 取り去る」ためのものて、す。関数 deletemin 決めなければなりません。て、すから , 二分 根からもっとも近い節まて、の経路の長さと は List 4 のように定義されていて , 部分木か 探索木の処理の計算量は , 探索の計算量に の差が 1 以ドて、あるような二分木を ( 広い意 ら最小の要素を探し出して部分木から取り 味て、の ) 完全二分木と定義します。 n 個の要 帰結されると考えることがて、きます。 除きます。そして , 取り節いた節へのポイ 先ほども考察したように , 探索の計算量 素をもつ完全二分木は , 根から節への経路 ンタを値として返します。 List 3 の (1) ~ ( 3 ) Fig. IO 子をふたつもつ節の削除 「 00t 「 00t つ f 「 ee される (a) ニ分探索木の特長 9 9 「 0 Ot 5 3 7 1 7 1 free される 8 3 8 ① ② ( a ) から要素 5 を削除すると ( b ) になる ( a ) ては変数 p は要素 9 のメンノ e 負を指している 要素 5 の右部分木中の最小の要素 3 が要素 5 があった位置へ移される 丸数字のポインタは List 3 の丸数字で示される文に対応している (a) (b) アルゴリズムとデータ構造入門 75

C の道具箱 汎用画面作成ツール 五ロ 行 を レ ラ ラ ウ ( 「ド ン 、イ ウ チ マ き ・続る 回の を画面止にコヒ。ーする際に , そのアドレス フプラリ ( 3 ) マルチウィ ド 道具箱に追加さた関数 を 1 行分ずらすことによって行う。 scroll( ) 関数は , この機能を実現するものて、ある。 この関数を呼ぶと指定したウインドウが 1 行 ・機能の概要 scroll() 関数 分上ードに移動する。この指定には囮 , 団キ ー ( あるいは一キー , ーキ (List2, CM910101 ) 今回追加された機能は以下のとおりて、あ ウインドウのスクロール ー ) を使用する。またこのスクロールモード : ウドウ内 0 画面 0 みを上下・ = ク 0 から脱出するには , キーを押せばよい 【書式】 ■サンプルプログラムの実行 ールすることができる <stdio. h> #include ・上下の指定に矢印キーを使用できる サンプルプログラム (scroll. exe, List 1 ) <stdlib. h> #include を実行すると , まずウインドウが表示され <memory. h> #include ・ライプラリの使用例 る (Fig. 1 ) 。次に囮 , 団キーを押すと , Fig. 2 のように , ウインドウの画面が上下にスク ・ウインドウのスクロール #include 'pldwn. h" ロールする。次にキーを押すと画面が ウインドウのスクロールは , 各ウインド #include 'window. h' 消去され終「する。 ウごとに設定されている , ノヾッフアの内容 #include "fkey. h" Fig. 2 スクロール後の画面 Fig. 1 サンプルプログラムの実行画面 応用 c 言語 99

アルゴリスム・テータ構造入門 その子をもってきます。っ あった場所に Fig. 6 子をふたつもつ節の削除 5 15 20 10 7 5 10 20 要素 7 を削除 23 29 2 ( a ) から要素 7 を削除すると ( b ) になる (a) 18 23 29 4 2 要素 7 があった場所に要素 7 の右部分木中の最小の要素 10 が置かれる 要素 10 があった場所には要素 15 が繰り上がる Fig. 7 最小の要素を削除する 5 2 5 (a ) 13 要素 2 を削除 20 7 最小の要素が子をもっていない場合 13 要素 5 を削除 20 5 7 7 20 7 (b) (d) 20 13 二分探索木からの要素の削除は , 探索や 挿入に比べると複雑て、す。何も考えずに節 を削除してしまうと , 二分探索木の定義を 満たさなくなる可能性があるからて、す。 削除の手順としては , まず削除すべき要 素を探し出します。これは , 探索の場合と まったく同じてす。削除すべき要素が見つ (c) 最小の要素が子をひとつもっている場合 一分探索木からの肖」除 かったら , 当然のことながら , それを取り こて , 節が子を何 除けばよいわけてす。 個もっているかによって , 処理を分ける必 要があります。 もっとも簡単なのは , その節が葉て、ある ( 子をもっていない ) 場合てす。この場合に は ,Fig. 4 のように , ただたんにその節を取 り去るだけてすみます。 次に , 子をひとつだけもっている場合を 考えます。この場合には , 削除される節が まり , 子を親の身代わりにすえるわけて、す。 なぜこれてうまくいくかを Fig. 5 をもとに説 明しましよう。 Fig. 5 ( a ) の二分探索木から , 要素 5 を削除 するとしましよう。二分探索木の定義から , ( 要素 5 の親て、ある ) 要素 9 から見たとき , 左 部分木 ( 要素 5 を根とする部分木 ) に含まれる すべての要素は 9 より小さくなっています。 この事実から , 要素 5 の子は ( 左右どちらの 子にしても ) 9 より小さいことになります。 したがって , 要素 5 がひとつの子をもってい るのなら , 要素 5 の代わりにその子にこて、 は 3 ) をすえて得られる木は , やはり二分探 索木となります。 最後に残ったのは , 削除すべき要素がふ たつの子をもっている場合て、 , このケース がいちばんやっかいて、す。削除する節を , その右部分木に含まれる最小の要素て、置き 換えれば , 二分探索木の性質を保っことが て、きます ( 左部分木に含まれる最大の要素て、 も可 ) 。たとえば , Fig. 6 ( a ) の木から要素 7 を削除してみましよう。要素 7 の右部分木に 含まれる最小の要素は 10 て、すから , 要素 7 の あった節に 10 を移動します。また , 要素 10 を取り去づた場所には , 要素 10 の子て、ある 要素 15 が繰り上がっていることに注意しま しよう (Fig. 6(b))0 さて , この手順が二分探索木の条件を満 たすことは , 先ほどと同様に簡単に証明て、 きます。 二分探索木においては , ある節 x の右部分 木の任意の要素は , その左部分木のどの要 素よりも大きくなっています。したがって , ある節 x をその右部分木のどの要素て、置き換 えても , 左部分木に対して , 二分探索木の 条件を満たします。 また , 右部分木の最小の要素 m を節 x の場 所に置けば , 得られた木においては , 新た に親となった節 m は右部分木のどの要素より も小さくなり , 右部分木に対しても二分探 索木の条件を満たしています。 ところて , この削除方法が正しいという アルゴリズムとデータ構造入門 73

ます。て、すから , (a) のように低くて十分に 枝分かれした二分探索木のほうが好ましい ことになります。 - 入のプロク、ラム 挿入の手順を C 言語て、記述したものが List 2 て、す。要素を挿入する場所を決める手順自 体は , 探索とまったく同じて、すが , コーデ イング上て、は , 現在注目中の節の表現法が 少し変わっています。つまり , 探索て、は注 目する節へのポインタを使って二分探索木 をたどっていましたが , 挿入て、は注目する 節へのポインタが入っている場所へのポイ ンタ , つまり親 ( のメンバ right または left) へ のポインタを使うようにしています。なぜ なら , 節を挿入するには , 親のメンバ left か right を変更して , その節を指すようにしな ければならないからて、す。これは , 連結リ ストにおいて , 要素を挿入するのにひとつ 前のセルへのポインタが必要になるのと似 ています。 関数 search(List 1 ) て、は変数 p は NODE * 型て、したが , 関数 insert(List 2 ) て、は変数 p は NODE * * 型になっています。 まず 5 行目て、変数 p が変数 root を指すよう に初期化します。次に , 6 行目の wh ⅱ e ループ を要素を挿入すべき場所が見つかるまて、繰 り返します。そして , 挿入すべき場所が見 つかったら , 15 行目以降が実行されます。 まず , 15 行目て、 , 標準関数 ma Ⅱ oc を使っ Fig. 3 ニ分探索木への挿入 Fig. 4 子をもたない節 ( つまり葉 ) の削除 1 9 5 7 (a ) 要素 1 を削除 ( a ) から要素 1 を削除すると ( b ) になる Fig. 5 子をひとつもつ節の削除 9 14 1 9 5 7 (b) 9 3 4 1 5 3 4 要素 5 を削除 (a) ( a ) から要素 5 を削除すると ( b ) になる。要素 5 があった場所に要素 3 を移動する て , 節を割り当てます。新しい節には子が ないのて、 , メンバ right と left には NULL を入 れておきます。 19 行目て、要素の値をセット してから , 20 行Ⅱて、節を正しい位置に挿入 します。 この時点て、 , ポインタ p は , 挿入され . る節 へのポインタが入っている場所を指してい ます。 2 (b) たとえば , Fig. 3 ( a ) の二分探索木に要素 10 を挿入することを考えましよう。この木 に対して insert ( 10 ) を実行したとき , while ループを抜けた時点て、は , ポインタ p は Fig. 3 ( b ) のように節 4 のメンバ right を指していま す。 20 行目て、は図中の点線部分のポインタ が連結されて , 要素 10 が挿入されます。 1 2 4 3 (a) ( a ) の木に要素 10 を挿入する 72 CMAGAZINE 1991 1 data left ri ht