讎ラ習 グ学 「タイマによって一定時間を検出した状態」 に相当します。実は , ANSIC における gets ( ) などの関数も , 実際にはキーポードを監 視して履歴を残す機能を持った割り込み処 理なのです。この処理は , コンパイラによ って自動的に用意される初期設定処理 ( ス タートアップルーチン ) によってプログラム の起動時に実行されています。 このような割り込みを使ったイベント駆 動型のプログラムとは , イベントと呼ばれ る OS が発生させる割り込みに対応した処理 をそれぞれ用意し , それらの集合体で構成 されているプログラムです。このボタンが 押されたらこの関数を呼ぶ , この入力フィ ールドに文字が入力されたらこの関数 , と いった関数の集まりなのです ( Fig. 3 ) 。 の点が , これまで 1 年間かけて説明してき たような関数を順番に実行するプログラミ ングと違うところです。 イベント対応プログラミング イベント駆動型のプログラムは , 用意し た各関数がいわば OS の一部として動作する ようなものです。このため , プログラムを 行うためには OS がどのようなイベントを発 生させるのか ( キーポードが押された , マ ウスを移動したなど ) , 使用する開発環境 がイベントをどのように処理するようにな っているか ( キーコードの通知 , マウス座 たとえ , 今最高の技術を持っていたとして 最後の最後に 標移動量の通知など ) , といった知識が必 も , 10 年後 , 5 年後 , もしかしたら 1 年後に 要になります。このあたりは , C 言語の知 も , その技術が陳腐化してしまうこともあ 識というよりも OS や開発環境に関する知識 りえるのです。ですから , 実際にプログラ 最終回となる今回は , この連載の読者で ムを作るのと同じぐらい , 勉強するという といえるでしよう。 あるみなさんが , 今後もプログラミングの 昔のパソコンでの開発経験がある人や , ことをたいせつに考えてください。明日の 勉強を続けていくうえで指針となるような 組み込み機器のプログラミングを行ってい あなたがテム・レイ ( 編注 ) になってしまうかど 話題を 3 っ取り上げてみました。 る人には , 割り込み処理の概念に親しみが C 言語初心者のみなさんが今の技術で作 うかは , 今日のあなたの勉強にかかってい あるので , イベント駆動型の概念を理解し れるプログラムと , 市販のソフトウェアの るのです。 やすいでしよう。しかし , プログラミング 1 年間 , ったない文章におっき合いいた 間にはたいへんな差があるように感じられ 初心者で , 割り込み処理と縁の遠かった人 るかもしれません。ですが , 少しずつでも だき , 本当にありがとうございました。そ は , 最初に壁を感じてしまうところかもし 勉強していけば , いつかはその差を埋める れでは , みなさんの作りたいプログラムが , れません。開発環境付属のサンプルプログ ことができるでしよう。 いつの日かできあがることを願って。 ラムなどを少しずつ改造しながら , 試行錯 私は , 技術者は勉強することをやめた時 編注 : アムロ・レイの父 ( 機動戦士ガンダム / サンラ 誤してみるとよいと思います。 点で技術者ではなくなると思っています。 イズより ) Fig. 2 ボーリングと割り込み処理 割り込み処理 メイン処理 計算処理 キーボードの 履歴取得 ポーリング 割り込み処理 キーボード監視 ここの処理中 , キーは検出 できない 計算処理 キーボード監視 キーが押されると , メイン処理を一時停止させて 割り込み処理が行われるため , 計算処理中でも キーを検出できる Fig. 3 イベント駆動型プログラム イベント : フィールドに入力が行われたら 処理の例 : 文字列変数 st 「にフィールドの文字列をコピーする イベント : ボタンが押されたら 処理の例 : 文字列変数 st 「の文字列をウインドウの見出しに表示する ウインドウ 第 . フィール ボタン 67 C 言語プログラミング学習塾
カリ 定の色でなければ」という条件に変更する までです。 Fig. 3 に示すように , 前回走査 の座標を 1 っ取り出し , その座標を新 だけで対応できます。 での右端以降では上下両方について調べて しい始点として , 1 ) からの処理を繰 やる必要があります。 り返す 以上を考慮して , ムダな処理を省いた処 6 ) バッファ上に , 次の始点となるべき シードベイントの高速化 理の流れは , 次のようになります。 座標がなくなれば処理終了 1 ) 始点から左向きに走査し , 同じ色の部 こまで説明してきたアルゴリズムは , なお , この流れで処理を行うためにはバ シードベイントの基本的な考え方で , 処理 分の左端を検索する ッファ上に の効率化はまったく考えていません。そこ 2 ) 求めた左端から右向きに走査し , 同じ ・画素の座標 で , 次にアルゴリズムを改良して , ムダな 色である間は塗りつぶし処理を行う だけでなく , 処理を省くようにしてみましよう。 3 ) 上記の 2 ) で走査するとき , 前の走査行 ・前の走査線との上下関係 前述のアルゴリズムでは , 左から右への の右端までを , ・前の走査における右端座標 取初の行の塲谷ば検素点 走査で必ず上下の画素を調べるようにして も記録しておく必要があります。 います。しかし , いちばん始めの行 ( ユー ザーが任意に指定した始点を含む行 ) を処 ) 前の走査行から上に移動してきた プログラムの作成 理するとき以外は , 必ずしも上下のすべて 合は上の画素のみ の画素を調べる必要がありません。たとえ それでは , 実際にプログラムを作成して i ) 前の走査行から下に移動してきカ ば , Fig. 3 のように , 前回走査した行より みましよう。今回も , プログラムは Pmacs 場合は下の画素の。 上の行を処理する場合は , 下の画素はすで という条件で画素を調べ , 領域内の画 描画プラグインとして実装しています。描 に処理されているので調べてもムダです。 素であれば , その座標をバッフアに記 画プラグインの仕様については , 詳しく説 同様に , 下の行を処理するときは , 上の画 明しませんが , プログラムを理解するうえ 録する。ただし , このバッフアに記録 素を調べるのはムダです。 で最低限必要となる関数の解説を TabIe 1 しようとする画素の左に , バッフアに にまとめます。 TabIe 1 を参照すれば , プ ですから , 座標を記録するバッフアに 己録済みの画素を含む領域内画素列が ログラムの流れは追えるかと思います。 上に移動してきたのか , 下に移動してきた 接している場合は , バッフアへの記録 のかを示す情報を追加し , " きた方向 " によ をスキップする まずは , 高速化を考えずに基本的なアル ゴリズムに従って実装したプログラムを L って , 調べる画素を制限することができま 4 ) 走査中の画素が , 前回走査した行の 右端を超える場合は , 3) の i)—iii) の条 す。これだけで , 画素を調べる処理が約半 ist4 に示します。 List4 は , ユーザがクリッ 件判断を行わず , 常に上下の画素を調 クした座標を始点として , そこからシード 分になるので , そのぶん高速処理が可能に べながら走査処理を続ける ペイントを行います。 なると考えられます。ただし , この方法で 処理を省略できるのは前回の走査での右端 5 ) 1 行の走査が終わったら , バッファ上 ペイント処理のメインとなるのは , PM cDrawIt 関数です。 Pmacs プラグインでは Fig. 3 走査処理の高速化 ユーザがクリックした座標は , PMsGetEn tryPoint で取得できるので , この座標を始 下の行は , すでに処理が完了し 点として , シードベイントを行います。座 ているので上方の画素について のみ領域内外の判断を行う 標を記録するバッフアは , List 3 で示した 配列をリングバッフアとして利用していま す。 前述のように , バッフアに記録する座標 の数が , 配列の要素数を超えると処理が破 綻します。リングバッフアを用いた場合に は , 先頭 ( 座標を記録すべき点 ) が末尾に追 いついたときが , ノヾッフアがいつばいにな ったときと判断できます。 List 3 ではこの チェックを省略しているので , バッファあ ふれが発生したときの動作は保障されませ 画像処理を極める ニ = ロ 太線内画素の下方画素は , 前回の走査で は未調査なので , この部分は上下両方の 画素について領域内外の判断を行う 今回の走査行 前回の走査範囲 上の太線内の画素において下方画 素の判定を忘れると , この画素を バッフアに記録できない 凡例 ロ領域外 ロ領域内 ・塗りつぶしが完了した画素 ■下の行の探索を省略できる画素 画像処理を極めるアルゴリズムラボ 101
List $n = ” strn 【 1 】 = ” e Ⅱ 0 第・ 「問 21 」 変数 $ a へのリファレンスを $ aref に代入する処理は次のどれか。 【 1 】① $ ー ②@ ③ % ④ ! 答え【 1 】 [ 問 2 引 【 2 】① $magic[$m] ② $magic[$m-l ] ③@magic[$m] ④@magic[$m-l ] ( 各 3 点 X2 ) 【 2 】 ② $aref = ($a) ; ① $aref = $$a, ③ $aref = *$a; ④ $aref = %$a, [ 問 2 ListI 4 は , ヒアドキュメントという手法を使って , 複数行を クオートする例である。【 1 】 , 【 2 】に適切なものは次のうちどれ ( 2 点 ) か ① EOF List p て土【 1 】 ② EOF; ③ <<EOF 〇 4 <<EOF 標準入力から 1 行を読み込んで , 文字列の最後の文字をカッ トしたものを $ st 「に格納したい。期待どおりに動作するのは次 のうちどれか。 ① $str = chop(STDIN) ; ② $str = chop (<STDIN>) ; ③ $str = chop($tmp = <STDIN>) ; ④ chop($str = <STDIN>) ; 問 23 List 13 のサブルーチン weekday は , 年 , 月 , 日の値の入った 3 つの引数を与え , それに対する曜日を 0 から 6 の値で戻す処理を 行うものである。【 1 】 , 【 2 】に適切なものを各選択肢の中から選 ( 3 点 ) sub weekday { List びなさい。 て e しれ ()y 十土北 ( $Y / 4 ) ー int($Y/100) 十土北 ( $Y / 400 ) 十【 2 】十 (d) $y-- if ( 師く 3 @magic = ( 0 , 3 , 2 , 5 を 0 , 3 , 5 , 1 , 4 , 6 , 2 , 4 リ (C) 2001 Phinloda, AII rights *. く / の </htm 【 2 】 答え【 1 】 問 25 ( 各 2 点 X2 ) 【 2 】 List 15 の処理と List 16 の処理は一見同じ処理のようだが , 実 は $ ⅱ ne に入る内容が異なる可能性がある。それはどのような場 合か List while ( く I わ ) { $line = $- # こに処理を書く ( 2 点 ) List ここに処理を書く while (defined($line = <IN>) ) 46 C MAGAZINE 2001 3
行できるものが多いようです。 この受け取ったスクリプトファイルから 1 つの命令となる「単語 ( トークン ) 」を取り 出します。言語仕様によってどんなものが 1 つの単語となるかはわかりませんが , 処 理の 1 つの基本となる単語をまずは取り出 すことから始まります。これを「字句解析」 といいます。 単語を取り出すことができたら , その単 / * 関数のポインタと命令の対のコード * / typedef 土 n し ( *cmdfuncptr ) ( char * s / * 対応する関数へのポインタ * / 1 インタブリタの簡単な例 cmdfuncptr cmdfunc; typedef struct ( / * 1 命令取り出す * / {NULL, 即阯 } , zombie {Cmd3, {Cmd2, "meka") , {Cmd1, "taco"} , cmd-t cmdlist[ ] = / * 命令のリスト * / int Cmd3(char *s) / * 命令その 3 * / 土 n し Cmd2(char *s) / * 命令その 2 int Cmd1(char *s) / * 命令その 1 * / } cmd—t; char * 町 void paser—st て ing ( void ) / * 文から命 -p を取り出す * / return S ー / * 叩〒 を切り出して詰める / * s におおもとのテキストから * / char far *getword(void) s = getword( ); / * 1 叩 -p 得る * / 土 n し土ー char far * 語に対応した機能を実行します。単語によ っては , ほかの単語と重なっていることも あるでしようし , 計算を行うような式の形 となっているものもあるでしよう。ある単 語同士の間には優先順位などを決めている こともあります。こうした単語同士の関係 に注意しながら , 処理を実行していくこと を「構文解析」と呼びます。 インタブリタが持つ基本的な構造は , のような字句解析と構文解析 , それによっ て行われる具体的な処理命令 , 場合によっ てはエデイタ部分などスクリプトを入力し たり編集する部分が組み合わされてできて います ( Fig. 1 ) 。 ・それぞれのアルゴリズム 構文解析や字句解析は昔からさまざまな アルゴリズムが考えられていました。本誌 でも 2000 年 5 月号の特集「スクリプト言語を 作ろう」などで何度か紹介しています。構 文解析として代表的なものを簡単にいくつ かあげてみると , ・再帰下降解析 「式」「項」「演算子」などに分け , それぞ れの解析ルーチンを作り , そこへ 1 単 語ずっ与えて解析を行う。「演算子」ま で解析したら「式」へ戻るというように 解析の終端に差しかかったらほかのル ーチンを再帰的に呼び出していく ・ LR 解析 単語が集まった文字列があるとして , それを左から順に読み込む。得た単語 同士の塊をさらに右側から見て単語同 士の優先順位などといった結合具合を 調べる。その時点の状態で行うべき処 理と次の状態への移動先を対にした解 析表を使うのが一般的。また , 左側か などといったものがあります。 ら調べる LL 解析もある この「 X 」を処理することで得られますね。 ることになります。最終的な計算結果は , 「 10 + 1 」を計算してから , 両者の値を「 >< 」す -1 ) >< ( 10 + 1 ) 」のような場合 , まず「 3 -1 」 , がされたデータとなります。たとえば「 ( 3 解析された単語は , それぞれに順序付け そこで , これを「根」と考えると , ほかの計 算部分はその根につながる「枝」と考えられ ます。まとめるとデータ構造のひとつであ る木構造となり , これを「解析木」と呼ばれ ています。実装の際にはデータをスタック 構造にして処理する方法がよくとられてい インタブリタの構造 どのような形であれ , 「スクリプトファ イルからある処理に変換する」ということ を考えると , インタブリタとは一種のフィ ルタのようなプログラムといえます。ソー スコードにするのなら List 1 のような形で す。「単語を読み込み」 , 「単語を計算順に 並べ替え」 , 「単語に応じた処理を呼び出 す」という処理の流れになりそうです。な お , ListI では分岐処理が多くなることを 考えてテープルジャンプを用いています。 WonderWitch の特性を考えると「なるべ く小さく」 , 「なるべく速く」というプログ ラミングスタイルが求められます。またメ モリの制約があるため , 再帰処理などもで きるだけ避けたいところです。 ■フレームワーク「らむね」 こでちょっと過去を振り返ります。筆 者の今までしてきたプログラミングを考え ると , だいぶ偏っているとは思いますが 「その時点の状態を示す変数」と「その変数 に応じた処理」 , 「状態を進める処理」とい う一連の状態遷移を扱うものばかり作って きた気がします。今回扱うようなプログラ ムで再帰処理をしない方法というと , 「 1 つの状態」を処理する関数をいくつか作り , その振る舞いを定義した表を多用すること 0 になるはずです。 ・・・いや , 白状します。 私はこういうプログラミングスタイルが好 きなんです ( 笑 ) 。 これらを効率よくプログラミングできな いかと考えて自分で作ってみたフレームワ ークが「らむね」です ( Fig. 2 ) 。らむねの構 成要素は「フィールド」 , 「ハンドラ (Famili ar : 使い魔 ) 」 , 「スペル」の 3 つがあります。 まずはだいたいのイメージをつかんでもら 1 26 / * 命令に対応した関数を探す * / 00 { / * 命令の比較 * / if (strcmp(s, cmdlist[i] . s)) { / * 関数を呼び出す * / cmdlist[il . cmdfunc(s); ) while (cmdlistti] . s ! = C MAGAZINE 2001 3
C + + を , 機能拡張された C 言語と捉えて使 うのも , 1 つの方向性でしよう。 イベント駆動型フログラム 最近の OS のインタフェイスは , GUI が標 準になっています。このため , GUI 上で動 作するウインドウアプリケーションを作り たいと考える人も多いと思います。 ANSIC は標準入出力をサポートしている ので , CUI 上で動作するプログラムを作成 することができます。ですが , GUI をサポー トする標準的な入出力の設定はないため , GUI 上で動作し , ポインティングデバイス ( マウスなど ) で操作できるプログラムを ANSIC の範囲内で作成することはできませ ん。 このため本連載では , Windows, Maci ntosh, X(UNIX のウインドウシステム ) でウ インドウを開き , その上にボタンなどを配 置し , マウスで操作するといったウインド ウブログラムの作り方について , まったく 言及してきませんでした。 割り込み処理 現在の一般的なウインドウ , すなわち GUI のプログラムは , OS にかかわらず , 実は同 じような骨組みで成り立っています。これ らは , イベント駆動型と呼ばれるタイプの プログラムです。イベント駆動型とは , 割 り込み処理の集合体で構成されるプログラ ムです。この「割り込み処理」とは , コンピ ュータが「ある状態になったときに実行さ れる処理」のことで , コンピュータのハー ドウェアとデータのやり取りを行う部分で よく使われています。 たとえば , キーポードからの入力を取得 する場合を考えてみましよう。まず考えら れるのは , 作成するプログラムの中で , とあるごとに何が押されたかキーポードを 監視する ( この手法はポーリングと呼ばれ る ) という方法があります。これは簡単で よさそうに見えるのですが , プログラムが 66 C MAGAZINE 2001 3 コラム 2 前回の演習問題の答え ・ゲームの作成 行っていても , キーポードの入力は履歴に ば , プログラム本体が時間のかかる処理を るシステムにするのです ( Fig. 2 ) 。こうすれ 文字列を取得する」プログラムで構成され み処理と , 「その履歴を利用して押された 押されたときに履歴を残す」という割り込 これを回避するために , 「キーポードが てしまうのです。 グラム側の都合で押していないことになっ ません。つまり , 押したはずのキーがプロ っていないときは押されたキーを検出でき ほかの計算などを行っていて監視状態にな 夫してみてください。 抑えることができるでしよう。いろいろ工 アの違い , 動作環境の違いによる悪影響を イミングを合わせたりすれば , ハードウェ ぶしではなく time ( ) を使ってより正確にタ うのが理想です。ループ処理による時間つ ち時間の調節をプログラム側で自動的に行 に大きなバラつきが考えられる場合は , 待 プラットホーム (OS) であっても動作環境 しなければなりません。このように , 同じ ってくるので , ほどよく遊べるように調節 よってループが回り切るまでの時間が変わ ムは , 実行するコンピュータの処理速度に 調節を行っています。このようなプログラ この ansl . c は , ループ処理で待ち時間の るでしよう。 ームプログラムを作成するうえで参考にな を行ったりしています。これらの手法はゲ 変わったり , ループによる動作時間の調節 とで , 動作させるたびに出題される問題が ansl . c では , 乱数の種を時間から得るこ きのような側面も持っています。 でキーを押すことを要求される , もぐら叩 ピングソフトです。ランダムなタイミング 収録しました。この ansl . c は , 一種のタイ VcmagaVCVans> ティレクトリに ansl . c を す。解答の一例として , 付録 CD ー ROM のく 簡単なゲームを作ってみようという問題で まず , 改行によるスクロールを利用した ・ラベルジャンプ 次に , ラベルジャンプを効率よく行うた めの方法です。これはたとえば , ラベルの インテックスを作成する方法や , ラベルを キャッシュする方法などを考えることがで きます。 ラベルのインテックスの作成をする方法 とは , あらかじめラベル名とそのラベルに fseek ( ) で到達するためのファイル先頭から の距離情報をセットにして準備することで す。プログラム起動時にすべてのラベルに ついて調べて情報を 1 回作成しておけば , 実際のラベルジャンプはこのテータを元に 行うことができます。 ラベルをキャッシュする方法も , 基本的 な考え方はインテックスと同じです。こち らは最初にまとまったテータを作らずに ラベル検索実行中に見つけたラベルに関し てそのつど記録していきます。 こで , シ ナリオファイルのどの位置までラベル検索 を行ったかも記憶しておきます。こうして おけば , ラベルジャンプの際には , まず記 憶しておいたラベル情報を調べてそこにラ ベル情報があればそれを使ってジャンプし , なかったらラベル検索を記憶した位置より 後ろで実施していきます。 この手法はインデックスの作成より複雑 ですが , 必要なときに必要なだけ検索する ので , 起動時にまとまった時間を取られず に済みます。 残っているので取りこばす心配がなくなり ます。一般的なコンヒ。ュータシステムでは , この割り込み処理の対象としてキーポード やマウス , 通信ポートやタイマなどを設定 できるようになっています。逆にいえば , 人力が取りこぼされると困るようなデバイ スは , 割り込み処理を設定する必要がある のです。 コンピュータサイエンスで習うタイムシ ェアリングによる並列処理も , タイマによ る一定時間ごとの割り込みによって実現さ れています。この場合の「ある状態」とは ,
る期間が長くなってしまうため , バッファ 塗りつぶす」という処理ですが , シードベ さて , シードベイントに話を戻しましよ サイズの限界を迎えやすくなる ) 。今回は , イントとしては , 「ある色に突き当たるま う。シードベイントでは FIFO , LIFO どち らのタイプのバッフアを用いても処理自体 でを塗りつぶす」というものもあります。 FIFO バッフアを利用してシードベイント を実現することを考えます。 FIFO'S ッファ これは , 領域の境界が特定の色で囲まれて は破綻しません。しかし , 同じサイズのバ を用いた場合のシードベイントの処理例を いる場合に利用されます。ちなみに , " 領 ッフアを用意した場合には , FIF()'S ッファ を用いるほうがより複雑な領域を塗りつぶ Fig. 2 に示します。 域の境界が特定色 " となっているシードベ すことができるようです (LIFO バッフアの こまで説明してきたシード イントを実現するには , こまでの説明の ところで , 「同一の色であれば」という条件を「ある特 ほうが , 座標がバッフア内にとどまってい ペイントのアルゴリズムは「同一の色内を シードベイント処理の流れ ( 1 ) 初期状態 ( 4 ) バッフア内の A を新しい始点とする 一 000 、 0 0 ~ 00 増■ 00 0000 ■ 00 000 000 、 0 0 ■■■■ 0 ■ バッファ B C D 始点とした A の座標を バッフアから除去する C B ( 5 ) 新しい始点を基準に ( 2 ) ( 3 ) の処理を繰り返す。ただし , すでに 塗りつぶしが完了している画素は , 領域外として扱う バッファ E の座標をバッフアに 記録する ( 2 ) 始点から領域外となる画素に突き当たるまで左方向に走査して 領域内の左端を求める 000 000 0 0 ■ 00 ■ 0 ■ 0 ■ 000 ( 6 ) 以下 , バッファ上に新しい始点となるべき座標がなくなるまで , ・・と新しい座標を取り出し , それぞれにつ 順に B , C , D , E , いて ( 2 ) ( 3 ) の処理を繰り返す ( 3 ) ( 2 ) で求めた画素から右方向に領域外となる画素の手前まで走 査しながら塗りつぶし処理を行う。同時に , 塗りつぶした画素 の上下を調べ , その画素が新しい始点となりうるなら , バッフ アに座標を記録する の左に記録済みの域すでに A の座標が記録 内画素がないのでバッされているので , バッ フアに座標を記録するフアへの記録は不要 ` 、 000 り・ 0 ■ 0 0 当 00 0000 バッファ A B C D A, B, C, D の座標を バッフアに記録する 凡例 ロ領域外 ■始点 ロ領域内 ■今回塗りつぶした画素 ゞ塗りつぶしが完了した画素 C の左側が領域内画素に接 していないので , バッファ に座標を記録する 100 c MAGMINE 2001 3
カリ 画像処理を極める 5 ) バッファ上に , 次の始点となるべき座 標がなくなれば処理終了 こで , バッフアとは , 複数の座標デー タを蓄積可能で , バッフアに蓄えられたデ ータは取り出しを行うまで , 削除されるこ となくどんどん溜まっていくようなデータ 形式です。プログラム的には配列や単方向 リストなどで実現するのが一般的でしよう。 上記の処理の流れによって , いちおう期 待どおりの塗りつぶし処理を行うことがで きます。しかし , この流れでは走査してい る行の上下にある領域内画素の座標をすべ て記録することになり , 効率的とはいえま せん。手順の 2 ) において , 領域内の画素が 見つかるとその右側に連続する領域内画素 はすべて塗りつぶされることが保証されま す。すなわち , バッフアに記録する座標も 最も左の 1 画素を記録しておけば十分だと いうことがわかります これを考慮して処理の流れを考えると前 述の手順 3 ) は次のようになります。 3 ) 上記の 2 ) で走査するとき , 検索点の 上下の画素を調べ , 領域内の画素で あれば , その座標をバッフアに記録 する。ただし , このバッフアに記録 しようとする画素の左に , バッファ に記録済みの画素を含む領域内画素 列が接している場合は , バッフアへ 日 FO バッフアへのデータ登録・取り 出しを行うプログラム 0 List #define BUFSIZE 2000 / / データを格納する領域 int buffer[BUFSIZE]; / / バッファ操作のための情報 int head=0; int tail=0; / / バッフアへの登録 VOid setData(int X) buffer[head]=x; head 十 / / バッフアからの取り出し int getData ( VOid ) int res ー res=buffer[tail ]; tail 十十一 return res ー の記録をスキップする さて , ここでシードベイントで利用する バッフアについて , もう少し詳しく見てい きましよう。 シードベイントで使用するバッフアは , 「不特定多数のデータを一度に記録したり , 取り出したりできるもの」でなくてはなり ません。このようなバッフアとしては , バ ッフアからの蓄積データの取り出し方によ って 2 種類が考えられます。すなわち , 最 初に記録したものを最初に取り出す“日 F 0 バッファ” (FirstInFirstOu レヾッファ ) と 最後に記録したものを最初に取り出す“凵 F 0 バッファ” (Last ln First Out) バッフアで す [ 注 ] 。どちらのバッフアも配列や単方向リ ストなどを利用して実装できますが , ではその一例として配列を利用して FIFO バッフアへのデータ登録 , 取り出しを行う プログラムを List 1 に LIFO バッフアへの データ登録・取り出しを行うプログラムを List2 に示します。 List 1 , 2 ともに処理はさほど変わりませ んが , FIFO バッフアでは次に取り出すべ きデータが記録されている位置と次にデー タを記録すべきバッフアの位置が異なるの で , それぞれを別の変数に格納しておく必 要があります。 また , List1 の実装では取り出し終えた 凵 FO バッフアへのデータ登録・取り 出しを行うプログラム #define BUFSIZE 2000 / / データを格納する領域 土 n セ buffer[BUFSIZE]; / / バッファ操作のための情報 int sp=O; / / バッフアへの登録 void setData(int x) buffer[sp]=x; sp + List / / バッフアからの取り出し int getData ( void ) int res; res=buffer[spl; return res ー データがいつまでも削除されることなく残 ってしまうためムダが多く , このままでは 処理が進むに従って配列の限界に達する可 能性が高くなります。ですから , 実際のプ ログラムでは , List3 のように配列の限界 に達したら配列の先頭に戻るように調整し てやる必要があります。このように工夫し た FIFO バッフアのデータ形式を , 先頭と 末尾がつながった形式のイメージから , “リングバッファ”と呼ぶ場合があります。 また , FIFO バッフアと LIFO ノヾッフアの いずれの場合でも , 蓄積したデータ数が配 列の数を超えると処理が破綻するので , 問 題が起こらないように十分に大きな配列を 用意してやる必要があります。この方針は , メモリなどのリソースに多くのムダを発生 させますが , 配列を利用する場合は仕方な いでしよう。このようなリソースのムダは 単方向リストを用いることで回避できます が , シードベイント用のバッフアにおいて は , メモリの確保・解放という処理が , か なり頻繁に発生するため , 配列による実装 に比べると格段に処理速度が遅くなります。 どちらの方法をとるかは場合によって見極 める必要がありますが , 今回は , 配列を用 いる方法がよいと思われます。 [ 注 ] F 旧 0 バッフアは「キュー」 , 凵 FO バッ フアは「スタック」という呼び方をされるこ ともあります。 曰 FO のリングバッファ #define BUFSIZE 2000 / / データを格納する領域 土 n セ buffer[BUFSIZE]; / / バッファ操作のための情報 int head=0; int tai トの 〃バッフアへの登録 VOid setData ( int X ) buffer[head]=x; head=(head 十 I)%BUFSIZE; / / バッフアからの取り出し 土 n し getData ( VOid ) int res; res=buffer [tail tail=(tail+1)%BUFSIZE; return res; List 画像処理を極めるアルゴリズムラボ 99
刃レゴリ・ 第 18 回 画像処理を極める デジタル画像での図形描画④ 領域の塗りつぶし ~ シードベイント 昌達 K'z をした領域を塗りつぶすアルゴリズム 指定した画素と同じ色の連続した領域 の 1 っとして古くからよく利用されて を別の色で塗り替えるという処理は , いる「シードベイント」の手法を紹介し ペイントツールの機能としてはごく一 魅 : 意 般的なものです。今回は , 任意の形状 ます。 塗りつぶし処理が行われるのは , A の領域 る条件を満たす」とは , 内部のみで , B , C などの領域はたとえ画 ・画素の値が , ある範囲内に収まってい はじめに 素値が A の領域と同じであっても塗りつぶ る場合 前回は , ソリッド図形 ( 形の内部まで画 ・変化の緩やかな部分を同一領域とみな されることはありません。 素が存在する図形 ) を描画するアルゴリズ シードベイントアルゴリズムのおおまか す ムとして多角形 ( ポリゴン ) の内部を塗りつ な流れは以下のようになります。 などさまざまなケースが考えられます。 今回は , 領域内を判断する条件として「画 1 ) 始点から左向きに走査し , 同じ色の部 ぶすアルゴリズムを紹介しました。今回は , 素値が同一の部分を領域とみなす」という 分の左端を検索する ソリッド図形の形状を一般化して , 任意の ものを基本に考え , その条件を満たす領域 2 ) 求めた左端から右向きに走査し , 同じ 領域内を塗りつぶすアルゴリズムを紹介し を塗りつぶすためのアルゴリズムを取り上 色である間は塗りつぶし処理を行う ます。 3 ) 上記の 2 ) で走査するとき , 検索点の上 領域を塗りつぶす処理を実現するには , げます。このような目的に利用できるアル まず , 何らかの方法で領域の情報が与えら ゴリズムはいくつか存在しますが , 今回は 下の画素を調べ , 領域内の画素であれ ば , その座標をバッフアに記録する れる必要があります。領域の表現の仕方は シードベイントを紹介します 4 ) 1 行の走査が終わったら , バッファ上 大きく分けて , の座標を 1 っ取り出し , その座標を新 ( 1 ) 領域の外郭となる図形の形状が何ら シードベイント しい始点として , 1 ) からの処理を繰り かの形で与えられている場合 ( 2 ) 領域の境界となる部分は特定できな シードベイントは , 画像内のある 1 点を 返す いが , 任意の画像が与えられ , ある 始点として , その周囲 ( 近傍の画素 ) で始点 特徴を満たす部分を領域内とみなす と同じ色の部分を塗りつぶすためのアルゴ リズムです。この場合 , 始点の指定は人手 ことができる場合 の 2 通りのパターンが考えられます。 で行うことが一般的です。つまり , シード ペイントとは , 「人手で指定された 1 点 ( 始 前回のスキャンラインコンバージョンア ルゴリズムは ( 1 ) のケースで , 領域の形状 点 ) を基準として , 始点と同じ画素値を持 を任意の多角形で与えて , その内部領域を つ領域を塗りつぶしていく」という処理な 塗りつぶすアルゴリズムです。 のです。ただし , 塗りつぶしを行う領域は 今回は , ②のケースとして , 「画像内で 連結している必要があります。 " ある条件 " を満たす」部分を塗りつぶす処 たとえば , Fig. 1 に示すような画像にお 理を考えます。ここでいう , 「画像内であ いて A の領域内に始点が与えられた場合 Fig. 1 シードベイントによる塗りつぶし 領域外 ■始点 98 c MAGAZINE 2001 3
[ 問 15 」 ② ・解説 続く名前をファイル名とみなし , そのファ 難しいと思われます。ファイル演算子 - s は , とはできますが , これより簡単に書くのは ほかにいろいろ苦労したコードを書くこ ・解説 $size = -s $filename; [ 問 16 」 算子の - e を用いて処理します。 ファイルの存在確認はファイルテスト演 イルのサイズを得ます。 ・・① ・解説 「問可 opendir を使ってティレクトリの一覧を得 50 C MAGAZINE 2001 3 ③ っているので , この条件が成立しないとき ②の処理は , 判定部分が ()i = 100 ) とな を実行するというものです。 ①の処理は , $ i の値が 100 でなければ p 血 t while, un ⅱ 1 の 4 種類があります。 くことができます。修飾子には , if, unless, 単純文の後ろには , 修飾子を 1 つだけ置 ・解説 [ 問 18 」 して処理することは可能です。 レクトリのなかから必要なファイルを選択 ルを使えば , 叩 end ⅳを使わなくても , ディ る処理の例です。公開されているモジュー に p ⅱ nt を実行しなければ同じ処理になりま せん。したがって , こは if ではなく unl ess を使うのが正解です。 実際にプログラムを書く場合は , このよ うなひねった書き換えではなく , 江 ( $i ! = 100 ) のように書いたほうがいいでしよう。 ・解説 [ 問 19 」 Perl では , 複合文は , ③ ・解説 ② 念です。リファレンスを使えるかどうかが , リファレンスは Perl 5 から追加された概 て参照するには , $$aref とします。 この例で , $ a の内容をリファレンスを使っ 「 \ 」演算子はリファレンスを生成します。 ・解説 [ 問 21 」 $ $ n を参照すればよいことになります。 文字列 " s ドですから , $ s 仕を参照するには 数を参照することができます。 $ n の内容が ます。つまり , その文字列を名前とする変 はシンポリックリファレンスとして扱われ 文字列をデリファレンスすると , その値 です。 まうかもしれませんが , PerI としては誤り C に慣れた方はうつかり elseif と書いてし のような形式を用います。 BLOCK … else BLOCK if (EXPR) BLOCK elsif (EXPR) perl 使いを極められるかどうかの壁になる ので , これから perl を使おうと考えている 方は , 気合を入れてマスターしてみてくだ さい。 [ 問 22 」 ④ ・解説 ch 叩はカットした文字を値として返しま す。したがって , $ s 仕に ch 叩の返した値を 代入しているものは , すべて期待はずれの 結果になってしまいます。代入式は左辺値 なので , ch 叩の引数として与えることがで きます。 [ 問 23 」 ・解説 ・・② 曜日を求める公式は有名ですが , ちょっ と複雑なので暗記するのもめんどうです。 いつでも見られるようにメモしてあれば , 覚える必要もないと思います。それでは問 題にならないのですが , 空欄を埋めるだけ であれば常識で解けるようにしてあります。 最初の空欄は , 引数をサプルーチンに取り 込む処理で , システム変数である@ーを使い ます。次の空欄は , 配列変数の@magic を 使うことがわかれば簡単です。引数には年 , 月 , 日が与えられるのですから , ほかに使われていない変数である $ m が使わ れるはずです。 $ m の値は月が人っている ことになっているので , すなわち 1 から 12 の 値をとると考えられます。 これに対して , 配列変数に代人している 値は 12 個で , $magic [ 0 ] から $magic [ 11 ] に よって参照できることになるので , $m -1 を インデックスにした $magic [$m - 1 ] が正解 です。
特集 プログラミング 期末試験 い方をしたあとでの斤 ee の呼び出し時点で です。ただし , このように書くと , 処理系 ても , コンパイルすると実行ファイルがで きることがあります。その場合 , math. h に ポインタが NULL であるかどうかを判断し によってはコンパイル時に警告のメッセー なくても , 期待どおりの処理が行われま あるプロトタイプ宣言がない状態でコンパ ジが出ることがあります。警告が出る理由 は , 実は , す。 イルされてしまったために , 予期せぬ値が 出ることがあります。 [ 問 16 」 ループ内部の処理で , sin 関数には i を 10.0 と書くつもりで , うつかり「 = 」を「 = 」と書 で割った結果を与えています。ということ いてしまうというミスを防ぐためですが は , i には sin 関数に与えたい数値の 10 倍の 今回の関数は , うつかりではなく「 = 」が目 値が入ってなければなりません。 1 から 2 ま 的どおりの処理となっていますから , 警告 で 0.1 きざみにループさせたいので , 10 倍し は無視してかまいません。 ヘッダファイル内でシンボルを定義する て , 10 から 20 までの値をとるようなプログ ポインタ dst が指している内容は * dst で , ラムになれば OK です。したがって , 【 2 】の とき , すでにそのシンポルが定義されてい その値を src が指している先に格納していき たらスキップするように定義を書けば , 正解は 10 ということになります。問題は 2 ます。格納した値がそのまま式の値となる 重に定義するエラーから逃れることができ の値で呼び出す必要があるかどうかですが ので , その値が。 \ 0 ' であればコピーは終了し ます。これはヘッダファイルではごく普通 「 2 まで」という表現はその値を含むと解釈 て while のループを抜け出します。和 ' では に使われる手法なので , 標準ヘッダファイ するのが自然なので , こは 2 でも呼び出 ない場合 , それぞれのポインタは + + 演算子 ルなどを見て実際どうなっているかを確認 すと解釈しました。したがって , i の値が 20 によって , 次のバイトを指すことになり , してみてください。 のときも , ループを実行する必要がありま す。すなわち , 【 3 】には 20 に 1 を加算した 21 目標は , まだ定義されていない場合に定 次の処理を行うことになります。 義などを行う処理をしたいのですから , #ifn NULL は空ポインタを意味する定数で , が入ります。 【 4 】は , double の引数があるときの p ⅱ n ば ヌル文字の和 ' とは意味が異なりますから , def—#endif で囲んでやれば OK です。 の書式文字列の問題です。 % d は整数 , %s は こでは間違いです。 [ 問ⅵ 文字列を引数に与える場合の書式ですから , [ 問 15 」 正解は % f です。 【 3 ト④ [ 問 18 」 浮動小数点数の計算で誤差が発生する 可能性があるから。 ・解説 浮動小数点の演算では , 0.1 を 10 倍しても 1 になるとは限りません。なぜなら , 0.1 と いう値は , 2 進数では割り切れないからで す。整数演算なら , オーパフローなどが発 生しないかぎり , 誤差は発生しません。確 実に期待した回数だけループさせるために は , 整数でループカウントして , それを使 って使いたい値を生成するのが基本です。 この場合は , 1.0 に 0.1 を 10 回加えても 2.0 び ったりになるとは限らないため , もし 2.0 よ りほんの少しでも大きな値になってしまう ・解説 ・・③ ・解説 ・解説 【 1 】数学関数を使うには , math. h をインク NULL というのはポインタのとる値とし ては特殊なので , 関数によっては , NULL ルードしなければなりません。これを忘れ を指定した場合にエラ ーになることがありま す。ただし , 斤 ee の場 void sample(void) 合は , 規格により , N struct f00 ( ULL を指定した場合に は何もしないと定めら れているので , free(N ULL) を実行しても問 題ありません。 List 20 は , 構造体を 部分的に使っている例 ですが , このような使 char * 町 char * 場 struct f00 X ー x. 日 = も / * 使わない * / x. セ = 日 00 ( 4 st て cpy ( x. 新 a を / * ( ここで何か x を使った処理を行う。例なので省略 ) * / / * 処理が終わったら、 x に確保した領域を開放する * / free(). 8) free(). t) 特集実力チェックプログラミング期末試験 c 言語編 19