10日目 12日目

11日目

目標

• 整列アルゴリズムを理解する
• 構造体を理解する

課題 12

並べ替え(バブルソート)

データをある規則にしたがって並べ替えることを「整列」と呼ぶ。 ソーティング(sorting)とも呼ばれる。 たとえば次のようなデータの並べ替えはすべてある規則にしたがっている。

プログラム上で整列を行うための方法には、様々なものが考案されている。 簡単で代表的なものとして、ここではバブルソートを取り上げる。

バブルソートは、未整列の列を左から順に隣り合った２つのデータを比較し、 順序が間違っていたら、交換を行うことで、整列を行う。 次に、上で扱った５つの数値データを昇順に並べ替える手続きを、 バブルソートで整列するのを見てみよう。 "|" は未整列と整列済みのデータの境界を示すものとする。

上のデータの変遷を見ると、未整列のデータの中での最大値が順に右に移動していく様子がわかる。 そのため、水の中の泡が浮いていくのに例えられ、バブルソートと呼ぶ。

バブルソートを C 言語の関数として表現した例を次に示す。 データは配列 a に、データ数は nとして渡されることとしよう。

int bubble_sort(int a[], int n) {
	int i, data, tmp;
	/* data: 整列する必要があるデータ数。 */
	for (data = n; data > 1; --data) {
		/* i: 現在比較中のデータペアの左側を示す */
		for (i = 0; i < data - 1; ++i) {
			/* 比較 */
			if (a[i] > a[i+1]) {
			      /* 間違っていたので交換 */
			      tmp = a[i];
			      a[i] = a[i+1];
			      a[i+1] = tmp;
			}
		}
	}
	return 0;
}

変数の値を交換するためには、一度値を退避しておく変数が必要であることを忘れると データが破壊されてしまうので注意が必要である。

バブルソートは 単純ではあるがデータ数が大きくなると急激に遅くなるアルゴリズムである。 それは、上記のプログラムの中で、比較が行われる回数を考えると良く分かる。 最初の for ループでは data変数が n から 2 まで変化していく。 内側の for ループでは 1 から data -1 まで変化する。 従って比較が行われる回数は

となる。 したがって、バブルソートの処理にかかる時間はデータ数の2乗したものに、ほぼ比例することになる。 つまり、データ数が2倍になれば、処理にかかる時間は4倍に、データ数が10倍になれば処理にかかる時間は100倍になることになる。

問題 12

さて、バブルソートを理解したところで、 課題10で取り上げた文字の出現回数や出現頻度のグラフを表示するプログラム(count2.c)の出力を、 出現回数が多いもの順に変更したい。 どのように修正すれば良いだろうか？ count3.c という名前で修正を施せ。

修正できたら、実行してみて意図通りに動いているかどうか確認せよ。

課題 13

構造体

ある授業の受講者に関する情報を取り扱うようなプログラムを考えるとしよう。 取り扱う情報としては、「学籍番号」、「姓」、「名」、 「講義への出席回数」、「テストの点数」を考える。 課題13では、このような情報をプログラム上でうまく取り扱う方法について取りあげる。

一番原始的な方法としては、

        /* 一人目 */
        char gakuseki_bango_01[10];
	char family_name_01[40];
	char given_name_01[40];
	int  shusseki_01;
	int  mark_01;

        /* 二人目 */
        char gakuseki_bango_02[10];
	char family_name_02[40];
	char given_name_02[40];
	int  shusseki_02;
	int  mark_02;

のように、すべてについて個別に変数を用意する方法が考えられる。 しかし、これではプログラムの可読性も低下するし、そもそも手間がかかって仕方がない。

このような場合には、配列を使えば良かったのであった。 そこで、配列を使って宣言すると次のようになる。 たとえば受講生が最大30人であるという事があらかじめ判っているとして、 配列を使って宣言を行うと、次のようになる。

        char gakuseki_bango[30][10];
	char family_name[30][40];
	char given_name[30][40];
	int  shusseki[30];
	int  mark[30];

しかし、これでも、ある受講生の情報が様々な配列にバラバラに格納されることになり、 扱いやすいとは言いがたい。たとえば、一人一人の学生の情報を入力するような 関数を考えた場合、引数として５つの変数を渡さなければならない。
問題11のようなソートをするようなことを想像してみよ。

このような複数の型をまとめて扱いたいような場合、 C 言語では、複数のデータをひとまとめにして扱う「構造体(structure)」という データ型を使用することができる。

