문서의 제목 나눔명조R, 40pt

Size: px

Start display at page:

Download "문서의 제목 나눔명조R, 40pt"

석 국
6 years ago
Views:

1 이문서는나눔글꼴로작성되었습니다. 설치하기 11차시 : 함수동적메모리할당다차원배열 프로그래밍및실험 제 11주 동국대학교조영석

2 6.6 함수인자로써의배열 - 함수정의에서배열로선언된형식매개변수는 pointer임. - 함수의인자로배열이전달되면배열의기본주소가 ( 배열의내용이아님 ) call-by-value로전달됨. - 배열원소는복사되지않음. 2

3 ( 예 ) #include <stdio.h> double sum(double *, int); void main( ) { double D[5] = {3.5, 4.5, 5.5, 6.5; /* D[4] == 0.0 */ int n = 5, i; for (i = 0, i < n; ++i) printf("%lf", *(D + i)); printf("\n%lf", sum(d, n)); double sum(double a[], int n) { /* n is the size of a[] */ int i; /* double a[] == double *a */ double sum = 0.0; /* 변수이름 = 함수이름, but O.K. */ for (i = 0; i < n; ++i) sum = sum + a[i]; return sum; 실행결과 :

4 sum( ) 이호출되는여러방법 호출 계산및리턴되는값 sum(v, 100) v[0] + v[1] v[99] sum(v, 88) v[0] + v[1] v[87] sum(&v[7], k - 7) v[7] + v[8] v[k - 1] sum(v + 7, 2 * k) v[7] + v[8] v[2 * k + 6] 4

