列ごとにその仮想配列のアクセスの特性に index には , 補助記憶の空き容量の範囲て、 ンクルードします。 応じて , バッフアのページ数や 1 ページの大 ②仮想配列の要素の型を宣言します (test2. 負けない任意の数を指定て、きます。 きさを指定てきるようになっています。 c の typedef 宣日。 ) ' の型には任意の型が この関数は fread ( ) に当たります。 指定て、きます。つまり int や char などの基 int vawrite(VARRY * vap, void * ptr, ラブラリ関数の 本型のほかに , 構造体や ( 普通の ) 配列な long index) : ptr て、示されるレコードの内容を vap て、指 ど , どんな型ても指定てきます。 仮想配列ライプラリて、は以下の関数が利 定される仮想配列の添字が index て、ある要 ③仮想配列をほかの変数と同様に宣言しま 素に書き込みます。工ラーが発生したと 用てきます。 す。つまり VARRY 型の変数を宣言します き一 1 , 正常終了したとき 0 を返します index VARRY * vaopen(size t recsiz, int pagsiz, (test2. c の main 関数のローカル変数 ) 。 には , 補助記憶の空き容量の範囲て、負て、 int bufsiz, char * file) ; れは標準入出力関数の FILE 型の変数に当 1 要素のサイズ (recsiz)'* イト , 1ページ (pag ない任意の数を指定てきます。 たります。 siz) 要素 , バッフアサイズ (bufsiz)R—ジ この関数は fwrite( ) に当たります。 VARRY 型変数を vaopen 関数を用いてオ ープンすると , 以後その変数を介して仮 の仮想配列をファイル ( file ) にオープンす ライラリの使い方 る。この関数は VARRY 構造体へのポイン 想配列にアクセスてきるようになります。 ④仮想配列への書き込みには vawrite 関数 , タを返します。オープンされた仮想配列 ライプラリの使い方の例として , テスト へのアクセスはこのポインタを用いて行 読み出しには varead 関数を用います。第 います。補助記憶域の不足などて仮想配 の点数の平均と分散を求めるプログラムを 1 引数には vaopen 関数を用いて得た 列がオープンてきないときは NULL を返 VARRY 型の変数を指定します。読み込み 示します。受験者の名前と組みを入力して , 先と書き込み元は , その要素の型を持っ します。 それをもとに結果を出力します。分散を求 file が NULL のときは , この関数が内部て、 変数へのポインタて、指定します。 varead めるには , 定義式を少し変形した式を用い 標準関数の tmpfile ( ) を用いて作成したフ たほうが計算が楽になりますが , ここては 関数を実行すると , そのポインタが指す 変数に指定された添字の要素の内容を代 ァイルが仮想配列のメモリとして用いら 仮想配列への書き込みと読み出しの例を示 れます。 入します。 vawrite 関数を実行すると , そ すため , あえて定義式どおりの計算を行い VARRY 構造体は , stdio. h の FILE 構造体 のポインタが指す変数の内容を指定され ます。 た添字の要素に代入します。 に当たり , vao n ( ) は fopen ( ) に当たりま 仮想配列と普通の配列の使い方の差を示 ⑤仮想配列が必要なくなれば vaclose 関数を す。 すため , 扱えるデータの数を除き同じ内容 用いて , その仮想配列をクローズします。 のプログラムを普通の配列を用いて実現し void vaclose(VARRY * vap) : これにより va 叩 en 関数の呼び出し時に主 vap て指定される仮想配列をクローズしま たものと仮想配列を用いて実現したものを す ova 叩 en( ) の引数 file に NULL を指定し 己憶上に確保されたバッフアなどのメモ それぞれ付録ディスク testl. c , test2. c に示 た場合 , 仮想配列の記憶のために作られ リが解放されます。複数の仮想配列を用 します。 たファイルは補助記憶上から自動的に消 い , かっ , それらの存在期間が異なるよ ふたつのプログラムを実行すると受験者 滅します。そうて、ない場合は , file て指定 うなプログラムを書く場合 , 貴重な主記 の名前と点数の入力を繰り返し求めてきま されたファイルの消去はユーザの責任と この関数をま 憶をムダにしないために すのて , それぞれを受験者の人数分入力し めに呼び出したほうがよいて、しよう。 なります。 ます。全員分を入力し終えたら , 次の入力 この関数は fclose ( ) にあたります。 配列といいながら , varead, vawrite 関数 時に , 点数に負の数を指定します。このと を用いなければならないという仮想配列へ int varead(VARRY * vap, long index, void き対応する受験者の名前は何てもかまいま のアクセス方法に抵抗を感じる方がいるか * ptr) : せん。そうすると平均と分散が画面に出力 vap< 指定される仮想配列の添字が index もしれませんが , プログラムを設計したり , されて , プログラムは終了します。 てある要素の内容を ptr て示されるアドレ 仮想配列を使うには以下のようにします。 コーディングしたりする際に配列という概 ①仮想配列を使うプログラムは , ファイル 念を用いることがてきることが重要て , そ スに読み出します。工ラーが発生したと の先頭て、ヘッダファイル varry. h を必ずイ の表記はあまり重要てはありません ( ほかの , 正常終了したとき 0 を返します。 一三ロ 140 C MAGAZINE 1 1 7

ワンポイント プログラミング 講座 RS232 ℃ 1 : #include く dos. h 〉 2 : #include く coniO. h> 3 : 4 : / * 記号定数の定義 * / 5 : #include "talk. h ” 6 : 7 : / * R S 2 3 2 ー C 初期化 * / 8 : void rs_init( void ) union REGS regs; regs. h. cl ー 0x0E; regs. h. 引 = 0X01 : = 0X4C08 : regs. X. bx int86( 0xDC, &regs, &regs 16 : } 18 : / * 受信可能チェック * / 19 : i nt rs-send-ready ( VOid ) 20 : { return( ( ( i 叩 ( 0X32 ) & 0X05 ) = 0X05 22 : } 23 : 24 : / * 1 文字出力 ( R S 2 3 2 ー C ) * / 25 : int rs-putc( int c ) 26 : { union REGS regs; 28 : 29 : regs. h. ah = 0X04 : (unsigned char ) c: 30 : regs. h. 引 intdos( &regs, &regs ) : return( (int ) regs. h. al ) : 32 : 33 : } 34 : 35 : / * 1 文字入力 ( R S 2 3 2 ー C ) 36 : int rs-getc( VOid ) 37 : { 38 : union REGS regs; 39 : 40 : regs. h. ah = 0X03 : intdos ( &regs, &regs ) : return( (int ) regs. h. ) : 42 : 43 : } 44 : 45 : / * 受信バッフア内の文字数チェック * / 46 : int rs-loc( void ) 47 : { union REGS regs; = 0x0e; 50 : regs. h. cl regs. h. 引 = 0X00 : int86( 0xDC, &regs, &regs ) ; 52 : return( (int ) regs. x. ax ) : 53 : 54 : } 55 : 56 : / * キーポードバッフアの状態チェック 57 : int kbd-buff ( void ) 58 : { union REGS regs; regs. h. ah = Ox0b; intdos( &regs, &regs 62 : return( ( regs. h. 引 64 : } RS232. H 1 : rs-init( void ) : extern VO i d 2 : int rs-send-ready( void ) : extern 3 : int rs-putc( int ) : extern 4 : rs-getc( void ) : int extern 5 : rs-loc( void ) : i nt extern 6 : kbd-buff( void ) : extern i nt List 2 List 1 TALK.H 1 : / * 記号定数の定義 * / 2 : #define 3 : 4 : #define 5 : #define 6 : #define 7 : 8 : #define 9 : #.define List 3 ever OK BUSY READY EMPTY 一 1 0 1 ? READY : BUSY ) : 1 1 仕様の決定 今回は上記の関数を利用して前回のプロ グラムに手を加え , 相手のディスクのディ レクトリ参照やファイル転送がてきるよう に拡張を行います。前回は単にキーポード からの入力データを送信し , 受信データを 端末に表示するだけの遊びにしか使えない プログラムてしたが , 今回はもっと実用的 な通信プログラムになるはずてす。まず , プログラムの仕様を決めなければなりませ ん。以下に実現させたい機能を列挙します。 ① 直結によるデータ送受信を基本とし , ヘイズ AT コマンド準拠モデムや JUST ー PC モデムなどによる電話回線による接 続も可能にしたい ② プログラムは 2 台て同じものが動き , ど ちらが先に起動されてもよい。回線が 接続した場合 , その旨のメッセージを 出力し , また , 一定時間未接続の場合 プログラムが自動的に終了する。 各機能は。ンド入力式にする。。 ③ マンドは以下のものをサポートする ( コ ワンポイントプログラミング講座 131 = 0 ? EMPTY : BUSY ) :

工ル・エス・アイジャパン lnformation from CompiIer Makers LSI C -86 Ver. 3.30 ライプラリのソース (), および 数のうち , 多バイト文字関係と 6 今回は , 6 月よりバージョンア 13 登録カード アセンプリ言語 ) locale. h を除く , すべての関数を用 ップ版のリリースを開始した LSIC 動作環境 7 ROM 化ツールおよびトレー ー 86 Ver. 3.30 を簡単に紹介しま 意しています。さらに UNIX< 用意 ングプログラム す。 されている関数や , MS-DOS との 豊富なサンプルプログラム インタフェイス関数など , 数多く 8 の関数を用意しています。 コンパイラドライバ (lcc) 9 言語仕様 また Ver. 3.30 から新たに追加さ 10 プリプロセッサのソース (cpp) れた関数を付録ディスク function. 11 UNIX ライクなプログラム保守 ・ ANSI 標準規格にほば準拠して tbl に収録しました。 ツール (make) 12 日本語マニュアル ・多バイト文字 (wchar t ) はサポー プロファイラ トしていません。 far/near/recursive/nonrec を Fig. 1 ROM 化プログラムの流れ プログラムを実行したとき , ど 追加しています。 ASM ソース C ソース の文を何回実行したか , またどの a86 86 くらい時間がかかったかなどの , プログラムの実行に関する情報を パッケージには ROM 化のための プロファイル情報と呼びます。プ 初期設定モジュールのソースが含 ロファイラは , このプロファイル まれています。これをターゲット 情報を得るためのツールて、す。プ システム用に修正することによっ ロファイラを使うことにより , 条 て , どのようなシステムにも対応 件判定の論理ミスなどを容易に発 見てきます。実行回数の多い関数 てきます。 リンカⅡ d. exe は . EXE ファイルだ を最適化すれば , プログラム全体 けてはなく , コアイメージ ( バイナ の効率を上げることがてきますが , リ ) あるいは intellec HEX ファイル プロファイラはその指標を与えて を生成します。 くれます。 lld に対してセグメントがロード prof は計数型プロファイラて , プ Fig. 2 プロファイル情報 されるべきアドレスを与えれば , ログラムのどの文を何回実行した かをカウントします。例として「エ ターゲットシステムに合わせたメ ラトステネスのふるい」を実行し , モリ配置の ROM モジュール作成て そのプロファイル情報を出力する きます。 と Fig. 2 のようになります。リスト lld は MS-LINK と同等のマップ の左端の数字は右側の文が実行さ ファイルを生成します。このマッ プファイルを ICE などて利用てきれ れた回数を表しています。 ば , シンポリックデバッグが可能 バッケージ内容 ROM 化プログラムの流れを Fig. 1 に示、します。 1 C コンパイラ 2 アセンプラ 3 リンカ ライプラリの特徴 4 プロファイラ ライプラリ (lib 形式 ) ANSI 標準規格て定義された関 5 160 C MAGAZINE 1 1 7 MS-DOS Ver. 2.1 以上 メモリ 384K バイト以上 供給メディア 5 〃 2HD , 3.5 〃 2HD ( そのほかはお問い合わせくだ 価格 48 , 000 円 0 ASM ソース ,asm ↓ MASM ほか ↓ ROM 化 lcc c cf c 86 「 86 lcc c 「 86 ・ obj . obj lcc マップファイル MAP ROM モジュール hex またはコア #include く stdio. h 〉 8190 #define SIZE #define TRUE 1 #define FA し SE 0 flags[SIZE + 1 ] : Char nain() 1 void 1 k, i, prine, count, iter; unsigned 1 printf("10 iterationsYn"); 1 fO 「 (iter = 1 : iter ← 10 : iter 十 + ) { 1 count = 0 : 10 fo 「 (i = 0 : i く : 引 ZE : i + + ) 10 flags[i] = TRUE; 81910 for (i : 0 : i ← SIZE.• i + + ) if (flags[i]) { 81910 18990 pr i ne fO 「 (k - i + prine: k く = SIZE; k + : prine) 18990 149990 flags[k] = FALSE; 18990 oount 十十 : 81910 1 0 printf("Xd prinesYn" count) :

を使って求め , 代入する。 Fig. 10 に示す方法がポインタの基本とな り , 配列や文字列などの処理をポインタを 使って行う。 こて , C 言語においてポインタを使用 し , 関数内て宣言している変数 ( 自動変数 ) をほかの関数て参照する場合の例を Fig. 11 に示す。 C 言語ては呼び出す側の変数ポイン C 言語ては呼び出す側の変数ポインタを関 数の引数とし , 呼び出された関数は , 呼び 出した側の変数をポインタにより間接的に 参照するのてある。 まず , 落ち穂拾いをしなくてはいけませ ん。前回の話の中て , インライン関数のご 利益をさもありがたげに述べたてましたが , SWAP ( ) マクロに対応するインライン関数 を提示しませんてした。 というのも , 関数 版 swap() を書くためには「参照型」の導入が 欠かせなかったからてす。 参照は , C 十十の初心者がまず飛び越えな くてはいけないハードルのひとってす。 C 言 語におけるポインタのように , これを把握 していないと話にならないというわけては ありませんが , 参照を使いこなせるかどう かて大きく差がついてしまうのて , キッチ リ抑えてください 参照は小粒で int&a; という記述は , int 型の変数を参 照するための変数として a を宣言していま す。「参照する」とはどういうことてしよう この連載の読者ともなれば , 「ポインタ」 などという概念は自明のものとして理解さ れていることと思いますが , それて、も参照 は難関てす。 120 C MAGAZINE 1991 7 このような手続きにおいて , C 十十ては , 参照型と呼ばれる機能を使用する。参照型 は , 変数に対し別名を指定する。 実践編 Fig. 13 参照型を用いた Fig. 1 1 の書き換え例 関数の型関数名 1 ( 引数リスト ) 変数 1 の宣言 関数 2 ( 変数 1 ) 関数の型関数名 2 ( テータ型 & 変数 2 ) 変数 2 ″関数 1 の変数 1 を参照 「参照する」とは , a という変数を介して何 かほかの変数にアクセスすることて、す。即 物的にいってしまうと , ほかの変数に a とい う名前を新たに割り当てたのと同じことに なります。 りません。したがって , いったんこのよう て , 参照型変数としての a のアドレスてはあ a て、求められるのは変数 b のアドレスてあっ の代入は b に代入しているのと同じこと。 & しているのとなんら変わりありません。 a へ a に対するあらゆる操作は , 直接 b を操作 られたのだと考えてかまいません。 b という変数に a という別の名前が割り当て ても , あくまても b の影のようなものてす。 繰り返しますが , a を「変数」と呼んて、はい ます。 参照するための変数として a が宣言されてい これなら正しい宣言て、す。 b という実体を int& a int b ; とり歩きしてしまっては困ります。 なのてあるから , ヾ a クという名前だけがひ 実体がなく , ほかの実体を指すための名前 は許されません。 a という変数そのものには ことになるのて , 上のような宣言は実際に つまり a はほかの変数の影として存在する 参照型は , 以下の形式て宣言する。宣言 時には , 必ずどの変数に対し別名を指定す るかを初期値として明記する。 データ型 & 名前 = 式 ( または変数名 ) : Fig. 12 に示すとおり , 変数 1 が対して別名 として変数 2 を定義し , 変数 2 によって変数 1 が参照てきることになる。したがって , Fig. 11 に示した手続きを , 参照型を用い , Fig. 13 のように記述することがてきる。 次回は拡張 C としての解説の最後として , ポインタ ( 今回の続き ) , 構造体を中心に話 を進める。 白倉伸一郎・山本浩文 に初期化してしまった a を , b てはない別の 変数の参照として定義しなおす方法はあり ません。 以下のような使い方が考えられます。 struct A { struct ETC { struct PASSWD { char* name ; int id : } passwd : } etc : このようにネストの入り組んだ構造体の 奧のほうに集中的にアクセスしたいような とき , struct PASSWD& passref a. etC. passwd ; とてもすれば , passref. name や pas sref. id などとしてアクセスすることがてき ます。 define< も同様のことカイきますが , 参照 を使えばスコープが限定されるのて , あと くされがありません。 また , const をつけて , const int& a のよ うに宣言すると , a の値を変更する操作が禁 止されます。最初から , const int tabstop 8 ; のように宣言された変数は値が固定され ますが , 値を変更したあとに途中から固定

COMPUTER PRO-STAFF SYSTEM CREATE O 言彡ロジェクトの 登ク 0 スリ ) しンス 数て 49 という値だからてす。同様に ' 2 ' は 10 一方 , ご存じのように , ANSI C は , 標準 ライプラリについても , 相当充実した決定 進数て 50 てす。 keypress が int<, case のオペランドが 1 , を盛り込んています。 これは原書のとおりて、す。正常に したがって , その部分はもちろん , ANSI コンパイルされ正常に走ります。 C 十十の一部ともなります。 しかし , cin や cout はどうなるのてしよう ? keypress が char<, case のオペランドが それらの元となっている , C 十十の ( 拡張 ) ス 1 , 2 , 3 の場合。これも無事にコンパイルさ トリームオプジェクトの , 定義の数々はど れますが , 正しくメッセージを表示させる ためには , 十囚 ( = コード うなるのてしよう ? ノヾリューが 1 ) 十 , 皿 + 回 ( = コードバリューが ぜひ , ANSIC 十十委員会における , 「標 準クラスライプラリ」に対する , 考え方の動 2 ) 十などと押す必要があります。 向を知りたいものてす。 ANSI C 十十の 標準クラスライプラリは formatting# 書式化 どうなるか ? それからもうーっ , 今回痛感した 今回私が経験したようなことは , Turbo C 十十のマニュアルも含め , 直接的にはどこ 追記しておきます。 プログラミングの界隈ては , 英語の動詞 にも書かれていません。 TurboC 十十のマ format を長らく , 「書式化する」と訳してき ニュアル中て、は , 資料は , 「 INTRODUC ました。「書式指定をする」と訳す場合もあ TIONJ の 5 章「 C 十十入門」の「 C 十十ストリ ームライプラリ」という節。そして先にもあ ります。 ポインタを邸文字列てあるぞ〃と指定し げた , 「 PROGRAMMER'S GUIDE 』の 3 章 たり , 数字の表示桁数とか , 右詰め , 左詰 「 C 十十のストリーム」て、す。 めなどを指定する場合 , この < 書式化する > ライプラリのリファレンスは , 今回 2 冊に という訳語がいちばんピッタリするように 分かれ , あわせて 900 ページ以上にも達しま 思えます。 す。 しかし , 元の動詞 format の意味には , た しかし , それらはすべて , < C の > 関数の とえば今回のように , 「文字列 ( = 数字文字 説明なんてすね。 cin や cout を典型とすると の文字コードの並び ) を数値に変換する」 , ころの , C 十十の標準〃クラスや , クラス といった , より一般的な「データ形式の変換 に付随するメソッド ( 処理子 (manipulator) と 処理」も含まれているのてす。「書式」という 呼んている ) に関する正式のリファレンスが 日本語からは , とうてい , そういう一般的 存在しません。 な変換処理まては , イメージがおよばない 上て感標準ククラス , というように標準 のてす。 の文字をダブルミニュートて囲んだのには , 今回のドジの大きな理由の一つに , 「書式 わけがあります。ストラウストラップらが つき入出力」という場合の「書式」という言葉 著した TThe Annotated C 十十 Reference の本来的な ( = 元の英語の ) 意味を , 私が十 ManuaI 』は , ANSIC 十十の原案文書だと 分理解していなかったことが , あげられる いわれています。そして同書は , 言語本体 と思います。 のリファレンスてすから , 当然のようにラ イプラリに関する記述は一切ありません。 IJ 高品質のンテーションを簡単に実現する、 新世代のプロジェクト指向プログラムヘルバ - です。 CPAD はこれまて C 言語による開発てソフトハウ スが悩んていた、開発時の工数短縮及び複数 人数によるプロジェクト管理を容易に致します。 また、既存のソースリストの仕様書を自動作成し ますの ( 管理体制を容易に画一化することが 可能となり、また、プログラマーの余分な負担を 軽減する事がてきます。 0 CPAD 2 98 シリーズ対応版・・・・・・¥ 85 , 000 ( 消費税別 ) 5 大機能 C スの解析、援助、学習ツールとして ① C 言語ソのドキュメント管理を自動化、一律化する。 ②カーコ、ン & リッチーの書式にソースをリフォーム。 ③ PAD 仕様に準ずる出力機能。 ( 自動出力印刷例参照 ) ④全ドキュメントはエテイタで編集可能。 ⑤豊富な出力機能。 ( 自動出力印刷例参照 ) ソフトウェアインフォメーションセンター く技術的なこ質問・こ相談に電話でお答えします〉 TEL. ( 06 ) 634 ー 2563 受付時間 AMIO : 00 ~ PM5 : 月曜日 ~ 金曜日 ( 祝日を除く ) 3 オオッカ商事 / ー、本社 : 〒 760 高松市西内町 5-14 く資料請求番号 105 > C 言語フォーラム 105

として数えることに注意 ) に当たるとして , パターンを x 文字ずらせばよいことになりま す。 また , 今まて、の例て、はパターンの最後の 文字て、不一致が見つかる場合だけを考察し てきました。パターンの最後以外の文字て、 不一致が見つかったときにはどうすればよ いて、しようか ? Fig. 5 ー①のケースを考えましよう。 ては , パターンとテキストを後ろから前に 向かって順に比較していくと , パターンの 3 文字目の c とテキストの 3 文字目の z が一致 しません。ここて , 単純にパターンを右に 五つずらすと Fig. 5 ー②になりますが , 残念 ながらこれは正しくありません。実際に Fig. 5 ー②にしてしまうと , 本来探索されな ければならないテキストの 4 文字目から始ま Fig. 7 BM 法の原理 ( 5 ) る abcab を見逃してしまいます。 今まて、 , 「パターンを x 文字分ずらす」とい う表現を使っていましたが , この表現は正 しくありません。正確にいえば , 「テキスト の注目点を x 文字分右にずらして , パターン の最後の文字から再び比較を始める」という ことを行う必要があります。この場合には , 不一致が見つかったときテキストの注目点 は ( 左から ) 3 文字目て、した。したがって , テ キストの注目点を 8 文字目に置き , そこにパ ターンの最後の文字が重なるようにパター ンをずらします ( Fig. 5 ー③ ) 。 また , パターン中に同じ文字が 2 回以上出 現する場合もあります (Fig. 6 ) 。この場合に は , Fig. 6 ー②のように最後に現れた場所に よって移動量を決めなければなりません。 さもなければ , 本来見つけるべき場所を見 ①バターンの 2 文字目の b がテキストの d と一致しない ↓注目点 X X X X d C d e X X X X a b c d e テキスト ノヾタ ーン ②文字 d はバターンの後ろから 2 文字目に当たるので , テキストの注目点を ひとつ右へずらして , ノヾターンを重ねる なんとバターンが後戻りしてしまう〃 ↓注目点 X X X X d C d e X X X X a b c d e テキスト バターン ③もし , 配列に従ってバターンを移動すると後戻りしてしまうなら , しよ うがないのでバターンをひとっすらす X X X X d C d e X X X X a b c d e 74 C MAGAZINE 1991 7 テキスト ノヾターン 逃してしまう可能性があります。 B M 法のプログラム さて , こまごまとした話をしてきました が , これを C 言語て、プログラムしたものが List 2 の関数 bm search て、す。この関数の呼び出 し方法は , List 1 の関数 brute force search とまったく同じになっています。 BM 法て、は , 不一致が見つかった文字によ って , パターンを何文字ずらすかを決定し ます。このような情報は , 実際に探索処理 に入る前 ( 前処理 ) て、テープルにするのが適 切て、しよう。この表は , 不一致になった文 字の文字コードを添え字として , 各要素に はパターンをずらす量を入れた配列 skip とし て実現します ( 9 行目 ) 。 こて、 , 1 バイトの 文字は 0 ~ 255 まて、の値をとります。したが って , 配列の大きさを 256 にしておきます。 また , 配列 skip は文字コードによって添え字 をつけます。もし char 型が符号っきだとす ると , めんどうなことになるのて、 , 文字は すべて符号なしとしておきます。 1 行目て、定 義されている uchar は符号なし文字を表しま す。 実際に配列 skip の内容を計算しているのは かって処理するのて、 , パターン中に同じ文 求めています。パターンの前から後ろへ向 16 ~ 19 行目て、 , 先ほど説明した方法て、値を になったら ) , 探索は成功て、す ( 35 ~ 36 行 すべての文字が一致したら ( つまり ,j= って ) 1 文字ずつ比較していきます。もし , 致するかを ( パターンの後ろから先頭に向か 内側のループは , パターンとテキストが一 の最後尾に行き当たるまて、繰り返します。 ープは , パターンをずらしながらテキスト によって構成されています。外側の while ル ています。また , 全体が二重の while ループ 注目点を , 変数 j がパターンの注目点を表し このプログラムては , 変数 i がテキストの れてうまく処理されます。 字が 2 回以上現れても , 最後のものが優先さ

アルゴリズムアータ構造入門 1 : 2 : 3 : 5 : 7 : 8 : 9 : 12 : 13 : 14 : 15 : 20 : 22 : 23 : 24 : 25 : 26 : 27 : 28 : 29 : 30 : 32 : 33 : 34 : 35 : 36 : 37 : 38 : 39 : 40 : 41 : 42 : 43 : 44 : 46 : Boye に M00 「 e のアルゴリズムによる文字列探索プログラム List 2 int bm search(uchar *text, int text_len, uchar *pattern, int pat_len) 4 : / * 長さ text_len の文字列 text から長さ pat_len の文字列 pattern を探索する。 ()M 法 ) * / #def i ne max (), b) uns igned Char #define uchar / * テキストとパターンの不一致が見つかったときに、どれだけ ずらすかを示す表。 * / int skipC256]; / * 変数 i は注目しているテキストの位置、変数 j は注目しているパタ 位置を表わすポインタ。 * / / * 表 skip を作成する。 * / for ( i = 0 : i く 256 : i + + ) skip[i] pat-len; for (i = 0 : i く pat_len skip[pattern[i]] = pat-len ーンの / * ポインタを初期化する。パターンを後ろから前に向かって比較する / * 最初の文字まで一致したら、探索は成功である。 = pattern[j]) { while (text[i] / * テキストとパターンが一致する間、くり返す。 * / J pat-len / * ポインタ j をパターンの最後の文字を指すようにする。 while (i く text-len) { / * テキストの最後尾に行き当たるまでくり返す。 * / ニ pat-len ので、パターンの長さー 1 に初期化する。 * / i + max(skip[text[i]], pat-len ー / * 一致しなかったので、パターンをずらす。 / * ポインタ i と j をそれぞれ 1 文字分戻す。 return i : return ー 1 : / * 結局見つからなかった。 * / リズムて、す。実用的には BM 法はもっとも速 い文字列探索アルゴリズムといえるて、しょ パターンとテキストを重ね合わせて , 右 端から左に向かって順番に文字を比較して いき , パターンとテキストの不一致が見つ かったら , 不一致の原因になった文字によ ってパターンをずらす量を決める , という のが BM 法の考え方て、す。 たとえば , Fig. 3 のようにテキスト abdefgh にパターン abc を重ね合わせて比較すること を考えましよう。まずパターンの最後の文 字をテキストと比較します (Fig. 3 ー① ) 。ハ ターンの最後の文字は c て、 , 対応するテキス トは d になっています。ここて、 , 文字 d はパ ターン中に出現しないことに注目しましょ フ。 文字 d はパターンに現れないのて、 , もしパ ターンをひとつずらしたとしても , やはり 文字 d のところて不一致になるのは明らかて、 す (Fig. 3 ー② ) 。同様にパターンをふたつず らしたとしても , やはり文字 d のところて、不 一致になります (Fig. 3 ー③ ) 。結局 , パター ンを一気に三つずらしてしまえばよいこと がわかります (Fig. 3 ー④ ) 。 結論としては , パターンに現れない文字 の場合にはパターンを m 文字ずらせばよい とになります。 このように BM 法て、は , 文字を 1 回比較す るだけて、パターンを最大 m 文字ずらすことが て、きます。したがって , うま - くいけば 0 ( n / m ) 程度の計算量て文字列の探索を行うこと が可能て、す。このように種明かしをされて みれば , ごく当然の発想のように思えます。 むしろ , こんな当たり前のことが 1977 年に なるまて、知られていなかったことのほうが よほど不思議なくらいてす。人生というの は応々にして , このようなものなのて、しょ BM 法の実際 さて , BM 法の原理は今説明したとおりな のて、すが , プログラムを作成する前に , 細 かい点を検討しておきましよう。 Fig. 3 の例 て、は , 不一致になった文字がパターンに含 まれていなかっのて、 , そのままパターン をその長さ m だけずらすことがて、きました。 しかし , 不一致になった文字が , パターン に含まれる文字だった場合にはどうすれば よいのて、しようか ? たとえば Fig. 4 のよう にテキスト abaabcd の先頭にパターン abc を 重ね合わせることを考えましよう。 こて、 は , パターンの 3 文字目の c とテキストの 3 文 字目の a が一致しません (Fig. 4 ー① ) 。 パターンをひとつずらしたとすると (Fig. 4 ー② ) , テキストの 3 文字目の a とパターンの 2 文字目の b は一致しないことは明らかて す。パターンをふたつずらしたとすると , 今度はパターンの 1 文字目とテキストの 3 文 字目がともに a なのて , OK てす。そこて結 局 , パターンをふたつずらせばよい なります。 不一致になった文字がパターンの中に出 現する場合には , その文字がパターンの後 ろから数えて x 文字目 ( 最後の文字を 0 文字目 アルゴリズムとデータ構造入門 73

0 プログラミング研究 特集 List A PC79801 版 ESC / P プリンタドライバのコンバイル 詳細はリストを参照していただくとして , ポイントだけを簡単に説明します。 テパイスへッダ (sdevhead: List 2 ) デバイスへッダを List 2 に示します。 COM モデルて、は CS = DS て、あるため , ストラテジ ルーチンと割り込みルーチンをオフセット アドレスだけて、表すことがて、きます。 Turbo C / C 十十て、は , この部分て、コンパイラが Warning を出しますが , 気にしないて、くだ 0 MS-C て、も Turbo C と同じ記述てよいはず なのて、すが , コンパイルエラーとなるため , ストラテジルーチンと割り込みルーチンの 工ントリーアドレスを main 関数て、設定する ようにしました ( タイニィモデルて、コンパイ ルしているのだから , Turbo C と同様に Warning て、よいと思うのて、すが 。 MS- C のタイニィモデルはスモールモデルと同じ ような扱いのようて、す ) 。 このため , TurboC / C 十十て、はデバイス ヘッダ ( DATA セグメント ) をなんとかし て , 先頭に持ってくるようにリンクすれば CONFIG. SYS に指定可能て、すが , MS-C< は CONFIG. SYS に登録するデバイスドライ バを記述しようとするならば , 別のアプロ ーチを取る必要があります。 属性はキャラクタデバイスと IOCTL ビッ トをセットしています。 / ストラテジルーチン (tar strategy, strategy : List3) ストラテジルーチンは far リターンする必 要があるため , far 関数て記述します。 Turbo C / C 十十てはストラテジルーチンの本体を呼 び出していますが , MS-C< はインラインア センプリ言語を使用しています。 TurboC/C 十十てはストラテジルーチン 特集 TSR プログラミング研究 51 / * コマンド 工ラ cmderr() : disable(); SS ー引 d ss : oldsp; enable() : asm pop es asm POP ds asm POP bp asm pop d i a S m PO p S ー asm POP dx a S m PO p C X asm pop bx asm pop ax 88 : 89 : 90 : 92 : 93 : 94 : 95 : 96 : 98 : 99 : 100 : 10 1 : 10 2 : void done() 10 3 : 104 : 10 5 : preqhead->status ニ 0X0100 : / * DONE ビットのセット 106 : } 107 : 108 : void cmderr() / * コマンドエラ 109 : 1 10 : preqhead->status = 0X8103 ; 1 1 1 : / * 工ラービット , DONE ビットセット無効なコマンド 1 12 : } 1 13 : 114 : unsigned char bss end; 1 15 : 116 : v 0 i d i n i t ( ) 1 18 : preqhead->unitnum 1 19 : preqhead->ptrans 120 : preqhead->status ニ 0X0100 : 121 / * 初期化処理 / * ユニット数 = 1 / * フリーメモリ開始アドレス / * DONE ビットのセット ニ &bss end; テパイスへッダ タ タ ンタ ンタ ダタインタイン ツンポインポイ へ・イのポ名イのポ スポタのルボタの イすンタイすンタ バ指インア指イン デをポイフをポイ スダリポスダ リポ ノヘントパ へ デスエンデス ( エン タイジェタイジェ バテみ クバテみク ラデラ込ラデラ込 ヤの性トりヤの性トり キ次属ス割キ次属ス割 cd cd , 十し E Q) O , ↑ー CZ O - 00 ・ー・ 0- ・ 1 0 0 0 , しーし Z ・ー・ー t.O C CO O ーしーし 本し + し 0 0 > tn CO 一 1 人ワ 3n0 -4 ・戸 0 《 0 っー》 011 っ乙っ 4 ・′ 0 ^ りー 8 1 ・↓ 11 1 よ 11 、ーよ、ー 4 , ー・、ーよ , ー / * キャラクタデパイスファイル名 lSt ストラテジルーチン 1 : # i fdef _TURBOC_ 引 , ds, es, dx, cx, bx ) 2 : void interrupt strategy( bp, di, cx, bx; / * ストラテジェントリ * / 3 : unsigned bp, di, si, = MK_FP( es, bx ) : 5 : preqhead 7 : 8 : VOid far far-strategy() strategy() : 10 : 12 : #else 13 : void far far-strategy() _asm mov word ptr cs:preqhead. bx asm mQV word ptr cs:preqhead 十 2. es 7 * ストラテジルーチンを呼び出すときに DOS が CS = DS に 設定しているため CS: は不要です * / 20 : #endif / * ストラテジェントリ * / / * ストラテジェントリ * / / * ストラテジェントリ * /

