立命館大学情報理工学部メディア情報学科

> Lecture > Programming Seminar 2

Last Update : Nov. 19, 2010

第７，８回演習

演習課題に関して

第７，８回の課題は，リストを用いてスタック及びキューを作成するというものです．配列を使った場合，予め決められた大きさになります(※注)．リストを使ってこれらのデータ構造を作成すると，配列を使った場合と比べてデータを格納できる量の制限が（ほぼ）無くなるというメリットがあります．

※注：プログラム中でmalloc関数を使って動的に配列のメモリを管理すれば，大きさを可変にすることも可能です．しかしながら，使用中に容量を変更するには手間がかかります．

「データ構造とアルゴリズム」の教科書にも考え方が記載されていますので，適宜参照してください．

今回はヒントとして，リストを使ってキューを作った場合の構造を図示していきます．これらの図をヒントに考えてみてください．

まずは最初に，キューを作成するときに使用するデータ構造を見てみましょう．今回は図に示したstruct queueとstruct queueheadという２つの構造体を使います．

struct queue {
  char key ;
  struct queue *next ;
};

struct queuehead {
  struct queue *top, *rear ;
} q ;

サンプルプログラム中では，qという名前のstruct queuehead構造体が1つ定義されています．キューに何もデータが入っていない変数qの初期状態を図示すると以下のようになります．topがキューの先頭（最初に入れたデータ）を，rearがキューの末尾（最後に入れたデータ）を指すことになります．

この初期状態を作り出すのは，サンプルプログラム中では，init_queue()関数です．

初期状態のキューにデータを挿入（Enqueue）するには，まず始めにデータを格納するためのstruct queue構造体を準備します．ここでは，struct queue構造体へのポインタ変数として，newDataという名前の変数を準備しています．そして，その中にデータ（data1）を入れます．図としては以下のようになります．

struct queue *newData ;

その上で，準備した構造体を指すようにtopとrearを変更すればOKです．図としては以下のような感じでしょうか．

この状態でさらにキューにデータを挿入にはどうすればいいでしょうか．ここでも先ほどと同様にデータを格納するstruct queue構造体を準備します．そして，その中にデータ（data2）を入れます．図としては以下のようになります．

キューでは，後から入れたデータをどんどん末尾に追加していけばいいわけですから，まずは，その時点で，rearが指していたもののnextが新たに作成した構造体になるようにします（図中①）．その上で，rearが指しているものを新たに作成した構造体にすれば作業は終了です（図中②）．順番に注意してください．図示すると以下のようになります．

注意点としては，初期状態に対してデータを挿入する場合と，それ以外の場合で処理が異なっているという点です．データの取り出し（Dequeue）については自分で考えてみてください．先に図を描くとわかりやすいと思います．

ポインタで作成したキューと，キューのイメージを対比させると以下のような図になるでしょう．

リストにおける構造体の領域確保

構造体を使ってリストを作成する場合，データを格納するstruct queueは必要に応じてメモリから領域を確保していく必要があります．これは構造体を指すポインタ変数を準備しただけでは行われず，必ずmallocもしくはそれに類するメモリ確保関数を使う必要があるからです．

ここでは，struct queue構造体を指すポインタ変数newDataがあった場合に，メモリ領域を確保するサンプルプログラムを示します．

struct queue* newData ;

newData = (struct queue *)malloc(sizeof(struct queue)) ;
if (newData == NULL) {    /* メモリ確保に失敗した場合のエラー処理 */
  fprintf(stderr, "Cannot allocate memory\n") ;
  exit(EXIT_FAILURE) ;
}

なお，malloc関数で確保したメモリ領域の中身は不定です（クリアされていない）．使用する前に中身を初期化しておく必要があります．メモリの確保に失敗した場合は，NULLが返されますので，エラー処理をしましょう．

また，メモリ領域を確保した場合，その使用が終了したら必ずメモリを解放する必要があります．解放にはfree関数を使用します．サンプルプログラムは以下のようになります．もし，メモリの解放を忘れるとメモリリークが発生します．

free(newData) ;    /* struct queue* newData としてポインタ変数が準備されている場合 */

注：メモリリークとは，コンピュータの動作中に使用可能なメモリ容量が減っていく現象のことです．