明解 ノ +bIC 言語 入門講座 Fig. 5 共用体の例 Fig. 6 構造体と共用体 struct { int long union { int long b; b; union ild { int long double d; (b) 共用体 (a) 構造体 体のオプジェクトを正しく使うには , 男性 か女性かを正しく記憶して , プログラムて 判断する必要があります。 バージョンアップした gstudent 構造体は , List 8 のように定義されることになります。 構造体のメンバに共用体が入っています ( そ の共用体のメンバにもたまたま構造体が入 っています ) 。たとえば性別を格納するメ ンバ sex には , 男性ならば 0 を , 女性ならば 1 を格納することにしましよう。その値を目 印にすることによって , 共用体の値を正し くアクセスてきるようになります。 構造体と共用体のイメージの違いを Fig. 6 に示します。構造体は直列 , 共用体は並列 な接続といったところて、しようか。 学生データ構造体 List 1 struct gstudent{ char 皿 me [ 2 の ; 2 / * 氏名り 3 i nt / * 身長り height; 4 float weight; / * 体重り 5 10 れ g schols; / * 奨学金事 / 6 i nt / * 性別 sex ; union { 7 8 float weight; / * 体重 * / struct ( 9 int b; 11 int 響 : / 事 w 事 / 12 int h; } bwh; } pro; 14 構造体・共用体の歴史 K & R 第 1 版では , 構造体・共用体に対して可能な操作は ①演算子によりメンバをアクセスする 共用体は , 複数のデータ間でメモリを ② & 演算子によりポインタを生成する 共有するデータ構造である だけでした。構造体・共用体を代入したり , 引数として渡したりすることはできず , 将来で きるようになるであろうと予言されていましたが , AN 引では正式にこれらの操作が認めら れました。 【自由課題】いろいろな構造体・共 用体を自分て、作成し , たくさんのプロ 違う値を代入してしまうようなことも考え する解答を収録していますのて , お読みく グラムを作ってみよう。 られます。このように考えると , 通常の int 型を使うのは , 適切てはないようてす。 また , 今月号の「 CMAGA セミナールー 次回てはまず 6 月号て予告した「列挙型』 ム』は , 3 級程度の実力があれば理解てきる まとめ に 0 、て解します。 はずて、す。ぜひ読んてください List 8 の構造体ては , 性別の表現として , さて付録ディスクの BohYoh ディレクトリ 0 か 1 のみを使うのて、すが , 間違えて 3 などの に , 府中市の深田一郎さんからの質問に対 124 C MAGAZINE 1 1 12

List 2 前と身長を扱う場合を考えましよう。たと えば小学校て、の身体検査の集計はどうする て、しようか。名前だけの表 , 身長だけの表 といった具合に , 別々に表 ( 配列 ) を作成す るてしようか ? 違いますよね。通常は , 各生徒に 1 枚のくカード > を用意して , そ こに名前や身長などを記入します。たとえ ば 50 人のクラスて、あれば , そのくカード > が 50 枚集まります。 C 言語て、は , 構造体 (structure) を用いるこ とによって , このようなくカード > のデー タ構造を表すことがて、きます。名前は文字 列 , 身長は int 型 , さらに追加する体重は f10 at 型 , 奨学金は long 型て、す。これを「ひとま とめ」にしてひとつのデータ構造とします。 構造体の宣言は List 3 のように行います。 39 : / * 九州大学工学部化学機械工学科松山研究室 * / 40 : / 事修士課程 1 年生の身長を昇順に並びかえる * / 42 : int main(void) 43 : { 44 : int i; int height[] = { 178 , 175 , 173 , 165 , 179 } ; 、 45 : char name ロ [ 8 ] = {"Sato", ” Sa 皿” , " Ta 0 ” , ” Mike", i ” } : sort(height, name, MAX) : ー 48 : for (i = 0 ; i く MAX; i + + ) 49 : printf("X-8s X4d*n", naneCi], heightCi]) ; return( の ; 52 : } 学生の構造体の宣言 List 1 : struct gstudent { char Ⅱ明 e [ 20 ] : 2 : height; 3 : int float weight; 4 : 10 schols; 5 : 名長重学 氏身体奨 構造体は , 複数のデータを「ひとまとめ」 にしたデータ構造である ここて、 gstudent を構造体タグ , name, h eight などをメン /<(member) と呼びます。 この List 3 の宣言は , オプジェクト ( 変数 ) を 宣言しているのて、はありません。 fstructg student というのは , これこれこういう型な のだよ』という宣言て、す。つまり Fig. 2 のよ うなカードの『形式 ( 枠組みの形 ) 』を作っ ているだけて、す。 fintJ の部分が fstruct gstuden を持っオプジェクトの宣言をも同時に行う とします。 この宣言により , gstudent 構造体は , na ことがてきます。そのときは t 』に変わっただけて、す。 List 3 のような宣 struct gstudent { me, height, weight, sch01s の 4 個のメンノヾ 言を行うことにより , この宣言以降の箇所 / * 中略 * / から構成されることになります。ここ <na て、は , プログラム中どこからて、も rstruct g me が配列て、あることに注意しましよう。配 studentJ という名前の型が自由に使えるよ 列も , 構造体のメンバになれます。 のように宣言します。これて、 x と z のふたっ うになります。同じ型のオプジェクトを宣 さてカードの「形式』だけあっても , そ のオプジェクトを宣言することになります。 言したいときに , わざわざ構造体の型を再 またタグ名を省略することもてきます。 こに名前などのデータを格納することはて、 宀言する必要はなくなります。 きません。通常の int 型のオプジェクトの宣 たとえば 言・定義を struct { / * 中略 * / int X , 構造体タグ名は , その構造体の名前を struct gstudent 型のオプジ と行うように 表す は , ここて宣言している構造体の型を持っ ェクトの宣言・定義を行うには a と b のふたつのオプジェクトを宣言するこ 構造体の型だけてなく , その構造体の型 struct gstudent z , 118 C MAGAZINE 1 1 12 Fig. 2 List 3 の構造体 struct gstudent 名長重金 学 氏身体奨

明解 IC 言ロロ 入門講座 とになります。しかし , 構造体自体には名 前がついていないのて、 , プログラムの別の 箇所て同じ型の構造体の宣言を手短に行う ことはてきなくなります。 配列は「同じ型」のデータの集合を効率 よく表すデータ構造です。一方構造体は , 一般に「違う型』のものの集合を効率よく 表すデータ構造であるといえます ( もちろ ん , たまたま同じ型ということもあります ) 。 構造体と配列の類似点 ・要素のアクセス Fig. 3 を見てください。配列と構造体の例 を示しています。配列て、あれば , たとえば [ ] 演算子と添え字を指定 a[4] のように , することによって任意の要素を表します。 構造体ては , この例ては x. y のように . 演算子 ( 通称「ドット演算子」 ) とメンバ名を指定す ることによって , 任意の要素を表します。 たとえば Fig. 3 配列と構造体 配列 構造体 0 1 」っ 4 び 3 一 4 一 5 int aC6]; struct xyz { int X; long y; double z; 名前空間 同一のスコープ中であっても , 名前空間 (name space) が異なれば , 同じ綴りの識別子 ( 名 前 ) を使うことができます。名前空間は次のように分類されます。 ( 1 ) ラベル名 ②タグ名 ( 3 ) メンバ名 ④そのほかの識別子 ( 関数名 , オプジェクト名など ) たとえば次のプログラムは , x をタグ名 , メンバ名 , オプジェクト ( 変数 ) 名 , ラベル名と して使用しています。 #include く stdiO. h> c=3 十 x. y ; のように使うことがてきます。 a [ 2 ] のよう に配列中のひとつの要素に着目すると「た だの int 型のオプジェクト』てあるのと同様 に , x. y も「ただの int 型のオプジェクト』と なります。 int main (void) 重要 struct x { int X , 構造体オプジェクト stc のメンバ mem は . 演算子 ( ドット演算子 ) を用いて StC. mem の形式でアクセスできる こて , オプジェクト名とメンバ名の両 方に x という同じ名前をつけていることに注 意しましよう。どちらの x てあるかは文脈に よって判断てきますね ( コラム名前空間参 X. X printf ("%d*n", x. x) : return( の : このように , 異なる名前空間に属するものに対しては , 同じ名前をつけても衝突は起こり ません。 ・初期化 配列の初期化は int a[6] = { 1 , 12 , 0 , 53 , 125 , のように { } て囲んだ初期化子を指定する ことによって行います。構造体の初期化も 同様てす。たとえば Fig. 3 の xyz 構造体に 対しては struct xyz c = { 15 , 35 , 17.5 } ; のように初期化てきます。 明解 ANSI C 言語入門講座 119

・配列化する 集合体 『配列』を要素とする配列は , 2 元配列と して実現します。たとえば , fint 型の大きさ 本文で解説しているように , 複数のオプジェクトの集まりを扱うという性質上 , 配列と構 4 の配列』を要素とする大きさ 3 の配列は 造体には数多くの共通点があります。 C 言語では , これら配列と構造体を総称して集合体 int a [ 3 ] [ 4 ] ; (aggregate) と呼びます。 のように宣言します。構造体を要素とする 配列を作ることもて、きます。たとえば rxy b のメンノヾ x , y, z の値が対応する a のメンバ、 z 構造体』を要素とする大きさ 3 の配列は に代入されます。 struct xyz b [ 3 ] ; ・関数の戻り値 のように宣言します。 構造体が代入て、きることから , 関数が構 構造体と配列の相違点 造体を返すことがて、きます 0List 4 のプログ ・代入 ラムを見てください。 setxyz 関数は引数と して受け取った x, y, z の値をメンバとして x, y が配列て、あるとします。すて、に説明 持っ構造体を返す関数て、す。この関数を呼 したように び出している 24 行目は a=setxyz(10, 320 , 35.6 ) ; それて、は , 先ほどの問題に戻りましよう。 のように配列の代入を行うことはて、きませ となっていますのて、 , setxyz の返す構造体 名前 , 身長 , 体重 , 奨学金をひとまとめに ん。しかし , 同じ型を持っ構造体は , その が , そっくり a に代入されます。 したデータ構造を struct gstudent 型とし , 値の代入を行うことがて、きます。たとえば 構造体を返す関数は , setxyz 関数て、の te 身長順にソートを行うプログラムが List 5 て、 struct xyz a, b ; mp のように , 作業用のオプジェクトが必要 す。今回の swap 関数は , ポインタ x , y の指 す構造体の中身をそっくり入れ換える関数 となります。 となっています。したがって , 呼び出す側 も swap(&data [i], &data ロ ] ) ; となります。 プログラムとはまったく関係のない話て、 すが , みなさん身長が高いこと , 身長と体 重には相対的独立性があること , 奨学金が 高額て、あることがよくわかります ( 誉 ) 。 【問題 2 】 List 5 のプログラムを , 体重 の順にソートするように書き換えよ。 構造体とポインタ 8 月号て、ポインタの例題として示した hiro ko 関数を覚えていますか ? ひろ子さんは 理想が高く ( 男の子に 180Cm 以上の身長を要 求します ) , しかもその人の身長が 180Cm よ り低ければ無理やり身長を 180Cm にしてしま う超能力を持っていましたね。 【問題 1 】 gstudent 構造体の各メンバ に値をセットする関数 struct gstudent setgstudent ( (char *name, int height, float weight, long schols) を書け。 のように代入を行います。この代入により , 構造体を返す関数 List く stdio. h> 1 : #include 3 : struct xyz ( 4 : i nt long y; double z; 8 : ー x , y , z の値を持つ xyz 構造体を返す 10 : struct xyz setxyz(int x, long y, double z) 11 : { 12 : struct xyz temp; 14 : temp. x = x; 15 : temp. y = y; 16 : temp. z = z; return(temp) : 18 : } 19 : 20 : int main(void) 22 : struct xyz a; 23 : a = setxyz(10, 320 , 35.6 ) ; 24 : printf("a. x:Xd a. y:Xld a. z:Xf ” 25 : return( の ; 26 : 120 C MAGAZINE 1991 12

のように struct をつけることなく宣言などに 使えます。 さて typedef< もっとも重要なことは 重要 typedef 宣言は , 新たな型を作るのでは ない。型の「同義語』を作るのである ということてす。 List 6 のプログラムを一 > 演算子および t ypedef 宣言を使用して簡潔に記述し直した プログラムを List 7 に示します。 共用体 さて学生データを例にして構造体の学習 をしました。男女の性差別をするつもりは ありませんが , 一般に女性の口から体重を 聞き出すのは失礼にあたると思います。し たがって , 男性て、あれば float 型の体重を , 女性て、あれば int 型三つて、表現てきるスリー サイズを記憶させると都合のよいこともあ るてしよう。 C 言語ては , 共用体 (union) を使うことに より , 可変なメンバを扱うことがて、きます。 Fig. 5 に共用体の例を示します。ここて、 , u nion は共用体てあることを意味します。 ild はタグ名て、あり , 宣言の方法などは構造体 と同様てす。また . 演算子およびー > 演算子 によってメンバをアクセスすることがてき るのも構造体と同じて、す。 構造体との違いは , 各メンバのすべてが 同時に存在するのて、はなく , 同時にはひと つのメンバだけが「意味を持つ』というこ とてす。 構造体と同様に と代入することがてきますが , その後て a=x. d , のように値を取り出しても , おそらくは意 味のない値となるてしよう ( もちろん , 故意 にそのような値を取り出すことも考えられ ますが , 処理系間の可搬性などは極端に低 明解 ノ \WC 言語 入門講座 構造体とアライメント 機械や処理系によっては , データオプジェクトが「 2 バイト単位の偶数アドレスにしか配 置できない」 , 「 4 バイト単位のアドレスに配置するとアクセスが高速となる』などの条件が つきます。たとえば 8086CPU の場合は , 配置の制限を受けることはありませんが , 奇数アド レスを先頭として配置されたデータよりも , 偶数アドレスを先頭として配置されたもののほ うが高速にアクセスできます。たとえば , 0 ~ 1 番地に格納された整数は , 1 ~ 2 番地に格納さ れた整数よりも高速な処理が可能となります。 次の構造体を考えましよう。 struct { char ch int long c , / * 1 バイト * / / * 2 バイト * / / * 4 バイト * / Fig. A(a) のような配置では , たとえ構造体自体が偶数アドレスに配置されたとしても , メンバ ch が 1 バイトであるため , i および c は奇数アドレスに配置されます。しかし , Fig. A ( b ) のように ch の後ろに「詰めもの」を挿入することにより , すべてのメンバが偶数アドレ スに配置され , ( a ) よりも高速にアクセスできるようになります。ただし構造体の大きさは 1 バイト増えてしまいます。 8086 用の処理系であれば , コンバイルオプションなどによって ( a ) とするか ( b ) とするかを 選択できるものが多いようです。 このような配置の問題は , 構造体だけの間題ではないのですが , とくに構造体の場合は問 題となることが多いようです。このように , ある値の倍数のアドレスへの配置のことをアラ Fig. A 構造体とアライメント イメントと呼びます。 つまり , 共用体は「メンバ i , 1 , d を同時 に使うことはないから , いっしよの領域に といった目的のために ch (a) 使用するものぞす。 閉じこめてしまえ』 いものとなります ) 。 struct { float weight : union WS { 共用体は次のようになるてしよう。 よう。体重またはスリーサイズを格納する さて体重とスリーサイズの話に戻りまし ch int b , int W ・ int h ; } bwh ; このように , 構造体を共用体のメンバとす ることもてきます。たとえば ws 共用体のオ プジェクト x に対して x. weight=60.0 ; x. bwh. b=80 ; のように使うことがてきます。この ws 共用 明解 ANSI C 言語入門講座 123

凡整数型とは列挙 , char, short int, int, と i-XList 1 は構造体の変数を別な構造体の いう型表記と区別不能になってしまう。 の問題が生じた原因はいうまて、もなく元の longint からなる。このようすを示すのが F 型へとキャストしようとしているため , コ ig. 3 てある。なお , Fig. 3 て、は省略している 宣言子を構成する場合に冗長なカッコを付 ンパイルエラーになるはずて、ある ( もし工ラ 加してしまった点にある。宣言子から識別 が , 凡整数型のうち列挙を除いた各型はさ ーにならない処理系があれば , それは ANS 子を取り去って抽象宣言子を構成する場合 らにそれぞれ signed/unsigned に分かれてい I から拡張されている ) 。 には , 元の宣言子の冗長なカッコをあらかじ る。 char< は plain char は別扱いて、 plain/s もっとも , 単にこのように異なる型の構 め排除しておく必要がある。そうて、ないと igned/unsigned の 3 種類の char があるが , そ 造体の変数へ ( どうしても ) 代入したければ , 思わぬ型を表すことになってしまうのて、要 れ以外の int 族て、は signed はデフォルトてあ ポインタを通じたキャストといういささか 注意て、ある。 り , たとえば singed int と int はまったく同じ 危ない手段があるにはある。たとえば List 1 て、あると解釈される。 の zot 関数を List 2 のように修正すればよ キャストの適用限界 一般に , スカラー型以外の型にキャスト を適用することはて、きない。またスカラー このように , いったん & 演算子て、アドレス , こて、キャストの限界に関して確認して 型をキャストしてスカラー型以外の型へと を取り , それを目的とする型へのポインタ おこう。本稿の冒頭て℃のキャストは非常に 変換することもて、きない。すなわち , にキャストし , さらに間接参照演算子 * を 強力て、あると述べた。しかしながら万能て、 キャストできるのはスカラー型の内部 適用して望む変数へと代入するというのは にかぎられる はない というよりも , 明らかに無意味な 構造体の場合にかぎらず使うことがてきる。 キャストや結果が極めてマシン依存になる のて、ある。スカラー型以外の型の代表例は これは知る人ぞ知る , 裏技に近いコーディ 集成型 (aggrigate type) と関数型 (function だろうキャストなどは許されていない ングテクニックて、ある。しかし , この技は 一般に相互にキャスト可能な型のクラス type) て、ある。たとえば構造体 (struct) の値 無闇に使うと移植性が確実に低下する。ワ が存在する。それは俗にスカラー型と呼ば をキャストして配列 ( という値 ) にするとか , ードアライメントや , 構造体内部のパッド れるものて、あり , ポインタ型と算術型から あるいはポインタ ( て、ある値 ) に変換すると の問題などが微妙に絡むからて、ある。だが 構成される。算術型はまた凡整数型と浮動 か , その逆とかは許されない。構造体同士 それは移植上の問題なのて、 , ここて、はこれ 小数型から構成されている。 てすら , 規格上キャストは許されない 以上深入りはしない 構造体から構造体への誤ったキャスト Fig. 3 スカラー型の構成 List 列挙型 Char 0 8 +> れⅡ 0 ・ 1 ・ 1 1 0 一 1 り 3 4 - -0 6 7 8 9 0 1 0 な 00 4 - -0 6 凡整数型 short int int long int float double long double オプジェクトへのポインタ 算術型 浮動小数型 スカラー型 構造体のポインタへのキャストを使う List 1 : void zot(void) b = *(struct bar *)&f; 3 : ポインタ型 関数へのポインタ 114 C MAGAZINE 1991 12

djgcc 詳解講座 第 2 回 djgcc のライフラリ関数 安田英之株プロシード ' 91 年 10 月号特集で取り上げた GNLJ C コンバイラ dJgcc 解説第 2 回はライプラリ関数の紹介とともに , 最新のアップテート情報を お届けします。また , オリジナルマニュアル『 GNLJ CC の利用お よび移植法』は、「オプションスイッチ」部分後半を翻訳掲載します。 raddress(DTA) 領域に対応するものて、 , フ います。 ァイルの属性 , 時刻・日付 , サイズ , ファ dirent はディレクトリのエントリ ( ディレ クトリ内のファイル ) の名前とその文字数が イル名を格納します。 今月から djgcc のライプラリ関数の解説を 入った構造体て、す。 int findfirst(const char * pathname, 始めます。今回はまず libsrc / c / dos に入って DIR *opendir(char *name) ・ struct ffblk * ffblk, int attrib) ; いる DOS ライプラリて、す。 ファイル名が name のディレクトリを開 き , 成功したらそのディレクトリの DIR 構造 MS-DOS のシステムコールを使って , パ bdos. c ス名が pathname ( ワイルドカードが使えま 体へのポインタ , 失敗したら NULL を返し す ) て、 , 属性が attrib て、あるような最初のフ ます。 int bdos (int func, unsigned dx, ァイルを探し , 結果を * ffblk に格納しま struct dirent * readdir(DlR * dir) ・ unsigned (l) ・ ディレクトリを読み , 工ントリ名を diren す。マッチするファイルがあったら 0 , な ファンクション番号 func の MS-DOS のフ t 構造体へのポインタて、返します。ファイル ァンクションコールを発行します。 かったら一 1 を返します。 の最後に達したら NULL を返します。 発行の前に変数 dx , al の値がそれぞれ ed findnext. s long telldir(DIR *dir) ; x, al レジスタに転送されます。 int findnext (struct ffblk * ffblk) ; ディレクトリの現在の参照位置を返しま 発行後の eax レジスタの値が返り値となり findfirst( ) て、設定した条件のファイルを す。 ます。 さらに探して , * ffblk に格納します。返り void seekdir(DIR *dir, long IOC) ・ bdosptr. c ディレクトリの参照位置を 10C に移動しま 値は同様て、す。 す。 int bdosptr(int func, void * dx, int86x. s void rewinddir(DIR * dir) ・ unsigned (l) ・ 80386 の割り込みに関する関数を定義して ディレクトリの参照位置を先頭に移動し 変数 dx の型がポインタ型になっているこ ます。 います。 と以外 , bdos( ) と同じて、す。 共用体 REGS はレジスタ構造を定義してい int closedir(DIR *dir) ・ dir. C ディレクトリを閉じます。 ます。 リアルモードのコンパイラと違って , RE ディレクトリを操作する関数が定義され findfirs. s GS に含まれる構造体 x のメンバは 32 ビット , ています。 構造体 h のメンバは 8 ビットまたは 16 ビット 本当は findfirst. s という名前なのて、しょ DIR はディレクトリの読み書きの際にどこ となっていて , x. ax が { x. al, x. ah, x. upp まて、読んだかなどの情報を保存しておく構 う。関数名もそうなっています。 er ax } に相当することに注意してくださ 造体て、 , ファイル参照の際の FILE 型に似て 構造体 f 用 lk は , MS-DOS の disk transfe djgcc 詳解講座・ Hello GCC World 71 dJgcc 研究

ライフボート lnformation from Compiler Makers Q PC-9801 の MS-DOS には , GR APH. SYS, GRAPH. L 旧というグラ フィックドライバがありますが , これを LatticeC で使うには , どう すればいいでしようか。 A Lattice C て、は , pascal キーワ ードっきの関数ポインタ経由の呼 び出し方法が , 若干異なるところ があります。付録ディスク収録 LI STI を例に説明します。 ①グラフィックドライバの有無を 確認するために f 叩 en 関数を使 用しますのて、 , 、、 stdio. h クをイン クルードします。 ② int86x 関数を使うために , 、、 d 。 s. ドをインクルードします。 ③ graph. sys を呼び出すためのエン トリポイントを得るための拡張 ファンクションの割り込み番号 を定義します。 ④ int86x 関数の引数て、使用する共 用体 , 構造体を定義します。 ⑤拡張ファンクションが返してく る graph. sys のエントリポイント テープルを受け取るための構造 体を定義します。 graph. sys は , far コールのためのアドレスを 40 個返してきます。これらのルー チンは , pa al 形式て呼ばれま す。 pascal 形式ては , 引数が左か ら右の順にスタックに積まれ , 引数のためのスタックの開放を 呼ばれたルーチンの側て行いま す ( C て、は , 引数が右から左の順 にスタックに積まれ , 引数が使 用したスタックの開放は , 呼ん だルーチンの側て行います ) 。 のため , 関数ポインタは , pasc al キーワードっきて定義します。 そして , 全体をひとつの構造体 にしています。 ⑥ graph. sys を呼び出すときに渡す 引数は , データを収めた領域へ のポインタにな・ります。そのデ ータを扱いやすいように , 共用 体を使って , メンバ名を定義し ています。 ⑦ 2K バイト分のワーク領域を確保 するための定義て、す。 ⑧表示モードを設定するファンク ションを呼び出すときの引数の 構造体て、す。 ⑨表示プレーンを設定するファン クションを呼び出すときの引数 の構造体てす。 ⑩表示スイッチを設定するファン クションを呼び出すときの引数 の構造体てす。 ⑩線描画のファンクションを呼び 出すときの引数の構造体てす。 呼び出すファンクションごとに 引数の構造体は異なります。他 のファンクションは , これを参 考に , graph. sys のマニュアルを ご参照のうえ , 定義してください @graph.sys が返すコードを受け取 るための変数て、す。 ⑩ FP SEG 関数 , FP OFF 関数を 使用するための一時的な変数て す。 Lattice C ては , 引数に far ポ インタのキャストをつければ , 関数の引数として使用てきます が , 他の処理系ては , far;* イン タ変数てなければならないもの もあるのて , ソースコードを共 有化したい場合は , 一時変数を 使用するとよいてしよう。 ⑩グラフィックドライバの有無を 明確にするためのファイルポイ ンタ定義てす。 ⑩ TJRAPH $ 〃がオープンてき れば , グラフィックドライバが インストールされています。確 認て、きたら , flcose 関数て、閉じて おきます。オープンて、きなけれ ば , グラフィックドライバがな いのて , プログラムを中止しま す。ただし , 互換機上ては , の方法て、確認てきなかったのて , プロンプトを出して , ユーザに 確認しています。 ⑩ graph. sys から , 工ントリポイン トを受け取るためにレジスタの アドレスを設定して , 拡張ファ ンクションを呼び出します。 ⑩初期化ファンクションを呼び出 します。引数は , ⑤て定義した 領域の先頭アドレスてす。初期 化ルーチンては , この領域に特 に設定するものはありません。 このとき , LatticeC て、は , 関数 の前のキャスト , (int pascal (far * ) ( ) ) を必ずつけてください ⑩以下 , 各ファンクションの呼び 出し方法は同じてす。入力引数 がある場合には , ⑤て、定義した 領域のメンバに値を設定して呼 び出します。 LISTI は , スクリーンの左上か ら右下に太い線を描画します。 Lattice C / DOS のバッケージ に入っている , MAKE ユーティリテ Q mmod : 9 . *Iattic41*I n ニ new d : f : *testprog*object Lattice C ィ LMK を使って Fig. 1 のようにリ ンクすると , うまくリンクできま せん。どこが悪いのでしようか ? A LMK からコマンドが起動され るとき , LMK は COMMAND ℃ O M を経由して起動します。これは , DIR などの組み込みコマンドを起動 てきるようにするためて、す。しか し , COMMAND.COM は , 128 文 字しか受け付けませんから , MAK E ファイルのコマンドが , マクロを 展開された状態て 128 文字を越んる と , 受け付けられません。お送り いただいた MAKE ファイルは , $ (d),$ (n),$ (mmod) が展開される と , LMB のコマンドラインが , 20 0 文字になるのて , LMB への起動が 掛かりません。 LMB は , 応答ファイ ルをサポートしていますのて、 , Fi g. 2 のように書き換えてください LMK は , く @ くから , < が先頭 にある行まて、を , そのコマンドへ のリダイレクトとして , (ex. LM B く tmpfile のように ) 処理しま す。 また , 応答ファイルの先頭に 、、 $ ( mmod ) \ c 十〃を加えています が , 場合によっては , LMB がスタ ートアップルーチンてあるヾ $ ( mm (d) *c" を正しくリンクて、きない とがあるのて、 , 指定してください Fig. lo $(n). exe : $(d)*log. obj $(d)*cons$(n). obj $(d)*log a. 0 切 $ ( d ) 判 09 ー b. obj \ $ ) Ⅵ og c. 0 切 $(d)*log d. obj LMB¯$(d)*Iog 十 $(di*cons$(n) 十 $(d)*log a 十 $(d)*log b 十 $(d)*log-c \ 十 $ ( d ) Ⅵ d,log$(n). ,$(mmod)*lcm$(mmod)*lc¯; 2 LMB $(d)*log 十 $(d)*cons$(n) 十 $(d)*log a 十 $ ( d ) Ⅵ 09 b 十 $ ( d ) Ⅵ 09 c \ 十 $(d)*log d, log$(n)„$(mmod)*lcm $Gfimod)*lc : LMB く@く $(mmod)*c 十 $(d)*log 十 $(d)*cons$(n) 十 $(d)*log a 十 $(d)*log b 十 $ ( d ) Ⅵ 09 ー $(d)*log_d,log$(n)„$(mmod)*lcm $(mmod)*lc . lnformation from Compiler Makers 159

1991 年 12 月 1 日発行 ( 毎月 1 回 1 日発行 ) 第 3 巻第 12 号通巻 27 号 1990 年 2 月 2 日第 3 種郵便物認可 提携・ LANG 誌 / 監修・石田晴久 C 言語技術情報誌・ C マカシン 1991 DEC. Vol. 3 No. 12 980yen 0 特集 最新コンハイラオハビュー —・コンバイラトレンド Ⅱ・主要コンバイラガイダンス Ⅲ・性能評価 速報日本語版 Mic 「 osoft FORTRAN Ve 「 .5.1 / djgcc 詳解講座 He 0 GCC wo d ・ライプラリ関数 提携記事 >Making a Hash of Your Data >Managing Software Projects with PIMs アルゴリズムとテータ構造入門・ヒープソート / AN CI Mo 「 e ・キャスト / 明解 ANSI C 言語入門講座・構造体と共用体 寺月リイ寸録・ 5 " ティスク . ⑧・叭 N c 言語入門講座。活用集・ 1991 年 c MAGA 刀 NE 総目次・本誌掲載ソースプログラム

アルゴリズム・テータ構造入門 は , 根のふたつの子はそれぞれ 9 , 15 なの て、 , このうち小さいほうの 9 と根の 20 を入れ 換えて , Fig. 2 (b) になります。 この状態て、も , 要素 20 は子 12 , 13 よりも大 きいのて、要素 20 と 12 を交換すると Fig. 2 (c) になります。ここて、も , 要素 20 は一方の 子 17 よりも大きいのて、 , 要素 20 と 17 を入れ 換えて最終的に Fig. 2 ( d ) になります。 Fig. 2 ( d ) は , 再び半順序木の条件を満たしてい ます。このように , 親のほうが子よりも大 きいなら , 子の小さいほうと親を交換する という手順を繰り返せば , 半順序木の条件 を保っことがて、きます。この例て、は , 要素 20 は葉まて、沈んて、きましたが , もし途中の 段階て、 < 親の値は子の値より大きくない > という条件が満たされればそこて、処理を打 ち切ります。 操作 delete min て、は , 根から葉に向かっ て要素の交換が行われます。木の高さは 10g 2n くらいて、すから , 平均すると約 ( log2n ) / 2 回交換が行われることになります。したが って , 操作 delete min の計算量は 1 回当たり O ( 10g n) になります。 次に , 操作 insert について考察してみまし よう。まず , 最初に挿入する要素を最下段 のいちばん左寄りの空いている場所に置き ます。もし , 最下段のすべての位置がふさ がっていれば , 最下段のさらに下のいちば ん左端に置きます。この場合 , 木の高さが Fig. 4 ニ分木の節点と配列の対応 ひとつ増えることになります。 例として , Fig. 1 の半順序木に要素 7 を挿 入することを考えてみましよう。まず , 要 素 7 を最下段のいちばん左寄りの空いている 場所に置くと Fig. 3 (a) のようになります。 insert て、は , delete min とは反対に葉から上 に向かって要素を浮き上がらせていきます。 こて、 , 新規に挿入した要素 7 とその親の関 係を調べます。ここて、は , 親が 13 て、子が 7 な のて、く親の値は子の値より大きくない > と いう関係が満たされていません。そこて、 , 親と子 ( つまり 13 と 7 ) を入れ換えると , Fig. 3 (b) の状態になります。 また , Fig. 3 ( a ) て、 7 の兄弟に当たるのは 20 て、すが , この要素をいじる必要はありま せん。要素 20 はすて、に親て、ある 13 より小さ くなっていて 13 をさらに小さい 7 に置き換え ても親子の大小関係は変わらないからて、す。 操作 insert て、はもし親のほうが子よりも大 きいなら , 親と子を交換するという手順を 繰り返せばよいことになります。 Fig. 3 ( b ) て、要素 7 とその親 9 との関係を調 べるとく親のほうが子よりも大きくない > の条件を満たしていません。したがって , 要素 7 と 9 を入れ換えて Fig. 3 (c) になりま す 0Fig. 3 ( c ) て、は , 要素 7 のほうが親て、ある 5 よりも大きいのて、 , これ以上交換を行う必 要はありません。この状態て、再び半順序木 の条件を満たすようになりました。 3 2 4 9 8 1 5 6 13 7 14 15 操作 insert は , 葉から根に向かって交換処 理を行います。木の高さは Iog2n 程度に保た れているのて、 , 平均して親子の入れ換えは ( 1 。 g2n ) / 2 回くらいになります。親子の大小 を比較して必要なら交換するという処理は 一定時間 O ( 1) て、て、きるのて、 , 操作 insert の計 算量は O (log n) になります。このように 半順序木て、は基本的なふたつの操作 delete min とⅲ sert をそれぞれ 1 回当たり O ( logn ) て、実行することがて、きます。 半順序木をプログラムて、実現するには , どうすればよいて、しようか ? まず考えら れるのは , ポインタによって節を結び付け たオーソドックスな木構造表現を使うこと て、す。普通の木構造て、は , 親から子へのポ インタを持たせます。半順序木て、は , 要素 を挿入するときに葉から根に向かって木を たどる必要があります。したがって , 子か ら親へのポインタも必要となり , ポインタ を使って半順序木を表現するのは困難て、す。 半順序木を効率よく実現するデータ構造 としてヒープ ( heap ) があります。話は少し はずれますが , データ構造やアルゴリズム の世界て、は , ヒープという用語はふたつの まったく別の意味を持つのて、注意してくだ さい。ひとつは , これから紹介する半順序 木を実現するためのデータ構造て、す。もう ひとつは , メモリ管理関連の用語て、任意の タイミングに割り当て・解放て、きるメモリ のことをヒープと呼びます。標準ライプラ リ関数の malloc と free て、扱うメモリプロック はヒープ領域に割り当てられます。プログ ラムを書く人にとっては , こちらのヒープ のほうが馴染み深いかもしれません。 ヒープとは , 配列を使って半順序木を表 現したものて、す。二分木の構造を配列の添 え字に巧妙にマッヒ。ングすることによって 対応する親と子を見つけることがて、きるよ うになっています。ゆえに操作 insert, del アルゴリズムとデータ構造入門 81