はじめに
前回の①では、直接探索アルゴリズムで並べ替えプログラムを作成するうえで必要となるC言語文法の制御文の中の条件文と繰り返し文を解説しました。その中で、条件文としては、if文、繰り返し文としては、for文の書き方や動きを説明しました。
今回の②では、変数をひと続きに管理する配列について解説していきます。繰り返し文と配列を使うとプログラムをシンプルに見やすく書くことができます。
条件文、繰り返し文、配列を学んだ上で直接探索アルゴリズムの並べ替えプログラムをつくっていきます。このプログラムで、それらのC言語文法の使い方を見ていきたいと思います。
このブログシリーズは、C言語文法の基礎を例題プログラムから学んでマスターしていくものです。
それでは、はじめていきます。
配列
配列は、データをひとまとまりにして扱いたいときに使います。
例えば、年齢というデータを扱う場合、Aさんひとりの年齢だけであれば、int型の変数を用意して、その変数に年齢の値を代入するとなりますが、AさんからDさんまで４人の年齢を管理するとなった場合はどうでしょうか。
ひとりの場合と同じように４つのint型変数をそれぞれ用意するということもできますが、ここで配列というものを使うと便利なことが多くあります。
C言語では、配列を次のように書きます。
作成する配列の名前を決めてその配列が扱う型と要素数を設定します。
変数と同様に型は配列名の前に記述し、配列の数は、配列名の後に [ ] を付けてその中に書きます。
先ほどの例を書くと次のようになります。
int age[4];年齢を扱う配列の配列名を「age」としました。ageはint型で４つの要素をもつ配列となります。
ここで、Aさん３０歳、Bさん４５歳、Cさん２５歳、Dさん４９歳とします。この場合は、配列にあらかじめこの数値を持たせたいとなります。配列に初期値を持たせたい場合は、次のように書きます。
int age[4] = {30,45,25,49};{ }の中をカンマで区切り、そこに初期値となる数値を記述します。それを代入演算子でage配列に代入するという形になります。初期値の数と型は、必ず設定したものと一致するようにします。
これで４つの要素を持つint型の配列ageが初期値を持った形で記述できました。
各要素は、それぞれ、age[0],age[1],age[2],age[3]というように０から連番で３までの数値をいれることで参照できます。
定義するときは要素数なので[4]となりますが、各要素を参照するときは、配列の要素は０から開始するというC言語の決まりがあるので０から３までになるというところに注意が必要です。
なぜ配列を使うのかというところをひとつの例で説明したいと思います。
例えば、あるタイミングで年齢を一斉に１加算するというプログラムがあったとします。
配列で定義されたものを使うと次のように繰り返し文を使ってシンプルに記述できます。
#include <stdio.h>
main()
{
int i;
int age[4] = {30,45,25,49};
for(i=0;i<4;i++)
{
age[i] = age[i] + 1;
printf(" %d\n",age[i]);
}
}
これを４つのint型変数を使って行うと次のように同じような記述を４つ繰り返し書くことになります。
この例では４つのデータでしたが、これが１０、２０、１００、１０００とデータ数が増えた場合はとても書ききれなくなります。
同じ属性値で同じ処理を行う場合は、その値を配列を使って定義して繰り返し文で処理をまとめることによってプログラムをシンプルに記述できます。
#include <stdio.h>
main()
{
int ageA = 30;
int ageB = 45;
int ageC = 25;
int ageD = 49;
ageA = ageA + 1;
ageB = ageB + 1;
ageC = ageC + 1;
ageD = ageD + 1;
printf(" %d\n",ageA);
printf(" %d\n",ageB);
printf(" %d\n",ageC);
printf(" %d\n",ageD);
}扱ってきたage[4]のような配列を一次元配列と呼びます。配列は二次元配列や三次元配列など多次元に拡張できますが、ここでは多次元の配列があるというまでにとどめます。
並べ替えプログラム
前回の①で条件文と繰り返し文、今回の②で配列というC言語の文法をみてきました。
ここで、あらためて例題を考えていきます。例題は次のようなものでした。
「80」,「41」,「35」,「90」,「40」,「20」という６つ数字を小さい順番に並べ替えるプログラムを作成してみましょう。
ここでは、直接探索というやり方で数字を小さい順番に並べることを考えてみます。
- 比較元を先頭の数字として最小値と仮定する。また、比較対象を先頭の右隣りの数字とする。
- 最小値と比較対象の値を比較して、小さい方の数字を最小値として記憶する。
- 比較対象としてさらに右隣りの数字がある場合は、その数字に対象を移して２に戻る。
- 記憶した最小値の数字と比較元の数字を入れ替える。
- 比較元を右隣りの数字に移してその値を最小値と仮定する。その比較元のさらに右隣りの数字を比較対象値とする。
- 比較対象値がない場合は、終了とする。ある場合は、２に戻る。
「記憶」は「変数に代入」、「比較」は「条件判断」、「戻る」は「繰り返す」というようにプログラムでは記述できます。
このアルゴリズムをC言語プログラムで書くと次のようになります。
プログラムの解説
このプログラムについてブロックごとに解説していきます。
#include <stdio.h>
main()
{
int i,j; //ループ用
int min_num; //最小値の配列番号
int min; //最小値
int temp; //数値の一時保存用
int number[6] = {80,41,35,90,40,20}; //並べ替え前の数値列今回は自作の関数はなく、表示のためにprntf関数を呼び出すため、ライブラリファイルのstdio.hを読み込み、main関数の中身をつくっていきます。
main関数では、はじめに使用する変数を定義します。このプログラムで扱う数値は、整数値で値も２桁ということで使用する変数はすべてint型としました。
変数 i と j は、繰り返し文で使用するために定義したループ変数です。
min_numとminは、最小値の配列番号と最小値を保存するために使う変数、tempは、比較元の値と最小値を入れ替えるときに一時的に値を保持するための変数、numberは、int型で要素を６つ持った配列で、80,41,35,90,40,20という値を初期値としています。
並び替えた後の数字列の記憶もこのnumberを書き換える形で使っていきます。
//初期状態を表示する
printf(" --- initial number ---\n");
for(j=0;j<6;j++)
{
printf(" %d ",number[j]);
}
printf("\n------------------------\n");続いて、この部分は、numberの初期値を画面表示するために記述したプログラムになります。
本質的な動作には関係ない部分なので特になくても動作に影響はしません。
結果を出力した際に動きをわかりやすくするために記述したものになります。
for(i=0;i<5;i++)
{
min_num = i; //最小値番号の初期設定値
min = number[min_num]; //最小値の初期設定値
for(j=i+1;j<6;j++)
{
if(min > number[j])
{ //比較元と比較対象の値を比較して
//比較対象の方が小さい場合は、その配列番号を記憶
min_num = j;
min = number[min_num];
}
}ここから直接探索アルゴリズムの本質的な部分になってきます。
この部分では、２つの繰り返し文が使われています。
ループ変数 i を使った繰り返し文は、比較元を遷移させていくための繰り返し処理です。
終了条件は、比較対象がひとつ存在するところまでということ６ではなく５としています。
ですので、このループは５回繰り返すということになります。
ループ内では、まず、比較元を仮の最小値としてその配列番号と値をそれぞれmin_numとminという変数に記憶するということをしています。
そして、ひとつの比較元に対してその値より右側に並ぶ比較対象の値から最小値を見つけるため、それらの値を取り出し比較するという動作を繰り返しています。
その繰り返しがループ変数 j を使ったfor文の繰り返し処理になります。
このループでは、仮に入れた最小値より比較対象値の方が小さい場合は、その配列番号と値を最小値として最小値を更新するということをしています。
//比較元の数字と記憶した最小値の数字を入れ替える
temp_num = number[i];
number[i] = number[min_num];
number[min_num] = temp_num;
//途中経過も含めて画面表示
for(j=0;j<6;j++)
{
printf(" %d ",number[j]);
}
printf("\n");
}
}この繰り返しによって、ひとつの比較元に対して、すべての比較対象値をチェックしてその中から最小のものを探すことができます。
その繰り返しが終わった時点で最小値が決定しているので、その値と比較元の値を入れ替えます。
値を入れ替えるとき直接比較元の値に最小値を代入してしまうと入れ替え先に元々の比較元の値を入れることができなくなってしまいます。
そのため、tempという変数を用意して、一時的に比較元の値を記憶して、その値を最小となった値のところに代入しています。
その後のfor文は、途中経過を含めて画面に結果を表示するためのものです。
ここまでがループ変数 i のfor文の処理です。この内部の処理を繰り返していきます。
ループ最後のprintf関数で各比較元に対しての結果が表示されます。
この繰り返しは５回行われるので５回分の結果が表示されることになります。そして、最後の５回目に出力されたのもが並び替えられた配列になります。
プログラムの実行結果
作成したプログラムをコンパイルして実行してみると次のような結果になります。
--- initial number ---
80 41 35 90 40 20
------------------------
20 41 35 90 40 80
20 35 41 90 40 80
20 35 40 90 41 80
20 35 40 41 90 80
20 35 40 41 80 90initial numberで囲った部分が並べ替え前の数字列になります。
初回の繰り返し処理では比較元の値「８０」に対して最小値「２０」が選択され、その値と入れ替えが行われます。その結果が次に出力された「20 41 35 90 40 80」になります。
これで最小値の２０が決定し、次の最小値を探していく流れになります。
次の比較元の値は「４１」となり、その値と比較対象「35 90 40 80」の中の最小値３５が決定して比較元と値の交換が行われます。
それが次の出力「20 35 41 90 40 80」です。
同様にして、比較元の値４０、４１、８０としたときの最小値の探索が行われ、値の交換がなされます。
比較元４０のときは、その値が最小値となっているので、その場合は、値の交換はされていません。
交換がされない場合でもプログラムでは、最小値を仮設定で比較元の値としているので問題なくプログラムが動作しています。
最終的な結果は、「20 35 40 41 80 90」となり、数字が小さい順番に並び替えられた形となっています。
まとめ
第六回では、直接探索アルゴリズムを使って与えられた数字列を小さい順番に並び替えるプログラムをつくり、その結果を確かめてきました。
その中で必要となるC言語の文法は、条件文や繰り返し文といった制御文と配列でした。これらの文法的な形や使い方を前回と今回で解説しました。
第一回から第六回までで、変数、配列、関数、制御文の基本的な解説をしてきました。
C言語の制御文には他にもあるのですが、ここで使用した条件文のif文、繰り返し文のfor文をマスターできれば基本的なプログラムは記述できると思います。
あとは、定数、記憶クラス、ここまでで登場していない演算子、構造体と共用体、ポインタというような項目が残っていますが、これらは応用として必要に応じて学んでいければよいと思います。
次回は、繰り返し文で扱ってこなかったwhile文や変数のスコープについて、その使い方を学習して、基礎からマスターのシリーズを完了したいと思います。
 | 価格:2,530円 |
コメント