第4回では，以下の項目に関して学ぶ．

  1. 双方向連結リスト
  2. 循環リスト

課題のソースコードのテンプレート:

課題1: 双方向連結リスト

単純な線形リストでは後続する要素を容易に見つけられるものの，先行する要素を見つけることは面倒である．そこで，後続する要素だけでなく，先行する要素へポインタを保持する双方向連結リストを考える．

ここでは，以下に示す構造体を用いて，整数の値を格納する双方向連結リストを構築するソースコード prog4-1.c を作成する．

struct element {
    int value;
    struct element *prev;
    struct element *next;
};
この構造体は，後続する要素を指すポインタ next だけでなく，先行する要素を指すポインタ prev を持つ．要素が末尾の場合，next は NULL とする．また，要素が先頭の場合，prev は NULL とする．

双方向連結リストは以下に示す構造体で表現する． 

struct list {
    struct element *top;
    struct element *rear;
};
top は双方向連結リストの先頭，rear は双方向連結リストの末尾を指すポインタである．リストが空の場合，top と rear は NULL とする．

双方向連結リストの例を図4.1に示す．


図4.1: 双方向連結リストの例

いま，双方向連結リストを構築するために，以下に示す4つの関数を用意する．

(1) 空の双方向連結リストを生成する．
struct list *create_list();
(2) 整数の値 value を格納した双方向連結リストの要素を生成する．
struct element *create_element(int value);
(3) list に格納されている整数の値を先頭から順番に画面に表示する．
void print_list(struct list *list);
(4) list に格納されている整数の値を末尾から順番に画面に表示する．
void print_reverse_list(struct list *list);

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

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

課題2: 双方向連結リストに対する操作(1)

課題1で作成したソースコード prog4-1.c に対して，以下に示す4つの関数を追加したソースコード prog4-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つの関数とテストコードを含む prog4-2.c を作成せよ．

課題3: 双方向連結リストに対する操作(2)

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

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

上記の構造体を用いて，以下に示す2つの関数を追加したソースコード prog4-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つの関数とテストコードを含む prog4-3.c を作成せよ．

課題4: 双方向連結リストに対する操作(3)

課題3で作成したソースコード prog4-3.c に対して，以下に示す3つの関数を追加したソースコード prog4-4.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) first の末尾に線形リスト second を付け加える．いいかえると，second に格納されている要素をそれらの順番を維持したまま，firstの末尾に挿入する．
struct list *append(struct list *first, struct list *second);

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

課題5: 循環リスト

線形リストの末尾の要素に，先頭の要素を指すポインタを保持したリストを循環リストという．

ここでは，以下に示す構造体を用いて，整数の値を格納する循環リストを構築するソースコード prog4-5.c を作成する．

struct element {
    int value;
    struct element *next;
};
この構造体は，後続する要素を指すポインタ next を持つ．

循環リストは以下に示す構造体で表現する． 

struct list {
    struct element *top;
};
top は循環リストの先頭を指すポインタである．リストが空の場合，top は NULL とする．

循環リストの例を図4.4に示す．


図4.4: 循環リストの例

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

(1) 空の双方向連結リストを生成する．
struct list *create_list();
(2) 整数の値 value を格納した双方向連結リストの要素を生成する．
struct element *create_element(int value);
(3) list に格納されている整数の値を先頭から順番に画面に表示する．
void print_list(struct list *list);

さらに，循環リストを操作する以下に示す3つの関数を用意する．

(4) list の先頭に要素 elem を挿入する．
void insert_front(struct list *list, struct element *elem);
(5) list において，要素 pos の直後に要素 elem を挿入する．
void insert_after(struct list *list, struct element *pos, struct element *elem);
(6) list において，要素 pos を削除する．
void delete(struct list *list, struct element *pos);

上記の6つの関数とテストコードを含む prog4-5.c を作成せよ．
Go to Top