제 2 장 : 배열과 구조 이 형 원 강릉대학교 컴퓨터공학과 자료 구조 제 2 장 : 배열과 구조 이 형 원 강릉대학교 컴퓨터공학과

학습 내용 배열과 구조체의 정의 및 C 언어에서의 표현 배열과 구조체를 이용한 예제 다양한 정방 행렬과 배열 표현 다항식 희소 행렬 다양한 정방 행렬과 배열 표현

배열 ADT 배열 Structure Array i) 일련의 연속적인 메모리 위치  구현 측면 ii) <index, value> 쌍으로 구성된 집합 Structure Array objects: index의 각 값에 대해 집합 item에 속한 한 값이 있는 <index,value>쌍의 집합. index는 일차원 or 다차원의 유한 순서 집합. functions: A Array, i index, x item, j, size integer Array Create(j,list) ::= return j차원의 배열. Item Retrieve(A, i) ::= if (iindex) return 배열 A의 인덱스 i와 관련된 항목 else return 에러. Array Store(A,i,x) ::= if (iindex) return 새로운 쌍<i,x>가 삽입된 배열 A else return 에러. end Array

C에서의 일차원 배열 int list[5], *plist[5]; 배열이 함수의 매개 변수로 사용되는 경우 5 개의 연속적인 메모리 장소 할당 list[i]: 정수, plist[i]: 정수로의 포인터 addrlist[i] = addrlist[0] + i*sizeof(int) list = list[0]를 가리키는 포인터 list + i = list[i]를 가리키는 포인터 (list+i) = &list[i], *(list+i) = list[i] 배열이 함수의 매개 변수로 사용되는 경우 일차원 배열의 범위는 주프로그램에서만 정의 Q. 배열의 크기가 부프로그램에서 필요하다면 ? call-by-value를 이용한 call-by-reference 효과

배열 프로그램의 예 #define MAX_SIZE 100 float sum(float [], int); float input[MAX_SIZE], answer; int i; void main(void) { float sum(float list[], int n) { for (i = 0; i < MAX_SIZE; i++) float tempsum = 0; input[i] = i; for (i = 0; i < n; i++) answer = sum(input, MAX_SIZE); tempsum += list[i]; printf("The sum is: %f", answer); return tempsum; } } 호출시 input(=&input[0])은 임시 장소에 복사되고 formal parameter list와 연관됨

구조 : struct type이 다른 데이타를 그룹화(레코드) 항목은 타입과 이름으로 식별 struct { char name[10]; int age ; float salary; } person; typedef 문장을 사용한 구조 데이타 타입 생성 typedef struct human_being { typedef struct { char name[10]; char name[10]; int age; 또는 int age; float salary; float salary; }; } human_being ; 변수 선언 : human_being person1, person2 ;

구조 : struct(계속) 구조 속의 또다른 구조 정의 typedef struct { typedef struct human_being { int month; char name[10]; int day; int age; int year; float salary; } date ; date dob; } ; [예] person1.dob.month = 2; person1.dob.day = 11; person1.dob.year = 1944;

유니언 union의 필드들은 메모리 공간을 공용 한 필드만 어느 한 시점에 활동적이 되어 사용 가능 값 할당 typedef struct sex_type { typedef struct human_being { enum tag {female, male} sex; char name[10]; union { int age; int children; float salary; int beard; date dob; } u ; sex_type sex_info; } ; }; 값 할당 human_being person1, person2; person1.sex_info.sex = male; person1.sex_info.u.beard = FALSE; person2.sex_info.sex = female; person2.sex_info.u.children = 4;

자체 참조 구조 구성요소 중 자신을 가리키는 포인터가 있는 구조 동적 기억장소 관리 루틴(malloc, free)이 필요 typedef struct list { char data; list *link; } ; list item1, item2, item3; item1.data = 'a'; item2.data = 'b'; item3.data = 'c'; item1.link = item2.link = item3.link = NULL; item1.link = &item2; item2.link = &item3;

