第3回 - リスト(1)

Go to Outline

課題1: 線形リスト

リスト(list)とは，要素を順序付けて格納するコレクションである．

ここでは，以下に示す構造体を用いて，整数の値を格納する線形リスト(線状リストや連結リストとも呼ぶ)を構築するソースコード prog3-1.c を作成する．

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

この構造体は，後続する要素を指すポインタ next を持つ．要素が末尾の場合，next は NULL とする．

通常，線形リストは先頭から要素をたどるため，リストの先頭を指すポインタを用意する．ここでは，リストを以下に示す構造体で表現する．

struct list {
    struct element *top;
};

top は線形リストの先頭を指すポインタである．リストが空の場合，top は NULL とする．

線形リストの例を図3.1に示す．

図3.1: 線形リストの例

いま，線形リストを構築するために，以下に示す3つの関数を用意する．

(1) 空の線形リストを生成する．

struct list *create_list();

(2) 整数の値 value を格納した線形リストの要素を生成する．

struct element *create_element(int value);

(3) list に格納されている整数の値を先頭から順番に画面に表示する．

void print_list(struct list *list);

上記の3つの関数を持つ prog3-1.c を作成せよ．

本課題では，図3.1の線形リストに対して，テスト関数 test1() がすでに用意されている．空のリスト，要素を3つ持つリストなど，さまざまな線形リストを構築するテストコードを prog3-1.c に追加せよ．

課題2: 線形リストに対する操作(1)

課題1で作成したソースコード prog3-1.c に対して，以下に示す4つの関数を追加したソースコード prog3-2.c を作成する．

(1) list の先頭に要素 elem を挿入する．

void insert_front(struct list *list, struct element *elem);

(2) list の末尾に要素 elem を挿入する．

void insert_rear(struct list *list, struct element *elem);

(3) list の先頭の要素を削除する．

void delete_front(struct list *list);

(4) list の末尾の要素を削除する．

void delete_rear(struct list *list);

上記の4つの関数とテストコードを含む prog3-2.c を作成せよ．

課題3: 線形リストに対する操作(2)

課題2で作成したソースコード prog3-2.c を，リストから任意の位置の要素を取得できるように改良する．このために，線形リストに格納されている要素の数を表す変数 size を追加した，以下の構造体を用意する．

struct list {
    struct element *top;
    int size;
};

上記の構造体を用いて，以下に示す2つの関数を追加したソースコード prog3-3.c を作成する．

(1) list に格納されている要素の数を返す．

int size_of_list(struct list *list);

(2) list の index 番目の要素を取得する．index 番目の要素が存在しない場合は，NULL を返す．

struct element *get_from_list(struct list *list, int index);

上記の2つの関数とテストコードを含む prog3-3.c を作成せよ．

課題4: 線形リストに対する操作(3)

課題3で作成したソースコード prog3-3.c では，線形リストは先頭の要素を指すポインタしか保持していない．このため，末尾に要素を追加するためには線形リストを前から順番にたどらなければならず，実行の効率が悪い．そこで，線形リストを表現する構造体を以下のように拡張する．

struct list {
    struct element *top;
    struct element *rear;
    int size;
};

rear は線形リストの末尾を指すポインタである．リストが空の場合，top と rear は NULL とする．

末尾へのポインタを持つ線形リストの例を図3.2に示す．

図3.2: 末尾へのポインタを持つ線形リストの例

ここでは，上記の構造体に対応するように prog3-3.c の関数を書き換えた，ソースコード prog3-4.c を作成する．

書き換え後の関数とテストコードを含む prog3-4.c を作成せよ．

課題5: 線形リストに対する操作(4)

課題4で作成したソースコード prog3-4.c に対して，以下に示す3つの関数を追加したソースコード prog3-5.c を作成する．

(1) list の index 番目の要素の前に要素 elem を挿入する．

void insert_at(struct list *list, int index, struct element *elem);

(2) list の index 番目の要素を削除する．

void delete_at(struct list *list, int index);

(3) list1 の末尾に線形リスト list2 を付け加える．いいかえると，list2 に格納されている要素をそれらの順番を維持したまま，list1 の末尾に挿入する．

struct list *append(struct list *first, struct list *second);

上記の3つの関数とテストコードを含む prog3-5.c を作成せよ．