多維數組-矩陣的壓縮存儲- 稀疏矩陣（二）

　　帶行表的三元組表

　　為了方便某些矩陣運算在按行優先存儲的三元組表中加入一個行表來記錄稀疏矩陣中每行的非零元素在三元組表中的起始位

　　置這就是帶行表的三元組表

　　()類型描述

　　#define MaxRow l //在三元組表定義前加入此最大行定義

　　typedef struct {

　　TriTupleNode data[MaxSize];

　　int RowTab[MaxRow];//行表應保證m≤MaxRow

　　int mnt;

　　}RTriTupleTable;

　　()帶行表的三元組表的操作

　　① 對於任給行號i(≤i≤m)能迅速地確定該行的第一個非零元在三元組表中的存儲位置為RowTab[i]

　　② RowTab[i](≤i≤m)表示第i行之前的所有行的非零元數

　　③ 第i行上的非零元數目為RowTab[i+]RowTab[i](≤i≤m)

　　④ 最後一行(即第ml行)的非零元數目為tRowTab[m](t為矩陣的非零元總數)

　　注意

　　若在行表中令RowTab[m]=t(要求MaxRow>m)會更方便 些且t可省略

　　帶行表的三元組表可改進矩陣的轉置算法具體【參閱其它參考書】

　　稀疏矩陣壓縮存儲方式分析

　　() 三元組表和帶行表的三元組表的特點

　　相應的算法描述較為簡單但這類順序存儲方式對於非零元的位置或個數經常發生變化的矩陣運算就顯得不太適合

　　【例】執行將矩陣B相加到矩陣A上的運算時某位置上的結果可能會由非零元變為零元但也可能由零元變為非零元這就會

　　引起在A的三元組表中進行刪除和插人操作從而導致大量結點的移動對此類運算采用鏈式存儲結構為宜

　　()稀疏矩陣的鏈式結構

　　稀疏矩陣的鏈式結構有十字鏈表等方法適用於非零元變化大的場合 比較復雜可【參閱其它參考書】

From:http://tw.wingwit.com/Article/program/sjjg/201311/23896.html