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

Presentation on theme: "자료 구조: Chapter 3 배열(1) 2017. 3. 23 순천향대학교 컴퓨터공학과 하 상 호."— 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 [1..maxdegree] of real; // 계수들을 순차적으로 저장 end;

8 poly_add() 예제 p=8x3+7x+1, q=10x3+3x2+1 p, q의 표현은?
p, q의 덧셈 결과 다항식을 r이라 할 때, r은?

9 poly_add() 예제 p1=2x4 +8x3+7x+1, p2=10x3+3x2 p, q의 표현은?
p, q의 덧셈 결과 다항식을 r이라 할 때, r은?

10 poly_add(): 알고리즘 알고리즘 type poly = record degree: integer;
coef: array of [1..maxdegree] of real; end; procedure poly_add(p, q: poly) // 동일 차수의 항을 순서대로 가져와서 더한다 end poly_add

11 poly_add(): 알고리즘 알고리즘 type poly = record degree: integer;
coef: array of [1..maxdegree] of real; end; procedure poly_add(p, q: poly) : poly r: poly; r.degree <- max(p.degree, q.degree); // r의 차수 설정 dp <- p.degree; dq<- q.degree // p, q의 현재 차수 설정 ip <- 0; iq<- 0; ir <-0; // p, q의 현재 인덱스 설정 while dp >= 0 and dq >= 0 do // 검사할 항이 남아 있으면 if dp = dq then r.coef[rf] <- p.coef[pf] + q.coef[qf]; ir++; ip++; iq++; // 인덱스 갱신 dp <- dp – 1; dq <- dq -1; // 차수 갱신 else if dp > dq then r.coef[rf] <- p.coef[pf]; ir++, ip++; dp <- dp – 1; else r.coef[rf] <- q.coef[qf]; ir++, iq++; dq <- dq – 1; end if repeat return r end poly_add 알고리즘

12 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;

13 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;

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

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

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

17 다항식 표현 방법 #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

18 다항식 표현 방법 #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

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

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

21 poly_add2() 예제 p=8x3+7x+1, q=10x3+3x2+1 p, q의 표현은?
type poly = record terms: array [1..maxterms] of term_type; num: integer; end; type term_type = record coef: real; expo: integer; poly_add2() 예제 p=8x3+7x+1, q=10x3+3x2+1 p, q의 표현은? p, q의 덧셈 결과 다항식을 r이라 할 때, r은?

22 poly_add2() 예제 p1=2x4 +8x3+7x+1, p2=10x3+3x2 p, q의 표현은?
type poly = record terms: array [1..maxterms] of term_type; num: integer; end; type term_type = record coef: real; expo: integer; poly_add2() 예제 p1=2x4 +8x3+7x+1, p2=10x3+3x2 p, q의 표현은? p, q의 덧셈 결과 다항식을 r이라 할 때, r은?

23 poly_add2(): 알고리즘 알고리즘 type poly = record
terms: array [1..maxterms] of term_type; num: integer; end; type term_type = record coef: real; expo: integer; 알고리즘 procedure poly_add2(p, q: poly): poly r: poly; // p, q의 항(계수,차수)을 순서대로 한 개씩 가져와서 적절하게 덧셈 수행 // 차수가 동일한 항만을 더함 end poly_add2

24 poly_add2(): 알고리즘 알고리즘 procedure poly_add2(p, q: poly) : poly r: poly;
ip <- 0; iq<- 0; ir <-0; // 다항식의 현재 항 인덱스 설정 while ip < p.num and iq < q.num do if p.terms[ip].expo = q.terms[iq].expo then r.terms[ir].coef <- p.terms[ip].coef + q.terms[iq].coef; r.terms[ir].expo <- p.terms[ip].expo; ir++; ip++; iq++; // 인덱스 갱신 else if p.terms[ip].expo > q.terms[iq].expo then r.terms[ir].coef <- p.terms[ip].coef; ir++; ip++; else r.terms[ir].coef <- p.terms[iq].coef; r.terms[ir].expo <- p.terms[iq].expo; ir++; iq++; end if repeat // 어느 한 쪽이 먼저 소진된 경우 처리 if ip < p.num then // p의 나머지 항들을 r로 이동 // q의 나머지 항들을 r로 이동 endif end poly_add2 알고리즘 type poly = record terms: array [1..maxterms] of term_type; num: integer; end; type term_type = coef: real; expo: integer;

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

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

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

28 프로그램: 희소행렬 표현 #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;

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

30 희소행렬 덧셈 알고리즘 #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; procedure sparse_matrix_add2(p, q: sparse_matrix) : sparse_matrix // p, q의 행, 열의 크기가 동일한지 검사 // p, q의 각 항을 순서대로 가져와서 동일 인덱스인지 검사하여 덧셈 수행 end sparse_matrix_add2