(C/C++) 검색 - 선형 탐색, 순차 탐색(Sequential Search)

검색 알고리즘은 검색 로직뿐만 아니라 삽입 삭제 로직도 같이 구현했습니다.

1. 선형 탐색, 순차 탐색(Sequential Search)

주어진 자료파일에서 처음부터 검색하여 필요한 데이터를 비교하며 찾는

가장 단순한 검색 방법입니다.

평균적으로 N/2 번의 비교를 하는 효율이 낮은 검색 방법이지만

구현하기 간단하고 정렬되어 있지 않은 대상으로도 가능하기 때문에 널리 사용하는 방법입니다.

 

2. 구현 방법

방법은 간단합니다. 첫번째 인덱스부터 끝까지 돌면서 값이 있는지 확인하면 끝이거든요!

검색은 배열을 반복문을 돌리면 끝입니다.

삽입은 순차탐색 특성상 정렬될 필요 없으니 마지막 위치에 넣었습니다.

삭제는 배열로 구현시 바로 빈자리를 채우는 방법과 표시만 해두고 나중에 처리하는(게으른 삭제) 방법중에

바로 삭제를 택했습니다. 

 

단순히 순차 탐색을 구현하는 것은 아주 간단하기 떄문에 한번 참조한 값을 또 참조할 확률이 높다고 가정하여

찾은 값을 배열의 가장 뒤로 이동하는 쪽으로 구현하도록 하겠습니다.

 

3. 배열을 이용한 순차 탐색 구현

struct Data
{
	int key;
	int phone;
};

class SequentialArray
{
private:
	Data* arrays;
	int maxCnt;
	int currentCnt;

	bool FineIndex(int key, int& index);
public:
	SequentialArray(int max = 100);
	~SequentialArray();
	bool Search(int key, Data& data);
	bool Insert(Data data);
	bool Delete(int key);
	void PrintAll();
};

배열 순차 탐색의 헤더 입니다.

기본적으로 검색은 키값을 통해 데이터를 읽어들이는 형태기 떄문에 Data 구조체를 하나 선언했습니다.

내부 연산에 필요한 FindIndex 함수만 Private 입니다.

 

#include "SequentialArray.h"
#include <stdio.h>

bool SequentialArray::FineIndex(int key, int& index)
{
	for (int i = currentCnt - 1; i >= 0; i--)
	{
		if (arrays[i].key == key)
		{
			index = i;
			return true;
		}
	}
	return false;
}

SequentialArray::SequentialArray(int max)
{
	maxCnt = max;
	currentCnt = 0;
	arrays = new Data[maxCnt];
}

SequentialArray::~SequentialArray()
{
	delete[] arrays;
}

bool SequentialArray::Search(int key, Data& data)
{
	int index = -1;
	if (FineIndex(key, index))
	{
		data = arrays[index];
		for (int i = index + 1; i < currentCnt; i++)
		{
			arrays[i - 1] = arrays[i];
		}
		arrays[currentCnt - 1] = data;
		return true;
	}

	return false;
}

bool SequentialArray::Insert(Data data)
{
	if (currentCnt >= maxCnt)
		return false;

	arrays[currentCnt++] = data;
	return true;
}

bool SequentialArray::Delete(int key)
{
	int index = -1;
	if (FineIndex(key, index))
	{
		for (int i = index + 1; i < currentCnt; i++)
		{
			arrays[i - 1] = arrays[i];
		}
		currentCnt--;
		return true;
	}

	return false;
}

void SequentialArray::PrintAll()
{
	for (int i = currentCnt - 1; i >= 0; i--)
	{
		printf("key : %d\tPhone : %d\n", arrays[i].key, arrays[i].phone);
	}
}

배열 순차 탐색의 CPP 입니다.

배열 뒤쪽 부터 찾는데 위에 설명드렸듯이 최신데이터가 가장 맨 뒤에 위치하기 때문입니다.

순차 탐색 자체가 정렬되지 않은 데이터를 찾을때 사용하기 때문에 

데이터 위치를 마음대로(정렬 신경안쓰고) 옮겨주었습니다.

 

4. 링크드리스트를 이용한 순차 탐색 구현

 

순차탐색은 마찬가지로 링크드 리스트로도 구현이 가능합니다.

다만 위 배열 순차탐색에서도 보셧듯이 살짝 응용의 영역이라 지난번 구현했던

링크드리스트 관련 포스팅을 링크 걸어두고 넘어가도록 하겠습니다.

(C) 자료구조 - 단일 연결 리스트(Singly Linked List)

위 링크드 리스트에서 Search 와 Delete 시 노드의 위치를 옮겨주기만 하면 됩니다.

 

감사합니다!