순서 리스트 순서 리스트(ordered list, linear list) 원소들의 순서가 있는 모임 : (a0, a1, ..., an-1) 예) Days-of-week : (Mon, Tue, Wed, Thu, Fri, Sat, Sun) : list 1st 2nd 3rd 4th 5th 6th 7th : order 연산 ⅰ. length n ⅱ. reading (R L, L  R) ⅲ. retrieve i-th element, 0 ≤ i < n ⅳ. update i-th element's value, 0 ≤ i < n ⅴ. insertion (i번째 위치, 0 ≤ i ≤ n) : i, i+1, ..., n-1  i+1, i+2, ..., n ⅵ. deletion (i번째 항목, 0 ≤ i < n) : i+1, ..., n-1 i, i+1, ..., n-2 표현 순차적 사상(배열) 비순차적 사상(연결 리스트)

다항식 다항식의 기초 A(x)=anxn + an-1xn-1 + … + a1x1 + a0x0 각 항이 axe where a : 계수(coefficient) an  0 e : 지수(exponent) - unique x : 변수(variable) 차수(degree) : 다항식에서 가장 큰 지수 A(x) = aixi, B(x) = bixi A(x) + B(x) =  (ai + bi) xi A(x) B(x) =  (aixi  ( bjxj )) Q. 다항식과 순서 리스트와의 관계 ?

다항식: ADT Polynomial Objects : P(x) =a1xe1+…+anxen:<ei,ai>의 순서쌍 집합 (ei (≥0):정수) Functions : poly, poly1, poly2  다항식, coef  계수, expon  지수 Polynomial Zero() ::= return p(x) = 0 Boolean IsZero(poly) ::= if (poly) return FALSE else return TRUE Coefficient Coef(poly,expon) ::= if (exponpoly) return 계수 else return 0 Exponent Lead_Exp(poly) ::= return poly에서 제일 큰 지수 Polynomial Attach(poly, coef, expon) ::= if (expon poly) return 오류 else return <coef, exp>항이 삽입된 다항식 poly Polynomial Remove(poly, expon) ::= if (expon poly) return 지수가 expon인 항이 삭제된 다항식 poly else return 오류 Polynomial SingleMult(poly,coef,expon) ::= return 다항식 poly coef xexpon Polynomial Add(poly1, poly2) ::= return 다항식 poly1 + poly2 Polynomial Mult(poly1, poly2) ::= return 다항식 poly1 * poly2

다항식: 함수 padd /* 다항식 d=a+b (다항식 표현에 독립) */ d = Zero(); while (! IsZero(a) && ! IsZero(b)) do { switch COMPARE(Lead_Exp(a), Lead_Exp(b)) { case -1: d = Attach(d, Coef(b, Lead_Exp(b)), Lead_Exp(b)); b = Remove(b, Lead_Exp(b)); break; case 0 : sum = Coef(a, Lead_Exp(a)) + Coef(b, Lead_Exp(b)); if (sum) { Attach(d, sum, Lead_Exp(a)); a = Remove(a, Lead_Exp(a)); b = Remove(b, Lead_Exp(b)); } break; case 1 : d = Attach(d, Coef(a, Lead_Exp(a)), Lead_Exp(a)); a = Remove(a, Lead_Exp(a)); } } a 또는 b의 나머지 항을 d에 삽입한다.

다항식: 표현 방법 다항식의 표현 방법 (I) #define MAX_DEGREE 101 /* 다항식의 최대 차수 + 1 */ typedef struct { int degree; float coef[MAX_DEGREE]; } polynomial; 예) x4+10x3+3x2+1를 polynomial type a에 저장 a.degree = 4 a.coef 1 10 3 0 1 ….. 단점 : 기억 장소의 낭비 가능성 Q. when ?

