순서 찾기 표 와 색인 찾기 표

검색 표 (search table) 는 같은 유형의 데이터 요소 (또는 기록) 로 구 성 된 집합 입 니 다.
검색 표 에 대한 동작 은 다음 과 같 습 니 다.
(1) 특정한 데이터 요소 가 검색 표 에 존재 하 는 지 조회 합 니 다.
(2) 특정한 데이터 요소 의 각종 속성 을 검색 합 니 다.
(3) 검색 표 에 데이터 요 소 를 삽입 합 니 다.
(4) 검색 표 에서 데이터 요 소 를 삭제 합 니 다.
검색 만 하 는 검색 표를 정적 검색 표 (Static Search Table) 라 고 합 니 다.
검색 과정 에서 검색 표 에 존재 하지 않 는 데이터 요 소 를 동시에 삽입 하거나 검색 표 에서 존재 하 는 데이터 요 소 를 삭제 하면 이 검색 표를 동적 검색 표 (Dynamic Search Table) 라 고 합 니 다.
키워드 (Key) 는 데이터 요소 (또는 기록) 의 특정한 데이터 항목 의 값 으로 데이터 요소 (또는 기록) 를 표시 할 수 있 습 니 다. 이 키 워드 를 유일한 표지 로 기록 할 수 있다 면 이 키 워드 를 주요 키워드 (Primary Key) 라 고 부 르 고 여러 기록 을 식별 하 는 다른 키 워드 를 차 키워드 (Secondary Key) 라 고 부 릅 니 다.데이터 요소 가 하나의 데이터 항목 만 있 을 때 그 키 워드 는 바로 이 데이터 요소 의 값 입 니 다.
검색 (Searching) 은 주어진 값 에 따라 검색 표 에서 키 워드 를 지정 한 값 의 기록 이나 데이터 요 소 를 확인 합 니 다.표 에 이러한 기록 이 존재 한다 면 찾 는 것 은 성공 적 이 고 존재 하지 않 으 면 찾 는 데 성공 하지 못 하고 '빈' 기록 이나 빈 지침 을 드 립 니 다.
전형 적 인 키워드 유형 설명 은 다음 과 같다.

typedef float KeyType; //  
typedef int KeyType; //  
typedef char *KeyType; //   

 데이터 요소 형식 정의:

typedef struct{
    KeyType key; //    
    ... //  
}

 두 키 워드 를 비교 하 는 매크로 정 의 는 다음 과 같 습 니 다.

//--       
#define EQ(a,b) ((a) == (b))
#define LT(a,b) ((a) < (b))
#define LQ(a,b) ((a) <= (b))

...

//--       
#define EQ(a,b) (!strcmp((a),(b)))
#define LT(a,b) (strcmp((a),(b)) < 0)
#define LQ(a,b) (strcmp((a),(b)) <= 0)

1 정적 탐색 표
추상 데이터 형식 정적 탐색 표 정 의 는 다음 과 같 습 니 다.

ADT StaticSearchTable{
      D:D               ，              ，             。
      R：          。
      P:
    Create(&ST,n);
          ：     n           ST。
    Destroy(&ST);
          ：     ST  。
          ：   ST。
    Search(ST,key);
          ：     ST  ，key             。
          ： ST         key     ，                 ，   “ ”。
    Traverse(ST,visit());
          ：     ST  ，visit           。
          ：      ST         visit()  。
}ADT StaticSearchTable;

1.1 순서 표 찾기
 

//-----------             ------------
typedef struct{
    Element *elem;//          
    int length;
}SSTable;

순차 탐색 표 구현 (Sequential Search):
    표 의 마지막 기록 부터 하나씩 기 록 된 키워드 와 주어진 값 을 비교 합 니 다. 만약 에 특정한 기록 의 키워드 와 주어진 값 이 성공 하면 성공 을 찾 습 니 다. 반대로 첫 번 째 기록 까지 성공 적 으로 비교 하지 못 하면 성공 하지 못 합 니 다.
 

