稀疏矩陣的存儲壓縮稀疏矩陣的存儲壓縮1稀疏矩陣

(SparseMatrix)行數m=6,列數n=7,非零元素個數t=6

2.4稀疏矩陣稀疏矩陣(SparseMatrix)行數m=6,2稀疏矩陣(SparseMatrix)的抽象數據類型

template<classType>class

SparseMatrix

{

int

Rows,Cols,Terms;//行/列/非零元素數

Trituple<Type>smArray[MaxTerms];public://三元組表

SparseMatrix(int

MaxRow,intMaxcol);

SparseMatrix<Type>Transpose();//轉置

SparseMatrix<Type>//相加

Add(SparseMatrix<Type>b);SparseMatrix<Type>//相乘

Multiply(SparseMatrix<Type>b);}

稀疏矩陣(SparseMatrix)的抽象數據類型3A的三元組順序表圖示

A

=

0

12

9

00000000000-3

0000

14

000

24

00000

18

0000015

00

-7

000rowcolval01234567831-3611512125218139432464-73614A的三元組順序表圖示A=0129004

三元組(Trituple)類的定義

template<classType>class

SparseMatrix<Type>;template<classType>class

Trituple{

friendclass

SparseMatrix<Type>private:

int

row,col; //非零元素所在行號/列號Typevalue;//非零元素的值}

三元組(Trituple)類的定義5稀疏矩陣轉置矩陣稀疏矩陣轉置矩陣6用三元組表表示的稀疏矩陣及其轉置用三元組表表示的稀疏矩陣及其轉置7稀疏矩陣轉置算法思想設矩陣列數為Cols，對矩陣三元組表掃描Cols次。第k次檢測列號為k的項。第k次掃描找尋所有列號為k的項，將其行號變列號、列號變行號，順次存于轉置矩陣三元組表。設矩陣三元組表總共有Terms項，其時間代價為O(Cols*Terms)。若矩陣有200行，200列，10,000個非零元素，總共有2,000,000次處理。稀疏矩陣轉置算法思想設矩陣列數為Cols，對矩陣三元組表掃8稀疏矩陣的轉置

template<classType>SparseMatrix<Type>SparseMatrix<Type>::Transpose(){

SparseMatrix<Type>b(Cols,Rows);

b.Rows=Cols;

b.Cols=Rows;

b.Terms=Terms;

//轉置矩陣的列數,行數和非零元素個數

if(Terms>0){

int

CurrentB=0;

//轉置三元組表存放指針稀疏矩陣的轉置9

for(intk=0;k<Cols;k++)

for(inti=0;i<Terms;i++)

if(smArray[i].col==k

){ b.smArray[CurrentB].row=k;

b.smArray[CurrentB].col=smArray[i].row;

b.smArray[CurrentB].value=smArray[i].value;

CurrentB++;

}}

returnb;}for(intk=0;k<10用三元組表表示的稀疏矩陣及其轉置用三元組表表示的稀疏矩陣及其轉置11快速轉置算法建立輔助數組rowSize和rowStart，記錄矩陣轉置后各行非零元素個數和各行元素在轉置三元組表中開始存放位置。掃描矩陣三元組表，根據某項的列號，確定它轉置后的行號，查rowStart表，按查到的位置直接將該項存入轉置三元組表中。轉置時間代價為O(max(Terms,Cols))。若矩陣有200列，10000個非零元素，總共需要10000次處理?？焖俎D置算法建立輔助數組rowSize和rowStar12

for(inti=0;i<Cols;i++)rowSize[i]=0; for(i=0;i<Terms;i++)rowSize[smArray[i].col]++;

rowStart[0]=0; for(i=1;i<Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1];for(inti=0;i<Cols;i+13稀疏矩陣的快速轉置template<classType>SparseMatrix<Type>SparseMatrix<Type>::FastTranspos(){

int

*rowSize=newint[Cols];

int*rowStart=

newint[Cols];

SparseMatrix<Type>b(Cols,Rows);

b.Rows=Cols;b.Cols=Rows;

b.Terms=Terms;if(Terms>0){for(inti=0;i<Cols;i++)rowSize[i]=0;for(i=0;i<Terms;i++)

rowSize[smArray[i].col]++;稀疏矩陣的快速轉置14

rowStart[0]=0;

for(i=1;i<Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1]; for(i=0;i<Terms;i++){

intj=rowStart[smArray[i].col];

b.smArray[j].row=smArray[i].col; b.smArray[j].col=smArray[i].row; b.smArray[j].value=smArray[i].value;

rowStart[smArray[i].col]++;

}}

delete

[]rowSize;

delete[]rowStart;

returnb;} rowStart[0]=0; 15稀疏矩陣在矩陣操作(+、-、*、/)時矩陣非零元素會發生動態變化，用稀疏矩陣的鏈接表示可適應這種情況。稀疏矩陣的鏈接表示采用正交鏈表：行鏈表與列鏈表十字交叉。行鏈表與列鏈表都是帶表頭結點的循環鏈表。用表頭結點表征是第幾行，第幾列。稀疏矩陣在矩陣操作(+、-、*、/)時矩陣非零元素會發生動態16稀疏矩陣的結點

headdownnextright(a)表頭結點(b)非零元素結點rightvaluedownheadrawcola[i][j]Falseij(c)建立a[i][j]結點

稀疏矩陣的結點

headdownnextright17稀疏矩陣的正交鏈表表示的示例稀疏矩陣的正交鏈表表示的示例18稀疏矩陣的鏈表表示的類定義enum

Boolean

{False,True};struct

Triple{introw,col;

floatvalue;};class

Matrix;class

MatrixNode{//矩陣結點定義friendclassMatrix;friendistream&operator>>(istream&,

Matrix&

); //矩陣輸入重載函數private:

MatrixNode*down,*right;

//列/行鏈指針

Booleanhead;//結點類型稀疏矩陣的鏈表表示的類定義19

Union

{Tripletriple;MatrixNode*next;}

//矩陣元素結點(False)或鏈頭結點(True)

MatrixNode(Boolean,Triple*);

//結點構造函數

}MatrixNode::MatrixNode(Booleanb,Triple*t){//矩陣結點構造函數

head=b;

//結點類型

if(b)

{right=next=this;}

else

triple=*t;}Union{Tripletriple;M20typedef

MatrixNode*MatrixNodePtr;//一個指針數組,用于建立稀疏矩陣

class

Matrix{

friendistream&

operator>>(istream&,Matrix&);//矩陣輸入public:

~Matrix(); //析構函數private:

MatrixNode*headnode;

//稀疏矩陣的表頭};typedefMatrixNode*MatrixNode21用正交鏈表表示的稀疏矩陣的建立istream&

operator

>>(istream

&is,Matrix&matrix){

Triples;

intp;

is>>s.row>>s.col>>s.value;

//輸入矩陣的行數,列數和非零元素個數

if(s.row>s.col)p=s.row;

else

p=s.col;//取行、列數大者

matrix.headnode=

//整個矩陣表頭結點

new

MatrixNode(False,

&s);

if

(!p){

//零矩陣時

matrix.headnode→right=matrix.headnode;

用正交鏈表表示的稀疏矩陣的建立22

return

is;

}

MatrixNodePtr*H=

new

MatrixNodePtr(p);

//建立表頭指針數組,指向各鏈表的表頭

for(inti=0;i<p;i++)

H[i]=

new

MatrixNode(True,0);

intCurrentRow=0;

MatrixNode*last=H[0];//當前行最后結點

for

(i=0;i<s.value;i++){ //建立矩陣

Triplet;

is>>t.row>>t.col>>t.value;

//輸入非零元素的三元組

returnis;23

if(t.row>CurrentRow)

{

//如果行號大于當前行,閉合當前行

last→right=H[CurrentRow];

CurrentRow=t.row;

last=H[CurrentRow]; }

last=last→right=

//鏈入當前行

new

MatrixNode(False,&t);

H[t.col]→next=H[t.col]→next→down=last;//鏈入列鏈表

}

last→right=H[CurrentRow];//閉合最后一行if(t.row>CurrentRo24

//閉合各列鏈表

for(i=0;i<s.col;i++)

H[i]→next→down=H[i];

//鏈接所有表頭結點

for

(i=0;i<p-1;i++)

H[i]→next=H[i+1];

H[p-1]→next=matrix.headnode;

matrix.headnode→right=H[0];

delete[]H;

returnis;}//閉合各列鏈表25稀疏矩陣的刪除為執行稀疏矩陣的刪除，需要使用可利用空間表來管理回收的空間?？衫每臻g表是單鏈表結構，只允許在表頭插入或刪除，其表頭指針為av。