5 순차 자료구조 방식.

Presentation on theme: "5 순차 자료구조 방식."— Presentation transcript:

1 5 순차 자료구조 방식

2 이 장에서 다룰 내용 선형 리스트 1 선형 리스트의 구현 2 다항식의 순차 자료구조 표현 3 행렬의 순차 자료구조 표현 4

3 선형 리스트 리스트(List) 자료를 나열한 목록 리스트의 예

4 선형 리스트 선형 리스트(Linear List) 순서 리스트(Ordered List) 자료들 간에 순서를 갖는 리스트
선형 리스트의 예

5 선형 리스트 리스트의 표현 형식 선형 리스트에서 원소를 나열한 순서는 원소들의 순서가 된다.
[표 5-2]의 동창이름 선형 리스트의 표현 동창 = (홍길동, 이순신, 윤봉길, 안중근) 공백 리스트 원소가 하나도 없는 리스트 빈괄호를 사용하여 표현

6 선형 리스트 선형 리스트의 저장 원소들의 논리적 순서와 같은 순서로 메모리에 저장 순차 자료구조
원소들의 논리적 순서 = 원소들이 저장된 물리적 순서 [표 5-2]의 동창 선형 리스트가 메모리에 저장된 물리적 구조

7 선형 리스트 순차 자료구조의 원소 위치 계산 선형 리스트가 저장된 시작 위치 : α 원소의 길이 : ℓ
원소의 길이 : ℓ i번째 원소의 위치 = α + (i-1)ⅹℓ

8 선형 리스트 선형 리스트에서의 원소 삽입 선형리스트 중간에 원소가 삽입되면, 그 이후의 원소들은 한자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시킨다.

