자료 구조: Chapter 3 배열(1) 2016. 3. 29 순천향대학교 컴퓨터공학과 하 상 호.

Presentation on theme: "자료 구조: Chapter 3 배열(1) 2016. 3. 29 순천향대학교 컴퓨터공학과 하 상 호."— Presentation transcript:

1 자료 구조: Chapter 3 배열(1) 순천향대학교 컴퓨터공학과 하 상 호

2 3장 목차 행렬 구조체 포인터

3 배열이란? 동일한 데이터 타입의 자료를 다룰 때 유용 반복 구조를 이용한 효과적인 배열 조작
int A0, A1, A2, A3, …,A9; int A[10]; 1 2 3 4 5 6 7 8 9

4 배열 ADT 배열: <인덱스, 요소> 쌍들의 집합 인덱스가 주어지면 해당되는 요소가 대응되는 구조 배열 ADT
객체: <i ∈ Index, e ∈ Element> 쌍들의 집합 여기서 Index는 순서를 나타내는 원소의 유한 집합 Element는 타입이 동일한 원소들의 집합 연산:   ▪ create(n) ::= n개의 요소를 가진 배열의 생성.  ▪ retrieve(a, i) ::= if (i ∈ Index) then return e where <i,e> ∈a else return error  ▪ store(a, i, item) ::= if (i ∈ Index) then return (a ∪<i,item>)

5 배열의 응용: 다항식 다항식의 일반적인 형태 프로그램상에서 다항식을 어떻게 표현할 것인가? 다항식은 항들의 모임
각 항의 표현은?

6 다항식 표현 방법 #1 10 6 3 다항식을 배열에 표현 모든 차수에 대한 계수값을 배열에 저장
변수 degree상에 몇 차식인지 표현 coef 10 6 3 1 2 4 5 7 8 9 degree 이를 표현하기 위한 적절한 자료 구조는? 5

7 다항식 표현 방법 #1 10 6 3 C 프로그램에서 다항식 표현은? => 구조체 (degree, coef)로 coef 1
6 3 1 2 4 5 7 8 9 degree 5 type poly = record degree: integer; // 최고 차수 coef: array of [1..maxdegree] of real; // 계수들을 순차적으로 저장 end;

8 poly_add() 2개의 다항식을 더하는 poly_add()를 분석하라 구분 내용 I O P E
P1=8x3+7x+1, p2=10x3+3x => p3 = ? p1=2x4 +8x3+7x+1, p2=10x3+3x2+1 => p3 =?

9 poly_add(): 알고리즘 알고리즘 type poly = record degree: integer;
coef: array of [1..maxdegree] of real; end; procedure poly_add(p, q: poly) r: poly; r.degree <- max(p.degree, q.degree); dp <- p.degree; dq<- q.degree // 다항식 현재 차수 설정 pf <- 0; qf<- 0; rf <-0; // 다항식 배열의 현재 인덱스 설정 while dp >= 0 and dq >= 0 do repeat end poly_add 알고리즘

10 poly_add(): C 코드 다항식 표현 type poly = record degree: integer;
coef: array of [1..maxdegree] of real; end; typedef struct { int degree; float coef[MAX_DEGREE]; } poly;

