アルゴリズムを
勉強するということは、自分のプログラム能力を向上させることにつながります。
例えばボロい中古の
パソコンと最新の良いパーツを載せたパソコンが、同じプログラムを
処理させたらきっと最新のパソコンのほうが処理が速いでしょう。
しかし、
目的は同じプログラムだけど、中古のパソコンのほうには
計算量を少なくするために
工夫されたアルゴリズムを使い、
最新のパソコンのほうのプログラムには
単純なアルゴリズムを使うと
中古のパソコンのほうが処理が速かったということがありえます。
プログラマーの腕次第です。
だからアルゴリズムを勉強して良いプログラマーになりたいですね！
それでは今日は初めてのアルゴリズムなので簡単な探索アルゴリズムをやります。
配列上のある要素を探しだすプログラムです。
例えばクラス名簿というクラス人数分のデータのなかから、
指定した学籍番号の生徒のデータを表示するプログラムを作れと教頭先生に命令されました。
流れはこんな感じでどうでしょう。
指定された学籍番号を記憶する。
↓
先頭の学籍番号から最後の学籍番号
まで比較していく。
↓
一致したらその学籍番号の生徒の他の
データを表示。最後まで一致しなかったら
画面に存在しないことを表示。
|
というわけで早速プログラムを作ってみましょう♪
クラス名簿はこのように
テキストファイルにあるとします。
meibo.txt
101 (学籍番号)
相沢 明 (氏名)
1 (欠席回数)
102
天野 山
0
103
大城 宗徳
3
104
香山 県
2
105
ケビン マイケル
0
106
笹川 京子
10
108
志村 敏郎
3
109
蘇芳 美文
5
110
森瀬 健二
2
|
H107番の生徒は退学したとします。
このような一人分のデータなどは構造体でまとめるといいですので
データ構造は構造体でこんな感じでよいでしょう
struct STUDENT
{
int number; /* 学籍番号 */
char name[32]; /* 氏名 */
int abs; /* 欠席回数 */
}
それではプログラム例です
#include <stdio.h>
typedef struct STUDENT
{
int number;
char name[32];
int abs;
}student;
int main(void)
{
FILE *fp;
student st[9]; /* 生徒人数分 */
int n;
int i;
int num;
/* ファイルオープン */
fp = fopen("meibo.txt","r");
if(fp == NULL){
perror("file open error");
return -1;
}
/* ファイルからデータを読み込む */
for(i = 0 ; i < 9 ; i ++){
fscanf(fp,"%d",&st[i].number);
fscanf(fp,"%s",&st[i].name);
fscanf(fp,"%d",&st[i].abs);
}
printf("検索する学籍番号を入力:");
scanf("%d",&num);
/* 配列の先頭から比較 */
for(i = 0 ; i < 9 ; i++){
/* 見つかった */
if(st[i].number == num){
printf("学籍番号:%d\n",st[i].number);
printf("氏名:%s\n",st[i].name);
printf("欠席:%d回\n",st[i].abs);
break;
}
}
/* 全ての配列を検査したが見つからなかった */
if(i == 9)
printf("学籍番号%d は名簿にはありません\n",num);
fclose(fp);
return 0;
}
|
for文で先頭から順番に比較していき、見つかったら表示してbreakで
ループをさっさと抜けるようにしました。
みつからなかった時の条件がなぜ
(i == 9)なのかというと
配列の最後の要素の添え字は 8 ですから該当しない場合はiは9になっているからです。
話は少し逸れますがこういうところに"9"という具体的な数字を書くのはよろしくないです。
なぜならあとで生徒40人分をやってみようとなったときはすべての"9"を"40"に換えなければ
いけないからです。ですのですこし改良したプログラムがこちらです。
#include <stdio.h>
typedef struct STUDENT
{
int number;
char name[32];
int abs;
}student;
int main(void)
{
FILE *fp;
student st[9]; /* 生徒人数分 */
int n=0;
int i;
int num;
/* ファイルオープン */
fp = fopen("meibo.txt","r");
if(fp == NULL){
perror("file open error");
return -1;
}
/* ファイルからデータを読み込む */
while(fscanf(fp,"%d %s %d",&st[n].number, &st[n].name, &st[n].abs) != EOF)
n++; /* ←生徒人数 */
printf("検索する学籍番号を入力:");
scanf("%d",&num);
for(i = 0 ; i < n ; i++){
if(st[i].number == num){
printf("学籍番号:%d\n",st[i].number);
printf("氏名:%s\n",st[i].name);
printf("欠席:%d回\n",st[i].abs);
break;
}
}
if(i == n)
printf("学籍番号%d は名簿にはありません\n",num);
fclose(fp);
return 0;
}
|
fscanfで
読み取るときに人数をカウントして使いまわしています。
あとデータの読み込みも改良しました。下線部分を見てください。
while文の中にfscanfを入れ、EOF というものが
でるまで読み込め！ということなのですが、fscanfでデータを読み込んでいくと
データを全て読み込んだあとにこの
EOFというものを返してきます。
これは
EndOfFileのことでデータの終わりを意味します。
ですから↓の意味は、
while(fscanf(fp,"%d",&a[i]) != EOF)配列a[i]にfpが読み込んだ値を入れろ！もし値が（データが）なければ終了だ！
という意味です。とりあえずファイルを全部読み込みたいときは使ったほうがいいでしょう。
というわけでデータの探索でした。
このような先頭からひとつずつ比較していく方法は
線形探索法といいます。
次回は別の探索アルゴリズムを紹介します。それではまた！
