CHAP 3: 배열, 구조체, 포인터
배열 같은형의변수를여러개만들때 int A, A1, A2, A3,,A9; int A[1]; 1 2 3 4 5 6 7 8 9 언제배열을사용하면효율적인프로그래밍이되는가? - 반복코드를작성할때 예 ) 최대값을구하는프로그램. 만약배열이없었다면? max=score[]; for(i=1;i<n;i++){ if( score[i] > max) max = score[i];
배열 ADT 배열이란? - < 인덱스, 요소 > 쌍의집합 인덱스에대해해당요소가대응되는구조 배열 ADT 객체 : < 인덱스, 요소 > 쌍의집합연산 : create(n) ::= n개의요소를가진배열의생성. retrieve(a, i) ::= 배열 A의 i번째요소반환. store(a, i, item) ::= 배열 A의 i번째위치에 item 저장.
1 차원배열 int A[5]; A[] A[1] A[2] A[3] A[4] 변수 메모리주소 A[] 기본주소 = base A[1] base + 1xsizeof(int) A[2] base + 2xsizeof(int) A[3] base + 3xsizeof(int) A[4] base + 4xsizeof(int)
2 차원배열 int A[3][4]; A[][] A[][1] A[][2] A[][3] A[1][] A[1][1] A[1][2] A[1][3] A[2][] A[2][] A[2][] A[2][] A[][1] A[][2] A[][3] A[][4] A[1][] A[1][2] A[1][3] A[1][4] 실제메모리에서의위치
연습 1 배열의활용 - 최대값찾기 #include <stdio.h> int main() { int score[1]={5, 2, 7, 1, 3, 2, 6, 11, 4, 8; int i, max; max=score[]; for(i=;i<1;i++) if( score[i] > max) max = score[i]; printf(" 최대값은 %d\n", max); return ;
배열의활용 2 차원배열 #include <stdio.h> 연습 2 int main() { int A[3][4]={{1,2,3,4, {5,6,7,8, {9, 1, 11, 12 ; int i, j; for(i=;i<3;i++) for(j=; j<4; j++) A[i][j]+=1; for(i=;i<3;i++) { for(j=; j<4; j++) printf("%d ", A[i][j]); printf("\n"); return ;
연습 3 배열의활용 함수의매개변수로서의배열 #include <stdio.h> #define MAX_SIZE 1 void sub(int var, int list[]) { var=1; list[]=1; int main() { int var; int list[max_size]; 예측해보세요 var=; list[]=; sub(var, list); printf("var=%d, list[]=%d \n", var, list[]);
다항식 배열의응용 - 다항식 n p( x) a x a a x a n n1 n1 x... 1 프로그램에서다항식을처리하려고하면어떤자료구조가필요한가? 다항식의덧셈, 뺄셈, 곱셈, 나눗셈연산을할때편리하고효율적인자료구조는? 배열사용 2 가지방법 방법 1. 다항식의모든항을배열에저장하는방법 방법 2. 이아닌항만을배열에저장하는방법
다항식표현방법 #1 지수들은내림차순으로정돈 모든차수에대한계수값을배열로저장 A = (n, a n, a n-1,..., a 1, a ) A 차수, n+1 coefficients 예 ) A(x) = 1x 5 +x 4 +x 3 +x 2 +6x+3 : n = 5 A = (5, 1,,,, 6, 3) : 7 eleme nts
다항식표현방법 #1 하나의다항식을하나의배열로표현 5 4 3 2 1 1x x x x 6x 3x 1 2 3 4 5 6 7 8 9 1 coef 1 6 2 #define MAX_DEGREE 1 typedef struct { int degree; float coef[max_degree]; polynomial; polynomial a = { 5, {1,,,, 6, 3 ;
다항식표현방법 #1( 계속 ) 장점 : 다항식의각종연산이간단해짐 단점 : 대부분의항의계수가 이면공간의낭비가심함. 예 ) 다항식의덧셈연산 while( Apos<=A.degree && Bpos<=B.degree ){ if( degree_a > degree_b ){ // A항 > B항 C.coef[Cpos++]= A.coef[Apos++]; degree_a--; else if( degree_a == degree_b ){ // A항 == B항 C.coef[Cpos++]=A.coef[Apos++]+B.coef[Bpos++]; degree_a--; degree_b--; else { // B항 > A항 C.coef[Cpos++]= B.coef[Bpos++]; degree_b--;
다항식표현방법 #2 a.degree << MAX_DEGREE a.coef[max_degree] 의대부분이 이다 ex) A(x) = x 1 + 1 A = (1, 1,,...,, 1) 999 다항식에서 이아닌항만을배열에저장 ( 계수, 차수 ) 형식으로배열에저장 ( 예 ) 1x 5 +6x+3 -> ((1,5), (6,1), (3,))
다항식표현방법 #2 다항식에서 이아닌항만을저장하는배열 struct { float coef; int expon; terms[max_terms]={ {1,5, {6,1, {3, ; 하나의배열로여러개의다항식을나타낼수있음. coef expon A B avail 1 2 3 4 5 6 7 8 9 1 8 3 7 1 1 1 3 3 2 1 terms
다항식표현방법 #2( 계속 ) 장점 : 메모리공간의효율적인이용 단점 : 다항식의연산들이복잡해진다 ( 예 ) 다항식의덧셈 A=8x 3 +7x+1, B=1x 3 +3x 2 +1, C=A+B coef expon A B avail 1 2 3 4 5 6 7 8 9 1 8 3 7 1 1 1 3 3 2 1 A B C avail coef expon 1 2 3 4 5 6 7 8 9 1 8 7 1 1 3 1 3 3 1 18 3 7 2 2 3 2 1
다항식덧셈연산 // C = A + B void poly_add2(int As, int Ae, int Bs, int Be, int *Cs, int *Ce) { float tempcoef; *Cs = avail; while( As <= Ae && Bs <= Be ) switch(compare(terms[as].expon,terms[bs].expon)){ case '>': // A의차수 > B의차수 attach(terms[as].coef, terms[as].expon); As++; break; case '=': // A의차수 == B의차수 tempcoef = terms[as].coef + terms[bs].coef; if( tempcoef ) attach(tempcoef,terms[as].expon); As++; Bs++; break; case '<': // A의차수 < B의차수 attach(terms[bs].coef, terms[bs].expon); Bs++; break; // A의나머지항들을이동함 for(;as<=ae;as++) attach(terms[as].coef, terms[as].expon); // B의나머지항들을이동함 for(;bs<=be;bs++) attach(terms[bs].coef, terms[bs].expon); *Ce = avail -1;
희소행렬 (sparse matrix) 배열을이용하여행렬 (matrix) 를표현하는 2 가지방법 (1) 2 차원배열을이용하여배열의전체요소를저장하는방법 (2) 이아닌요소들만저장하는방법 희소행렬 : 대부분의항들이 인배열 2 1 5 6 8 9 7 5 7 1 9 8 3 2 B A
희소행렬표현방법 #1 2 차원배열을이용하여배열의전체요소를저장하는방법 장점 : 행렬의연산들을간단하게구현할수있다. 단점 : 대부분의항들이 인희소행렬의경우많은메모리공간낭비 2 A 8 7 3 9 1 5 9 B 6 5 2 7 8 1 1 2 2 3 A= B= 1 8 9 1 1 2 3 4 5 1 2 7 1 2 1 9 1 2 1 82 2 1 2 1 2 3 6 51 2 1 2 2 7 5 4 1 2 1 12 5 2
희소행렬표현방법 #2 효율적기억장소사상 ⅰ) <i, j, value> : 3-tuples (triples) ⅱ) no. of rows ⅲ) no. of columns ⅳ) no. of non-zero elements ⅴ) ordering(column major or row major)
희소행렬표현방법 #2 이아닌요소들만저장하는방법 장점 : 희소행렬의경우, 메모리공간의절약 단점 : 각종행렬연산들의구현이복잡해진다. 행열값 1 2 7 1 1 32 9 8 2 3 2 1 1 82 A 8 9 1 B 6 5 A= B= 3 1 1 92 7 5 1 4 1 21 12 2 5 2 7 6 2 2 5 행열값 31 72 1 1 1 92 2 1 51 82 3 3 1 62 4 3 1 52 5 4 5 1 6 5 2 2
희소행렬연산비교 전치연산프로그램의비교 1) 배열 for (j = ; j < colums; j++) for (i = ; i < rows; i++) b[j][i] = a[i][j];
희소행렬연산비교 2) 이아닌요소들만저장하는방법
구조체 구조체 (structure): 타입이다른데이터를하나로묶는방법 배열 (array): 타입이같은데이터들을하나로묶는방법 배열 구조체 필드 1 char carray[1]; struct example { char cfield; int ifield; float ffield; double dfield; ; struct example s1;
구조체의사용예 #1 구조체의선언과구조체변수의생성 struct person { char name[1]; // 문자배열로된이름 int age; // 나이를나타내는정수값 float height; // 키를나타내는실수값 ; struct person a; // 구조체변수선언 typedef 을이용한구조체의선언과구조체변수의생 typedef 성 struct person { char name[1]; // 문자배열로된이름 int age; // 나이를나타내는정수값 person; person a; float height; // 키를나타내는실수값 // 구조체변수선언
구조체의사용예 #2 구조의멤버연산자 구조체멤버에접근하려면연산자. 을사용한다 Ex) struct person a ; strcpy(a.name, james ); a.age = 1; a.salary = 35;
구조체의대입과비교연산 구조체변수의대입 : 가능 struct person { char name[1]; int age; float height; ; main() { person a, b; b = a; // 문자배열로된이름 // 나이를나타내는정수값 // 키를나타내는실수값 // 가능 구조체변수끼리의비교 : 불가능 main() { if( a > b ) printf("a 가 b 보다나이가많음 "); // 불가능
#include <stdio.h> 구조체연습 #4 struct person { char name[1]; // 문자배열로된이름 int age; // 나이를나타내는정수값 float height; // 키를나타내는실수값 ; int main() { struct person a ; strcpy(a.name, "james"); a.age = 1; a.height = 178.5; printf("name=%s, age=%d, height=%.1f \n", a.name, a.age, a.height); return ;
구조체안의구조체 구조속의또다른구조정의 typedef struct { int month; int day; int year; date; typedef struct human_being { char name[1]; int age; float salary; date dob; ; [ 예 ] A person born on February 14, 1988 person1.dob.month = 2; person1.dob.day = 11; person1.dob.year = 1944;
자체참조구조체 #1 자체참조구조체 (self-referential structure): 필드중에자기자신을가리키는포인터가한개이상존재하는구조체 연결리스트나트리에많이등장 typedef struct ListNode { char data[1]; struct ListNode *link; ;
자체참조구조체 #2 ListNode item1, item2, item3; item1.data = a ; item2.data = b ; item3.data = c ; item1.link = item2.link = item3.link = NULL; item1 item2 item3 a NULL b NULL c NULL
구조체연결 자체참조구조체 #3 item1.link=&item2; item2.link=&item3; item1 item2 item3 a b c NULL
유니언 (union) 유니언 ( Union) union의필드들은메모리공간을공용한필드만어느한시점에활동적이되어사용가능 typedef struct sex_type { enum tag_field {female, male sex; union { ; int children; int beard; u ; typedef struct human_being { char name[1]; int age; float salary; date dob; sex_type sex_info; ; human_being person1, person2;
구조체연습 #5 구조체배열을만들어보라. 정수항목인 number 와문자열항목인 name 을갖는구조체를정의하고크기가 3 인구조체배열을생성하시오. #define SIZE 1 struct { int number; char name[size]; sa [5]; #define SIZE 1 struct test{ int number; char name[size]; ; struct test sa [3];
연습 5 답 #include <iostream> #include <string.h> #define SIZE 1 struct test{ int number; char name[size]; ; int main() { struct test sa[3]; int i; sa[].number=1; strcpy(sa[].name, "test"); sa[1].number=2; strcpy(sa[1].name, "test1"); sa[2].number=3; strcpy(sa[2].name, "test2"); for(i=; i<3; i++) printf("number %d name=%s \n", sa[i].number, sa[i].name); return ;
연습 #6 person 이라는구조체를만들어보자. 이구조체에는문자배열로된이름, 사람의나이를나타내는정수값, 각개인의월급을나타내는 float 값등이변수로들어가야한다. person 구조체에생년월일구조체를추가하여라 (month, day, year )
연습 #6 답 person 이라는구조체를만들어보자. 이구조체에는문자배열로된이름, 사람의나이를나타내는정수값, 각개인의월급을나타내는 float 값등이변수로들어가야한다. person 구조체에생년월일구조체를추가하여라 (month, day, year ) struct person { char name[size]; int age; float salary; struct { int month; int day; int year; birthday; ; struct person JMH; struct date { int month; int day; int year; ; struct person { char name[1]; int age; float salary; struct date birthday; ; struct person JMH;
포인터 : 다른변수의주소를가지고있는변수 char a='a'; char *p; p = &a; 포인터 (pointer) 포인터가가리키는내용의변경 : * 연산자사용 *p= 'B';
포인터 (pointer) 포인터 : 다른변수의주소를가지고있는변수 char a='a'; char *p; p = &a; 포인터가가리키는내용의변경 : * 연산자사용 *p= 'B';
포인터와관련된연산자 & 연산자 : 변수의주소를추출 * 연산자 : 포인터가가리키는곳의내용을추출 char a= A ; p // 포인터 *p // 포인터가가리키는값 *p++ // 포인터가가리키는값을가져온다음, 포인터를한칸증가한다. *p-- // 포인터가가리키는값을가져온다음, 포인터를한칸감소한다. (*p)++ // 포인터가가리키는값을증가시킨다. int a; // 정수변수선언 int *p; // 정수포인터선언 int **pp; // 정수포인터의포인터선언 p = &a;// 변수 a와포인터 p를연결 pp = &p; // 포인터 p와포인터의포인터 pp를연결
디양한포인터 포인터의종류 void *p; // p는아무것도가리키지않는포인터 int *pi; // pi는정수변수를가리키는포인터 float *pf; // pf는실수변수를가리키는포인터 char *pc; // pc는문자변수를가리키는포인터 int **pp;// pp는포인터를가리키는포인터 struct test *ps; // ps는 test 타입의구조체를가리키는포인터 void (*f)(int) ; // f는함수를가리키는포인터 포인터의형변환 : 필요할때마다형변환하는것이가능하다. void *p; pi=(int *) p;
함수의파라미터로서의포인터 함수안에서파라미터로전달된포인터를이용하여외부변수의값변경가능 void swap(int *px, int *py) { int tmp; tmp = *px; *px = *py; *py = tmp; main() { int a=1,b=2; printf("swap 을호출하기전 : a=%d, b=%d\n", a,b); swap(&a, &b); printf("swap 을호출한다음 : a=%d, b=%d\n", a,b);
배열과포인터 배열의이름 : 사실상의포인터와같은역할 컴파일러가배열의이름을배열의첫번째주소로대치
배열과포인터 int *list1; int list2[5]; list2 = list2[] 를가리키는포인터 list2 + i = list2[i] 를가리키는포인터 (list2+i) == &list2[i], *(list2+i) == list2[i]
구조체의포인터 구조체의요소에접근하는연산자 : -> main() { struct { int i; float f; s, *ps; ps = &s; ps->i = 2; ps->f = 3.14;
포인터의포인터 int a; // 정수변수변수선언 int *p; // 정수포인터선언 int **pp; // 정수포인터의포인터선언 p = &a; // 변수 a와포인터 p를연결 pp = &p; // 포인터 p와포인터의포인터 pp를연결
포인터연산 포인터에대한사칙연산 : 포인터가가리키는객체단위로계산된다. p // 포인터 p+1 // 포인터 p 가가리키는객체의바로뒤객체 p-1 // 포인터 p 가가리키는객체의바로앞객체
포인터사용시주의할점 포인터가아무것도가리키고있지않을때는 NULL 로설정 int *pi=null; 초기화가안된상태에서사용금지 main() { char *pc; *pc = 'E ; // 포인터 pi는초기화가안되어있음 // 위험한코드 포인터타입간의변환시에는명시적인타입변환사용 int *pi; float *pf; pf = (float *)pi;
연습 1 포인터연습 #7 int a=1; printf("a 의값은 %d \n", a); printf("a 의주소값은 %d \n", &a); printf("a 의값은 %d \n", *&a); 연습 2 int a=1, b=2; int *p=&a; printf("a=%d *p=%d \n", a, *p); b=*p; printf("a=%d b=%d, *p=%d \n", a, b, *p); *p=3; printf("a=%d b=%d, *p=%d \n", a, b, *p);
연습 3 swap #include <stdio.h> #include <stdlib.h> void swap(int a, int b); int main() { 포인터연습 #7 #include <stdio.h> #include <stdlib.h> void swap(int *pa, int *pb); int main() { int a=1, b=2; printf("a= %d, b=%d \n", a, b); swap(a, b); printf("a= %d, b=%d \n", a, b); return ; void swap(int a, int b) { int t; t=a; a=b; b=t; int a=1, b=2; printf("a= %d, b=%d \n", a, b); swap(&a, &b); printf("a= %d, b=%d \n", a, b); return ; void swap(int *pa, int *pb) { int t; t=*pa; *pa=*pb; *pb=t;
동적메모리할당 프로그램이메모리를할당받는방법 1. 정적메모리할당 2. 동적메모리할당 정적메모리할당 프로그램이시작하기전에메모리크기가결정됨 프로그램의수행도중크기변경불가 ex) int A[5]; 결정된크기보다더큰입력은처리할수없고작은입력인경우메모리 낭비 ( 예 ) 변수나배열의선언 int buffer[1]; char name[] = data structure"; 동적메모리할당 프로그램의실행도중필요한만큼메모리를할당받음 필요없을때는반납 메모리효율적사용
동적메모리할당 전형적인동적메모리할당코드 main() { int *pi; pi = (int *)malloc(sizeof(int)); // 동적메모리할당... // 동적메모리사용... free(pi); // 동적메모리반납 동적메모리할당관련라이브러리함수 malloc(size) // 메모리할당 free(ptr) // 메모리할당해제 sizeof(var) // 변수나타입의크기반환 ( 바이트단위 )
동적메모리할당라이브러리 malloc(int size) size 바이트만큼의메모리블록을할당 (char *)malloc(1) ; /* 1 바이트로 5 개의정수를 저장 */ (int *)malloc(sizeof(int)); /* 정수 1 개를저장할메모리확보 */ (struct Book *)malloc(sizeof(struct Book)) /* 하나의구조체 생성 */ free(void ptr) ptr 이가리키는할당된메모리블록을해제
동적메모리할당라이브러리 sizeof 키워드 변수나타입의크기반환 ( 바이트단위 ) size_t i = sizeof( int ); // 4 struct AlignDepends { char c; int i; ; size_t size = sizeof(struct AlignDepends); // 8 int array[] = { 1, 2, 3, 4, 5 ; size_t sizearr = sizeof( array ) / sizeof( array[] ); // 2/4=5
연습 #8 - 동적메모리할당예제 정수항목인 number 와문자열항목인 name 을갖는구조체를정의하고크기가 2 인구조체배열을동적으로할당해보시오. struct Example { int number; char name[1]; ; int main() { struct Example *p; p=(struct Example *)malloc(2*sizeof(struct Example));
동적메모리할당예제 8 답 struct Example { int number; char name[1]; ; void main() { struct Example *p; p=(struct Example *)malloc(2*sizeof(struct Example)); if(p==null){ fprintf(stderr, "can't allocate memory\n") ; exit(1) ; p->number=1; strcpy(p->name,"park"); (p+1)->number=2; strcpy((p+1)->name,"kim"); free(p);
앞의동적메모리예제에서 생략 동적메모리할당예제 8- 계속 free(p); 메모리를해제하기전에 p 의내용을출력하는부분을작성하여테스트해보시오. p->number=1; strcpy(p->name,"park"); (p+1)->number=2; strcpy((p+1)->name,"kim"); for( i=; i<=1; i++) printf("struct Example %d: %d, %s\n", i, (p+i)->number, (p+i)->name); free(p); 생략
연습 #9 #1. int i=1; int *p; p=&i; *p=8; 의문장이수행되면 i 값은얼마인가? #2. int i=1; int *p; p=&i; (*p)--; 의문장이수행되면 i 값은얼마인가? #3. int a[1]; int *p; p=a; *p++=5; 의문장이수행되면변경되는배열의요소는? #4. int a[1]; int *p; p=a; *++p=5; 의문장이수행되면변경되는배열의요소는? #5 int a[1]; int *p; p=a; (*p)++; 의문장이수행되면변경되는배열의요소는?
연습 #1 다음에대하여연습해보시오. a) 1 개의원소를갖는 numbers 라는 float 형의배열을선언하고, 원소들을., 1.1, 2.2,..., 9.9 의값으로초기화하라. 기호상수 SIZE 는 1 으로정의되었다고가정한다. b) float 형의객체를가리키는포인터 nptr 을선언하라. c) 배열첨자표기법을사용하여배열 numbers 의원소들을출력하라. : for(i=;i<1; i++) d) 포인터변수 nptr 에배열 numbers 의시작주소를대입하는두개의다른문장을제시하라. e) 포인터 nptr 을사용해서포인터표기법으로배열 numbers 의원소들을출력하라. f) 포인터 nptr 에첨자를적용하여배열 numbers 의원소들을출력하라.
#include <stdio.h> # define SIZE 1 int main() { float numbers[size] = {., 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9; // a) float *nptr; //b) int i; 연습 #1 - 답 for (i = ; i < SIZE; i++) printf( %.1f, numbers[i] ) ; //c) printf( \n ); nptr = numbers; // d) or nptr = &numbers[]; //d) for (i = ; i < SIZE; i++) printf( %.1f, *(nptr + i) ); //e) printf( \n ); for (i = ; i < SIZE; i++) printf( %.1f, nptr[i] ); //f) return ;
연습 #11 Q. 배열 x 를 {1, 2, 3, 4, 5, 6 으로초기화한후포인터 p 를정의하고포인터 p 에저장할주소는 x[2] 로하고 *(p+3) 와 *(p-2) 의값및그곱을구하는프로그램을작성하여라. ( 먼저값을예측해보시오 ) int main() { int x[]={1,2,3,4,5,6; int *p=&x[2]; printf( *(p+3)= %d \n, *(p+3)); printf( *(p-2)= %d \n, *(p-2)); printf( *(p+3) x *(p-2) = %d \n, *(p+3) * *(p-2) );
연습 #12 1 차원배열을만들고원소값을입력받는함수와출력하는함수를각각작성해보시고
#include <stdio.h> #define SIZE 5 void READM(int n, int *A); void PRINTM(int n, int *A); int main() { int A[SIZE]; READM(SIZE, A); PRINTM(SIZE, A); system("pause"); return ; return ; void READM(int n, int *A) { int i; printf("enter %d numbers\n", n); for(i=;i<n;i++) scanf("%d", &A[i]); return ; void PRINTM(int n, int *A) { int i; printf("here are %d numbers\n", n); for(i=;i<n;i++) printf("%d ", A[i]); printf("\n"); return ;
#include <stdio.h> #define SIZE 5 void READM(int n, int *A); void PRINTM(int n, int *A); int main() { int A[SIZE]; READM(SIZE, A); PRINTM(SIZE, A); system("pause"); return ; return ; void READM(int n, int *A) { int i; printf("enter %d numbers\n", n); for(i=;i<n;i++) scanf("%d", &A[i]); return ; void PRINTM(int n, int *A) { int i; printf("here are %d numbers\n", n); for(i=;i<n;i++) printf("%d ", A[i]); printf("\n"); return ;