다항식: 표현 방법(계속) 다항식의 표현 방법 (II) typedef struct { float coef; int expon; } polynomial; polynomial terms[MAX_TERMS]; 예) A(x)=2x1000+1, B(x)=x4+10x3+3x2+1를 배열 terms에 저장 starta finisha startb finishb avail coef 2 1 1 10 3 1 exp 1000 0 4 3 2 0 장점: sparse polynomial의 경우 기억 장소 문제 해결 terms안에 저장될 다항식의 수에 제한이 없음 단점: 최악의 경우, (I) 보다 2배의 기억장소 Q. when ?

다항식: 알고리즘 padd void padd(int starta, int finisha, int startb, int finishb, int *startd, int *finishd) { float coefficient; *startd = avail; while (starta <= finisha && startb <= finishb) switch (COMPARE(terms[starta].expon, terms[startb].expon)) case -1: attach(terms[startb].coef, terms[startb].expon); startb++; break; case 0: coefficient = terms[starta].coef + terms[startb].coef; if (coefficient) attach(coefficient, terms[starta].expon); starta++; startb++; break; case 1: attach(terms[starta].coef, terms[starta].expon); starta++; for(; starta <= finisha; starta++) attach(terms[starta].coef,terms[starta].expon); for(; startb <= finishb; startb++) attach(terms[startb].coef, terms[startb].expon); *finishd = avail-1; }

다항식: 알고리즘 padd(계속) padd의 분석 (m,n: A와 B의 0이 아닌 항의 수) 시간 복잡도 void attach(float coefficient, int exponent) { /* 새 항을 다항식에 첨가 */ if (avail >= MAX_TERMS) { fprintf(stderr, "다항식에 항이 너무 많다."); exit(1); } terms[avail].coef = coefficient; terms[avail++].expon = exponent; } padd의 분석 (m,n: A와 B의 0이 아닌 항의 수) 시간 복잡도 while 루프 : 각 반복마다 starta나 startb 또는 둘 다 값이 증가 최대 반복 횟수 = m+n-1 Q.When ? for 루프 : O(m+n) 문제점 : avail = MAX_TERMS ? 불필요한 다항식 제거 후 배열 끝에 연속적인 가용공간 생성 데이타 이동시간, 각 다항식의 starti, finishi 변경

희소행렬의 표현 행렬의 표준 표현 희소 행렬의 표현 방법 2차원 배열 희소 행렬(sparse matrix)의 경우 기억 장소 낭비 희소 행렬의 표현 방법 store only the nonzero elements typedef struct { int col; int row ; int value ; } term; term a[MAX_TERMS]; 추가 고려 사항 행의 수, 열의 수, non-zero elements의 수, 순서 (열 우선 or 행 우선)

희소행렬의 표현(계속) 표준 표현 희소 행렬 표현 표준 표현 희소 행렬 표현 열0 열1 열2 열3 열4 열5 행 열 값 행0 15 0 0 22 0 -15 a[0] 6 6 8 행1 0 11 3 0 0 0 a[1] 0 0 15 행2 0 0 0 -6 0 0 a[2] 0 3 22 행3 0 0 0 0 0 0 a[3] 0 5 -15 행4 91 0 0 0 0 0 a[4] 1 1 11 행5 0 0 28 0 0 0 a[5] 1 2 3 a[6] 2 3 -6 a[7] 4 0 91 a[8] 5 2 28 a[0].row: 행수, a[0].col: 열수, a[0].value: 0이 아닌 항의 총수 행 우선 & 행 내에서는 열우선

행렬의 전치 ⑴ 일반적인 행렬 표현법 행렬 전치의 예 알고리즘  15 10 0   15 5 0   15 10 0   15 5 0   5 0 0  ==>  10 0 20   0 20 0   0 0 0  알고리즘 void normal_transpose(term a[], term b[], int columns, int rows) { /* a를 전치시켜 b에 저장 */ int i, j; for (j=0; j<columns; j++) for (i=0; i<rows; i++) b[j][i] = a[i][j]; } Q. 시간 복잡도 ?

