鄔恩杰 張靜
摘要:帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)是稀疏矩陣壓縮存儲(chǔ)的一種實(shí)用的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。文中描述了稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)及基于此鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的相加運(yùn)算算法,并應(yīng)用C++類模板完成矩陣相加算法的具體實(shí)現(xiàn),對(duì)類中參數(shù)的抽象化,提高了程序代碼的復(fù)用性。
關(guān)鍵詞:稀疏矩陣;行指針數(shù)組;鏈表存儲(chǔ)結(jié)構(gòu);矩陣相加算法
中圖分類號(hào):TP311 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2016)36-0035-03
1稀疏矩陣
矩陣在科學(xué)計(jì)算中的應(yīng)用十分廣泛,而且隨著計(jì)算機(jī)應(yīng)用的發(fā)展,大量出現(xiàn)處理高階矩陣問(wèn)題,有的甚至達(dá)到幾十萬(wàn)階、幾千億個(gè)元素,這就有點(diǎn)要挑戰(zhàn)計(jì)算機(jī)的內(nèi)存容量了。然而,在大量的高階矩陣問(wèn)題中,絕大部分元素是零值,且非零值的分布沒(méi)有一定的規(guī)律。當(dāng)非零元素所占比例小于等于25%~30%時(shí),我們稱這種含有大量零元素的矩陣為稀疏矩陣。壓縮這種零元素占據(jù)的空間,節(jié)省內(nèi)存同時(shí)能夠避免大量零元素進(jìn)行的無(wú)意義運(yùn)算,大大提高運(yùn)算效率。[1]
稀疏矩陣壓縮存儲(chǔ)的順序方式有三元組表、偽地址表示法等;鏈?zhǔn)浇Y(jié)構(gòu)有十字鏈表結(jié)構(gòu)、帶行指針數(shù)組的鏈表結(jié)構(gòu)等。本文著重介紹帶行指針數(shù)組的鏈表結(jié)構(gòu)及基于此結(jié)構(gòu)的稀疏矩陣類對(duì)象構(gòu)造、輸入、輸出、相加等基本算法。
2稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)[2]
稀疏矩陣中的每行對(duì)應(yīng)一個(gè)單鏈表,每個(gè)單鏈表都有個(gè)表頭指針,為了便于訪問(wèn)每一個(gè)單鏈表,需要使用一個(gè)行指針數(shù)組,該數(shù)組中的第i個(gè)元素用來(lái)存儲(chǔ)矩陣中第i行對(duì)應(yīng)的單鏈表的表頭指針,該指針指向第i行第一個(gè)非零結(jié)點(diǎn),若該行無(wú)非零元,則該指針為空。
帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)中,把具有相同行號(hào)的三元組結(jié)點(diǎn)按照列號(hào)從小到大的順序鏈接成一個(gè)單鏈表,每個(gè)結(jié)點(diǎn)由3個(gè)域組成:非零元所在列的列號(hào)(col),非零元的值(value)及指向本行下一個(gè)非零元的指針(next)。例如,稀疏矩陣A6×7如圖1及其帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)如圖2所示。
3稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)類型
3.1結(jié)點(diǎn)類定義
稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)中每一個(gè)非零元結(jié)點(diǎn)的類的C++模板如下:[3]
template
structTripleNode
{int col;
T value;
TripleNode
TripleNode
{col=x.col;value=x.value;next=NULL;return *this;}}
3.2帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)表示的稀疏矩陣類
帶行指針的單鏈表存儲(chǔ)結(jié)構(gòu)表示的稀疏矩陣類包含稀疏矩陣行數(shù)、列數(shù)及非零元個(gè)數(shù)及動(dòng)態(tài)行指針數(shù)組4個(gè)私有成員及稀疏矩陣的構(gòu)造函數(shù)、析構(gòu)函數(shù)、輸入、輸出、轉(zhuǎn)置、相加、相乘等公有成員函數(shù)的聲明,類的C++模板如下:
template
classSparseMatrix
{private:
int Rows,Cols,Terms;
TripleNode
public:
SparseMatrix(int rc,int cc,int tc);
~SparseMatrix(){delete []PROWS;}
void Add(SparseMatrix
void create_SparseMatrix();
void print_SparseMatrix();};
4基于帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)基本運(yùn)算
4.1構(gòu)造函數(shù)
template
SparseMatrix(intrc,intcc,inttc)
{ Rows=rc; Cols=cc; Terms=tc;
PROWS=newTwo_tuple
for (intI=0;I 4.2 建立帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu) 在實(shí)例化稀疏矩陣時(shí)通過(guò)構(gòu)造函數(shù)建立只有行指針數(shù)組的空的稀疏矩陣。在此基礎(chǔ)上按行優(yōu)先,列號(hào)從小到大順序輸入非零元所在行、列和值,申請(qǐng)一個(gè)結(jié)點(diǎn)所需存儲(chǔ)空間,并將非零元的列號(hào)和值存入相應(yīng)域,按列號(hào)從小到大的順序?qū)⒋私Y(jié)點(diǎn)插入到對(duì)應(yīng)行尾部。構(gòu)造函數(shù)及建立鏈表結(jié)構(gòu)代碼: template voidcreate_SparseMatrix() { int r,c; T v; Two_tuple for (int i=0;i {cin>>r>>c>>v; s=newTwo_tuple s->col=c;s->value=v;s->next=NULL; p=PROWS[r]; q=p; while(p) { q=p;p=p->next;} if (p==q){ PROWS[r]=s;} else { q->next=s;}}} 4.3 基于帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)稀疏矩陣相加算法
兩個(gè)矩陣相加前提條件是兩個(gè)矩陣行數(shù)和列數(shù)分別對(duì)應(yīng)相等。相加的結(jié)果仍是同型矩陣。設(shè)有兩個(gè)m×n矩陣A和B,相加結(jié)果設(shè)為C,也是一個(gè)m×n的矩陣。對(duì)于C中每個(gè)元素C[i][j]有以下三種情況:[4]
[CIJ=aijbijaij+bijbij=0aij=0aij=0且bij=0 ]
在帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)稀疏矩陣相加算法思想是:分別建立矩陣A和B的帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)。相加算法從矩陣的第一行起逐行進(jìn)行。對(duì)每一行都從行鏈表的頭指針開(kāi)始,分別找到A和B在該中的第一個(gè)非零元結(jié)點(diǎn)后開(kāi)始比較,然后按不同情況分別處理。設(shè)兩個(gè)指針p和q分別初始化為指向A、B鏈表存儲(chǔ)結(jié)構(gòu)的第一行第一個(gè)非零元結(jié)點(diǎn),當(dāng)p、q都非空時(shí)(意味著p、q所指的當(dāng)前行沒(méi)有遍歷到行尾),生成C中結(jié)點(diǎn)s的三種情況可按如下處理。
1)若p->col < q->col或者 q==NULL時(shí),則將p結(jié)點(diǎn)數(shù)據(jù)復(fù)制到s,p指針向右移動(dòng),指向本行下一個(gè)非零元。
2)若p->col > q->col或者 p==NULL時(shí),則將q結(jié)點(diǎn)數(shù)據(jù)復(fù)制到s,q指針向右移動(dòng),指向本行下一個(gè)非零元。
3)若p->col == q->col且p->value + q->value[≠]0,則將q結(jié)點(diǎn)數(shù)據(jù)復(fù)制到s,s->value=p->value+q->value, p和q指針?lè)謩e向右移動(dòng),指向各自行下一個(gè)非零元。
同理,如此重復(fù)處理其余每一行,直到所有結(jié)點(diǎn)都被合并到結(jié)果矩陣中。
template
voidAdd(SparseMatrix
{ TripleNode
int i;
T v;
if (Rows != b.Rows||Cols != b.Cols)
{ cerr<<"Incompatible Matrix!"< for ( i =0;i { p = PROWS[i]; q = b.PROWS[i]; while(p && q) { s=newTripleNode if (p->col< q->col) { *s=*p;C.insert(i,s); C.Terms++;p=p->next;} elseif (p->col> q->col) { *s=*q;C.insert(i,s); C.Terms++;q=q->next;} else {v=p->value+q->value; if (v) { *s=*p;s->value=v;C.insert(i,s);C.Terms++;} p=p->next;q=q->next;}} while(p) { s=newTripleNode C.insert(I,s);C.Terms++;p=p->next;} while(q) { s=newTripleNode C.insert(i,s);C.Terms++;q=q->next; } }} 4.4 基于帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)的稀疏矩陣輸出算法 從行指針數(shù)組的第一行開(kāi)始,逐行遍歷并輸入鏈表中非零元的三元組形式。 template voidprint_SparseMatrix() {Two_tuple cout<<"rows:"< for (int i =0;i { p=PROWS[i]; while(p) { cout<<"("<col<<","< p=p->next;}}} 5算法性能分析 在稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)上,建立單鏈表存儲(chǔ)結(jié)構(gòu)的算法時(shí)間復(fù)雜度是O(Rows+Terms)。相加算法的主要過(guò)程是對(duì)A和B單鏈表逐行進(jìn)行掃描,其時(shí)間性能主要取決于A、B的行數(shù)Rows和非零元素的個(gè)數(shù)Terms,因此,該矩陣相加算法時(shí)間復(fù)雜度為O(2*Rows+A.Terms+B.terms)。當(dāng)稀疏矩陣的非零元素的個(gè)數(shù)Terms遠(yuǎn)遠(yuǎn)小于矩陣的行、列數(shù)時(shí),矩陣相加算法的時(shí)間復(fù)雜度比采用二維數(shù)組存儲(chǔ)時(shí)的時(shí)間復(fù)雜度O(Rows [× ]Cols)要好很多。 參考文獻(xiàn): [1] 李平,王秀英.計(jì)算機(jī)軟件技術(shù)基礎(chǔ)[M].北京:機(jī)械工業(yè)出版社,2015:61-63。 [2] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程(C/C++描述)[M].北京:清華大學(xué)出版社,2004:98-99. [3] 鄭莉,董淵,何江舟.C++語(yǔ)言程序設(shè)計(jì)[M].北京:清華大學(xué)出版社,2010:309-314. [4] 張小莉,王苗,羅文劼.數(shù)據(jù)結(jié)構(gòu)與算法[M].3版.北京:機(jī)械工業(yè)出版社,2016:97-98.