単方向リストの実装

単方向リスト

リストとは順序を持ったデータの集合を表すデータ構造で，任意の位置への挿入，削除などの機能を持つ．また，リストのデータ構造をポインタにより実現したものを連結リスト(Linked list)と呼ぶ．

連結リストは，そのポインタの方向性から単方向リストと双方向リストに分類される．

単方向リスト

単方向リストは，データを格納する「要素」と「ポインタ」を組にした「セル」と呼ばれる単位で，データの順序を管理する連結リスト構造である．ポインタには，次のセルのアドレスが格納されている．

要素の挿入や削除は，ポインタの指す先を変更することにより行う．要素そのものの位置を変更する必要がないため，配列を用いたリスト構造と比較して高速に処理を行うことができる．

双方向リスト

双方向リストは，「要素」と「次のセルを指すポインタ」「前のセルを指すポインタ」でセルを構成した連結リスト構造である．セルに必要とするメモリ量が増加し，挿入・削除などの操作が複雑になるが，リストを前方にも後方にもたどれる利点がある．

プログラムの概要

この課題では，７文字までの文字列を要素とした単方向リストを実装する．

プログラムが実行されると，ユーザーからの入力待ちとなる．コマンドにより，以下の５つの処理を実行する．

リストの先頭に追加 (A)dd,
任意の位置に挿入 (I)nsert
任意のセルを削除 (D)elete
リストの全体を表示 (P)rint
プログラム終了 (E)xit

プログラム実行例を以下に示す．（赤字はユーザが入力する部分）

>>     <- 入力待ち．エンターを入力するとヘルプを表示
(A)dd, (I)nsert, (D)elete, (P)rint, (E)xit
>>a   <- 先頭に挿入
先頭に挿入する文字列を入力：apple <- 挿入する文字列を入力
>>a
先頭に挿入する文字列を入力：orange
>>p   <- リストの状態の表示
- addr -- next -:string
[00430100][00430080]:HEADER    <- セルのアドレスと
[00430080][004300c0]:<orange>     メンバの値が表示される
[004300c0][00000000]:<apple>
------
>>i <- 新規セルの挿入
挿入位置の文字列を入力:orange
挿入する文字列を入力:banana
>>p
- addr -- next -:string
[00430100][00430080]:HEADER
[00430080][00430040]:<orange>
[00430040][004300c0]:<banana> <- banana が挿入された
[004300c0][00000000]:<apple>
------
>>d <- セルの削除
削除する文字列を入力:orange
>>p
- addr -- next -:string
[00430100][00430040]:HEADER
[00430040][004300c0]:<banana>
[004300c0][00000000]:<apple>
------
>>e

サンプルプロジェクトが P:\学部授業関連\2011年度後期\プログラミング演習II\hasegawa\slist においてあるので，ディレクトリごとコピーして使用すること．

サンプルプログラム

サンプルプログラムを以下に示す．

プログラムは，リスト操作を行う List から始まる名前の関数群と，これらのリスト操作関数を呼び出す main 関数から構成されている．
（リストを扱う関数には，すべて List から始まる関数名をつけている．このようにまとまった機能を持つ関数群に特定のプリフィックスをつけた命名をすることは，名前空間の管理機能を持たないC言語プログラムの設計を見やすくするために効果的である．）

本プログラムで使用するリスト構造

本プログラムで使用するリスト構造のための構造体定義とその詳細を解説する．

セルの構造体定義

プログラムに使用するセルの構造体定義を以下に示す．

/* リストセル　構造体定義 */
typedef struct cell {
char string[8];
struct cell *next;
} CELL, *PCELL;

セルに使用する cell 型構造体は，8バイトの文字配列 string と，cell 型構造体を指すポインタの２つのメンバで構成されている．

同時に typedef 宣言を用いて，struct cell と同じ意味の CELL型と，CELL型を指すポインタ型の PCELL を宣言している．

リスト構造

この課題で用いるリスト構造では，リストの先頭には，要素が空のセル（ヘッダーセル）を常に配置する構造とする．リストの終端ノードの next メンバは NULL とする．

常にヘッダセルを持たせる構造により，ノードの削除をする関数の引数として，「削除する直前のセルのアドレス」を渡すことができ，プログラムの構造を簡略化できるようにしてある．

リストが空の状態