9 선형 리스트 원소 삽입 방법 삽입할 자리를 만들기 위한 자리이동 횟수 원소를 삽입할 빈 자리 만들기
☞ 삽입할 자리 이후의 원소들을 한자리씩 뒤로 자리 이동 시키기 준비한 빈 자리에 원소 삽입하기 삽입할 자리를 만들기 위한 자리이동 횟수 (n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리에 원소를 삽입하는 경우 : k번 원소부터 마지막 n번 원소까지 (n-k+1)개의 원소를 이동 이동횟수 = n-k+1 = 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 +1

10 선형 리스트 선형 리스트에서의 원소 삭제 선형리스트 중간에서 원소가 삭제되면, 그 이후의 원소들은 한자리씩 자리를 앞으로 이동하여 물리적 순서를 논리적 순서와 일치시킴

11 선형 리스트 원소 삭제 방법 삭제 후, 빈 자리를 채우기 위한 자리이동 횟수 원소 삭제하기 삭제한 빈 자리 채우기
☞ 삭제한 자리 이후의 원소들을 한자리씩 앞으로 자리 이동시키기 삭제 후, 빈 자리를 채우기 위한 자리이동 횟수 (n+1)개 원소로 이루어진 선형 리스트에서 k번 자리의 원소를 삭제한 경우 (k+1)번 원소부터 마지막 n번 원소까지 (n-(k+1)+1)개의 원소를 이동 이동횟수 = n-(k+1)+1 = n-k = 마지막 원소의 인덱스-삭제한 자리의 인덱스

12 선형 리스트의 구현 선형 리스트의 구현 순차 구조의 배열을 사용 배열 - <인덱스, 원소>의 순서쌍의 집합
배열의 인덱스 – 배열 원소의 순서

13 선형 리스트의 구현 1차원 배열을 이용한 선형 리스트의 구현 예: 분기별 노트북 판매량 1차원 배열을 이용한 구현
int sale[] = new int[] {157, 209, 251, 312}  논리적 구조  물리적 구조

14 선형 리스트의 구현 분기별 판매량 리스트 프로그램 실행 결과 01 class Ex5_1{
02 public static void main(String srgs[]){ 03 int sale[] = new int[]{157, 209, 251, 312}; 04 05 for(int i=0; i<4; i++) 06 System.out.printf("%d/4분기 : sale[%d]= %d %n", i+1, i, sale[i]); 07 } 08 } [예제 5-1]

15 선형 리스트의 구현 2차원 배열을 이용한 선형 리스트의 구현 예 : 2004~2005년 분기별 노트북 판매량
2차원 배열을 이용한 구현 int sale[][] = new int[][]{{63, 84, 140, 130}, {157, 209, 251, 312}};  논리적 구조

16 선형 리스트의 구현 2차원 배열의 물리적 저장 방법 2차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법 사용
행 우선 순서 방법(row major order) 2차원 배열의 첫 번째 인덱스인 행 번호를 기준으로 사용하는 방법 sale[0][0]=63, sale[0][1]=84, sale[0][2]=140, sale[0][3]=130, sale[1][0]=157, sale[1][1]=209, sale[1][2]=251, sale[1][3]=312 원소의 위치 계산 방법 : α + (iⅹnj + j)ⅹℓ 행의 개수가 ni이고 열의 개수가 nj인 2차원 배열 A[ni][nj]의 시작주소가 α이고 원소의 길이가 ℓ 일 때, i행 j열 원소 즉, A[i][j]의 위치 열 우선 순서 방법(column major order) 2차원 배열의 마지막 인덱스인 열 번호를 기준으로 사용하는 방법 sale[0][0]=63, sale[1][0]=157, sale[0][1]=84, sale[1][1]=209, sale[0][2]=140, sale[1][2]=251, sale[0][3]=130, sale[1][3]=312 원소의 위치 계산 방법 : α + (jⅹni + i)ⅹℓ

17 선형 리스트의 구현  물리적 구조

18 선형 리스트의 구현 2007, 2008년 분기별 판매량 선형 리스트 프로그램 01 class Ex5_2{
02 public static void main(String srgs[]){ 03 int sale[][] = new int[][]{{63, 84, 140, 130}, {157, 209, 251, 312}}; 05 06 for(int i=0; i<2; i++){ for(int j=0; j<4; j++) System.out.printf("%d/4분기 : sale[%d][%d]= %d %n", j+1, i, j, sale[i][j]); 10 System.out.println(); 11 } 12 } 13 } [예제 5-2]

19 선형 리스트의 구현 실행 결과

20 선형 리스트의 구현 3차원 배열을 이용한 선형 리스트의 구현 예 : 2004~2005년, 1팀과 2팀의 분기별 노트북 판매량

21 선형 리스트의 구현 3차원 배열을 이용한 구현 int sale[][][] = new int [][][]{{{63, 84, 140, 130},                       {157, 209, 251, 312}},                                          {{59, 80, 130, 135},                         {149, 187, 239, 310}}                    };  논리적 구조

22 선형 리스트의 구현 3차원 배열의 물리적 저장 방법 3차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법 사용
면 우선 순서 방법 3차원 배열의 첫 번째 인덱스인 면 번호를 기준으로 사용하는 방법 원소의 위치 계산 방법 : α + {(iⅹnjⅹnk) + (jⅹnk) + k}ⅹℓ 면의 개수가 ni이고 행의 개수가 nj이고, 열의 개수가 nk 인 3차원 배열 A[ni][nj][nk] 시작주소가 α이고 원소의 길이가 ℓ 일 때, i면 j행 k열 원소 즉, A[i][j][k]의 위치 열 우선 순서 방법 3차원 배열의 마지막 인덱스인 열 번호를 기준으로 사용하는 방법 원소의 위치 계산 방법 : α + {(kⅹnjⅹni) + (jⅹni) + i}ⅹℓ

23 선형 리스트의 구현  물리적 구조

24 선형 리스트의 구현 1, 2팀의 2007, 2008년 분기별 판매량 선형 리스트 프로그램 01 class Ex5_3{
02 public static void main(String srgs[]){ 03 int sale[][][] = new int [][][]{{{63, 84, 140, 130}, {157, 209, 251, 312}}, {{59, 80, 130, 135}, {149, 187, 239, 310}} }; 08 09 for(int i=0; i<2; i++){ System.out.printf("<< %d 팀 >> %n", i+1); for(int j=0; j<2; j++){ for(int k=0; k<4; k++) System.out.printf("%d/4분기 : sale[%d][%d][%d] = %d %n", k+1, i, j, k, sale[i][j][k]); System.out.println(" "); } [예제 5-3]

25 선형 리스트의 구현 실행결과 System.out.println(); 18 } 19 } 20 } [예제 5-3]

26 다항식의 순차 자료구조 구현 다항식 aXe 형식의 항들의 합으로 구성된 식 지수에 따라 내림차순으로 항을 나열
a : 계수(coefficient) X : 변수(variable) e : 지수(exponent) 지수에 따라 내림차순으로 항을 나열 다항식의 차수 : 가장 큰 지수 다항식 항의 최대 개수 = (차수 +1)개

27 다항식의 순차 자료구조 구현 다항식의 순차 자료형 ADT Polynomial
데이터 : 지수(ei)-계수(ai)의 순서쌍 <ei, ai>의 집합으로 표현된 다항식 p(x) = a0xe0 + a1xe1 + … + aixei + … + anxen (ei는 음이 아닌 정수) 연산 : p,p1,p2 ∈ Polynomial; a ∈ Coefficient; e ∈ Exponent; // p,p1,p2는 다항식이고, a는 계수, e는 지수를 나타낸다. zeroP( ) ∷= return polynomial p⒳=0; // 공백 다항식(p(x)= 0)을 만드는 연산 isZeroP(p) ∷= if (p) then false else return true; // 다항식 p가 0(공백 다항식)인지 아닌지 검사하여 0이면 true를 반환하는 연산 coef(p,e) ∷= if (<e,a> ∈ p) then return a else return 0; // 다항식 p에서 지수가 e인 항의 계수 a를 구하는 연산. 지수가 e인 항이 없으면 0 반환 maxExp(p) ∷= return max(p.Exponent); // 다항식 p에서 최대 지수를 구하는 연산 [ADT 5-1]

28 다항식의 순차 자료구조 구현 다항식의 순차 자료형
addTerm(p,a,e) ∷= if (e ∈ p.Exponent) then return error else return p after inserting the term <e,a>; // 다항식 p에 지수가 e인 항이 없는 경우에 새로운 항 <e,a>를 추가하는 연산 delTerm(p,e) ∷= if (e ∈ p.Exponent) then return p after removing the term <e,a> else return error; // 다항식 p에서 지수가 e인 항 <e,a>를 삭제하는 연산 multTerm(p,a,e) ∷= return (p * axe); // 다항식 p의 모든 항에 axe항을 곱하는 연산 addPoly(p1,p2) ∷= return (p1 + p2); // 두 다항식 p1과 p2의 합을 구하는 연산 multPoly(p1,p2) ∷= return (p1 * p2); // 두 다항식 p1과 p2의 곱을 구하는 연산 End Polynomial [ADT 5-1]

29 다항식의 순차 자료구조 구현 다항식의 표현 1차원 배열을 이용한 순차 자료구조 표현
각 항의 지수와 계수의 쌍에 대한 선형 리스트 예) A(x)=4x3+3x2+2 ☞ p1= ((3,4), (2,3), (0,2)) 1차원 배열을 이용한 순차 자료구조 표현 차수가 n인 다항식을 (n+1)개의 원소를 가지는 1차원 배열로 표현 배열 인덱스 i = 지수(n-i) 배열 인덱스 i의 원소 : 지수(n-i)항의 계수 저장 다항식에 포함되지 않은 지수의 항에 대한 원소에 0 저장

