大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第四章：多維數(shù)組和廣義表-第二節(jié)-矩陣的壓縮存儲

第二節(jié)矩陣的壓縮存儲

一、特殊矩陣

特殊矩陣：是相同值的元素或者零元素在矩陣中的分布有一定規(guī)律

的矩陣。

1、對稱矩陣

若n階方陣A中的元素滿足下述性質(zhì)：

aij=aji(0<i,j<n-l)

則稱A為n階的對稱矩陣。

對于一個(gè)n階對稱矩陣，可只存儲其下三角矩陣：

/^aoo

aioan

320a21電2

?????????

^3n-103^-11an-ln-^

將元素壓縮存儲至I」1+2+3+…+n=n(n+1)/2個(gè)元素的存儲空間

中，假設(shè)以一維數(shù)組sa[n(n+1)/2]作為n階對稱矩陣A的存儲結(jié)

構(gòu)，以行序?yàn)橹餍虼鎯ζ湎氯?包括對角線)中的元素，數(shù)組M[k]

和a.j的對應(yīng)關(guān)系：

"1+2+3+…-iqT(i+1)/2+j當(dāng)iZj

、j(j+1),2*當(dāng)i<j

真題選解

（例題?單選題）設(shè)有一個(gè)10階的對稱矩陣A,采用行優(yōu)先壓縮存

儲方式，譏1為第一個(gè)元素，其存儲地址為1,每個(gè)元素占一個(gè)字節(jié)空

間，則385的地址為（）

A.13

B.18

C.33

D.40

隱藏答案

【答案】C

【解析】an為第一個(gè)元素，a85是第（1+2+3+4+5+6+7）

+5=33個(gè)元素，則m5的地址為1+（33-1）*1=33。注意不要死記

硬背公式。

（例題算法設(shè)計(jì)題）已知A和B是兩個(gè)nxn階的對稱矩陣，因

為是對稱矩陣，所以僅需要輸入下三角元素值存入一維數(shù)組。試寫一

算法，求對稱矩陣A和B的乘積。

隱藏答案

【分析】對稱矩陣的第i行和第j列的元素?cái)?shù)據(jù)在一維數(shù)組中的位

置：

L=i（i+l）/2+j當(dāng)i習(xí)時(shí)A.,Bij處在下

三角中）；

L=j(j+l)/2+i當(dāng)i<j時(shí)向，Bij處在

上三角中）；

L代表A.或By在對稱矩陣存儲的一維中的位置，而且0W

L<n(n+l)/2

【算法描述】

voidmatrlxmult(inta[],intb[],intc[][20],intn)

{//n為A、B矩陣下三角元素個(gè)數(shù)，a,b分別為一維數(shù)組，

〃存放矩陣A和B的下三角元素值，c存放A和B的乘積

for(i=0;i<20;i++)

for(j=O;j<20;j++)

{s=0;

for(k=0;k<n;k++)

{if(i>=k)〃表示元素為下三角的元

素，計(jì)算在a數(shù)組中的下標(biāo)

Ll=i*(i+l)/2+k;

else〃表示元素為上三角的元

素，計(jì)算下標(biāo)

Ll=k*(k+l)/2+i;

if(k>=j)〃表示元素為下三角的元

素，計(jì)算在b數(shù)組中的下標(biāo)

L2=k*(k+l)/2+j;

else

L2=j*(j+l)/2+k;

s=s+a[Ll]*b[L2];〃計(jì)算矩陣成績

)

c[i][j]=s;

)

)

2.三角矩陣

/aoocc…cA酒0a10^20…an-io

aanccan

10ca21…an-ll

a20a21堰2???ccc322''"a2n-l

????????,??????■■■???

cc

L…。

芝10%-12an-ln-lJc%-lnTJ

下三角矩陣上三角矩陣

下三角矩陣的主對角線上方均為常數(shù)C或零；上三角矩陣是指矩陣

的下三角(不包括對角線)中的元素均為常數(shù)c或是零的n階方陣。一

