Linked list

出席の確認はOpenLMS の 3 限のコマを用いて行う． 3限の授業時間中に出席登録を完了せよ．

レポート提出確認

この授業のトップページからレポートのページに移動し，レポートの提出状況を常に確認せよ．

講義

教科書の補足

p.19 の List2.4 は二分探索法におけるデータの登録を行う関数 add_binary の疑似コードである．（(4) はtable[pos].data = data;の間違いであること，最後に(5)として n++; を追加しなければならないことに注意）第 3 回課題のプログラムに add_binary を追加して，実際に動作するプログラムとして完成させることができる． List2.4 中の (1) の部分は第 3 回課題の position_search を使い，(2) の部分を完成させればよい．

完成した add_binary をテストするメインルーチンでは print_all が利用できる． print_all で要素を挿入する前の全データを表示しておき，add_binary で要素を挿入した後で print_all を行って比較することで add_binary が正しく動作しているかどうかのテストができる．

5.1 連結リスト

教科書の 5.1 節ではポインタを利用した連結リストの説明がされているが，その前にそれに必須の知識である， 動的メモリ割り当て と自己参照的構造体について説明する．

リストを実現する場合，連結リストが配列と比較して優れているのは，

なことが挙げられる．検索に時間がかかる欠点もあるので，検索とあわせて挿入，削除が行われる場合は 2 番目の利点はあまりない．

ポインタと動的割り当て

データの増減に合わせて実行時に使用記憶領域を増減できるという利点は連結リストをポインタを用いて実現していることで可能になっている．ここで理解しなければならない概念は動的メモリ割り当て と自己参照的構造体である．以下に説明する．

動的メモリ割り当て

ここでポインタを利用した動的メモリ割り当てについて説明し，演習を行う．教科書では 22 章に関連した説明がある．

処理するデータの要素数がわからないとき，配列による実現では要素数を予測してコンパイル時に配列の大きさを決める必要がある．これをメモリの静的割り当て という．静的割り当てでは，メモリが足りなくなればプログラムは正常に動作しないし，逆に要素数が予想が多すぎたときも宣言したメモリ領域が無駄に占有されるので効率が悪い．

要素数が増えて領域が必要になったときに 実行時にメモリを新たに確保することをメモリの動的割り当てという．

この授業では動的メモリ割り当てに malloc 関数を使用する．動的割り当てを使用する基本的な手順は，以下の通りである．

静的割り当てと動的割り当てで整数型の変数を使用するソースを比較する．以下のソースは静的割り当てにより整数型の変数 i を利用するソースである．

#include <stdio.h>

int main(void)
{
    int i;

    i = 10;
    printf("%d\n", i);
}

上記と同様のことを動的割り当てで行うソースは（実用的なものではないが）以下のものである．

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *ip;  /*この時点ではまだ整数を入れる領域は確保されない*/

    ip = malloc(sizeof(int)); /*ここで領域が確保される*/
    *ip = 10;
    printf("%d\n", *ip);
    free(ip);
}

malloc を利用するときはメモリ制御関連のルーチンが書かれている <stdlib.h> をインクルードする必要がある（図4.2の2行目）．

int *ip; で宣言されているのは整数型領域へのポインタ を格納する変数 ip であることに注意する．変数 ip の領域はここで確保されるが，整数型ではなく整数へのポインタ型の領域である．

int *ip; という文は「*ip が整数型である」とも読めるし，「(int *) 型（intへのポインタ型）の変数 ip」とも読める．後者のほうが正確な表現だが，変数に格納されたデータにアクセスする場合は前者のように読むと分りやすい．図4.2 の 9, 10 行目もそのように読むと理解しやすい．注意しなければいけないのは変数宣言 int *ip; で変数 ip の領域が確保されただけでは整数を入れる領域 *ip は確保されず使えないことである． malloc を行って領域を確保して初めて整数型の領域 *ip を使う事ができるようになる．

malloc の使い方は一見複雑だがパターンになっているので覚えてしまえばよい．malloc の引数には確保すべき領域のサイズを指定しなければならないが，通常図4.2のように sizeof(「格納するデータの型」) と書くパターンが多い． sizeof 演算子は変数型が引数であった場合その格納データ領域の大きさを返す．この授業ではmalloc(sizeof(「データ型」))のパターンしか使わない（「データ型」の部分をその場に応じたものに変える）のでこの使い方のみ覚えればよい．

malloc による領域割り当て後は ip が指す領域は間接演算子 * を前につけて *ip とすることで普通の整数型変数と同じように利用できる．

malloc は領域の確保に失敗すると値として NULL を返すのでその場合にプログラム強制的に異常終了させるライブラリ関数 exit を使用したものが以下のサンプルコードである．図4.3 の if 文とその下の exit(1) までを動的メモリ割当の決まり文句と思って使えばよい．（"int" の部分を状況に応じて変える）図4.3 を適当な名前で保存してテスト実行し，ポインタ ip が指す領域にある整数型のデータを間接演算子 * を使って利用できることを確認せよ．

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *ip; 

    if ((ip = malloc(sizeof(int))) == NULL)
        exit(1);
    *ip = 10;
    printf("%d\n",*ip);
    free(ip);
}

