break - みる会図書館


検索対象: 月刊 C MAGAZINE 1993年2月号
9件見つかりました。

1. 月刊 C MAGAZINE 1993年2月号

れ以外の関数は見えても意味がないのて、あ る。そこて、 , 外部から呼び出す関数以外を static とし , 隠蔽するためにひとつのファイ ルにまとめたのだ しかし結果としては BPlus の処理を記述 するソースファイルが 90K バイトにもなって しまい , あまりおもしろくない。さらに検 討が必要て、あるといえよう。 BPL は現在最新バージョンが 52 て、ある が , 細かい変更により不規則に更新されて いる。最新のソースプログラムは NIFTY- Serve のプログラマーズフォーラム (FPRO G) て、公開されているのて、 , あまりおもしろ くないプログラムて、あるが , 参照していた だければ幸いて、ある ( 編集部注 : 1992 年 12 月 12 日現在のものを付録ディスクに収録した ) 。 BPIus のプロトコルの仕様概略はすて、に 述べたのて , 以下は , ポイントとなる処理 がどのように記述されているかを中心にい くつかの処理を例に説明をする。 バ , ット処理 ( 受信 ) いうまて、もなくもっとも重要な処理がパ ケットの送受信処理て、ある。 BPL の中て、 は , wait for acknowledge という関数がパ ケット受信処理になる。 BPIus の処理の中 て、もっともややこしい処理なのだが , ドキ ュメントを参考にして , てきるだけ忠実に 書いたつもりのものが List 2 て、ある。しか し , C のプログラムとして見ると , あまり美 しい構造とはいえないようて、ある。 構造としては , while ループの中て、 , デー タを受信して , それによってバケットが完 成したり , ACK や , そのほかコントロール コードを受け取れば , 受信データに応じた 処理を行うという感じて、ある。 sts という変 数が終了条件になっている。 あまり美しくない点を指摘すると , まず , チェックサムを計算する処理のために , < c hecksum > という変数がアドレス渡しとし 62 C MAGAZINE て使われていること。 1993 2 という変数を外に見せたくないために こは , < checksum > List 3 : 5 : 6 : 9 : 10 : 13 : 14 : 18 : 19 : 20 : 21 : 22 : 23 : 24 : 25 : 26 : 28 : 29 : 30 : 32 : 33 : 35 : 36 : 37 : 38 : 39 : 40 : 43 : 44 : 45 : 46 : 48 : 49 : 50 : 52 : 53 : 54 : 55 : 56 : 58 : 59 : 60 : 62 : 63 : 64 : 66 : 68 : 69 : 76 : * packet を受け取った場合は、 1 を戻す。内容は current-packeto * ack が得られたら、 0 を戻す。 2 : / * ACK 待ち状態の FSA wait for acknowledge 関数 sts ニ s-resend-packets() : case S_Resend-Packets: break; sts s-send-enq() ; case S_Send-ENQ. break, s ts = 0 : s_send_ack(); case S_Send_ACK : break; sts = s-send-nak ( ) : case S_Send-NAK : break; sts = s-verify-packet() , case S-Ver i fy-Packet : break , sts s-veri fy-cks(checksum) : case S-Vei fY-CKS : break. sts s-veri fy-crc(checksum) , case S-Ver i fY-CRC: break; sts = s-get-crc(&checksum) ; case S_Get_CRC: break; sts = s-get-check(&checksum) : case S_Get-Check: break; sts = s-get-data() : case S_Get_Data: break; sts = s-dle-b-seen() : case S_DLE_B_Seen. b reak ; StS = s_dle_seen(receive) : case S_DLE_Seen: break ; sts = s_get-dle(receive) : case S_Get_DLE: svitch (acknovledge-status) { vhile (sts > = の { after-enq = 0 : int sts UWORD checksum; 7 : STATIC int wait_for-acknovledge(int receive) * error の場合はく 0 break; if (sts = FINISH) { sts = acknovledge-status return Sts; = S-Verify-Packet ? 1 : 0 :

2. 月刊 C MAGAZINE 1993年2月号

ったらふつうは ' \ 0 ' て、終わるバイト列にな なたはプログラムに関する試金石を手に入 り , その ' \ 0 ' もコピーすることになります れたことになります。あなたの目の前にひ が , 問題としてはそのへんをはっきりさせ とっプログラムがあったとします。それが , こまて、書いてきて , 私は今月の ておいたほうがよいのて、す。 strcpy , strncp よいプログラムかどうかは , そのプログラ さて , テーマ , すなわち本連載の全体にわたって ムの動作が「はっきりと」書かれているかど y,memcpy の違いに相当します。 コヒ。ー先の領域は誰が確保するか。 strcp 通用する共通のテーマが発見て、きたように うかて、判断て、きることになるからて、す。そ y て、はコヒ。ーする先の領域は , 関数を呼び出 思います。それは , のプログラムの書き方の中にあいまいな部 す側のほうが前もって確保し , その領域の 「あいまいなものをはっきりさせよう」 分があったらそこはよくない部分て、す ( きっ 先頭のアドレスを strcpy に渡します (List 1 ということて、す。 とそこにはバグがいるて、しよう ) 。 て、いえば変数 dst) 。けれども違うやり方だっ やまとことばなら「はっきりさせる」 , 漢 例題をあわてて読んて、 , あいまいな部分 てあります。たとえば関数内部の static な領 語なら「明確化」 , これが本連載の共通テー をはっきりさせないままプログラムを作り , 域にコヒ。ーし , そのアドレスを返すのて、も マて、あったといえそうて、す。今月の初めに 「て、きたて、きた」と喜んて、いるのはよろしく よいときがあるし , 関数が自分て、 malloc を 私はこの 1 年間の連載の内容を振り返りまし ないのて、す。 呼び出してその領域にコピーし , そのアド ちょっと能書きが長すぎたようなのて、 , た。いま読み返してみると , あちこちに「は っきり」というキーワードが登場しているの レスを返してもよいて、しよう。そこが例題 プログラムの具体例て、説明しましよう。「あ に気がつきました。プログラミングという の文章て、は不明になっています。もしも関 いまいなものをはっきりさせる」とはどうい 数が自分て、 mall 。 c を呼び出す場合は , もし 作業て、は , あいまいなものをはっきりさせ うことかをはっきりさせてみましよう。 メモリが足りなくなったときの処理につい ることが本質的な意味を持っているようて、 「は ? きりさせる」ニその 1 す。ふむふむ。 てもはっきりさせておかなくてはならない て、しよう。 混乱している考えを整理する。ごちゃま ・・・などなど , 詳しくやっていたらきり ぜになっているものをきれいに分ける。共 具体的なプログラム例を通して , 「はっき がないのて、このへんて、やめておきましよう。 通のものをひとつに集める。ふさわしい関 りさせる」とはどのようなことかを見てみま ともかく , 例題の文章はこれだけの情報が 数名を考える。リストアップする。状態分 しよう。 List 2 をご覧ください。これはプロ 不足していたのて、す。情報が不足している けする。図を書く。仕様書を書く。プログ グラムの一部分て、す。どのへんがはっきり と , どうしてもあいまいな表現になってし ラムを書く。 していないて、しようか。 これはすべて , 「あいまい まいます。長さの限界は , 文字列の意味は , なものをはっきりさせる」ということにほか これは簡単て、す。 switch 文の default があ 領域の確保場所は , 工ラー処理は , なりません。なるほど。 りません。変数 c の値が ' C ' のときは関数 pr プログラミングて、は「はっきりさせる」こ ったいどうすればよいのかをはっきりさせ int cur dir ( ) が呼ばれます。 ' D ' のときは ないと , 例題を考えてはいけません。 とがたいせって、あると納得て、きたとき , あ 関数 print_dir( ) が呼ばれます。 ' Q' のとき は関数 quit program( ) が呼ばれます。それ はっきりさせよう一その 1 List 2 を修正する て、は , それ以外のときは ? それ以外の場 合についてはプログラムには何も書かれて いません。 こが「はっきりしていない」部 分て、す。 もちろん List 2 はプログラムとして動作し ないわけて、はありません。構文としては正 しい switch 文て、す。 switch 文に default は書 いても書かなくてもいいのて、すから , コン パイラは何も文句をいわずこの部分を処理 してくれるて、しよう。しかし , プログラム 中にはっきりと「それ以外の場合」の処理を 書いてないと , あらぬ誤解が生じます。 のプログラムを読む人は「 default はワザと書 「はきりさせる」ということ List List switch (c) { print cur—dir() : break ; print—dir(); break : qu i t—program ( ) ; break ; default: / * 処理は不要 * / break; switch (c) { print—cur_dir(); break ; print—dir(); break ; qu i t—program ( ) : break ; 118 C MAGAZINE 1993 2

3. 月刊 C MAGAZINE 1993年2月号

ープロクラミンク熨場 Dr. 望洋の て、ある。 なお実際には , 未使用領域を管理するた めの情報などもあり , もっと複雑な管理が なされている。 さて , List 1 の実現は , く欠点 1 > ひとつひとつの要素のためのメモリを確 保するときオーパヘッドか大きい という欠点があるようだ。 とくに , 要素が 小さく , 要素数が多い場合は , あまり利用 しないほうがよいだろう。場合によっては , 動的に要素を確保するたびに , 内部的には , それより大きいメモリが消費されるかもし れないのだから。 ・線形リストの特徴 最初にも述べたように , 線形リストは List 1 node *ptr ー * top : vhile (ptr->next ! = NUL い ptr ptr->next; = AllocN0de() : ptr->next SetNode(ptr->next, no, name, NUL い ; ー先頭の要素を削除ー VOid DeleteNode(node **top) if (*top ! = NULL) { (*top)->next; node *ptr free()t 叩 ): *top = ptr; ー全ての要素を削除 void Clear い st(node **top) vhile (*top ! ニ NULL) DeleteN0de(top) : 一線形リストを初期化する一 VOid InitList(node **top) - 線形リストの使用を終了する一 VOid Term い st(node **t 叩 ) ClearList(top); / * 省略 * / ーメニュー選択 menu SelectMenu(void) int ch ; 【利点 1 】 要素の挿入・削除などの操作を , 要素の 物理的な移動を伴うことなく実現できる *top ニ NULL; というメリットがある。また , 実行結果か らもわかるように 要素の追加や削除は自由自在て、ある。した がって , 【利点 2 】 未知のテータ数に対しても , 正しく動作 させることができる。すなわち , コンパ イル時 ( プログラム開発時 ) はもちろん , 処理開始時にすら , データ数が既知であ る必要がない ( メモリの許すかぎり ) do { pu t s ( " ( 1 ) 先頭に要素を挿入 ( 2 ) 末尾に要素を追加 " ) : puts("(3) 先頭の要素を削除 ( 4 ) 全ての要素を表示 " ) ; put s ( " ( 5 ) 全ての要素を削除 ( 0 ) 処理終了 " ) : scanf( ” %d ” } vhile ()h く Term Ⅱ ch > Clear); return ((menu) (ch)) : int main(void) ーメイン一 int node InitList(&Iist); menu; * ⅱ s t ; というメリットがある。これは , C 言語の単 純な配列て、は実現て、きないことて、ある。 しかし , Fig. 1 からもわかるように , そも そも線形リストは , 「次のデータを指すポイ ンタ」をたぐっていくことしかて、きないた め , 大石さんも指摘するように く欠点 2 > ランダムな要素のアクセスが不得手であ る node x; swi tch (menu ニ SelectMenu()) { = Read(" 挿入” ): case lnsert: X InsertNode(&list, x. no, x. name) : : Read ( " 追加 " ) : case Append : x AppendNode(&list, x. no, x. name) : case DeIete: DeleteNode(&list) : PrintList(&list); case Print ・ CIearList(&Iist); case Clear } vhile (menu ! : Term); TermList(&Iist); return ( 0 ) : break , break, break, break , break, という大きな欠点がある。 D 「 . 望洋のプログラミング道場 123

4. 月刊 C MAGAZINE 1993年2月号

List 2 リストの例を List 2 に示す。 このプログラムは , List 1 とほば 1 対 1 に対 応させているのて、 , リストをよく見比べれ ば , 大枠は理解て、きるだろう。そこて、 , 削 除レコードの管理についてのみ解説するこ ・削除レコードの管理 線形リストを配列て、実現しているわけだ , ここて、次の間題を考えよう。 【問題】要素を削除すると , 配列に空 きがて、きてしまうのて、はないか ? Fig. 8 を見ていただきたい。 ( a ) の状態て、 は , 要素が四つの状態て、ある。 こて、要素 を追加した場合 , 配列の 5 番目の位置に , そ の要素を追加することになる。ただし , 線 形リストの要素は , 配列の添え字の順に並 んて、いるわけて、はないのて、 , ここて、は「線形 リストの末尾」に要素を追加したとはかぎら ことに注意していただきたい。あくま て、も , 物理的な末尾の位置に要素を追加し たのて、ある。 こて、 , 若干の用語の定義をしよう。線 形リスト中の各データのことを要素という。 もちろん , 要素の物理的な位置関係と , 線 形リスト中の位置関係は異なる。そこて , 配列上ての要素の位置 ~ すなわち添え字の ことをインデックスと呼ぶ ( インデックスは 0 から始まることに注意 ! ! ) 。また , 配列とい う観点から見た各データをレコードと呼ぶ 先の例て、は , 要素を追加した結果 , イン デックス = 4 の位置にレコードが格納された ことになる。 さて , ここて 2 レコードのデータを削除し よう (c) 。削除されたレコードは , 無効なレ ドが削除されているのて、 , delete は 2 という ポインタなのて、ある。また , 各要素は , 削 コードとなるが , それ以降の要素の追加な 値を持つ。 除リストの次の要素を指すための Dnext メン どに際しては , 有効に再利用しなけれはな こまて説明すれば , ピンとくる方もい ヾを持っている。 らない。そこて、導入したのが , list 型中の d らっしやるだろう。削除されたレコード群 さらに , list 型には , 現在配列中のどのレ eleted メンバて、ある。 も線形リスト構造て、管理するのて、ある。 コードまて、を利用しているかを記憶するた (a) や (b) のように , 削除されたレコード こて、は , その線形リストのことを削除リス めに , max メンノヾを用意している。 が存在しなければ , deleted は , Null すなわ トと呼ばう。 Fig. 9 の例て、説明しよう。 ( a ) の状態は , ち一 1 の値を持つ。 ( c ) の状態て、は , 2 レコー deleted は , 削除リストの先頭要素を指す max が 7 て、あり , 1 , 3 , 5 のレコードが削除 if (T 叩 = Nu Ⅱ ) InsertN0de(Iist, no, name); else { lndex ptr ニ TOP, while (Next(ptr) ! : Null) ptr = Next(ptr); Next(ptr) = GetIndex(list); SetN0de(&list->n[Next(ptr)], no, name, NuII); ー先頭の要素を削除ー void DeleteNode(list *list) i f (T 叩 ! ニ Nu Ⅱ ) { lndex ptr Second; DeIeteIndex(list, T 叩 ): T 叩ニ ptr; 力 ー全ての要素を削除 VO i d ロ earL i s t ( ⅱ s t * ⅱ s t ) ⅶⅱ e ( T 叩 ! : Nu 日 ) DeIeteN0de(list) ; 一線形リストを初期化する一 VO i d I n i tL i s t ( 1 i s t * ⅱ s t, i n t s i ze) calloc(size, sizeof(node)); list—>max list->deleted ニ Null; list->n list->top / * 省略 * / ーメイン一 int main(void) i n t 1 i s t menu ; ⅱ s t ; i t し i s t ( & ⅱ s t, 10 の : do { node x; svi tch (menu : SelectMenu()) { ニ Read(" 挿入 "): case lnsert: X InsertN0de(&Iist, x. no, x. name) : case Append : X = Read( ”追加 "): AppendN0de(&list, x. no, x. name) ; case DeIete: DeleteNode(&list) : case Print ・ PrintList(&list); case Clear ・ CIearList(&list); } vhile (menu ! ニ Term) ; TermList(&list); return ( 0 ) : break, break, break, break, break : 126 C MAGAZINE 1993 2

5. 月刊 C MAGAZINE 1993年2月号

C プロラマのための List 1 バイプ起動ユーティリティ (pipemain. c: 抜粋 ) List / * CTR い C 割込無視 int fi gnore-ctrlc / * ハ。イフ。処理ハ・ツフアオ - ハ・フロー int fbufover / * メモリ種別 int memtype = MEMMAIN; / * 入力ハ。イフ。処理ハ・ツフアへのホ。インタ * / char far *prdmem, / * 出力ハ。イフ。処理ハ・ツフアへのホ。インタ * / char far *pvrmem, / * 入力ハ。イフ。処理サイス・ハ・ツフアへのホ。インタ * / unsigned long *prdsiz; / * 出力ハ。イフ。処理サイス・ハ・ツフアへのホ。インタ * / unsigned long *pvrsiz; / * 入力ハ。イフ。処理ハ・ツファ位置 unsigned long lrdpos; / * 出力ハ。イフ。処理ハ・ツファ位置 unsi gned long lvrpos; *p i pemen[ 2 ] : / * ハ。イフ。処理月・ツフアへのホ。インタ ( 固定 ) * / void far unsigned long lpipesiz[ 2 ] / * ハ。イフ。処理ハ・ツフアサイス・ / * ハ。イフ。処理ハ・ツフアサイス・ unsigned long lpipemax = 円 PESI ZE , void dos3f( struct sirstk far * ). d0S40 ( struct sirstk far * ) : void interrupt $ifndef __TURBOC_ far $endif ne 町 21 ( struct sirstk sirarg ) svi tch ( s i rarg. ax > > 8 ) { case 0X25 if ( fignore_ctrlc & & ( sirarg. ax & 0xff ) break, -chain-intr( 引 d -21 ) : break, case 0X3f i f ( s i rarg. bx ! : FD 燼 Ⅱ prdmem - : NULL ) -chain-intr( 引 d -21 ) ; d0S3f( &sirarg ) ; break, case 0X40 if ( sirarg. bx ! : FDOUT Ⅱ pvrmem ニ NULL ) -chain-intr( 引 d ー 21 ) : d0S40 ( &sirarg ) : break, default chain-intr( 引 d ー 21 ) : break; 十 ーー 0 0 0 0 0 V) X X 0 = FALSE; : FALSE; / * チェーンするアト・レス #end i f int main( int argc, char *argv[] ) static char iret[] ニ { 0xcf } : char cmdnam[ PATHLEN ] ; char CO 引 ine[ 256 ] ; int indexrd indexvr int count, ret; if ( --argc Ⅱ **argv svi tch ( argv [ 0 ] [ 1 ] ) { case case m / * チェーンするアト・レスをスタックに積む * / ヨ ライトハント・ル 入力 ds:dx : ハ・ツフアのアト・レス cx = 書込みハ・仆数 bx ニファイル・ハント・ル 出力 ax : 書き込んだハ・仆数 void d0S40 ( struct sirstk far *pirarg ) if ( *pvrsiz 十 pirarg->cx 〉 lpipemax ) { ( unsigned ) ( lpipemax - *pvrs i z ) ; pirarg- 〉 ax / * ハ。イフ。処理ハ・ツフアオーハ・加 - fbufover = TRUE; } else / * 書き込んだハ・仆数 pirarg->ax ニ pirarg- 〉 memcpy( MK-FP( FP-SEG( P 響 ) + ( unsigned ) ( lvrpos 〉 > 4 ). FP_OFF( p 田 e 田 ) + ( ( unsigned )lvrpos & 0x0f ) ). MK_FP( pi rarg->ds, pirarg->dx ) , / * ハ。イフ。処理ハ・ツファ書込み pirarg—>ax ) ; / * 出力ハ。イフ。処理サイス・更新 *pvrsiz 十 = pirarg—>ax; / * 出力ハ。イフ。処理ハ・ツファ位置史新 lvrpos 十 : pirarg—>ax. / * キャリ - リセット pirarg- 〉 flags & : Oxfffe• / * retf * / / * IRET / * 起動コマント・名 / * コマンド・ライン / * 配列添字 / * 引数の取得 / * ハ。イフ。処理ハ・ツファ : メイン・メモリ = strtoul( &argv[ 0 ] [ 2 ] , NUL し 10 ) ; / * ハ。イフ。処理ハ・ツフア・サイス・ ( ( lpipemax + 15 ) / 0X10 ) * 0X10 : / * ハ。ラク・ラフ・サイス・に切り上げ ニ MEMMAIN; / * メモリ種別 : メイン・メモリ / * 使用法表示 / * CTR い C 割込無視 ? : T23 ) / * 割込へ・クタ 23h の設定を無視する / * 元の INT 21h ハント・ラを呼び出す / * 標準入力以外 ? / * 入力ハ。イフ。処理なし ? / * 元のは T 21h れント・ラを呼び出す / * リードハンドル lpipemax lpipemax memtype break, default usage() ; break, / * 標準出力以外 ? / * 出力れ。イフ。処理なし ? / * 元の燼 T 21h ハント・ラを呼び出す / * ライトハンドル —argc : 十十 argv; / * 元の INT 21h ハント・ラを呼び出す if ( argc usage() : return( 1 ) : / * 使用法表示 リードハンドル 入力 ds:dx ニハ・ツフアのアト・レス cx : 読込みハ・イト数 bx ニファイル吶ンドル 出力 ax : 読み込んだハ・イト数 VOid dos3f( struct sirstk far *pirarg ) ( lrdPOS 十 pirarg- 〉 CX く = *prdsi Z ) ? pirarg->cx pi rarg->ax / * 読み込んだハ・イト数 memcpy( MK-FP( pirarg->ds, pirarg->dx ). MK_FP( FP_SEG( prdmem ) + ( unsigned ) ( lrdpos > 〉 4 ) , FP_OFF( prdmem ) + ( ( unsigned )lrdpos & 0x0f ) ) , pirarg->ax ) : / * ハ。イフ。処理ハ・ツファ読込み / * 入力ハ。イフ。処理ハ・ツファ読込み位置更新 * / lrdpos 十 : pirarg->ax . pirarg->flags & : Oxfffe; / * キャリーリセット ワ 1 . DOS 3. x 以降で動作させてください . \n ” ) : if ( memtype : MEMMAIN ) { / * メモリ種別 : メイン・メモリ ? i f ( ( P i pemem [ 0 ] : ha Ⅱ OC ( ゆ i pemax, 1 ) ) : NULL Ⅱ ( pipemem[ 1 ] ー halloc( lpipemax. ー ) ) : NULL ) { puts_err( "pipenain ・メモリが足りません . \ 心 ) : return( 1 ) : -dos-setvect( Ⅷ T23 , ( void ( interrupt far * ) ( ) ) iret ) ; / * CTRL+C 割込無視 引 d ー 21 ニ _dos_getvect( T21 ) : / * 割込へ・クタ取得 -dos-setvect( T21 , ne 響 -21 ) : / * 割込へ・クタ設定 for ( cmdnam[ 0 ] --argc, 十十 argv ) { count if ( !strcmp( *argv, pipech ) Ⅱ argc pipemem[ indexvr ] : ニ 0 ? NULL ・ pvrmem argc / * 出力ハ。イフ。処理ハ・ツフアへのホ。インタ prdmem : count : 0 ? NULL pipemen[ indexrd ] , / * 入力ハ。イフ。処理ハ・ツフアへのネ。インタ &lpipesiz[ indexvr ] : / * 出力ハ。イフ。処理サイス・・ハ・ツフアへのホ。インタ : & ゆ i pes i z [ i ndexrd ] , / * 入力ハ。イフ。処理サイス・・ハ・ツフアへのホ。インタ ー p i pes i Z [ i ndexwr ] / * ハ。イフ。処理ハ・ツフア・サイス・リセット lrdpos ニ 0 し / * 入力れ。イフ。処理ハ・ツファ位置リセット * / lvrpos / * 出力ハ。イフ。処理ハ・ツファ位置リセット * / ー spavnl ( P_WAIT, cmdnam, cmdnam, co 引 ine, N 乢し ) ; ret i f ( ret puts_err( ” pipemain コマント・の起動に失敗しました . \ 心 ) ; break, pvrsi Z prdsi Z i f ( argc break , 十十 count; indexrd indexvr; indexvr = indexvr; cmdnam[ 0 ] } else if ( cmdnam[ 0 ] static char *pcomspec comline[ 0 ] $i fdef _TURBOC_ void _chain_intr( void ( interrupt far *inthdl ) ( ) ) / * 入力配列添字 / * 出力配列添字 / * 起動コマント・名リセット ニ NULL; / * 環境変数 COMSPEC へのホ。インタ * / / * コマンド・ライン リセット 新 MS-DOS プログラミング入門 101

6. 月刊 C MAGAZINE 1993年2月号

ログラミング List 4 ば firstC1) に登録し・・・・・などとすれば , ひ とつひとつのリストが短くなるのて、 , 検索 が高速化て、きます。 しかし , 商品名の頭 1 文字て、分類するのて、 は , リストごとの長さに差が生じやすい とがわかります。 もっとよい方法はいろいろありますが , たとえば商品名の全文字コードを合計して , それを適当な定数て、割った余りによって分 類するだけて、も , すいぶんよくなります。 つまり , の値て、分類するのて、す ( % は C 言語て、割り算 の余りを求める演算子て、したね ) 。 文字列を数値に変換する関数を一般にハ ッシュ関数といいます。 ハッシュ (hash) はハヤシライスの語源と もいわれ , 切り刻んて、ごたまぜにすること て、す。 上の式はもっとも簡単なハッシュ関数の ひとって、す。 上の割り算の定数は 2 の倍数て、ない適当な 数とします。たとえば 63 とすると , リスト の先頭のポインタは first [0] , first [ 1 ] , first [ 62 ] の 63 個が必要て、す。このようなハッシュ関 数とともに使う配列をハッシュ表 (hash ta ble) ということがあります。そこて、 , List 4 て、は first [ ] の代わりに hashtab [ ] とい う名前にしました。 このようなたくさんの改良を加えた List 4 をご賞味ください return (int)x; / * long を i nt にして返す * / / * ハッシュ関数 * / 29 : 30 . } 32 : unsigned hash(char *s) 33 : { 34 : unsigned i 35 : while ()s ! ニ 36 : 37 : i 十ニ * S 十十 ; 38 : return i % HASHSIZE; 39 : } 40 : void touroku(void) 42 : unsigned i; 43 : struct srec *p; char sname[128]; 44 . 45 : 46 : 48 : 49 : 50 : 52 : 53 : 54 : 55 : 56 : 57 : 58 : 59 : 62 : } 63 : 64 : struct srec *search(struct srec *p, char *S) while ()p ! = NULL) & & (strcmp(p->name, 67 : p->next; 68 : return p; 70 : 71 : void kensaku(void) 72 : { 73 : unsigned i; 74 : struct srec *srecp; char snameC128]; 75 : 76 : printf( ”品名 ? " ) : 77 : if (scanf("%127s%*CA%n] ” exit(EXIT_FAILURE); hash(sname) : 80 : = search(hashtab[i], sname) ; srecp if (srecp ! = NULL) 82 : printf("%s は %d 円です \ n " , sname, 83 : srecp->price) ; 84 : printf("%s は登録されていません \ n ” 85 : sname) ; 86 : } int main() 88 . 90 . 92 : 93 : 95 : 96 . / * i を HASHS I ZE で割った余り * / / * 登録 * / ニ malloc(sizeof *p); P = NULL) { printf( ”メモリ不足 %n"); printf(" 品名 ? " ) ; if (scanf("%127s%*CA%n]" sname) ! = exit(EXIT_FAILURE); = malloc(strlen(sname) + 1 ) ; p->name if ()- 〉 name ニ NULL) { printf(" メモリ不足 %n"); free(p) : strcpy(p->name, sname) : = getint(" 値段 ? " ) ; p->price hash(p->name) ; ニ hashtab[i]; p->next hashtab[i] return; return; / * 文字列をコピー * / / * 検索 * / sname) ! ニ e ー se 情報処理試験 C 言語対策講座 て、 , 昨秋行われた第 2 種情報処理技術者試 験の史上初の C 言語の出題のうち , 前回解説 しなかった問 18 て、すが・・・ 問題を見ていただければわかるように 今回解説した List 4 が解答になってしまいま した。復習のため , List 4 を見ないて、解いて ください ⅶⅱ e ( I) { switch (getint("(l) 登録 ( 2 ) 検索 case 1 : touroku(); break; kensaku() : case 2 : break; case 3 : return EXIT_SUCCESS; 98 C MAGAZINE 1993 2

7. 月刊 C MAGAZINE 1993年2月号

C プログラミング Li st 3 55 : i nt 56 : 58 : 59 : 60 : 62 : 63 : 65 : 66 : 68 : 69 : 70 : 71 : 75 : 77 : 80 : 81 : 82 : 83 : 84 . 85 : 86 . d P u t c ( ' \ b ' ) ; Li st S ー gn len *value i n t C, ー en, S i gn : / * long の値 val ue を入力 * / getlong(char specialchars[], long *value) i f 0 en = i f ( i s d i g i t (c ) ) { dputc(c); len 十十 : *value } e lse i f (c dputc(c) : len 十十 : S ー g n S ー gn } else if (strchr(specialchars, i f ( i sd i g i t ( c ) ) { } e lse { } se dpu tc ( ' ' ) : break : dputc(c); *value 10 * *value + (c len 十十 : dputc(c) : if (*value くニ (LONG-MAX ー } se dpu tc ( ' ' ) : } e lse dpu tc ( ' ' ) : *v a lue / = 10 ; dpu tc ( ' %b ' ) ; len- } se i f (c dputc(' return *value d pu t c ( ' ' ) ; S ー gn ; C : 簡単な商品データベースソフト ( 2 ) 1 : 2 : 3 : 4 : 5 : 8 : 9 : 14 : 15 : 16 : 20 : 22 : 23 : 24 : 25 : 26 : 28 : # i nc lude く s td i 0. h > # i ncl ude く s td ⅱ b. h 〉 #include く string. h 〉 # i ncl ude <l i m i t s. h 〉 6 : #define HASHSIZE 63 struct srec { struct srec *next; i n t pr i ce ; char *name; / * INT_MAX, INT_MIN * / / * ハッシュ表の大きさ * / / * 次のデータへのポインタ * / / * ノ、ツシュ表 / * 品名 * / / * 値段 * / / * 整数の入力 * / struct srec *hashtabCHASHSIZE] : int getint(char *prompt) ー ong X ; char inbufC128], *rest; errno prompt) : printf("%s" / * 入力を促すメッセージを出力 * / / * 工ラー番号をクリア * / if (scanf("%127s%*[A%n]" exit(EXIT_FAILURE); : strtol(inbuf, &rest, while (errno ! : 0 Ⅱ *rest ! ニ inbuf) ! ニ X / * 文字列を ng に * / Ⅱ x > INT-MAX Ⅱ x く INT_MIN); が , ANSI/ISO のライプラリ関数を使って たとえば List 4 の getint() のようにし ほば完全なエラーチェックがて、きます。 て , も , のままて、は登録件数が多いとリスト構造が さらに本質的な改良をしましよう。 List 2 ハッノング のて、す。 が 0 のところだけ p ー > price を出力すればよい strcmp()- > name, s) 名を s とすると , するのてしたね。つまり , 検索したい商品 が使えます。この戻り値が 0 なら r と s は一致 strcmp(), s) た のて、す。文字列の比較には , 前回も登場し したところだけ出力するようにすればいい れは show ( ) に少し手を加えて , 品名が一致 るような検索ルーチンもほしいて、すね。 また , 商品名を入力すると値段を出力す 入するのて、す。 確保し , その先頭番地をポインタ name に代 た文字列の長さに応じて malloc ( ) て、領域を にするわけて、す。こうしておいて , 入力し のように変えます。名前の部分をポインタ Char *name , int price , struct srec * next ・ struct srec { れには struct srec の定義を が , これを伸縮可能にしてみましよう。そ st 2 て、は商品名は 20 バイト以内としました もう少し本質的な改良をしましよう。 Li て、す。 力をエラーて、はなく 0 と解釈してしまうこと この getint( ) の問題点は十だけやーだけの入 とするリストに登録し , 商品名が B て、始まれ き , 商品名が A て始まれば first [ 0 ] を先頭 て、 , リストの先頭の要素を複数用意してお 長くなり , 検索に時間がかかります。そこ 実践 c プログラミング入門 97

8. 月刊 C MAGAZINE 1993年2月号

え方が整理されてきて , 現在主流になって いると思われるプログラミングに対する視 点とは , やや違った面があるのて、す。 、、その後整理されてきた考え方〃の中て、 , 大きなもののひとつが「木構造の一般性」て、 はないて、しようか。多くの問題を , 、、ツリー にマッピングてきる , という認識て、す。た とえば , 自然言語処理の教科書は , テキス トを木構造に分解する ~ 再構築する , とい う処理がほとんどの場合の出発点になって いるて、しよう。往時のいわゆる、、リスト〃も , 今ては木の特殊形て、ある , という認識が一 般化しています。 てすから , 式の評価という課題も , その 式が四則演算を中心とする算術式て、あれ , あるいはプログラミング言語て、書かれたソ ースリストを構成する式〃てあれ , 最近の アルゴリズムの本は「パースツリー」という 木構造て、表現把握する , という方式にほば 統一されています。ただし , 言うまてもな く , 木はあくまて、も論理的・概念的な表現 て、あり , コンビュータのメモリの上に実装 される、、木クの形状は , よく図て、示されるツ リーとはぜんぜん違います。 ( 2 十 3 ) * 8 という式を , 「パースツリー」て、 表現すると , Fig. 1 のようになります。 そこて、 , 今プログラミングを学ぶ人は , ほとんどの問題を木て、表現て、きるいフ List 疑似コード : 式の評価 Fig. 1 「パースツリー」で表現した ( 2 十 3 ) * 8 という式 2 十 3 とを , 当たり前のように受け取りつつプロ グラミングの技法を磨いていくのだと思い ますが , そうすると意外と , 実装レベルて、 の多様性を見失いかねないのて、はないて、し ようか。 逆にいうと , さまざまな基本的データ構 造の , 実装レベルて、の多様性を実現し , あ るいは理解て、きるという点が , C などの原始 的な言語のありがたさて、しよう。 こまて、書いたところて、昼食のため 多いよね。元々ソースと共に配付されてい 形態は , ソースが伴わないことが圧倒的に 日本のフリーソフトウェアの流通・配付 してしまいました。 中断したのて、 , ぜんぜん別のことを思い出 0 第 void eval( expression E ) vhile( 1 ) { tOken X = getnexttoken( svitch( type( x ) ) { x = 叩 ( pop(), POP() ) : / / オペランドをポップして演算し / / 演算子ならスタックから / / 上の例では , 2 , 3 が順次スタックへ入る / / オペランドは単純にスタックへブッシュ / / 式の最後に達した E ) : / / ' 23 + ' なら最初は x に ' 2 ' が入る case TERMINATOR: return; case OPERAND push( x ) : break, case OPERATOR push( x ) : るものて、も , 出版社などがソースを外して 「おまけディスク」なんかに入れたりする。 最近は「おまけディスク」付きの雑誌が増え ているけど , なんだか , がつがっとした文 化的に虚しい現象に思えてならない クリントン / ゴア両人の顔を見てて , 日本 の政治家はいつのまにか , 顔も行ないも士 操もすべて薄汚い , 、、おっさん顔〃の連中ば っかりになってもうたな , と思いまして , 彼らを選出した多くの日本人の精神風土が , 「消費者的たかり根性」なのて、はないか , と。 フリーソフト = ただの ( 無科の ) ソフト , と いう考え方も , まさしく 100 % 消費者根性て、 あります。 N ES ( N intendo Enterta inment System, a. k. a. ファミコン ) も , ほとんどの家庭に PC のない日本の状況て、考えると , わびしい なぜなら , せつかくのコンヒ。ュータて、あり ながら , 外部ファイルとプログラミングイ ンタフェイスがないからて、す。「外部ファイ ル」と「プログラミングインタフェイス」が提 供されれば , ゲームそのものも , そしてゲ ームの遊び方も , ものすごう奥深くおもし ろうなりまっせ ! ファミコン用の外部フ ァイル装置としては , アスキーからくター ポファイル〉という名の RAM ファイルみた いなものが発売されていますが , それはコ ンヒ。ュータの、、標準的一般的な〃外部ファイ ルて、はないて、す。 まあ , 単なる玩具だと思えば諦めもつく のかもしれませんが , 日本の子供たちが日 常いじるコンヒ。ュータが , こんな不自由な 仕様のものて、は可哀相 , と思いますね。な んかの外部ファイル , たとえば「ばくが育て たモンスター△△△のデータ」なんてのを作 って , 友だちと交換しあう , 競い合う , な んてことて、も , コンピュータの、、消費者的利 用〃から、、創造的利用クへ , 半歩ぐらい踏みだ / / 結果を次以降の演算子のためのオペランドとしてブッシュ せるのに・ 。ゲームの遊び方だって , 「自 分が作ったプログラムによって主人公たち を動かす・・・・・・自分はこれからしばらくの間 , C 言語フォーラム コントローラに手を触れない」というモード 113

9. 月刊 C MAGAZINE 1993年2月号

Li st 1 List 1 static char *msg[] " \ 033 [ 36m ハ。イフ。起動ユーティリティ ハ・ - シ・ヨン 0. 01 \ n ” "Copyright (C) 1992 N. NakashimaY033[mYnYn" " 使用法 : pipemain [ - M くれ・ツフア・サイス・ > ] c 面 1 ! cmd2 ! cmd3 ハ。イフ。処理ハ・ツファ : メイン・メモリ \ n ” register char **pmsg : nsg, vhile ( **pmsg ) puts-err( *pmsg 十十 ) : ex i t ( 1 ) ; ニ NULL ) { i f ( getcmd( cmdnam, *argv ) / * 起動コマント・が見つからない i f ( pcomspec ニ NULL : NULL ) { & & ( PCOmspec ニ getenv( "COMSPEC ” ) ) puts-err( "pipemain : 環境変数 COMSPEC が未定義です . \n" break, strcpy( cmdnam. PCONSPec ) ; / * 起動コマント・名 : COMMAND. COM * / strcpy( comline, strcat( comline, *argv ) : strcat( CO 引 ine. . %nYn ” } se strcat( comline, *argv ) : strcat( comline. Table 3 EMM ファンクション 24 Move Memory Region Move Memory Region ( メモリ領域の移動 ) AX = 5700h DS : : コピー元・コピー先の情報からなる構造体 MOVE SOURCE DEST STRUC REGION LENGTH dd SOURCE MEMORY TYPE db SOURCE HANDLE dw SOURCE 爪 L OFFSET dw SOURCE 爪 L SEG PAGE dw DEST MEMORY TYPE db DEST HANDLE dw DEST INITIAL OFFSET dw DEST 爪 L SEG PAGE dw MOVE SOURCE DEST ENDS INT 67h 返り値 AH : 終了ステータス 次の 4 種類のメモリ領域コピーを行います ・標準メモリ→標準メモリ ・標準メモリ→拡張メモリ ・拡張メモリ→標準メモリ ・拡張メモリ→拡張メモリ DS : の指す構造体は次の要素からなる ・ REGION LENGTH コピーするメモリ領域のバイト数 ・ SOURCE MEMORY TYPE コピー元領域のメモタイプ 0 : コピー元が標準メモリ 1 = コピー元が拡張メモリ ・ SOURCE HANDLE コピー元の拡張メモリ領域の八ンドル番号 コピー元が標準メモリの場合は 00h ・ SOURCE 爪 L OFFSET コピーを開始すコピー元領域内のオフセット コピー元が拡張メモリ領域の場合 0000h ~ 3FFFh コピー元が標準メモリ領域の場合 0000h ~ OFFFFh ・ SOURCE 爪 L SEG PAGE コピーを開始すコピニ元領域内のセグメント または論理ページ番号 コピー元が拡張メモリ領域の場合論理ページ番号 コピー元が標準メモリ領域の場合セグメントアドレス ・ DEST MEMORY TYPE コどー先領域のヌモリタイプ 0 : コピー先が標準メモリ 1 : コピー先が拡張メモリ ・ DEST HANDLE コピ先の拡張メモリ領域の八ンドル番号 コピー先か標準メモリの場合は 00h ・ DEST 爪 L OFFSET コどーを開始するコピー先領域内のオフセット コピー先が拡張メモリ領域の場合 0000h ~ 3FFFh コピー先が標準メモリ領域の場合 0000h ~ OFFFFh ・ DEST 爪 L SEG PAGE コピを開始するゴピー先領域内のセグメント または論理ページ番号 コピー先が拡張メモリ領域の場合論理ページ番号 コピー先が標準メモリ領域の場合セグメントアドレスか / * 割込へ・クタを元に戻す dos-setvect( INT21, 引 d ー幻 ) , / * ハ。イフ。処理ハ・ツファわハ・加ー if ( fbufover ) : ハ。イフ。処理ハ・ツフアがオ - ハ・フロ - しました . \ n " ) . puts-err( p i pema ー n return( ret ) : TURBOC_ $ifdef $def ine ATR-EXEC $else $def ine ATR_EXEC $endif 実行ファイルの検索 っ ! 1 ! っ ! っ ! っ ! っ ! っ ! っ ! っ ! ( FA_RDONLY ー FA_HIDDEN ー FA_SYSTEM ) ( _A_RDON し Y ー _A_HIDDEN ー -A-SYSTEH ) 引 数 . EXE の順に検索する PATH のリストにしたがって . COM. 検索ファイルなし 返り値 NU しし fullpath : 検索ファイルあり char *getcmd( char fullpath[], char srcfile[] ) / * 結果を返すフル・ハ。ス名 / * 検索ファイル名 / * 検索ハ。スへのホ。インタ / * コマント・名 / * 拡張子なしフラク・ char far *ppath, char cmdnam[ PATHLEN ] ; i n t fn oex t . struct find_t dta, strcpy( fullpath, srcfile ) ; if ( !_dos-findfirst( fullpath, ATR-EXEC, &dta ) ) / * 検索ファイルあり return( fullpath ) : strcpy( cmdnam, srcfile ) : ニ N 乢し / * 拡張子なしフラク・ strchr( cndnam. fnoext fullpath[ 0 ] ・ \ 0 第 / * 検索ハ。ス : getenv( "PATH" ) ; ppath if ( ppath - : NU ししⅡ !ppathC 0 ] ) / * 環境変数が見つからない return( NULL ) : char *p, int ch fullpath' vhile ( *ppath & & *ppath ! : ( unsigned char ) ( * P + + ch if ( iskanji( ch ) & & *ppath ) *ppath 十十 : * p 十十 if ( ch い * p 十十 strcpy( p, cmdnam ) . if ( !_dos-findfirst( fullpath, ATR-EXEC. &dta ) ) return( fullpath ) ; / * 検索ファイルあり / * 拡張子なしフラク・ if ( fnoext ) { char *pext ニ fullpath + strlen( fullpath ) ; strcpy( pext, if ( !_dos_findfirst( fullpath. ATR_EXEC. &dta ) ) return( fullpath ) : / * 検索ファイル . COM あり strcpy( pext, 汀 ( !_dos_findfirst( fullpath, ATR_EXEC. &dta ) ) return( fullpath ) : / * 検索ファイル . EXE あり } while ( *ppath + + ) : fullpath[ 0 ] return( NULL ) : : *ppath 十十 ) : / * 検索ファイルが見つからない 返り値 - は以外 : 実際に出力したハ・仆数 int puts-err( char *msg ) 工ラ - / * 文字列標準巧 - 出力 return( vrite( 2 , msg. strlen( msg ) ) ) ; / * 使用法表示 VOid usage( VOid ) 102 C MAGAZINE 1993 2