Programming C ex09

演習問題１（リストの実装練習）

プログラム /home/course/prog1/public_html/2026/ex/ex09/prog00.c、
ヘッダファイル /home/course/prog1/public_html/2026/ex/ex09/prog00.h は、ハンドアウトLec09-19〜22 (pp.130-131) に出てきた、リストの基本操作を行うプログラムである。
これを各自prog00.c, prog00.hとして自分のディレクトリにコピーし、ハンドアウトLec09-23 (p.131) 通りの動作を行う事を確認せよ。（これらのファイルは提出しない）

さて、ハンドアウトでは、リストのデータとして int型の構造体メンバー key を考えたが、もう少し実用的なデータを扱うプログラムに変更する。
今回の演習では、リストのデータとして、学生のID番号 (id)、姓 (surname)、名 (givenname)、及びGPA (gpa)を格納するRecord型構造体を考えてみる。学生のID番号は正であるとする。

この問題ではプログラム本体prog01.cとともにヘッダファイルstudlist.hも作成する。studlist.hは続く問題2でも変更なしでそのまま使用する。

(提出ファイル名: prog01.c, studlist.h)

手順は以下の通り：

prog00.h と以下の手順を基に、studlist.hの空欄を埋めて、ヘッダファイルを完成させなさい。

手順：

学生のID番号 (id)、姓 (surname)、名 (givenname)、及びGPA (gpa)を格納するRecord型構造体を宣言する(すでに宣言済み)。
Record型の構造体変数 data をデータとするリストを扱えるように、node構造体を宣言する。

studlist.h

/* Record構造体の宣言 */
typedef struct {
  int id;
  char surname[12];
  char givenname[12];
  double gpa;
} Record;

/* node構造体の宣言 */
typedef ________ ________ *NodePointer;
struct node {
  ________ data;
  ________ next;
};

/* プロトタイプ宣言 */
NodePointer insert(Record); /* 新しいノード挿入関数 */
NodePointer finditem(int); /* リスト内の重複するノード検索関数 */
void listprint(void); /* リスト内データの表示関数 */
NodePointer make_1node(Record, NodePointer); /* 新しいノード作成関数 */

/* グローバル変数 head */
NodePointer head;

prog00.c と以下の手順を基に、prog01.cの空欄を埋めて、プログラムを完成させなさい。

手順：

ヘッダファイル(studlist.h)をインクルードする。
main 関数
- 空のリスト（headのみ）を作成し、listprint 関数で現在のリストを出力する。なお、headノードを作る際、ノードの内容は意味のある情報でなくてよいので、宣言されているRecord型の変数rをmake_1node 関数の１つ目の引数として渡している。
- キーボードから入力されるデータ（ID番号、姓、名、GPA）に基づいて、insert 関数を用いて順次新しいノードをリストに挿入する。その後、毎回 listprint 関数でリスト全体を出力する。
- なお、insert 関数が NULL を返した場合は、ID番号に対するメッセージを表示する。
insert 関数
- Record型の引数をとる。
- finditem 関数を用いて構造体変数 data 内のメンバーidが重複するノードがリスト中にあるか調べる。
- 重複するノードがリスト中にある場合は挿入を行わず NULL を返す。
- 重複してない場合は、make_1node関数を用いて新しいノードを作成し、headノードの下に新しいノードをつなぐ。
listprint 関数
- headの次のノードからNULLの前まで、構造体変数 data 内のデータを（ID番号、姓、名、GPA）の順で順次出力する。
- 書式は実行例を参考にすること（厳密に一致させる必要はない。書式指定については下の注記も参照のこと）。
finditem 関数
- int型の引数をとる。
- リスト内の構造体変数 data のメンバー id の値と同じ値があるか、headからNULLの一つ前までのノードを検索する。
- 見つかった場合はその一つ手前のノードを指すポインタが戻り値となり、見つからなかった場合はNULLを戻り値とする。
make_1node 関数
- １つ目の引数はRecord型をとり、2つ目の引数はNodePointer型をとる。
- malloc関数を用いて、ノード1個分のメモリを割り当てる。
- node構造体のメンバーであるdataとnextに引数の値をセットする。

