システムプログラミング序論 演習

演習4： 動的なメモリ割り当てとリスト構造

例題1： ファイルに含まれているデータをソートするプログラム

#include <stdio.h> #include <stdlib.h> #include <string.h> struct record { int number; char name[256 + 1]; int point; struct record *next; }; struct record *head = NULL; void insert_list(int no, char *nam, int pnt) { struct record *p, *q, *t; t = (struct record *)malloc(sizeof(struct record)); if (t == NULL) { fprintf(stderr, "Out of memory\n"); exit(1); /* Terminate the program with the exit status */ } t->number = no; strcpy(t->name, nam); t->point = pnt; q = NULL; for (p = head; p != NULL; p = p->next) { if (p->point >= pnt) { break; } q = p; } if (q != NULL) { q->next = t; } else { head = t; } t->next = p; } int main(int argc, char *argv[]) { FILE *fp; int nlines, i; int no, pnt; char nam[256 + 1], buf[1024 + 1]; struct record *p; if (argc != 2) { fprintf(stderr, "Missing file argument\n"); return 1; } if ((fp = fopen(argv[1], "r")) == NULL) { fprintf(stderr, "Can't open %s\n", argv[1]); return 1; } if (fgets(buf, sizeof(buf), fp) == NULL) { fprintf(stderr, "Can't read input data\n"); return 1; } if (sscanf(buf, "%d", &nlines) != 1) { fprintf(stderr, "Invalid input data\n"); return 1; } for (i = 0; i < nlines; i++) { if (fgets(buf, sizeof(buf), fp) == NULL) { fprintf(stderr, "Can't read input data\n"); return 1; } if (sscanf(buf, "%d %s %d", &no, nam, &pnt) != 3) { fprintf(stderr, "Invalid input data\n"); return 1; } insert_list(no, nam, pnt); } fclose(fp); for (p = head; p != NULL; p = p->next) { printf("%d %s %d\n", p->number, p->name, p->point); } return 0; }

• このプログラムは ex4_data.txt と同様の形式で書かれた入力ファイルを受け取ることを想定している． すなわち，入力ファイルの先頭行にはデータの個数が書かれている． 以降の各行には学生のデータが1行につき1人分ずつ書かれている． 学生1人分のデータとして，学籍番号，名前，点数がこの順番で1個ずつ書かれており，それらは1個の空白で区切られている． 名前が同じであるような異なる行はない． データの個数は高々100である． 学籍番号は9桁の整数である． 名前はアルファベットのみからなり，高々256文字である． 点数は最小0，最大100の整数である． 入力ファイルの1行の長さは，改行を含めても，高々1024文字である．
• このプログラムをファイルに保存し，そのファイルを gcc コマンドでコンパイルしなさい．
• できた実行型ファイルを，ex4_data.txt をコマンドライン引数に与えて実行し，点数の低い順にソートされた結果が表示されることを確認しなさい．
• このプログラムは実行時に確保したメモリ領域を解放しないまま終了する．もしプログラムの終了前に解放する場合には，return文の前に

  for (p = head; p != NULL; p = p->next) {
    free(p);
  }
    

  を加える（2019年11月6日17:10追記）．

課題1

例題1のプログラムを参考に，例題の入力ファイルと同じフォーマットのファイルのファイル名をコマンドライン引数から受け取り，ファイルに含まれている学籍番号，名前，点数を読み取り，それらの情報が書かれた行を，名前のアルファベット順に表示するプログラムを作成しなさい． 文字列の順序比較にはライブラリ関数の strcmp を使って良い． プログラムのソースファイル名は ex4_1.c，実行ファイル名は ex4_1 とする． 例題の入力ファイルを与えたときの実行結果を示しなさい． 余裕があれば他の入力ファイルを与えたときの実行結果も示しなさい．

課題2

例題1のプログラムを参考に，例題の入力ファイルと同じフォーマットのファイルのファイル名をコマンドライン引数から受け取り，ファイルに含まれている学籍番号，名前，点数を読み取り，それらの情報が書かれた行で，平均点以上の学生のものを，点数の高い順に表示するプログラムを作成しなさい． プログラムのソースファイル名は ex4_2.c，実行ファイル名は ex4_2 とする． 例題の入力ファイルを与えたときの実行結果を示しなさい． 余裕があれば他の入力ファイルを与えたときの実行結果も示しなさい． 注意： 変数の初期化を忘れて平均点の計算結果が正しくなくなるレポートが過去に多く見られた． 初期化が必要な変数を初期化することを忘れないようにしよう． 初期化に関する注意を加えました．（2019年11月6日 16:35 追記）

例題2： ファイルに含まれている単語の出現頻度を表示するプログラム

