Linked list 2

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

レポート提出確認

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

講義

5.1.1

    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);

第 4 回課題の print_all を作成するにはこの出力部分をループで実現しなければならない．ループにするためにはループ変数を決めて，同じ形を繰り返すように変形しなければならない．上のプログラム部分は以下のものと等価である．（p は (struct CELL *) 型のポインタ変数とする）

    p = header.next;
    printf ("%d ",p->value);
    p = p->next;
    printf ("%d ",p->value);
    p = p->next;
    printf ("%d ",p->value);
    p = p->next;
    printf ("%d ",p->value);

これで printf ("%d ", p->value); p = p->next; をループの中で繰り返せばよいことがわかる．最後の要素を出力したときのポインタ p が指す要素の p->next の値は NULL であるからこれをループ終了の条件とすればよい．結局 print_all は以下のようなループで作ることができる．

void print_all(void)
{
    struct CELL *p;

    p = header.next;
    while (p != NULL){
        printf("%d ", p->value);
        p = p->next;
    }
    printf("\n");
}

この，リストの先頭から最後までたどる処理は連結リストの基本となる処理なのでよく理解すること．

練習5.1

前回図4.5 の main 関数の上に print_all() 関数を追加し，出力するための行

    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");

5.1.2連結リストの基本的性質

単純な連結リストでは，途中の要素にアクセスするためには先頭から一つずつ next メンバをたどってゆく必要がある．（$O(n)$）また，全ての要素にデータを格納する領域の他に次の要素を指すポインタを格納する領域が必要である．

要素の途中への挿入，削除は，近隣の数個の要素の next メンバの書き換えで行うことができる．配列のように後の要素を全てずらす必要がない．

P.54 Fig5.2 の操作を実際に行ってみる．前回図4.5 の2個目の要素の後ろに要素（value=8 とする）を挿入する手順を説明する．まず教科書 p.54 Fig 5.2 と同じ状況になるように挿入位置の前の要素へのポインタを記憶する変数 x と新しい要素へのポインタを記憶する変数 p を main 関数の最初の変数宣言の場所に付け加える．

    struct CELL *ap, *bp, *cp, *dp, *x, *p;

の行でリスト(2,5,12,-4)が完成している．その後ろに挿入作業のコードを追加する．

教科書図 5.2 の変数 x と同じ状況にするには 2 個めの要素へのポインタ bp を x に代入すればよい．（2番目の後に挿入するため）

次にmalloc を行い，要素一つ分のメモリを確保してそのアドレスを変数 p に保存する以下の文を挿入する．

    if ((p = malloc(sizeof(struct CELL))) == NULL)
        exit(1);

次にデータの記録（value=8）と周辺のポインタのつなぎ変えを行う．具体的にはまず p->value にデータである 8 を代入する． x->next には旧3番めの要素へのポインタが格納されている．この値は新4番目として必要なので先に p->next にコピーしておく．次に x->next へ新3番目となる新しく作成した要素へのポインタ p を代入する．（x->next が p と同じものを指すようにする）まとめると，具体的には上の図5.7「malloc による領域確保」の次に以下の文を挿入する．

    p->value = 8;
    p->next = x->next;
    x->next = p;

2 行目と 3 行目の順番を逆にししまうと後で必要になる新4番目へのポインタの値が消えてしまうので正しく動作しないことに注意せよ．

練習5.2

main に上記の変更を行い，挿入作業（図5.6,図5.7と図5.8追加部分）の前後で print_all()を実行するテストプログラムを作成し，実行してリストが (2 5 12 -4) から (2 5 8 12 -4) に変化し，実際に挿入が行われていることを確認せよ．

必要になってから要素の領域を動的に増やせることが連結リストの大きな利点である．

練習5.3

P.54 Fig5.3 をよく見て，練習 5.2 の状態のリスト(2 5 8 12 -4) から2 番目の要素を削除するようにポインタをつなぎ変えよ． print_all() を使って削除されていることを確認せよ．

実際のプログラムでは，ここまでの例の変数 ap, bp, cp, dp のように全ての要素へのポインタを記憶しておくようなことはしない．「現在見ている要素」へのポインタ p を用意しておいて p = p->next などを実行して p を「進めながら」処理する．

