배열 및 행렬 의 압축 저장 소

데이터 구조 중의 선형 구 조 는 선형 표, 창고, 대기 열, 그리고 열 을 포함 하 는데 이런 구조의 데이터 요 소 는 모두 분해 되 지 않 는 원자 유형 이다.배열 과 광의 표 는 선형 표 가 다음 과 같은 의미 이상 의 확장 이 라 고 볼 수 있다. 표 의 데이터 요소 자체 도 데이터 구조 이다.
배열
1. 선형 표 와 마찬가지 로 배열 의 모든 데이터 요 소 는 통 일 된 데이터 형식 에 속 해 야 합 니 다.배열 중의 모든 데이터 요 소 는 한 조 의 아래 표 (j1, j2,..., jn) 에 대응 하고 각 아래 표 시 는 각자 의 수치 범위 가 있 으 며 0 ≤ ji ≤ bi - 1, bi 는 제 i 차원 의 길이 (i = 1, 2, 3,..., n) 라 고 부른다.n = 1 일 때 n 차원 배열 은 정 해진 선형 표 로 퇴화 된다.
n 차원 배열 도 선형 표 의 보급 이 라 고 볼 수 있다.n 차원 배열 형식 은 데이터 요소 가 n - 1 차원 배열 형식의 1 차원 배열 형식 으로 정의 할 수 있 습 니 다.초기 화 와 소각 을 제외 하고 배열 은 요소 에 액세스 하고 요소 값 을 수정 하 는 작업 만 합 니 다.
2. 일반적으로 순서 저장 구 조 를 이용 하여 배열 을 나타 낸다.배열 이 다 차원 이기 때문에 연속 저장 장치 로 배열 의 데이터 요 소 를 저장 하려 면 저장 순 서 를 정 해 야 합 니 다.2 차원 배열 에 대해 두 가지 저장 방식 이 있 는데 그것 이 바로 열 순 서 를 위주 로 하 는 순서 (높 은 아래 표 시 는 가장 안쪽 표 시 를 우선 으로 하 는 것) 와 행 순 서 를 위주 로 하 는 순서 (낮은 표 시 는 가장 바깥쪽 표 시 를 우선 으로 하 는 것) 의 저장 방식 이다.
모든 데이터 요소 가 L 개의 저장 부 를 차지한다 고 가정 하면 2 차원 배열 A 에서 모든 요소 의 저장 위 치 는 공식 적 으로 LOC (i, j) = LOC (0, 0) + (b2) 로 계산 할 수 있다.×i + j) L, LOC (0, 0) 는 첫 번 째 요소 a00 의 저장 위치 입 니 다.
2. 행렬 의 압축 저장 소
행렬 의 원 을 효과적으로 저장 하면 행렬 의 각종 연산 을 효과적으로 진행 할 수 있다.
압축 저장 소 란 여러 개의 값 이 같은 원 에 하나의 저장 공간 만 분배 합 니 다.0 원 에 대해 공간 을 분배 하지 않 는 다.
희소 행렬 의 압축 저장 소:
이런 행렬 은 0 원 이 아니 라 0 원 이 적 고 분포 가 일정한 규칙 이 없다.m * n 의 행렬 에서 t 개의 요소 가 0 이 아니 라 고 가정 합 니 다.령 = t / (m * n) 행렬 의 희소 인자.  = 0.05 시 희소 행렬 이 라 고 한다.
메모리 국 은 정식 적 으로 0 원 이 아 닌 값 을 저장 하 는 것 외 에 그 가 있 는 줄 과 열의 위치 (i, j) 를 기록 해 야 한다. 하나의 3 원 그룹 (i, j, aij) 은 유일 하 게 행렬 A 의 0 원 이 아 닌 것 을 확정 했다.
3 원 그룹 표 의 서로 다른 표현 방법 을 바탕 으로 희소 행렬 의 서로 다른 압축 저장 방법 을 이 끌 어 낼 수 있다.
1, 3 원조 순서 표

#define MAXSIZE 500
typedef struct{
int i,j;    //            
ElemType e;}Triple;

4. 567913. data 도 메 인 에서 0 원 이 아 닌 3 원 그룹 은 행 순 서 를 위주 로 순서대로 배열 되 어 있다.
빠 른 전환 알고리즘: a. data 와 b. data 표 는 각각 희소 행렬 M, T 의 비 0 원 3 원 그룹 표 이 고 T 는 M 의 전환 행렬 입 니 다. 행렬 M 의 각 열 즉 T 의 각 줄 의 땅 이 0 원 이 아 닌 b. data 에 있 는 위 치 를 미리 확정 하면 a. data 의 3 원 그룹 을 다음 에 옮 길 때 b, data 의 적당 한 위치 에 직접 올 려 놓 아 전환 시간 을 실현 할 수 있 습 니 다.복잡 도 는 선형 이다.
전환 하기 전에 먼저 원 매트릭스 M 에서 각 열 에 0 원 이 아 닌 개 수 를 구 한 다음 에 각 열의 첫 번 째 비 0 원 이 b. data 에서 가 져 야 할 위 치 를 구 해 야 한다.

typedef struct{
Triple data[MAXSIZE+1];  //       ，data[0]   
int mu,nu,tu;    //     ，        
}TSMatrix;

2. 행 논리 링크 의 순서 표
이 저장 구 조 는 임의의 줄 의 비 0 원 을 무 작위 로 액세스 할 수 있 습 니 다. 행렬 알고리즘 에서 '줄' 정 보 를 표시 하 는 보조 배열 cpot 를 희소 행렬 의 저장 구조 에 고정 시 킵 니 다.

Status FastTransposeSMatrix(TSMatrix M,TSMatrix *T)
 { //       M     T
   T.mu=M.nu;
   T.nu=M.mu;
   T.tu=M.tu;
   if(T.tu)
   {
     for(col=1;col<=M.nu;++col)
       num[col]=0; //    
     for(t=1;t<=M.tu;++t) // M            
       ++num[M.data[t].j];
     cpot[1]=1;
     for(col=2;col<=M.nu;++col) //  col         b.data     
       cpot[col]=cpot[col-1]+num[col-1];
     for(p=1;p<=M.tu;++p)
     {
       col=M.data[p].j;
       q=cpot[col];
       T.data[q].i=M.data[p].j;
       T.data[q].j=M.data[p].i;
       T.data[q].e=M.data[p].e;
       ++cpot[col];  //    +1
     }
   }
   return OK;
 }

행렬 곱 하기: Q = M * N
알고리즘 설명:

Typedef struct{
Triple data[MAXSIZE++1];
Int rpos[MAXRC+1];
Int mu,nu,tu;
}RLSMatrix;

요점: 빠 른 전환 알고리즘 에 설 치 된 보조 벡터 용법 을 배 웁 니 다. 즉, 각 열 에 0 원 이 아 닌 벡터 num [col] 과 각 열 을 표시 하 는 첫 번 째 비 0 원 이 행렬 3 원 그룹 표 에서 적당 한 위 치 를 설명 하 는 벡터 cpot [col] 입 니 다.