連結リスト，スタック，キュー

ATTENTION!

この課題から，C言語を本格的に利用したプログラミングが始まります． C言語の書き方について不安のある人は，実験に取り組む前にコンピュータとプログラミングの内容をしっかり復習してください．

• ちなみに今回の課題は，配列，構造体，ポインタ，メモリ領域の動的確保・解放の内容が極めて重要になります．

実験をスムーズに進めるためのコツ

1. 安定したプログラミング環境を用意しましょう．
   • 「安定した」とは，プログラムを走らせるためのハードウェア的な観点，プログラムをコンパイルするためのソフトウェア的な観点の両方から見て安定していることを意味します．
   • また，この実験はコードを書いてなんぼですので，自分にとってなるべくストレスを感じさせず，書きやすいエディタを使いましょう．今だとVSCodeが良いのではないでしょうか．
2. コード中のコメントは英語で付けましょう．
   • なるべく日本語(マルチバイト文字)でのコメントはやめて，ASCIIコードで表現可能な言語(つまり英語)でコメントしましょう．文字化けや思わぬ動作を引き起こす原因となることがあります．
3. コンパイラの警告・エラーメッセージをよく読みましょう．
   • gcc (linux) なら -Wall -Wextra -g のオプションは付けてコンパイルしましょう．
   • コンパイルエラーは，メッセージを読めばだいたい解決出来ますし，エラーメッセージが良く分からなくても，そのエラーメッセージをGoogle検索すると解決策がすんなり見つかることが多いです．まずは，自分で色々試してみて，どうしても分からない時にTAや教員を頼りましょう．
4. 開発を補助するツールを積極的に利用してみましょう．
   • 世の中には，Cプログラマを支援するための開発ツールが転がっています．以下は一見の価値ありです．
   • C/C++プログラマのための開発ツール
5. コードをしっかり管理しましょう．
   • 実験が進むと，どのファイルに何を書いたかを把握するのが大変になりますし(デバッグ用のコードを書いていたりしたら尚更)，ちゃんと管理しないとバグを引き起こす原因となります．
   • なるべくバージョン管理システム(Gitを推奨)を利用してコードを管理しましょう．おすすめは，GitHubのプライベートリポジトリを使っての開発です．

ベースとなるソースコードの公開について

• 本ページで示しているソースコードは，以下のURLにて取得できます
  • https://www.coins.tsukuba.ac.jp/~fujita/dsa-jikken/dsa-jikken2.zip

連結リストの実装

以下は，教科書リスト2.2 ~ 2.5を元にした連結リストを実現するC言語プログラムである．ソースコードは，linked_list.h，linked_list.c，main_linked_list.c に分割されている．

ヘッダーファイル linked_list.h

#ifndef INCLUDE_GUARD_LINKED_LIST_H
#define INCLUDE_GUARD_LINKED_LIST_H

typedef struct cell {
  int data;
  struct cell *next;
} Cell;

extern Cell *head;

void insert_cell(Cell *p, int d);
void insert_cell_top(int d);
void delete_cell(Cell *p);
void delete_cell_top(void);
void display(void);

#endif  // INCLUDE_GUARD_LINKED_LIST_H

ソースファイル linked_list.c

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

Cell *head = NULL;

void insert_cell(Cell *p, int d) {
    // ここを埋める
}

void insert_cell_top(int d) {
    Cell *new_cell = (Cell*)malloc(sizeof(Cell));
    new_cell->data = d;
    new_cell->next = head;
    head = new_cell;
}

void delete_cell(Cell *p) {
    // ここを埋める
}

void delete_cell_top(void) {
    // ここを埋める
}

void display(void) {
    // ここを埋める
}

ソースファイル main_linked_list.c

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

int main(void) {
    insert_cell_top(1);
    insert_cell(head, 3);
    insert_cell(head, 2);
    display();

    delete_cell(head);
    display();

    delete_cell_top();
    display();

    return EXIT_SUCCESS;
}

C言語特有の記法について簡単に説明する．

#ifndef INCLUDE_GUARD_LINKED_LIST_H
#define INCLUDE_GUARD_LINKED_LIST_H

// ~~~~~~~~ Header details ~~~~~~~~

#endif  // INCLUDE_GUARD_LINKED_LIST_H

このような記述方法を「インクルードガード」と呼ぶ．

この実験ぐらいの開発規模だったらまだ考えなくて良い話だが，プログラム開発が大規模化すると，あるヘッダファイル A.h を他のヘッダーファイル B.h でインクルードして使うというのが起こり得る．

その際に，このインクルードガードを施しておかないと，A.h と B.h を両方インクルードして使った時に，A.h が2重でインクルードされるので，コンパイルエラーとなる．

