画像(logo)

HOME/[C言語]サンプルプログラム集 目次/線形探索法

広告

[C言語 サンプルプログラム集]
線形探索法

広告

↓2016年02月29日発売↓

12歳からはじめる ゼロからのC言語 ゲームプログラミング教室

目次へ戻る

線形探索法

今回は線形探索法をやります。

配列など複数の要素を先頭から一つずつ順番に調べていって対象物を見つける探索法でリニアサーチともいいます。

普通に線形探索法

#include <stdio.h>

int main(){
	int ary[10] = {12,7,1,9,56,2,4,33,2,77};
	int target = 2;
	int i = 0;
	int j = 0;

	while(1){
		if(i == 10){
			break;
		}
		else if(ary[i] == target){
			break;
		}
		i++;
	}

	printf("配列の内容\n");

	for(j=0;j<10;j++){
		printf("[%d]",ary[j]);
	}

	printf("\n\n探す数字 = %d\n\n",target);

	if(i == 10){
		printf("見つかりませんでした!\n");
	}
	else{
		printf("添え字番号%d番目で見つかりました!\n",i);
	}

	return 0;
}

■実行結果■

画像(cs_12_1)

配列「ary」から対象となる数字、今回は数字の「2」を探索します。

まずは探す対象を決めるのと、ループ用の変数を用意します。

int target = 2;
int i = 0;

探す対象は変数「target」に、そしてループ用の変数「i」を用意しました。

あとはループ命令を使ってひたすら先頭から順に探していきます。

while(1){
	if(i == 10){
		break;
	}
	else if(ary[i] == target){
		break;
	}
	i++;
}

今回は「while」ループを使っておりますが、もちろん「for」ループなどでも大丈夫です。

使いやすい方をお使いください。

ループの終了条件は「見つからなかった場合」と「途中で見つけた場合」ですね!

見つからなかった場合

ループ用の変数が配列のサイズに到達した場合はその配列内に「探す対象」がなかったという事なので「break」文でループを抜けます。

途中で見つけた場合

見つけた時点で「break」文でループを抜けます。

これで普通の線形探索法は完了です。

どんなに大量のデータでも端から一つずつ探索していくのでそれなりに時間がかかります。

線形探索法関数

#include <stdio.h>

int my_linear(int,int *,int);

int main(){
	int ary[10] = {12,7,1,9,56,2,4,33,2,77};
	int target = 2;
	int result = 0;
	int j = 0;

	result = my_linear(target,ary,sizeof(ary) / sizeof(int));

	printf("配列の内容\n");

	for(j=0;j<10;j++){
		printf("[%d]",ary[j]);
	}

	printf("\n\n探す数字 = %d\n\n",target);

	if(result == -1){
		printf("見つかりませんでした!\n");
	}
	else{
		printf("添え字番号%d番目で見つかりました!\n",result);
	}

	return 0;
}

int my_linear(int target,int *ary,int ary_size){
	int i = 0;
	while(1){
		if(i == ary_size){
			break;
		}
		else if(*(ary + i) == target){
			break;
		}
		i++;
	}

	if(i == ary_size){
		return -1;
	}
	else{
		return i;
	}
}

■実行結果■

画像(cs_12_2)

線形探索法の関数を作ります。

int my_linear(int target,int *ary,int ary_size){
	int i = 0;
	while(1){
		if(i == ary_size){
			break;
		}
		else if(*(ary + i) == target){
			break;
		}
		i++;
	}

	if(i == ary_size){
		return -1;
	}
	else{
		return i;
	}
}

ここで必要な情報は探す対象、対象を探す配列、その配列のサイズなので

int my_linear(int target,int *ary,int ary_size)

引数はこちらになります。

あとは同じようにループ用の変数を用意して、ひたすら先頭から順に探していきます。

配列が引数の場合はその先頭アドレスが渡されるのでそのまま

*ary

こちらが最初の要素となり、その後の要素はそこにアドレス演算をするようなカタチで求めます。

ary[2]

*(ary + 2)

