可將二維數(shù)組的行為主序和列為主序的存儲(chǔ)方式推廣到一般情況，可得到 n 維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系

3.特殊矩陣的壓縮存儲(chǔ)

宗旨：為值相同的矩陣元素只分配一個(gè)空間，對(duì)零元不分配存儲(chǔ)空間.

(1) 特殊矩陣：非零元在矩陣中的分布有一定規(guī)則

1. 上（下）三角矩陣
2. 對(duì)稱矩陣
3. 對(duì)角矩陣

(2.)稀疏陣：零元多，分布無規(guī)律

（1）. 上三角矩陣—列為主序壓縮存儲(chǔ)

存儲(chǔ)方式：列為主序壓縮存儲(chǔ)和行為主序壓縮存儲(chǔ)，存儲(chǔ)空間是一維的，將二維數(shù)組以一維方式存儲(chǔ)。
特點(diǎn)：均可以隨機(jī)訪問數(shù)組元素。

上三角矩陣—列為主序壓縮存儲(chǔ)–數(shù)組sa[M]

(1)下三角為0時(shí)：
當(dāng)i≤j時(shí)，aij為非0元，存放地址Loc(aij)的計(jì)算公式：
$$Loc(a_{ij})=Loc(a_{11})+(\frac{(j?1)?j}{2}+i?1)?L,(condition:i\le j)$$

一維存儲(chǔ)空間用一維數(shù)組sa[M]表示， Loc(aij)計(jì)算公式（a11存于sa[0],地址為0 ）：
$$Loc(a_{ij})=0+(\frac{(j?1)?j}{2}+i?1)?1,(condition:i\le j)$$
數(shù)組sa的大小:$$M=\frac{(n+1)?n}{2}$$

aij(i≤j)存于下標(biāo)為k的一維數(shù)組元素中:
$$Loc(aij)=k=\frac{(j?1)?j}{2}+i?1$$

(2)下三角為常數(shù)時(shí)：
常數(shù)的存放的位置為：$$\frac{(n+1)?n}{2}$$
數(shù)組sa的大小:$$M=\frac{(n+1)?n}{2}+1$$

（2）. 下三角矩陣—行為主序壓縮存儲(chǔ)

存儲(chǔ)方式：列為主序壓縮存儲(chǔ)和行為主序壓縮存儲(chǔ)，存儲(chǔ)空間是一維的，將二維數(shù)組以一維方式存儲(chǔ)。
行為主序壓縮存儲(chǔ)：從第一行開始依次存放每一行的“非0（C）元”

特點(diǎn)：均可以隨機(jī)訪問數(shù)組元素。

下三角矩陣—行為主序壓縮存儲(chǔ)–數(shù)組sa[M]

(1)上三角為0時(shí)：
當(dāng) j≤i時(shí)，aij為非0元，存放地址Loc(aij)的計(jì)算公式：
$$Loc(a_{ij})=Loc(a_{11})+(\frac{(i?1)?i}{2}+j?1)?L,(condition:j\le i)$$

一維存儲(chǔ)空間用一維數(shù)組sa[M]表示， Loc(aij)計(jì)算公式（a11存于sa[0],地址為0 ）：
$$Loc(a_{ij})=0+(\frac{(i?1)?i}{2}+j?1)?1,(condition:j\le i)$$
數(shù)組sa的大小:$$M=\frac{(n+1)?n}{2}$$

aij(i≤j)存于下標(biāo)為k的一維數(shù)組元素中:
$$Loc(aij)=k=\frac{(i?1)?i}{2}+j?1$$

上三角為常數(shù)時(shí)：
常數(shù)的存放的位置為：$$\frac{(n+1)?n}{2}$$
數(shù)組sa的大小:$$M=\frac{(n+1)?n}{2}+1$$

（3）. 對(duì)稱矩陣

存放方式：只存上三角陣或只存下三角陣都可以

地址計(jì)算公式 : 參考上三角和下三角矩陣的地址計(jì)算公式

（4）. 對(duì)角矩陣

對(duì)角矩陣 –2d+1對(duì)角陣：主對(duì)角線和主對(duì)角線上面d條對(duì)角線、主對(duì)角線下面d條對(duì)角線上的數(shù)據(jù)元素分布不規(guī)律，非0（C）.

2d+1 對(duì)角陣特點(diǎn)：**第一行和最后一行每行有d+1個(gè)數(shù)據(jù)元素**，余下每行**最多**2d+1個(gè)數(shù)據(jù)元素

壓縮存儲(chǔ)方法：第一行和最后一行每行存 d+1 個(gè)數(shù)據(jù)元素，余下每行存 2d+1 個(gè)數(shù)據(jù)元素