このとき，「B.h だけをインクルードすればいいじゃない」と思うかもしれない．確かにそうすれば，2重インクルードを回避できるが，本格的なプログラム開発は，ヘッダファイルも人が目で把握できる量を軽く超えるので，各ヘッダファイルの依存関係を洗って，厳選してインクルードというのは現実的に不可能である．

そのため，このような仕組みが必要となる．なお，C/C++が標準で提供する全てのヘッダーファイルにはインクルードガードが使われている．

「#pragma onceで出来るよ」と思う人もいるかもしれないが，#pragma onceはコンパイラの独自実装であり，標準に含まれた機能ではない．そのため，移植性が求められるソースコードでは使わない方が良い．

extern Cell *head;

グローバル変数を複数ファイルで共有するための宣言．グローバル変数の定義はソースファイル linked_list.c に記述している．コード行数や関数の引数などを教科書のリストと完全一致させるためにグローバル変数としている．

Cell *new_cell = (Cell*)malloc(sizeof(Cell));

Cell サイズ分のメモリ領域を動的に確保し，そのアドレスをポインタ new_cell に格納している． オブジェクト指向的に考えると，Cellのインスタンス化と見なせる．

コンパイルと実行

以下の内容の Makefile を作成する．

ファイル Makefile

linked_list: linked_list.o main_linked_list.o

コマンドラインでmakeコマンドを実行すると，Cコンパイラによって実行ファイルが生成される． 実行ファイル linked_list を実行すると，表示はvoid display(void)関数の実装によるが，例えば以下のような結果が表示される．

$ make
cc    -c -o linked_list.o linked_list.c
cc    -c -o main_linked_list.o main_linked_list.c
cc   linked_list.o main_linked_list.o   -o linked_list
$ ./linked_list
1 2 3
1 3
3
$

課題2-1 (基本課題)

1. セルに整数値を格納する連結リストを実現するプログラムlinked_listを実装せよ．linked_list.cには，最低限以下の関数を定義すること．
2. void insert_cell(Cell *p, int d): セル p の直後に新しいセルを挿入する．
3. void insert_cell_top(int d): リストの先頭に新しいセルを挿入する
4. void delete_cell(Cell *p): セル p の直後のセルを削除する．
5. void delete_cell_top(void): リストの先頭のセルを削除する．
6. void display(void): リストの要素を順に標準出力に表示する．
   • ただし，実行例と同等の書式を用いて要素を標準出力に表示にすること．
   • 要素間を半角スペース1文字で区切って出力すること．
   • 最後の要素を出力した後は，改行を1文字出力すること．
7. 以下の要件を全て満たすことを確認すること．
8. セルをリストの先頭に挿入できること
9. セルを指定したセルの直後に挿入できること
10. 先頭セルを削除できること
11. 指定したセルの直後のセルを削除できること

キューの実装

以下は，教科書リスト 2.9 ~ 2.10 を元にした，リングバッファ (教科書 p.33 2.5.3項) の機能を持つキューを実現するC言語プログラムである． ソースコードは，queue.h，queue.c，main_queue.c に分割されており，queue.h と main_queue.c のみを以下に表示する． すなわち，linked_list.c とは違い，queue.c はノーヒントで実装してみよう．

ヘッダーファイル queue.h

#ifndef INCLUDE_GUARD_QUEUE_H
#define INCLUDE_GUARD_QUEUE_H

typedef struct queue {
   int *buffer;
   int length;
   int front;
   int rear;
} Queue;

Queue *create_queue(int len);
void enqueue(Queue *q, int d);
int dequeue(Queue *q);
void display(Queue *q);
void delete_queue(Queue *q);

#endif  // INCLUDE_GUARD_QUEUE_H

ソースファイル main_queue.c

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

int main(void) {
    int i;
    Queue *test_q = create_queue(10);

    enqueue(test_q, 1);
    enqueue(test_q, 2);
    display(test_q);

    printf("%d\n", dequeue(test_q));
    printf("%d\n", dequeue(test_q));

    for (i = 0; i < 8; i++) {
        enqueue(test_q, i);
    }
    for (i = 0; i < 5; i++) {
        dequeue(test_q);
    }
    for (i = 0; i < 5; i++) {
        enqueue(test_q, 10 + i);
    }
    display(test_q);

    delete_queue(test_q);

    return EXIT_SUCCESS;
}

コンパイルと実行

以下の行を Makefile に加える．

linked_list: linked_list.o main_linked_list.o

queue: queue.o main_queue.o  # added

さらに，

$ make queue

を実行することでコンパイル出来る． 実行ファイル queue を実行すると，以下のような結果が表示される．

$ ./queue
1 2
1
2
5 6 7 10 11 12 13 14
$

課題2-2 (基本課題)