• このプログラムは引数で指定されたファイルを読み込み，単語が何回使われているかを，単語の辞書順に表示するプログラムである． 単語とは空白文字を含まない英数字，アポストロフィ（'），およびハイフン（-）からなる文字列とする． ピリオド，カンマ，クエスチョン記号（?），エクスクラメーション記号（!），ダブルクオーテーション記号（"）などを含むその他の文字は，単語を構成する文字ではなく，空白文字と同じとみなす．よって，1973 も -- も1つの単語とみなされ，Dr. は Dr という単語とみなされる． 辞書順に並べるための文字の順としては ',-,0, 1, ..., 9, A, B, ..., Z, a, b, ... z という順を用いるものとする． この順は文字のASCIIコードの順と同じである． 例えば，辞書で Zoo は absent よりも前に出現するものとする． 大文字小文字の表現が異なる単語は別の単語であるとみなす．例えば，university と University は別の単語であるとみなす． 単語の文字数は高々64である． 大体のプログラムの構造は次のようになる．
  • read_word_from_file は引数 fp で指定されるファイルから単語を順に読み込み，それを word で指定されるメモリ領域に書き込む関数である． 単語の読み込みに成功した場合には1を，ファイルの末尾に達したなどの理由により単語を読み込めなかった場合には0を返す．
  • add_word_to_list は複数の単語を，単語の情報を保持する構造体のリストで管理するための関数である． そのリスト（の先頭へのポインタ）はポインタ型の大域変数 head が保持している． 引数に与えられた単語 word がもしリストになければ，その単語（の情報を保持する構造体）をリストに辞書順で登録する． もしリストにあれば，リスト中の対応する構造体が保持する出現頻度 count の値を1増やす．
  辞書順ではアポストロフィとハイフンがどこに入るかという情報を加えました．（2019年11月6日 14:40 追記）

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> struct record { char word[64 + 1]; int count; struct record *next; }; struct record *head = NULL; int read_word_from_file(FILE *fp, char *word); void add_word_to_list(char *word); int main(int argc, char *argv[]) { FILE *fp; char word[64 + 1]; struct record *p; if (argc != 2) { fprintf(stderr, "Missing file argument\n"); return 1; } if ((fp = fopen(argv[1], "r")) == NULL) { fprintf(stderr, "Can't open %s\n", argv[1]); return 1; } while (read_word_from_file(fp, word)) { add_word_to_list(word); } fclose(fp); for (p = head; p != NULL; p = p->next) { printf("%s %d\n", p->word, p->count); } return 0; }

• このプログラムをファイルに保存しなさい．そのファイルをgccコマンドでコンパイルしようとすると，エラーが出てコンパイルできないことを確認しなさい．このプログラムは不完全であり，課題3，4のプログラムの元になるものである．

課題3

read_word_from_file と add_word_to_list を完成させて，例題2のプログラムを完成しなさい． プログラムのソースファイル名は ex4_3.c，実行ファイル名は ex4_3 とする． 入力としてファイル ex4_message.txt を与えて ./ex4_3 ./ex4_message.txt を実行し，プログラムが正しく動くことを確認しなさい． なお，一例を出すと，cutting-edge は1回，global は5回，education は6回，of は29回出現していると表示されるのが正しい． また，表示される出力は274行となり，最初の5行が -- 1 1872 1 1973 1 Amid 1 Based 1 となり，最後の5行が wide 1 will 2 with 3 world 1 would 1 となるのが正しい．この実行結果はレポートに含める必要はない． 入力としてファイル ex4_toyoda.txt を与えて ./ex4_3 ./ex4_toyoda.txt を実行し， 表示される結果の最初の10行と最後の10行をレポートに書きなさい． 作成するプログラムで実行時にメモリ領域を確保した場合，プログラムの終了前にそれらを解放しなくてもよいものとする（2019年11月6日17:15追記）． ヒント： add_word_to_list の中では，ファイルから読んだ文字列を格納するメモリ領域を確保するために，ライブラリ関数の malloc を呼び出す必要があるだろう．一方，read_word_from_file には，すでに確保されたメモリ領域へのポインタが渡されるので，関数内で新たにメモリ領域を確保する必要はないだろう． ヒント： アポストロフィ文字をプログラムの中で扱う際には注意が必要である．C言語で文字を表現するための括り記号はシングルクォーテーションであり，それはアポストロフィそのものであるからである．アポストロフィ文字をC言語のプログラムの中で表現する方法については，Webを検索するなどして自分で調査してほしい．

課題4

このプログラムを元に，出現頻度の高い順に単語と出現頻度を表示するプログラムを作りなさい． 出現頻度が同じ単語が複数存在する場合には，それらの単語は任意の順で表示して良い． プログラムのソースファイル名は ex4_4.c，実行ファイル名は ex4_4 とする． 入力として課題3と同じファイルを使って ./ex4_4 ./ex4_message.txt を実行し，プログラムが正しく動くことを確認すること． なお，一例を出すと，出現頻度の第5位は as で出現頻度は14，第11位は society で出現頻度は7となるのが正しい． この実行結果はレポートに含める必要はない． 入力として課題3と同じファイルを使って ./ex4_4 ./ex4_toyoda.txt を実行し，表示される結果の ファイル先頭行から出現頻度10以上の行までの部分 出現頻度1である単語の個数 をレポートに書きなさい． 作成するプログラムで実行時にメモリ領域を確保した場合，プログラムの終了前にそれらを解放しなくてもよいものとする（2019年11月6日17:15追記）． レポートに書く必要はない（書いてもいい）が，余裕があれば，作ったプログラムに長い文書を与えてみるのも面白いかもしれない． Project Gutenberg には，著作権が切れた小説のデータが大量に公開されている． たとえば「宝島」がある． 入力としてファイル ex4_island.txt を与えてみよう． 出現頻度の第100位は squire で出現頻度は88，第183位は HISPANIOLA で出現頻度は51，第275位は treasure で出現頻度は35となるのが正しい． 単語の総数は7103となり，出現頻度1である単語の個数は3761となるのが正しい．