prog01.c

#include <stdio.h>
#include <stdlib.h>
#include ________

int main()
{
  Record r;
 
  /* リストの初期化 */
  /* headノードの内容は意味のある情報でなくてよい */
  r.id = 0;
  head = make_1node( r,________);

  listprint();
  
  /* 新しいノードをリストに追加する */
  /* CTL+D でループを抜ける */
  while (1) {
    printf("Insert new student data: (ID Surname Givenname GPA) -> ");
    
    if (scanf("%d %s %s %lf", ________, ________, ________, ________) != 4) {
      printf("\n");
      break;
    }
    if (insert(________) == NULL) {
      printf("ID %d is already on the list!\n", ________);
    }
    listprint();
  }
  printf("\n");
  return 0;
}

NodePointer insert(Record r)
{
  NodePointer newnode;

  if (finditem(________) == NULL) { /* 重複するノードの検索 */
    newnode = make_1node(________, ________); /* headの下に新しいノードを作成 */
    ________ = newnode; /* headの下に新しいノードをつなぐ */
    return newnode;
  }
  else return NULL;
}

void listprint(void)
{
  NodePointer n;

  printf("Head - \n");
  for(n = ________; ________; n = ________){ /* headの次のノードからNULLの前までたどる */
    printf("  %7d %-12s %-12s %5.2f\n", ________, ________, ________, ________);
  }
  printf("\n");
}

NodePointer finditem(int sid)
{
  NodePointer n;

  for (n = ________; ________; n = ________) { /* headからNULLの一つ前までのノードをたどる */
    if (________ == sid) return ________; /* sidと同じ値が見つかったら一つ手前のノードを指すポインタを返す */
  }
  return NULL;
}

NodePointer make_1node(Record r, NodePointer p)
{
  NodePointer n;

  if ((n = (________)malloc(________) ) == NULL) { /* メモリ確保 */
    printf("Error in memory allocation\n");
    exit(8);
  }

  /* dataとnextに引数の値をセットする */
  n->data = ________; 
  n->next = ________; 
  return n;
}

実行例

% ./a.out
Head -

Insert new student data: (ID Surname Givenname GPA) -> 1301001 AIZU Taro 3.5
Head -
  1301001 AIZU         Taro          3.50

Insert new student data: (ID Surname Givenname GPA) -> 1301022 BANDAI Hanako 3.15
Head -
  1301022 BANDAI       Hanako        3.15
  1301001 AIZU         Taro          3.50

Insert new student data: (ID Surname Givenname GPA) -> 1301033 TSURUGA Shirou 2.9
Head -
  1301033 TSURUGA      Shirou        2.90
  1301022 BANDAI       Hanako        3.15
  1301001 AIZU         Taro          3.50  
      
Insert new student data: (ID Surname Givenname GPA) -> Ctrl-D
%

[文字列表示の書式指定について]
実行例の氏名表示の部分のように文字列の長さの上限が決まっていて、その範囲で表示すべき文字数に変化がある場合、 %12s のように%sに対する桁数指定を行うと、指定分の桁数の表示幅が確保されて、その桁数内での右詰めの表示になる。また、%-12s のように桁数指定値に負号を付けると左詰めとなる（表示例ではこの方法を用いている）。printf関数の桁数に関する書式指定についてはハンドアウトp.16のLec03-14で説明されている%dについての内容が%sに対しても適用できる。

演習問題２（リストの拡張）

prog01.cを prog02.cにコピーし、 prog02.cに以下のような機能を追加したプログラムにせよ。最初に、/home/course/prog1/public_html/2026/ex/ex09/Student.txtを自分のディレクトリにコピーしなさい。

(提出ファイル名: prog02.c)