般情況下，三角矩陣的常數(shù)c均為零。

三角矩陣可壓縮存儲到數(shù)組M[n(n+1)/2+1]中。

上三角矩陣中，主對角線上的第i行有n-i+1個(gè)元素，以行序?yàn)橹?/p>

序存放，M[k]和ag的對應(yīng)關(guān)系是：

一好(11-1)411?2)+…(2n?i+2)2-+j-i當(dāng)iWj

k=<

?n(n+1)/2當(dāng)i習(xí)

下三角矩陣中，以行序?yàn)橹餍虼娣?，與對稱矩陣類是，M[k]和aij

的對應(yīng)關(guān)系是：

ri(i^l)/2+j當(dāng)i為

k=y

、n(n^l)/2當(dāng)i<j

真題選解

(例題?填空題)L假設(shè)一個(gè)10階的上三角矩陣A按行優(yōu)先順序

壓縮存儲在一維數(shù)組B中，若矩陣中的第一個(gè)元素an在B中的存儲

位置k=0,則元素a55在B中的存儲位置k=。

隱藏答案

【答案】34

【解析】元素a55的前面存儲了4行，每行存儲的元素個(gè)數(shù)分別

為：10、9、8、7,元素a55存儲在第5行要存儲的第1個(gè)元素，所

以a55在B中的存儲位置k=0+[(10+9+8+7)+l-l]=34

二、稀疏矩陣

1、稀疏矩陣的定義

含有大量的零元素且零元素分布沒有規(guī)律矩陣稱為稀疏矩陣。

2、三元組表

(1)三元組表的含義：一個(gè)稀疏矩陣可用一個(gè)三元組線性表表

示，每個(gè)三元組元素對應(yīng)稀疏矩陣中的一個(gè)非零元素，包含有該元素

的行號、列號和元素值。每個(gè)三元組元素在線性表中是按照行號值的

升序?yàn)橹餍?、列號值的升序?yàn)檩o序(即行號值相同再按列號值順序)

排列的。

【例】畫出下列稀疏矩陣對應(yīng)的三元組表

<0010\

0500

0000

-7J

00

【解析】根據(jù)前面三元組的含義很容易畫出該矩陣的三元組表。

【答案】

j

021

115

30-4

33-7

(2)三元組表的類型定義

#defineMaxsize1000〃假設(shè)非零元素個(gè)數(shù)的最大為1000個(gè)

typedefstruct

{intij;〃非零元素的行號、列號(下標(biāo))

DataTypev;〃非零元素值

}TriTupleNode;

typedefstruct

{TriTupleNodedata[Maxsize];/府儲三元組的數(shù)組

intm,n,t;〃矩陣的行數(shù)、列數(shù)和非零元素個(gè)數(shù)

}TSMatrix;〃稀疏矩陣類型

【例】試寫一個(gè)算法，建立順序存儲稀疏矩陣的三元組表。

【分析】假設(shè)A為一個(gè)稀疏矩陣，其數(shù)據(jù)存儲在二維數(shù)組a中，b

為一個(gè)存放對應(yīng)于A矩陣生成的三元組表。在這個(gè)算法中，要進(jìn)行二

重循環(huán)來判斷每個(gè)矩陣元素是否為零，若不為零，則將其行、列下標(biāo)

及其值存入b中。

【算法描述】

voidCreateTriTable(TSMatrix*b,inta[][5],intm,intn)

{//建立稀疏矩陣的三元組表

inti,j,k=0;

for(i=0;i<m;i++)

for(j=0;j<n;j++)

if(a[i][j]!=O)〃找出非零元素

{b->data[k].i=i;〃記錄非零元素行下標(biāo)

b->data[k].j=j;〃記錄非零元素列下標(biāo)

b->data[k].v=a[i][j];〃保存非零值

k++;〃統(tǒng)計(jì)非零元素個(gè)數(shù)

)

b->m=m;b->n=n;〃記錄矩陣行列數(shù)

b->t=k:〃保存非零個(gè)數(shù)

)

