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

ATTENTION!

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

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

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

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

連結リストの実装

以下は，教科書リスト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;
}

サンプルコード一式はここからダウンロード出来る．

コマンドラインでやりたい人は，

mac$ wget https://www.coins.tsukuba.ac.jp/~rkobayashi/lecture/dsa-jikken/samples/linked_list.tar.gz

でダウンロードして，

mac$ tar -xvzf linked_list.tar.gz

すれば解凍出来る．

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)関数の実装によるが，例えば以下のような結果が表示される．

mac$ 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
mac$ ./linked_list
1 2 3
1 3
3
mac$

課題2-1 (基本課題)

1. セルに整数値を格納する連結リストを実現するプログラム linked_list を実装せよ．linked_list.c には，最低限以下の関数を定義すること．
   • void insert_cell(Cell *p, int d): セル p の直後に新しいセルを挿入する．
   • void insert_cell_top(int d): リストの先頭に新しいセルを挿入する
   • void delete_cell(Cell *p): セル p の直後のセルを削除する．
   • void delete_cell_top(void): リストの先頭のセルを削除する．
   • void display(void): リストの要素を順に標準出力する．
2. 以下の要件を全て満たすことを確認すること．
   • セルを，リストの先頭に挿入できること
   • セルを，指定したセルの直後に挿入できること
   • 先頭セルを削除できること
   • 指定したセルの直後のセルを削除できること

キューの実装

以下は，教科書リスト 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) {
  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));

  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 を実行すると，以下のような結果が表示される．

mac$ ./queue
Queue created!
1 2
1
2
Queue deleted!
mac$

課題2-2 (基本課題)

1. リングバッファ (教科書 p.33 2.5.3項) の機能を持つキューを実現するプログラム queue を実装せよ．queue.c には，最低限以下の関数を定義すること．
   • Queue *create_queue(int len): サイズ len のキューを作成・初期化する．処理が完了したら，Queue created!を標準出力し，Queue型のポインタを返す．
   • void enqueue(Queue *q, int d): キューに整数を格納する．
   • int dequeue(Queue *q): キューから整数を取り出す．
   • void display(Queue *q): キューの要素を先頭から順に出力する．
   • void delete_queue(Queue *q): キューを破棄する．処理が完了したら，Queue deleted!を標準出力する．
2. 以下の要件を全て満たすことを確認すること．
   • キューに整数を1つ格納し，それが取り出せること
   • キューに整数を複数連続して格納し，それが格納した順番で取り出せること
   • キューに格納するデータが配列の末尾と先頭にまたがる場合で，上の 1, 2 が行えること
   • キューに格納するデータが配列の末尾と先頭にまたがる場合と，そうでない場合の両方の状態について，1) 要素を取り出し、キューが空になった後にさらに要素取り出そうとした時，2) キューが一杯の時にさらに格納しようとした時，その旨を標準エラー出力すること．
     • キューが空の時，キューが一杯の時の処理は，以下を参考にしてください．
       • dequeue() の戻り値を，各自適切に設定し，その旨をレポートに記載する
       • プログラムを終了する場合は、以下を呼び出す (stdlib.h で定義されている)

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

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

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

  elem = SearchCell(head, 5);
  DeleteCell(elem);
  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 を実行すると，以下のような結果が表示される．

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

課題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 から順に出力する
2. 以下の要件を全て満たすことを確認すること．
   • セルを，リストの先頭，末尾，中間に挿入できること
     • どのセルをリストの先頭とするかは各自で定義すること．教科書や課題のサンプルコードでは，慣例的に head セルを用意し，head セルの next が指すセルを先頭セル，head セルの prev が指すセルを末尾セルとして扱っている．
   • 先頭セル，末尾のセル，中間のセルが削除できること
   • 生成しただけで挿入していないセルがリストに繋がれていないことをメッセージとして出力すること
   • SearchCell()関数によって，先頭セル，末尾のセル，中間のセルを探せること
3. 配列のデータを読み込みリストに追加する関数 ReadFromArray()、配列にリストの要素を書き出す関数 WriteToArray()、ファイルからデータを読み込みリストに追加する関数 ReadFromFile()、ファイルにリストの要素を書き出す関数 WriteToFile() を追加し，作成した関数が正しく動作することを，例を使って示しなさい．

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

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

また，レポートには，

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

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

提出締切

2022年10月24日（月）13:30