연습문제_Q1 > search 함수를 while문이 아닌 for문을 사용하여 프로그램을 수정하시오. (search함수는 보초법 사용)
#include <stdio.h>
#include <stdlib.h>
int search(int a[], int n, int key)
{
int i = 0;
a[n] = key;
for(i=0; i <=n ; i++) {
if(a[i] == key) //포문이 여기서 꼭 걸리게 됌. (보초법으로 인해 i=n일땐 무조건)
break;
}
return i==n?-1:i;
}
int main() {
int i, nx, ky, idx;
int *x;
puts("선형 검색(보초법)");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx+1, sizeof(int));
for(i = 0; i< nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
printf("검색값 : ");
scanf("%d", &ky);
idx = search(x, nx, ky);
if(idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
free(x);
return 0;
}
연습문제_Q2 > 선형 검색의 스캐닝 과정을 상세하게 표현하는 프로그램을 작성하세요.
참고로 나는 보초법 기반으로 작성하였다.
#include <stdio.h>
#include <stdlib.h>
int search(int a[], int n, int key)
{
printf(" |");
for(int z=0; z<=n; z++){
printf("%3d", z);
}
printf("\n---+");
for(int z=0; z<=n; z++){
printf("---");
}
putchar('\n');
int i = 0;
a[n] = key;
for(i=0; i <=n ; i++) {
printf(" |");
for(int x=0; x<i; x++)
printf(" ");
printf(" *\n");
printf("%3d|", i);
for(int q=0; q<=n; q++) {
printf("%3d", a[q]);
}
putchar('\n');
if(a[i] == key)
break;
printf(" |\n");
}
return i==n?-1:i;
}
int main() {
int i, nx, ky, idx;
int *x;
puts("선형 검색(보초법)");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx+1, sizeof(int));
for(i = 0; i< nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
printf("검색값 : ");
scanf("%d", &ky);
idx = search(x, nx, ky);
if(idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
free(x);
return 0;
}
연습문제_Q3 > 요소의 개수가 n인 배열 a에서 key와 일치하는 모든 요소의 인덱스를 배열 idx의 맨 앞부터 순서대로 저장하고, 일치한 요소의 개수를 반환하는 함수 int search_idx(const a[], int n, int key, int idx[]) 를 작성하세요.
#include <stdio.h>
#include <stdlib.h>
int search_idx(const int a[], int n, int key, int idx[]) {
int counter=0;
for(int i=0; i<n ;i++) {
if(a[i]==key)
idx[counter++]=i;
}
return counter;
}
int main() {
int N; // 전체 요소 갯수
int *p;
int *p2;
int key; // 찾을 값
int num; // 일치하는 요소의 갯수
printf("요소의 갯수 : ");
scanf("%d", &N);
p = calloc(N, sizeof(int));
p2 = calloc(N, sizeof(int));
printf("요소 값들 : ");
for(int i=0; i<N; i++)
scanf("%d", &p[i]);
printf("찾을 값 : ");
scanf("%d", &key);
num = search_idx(p, N, key, p2);
for(int i=0; i<num; i++) {
printf("%d ", p2[i]);
}
free(p);
free(p2);
return 0;
}
연습문제_Q4 > 이진 검색의 과정을 자세히 출력하는 프로그램을 작성하세요.
#include <stdio.h>
#include <stdlib.h>
int bin_search(const int a[], int n, int key) {
printf(" |");
for(int i=0; i<n; i++)
printf("%3d", i);
printf("\n---+");
for(int i=0; i<n; i++)
printf("---");
putchar('\n');
int pl = 0;
int pr = n - 1;
int pc;
do {
pc = (pl + pr) / 2;
printf(" |");
for(int i=0; i<n; i++) {
if(i==pl)
printf(" <-");
else if(i==pc)
printf(" +");
else if(i==pr)
printf(" ->");
else
printf(" ");
}
putchar('\n');
printf("%3d|", pc);
for(int i=0; i<n; i++) {
printf("%3d", a[i]);
}
putchar('\n');
if(a[pc] == key)
return pc;
else if(a[pc] < key)
pl = pc + 1;
else
pr = pc - 1;
printf(" |\n");
} while(pl <= pr);
return -1;
}
int main() {
int i, nx, ky, idx;
int *x;
puts("이진 검색");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
printf("오름차순으로 입력하세요.\n");
printf("x[0] : ");
scanf("%d", &x[0]);
for(i = 1; i < nx; i++) {
do {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
} while(x[i] < x[i - 1]);
}
printf("검색값 : ");
scanf("%d", &ky);
idx = bin_search(x, nx, ky);
if(idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d는(은), x[%d]에 있습니다.\n", ky, idx);
free(x);
return 0;
}
연습문제_Q5 > 우리가 살펴본 이진 검색 알고리즘은 프로그램을 검색할 값과 같은 값을 갖는 요소가 하나 이상일 경우 그 요소 중에서 맨 앞의 요소를 찾지 못합니다. 맨 앞의 요소를 찾는 int bin_search(const int a[], int n, int key)를 작성해 보세요.
- 이진 검색 알고리즘에 의해 검색에 성공했을 때, 그 위치로부터 앞쪽으로 하나씩 검사하면 여러 요소가 일치하는 경우에도 가장 앞쪽에 위치하는 요소의 인덱스를 찾아낸다. 즉, 배열의 맨 앞을 넘지 않는 범위에서 같은 값의 요소가 계속되는 한 앞쪽으로 스캔한다.
#include <stdio.h>
#include <stdlib.h>
// 일치하는 요소가 여러개일때, 가장 맨 앞의 인덱스를 리턴하게끔 하는 bin_search2 함수
int bin_search2(const int a[], int n, int key) {
int pl = 0;
int pr = n-1;
int pc;
do {
pc = (pl + pr) / 2;
if(a[pc] == key) {
// while문 탈출조건
// 1. pc가 0보다 작아졌거나,
// 2. pc값 변화 도중 요소 값이 찾으려는 key값과 다르게 될 때
// 이므로, while 문 탈출시에는 원하는 pc값보다 하나 적어진 상태일 때가 되니 리턴은 ++pc.
// 하지만 이런식으로 구현하면 최악의 조건에 O(n)이 발생할 수 있다. 사실 이 과정도 이분탐색으로 해줘야한다.
while(--pc>=0) {
if(a[pc]!=key)
break;
} return ++pc;
}
else if(a[pc] < key)
pl = pc + 1;
else
pr = pc - 1;
} while(pl <= pr);
return -1;
}
int main() {
int i, nx, ky, idx;
int *x;
puts("이진 검색");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
printf("오름차순으로 입력하세요.\n");
printf("x[0] : ");
scanf("%d", &x[0]);
for(i = 1; i < nx; i++) {
do {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
} while(x[i] < x[i - 1]);
}
printf("검색값 : ");
scanf("%d", &ky);
idx = bin_search2(x, nx, ky);
if(idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d는(은), x[%d]에 있습니다.\n", ky, idx);
free(x);
return 0;
}
// 문제에서 주어진 정답 함수 ( pc값을 pl값과 비교하면서 처리함. )
///*--- 요솟수 n인 배열 a에서 key와 일치하는 요소를 2진 검색 (가장 앞쪽에 있는 요소를 검색) ---*/
//int bin_search2(const int a[], int n, int key)
//{
// int pl = 0; /* 검색 범위의 첫 인덱스 */
// int pr = n - 1; /* ·· 끝 인덱스 */
// int pc; /* ·· 가운데 인덱스 */
//
// do {
// pc = (pl + pr) / 2;
// if (a[pc] == key) { /* 검색 성공 */
// while (pc > pl && a[pc - 1] == key)
// pc--;
// return pc;
// }
// else if (a[pc] < key)
// pl = pc + 1;
// else
// pr = pc - 1;
// } while (pl <= pr);
//
// return -1; /* 검색 실패 */
//}
연습문제_Q6 > 요소의 값이 내림차순으로 정렬된 long형 배열에서의 검색을 bsearch 함수를 사용하여 프로그램을 작성
#include <stdio.h>
#include <stdlib.h>
// long형을 비교하는 함수(내림차순 기준)
int long_cmpr(const long *p1, const long *p2) {
if(*p1 < *p2)
return 1; //오름차순이라면 -1
else if(*p1 > *p2)
return -1; //오름차순이라면 1
else
return 0;
}
int main() {
int i, nx;
long ky;
long *x;
long *p;
puts("bsearch 함수를 사용하여 검색");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(long));
printf("내림차순으로 입력하세요.\n");
printf("x[0] :");
scanf("%ld", &x[0]);
for(i = 1; i < nx; i++) {
do {
printf("x[%d] : ", i);
scanf("%ld", &x[i]);
} while(x[i] > x[i-1]);
}
printf("검색값 : ");
scanf("%ld", &ky);
p = bsearch(&ky, x, nx, sizeof(long), (int(*)(const void *, const void *))long_cmpr);
if(p == NULL) {
puts("검색에 실패했습니다.");
} else
printf("%ld(은)는 x[%ld]에 있습니다.\n", ky, (long)(p-x));
free(x);
return 0;
}
연습문제_Q7 > bsearch 함수와 같은 형식으로 호출할 수 있는 다음 함수를 작성하세요. 단, 선형 검색 알고리즘을 사용하고, 배열은 정렬되어 있지 않아도 좋습니다.
void *seqsearch(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
#include <stdio.h>
#include <stdlib.h>
int compar(int *a, int *b) {
if(*a == *b)
return 0;
else
return 1;
}
void *seqsearch(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) {
size_t i = 0;
for(i=0; i< nmemb; i++) {
//&base[i*size] 또는 base+(i*size) 형식으로 진행할 수 있다.
if(compar(key, &base[i*size])==0) //포인터 연산. size에 맞게 다음 요소의 주소를 찾음.
break;
}
return i==nmemb ? NULL : &base[i*size];
}
int main() {
int *p;
int N;
int key;
int *pp;
printf("요소 갯수 : ");
scanf("%d", &N);
p = calloc(N, sizeof(int));
printf("순서대로 요소 나열 : ");
for(int i=0; i< N; i++) {
scanf("%d", &p[i]);
}
printf("찾을 값 : ");
scanf("%d", &key);
pp = seqsearch(&key, p, N, sizeof(int), (int(*)(const void *, const void *))compar);
if(pp==NULL)
printf("값 찾기 실패");
else
printf("x[%d]에 있습니다.", pp-p);
free(p);
return 0;
}
연습문제_Q8 > bsearch 함수와 같은 형식으로 호출할 수 있는 다음 함수를 이진 검색 알고리즘을 사용하여 작성하세요.
void *binsearch(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));
#include <stdio.h>
#include <stdlib.h>
//오름차순 기준
int compar(int *a, int *b) {
if(*a < *b)
return -1;
else if(*a > *b)
return 1;
else
return 0;
}
void *binsearch(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) {
size_t pl = 0;
size_t pr = nmemb -1;
size_t pc;
do {
pc = (pl + pr) / 2;
switch(compar(key, base+(size*pc))) {
case 0:
return base+(size*pc);
case 1:
pl = pc + 1;
break;
case -1:
pr = pc - 1;
break;
}
}while (pl<=pr);
return NULL;
}
int main() {
int *p;
int N;
int key;
int *pp;
printf("요소 갯수 : ");
scanf("%d", &N);
p = calloc(N, sizeof(int));
printf("순서대로 요소 나열 : ");
for(int i=0; i< N; i++) {
scanf("%d", &p[i]);
}
printf("찾을 값 : ");
scanf("%d", &key);
pp = binsearch(&key, p, N, sizeof(int), (int(*)(const void *, const void *))compar);
if(pp==NULL)
printf("값 찾기 실패");
else
printf("x[%d]에 있습니다.", pp-p);
return 0;
}
+ Q. bsearch함수를 구현하면서, 10 20 30 40 50 이렇게 요소들을 나열하고 찾는 값을 0이나 1 2 같은 숫자를 넣었을 때 내가 짠 프로그램이나 정답으로 제공해준 프로그램이나 둘 다 [-1] 요소에서 찾았다거나 프로그램 런타임 에러가 뜨던데.. 이 원인은 아직 모르겠음
-> 알아냄.
이진탐색 알고리즘이 pl = 0이고 pr = 1인 경우 pc = 0 + 1 / 2 = 0이 되는 특성으로부터, 찾는 값이 더 작고 동시에 요소에 없는 값일 경우로부터 비롯될 수 있는 예외사항이다.
pl = 0, pr = 1, pc = 0 인 경우, 찾으려는 값이 배열의 첫번째 인자보다 작게 입력된 값일 경우에 pr = pc - 1이 되는데, size_t 형 변수 pr이 0 - 1의 결과인 마이너스 값을 갖게 되면서 발생하는 오류다. size_t 형 변수에 -1가 들어가면 -1이 저장되는 게 아니라 에러를 뿜으며 의미없는 쓰레기값이 들어간다.
이를 해결하기 위한 두 가지 방법이 있다.
한가지는 간단하게 형변환하는 방법. size_t형 변수를 사용하지 않으면 된다.
int pl = 0;
int pr = (int)nmemb -1;
int pc;
이런식으로 pl, pr, pc를 int형 변수로 선언하고 size_t형 변수를 int형으로 형변환한다.
그러면 pr에 값에 -값이 들어가면 알아서 while(pl<=pr)에서 반복문을 종료시키고 return NULL이 처리된다.
다른한가지는 size_t 형을 그대로 고수하되, 예외처리를 해주는 방법.
원래대로 size_t pr, pc ,pl을 선언해주고 이를 nmemb과 통일하여 잘 연산시켜준 뒤, 배열의 처음이나 끝을 넘어가는 경우를 if문으로 필터링해줬다. (가장 큰 요소보다 더 큰 값을 입력해도 어차피 pl<=pr에서 걸리므로 배열의 끝을 넘어가는 경우는 생기지 않는 것 같은데 하는김에 그냥 해줬다.)
#include <stdio.h>
#include <stdlib.h>
//오름차순 기준
int compar(int *a, int *b) {
if(*a < *b)
return -1;
else if(*a > *b)
return 1;
else
return 0;
}
void *binsearch(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) {
size_t pl = 0;
size_t pr = nmemb -1;
size_t pc;
do {
pc = (pl + pr) / 2;
switch(compar(key, base+(size*pc))) {
case 0:
return base+(size*pc);
case 1:
if(pc+1<nmemb)
pl = pc + 1;
else
return NULL;
break;
case -1:
if(pc!=0)
pr = pc - 1;
else
return NULL;
break;
}
}while (pl<=pr);
return NULL;
}
int main() {
int *p;
int N;
int key;
int *pp;
printf("요소 갯수 : ");
scanf("%d", &N);
p = calloc(N, sizeof(int));
printf("순서대로 요소 나열 : ");
for(int i=0; i< N; i++) {
scanf("%d", &p[i]);
}
printf("찾을 값 : ");
scanf("%d", &key);
pp = binsearch(&key, p, N, sizeof(int), (int(*)(const void *, const void *))compar);
if(pp==NULL)
printf("값 찾기 실패");
else
printf("x[%d]에 있습니다.", pp-p);
return 0;
}
이렇게 하면 size_t의 자료형에 마이너스 값이 들어가지 않게 되면서 에러를 피할 수 있다.
책의 예외 오류를 찾아 내가 개선한 것 같은데, 이거 제보를 해야하나..?? 기분은 좋다.
연습문제_Q9 > bsearch 함수와 같은 형식으로 호출할 수 있는 다음 함수를 작성하세요. 이진 알고리즘을 사용하여 일치하는 요소의 검색에 성공하면 그 위치에서 앞쪽으로 선형 검색을 수행하여 가장 앞쪽의 요소에 대한 포인터를 반환하는 함수를 작성하세요.
void *bsearchx(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
이번엔 위에 Q8의 예외를 해결하기 위해 int 형변환 방법을 사용했다.
#include <stdio.h>
#include <stdlib.h>
//오름차순 기준
int compar(int *a, int *b) {
if(*a < *b)
return -1;
else if(*a > *b)
return 1;
else
return 0;
}
void *bsearchx(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) {
int i = 0;
int pl = 0;
int pr = (int)nmemb -1;
int pc;
do {
pc = (pl + pr) / 2;
switch(compar(key, base+(size*pc))) {
case 0:
// while문 탈출 조건
// 1. --pc가 0보다 작아진 경우
// 2. 연산된 pc의 인덱스에 해당하는 값이 key값과 다를 경우
// 따라서 while문 탈출시에는 원하는 pc값보다 하나 작아진 상태이므로 ++pc를 사용해줘야함.
// -> 0보다 작아졌거나, 값이 다를 경우 while문을 탈출하게 되므로 ++pc한 값을 리턴.
while(--pc>=0) {
if(compar(key, base+(size*pc))!=0)
break;
}
return base+(size*++pc);
case 1:
pl = pc + 1;
break;
case -1:
pr = pc - 1;
break;
}
}while (pl<=pr);
return NULL;
}
int main() {
int *p;
int N;
int key;
int *pp;
printf("요소 갯수 : ");
scanf("%d", &N);
p = calloc(N, sizeof(int));
printf("순서대로 요소 나열 : ");
for(int i=0; i< N; i++) {
scanf("%d", &p[i]);
}
printf("찾을 값 : ");
scanf("%d", &key);
pp = bsearchx(&key, p, N, sizeof(int), (int(*)(const void *, const void *))compar);
if(pp==NULL)
printf("값 찾기 실패");
else
printf("x[%d]에 있습니다.", pp-p);
return 0;
}
ps. 연습문제 정답들이 기존 예제들에서 일부러 꼬아놓은건지, 그냥 의도치 않은건지 모르겠는데.. 기존의 함수의 인자 선언 순서를 뒤바꿔서 구현해서, 오름차순/내림차순 그리고 pc pl pr의 계산을 헷갈리게 만들었다. 의도해서 열심히 집중하라고 하는건지, 아니면 편한대로 걍 적다보니 의도치않게 그런건진...근데 코드 중에 내가 찾은 예외사항에 대해서도 처리가 안되어 있는 걸 보니 그렇게 의도적으로 기발하게 꼬아서 낸 건 아닌듯..?
-> bsearch가 비교함수를 작성할 때 첫번째 인자가 key값에 대한 것이고 두번째 인자가 비교하려는 인덱스에 대한 값이라고 나와있는데, bsearch 함수를 직접 구현하라고 하는 문제들에 인자의 순서를 바꿔서 연습문제 정답에 구현해놓으시는 바람에 오름차순/내림차순 그리고 pr pc pl 계산도 헷갈리고 ..덕분에 짜증은 많이 났음..ㅎㅎ. 책에서의 공부를 토대로 연습문제 코드를 짜고나서 정답과 비교하며 공부하는 도중에 내 답이랑 다르고 헷갈려서 한참을 혼동속에 보냈다. 왜 이렇게 하신건지... 공부한 내용을 적용하려는데 전혀 반대의 방법을 정답으로 주시니...학습 내용에 분열이 오면서 너무나도 헷갈렸다.
현재 내가 구현한 방식은 비교함수의 첫번째 인자를 key값에 대한 인자, 두번째가 배열 요소에 대한 인자로 생각한 뒤 비교함수에서 첫번째 인자의 요솟값이 작으면 음수값(-1), 크면 양수값(1), 같으면 0을 리턴하고(오름차순 기준 약속임) 그에 맞게 pl pr 을 세팅해준다. 이게 책에서 설명한방식임.
근데 연습문제 정답 예제는 책에서 설명한 대로가 아닌 인자 순서를 뒤바꿨던데, 나는 내가 구현한게 맞다고 생각. 책 오타인듯.
+ 내 방법이 맞다는 것을 찾음. 책 오타맞음.
첫번째 인자가 key에관한 인자, 두번째 인자가 현재 배열 위치에 관한 인자.
그리고 오름차순 기준, 키값인 첫번째 인자가 두번째 인자보다 작으면 음수값(-1), 크면 양수값(1), 같으면 0 리턴하는게 맞다는게 입증.
www.ibm.com/support/knowledgecenter/ko/ssw_ibm_i_73/rtref/bsearch.htm
공부 내용 정리
▶︎ 선형 검색
배열에서의 가장 기본적인 알고리즘.
요소가 직선형태인 자료구조에서 원하는 값을 만날 때까지 맨앞에서부터 순서대로 요소 검색.
평균 n/2회.
시간복잡도 O(n)
∙ 선형검색의 종료 조건 feat. 배열
1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (검색 실패)
2. 검색할 값과 같은 요소를 발견한 경우 (검색 성공)
∙ 보초법
선형 검색은 반복할 때마다 위의 종료조건 1과 2를 모두 체크한다. 종료 조건 검사 비용을 무시할 수는 없다. 이 비용을 반으로 줄이는 방법이 보초법. 검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장. 이 값을 보초라고 한다.
ex) 입력받는 int형 데이터 개수가 6개인 경우
int a[6]이 아닌 int a[7]을 선언하여 보초 자리를 마련해놓고, a[6] 자리에 보초값을 넣는다.
▶︎ 이진검색
요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘. 따라서 알고리즘의 전제 조건은 데이더가 키 값으로 이미 정렬되어 있어야 함.
이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다.
검색 범위의 중앙에 위치한 요소와 찾으려는 값을 비교하여 검색 범위를 좁혀나가며 값을 찾는다.
평균 log n 회
시간복잡도 O(log n)
ex) n개의 요소가 오름차순일때
p1 = 0
pr = n-1
pc = (n-1)/2
pc와 키값의 대소를 비교하며 p1, pr, pc를 변경해나간다.
∙ 이진 검색 알고리즘의 종료 조건
1.a[pc]와 key가 일치하는 경우
2. 검색 범위가 더 이상 없는 경우
▶︎ 복잡도
알고리즘의 성능을 평가하는 기준.
1. 시간복잡도 : 실행에 필요한 시간을 평가한 것
2. 공간복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
∙ 시간복잡도
O(1) : 한 번만 실행하는 경우
O(n) : n에 비례하는 횟수만큼 실행하는 경우.
-> n/2번 실행해도 O(n/2)이 아닌 O(n)으로 표현하는데, 이유는 n의 값이 무한히 커진다고 가정했을 때 그 값의 차이가 무의미해지기 때문이다.
+ 시간복잡도 평가에는 극한의 개념이 도입되는 느낌이다.
∙ O(f(n))과 O(g(n))의 복잡도를 계산하는 방법
O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
-> 두개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 선택한다. 이는 둘이아니라 셋이던 넷이던 그 이상이던 마찬가지다.
다시말해 전체 복잡도는 차원이 가장 높은 복잡도를 선택한다.
▶︎ 함수 포인터
함수를 가리키는 포인터.
Ex) 아래에 함수가 있다.
double func(int); // int형 인수를 받아들여 double형 값을 반환하는 함수 선언
이 함수를 가리키는 포인터형은 'int형 인수를 받아들여 double형 값을 반환하는 함수' 에 대한 포인터다. 이 함수를 가리키는 포인터 fp의 선언은 아래와 같다.
double(*fp)(int); // int형 인수를 받아들여 double형을 반환하는 함수에 대한 포인터 fp의 선언
+ 변수 이름을 ()로 꼭 감싸줘야한다. 감싸주지 않으면 다른 의미의 함수선언문이 되어버림.
double *fp(int); // int형 인수를 받아들여 double에 대한 포인터를 반환하는 함수 선언
∙ 사용 예
int hello(int a, int b)
{
...중략
}
void call_func(int(*call)(int, int))
//또는 void call_func(int call(int, int))
{
(*call)(5, 6) // 또는 그냥 call(5, 6)도 상관없음
}
+배열을 매개변수로 하는 함수에서 int *p를 int p[]로 선언하여 받는것처럼 int(*call)(int, int)로 선언하여 받거나 int call(int, int)로 선언하여 받거나 상관없음
+ 자세히 기억은 안나지만 배열 a에서 scanf할때 &a를 하던 a를 하던 똑같은결과였던것같은데, 그런 비슷한 이유로 (*call)(5, 6)을 하던 call(5, 6)을하던 상관없는듯.
▶︎ bsearch 함수
C언어의 표준 라이브러리는 다양한 자료형의 각 배열에서도 검색 가능한 bsearch 함수를 제공한다.
특징 1. 검색 대상의 배열은 항상 정렬되어 있어야한다.
특징 2. 검색하는 값과 같은 요소가 여러 개 존재하는 경우, 항상 가장 앞쪽에 있는 요소를 찾아내는건 아니다.
헤더 : #include <stdlib.h>
형식 : void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));
설명 : base가 가리키는 요소의 개수가 nmemb개이고 요소의 각 크기가 size인 객체 배열에서 key가 가리키는 객체와 일치하는 요소를 검색. compar가 가리키는 비교함수는 key 객체에 대한 포인터를 첫 번째 인수로, 배열 요소에 대한 포인터를 두 번째 인수로 하여 호출한다. compar가 가리키는 비교 함수는 key 객체가 배열 요소보다 작으면 음수값을, 일치하면 0을, 크면 양수값을 반환하도록 작성(오름차순 기반의 데이터 기준)해야 한다.
반환값 : 검사하는 대상 중 일치하는 요소에 대한 포인터를 반환. 일치하는 요소가 없다면 NULL 반환.
사용 예)
//비교함수
int int_cmp(const int *a, const int *b)
{
if(*a < *b)
return -1;
else if(*a > *b)
return 1;
else
return 0;
}
일때,
int *p = bsearch(&key, x, nx, sizeof(int), (int(*)(const void *, const void *))int_cmp);
// int key = 검색값
// int nx = 요소 갯수
// int *x = calloc(nx, sizeof(int));
∙ 참고
(int(*)(const void *, const void *)) 캐스팅
-> 위 형식은 함수포인터 형식. int형을 반환하고 인자값이 const void *, const void * 인 함수포인터로 캐스팅하려는것. Bsearch의 인자가 그렇기때문.
Q. 캐스팅의 2가지(자동, 수동)에 대한 개념이 C언어에선 좀 불분명한듯?
▶︎ 포인터 연산
포인터 변수의 연산은 자료형에 따라 달라진다.
뭔소리냐면
int *num 이라는 변수가 있고
num = &key 를 통해 num 변수에 key 정수 변수의 주소값을 넣어준다.
이때 &key = 00A3FC00이라고 할 때
num = num+1; 연산을 시켜주면
주소가 00A3FC04로 4가 증가한다. int형은 4바이트이기때문.
만약 int 형 포인터가 아닌 char형 포인터로 자료형만 다르고 num = num+1 연산은 동일시 해주면 주소값은 1만 증가한다. char 형은 1바이트이기때문이다.
이렇게 포인터 변수에 연산을 하는 결과는, 동일한 연산이라도 그 포인터 변수의 자료형에 따라 달라진다. 기준에 맞게 연산되는것이다.
출처 - 'Do it 알고리즘과 함께 공부하는 자료구조 C언어편' 도서
'[알고리즘 + 자료구조] > [Do it 자료구조와 함께 배우는 알고리즘]' 카테고리의 다른 글
| [알고리즘] Do it 자료구조와 알고리즘 6장 정리 2/2 (0) | 2020.11.27 |
|---|---|
| [알고리즘] Do it 자료구조와 알고리즘 5장 정리 (0) | 2020.10.28 |
| [알고리즘] Do it 자료구조와 알고리즘 4장 정리 (0) | 2020.10.15 |
| [알고리즘] Do it 자료구조와 알고리즘 2장 정리 (0) | 2020.10.09 |
| [알고리즘] Do it 자료구조와 알고리즘 1장 정리 (0) | 2020.10.07 |