【例】試寫一個(gè)算法，實(shí)現(xiàn)以三元組表結(jié)構(gòu)存儲的稀疏矩陣的轉(zhuǎn)置

運(yùn)XA算~A-。

【分析】對于一個(gè)mxn的矩陣M,它的轉(zhuǎn)置矩陣T是一個(gè)nxm

的矩陣，而且M尸方(0<i<m,0<j<n),即M的行是T的列,M的

列是T的行。

[0010\

/03050

、300

0

00-200

T=0-208

10006

oj000

g080

<006V

稀疏矩陣M和它的轉(zhuǎn)置矩陣T

矩陣M對應(yīng)的三元組表矩陣M的轉(zhuǎn)置矩陣對應(yīng)的三元組表

a.dqtab.data

(1)一般的轉(zhuǎn)置算法

【算法思想】對M中的每一列col(Owcolwa.n-l)從頭至尾依次掃

描三元組表，找出所有列號等col的那些三元組，并將它們的行號和

列號互換后再依次存入b->data中，這樣就可得到T的按行優(yōu)先的三

兀組表。

【算法描述】

voidTransMatrix(TSMatrixa,TSMatrix*b)

{//a和*b是矩陣M、T的三元組表表示，求稀疏矩陣M的轉(zhuǎn)置T

intp,q,col;

b->m=a.n;b->n=a.m;//M和T彳亍歹U數(shù)互

換

b->t=a.t;〃賦值非零元素個(gè)數(shù)

if(b->t<=0)

printf("M中無非零元素!。;

else

{q=0；

for(col=0;col<a.n;++col)

for(p=0;p<a.t;++p)〃掃描M的三元組

表

if(a.data[p].j==col)〃找與col相等的三

元組

{b->data[q].i=a.data[p].j;

b->data[q].j=a.data[p].i;

b->data[q].v=a.data[p].v;

++q；

}

)

)

【算法分析】該算法的時(shí)間復(fù)雜度為O(nxt),即與稀疏矩陣M的

列數(shù)和非零元素個(gè)數(shù)的乘積成正比。一般的矩陣轉(zhuǎn)置算法的時(shí)間復(fù)雜

度為該算法僅適用于非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素個(gè)

0(mxn)ot

數(shù)mxn的情況。

(2)快速轉(zhuǎn)置算法

【算法思想】創(chuàng)建兩個(gè)數(shù)組和。]存放矩陣第

numrownextonumj

列上非零元素個(gè)數(shù)，rownext[i]代表轉(zhuǎn)置矩陣第i行的下一個(gè)非零元素

在b中的位置。

【算法描述】

voidFaStTran(TSMatfixa,TSMatrix*b)

{intcol,p,t,q;

int*num,*rownext;

num=(int*)calloc(a.n+l,4);//分配n+1個(gè)

長度為4的連續(xù)空間

rownext=(int*)calloc(a.m+l,4);//分配m+1

個(gè)長度為4的連續(xù)空間

b->m=a.n;b->n=a.m;b->t=a.t;

if(b->t)

{for(col=0;col<a.n;++col)

num[col]=0;〃初始化

for(t=0;t<a.t;++t)

++num[a.data[t].j];〃計(jì)算每列非零元

素?cái)?shù)

rownext[0]=0;

for(col=l;col<a.n;++col)〃給出b中每

一行的起始點(diǎn)

rownext[col]=rownext[col-l]+num[col-l];

for(p=0;p<a.t;++p)〃執(zhí)行轉(zhuǎn)置操(乍

{col=a.data[p].j;

q=rownext[col];

b->data[q].i=a.data[p].j;

b->data[q].j=a.data[p].i;

b->data[q].v=a.data[p].v;

++rownext[col];〃下一次再有

該行元素，起始點(diǎn)就比上一個(gè)加了1

)

)

)

【算法分析】算法的時(shí)間復(fù)雜度為0(t)

3、帶行表的三元組表

帶行表的三元組表：又稱為行邏輯鏈接的順序表。在按行優(yōu)先存儲

的三元組表中，增