ファイルからのデータ読み取り機能
- 起動時にStudent.txtからデータを読み取り、リストに順次挿入する。ファイルの最後まで終わったら関数listprint() で一度リスト全体を表示する。
- ファイルからのデータ入力と表示の終了後は、prog01.cと同じくキーボードからのデータとリストへの追加が行えるようにすること。ID番号が重複していた場合の動作も元のまま残すこと。
ノード挿入位置の変更
- 関数 insert()を修正して、新しいノードをリストの先頭（head の次）ではなくリストの最後に挿入するようにする。具体的には以下の通りである。
- 関数 insert() では、入力されたID番号が既にリスト中にあるか finditem 関数を使ってチェックし、有った場合は前と同様に挿入を行わず NULL を返す。無ければ、ノードを最後までたどってリストの最後に挿入し、挿入したノードへのポインタを返す。
ノード数のカウント
- 関数 listprint()を修正して、ノード内容の一覧表示の後にノードの数（Headは含まない）を表示するようにする。
なお、finditem関数には手を加えない。また外部変数も追加しないこととする。

prog01.c を prog02.c に、コピーしてから、prog02.cを修正すると良い。問題1で使用したstudlist.h をそのまま用いて、変更する必要はない。

ヒント：ファイルからのデータ読み取り機能とノード挿入位置の変更の両者を一括して解決しようとすると、エラーがあった場合、どちらに問題があるのか切り分けが難しくなるので、一方の処理が完成してから、もう一方の処理を加えるようにすると良い。

実行例

% ./a.out
Head - 
  1301001 AIZU         Taro         3.50
  1301022 BANDAI       Hanako       3.15
  1301033 TSURUGA      Shirou       2.90
    .....（中略）
  1301150 KITAKATA     Testuo       3.55
  1301164 SUKAGAWA     Yoshiko      3.20
  1301200 ASHINOMAKI   Masaru       3.00
14 nodes exist in the list.

Insert new student data: (ID Surname Givenname GPA) -> 1301001 AIZU Taro 3.5
ID 1301001 is already on the list!
Head - 
  1301001 AIZU         Taro         3.50
  1301022 BANDAI       Hanako       3.15
  1301033 TSURUGA      Shirou       2.90
    .....（中略）
  1301150 KITAKATA     Testuo       3.55
  1301164 SUKAGAWA     Yoshiko      3.20
  1301200 ASHINOMAKI   Masaru       3.00
14 nodes exist in the list.

Insert new student data: (ID Surname Givenname GPA) -> 1301100 IKKI Goro 3.0
Head - 
  1301001 AIZU         Taro         3.50
  1301022 BANDAI       Hanako       3.15
  1301033 TSURUGA      Shirou       2.90
    .....（中略）
  1301150 KITAKATA     Testuo       3.55
  1301164 SUKAGAWA     Yoshiko      3.20
  1301200 ASHINOMAKI   Masaru       3.00
  1301100 IKKI         Goro         3.00
15 nodes exist in the list.

Insert new student data: (ID Surname Givenname GPA) -> Ctrl-D
%

演習問題３（削除の実装）

演習問題２のプログラムにノードを削除する機能を追加する。

prog02.c を prog03.c に、studlist.h を studlist03.h にコピーしてから、prog03.cとstudlist03.h を適宜修正して作成すること。今度はヘッダファイルも修正する必要があるので注意すること。

(提出ファイル名: prog03.c, studlist03.h)

delete 関数を追加する。
1. リストを削除する方法については、以下の説明を参考すること。
  （説明はここ：この説明はハンドアウトハンドアウトLec09-24〜28 (pp.131-132) に記述があった）
  なお、どうしても分からない場合はスタッフ等に聞くこと。
2. delete 関数のプロトタイプは
```
NodePointer delete(int);
```
  とし、以下のような動作を行う。
  1. 引数で指定された数をID番号とみなし、リスト内の構造体変数 data のメンバー id が同じ値をもつノードを検索する
  2. 一致するノードが存在すればそのノードを削除し、一つ前のノードポインタをリターンする
  3. 一致するノードが存在しなければ、 NULL をリターンする。