30 다항식의 순차 자료구조 구현 예) A(x)=4x3+3x2+ 2 의 순차 자료구조 표현 희소 다항식에 대한 1차원 배열 저장
예) B(x)=3x x + 4 차수가 1000이므로 크기가 1001인 배열을 사용하는데, 항이 3개 뿐이므로 배열의 원소 중에서 3개만 사용 ☞ 998개의 배열 원소에 대한 메모리 공간 낭비!

31 다항식의 순차 자료구조 구현 2차원 배열을 이용한 순차 자료구조 표현
다항식의 각 항에 대한 <지수, 계수>의 쌍을 2차원 배열에 저장 2차원 배열의 행의 개수 = 다항식의 항의 개수 2차원 배열의 열의 개수 = 2 예) B(x)=3x x + 4 의 2차원 배열 표현 1차원 배열을 사용하는 방법보다 메모리 사용 공간량 감소 ☞ 공간 복잡도 감소 ☞ 프로그램 성능 향상!

32 다항식의 순차 자료구조 구현 다항식의 덧셈 addPoly() addPoly(A, B)
// 주어진 두 다항식 A와 B를 더하여 결과 다항식 C를 반환하는 알고리즘 C ← zeroP(); while (not isZeroP(A) and not isZeroP(B)) do { case { maxExp(A) < maxExp(B) : C ← addTerm(C, coef(B, maxExp(B)), maxExp(B)); B ← delTerm(B, maxExp(B)); maxExp(A) = maxExp(B) : sum ← coef(A, maxExp(A)) + coef(B, maxExp(B)); if (sum≠0) then C ← addTerm(C, sum, maxExp(A)); A ← delTerm(A, maxExp(A)); maxExp(A) > maxExp(B) : C ← addTerm(C, coef(A, maxExp(A)), maxExp(A)); } [알고리즘 5-1]

