순차 탐색
•
데이터 집합의 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 탐색 알고리즘
•
순차 탐색은 한쪽 방향으로만 탐색을 수행한다고 해서 선형 탐색(Linear Search)라고 부른다.
•
정렬되어 있지 않은 데이터 집합 속에서 원하는 데이터를 찾을 수 있는 유일한 방법
링크드 리스트의 순차 탐색 구현
Node* SSL_SequentialSearch(Node* Head, int Target)
{
Node* Current = Head;
Node* Match = NULL;
while (Current != NULL)
{
if (Current->Data == Target)
{
Match = Current;
break;
}
else
Current = Current->NextNode;
}
return Match;
}
C
Self-Organizing Sequential Search
자기 구성 순차 탐색이란 자주 사용하는 데이터를 데이터 집합의 앞쪽에 배치함으로써 순차 탐색의 검색 효율을 끌어올리는 방법
자주 사용되는 항목 선별
전진 이동법 (Move To Front)
데이터 집합에서 어느 항목이 한번 탐색되고 나면, 그 항목을 데이터 집합의 가장 앞(링크드 리스트에서 Head)에 위치시키는 방법
Node* SSL_SequentialSearch(Node* Head, int Target)
{
Node* Current = Head;
Node* Previous = NULL;
Node* Match = NULL;
while (Current != NULL)
{
if (Current->Data == Target)
{
Match = Current;
if (Previous != NULL)
{
// 자신의 앞 노드와 다음 노드를 연결
Previous->NextNode = Current->NextNode;
// 자신을 리스트의 가장 앞으로 옮기기
Current->NextNode = (*Head);
(*Head) = Current;
}
break;
}
else
{
Previous = Current;
Current = Current->NextNode;
}
}
return Match;
}
C
전위법 (Transpose)
탐색된 항목을 바로 이전 항목과 교환하여 검색될 때마다 검색된 데이터를 점진적으로 앞으로 이동 시키는 방법
빈도 계수법 (Frequency Count)
데이터 집합 내의 각 요소들이 탐색된 횟수를 별도의 공간에 저장해 두고, 탐색된 횟수가 높은 순으로 데이터 집합을 재구성하는 전략의 알고리즘
