アルゴリズム・テータ構造入門 たがって , ② , ③ , ⑤は旦回実行されます。 るアルゴリズムて、は , 計算量は O ( 1 ) , 0 ( 10g 以上をまとめると関数 sea 「 ch の各文の実行 n) , O (n) , O (n log n) あたりまて、に限られ 回数は TbI. 1 のようになります。 ます。 O(n2) となると , ちょっと大きなデー この数字をもとに , 各ステートメントの タを扱おうとすると , かなり苦しくなりま 計算量を求めてみます。 す。 今度は計算量の乗算について考えてみま しよう。 0 ( f ( n ) ) の計算量をもっループを 0 ( g ( n ) ) 回繰り返すとすると , 全体の計算量 ① の計算量 0 ( 1 ) ②③⑤ の計算量 O(n) ④ の計算量 0 ( 1 ) ⑥ の計算量 0 ( 1 ) となるのて , この合計を求めます。 関数 sea 「 ch の計算量 = 0 ( 1 ) + 0 ( n ) + 0 ( 1 ) + 0 ( 1 ) =O(max(1, n, 1 , まず , 基本的な操作の計算量を定めまし 結局 , 関数 sea 「 ch の計算量は 0 ( n ) という となります。たとえば , 0 ( n ) のループを旦 よう。アルゴリズムやプログラムては , 数 ことになります。つまり , リニアサーチを 2 値の演算 , データの入出力 , ポインタをた 回繰り返すと , 全体て 0 ( n2 ) の計算量になり 使うと , テープルに登録されているデータ ぐる , データを代入する , などが基本操作 ます。 の個数に比例した時間がかかることになり てあると考えられます。このような処理に それて、は , 関数 search (List1) の計算量を ます。 100 個のデータが登録されていて , サ 調べてみましよう。①は , 関数 search が呼 かかる時間は , 入力データの分量にかかわ ーチに平均 1 ミリ秒かかったとしましよう。 び出されると , 必ず 1 回だけ実行されるの らず一定て、す。したがって , その計算量は もし , 登録するデータを 100 倍 ( 10000 個 ) に O ( 1 ) て表現されます。ここて、 , 0 ( 1 ) は , n て、 , O ( 1 ) になりますよ wh ⅱ e ループの中て、毎 すると , 平均サーチ時間も 100 倍 ( 100 ミリ秒 ) 回実行される② , ③ , ⑤は , 基本的な操作 を含まない関数 , つまり定数を意味してい に増加することになります。 ます。ただし , 関数呼び出しを含む演算や て、すからそれぞれ 0 ( 1 ) て、す。ループ実行 1 回 代入文については , O ( 1 ) て、はなくて , 呼び 当たりの計算量は , これら 3 ステートメント の計算量の合計になるのて、 , 出される関数の計算量がかかることに注意 0 ( 1 ) + 0 ( 1 ) + 0 ( 1 ) してください =O(max(1, 言語によっては , 配列をまるごと リニアサーチは , O (n) のアルゴリズムて、 = 0 ( 1 ) 代入したり演算したりてきるものもありま すが , テープルサーチを行うアルゴリズム となります。 wh ⅱ e ループは平均すると n / 2 回 すが , この場合の計算量は配列の大きさに にはもっと性能がいいものもあります。 実行されるのて , wh ⅱ e ループ全体の計算量 依存することになります。 こて、は , バイナリサーチ ( 2 分法 ) の計算量を 次に , 計算量の加算を考えてみましよう。 求めてみましよう。 は , t 算量 O ( f ( n ) ) , O ( g ( n ) ) のふたつの操作を バイナリサーチとは , あらかじめキーの = 0 ( 1 ) * 0 ( n ) 連続して実行する場合の計算量は , 昇順 ( 降順て、もかまいません ) にソートされ ている配列に対して , ある特定のキーをも となります。④は , データがテープル内に っデータを探し出す検索法てす (List2)0 になります。計算量の大小は , 関数 f(n), g 存在していた場合に 1 回だけ実行されます。 のプログラムては , 変数 low に着目している (n) の増加率によって決まります。 n をどん ⑥は , ④とは反対に , データが見つからな どん大きくしていくことによって , 関数の 範囲の下限 , 変数 high に上限をつねにセッ 増加率の大小がわかります。計算量の評価 かった場合に限り 1 回だけ実行されます。 トするようにしています。そして , 着目し ④ , ⑥ともに , 1 回しか実行されないのて , ている範囲の中央 mid 引 e の要素とキーとを てよく使われる関数としては , n の k 乗 ( 1 = 計算量はともに 0 ( 1 ) てす。 こまてて、求め (n0) , n, n2, n3, .. ) , 10g1n , 2n ( 2 の n 乗 ) 比較して , 一致すれば見つかったことにな た各ステートメントの計算量は TbI.1 のよう などがあります。 これらの間には , ります。一致しなければ , 着目する範囲を になります。 増加率 前半分または後半分になるようにして low, 大 さて , 各ステートメントの計算量が求め high をセットして繰り返します。バイナリ られたのて , 合計をとれば関数 sea 「 ch の計 1 10g n nk サーチの過程を Fig. 1 に示します。 2n という関係があります。ただし , 実用にな 算量が得られます。それぞれ , List2 から , バイナリサーチの計算量を求 方 の 0 ( 1 ) * ( n / 2 ) 一言 アルゴリズムとデータ構造入門 81

の場合はアドレス取得演算子 ) を用いてその 変数のアドレスを取り出せます。 &aC0] とすれば a [ 0 ] の , &aC3] とすれば aC3] の , それぞれアドレスを取り出せま す。ここてこのアドレスを格納するための ポインタ p を用意しましよう。 int *p; 配列変数のアドレスをポインタに代入は p=&aC0]; List 1 a [ 5 ] ; int 0 1 よワ 3 っ 0 4 -0 ^ 0 々ー 8 ← 4 でも良いです * / / * 真中の式は = 100 十 fo r for (i ー printf("%d 補足解説 コラム 1 るのかというと , 関数のプロトタイプ宣言により型チェックが厳しく 前回の解説で説明不足の点をここで説明しておきます。 なったために導入された , というわけです。 次のようなプロトタイプ宣言があったとします。 一補足ー 1 ポインタの配列 void *func(void * ) ポインタの配列というものも存在します。その宣言の例としては , この場合 , 関数 func の引数および関数の型は , どのような型へのポ 次のようになります。 インタであってもよいということを示しています。 int * pC4] ; 注意点としては , ポインタで参照するには必ず別の型へキャストし この配列の要素はポインタです。そのポインタの値がそれぞれメモ なくてはならないことです。 リを指すように設定された後のメモリイメージは , Fig. C ー 1 のようにな ■補足ー 4 関数へのポインタ ります。つまり p[l] がどこかのアドレスをポイントしていることにな 関数名はその関数が置かれているアドレスを指すポインタ定数であ ります。そのアドレスの値は , * P [ 1 ] として参照できます。 ると考えられます。そこで ( ) 演算子により , 関数名 ( ) とすることによ ■補足ー 2 ポインタのポインタ って関数がコールされます。 ちょっと込み入ったプログラムを見ていて そこで関数へのポインタを定義しておき , それを用いて関数を実行 できます。たとえば , といった表現を見たことはありませんか ? 問接演算子がついている のでポインタの一種だということはわかりますが , ふたつもついてい double (*func)( ) と関数へのポインタ func を宣言しておいて , るとよくわからなくなってきますね。宣言はたとえば , func=sin int * * p ; と sin 関数のアドレスを func に渡します ( sin はこれに先だって宣言され として行われます。意味するところは次のようになります。 る必要がある ) 。 * * p は i nt 型のデータを表現しています。すると * P はそのデータの 格納アドレスを指すポインタです。さらに p はそのポインタの値の格納 ( * func)(0.5) とすると , これは sin ( 0.5 ) を行ったことと同じになるのです。さらに 場所を指すポインタである , ということができます。イメージを Fig. C ー 2 に示します。ちょっと複雑ですね。文字列で使用例が出てきますか func=log と代入しなおせば , func という名前のままで今度は log 関数が呼び出せ らそれを参照してください。 ■補足ー 3 void * こうした作業は初級者の領域を大幅に逸脱するので , とく 本文中には出てきませんが void * 型というポインタがあります。 しかし , に詳しくは説明しません。興味のある方はご自分で調べてください。 これはすべての型へのポインタを表しています。なぜこんなものがあ Fig. C-2 Fig. C-I P[OI P[II P[2] P [ 31 メモリ * P 128 CMAGAZINE 1990 6

ハッシュ関数がぶつかることがあります。 に発生するようになるのて , 計算量は 0 ( 1 ) じようぶてしよう。しかし , 反対にデータ つまり , 異なるキーに対して同一の値を生 の件数と検索回数があまり違わない ( たとえ とみなせなくなります。ハッシュ関数はか 成してしまう可能性があります。今の例て ば n = 3000 , A = 1000 の場合には , 最初にま たよりがないランダムな値を発生させると とめてデータを登録しておき , あとは検索 は , key = 134 というデータがあったとする 仮定すると , だいたい使用率 90 パーセント と , key = 2034 のデータとぶつかってしまい するだけという使い方てなければ実用には 程度が目安となります。これ以上使用率が ます。このような場合の対処方法としては 高くなると , 登録 , 検索は 0 ( 1 ) とはみなせ ならないてしよう。 いくつかの方法があります。たとえば , 同 基本的には , バイナリサーチは , プログ なくなります。 ーのハッシュ値をもっデータをポインタて、 ラムの実行中に頻繁にデータ登録を行いな このように ハッシュ法は , 正しくハッ つないておくというのも一例てす。 がら , 同時に検索も行うという使い方には シュ関数を選択すれば , 登録 , 検索ともに ハッシュ法については , いずれ独立した 向かないアルゴリズムだということがてき O ( 1 ) て、行えるたいへん優れたアルゴリズム 話題として取り上げる予定なのて , ここて てす。しかし , データの個数よりも 10 パー るてしよう。 は計算量を求めるだけにとどめ , 詳細につ セント程度大きい配列を確保しておく必要 いては説明しません。 があり , これも一種の空間と時間のトレー ヘッジ , ハッシュ関数は基本操作のみて、実現てき ドオフてある , といえるてしよう。 るのて , 計算量は 0 ( 1 ) てす。したがって , ハッシュ値のぶつかりを考慮しなければ , データの検索を話題にするのにハッシュ ア丿ゴズムの比鮫 ハッシュ法による登録 , 検索にかかる計算 法に触れないわけにはいきません。ハッシ 量は 0 ( 1 ) ということになります。ハッシュ ュ法ては , キーのデータから配列のインデ 値がぶつかった場合の計算量の解析はかな アルゴリズムの善し悪しの例として , リ クスを得る関数 ( ハッシュ関数と呼びます ) り複雑になりますが , ハッシュ法の対象と ニアサーチ , バイナリサーチ , ハッシュ法 を使って高速に検索を行うことがてきます。 なる配列の大きさに比べて登録されている の 3 者を例にとって , 登録 , 検索の計算量を たとえば , 大きさ 100 の配列を使って整数の 調べてきました。計算量て評価すると , も データの個数が十分に小さいときには , ぶ キーをもっデータを扱うには , ハッシュ関 つかりが起きることはあまりないと考えら っとも優れているのはハッシュ法 , 次いて 数 h(key) を , れますから , ぶつかりによる影響は無視す バイナリサーチ , リニアサーチの順番にな h(key)=key % 100 ることがてきます。 ります。しかし , 計算量が万能のものさし と定めます。こうすれば , key を与えられた ハッシュ法の性能は , ハッシュ関 また , て、はありません。計算量以外の得失として とき , h ( key ) を計算するとそのデータが格納 数の質 ( どれだけランダムな値を発生て、きる 次のようなものがあります。 されている場所がわかります。 key = 2034 の か ) にも大きく左右されますにの見地から ・リニアサーチでは , データを登録した データは , 順番が保存されている ( データを配列の すると , 先ほどのハッシュ関数は優れてい h ( 2034 ) = 2035 % 100 = 34 先頭から順に取り出せばよい ) 。ほかの るとはいえません ) 。配列の大きさに対して なのて , tabIe[34] に格納されていること データの量が多くなると , ぶつかりが頻繁 アルゴリズムでは , 登録した順番は失 になります。 われてしまう。 TbI. 2 リニアサーチとバイナリサーチの計算量 ・ハッシュ法では , 登録するデータの個 数より大きいデータ領域を確保しなけ 登録 ( n 要素当たり ) ればならない。また , ハッシュ関数の 選択次第では , ハッシュ値のぶつかり が頻発して , 性能が大福に低下するお それがある。 このように , 実世界ては , アルゴリズム の選択には考慮すべきさまざまなファクタ ーがあります。 1 検索 ( 1 回当たり ) リニアサーチ O(n) O(n) 0 ( n2 ) バイナリサーチ 0 い og n) ※ただし , バイナリサーチでは , あらかじめテータをまとめて ( 未ソートのまま ) 登録してからソートすることによって , n 要素を O(n log n ) の計算量で登録することができる 84 CMAGAZINE 19 6

TbI. 1 関数 search の各ステートメントの実行回数 先ほど考察したように , 残念ながらアルゴ ーディングの技量に左右されてしまう , と リズムの実行性能はこれらのファクターに いう第 2 の間題があります。結論としては , 大きく左右されます。したがって , 「このア 従来のべンチマークテストのように , 実際 ルゴリズムの実行時間は , 入力の大きさ n の に動かして時間を測定する実験的な方法は , アルゴリズムの評価には使用て、きないこと 2 乗に比例する」といった程度の精度て、しか 表現て、きません。その比例定数は , 使用す になります。 るマシンやコンパイラの性能 , そしてプロ グラマの腕によって決まります。 実行時間が n の 2 乗に比例するアルゴリズ ムを , 「実行時間が O ( n2 ) のアルゴリズム」と 上記の理由から , アルゴリズムの性能を 呼びます。 O(n2) は , 「 n2 のオーダー」または 「オーダー n2 」と読みます。また , 一般に実行 表現するには , 実在のマシンを使わずに 計算量 (complexity) という抽象的な尺度が 時間が f ( n ) のアルゴリズムを「オーダー f ( n ) 用いられます。計算量は , 入力データの大 のアルゴリズム」と呼びます。 を行う単純なアルゴリズム ( リニアサーチ ) きさ n の関数として表現します。計算量とい ここて、 , n 個のデータが登録されているテ ープルから , ある特定のキーをもっデータ う概念は , ある仮想的なコンビュータを使 を使用しています。プログラムの内容はわ ってアルゴリズムを実行したときに , どれ をサーチする例を考えてみましよう。テー ざわざ説明するまて、もないて、しよう。 プルに登録されているデータの個数の増加 くらいの時間がかかるかを , 入力の大きさ 関数 search の先頭から見ていきましよ う。関数 sea 「 ch が呼び出されると , まず① にともない , サーチ時間がどのように増え n の関数としてごくごく大雑把に表したもの て、す。くわしくは参考文献 ( 1 ) ②を見てい るかが問題になるのて、 , テープルに含まれ が 1 回だけ実行されます。次に② ~ ⑤の wh ⅱ e こて、は簡単に説明す るエントリ数を入力の大きさ n とするのが自 ループが , ③の if 文の条件が成立するまて、繰 ただくこ り返し実行されます。より正確にいうと , ることにしましよう。 然てしよう。 テープルサーチを行うプログラムを List1 繰り返し実行されるのは , ② , ③ , ⑤の 3 つ 計算量を表す際には , ハードウェアやコ に示します。このプログラムて、は , 配列を の文て、す。そして , ③の if 文の条件が成り立 ンパイラの性能 , プログラミング技術に影 端から順番にスキャンしながらキーの比較 っと④が 1 回だけ実行されて関数 sea 「 ch から 響されない表現を用いなければなりません。 リターンします。また , データが見つから リニアサーチ (search. c) List 1 なかった場合には , ⑥が 1 回実行されて , リ ターンします。 こて、 , ② ~ ⑤の wh ⅱ e 文は何回実行され るのかを , 考えてみましよう。テープルに は , 全部て、 n 個のデータが登録されていま す。最良のケースは 1 回目のループて、目的の データが見つかる場合て、す。反対に , 最悪 のケースは , n 回ループを繰り返したあげ く , データが見つからずに⑥に抜ける場合 て、す。このように wh ⅱ e ループは , 最小 1 回 , 最大 n 回実行されます。 テープルにはランダムな順て、データが登 録されていて , サーチするキーもランダム に与えられると仮定すると , このループは 平均一回繰り返されることになります。し 実行回数 文 ① ※テータが見つかった場合には , ④が実行され , ⑥は実 行されない ※テータが見つからない場合には , ④は実行されす , ⑥ が実行される 1 n/2 n/2 1 n / 2 1 数 個 の タ る て れ さ 録 に 0 1 2 っ 0 4 5 6 7 8 9 0 1 2 っ 0 -4 5 6 7 8 9 ①②③④⑤⑥ 1 wh i 厄 ( i く n) { i f (tab 1 e [ i ]. key = key) return (table[i]. data) : / * 見つかった * / / * 見つからなかった * / ー 1 : return 80 CMAGAZINE 1990 6

さて , 各ステーテメントの計算量は次の り , それぞれのアルゴリズム ( およびプログ めてみましよう。①②は関数 binary_search ラムの書き方 ) て異なるのて単純には比較て ようになります。 が呼び出されると必ず 1 回だけ実行されるの 0 ( 1 ) ①②の計算量 て , 0 ( 1 ) てす。次に , ③ ~ ⑩の wh ⅱ e ループ きませんが , ループ実行回数の比 ( 500 : 10 ) 0(log n) ③ ~ ⑩の計算量 を考えるとバイナリサーチのほうがかなり に注目します。このループの中身の計算量 0 ( 1 ) の計算量 高速な検索が期待てきます。 ⑩ は , ④ ~ ⑩の計算量を合計したものになり したがって , バイナリサーチの計算量は , ます。④ ~ ⑩の各ステートメントては基本 0 ( 1 ) + 0 ( log n ) + 0 ( 1 ) ァーの登録 操作のみを行っているのて , 計算量はそれ =O(max(1' log n, 1 ) ぞれ O ( 1 ) てす。したがって , while ループの =O(log n) 中身全体の計算量は 0 ( 1 ) てす。 これまて , リニアサーチとバイナリサー となります。 wh ⅱ e ループは何回実行されるてしようか ? チについて , 特定のキーをもつデータを検 リニアサーチの計算量が O ( n ) てあるのに バイナリサーチては , 1 回ループを繰り返す 索するための計算量を評価しました。そし 対し , バイナリサーチの計算量は O ( 10g n) たびに , 着目する範囲が半分になります。 て , バイナリサーチのほうが優れているこ に収まっています。 0 ( n ) と O ( 1 。 g n ) の違い て、すから , このループが実行される回数は , とがわかりました。しかし , データを検索 は実用上かなり大きなものてす。 たかだか 10g2n 回程度になります。したがっ するためには , あらかじめデータを登録し たとえば , 要素 1000 個が登録されている て while ループの計算量は , ておかなければなりません。そこて , 今度 配列からデータを探すケースを想定してみ ループの中身の計算量 x 実行回数 ましよう。リ = アサーチては平均晋回 , つ はデータの登録にどのくらいの計算量が必 =O(1)XO(log n) 要かを考察しましよう。 まり 500 回ループを実行します。それに対し =O(log n) リニアサーチて、は , データの登録は配列 て , バイナリサーチては平均 10g2n 回 ( つまり となります。⑩はキーが見つからなかった の最後尾の要素にセットするだけてすみま 10 回程度 ) しかループを実行しません。ルー 場合に限り , 1 回だけ実行されるのて , O ( 1 ) す。配列の最後尾は , 変数 n ておさえていま プ 1 回当たりの実行時間は , 定数係数にあた てす。 すから , データの登録は次のようになりま す。 add(int key, int data) ー第■。第 バイナリサーチ (b-search. c) List 2 1 : struct { 2 : int key; 3 : int data : 4 : } tab 厄 [ 100 ] : 5 : / * tab le に登録されているデータの個数 * / 6 : int 7 : 8 : int binary-search ( int key) int 10W , high, middle; 10W high = n while ( 10W ← high) { m i ddl e = 0 ow + h i (h) / 2 : if (key ー = table[middle]. key) return (table [middle]. data) : else if (key く table[middle]. key) high = middle else / * key > tabIeCmiddIe]. key である * / 22 : low = m i dd I e + 1 : 24 : return ← 1 ) : / * 見つからなかった * / 25 : } if (n 〉 = 100 ) er 「 0 「 ( " 要素数が多すぎる " ) : table[n]. key=key : table[n]. data=data : n 十十 ; ①②③④⑤⑥⑦⑧⑨⑩⑩ この計算量が O ( 1 ) なのは明らかてす。 次に , バイナリサーチのデータ登録を考 えましよう。バイナリサーチては , 「つねに キーの昇順にデータが整列している」という 原則を守らなければなりません。したがっ て , データを登録するとき全体の並びが昇 順に保たれるように , 正しい位置を選んて データを挿入する必要があります。データ 登録の手順は次のようになります。 add binary(int key, int data) 82 CMAGAZINE 19 6

の解放は , f 「 ee ( ) 関数を使用しなくても , プ れていく。 malloc() 関数と ログラムを終了したときに自動的に解放さ また , p 「 intf ( ) 関数を使用して格納された free( ) 関数の使用仞 れるが , サンプルてはていねいに領域の解 領域から読み込みを行っている。ここて、 buffe 「 変数を使用している。 buffe 「変数は , 先ほど 放を行っている。 も説明したように確保した領域の先頭アド m 訓。 c ( ) 関数は , 指定された値をヒープ領 レスを格納している。その先頭アドレスか 域にユーザ領域として割り当てる関数て、あ ら p 「 intf ( ) 関数が読み込んて、いる。ただ , 文 る。 f 「 ee ( ) 関数は , m 訓。 c ( ) 関数によって割 字列が格納されたときは , その先頭アドレ り当てられた領域を解放する関数て、ある。 スタックにどれだけ利用可能サイズがあ スがズレながら格納されていくわけて、はな 実際にサンプルのプログラム ( List1 ) を見 るのか , stackavail( ) 関数を使って調べるこ い obuffer には , つねに m 訓 oc ( ) 関数によっ てみよう。このプログラムは , TurboC と MS とがて、きる。そして , スタック領域を指定 て割り当てられた領域の先頭アドレスが格 ー C て、コンパイルすることがて、きる。たた サイズだけ確保する関数は訓。 ca ( ) 関数を使 納されている。 し , ヘッダファイルがそれぞれ異なってい 用する。ただ , この関数は MS ー C Ver. 5.1 格納した文字列の読み込みが終了すると , るものがあるのて、注意がいる。つまり , Turb0C だけにしかサポートされていないのて , MS 割り当てられた領域を解放するために f 「 ee ( ) ては , alloc. h を使用し , MS-C て、は mal -C Ver. 5.1 以外て、はコンパイルて、きない 関数を実行している。 f 「 ee ( ) 関数には , 領域 10C. h を使用しているのて、ある。そのための プログラム (List2) を見てみよう。メイン の先頭アドレスが格納されている buffe 「を指 ヘッダファイルの選択を # if と # se を使用 関数には void 修飾子がついていて , メイン 定しなければいけない。指定されたた領域 し , コンパイル時に自動的に切り換えてい スタックサイズを調べるサンプルプログラム ただし , プログラムが ANSI に準拠してい るなら , く stdlib. h > のヘッダファイルを選 択すればよいのて、 , そのときは , #if と #else の部分を削除する。 次に , メイン関数て、は返り値がないのて、 void 修飾子をつけ , 引数もないのて、 void を 置いている。 buffer は cha 「型のポインタ変数 て、ある。この変数には , m 訓。 c ( ) 関数によっ て割り当てられた領域の先頭アドレスが格 納される。割り当ては , 10 バイトを指定し ている。もし , m 訓。 c ( ) 関数の実行て、失敗し たなら , 工ラーとして NULL が返されるの て、 if 文ては , NULL に等しいかどうかのチェ ックを行っている。工ラーの場合には , 工 ラーメッセージを出力してプログラムを終 「させている。 次にユーザがスクリーンから文字列を入 力するためのメッセージを p 「 intf ( ) 関数を使 って行っている。メッセージが出力される とカーソルは scanf ( ) 関数のために入力が行 われるまて、ウェイトすることになる。スク リーンから入力された文字列は , 格納先と して buffe 「変数を指定しているのて、入力され た文字列はそのまま確保した領域に格納さ List 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 13 : * / 14 : 15 : #include く stdio. h> 16 : #include く stdlib. h> 17 : #include く malloc. h> 19 : void main ( void ) Char *buffer; 22 : printf("stack avail = %d Yn" 23 : 24 : buffer = alloca( 100 ) : if( buffer = NULL ) 26 : printf("stack allocation failed. Yn") : exit ( ー 32 : 33 : 34 : A. Akitu 1990 ー 04 ー 01 MSC v5. 1 cl /AS /W3 sta. c Programmed by Dated Compi ler Version Purposed 最初にスタックサイズを調べ , スタック領域を指定サイズ だけ消耗させる。 もう一度同じ関数を使ってスタックサイズを調べる。 stackavai 1 ( ) ) : else printf("stack allocation successed. Yn") : printf("stack avail ニ %d Yn", stackavail ( ) ) : 92 CMAGAZINE 1990 6

ライプラリ編 [ 2 ] 今回は , ライプラリ編といいつつ , ヘッ ダファイルを取り上げます。なにしろ , 今 回が「プリプロセッサ特集」という様相を呈 していますのて、 , どこかてヘッダファイル について触れないわけにはいきません。ま た , ライプラリとヘッダが密接な関係にあ るのはご承知のとおりて、す。 標準ヘッダ ANSI 規格て、は , 以下に示す 15 個のファイ ルが標準ヘッダとして規定されています。 く assert. h> プログラム診断用関数 asse 「 t ( ) を定義する ヘッダて、す。この関数は , マクロ定義によ って実現されており , 直前に非デバッグ指 定用マクロ NDEBUG が定義されていると , void 式となります。 く ctype. h > 文字種別判定用ビットマスク , および判 定用マクロ関数を定義するヘッダて、す。 く errno. h> プログラム実行時におけるエラー情報に 関するマクロを定義します。 く float. h > 浮動小数点型の範囲 ( 数量的限界 ) がマク ロ定義されています。浮動小数点型の特性 は , 処理系および実行環境に依存しますが , 通常 , 旧 EE の浮動小数点演算規格に準拠し たものになります。つまり , MS-DOS の処 理系て、は , インテルの 8087 ( 287 , 387 ) のス ペックと同一になります。 く limits. h> 整数型の範囲 ( 上限値と下限値 ) , 特性 ( 処 理系に依存する ) がマクロ定義されていま す。 c h a 「 , s i n g e d c h a r , u n s i g n e d char, short, unsigned short, int, unsigned int, long, unsigned long の各タイプにつ いての定義が行われていますが , 将来的に は , マルチバイトキャラクタについての定 義が追加されるて、しよう。 く loca . h > プログラムが使用される地域別 ( 国別 ) に 異なるて、あろう処理を行うためのマクロが 定義されています ( 具体的には , 通貨の単位 / 表示形式 , 日付や時刻の表現形式などて、 す ) 。 ANSI 規格て、は , 処理系 ( 地域 ) ごとに 必要な情報を LC て、始まるマクロ名として , このヘッダに追加することが許可されてい ます。混乱を避けるため , ューザプログラ ム内て、は LC て、始まるマクロ名を使用しない よう心がけたほうがよいて、しよう。 く math . h > 数学関数 ( 平方根 , 対数 , 三角関数など ) のプロトタイプが行われています。 く setjmp. h> 非局所的な分岐 ( C の制御構造以外の分 岐 ) を行うための関数 , s mp ( ),longjmp( ) などが定義されています。 く signal.h> シグナル操作 / 処理 ( signal( ) , raise( ) ) に 関するマクロが定義されています。このヘ ッダて、は , S , SIG て、始まるマクロ名が予 約されています。通常 , シグナル処理は , 処理系 , そしてオペレーティングシステム に依存しますのて、 , S 給マクロが追加される 可能性があります。ューザプログラム内て、 は S 旧て、始まるマクロ名を使用しないほうが よいて、しよう。 く stdarg. h> 不特定数個の因数を処理する関数のため のマクロ定義を行います。このヘッダて、定 義されている va list, va arg( ) , va end(), va sta 「 t ( ) などのマクロ定義 , マク TbI.2 <string. h> の予約された関数名 WCS—- 文字列操作用 メモリ操作用 ワイド文字列操作用 ロ関数は , 可変個の因数をもっ関数 (printf( ) など ) のポータビリティを高めるためのもの て、す。 く stddef. h> く stdio. h> 標準入出力のためのマクロ定義 , プロト タイプを行うへッダて、す。 く stdlib. h> 一般的な ( 汎用の ) 標準ライプラリ関数の プロトタイプ , および ?TYPEDEF を行います。 < stdio. h> と合わせてもっとも使用頻度の高 いへッダて、しよう。 く string. h> 文字列操作のための関数のプロトタイプ を行います。このヘッダて、は , Tbl. 2 の文字 列て、始まる関数名が予約されています。 TbI.2 に該当する関数名は , ューザプログ ラムまたは , ユーザのライプラリて、は使用 しないほうがよいて、しよう。 く time. h > 時間に関する処理を定義します。 ANSI 規 格の時間処理用関数は , グリニッジ標準時 を基準として処理されます。実際にユーザ が使用する地域時間 , 季節時間などに関し ては処理系に依存しています。 以上のヘッダファイルによって定義され ている ( 標準的な ) マクロ , および TYPEDEF を TbI. 3 にまとめます。 準標準ヘッダ 以下に示すヘッダは , ANSI 規格て、は定義 されていませんが , PragmaC において標 準とする ( または予約する ) ものて、す。 く conio. h> コンソール入出力 ( ストリームて、はない ) , I / O ポートへの入出力関数を宣言します。 く direct. h> ディレクトリ操作に関する関数を宣言し ます。 く dos. h > MS-DOS のファンクションコールに関連 する関数を宣言します。また 8086 のセグメ ンテーションと C のポインタとの変換用マク プロジェクト PragmaC 43

約て、は , 関数の引数をすべてスタック上に ブッシュして渡すのて、はなく , レジスタも 使用します。引数の順序は右から左て、はな く , 左から右へ行います。 long double 新しく long dou e が追加されています。 long dou e は , 80X87 の内部レジスタと同 じ 80bit ( 10 バイト ) の浮動小数点数て、す。 MS -C Ver. 5.1 ても浮動小数点数の内部演算に は , これが使われていましたが ( 代替数値演 算ライプラリを除く ) , Ver. 6.0 て、は新しい 型として直接使えるようになりました。仮 りに dou e を使用しても内部演算て、はこの long double が使われているのて、 , long dou e を使用しても dou e を使用したとき に比べ , 演算速度はほとんど変わらないて、 しよう。 long double のために , ランタイム ライプラリに sinl(long double 用 sin 関数 ) な どいくつかの関数が追加されています。 べースドボインタ C 言語て重要て、しかもよく使うものとして ポインタがあります。 MS ー C て、はインテルの 86 系の CPU のアーキテクチャ上の理由によ り , far ポインタと near ポインタを導入して います。 far ポインタは任意のアドレスをさ すことがて、きますが , 効率は悪くなってし まいます。 near ポインタはひとつのセグメ ント内しかさすことがて、きませんが , far;tk インタに比べて非常に効率がよくなります。 MS-C Ver. 6.0 ては , near;tk インタの効率 のよさと far'* インタの任意のアドレスをさ せるというふたつの特性をもった , べース ドボインタという新しいポインタを導入し ています。 /AC /AH /AL /AM /AS /AT /Au /Aw / B ロ , 2 , 3 ] /batc h /c /C /D /EP / Fa /Fb / Fc /Fe /Fm / Fo /FPa /FPc /link /HELP /H /Gt /G s /Gr /Gm /Gi /Ge /Gd /Gc /G 2 /G 1 /G 0 / Fx / Fs /FR /Fr /FPi 87 /FPi /FPc 87 コンバクメモリモテル ヒュージメモリモテル ラージメモリモテル ミディアムメモリモテル スモールメモリモデル タイニィモテル ( 、 COM ファイル ) SS!=DS DS を再ロードする SS!=DS DS を再ロードしない オプジェクトリストを生成する ( C のソースを含む ) バウンドタイプの実行プログラムを作成する アセンプラソースを生成する スタックサイズの指定をする プリプロセスの出力を標準出力に書く ( # ⅱ ne 命令を含まない ) プリプロセスの出力を標準出力に書く ( # ⅱ ne 命令を含む ) シンボルの定義をする プリプロセスファイルにコメントを残す コンノヾイルのみ実行する バッチモード ラージモデルコンバイラの指定をする ソースリストを生成する 拡張 PWB ソースプラウザ情報を生成する PWB ソースプラウサ情報を生成する 80X87 ライプラリ ( 80X87 インラインコード ) 工ミュレータライプラリ ( 80X87 インラインコード ) 80X87 ライプラリ 工ミュレータライプラリ 代替数値演算ライプラリ オプジェクトファイル名を指定する リンカマップを生成する オプジェクトリストを生成する 実行プログラムのファイル名を指定する char のテフォルトを unsigned にする インクルードファイルのティレクトリを指定する オプションの簡単な説明を表示する 外部シンホル名の有効文字数を指定する Windows 用コードを生成する スレショルドの値を指定する スタックチェックルーチンを使用しない 高速呼び出し規約を使用する 定数を CONST セグメントに配置する インクリメンタルコンバイルを実行する スタックチェックルーチンを使用する C 呼び出し規約を使用する Pascal 呼び出し規約を使用する 80286 命令セットを使用する 8 田 86 命令セットを使用する 8086 命令セットを使用する MASM のクロスリファレンスファイルを指定する / Lp /MA /MD /ML /MT /ND /NM /nologo /NT / 0 a / 0 c / 0 d / 0 e /Og / 0 i /On / 0 p / 0 s /Ot /Ow /Ox / 0 z /q c /Sp /Ss /St /Ta /Tc /u / W[O,I , 2 , 3 , 4.5 ] /Za /Zc /Zd /Ze /Zg /Zi / 刀 /Zp /Zr /Zs ロテクトモード用のリンクをする リアルモード用のリンクをする MASM オプションを指定する DLL を作成する 静的リンクを使用する マルチスレッドプログラムを作成する テータセグメント名を指定する コードセグメント名内のモジュール名を指定する ロゴメッセージを出さない コードセグメント名を指定する 変数などの工イリアスを使用していないことを仮定する プロックレベルでの共通式の最適化をする 最適化を抑制する レジスタ変数の最適化をする グローバルなコードの最適化をする 埋め込み関数を使用する ループ最適化をする 危険なループ最適化を抑制する 浮動小数点数の取り扱いを一致させる 関数の終了方法を共通にする コードサイズを小さくするように最適化する 実行速度を速くするように最適化する 関数間での工イリアスを仮定する 通常での最大限の最適化をする (/Ocegilt / Gs と同等 ) 最大限のループ最適化をする プリプロセスファイルを生成する クイックコンパイルを実行する ソースリストの 1 行文字数を指定する ソースリストの一頁行数を指定する ソースリストのサプタイトルを指定する ソースリストのタイトルを指定する アセンプラソースファイルを指定する C ソースファイルを指定する すべての定義ずみシンホルを未定義にする 未定義にする定義ずみシンホルを指定する ノヾージョン名を指定する 警告レベルを指定する 標準のインクルードファイルディレクトリを検索しない マイクロソフトの言語拡張を禁止する pasca 言された名前の大文字と小文字の区別をする SYMDEB のための情報を生成する マイクロソフトの言語拡張を可能にする 関数のプロトタイプ宣言を生成する コードピューのための情報を生成する テフォルトライプラリの情報を削除する 構造体などのテータのバックを指定する ヌルポインタのチェックをする 構文チェックのみを実行する リンカ プシンを指定する 26 CMAGAZINE 1990 6

マイクロソフト 0 「 m 面 on from (ompiler ma 「 5 MS-C QuickC これらの BIOS ライプラリを使う す。キーポード BIOS を使う関数は , この関数を使った汎用関数が と , ハードウェアに密着したプロ List2C す。このプログラムにはふ bios keybrd 関数てす。この関数 グラムになりますから , ほかの機 のプロトタイプは List1 てす。ひと たつの関数例があります。 種への移植性 ( 互換性 ) は低くなり ひとつ目は , getkey 関数てす。 つ目の引数 se Ⅳ ice の意味とそのと 0 ます。しかし , 高速て細かい操作 QuickC Ve 「 . 2.0 には B ℃ S ラ この関数は , 1 文字入力されるま きの関数の戻り値は , TbI. 1 のとお イプラリが付属していますが , 使 がてきるようになります。 て待っ関数てす。キャラクタコー りてす。 い方がよくわかりません。どうす QuickC< は , QC アドバイザに もともとキーポード BIOS は , ドを返しますから , getcha 「関数な れば OS ライプラリを使えるよう BIOS ライプラリを使ったサンプル INT18H の割り込みを使うものて どの 1 文字入力関数の代わりに使 になりますか ? プログラムを搭載していますが , す。このとき AH レジスタの値にセ うことがてきます。しかし ,getchar BIOS の機能は多岐に及んているの ットする値によって上のような動 関数などと異なり , シフト状態 0 ( , 新キー , キー C のプログラムで , キーポード て、 , それだけては実用的な使い方 作をさせることがてきます。実は , 入力待ち状態にせずにリアルタイ これらの機能は , AH レジスタにそ はてきないかもしれません。 などの状態 ) とキースキャンコード ムにキーの入力を知るにはどうす BIOS はハードウェアに密着した れぞれ 0 , 1 , 2 , 3 , 4 を指定したと ( キーポード上の絶対位置を表すコ ればよいですか ? 低水準なプログラムの集まりてす きと同じ動作をします。 ード ) をグローバル変数に返しま から , これらの BIOS ライプラリを 0 PC ー 9800 シリーズの方向キー 使うときには , ハードウェアや BIOS やファンクションキーを使ったア の資料が必須てす。 PC ー 9800 シリー プリケーションの書き方を教えて ズてあれば , 「 PC ー 9800 シリーズテ クニカルデータブック」 ( アスキー ) ください。 TbI. 1 引数 se Ⅳ ice の意味と関数の戻り値 を参考にするとよいてしよう。 記号定数 意味と関数の戻り値 A 今回は , 上記の 3 つの質問にま 今回は , これらの BIOS ライプラ キーバッフアのテータを読み出す とめてお答えいたします。 リの中から , 比較的機能が単純て , KEYBRDHEAD 、上位 8bit: スキャンコード下位 8bit: キャラクタコード かっ便利なキーポード BIOS につい マイクロソフトの日本語版言語 キーデータがあるか KEYBRD READYL 製品ては , QuickC Ver. 2.0 て初め て解説します。 、 0 : テータなし 0 以外 : テータあり 現在のシフトステータス て BIOS ライプラリが付属しまし C 言語てキー入力を知る関数に , KEYBRD SHIFTSTATU$+ 0X0 : シフトなし 0X1 :SHIFT キー 2 :CAPS 0X4 : KANA た。 BIOS ライプラリとは , その名 scanf 関数や getc 関数 , gets 関数な 0X8 :GRPH 0X10 : CTRL どがあります。これらの関数は , のとおりハードウェアの BIOS ルー キーボードインタフェイスの初期化 KEYBRD 」 NITIALIZE なし リダイレクトが可能なものて , MS チンを制御するものてす。 キー入力状態を Keyta e に返す KEYBRD SENSE BIOS は , ハードウェアを直接制 ー DOS 以外の処理系ても共通なも なし のてす。しかし , これらの関数て 御するごく低水準なプログラムの 集まりてす。 MS-DOS< も , この はカーソルキーやファンクション キーキーなどといった , BIOS をとおしてパソコンを制御し ています。 BIOS には , キーポード その機種に特有なキーが押された BIOS, CRT BIOS, グラフ かを知ることはてきません。また , BIOS, ディスク BIOS, マウス 必ず文字入力待ちになってしまい BIOS, プリンタ BIOS, RS-232C ます。 kbhit を併用しても , バッフ BIOS, GP-IB BIOS, サウンド アに入力された文字列がとどまっ BIOS などがあります。このうち てしまいますから , リアルタイム QuickCC は , ディスク BIOS, キー にキー人力を調べることがてきま ポード BIOS, プリンタ BIOS, RS せん。 ー 232C BIOS などを使うライプラリ このようなときに役立つのが , をサポートしています。 キーポード BIOS ライプラリ関数て、 148 CMAGAZINE 19 6 Q&A List 1 unsigned CDEC し bios-keybrd(unsigned service. uns igned char *keytable) : List 2 getkey. c 1 : #include く bios. h> 2 : #include く stdio. h> 3 : 4 : #define SHIPT 0X1 5 : #define CAPS 0X2 6 : #define KANA 0X4 7 : #define GRPH 0X8 8 : #define CTR し 0X10 9 : 10 : unsigned int shift, lastkey: 12 : 13 : * 一文字入力待ちルーチン 14 : * 戻り値 : キャラクタコード 15 : * shift シフト状態 * lastkey : キーポードスキャンコード 16 : 17 : 18 : int getkey(void) 19 : { 20 : int c; while (-bios-keybrd(-KEYBRD-READY. の ! = の / * キーが入力されたか * / 22 :

CIimbinc Up 0 Windows してす。しかし , 対応てきないバグもある のて、す。用心してください。 Actor には , Actor のオプジェクトを調 べることのて、きる , 低レベルのデバッガ (SYMDEB 風の ) がついてきます。シリア ルポートに端末装置をつなぐと , このデバ ッガを起動して , アプリケーションと Actor を低レベルて、観察て、きます。私はこ のデバッガを使ったことがない ( シリアル ポートにつなげるような別の端末装置がな かった ) のて、すが , この機能によって Actor を , Windows SDK のようにスタンドアロ ンて、使うことがて、きるて、しよう。 ッターを拳で叩く このふたつの開発系の強みは , これらが 提供している関数コールによって , 開発者 が Windows 環境にアクセスて、きる , とい う点にあります。 Windows SDK は C の複 数のメモリモデル用のライプラリと , アセ ンプリ言語のマクロ集を提供しています。 ただし , コールした Windows の部品はア プリケーションのコード空間には存在しな いのて、 , ライプラリ中の関数はすべて , far pascal のコール方式を用いています。実 際 , Windows の構成部品は , メモリのいた るところに置かれます。 Windows は絶え ず , コードとデータを移動したり廃棄した りして , 新たなメモリ領域を作り出してい ます。したがってライプラリは実は , Win d 。 ws の上位管理部分に制御を渡すスタブ ルーチン集て、す。そして Windows のこの 管理部分が最終的に , メモリ上の正しい番 地へと制御を渡すのてす。 そのために Windows SDK のヘッダフ ァイルは , 関数プロトタイプと typedef 文 を大量に使っています。アプリケーション のコード中に , けったいな変数宣言をたく さんばらまくことになります。初心者が Windows プログラミングにうんざりする 理由のひとつが , この点にあります。また , C のランタイムライプラリにてきることの CMAGAZINE 19 6 多くを , Windows に依存することになり 20 ます。 C の標準ライプラリ関数の一部は , Windows が必要とする far 型を扱えない し , また , 特定の条件に依存しているルー チンもあるからて、す。たとえば C のランタ イム関数は DS と SS が等しいことを前提 としていますが , Windows の下て、はそう て、はないのて、す。 よく使う C の関数て、 , Windows の下て、 はまったく使えないものもあります。その ひとつが printf て、す。 stdout への出力はす べて Windows が捕捉するのて、 , コード中 に printf を書いても無意味なのて、す。 「おいおい , 待てよ」 , という読者の声が聞 こえてきます。「変数を正しいデータ型にキ ャストして , それを C の通常の関数に渡す ことはて、きるんだろ」。 ところが残念ながら , これもだめて、す。 変数を Windows 独自のデータ型て、宣言し ても , それはほとんど far 変数て、す。それを nea 「にキャストすると , セグメントが無指 定になり , 同一アドレス ( = 同じ変数 ) て、あ ることが保証されないのて、す。 しかし , Windows のルーチンがいろい ろめんどうを見てくれるのて、 , こういった 点はあまり問題になりません。一部の C 関 数は使えなくなりますが , 意外と失うもの は少ないのて、す。 Windows のシステム制 御範囲は , けっこう OS なみに大きい , とい う点に目を向けるべきて、しよう ( ファイル I / O だけは DOS が担当する ) 。 Windows のライプラリは数百個の関数 を提供しています。これらの関数を種類分 けすることはて、きますが , 一部の関数は汎 用的なのて、 , 特定の種類にあてはめること がて、きません。もっとも高レベルに属する のが , W i n d 0 w M a n a g e 「 t e 「 f a c e , Graphics Device lnterface, そして SYS tem Services lnterface の関数て、す。これ らの大きなグループを , さらに小分類する ことがて、きます。 Window Manager lnter face のグループは約 18 個の小グループに 分類て、きます 0Graphics Device lnterface は 15 , System Services lnterface は 11 の 小グループに分けられます。本稿て、は , ラ イプラリの全体を扱うことはて、きませんが , このようなグループ分けについてお教えす ることには , 意味があります。つまり , 関 数はグループ分けして理解したほうが , そ うしない場合よりも Windows を早く学べ るからてす。 Windows の初心者は , 自分が 当面必要とする分野に集中しながら , 関数 を 1 グループすっ学んていけます。 Actor も , Windows のライプラリへの全 面的なアクセスを提供しています。ライプ ラリ全体が , Actor の内部にあるからてす。 Actor は Windows にアクセスするための クラスを提供していますが , プログラマが 直接に Windows の関数をコールすること もて、きるのて、す。ただしそれは , Windows SDK の場合ほど単純明快て、はありません。 Actor は C と同じように言語なのて、 , く基本的なデータ型もサポートしなければ なりません。そこて、 , int 整数 , long 整数 , 浮動小数点数 , などの演算を扱うクラスや , 文字列を実現するためのクラスなども備え ています 0Actor はまた , Smalltalk のユー ザにはおなじみの , C011ections, Sorted CoIIections, Dictionaries, Arrays, Sets, Bags といった , なんだかおもしろそうな クラスも提供しています。 「て、は , Actor て、も Windows SDK と同じ ように関数へのアクセスがて、きるのなら , 両者のどこが違うのだ ? 」 よい質問て、す。その違いは , Act 。 r のクラ スの多くは , ただシコシコと , プログラマ に代わって Windows のルーチンをコール しているだけなのて、すが , それらはまた , プログラマから仕事の一部を取り上げても "Hell, wo 日 d / " を表示するプログラム ( Act0 「 ) = new(TextWindow, ThePort, ni l, 1 : nyWindow ”Å SampIe Window ” , nil); 2 : show(nyWindow, 1 ) : 3 : printString(myWindow, ” He Ⅱ 0 第 world! ” ): List 1