33 다항식의 순차 자료구조 구현 다항식의 덧셈 addPoly()
if (not isZeroP(A)) then A의 나머지 항들을 C에 복사 else if (not isZeroP(B)) then B의 나머지 항들을 C에 복사 return C; End addPoly() [알고리즘 5-1]

34 다항식의 순차 자료구조 구현 다항식의 덧셈 프로그램 01 public class Ex5_4{
02 public static void main(String args[]){ 03 float a[]= new float[] {4,3,5,0}; 04 float b[]= new float[] {3,1,0,2,1}; 05 Polynomial A = new Polynomial(3, a); 06 Polynomial B = new Polynomial(4, b); 07 OperatePoly optPoly = new OperatePoly(); 08 Polynomial C = optPoly.addPoly(A,B); 09 System.out.printf("A(x)="); A.printPoly(); 10 System.out.printf("B(x)="); B.printPoly(); 11 System.out.printf("C(x)="); C.printPoly(); 12 } 13 } 14 15 class OperatePoly{ 16 private int degree_A=0, degree_B=0, degree_C=0, index_A=0,index_B=0, index_C=0; [예제 5-4]

35 다항식의 순차 자료구조 구현 17 private int expo_A, expo_B;
18 private float coef_A, coef_B, coef_C; 19 20 public Polynomial addPoly(Polynomial A, Polynomial B){ 21 degree_A = A.getDegree(); 22 degree_B = B.getDegree(); 23 expo_A = degree_A; 24 expo_B = degree_B; 25 if(degree_A >= degree_B) degree_C=degree_A; 26 else degree_C=degree_B; 27 Polynomial C = new Polynomial(degree_C); 28 while(index_A <= degree_A && index_B <= degree_B){ if(expo_A > expo_B){ C.setCoef(index_C++, A.getCoef(index_A++)); expo_A--; 32 } else if(expo_A == expo_B){ C.setCoef(index_C++, A.getCoef(index_A++) B.getCoef(Index_B++)); [예제 5-4]

36 다항식의 순차 자료구조 구현 35 expo_A--; expo_B--; 36 } 37 else {
} else { C.setCoef(index_C++, B.getCoef(index_B++)); expo_B--; } 41 } 42 return C; 43 } 44 } 45 46 class Polynomial{ 47 private int degree; 48 private float coef[]=new float[20]; 49 50 Polynomial (int degree, float coef[]){ 51 this.degree = degree; 52 this.coef = coef; 53 } [예제 5-4]

37 다항식의 순차 자료구조 구현 54 Polynomial (int degree){ 55 this.degree = degree;
56 for(int i=0; i<=degree; i++) 57 this.coef[i] = 0; 58 } 59 public int getDegree(){ 60 return this.degree; 61 } 62 public float getCoef(int i){ 63 return this.coef[i]; 64 } 65 public float setCoef(int i, float coef){ 66 return this.coef[i]=coef; 67 } 68 public void printPoly(){ 69 int temp= this.degree; 70 for(int i=0; i<=this.degree; i++){ System.out.printf("%3.0fx^%d", this.coef[i], temp--); 72 } [예제 5-4]

38 다항식의 순차 자료구조 구현 73 74 System.out.println(); 75 } 76 } [예제 5-4]

39 다항식의 덧셈 – 프로그램 실행결과 실행 결과 A(x) = 4x3 + 3x2 + 5x
B(x) = 3x4 + x3 + 2x + 1 C(x) = A(x) + B(x) = 3x4 + 5x3 + 3x2 + 7x + 1

40 행렬의 순차 자료구조 표현 행렬(matrix) m x n 행렬 m : 행의 개수 n : 열의 개수

