アルゴリズムアータ構造入門 Fig. 2 リストの表現法 head 2 struct CELL { struct CELL int } * head, 5 * next, value, / * 次のセルへのポインタ * / 連結リストによる表現 0 リストはポインタによって連結されたセルとして表現される struct CELL { struct CELL * next ; int } * head ; value ; 連結リストの性質 挿入前 Fig. 3 連結リストへの挿入 ( 1 ) の要素は 0 から始まるのて、 , n 番目の要素は a [ 2 ] に格納されています。 C 言語ては , 配列 す。たとえば , Fig. 1 て、は , 3 番目の要素は クセスてきるのて , 0 ( 1 ) の計算量になりま がて、きます。要素にはつねに一定時間てア ことて , 任意の要素を高速に参照すること しよう。まず , 配列て、は何番目と指定する 配列との比較をまじえながら考察してみま さて , ここて、連結リストの性質について , aCn ー 1 ] に対応していることに注意しましよ う。このように配列て、はデータを「ランダ ムアクセス』することが可能て、す。 これに対して , 連結リストの場合には , ポインタを順番にたどる「シーケンシャル アクセス』しかて、きません。 3 番目の要素を 参照するには , 変数 head から 3 回ポインタを たどる必要があります。リストの要素数が n 個て、あるとき , 任意の要素を参照するには 平均して晋回ポインタをたどらなければな らないのて、 , 計算量は O ( n ) になります。 のように , 連結リストては要素を自由に参 照するにはコストがかかります。ただし , 先頭の要素はつねに変数 head て指されてい るのて、 , O ( 1 ) て、参照て、きます。 また , セルは直前の要素へのポインタを もっていないのて , シーケンシャルアクセ スは前進方向のみ可能て、 , バックすること はて、きません。このように , 要素のアクセ スについては , 連結リストはかなりのハン デを背負っているといえるて、しよう。しか し実際には , 順番に要素をたどるだけても 十分なケースが多いのて、 , この点はあまり 大きな欠点とはなりません ( 後向きにもたど れる連結リストについては , 次回て、説明し ます ) 。 またこの点に関しては , つねに特定の要 素を指すようなポインタ変数を用意してお けば , 問題を回避することも可能てす。た メンバ next は次のセルへのポインタ , メン バ v 引 ue は int 型になっていて要素の値がセッ トされます。変数 head はセルへのポインタ ( つまり st 「 uct CELL * 型 ) として定義され ていて , このリストの先頭を指しています。 変数 head から順にポインタをたどって各要 素を順番にアクセスすることがてきます。 また , 変数 head が NULL のとき , リストは 空て、ある ( 要素がひとつもないリスト ) とす ることは自然な表現てしよう。 配列の場合は , fO 「 (i = 0 : i く n : i 十十 ) printf("%d*n", aCi]) ; というように fo 「文を使ってインデクスをひ とつずっ増加させながら , 各要素を順に参 照します。連結リストては , fo 「文を使って ポインタをたどりながら , 各要素に順番に アクセスてきます。 struct CELL *p : fO 「 (p=head ; p!=NULL : p=p—>next) printf("%d*n", p—>value) ; 0 ポインタ x で指されているセルの後ろに , ポインタ P で指されているセルを挿入する アルゴリズムとデータ構造入門 73
アルゴリズム・テータ構造入門 Fig. 7 リストの連結と分断 0 連結リスト a の後に連結リスト b を連結する 0 0 連結リスト a の最後のセルへのポインタ ( 上の図の x ) がわかっていれば O ( 1 ) て連結できる リストの連結 0 連結リスト a を x て指されるセルの直後で切断する リストの分断 コーディングすると , x ー > n ext ; p—>next x— > next 字は , Fig. 6 の矢印に対応 ) 。 コーディングは次のようになります ( 丸数 みて、す。 化するポインタは , 斜線部分とポインタ p の が終わった状態が Fig. 6 てす。ここて、 , 変 れたセルを指しているようにします。削除 理が完了した時点て、 , ポインタ P が , 削除さ セルを削除してみます。この際に , 削除処 5 て , ポインタ x て、指されているセルの次の 次に削除について , 見てみましよう。 Fig. 応 ) 。 となります ( 丸数字は , Fig. 4 の矢印に対 x—>next ; ・・・① x—> next p—>next; ・・・② こて、 , 挿入・削除を行う場所がどのよ うに指定されるかに注目してみましよう。 削除の場合は , 削除したいセルそのものて、 はなく , ひとつ手前のセルへのポインタが 必要となります。いい換えれば , 連結リス トては , ある勝手な要素を指定してそれを 削除することはてきません。これは , ある 意味てはかなりきつい制限て、す。また , 同 様に挿入ては , 指定した要素の後ろに挿入 することは簡単て、すが , 前に挿入すること はてきません。これらの制限は , 連結リス トを扱ううえての要注意事項て、す。 連結リストて、は , あらかじめリストの長 さを決めておく必要はありません。要素が いくらてもリス 増えれば増えたぶんだけ , トを長くて、きます。それに比べて , 配列て、 はあらかじめ長さを見積もって , 最大長に 合わせて領域を確保しておかなければなり ません。また配列て、は , 利用しない部分は ムダになるうえに , あらかじめ決めた個数 以上の要素の登録はて、きません。 先ほど , 連結リストてはポインタのぶん だけ余分にメモリが必要てある , と説明し ました。しかし , 配列のように固定長て、確 保するために生じるムダがないのて , 連結 リストのほうがメモリを有効に利用てきる こともあります。どちらが一方的に優れて いる , ということてはなく , ケースパイケ ースてどちらが有利かを判断する必要があ ります。連結リストて、のメモリ管理につい ては , 後ほど説明しましよう。 アルゴリズムとデータ構造入門 75
アルゴリズム く第 3 回〉連結リスト 近藤嘉雪 先月は , 配列を利用してリストを表現する方法を勉強 しました。今月は , もうひとつの表現法『連結リスト』 について学ぶことにしましよう。 目朝囚固 連結リズ は 4 つの要素 2 , 5 , 12 , ー 4 がこの順番て、並ん 素の数を変数 n て、管理しています。ーリストに ものて、す。配列 a にリストの要素を入れ , 要 Fig. 1 は整数のリストを配列て、表現した ばんてしよう。 を理解するには , 絵を描いてみるのがいち トのようにポインタを多用するデータ構造 ポインタをセットしておきます。連結リス 要素はありませんから , メンバ next には NULL す。また最後の要素については , 次にくる メンバ next は , 次の要素を指すポインタて、 data ; MYDATA struct CELL *next : st 「 uct CELL { 宣言します。 次のようにふたつのメンバをもつ構造体を 型のデータを並べたリストを表現するには , のポインタを付加します。たとえば , MYDATA list と呼ばれます。各要素には , 次の要素へ れている (link されている ) ことから , linked わせたものてす。ポインタによってつなが まれる各要素をポインタによってつなぎ合 連結リスト (linked list) とは , リストに含 Fig. 1 リストの表現法 配列 a a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] n=4 ( 要素の数 ) int a [ 10 ] ; / * リストを表現する配列 * / int n; / * リストの要素数 * / ( a ) 配列による表現 ひとつひとつがリストの要素を表していま Fig. 2 のようになります。ここて、は , 箱の このリストを , 連結リストて、表現すると す。この箱のことをセル (cell) とも呼びま セルの型が次のように定義 す。 こて、は , されています。 ています。 72 CMAGAZINE 19 8
連結リストへの挿入 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. 4 のようにな とえば , 待ち行列を実現するのなら , つね しよう。 Fig. 3 て、 , ポインタ x て、指されてい ります。このとき , 図中て、斜線をひいたポ に最後の要素を指しているポインタ変数を るセルの次に , ポインタ P て、指されている新 インタの値が書き換えられます。具体的に もたせればうまくいきます。 連結リストて、は , 各セルに , 次のセルへ のポインタをもたせなければなりません。 つまり , 1 セルにつき 2 ないし 4 バイト ( ポイ ンタが 16 ビット長なら 2 バイト , 32 ビット長 なら 4 バイト ) の領域がポインタのために必 要となります。 Fig. 1 ~ 2 の例のように , 扱 うデータ型のサイズが小さければこのオー バヘッドもバカになりません。しかし反対 に考えれば , ある程度大きなデータ型を管 理するのて、あれば , ポインタのために必要 となるメモリは問題にならないと考えてよ いて、しよう。 冒頭から悪い点ばかりを取り上げてしま いました。「何だ , 配列に比べてちっともい いところがないじゃないか。連結リストな んか勉強しないて、いいや」と思った方も多い と思います。ても , これから連結リストの よい点を説明するのて、 , もうちょっとだけ 辛抱してください。つき合ってみれば , な かなかいい奴だということがわかるて、しょ うから・・ 連結リストの利点といえば , まず要素の 挿入や削除が簡単に行えることが挙げられ ます。前回お話したように , 配列て、リスト を表現する場合 , 要素の挿入 , 削除はかな りの大仕事になります。 挿入のときには , 挿入する地点から後ろ にある全要素をひとつずっ後ろにずらさな ければなりません。リストの要素の数を n 個 とすると , 平均昜個の要素をずらす必要が あるのて、 , 挿入の計算量は O ( n ) になりま す。また , 削除についても同様にして平均 一個の要素を移動する必要があり , O ( n ) の 2 計算量になります。 これに対して , 連結リストて、表現した場 合は , 挿入・削除を行うのにセル自体を移 動する必要がなく , 数個のポインタを書き 換えるだけてすみます。これはつねに一定 時間て、実行て、き , 計算量は O ( 1 ) になりま す。 74 CMAGAZINE 19 8 Fig. 4 連結リストへの挿入 ( 2 ) ② ① 挿入後 0 ポインタ x で指されているセルの後ろに , ポインタ p て指されているセルを挿入する 0 斜線部分のポインタが書き換えられる Fig. 5 連結リストからの削除 ( 1 ) 削除前 0 ポインタ x で指されているセルの次のセルを削除する 削除したセルはポインタ p が指すようにする Fig. 6 連結リストからの削除 ( 2 ) 2 ① 削除後 0 ポインタ x で指されているセルののルを削除する 削除したセルはポインタ p が指すようにする 0 斜線部分のポインタが書き換えられている
アルゴリスムアータ構造入門 別扱いにしなければなりません。 この例のように , 一方が他方を追いかけ るという関係のふたつのポインタを使って リストをスキャンする , というのは連結リ 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
の 2 種類に分類て、きます。記憶クラスて、いえ ます。先ほど説明した例と同様に , ポイン 連結リストて、は , 複数のリストを連結し タ x て指されるセルの直後に新しいセルを挿 ば , extern と static が前者 , autO と register て新しいリストを作る , ひとつのリストを 入しています。「セルに値をセットする』と が後者になります ( 関数の内部て、定義した ふたつに分断する , という操作が容易に行 static 変数は , 定義されている関数の外側て いう部分て、は , 割り当てたばかりのセル ( ポ えます (Fig. 7 ) 。あらかじめ , 最後のセル は参照することはて、きないのて、 , 一見 , ② インタ p が指している ) に , 必要な値をセッ へのポインタがわかっていれば , 連結も分 トします。たとえば , に分類されるように思えますが , そのよう 断も O ( 1 ) て、実行て、きます。これらの操作 な変数の値はプログラムの実行が終わるま は , 配列てもて、きないことはありませんが , p—>value 125 ; て、保持されるのて、 , ①になります ) 。 などとします。 要素をある配列から別の配列へコピーしな しかし実際にプログラミングをしてみる 関数 malloc は割り当てるべきメモリがな ければならないのて , リストの長さに比例 と , 関数の実行とは関係なく寿命をコント くなってしまったら , NULL を返します。 した計算量がかかります。 そこて、 , 3 ~ 4 行目て、 , 関数 ma Ⅱ oc の返す値 ロールて、きるような変数がほしくなります。 最後になってしまいましたが , 複雑なデ が NULL て、あるかどうかをチェックしてい また , 連結リストのようなデータ構造を実 ータ構造を構築することができる , という 現するには , メモリを任意の時点て、割り当 ます。 mall oc のように , 工ラーが発生した のが連結リストの最大の利点て、す。不定長 ときに , それを通知する特別な値を返すよ てて , 解放て、きなければなりません。 の連結リストが不定個存在する , 連結リス うな関数については , 必ずチェックを行う このようなニーズを満たすものとして , トの要素が別の連結リストへのポインタを C 言語て、は標準ライプラリにメモリ管理用の のが鉄則て、す。 もっている ( つまりリストのリストになって このようなチェックを忘れても , テスト 関数が用意されていて , プログラムの実行 いる ) , セルに複数のポインタをもたせるこ 中のように扱うデータが少量の場合には , とによって同時に複数の連結リストに所属 中の任意の時点て、メモリを割り当てたり解 メモリを使い切ることはまずないのて、 , な 放したりすることがて、きます。メモリを割 て、きるようにする , などのくふうによって , んら不都合は生じないてしよう。しかし , 非常に込み入った関係を表現するようなデ り当てるのは ma Ⅱ oc , 解放するのは f 「 ee とい デバッグがすんて、本番使用を開始すると , ータ構造を作ることが可能て、す。連結リス う関数て、す。 大量のデータが入力されてメモリを使い切 トをベースにしてどのようなことがて、きる このようなメモリ管理を行う関数のしく みは , それ自体アルゴリズム的にたいへん ってしまい , ある日突然プログラムが暴走 かは , 次回て、取り上げます。 してしまう状況は十分に考えられます。 おもしろいものて、す。また , 使わなくなっ メモリ管理について たメモリは , free 関数によってシステムに返 のような関数はエラーを通知するのに NULL という値を使うことが多いのて、 , メモリ保 すことになっていますが , 使わなくなった 護が不十分な OS て、はシステム領域を書き換 連結リストを使う場合には , 要素を入れ メモリを自動的に回収する (garbage collec えてしまい , 暴走する可能性が大て、す ( とく るセルは , 必要になるたびに割り当てるこ tion : ゴミ集め ) という技法もあります。 に MS-DOS 上て、 large model のプログラムて、 れらのメモリ管理については , いずれ独立 とになります。つまり , プログラムを書く はほば確実に暴走します ) 。反対に , きちん したテーマとして取り上げることにしまし うえて、 , 明示的にメモリ管理を行わなけれ とメモリ保護が行われている OS ( たとえば ばなりません。配列を利用するのなら , 必 よう。 UNIX) て、は , システム領域への書き込みは 要な領域を配列としてあらかじめ割り当て 連結リストへの挿入 ード的に禁止され , 書き込もうとした時 ておけばよいのて、 , メモリ管理は必要あり 占て、プログラムは強制的に終了させられる ません ( 厳密にいえば , 配列内のデータを管 のて、 , MS-DOS などに比べると「安全』て、 先ほど , 連結リストへの挿入 , 削除につ 理するのもメモリ管理には違いありません す。しかし , いずれにしても , あまりうれ いて簡単に説明しましたが , ここて、はより 詳しく考察してみましよう。実際にプログ しいことて、はないのて , このようなチェッ C 言語の変数をその寿命という点からみれ ラムを書くときには , とくに境界条件に注 クをめんどうがらずに行うことを習慣づけ ①プログラムの実行開始から実行終了 意する必要があります。 てください まで存在するもの メモリが不足するといった事態を除けば , 連結リストにつなぐセルを割り当てるに は , 標準関数ライプラリの ma Ⅱ oc を利用す ②関数の実行が始まるときから , その 連結リスト自体には長さの制限はまったく 関数の実行が終わるまで存在するも るのがいちばん簡単て、す。セルの割り当て ありません。これが配列の場合との大きな も含んだ形の挿入は List 1 ( 1 ) のようになり 違いて、す。 の 76 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 がないものとして考え
五ロ ニ = ロ ニ = ロ はじめて学ぶプロクラー ニンク 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 ;
とを示す末尾ポインタの代わりに リスト の最後のポインタに 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