1. リングバッファ (教科書 p.33 2.5.3項) の機能を持つキューを実現するプログラムqueueを実装せよ．queue.c には，最低限以下の関数を定義すること．
   • Queue *create_queue(int len): 容量がlen個のキューを作成・初期化する．作成したQueue型のポインタを返す．
   • void enqueue(Queue *q, int d): キューに整数dを格納する．
   • int dequeue(Queue *q): キューから整数を取り出す．
   • void display(Queue *q): キューの要素を先頭から順に出力する．
     • ただし，実行例と同等の書式を用いて要素を標準出力に表示にすること．
     • 要素間を半角スペース1文字で区切って出力すること．
     • 最後の要素を出力した後は，改行を1文字出力すること．
   • void delete_queue(Queue *q): キューを破棄する．それまでにキューで確保したメモリをすべて開放すること．
2. 以下の要件を全て満たすことを確認すること．
   • キューに整数を1つ格納し，それが取り出せること
   • キューに整数を複数連続して格納し，それが格納した順番で取り出せること
   • キューに格納するデータが配列の末尾と先頭にまたがる場合で，上の 1, 2 が行えること
   • キューに格納するデータが配列の末尾と先頭にまたがる場合と，そうでない場合の両方の状態について，次に示す状態はエラーとして扱う．標準エラー出力にエラーメッセージを表示し，exit関数を用いてプログラムを異常終了させること．
     1. 要素を取り出し、キューが空になった後にさらに要素取り出そうとした時
     2. キューが一杯の時にさらに格納しようとした時
     3. プログラムを異常終了する場合は、以下を呼び出す (stdlib.h で定義されている)
     4. エラーメッセージの文面は任意だが，発生した問題の意味がわかる文が望ましい．

exit(EXIT_FAILURE);

双方向循環リストの実装 (発展課題)

以下は，ダミーセルheadを用いる双方向循環リストを実現するC言語プログラムである． ソースコードは，doublylinked_list.h，doublylinked_list.c，main_doublylinked_list.c に分割されており，doublylinked_list.h と main_doublylinked_list.c のみを以下に表示する． doublylinked_list.c はqueue.c と同様にノーヒントで実装してみよう．

ヘッダーファイル doublylinked_list.h

#ifndef INCLUDE_GUARD_DOUBLYLINKED_LIST_H
#define INCLUDE_GUARD_DOUBLYLINKED_LIST_H

#include <stdbool.h>

typedef struct cell {
    int data;
    bool is_head;
    struct cell *prev;
    struct cell *next;
} Cell;

Cell *CreateCell(int d, bool is_head);
void InsertNext(Cell *this_cell, Cell *p);
void InsertPrev(Cell *this_cell, Cell *p);
void DeleteCell(Cell *this_cell);
Cell *SearchCell(Cell *this_cell, int d);
void Display(Cell *this_cell);
void DisplayReverse(Cell *this_cell);

void ReadFromArray(Cell *this_cell, int *data, unsigned int len);
void WriteToArray(Cell *this_cell, int *data, unsigned int max_len);
void ReadFromFile(Cell* this_cell, const char *filename);
void WriteToFile(Cell* this_cell, const char *filename);

#endif  // INCLUDE_GUARD_DOUBLYLINKED_LIST_H

ソースファイル main_doublylinked_list.c

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

int main(void) {
    Cell* head = CreateCell(0, true);
    Cell* elem;

    InsertNext(head, CreateCell(2, false));
    InsertNext(head, CreateCell(1, false));
    InsertPrev(head, CreateCell(5, false));
    Display(head);
    DisplayReverse(head->prev);

    elem = SearchCell(head, 2);
    InsertNext(elem, CreateCell(3, false));
    Display(head);

    elem = SearchCell(head, 5);
    DeleteCell(elem);
    Display(head);

    DeleteCell(head->next);
    DeleteCell(head->prev);
    DeleteCell(head->next);
    Display(head);

    return EXIT_SUCCESS;
}

コンパイルと実行

以下の行を Makefile に加える．

linked_list: linked_list.o main_linked_list.o

queue: queue.o main_queue.o

doublylinked_list: doublylinked_list.o main_doublylinked_list.o  # added

さらに，

$ make doublylinked_list

を実行することでコンパイル出来る． 実行ファイル doublylinked_list を実行すると，以下のような結果が表示される．

$ ./doublylinked_list
1 2 5
5 2 1
1 2 3 5
1 2 3

$

課題2-3 (発展課題)

