[C] Binary Search, Sequential Search(이진찾기, 순차적찾기) 단어검색

/* squential search, binary search
   단어 찾기 프로그램
	작성자 : 김영준
	날짜 : 2013/10/3
*/
#include <stdio.h>
#include <string.h>

// 전역선언
typedef struct words {
	char words[30];	// 파일중 제일 긴 단어 22자
} Words;

const int MAX_SIZE = 26000;

// 기본형선언
void readWords(Words* wordsArray, int* last);
void seqSearcah(Words wordsArray[], int last); 
void binarySearch(Words wordsArray[], int last);

int main(void) {
// 지역정의 
	Words wordsArray[MAX_SIZE];
	int last = 0;

// 문장들
	readWords(wordsArray, &last);
	seqSearch(wordsArray, last);
	printf("\n");
	binarySearch(wordsArray, last);
	return 0;
} // main

/* ================= readWords =================
	파일을 읽어서 배열에 적재한다.
	사전조건		wordsArray는 채워져야 할 배열
				last는 마지막 요소의 인덱스
	사후조건		배열이 채워짐
*/
void readWords(Words* wordsArray, int* last) {
// 지역변수
	char buf[256];
	FILE* fp = fopen("/usr/dict/words", "r");

// 문장들
	if(fp == NULL) {
		printf("File is null\n");
		exit(1);
	}

	printf("단어 읽는 중");
	while(fgets(buf, sizeof(buf), fp) != NULL) {
			//개행문자 삭제
			buf[strlen(buf)-1] = 0;
			// 문자열 복사 함수 strcpy() 사용.
			strcpy(wordsArray[*last].words, buf);
			(*last)++;
			if(*last % 1000 == 0) {
				printf(".");
			}
	}
	printf("%d 단어의 사전 구축 완료\n", *last);
	fclose(fp);
} // readWords

/* ================= seqSearch =================
	순차적 찾기로 목표를 찾는다.
	모두 찾고나면 결과를 출력한다.
	사전조건		wordsArray는 데이터를 가지고 있는 배열
				last는 마지막 요소의 인덱스
*/
void seqSearch(Words wordsArray[], int last) {
	int looker;
	char target[256];

	printf("영어 단어 찾기(Sequential Search)\n");
	printf("==================================\n");

	while(1) {
		looker = 0;
		printf("단어 입력(quit:ESC) : ");
		fgets(target, sizeof(target), stdin);
		// 개행문자 삭제
		target[strlen(target)-1] = 0;

		if(target[0] == 27){
			printf("Program quit...\n");
			break;
		}

		// seqSearch
		while(looker < last && strcasecmp(target, wordsArray[looker].words)) {
			looker++;
		}

		// 결과 출력
		if(!strcasecmp(target, wordsArray[looker].words)) {
			printf("단어 %s 찾음 비교횟수 : %d\n", target, looker+1);
		} else {
			printf("단어 %s 찾기실패 비교횟수 : %d\n", target, looker+1);
		}
	}

	printf("==================================\n");
	printf("Sequential search 끝\n");

} // seqSearch

/* ================= binarySearch =================
	이진 찾기로 목표를 찾는다.
	모두 찾고나면 결과를 출력한다.
	사전조건		wordsArray는 데이터를 가지고 있는 배열
				last는 마지막 요소의 인덱스
*/
void binarySearch(Words wordsArray[], int end) {
// 지역변수
	int looker;
	char target[256];
	int first, mid, last;
	int cnt = 0;

// 문장들
	printf("영어 단어 찾기(binary Search)\n");
	printf("==================================\n");
	
	while(1) {
		looker = 0;
		first = 0;
		last = end;
		cnt = 0;

		printf("단어입력(quit:ESC) : ");
		fgets(target, sizeof(target), stdin);
		// 개행문자 삭제
		target[strlen(target)-1] = 0;

		if(target[0] == 27) {
			printf("Program quit...\n");
			break;
		}

		// binarySearch
		while( first <= last) {
			mid = (first + last) / 2;
			if(0 < strcasecmp(target, wordsArray[mid].words)) {
				first = mid + 1;
			} else if(0 > strcasecmp(target, wordsArray[mid].words)) {
				last = mid - 1;
			} else {
				break;
			}
			cnt++;
		}

		// 결과 출력
		if(!strcasecmp(target, wordsArray[mid].words)) {
			printf("단어 %s 찾음 비교횟수 : %d\n", target, cnt+1);
		} else {
			printf("단어 %s 찾기실패 비교횟수 : %d\n", target, cnt+1);
		}

	}

	printf("==================================\n");
	printf("Sequential search 끝\n");
} // binarySearch