自己参照的構造体

自己参照的構造体とは以下の例のように構造体に自分と同じ型のデータへのポインタをメンバとして含む構造体である．

struct CELL {
    struct CELL *next;
    int value;
};

自己参照的構造体は主に動的割り当てと組み合わせて使われる．連結リストは自己参照的構造体と動的割り当てを利用したデータ構造である．

以下の図4.5は教科書p.51 Fig5.1(b)の連結リストを構成したものである．ただし，教科書教科書p.50 から p.59ではグローバル変数 header が連結リストの最初の要素へのポインタ変数となっているのに対して，図 4.5 では header は各要素と同じ型である struct CELL 型要素となっている．このため図4.5のグローバル変数 header は他の要素と同様に next, value メンバをもつ．しかし，header.value は使わず， header.next のみを連結リストの最初を指すポインタとして利用する．つまり，教科書の header は図 4.5 の実装では header.next と読み替える必要があることに注意せよ．

#include <stdio.h>
#include <stdlib.h>

struct CELL {
    struct CELL *next;
    int value;
} header;

int main(void)
{
    struct CELL *ap, *bp, *cp, *dp;

    if ((ap = malloc(sizeof(struct CELL))) == NULL)
        exit(1);
    if ((bp = malloc(sizeof(struct CELL))) == NULL)
        exit(1);
    if ((cp = malloc(sizeof(struct CELL))) == NULL)
        exit(1);
    if ((dp = malloc(sizeof(struct CELL))) == NULL)
        exit(1);
    header.next = ap; /*header.next が最初の要素を指す*/
    ap->value = 2;
    ap->next = bp;    /*最初の要素のnextが2個目の要素を指す*/
    bp->value = 5;
    bp->next = cp;    /*2個目の要素のnextが3個目の要素を指す*/
    cp->value = 12;
    cp->next = dp;    /*3個目の要素のnextが最後の要素を指す*/
    dp->value = -4;
    dp->next = NULL;  /*最後の要素のnextは何も指さない*/

    printf ("%d ",header.next->value);
    printf ("%d ",header.next->next->value);
    printf ("%d ",header.next->next->next->value);
    printf ("%d ",header.next->next->next->next->value);
    printf ("\n");
}

図 4.5 では，例えば ap は stcuct CELL 構造体（next と value の両方の2つのメンバを記録できる）の変数へのポインタ変数（アドレスを格納する変数）である．これも
ap = malloc(sizeof(struct CELL));
により malloc で実際に領域を確保して，確保できたアドレスをポインタ変数 ap に格納している．領域が確保できた後は前の整数型の例と同じようにポインタ変数の前に間接演算子 * をつけて *ap と書くことで実際に値を記録できる「実体」の変数として利用できる．

今回は *ap は stcuct CELL 型の構造体変数なので
(*ap).next で next メンバ
(*ap).value で value メンバにアクセスできる．
この括弧は省略できない．理由は * よりも . のほうが優先順位が高いためで， *ap.next と書くと *(ap.next) の意味になって正しいプログラムでなくなるためである．

ポインタを「実体化」させてメンバにアクセスする，というのは頻繁に使われるので短縮形が用意されている．それがアロー演算子 -> で， (*ap).next の代わりに ap->next と書ける．ポインタ変数 ap を ->で「実体化」させつつ next メンバにアクセスする，と読むとよい．メンバにアクセスするとき，変数が図4.5のheader変数のように「実体」の変数であればドット演算子を使い，
header.next
と書き，変数が「実体」ではなくポインタ変数であればアロー演算子を使って
ap->next
と書く，と理解してもよい．

図 4.5 のように連結リストの先頭を指すのにリストの要素と同じ型のダミーを用意してその next メンバのみを利用する実装は，要素の削除や挿入のソースが簡単になるためによく用いられる．教科書も p.60 以降はこの実装を採用している．

図 4.5 を読み，実行してポインタの代入による繋ぎ合わせを理解せよ．

練習4.2

図4.5の next メンバへの代入文，すなわち，
header.next = ap;
ap->next = bp;
bp->next = cp;
cp->next = dp;
dp->next = NULL;
の右辺のみを書き換えてリストの要素の順番を (-4 12 5 2)になるようにポインタのつなぎかえを行え．出力も確認せよ．

5.1.1連結リストとは?

連結リストとは上で説明したように動的割り当てと自己参照的構造体を組み合わせてリストを実現したもの．「ポインタ」はメモリ上のアドレスのことだと考えて理解する． p.52 5,6行目の for ループのように，ある要素を指しているポインタを次の要素を指すように更新してゆく手法は連結リストに対する操作で最も多用される基本的なものである．　

Linked list 連結リスト

出席登録