＊＊＊連結リスト＊＊＊

構造体の説明の最後に複雑なデータ構造の説明を行いたいと思います。

ここで説明するデータ構造は連結リストと呼ばれ構造体を使用したデータ構造としては最も基本的なデータ構造のうちの一つです。

この連結リストとはどのようなデータ構造かというと新しいデータの登録、必要がなくなったデータの削除が簡単に行えるデータ構造です。

例えば何らかの方法を用いて人の名前を線形に格納する事を考えます。この時に当然考えなくてはならない事はこのデータ構造に対してどのような操作が必要になるのかという事です。

データの検索、挿入、削除、変更、整列、データ構造の分割、コピー、要素数を求める、などと行った作業が必要になります。

もちろん、これら全ての作業が一つのプログラムで同時に必要になる事はあまりないでしょうが、せめてこれから自分が作るプログラムで使う操作だけは効率よく実行できるようにしておきたいものです。

　

この時、線形にデータを格納する方法として、今まで説明してきた方法だと配列がありますが、仮に配列を用いてデータを格納していったとして、上の操作のうちどれが簡単にできるでしょうか。

例えばデータの削除です。

配列を用いてデータを削除する時はまず、削除するデータを検索し、そのデータを削除し、そして空白ができたところを詰めていきます。

この時、最後の空白を詰める作業は平均して(配列の要素数 /2)回データの移動を行わなくてはなりません。また、新しいデータの登録を行う時も配列の場合だとあらかじめ決められた要素数の上限を超えて登録する事ができないといった欠点や、最初から、要素数の上限分だけメモリが確保されているのでメモリの無駄ができてしまいます。

このような欠点が配列にはあるのです。

これらの欠点を連結リストを用いる事で解決する事ができます(逆に配列の長所が失われるので連結リストと配列はうまく使い分けで下さい)。

例えば必要がなくなったデータの削除ですが、これを行う時には、削除するデータを検索する、データを削除する、という作業だけでできます。

また、新しいデータの登録では連結リストの場合あらかじめ要素数の上限が決められている事がないので、効率よく登録する事ができます。

それでは実際に連結リストを紹介します。プログラム(図2-3-1)を見て下さい。

図2-3-1

ここでは、連結リストに対して、データの検索、挿入、削除、変更を行う関数を紹介します。とりあえず実際のプログラムを見てから以下の説明を読んで下さい。

このプログラムは今までのものと異なりmainの関数がありません。理由は必要がないからですが、今後サンプルプログラムを提示する時にはmainの関数がない時が多いのでそのことに注意して下さい。

このプログラムは関数Serch、Insert、Delete、renewalの四つから構成されています。それぞれの関数で分からないところが今の段階では多いと思うので順番に説明していきます。

関数Serchはデータの検索を行います。引数に検索したいキーワードを入れて検索します。

検索に成功したらそのkeyを持つデータへのポインタを返し、失敗したらNULLを返します。（ここでNULLとは何もない事を表します。NULLを使用するためにはヘッダファイルstdio.hをインクルードします。）

　

この関数で見た事がないものといえばstrcmpという関数でしょう。この関数はstring.hをインクルードして使用する関数で、文字列の比較を行います。

strcmp(char *s,char *t)は2つの文字列sとtを辞書的な順序で比較し、文字列が等しい時は０を返し、辞書式順序がsの方が先の時は正の値を返します。逆にtのほうが先の時は負の値を返します。

ここでは文字列が等しいかどうかを考えているので返値が０であるかどうかに注目します。返値が０の時は検索しているデータが見つかったという事なのでそこで関数を終了して(return)そのポインタ変数を返します。

　

次にポインタ変数の使い方についての説明ですが、ここでは関数の最初にName *p;という部分があります。これがポインタ変数の使用宣言です。

