자료구조(탐색)

목차

1. 정의
2. 전제조건
3. 자료의 정의
4. 탐색 작업의 구분

1. 선형 탐색(Linear Search)
2. 제어 탐색(Controlled Search)
3. 블록 탐색(Block Search)
4. 트리탐색(Tree Search
5-1. 해싱(Hashing)
5-2. 해싱함수(Hashing Function)의 종류
5-3. 과잉 상태의 처리

본문내용

1. 선형 탐색(Linear Search)

1) 정의 : 모든 레코드를 대상으로 처음부터 하나씩 차례로 비교하면서 마지막 레코드
까지 일치하는 것을 찾아 순차적으로 조사하는 것

2) 방법
① 레코드를 주어진 조건(Key)으로 순차적으로 검색하는 방법
② 주어진 조건(Key)을 첫번째 원소의 키 값으로 설정 후 검색하는 방법
③ 레코드를 일단 순서대로 정렬한 후에 순처적으로 검색하는 방법

3) 탐색장(search length)
파일 내의 특정 레코드를 찾기 위한 비교 횟수를 말한다. 일반적으로 선형탐색의 성능은 탐색장의 평균 비교 횟수(average search length)로 나타낼 수 있다.
임의의 레코드 Ri 는 그 레코드에 접근하는 확률 Pi를 갖는다고 하자. Pi는 예측하기가 모호하므로 n개의 레코드 각각이 나타나는 확률이 같다고 가정하면 레코드 Ri의 확률값은 1/n이 된다.

참고 자료

없음