鄔恩杰　張靜

摘要：帶行指針數(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*next；

TripleNode& operator=（TripleNode&x）

{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 **PROWS；

public：

SparseMatrix（int rc，int cc，int tc）；

～SparseMatrix（）{delete []PROWS；}

void Add（SparseMatrix&b，SparseMatrix&c）；

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 *[Rows]；

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 *p，*q，*s；

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&b，SparseMatrix&C）

{ TripleNode *p，*q，*s，*t；

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 ； *s=*p；

C.insert（I，s）；C.Terms++；p=p->next；}

while（q）

{ s=newTripleNode ；*s=*q；

C.insert（i，s）；C.Terms++；q=q->next； } }}

4.4 基于帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)的稀疏矩陣輸出算法

從行指針數(shù)組的第一行開(kāi)始，逐行遍歷并輸入鏈表中非零元的三元組形式。

template

voidprint_SparseMatrix（）

{Two_tuple *p；

cout<<"rows："<

for （int i =0；i

{ p=PROWS[i]；

while（p）

{ cout<<"（"<col<<"，"<value<<'）'<

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.