プログラミングC
第9回 演習問題

A問題(50点)

演習問題1(リストの実装練習)

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

さて、ハンドアウトでは、リストのデータとして int型の構造体メンバ key を考えたが、 もう少し実用的なデータを扱うプログラムに変更する。

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

手順は以下の通り:
  1. prog00.hstulist01.h という名前でコピーし、以下の変更を加える
    1. node の宣言の前に次の宣言を追加する。これは学生のID番号、姓 (Surname)、名 (Given name)、クラスを格納するRecord型構造体の宣言である:
      typedef struct {
        int id;
        char surname[12];
        char givenname[12];
        char class[3];
      } Record;
    2. node構造体の宣言を以下のように変更することで、 Record型の構造体変数 data をデータとするリストを扱えるようにする。
      typedef struct node *NodePointer;
      struct node {
        Record      data;
        NodePointer next;
      };
    3. 必要に応じてヘッダ中の関数プロトタイプ宣言(戻り値、引数の型)を修正する(下記の関数説明参照)。

  2. プログラム prog00.cprog01.c という名前にコピーし、その各部を次のように修正する:
    1. #include "prog00.h"#include "stulist01.h"に書き換える
    2. 関数 insert() の引数は Record型とし、関数の中身もそれに応じて変更する。 これに伴い、関数 make_1node() の1つ目の引数もRecord型になる。 prog00.c と同様に、finditem() 関数を用いてデータのID番号が重複するノードがリスト中にあるか調べ、 重複している場合は挿入を行わず NULL を返す。
    3. 関数 finditem() は int型の引数をとり、構造体変数 data のメンバ id に同じ値があるかリストを検索する。 見つかった場合はその一つ手前のノードを指すポインタが戻り値となり、 見つからなかった場合は NULL を戻り値とする。
    4. 関数 listprint() は、構造体変数 data 内のデータを(クラス, ID番号, 姓, 名)の順で順次出力する。
      書式は実行例を参考にすること(厳密に一致させる必要はない。書式指定については下の注記も参照のこと)。
    5. main() ではループを用いたノードの自動生成をやめ、空のリスト(headのみ)を作成後に、 キーボードから入力されるデータ(クラス, ID番号, 姓, 名)に基づいて、関数 insert() を用いて順次新しいノードを リストに挿入する。関数 insert() が NULL を返した場合はメッセージを表示する。 その後毎回関数 listprint() でリスト全体を出力する。
    6. キーボードから Ctrl-D が入力されたらプログラムを終了する。


    実行例は以下の通り
    % ./a.out
    Head -
    
    Insert new data: (class ID name) -> C1 1301001 AIZU Taro
    Head -
       C1 1301001 AIZU         Taro        
    
    Insert new data: (class ID name) -> C2 1301022 BANDAI Hanako
    Head -
       C2 1301022 BANDAI       Hanako      
       C1 1301001 AIZU         Taro  
    
    Insert new data: (class ID name) -> C4 1301033 TSURUGA Shirou
    Head -
       C4 1301033 TSURUGA      Shirou      
       C2 1301022 BANDAI       Hanako      
       C1 1301001 AIZU         Taro
    
    Insert new data: (class ID name) -> C1 1301001 AIZU Jiro
    ID 1301001 is already on the list!
    Head -
       C4 1301033 TSURUGA      Shirou      
       C2 1301022 BANDAI       Hanako      
       C1 1301001 AIZU         Taro
          
    Insert new data: (class ID name) -> Ctrl-D
    % 
[文字列表示の書式指定について]
実行例の氏名表示の部分のように文字列の長さの上限が決まっていて、その範囲で表示すべき文字数に変化がある場合、 %12s のように%sに対する桁数指定を行うと、指定分の桁数の表示幅が確保されて、その桁数内での右詰めの表示になる。また、%-12s のように桁数指定値に負号を付けると左詰めとなる(表示例ではこの方法を用いている)。printf関数の桁数に関する書式指定についてはハンドアウトp16のLec03-14で説明されている%dについての内容が%sに対しても適用できる。

B問題

演習問題2(リストの拡張)

prog01.c を修正して、以下のような機能を追加したプログラムにせよ。

prog01.cprog02.c に、stulist01.hstulist02.h にコピーしてから、prog02.cを適宜修正して作成する。stulist02.h は元のstulist01.h が問題1で完成していればコピーしたものをそのまま用いてよく、変更する必要はない。

