1. 2차원 배열을 이용한 선형 리스트 구현
가. 2차원 배열을 이용한 선형 리스트 구현
1) 2차원 배열을 이용한 구현
예를 들어 다음과 같은 분기별 노트북 판매량 표를 2차원 리스트로 만든다고 해보자.
[2016~2017년 분기별 노트북 판매량 리스트]
| 연도 / 분기 | 1/4분기 | 2/4분기 | 3/4분기 | 4/4분기 |
| 2016년 | 63 | 84 | 140 | 130 |
| 2017년 | 157 | 209 | 251 | 312 |
이 때 분기와 연도를 모두 표현해야 하므로 순서가 두 종류가 필요함.
따라서 행 인덱스와 열 인덱스가 있는 2차원 배열을 사용
2차원 배열구조를 논리적으로 표현할 때는 행과 열의 구조(2차원)로 나타내지만 실제로 메모리에 저장될 때는 1차원 구조로 저장됨.
C언어로 다음과 같이 2차원 배열을 만들고, 표로 도식화 하면 아래의 표와 같음.
int sale[2][4] = { { 63, 84, 140, 130 }, { 157, 209, 251, 312 } };| sale | [0] | [1] | [2] | [3] |
| [0] | 63 | 84 | 140 | 130 |
| [1] | 157 | 209 | 251 | 312 |
나. 2차원 배열의 물리적 저장 방법
2차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법을 사용함.
1) 행 우선 순서 방법(Row Major Order)
2차원 배열의 첫 번째 인덱스인 행 번호를 기준으로 사용하는 방법(더 보편적인 방법)
위의 예제가 다음과 같은 순서로 물리적인 공간에 저장됨.
sale[0][0] = 63, sale[0][1] = 84, sale[0][2] = 140, sale[0][3] = 140, sale[1][0] = 157, sale[1][1] = 209, sale[1][2] = 251, sale[1][3] = 312
2) 열 우선 순서 방법(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
3) 원소의 위치 계산
행의 개수가 \(n_{i}\)이고 열의 개수가 \(n_{j}\)인 2차원 배열 A[\(n_{i}\)][\(n_{j}\)]의 시작주소가 \(\alpha\)이고, 원소의 길이((메모리 크기))가 \(l\)이라면, i행 j열 원소, 즉, A[i][j]의 원소 위치를 계산하면 다음과 같다.
행우선 : \(\alpha \: + \: (i \: \times \: n_{j} \: + \: j) \: \times \: l\)
열우선 : \(\alpha \: + \: (j \: \times \: n_{i} \: + \: i) \: \times \: l\)
다. 2차원 논리 순서를 1차원 물리 순서로 변환
라. 2차원 배열의 논리적, 물리적 순서 확인하기 프로그램
#include <stdio.h>
void main() {
int i, *ptr;
int sale[2][4] = {
{ 63, 84, 140, 130 },
{ 157, 209, 251, 312 }
};
ptr = &sale[0][0];
for (i = 0; i < 8; i++) {
printf("\n address : %u sale %d = %d", ptr, i, *ptr);
ptr++;
}
getchar();
}마. 실행 결과
address : 627098640 sale 0 = 63
address : 627098644 sale 1 = 84
address : 627098648 sale 2 = 140
address : 627098652 sale 3 = 130
address : 627098656 sale 4 = 157
address : 627098660 sale 5 = 209
address : 627098664 sale 6 = 251
address : 627098668 sale 7 = 312
C 컴파일러가 행 우선 순서 방법으로 2차원 배열을 저장함을 확인할 수 있음.
2. 3차원 배열을 이용한 선형 리스트 구현
가. 3차원 배열을 이용한 선형 리스트 구현
1) 3차원 배열을 이용한 구현
예를 들어 다음과 같은 각 팀 당 분기별 노트북 판매량 표를 3차원 리스트로 만든다고 해보자.
[1팀과 2팀의 분기별 노트북 판매량 리스트]
| 팀 | 연도 / 분기 | 1/4분기 | 2/4분기 | 3/4분기 | 4/4분기 |
| 1팀 | 2016년 | 63 | 84 | 140 | 130 |
| 2017년 | 157 | 209 | 251 | 312 | |
| 2팀 | 2016년 | 59 | 80 | 130 | 135 |
| 2017년 | 149 | 187 | 239 | 310 |
연도와 분기 그리고 팀 순서도 나타내야 하므로 세 종류 순서를 표현해야 함.
이럴 때는 면 인덱스, 행 인덱스, 열 인덱스가 있는 3차원 배열을 사용
int sale[2][2][4] = {
{
{ 63, 84, 140, 130 },
{ 157, 209, 251, 312 }
},
{
{ 59, 80, 130, 135 },
{ 149, 187, 239, 310 }
}
};| sale[0] | [0] | [1] | [2] | [3] |
| [0] | 63 | 84 | 140 | 130 |
| [1] | 157 | 209 | 251 | 312 |
| sale[1] | [0] | [1] | [2] | [3] |
| [0] | 59 | 80 | 130 | 135 |
| [1] | 149 | 187 | 239 | 310 |
나. 3차원 배열의 물리적 저장 방법
3차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법을 사용
면의 개수가 \(n_{i}\)이고, 행의 개수가 \(n_{j}\)이고, 열의 개수가 \(n_{k}\)인 3차원 배열 A[\(n_{i}\)][\(n_{j}\)][\(n_{k}\)], 시작주소가 \(\alpha\)이고 원소의 길이(메모리 크기)가 \(l\)일 때, i면 j행 k열 원소 즉, A[i][j][k]의 위치(순서) 계산 방법
1) 면 우선 순서 방법
3차원 배열의 첫 번째 인덱스인 면 번호를 기준으로 사용하는 방법(면, 행, 열 순서)
\( \alpha \: + \: \left\{(i \: \times \: n_{j} \: \times \: n_{k}) \: + \: (j \: \times \: n_{k}) \: + \: k \right\} \: \times \: l\)
2) 열 우선 순서 방법
3차원 배열의 마지막 인덱스인 열 번호를 기준으로 사용하는 방법(열, 행, 면 순서)
\( \alpha \: + \: \left\{(k \: \times \: n_{j} \: \times \: n_{i}) \: + \: (j \: \times \: n_{i}) \: + \: i \right\} \: \times \: l\)
다. 3차원 논리 순서를 1차원 물리 순서로 변환
라. 3차원 배열의 논리적, 물리적 순서 확인하기 프로그램
#include <stdio.h>
void main() {
int i, *ptr;
int sale[2][2][4] = {
{
{ 63, 84, 140, 130 },
{ 157, 209, 251, 312 }
},
{
{ 59, 80, 130, 135 },
{ 149, 187, 239, 310 }
}
};
ptr = &sale[0][0][0];
for (i = 0; i < 16; i++) {
printf("\n address : %u sale %2d = %3d", ptr, i, *ptr);
ptr++;
}
getchar();
}마. 실행 결과
address : 417069616 sale 0 = 63
address : 417069620 sale 1 = 84
address : 417069624 sale 2 = 140
address : 417069628 sale 3 = 130
address : 417069632 sale 4 = 157
address : 417069636 sale 5 = 209
address : 417069640 sale 6 = 251
address : 417069644 sale 7 = 312
address : 417069648 sale 8 = 59
address : 417069652 sale 9 = 80
address : 417069656 sale 10 = 130
address : 417069660 sale 11 = 135
address : 417069664 sale 12 = 149
address : 417069668 sale 13 = 187
address : 417069672 sale 14 = 239
address : 417069676 sale 15 = 310
C 컴파일러가 면 우선 순서 방법으로 3차원 배열을 저장함을 확인할 수 있음.
3. 희소행렬의 순차 자료구조 구현
가. 행렬(Matrix)의 개념
행과 열로 구성된 자료구조
\(m \times n\) 행렬 : 행 개수가 m개, 열 개수가 n개인 행렬
\(\begin{vmatrix} a_{11} & \dots & a_{1n} \\ \dots & \dots & \dots \\ a_{m1} & \dots & a_{mn} \\ \end{vmatrix}\)
정방행렬 : 행렬 중에서 m과 n이 같은 행렬(정사각행렬)
\(\begin{vmatrix} a_{11} & \dots & a_{1n} \\ \dots & \dots & \dots \\ a_{n1} & \dots & a_{nn} \\ \end{vmatrix}\)
전치행렬 : 행렬(A)의 행과 열을 서로 바꿔 구성한 행렬(A')
\(A=\begin{vmatrix} a_{11} & \dots & a_{1n} \\ \dots & \dots & \dots \\ a_{m1} & \dots & a_{mn} \\ \end{vmatrix}, \: A'=\begin{vmatrix} a_{11} & \dots & a_{m1} \\ \dots & \dots & \dots \\ a_{1n} & \dots & a_{mn} \\ \end{vmatrix}\)
나. 행렬의 선형 리스트 표현
행렬의 각 원소는 행과 열로 표현할 수 있으므로 선형 리스트 표현 mxn 행렬 A를 아래와 같이 2차원 배열 A[m][n]으로 표현할 수 있음.
다. 희소행렬(Sparse Matrix)
행렬의 원소 중에서 많은 항들이 0으로 구성된 행렬
https://ko.wikipedia.org/wiki/성긴_행렬
성긴 행렬 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 성긴 행렬의 예 ( 11 22 0 0 0 0 0 0 33 44 0 0 0 0 0 0 55 66 77 0 0 0 0 0 0 0 88 0 0 0 0 0 0 0 99 ) {\displaystyle {\begin{pmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&
ko.wikipedia.org
원소 대부분이 0이라 실제로 사용하지 않는 공간이 많아 기억 공간의 활용도가 떨어짐.
따라서 기억공간을 좀더 효율적으로 사용하려면 0이 아닌 값이 있는 원소만 따로 배열로 구성하는 방법을 사용할 수 있음.
1) 희소 행렬에 대한 2차원 배열 표현
위의 희소 행렬 B는 배열의 원소 56개 중 실제 사용하는 것은 0이 아닌 원소를 저장하는 10개뿐이므로 46개의 메모리 공간 낭비
기억 공간을 좀 더 효율적으로 사용하기 위해 0이 아닌 값이 있는 원소만 따로 배열로 구성하는 방법을 사용
① 0이 아닌 원소만 추출하여 <행번호, 열번호, 원소> 쌍으로 배열에 전장
② 추출한 순서쌍을 2차원 배열에 행으로 저장
③ 원래의 행렬에 대한 정보를 순서쌍으로 작성하여 0번 행에 저장
2) 희소행렬의 전치 행렬 변환 프로그램
위의 희소행렬 B와 B의 전치행렬을 2차원 배열로 나타내면 다음과 같음.
그리고 원소만 따로 배열로 구성하면 다음과 같음.
위와 같이 동작하는 C 프로그램 코드
#include <stdio.h>
typedef struct {
int row, col, value;
} term;
void smTranspose(term a[], term b[]) {
int m, n, v, i, j, p;
m = a[0].row;
n = a[0].col;
v = a[0].value;
b[0].row = n;
b[0].col = m;
b[0].value = v;
if (v > 0) {
p = 1;
for (i = 0; i < n; i++)
for (j = 1; j <= v; j++)
if (a[j].col == i) {
b[p].row = a[j].col;
b[p].col = a[j].row;
b[p].value = a[j].value;
p++;
}
}
}
void main() {
int i;
term a[11] = {
{8, 7, 10},
{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[11];
smTranspose(a, b);
printf("<< Sparse Matrix >>\n");
for (i = 1; i < 11; i++) {
printf("%d %d %d\n", a[i].row, a[i].col, a[i].value);
}
printf("\n");
printf("<< Transpose Sparse Matrix >>\n");
for (i = 1; i < 11; i++) {
printf("%d %d %d\n", b[i].row, b[i].col, b[i].value);
}
getchar();
}실행 결과
<< Sparse Matrix >>
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
<< Transpose Sparse Matrix >>
0 2 23
0 6 52
1 4 14
2 0 2
3 3 31
4 1 7
4 7 11
5 4 25
6 0 12
6 5 6