11 poly_add(): C 코드 (프로그램 3.2)
polynonial polyAdd(polynomial A, polynomial B) { polynomial C; int Apos = Bpos = Cpos = 0; // 현재 배열 위치 int degree_a = A.degree, degree_b = B.degree; // 현재 차수 int C.degree = MAX(A.degree, B.degree); // 결과 다항식 차수 while ( Apos<=A.degree && Bpos<=B.degree ) { if( degree_a > degree_b ) { C.coef[Cpos++]= A.coef[Apos++]; degree_a--; } else if( degree_a == degree_b ){ C.coef[Cpos++]=A.coef[Apos++]+B.coef[Bpos++]; degree_a--; degree_b--; else { C.coef[Cpos++]= B.coef[Bpos++]; degree_b--; return C;

12 다항식 표현 방법 #1 평가 장점: 다항식의 연산이 간단 단점: 대부분의 항의 계수가 0이면 공간의 낭비가 심함.
Ex 다음 다항식을 표현하면? 10x100+6

13 다항식 표현 방법 #2 다항식에서 0이 아닌 항만을 배열에 저장하면?

14 다항식 표현 방법 #2 다항식에서 항의 정보 (계수, 차수)를 배열에 저장 Ex. 10x5+6x+3 10x100+6

15 다항식 표현 방법 #2 하나의 배열에 여러 개의 다항식을 표현하는 것이 가능 3 8 1 7 10 2 4 5 6 9 A B
10 2 4 5 6 9 A B avail coef expon terms

16 다항식 표현 방법 #2(계속) 다항식의 연산은? (예) 다항식의 덧셈: A=8x3+7x+1, B=10x3+3x2+1 => C=A+B 3 8 1 7 10 2 4 5 6 9 A B avail coef expon 18 C

17 다항식 연산 #2: 덧셈 덧셈 알고리즘 A, B의 다항식을 더하여 다항식 C를 구한다고 가정 (A, B의 각 항들은 (차수, 계수)로 표현되고, 높은 차수부터 저장되어 있음) 순서대로 A, B의 각 항의 지수를 비교하여 두 지수가 같으면 A, B의 해당 항의 계수를 더하여 C로 이동 두 지수가 다르면, 지수가 큰 항을 C로 이동 어느 한쪽의 다항식의 항이 모두 소진되면 다른 다항식에 남아 있는 모든 항들을 C로 이동 Ex. A=2x4 +8x3+7x+1, B=10x3+3x2+1

18 poly_add2() 2개의 다항식을 더하는 poly_add2()를 분석하라 구분 내용 I O P E
P1=8x3+7x+1, p2=10x3+3x => p3 = ? p1=2x4 +8x3+7x+1, p2=10x3+3x2+1 => p3 =?

19 poly_add2() 2개의 타입 poly, term_type 정의 type poly = record
terms: array of [1..maxterms] of term_type; // 항의 정보 num: integer; // 항의 개수 end; type term_type = record coef: real; // 계수 expo: integer; // 차수

20 poly_add2(): 알고리즘 알고리즘 procedure poly_add2(p, q: poly) r: poly;
pf <- 0; qf<- 0; rf <-0; // 다항식의 현재 항 인덱스 설정 while pf <= p.num and qf <= q.num do repeat // 어느 한 쪽이 먼저 소진된 경우 처리 if pf <= p.num then // p의 나머지 항들을 r로 이동 else // q의 나머지 항들을 r로 이동 endif end poly_add2 알고리즘

21 poly_add2(): C 코드 다항식 표현 type poly = record
terms: array of [1..maxterms] of term_type; integer num; end; type term_type = record coef: real; expo: integer; typedef struct { float coef; int expon; } term_type; term_type terms[MAX_TERMS]; int num; } poly;

22 void poly_add2(int As, int Ae, int Bs, int Be, int *Cs, int *Ce)
{ // As, Ae는 다항식 A의 시작과 끝 위치; Bs, Be는 다항식 B의 시작과 끝 위치 float tempcoef; *Cs = avail; // avile은 전역변수, 결과 다항식 배치 위치 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 != 0) attach(tempcoef, terms[As].expon); As++; Bs++; break; case '<': // A의 차수 < B의 차수 attach(terms[Bs].coef, terms[Bs].expon); Bs++; break; } if (As <= Ae) then // B의 항이 모두 소진; A의 나머지 항들을 이동 for(;As<=Ae;As++) else for(;Bs<=Be;Bs++) *Ce = avail -1; void attach(float coef, int expon) { if (avail > MAX_TERMS) then error; terms[avail].coef = coef; terms[avail++].expon = expon; }

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

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

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

26 프로그램: 희소행렬 표현 #define MAX_TERMS 10 typedef struct { // 행렬 원소 표현
int row; int col; int value; } element; typedef struct sparse_matrix { // 희소 행렬 표현 element data[MAX_TERMS]; int rows; // 행의 크기 int cols; // 열의 크기 int terms; // 0이 아닌 항의 개수 } sparse_matrix;

27 희소행렬 표현방법 #2 2개의 희소 행렬 A, B를 더하여 C에 할당하는 프로그램 고려(A, B의 각 요소들은 (행, 열, 값)으로 표현되고, 인덱스(=행*열크기+열)가 앞선 순으로 저장되어 있음) 다항식의 항들을 더하는 것과 유사 A, B의 두 요소의 인덱스가 같으면 두 요소의 값을 더하여 C로 이동 인덱스가 서로 다르면, 앞선 인덱스를 갖는 요소를 C로 이동 어느 한쪽 행렬 요소가 소진되면, 다른 행렬의 나머지 요소들을 C로 이동