數(shù)據(jù)結(jié)構(gòu)數(shù)組第一頁，共四十二頁，2022年，8月28日定義：相同類型的數(shù)據(jù)元素的集合。一維數(shù)組的示例：352749186054778341020123456789一維數(shù)組2.4.1數(shù)組的定義第二頁，共四十二頁，2022年，8月28日數(shù)組的定義和初始化main(){inta1[3]={3,5,7},*elem;for(inti=0;i<3;i++)printf(“%d”,a1[i],“\n”);//靜態(tài)數(shù)組elem=a1; for(inti=0;i<3;i++){printf(“%d”,*elem,“\n”);//動(dòng)態(tài)數(shù)組elem++;}}2.4.1數(shù)組的定義第三頁，共四十二頁，2022年，8月28日一維數(shù)組存儲方式352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la2.4.1數(shù)組的定義第四頁，共四十二頁，2022年，8月28日二維數(shù)組：類似于線性表，一個(gè)二維數(shù)組的邏輯結(jié)構(gòu)可形式地表示為：2_Array=(D,R)D={aij(i=0,1,…,m-1,j=0,1,…,n-1)},aij是同類型數(shù)據(jù)元素的集合。R={ROW,COL}是數(shù)據(jù)元素上關(guān)系的集合。2.4.1數(shù)組的定義a11a12a13…a1na21a22a23…a2nam1am2am3…amn…ai,j-1

aij

ai,j+1

………

ai-1,j

ai+1,j

Am,n=第五頁，共四十二頁，2022年，8月28日aij受行列兩個(gè)關(guān)系的約束：第i行的行向量，第j列的列向量。ROW={<aij,ai(j+1)>|0im-1,0jn-2}每一行上的列關(guān)系。

aij的行前趨ai,j-1，aij的行后繼ai,j+1COL={<aij,a(i+1)j>|0im-2,0jn-1}每一列上的行關(guān)系。

aij的列前趨ai-1,j，aij的列后繼ai+1,j2.4.1數(shù)組的定義第六頁，共四十二頁，2022年，8月28日行優(yōu)先存放(例：pascal、C語言)：

設(shè)數(shù)組開始存放位置LOC(0,0)=a,每個(gè)元素占用l個(gè)存儲單元

LOC(i,j)=a+(in+j)l2.4.2數(shù)組的順序存儲結(jié)構(gòu)約定存放次序：因?yàn)橛?jì)算機(jī)的存儲單元是一維的，數(shù)組可以是多維的，所以必須約定存放次序。第七頁，共四十二頁，2022年，8月28日

列優(yōu)先存放(例：Fortran語言)

：

設(shè)數(shù)組開始存放位置LOC(0,0)=a,每個(gè)元素占用l個(gè)存儲單元

LOC(i,j)=a+(jm+i)l2.4.2數(shù)組的順序存儲結(jié)構(gòu)第八頁，共四十二頁，2022年，8月28日三維數(shù)組：各維元素個(gè)數(shù)為

m1,m2,m3下標(biāo)為i1,i2,i3的數(shù)組元素的存儲地址：(按頁/行/列存放)LOC(i1,i2,i3)=a+(i1m2m3+i2m3+i3

)*l

前i1頁總元素個(gè)數(shù)第i1頁的前i2行總元素個(gè)數(shù)2.4.2數(shù)組的順序存儲結(jié)構(gòu)第i1頁的第i2行i3列前元素個(gè)數(shù)第九頁，共四十二頁，2022年，8月28日下標(biāo)為i1,i2,i3的數(shù)組元素的存儲地址：(按列/行/頁存放)LOC(i1,i2,i3)=a+(i3m1m2+i2m1+i1

)*l

前i3列總元素個(gè)數(shù)第i3列的前i2行總元素個(gè)數(shù)2.4.2數(shù)組的順序存儲結(jié)構(gòu)第i3列的第i2行i1頁前元素個(gè)數(shù)第十頁，共四十二頁，2022年，8月28日

n維數(shù)組：各維元素個(gè)數(shù)為m1,m2,m3,…,mn

下標(biāo)為

i1,i2,i3,…,in

的數(shù)組元素的存儲地址：

LOC(i1,i2,…,in)=a+(i1m2m3…mn+i2m3m4…mn++……+in-1mn+in)l

2.4.2數(shù)組的順序存儲結(jié)構(gòu)第十一頁，共四十二頁，2022年，8月28日

二維數(shù)組

三維數(shù)組

行向量下標(biāo)

i1

頁向量下標(biāo)

i1

列向量下標(biāo)

i2

行向量下標(biāo)

i2

列向量下標(biāo)