5 6.7 예제 : 버블정렬 void swap(int *, int *); void bubble(int a[], int n) { int i, j; for (i = 0; i < n - 1; ++i) for (j = n - 1; j > i; --j) if (a[j - 1] > a[j]) swap(&a[j - 1], &a[j]); 5

6 int a[] = {7, 3, 66, 3, -5, 22, -77, 2; bubble(a, 8); i = 0, j = 7 i = 0, j = 6 i = 0, j = 5 i = 0, j = 4 i = 0, j = 3 i = 0, j = 2 i = 0, j = 1 a[j-1] > a[j]? a[6] v.s. a[7] a[5] v.s. a[6] a[4] v.s. a[5] a[3] v.s. a[4] a[2] v.s. a[3] a[1] v.s. a[2] a[0] v.s. a[1] 6

7 i = 1, j = 7 a[6] v.s. a[7] : : : : i = 7, j = 2 a[1] v.s. a[2] i = 2, j = 7 a[6] v.s. a[7] : : : : i = 7, j = 3 a[2] v.s. a[3] i = 3, j = 7 a[6] v.s. a[7] : : : : i = 7, j = 4 a[3] v.s. a[4] : : i = 6, j = 7 i = 7, j = 7 a[6] v.s. a[7] 실행종료 7

8 i j i j i : : j i j i j 종료. 8

9 algorithm 의효율성분석 : 비교횟수 for (i = 0; i < n - 1; ++i) for (j = n - 1; j > i; --j) if (a[j - 1] > a[j]) swap(&a[j - 1], &a[j]); i의변화 : 0 부터 (n-2) 까지 (n-1) 회 j의변화 : (n-1) 부터 (i+1) 까지 (n-2)+(n-3)+(n-4)+ +1회 = (n-2)(n-1)/2 = (n 2-3n+2)/2 n 2 = O(n 2 ) n( 자료의개수 ) 가늘어나면시간복잡도 (time complexity) 가크게증가 9

10 6.8 calloc( ) 과 malloc( ) 을이용한동적메모리할당 (dynamic memory allocation) - 표준 library 에제공. - prototype 은 stdlib.h 에포함됨. - calloc( ) : Contiguous Allocation. calloc(n, el_size) 각원소가 el_size 인 n 개의원소로이루어진배열. memory 영역은모든 bit 가 0 으로초기화됨. void * 형의 pointer 가 return 됨. ( 또는 NULL 이 return 됨. - 실패했을경우 ) 10

11 - malloc( ) : Memory Allocation. malloc(memory_size) memory 의초기화않음. calloc( ) 보다시간이적게걸림. void * 형의 pointer( 또는 NULL) 가 return 됨. - free(ptr) 동적으로할당받은공간은함수의실행이끝나도 system 에반환되지않으므로반드시명시적으로반환할것. 11

12 ( 예 ) #include <stdio.h> #include <stdlib.h> int main( ) { int *a; int n;... a = calloc(n, sizeof(int)); /* machine independent */... free(a); 또는, a = malloc(n * sizeof(int)); 12

13 6.9 예제 : 합병 (merge) 과합병정렬 (merge sort) a - 두개의정렬된 array a[] 와 b[] 를이용하여하나의정렬된 array c[] 를만드는방법 N-1 b M-1 a[i] b[j] c N+M-2 c[k] a[i] 와 b[j] 를비교하여작은수를 c[k] 에저장하고작은쪽의 index 와 c[] 의 index 를하나씩증가시킴. a[], b[] 어느한쪽의 index가범위를넘으면 ( 즉, 모두 c[] 로옮겨지면 ) 다른 array의나머지 element를모두 13 순서대로 c[] 에옮김.

14 File "mergesort.h" 의내용. #include <assert.h> #include <stdio.h> #include <stdlib.h> void merge(int a[], int b[], int c[], int m, int n); void mergesort(int key[], int n); void wrt(int key[], int sz); 14

15 File "merge.c" 의내용. #include "mergesort.h" void merge(int a[], int b[], int c[], int m, int n) { int i = 0, j = 0, k = 0; while (i < m && j < n) if (a[i] < b[j]) c[k ++] = a[i++]; else c[k++] = b[j++]; while (i < m) c[k++] = a[i++]; while (j < n) c[k++] = b[j++]; 15

16 File "mergesort.c" 의내용. #include "mergesort.h" void mergesort(int key[], int n) { int j, k, m, *w; for (m = 1; m < n; m = m * 2) ; if (n < m) { printf("\nerror : Array size must be a power of 2.\n"); exit(1); w = calloc(n, sizeof(int)); assert(w!= NULL); for (k = 1; k < n; k = k * 2) { for (j = 0; j < n - k; j = j + 2 * k) merge(key + j, key + j + k, w + j, k, k); for (j = 0; j < n; ++j) key[j] = w[j]; free(w); 16

17 n = 8 의경우 key A B C D merge(key+j, key+j+k, w+j, k, k); k j(=j+2k) n-k function call merge(key+0, key+0+1, w+0, 1, 1); A merge(key+2, key+2+1, w+2, 1, 1); B merge(key+4, key+4+1, w+4, 1, 1); C merge(key+6, key+6+1, w+6, 1, 1); D 17

18 key A B k j(=j+2k) n-k function call merge(key+0, key+0+2, w+0, 2, 2); A merge(key+4, key+4+2, w+4, 2, 2); B key A k j(=j+2k) n-k function call merge(key+0, key+0+4, w+0, 4, 4); A 18

19 합병정렬의효율성분석 : - array(data) 의크기가 2의거듭제곱인경우에효율적 - data 비교횟수분석 : N = 32 = 2 5 의경우 k=1 (1:1) 16set(1회 ( 2)/set 비교 ) 비교횟수 32회 k=2 (2:2) 8set(max 3회 ( 4)/set) 비교횟수 32회 k=4 (4:4) 4set(max 7회 ( 8)/set) 비교횟수 32회 k=8 (8:8) 2set(max 15회 ( 16)/set) 비교횟수 32회 k=16 (16:0) 정렬완료 외부 loop: 4회 ( 5회; log 2 32 = log = 5 log 2 2 = 5) 내부 loop: 32회비교 (= N) 총 loop횟수 : 5 * 32 (= log 2 N * N = N log 2 N) time complexity: O(n log n): Bubble Sort에비해매우양호 19

20 6.10 문자열 - char형의 1차원배열. - 문자열은 '\0'(NULL) 로끝남. - 문자열의크기는 '\0' 를포함하며가변임. ( 예 ) "abc" : 크기 = 4, 마지막 element = '\0' - char *p = "abc"; /* char *p; p = "abc"; */ printf("%s %s\n", p, p + 1); 실행결과 : abc bc p는문자열 "abc" 의 'a' 의주소값을가짐. printf() 는 p에서시작하여 '\0' 의직전까지 print. - 문자열상수는 pointer로취급됨. "abc"[1] == 'b' *("abc" + 2) == 'c' 20

21 - char *p = "abcde"; char s[] = "abcde"; s a b c d e \0 ( 예 ) 문자열내의단어의수를세는 program. #include <stdio.h> #include <ctype.h> int word_count (const char *a); void main() { char *s = "Mary had a little lamb."; printf("\n%s\n", s); p a b c d e \0 임시 memory 영역 printf("\nnumber of words : %d", word_count(s)); 21

22 int word_count (const char *s) { int count = 0; while (*s!= '\0') { while( isspace(*s) ) /* skip space */ ++s; if (*s!= '\0') { /* found a word */ ++ count; while (!isspace(*s) && *s!= '\0') ++s; /* skip the word */ return count; 22

23 6.11 표준라이브러리에있는문자열조작함수 (string.h) - char *strcat(char *s1, const char *s2); 두개의문자열 s1 과 s2 를결합하여 s1 에결과저장. s1 은결과를저장할수있을만큼의충분한공간을 point 할수있도록해야함. 문자열 s1 이 return 됨. char *strcat(char *s1, register const char *s2) { register char *p = s1; while (*p) /* go to the end */ ++p; while (*p++ = *s2++) /* copy */ ; return s1; 23

24 - int strcmp(const char *s1, const char *s2); 두문자열이인자로전달됨. s1과 s2를사전적순서로비교하여 s1이작으면음수, 크면양수, 같으면 0을 return. 24

25 - char *strcpy(char *s1, const char *s2); 문자열 s2 를 '\0' 이나올때까지 s1 에복사. s1 의내용은 s2 의내용으로 overwrite 됨 s1 에충분한공간이마련되어야함. pointer s1 이 return 됨. char *strcpy(char *s1, register const char*s2) { register char *p = s1; while(*p++ = *s2++) ; return s1; 25

26 - size_t strlen(const char *); '\0' 을제외한문자의개수를 returen. size_t 는부호없는정수적형. 4 bytes/word system 에서는 unsigned int. 2 bytes/word system 에서는 unsigned long. size_t strlen(const char *s) { size_t n; for (n = 0; *s!= '\0'; ++s) ++n; return n; 26

27 선언및초기화 char s1[] = "beautiful big sky country", s2[] = "how now brown cow"; 수식 값 strlen(s1) 25 strlen(s2 + 8) 9 strcmp(s1, s2) 문장 printf("%s", s1+10); 음의정수 출력되는값 big sky country strcpy(s1 + 10, s2 + 8); strcat(s1, "s!"); printf("%s", s1); beautiful brown cows! 27

28 6.12 다차원배열 int a[100]; int b[2][7]; : 일차원배열 : 이차원배열 int c[5][3][2]; : 삼차원배열 28

29 - 2차원배열 ( 예 ) int a[3][5]; row( 행 ) column( 열 ) 1열 2열 3열 4열 5열 1행 a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] 2행 a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] 3행 a[2][0] a[2][1] a[2][2] a[2][3] a[2][4] - a[i][j] 의다른표현 *(a[i] + j) (*(a + i))[j] *((*(a + i)) + j) *(&a[0][0] + 5 * i + j) 29

30 형식매개변수선언 - 함수를정의할때형식매개변수가다차원배열일경우, 첫번째를제외한모든크기를명시해야함. ( 예 ) int a[3][5]; int sum(int a[][5]) { int i, j, sum = 0; for (i = 0; i < 3; ++i) for (j = 0; j < 5; ++j) sum = sum + a[i][j]; return sum; 30

31 매개변수의다른정의 : 함수정의의 header에서만동일함. int a[][5] int a[3][5] : 상수 3을 compiler는무시 int (*a)[5] ( 비교 : 1차원배열 ) int b[] int b[3] int *b 31

32 - 초기화 int a[2][3] = {1, 2, 3, 4, 5, 6; int a[2][3] = {{1, 2, 3, {4, 5, 6; int a[][3] = {{1, 2, 3, {4, 5, 6; 내부중괄호가생략되면 a[0][0], a[0][1], a[0][2], a[1][0], a[1][1], a[1][2] 의순으로초기화함. - typedef의사용 #define N 3 typedef double scalar ; typedef scalar vector[n]; typedef scalar matrix[n][n]; ( 또는 typedef vector matrix[n];) 32

33 ( 예 ) void add(vector x, vector y, vector z) { int i; for (i = 0; i < N; ++i) x[i] = y[i] + z[i]; scalar dot_product(vector x, vector y) { int i; scalar sum = 0.0; for (i = 0; i < N; ++i) sum = sum + x[i] * y[i]; return sum; 33

34 void multiply (matrix a, matrix b, matrix c) { int i, j, k; for (i = 0; i < N; ++i) { for (j = 0; j < N; ++j) { a[i][j] = 0.0; for (k = 0; k < N; ++k) a[i][j] = a[i][j] + b[i][k] * c[k][j]; = * 34

35 6.13 포인터배열 ( 예 ) char * w[5]; w[0] = "Mary"; w[1] = "had"; w[2] = "a"; w[3] = "little"; w[4] = "lamb."; w[0] M a r y \0 "Mary" h a d \0 "had" a \0 "a" l i t t l e \0 "little" l a m b. \0 "lamb." 35

36 #include <stdio.h> #define N 5 void main() { char *w[n]; int i; w[0] = "Mary"; w[1] = "had"; w[2] = "a"; w[3] = "little"; w[4] = "lamb."; printf ("\n%s %s %s %s %s\n", w[0], w[1], w[2], w[3], w[4]); printf ("\n%s %s %s %s %s\n", *w, *(w+1), *(w+2), *(w+3), *(w+4)); 36

37 #include <stdio.h> #define N 5 void main() { char *w[n]; int i; *w = "MARY"; *(w+1) = "HAD"; *(w+2) = "A"; *(w+3) = "LITTLE"; *(w+4) = "LAMB."; for (i=0; i<n; ++i) printf ("%s ", w[i]); for (i=0; i<n; ++i) printf ("%s ", *(w+i)); 37

38 문자열정렬 void sort_words(char *w[], int n) { int i, j; for (i = 0; i < n; ++i) for (j = i + 1; j < n; ++j) if (strcmp(w[i], w[j]) > 0) swap(&w[i], &w[j]); void swap(char **p, char **q) { char *tmp; tmp = *p; *p = *q; *q = tmp; 38

39 6.14 main( ) 함수의인자 #include <stdio.h> void main(int argc, char *argv[]) { int i; printf("argc = %d\n", argc); for (i = 0; i < argc; ++i) printf("argv[%d] = %s\n", i, argv[i]); my_echo 라는이름의실행화일을생성. my_echo a is for apple. ( 실행결과 ) argc = 5 argv[0] = my_echo argv[1] = a argv[2] = is argv[3] = for argv[4] = apple. 39

40 6.15 래기드배열 (ragged array) 6.16 인자로서의함수 6.17 예제 6.18 함수포인터의배열 6.19 형한정자 const와 volatile 생략. 40

41 감사합니다. 이문서는나눔글꼴로작성되었습니다. 설치하기

Microsoft PowerPoint - chap06.ppt

Microsoft PowerPoint - chap06.ppt 2010-1 학기프로그래밍입문 (1) 6 장배열, 포인터, 문자열 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 0 목차 6.1 1차원배열 6.2 포인터 6.3 참조에의한호출 6.4 배열과포인터의관계 6.5 포인터연산과원소크기 6.6 함수인자로서의배열 6.7 예제 : 버블정렬 6.8 calloc() 과 malloc() 을이용한동적메모리할당