リストに要素が２つ(banana，apple）格納されている状態

ListCreate() リストの構築

ヘッダセルを含めて，セルの領域のアロケートはリスト関数群で行う（main関数では malloc などを呼び出さない）．

ListCreate() 関数は，空のリストを作成するための関数である．リストを使用する main 関数は，ヘッダセルのアドレスを保持する PCELL 型の変数を用意し，ListCreate() 関数の戻り値を保存する．

main 関数での ListCreate 関数呼び出し前後の様子

ListInsert() 関数セルの挿入

ListInsert() 関数は，任意のセルを指すポインタ pos と，新規に作成するセルの文字列を引数として受け取り，新規にセルを作成した後に pos で指定されたセルの直後に挿入する．また，この関数にヘッダセルのアドレスを渡すと，リストの先頭にセルを追加することができる．
（常に空のヘッダセルを設けているので，この関数は挿入する先がリストの先頭か否かを区別せずに処理をすることができるようになっている．）
ListInsert 関数の動作を，プログラムコードを交えながら以下に示す．

1) 関数が呼び出された時の状態

２）　新しいセルのメモリ領域を確保

３）新しく作成したセルの string メンバに文字列をコピー

４）ポインタの付け替え　１

５）ポインタの付け替え　２

(構造体メンバへの間接参照については，課題１構造体を参照すること．）

ListDelete() 関数

ListDelete 関数は，削除するセルの直前のセルを指すポインタを引数として受け取る．ポインタを張替えを行った後に，不必要になったセルを free 関数で解放する．

１）関数が呼び出された状態

２）ポインタの付替え

３）不要になったセルの解放

注)ポインタの付け替えを行った後に不要になったセルを解放するので，削除するセルのアドレスを一時的に保存しておく変数が必要になることに注意．

ListDestory() 関数

ListDestory 関数は，ヘッダセルへのポインタを受け取り，そのリストに含まれるすべてのセル（ヘッダセルを含む）のメモリ領域の解放を行う．

セルの next メンバをたどりながらループをまわし，すべてのセルを順番に開放していく．

この他の関数については，サンプルプログラム中のコメント，およびサンプルコードを参照すること．

課題内容

１）デモプログラムを動作させ，挿入，削除などの操作を行いながらリストの表示を確認し，各セルの値（特に各セルのアドレスと next フィールドの値の関係）を確認する．
（完成したデモプログラムが，slist フォルダ内の slist_demo.exe として置いてあるので，これを使用する．）

２）この資料を元に，セルの挿入(ListInsert)，セルの削除(ListDelete) リスト全体の破棄(ListDestory) を完成させる．

３) main 関数を以下のテスト用コードと差し替え，デバッガ上で実行し，異常終了することなく正しく動作することを確認する．このときメモリリークが発生していないことを確認する．

// テスト用メイン関数
int main()
{
    PCELL header;

    header = ListCreate(); //リストの構築

    ListInsert(header, "panda"); //要素の先頭への挿入
    ListInsert(header, "hippo");
    ListInsert(header, "shark");
    ListInsert(header, "koala");
    ListInsert(header, "giraff");
    ListInsert(header, "crane");

    ListPrintAll(header); //表示

    // 挿入のテスト
    ListInsert(ListNext(ListGetPrevPos(header, "shark")), "walrus");

    // 削除のテスト
    ListDelete(ListGetPrevPos(header, "shark"));
    ListDelete(header);

    ListPrintAll(header); // 表示

    ListDestroy(header);
    //メモリリーク情報の表示
    _CrtDumpMemoryLeaks();

}

以下のような実行結果が得られればよい．

- addr -- next -:string
[00430100][00431dc0]:HEADER
[00431dc0][00431e00]:<crane>
[00431e00][00431e40]:<giraff>
[00431e40][00430040]:<koala>
[00430040][00430080]:<shark>
[00430080][004300c0]:<hippo>
[004300c0][00000000]:<panda>
------
- addr -- next -:string
[00430100][00431e00]:HEADER
[00431e00][00431e40]:<giraff>
[00431e40][00431d80]:<koala>
[00431d80][00430080]:<walrus>
[00430080][004300c0]:<hippo>
[004300c0][00000000]:<panda>
------

４） main 関数を初期状態に戻し，追加する文字列の長さをいろいろと変更しながら実行し，そのときの様子を確認せよ．プログラムが異常終了する場合，なぜそのようになるかを考察せよ．

5) CELL 構造体（struct cell) のサイズを調べよ．さらに string メンバの要素数を８から９に変更し，このときに構造体のサイズがどのように変化するかを確認し，その結果を考察せよ．

6) (オプション課題) 単方向リストを双方向リストに変更せよ．さらに，リストを逆順に表示する ListRevPrintAll 関数を実装せよ．

課題１ 単方向リストの実装