[ 자료구조 및 알고리즘 ] 4. 순차 자료구조 - 4. 행렬의 순차 자료구조 표현

행렬(matrix)

m x n 행렬

• m : 행의 개수
• n : 열의 개수
• 원소의 개수 : (m x n) 개

전치 행렬

행렬의 행과 열을 서로 교환하여 구성한 행렬

행렬 A의 모든 원소의 위치(i, j)를 (j, i)로 교환

m×n 행렬을 n×m 행렬로 변환한 행렬 A’는 행렬 A의 전치행렬

 

 

행렬의 순차 자료구조 표현

2차원 배열 사용

• m×n행렬을 m행 n열의 2차원 배열로 표현 

희소 행렬에 대한 2차원 배열 표현
• [그림 4-17]의 희소 행렬 B는 배열의 원소 56개 중에서 실제 사용하는 것은 0이 아닌 원소를 저장하는 10개 뿐이므로 46개의메모리 공간 낭비

• 희소 행렬인 경우에는 0이 아닌 원소만 추출하여 <행번호, 열번호, 원소>쌍으로 배열에 저장

• 추출한 순서쌍을 2차원 배열의 행으로 저장
• 원래의 행렬에 대한 정보를 순서쌍으로 작성하여 0번 행에 저장

− <전체 행의 개수, 전체 열의 개수, 0이 아닌 원소의 개수>

 

희소 행렬의 추상 자료형

 

희소행렬의 전치 연산 알고리즘