studlist03.hに delete 関数のプロトタイプ宣言を追加する。
演習問題２のプログラムにおけるファイルからのデータ読み取りが済んだ後で、実行例のように対話的にノードの追加または削除を選んで実行可能になるように、main 関数を修正する。

ノードの追加は演習問題２のプログラムと同じく、insert 関数を用いる
ノードの削除はdelete 関数を用いる。なお、削除すべきノードが存在しない場合はその旨のメッセージを表示すること
Ctrl-Dの入力で終了させること

実行例

% ./a.out
Head - 
  1301001 AIZU         Taro         3.50
  1301022 BANDAI       Hanako       3.15
  1301033 TSURUGA      Shirou       2.90
    .....（中略）
  1301150 KITAKATA     Testuo       3.55
  1301164 SUKAGAWA     Yoshiko      3.20
  1301200 ASHINOMAKI   Masaru       3.00
14 nodes exist in the list.

Choose operation (1: Insert, 0: Delete, ^D: Finish) -> 1
Insert new student data: (ID Surname Givenname GPA) -> 1301100 IKKI Goro 3.00
Head -
  1301001 AIZU         Taro         3.60
  1301022 BANDAI       Hanako       3.15
  1301033 TSURUGA      Shirou       2.90
    .....（中略）
  1301150 KITAKATA     Testuo       3.55
  1301164 SUKAGAWA     Yoshiko      3.20
  1301200 ASHINOMAKI   Masaru       3.00
  1301100 IKKI         Goro         3.00
15 nodes exist in the list.

Choose operation (1: Insert, 0: Delete, ^D: Finish) -> 0
Delete ID -> 1209001
ID 1209001 is not found.
Head -
  1301001 AIZU         Taro         3.50
  1301022 BANDAI       Hanako       3.15
  1301033 TSURUGA      Shirou       2.90
    .....（中略）
  1301150 KITAKATA     Testuo       3.55
  1301164 SUKAGAWA     Yoshiko      3.20
  1301200 ASHINOMAKI   Masaru       3.00
  1301100 IKKI         Goro         3.00
15 nodes exist in the list.

Choose operation (1: Insert, 0: Delete, ^D: Finish) -> 0
Delete ID -> 1301022
Head - 
  1301001 AIZU         Taro         3.50
  1301033 TSURUGA      Shirou       2.90
    .....（中略）
  1301150 KITAKATA     Testuo       3.55
  1301164 SUKAGAWA     Yoshiko      3.20
  1301200 ASHINOMAKI   Masaru       3.00
  1301100 IKKI         Goro         3.00
14 nodes exist in the list.

Choose operation (1: Insert, 0: Delete, ^D: Finish) -> Ctrl-D
%

[エラー処理について]
この問題の実行例では、プログラムの基本的な想定通りの入力しか試していません。例えばノードの追加、削除、プログラムの終了を選ぶところで、それぞれの操作を指定するコマンドだけを試しています。しかし、開発者が予期していなかった操作を使用者がしてしまうこともあり得ますので、実用的なプログラムではそのような場合に備えてのエラー処理が重要になります。さらに、このプログラムではループを使って繰り返し処理をしているため、一つ前の操作で予期しない入力があると次の操作で問題が顕在化する場合も出てきます。特に、scanf関数ではキーボードからの入力が一旦格納させる入力バッファ（これはプログラム本体ではなくOSやターミナルが管理します）との相互作用で問題が生じます。この問題では上で指示された仕様が満たされていればよく、エラー処理については問いませんが、解答例ではそこまで考慮したものを準備していますので、より深く理解したい人は解答例の公開後に内容をよく見てみてください。
具体的にはChoose operationの入力部分で数値入力が必要とされるが、間違ってアルファベット等の文字が入力するとプログラムが暴走する。回答例ではエラー処理としてrewind()関数を使用プログラムを提示している。なお、今回の演習の回答としてrewind()関数を使用しなくても良いとする。

演習問題４（降順/昇順の挿入）

演習問題２のプログラムを改良して、ノードをIDの降順、または昇順に挿入する機能を追加する。

