---------------- DATA STRUCTURES USING C ---------------- CHAPTER 배열과구조체 1/20
많은자료의처리? 배열 (array), 구조체 (struct) 성적처리프로그램에서 45 명의성적을저장하는방법 주소록프로그램에서친구들의다양한정보 ( 이름, 전화번호, 주소, 이메일등 ) 를통합하여저장하는방법 홍길동 이름 : 홍길동 1 번 2 번 3 번 45 번 전화 : 010-1234-56XX 84 72 94 87 주소 : 서울특별시 XX 구 YY 동 이메일 : kdhong@korea... 반학생들의성적처리 친구주소록만들기 2/20
배열 같은형의변수를여러개만드는경우에사용 여러개의변수선언 : int A0, A1, A2, A3,,A5; 하나의배열선언 : int A[6]; a3 a5 a6 a2 a1 a4 A[0] A[1] A[2] A[3] A[4] A[5] 변수선언 배열선언 만약배열이없다면? 반복문을사용할수없다! 3/20
배열의특징 배열 : < 인덱스, 요소 > 쌍의집합 인덱스가주어지면해당되는요소가대응되는구조 직접접근 (direct access) 방식 항목접근의시간복잡도가 O(1) 연결리스트 (5장) 벡터? 순차접근 (sequential access) 방식 항목접근의시간복잡도 O(n) C++ 의 STL에서 vector 제공 배열과벡터의차이는? 4/20
1 차원배열 자료형배열이름 [ 배열의 _ 크기 ]; int A[6]; 5/20
배열의복사 변수의복사와배열의복사 #include <stdio.h> void main() { int A[5] = { 10, 20, 30 ; int B[5], i, x = 2018, y = 0; y = x; for (i = 0; i < 5; i++) B[i] = A[i]; printf(" 변수복사결과 : x=%d, y=%d\n", x, y); printf(" 배열복사결과 : \n"); for (i = 0; i < 5; i++) { printf("a[%d] = %d\t", i, A[i]); printf("b[%d] = %d\n", i, B[i]); 6/20
문자열 : 특별한 1 차원배열 char s[12] = game over ; 문자열처리 문자열의복사나비교를위해 = 나 == 또는 < 등의연산자를사용할수없다. strcmp(), strcpy(), <string.h> 포함 7/20
2 차원배열 자료형배열이름 [ 행의 _ 크기 ][ 열의 _ 크기 ]; int A[4][3]; int A[4][3]= { {1,2,3, {4,5,6, {7,8,9, {10,11,12 ; 8/20
함수의매개변수로서의배열 변수의전달 값을복사 (call by value) 배열의전달 첫번째항목의주소를전달 ( 주소를복사 ) void copy_array(int a[], int b[], int len) { int i; for (i = 0; i < len; i++) b[i] = a[i]; void copy_variable(int a, int b) { b = a; int A[5] = { 10, 20, 30 ; int B[5], i, x = 2018, y = 0; copy_variable(x, y); copy_array(a, B, 5); 9/20
배열에서의주의사항 매개변수로배열의길이도전달해야함. int findmaxvalue( int a[], int len ) int arr[10] = {3, ; int maxval = findmaxvalue( arr, 10 ); 2 차원이상의다차원배열의매개변수전달에조심. int findmaxpixel( int a[][5], int h, int w ) 10/20
구조체 기존의자료형들을조합해새로운자료형을만드는방법 배열과의차이 구조체 (structure): 타입이다른데이터를하나로묶음 배열 (array): 타입이같은데이터들을하나로묶음 11/20
구조체의정의와선언 정의 선언 struct Student { typedef struct Student_t { int id; int id; char name[20]; char name[20]; double score; double score; ; Student; struct Student a; Student a; Student a = { 201803156, 홍길동, 96.3 ; 멤버접근 : 항목연산자 (membership operator) '.' a.id = 30830; a.score = 92.3; strcpy(a.name, "Jinyoung"); // a.name = Jinyoung ; 은오류발생 12/20
구조체와연산자 대입연산자만가능 int x, y=10; Student a, b={ 201803156, 홍길동, 96.3 ; x = y; // OK: int 변수의복사 a = b; // OK: 구조체변수의복사 다른연산자사용불가 if( a > b ) a += b; // 오류 : 구조체의비교연산불가 // 오류 : 구조체의다른대입연산도불가 int compare(student a, Student b) { return a.id b.id; 13/20
구조체와함수 함수의매개변수나반환형으로사용할수있음. Call by value 다음함수의동작은? void print_complex(complex c) { printf("%4.1f + %4.1fi\n", c.real, c.imag); void reset_complex(complex c) { c.real = c.imag = 0.0; 14/20
배열과구조체의응용 : 다항식 다항식의일반적인형태 n p( x) a x a a x a n n 1 n 1 x... 처리를위한다항식의자료구조가필요 어떤자료구조가다항식의연산을편리하게할까? 1 0 다항식을위한자료구조? 배열을사용하는방법 모든항의계수를배열에저장 다항식의 0이아닌항만을배열에저장 : 희소다항식 15/20
다항식구조체 #define MAX_DEGREE 101 // 다항식의최고차수 + 1 typedef struct { int degree; float coef[max_degree]; Polynomial ; 방법 1: coef [0] [1] [2] [3] [4] [5] [6] [7] [8] 10 0 0 0 6 3... [9]... 방법2: coef 3 6 0 0 0 10 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 16/20
다항식입출력연산 ( 방법 1) void print_poly(polynomial p, char str[]) { int i; printf("\t%s", str); for( i=0 ; i<p.degree ; i++) printf("%5.1f x^%d + ", p.coef[i], p.degree-i); printf( "%4.1f\n", p.coef[p.degree] ); Polynomial read_poly() { int i; Polynomial p; printf(" 다항식의최고차수를입력하시오 : "); scanf( "%d", &p.degree ); printf(" 각항의계수를입력하시오 ( 총 %d 개 ): ", p.degree+1); for( i=0 ; i<=p.degree ; i++) scanf( "%f", p.coef+i ); return p; 17/20
다항식의덧셈연산 다항식덧셈알고리즘? 단순화방법? c=a+b c = a; c += b; Polynomial add_poly(polynomial a, Polynomial b) { int i; Polynomial p; if (a.degree > b.degree) { p = a; for( i=0 ; i<=b.degree ; i++ ) p.coef[i+(p.degree-b.degree)] += b.coef[i]; else { p = b; for( i=0 ; i<=a.degree ; i++ ) p.coef[i+(p.degree-a.degree)] += a.coef[i]; return p; 18/20
다항식프로그램 void main() { Polynomial a, b, c; a = read_poly(); b = read_poly(); c = add_poly (a, b); print_poly(a," A = "); print_poly(b," B = "); print_poly(c,"a+b= "); 19/20
희소다항식의표현 희소다항식 (Sparse Polynomial) 이란? 대부분항의계수가 0 인다항식 Polynomial: [0] [1] [2] [3] [4] [5]... [98] [99] [100] coef 10 0 0 0 0 0... 0 0 6... SparsePoly: expo coef Term 100 0 10 6 [0] [1] [2] [3] [4] [5] [6] typedef struct { int Term SparsePoly; nterms; term[max_terms]; typedef struct { int float Term; expon; coef; 20/20