행렬의 전치(계속) ⑵ 희소 행렬(행우선) 표현법 행 열 값 행 열 값 a[0] 6 6 8 b[0] 6 6 8 a[1] 0 0 15 b[1] 0 0 15 a[2] 0 3 22 b[2] 0 4 91 a[3] 0 5 -15 b[3] 1 1 11 a[4] 1 1 11 b[4] 2 1 3 a[5] 1 2 3 b[5] 2 5 28 a[6] 2 3 -6 b[6] 3 0 22 a[7] 4 0 91 b[7] 3 2 -6 a[8] 5 2 28 b[8] 5 0 -15 각 행 i에 대해서 <i,j,value><j,i,value> : 행 우선이 유지 X 각 열 j에 대해서 <i,j,value><j,i,value> : 행 우선이 유지됨

행렬의 전치(계속) void transpose(term a[], term b[]) { /* a를 전치시켜 b에 저장 */ int n, i, j, currentb; n=a[0].value; b[0].row=a[0].col; b[0].col=a[0].row; b[0].value=n; if (n > 0) { currentb = 1; for (i =0; i < a[0].col; i++) /* a에서 열별로 전치*/ for (j = 1; j <= n; j++) /* 현재 열로부터 원소를 찾는다. */ if (a[j].col == i) { /* 현재 열에 있는 원소를 b에 첨가 */ b[currentb].row = a[j].col; b[currentb].col = a[j].row; b[currentb].value = a[j].value; currentb++; } } } Q. 시간 복잡도 ?

행렬의 전치(계속) ⑶ 희소 행렬의 빠른 전치 void fast_transpose(term a[], term b[]) { /* a를 전치 b에 저장 */ int row_terms[MAX_COL], starting_pos[MAX_COL]; int i,j, num_col = a[0].col, num_terms = a[0].value; b[0].row = num_cols; b[0].col = a[0].row; b[0].value = num_terms; if (num_terms > 0) { for(i=0; i < num_cols; i++) row_terms[i] = 0; for(i = 1; i <= num_terms; i++) row_terms[a[i].col]++; starting_pos[0] = 1; for(i=1; i<num_cols; i++) starting_pos[i]=starting_pos[i-1]+row_terms[i-1]; for(i = 1; i <= num_terms; i++) { j = starting_pos[a[i].col]++; b[j].row = a[i].col; b[j].col = a[i].row; b[j].value = a[i].value; } } } Q. 시간 복잡도 ?

행렬 전치 알고리즘의 분석 시간 복잡도 Q. What can you say from these ? 희소 행렬 (원소 수 << columns*rows) ⑴ Ο(columns·rows) ⑵ Ο(columns·elements) ⑶ Ο(columns+elements) 희소 행렬이 아닌 경우 (원소 수  columns*rows) ⑴ Ο(columns·rows) ⑵ Ο(columns·elements) = Ο(columns2·rows) ⑶ Ο(columns+elements) = Ο(columns·rows) Q. What can you say from these ?

다양한 형태의 정방 행렬 대각 행렬(diagonal matrix) A[n][n] 0 x 0 0 A[i][j] = 0 if i  j 0 0 x 0 0 0 0 x 하삼각 행렬(lower triangular matrix) A[n][n] x x 0 0 A[i][j] = 0 if i < j x x x 0 x x x x

다양한 형태의 정방 행렬(계속) 상삼각 행렬(upper triangular matrix) A[n][n] x x x x 0 x x x A[i][j] = 0 if i > j 0 0 x x 0 0 0 x 3원 대각 행렬(tridiagonal matrix) A[n][n] x x 0 0 0 x x x 0 0 A[i][j] = 0 if |i - j| > 1 0 x x x 0 0 0 x x x 0 0 0 x x