1. セルに整数値を格納する双方向リストを実現するプログラム doublylinked_list を実装せよ．doublylinked_list.c には，最低限以下の関数を定義すること．
   • Cell *CreateCell(int d, bool is_head): セルの生成および初期化を行い，Cell型のポインタを返す．生成したセルが head (ダミーセル) かを識別するためのフラグ is_head がセットされる．
   • void InsertNext(Cell *this_cell, Cell *p): セルthis_cell の次に，セル p を挿入する．
   • void InsertPrev(Cell *this_cell, Cell *p): セル this_cell の前に，セル p を挿入する．
   • void DeleteCell(Cell *this_cell): this_cell をリストから削除する．
   • Cell *SearchCell(Cell *this_cell, int d): 与えられた整数 d を保持しているセルを this_cell から順に探し，見つかったらそのセルを返す．見つからなければ NULL を返す．
   • void Display(Cell *this_cell): this_cellから末尾に向けて，要素を順に標準出力へ表示する．
     • ただし，実行例と同等の書式を用いて要素を標準出力に表示にすること．
     • 要素間を半角スペース1文字で区切って出力する．
     • ダミーセルは表示しない．
     • 最後の要素を出力した後は，改行を1文字出力する．
   • void DisplayReverse(Cell *this_cell): this_cellから先頭に向けて，要素を逆順に標準出力へ表示する．
     • 書式はDisplay()と同じとすること．
2. 以下の要件を全て満たすことを確認すること．
   • セルを，リストの先頭，末尾，中間に挿入できること
   • 先頭セル，末尾のセル，中間のセルが削除できること
   • SearchCell()関数によって，先頭セル，末尾のセル，中間のセルを探せること
3. doublylinked_list.c に，配列のデータを読み込みリストに追加する関数 ReadFromArray()，配列にリストの要素を書き出す関数 WriteToArray()，ファイルからデータを読み込みリストに追加する関数 ReadFromFile()、ファイルにリストの要素を書き出す関数 WriteToFile() を追加し，作成した関数が正しく動作することを，例を使って示しなさい．
   • void ReadFromArray(Cell *this_cell, int *data, unsigned int len): セルthis_cellの後に，長さlenの配列dataに含まれている要素を追加する関数．
   • void WriteToArray(Cell *this_cell, int *data, unsigned int max_len): セルthis_cellから末尾までに含まれる要素を，長さがmax_lenである配列dataに書き込む関数．
     • ただし，リストの長さがmax_lenを超える場合はエラーとして扱う．標準エラー出力にエラーメッセージを表示し，exit関数を用いてプログラムを異常終了させること．
     • エラーメッセージの文面は任意だが，発生した問題の意味がわかる文が望ましい．
   • void WriteToFile(Cell* this_cell, const char *filename): セルthis_cellから末尾までに含まれる要素を filenameで指定されたテキストファイルへ書き出す関数．
     • 出力したファイルを再びReadFromFile関数で読み込めるように，書式を合わせてファイルに出力すること
   • void ReadFromFile(Cell* this_cell, const char *filename): filenameで指定されたテキストファイルから内容を読み込み，セルthis_cellの後にファイルから得られた要素を追加する関数．
     • 入力ファイルは1行毎に1つの要素（数字）が記入されたファイルである．複数行で構成されている場合もある．
     • Display関数の書式とは異なることに気をつけること
   • その他，エラーが発生しプログラムの続行が難しい場合は，標準エラー出力にエラーメッセージを表示し，exit関数を用いてプログラムを異常終了させること．
     • エラーメッセージの文面は任意だが，発生した問題の意味がわかる文が望ましい．

要件確認についての注意事項

要件確認するためには，各自で適宜 main 関数の中身を書き換え，テストパターンを追加してください．

また，レポートには，

• 「プログラムの入力となるデータが何で，それがプログラムのどの部分でどのようなロジックで処理されているため，このような実行結果が得られるから，要件を満たしている」という説明文
• その実行結果

の両方を書いてください．そうでないと，レポートの読み手(採点者)は，要件を満たすことを本当に確認出来ているのか判断出来ません．

提出物について

自動採点の注意点

• レポートの自動採点を行うため，以下の指示に従ってプログラムを作成，提出すること．
• 関数名，引数，戻り値はサンプルから変更しないこと．
• プログラムの出力もサンプルから変更しないこと．

提出ファイル一覧

• report2.pdf （レポート）
• Makefile
• main_linked_list.c
• linked_list.c
• linked_list.h
• main_queue.c
• queue.c
• queue.h
• main_doublylinked_list.c （発展課題）
• doublylinked_list.c （発展課題）
• doublylinked_list.h （発展課題）

提出ファイルの構成

• ディレクトリ class2 を作成して，その中に上記ファイルを配置すること．
• class2 を ZIP で圧縮した class2.zip ファイルを manaba に提出すること．

（class2.zip）の構造）
class2/
  +-report2.pdf
  +-Makefile
  +-main_linked_list.c
  +-...

提出締切

• 2023年10月28日（月）13:30
• 前日・前々日は全学停電中なので注意してください
• Manabaは停電の影響を受けませんが，一部計算機は止まっている場合があります