C로 쉽게 풀어쓴 자료구조 © Copyright 생능출판사 2011

Presentation on theme: "C로 쉽게 풀어쓴 자료구조 © Copyright 생능출판사 2011"— Presentation transcript:

1 C로 쉽게 풀어쓴 자료구조 © Copyright 생능출판사 2011
CHAP 3:배열, 구조체, 포인터 C로 쉽게 풀어쓴 자료구조 © Copyright 생능출판사 2011

2 배열이란? 같은 형의 변수를 여러 개 만드는 경우에 사용 반복 코드 등에서 배열을 사용하면 효율적인 프로그래밍이 가능
int A0, A1, A2, A3, …,A9;  int A[10]; 반복 코드 등에서 배열을 사용하면 효율적인 프로그래밍이 가능 예) 최대값을 구하는 프로그램: 만약 배열이 없었다면? 1 2 3 4 5 6 7 8 9 tmp=score[0]; 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[0] A[1] A[2] A[3] A[4] A[5] base base+sizeof(int)

5 2차원 배열 int A[3][4]; 실제 메모리안에서의 위치 A[2][0] A[2][1] A[2][2] A[1][0]
… A[1][3] 실제 메모리안에서의 위치

6 배열의 응용: 다항식 다항식의 일반적인 형태 프로그램에서 다항식을 처리하려면 다항식을 위한 자료구조가 필요-> 어떤 자료구조를 사용해야 다항식의 덧셈, 뺄셈,곱셈, 나눗셈 연산을 할때 편리하고 효율적일까? 배열을 사용한 2가지 방법 다항식의 모든 항을 배열에 저장 다항식의 0이 아닌 항만을 배열에 저장

7 다항식 표현 방법 #1 10 6 3 모든 차수에 대한 계수값을 배열로 저장 하나의 다항식을 하나의 배열로 표현 coef 1 2
6 3 1 2 4 5 7 8 9 typedef struct { int degree; float coef[MAX_DEGREE]; } polynomial; polynomial a = { 5, {10, 0, 0, 0, 6, 3} };

8 다항식 표현 방법 #1(계속) #include <stdio.h>
장점: 다항식의 각종 연산이 간단해짐 단점: 대부분의 항의 계수가 0이면 공간의 낭비가 심함. 예) 다항식의 덧셈 연산 #include <stdio.h> #define MAX(a,b) (((a)>(b))?(a):(b)) #define MAX_DEGREE 101 typedef struct { // 다항식 구조체 //타입 선언 int degree; // 다항식의 차수 float coef[MAX_DEGREE]; // 다항식의 계수 } polynomial;

9 다항식 표현 방법 #1(계속) // C = A+B 여기서 A와 B는 다항식이다.
polynomial poly_add1(polynomial A, polynomial B) { polynomial C; // 결과 다항식 int Apos=0, Bpos=0, Cpos=0; // 배열 인덱스 변수 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--; }

10 다항식 표현 방법 #1(계속) 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; // 주함수 main() { polynomial a = { 5, {3, 6, 0, 0, 0, 10} }; polynomial b = { 4, {7, 0, 5, 0, 1} }; polynomial c; c = poly_add1(a,b);

11 다항식 표현 방법 #2 다항식에서 0이 아닌 항만을 배열에 저장 (계수, 차수) 형식으로 배열에 저장
(예) 10x5+6x+3 -> ((10,5), (6,1), (3,0)) 하나의 배열로 여러 개의 다항식을 나타낼 수 있음. struct { float coef; int expon; } terms[MAX_TERMS]={ {10,5}, {6,1}, {3,0} }; 3 8 1 7 10 2 4 5 6 9 A B avail coef expon terms

12 다항식 표현 방법 #2(계속) 장점: 메모리 공간의 효율적인 이용 단점: 다항식의 연산들이 복잡해진다(프로그램 3.3 참조).
(예) 다항식의 덧셈 A=8x3+7x+1, B=10x3+3x2+1, C=A+B A B avail 1 2 3 4 5 6 7 8 9 10 8 7 1 10 3 1 coef 3 1 3 2 expon A B C avail 1 2 3 4 5 6 7 8 9 10 8 7 1 10 3 1 18 3 7 2 coef 3 1 3 2 3 2 1 expon

13 다항식 표현 방법 #2(계속) #define MAX_TERMS 101 struct { float coef; int expon;
} terms[MAX_TERMS]={ {8,3}, {7,1}, {1,0}, {10,3}, {3,2},{1,0} }; int avail=6; // 두개의 정수를 비교 char compare(int a, int b) { if( a>b ) return '>'; else if( a==b ) return '='; else return '<'; }