i3第十二頁，共四十二頁，2022年，8月28日特殊矩陣的壓縮存儲特殊矩陣：是指非零元素的分布有一定規(guī)律/大量零元素的矩陣。壓縮存儲：針對階數(shù)很高的特殊矩陣。為節(jié)省存儲空間，可以不存儲零元素或?qū)ΨQ元素。

對稱矩陣

三對角矩陣2.4.2數(shù)組的順序存儲結(jié)構(gòu)第十三頁，共四十二頁，2022年，8月28日對稱矩陣的壓縮存儲設(shè)有一個(gè)

nn

的對稱矩陣

A。在矩陣中，aij=aji2.4.2數(shù)組的順序存儲結(jié)構(gòu)第十四頁，共四十二頁，2022年，8月28日

為節(jié)約存儲空間，只存對角線及對角線以上的元素，或者只存對角線及對角線以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。

把它們按行存放于一個(gè)一維數(shù)組B中，稱之為對稱矩陣A的壓縮存儲方式。

數(shù)組B共有

n+(n-1)++1=n(n+1)/2個(gè)元素。2.4.2數(shù)組的順序存儲結(jié)構(gòu)第十五頁，共四十二頁，2022年，8月28日上三角矩陣下三角矩陣第十六頁，共四十二頁，2022年，8月28日下三角矩陣Ba00a10a11a20a21a22a30a31a32……

an-1n-1

012345678n(n+1)/2-1若

i

j,數(shù)組元素A[i][j]在數(shù)組B中的存放位置為

1+2++i+j=(i+1)i/2+j前i行元素總數(shù)

第i行第j個(gè)元素前元素個(gè)數(shù)第十七頁，共四十二頁，2022年，8月28日

若i<j，數(shù)組元素A[i][j]在矩陣的上三角部分,在數(shù)組B中沒有存放，可以找它的對稱元素：A[j][i]：=j(j+1)/2+i

若已知某矩陣元素位于數(shù)組B的第k個(gè)位置，可尋找滿足i(i+1)/2k<(i+1)(i+2)/2的i(行號),

j=k-i(i+1)/2(列號)

例:當(dāng)k=8,34/2=6k

<4*5/2=10,取i=3。則j=8-34/2=2。

2.4.2數(shù)組的順序存儲結(jié)構(gòu)第十八頁，共四十二頁，2022年，8月28日上三角矩陣Ba00a01a02a03a11a12a13a22a23

a33

0123456789

若i

j，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為n+(n-1)+(n-2)++(n-i+1)+j-i=(2n-i-1)i/2+j前i行元素總數(shù)

第i行第j個(gè)元素前元素個(gè)數(shù)n=4第十九頁，共四十二頁，2022年，8月28日

若i>j，數(shù)組元素A[i][j]在矩陣的下三角部分，在數(shù)組B中沒有存放。因此，找它的對稱元素A[j][i]。

A[j][i]在數(shù)組B的第(2n-j-1)

j/2+i的位置中找到。2.4.2數(shù)組的順序存儲結(jié)構(gòu)第二十頁，共四十二頁，2022年，8月28日三對角矩陣的壓縮存儲Ba00a01a10a11a12a21a22a23…

an-1n-2an-1n-1

0123456789102.4.2數(shù)組的順序存儲結(jié)構(gòu)第二十一頁，共四十二頁，2022年，8月28日

三對角矩陣中除主對角線及在主對角線上下最臨近的兩條對角線上的元素外，所有其它元素均為0。總共有3n-2個(gè)非零元素。將三對角矩陣A中三條對角線上的元素按行存放在一維數(shù)組B中，且a00存放于B[0]。在三條對角線上的元素aij

滿足

0i

n-1,i-1

j

i+1在一維數(shù)組B中A[i][j]在第i行，它前面有3i-1個(gè)非零元素,在本行中第j列前面有j-i+1個(gè)，所以元素A[i][j]在B中位置為k=2i+j。2.4.2數(shù)組的順序存儲結(jié)構(gòu)第二十二頁，共四十二頁，2022年，8月28日2.4.3稀疏矩陣(SparseMatrix)

非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于矩陣元素個(gè)數(shù)且分布無規(guī)律可循。

在上圖中,矩陣A是6*7的矩陣,它有42個(gè)元素,但只有8個(gè)非零元素。

簡單的壓縮存儲會(huì)失去隨機(jī)存取功能，還要存儲輔助信息

存儲非零元素時(shí)，存儲元素的行列號

存儲方式：

順序存儲：不改變矩陣的稀疏程度(存取、修改、轉(zhuǎn)置)

