Data Structure Chapter 3. 배열, 구조체, 포인터 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr
배열
배열 같은형의변수를여러개만드는경우에사용 int A, A1, A2, A3,,A9; int A[1]; 1 2 3 4 5 6 7 8 9 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램 : 만약배열이없었다면? tmp=score[]; for(i=1;i<n;i++){ if( score[i] > tmp ) tmp = score[i]; 3
배열 ADT 정의 : < 인덱스, 요소 > 쌍의집합 인덱스가주어지면해당되는요소가대응되는구조 배열 ADT 객체 : < 인덱스, 요소 > 쌍의집합연산 : create(n) ::= n 개의요소를가진배열의생성. retrieve(a, i) ::= 배열 A 의 i 번째요소반환. store(a, i, item) ::= 배열 A 의 i 번째위치에 item 저장. 4
1 차원배열 int A[6]; A[] A[1] 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) 5
2 차원배열 int A[3][4]; A[][] A[][] A[][1] A[][2] A[1][] A[1][1] A[1][2] A[2][] A[2][1] A[2][2] A[][3] A[1][3] A[2][3] A[][1] A[][2] A[][3] A[1][] A[2][3] 실제메모리안에서의위치 6
배열의응용 : 다항식
배열의응용 : 다항식 다항식의일반적인형태 n p( x) a x a a x a n n1 n1 x... 1 프로그램에서다항식을처리하려면다항식을위한자료구조가필요 다항식의덧셈, 뺄셈, 곱셈, 나눗셈연산이편리하고효율적이어야함 배열을사용한 2 가지방법 다항식의모든항을배열에저장 다항식의 이아닌항만을배열에저장 8
다항식의표현방법 모든항저장 (1/4) 모든차수에대한계수값을배열로저장 하나의다항식을하나의배열로표현 5 4 3 2 1 1x x x x 6x 3x 1 2 3 4 5 6 7 8 9 1 coef 1 6 3 typedef struct { int degree; float coef[max_degree]; polynomial; polynomial a = { 5, {1,,,, 6, 3 ; 9
다항식의표현방법 모든항저장 (2/4) 장점 : 다항식의각종연산이간단해짐 단점 : 대부분의항의계수가 이면공간의낭비가심함. 예 ) 다항식의덧셈연산 #include <stdio.h> #define MAX(a,b) (((a)>(b))?(a):(b)) #define MAX_DEGREE 11 typedef struct { int degree; float coef[max_degree]; polynomial; // 다항식구조체타입선언 // 다항식의계수 // 다항식의차수 1
다항식의표현방법 모든항저장 (3/4) // C = A+B 여기서 A와 B는다항식이다. polynomial poly_add1(polynomial A, polynomial B) { polynomial C; // 결과다항식 int Apos=, Bpos=, Cpos=; // 배열인덱스변수 int degree_a=a.degree; int degree_b=b.degree; C.degree = MAX(A.degree, B.degree); // 결과다항식차수 while( Apos<=A.degree && Bpos<=B.degree ){ if( degree_a > degree_b ){ // A항 > B항 C.coef[Cpos++]= A.coef[Apos++]; degree_a--; 11
다항식의표현방법 모든항저장 (4/4) // 주함수 main() { 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--; return C; polynomial a = { 5, {3, 6,,,, 1 ; polynomial b = { 4, {7,, 5,, 1 ; polynomial c; c = poly_add1(a, b); 12
다항식표현방법 이아닌항저장 (1/6) 다항식에서 이아닌항만을배열에저장 ( 계수, 차수 ) 형식으로배열에저장 예 ) 1x 5 +6x+3 -> ((1,5), (6,1), (3,)) struct { float coef; int expon; terms[max_terms]={ {1,5, {6,1, {3, ; 하나의배열로여러개의다항식을나타낼수있음. A B avail coef expon 1 2 3 4 5 6 7 8 9 1 8 3 7 1 1 1 3 3 2 1 terms 13
다항식표현방법 이아닌항저장 (2/6) 장점 : 메모리공간의효율적인이용 단점 : 다항식의연산들이복잡해진다 ( 프로그램 3.3 참조 ). 예 ) 다항식의덧셈 A=8x3+7x+1, B=1x3+3x2+1, C=A+B A B avail 1 2 3 4 5 6 7 8 9 1 coef expon 8 3 7 1 1 1 3 3 2 1 terms A B C avail 1 2 3 4 5 6 7 8 9 1 coef 8 7 1 1 3 1 18 3 7 2 expon 3 1 3 2 3 2 1 14
다항식표현방법 이아닌항저장 (3/6) #define MAX_TERMS 11 struct { float coef; int expon; terms[max_terms]={ {8,3, {7,1, {1,, {1,3, {3,2,{1, ; int avail=6; // 두개의정수를비교 char compare(int a, int b) { if( a>b ) return '>'; else if( a==b ) return '='; else return '<'; 15
다항식표현방법 이아닌항저장 (4/6) // 새로운항을다항식에추가한다. void attach(float coef, int expon) { if( avail>max_terms ){ fprintf(stderr, " 항의개수가너무많음 \n"); exit(1); terms[avail].coef=coef; terms[avail++].expon=expon; 16
다항식표현방법 이아닌항저장 (5/6) // C = A + B 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; 17
다항식표현방법 이아닌항저장 (6/6) // 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; // void main() { int Cs, Ce; poly_add2(,2,3,5,&cs,&ce); 18
배열의응용 : 희소행렬
2 2 희소행렬 배열을이용하여행렬 (matrix) 을표현하는 2 가지방법 2 차원배열을이용하여배열의전체요소를저장하는방법 이아닌요소들만저장하는방법 희소행렬 : 대부분의항들이 인배열 2 1 5 6 8 9 7 5 7 1 9 8 3 2 B A
희소행렬표현방법 전체요소저장 (1/3) 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 21 5 2 21
희소행렬표현방법 전체요소저장 (2/3) #include <stdio.h> #define ROWS 3 #define COLS 3 // 희소행렬덧셈함수 void sparse_matrix_add1(int A[ROWS][COLS], int B[ROWS][COLS], int C[ROWS][COLS]) // C=A+B { int r,c; for(r=;r<rows;r++) for(c=;c<cols;c++) C[r][c] = A[r][c] + B[r][c]; 22
희소행렬표현방법 전체요소저장 (3/3) main() { int array1[rows][cols] = { { 2,3,, { 8,9,1, { 7,,5 ; int array2[rows][cols] = { { 1,,, { 1,,, { 1,, ; int array3[rows][cols]; sparse_matrix_add1(array1,array2,array3); 23
희소행렬표현방법 이아닌요소저장 (1/5) 이아닌요소들만저장하는방법 장점 : 희소행렬의경우, 메모리공간의절약 단점 : 각종행렬연산들의구현이복잡해진다. 행열값 1 2 7 1 1 32 9 8 2 3 2 1 1 8 2 A 8 9 1 B A= B= 6 5 3 1 1 9 2 7 5 1 4 1 21 21 2 5 2 7 6 2 2 5 행열값 31 27 1 1 1 92 2 1 51 82 3 3 1 62 4 3 1 52 5 4 5 1 6 5 2 2 24
희소행렬표현방법 이아닌요소저장 (2/5) #define ROWS 3 #define COLS 3 #define MAX_TERMS 1 typedef struct { int row; int col; int value; element; typedef struct SparseMatrix { element data[max_terms]; int rows; // 행의개수 int cols; // 열의개수 int terms; // 항의개수 SparseMatrix; 25
희소행렬표현방법 이아닌요소저장 (3/5) // 희소행렬덧셈함수 // c = a + b SparseMatrix sparse_matrix_add2(sparsematrix a, SparseMatrix b) { SparseMatrix c; int ca=, cb=, cc=; // 각배열의항목을가리키는인덱스 // 배열 a와배열 b의크기가같은지를확인 if( a.rows!= b.rows a.cols!= b.cols ){ fprintf(stderr," 희소행렬크기에러 \n"); exit(1); c.rows = a.rows; c.cols = a.cols; c.terms = ; 26
희소행렬표현방법 이아닌요소저장 (4/5) while( ca < a.terms && cb < b.terms ){ // 각항목의순차적인번호를계산한다. int inda = a.data[ca].row * a.cols + a.data[ca].col; int indb = b.data[cb].row * b.cols + b.data[cb].col; if( inda < indb) { // a 배열항목이앞에있으면 c.data[cc++] = a.data[ca++]; else if( inda == indb ){ // a와 b가같은위치 if( (a.data[ca].value+b.data[cb].value)!=){ c.data[cc].row = a.data[ca].row; c.data[cc].col = a.data[ca].col; c.data[cc++].value = a.data[ca++].value + b.data[cb++].value; else { ca++; cb++; else // b 배열항목이앞에있음 c.data[cc++] = b.data[cb++]; 27
희소행렬표현방법 이아닌요소저장 (5/5) // 배열 a와 b에남아있는항들을배열 c로옮긴다. for(; ca < a.terms; ) c.data[cc++] = a.data[ca++]; for(; cb < b.terms; ) c.data[cc++] = b.data[cb++]; c.terms = cc; return c; // 주함수 main() { SparseMatrix m1 = { {{ 1,1,5,{ 2,2,9, 3,3,2 ; SparseMatrix m2 = { {{,,5,{ 2,2,9, 3,3,2 ; SparseMatrix m3; m3 = sparse_matrix_add2(m1, m2); 28
구조체
구조체 vs 배열 구조체 (structure) : 타입이다른데이터를하나로묶는방법 배열 (array) : 타입이같은데이터들을하나로묶는방법 배열 구조체 필드 1 char carray[1]; struct example { char cfield; int ifield; float ffield; double dfield; ; struct example s1; 3
구조체의사용예 구조체의선언과구조체변수의생성 struct person { char name[1]; int age; float height; ; struct person a; // 문자배열로된이름 // 나이를나타내는정수값 // 키를나타내는실수값 // 구조체변수선언 typedef 을이용한구조체의선언과구조체변수의생성 typedef struct person { char name[1]; int age; float height; person; person a; // 문자배열로된이름 // 나이를나타내는정수값 // 키를나타내는실수값 // 구조체변수선언 31
구조체의대입과비교연산 구조체변수의대입 : 가능 struct person { char name[1]; int age; float height; ; main() { person a, b; b = a; // 문자배열로된이름 // 나이를나타내는정수값 // 키를나타내는실수값 // 가능 구조체변수끼리의비교 : 불가능 main() { if( a > b ) printf("a 가 b 보다나이가많음 "); // 불가능 32
구조체를포함하는구조체 구조체를포함하는구조체 구조체란하나이상의변수를그룹지어서새로운자료형을정의하는것이므 로구조체변수도구조체멤버로할수있다. struct point { int x; int y; struct circle { struct point p; double radius; ; circle point x y radius 33
중첩된구조체변수의초기화 중첩된구조체변수의초기화 총맴버의개수만큼 { 안에입력하면순서대로값이초기화된다. 내부에구조체를구분해주기위해서 { 을사용한다. int main() { struct simple c1 = {1, 1, 1.5; struct simple c2 = {{3, 3, 2.4; struct simple c3 = {1, 1; struct simple c4 = {{1, 1; return ; c1 c2 c3 c4 x = 1 x = 3 x = 1 x = 1 y = 1 y = 3 y = 1 y = radius = 1.5 radius = 2.4 radius =. radius = 1. 34
구조체를포함하는구조체주의점 (1/2) 자기자신은포함할수없음 구조체가무한히반복되므로구조체의크기를측정할수없음 struct person { char name[2]; int age; struct person frnd; ; 에러발생 person name age person name age person 35
구조체를포함하는구조체주의점 (2/2) 자기자신을포인터로가리킬수는있음 struct person { char name[2]; int age; struct person *frnd; int main() { struct person person1, person2, person3; person1.frnd = &person2; person2.frnd = &person3; return ; person1 name age frnd person3 name age frnd person2 name age frnd 36
자체참조구조체 자체참조구조체 (self-referential structure) 필드중에자기자신을가리키는포인터가한개이상존재하는구조체 연결리스트나트리에많이등장 typedef struct ListNode { char data[1]; struct ListNode *link; ListNode; 37
포인터
포인터 (pointer) 정의 : 다른변수의주소를가지고있는변수 char a='a'; char *p; p = &a; 26 26 A 주소 포인터가가리키는내용의변경 : * 연산자사용 *p= 'B'; 포인터 p 26 변수 a 주소 26 B 포인터 p 변수 a 39
포인터와관련된연산자 & 연산자 : 변수의주소를추출 * 연산자 : 포인터가가리키는곳의내용을추출 26 26 B 주소 포인터 p 변수 a p // 포인터 *p // 포인터가가리키는값 *p++ // 포인터가가리키는값을가져온다음, 포인터를한칸증가한다. *p-- // 포인터가가리키는값을가져온다음, 포인터를한칸감소한다. (*p)++ // 포인터가가리키는값을증가시킨다. int a; // 정수변수선언 int *p; // 정수포인터선언 int **pp; // 정수포인터의포인터선언 p = &a; // 변수 a와포인터 p를연결 pp = &p; // 포인터 p와포인터의포인터 pp를연결 4
다양한포인터 포인터의종류 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; 41
함수의파라미터로서의포인터 함수안에서파라미터로전달된포인터를이용하여외부변수의 값변경가능 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); 42
배열과포인터 배열의이름 : 사실상의포인터와같은역할 1 14 18 22 26 3 A[] A[1] A[2] A[3] A[4] A[5] A 컴파일러가배열의이름을배열의첫번째주소로대치 43
구조체의포인터 구조체의요소에접근하는연산자 : -> 98 main() { struct { int i; float f; s, *ps; ps = &s; ps->i = 2; ps->f = 3.14; 98 ps 2 3.14 s s.i = ps->i s.f = ps->f 44
포인터의포인터 89 56 26 56 포인터의포인터 pp 26 포인터 p A 변수 a int a; // 정수변수변수선언 int *p; // 정수포인터선언 int **pp; // 정수포인터의포인터선언 p = &a; // 변수 a와포인터 p를연결 pp = &p; // 포인터 p와포인터의포인터 pp를연결 45
포인터연산 포인터에대한사칙연산 : 포인터가가리키는객체단위로계산된다. p // 포인터 p+1 // 포인터 p가가리키는객체의바로뒤객체 p-1 // 포인터 p가가리키는객체의바로앞객체 1 14 18 22 26 3 A[] A[1] A[2] A[3] A[4] A[5] p-1 p p+1 46
포인트사용시주의할점 포인터가아무것도가리키고있지않을때는 NULL 로설정 int *pi=null; 초기화가안된상태에서사용금지 main() { char *pc; *pc = 'E ; // 포인터 pi는초기화가안되어있음 // 위험한코드 포인터타입간의변환시에는명시적인타입변환사용 int *pi; float *pf; pf = (float *)pi; 47
동적메모리할당
동적메모리할당 (1/2) 프로그램이메모리를할당받는방법 정적메모리 동적메모리할당 정적메모리할당 메모리의크기는프로그램이시작하기전에결정 프로그램의수행도중에그크기가변경될수는없다. 예 ) 변수나배열의선언 int buffer[1]; char name[] = data structure"; 동적메모리할당 프로그램의실행도중에메모리를할당받는것 필요한만큼만할당을받고또필요한때에사용하고반납 메모리를매우효율적으로사용가능 49
동적메모리할당 (2/2) 전형적인동적메모리할당코드 main() { int *pi; pi = (int *)malloc(sizeof(int)); // 동적메모리할당... // 동적메모리사용... free(pi); // 동적메모리반납 동적메모리할당관련라이브러리함수 malloc(size) // 메모리할당 free(ptr) // 메모리할당해제 sizeof(var) // 변수나타입의크기반환 ( 바이트단위 ) 5
동적메모리할당라이브러리 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 51
동적메모리할당예제 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); 52