독학사2단계_자료구조_2장 배열

2장. 배열

가) 개요

1. 정의

·일련의 항목들이 동일 크기로 순서를 갖고 배열된 자료 구조

·동일한 자료구조를 가진 원소들의 집합

·색인과 값의 쌍으로 이루어진 집합

·연속된 메모리 블록을 사용하며

※ 1차원 배열

·배열 내의 원소들은 각각 하나의 명칭과 일차원적인 첨자로 유일하게 결정된다.

·동일한 자료구조를 가지는 원소들로 구성된 유한 집합인 논리적 자료형을 말한다.

※ 다차원 배열 

·

나) 순서리스트 :: ADT(추상자료형)을 정희하기 위한 연산

·NULL

다) 배열의 표현

1. 다차원 배열의 행우선과 열우선

·행우선

배열 A[5][4]를 1부터 순차적으로 채워넣을때 순서

C언어에서 사용하는 방법

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16
17	18	19	20

·열우선

배열 A[5][4]를 1부터 순차적으로 채워넣을때 순서

1	6	11	16
2	7	12	17
3	8	13	18
4	9	14	19
5	10	15	20

라) 희소 행렬(Sparse Matrix)

1. 희소 행렬의 표현

·행렬의 원소중 0인 원소의 갯수가 많을 때 이를 희소 행렬이라고 한다.

·희소 행렬은 연결 리스트를 이용해서 저장하면 가장 효율적이다.

0이 아닌 값들 끼리만 연결해서 저장하면 메모리의 낭비를 막을 수 있다.

		Column
		0	1	2	3	4	5
R O w	0	15	0	0	0	0	0
	1	0	0	14	0	16	0
	2	0	8	0	0	0	0
	3	0	0	0	10	0	0
	4	23	0	0	0	0	0
	5	0	0	0	0	0	42
	6	0	0	3	0	0	0
	7	0	0	0	0	0	0

이런 행렬을 다음과 같이 축햑시켜 표현한다.

Data	Row	Column	Value
[0]	8	6	7
[1]	0	0	15
[2]	1	2	14
[3]	1	4	16
[4]	3	3	10
[5]	4	0	23
[6]	5	5	42
[7]	6	2	3

Data를 배열 A라고 했을때

A의 첫 번째 인덱스에는 원래의 희소 행렬의 행과 열의 값과 0이 아닌 값을 가지는 원소의 갯수를 표현한다.

2. 전치 행렬

·행렬의 각 원소들의 행과 열값을 서로 바꾸어 표현한 행렬이다. 예를들어 A[4][2]의 값은 A[2][4]의 값으로 저장된다.

1	2	3
4	5	6
7	8	9

위 행렬을 전치 행렬으로 표현하면 아래와 같다.

1	4	7
2	5	8
3	6	9

·임의의 행렬이 어떤 조건을 성립하게되면 그 행렬의 역행렬은 전치행렬이된다.

역행렬을 구하는 것보다 전치행렬을 구하는게 쉽기 때문에 자주 쓰인다.