41 행렬의 순차 자료구조 표현 전치 행렬 행렬의 행과 열을 서로 교환하여 구성한 행렬
행렬 A의 모든 원소의 위치(i, j)를  (j, i)로 교환 m×n 행렬을 n×m 행렬로 변환한 행렬 A’는 행렬 A의 전치행렬 예)

42 행렬의 순차 자료구조 표현 행렬의 순차 자료구조 표현 2차원 배열 사용 m×n행렬을 m행 n열의 2차원 배열로 표현 예)

43 행렬의 순차 자료구조 표현 희소 행렬에 대한 2차원 배열 표현
[그림 5-17]의 희소 행렬 B는 배열의 원소 56개 중에서 실제 사용하는 것은 0이 아닌 원소를 저장하는 10개 뿐이므로 46개의메모리 공간 낭비 희소 행렬인 경우에는 0이 아닌 원소만 추출하여 <행번호, 열번호, 원소> 쌍으로 배열에 저장 [0] [1] [2] [3] [4] [5] [6] 2 12 7 23 31 14 25 6 52 [7] 11 <0, 2, 2> <0, 6, 12> <1, 4, 7> <2, 0, 23> <3, 3, 31> <4, 1, 14> <4, 5, 25> <5, 6, 6> <6, 0, 52> <7, 4, 11> B [8][7]

44 행렬의 순차 자료구조 표현 추출한 순서쌍을 2차원 배열의 행으로 저장
원래의 행렬에 대한 정보를 순서쌍으로 작성하여 0번 행에 저장 <전체 행의 개수, 전체 열의 개수, 0이 아닌 원소의 개수>

45 행렬의 순차 자료구조 표현 희소행렬의 추상 자료형 ADT SparseMatrix
데이터 : 3원소쌍 <행 인덱스, 열 인덱스, 원소 값>의 집합 연산 : a,b∈SparseMatrix; c∈Matrix; u,v∈value; i∈Row; j∈Column; // a와 b는 희소행렬, c는 행렬, u와 v는 행렬의 원소값을 나타내며, i와 j는 행 인덱스와 열 인덱스를 나타낸다. createSM(m,n) ∷= return an empty sparse matrix with m×n; // m×n의 공백 희소행렬을 만드는 연산 transposeSM(a) ∷= return c where c[j,i]=v when a[i,j]=v; // a[i,j]=v를 c[j,i]=v로 전치시킨, 전치행렬 c를 구하는 연산 addSM(a,b) ∷= if (a.dimension = b.dimension) then return c where c[i,j]=v+u where a[i,j]=v and b[i,j]=u else return error; // 차수가 같은 희소행렬 a와 b를 합한 행렬 c를 구하는 연산 multiSM(a,b) ∷= if (a.n = b.m) then return c where c[i,j]=a[i,k]× b[k,j]; // 희소행렬 a의 열의 개수(n)와 희소행렬 b의 행의 개수(m)가 같은 경우에 두 행렬의 곱을 구하는 연산 End SparseMatrix [ADT 5-2]

46 행렬의 순차 자료구조 표현 희소행렬의 전치 연산 transposeSM() transposeSM(a[])
m ← a[0,0]; // 희소행렬 a의 행 수 n ← a[0,1]; // 희소행렬 a의 열 수 v ← a[0,2]; // 희소행렬 a에서 0이 아닌 원소 수 b[0,0] ← n; // 전치행렬 b의 행 수 지정 b[0,1] ← m; // 전치행렬 b의 열 수 지정 b[0,2] ← v; // 전치행렬 b의 0이 아닌 원소 수 지정 if (v > 0) then { // 0이 아닌 원소가 있는 경우에만 전치 연산 수행 p ← 1; for (i←0; i < n; i←i+1) do { // 희소행렬 a의 열별로 전치 반복 수행 for (j←1; j <= v; j←j+1) do { // 0이 아닌 원소 수에 대해서만 반복 수행 if (a[j,1]=i) then { // 현재의 열에 속하는 원소가 있으면 b[]에 삽입 b[p,0] ← a[j,1]; b[p,1] ← a[j,0]; b[p,2] ← a[j,2]; p ← p+1; } return b[]; End transposeSM() [알고리즘 5-2]