4장. 순차자료구조

Size: px

Start display at page:

Download "4장. 순차자료구조"

호경 한
5 years ago
Views:

1 순차자료구조방식 자바로배우는쉬운자료구조

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

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

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

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

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

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

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

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

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

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

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

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

$선형리스트의구현 (3) 분기별판매량리스트프로그램 01 class Ex5_1{ 02 public static void main(string srgs[]){ 03 int sale[] = new int[]{157, 209, 251,$

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

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

16 선형리스트의구현 (5) 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ⅹn j + j)ⅹl» 행의개수가 n i 이고열의개수가 n j 인 2차원배열 A[n i ][n j ] 의시작주소가 α이고원소의길이가 l 일때, 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ⅹn i + i)ⅹl 16

17 선형리스트의구현 (6) 물리적구조 17

$선형리스트의구현 (7) 2007, 2008 년분기별판매량선형리스트프로그램 01 class Ex5_2{ 02 public static void main(string srgs[]){ 03 int sale[][] = new int[][]{{63, 84, 140, 130}, 04 {157, 209, 251, 312}}; 05$

18 선형리스트의구현 (7) 2007, 2008 년분기별판매량선형리스트프로그램 01 class Ex5_2{ 02 public static void main(string srgs[]){ 03 int sale[][] = new int[][]{{63, 84, 140, 130}, 04 {157, 209, 251, 312}}; for(int i=0; i<2; i++){ 07 for(int j=0; j<4; j++) 08 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] 18

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

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

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

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

23 선형리스트의구현 (12) 물리적구조 23

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

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

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

27 다항식의순차자료구조구현 (2) 다항식의추상자료형 (1) ADT Polynomial [ADT 5-1] 데이터 : 지수 (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에서최대지수를구하는연산 27

28 다항식의순차자료구조구현 (3) 다항식의추상자료형 (2) addterm(p,a,e) = if (e p.exponent) then return error [ADT 5-1] 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 28

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

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

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

32 다항식의순차자료구조구현 (7) 다항식의덧셈 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)); B delterm(b, maxexp(b)); maxexp(a) > maxexp(b) : C addterm(c, coef(a, maxexp(a)), maxexp(a)); A delterm(a, maxexp(a)); } } [ 알고리즘 5-1] 32

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

34 다항식의순차자료구조구현 (9) 다항식의덧셈프로그램 01 public class Ex5_4{ [ 예제 5-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 } class OperatePoly{ 16 private int degree_a=0, degree_b=0, degree_c=0, index_a=0,index_b=0, index_c=0; 34

35 다항식의순차자료구조구현 (10) 17 private int expo_a, expo_b; 18 private float coef_a, coef_b, coef_c; 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){ 29 if(expo_a > expo_b){ 30 C.setCoef(index_C++, A.getCoef(index_A++)); 31 expo_a--; 32 } 33 else if(expo_a == expo_b){ 34 C.setCoef(index_C++, A.getCoef(index_A++)+ B.getCoef(Index_B++)); [ 예제 5-4] 35

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

37 다항식의순차자료구조구현 (12) 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++){ 71 System.out.printf("%3.0fx^%d", this.coef[i], temp--); 72 } [ 예제 5-4] 37

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

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

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

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

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

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

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

45 행렬의순차자료구조표현 (6) 희소행렬의추상자료형 ADT SparseMatrix 데이터 : 3 원소쌍 < 행인덱스, 열인덱스, 원소값 > 의집합 [ADT 5-2] 연산 : 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]; else return error; // 희소행렬 a 의열의개수 (n) 와희소행렬 b 의행의개수 (m) 가같은경우에두행렬의곱을구하는연산 End SparseMatrix 45

46 행렬의순차자료구조표현 (7) 희소행렬의전치연산 transposesm() transposesm(a[]) [ 알고리즘 5-2] 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() 46

47 자바로배우는쉬운자료구조 5 장끝

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 System Software Experiment 1 Lecture 5 - Array Spring 2019 Hwansoo Han (hhan@skku.edu) Advanced Research on Compilers and Systems, ARCS LAB Sungkyunkwan University http://arcs.skku.edu/ 1 배열 (Array) 동일한타입의데이터가여러개저장되어있는저장장소