2d+1-對(duì)角陣行為主序壓縮存儲(chǔ)地址計(jì)算公式：
矩陣元素下標(biāo)從0開始的地址計(jì)算公式：
$$Loc(a_{ij})=Loc(a_{00})+(2d+1)?i?d+j?(i?d)=Loc(a_{00})+(2d+1)?i+j?i$$
$$0\le i,j<n,|i?j|\le d$$

§矩陣元素下標(biāo)從1開始的地址計(jì)算公式：
$$Loc(a_{ij})=Loc(a_{11})+(2d+1)?(i?1)?d+j?i+d=Loc(a_{11})+(2d+1)?(i?1)+j?i$$
$$1\le i,j\le n,|i?j|\le d$$

4. 稀疏矩陣

稀疏矩陣: 矩陣元素零元多，在矩陣中隨機(jī)出現(xiàn)
假設(shè) m行 n列的矩陣含 t個(gè)非零元素,則稀疏因子：$$\delta =\frac{t}{m?n}$$
通常認(rèn)為 δ ≤ 0.05 的矩陣為稀疏矩陣。

壓縮存儲(chǔ)原則：只存儲(chǔ)每個(gè)非零元的行、列下標(biāo)及其值和矩陣的行列維數(shù)

常規(guī)存儲(chǔ)方法缺點(diǎn):

(1) 零值元素占了很大空間;
(2) 計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。

解決問題的原則:

(1) 盡可能少存或不存零值元素；
(2) 盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；
(3) 操作方便。 即：盡可能快地找到與下標(biāo)值(i,j)對(duì)應(yīng)的元素，盡可能快地找到同一行或同一列的非零值元。

5. 稀疏矩陣的壓縮

稀疏矩陣的壓縮存儲(chǔ)方法:

1. 三元組順序表
2. 行邏輯聯(lián)接的順序表
3. 十字鏈表

（1）. 三元組順序表

三元表結(jié)構(gòu)：

//三元表結(jié)構(gòu)：
typedef struct{  
    int i, j;       //非零元的行、列下標(biāo) 
    int e;   //非零元的值
} Triple;

//稀疏矩陣的結(jié)構(gòu)
#define MAXSIZE 100  //非零元最大個(gè)數(shù)
typedef struct{  
    Triple data[MAXSIZE + 1];       //三元組表，data[0]未用
    int mu, nu, tu; //矩陣行、列數(shù)、非零元個(gè)數(shù)
} TSMatrix;

特點(diǎn)：
有序的雙下標(biāo)法行序有序存儲(chǔ)
便于進(jìn)行依行順序處理的矩陣運(yùn)算
若需存取某一行中的非零元，需**從頭開始查找**。

壓縮存儲(chǔ)后，元素aij的存儲(chǔ)位置與其下標(biāo)無關(guān)，而取決于之前的非零元個(gè)數(shù)
非零元以行為主序順序存放

（2）. 行邏輯聯(lián)接的順序表

#define MAXRC 500 
//行邏輯聯(lián)接的順序表
typedef struct {
    Triple data[MAXSIZE + 1];
    int  rpos[MAXRC + 1]; // 每一行非0元存放的起始位置
    int  mu, nu, tu;
} RLSMatrix; // 行邏輯鏈接順序表類型

（3）. 十字鏈表

用三元組表存儲(chǔ)稀疏矩陣，在單純的存儲(chǔ)和做類似轉(zhuǎn)置之類的運(yùn)算時(shí)可以節(jié)約存儲(chǔ)空間，且運(yùn)算速度較快;
但當(dāng)進(jìn)行矩陣相加等運(yùn)算時(shí)，稀疏矩陣的非零元位置和個(gè)數(shù)都會(huì)發(fā)生變化。使用三元組表必然會(huì)引起數(shù)組元素的大量移動(dòng)。

1. 采用鏈表存放稀疏矩陣的非0元
2. 將稀疏矩陣每行的非0元按照列升序的順序放在一個(gè)單鏈表中
3. 將稀疏矩陣每列的非0元按照行升序的順序放在一個(gè)單鏈表中

即：
稀疏矩陣的每個(gè)非0元即位于一個(gè)行單鏈表，也同時(shí)位于一個(gè)列單鏈表
用一維數(shù)組保存每行非0元的單鏈表的頭指針
用一維數(shù)組保存每列非0元的單鏈表的頭指針

十字鏈表 ：每個(gè)非零元用含有五個(gè)域的結(jié)點(diǎn)表示（非零元的所在行、列、值，及同行、同列的下一個(gè)非零元）

//十字鏈表
typedef struct OLNode{ 

    int row, col; //非零元所在行、列
    int val; //非零元的值
    struct OLNode*right, *down;//同行、同列的下一個(gè)非零元
}OLNode,* OLink;