P.56 Fig5.4,5.5 のように連結リストは，接続，切断ポイントのポインタが分っていれば簡単に（$O(1)$で）接続，切断が行える．

5.1.3 連結リストとメモリ管理

動的割り当てを行うのでプログラム実行中に領域を確保する関数を実行する必要がある．この授業では malloc を使う．コンパイル時ではなく，プログラム実行中の任意の時点で malloc で領域を確保し， free で解放できる．　

5.1.4 連結リストの操作

5.1.4.1 要素の挿入

ここからは練習5.2までのように全ての要素へのポインタを記憶することなく必要なポインタ変数だけ使用してメモリの動的割り当てを行うより実践的な関数を実装してゆく．また，データ構造の実現と本体アルゴリズムを分離する意味から，抽象データ型リスト（データ構造である連結リストとは別の概念であることに注意）の基本操作（教科書p.35 Table 4.1）を関数として提供し， main からは基本操作関数を通してのみデータにアクセスする方針でプログラムを作成する．例えば今まで行っていたように main 内で直接構造体の value メンバの値を参照するようなことはせず，値を取り出す基本操作関数を通して要素の値を受け取るような構造にする．

データ構造と本体アルゴリズムを分離し，基本操作のアクセス方法を決めることで，データ構造だけの改良，本体アルゴリズムだけの変更ができる．これは抽象化を意識したソフトウェアの開発方法で，大規模なソフトウェアになるほど重要になる．

使用する連結リストはこれまでと同様に struct CELL 型として宣言されたグローバル変数 header をダミーヘッダとしたものとする． header.next が NULL なら連結リストは空であり， NULL でなければ header.next が一個目の要素へのポインタとなる．

最初に空のリストを作成する関数 new_list を作成する．構造体 header はグローバル変数として宣言されているのでプログラム開始時は領域は確保されているが値が設定されていない状態になっている．new_list のすべきことはグローバル変数 header の next メンバに NULL を代入することである．関数 new_list には引数も戻り値もない．

void new_list(void)
{
    header.next = NULL;
}

次にリストの先頭に要素を挿入する関数 insert_head を作成する．この関数には引数として挿入する要素の値（value メンバに設定する値）を渡す必要がある．この int 型のパラメータの名前を v とする．

手順としてはまず以下のことを行い，挿入する一個分の要素を作成する．

次に，p が指している（アドレスが p である）新たに作成した要素を連結リストの先頭に挿入するためのポインタのつなぎ変えを行う．連結リストが空のときでも正しく動作するかどうか吟味することは重要である．このような場合には漏れがないように場合分けを行って考察する．

ここで上記 2 つの場合をよく見ると，要素が存在するときの処理を連結リストが空のときに行っても正しい値が設定されることがわかる．（空のリストの header.next は NULL だから）このことからプログラムでは場合分けは必要なく，要素があるとき用に書いた処理を行えば両方の場合で正しく動作することがわかる．

void insert_head(int v)
{
    struct CELL *p;

    if ((p = malloc(sizeof(struct CELL))) == NULL)
        exit(1);
    p->value = v;
    p->next = header.next;
    header.next = p;
}

sttuct CELL 構造体の定義と，これまで作成した new_list, insert_head, print_all をまとめて，main として簡単なテストを行うプログラムを付け加えたものが下の図5.11 である．実行し，main 内のテスト内容を変更して動作を確認せよ．

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

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

void insert_head(int v)
{
    struct CELL *p;

    if ((p = malloc(sizeof(struct CELL))) == NULL)
        exit(1);
    p->value = v;
    p->next = header.next;
    header.next = p;
}

void new_list(void)
{
     header.next = NULL;
}

void print_all(void)
{
    struct CELL *p;

    p = header.next;
    while (p != NULL)
    {
        printf("%d ",p->value);
        p = p->next;
    }
    printf("\n");
}

int main(void)
{
    new_list();
    print_all();
    insert_head(-4);
    print_all();
    insert_head(12);
    print_all();
    insert_head(5);
    print_all();
    insert_head(2);
    print_all();
}

Linked list 2 連結リストその2

出席登録