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

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

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

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

1. prog00.h と以下の手順を基に、studlist.hの空欄を埋めて、ヘッダファイルを完成させなさい。
手順：
• 学生のID番号 (id)、姓 (surname)、名 (givenname)、及び年齢 (age)を格納するRecord型構造体を宣言する(すでに宣言済み)。
• Record型の構造体変数 data をデータとするリストを扱えるように、node構造体を宣言する。

studlist.h

/* Record構造体の宣言 */
typedef struct {
  int id;
  char surname[12];
  char givenname[12];
  int age;
} 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;

2. prog00.c と以下の手順を基に、prog01.cの空欄を埋めて、プログラムを完成させなさい。
手順：
• ヘッダファイル(studlist.h)をインクルードする。
• main 関数
  • 空のリスト（headのみ）を作成し、listprint 関数で現在のリストを出力する。なお、headノードを作る際、ノードの内容は意味のある情報でなくてよく、宣言されているRecord型の変数をmake_1node 関数の１つ目の引数として渡すこと。
  • キーボードから入力されるデータ（ID番号、姓、名、年齢）に基づいて、insert 関数を用いて順次新しいノードをリストに挿入する。その後、毎回 listprint 関数でリスト全体を出力する。
  • なお、insert 関数が NULL を返した場合は、ID番号に対するメッセージを表示する。
• insert 関数
  • Record型の引数をとる。
  • finditem 関数を用いて構造体変数 data 内のメンバーidが重複するノードがリスト中にあるか調べる。
  • 重複するノードがリスト中にある場合は挿入を行わず NULL を返す。
  • 重複してない場合は、make_1node関数を用いて新しいノードを作成し、headノードの下に新しいノードをつなぐ。
• listprint 関数
  • headの次のノードからNULLの前まで、構造体変数 data 内のデータを（ID番号、姓、名、年齢）の順で順次出力する。
  • 書式は実行例を参考にすること（厳密に一致させる必要はない。書式指定については下の注記も参照のこと）。
• 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;
  int i;
 
  /* リストの初期化 */
  head = make_1node( ________, NULL );

  listprint();
  
  /* 新しいノードをリストに追加する */
  /* CTL+D でループを抜ける */
  while (1) {
    printf("Insert new student data: (ID Surname Givenname Age) -> ");
    
    if (scanf("%d %s %s %d", ________, ________, ________, ________) != 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 %d\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に引数の値をセットする */
  ________ = ________; 
  ________ = ________; 
  return n;
}

% ./a.out
Head -

Insert new student data: (ID Surname Givenname Age) -> 1301001 AIZU Taro 19
Head -
  1301001 AIZU         Taro         19

Insert new student data: (ID Surname Givenname Age) -> 1301022 BANDAI Hanako 22
Head -
  1301022 BANDAI       Hanako       22
  1301001 AIZU         Taro         19

Insert new student data: (ID Surname Givenname Age) -> 1301033 TSURUGA Shirou 21
Head -
  1301033 TSURUGA      Shirou       21
  1301022 BANDAI       Hanako       22
  1301001 AIZU         Taro         19

Insert new student data: (ID Surname Givenname Age) -> 1301001 AIZU Jiro 18
ID 1301001 is already on the list!
Head -
  1301033 TSURUGA      Shirou       21
  1301022 BANDAI       Hanako       22
  1301001 AIZU         Taro         19
      
Insert new student data: (ID Surname Givenname Age) -> Ctrl-D
%