14 다항식 표현 방법 #2(계속) // 새로운 항을 다항식에 추가한다.
void attach(float coef, int expon) { if( avail>MAX_TERMS ){ fprintf(stderr, "항의 개수가 너무 많음\n"); exit(1); } terms[avail].coef=coef; terms[avail++].expon=expon;

15 다항식 표현 방법 #2(계속) // 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; }

16 다항식 표현 방법 #2(계속) // 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(0,2,3,5,&Cs,&Ce);

17 희소행렬 배열을 이용하여 행렬(matrix)를 표현하는 2가지 방법 희소행렬: 대부분의 항들이 0인 배열
(1) 2차원 배열을 이용하여 배열의 전체 요소를 저장하는 방법 (2) 0이 아닌 요소들만 저장하는 방법 희소행렬: 대부분의 항들이 0인 배열

18 희소행렬 표현방법 #1 2차원 배열을 이용하여 배열의 전체 요소를 저장하는 방법 A= B=
장점: 행렬의 연산들을 간단하게 구현할 수 있다. 단점: 대부분의 항들이 0인 희소 행렬의 경우 많은 메모리 공간 낭비 2 1 5 4 6 3 9 8 7 7 8 9 5 1 2 3 A= B=

19 희소 행렬 #1 #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=0;r<ROWS;r++) for(c=0;c<COLS;c++) C[r][c] = A[r][c] + B[r][c]; }

20 희소 행렬 #1 main() { int array1[ROWS][COLS] = { { 2,3,0 }, { 8,9,1 },
{ 7,0,5 } }; int array2[ROWS][COLS] = { { 1,0,0 }, { 1,0,0 }, { 1,0,0 } }; int array3[ROWS][COLS]; sparse_matrix_add1(array1,array2,array3); }

21 희소행렬 표현방법 #2 0이 아닌 요소들만 저장하는 방법 A= B= 장점: 희소 행렬의 경우, 메모리 공간의 절약
단점: 각종 행렬 연산들의 구현이 복잡해진다. 2 5 6 7 1 4 9 3 8 행 열 값 A= B=