鏈?zhǔn)酱鎯Γ焊淖兙仃嚨南∈璩潭?相加、相乘)第二十三頁，共四十二頁，2022年，8月28日稀疏矩陣的抽象數(shù)據(jù)類型(三元組順序表）#defineMAXSIZE12500typedefstruct{ inti,j; //非零元素行號/列號 ElemTypee;//非零元素的值}Triple;//三元組typedefstruct{ Tripledata[MAXSIZE]; intmu,nu,tu;//矩陣行數(shù)、列數(shù)、非零元個(gè)數(shù)}TSMatrix;//稀疏矩陣類定義

2.4.3稀疏矩陣(SparseMatrix)第二十四頁，共四十二頁，2022年，8月28日2.4.3稀疏矩陣(SparseMatrix)稀疏矩陣A76第二十五頁，共四十二頁，2022年，8月28日轉(zhuǎn)置矩陣B67=AT762.4.3稀疏矩陣(SparseMatrix)第二十六頁，共四十二頁，2022年，8月28日用三元組表表示的稀疏矩陣及其轉(zhuǎn)置2.4.3稀疏矩陣(SparseMatrix)如果只簡單交換行列下標(biāo)，所得B是按列優(yōu)先存儲第二十七頁，共四十二頁，2022年，8月28日稀疏矩陣轉(zhuǎn)置算法思想

顯然，一個(gè)稀疏矩陣的轉(zhuǎn)置仍然是一個(gè)稀疏矩陣。(1)將矩陣的行列值交換(2)將每一個(gè)三元組的i和j相互調(diào)換(3)重排三元組之間的次序

可以有兩種處理方法：2.4.3稀疏矩陣(SparseMatrix)第二十八頁，共四十二頁，2022年，8月28日方法一：按照A(mn)的列序來進(jìn)行轉(zhuǎn)置,設(shè)矩陣列數(shù)為nu，對矩陣三元組表掃描nu次。第k次檢測列號為k的項(xiàng)。第k次掃描找尋所有列號為k的項(xiàng)，將其行號變列號、列號變行號，順次存于轉(zhuǎn)置矩陣三元組表。2.4.3稀疏矩陣(SparseMatrix)按A的列下標(biāo)轉(zhuǎn)置，所得B是按行優(yōu)先存放第二十九頁，共四十二頁，2022年，8月28日稀疏矩陣的轉(zhuǎn)置StatusTransposeSMatrix(TSMatrix&A,TSMatrix&B){ B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;

//轉(zhuǎn)置矩陣的列數(shù),行數(shù)和非零元素個(gè)數(shù)

if(B.tu){ q=0;//矩陣B的指針 for(col=0;col<=A.nu-1;++col) for(p=0;p<=A.tu-1;++p)//矩陣A的指針 if(A.data[p].j==col){ B.data[q].i=A.data[p].j; B.data[q].j=A.data[p].i; B.data[q].e=A.data[p].e; ++q; } } return1;}//TransposeSMatrix2.4.3稀疏矩陣(SparseMatrix)特點(diǎn)：以B矩陣的三元組為中心，在A矩陣的三元組中通盤查找合適的結(jié)點(diǎn)置入B中。第三十頁，共四十二頁，2022年，8月28日

該算法主要工作是在pcol的兩重循環(huán)中做的，所以時(shí)間復(fù)雜度是O(nutu)。一般矩陣的轉(zhuǎn)置算法是在numu的兩重循環(huán)中做的，時(shí)間復(fù)雜度是O(numu)。當(dāng)稀疏矩陣的非零元個(gè)數(shù)tu=numu時(shí)，其時(shí)間復(fù)雜度:O(nutu)=O(nunumu)=O(nu2mu)大大高于一般矩陣的時(shí)間復(fù)雜度，所以該算法僅適用于tu<<numu的稀疏矩陣。2.4.3稀疏矩陣(SparseMatrix)用三元組節(jié)省了存儲空間，但增加了執(zhí)行時(shí)間第三十一頁，共四十二頁，2022年，8月28日方法二：快速轉(zhuǎn)置運(yùn)算(帶輔助向量的三元組)預(yù)先確定A的每一列第一個(gè)非零元在B中應(yīng)有的位置，則在轉(zhuǎn)置時(shí)就可直接放到B中去，所以在轉(zhuǎn)置前，應(yīng)先求得A的每一列中非零元的個(gè)數(shù)和每一列的第一個(gè)非零元在B中的位置。

只需對A掃描一遍。需要兩個(gè)輔助數(shù)組num和pos。num表示A中第col列非零元素的個(gè)數(shù)。pos表示A中第col列第一個(gè)非零元素在B中的位置。顯然有：pos[0]=0pos[col]=pos[col-1]+num[col-1]2.4.3稀疏矩陣(SparseMatrix)第三十二頁，共四十二頁，2022年，8月28日矩陣A的輔助數(shù)組的值Col012356num[col]111221pos[col]012357轉(zhuǎn)置矩陣第三十三頁，共四十二頁，2022年，8月28日StatusFastTransposeSMatrix(TSMatrix&A,TSMatrix&B){ B.mu=A.nu;B.nu=A.mu;B.tu=A.tu; if(B.tu){ for(col=0;col<=A.nu-1;++col)num[col]=0;//初始化num for(t=0;t<=A.tu-1;++t)++num[A.data[t].j];//求A中每列非零元個(gè)數(shù) pos[0]=0; for(col=1;col<=A.nu-1;++col)pos[col]=pos[col-1]+num[col-1];

//求第col列中第一個(gè)非零元在B中的序號 for(p=0;p<=A.tu-1;++p){ col=A.data[p].j;q=pos[col]; B.data[q].i=A.data[p].j; B.data[q].j=A.data[p].i; B.data[q].e=A.data[p].e;++pos[col];//該列下一元素位置 } } return1;}//FastTransposeSMatrix2.4.3稀疏矩陣(SparseMatrix)第三十四頁，共四十二頁，2022年，8月28日

該算法有四個(gè)并列的單循環(huán)，所以算法復(fù)雜度是O(2nu+2tu)=O(nu+tu)。當(dāng)稀疏矩陣的非零元個(gè)數(shù)tu=numu時(shí)，其時(shí)間復(fù)雜度:O(nu+tu)=O(nu+numu)=O(numu)增加列輔助向量提高了轉(zhuǎn)置的運(yùn)算速度，但有空間代價(jià)。2.4.3稀疏矩陣(SparseMatrix)第三十五頁，共四十二頁，2022年，8月28日

2.4.4數(shù)組的鏈?zhǔn)酱鎯Y(jié)構(gòu)帶行指針的鏈表

把具有相同行號的非零元用一個(gè)單鏈表連接起來，稀疏矩陣中的若干行組成若干個(gè)單鏈表，合起來稱為帶行指針的鏈表。

例如，稀疏矩陣A的帶行指針的鏈表：存儲量：3tu+mu第三十六頁，共四十二頁，2022年，8月28日十字鏈表非零元結(jié)點(diǎn)：既是第i行循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，又是第j列循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，相當(dāng)于處在一個(gè)十字交叉路口，故稱鏈表為十字鏈表。行、列循環(huán)鏈表的表頭結(jié)點(diǎn)：行、列、值為0，并且將所有的行、列鏈表和頭結(jié)點(diǎn)一起鏈成一個(gè)循環(huán)鏈表。在行(列)表頭結(jié)點(diǎn)中，行、列域的值都為0，故兩組表頭結(jié)點(diǎn)可以共用：即第i行鏈表和第j列鏈表共用一個(gè)表頭結(jié)點(diǎn)，這些表頭結(jié)點(diǎn)本身又可以通過val域(非零元值域，但在表頭結(jié)點(diǎn)中為next，指向下一個(gè)表頭結(jié)點(diǎn))相鏈接?？偟念^結(jié)點(diǎn)(由指針hm指示，行、列域分別為稀疏矩陣的行、列數(shù))，指向第一個(gè)表頭結(jié)點(diǎn)。整個(gè)十字鏈表可由hm指針唯一確定。2.4.4數(shù)組的鏈?zhǔn)酱鎯Y(jié)構(gòu)第三十七頁，共四十二頁，2022年，8月28日2.4.4數(shù)組的鏈?zhǔn)酱鎯Y(jié)構(gòu)00nextdownright十字鏈表表頭結(jié)點(diǎn)rowcolvaldownright十字鏈表非零元結(jié)點(diǎn)行指針域列指針域行、列和值的三元組mununext十字鏈表總的表頭結(jié)點(diǎn)hm第三十八頁，共四十二頁，2022年，8月28日十字鏈表2.4.4數(shù)組的鏈?zhǔn)酱鎯Y(jié)構(gòu)第三十九頁，共四十二頁，2022年，8月28日第一步，建立表頭的循環(huán)鏈表

輸入矩陣的行、列數(shù)和非零元素個(gè)數(shù)：m,n和t。表頭結(jié)點(diǎn)的個(gè)數(shù)s=max(m,n)。建立總表頭結(jié)點(diǎn)(由hm指針指向)和s個(gè)行、列表頭結(jié)點(diǎn)，并使用next域使s+1個(gè)頭結(jié)點(diǎn)組成一個(gè)循環(huán)鏈表?？偙眍^結(jié)點(diǎn)的行、列域分別為m和n；s個(gè)表頭結(jié)點(diǎn)的行列域分別為0。s個(gè)行、列表頭結(jié)點(diǎn)中的行、列指針域right和down均指向頭結(jié)點(diǎn)本身。第二步，生成表中結(jié)