prog02.c を prog04.c に、studlist03.h を studlist04.h にコピーしてから、prog04.cとstudlist04.h を適宜修正して作成すること。

(提出ファイル名: prog04.c, studlist04.h)

基本的には、

コマンドライン引数で指定されたファイルからIDを読み込み
ID順になるようにリストを作成し
標準入力から入力された新規データを、IDの順序を維持するようにリストに挿入する

プログラムとする。ただし、

ファイル名はコマンドライン引数で与えるようにし、ファイル名の指定がない場合は Student.txt から読み取る
IDの並べ替えは、ユーザが指定する順序（降順descending (d) または昇順ascending (a)）に従う。（降順は 5,4,3,2,1 のような大→小の順序、昇順は 1,2,3,4,5 のような小→大の順序をいう））
ID入力の前にはIDリストの内容を表示する
Ctrl-D が入力されるまで、繰り返し、IDの入力を受け付ける

ようにすること。
また、このプログラムではリストにデータを挿入する関数 NodePointer insert_sort(Record, char); を作成して利用せよ。ここで、insert_sort 関数の第一引数は入力ノードを示す引数、第二引数は降順か昇順かを指定する引数である。
この関数は、リストの先頭からIDを調べていき、

昇順の場合：入力ノードのID番号より、大きいID番号を持つノードの前
降順の場合：入力ノードのID番号より、小さいID番号を持つノードの前

に入力ノードを挿入する関数である。この関数を用いると指定された並べ替えが実現できるが、リストの末尾の処理に気をつけて作成すること。
なお科目の指定と降順/昇順の指定は、実行例のように最初にキーボードから与えるものとする。

実行例

% ./a.out
Enter sort mode (d:descending / a:ascending) -> d
Head - 
  1301200 ASHINOMAKI   Masaru       3.00
  1301164 SUKAGAWA     Yoshiko      3.20
  1301150 KITAKATA     Testuo       3.55
  1301123 SOUMA        Hikaru       3.80
  1301099 IWAKI        Youko        3.90
    .....（中略）
  1301007 FUKUSHIMA    Ichiro       3.60
  1301004 BANGE        Jiro         3.40
  1301001 AIZU         Taro         3.50
14 nodes exist in the list.

Insert new student data: (ID Surname Givenname GPA) -> 1301100 IKKI Goro 3.0
Head - 
  1301200 ASHINOMAKI   Masaru       3.00
  1301164 SUKAGAWA     Yoshiko      3.20
  1301150 KITAKATA     Testuo       3.55
  1301123 SOUMA        Hikaru       3.80
  1301100 IKKI         Goro         3.00
  1301099 IWAKI        Youko        3.90
    .....（中略）
  1301001 AIZU         Taro         3.50
15 nodes exist in the list.

Insert new student data: (ID Surname Givenname GPA) -> Ctrl-D
%

% ./a.out
Enter sort mode (d:descending / a:ascending) -> a
Head - 
  1301001 AIZU         Taro         3.50
  1301004 BANGE        Jiro         3.40
  1301007 FUKUSHIMA    Ichiro       3.60
    .....（中略）
  1301150 KITAKATA     Testuo       3.55
  1301164 SUKAGAWA     Yoshiko      3.20
  1301200 ASHINOMAKI   Masaru       3.00
14 nodes exist in the list.

Insert new student data: (ID Surname Givenname GPA) -> 1301003 INAWASHIRO Fumiko 3.7
Head - 
  1301001 AIZU         Taro         3.50
  1301003 INAWASHIRO   Fumiko       3.70
  1301004 BANGE        Jiro         3.40
  1301007 FUKUSHIMA    Ichiro       3.60
    .....（中略）
  1301150 KITAKATA     Testuo       3.55
  1301164 SUKAGAWA     Yoshiko      3.20
  1301200 ASHINOMAKI   Masaru       3.00
15 nodes exist in the list.

Insert new student data: (ID Surname Givenname GPA) -> Ctrl-D
%

プログラミングＣ 第９回 演習問題

プログラミングＣ
第９回演習問題