선형 리스트 : 자료들 간의 순서를 갖는 리스트.
원소를 나열한 순서 = 원소들의 순서
원소가 하나도 없는 리스트는 공백 리스트라고 하며, 빈 괄호를 사용하여 표현한다.
선형 리스트 원소의 논리적 순서와 같은 순서로 메모리에 저장이 된다.
순차 자료구조의 원소 위치 계산(메모리 주소)
선형리스트가 저장된 시작 위치 : α
원소의 길이 : ι
i번째 원소의 위치 = α + (i-1)* ι
1차원 배열은 선형의 형태를 띄고 있어 하나의 인덱스 값을 이용해서 모든 원소에 접근 가능하다.
int형 1차원 배열이 있다고 하자. int형은 4byte의 크기를 가진다. 따라서 배열의 인덱스가 하나 증가할 때마다 메모리 주소는 4 byte씩 증가한다.
배열에서 첫번째 원소의 인덱스는 0이고 n번째 원소의 인덱스는 (n-1)이다.
원소의 크기(길이)가 ι 이고 첫번째 원소의 메모리 주소가 α일 때 n번째 원소의 위치, 즉 메모리 주소는 α + (i-1)* ι 이다.
-선형 리스트의 원소 삽입
선형 리스트 중간에 원소가 삽입되면, 그 이후 원소들은 한자리 씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시킨다.
1. 원소를 삽입할 빈자리를 만든다.
이때 인덱스 찾는 작업 실시해준다. 삽입할 자리 이후의 원소들을 한자리 씩 뒤로 자리이동을 시킨다.
2. 빈 자리에 원소를 삽입한다.
*자리 이동 횟수 = n-k+1 = 마지막 - 삽입 + 1 (n: 마지막 원소의 인덱스 k: 삽입할 자리의 인덱스)
-선형 리스트 원소 삭제
원소 삭제 후 원소들은 한자리 씩 자리를 앞으로 이동하여 물리적 순서를 논리적 순서와 일치시킨다.
원소 삭제 후 (인덱스 저장) 삭제한 자리 이후 원소들을 한자리 씩 앞으로 자리 이동
*자리 이동 횟수: n - (k+1) + 1 = n - k = 마지막 원소 인덱스 - 삭제한 자리 인덱스
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
package ch_05;
public class ch5_0 {
public static void main(String[] args) {
//선형 리스트 구현 및 삽입/삭제 예제
int a[] = new int[] {3, 6, 12, 15, 18, 21, 24, 0, 0, 0};
for(int i = 0; i<7; i++) System.out.printf("a[%d] = %d\n", i, a[i]);
System.out.println("\n\n");
int index = 0;
for(int i = 0; i < 7; i++) {
int addNum = 9;
if (a[i] > addNum && a[i-1] < addNum) index = i;
}
for(int i = 6; i >= index; i--) a[i+1] = a[i]; //한 칸씩 뒤로 미루기.
a[index] = 9;
index = 0;
for (int i = 0; i < 7; i++) {
int delNum = 12;
if (a[i] == delNum) index = i;
}
for(int i = index; i <= 7; i++) a[i] = a[i+1]; //12삭제.
for(int i = 0; i < 8; i++)
System.out.printf("a[%d] = %d\n", i, a[i]);
}
}
|
cs |
-2차원 배열을 이용한 선형 리스트 구현
-3차원 배열을 이용한 선형리스트 구현 / [][][] : 면 행 열
1. 면 우선 방법 : 면 번호를 기준
원소의 위치 계산 방법 : α + {(iⅹnjⅹnk ) + (jⅹnk ) + k}ⅹℓ
면의 개수가 ni이고 행의 개수가 nj이고, 열의 개수가 nk 인 3차원 배열 A[ni][nj][nk]
» 시작주소가 α이고 원소의 길이가 ℓ 일 때, i면 j행 k열 원소 즉, A[i][j][k]의 위치
2. 열 우선 방법 : 열 번호 기준
원소의 위치 계산 방법 : α + {(kⅹnjⅹni ) + (jⅹni ) + i}ⅹℓ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
package ch_05;
// 면, 행 , 열로 이루어진 3차원 배열을 이용한 선형리스트 구현.
public class ArrayList3D {
public static void main(String[] args) {
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 y = 0; y < 2; y++) {
for(int x = 0; x < 4; x++) {
System.out.printf("%d 4분기 : sale[%d][%d][%d] = %d %n" ,
x+1, i, y, x, sale[i][y][x]);
System.out.println("----------------");
}
System.out.println();
}
}
}
}
|
cs |
-다항식 덧셈 예제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
package polynomial;
//coefficient : 계수
public class Polynomial {
private int degree;
private float coef[] = new float[20];
Polynomial(int degree, float[] coef) {
this.degree = degree;
this.coef = coef;
}
Polynomial(int degree){
this.degree = degree;
for(int i = 0; i <= degree; i++) {
this.coef[i] = 0;
}
}
public int getDegree() {
return degree;
}
public float getCoef(int i) {
return coef[i];
}
public void setCoef(int i, float coef) {
this.coef[i] = coef;
}
public void printPoly() {
int temp = this.degree;
for(int i = 0; i <= this.degree; i++) {
System.out.printf("%3.0fx^%d ", this.coef[i], temp--);
}
}
}
|
cs |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
package polynomial;
public class AddPoly{
private int degree_A = 0, degree_B = 0, degree_C = 0, //차수
index_A = 0, index_B = 0, index_C = 0;
private int expo_A, expo_B;
private float coef_A, coef_B, coef_C; //계수
public Polynomial addPoly(Polynomial A, Polynomial B) {
degree_A = A.getDegree();
degree_B = B.getDegree(); //다항식 A와 B의 계수 가져옴.
expo_A = degree_A;
expo_B = degree_B;
//두 다항식의 덧셈의 결과는 최고차항의 계수가 C의 계수가 됨.
if(degree_A >= degree_B) degree_C = degree_A;
else degree_C = degree_B;
Polynomial C = new Polynomial(degree_C);
while(index_A <= degree_A && index_B <= degree_B) {
if(expo_A > expo_B) {
C.setCoef(index_C++, A.getCoef(index_A++));
expo_A--;
}
else if(expo_A == expo_B) {
C.setCoef(index_C++, A.getCoef(index_A++)+B.getCoef(index_B++));
expo_A--; expo_B--;
}
else {
C.setCoef(index_C++, B.getCoef(index_B++));
expo_B--;
}
}
return C;
}
}
|
cs |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
package polynomial;
public class Main01 {
public static void main(String[] args) {
float a[] = new float[] {4,3,5,0}; //A의 계수 배열a에 저장
float b[] = new float[] {3,1,0,2,1}; //B의 계수 배열b에 저장
Polynomial A = new Polynomial(3,a); //degree=3, 계수 a
Polynomial B = new Polynomial(4,b); //degree=4, 계수 b
AddPoly addpoly = new AddPoly();
Polynomial C = addpoly.addPoly(A, B);
System.out.printf("A(x) = "); A.printPoly();
System.out.println();
System.out.printf("B(x) = "); B.printPoly();
System.out.println();
System.out.printf("C(x) = "); C.printPoly();
}
}
|
cs |
다항식 & 행렬과 배열
- 전치행렬 : 행렬의 행과 열을 서로 교환하여 구성.
m*n 행렬 A의 전치행렬은 n*m 행렬 a.
- 희소 행렬(희소 다항식과 같은 원리)
모든 원소를 배열로 옮길 때, 메모리에는 0이 아닌 원소만 저장한다.
따라서 희소 행렬인 경우에는 0이 아닌 원소만 추출하여 배열에 저장한다.
<행번호,열번호,원소> 쌍으로 2차원 배열에 저장
다항식도 같은 원리로 생각하면 된다.
2차원 배열을 이용한 순차 자료구조 표현할 때 각 항에 대한 <지수, 계수> 쌍을 2차원 배열에 저장한다.
이는 1차원 배열을 사용하는 방법보다 메모리 사용 공간량이 감소한다. 즉, 공간 복잡도가 감소하면 프로그램 성능이 향상됨.
'Major > Data Structure & Algorithm' 카테고리의 다른 글
연결리스트 노드 개수 카운팅,특정 노드 순서 바꾸기,첫번째 노드 삭제하기 ... (0) | 2022.04.03 |
---|---|
[JAVA] 연결리스트, 노드, 삽입 및 삭제 (0) | 2022.04.03 |
[python+]연결리스트,노드,삽입,삭제 (0) | 2022.04.02 |
[2월 18일] Selection Sort Algorithm 삽입정렬, Insertion Sort Algorithm 삽입정렬 (0) | 2022.02.18 |
[2월 5일] 버블정렬 알고리즘, 문자수만큼 회전하기 (0) | 2022.02.15 |