構造体を使用するためには、最初にどのようなデータを含む構造体なのかを宣言する必要がある。 宣言は structを用いて

struct student_info {
      char gakuseki_bango[10];
      char family_name[40];
      char given_name[40];
      int shusseki;
      int mark;
};

のように行う。student_info はタグと呼ばれ、構造体の型についた名前のようなものである。 (宣言と同時に変数も宣言してしまうような場合には、タグは省略することも可能。) {} でくくられた中に宣言された変数は「メンバ」と呼ばれる。 この宣言により、student_infoという構造体の構成が定義されたので、 これ以降 student_info「型」の変数は、通常の型(int 等)と同様、 次のような宣言で使用することができる。

  struct student_info info;
  struct student_info data[40];
  struct student_info *pdata;

dataは、構造体の配列の宣言の例であり、pdataは構造体のポインタの宣言の例である。

構造体の宣言と変数の宣言を同時にすることもできる。

struct student_info {
      char gakuseki_bango[10];
      char family_name[40];
      char given_name[40];
      int shusseki;
      int mark;
} info, data[40], *pdata;

構造体の初期化の際には、次のようにして値をセットすることができる。

   struct student_info info = {
       "08913765",
       "大垣内",
       "多徳",
       13,
       65
   };

しかし、初期化以外の場面ではこの手法は取れず、値を設定するためには、 メンバーごとに行う必要がある。ただし、同じ型の構造体変数からの代入は可能である。

構造体の各メンバーへのアクセスは.演算子を用いる。 各メンバーはその型に可能な行為はすべて許される。

    strcpy(info.gakuseki_bango, "08913765");
    strcpy(info.family_name, "大垣内");
    strcpy(info.given_name,  "多徳");
    info.shusseki = 13 + 2;
    info.mark     = 65;
    scanf("%s%s%s%d%d", info.gakuseki_bango,
          info.family_name, info.given_name,
          &info.shusseki, &info.mark); /* 標準入力からの書式指定読込み */

構造体が、ポインタ変数であった場合、"*" 演算子よりも、"."演算子の優先順位が高いため、 (*pdata).shussekiのように必ず "()" が必要である。 いちいち "()" をつけるのは煩雑なので、その短縮形として padta->shussekiという 形式を使うことができる。

strcpy関数は、第二引数で与えられる文字列(char 型のポインタであった)の 内容を、第一引数で与えられるポインタにコピーする。 コピー先の大きさに関するチェックは行われないので、注意すること。 特に文字列には、終端文字が含まれる為に「目に見える」長さより1バイト多く必要である事に留意する。 コピーする文字列の長さを制限するstrncpyなどもある。

自分で作るヘッダファイル

上の構造体の定義が書かれているファイルは struct.h という名前にしてある。 この内容を、プログラムに取り込むには、ファイルに実際に加える方法だけでなく、 #include 文をつかって、読み込ませることも可能である。

ただし、自分で作ったヘッダファイルは、標準の場所にないため

  #include "struct.h"

のように <> ではなく、""でファイル名を囲むことに気をつける必要がある。 (囲み方によってファイル探索の順番や探索される場所が変更される。)

問題 13

ある講義の受講生のデータとして次のような書式の data.txtを用意した。 このファイルは一行が一人の学生を表しており、それぞれ、学籍番号、姓、名、出席回数、テストの点数が書かれているものとする。

239333 伊藤 要      12 67
299721 河合 勇      9  77
322900 宮塚 茂雄    9  45
339202 金元 武紀    10 70
347048 原田 博夫    10 98
356778 坂本 登喜子  13 69
359157 酒井 伝      9  73
373459 小玉 直栄    9  58
423416 小畑 則男    13 99
457244 松川 純子    11 58
461810 松倉 誠      10 80
463396 上坂 正恵    11 79
517319 上田 秀樹    11 56
538730 斉藤 久則    14 83
565631 滝波 幹雄    11 92
574962 竹澤 寛治    12 46
583885 長谷川 益雄  10 39
643907 渡辺 永充    8  94
657744 南保 一敏    11 76
664971 山口 亜佐子  10 53

1. このファイルを読み込み、テストの点数に加えて出席回数1回につき 2点与えたものを総合得点として計算し、 各人の学籍番号、姓名、総合得点を表示するプログラムを作成せよ。

2. 総合得点の最高点、最低点を求め、該当する受講生の情報を表示するように改良せよ。

3. 学籍番号、姓名、総合得点を総合得点の高い順に表示できるように改良せよ。