[Do it! 자료구조와 함께 배우는 알고리즘 입문 C언어편] 03장 검색

etc./Do it! 공부단

innit 2021. 8. 30. 22:11

1. 책 DB를 넣어주세요.

2. 나의 스터디 흔적을 사진으로 보여주세요.

3. 이번 스터디에서 특별히 좋았던 점이나 어려웠던 점이 있었나요? 새로 알게된 부분이 있다면 알려주세요. 다음에 이 책으로 공부할 스터디룸의 독자들에게 큰 도움이 됩니다.

- (p.96) 검색의 종류

1) 배열 검색

- 선형 검색

- 이진 검색

- 해시

2) 선형리스트 검색

3) 이진탐색트리 검색

- (p.104) 선형 검색

원리 : 배열의 끝까지 도달하면 return -1; 킷값과 동일한 요소를 발면하면 return i;

보완 : 보초법(sentinel), 배열의 맨 마지막에 킷값(보초)을 추가해서 종료조건을 2개에서 1개로 줄이기

- (p.106) 이진 검색

원리 : 맨 앞 인덱스 pl, 중앙 인덱스 pc, 맨 뒤 인덱스 pr 설정 후 a[pc]와 킷값을 비교해나가기

(do ~ while문 사용!)

- (p.116) bsearch 함수★

- 유틸리티 함수

- 정렬된 배열에서 검색하는 함수

- 같은 요소가 여러 개 존재하는 경우, 항상 가장 앞쪽 요소를 찾는 건 아니다

- 헤더 : #include <stdlib.h>

- 형식 : void *bsearch (const void *key, 키 값

const void *base, 배열 포인터

size_t nmemb, 요소 개수

size_t size, 요소 크기

int(*compar)(const void *, const void *) 비교함수

);

- 비교함수

- 역할 : bsearch함수 내에서 '키 값'과 '배열의 요소'를 비교

- 비교대상의 자료형마다 비교 방법이 다르기 때문에 상황에 맞게 사용자가 직접 작성해줘야 한다.

- 지켜줘야하는 규칙

- 첫 요소 < 뒷 요소 : 음수 반환

- 첫 요소 > 뒷 요소 : 양수 반환

- 첫 요소 = 뒷 요소 : 0 반환

- (p.123) 함수 포인터★

double func (int);	int형을 받아들여 double형을 반환하는 함수
double (*fp) (int);	"int형을 받아들여 double형을 반환하는 함수"를 가르키는 포인터
double *fn (int);	int형을 받아들여 "double형을 가르키는 포인터"를 반환하는 함수