（1）、目的：對于在實際問題中出現(xiàn)的大型的稀疏矩陣，若用常規(guī)分配方法在計算機中儲存，將會產(chǎn)生大量的內(nèi)存浪費，而且在訪問和操作的時候也會造成大量時間上的浪費，為了解決這一問題，從而善生了多種解決方案。

（2）、由于其自身的稀疏特性，通過壓縮可以大大節(jié)省稀疏矩陣的內(nèi)存代價。具體操作是：將非零元素所在的行、列以及它的值構(gòu)成一個三元組（i,j,v），然后再按某種規(guī)律存儲這些三元組，這種方法可以節(jié)約存儲空間。

具體如下圖：

#define SMAX 1000
typedef struct
{
    int i,j;     //儲存非零元素的行和列信息
    ElementType e; //非零元素的值
} Triple;       //定義三元組類型
typedef struct
{
    int mu,nu,tu; //矩陣的行、列和非零元素的個數(shù)
    Triple data[SMAX]; //三元組表
} TSMatrix；

注意：為更可靠描述，通常再加一個“總體”信息：即總行數(shù)、總列數(shù)、非零元素總個數(shù)。

用常規(guī)的二維數(shù)組表示時的算法：

for (col=1; col<=nu; ++col)
{
    for (row=1; row<=mu; ++row)
    {
        T[col][row] = M[row][col];
    }
}

其時間復(fù)雜度為: O(mu×nu)

用三元組表示如何實現(xiàn)呢？

解決思路：只要做到
將矩陣行、列維數(shù)互換
將每個三元組中的i和j相互調(diào)換
重排三元組次序，使mb中元素以N的行(M的列) 為主序

方法一：按列序轉(zhuǎn)置

即按mb中三元組次序依次在ma中找到相應(yīng)的三元組進行轉(zhuǎn)置。為找到M中每一列所有非零元素，需對其三元組表ma從第一行起掃描一遍。由于ma中以M行序為主序,所以由此得到的恰是mb中應(yīng)有的順序。

void TransposeTSMatrix(TSMatrix  A,  TSMatrix  * B)
{
    /*求矩陣A的轉(zhuǎn)置矩陣B，矩陣用三元組表表示*/
    int  p,q, k ;
    B->mu= A.nu ;
    B->nu= A.mu ;
    B->tu= A.tu ;
    if(B->tu)///整個矩陣非零元素的個數(shù)不為0
    {
        q=1;
        for(k=1; k<=A.nu; k++)///遍歷A矩陣的列數(shù)
        {
            for(p=1; p<=A.tu; p++)///遍歷矩陣A的三元組
            {
                if(A.data[p].j==k)///矩陣的列與三元組的列對應(yīng)
                {
                    B->data[q].i=A.data[p].j;
                    B->data[q].j=A.data[p].i;
                    B->data[q].e=A.data[p].e;
                    q++;
                }
            }
        }
    }
}

時間復(fù)雜度：O（nu*tu)

方法二：快速轉(zhuǎn)置

即按ma中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入b中恰當(dāng)位置
此法關(guān)鍵是要預(yù)先確定M中每一列第一個非零元在mb中位置，
為確定這些位置，轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個數(shù)

實現(xiàn)：設(shè)兩個數(shù)組

num[col]：表示矩陣M中第col列中非零元個數(shù)
cpot[col]：指示M中第col列第一個非零元在mb中位置

其中：

cpot[1]=1;

cpot[col]=cpot[col-1]+num[col-1]; (2<=col <=ma[0].j)

FastTransposeTSMatrix (TSMatrix  A,  TSMatrix  * B)
{
    /*基于矩陣的三元組表示，采用快速轉(zhuǎn)置法，求矩陣A的轉(zhuǎn)置矩陣B */
    int col,t,p,q;
    int num[MAXSIZE+1];///A每一列中非零元素的個數(shù)
    int cpot[MAXSIZE+1];///A每一列中第一個非零元素在B中的位置
    B->tu= A.tu ;
    B->nu= A.mu ;
    B->mu= A.nu ;
    if(B->tu)
    {
        for(col=1; col<=A.nu; col++)///初始化
        {
            num[col]=0;
        }
        for(t=1; t<=A.tu; t++)
        {
            num[A.data[t].j]++; /*計算每一列的非零元素的個數(shù)*/
        }
        cpot[1]=1;
        for(col=2; col<=A.nu; col++)
        {
            /*求col列中第一個非零元素在B->data[ ]中的正確位置*/
            cpot[col]= cpot[col-1]+num[col-1];
        }
        for(p=1; p<=A.tu; p++)///遍歷三元組A
        {
            col=A.data[p].j;///col記錄當(dāng)前所處的列
            q=cpot[col];///q代表每一列第一個非零元素
            B->data[q].i=A.data[p].j;
            B->data[q].j=A.data[p].i;
            B->data[q].e=A.data[p].e;
            cpot[col]++;
            ///將A中每一列的第一個元素定位確定后，若這一列之后還有的元素那位置必然在第一個元素對應(yīng)三元組位置的后面
        } 
    } 
} 

總結(jié)

以上是生活随笔為你收集整理的数据结构——稀疏矩阵三元组表示法+算法详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。