데이터 구조 (17) 배열 과 행렬
2. 배열 의 실현 메커니즘: 배열 은 보통 바이트 단위 로 하고 메모리 단위 의 주소 이미지 공식 에 따라 메모 리 를 분배 합 니 다.고급 언어 로 배열 을 정의 할 때, 배열 이 메모리 에 있 는 첫 번 째 주 소 는 시스템 동적 으로 분배 되 고 저 장 됩 니 다.고급 언어 는 보통 메모리 에 저 장 된 첫 번 째 주 소 를 배열 이름 으로 저장 합 니 다.한 배열 의 첫 주 소 를 확정 하면 시스템 은 이 배열 의 임의의 배열 요소 의 메모리 주 소 를 계산 할 수 있다.배열 의 각 요소 의 메모리 주 소 를 계산 하 는 시간 이 같 기 때문에 배열 에 있 는 임의의 요 소 를 액세스 하 는 시간 도 같 습 니 다. 보통 이러한 특성 을 가 진 저장 구 조 를 랜 덤 저장 구조 라 고 합 니 다.그 러 니까 배열 은 랜 덤 저장 구조의 특성 을 가지 고 있다.
3. 수치 분석 에서 같은 데이터 요소 나 0 요 소 를 가 진 고급 행렬 이 자주 나타난다.같은 요소 나 0 요 소 를 많이 가지 고 데이터 분 포 는 일정한 규칙 을 가 진 행렬 을 특수 행렬 이 라 고 부른다. 예 를 들 어 대칭 행렬, 삼각 행렬 과 대각 행렬 이다.저장 공간 을 절약 하기 위해 서 는 이런 행렬 을 압축 저장 해 야 한다.압축 저장 의 원칙 은 여러 개의 값 이 같은 행렬 요소 가 같은 저장 공간 을 분배 하고 0 요 소 는 저장 공간 을 분배 하지 않 는 다 는 것 이다.대칭 행렬, 삼각 행렬 과 대각 행렬 에 있어 서 먼저 행렬 의 임 의 요소 와 압축 된 배열 의 아래 표 시 된 대응 관계 에 따라 모든 데이터 요소 가 배열 에 저 장 된 위 치 를 얻 은 다음 에 0 이 아 닌 데이터 요 소 를 한 배열 에 저장 합 니 다.
4. 비교적 많은 0 요 소 를 가지 고 0 요소 가 아 닌 분포 불규칙 한 행렬 을 희소 행렬 이 라 고 한다.희소 행렬 에 0 이 아 닌 원소 의 분포 가 불규칙 하기 때문에 특수 행렬 처럼 0 이 아 닌 원소 값 만 저장 할 수 없다.희소 행렬 의 두 가지 상용 저장 구 조 는 삼원 조 표 저장 과 십자 체인 표 저장 이다.
1. 희소 행렬 의 3 원 그룹 표 저장.
(1) 희소 행렬 에 있 는 임의의 비 0 요소 에 대해 0 요소 가 아 닌 값 (value) 을 저장 하 는 것 외 에 줄 (row), 열 (column) 의 위 치 를 동시에 저장 해 야 합 니 다.반대로 3 원 그룹 (row, column, value) 을 사용 하면 0 이 아 닌 요 소 를 유일 하 게 확인 할 수 있 습 니 다.따라서 희소 행렬 은 0 원 이 아 닌 3 원 조 와 그 행렬식 에서 유일 하 게 확정 할 수 있다.
(2) 희소 행렬 의 전환 행렬 의 3 원 목록 에 저 장 된 행렬 전환 알고리즘
：
0 0 8 0 0 0 0 2 8
0 0 0 0 0 0 2 0 5
5 0 0 0 16 0 2 4 16
0 0 18 0 0 0 3 3 18
0 0 0 9 0 0 4 3 9
：
0 0 5 0 0 0 2 5
0 0 0 0 0 2 0 8
8 0 0 18 0 2 3 18
0 0 0 0 9 3 4 9
0 0 16 0 0 4 2 16
0 0 0 0 0 희소 행렬 이 삼원 조 순서 표 로 표 시 될 때 선행 서열, 후 열 서열 의 원칙 으로 비 0 원 소 를 저장 하면 희소 행렬 의 연산 에 유리 하 다.그러나 행렬 번호 에 따라 직접 교환 하여 전환 하면 얻 은 3 원 조 순서 표 는 선행 순서, 후 열 순서 의 원칙 에 만족 하지 않 는 다.
이 문 제 를 해결 하기 위해 서 는 이렇게 행렬 전환 을 할 수 있 습 니 다. 전환 전의 3 원 조 를 스 캔 하고 선 열 순서, 후 행 순서 의 원칙 에 따라 3 원 조 를 옮 길 수 있 습 니 다.원 매트릭스 에서 얻 은 3 원 그룹 에서 0 줄 부터 열 번호 가 0 인 요 소 를 아래로 검색 하고 (2, 0, 5) 를 찾 으 면 (0, 2, 5) 로 전환 하고 전 치 된 3 원 그룹 순서 표 에 저장 합 니 다.이 어 열 번호 가 1 인 요 소 를 검색 해 보 았 으 나 찾 지 못 했다.열 번호 가 2 인 요 소 를 검색 하고 (0, 2, 8) 을 찾 아 (2, 0, 8) 로 전환 하여 전 치 된 3 원 그룹 순서 표 에 넣 습 니 다.순서대로 유추 하면 3 원 조 를 스 캔 할 때 까지 행렬 의 전 치 를 완성 할 수 있 고 전 치 된 3 원 조 표 는 선행 순서, 후 열 순서 의 원칙 을 만족 시 켜 야 한다.
(3) 희소 행렬 의 전환 행렬 을 구 하 는 3 원 목록 에 저 장 된 행렬 의 빠 른 전환 알고리즘
매트릭스 쾌속 전환 알고리즘 의 기본 사상 은 원 희소 행렬 이 N 이 고 그 3 원 그룹 순서 표 는 TN 이 며 N 의 전환 행렬 은 M 이 고 그 에 대응 하 는 3 원 그룹 순서 표 는 TM 이다.먼저 N 의 각 열의 첫 번 째 비 0 요소 가 전 환 된 TM 의 줄 번 호 를 구하 고 전 환 된 TN 을 스 캔 하여 이 열 에 있 는 요 소 를 TM 의 해당 위치 에 한 번 에 저장 합 니 다.N 에서 첫 번 째 열의 첫 번 째 비 0 요 소 는 반드시 TM 의 첫 번 째 줄 위치 에 저장 되 기 때문에 첫 번 째 열의 비 0 요소 개 수 를 알 고 있다 면 두 번 째 열의 첫 번 째 비 0 요소 가 TM 에서 의 줄 번 호 는 첫 번 째 비 0 요소 가 TM 에서 의 줄 번호 에 첫 번 째 열의 비 0 요소 개 수 를 더 한 것 과 같다.원 매트릭스 의 3 원 그룹 저장 순 서 는 선행 후 열 이기 때문에 같은 줄 에 서 는 반드시 열 번호 가 작은 요 소 를 만 나 야 합 니 다. 그러면 원 매트릭스 N 의 TN 을 한 번 스 캔 하면 됩 니 다.
num [i] 배열 은 N 에서 i 열 비 0 요소 의 개 수 를 나타 내 고 다음 과 같다. {1, 0, 2, 1, 1, 0}
cpot [i] 배열 은 N 에서 i 열 의 첫 번 째 비 0 요소 가 TM 에 있 는 위 치 를 나타 낸다. 즉, cpot [i] = cpot [i - 1] + num [i - 1] 은 다음 과 같다. {0, 1, 1, 3, 4, 5}
원 매트릭스 N 의 3 원 그룹 순서 표 TN 을 순서대로 스 캔 합 니 다. 첫 번 째 col 열 비 0 요 소 를 스 캔 할 때 TM 의 cpot [col] 줄 번호 위치 에 직접 저장 한 다음 cpot [col] 에 1 을 추가 합 니 다. 즉, cpot [col] 은 항상 다음 col 열 비 0 요소 가 TM 에 있 는 줄 수 입 니 다.
즉, 먼저 원 3 원 순서 표 TN 을 옮 겨 다 니 며 0 번 째 데이터 요 소 를 얻 은 것 은 (0, 2, 8) 이 고 그 열 수 는 2 이 며, 2 번 째 배열 요소 가 TM 에 있 는 줄 수 그룹 에 따라 알 수 있다 (0, 2, 8). 이 데이터 요 소 는 TN 에서 틀림없이 cpot [2] = 1 줄 에 놓 여 있 기 때문에 행렬 을 교환 한 다음 (2, 0, 8) TN 의 첫 번 째 줄, 즉 data [1] 이다.의 위치 에서 cpot [2] + 1 = 2 를 사용 합 니 다. 이것 은 N 에서 같은 열 에 두 개의 데이터 요소 가 있다 면 (0, 2, 8) 아래 에 있 는 그 데이터 요 소 는 반드시 TN 중의 (2, 0, 8) 아래 에 두 어야 하기 때 문 입 니 다. 행렬 전환 의 원리 에 따라 잘 이해 할 수 있 습 니 다.그리고 차례대로 유추 하면 새로운 TN 순서 표를 얻 을 수 있다.
(4) 희소 행렬 의 삼원 조 순서 저장 구조의 장단 점: 저장 공간 을 절약 하고 연산 속 도 를 가속 화 할 수 있 으 나 연산 과정 에서 계수 행렬 의 비원 소 위치 가 변화 하면 반드시 수조 에서 원소 의 이동 을 일 으 킬 수 있다. 이때 수조 원 소 를 삽입 하거나 삭제 하 는 작업 은 불편 하 다.이 문제 에 대해 체인 식 저장 구 조 를 이용 하여 희소 행렬 을 표시 할 수 있 으 며 삽입 또는 삭제 작업 을 하 는 것 이 더욱 편리 하 다.
2. 희소 행렬 의 십자 링크 저장.
(1) 희소 행렬 에서 0 요소 가 아 닌 위치 나 개수 가 자주 변화 할 때 3 원 짜 리 순서 표 저장 구 조 를 사용 하 는 것 이 아니 라 체인 식 저장 구 조 를 사용 해 야 한다.
(2) 십자 링크 에서 희소 행렬 의 비 0 요 소 는 하나의 노드 로 표시 합 니 다. 각 노드 는 5 개의 도 메 인 으로 구성 되 어 있 습 니 다. 그 중에서 row 도 메 인 은 0 요소 가 아 닌 줄 의 위 치 를 저장 하고 column 도 메 인 은 0 요소 가 아 닌 열 에 있 는 위 치 를 저장 합 니 다. value 도 메 인 은 이 0 요소 가 아 닌 값 을 저장 합 니 다. right 도 메 인 은 이 0 요소 가 아 닌 다음 비 0 요소 노드 지침 을 저장 합 니 다.다운 도 메 인 은 0 이 아 닌 요소 와 같은 열 에 있 는 다음 0 이 아 닌 요소 노드 지침 을 저장 합 니 다.같은 줄 의 비 0 원소 결점 은 right 역 을 통 해 하나의 선형 체인 테이블 로 연결 되 고 같은 열의 비 0 원소 결점 은 down 역 을 통 해 하나의 선형 체인 테이블 로 연결된다. 모든 비 0 원소 결점 은 특정한 줄 체인 테이블 의 결점 이자 특정한 열 체인 테이블 의 특정한 결점 이다. 전체 희소 행렬 은 하나의 십자 교차 체인 테이블 을 구성 하기 때문에 이런 체인 테이블 을 십자 체인 테이블 이 라 고 부른다.
5. 희소 행렬 의 3 원 순서 표 저장 구조의 자바 언어 코드 실현:
package bigjun.iplab.sparseMatrix;
/**
*
*/
public class TripleNode {
public int row; //
public int column; //
public int value; //
//
public TripleNode(int row, int column, int value) {
this.row = row;
this.column = column;
this.value = value;
}
//
public TripleNode() {
this(0, 0, 0);
}
}package bigjun.iplab.sparseMatrix;
/**
*
*/
public class SparseMatrix {
public TripleNode data[]; //
public int rows; //
public int columns; //
public int nums; //
// 1: maxSize
public SparseMatrix(int maxSize) {
data = new TripleNode[maxSize];
for (int i = 0; i < data.length; i++) {
data[i] = new TripleNode();
}
rows = 0;
columns = 0;
nums = 0;
}
// 2:
// ， 1
public SparseMatrix(int mat[][]) {
int i,j, k = 0, count = 0;
rows = mat.length; //
columns = mat[0].length; //
for (i = 0; i < rows; i++) { //
for (j = 0; j < columns; j++) {
if (mat[i][j] != 0) {
count++;
}
}
}
nums = count; //
data = new TripleNode[nums]; // 1
for (i = 0; i < rows; i++) {
for (j = 0; j < columns; j++) {
if (mat[i][j] != 0) {
data[k] = new TripleNode(i, j, mat[i][j]); //
k++;
}
}
}
}
//
public SparseMatrix transpose() {
SparseMatrix tMatrix = new SparseMatrix(nums); //
tMatrix.columns = rows; //
tMatrix.rows = columns; //
tMatrix.nums = nums; //
int q = 0;
for (int i = 0; i < columns; i++) { // 0
for (int j = 0; j < nums; j++) { //
if (data[j].column == i) { // i i ， 0 1...
tMatrix.data[q].row = data[j].column;
tMatrix.data[q].column = data[j].row;
tMatrix.data[q].value = data[j].value;
q++;
}
}
}
return tMatrix;
}
//
public SparseMatrix fastTranspose() {
SparseMatrix tMat = new SparseMatrix(nums); //
tMat.columns = rows; //
tMat.rows = columns; //
tMat.nums = nums; //
int i, j = 0, k = 0;
int[] num, cpot;
if (nums > 0) {
num = new int[columns]; // num[i] N i
cpot = new int[columns];
// num
for (i = 0; i < columns; i++) {
num[i] = 0;
}
//
for (i = 0; i < nums; i++) {
j = data[i].column;
num[j]++;
}
// 1 TM
cpot[0] = 0;
for (i = 1; i < columns; i++) {
cpot[i] = cpot[i-1] +num[i-1];//cpot[i] N i TM
}
//
for (i = 0; i < nums; i++) { //
j = data[i].column;
k = cpot[j]; // TM
tMat.data[k].row = data[i].column;
tMat.data[k].column = data[i].row;
tMat.data[k].value = data[i].value;
cpot[j]++; //
}
}
return tMat;
}
//
public void MatrixTraverse() {
System.out.println(" : ");
System.out.println(" : " + rows + ", : " + columns + ", : " + nums);
System.out.println(" ");
for (int j = 0; j < nums; j++) {
System.out.println(data[j].row + "\t" + data[j].column + "\t" + data[j].value);
}
}
public static void main(String[] args) {
int m[][] = {
{0, 0, 8, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{5, 0, 0, 0, 16, 0},
{0, 0, 18, 0, 0, 0},
{0, 0, 0, 9, 0, 0}
};
SparseMatrix sM = new SparseMatrix(m);
sM.MatrixTraverse();
SparseMatrix tM = sM.transpose();
tM.MatrixTraverse();
SparseMatrix fM = sM.fastTranspose();
fM.MatrixTraverse();
}
} :
: 5, : 6, : 5
0 2 8
2 0 5
2 4 16
3 2 18
4 3 9
:
: 6, : 5, : 5
0 2 5
2 0 8
2 3 18
3 4 9
4 2 16
:
: 6, : 5, : 5
0 2 5
2 0 8
2 3 18
3 4 9
4 2 16다음으로 전송:https://www.cnblogs.com/BigJunOba/p/9205110.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