配列などを渡している時はバッファオーバーしないように配列サイズの監視も重要です。

広告

構造体配列に線形探索法

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

struct STUDENT{
	char name[128];
	int score;
};

struct STUDENT set_data(char *, int);
int my_linear2(char *,struct STUDENT *,int);

int main(){
	int result = 0;
	char *target = "saitou";
	int j = 0;
	struct STUDENT student[5];

	student[0] = set_data("tanaka",100);
	student[1] = set_data("suzuki",69);
	student[2] = set_data("satou",80);
	student[3] = set_data("saitou",92);
	student[4] = set_data("watanabe",35);

	result = my_linear2(target,student,sizeof(student) / sizeof(struct STUDENT));

	printf("配列の内容\n");

	for(j=0;j<5;j++){
		printf("名前 %s:得点 %d\n",student[j].name,student[j].score);
	}

	printf("\n探す対象 = %s\n\n",target);

	if(result == -1){
		printf("見つかりませんでした!\n");
	}
	else{
		printf("添え字番号%d番目で見つかりました!\n",result);
		printf("名前 %s:得点 %d\n",student[result].name,student[result].score);
	}

	return 0;
}

struct STUDENT set_data(char *name, int score){
	struct STUDENT tmp;
	strcpy(tmp.name,name);
	tmp.score = score;
	return tmp;
}

int my_linear2(char *target,struct STUDENT *ary,int ary_size){
	int i = 0;

	while(1){
		if(i == ary_size){
			break;
		}
		else if(strcmp((ary + i)->name,target)==0){
			break;
		}
		
		i++;
	}

	if(i == ary_size){
		return -1;
	}
	else{
		return i;
	}
}

■実行結果■

画像(cs_12_3)

より実用的なプログラムにおいては構造体の特定の要素を探索する事もあるかもしれません。

struct STUDENT{
	char name[128];
	int score;
};

生徒の名簿からある特定の生徒の名前を線形探索法を用いて探索しそのデータを表示します。

int my_linear2(char *target,struct STUDENT *ary,int ary_size){
	int i = 0;

	while(1){
		if(i == ary_size){
			break;
		}
		else if(strcmp((ary + i)->name,target)==0){
			break;
		}
		
		i++;
	}

	if(i == ary_size){
		return -1;
	}
	else{
		return i;
	}
}

今回は構造体の配列を渡すので引数は

int my_linear2(char *target,struct STUDENT *ary,int ary_size){
}

探す対象と構造体の配列の先頭アドレスを受け取る為のポインタとその配列のサイズになりますね。

後は同じようにループ用の変数を用意して、ひたすら先頭から順に探していくだけです。

int i = 0;

while(1){
	if(i == ary_size){
		break;
	}
	else if(strcmp((ary + i)->name,target)==0){
		break;
	}
		
	i++;
}

この時に構造体の各メンバにアクセスするには

(ary + i)->name

ポインタで受け取っているのでアロー演算子になる事に注意です!

□ページの先頭へ□

□目次へ戻る□

□HOME□

広告

↓2017年06月16日発売↓

やさしいC 第5版 (「やさしい」シリーズ)

新品価格
¥2,700から
(2017/5/1 13:05時点)

↓2014年08月09日発売↓

新・明解C言語 入門編 (明解シリーズ)

新品価格
¥2,484から
(2017/5/1 13:08時点)

↓2016年02月20日発売↓

新・解きながら学ぶC言語

新品価格
¥2,160から
(2017/5/1 13:10時点)

↓2017年02月11日発売↓

C言語プログラミング基本例題88 88

新品価格
¥3,024から
(2017/5/1 13:12時点)

↓2016年12月15日発売↓

Cの絵本 第2版 C言語が好きになる新しい9つの扉

新品価格
¥1,490から
(2017/5/1 13:13時点)

↓2017年02月08日発売↓

新・明解C言語で学ぶアルゴリズムとデータ構造 (明解シリーズ)

新品価格
¥2,700から
(2017/5/1 13:15時点)