이진 탐색 질문드립니다.
아더
질문 제목 : txt를 읽어와 이진탐색을 하는 소스
stack overflow가 걸리는데 어느쪽에서 걸리는지를 모르겠내요.
질문 내용 :
#includestdio.h
#include string.h
#includestdlib.h
#define max 500 // 이진 탐색에 사용합니다.
#define find 30 //검색에 사용합니다.
#define _crt_secure_no_warnings
int binary(int firstline, int finalline,int serchnum, char serchkey[], char** key); //이진 탐색을 위한 함수 선언입니다.
int main(){
int line = 0; //읽어온 파일의 총 라인 수를 계산하기 위한 변수
int serchnum = 0; // 검색 후 단어의 위치를 저장하는 변수입니다.
int fline = 1; //검색 시작에 사용될 변수입니다.
char** keycode; //검색할 단어를 저장하는 변수입니다.
char serchkey[find];
int i = 0; //반복문에 사용될 변수입니다.
int j = 0;
file * file = fopen(news_data.txt, rt); // 파일을 엽니다.
if(file == null) // 이상이 있는지 체크합니다.
{
printf(파일을 못 읽었습니다.!\n);
return 0; // 종료
}
keycode = (char**)malloc(sizeof(char*)* max); //힙 영역에 저장하기 위해 keycode를 동적으로 할당합니다.
for( j=0; jmax; j++ ){
keycode[j] = (char*) malloc(sizeof( char )*max);
}
printf(------ 프로그램 시작 --------\n);
while(1) // 반복문을 시작합니다.
{
if(feof(file) != 0) // 파일을 끝까지 읽었는지 확인을 합니다.
break;
fgets(keycode[i], max, file); //keycode에 파일에서 읽어온 값들을 저장합니다.
i++;
line++; // 한 줄을 읽었으니 라인수를 증가시킵니다.
}
printf(총 단어의 개수는 %d 입니다.\n\n,line);
printf(검색 할 단어를 선택하세요.:);
scanf(%s, &serchkey); //검색 할 단어를 입력합니다.
serchnum = binary(fline,line,serchnum,serchkey,keycode); // serchnum에 binary함수에서 반환된 정수값을 대입합니다.
printf(-----검색 종료----- \n);
printf(당신이 찾은 단어는 %d 번째 단어입니다.\n,serchnum); //serchnum값을 출력하고 종료합니다.
for(j=0; jmax; j++ ) //동적으로 할당된 영역을 해제합니다.
{
free(keycode[j]);
}
free(keycode);
return 0;
}int binary(int firstline, int finalline,int serchnum, char serchkey[], char** key){
int first, final, center; //이진 탐색을 위해 첫번째, 가운데, 마지막 변수를 선언합니다.
int result; //strcmp 실행 후 리턴값 반환이 되는 변수를 선언합니다
int j;
first = firstline;
final = finalline; //first에 1을, final에 위에서 읽었던 마지막 줄의 수를 대입합니다.
center = (first + final) / 2; //파일의 가운데에 있는 단어를 대입합니다.
result = strcmp(serchkey,key[center]); //result에 두 단어를 비교한 리턴 값을 대입합니다.
serchnum = center;if(result == 0) //result가 0이라면 해당 단어를 찾은 것이므로 결과값을 리던하고 종료하게 됩니다.
return serchnum;
else if(result 0){ //result 가 0보다 작다면 검색하는 단어가 중간의 단어보다 앞에 있게 됩니다.
final = center - 1;
return binary(firstline, final,serchnum, serchkey, key);
}
else if(result 0){ //result 가 0보다 크다면 컴색하는 단어가 중간의 단어보다 뒤에 있게 됩니다.
first = center + 1;
return binary(first, final, serchnum, serchkey, key);
}
else{
printf(맞는 단어를 찾지 못하였습니다.\n);
return 0;
}
}
저번에 답변주신대로 열심히 궁리해서 결국 실행이 되었습니다. 하지만
이렇게 하고 실행을 하면 검색 부분에서 stack overflow가 걸려 진행이 안됩니다.
keycode도 동적 할당을 하였는데 어느부분에서 문제가 생기는지를 모르겠습니다.ㅠㅜ
-
헤벌심
문자열을 비교한 뒤 처음과 마지막이 같다면 재귀를 호출하지말고 끝내는 것도 필요할 겁니다
-
연초록
아!!! 해결했습니다. 검색하는 단어를 fgets로 받아버리니까 해결되는군요 ㅠㅠ
이거때문에 며칠을 고생했는지 ㅠㅠ
답변 감사드려요 덕분에 많이 배우고 갑니다^^ -
채꽃
줄내림 제거를 추가해서 되는가 싶었는데 마지막단어만 검색되고 나머진 역시 오버플로가 걸리내요...
while(1) // 반복문을 시작합니다.
{
if(feof(file) != 0) // 파일을 끝까지 읽었는지 확인을 합니다.
break;
\t\tfgets(keycode[i], MAX, file);
\t\t**(keycode+(strlen(keycode[i])-1))=0; //이렇게 추 -
든솔
fgets함수로 입력받으면 줄내림문자까지 함께 입력받게 됩니다. 입력받은 뒤에 줄내림 문자를 없애는 루틴을 추가하세요. 아니면 어짜피 찾고자 하는 키워드를 \%s\로 받으니 fgets 대신에 scanf(\%s\)로 입력받아도 되구요.