typedef struct{ 
    OLink rhead[M],chead[N]; //行、列指針數(shù)組
    int mu, nu, tu; //行、列數(shù)及非零元個(gè)數(shù)
}CrossList;

6. 稀疏矩陣的轉(zhuǎn)置（普通轉(zhuǎn)置 和 快速轉(zhuǎn)置）

解決思路：

1. 將矩陣行、列維數(shù)互換，非零元個(gè)數(shù)不變
2. 將每個(gè)三元組中的i和j相互調(diào)換，非零元值不變
3. 重排次序，使T.data中元素以T的行(M的列)為主序
   

方法一（普通轉(zhuǎn)置）復(fù)雜度為O(T.mu×T.nu)

按矩陣T中三元組表T.data的次序依次在矩陣M的三元組表M.data中找到相應(yīng)三元組進(jìn)行轉(zhuǎn)置
為找到M.data中第i列所有非零元素，需對(duì)M.data掃描一遍
由于M.data以M行序?yàn)橹餍?，所以得到的恰是T.data中應(yīng)有的順序

//復(fù)雜度為O(T.mu×T.nu)
Status TransposeSMatrix(TSMatrix M, TSMatrix &T){ 
    int col, p, k;
    T.mu=M.nu;  
    T.nu=M.mu; 
    T.tu=M.tu; 
    if(T.tu){ //有非零元，轉(zhuǎn)置
        k=1;//k為T.data表下標(biāo)
        for(col=1;col<=M.nu;col++)//查找M每一列的非零元
            for( p=1;p<=M.tu;p++)//掃描M的所有非零元
                if( M.data[p].j==col ){ 
                    T.data[k].i=M.data[p].j;
                    T.data[k].j=M.data[p].i;
                    T.data[k].e=M.data[p].e; 
                    k++;
                }
        return OK;
    }
    return ERROR;
}

//T(n)=O(M.nu×M.tu)
//若M.tu與M.mu×M.nu同數(shù)量級(jí)則 T(n)=O(M.mu×M.nu^2)

方法二：快速轉(zhuǎn)置 復(fù)雜度O(S.nu+S.tu)

//復(fù)雜度O(S.nu+S.tu) 
//若S.tu與S.mu×S.nu同數(shù)量級(jí)則 T(n)=O(S.mu×S.nu)
void TransPose_F(TSMatrix S,TSMatrix &Transpose_S){
    //S為原來矩陣
    //Transpose_S為轉(zhuǎn)置后矩陣
    Transpose_S.mu=S.nu;
    Transpose_S.nu=S.mu;
    Transpose_S.tu=S.tu;
    if(S.tu){
        //判斷是否為空
        int col;//列
        int num[MAXSIZE]={0};// 記錄原三元組中列號(hào)為 col 的項(xiàng)的數(shù)目。 輔助數(shù)組
        int cpot[MAXSIZE]={0};// 記錄原三元組中列號(hào)為 col 的項(xiàng)在新三元組中的首位置。 輔助數(shù)組
        
        //掃描第一次 記錄元素矩陣S中列數(shù)為j的個(gè)數(shù)
        for(int i=1;i<=S.tu;i++){
            //記錄元素矩陣S中列數(shù)為j的個(gè)數(shù)
            num[S.data[i].j]++;
        }

        cpot[1]=1;//初始化第一個(gè)元素的地址

        //掃描第二次 記錄原三元組中列號(hào)為 col 的項(xiàng)在新三元組中的首位置
        for(col=2;col<=S.nu;col++){
            //列號(hào)為 col 的項(xiàng)在新三元組中的首位置
            cpot[col]=cpot[col-1]+num[col-1];
        }

        //掃描第三次 轉(zhuǎn)置
        for(int t=1;t<=S.tu;t++){
            col=S.data[t].j;//列數(shù)
            int s=cpot[col];//地址  下標(biāo)

            Transpose_S.data[s].e=S.data[t].e;
            Transpose_S.data[s].i=S.data[t].j;
            Transpose_S.data[s].j=S.data[t].i;

            cpot[col]++;//下標(biāo) 后移
        }
    }
}

感謝閱讀！
前幾期期鏈接：文章來源地址http://www.zghlxwxcb.cn/news/detail-845747.html

1. 【數(shù)據(jù)結(jié)構(gòu)】棧與隊(duì)列的概念和基本操作代碼實(shí)現(xiàn)
2. 【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹的概念與基本操作代碼實(shí)現(xiàn)

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】數(shù)組（稀疏矩陣、特殊矩陣壓縮、矩陣存儲(chǔ)、稀疏矩陣的快速轉(zhuǎn)置、十字鏈表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！