CHAP 3: 배열, 구조체, 포인터 C 로쉽게풀어쓴자료구조 Copyright 생능출판사 25
배열이란? 같은형의변수를여러개만드는경우에사용 int A, A, A2, A3,,A9; int A[]; 2 3 4 5 6 7 8 9 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램 : 만약배열이없었다면? tmp=score[]; for(i=;i<n;i++){ if( score[i] > tmp ) tmp = score[i]; C 로쉽게풀어쓴자료구조 생능출판사 25
배열 ADT 배열 : < 인덱스, 요소 > 쌍의집합 인덱스가주어지면해당되는요소가대응되는구조 배열 ADT 객체 : < 인덱스, 요소 > 쌍의집합연산 : create(n) ::= n 개의요소를가진배열의생성. retrieve(a, i) ::= 배열 A 의 i 번째요소반환. store(a, i, item) ::= 배열 A 의 i 번째위치에 item 저장. 요소 인덱스 C 로쉽게풀어쓴자료구조 생능출판사 25
차원배열 int A[6]; A[] A[] A[2] A[3] A[4] A[5] base base+5*sizeof(int) base+4*sizeof(int) base+3*sizeof(int) base+2*sizeof(int) base+sizeof(int) C 로쉽게풀어쓴자료구조 생능출판사 25
2 차원배열 int A[3][4]; A[][] A[][] A[][] A[][2] A[][] A[][] A[][2] A[2][] A[2][] A[2][2] A[][3] A[][3] A[2][3] A[][] A[][2] A[][3] A[][] A[2][3] 실제메모리안에서의위치 C 로쉽게풀어쓴자료구조 생능출판사 25
배열의응용 : 다항식 다항식의일반적인형태 n p( x) a x a a x a n n n x... 프로그램에서다항식을처리하려면다항식을위한자료구조가필요 -> 어떤자료구조를사용해야다항식의덧셈, 뺄셈, 곱셈, 나눗셈연산을할때편리하고효율적일까? 배열을사용한 2 가지방법 ) 다항식의모든항을배열에저장 2) 다항식의 이아닌항만을배열에저장 C 로쉽게풀어쓴자료구조 생능출판사 25
다항식표현방법 # 모든차수에대한계수값을배열로저장 하나의다항식을하나의배열로표현 5 4 3 2 x x x x 6x 3x 2 3 4 5 6 7 8 9 coef 6 3 typedef struct { int degree; float coef[max_degree]; polynomial; polynomial a = { 5, {,,,, 6, 3 ; C 로쉽게풀어쓴자료구조 생능출판사 25
다항식표현방법 #( 계속 ) 장점 : 다항식의각종연산이간단해짐 단점 : 대부분의항의계수가 이면공간의낭비가심함. 예 ) 다항식의덧셈연산 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--; C 로쉽게풀어쓴자료구조 생능출판사 25
다항식표현방법 #2 다항식에서 이아닌항만을배열에저장 ( 계수, 차수 ) 형식으로배열에저장 ( 예 ) x 5 +6x+3 -> ((,5), (6,), (3,)) struct { float coef; int expon; terms[max_terms]={ {,5, {6,, {3, ; 하나의배열로여러개의다항식을나타낼수있음. coef expon A B avail 2 3 4 5 6 7 8 9 8 3 7 C 로쉽게풀어쓴자료구조 생능출판사 25 3 3 2 terms
다항식표현방법 #2( 계속 ) 장점 : 메모리공간의효율적인이용 단점 : 다항식의연산들이복잡해진다 ( 프로그램 3.3 참조 ). ( 예 ) 다항식의덧셈 A=8x 3 +7x+, B=x 3 +3x 2 +, C=A+B A B avail coef expon 2 3 4 5 6 7 8 9 8 3 7 3 3 2 A B C avail 2 3 4 5 6 7 8 9 coef 8 7 3 8 3 7 2 expon 3 3 2 3 2 C 로쉽게풀어쓴자료구조 생능출판사 25
다항식표현방법 #2( 계속 ) // 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 -; C 로쉽게풀어쓴자료구조 생능출판사 25
C 로쉽게풀어쓴자료구조 생능출판사 25 희소행렬 배열을이용하여행렬 (matrix) 를표현하는 2 가지방법 () 2 차원배열을이용하여배열의전체요소를저장하는방법 (2) 이아닌요소들만저장하는방법 희소행렬 : 대부분의항들이 인배열 2 5 6 8 9 7 5 7 9 8 3 2 B A
희소행렬표현방법 # 2 차원배열을이용하여배열의전체요소를저장하는방법 장점 : 행렬의연산들을간단하게구현할수있다. 단점 : 대부분의항들이 인희소행렬의경우많은메모리공간낭비 2 A 8 7 3 9 5 9 B 6 5 2 7 8 2 2 3 A= B= 8 9 2 3 4 5 2 7 2 9 2 82 2 2 2 3 6 5 2 2 2 7 5 4 2 2 5 2 C 로쉽게풀어쓴자료구조 생능출판사 25
희소행렬표현방법 #2 이아닌요소들만저장하는방법 장점 : 희소행렬의경우, 메모리공간의절약 단점 : 각종행렬연산들의구현이복잡해진다. 행열값 2 7 32 9 8 2 3 2 8 2 A 8 9 B 6 5 A= B= 3 9 2 7 5 4 2 2 2 5 2 7 6 2 2 5 행열값 3 72 92 2 5 82 3 3 62 4 3 52 5 4 5 5 2 2 6 C 로쉽게풀어쓴자료구조 생능출판사 25
구조체 구조체 (structure): 타입이다른데이터를하나로묶는방법 배열 (array): 타입이같은데이터들을하나로묶는방법 배열 구조체 필드 char carray[]; struct example { char cfield; int ifield; float ffield; double dfield; ; struct example s; C 로쉽게풀어쓴자료구조 생능출판사 25
구조체의사용예 구조체의선언과구조체변수의생성 struct person { char name[]; int age; float height; ; struct person a; // 문자배열로된이름 // 나이를나타내는정수값 // 키를나타내는실수값 // 구조체변수선언 typedef 을이용한구조체의선언과구조체변수의생성 typedef struct person { char name[]; int age; float height; person; person a; // 문자배열로된이름 // 나이를나타내는정수값 // 키를나타내는실수값 // 구조체변수선언 C 로쉽게풀어쓴자료구조 생능출판사 25
구조체의대입과비교연산 구조체변수의대입 : 가능 struct person { char name[]; int age; float height; ; main() { person a, b; b = a; // 문자배열로된이름 // 나이를나타내는정수값 // 키를나타내는실수값 // 가능 구조체변수끼리의비교 : 불가능 main() { if( a > b ) printf("a 가 b 보다나이가많음 "); // 불가능 C 로쉽게풀어쓴자료구조 생능출판사 25
자체참조구조체 자체참조구조체 (self-referential structure): 필드중에자기자신을가리키는포인터가한개이상존재하는구조체 연결리스트나트리에많이등장 typedef struct ListNode { char data[]; struct ListNode *link; ListNode; C 로쉽게풀어쓴자료구조 생능출판사 25
포인터 (pointer) 포인터 : 다른변수의주소를가지고있는변수 26 주소 char a='a'; char *p; p = &a; 26 A 포인터 p 변수 a 포인터가가리키는내용의변경 : * 연산자사용 *p= 'B'; 26 주소 26 B 포인터 p 변수 a C 로쉽게풀어쓴자료구조 생능출판사 25
포인터와관련된연산자 & 연산자 : 변수의주소를추출 * 연산자 : 포인터가가리키는곳의내용을추출 *p 주소 26 &a 26 A 포인터 p 변수 a p // 포인터 *p // 포인터가가리키는값 *p++ // 포인터가가리키는값을가져온다음, 포인터를한칸증가한다. *p-- // 포인터가가리키는값을가져온다음, 포인터를한칸감소한다. (*p)++ // 포인터가가리키는값을증가시킨다. int a; // 정수변수선언 int *p; // 정수포인터선언 int **pp; // 정수포인터의포인터선언 p = &a; // 변수 a와포인터 p를연결 pp = &p; // 포인터 p와포인터의포인터 pp를연결 C 로쉽게풀어쓴자료구조 생능출판사 25
디양한포인터 포인터의종류 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; C 로쉽게풀어쓴자료구조 생능출판사 25
함수의파라미터로서의포인터 함수안에서파라미터로전달된포인터를이용하여외부변수의값변경가능 void swap(int *px, int *py) { int tmp; tmp = *px; *px = *py; *py = tmp; main() { int a=,b=2; printf("swap 을호출하기전 : a=%d, b=%d\n", a,b); swap(&a, &b); printf("swap 을호출한다음 : a=%d, b=%d\n", a,b); C 로쉽게풀어쓴자료구조 생능출판사 25
배열과포인터 배열의이름 : 사실상의포인터와같은역할 4 8 22 26 3 A[] A[] A[2] A[3] A[4] A[5] A 컴파일러가배열의이름을배열의첫번째주소로대치 C 로쉽게풀어쓴자료구조 생능출판사 25
구조체의포인터 구조체의요소에접근하는연산자 : -> 98 ps 98 2 3.4 s.i = ps->i s.f = ps->f s main() { struct { int i; float f; s, *ps; ps = &s; ps->i = 2; ps->f = 3.4; C 로쉽게풀어쓴자료구조 생능출판사 25
포인터의포인터 89 56 26 56 포인터의포인터 pp 26 포인터 p A 변수 a int a; // 정수변수변수선언 int *p; // 정수포인터선언 int **pp; // 정수포인터의포인터선언 p = &a; // 변수 a와포인터 p를연결 pp = &p; // 포인터 p와포인터의포인터 pp를연결 C 로쉽게풀어쓴자료구조 생능출판사 25
포인터연산 포인터에대한사칙연산 : 포인터가가리키는객체단위로계산된다. p // 포인터 p+ // 포인터 p가가리키는객체의바로뒤객체 p- // 포인터 p가가리키는객체의바로앞객체 4 8 22 26 3 A[] A[] A[2] A[3] A[4] A[5] p- p p+ C 로쉽게풀어쓴자료구조 생능출판사 25
포인터사용시주의할점 포인터가아무것도가리키고있지않을때는 NULL 로설정 int *pi=null; 초기화가안된상태에서사용금지 main() { char *pc; *pc = 'E ; // 포인터 pi는초기화가안되어있음 // 위험한코드 포인터타입간의변환시에는명시적인타입변환사용 int *pi; float *pf; pf = (float *)pi; C 로쉽게풀어쓴자료구조 생능출판사 25
동적메모리할당 프로그램이메모리를할당받는방법 정적메모리 동적메모리할당 정적메모리할당 메모리의크기는프로그램이시작하기전에결정 프로그램의수행도중에그크기가변경될수는없다. 만약처음에결정된크기보다더큰입력이들어온다면처리하지못할것이고더작은입력이들어온다면남은메모리공간은낭비될것이다. ( 예 ) 변수나배열의선언 메모리 2 바이트가필요한데. 운영체제 int buffer[]; char name[] = data structure"; 동적메모리할당 프로그램의실행도중에메모리를할당받는것 필요한만큼만할당을받고또필요한때에사용하고반납 메모리를매우효율적으로사용가능 프로그램 C 로쉽게풀어쓴자료구조 생능출판사 25
동적메모리할당 전형적인동적메모리할당코드 main() { int *pi; pi = (int *)malloc(sizeof(int));...... free(pi); // 동적메모리할당 // 동적메모리사용 // 동적메모리반납 동적메모리할당관련라이브러리함수 malloc(size) // 메모리할당 free(ptr) // 메모리할당해제 sizeof(var) // 변수나타입의크기반환 ( 바이트단위 ) C 로쉽게풀어쓴자료구조 생능출판사 25
동적메모리할당라이브러리 malloc(int size) size 바이트만큼의메모리블록을할당 (char *)malloc() ; /* 바이트로 5 개의정수를저장 */ (int *)malloc(sizeof(int));/* 정수 개를저장할메모리확보 */ (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[] = {, 2, 3, 4, 5 ; size_t sizearr = sizeof( array ) / sizeof( array[] ); // 2/4=5 C 로쉽게풀어쓴자료구조 생능출판사 25
동적메모리할당예제 struct Example { int number; char name[]; ; void main() { struct Example *p; p=(struct Example *)malloc(2*sizeof(struct Example)); if(p==null){ fprintf(stderr, "can't allocate memory\n") ; exit() ; p->number=; strcpy(p->name,"park"); (p+)->number=2; strcpy((p+)->name,"kim"); free(p); C 로쉽게풀어쓴자료구조 생능출판사 25