ライフホ - ト lnformation from Compiler Makers 田 ov bp, offset DGROUP :-rdata Lattice C Q ー f オプションを使って 8087 命 令をインライン展開していますが , 8087 を搭載していないマシンで使 用するとハングアップしてしまい ます。これを避ける方法はありま せんか ? A LatticeC て、はスタートアップ ルーチンの中て、 , 80X87 の有無をチ ェックして外部変数 NDP に格納 しています。 80X87 があれば NDP 1 となり , 80X87 がなければ NDP = 0 となります。例として , プログラムの冒頭て、 List 1 のように し , 80X87 がなければ実行を中止し てください。 Q DOS 工クステンダ「 DOS / 16M 」 を使用していますが , 引 OS ルーチ ンを使用する場合は , どうすれば よいでしようか ? A DOS / 16M 上てのプログラム は , プロテクトモード状態て実行 するのて , リアルモード用に書か れた BIOS ルーチンを使う場合に は , ちょっとした工夫が必要てす。 この工夫は BIOS のパラメータ に , ポインタが含まれているかど うかて変わります。なお , DOS の ファンクションコールならば , Table 1 にあげたもの以外は自動 的にシミュレートしますから , プ ログラムを手直しする必要はあり ません。 印 OS のパラメータにポインタが含 まれていない場合 PC ー 9801 のディスク BIOS のシー クファンクションのように , BIOS を呼び出すときのレジスタ設定が 値のみの場合には , リアルモード プログラムと同じように扱えます。 DOS / 16M て、は割り込みが発生す ると , プロテクトモードからリア ルモードに切り換えることをデフ オルトとしているからてす。 List 2 のプログラムは , リアルモードの プログラムても DOS / 16M のプログ ラムて、も動作可能てす。 引 OS の / ヾラメータにポインタが含 まれている場合 PC ー 9801 のディスク BIOS のデー タの読み出しファンクションのよ うに , BIOS を呼び出すときのレジ スタ設定にポインタ ( アドレス ) が 含まれている場合には , そのポイ ンタをリアルモードのポインタに 変換する必要があります。 プロテクトモードては , アドレ スはすべて論理アドレスとなって おり , セグメントアドレスはディ スクリプタテープルへのインデッ クスとなっています。この論理ア ドレスをそのままリアルモードて 動作する BIOS に渡すと , BIOS は プログラムの意図とはまったく異 なるアドレスに書き込みます。 また BIOS がアクセスてきるアド レスは , IM バイト以下のアドレス て、あるため , BIOS に渡すアドレス のエリアは IM バイト以下のメモリ に確保しなければなりません。ま とめると以下のようになります。 ① IM バイト以下のメモリを確保 する ②①て確保したメモリのアドレス をリアルモードのアドレスに変 換する ③②のアドレスをレジスタに設定 して BIOS を呼び出す これを簡単に実現するためのプ TabIe 1 手直しが必要な DOS ファンクションコール ファンクションサプファンクション 4Bh 26h 44h 65h 01 H 以上 12 / 13 Load overlay など Create PSP gene 「 ic IOCTL functions Get Extended Country lnformation の monocase routine FCB を使うレ 0 ファンクションは , DTA の大きさとしてテフォルトの 128 バイトのみのサポート List 1 extern unsigned char -NDP; mai ・ n() if( ! -NDP ) { printf( ”韓* 数値演算プロセッサ 80X87 がありません。 yn"); List 2 exit(l): 凱 OV 第 OV 第 OV int ah, 10h al,90h c し 4 1 bh シークファンクション : デバイス種別ュニット番号 (DA/UA) : シリンダ番号 (C) : ディスク田 OS の呼び出し List 3 mov ah, MU し TRK + DB し DENS + REQSEEK + READFUNC ends _DATA -rdata db DTL dup(?) : データバッファ rdata public _DATA segnnet word public ・ DATA DGROUP group DATÅ : ディスク田 OS 呼び出し データバッフアのセグメントアドレス データバッフアのオフセットアドレス : セクター長 (N) : セクター番号 (R) : ヘッド番号 (H) : シリンダ番号 (C) : データ長 : デパイス種別ユニット番号 (DA/UA) データ読み出しファンクション int lbh 田 ov es. DGROUP 第 ov ch, SEC し EN 田 ov dl, SBCNUH 田 ov dh, HEDNUM mov cl, CY し NUM 田 ov bx, DTL nov al. DAUAO ロテクトモード変換ユーティリテ ィ MAKEPM に -TD オプションを 指定すると ,DGROUP がトランス ペアレントな状態になります。ト ランスペアレントとは , 論理アド レスと , それに対応する物理アド レスが同じ値てあるアドレスのこ とてす。したがって , アドレスを 渡す BIOS を呼び出すプログラムの 場合 , MAKEPM の -TD オプショ ンを指定してください。これて List 3 のようなプログラムも実行てきま す。 lnformation from Compiler Makers 161

プログラミング添削 Li st 1 あります。それは何て、しようか ? みなさ んも記事を読み進める前に付録ディスクに 収録されている川原さんのプログラムを読 んて、考えてみてください ・関数の設計 関数の入出力設計 さて List 1 に示している KeyCodeCheck 関 数が事実上のメインとなる部分てす。 まずこの関数は基本的に入出力がまった くないことに気づきます。確かにその場て カーソルキーなどを用いて自由自在に文字 列を入力てきます。しかし関数の終了時に どこにもその文字列を格納していません。 つまり , この関数はデモンストレーション 関数と呼ぶべきものてあり , 実用関数とは いえません。 さらに実際にアプリケーションを作成す るときは , 既存の文字列を編集てきなくて はなりません。 たとえばファイル名を入力する場合を考 えてください。毎回毎回最初からキーを打 つのは大変てすね。 以上の問題点を解決するには次のような 方針を立て , 抜本的な改良が必要てす。 く方針 1 > 文字列を受け取り , それを自由に ( 1 行内 で ) 編集できるようにする。ただしヌル文字 列を受け取った場合は新規入力とする。関 数終了時には受け取った文字列に編集・入力 後の文字列を格納する。 このように関数を設計する際は入出力の 仕様をはっきりさせましよう。一見同じ動 作をするような関数ても入出力の仕様が異 なれば , その内容も変わってくるものてす。 川原さんのプログラムは動作のみを追求し ているようて、す。 0 1 人ワ】 00 -4 ・ - -0 ー 8 0 ・ー・ワ 0 っ 0 -4 - -0 ー 8 0 1 より 0 っ 0 4 ・ - -0 ー 8 0 1 0 乙っ 0 -4 - -0 ー 8 0 1 人ワレっ 0 ・ ^ 0 ー 8 0 14 っ 0 00 -4 ・ ^ 0 ー 8 0 11 っ 0 ・ 4 ・′ 0 ー 8 0 14 っ 0 っ 0 -4 ・′ 0 ワ 3 っ 0 っ 0 0 乙ワ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 00 っ 0 っ 0 4 -4 -4 -414 ・ 4 -4 ・ 4 4 -4 -0 -0 - -0 - -0 -0 - -0 -. 0 -0 -0 - -0 CD e-O C•D CD ^ 0 CD CD c-O CD 7 ・ - 々ー行ー行ー行ーーっー々ーーー 8 8 8 8 8 8 8 8 8 8 0 》 9 0 》 int cn, max, ptype, gtype, kanjiflag; unsigned int code, byte; ニ OFF; kanjiflag max while ( ( code = GetKeyCode() ) ! = CR ) { switch ( code ) { case ESC break : case RIGHT ・ if ( cn く max ) { gtype = GetChar( P し EPT + cn, PTOP, TYPEI ) : if ( cn く CMAX ー gtype ) { cn 十 = gtype; CursorPosition( P し EPT 十 cn, PTOP ) : break , case し EFT if ( cn > 0 ) { = GetChar( P し EFT + cn ー 1 , PTOP, TYPEI ) ; CursorPosition( P し EPT + cn, PTOP ) : break ; case DEL ・ if ( cn く max ) { = GetChar( P し EFT + cn, PTOP, TYPEI ) : gtype Char し Sh ift ( P し EFT + cn, PTOP, gtype, max ー cn - gtype ) : = gtype; max break ; case BS if ( cn > 0 ) { gtype = GetChar( PLEFT 十 cn - 1 , PTOP, TYPEI ) : CharLSh i ft ( P し EFT 十 cn ー gtype, PTOP, gtype, max ー gtype : = gtype : max CursorPosition( PLEFT 十 cn, PTOP ) : break : case UP case DOWN ・ case INS case HCLR case TAB break; default if ( kanjiflag = OFF ) { if ( SJISCharaType( code, 0 , TYPE2 ) ! = HI ) { byte = COde : kanj i 日 ag = ON : } 引 se i f ( max く CMAX ) { CharRShift( PLEFT 十 max ー 1 , PTOP, HA, max ー cn ) : PutChar( PLEFT + cn, PTOP, code, 0 , HI ) : if ( cn く CMAX - HA ) { CursorPosition( P し EFT 十 cn + HA, PTOP ) : cn 十十 : max 十十 : } else if ( max + 1 く CMAX ) { = SJISCharaType( byte, code, TYPEI ) : ptype PutChar( PLEFT + cn, PTOP, byte, code, ptype ) : if ( cn く CMAX ー ptype ) { CursorPosition( P し EFT 十 cn + ptype, PTOP ) : cn 十ニ ptype; max 十 = ptype; kanjiflag = OFP; } 引 se kanjiflag = OFF; break; cn ) : CharRShift( PLEFT 十 max ー 1 , PTOP, ptype, max - cn ) : 関数を設計する際は動作だけではなく 入出力を明確にすること プログラミング添削 135