とを示す末尾ポインタの代わりに リスト の最後のポインタに NULL が用いられるこ とがよくあります (Fig. 2 参照 ) 。 木構造リスト 連結リスト以外の代表的なリスト構造に は , 木構造リスト (tree-structured list) が あります。木構造リストとは , ひとつのセ ルが , ふたつ以上のセルを指すような連結 リストのことてす。木構造には , いろいろ なものが考えられていますが , よく用いら れるのは , ひとつのセルが , ふたつのセル を指す木構造てす。これは , 二分木または 二進木と呼ばれています。ひとつの dou e 型のデータ構造をもつ二分木は , 以下のよ Fig. 3 木構造リストに分木 ) 「 00t NULL NULL NULL NULL 114 CMAGAZINE 19 8 うに宣言てきます。 struct tree { double data ; struct tree * car ; / * left struct tree * cdr ; / * right pointer pointe 「 こて , ca 「 ( カー ) は , 木 ( tree ) の左ポイ を用いて , 二分木を表すことがてきるわけ てもけっこうてす。とにかく , この構造体 わかりにくい場合は , ほかのメンバ名にし LISP という言語に由来しているのてすが , す。 ca 「や cd 「というメンバ名のつけ方は , ンタてあり , cd 「 ( クダー ) は右ポインタて、 てす (Fig. 3 参照 ) 。 NULL NULL データ リスト構造を用いた動的領域確保 それて、は , 実際にリスト構造を用いて動 的に領域を確保してみましよう。これから 紹介するのは , 構造体宣言と関数のプロト タイプ宣言をする共通のヘッダファイル ( List 5 ) , リスト構造を用いて入力を行う関数 input (List 6 ) , リスト構造のデータを出力する関 数 output(List 7 ) , そのふたつの関数の動作 を確認する main 関数 (List 8 ) て、す。 ヘッダファイル list. h まずヘッダファイル list. h ( List 5 ) の説明 から始めましよう。 4 行目から 7 行目にかけ て , リスト構造を用いるための自己参照的 構造体を宣言しています。ここて、は , 構造 NULL NULL NULL NULL

投資が必要て、す。ノードディスクつきの 286 List 3 35 : / * WndClass. hlnstance WndClass. hCursor 14 : 15 : 16 : 17 : 19 : 20 : 22 : 23 : 24 : 25 : 26 : 28 : 29 : 30 : 31 : 32 : 33 : 34 : 36 : 37 : 38 : ・ 39 : 40 : 41 : 42 : 43 : 44 : 45 : 46 : 47 : 48 : 49 : 50 : 51 : 52 : 53 : 54 : 55 : 56 : 58 : 59 : 60 : 61 : 62 : 63 : 64 : 66 : 68 : 69 : 70 : 73 : 74 : 75 : 76 : 77 : 79 : 80 : 81 : 82 : 83 : 84 : 85 : 86 : 88 : 89 : * ウインドウ・クラスの関数 ~ もつばらシステム・メニューからの * 破壊メッセージ (destroy message) を待つ long FAR PASCAL WndProc( hWnd, msg, hWnd; HWND unsigned msg; Param, 1 Param ) WORD LONG wParam ; 1 Param ; swi tch( msg ) case WM_DESTROY : PostQuitMessage( 0 ) ; break; default: return ( De fW i ndowpr OC ( hWnd, msg , * WinMain 関数ーー Windows アプリケ return( NULL ) ; wParam, 1 Param ーションの入口が Wi ain ( ) int PASCAL WinMain( hlnstance, hPrev, lpCmdLine, nCmdShow ) HANDLE hlnstance, hPrev; LPSTR 1 pCmdL i ne ; int nCmd Show ; HWN D hWnd ; MSG msg; / * プログラムは一度に 1 コピーしか走らせない * / if( hPrev ) return( NULL ) ; / * ウインドウ・クラスを登録する * / WndClass. WndClass. hlcon WndClass. lpfnWndProc style = NULL; = WndProc; hlnstance; = LoadCursor( NULL, IDC_ARROW ) ; = LoadIcon( NULL, IDI—APPLICATION WndClass. hbrBackground = GetStockObject( WHITE_BRUSH ) ; = (LPSTR) NULL; WndClass. lpszMenuName WndClass. lpszClassName = (LPSTR) ” SampIe" ・ WS_OVERLAPPEDWINDOW, CW_USEDEPAULT, SampI e W i ndows Program , hWnd = CreateWindow( ” Sample ” , / * アプリケーションのウインドウを作る * / return( NULL ) : if( !RegisterCIass( &WndClass ) ) CW_USEDEFAUW, CW_USEDEFAULT, CW_USEDEFAULT, NULL, NULL, hlnstance, NULL ) : て、す。 PM には OS / 2 の機能を活用てきるよ うに , 多くの機能が盛り込まれています。 しかしプログラムの構造はよく似ているの て、 , Windows のプログラムを PM 用に変換 するのは , Mac のプログラムを PM に移植す るより楽て、はないか , という気がします。 List 4 は , PM のプログラムの骨格て、す。 List 3 の Windows 用プログラムと比較して みてください 0 開発環境 フロッヒ。ー 2 台のメインメモリ 256K バイト のマシンが , 本格的な開発環境て、あった時 代は遠く去りました。今日の GUI は , より強 力なマシンと多くの資源を要求します。 Mac はそれ自体が相当に高価て、す。これ にハードディスク , IM バイトの RAM, そ して C または PascaI のコンパイラを加えま す。「 lnside Macintosh 」 ( 参考文献 1 ) を全巻 そろえることも , 絶対的に必要て、す。 Amiga て、は 512K バイトのメインメモリと フロッビー 2 台て , いちおうの開発はて、きま すが , ほとんどの開発者が , ハードディス ク , 数 M バイトの RAM, そして C コンパイ ラという環境を使います ( Amiga はマルチタ スクのオペレーティングシステムなのて、 , メモリが多いと RAM ドライプへの利用や , ほかのアプリケーションを同時に実行て、き るなどの点て、有利て、す ) 。 Amiga のリファレ ンスマニュアルも , 別途に購入て、きます。 MS Windows て、開発をするには , 相当の if( !hWnd ) return( NULL ) : / * ウインドウを表示する * / ShowWindow( hWnd, nCmdShow ) : UpdateWindow( hWnd ) : / * メッセージの処理へり whi le( GetMessage( &msg, NULL, Trans IateMessage( &msg ) ; DispatchMessage( &msg ) ; return( msg. wParam ) : NU LL, NULL または 386 マシン , マウス , 良質なグラフィ クカード ,MS-C( または PascaI), そして MS Windows SDK て、す。 OS/2 PM はコストの点て、は最悪てす。 OS/ 2 を走らせることのてきる 286 または 386 マシ ン , EGA または VGA グラフィックカード , マウス , 2M バイト以上の RAM ( 多いほどよ い ) , OS / 2 のカーネル , OS / 2 用 C コンパイ ラ , そして OS/2 Programmer's TooIkit が 必要てす。 GUI の基礎の基礎 29

Amiga 旧 tuition のプログラム例 Li st 2 上 , 幅 , 高さ * / struct Window 13 : #define TRUE 1 12 : #define FALSE 0 #include く proto/intuition. h> #include く intuition/intuition.h 〉 #include く exec/types. h 〉 * ューザがそれを指定するのを待つ . * このプログラムは 1 項目だけのメニューを作り , * Amiga lntuition のプログラム例 2 : 4 : 5 : 7 : 8 : 9 : 10 : 11 : 14 : 15 : 19 : 20 : 22 : 23 : 24 : 25 : 26 : 28 : 29 : 30 : 31 : 32 : 33 : 34 : 35 : 36 : 37 : 38 : 39 : 40 : 42 : 43 : 44 : 45 : 46 : 47 : 48 : 49 : 50 : 51 : 53 : 54 : 55 : 56 : 57 : 58 : 59 : 60 : 61 : 62 : 63 : 64 : 65 : 66 : 68 : 69 : 72 : 73 : 74 : 75 : 76 : 77 : NULL, / * 次のメニュー * / struct MenuItem FirstMenuItem 27 : / * メニュー項目 * / NULL (UBYTE * ) ” Quit ” NULL, 1 , 0 , JAMI, 0 , 0 , struct IntuiText FirstItemText 17 : / * メニュー項目の言葉 * / struct IntuitionBase *IntuitionBase; (APTR) &FirstItemText, / * 項目の言葉 * / 0 , ITEMTEXT + ITEMENABLED + HIGHCOMP, / * フラグ 0 , 0 , 72 , 8 , / * 左 , 上 , 幅 , 高さ * / &FirstMenuItem (UBYTE * ) ” Project , MENUENABLED, 0 , 0 , 72 , 10 , / * 左 , NULL, / * 次のメニュー * / struct Menu MenuDefn 41 : / * メニューの定義 * / 0 NULL, 0 , struct NewWindow WindowDefn 52 : / * これが今回のウインドウの定義 * / NULL, / * ガジェット・リスト中の最初のガジェット * / WINDOWCLOSE + WINDOWDRAG + WINDOWDEPTH + SMART_REFRESH + ACTIVATE, CLOSEWINDOW + MENUPICK, 640 , 2 圓 , / * ウインドウの幅と高さ * / 0 , 0 , な画面の TopLeft に対するウインドウの原点 XY 座標 * / (UBYTE * ) ” Window ” , / * ウインドウのタイトル * / NULL, / * カスタムの CHECKMARK 像 * / WBENCHSCREEN / * デスティネーションのスクリーン・タイプ * / 640 , 200 , / * 最大の幅と高さ * / 640 , 200 , / * 最小の幅と高さ * / NULL, / * カスタムのビットマップ * / NULL, / * カスタムのスクリーン・ポインタ * / * プログラム主部 int main() *window, MIT の X Window System を Amiga に移植 することがて、きたほどてす ) 。 List 2 は , 単純なメニューを表示する Amiga のプログラムの例て、す。同等の Mac や Windows のプログラムより相当長くなっ ていますが , それはリソースをサポートし ていないせいて、もあります。何もかも , プ ログラムのソースの中て、定義しなくてはな らないのて、す。もうひとつの理由は ,lntuition がかなり低レベルの機能をサポートしてい ることて、す。 GUI の基本はすべてここにあり ますが , プログラマは大量の細部的な事が らを指定し , ラジオボタン , リストボック スなどの高レベルのアイテムをすべて自作 しなければなりません。この方法には利点 もありますが ( たとえば柔軟性 ) , 複数のア プリケーション間て、の一貫性は乏しくなり ます。 M S Windows Mac や Amiga と違って , IBM PC には標 準的な GUI がありません。外部から購入しな ければなりません。それらの中て、は , MS Windows がもっとも広く採用され , そして 影響力をもっています。 MS Windows は ,DOS 上のアプリケーシ ョンとして走ります。普通の DOS アプリケ ーションも Windows 上て、走りますが , Win dows の機能を利用することはてきません ( 現 在走っている Windows プログラムは , DOS アプリケーションの実行中は保留になりま す ) 。 Windows の下て、仕事をするには , プロ グラムは MS Windows Software Devel- 叩 ment Kit(SDK) を使って開発しなければ なりません。いずれの Windows プログラム を使うにも , Windows システムが必要て、す ( 一部には Windows のコピーがバンドルされ ています ) 。 MS Windows の GUI は , Mac や Amiga の GUI より高度て、す。「よい」という意味てはな く , たんに機能やオプションの数が多いの GUI の基礎の基礎 てす。 Windows てのプログラミングは , 従 27

List 2 る場合には , つねにこのファイル形式が基 本となります。ファイルが決定すれば , 後 は単純作業てす。 1 画面は先に述べた txt と at 「 を単純に出力して作成します。何枚も静止 画面を作成するわけてすから , ファイル名 に番号を入れておけば , 順序がわかります ね。 CSET て、は , このファイル形式を VRM 形式という名前をつけ , 順序だった静止画 面ファイルに auto# # # #. VRM というよう , # # # # に 0000 ~ 9999 まて、の番号をつけた ファイルを作成しています。 ファイルを扱うプログラムを書いた方な らおわかりて、しようが , いちばん単純なフ アイル構造としました。この方法だと , 通 常のエデイタて、も編集て、きますし , ほかの ツールからいちばん楽にコンバートて、きる 方法だからて、す ( ここまて、の作成がてきれ ば , ほかの機種へのコンバートがて、きるて、 しよう ) 。サンプルプログラム (List 1 samplel. c) を用意しましたが , このファイ ルの形式をよく理解しないと , 差分作成ル ーチンがよくわからないと思いますのて、 , しつかりと頭に入れてください ESC の差分出力原理 て、は , 色部分を除いた場合の差分出力に ついて考えてみます。配列て考えてみまし char sl [20] = char s2 [ 20 ] = char sb [20] ・ 上記の sl と s2 の変更部分に注目すれば , 配列 sb に同じ部分に NULL, 変更部分に新 しい文字を入れるのは簡単にて、きますね (List 2 ) 。て、きあがった差分ファイルから , NULL て、ないところを書き出せば , 変史部分の ESC 出力がて、きます。ただ , 色の情報と日本語 2 バイト文字を考えると , もうひとくふう必 要てす ( 残念ながら , 現在の CSET ルーチン はまだ最適化が完全てはないのて , よい方 法がありましたらお教えください ) 。詳しく s2 [ 20 ] = " Char sb [ 20 ] : Char i nt i = 0 : while(sl[i]) if(sI[i]!=s2[i]) sb[i]=s2Ci]; e 1 se sb[i]=NU しし : -4 - -0 ^ 0 々ー 8 0 11 っ 0 っ・戸 0 cset 差分の心臓部 LiSt cset 差分の心臓部 ? ESC 差分のワークへの出力変更部分は , そのままテキストとアトリビュートを , さらに , 同じ部分に * / は , NULL を txt, att へ格納 ひとつ前の画面のテキスト * 引 d 5 : 現在の画面のテキスト *new 6 . 差分データのテキスト *sab 7 : ひとつ前の画面のアトリヒ・ユート 8 : 現在の画面のアトリヒ・ユート *nat 9 . 差分データのアトリヒ・ユート *sat 10 : / * len ワークエリアの最大長 ( 80 * 24 ) Sabun (char *old, char *new, char *sab, 11 : VO i d char *oat,char *nat, char *sat, int len) 13 : i nt i : 文字列の位置カウンター 15 : 日本語サーチボインタからの位置 Char 日本語サーチボインタ 17 : po=old; 0 L D 文字列の先頭にセット for(i=0,j=0; i + + , j + + ) / * 最大文字長まで差分出力を行う * / i く 1 en : 20 : if(iskanji (*new)) / * 現在注目の位置が漢字 1 ハ・イト目 ? * / 22 : / * 日本語 1 バイト目の時には , 0 し D * / 23 : / * の注目文字も , 漢字 1 ハ・イト目かを * / 24 : / * 調べて , なおかっ , 2 ハ・イト目も合 * / / * 致しているか ? 26 : 28 : &&(nthctype(po, j)== 29 : 30 : / * 日本語 1 パイト目だから , 日本語 31 : / * サーチボインターを再セット 32 : / * 上記条件に一致しているので , NU 33 : / * ししをセットする 34 : / * 漢字 1 パイト目だから , 2 パイト目 35 : / * の処理を行うためにポインタをひ 36 : / * とつ進める 01d 十十 : new 十十 : sab 十十 : oat 十十 : nat 十十 : sat 十十 : i 十十 : j 十十 : 38 : / * 同様に 2 ハ・仆目にも NU ししセット *sab=NU しし : 39 : *sat=NULL; 40 : / * 0 し D と NEW が一致していない場合は / * 差分には N E W を送り出す 42 : *sab=*new : 43 : *sat=*nat : 44 : 01d 十十 : new 十十 ; sab 十十 : oat 十十 ; nat 十十 : sat 十十 : i 十十 : j 十十 : 45 : *sab=*new ; 46 : *sat=*nat : 49 : 50 : 52 : 53 : 55 : 0 po=old; *sab=NU し L : *sat=NULL; e ー se 現在注目の N E W が半角の場合 i f (nthctype (po, j) ! : の / * 0 L D が半角文字でない場合は N E W をセットする *sab=*new : *sat=*nat; e 1 se Conference Room 139

アルゴリスムアータ構造入門 別扱いにしなければなりません。 この例のように , 一方が他方を追いかけ るという関係のふたつのポインタを使って リストをスキャンする , というのは連結リ Fig. 11 Fig. 12 Fig. 13 関数 inse の動作 ( 3 ) head NULL 境界条件その 1 head ストを処理するための定石て、す。そして , セルを使って連結リストを表すという手法 を用いることによって , 境界条件をとくに 意識しないてもコーディングがてきます。 2 n ew NULL 空リストへの挿入 0 空リストへ v 引 ue = 2 のセルを挿入する 0 左が挿入前 , 右が挿入後の状態である 0 変数 head がセルと同じ形式になっているので , 特別扱いしかなくても正しく処理てきる 関数 inse の動作 ( 4 ) 2 1 new 5 7 境界条件その 2 ーーリストの先頭への挿入 0 変数 head がセルと同じ形式になっているので , 特別扱いしなくても正しく処理できる 0v 引 ue = 1 のセルを追加する。このセルはリストの先頭に挿入される 関係 inse の動作 ( 5 ) head 2 境界条件その 3- ーーリスト末尾への挿入 5 7 q まとめ 12 る予定て、す。 ータ構造を表現する方法についても説明す た , 連結リストをベースに , より複雑なデ (doubly linked list) を取り上げます。ま て循環リスト (circular list) と双方向リスト 来月は , 連結リストのバリエーションとし データ構造「連結リスト』を勉強しました。 今月は , リストを表現するもうひとつの new N U LL P 0v 引 ue = 15 のセルを追加する。このセルはリストの末尾に追加される 80 CMAGAZINE 19 8

( たとえば , セルの値をローカル変数にコヒ。 ーしておき , あとて、関数の値としてリター ンする , など ) 。最後に , 8 行目ては , 関数 f 「 ee を呼び出して , 削除したセルを解放しま す。 リストの先頭の要素を削除する手順は , List 2 ②のようになります。ここて、は , 連 結リストは , 先頭へのポインタ head によっ て管理されていることを想定しています。 境界条件は , 「リストが空である』というこ とて、す。 3 ~ 4 行目て、 , リストが空てあれば ェラーにしています。挿入の場合と同様に List 2 ( 1 ) と List 2 ( 2 ) の違いは , x ー > next が head に置き換わっただけて、す。削除の処理 も , リストの先頭を , struct CELL * head : て、はなく , struct CELL head ; とすることによって , 先頭のセルの削除と 途中のセルの削除を統一的に扱うことが可 能てす。つまり , x = &head ・ として List 2 ( 1 ) を実行すれば , 先頭のセル を削除することがて、きます。また , リスト が空の場合も正しく扱われる ( 工ラーになる ) 境界条件の扱しい ことがわかります。 78 CMAGAZINE 19 囲 8 数値の昇順 ( 小→大の順 ) に並んて、いる連 界条件を意識せずにすみます。 とがなくなり , プログラムを書くときに境 ると , 見かけ上 , 連結リストが空になるこ リストの先頭をセルによって表す方法をと て , 簡単に扱えることを示しました。また , ば , 先頭への挿入と削除を特別扱いしない のポインタて、はなく ) セルそのものを使え 先ほどリストの先頭を示すのに , ( セルへ す。 ストが空のときの扱いが境界条件になりま リストの処理て、は , 先頭 / 末尾の扱い連結リ 条件に注意することがたいせって、す。連結 実際にプログラムを書くうえて、は , 境界 連結リストからの削除 ( 1 ) ポインタ x で指されたセルの直後のセルを削除する List 2 8 : free(p); 7 : p で指されたセルの内容を取り出す p->next; X—〉 next p = x->next; fatal-error ( " 最後の次にはセルはないので削除できない。 " ) i f (x->next = = NULL) 1 : struct CEL し *p; 6 : 5 : 4 : 3 : 2 : ( 2 ) リストの先頭のセルを削除する 7 : p で指されたセルの内容を取り出す head = p->next; 5 : P = head : fata l-error ( " リストが空なので削除できないつ : if (head = NU しい 1 : struct CEL し *head, *p; ※変数 head がリストの先頭を指しているものとする 6 : 4 : 3 : 2 : 8 : free(p) : 結リストがあり , そこに新しい要素を追加 したとしましよう。当然のことながら , 要 素の昇順の並びを保っ位置に挿入しなけれ ばなりません。セルは , struct CELL { st 「 uct CELL *next ; int value ; と定義されているものとします。また , 連 結リストは次の変数 head によって先頭が与 えられています。 struct CELL head ; この連結リストに新しい要素を追加する 関数 insert を List 3 に示します。このプログ ラムのポイントは , 連結リストをたどると きにふたつのポインタ変数 p と q を使ってい るという点てす。ポインタ p は , 現在着目し ているセルを指しています。もう一方のポ インタ q は , p が指している直前のセルを指 すようになっています。 連結リストには , 指定したセルの直後へ の挿入は簡単にて、きるが , 直前への挿入は て、きない , という性質がありました。そこ て , 関数 inse 「 t て、は着目するセルの直前のセ ルへのポインタをもっことによって , この 問題を解決しています。 うになっています。また , wh ⅱ e ループを 1 回 と初期化します。この時点て、は Fig. 9 のよ q = &head ; P head . next : まず , wh ⅱ e ループに入る前に がこの順に登録されていることにします。 う。連結リストにはあらかじめ 2 , 5 , 7 , 12 次にポインタ q の役目を考えてみましよ 要があります。 のとき , 新しい要素は p の直前に挿入する必 い ) 値をもっ要素が見つかった場合て、す。 きいはり正確には大きいか、あるいは等し NULL になります。後者は , 変数 a よりも大 す。また , リストが空て、あった場合も p が 存のすべての要素よりも大きかった場合て、 なります。前者のケースは , 変数 a の値が既 へのポインタが入っているかのいずれかに 占て、は , p には NULL が入っているか , セル となります。この wh ile 文を実行し終えた時 P p—>next; while (p ! = NULL & & a > p—>value) P head . next ; ると , while ループは , まずは , ポインタ q がないものとして考え

連結リストへの挿入 List 1 い ) ポインタ x で指されたセルの直後に新しいセルを挿入する 1 : struct CEL し *p; 3 : if ()P = malloc(sizeof(struct CE しい)) fatal-error(" メモリが足らない "): 5 : セルに値をセットする p->next x—>next; x—>next 7 : 6 : 4 : 2 : ( 2 ) リストの先頭に新しいセルを挿入する ニ NULL) ※変数 head がリストの先頭を指しているものとする アルゴリスムアータ構造入門 struct CELL * p ; て、 , 境界条件をうまく扱うことがて、きます。 ねに少なくともひとつのセルが存在するの ールドのデータには意味がありません。つ ダミーて、 , 次セルへのポインタ以外のフィ とつのセルは連結リスト自身を表すための なります (Fig. 8 ) 。実際には , このただひ は最低て、もひとつのセルが存在することに このような方式をとると , 連結リストに とします。 printf("%d*n", p—>value) ; for(p=head, next : p!=NULL ; p=p—>next) 1 : 2 : 3 : 4 : 6 : struct CELL *head, *p; if ()p = malloc(sizeof(struct CE しい)) fatal ー error ( " メモリが足らない " ) : = NU しい 5 : セルに値をセットする head : p->next 7 : head = p : 要素がひとつもないリスト る部分 ) にはゴミの値が入っている ※ head セルの左半分 ( セルの値が入 head Fig. 8 セルを使ってリストの先頭を表す方法 ている部分が , head に変わっている点だけ と , その違いは 6 ~ 7 行目て x ー > next となっ ところて、 ,List 1 ( 1 ) と List 1 ②を比べる す。 なりません。これは , 典型的な境界条件て する場合ては , 異なった処理をしなければ るのに , 先頭に挿入する場合と途中に挿入 このように , 連結リストに要素を挿入す たときも , List 1 ②はうまく動きます。 の場合 , つまりもともとリストが空てあっ ります。境界条件として , 変数 head が NULL の先頭に挿入するには List 1 ②のようにな たな要素を挿入するものてす。連結リスト さて List 1 ( 1 ) は , 連結リストの途中に新 て、す。これは , 連結リストの先頭が struct CELL 型そのものて、はなく , struct CELL 型 へのポインタて、与えられているからて、す。 struct CELL head , て、はなく , struct CELL *head ; そこて , 変数 head を , 入もまったく同様に扱うことが可能て、す。 と定義すると , 先頭への挿入も途中への挿 2 head って処理するには , ます。また , セルをひとつずつ順番にたど として , List 1 ( 1 ) を適用すればうまくいき x=&head ; つまり , 先頭へ挿入するには , 5 4 つの要素 ( 2 , 5 , 12 , ー 4 ) をもつリスト 連結リストからの削除 次に連結リストから特定のセルを削除す ることを考えましよう。ポインタ x て、指され たセルの直後のセルを削除するには , List こて、 , 境界条件と 2 ( 1 ) のようにします。 して , 削除すべきセルが存在しない うケースを考慮する必要があります。ポイ ンタ x が連結リストの最後のセルを指してい る場合が , このケースに該当します。ポイ ンタ x 自身が最後のセルを指しているとき , 当然のことながら次のセルは存在しません。 て、すから , この場合には削除しようにも無 理な相談て、す。これをチェックしているの が , List 2 ( 1 ) の 3 ~ 4 行目て、す。 , 7 行目の『 p て、指されたセルの内容 を取り出す』という部分て、は , P て指された セルの内容を使って必要な処理を行います 12 アルゴリズムとデータ構造入門 77

五ロ ニ = ロ ニ = ロ はじめて学ぶプロクラー ニンク Fig. 2 線形連結リスト head pointe 「 セル ポインタ NULL tail pointe 「 を見てください のようになっているのて , ぜひ覚えておい てください。 まず , このプログラムの概要について説明 線形連結リスト 22 行目ては , 確保した領域の先頭ポイン します。最初に , メモリに確保したい領域 ひとつの double 型のデータをもつリスト タを後て使用するために保存しています。 の大きさ ( 配列の添字に相当する ) を入力し 構造を実現するためには , 以下のような構 25 ~ 29 行目にかけて , 確保した領域にデー ます。そして , 関数 ma 日 oc を使い , 入力し 造体を用います。 タを入力しています。入力が終わるのは , た数の dou e 型の配列に相当する領域を動 struct list { EOF を入力するか , 確保した配列の個数だ 的にメモリに取ります。さらに確保した領 け入力し終わったときてす。 31 ~ 33 行目に 域に , データを入力します。入力の終了は / * データ部 * / かけては , 確保した領域に入力されたすべ 確保した領域の個数まて入力したときか , てのデータを出力しています。 34 行目て、は , struct list * next ptr ; EOF を入力したときてす。そして , そのデ / * ポインタ部 * / 確保していた領域を解放しています。この ータを出力し , 領域を解放しています。 ように , 関数 f 「 ee は , 関数 rn 訓 oc て確保した それては ,List 4 を実際に追いかけてみま 構造体 struct list 型の中に , さらに struct 先頭ポインタを引数として , 確保した領域 しよう。 10 , 11 行目ては , 領域の大きさを入 list 型のポインタがメンバになっています。 を解放するのてす。 力しています。 13 ~ 16 行目は , 0 以下の領域 この再帰的とも見える宣言は , 慣れないう このプログラムを実行するとき , 確保し を取ろうとしたときのエラー処理をします。 ちは奇妙に感じるかもしれませんね。しか た領域すべてにデータを入れないて入力を そして 18 行目て , 実際にメモリを動的に取 終了ー十て終了 ) し , 出力すると , し , メンバてある っています。関数 ma Ⅱ oc の引数は sizeof 入力されていない部分のデータにゴミが入 struct list * next ptr ・ ( doub 囘に確保したい配列の大きさをかけ という部分は , あくま <struct ⅱ st 型のポイ っていることが確かめられると思います。 たものになっています。こうすることによ ンタてあり , struct ⅱ st てはありません。 これは関数 ma 日 oc は領域を確保するとき って , 必要なバイト数をメモリに確保てき データとポインタの組は , セル (cell) と呼 に , 初期化を行わないためてす。関数 m 訓 oc るのてす。もし doub 型のサイズが処理系 ばれます。セルはデータ部とポインタ部て、 が初期化をしないために , このプログラム によって異なっていたとしても , sizeof を使 構成されます。このセルを複数個 , ポイン を何度も走らせてみると , 前に入力したデ うことにより正常に動作するプログラムに タにより連結することによって , 連結リス ータがメモリに残っているのがわかるてし なるのてす。 ト (linked list ) が実現てきます。つまり , セ 関数 ma 日 oc の戻り値は , 確保した領域の よフ。 ルのポインタ部が , 次のセルを指すように 先頭アドレスを示す void 型のポインタてす。 連結しているのてす。この連結リストのこ したがって , 用いようとしている型にキャ とをスト構造クと呼んています。この ストしなければなりません。この場合は , ような構造を固定長のデータ部をもつ線形 doub 型のポインタにキャストすればよい 連結リストとも呼びます。 リスト構造を実現するには , 自己参照的 わけてす。また , 関数 m 訓 oc は , 領域が確 リスト構造を用いるには , リストの先頭 構造体を用います。自己参照的構造体とは , 保てきなかったときに NULL を返すのて , を表す先頭ポインタ (head pointer) と , リ 構造体自身の中に自分と同じ構造体型て指 NULL と比較することにより , 工ラー処理 ストの末尾を表す末尾ポインタ (tail すポインタをメンバとしている構造体のこ をしています。この部分のようなプログラ p 。 inter ) が必要てす。最後のリストてあるこ とてす。 ムの書き方は , 関数 ma ⅱ oc を使用する定石 はじめて学ぶ C プログラミング 113 double data ;

Skin 0 れ d M PARAM mpl , M PARAM 叩 2 13 : HAB 58 : } ones List 4 Presentation Manage 「用のスケルトンの例 [ 4 ] [ 5 ] [ 6 ] [ 8 ] [ 9 ] [ 7 ] Farrel Tim Windows 1987. 、、 Programming with Que Corporation 2 : 3 : 4 : 5 : 6 : 7 : 10 : 15 : 17 : 20 : 22 : 23 : 24 : 25 : 26 : 28 : 29 : 30 : 31 : 32 : 33 : 34 : 35 : 36 : 38 : 39 : 40 : 41 : 42 : 43 : 44 : 45 : 46 : 48 : 49 : 50 : 51 : 52 : 53 : 54 : 55 : 56 : * Presentation Manager 用のスケ丿レトンの例 * ユーザが普通のシステム・メニューを使って , * ウインドウをクローズするのを待つだけ . 8 : #include く 0S2. h > 9 : #include ” sample. h ” 11 : MRESULT EXPENTRY WndProc( HWND hwnd, USHORT hab ; 14 : static CHAR szClientClass[] 16 : void cdecl main( void ) msg, Sample ” ; HMQ HWN D HWN D QMSG hmq ; hwndClient; hwndFrame; qmsg; static ULONG fICreate = FCF—TITLEBAR ー FCF—SYSMENU ー FCF—TASKLIST ー szClientClass, "SampIe Application ” (PULONG)&flCreate, hwndFrame = WinCreateStdWindow( HWND—DESKTOP, WS—VISIBLE, f 1 C reate = FCF_STANDARD : WinRegisterCIass( hab, szClientClass, WndProc, OL, 0 ) ; hmq = WinCreateMsgQueue( hab, 0 ) : hab = WinInitialize( NULL ) : FCF_SHELLPOSITION ー FCF MINMAX ー FCF_SIZEBORDER; (PHWND)&hwndCI ient ) ; OL, NULL, OL, whi le( WinGetMsg( hab, (PQMSG)&qmsg, (HWND)NULL, 0 , Grayson,Paul, 、、 Windows of Opportunity" PC Tech Journal , Feb. 1987 , p. 70. Hayes , Frank , and Nick Baran , 、、 A Guide to GUIs" BYTE, Jul. 1989 , p. 250. lacobucci , Ed. , 、、 OS / 2 Program mer's Guide" Osborne/McGraw ー Hill , 1988. McNierney, Ed. , 、、 Projecting a Graphics lnterface" PC Tech Journal Mar. 1988 , p. 54. McNierney , Ed. , $The User at the Controls" PC Tech Journal , Mar. 1988 , p. 65. [ 10 ] 、、 Microsoft Windows Software WinDispatchMsg( hab, (PQMSG)&qmsg ) : WinDestroyWindow( hwndFrame ) ; WinDestroyMsgQueue( hmq ) ; WinTerminate( hab ) ; 47 : MRESULT EXPENTRY WndProc( HWND hwnd, USHORT msg, M PARAM mpl, PARAM mp2 ) switch( msg ) { case WM_CLOSE: WinPostMsg( hwnd, WM—QUIT, break; default: return( WinDefWindowProc( hwnd, return( FALSE ) : [ 2 ] [ 3 ] OL, 0L ) ; msg, mpl, 叩 2 Macintosh" , vols. I ー V , Addison Wesley , 1985. Apple Computer [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] 好むと好まざるとにかかわらず ( 1989 年 11 月号の CL 誌のコラムにプルーストンキンが 書いた「 GUI なんてアッカンべー / 」を見てく ださい ) , GUI はいまや主流派てす。ここて は , そのごく一部をご紹介しただけて、す。 GUI について , より詳しく知りたい方は , 参 lnc . 、、 Human DeveIopment Kit" Microsoft Corp. , 1987. Peck , Robert A. , 、、 Programmer's Guide to the Amiga" ,SYBEX lnc. , 1987. PetzoId , CharIes , 、、 Programming the OS/2 Presentation Man ager" Microsoft Press , 1989. Rochkind , Marc J. , "Technical Overview of the ExtensibIe Vir tual Toolkit(XVT)" ,Advanced P r 0 g r a m m i n g I n s t i t u t e Ltd. , 1987. Seymour , Jim , $The GUI : An lnterface You Won't Outgrow PC Magazine 8 ( 15 ) : 97. Valdes , Ray ,$A Virtual T001kit for Windows and the Mac BYTE, Mar. 1989 , p. 209. 考文献を見てください [ 参考文献 ] [ 1 ] Apple Computer lnc. $lnside lnterface GuideIines : The Apple Desktop lnterface" Addis on-WesIey , 1985. 、、 Commodore Business Machines lnc. Amiga lntuition Reference Manual" , Addison-Wesley , 1986. Eric Giguere 氏は , カナダ , オンタリオ州 ウォータールー大学計算機科学科の 4 年生 て、 , ときどきコンヒ。ュータ雑誌に寄稿して います。 30 CMAGAZINE 19 8

28 来のプログラミングとかなり違いがありま す。細かい事がらが多いのて、 , それらに圧 倒されそうになります。 は , たんに関数名を書き換えたぐらいて、は のて、すから当然て、す。しかしソースコード くりて、すが , 後者は前者をもとに作られた Windows と PM は外見や使い勝手がそっ のことはいえません。 ししか使った経験がないのて、 , あまり多く テム用の GUI てす。 OS/2 も PM も , 私は少 PM は IBM の OS / 2 オペレーティングシス Manager (PM) PresentatIon ドに多様な機能をもたせることがて、きます。 せん。したがってプログラマは , キーポー 用が推奨されていますが , 必須て、はありま スドライバもサポートします。マウスの使 クポードや各種プリンタ用の無数のデバイ のグラフィックと , さまざまなグラフィッ ートします。それはまた , デバイス非依存 Mac と同様 , Windows もリソースをサポ れるからて、す ) 。 て、はなく , アプリケーション全体に向けら は特定のウインドウやウインドウクラスに しようか ? それは , ある種のメッセージ べントを直接 window class に送らないのて、 window class に回して処理させます ( なぜイ WinMain() 関数に受け取り , 次にそれらを 起すると , アプリケーションはそれらを が window class の関数て、す。イベントが生 共有しますが , その中て、もっとも重要なの ドウはすべて , そのクラスに共通の機能を ません。そのクラスの下に作られるウイン ドウクラスを定義して登録しなければなり ウインドウを作るためには , そのウイン イスの構成部位を扱うことて、す。 オプジェクト指向的に , ユーザインタフェ もっとも顕著な違いは , Windows は , より グラムて、す。 List 1 や List 2 と比べた場合の List 3 は , Windows の基礎的な骨格プロ 1990 8 すまないくらい , 可搬性にはほど遠いもの Skin and 12 : / * 0 n e 5 80 : 81 : 82 : 83 : 84 : 85 : 86 : 88 : 89 : 90 : 91 : 92 : 93 : 94 : 95 : 96 : 98 : 99 : 100 : 101 : 102 : 103 : 104 : 105 : 106 : 107 : 108 : 109 : 110 : 111 : 112 : 113 : 114 : 115 : 116 : 117 : 118 : 119 : 120 : 121 : 122 : 123 : 124 : 125 : 126 : 127 : 128 : 129 : 130 : 131 : LiSt 2 List 3 0 struct lntuiMessage *msg; done : int while( msg (struct IntuiMessage * ) GetMsg( window->UserPort ) ) { / * メッセージを待つ * / WaitPort( window- 〉 UserPort ) : while( !done ) { done ニ FALSE; / * イベント・ループ * / SetMenuStrip( window, &MenuDefn ) : / * メニュー接続する * / return( 0 ) : if( window = NULL ) window = 0penWindow( &WindowDefn ) ; ーメニューがウインドウに接続していなければならない . * / / * ウインドウをオープンする return( 0 ) ; if( IntuitionBase = NULL ) IntuitionBase = (void * ) 0penLibrary( ” intuition. library ” , OL ) : 共用ライブラリをオープンする . * / / * まず I Ⅱ tuition の機能にアクセスするために , Microsoft Windows のプログラム例 return( 0 ) : CIoseLibrary( IntuitionBase ) : CIoseWindow( window ) : CIearMenuStrip( window ) : / * 後始末 * / ReplyMsg( (struct Message * ) msg ) ; break ; done ニ TRUE; if( MENUNUM( msg->Code ) ! = MENUNULL ) { case MENUPICK: break ; done ニ TRU E ; case CLOSEWINDOW: switch( msg->Class ) { * Microsoft Windows のプログラム例 * 普通のシステム・メニューを使ってユーザが , * ウインドウをクローズするのを待つ . #include ”響 indO 響 s. h ” 10 : WNDCLASS WndClass; 11 : 9 : 8 : 6 : 5 : 4 : 3 : 2 : 0 CMAGAZINE