資料結構 壓縮矩陣筆記

/*
數組的壓縮儲存：
    在一些高階矩陣中，非零元素非常少，此時如果使用二維數組将造成
    儲存空間的浪費，這時可隻儲存部分元素，進而提高儲存空間的利用
    率，通常的做法是為多個相同值的元素隻配置設定一個儲存單元，對值為
    零的元素不配置設定儲存單元。我們把非零元素個數遠小于二維數組總元
    素個數，或元素分布呈一定規律的（對稱矩陣，三角矩陣，對角矩陣）
    特殊矩陣壓縮儲存。
    
    對稱矩陣：
        矩陣元素的值與下标的關系： a(i,j) = a(j,i)
        我們隻需為每一對稱元素配置設定一個儲存單元，這樣可以将 n*n 個
        元素儲存在一個 n(n+1)/2 的儲存空間裡。
        假設用以為數組儲存上三角或下三角元素。則一維數組的下标 k
        與 n 階對稱陣的元素 a(i,j) 的下标對應關系為：
            如果 i >= j 時，以下三角儲存， k = i*(i+1)/2 + j
            如果 i < j  時，以上三角儲存， k = j*(j+1)/2 + i
            
    三角矩陣：
        分為上三角矩陣和下三角矩陣，其中在上三角矩陣中，下三角元素
        全部為一個常數c,下三角矩陣中，上三角元素全部為一個常數c。
        以上三角矩陣為例，上三角矩陣的壓縮規則是隻儲存上三角元素，
        不儲存下三角元素，或隻用一個儲存單元儲存下三角非零元素
        用一維數組儲存上三角矩陣，采取使用一個儲存單元儲存下三角元
        素的方法，一維數組的長度為 n*(n+1)/2 + 1 一維數組的下标 k與
         n 階上三角矩陣的元素 a(i,j) 的下标對應關系為：
            如果 i <= j, k = i*(2n-i+1)/2 + j -i
            如果 i > j , k = n*(n+1)/2 
        下三角矩陣使用一維數組儲存後相應的對應關系為：
            如果 i >= j, k = i*(i+1)/2 + j
            如果 i <  j, k = n*(n+1)/2 
        
        其中第 k = n*(n+1)/2 的位置存放的是常數 c 
        
        以上三角矩陣為例：
        # include <stdio.h>
        # define N 5
        
        int main(void)
        {
            int arry[N][N];
            int arr[N*(N+1)/2 + 1] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0};
            int i, j, k;
            for (i = 0; i < N; ++i)
            {
                for (j = 0; j < N; ++j)
                {
                    if (i <= j)
                    {
                        k = i*(2*N-i+1)/2 + j -i;
                        arry[i][j] = arr[k];
                    }
                    else
                    {
                        k = N*(N+1)/2;
                        arry[i][j] = arr[k];
                    }
                }
            }
            for (i = 0; i < N; ++i)
            {
                for (j = 0; j < N; ++j)
                    printf("%-5d", arry[i][j]);
                
                printf("\n");
            }
            
            return 0;
        }
        
        輸出結果：
        1    2    3    4    5
        0    6    7    8    9
        0    0    10   11   12
        0    0    0    13   14
        0    0    0    0    15 
         
        
    對角矩陣：（數學上的問題 <-0-0->） 
        也稱為帶狀矩陣，就是所有的非零元素都集中在以對角線為中心的帶狀 
        區域内（對角線的個數位奇數），即除了主對角線和主對角線上下若幹
        條對角線的元素外，其它元素均為常數 c . 
*/ 

/*
假設已有一個 n*n 的 上三角矩陣 A ，且上三角矩陣 A 的元素已按行為主序連續壓縮 
存放在數組 B 中，設計一個算法，将 B 中的元素案列為主序連續壓縮存放在數組 C中
         1 2  3  4  5 
         0 6  7  8  9
A(5*5) = 0 0 10 11 12 
         0 0  0 13 14
         0 0  0  0 15   
其中 B = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0},
     C = { 1, 2, 6, 3, 7, 10, 4, 8, 11, 13, 5, 9, 12, 14, 15, 0}.
     
思路：将一維數組B還原成二維數組A，再将二維數組儲存在C中
*/ 

# include <stdio.h>
# define N 5

void Trans_To_Original(int arry[N][N], int * arr);
void Trans_To_Compress(int arry[N][N], int * arr);
void Show(int arry[N][N], int * arr1, int * arr2); 

int main(void)
{
    // 建立一個一維數組儲存已知的以行為主序壓縮後所得元素 
    int B[(N+1)*N/2 + 1] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0};
    int A[N][N] = {0};
    Trans_To_Original(A, B);
    
    // 建立一個一維數組儲存以列為主序壓縮所得的資料
    int C[(N+1)*N/2 + 1];
    Trans_To_Compress(A, C);
    
    // 将三個數組列印輸出 
    Show(A, B, C);
    
    return 0;
}

void Trans_To_Original(int arry[N][N], int * arr)
{
    int i, j, k;
    for (i = 0; i < N; ++i)
    {
        for (j = 0; j < N; ++j)
        {
            if (i <= j)
            {
                k = i*(2*N-i+1)/2 + j -i;
                arry[i][j] = arr[k];
            }
            else
            {
                k = N*(N+1)/2;
                arry[i][j] = arr[k];
            }
        }
    }
    
    return;
}

void Trans_To_Compress(int arry[N][N], int * arr)
{
    int i, j, k = 0;
    // 按列為主序壓縮 
    for (i = 0; i < N; ++i)
    {
        for (j = 0; j <= i; ++j)
        {
            arr[k++] = arry[j][i];
        }
    }
    arr[(N+1)*N/2] = 0;
    
    return;
}

void Show(int arry[N][N], int * arr1, int * arr2)
{
    int i, j, k;
    printf("原二維數組為：\n");
    for (i = 0; i < N; ++i)
    {
        printf("              ");
        for (j = 0; j < N; ++j)
        {
            printf("%-5d", arry[i][j]);
        }
        printf("\n");
    }
    printf("以行為主序壓縮所得結果為：\n");
    for (k = 0; k < (N+1)*N/2; ++k)
    {
        printf("%-3d", arr1[k]);
    }
    printf("\n以列為主序壓縮所得結果為：\n");
    for (k = 0; k < (N+1)*N/2; ++k)
    {
        printf("%-3d", arr2[k]);
    }
    printf("\n");
    
    return;
}