[リソース構造]:線形検索(C)

出典>DO IT C言語材料構造(入門)
この授業では、線形探索について説明します.
線形検索とは?
これは

配列における探索方法の中で最も基本的なアルゴリズムである.

要素の直線形状配列における探索は、必要なキー値を有する要素に遭遇するまで、先頭から要素を順次出力し、これが線形探索OR順序探索アルゴリズムである.

配列の要素を先頭から順番に検索します.

下図を見る.

検索は次のように行われます.

1. 첫 번째 요소 6에 주목한다 -> 원하는 값이 없다.
2. 두 번째 요소 4에 주목한다 -> 원하는 값이 없다.
3. 세 번째 요소 3에 주목한다. -> 원하는 값이 없다.
4. 네 번째 요소 2에 주목한다. -> 원하는 값이다 검색에 성공했다.

キー値を持つ要素が常に配列に存在しない場合?
列の末尾を通る.
成功と失敗の終結条件は2つある.

1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우-> 검색 실패
2. 검색할 값과 같은 요소를 발견한 경우 -> 검샐 성공 

次の例を示します.

#include <stdio.h>
#include <stdlib.h>

// <main>
//idx = Search(x, nx, ky);
//const int  a[] = x  
//int nx = int n 
//int key = ky
int Search(const int a[], int n, int key)// 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형탐색한다.
{
	int i = 0;
	while (1)
	{
		if (i == n)
			return -1;
		if (a[i] == key)
			return i;
		i++;
	}

}

int main()
{
	int i, nx, ky, idx;
	int* x; // 포인터 x를 선언한다. why? -> 배열의 첫 번째 요소를 가리키려고
	puts("선형 검색\n");
	puts("요소 개수 : ");
	scanf_s("%d", &nx);
	x = calloc(nx, sizeof(int)); // x에 대한 주소 값 자체가 -> 메모리를 만든다. -> nx만큼 배열이 형성된다.
	for (i = 0; i < nx; i++) // 1. 전체적으로 for문을 돌면서 사용자로부터 값을 받는다.
	{
		printf("x[%d] : ", i);
		scanf_s("%d", &x[i]); // 배열에 값을 입력한다.
	}
	printf(" 검색 값  : ");
	scanf_s("%d", &ky); // ky값을 받는다. 선형탐색을 시작한다.
	idx = Search(x, nx, ky);
	if (idx == -1)
		puts("검색에 실패했습니다.");
	else
		printf("%d는 x[%d]에 있습니다.\n",ky, idx);


	free(x);
}

<コアコード1>

// <main>
//idx = Search(x, nx, ky);

int Search(const int a[], int n, int key)// 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형탐색한다.
{
	int i = 0;
	while (1)
	{
		if (i == n)
			return -1;
		if (a[i] == key)
			return i;
		i++;
	}

}

Search関数は常に配列aのn個の要素を線形に探索し、探索値はキーの要素である.

キーワードの値を持つ複数の要素が存在する場合、戻り値は検索中に初めて発見された要素のインデックスとなります.

キー値が存在しない場合は、-1を返します.

 1. i == n이 성립하는 경우 ( 종료조건 1 : 검색 실패하므로 -1를 반환 )
 2. a[i] == key가 성립하는 경우 (종료조건 2 : 검색 성공이므로 i를 반환 )

<典型的な結果>

<戻り値が重複している場合>

While文ではなくfor文で簡単に明瞭に表現します.

int Search(const int a[], int n, int key)
{
  int i;
  for(i = 0; i < n; i++)
    if(a[i] == key)
      return i;
   return -1;
}

※参考:無限ループの実現
1.同時ドア

while(1)
{



}

2.文のために

for( ; ; ) {



}

3. do~while

do{


}while(1);

ホイッスルほう

リニアサーチは、繰り返すたびに終了条件を確認します.

1. 검색할 값을 발견하지 못하면 배열의 끝으로 간 경우
2. 검색할 값과 같은 요소를 발견한 경우

哨兵法は、検索する値などの要素を後ろに置く.(赤)
検索

6:a[5]=6(検索失敗)

検索

2と仮定すると、入力(検索成功)a[7]=2(歩哨)

必要な値が元のデータに存在しなくても、哨兵としてのa[7]が検索されると、終了条件が確立される->複文では,歩哨の役割は終了判断回数を2回から1回に減らすことである.

最後の赤い配列部分では、入力した要素数を加算する1サイズの配列が生成されます.

次の例です.

#include <stdio.h>
#include <stdlib.h>

int Search(int p[], int nx, int ky)
{
	int i = 0;
	p[nx] = ky; //검색값 ky를 보초로 p[nx]에 대입한다.
	while (1)
	{

		if (p[i] == ky)
			break;
		i++;
	}
	return i == nx ? -1 : i;
	//변수 i값이 nx이면 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환한다.

}

int main()
{
	int i, nx, ky, idx;
	int* p;
	puts("선형탐색으로 검색한다.(보초법)");
	printf("요소 개수를 입력하세요 : "); scanf_s("%d", &nx);
	p = calloc(nx + 1, sizeof(int));//요소의 개수가 (nx+1)인 int형 배열을 생성했다.
	for (i = 0; i < nx; i++)
	{
		printf("x[%d] : ", i); scanf_s("%d", &p[i]); // 사용자가 입력하는 spot
	}
	printf("검색값 : "); scanf_s("%d", &ky);
	idx = Search(p, nx, ky);
	if (idx == -1)
	{
		puts("검색에 실패했습니다.");
	}
	else
	{
		printf("%d(은) x[%d]에 있습니다. \n", ky, idx);
	}
	free(p);
	return 0;

}

<結果>

<コアコード1>

int Search(int p[], int nx, int ky)
{
	int i = 0;
	p[nx] = ky; //검색값 ky를 보초로 p[nx]에 대입한다.
	while (1)
	{

		if (p[i] == ky)
			break;
		i++;
	}
	return i == nx ? -1 : i;
	//변수 i값이 nx이면 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환한다.

}

検索値キーを哨戒としてa[n]を代入する.

配列要素を順にチェックします.以前.
1. if(i == n)
2.if(a[i]==ky)は、if文が1つしか使用されていません.

の3つの演算子で繰り返し完了した場合、見つかった値が配列の元のデータであるかどうかを判断する必要があります.変数iの値がnxの場合、検索値は秒=>検索に失敗しました-1は

を返します.