[ 자료구조 및 알고리즘 ] 4. 순차 자료구조 - 2. 선형 리스트의 구현

1차원 배열을 이용한 선형 리스트의 구현 

[표4-3]분기별 노트북 판매량 리스트

1차원 배열을 이용한 구현

• int sale[] = new int[] {157, 209, 251, 312};

논리적 구조

물리적 구조

1차원 배열을 이용한 선형 리스트 프로그램

class Ex5_1{
	public static void main(String srgs[]){
		int sale[] = new int[]{157, 209, 251, 312};

	for(int i=0; i<4; i++)
		System.out.printf("%d/4분기 : sale[%d]= %d %n", i+1, i, sale[i]);	
	}
}

실행 결과

실행 결과 확인

• 배열 sale의 시작 주소 : 1245036

• sale[2]=251의 위치 = 시작주소 + (인덱스x4바이트) 

                                   = 1245036 + (2x4바이트)

                                   = 1245044
• 논리적인 순서대로 메모리에 연속하여 저장된 순차구조임을 확인

 

 

 

이차원 배열을 이용한 선형 리스트의 구현

[표4-4]2009~2010년 분기별 노트북 판매량

2차원 배열을 이용한 구현

int sale[][] = new int[][]{{63, 84, 140, 130}, {157, 209, 251, 312}};

 

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

−  원소의 위치 계산 방법 : α + (ixnj + j)xl

행의 개수가 ni이고 열의 개수가 nj인 2차원 배열 A[ni][nj]의 시작주소가 α이고 원소의 길이가 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

−  원소의 위치 계산 방법 : α + (jxni + i)xl

 

class Ex5_2{
	public static void main(String srgs[]){
		int sale[][] = new int[][]{{63, 84, 140, 130},{157, 209, 251, 312}};

		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]);
		System.out.println();
        }
	}
}

실행 결과

실행 결과 확인

• 시작주소α=1245012, ni=2, nj=4, i=1, j=1, l=4

• sale[1][1]=209의 위치 = α+ (ixnj+j)xl

                                        = 1245012 + (1x4+1)x4

                                        = 1245012 + 20
                                        = 1245032

• C 컴파일러가 행 우선 순서 방법으로 2차원 배열을 저장함을 확인

 

 

3차원 배열을 이용한 선형 리스트의 구현

[표4-5]2009~20010년, 1팀과 2팀의 분기별 노트북 판매량

3차원 배열을 이용한 구현

int sale[][][] = new int [][][]{{{63, 84, 140, 130},

                                                  {157, 209, 251, 312}},

                                                  {{59, 80, 130, 135},

                                                  {149, 187, 239, 310}}};

3차원 배열의 물리적 저장 방법

• 3차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법을 사용

• 면 우선 순서 방법
−3차원 배열의 첫 번째 인덱스인 면 번호를 기준으로 사용하는 방법 −원소의 위치 계산 방법 : α + {(ixnjxnk) + (jxnk) + k}xl

면의 개수가 ni이고 행의 개수가 nj이고, 열의 개수가 nk 인 3차원 배열 A[ni][nj][nk], 시작주소가 α이고 원소의 길이가 l 일 때, i면 j행 k열 원소 즉, A[i][j][k]의 위치

 

• 열 우선 순서 방법

− 3차원 배열의 마지막 인덱스인 열 번호를 기준으로 사용하는 방법 

−원소의 위치 계산 방법 : α + {(kxnjxni) + (jxni) + i}xl

class Ex5_3{
	public static void main(String srgs[]){
		int sale[][][] = new int [][][]{{{63, 84, 140, 130},
										{157, 209, 251, 312}}, 
                                        {{59, 80, 130, 135},
										{149, 187, 239, 310}} };
		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("--------------------------");
		}

실행 결과

실행 결과 확인

• 시작주소α=1244980, ni=2, nj=2, nk=4, i=1, j=1, k=2, l=4

• sale[1][1][2]=239의 위치 = α+{(ixnjxnk)+(jxnk)+k}xl

                                             = 1244980 + {(1x2x4)+(1x4)+2}x4

                                             = 1244980 + 56
                                             = 1245036

• C 컴파일러가 면 우선 순서 방법으로 3차원 배열을 저장함을 확인