この変数に連結リストの先頭のポインタを代入し、一つ一つkeyを確認しながら進んでいきます。この変数は常にデータへのポインタである訳ですから、検索中のデータが見つかればこの値を返してやれば(return p)良いという事になります。

　

ところで連結リストは常にNULLで終了しますのでpの値がNULLになったら検索は失敗です。その時は失敗を表すNULLを返しましょう。

　

関数Insetはデータの挿入を行います。すでにそのデータが存在している時は何もせずにそのまま終了します。

この関数ではまず連結リストの仲に新しく加えようとするデータが存在するかどうかを調べます。

ここで使うのは先ほど定義した関数Serchです。この関数を用いてデータが存在するかどうかを調べます。

そして先ほどもいった通りデータが存在している時は何もせずに終了します(return)。そうでない時は二つの場合に分けて新しいデータを登録します。

一つは連結リストが空の時です。この時は連結リストの先頭にデータを加えます。

この時、新しいデータのためにメモリを確保しなければなりません。そのために使用する関数が標準関数のmallocです。この関数はヘッダファイルstdlib.hをインクルードしてから使います。

この関数は確保したいメモリの大きさを受け取って、確保したメモリの先頭のアドレスを返します。

この説明で良く分からなければmallocを使う時はサンプルプログラムをそのまま真似るだけで良いでしょう。

また、このmallocの中で使用しているsizeof演算子はデータ型の大きさを求める演算です。mallocと一緒に覚えておくと便利です。

　

さて、メモリを確保したら、今度はその領域に加えるべきデータを代入します。メンバ演算子を使って代入しましょう。

この時用いる演算子は->です。また、ここでは連結リストの先頭に新しいデータを代入する訳ですから、今までの先頭、つまりはFirstには後ろに退いてもらいましょう。

具体的にどのように後ろに退けるのかというと新しく登録した変数 p の次に、つまり p->next にFirstを代入します。

このようにすれば新しいデータが連結リストの先頭になります。

しかし、変数Firstは常にリストの先頭を指すようにしたいので、データの登録が終了したら変数Firstの値を変更し、リストの先頭を指すようにしましょう。

　

続いてリストが空でない時ですが、この時はまずデータを挿入すべき場所を検索します。

この関数は辞書式にデータを挿入していくので当然挿入すべき場所を検索する時には先ほど説明した標準関数strcmpを用います。そして挿入すべきデータが変数 p->name と p->next->name の間にきたらその p の次に挿入します。

挿入する時は新しくメモリを確保して、確保した領域に必要なデータを代入し新しいデータが変数 p のすぐ後ろに来るようにします。なお、文字列を代入する時は標準関数のstrcpyを用います。

関数Deleteはデータの削除を行います。

データを検索し、そのデータが存在する時は削除し、存在しない時は終了します。

　

まず、ここで用いている関数でfreeという関数の説明を行います。この関数はmallocで確保した領域を解放する時に用いる関数です。

freeには解放したい領域の先頭を示すポインタを渡して領域を解放します。ただ単に解放したい領域の先頭を渡すだけですから簡単におもえますが、この関数を用いる時は注意が必要です。

この関数はエラーの管理をしていないのでこの関数に値を渡す時はその値がmallocで確保した領域の先頭を表すものなのかどうかを考えて渡しましょう。

また、ここで説明したfree、mallocは動的メモリ管理を行う時には必須なので絶対に覚えなくてはなりません。

　

さて、関数freeの説明が終わったところでデータの削除の方法を見てみます。まず連結リストの先頭に削除すべきデータがあるかどうかを調べます。そしてここに削除すべきデータが存在する時はそのデータを削除します。

まず、変数 p に削除すべきデータへのポインタ(First)を代入します。次に先頭を表す変数Firstを一つ進めます。

そうするとその時はリストの先頭は変数 p で表されていますから、これを関数freeで削除してやれば良い事になります。

関数renewalはデータの更新を行います。古いデータの上に上書きをするだけなので特に説明は要らない関数でしょう。