ヒント:ファイルからのデータ読み取り機能とノード挿入位置の変更の両者を一括して 解決しようとすると、エラーがあった場合、どちらに問題があるのか切り分けが難しくなるので、一方の処理が完成してから、もう一方の処理を加えるようにすると良い。
(提出ファイル名: prog02.c, stulist02.h)
% ./a.out
Head - 
   C1 1301001 AIZU         Taro        
   C2 1301022 BANDAI       Hanako      
   C4 1301033 TSURUGA      Shirou      
    .....(中略)
   C5 1301150 KITAKATA     Testuo      
   C5 1301164 SUKAGAWA     Yoshiko     
   C6 1301200 ASHINOMAKI   Masaru      
14 nodes exist in the list.

Insert new data: (class ID name) -> C1 1301001 AIZU Jiro
ID 1301001 is already on the list!
Head - 
   C1 1301001 AIZU         Taro        
   C2 1301022 BANDAI       Hanako      
   C4 1301033 TSURUGA      Shirou      
    .....(中略)
   C5 1301150 KITAKATA     Testuo      
   C5 1301164 SUKAGAWA     Yoshiko     
   C6 1301200 ASHINOMAKI   Masaru      
14 nodes exist in the list.

Insert new data: (class ID name) -> C3 1301100 IKKI Goro
Head - 
   C1 1301001 AIZU         Taro        
   C2 1301022 BANDAI       Hanako      
   C4 1301033 TSURUGA      Shirou      
    .....(中略)
   C5 1301150 KITAKATA     Testuo      
   C5 1301164 SUKAGAWA     Yoshiko     
   C6 1301200 ASHINOMAKI   Masaru      
   C3 1301100 IKKI         Goro        
15 nodes exist in the list.

Insert new data: (class ID name) -> Ctrl-D
%

演習問題3(削除の実装)

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

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

(提出ファイル名: prog03.c, stulist03.h)
  1. delete 関数を追加する。
    1. リストを削除する方法については、以下の説明を参考すること。
      説明はここ :この説明はハンドアウト(prog00.c)用のものとなっている)
      なお、どうしても分からない場合はスタッフ等に聞くこと。
    2. delete 関数のプロトタイプは
      NodePointer delete(int);
      とし、以下のような動作を行う。
      1. 引数で指定された数をID番号とみなし、リスト内の構造体変数 data のメンバ id が同じ値をもつノードを検索する
      2. 一致するノードが存在すればそのノードを削除し、 一つ前のノードポインタをリターンする
      3. 一致するノードが存在しなければ、 NULL をリターンする。
  2. stulist03.hdelete 関数のプロトタイプ宣言を追加する。
  3. 演習問題2のプログラムにおけるファイルからのデータ読み取りが済んだ後で、対話的にノードの追加または削除を選んで実行可能になるように、main 関数を修正する。
% ./a.out
Head - 
   C1 1301001 AIZU         Taro        
   C2 1301022 BANDAI       Hanako      
   C4 1301033 TSURUGA      Shirou      
    .....(中略)
   C5 1301150 KITAKATA     Testuo      
   C5 1301164 SUKAGAWA     Yoshiko     
   C6 1301200 ASHINOMAKI   Masaru      
14 nodes exist in the list.

Choose operation (1: Insert, 0: Delete, ^D: Finish) -> 1
Insert new data: (class ID name) -> C3 1301100 IKKI Goro
Head -
   C1 1301001 AIZU         Taro        
   C2 1301022 BANDAI       Hanako      
   C4 1301033 TSURUGA      Shirou      
    .....(中略)
   C5 1301150 KITAKATA     Testuo      
   C5 1301164 SUKAGAWA     Yoshiko     
   C6 1301200 ASHINOMAKI   Masaru      
   C3 1301100 IKKI         Goro        
15 nodes exist in the list.

Choose operation (1: Insert, 0: Delete, ^D: Finish) -> 0
Delete ID -> 1209001
ID 1209001 is not found.
Head -
   C1 1301001 AIZU         Taro        
   C2 1301022 BANDAI       Hanako      
   C4 1301033 TSURUGA      Shirou      
    .....(中略)
   C5 1301150 KITAKATA     Testuo      
   C5 1301164 SUKAGAWA     Yoshiko     
   C6 1301200 ASHINOMAKI   Masaru      
   C3 1301100 IKKI         Goro        
15 nodes exist in the list.

