반응형
순차 검색은 데이터를 검색하기 위한 가장 기초적인 검색 방법 하나 이다.
1. 자료가 미리 정렬되지 않은 경우의 순차 검색
- 모든 자료를 처음부터 마지막까지 순차적으로 모두 비교하며 검색한다.
그러므로 데이터가 자료에 있는지 없는지 여부는 검색을 마지막까지 모두 검색한 후에나 확인 가능하다.
2. 자료가 미리 정렬된 경우의 순차 검색
- 이 경우도 위와 동일하게 처음부터 마지막까지 순차적으로 모두 비교하며 검색한다.
하지만 위의 경우와는 다르게 데이터가 정렬되 있으므로, 자료가 조건에 만족하지 못한다면,
중간에 데이터 유무를 확인할 수 있다.
3. 색인 순차 검색
색인 순차 검색은
자료의 Index를 가지고 검색하는 방식으로 기존의 데이터의 Index에 해당하는 데이터를 가지고
검색하므로 검색의 효율을 높인다.
순차검색은 모든 데이터 순차적으로 비교해야 하지만 색인 순차검색은 일정 간격으로 저장하기 때문에 찾아야 하는
전체 자료의 갯수가 감소하므로 더 효율적이다.
Index_Search.h
#ifdef _INDEX_SEARCH_ #endif _INDEX_SEARCH_ typedef struct Index_Search{ int data; int position; }Index_Table; void Create_Index_Table(int data[], int data_count, int index_size); int Index_Searching(int data[], int data_size, int search_data);
Index_Search.c
#include"Index_Search.h" #include<stdlib.h> #include<stdio.h> Index_Table* table; static int table_size=0; void Create_Index_Table(int data[], int data_size, int index_size) { int i; //인덱스 테이블의 크기가 데이터 의 크기보다 클때 if (index_size>data_size) return; //Index 테이블 동적할당 table = (Index_Table*)malloc(sizeof(Index_Table)*index_size); table_size=index_size; for(i=0;i<index_size;i++) { table[i].position=(data_size/index_size)*i; table[i].data=data[(data_size/index_size)*i]; } return ; } int Index_Searching(int data[],int data_size, int search_data) { int i,j; //범위 벗어난 데이터 검색 실패 if(data[0]>search_data||data[data_size-1]<search_data) return 0; for(i=0;i<table_size;i++) { if(search_data<table[i].data) //찾는 데이터가 테이블의 데이터보다 작다면 for(j=table[i-1].position;j<table[i].position;j++) //테이블 전의 데이터의 위치부터 현재 데이터까지 검색 if(data[j]==search_data) return 1; //데이터 찾으면 1 반환 } //위의 조건을 만족하지 못한다면, 테이블의 최고 인덱스의 position부터 //data 배열의 최고 인덱스 까지 검색 for(j=table[i].position;j<data_size;j++) if(data[j]==search_data) return 1; return 0; }
반응형
'ETC > Data Struct | Algorithm' 카테고리의 다른 글
정렬 - 삽입 정렬 (0) | 2012.09.11 |
---|---|
정렬 - 퀵 정렬(Quick Sort) (0) | 2012.09.10 |
정렬 - 버블 정렬 (Bubble_Sort) (0) | 2012.09.10 |
정렬 - 선택 정렬 (Selection Sort) (0) | 2012.09.10 |
연결리스트 (LinkedList) (0) | 2012.09.09 |