int search_seq(SSTable ST,KeyType key){
    int i;
    //    ST         =key     ，
    //   ，              ，   0.
    ST.elem[0].key = key;//  
    for(i=ST.length;!ST.item[i].key == key;--i) //     
    return i; //    ，i =0
}//search_seq

작업 의 성능 분석 찾기:
하나의 알고리즘 의 좋 고 나 쁨 을 평가 하 는 양 도 는 세 가지 가 있다.
시간 복잡 도
공간 복잡 도 (알고리즘 을 평가 하 는 데이터 구조 가 차지 하 는 저장 및 대량의 추가 저장)
알고리즘 의 기타 성능
일반적으로 '그 키워드 와 주어진 값 을 비교 한 기록 개수 의 평균 값' 을 알고리즘 의 좋 고 나 쁨 을 평가 하 는 근거 로 한다.
평균 검색 길이 (Average Search Length): 검색 표 에 기 록 된 위 치 를 확인 하기 위해 주어진 값 과 비교 해 야 할 키워드 갯 수 에 대한 기대 입 니 다.
(1) 등 확률 의 경우 순서대로 검색 에 성공 한 평균 검색 길 이 는 다음 과 같 습 니 다.
(n+1)/2
 
(2) 검색 에 성공 하지 못 한 평균 검색 길 이 는?
n+1
(3) 검색 이 성공 하지 못 할 확률 을 무시 할 수 없 을 때 검색 성공 과 검색 이 성공 하지 못 할 확률 이 같다 고 가정 하면 순서대로 찾 는 평균 검색 길 이 는 다음 과 같다.
3(n+1)/4
 
순서 찾기 의 단점: n 이 클 때 찾기 효율 이 낮 습 니 다.
 
1.2 질서 표 찾기
반절 찾기 (Binary Search): 검색 대기 기록 이 있 는 범 위 를 확인 한 다음 에 기록 을 찾 거나 찾 지 못 할 때 까지 범 위 를 점차적으로 좁 힙 니 다.
순서대로 찾 는 검색 과정 은 다음 과 같 습 니 다.
(1) 조사 대기 기록 이 있 는 범 위 를 확정 하고 구간 범 위 를 [low, high] 로 설정한다.
(2) 이 구간 중간 위치 에 있 는 값 mid, mid = [low + high] / 2 구하 기;
(3) 주어진 key 값 을 질서 표 의 mid 에 기 록 된 키워드 ST. item [mid]. key 와 비교 합 니 다.
(3.1) key = = = ST. item [mid]. key 를 찾 으 면 성공 합 니 다.
(3.2) key < ST. item [mid]. key 의 경우 high = mid - 1, high 가 low 보다 작은 지 판단 하고, high < low 의 경우 검색 에 성공 하지 못 합 니 다. 그렇지 않 으 면 조사 대기 기록 은 새로운 구간 [low, high] 에서 계속 실행 할 수 있 습 니 다 (2)
(3.3) key > ST. item [mid]. key 의 경우 low = mid + 1 로 high 가 low 보다 작은 지 판단 하고, high < low 의 경우 찾 는 데 성공 하지 못 합 니 다. 그렇지 않 으 면 조사 대기 기록 은 새로운 구간 [low, high] 에서 절 차 를 계속 수행 할 수 있 습 니 다 (2).
알고리즘 구현 은 다음 과 같 습 니 다.
 