Choose operation (1: Insert, 0: Delete, ^D: Finish) -> 0
Delete ID -> 1301022
Head - 
   C1 1301001 AIZU         Taro        
   C4 1301033 TSURUGA      Shirou      
    .....(中略)
   C5 1301150 KITAKATA     Testuo      
   C5 1301164 SUKAGAWA     Yoshiko     
   C6 1301200 ASHINOMAKI   Masaru      
   C3 1301100 IKKI         Goro        
14 nodes exist in the list.

Choose operation (1: Insert, 0: Delete, ^D: Finish) -> Ctrl-D
%
[エラー処理について]
この問題の実行例では、プログラムの基本的な想定通りの入力しか試していません。例えばノードの追加、削除、プログラムの終了を選ぶところで、それぞれの操作を指定するコマンドだけを試しています。しかし、使用者が開発者が予期していなかった操作をしてしまうこともあり得ますので、実用的なプログラムではそのような場合に備えてのエラー処理が重要になります。さらに、このプログラムではループを使って繰り返し処理をしているため、一つ前の操作で予期しない入力があると次の操作で問題が顕在化する場合も出てきます。特に、scanf関数ではキーボードからの入力が一旦格納させる入力バッファ(これはプログラム本体ではなくOSやターミナルが管理します)との相互作用で問題が生じます。この問題では上で指示された仕様が満たされていればよく、エラー処理については問いませんが、解答例ではそこまで考慮したものを準備していますので、より深く理解したい人は解答例の公開後に内容をよく見てみてください。

Extra問題

演習問題4(降順/昇順の挿入)

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

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

基本的には、 プログラムとする。ただし、 ようにすること。
また、このプログラムではリストにデータを挿入する関数 NodePointer insert_sort(Record, char); を作成して利用せよ。 ここで、insert_sort 関数の 第一引数は入力ノードを示す引数、 第二引数は降順か昇順かを指定する引数である。
この関数は、リストの先頭からIDを調べていき、 に入力ノードを挿入する関数である。この関数を用いると指定された並べ替えが実現できるが、 リストの末尾の処理に気をつけて作成すること。
なお科目の指定と降順/昇順の指定は、実行例のように最初にキーボードから与えるものとする。
(提出ファイル名: prog04.c, stulist04.h)

% ./a.out
Enter sort mode (d:descending / a:ascending) -> d
Head - 
   C6 1301200 ASHINOMAKI   Masaru      
   C5 1301164 SUKAGAWA     Yoshiko     
   C5 1301150 KITAKATA     Testuo      
   C3 1301123 SOUMA        Hikaru      
   C5 1301099 IWAKI        Youko       
    .....(中略)
   C1 1301007 FUKUSHIMA    Ichiro      
   C3 1301004 BANGE        Jiro        
   C1 1301001 AIZU         Taro        
14 nodes exist in the list.

Insert new data: (class ID name)) -> C3 1301100 IKKI Goro
Head - 
   C6 1301200 ASHINOMAKI   Masaru      
   C5 1301164 SUKAGAWA     Yoshiko     
   C5 1301150 KITAKATA     Testuo      
   C3 1301123 SOUMA        Hikaru      
   C3 1301100 IKKI         Goro        
   C5 1301099 IWAKI        Youko       
    .....(中略)
   C1 1251007 Nagashi           80
   C3 1251004 Sato              50
   C1 1251001 Yamada           100
15 nodes exist in the list.

Insert new data: (class ID name) -> Ctrl-D
%

% ./a.out
Enter sort mode (d:descending / a:ascending) -> a
Head - 
   C1 1301001 AIZU         Taro        
   C3 1301004 BANGE        Jiro        
   C1 1301007 FUKUSHIMA    Ichiro      
    .....(中略)
   C5 1301150 KITAKATA     Testuo      
   C5 1301164 SUKAGAWA     Yoshiko     
   C6 1301200 ASHINOMAKI   Masaru      
14 nodes exist in the list.

Insert new data: (class ID name)) -> C5 1301003 INAWASHIRO Fumiko
Head - 
   C1 1301001 AIZU         Taro        
   C5 1301003 INAWASHIRO   Fumiko      
   C3 1301004 BANGE        Jiro        
   C1 1301007 FUKUSHIMA    Ichiro      
    .....(中略)
   C5 1301150 KITAKATA     Testuo      
   C5 1301164 SUKAGAWA     Yoshiko     
   C6 1301200 ASHINOMAKI   Masaru      
15 nodes exist in the list.

Insert new data: (class ID name) -> Ctrl-D
%