22 희소 행렬 #1 #define ROWS 3 #define COLS 3 #define MAX_TERMS 10
typedef struct { int row; int col; int value; } element; typedef struct SparseMatrix { element data[MAX_TERMS]; int rows; // 행의 개수 int cols; // 열의 개수 int terms; // 항의 개수 } SparseMatrix;

23 희소 행렬 #1 // 희소 행렬 덧셈 함수 // c = a + b
SparseMatrix sparse_matrix_add2(SparseMatrix a, SparseMatrix b) { SparseMatrix c; int ca=0, cb=0, cc=0; // 각 배열의 항목을 가리키는 인덱스 // 배열 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 = 0;

24 희소 행렬 #1 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가 같은 위치 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 // b 배열 항목이 앞에 있음 c.data[cc++] = b.data[cb++];

25 희소 행렬 #1 // 배열 a와 b에 남아 있는 항들을 배열 c로 옮긴다. for(; ca < a.terms; ca++)
c.data[cc++] = a.data[ca++]; for(; cb < b.terms; cb++) 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 = { {{ 0,0,5 },{ 2,2,9 }}, 3,3,2 }; SparseMatrix m3; m3 = sparse_matrix_add2(m1, m2);

26 구조체 구조체(structure): 타입이 다른 데이터를 하나로 묶는 방법
배열(array): 타입이 같은 데이터들을 하나로 묶는 방법 구조체 배열 필드 1 char carray[100]; struct example { char cfield; int ifield; float ffield; double dfield; }; struct example s1;

27 구조체의 사용예 구조체의 선언과 구조체 변수의 생성 typedef을 이용한 구조체의 선언과 구조체 변수의 생성
struct person { char name[10]; // 문자배열로 된 이름 int age; // 나이를 나타내는 정수값 float height; // 키를 나타내는 실수값 }; struct person a; // 구조체 변수 선언 typedef을 이용한 구조체의 선언과 구조체 변수의 생성 typedef struct person { char name[10]; // 문자배열로 된 이름 int age; // 나이를 나타내는 정수값 float height; // 키를 나타내는 실수값 } person; person a; // 구조체 변수 선언

28 구조체의 대입과 비교 연산 구조체 변수의 대입: 가능 구조체 변수끼리의 비교: 불가능 struct person {
char name[10]; // 문자배열로 된 이름 int age; // 나이를 나타내는 정수값 float height; // 키를 나타내는 실수값 }; main() { person a, b; b = a; // 가능 } 구조체 변수끼리의 비교: 불가능 main() { if( a > b ) printf("a가 b보다 나이가 많음"); // 불가능 }

29 int compare(person a, person b)
{ if (a.age>b.age) return 1; else if (a.age==b.age) return 0; else return -1; } void main() person a,b; a.age=30; b.age=20; //strcpy(a.name, “Tom”) //sprintf(a.name, “%s”, “Tom”); if(compare(a,b)>0) printf(“a가 b보다 나이가 많음”); else printf(“a가 b보다 나이가 많지 않음”);

30 구조체 배열 #define MAX_STUDENTS 200 #define MAX_NAME 100 typedef struct{
int month; int date; }BirthdayType; char name[MAX_NAME]; BirthdayType birthday; }StudentType; StudentType students[MAX_STUDENTS];

31 void main() { strcpy(students[0]. name, “HongGil Dong”); students[0]
void main() { strcpy(students[0].name, “HongGil Dong”); students[0].birthday.month=10; students[0].birthday.date=28; }

32 자체참조 구조체 자체 참조 구조체(self-referential structure): 필드중에 자기 자신을 가리키는 포인터가 한 개 이상 존재하는 구조체 연결 리스트나 트리에 많이 등장 typedef struct ListNode { char data[10]; struct ListNode *link; } ListNode;

33 포인터(pointer) 포인터: 다른 변수의 주소를 가지고 있는 변수 포인터가 가리키는 내용의 변경: * 연산자 사용 주소
26 ‘A’ 변수 a 주소 포인터 p 포인터: 다른 변수의 주소를 가지고 있는 변수 char a='A'; char *p; p = &a; 포인터가 가리키는 내용의 변경: * 연산자 사용 26 ‘B’ 변수 a 주소 포인터 p *p= 'B';

34 포인터와 관련된 연산자 & 연산자: 변수의 주소를 추출 * 연산자: 포인터가 가리키는 곳의 내용을 추출 26 &a *p ‘A’
int a; // 정수 변수 선언 int *p; // 정수 포인터 선언 int **pp; // 정수 포인터의 포인터 선언 p = &a; // 변수 a와 포인터 p를 연결 pp = &p; // 포인터 p와 포인터의 포인터 pp를 연결

35 디양한 포인터 포인터의 종류 포인터의 형변환: 필요할 때마다 형변환하는 것이 가능하다.
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;

36 함수의 파라미터로서의 포인터 함수안에서 파라미터로 전달된 포인터를 이용하여 외부 변수의 값 변경 가능
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);

37 함수의 파라미터로서의 포인터 typedef struct { int x; int y; }PointType;
Int get_line_parameter(PointType p1, PointType p2, float *slope, float *yintercept) { if(p1.x==p2.x) return -1; else{ *slope=(float)(p2.y-p1.y)/(float)(p2.x-p1.x); *yintersept=p1.y-(*slope)*p1.x; return 0;}

38 void main() { PointType pt1={3,3},pt2={6,6}; float s,y; if(get_line_parameter(pt1,pt2, &s, &y)==-1){ printf(“error\n”); } else{ printf(“기울기는 %f, y절편은 %f\n”,s,y);

39 배열과 포인터 배열의 이름: 사실상의 포인터와 같은 역할 컴파일러가 배열의 이름을 배열의 첫번째 주소로 대치 10 A[0] A
14 A[1] 18 A[2] 22 A[3] 26 A[4] 30 A[5] 컴파일러가 배열의 이름을 배열의 첫번째 주소로 대치

40 구조체의 포인터 구조체의 요소에 접근하는 연산자: -> 98 2 s.I = ps->i ps 3.14
s.f = ps->f main() { struct { int i; float f; } s, *ps; ps = &s; ps->i = 2; ps->f = 3.14; }

41 포인터의 포인터 int a; // 정수 변수 변수 선언 int *p; // 정수 포인터 선언
56 26 ‘A’ 변수 a 포인터 p 89 포인터의 포인터 pp int a; // 정수 변수 변수 선언 int *p; // 정수 포인터 선언 int **pp; // 정수 포인터의 포인터 선언 p = &a; // 변수 a와 포인터 p를 연결 pp = &p; // 포인터 p와 포인터의 포인터 pp를 연결

42 포인터 연산 포인터에 대한 사칙연산: 포인터가 가리키는 객체단위로 계산된다. 10 A[0] p 14 A[1] 18 A[2]
p+1 // 포인터 p가 가리키는 객체의 바로 뒤 객체 p-1 // 포인터 p가 가리키는 객체의 바로 앞 객체 10 A[0] p 14 A[1] 18 A[2] 22 A[3] 26 A[4] 30 A[5] p+1 p-1

43 포인터 사용시 주의할 점 포인터가 아무것도 가리키고 있지 않을 때는 NULL로 설정 초기화가 안된 상태에서 사용 금지
int *pi=NULL; 초기화가 안된 상태에서 사용 금지 main() { char *pc; // 포인터 pi는 초기화가 안되어 있음 *pc = 'E’; // 위험한 코드 } 포인터 타입간의 변환시에는 명시적인 타입 변환 사용 int *pi; float *pf; pf = (float *)pi;

44 프로그램의 과정과 메모리할당 C 언어의 메모리관리구조 1.프로그램작성 2. 컴파일 3.링크 4.실행화일 생성
1.데이터영역 –전역변수와 static 변수가 할당 2.힙(heap)영역-프로그래머가 관리하는 메모리영역 3.스택 영역 -지역변수와 매개변수가 저장되는 영역 스택과 데이터 영역에 할당될 메모리의 크기는 컴파일되는 동안 결정(정적 할당) 힙에는 실행시(런 타임) 필요한 만큼 메모리를 할당할 수 있다 (동적할당)

45 동적 메모리 할당 프로그램이 메모리를 할당받는 방법 정적 메모리 할당 정적 메모리 동적 메모리 할당
메모리의 크기는 프로그램이 시작하기 전에 결정 프로그램의 수행 도중에 그 크기가 변경될 수는 없다. 만약 처음에 결정된 크기보다 더 큰 입력이 들어온다면 처리하지 못할 것이고 더 작은 입력이 들어온다면 남은 메모리 공간은 낭비될 것이다. (예) 변수나 배열의 선언 int buffer[100]; char name[] = “data structure"; 프로그램의 실행 도중에 메모리를 할당받는 것 필요한 만큼만 할당을 받고 또 필요한 때에 사용하고 반납 메모리를 매우 효율적으로 사용가능 메모리 200바이트가 필요한데…. 운영체제 프로그램

46 메모리의 동적할당과 해제 malloc함수- Heap영역에 메모리를 할당하는 함수
성공시 할당된 메모리의 첫번째 주소리턴, 실패시 NULL포인터 리턴 #include<stdlib.h> void* malloc(size_t size) int *i=(int*)malloc(sizeof(int)); free함수 – Heap영역에 할당된 메모리 해제 void free(void *ptr) //즉 어떤 포인터도 인자로 전달가능

47 동적 메모리 할당 전형적인 동적 메모리 할당 코드 동적 메모리 할당 관련 라이브러리 함수
main() { int *pi; pi = (int *)malloc(sizeof(int)); // 동적 메모리 할당 ... … // 동적 메모리 사용 free(pi); // 동적 메모리 반납 } 동적 메모리 할당 관련 라이브러리 함수 malloc(size) // 메모리 할당 free(ptr) // 메모리 할당 해제 sizeof(var) // 변수나 타입의 크기 반환(바이트 단위)

48 동적 메모리 할당 라이브러리 malloc(int size)
(char *)malloc(100) ; /* 100 바이트로 100개의 문자를 저장 */ (int *)malloc(sizeof(int));/* 정수 1개를 저장할 메모리 확보*/ (struct Book *)malloc(sizeof(struct Book))/* 하나의 구조체 생성 */ free(void ptr) ptr이 가리키는 할당된 메모리 블록을 해제 sizeof 키워드 변수나 타입의 크기 반환(바이트 단위)

49 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[0] ); //20/4=5

50 동적할당의 예 #include<stdlib.h> #include<stdio.h> int main()
{ int *a; a=(int*)malloc(sizeof(int)); if(a==NULL){ printf(“메모리할당실패”); exit(1);} *a=20; printf(“힙에 저장된 변수 a:%d\n”, *a); free(a);//메모리해제 return 0; }

51 스택 영역 -지역변수와 매개변수가 저장되는 영역
스택과 데이터 영역에 할당될 메모리의 크기는 컴파일되는 동안 결정(정적 할당) void main() { int x=10; int a[10]; //ok int b[x] ;//에러 왜? int *p; p=(int*)malloc(sizeof(int)*x); }

52 동적할당 예 #include<stdio.h> #include<stdlib.h>
void function(int); int main() { int m=0; fputs(“배열의 크기를 입력하시오:”, stdout); scanf(“%d”,&m); function(m); return 0; } x

53 동적할당 예 void function(int i) { //int array[i]; 왜 안될까? (다음 장)
int *array=(int*)malloc(sizeof(int)*i); int j; if(array==NULL){ printf(“메모리할당 실패”); exit(1);} /*동적 할당한 메모리 사용*/ for(j=0;j< i;j++) array[j]=j+1; for(j=0;j< i;j++) printf(“%d “, array[j]); printf(“\n”); free(array); }

54 잘못된 예 void function(int i) { //int i=10; (1) int array[i]; }
(1)의 주석처리를 해제하면 되는가? ---답은 안됨. ---변수 i가 초기화 되는때는 컴파일되는때가 아니라 실행되는 순간에 결정되기때문

55 동적 메모리 할당 예제 struct Example { int number; char name[10]; };
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);

56 void형 포인터 void 형 포인터는 무엇이든 담을 수 있는 포인터 char c=‘a’; int n=10;
void *vp; //void포인터 선언 vp=&c; vp=&n; void 포인터는 포인터 자체에 데이터에 대한 정보가 없으므로(몇 바이트 읽어 들여야 하는지)가 없으므로 값을 변경, 참조,포인터연산등등이 허용되지 않는다. 즉 주소값을 저장하는 것 이외에 아무일도 할 수 없다.

57 void형 포인터 int n=10; void *vp=&n;//void포인터 선언 및 초기화 * vp=20;//error
명시적 형 변환 과정을 거쳐서 사용한다. void *vp=&n; *((int*)vp)=20;//int형 포인터로 변환 일단 주소값을 저장하고 포인터의 타입은 나중에 결정할 때 사용. 메모리의 동적할당에 유용하게 사용