int binarySearch(STable ST,KeyType key){
	int mid,low=0,high=ST.length;
	while(low <=high){
		mid = (low+high)/2;
		if(ST.item[mid].key == key) return mid;
		elseif(ST.item[mid].key < key) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}

 
반 으로 접어 서 찾 는 과정 은 이 진 트 리 로 표시 할 수 있 습 니 다.
판정 트 리 는 검색 과정 을 설명 하 는 이 진 트 리 입 니 다.
절반 으로 나 누 어 찾 을 때 주어진 값 과 비교 하 는 횟수 는 [log (2) n] + 1 회 입 니 다.
(1) 검색 에 성 공 했 을 때의 평균 검색 길이:
ASL = (n+1)/n * log(2)(n+1) - 1
n > 50 시
ASL = log(2)(n+1)-1
(2) 검색 에 성공 하지 못 했 을 때의 평균 검색 길이
uASL = log(2)(n+1)
절반 으로 나 누 어 찾 는 장점: 순서대로 찾 는 것 보다 효율 이 높다.
단점: 질서 표 에 만 적용 되 고 순서 저장 구조 로 선형 링크 에 사용 할 수 없습니다.
 
1.3 색인 순서 표 찾기
 
색인 순서 표 는 데 이 터 를 저장 하 는 순서 표 (주 표 라 고 함) 와 색인 표 두 부분 을 포함한다. 순서 표 는 약 간 자 표 (블록 이 라 고도 함) 로 나 뉜 다.전체 순서 표 가 질서 가 있 거나 블록 이 질서 가 있 습 니 다. 각 하위 표 의 최대 키 워드 를 꺼 내 고 이 키 워드 를 가리 키 는 하위 표 의 첫 번 째 요 소 를 기록 하 는 지침 을 추가 하면 하나의 색인 항목 을 구성 합 니 다. 이 색인 항목 을 키워드 증가 순서에 따라 배열 하면 색인 표 가 됩 니 다.
색인 순서 표 는 블록 별로 찾 을 수 있 으 며 과정 은 두 단계 로 나 뉜 다.
(1) 조사 대기 기록 이 있 는 하위 표 (블록) 를 확인 합 니 다. 색인 표 는 키워드 에 따라 질서 있 게 배열 되 어 있 기 때문에 색인 표 에 대해 서 는 절반 으로 찾 을 수 있 습 니 다. 만약 에 조사 대기 기록 키워드 의 key 값, < = i 키 표 의 최대 키워드, 그리고 i - 1 키 표 의 최대 키워드, 즉 K (i - 1) < key < K (i) 보다 크 면 조사 대기 키 워드 는 i 키 표 에 있 습 니 다.
(2) 확 정 된 하위 표 에서 조사 대기 기록 의 위 치 를 확인한다. 하위 표 의 기록 이 반드시 키워드 에 따라 질서 있 게 배열 되 지 않 기 때문에 순서대로 찾 을 수 밖 에 없다.
색인 표 형식 정 의 는 다음 과 같 습 니 다.
 

#define MAXLEN <       >
typedef int keytype;
typedef struct{
    keytype key;
    int link;
}IndexType;//       
typedef IndexType IDX[MAXLEN+1];//     ，   1  

 
 색인 표 찾기 알고리즘:
 

IndxSearch(IDX idx,int b,STable,keytype key){
    int s = ST.length / b; //b         ，s          
    int i,j;
    for(i=1;i<b+1;i++)
        if(key <= idx[i]) break;
    if(i == b+1) return 0;//         

    //  ，    idx[i].link  ，    0  ，   if  j == idx[i].link-1
    for(j = idx[i].link+s-1;key!=ST.item[j].key;j--);
    if(j == idx[i].link-1) return 0;    
    else return j;
}

   
일반적인 상황 에서 블록 찾기 를 위해 길이 가 n 인 시 계 를 b 블록 으로 고 르 게 나 눌 수 있 습 니 다. 각각 s 개의 요소, 즉 b = [n / s] 가 있 습 니 다. 색인 표 가 순서대로 찾 으 면 성공 할 때의 평균 검색 길 이 는 다음 과 같 습 니 다.
(s+b+2)/2
색인 표 가 절반 으로 찾 으 면 성공 할 때의 평균 검색 길 이 는 다음 과 같 습 니 다.
log(2)(n/s+1)+s/2