數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)（第二版）課件 第5章數(shù)組

第五章數(shù)組數(shù)組—邏輯結(jié)構(gòu)數(shù)組是我們很熟悉的一種數(shù)據(jù)結(jié)構(gòu)，可以把數(shù)組看做是線性表的推廣。數(shù)組的特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。一維數(shù)組二維數(shù)組三維數(shù)組數(shù)組—邏輯結(jié)構(gòu)從小事做起，學(xué)會(huì)“積累”，學(xué)習(xí)也是一個(gè)積累的過(guò)程。使學(xué)生明白“積少成多”，能力才能螺旋式上升。數(shù)組—邏輯結(jié)構(gòu)數(shù)組的特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，一維數(shù)組可以看做是一個(gè)線性表；（a1a2…aj…an）二維數(shù)組可以看做是“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組；三維數(shù)組可以看做是“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組。a11a12…a1j…a1na21a22…a2j…a2nai1ai2…aij…ainam1am2…amj…amnAm×n=……………………m行n列的二維數(shù)組看成n個(gè)列向量的線性表推廣：

n維數(shù)組—每個(gè)數(shù)據(jù)元素受n個(gè)關(guān)系的約束，每一單個(gè)關(guān)系，仍是線性關(guān)系。也可看成m個(gè)行向量的線性表B=(βiβ2β1βm……a11a12…a1j…a1na21a22…a2j…a2nai1ai2…aij…ainam1am2…amj…amnAm×n=……………………A=(α1

α

2…α

j

…α

n)每一個(gè)數(shù)組元素aij在第i行，第j列，受到兩個(gè)線性關(guān)系的約束，就是行和列關(guān)系。數(shù)組—邏輯結(jié)構(gòu)一般來(lái)說(shuō)，在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。通常在各種高級(jí)語(yǔ)言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。在數(shù)組中通常做下面兩種操作：(1)取值操作：給定一組下標(biāo)，讀其對(duì)應(yīng)的數(shù)據(jù)元素。(2)賦值操作：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)據(jù)元素。從數(shù)組的特殊結(jié)構(gòu)可看出，數(shù)組中的每個(gè)元素由一個(gè)值和一組下標(biāo)來(lái)描述。Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..數(shù)組—邏輯結(jié)構(gòu)由于對(duì)數(shù)組一般不做插入、刪除操作；一旦建立了數(shù)組，數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)；

采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組；由于存儲(chǔ)單元是一維的結(jié)構(gòu)，而數(shù)組是多維的結(jié)構(gòu)，則采用一組連續(xù)存儲(chǔ)單元存放數(shù)組元素就有個(gè)次序約定問(wèn)題。一般有兩種存儲(chǔ)方式：一是以行為主序(即先行后列)的順序存放，一行存儲(chǔ)完了接著存儲(chǔ)下一行。二是以列為主序(即先列后行)的順序存放，一列存儲(chǔ)完了接著存儲(chǔ)下一列。數(shù)組—存儲(chǔ)結(jié)構(gòu)數(shù)組—存儲(chǔ)結(jié)構(gòu)第一行第二行第一列第二列第三列a11a12a13a21a22a232×3數(shù)組的邏輯狀態(tài)a11a12a23a21a22a23

以行為主序a11a21a12a22a13a23

以列為主序采用以行為主序的方法存放，則存放順序?yàn)椋篴111，a112，a121，a122，…，a331，a332，a341，…；采用以縱為主序的方法存放，則順序?yàn)椋篴111，a211，a311，a121，a221，a321，…，a132，a232，a332，a142，a242，a342。假設(shè)有一個(gè)3?×?4?×?2的三維數(shù)組，共有24個(gè)元素。三維數(shù)組元素的下標(biāo)由三個(gè)數(shù)字表示，即行、列、縱三個(gè)方向。A231表示第2行、第3列、第1縱的元素。數(shù)組—存儲(chǔ)結(jié)構(gòu)

數(shù)組的順序存儲(chǔ)是一種隨機(jī)存取的結(jié)構(gòu)。如果已知多維數(shù)組的維數(shù)，以及每維的上、下界，就可以方便地將多維數(shù)組按順序存儲(chǔ)結(jié)構(gòu)存放在計(jì)算機(jī)中了。同時(shí)，根據(jù)數(shù)組的下標(biāo)，可以計(jì)算出數(shù)組中某個(gè)數(shù)組元素在存儲(chǔ)器中的位置。設(shè)有m?×?n二維數(shù)組Amn，假設(shè)下標(biāo)從1開始，以“以行為主序”的分配為例。設(shè)數(shù)組中的a11存儲(chǔ)地址為L(zhǎng)oc(a11)，每個(gè)數(shù)組元素占據(jù)L個(gè)地址單元，那么aij的物理地址可計(jì)算出來(lái)：Loc(aij)?=?Loc(a11)?+?((i?-?1)×n?+?j?-?1)?×?L

這是因?yàn)閿?shù)組元素aij的前面有i-1行，每一行的元素個(gè)數(shù)為n，在第i行中它的前面還有j-1個(gè)數(shù)組元素。數(shù)組—存儲(chǔ)結(jié)構(gòu)

同理，可得到三維數(shù)組Amnp中任意元素aijk的存儲(chǔ)地址的計(jì)算公式：Loc(aijk)?=?Loc(a111)?+?((i?-?1)?×?n?×?p?+?(j?-?1)?×?p?+?k?-?1)?×?L

數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)，一旦數(shù)組下標(biāo)確定之后，數(shù)組中的元素可隨機(jī)存取。我們稱具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)為隨機(jī)存儲(chǔ)結(jié)構(gòu)。數(shù)組—存儲(chǔ)結(jié)構(gòu)推廣到一般的三維數(shù)組：A[c1..d1][c2..d2][c3..d3]，則aijk的物理地址為:Loc(aijk)=Loc(ac1c2c3)+((i-c1)×(d2-c2+1)×(d3-c3+1)??+(j-c2)×(d3-c3+1)+(k-c3))×L對(duì)于n維數(shù)組A(c1..d1,c2..d2,…,cn..dn)，我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素aj1j2…jn的存儲(chǔ)地址的計(jì)算公式：

容易看出，數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)，一旦數(shù)組下標(biāo)確定之后，數(shù)組中的元素可隨機(jī)存取。我們稱具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)為隨機(jī)存儲(chǔ)結(jié)構(gòu)。數(shù)組—存儲(chǔ)結(jié)構(gòu)矩陣是一個(gè)二維數(shù)組，它是很多科學(xué)與工程計(jì)算問(wèn)題中研究的數(shù)學(xué)對(duì)象。矩陣可以用行優(yōu)先或列優(yōu)先方法順序存放到內(nèi)存中，但是，當(dāng)矩陣的階數(shù)很大時(shí)將會(huì)占較多存儲(chǔ)單元。而當(dāng)數(shù)組元素分布呈現(xiàn)某種規(guī)律時(shí)，這時(shí)，從節(jié)約存儲(chǔ)單元出發(fā)，可考慮若干數(shù)組元素共用一個(gè)存儲(chǔ)單元，即進(jìn)行壓縮存儲(chǔ)。所謂壓縮存儲(chǔ)，是指為多個(gè)值相同的數(shù)組元素只分配一個(gè)存儲(chǔ)空間，值為零的數(shù)組元素不分配空間。特殊矩陣—壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)是為了節(jié)約空間，雖然現(xiàn)在計(jì)算機(jī)硬件發(fā)展很快，其處理量以指數(shù)級(jí)增長(zhǎng)，必須考慮存儲(chǔ)空間的有效利用?！扒趦€節(jié)約”，杜絕浪費(fèi)。Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..在一個(gè)n階方陣中，有aij

=

aji，稱之為對(duì)稱矩陣；對(duì)稱矩陣的特點(diǎn)是：在一個(gè)n階方陣中，有aij

=

aji，其中1≤i,j≤n。對(duì)稱矩陣關(guān)于主對(duì)角線對(duì)稱，因此只需存儲(chǔ)上三角或下三角部分即可。特殊矩陣—壓縮存儲(chǔ)透過(guò)現(xiàn)象看本質(zhì)！??！對(duì)于n*n矩陣A，只存儲(chǔ)A中的下三角中的數(shù)組元素aij，上三角中的數(shù)組元素aij，和對(duì)應(yīng)的aji相等，因此當(dāng)訪問(wèn)的數(shù)組元素在上三角時(shí)，直接去訪問(wèn)和它對(duì)應(yīng)的下三角數(shù)組元素即可，這樣，原來(lái)需要n2個(gè)存儲(chǔ)單元，現(xiàn)在只需要n(n+1)/2個(gè)存儲(chǔ)單元了，節(jié)約了n(n-1)/2個(gè)存儲(chǔ)單元，當(dāng)n較大時(shí)，這是可觀的一部分存儲(chǔ)資源。Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..特殊矩陣—壓縮存儲(chǔ)透過(guò)現(xiàn)象看本質(zhì)?。?！第1行第2行第3行第n行對(duì)于下三角中的數(shù)組元素aij，其特點(diǎn)是：i≥j且1≤i≤n，存儲(chǔ)到SA中后，根據(jù)存儲(chǔ)原則，它前面有i-1行，共有1?+?2?+?…?+?i?-?1?=?i?×?(i?-?1)?/?2個(gè)元素。而aij又是它所在的行中的第j個(gè)，所以在上面的排列順序中，aij是第i?×?(i?-?1)?/?2?+?j個(gè)元素。因此它在SA中的下標(biāo)k與i、j的關(guān)系為Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..12345···n(n+1)/2a10a21a22a31a32a33···an1an2···ann特殊矩陣—壓縮存儲(chǔ)若i?<?j，則aij是上三角中的數(shù)組元素，因?yàn)閍ij?=?aji，這樣，訪問(wèn)上三角中的數(shù)組元素aij時(shí)則去訪問(wèn)和它對(duì)應(yīng)的下三角中的aji即可，因此將上式中的行列下標(biāo)交換就是上三角中的數(shù)組元素在SA中的對(duì)應(yīng)關(guān)系：

綜上所述，對(duì)于對(duì)稱矩陣中的任意數(shù)組元素aij，若令I(lǐng)?=?max(i,j)，J?=?min(i,j)，則將上面兩個(gè)式子綜合起來(lái)得到：k?=?I?×?(I-1)/2?+?J。特殊矩陣—壓縮存儲(chǔ)下三角矩陣上三角矩陣三角矩陣與對(duì)稱矩陣類似，不同之處在于存完下三角中的數(shù)組元素之后，緊接著存儲(chǔ)對(duì)角線上方的常量，因?yàn)槭峭粋€(gè)常數(shù)，所以存一個(gè)即可。這樣一共存儲(chǔ)了n?×?(n+1)/2+1個(gè)元素。下三角矩陣的壓縮存儲(chǔ)形式362481746082957c12345678910111213141516特殊矩陣—壓縮存儲(chǔ)若矩陣中所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為對(duì)角矩陣。常見(jiàn)的有三對(duì)角矩陣、五對(duì)角矩陣、七對(duì)角矩陣等。三對(duì)角帶狀矩陣特點(diǎn)：第一行、第n行只有兩個(gè)非零元素，中間n-2行每行有三個(gè)非零元素。12345678910111213a11a12a21a22a23a32a33a34a43a44a45a54a32特殊矩陣—壓縮存儲(chǔ)(1)確定存儲(chǔ)該矩陣所需的一維向量空間的大小。所需一維向量空間的大小為2?+?2?+?3(n?-?2)?=?3n?-?2(2)確定非零元素在一維數(shù)組空間中的位置：Loc[i,j]。前i-1行元素個(gè)數(shù)?=?3?×?(i-1)?-?1(因?yàn)榈?行只有兩個(gè)非零元素)；第i行中aij前非零元素個(gè)數(shù)?=?j-i+1，其中j-i的絕對(duì)值小于等于1?，F(xiàn)在的任務(wù)是：將矩陣中的非零元素aij壓縮存儲(chǔ)。Loc[i,j]?=?Loc[1,1]?+?3(i?-?1)?-?1?+?j?-?i?+?1?=?Loc[1,1]?+?2(i?-?1)?+?j?-?1特殊矩陣—壓縮存儲(chǔ)總而言之，對(duì)特殊矩陣的壓縮存儲(chǔ)方法時(shí)可以總結(jié)為兩條：首先，確定壓縮存儲(chǔ)矩陣所需的空間的大小。第二：確定矩陣元素aij在壓縮存儲(chǔ)區(qū)域中的位置。特殊矩陣—壓縮存儲(chǔ)內(nèi)容回顧數(shù)組—邏輯結(jié)構(gòu)數(shù)組是我們很熟悉的一種數(shù)據(jù)結(jié)構(gòu)，可以把數(shù)組看做是線性表的推廣。數(shù)組的特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。一維數(shù)組二維數(shù)組三維數(shù)組數(shù)組—邏輯結(jié)構(gòu)從小事做起，學(xué)會(huì)“積累”，學(xué)習(xí)也是一個(gè)積累的過(guò)程。使學(xué)生明白“積少成多”，能力才能螺旋式上升。對(duì)于n維數(shù)組A(c1..d1,c2..d2,…,cn..dn)，我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素aj1j2…jn的存儲(chǔ)地址的計(jì)算公式：

容易看出，數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)，一旦數(shù)組下標(biāo)確定之后，數(shù)組中的元素可隨機(jī)存取。我們稱具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)為隨機(jī)存儲(chǔ)結(jié)構(gòu)。數(shù)組—存儲(chǔ)結(jié)構(gòu)矩陣是一個(gè)二維數(shù)組，它是很多科學(xué)與工程計(jì)算問(wèn)題中研究的數(shù)學(xué)對(duì)象。矩陣可以用行優(yōu)先或列優(yōu)先方法順序存放到內(nèi)存中，但是，當(dāng)矩陣的階數(shù)很大時(shí)將會(huì)占較多存儲(chǔ)單元。而當(dāng)數(shù)組元素分布呈現(xiàn)某種規(guī)律時(shí)，這時(shí)，從節(jié)約存儲(chǔ)單元出發(fā)，可考慮若干數(shù)組元素共用一個(gè)存儲(chǔ)單元，即進(jìn)行壓縮存儲(chǔ)。所謂壓縮存儲(chǔ)，是指為多個(gè)值相同的數(shù)組元素只分配一個(gè)存儲(chǔ)空間，值為零的數(shù)組元素不分配空間。特殊矩陣—壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)是為了節(jié)約空間，雖然現(xiàn)在計(jì)算機(jī)硬件發(fā)展很快，其處理量以指數(shù)級(jí)增長(zhǎng)，必須考慮存儲(chǔ)空間的有效利用?！扒趦€節(jié)約”，杜絕浪費(fèi)。設(shè)m?×?n矩陣中有t個(gè)非零元素且t?<<?m?×?n，稀疏矩陣—壓縮存儲(chǔ)δ=t/m?×?n，δ稱為稀疏因子,

δ≤0.05時(shí)為稀疏矩陣。如果按順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，會(huì)造成空間的浪費(fèi)。通常零元素分布沒(méi)有規(guī)律，存儲(chǔ)非零元素的值是不夠的，還要記下它所在的行和列。將非零元素所在的行、列以及它的值構(gòu)成一個(gè)三元組(i,j,v)，然后再按某種規(guī)律存儲(chǔ)這些三元組，這種方法可以節(jié)約存儲(chǔ)空間。透過(guò)現(xiàn)象看本質(zhì)?。?！將三元組按行優(yōu)先的順序，同一行中列號(hào)從小到大的規(guī)律排列成一個(gè)線性表，稱為三元組表，采用順序存儲(chǔ)方法存儲(chǔ)該表。

ijv123456711122351462341

1522

-15113691顯然，要唯一地表示一個(gè)稀疏矩陣，可在存儲(chǔ)三元組表的同時(shí)存儲(chǔ)該矩陣的行、列，為了運(yùn)算方便，矩陣的非零元素的個(gè)數(shù)也同時(shí)存儲(chǔ)。稀疏矩陣—壓縮存儲(chǔ)1defineSMAX10242typedefstruct3{4inti,j; 5datatypev; 6}SPNode; 7typedefstruct8{9intmu,nu,tu;10SPNodedata[SMAX]; 11}SPMatrix; /*一個(gè)足夠大的數(shù)*//*非零元素的行、列*//*非零元素值*//*三元組類型*//*矩陣的行、列及非零元素的個(gè)數(shù)*//*三元組表的存儲(chǔ)類型*//*三元組表*/稀疏矩陣—壓縮存儲(chǔ)稀疏矩陣的三元組表表示法雖然節(jié)約了存儲(chǔ)空間，但比起矩陣正常的存儲(chǔ)方式來(lái)講，其實(shí)現(xiàn)相同操作要耗費(fèi)較多的時(shí)間，同時(shí)也增加了算法的難度，以耗費(fèi)更多時(shí)間為代價(jià)來(lái)?yè)Q取空間的節(jié)省。稀疏矩陣—壓縮存儲(chǔ)

所謂矩陣轉(zhuǎn)置，是指變換元素的位置，把位于(row，col)位置上的元素?fù)Q到(col，row)位置上，也就是說(shuō)，把元素的行、列互換。采用矩陣的正常存儲(chǔ)方式時(shí)，實(shí)現(xiàn)矩陣轉(zhuǎn)置的經(jīng)典算法如下：1voidTransMatrix(datatypesource[n][m],datatypedest[m][n])2{/*source和dest分別為被轉(zhuǎn)置的矩陣和轉(zhuǎn)置以后的矩陣*/3inti,j;4for(i=0;i<m;i++)5for(j=0;j<n;j++)6dest[i][j]=source[j][i];7}

顯然，時(shí)間復(fù)雜度為O(m?×?n)。1稀疏矩陣的轉(zhuǎn)置在A的三元組存儲(chǔ)基礎(chǔ)上得到B的三元組表存儲(chǔ)算法思路：①由A的行數(shù)、列數(shù)、非零元數(shù)目轉(zhuǎn)化成B的列數(shù)、行數(shù)、非零元數(shù)目。②按A的列(B的行)進(jìn)行循環(huán)處理：對(duì)A的每一列掃描三元組，找出相應(yīng)的元素，若找到，則交換其行號(hào)與列號(hào)，并存儲(chǔ)到B的三元組中。-746815167182562434514634-3133931212211ecolrow14368-7647244369135185241212315612-3311ecolrow(a)三元組表A(b)三元組表B

1稀疏矩陣的轉(zhuǎn)置1SPMatrix*TransM1(SPMatrix*A)2{SPMatrix*B;3intp,q,col;//p為A中下標(biāo)，q為B中下標(biāo)4B=(SPMatrix*)malloc(sizeof(SPMatrix));/*申請(qǐng)存儲(chǔ)空間*/5B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;/*稀疏矩陣的行、列、元素個(gè)數(shù)*/6if(B->tu>0)/*有非零元素則轉(zhuǎn)換*/7{q=1;8for(col=1;col<=(A->nu);col++)/*按A的列序轉(zhuǎn)換*/9for(p=1;p<=(A->tu);p++)/*掃描整個(gè)A的三元組表*/10if(A->data[p].j==col)//三元組中的元素在當(dāng)前列。11{B->data[q].i=A->data[p].j;//逐個(gè)復(fù)制當(dāng)前的A三元組元素到B三元組12B->data[q].j=A->data[p].i;13B->data[q].v=A->data[p].v;14q++;15}/*if*/16}/*if(B->tu>0)*/17returnB;/*返回的是轉(zhuǎn)置矩陣的指針*/18}/*TransM1*/時(shí)間復(fù)雜度為O(A.n×A.len),最壞情況當(dāng)A.len=A.m×A.n時(shí)，時(shí)間復(fù)雜度為O(A.m×A.n2)。1稀疏矩陣的轉(zhuǎn)置依次按三元組表A的次序進(jìn)行轉(zhuǎn)置，轉(zhuǎn)置后直接放到三元組表B的正確位置上。這種轉(zhuǎn)置算法稱為快速轉(zhuǎn)置算法。

為了能將待轉(zhuǎn)置三元組表A中元素一次定位到三元組表B的正確位置上，需要預(yù)先計(jì)算以下數(shù)據(jù)：待轉(zhuǎn)置矩陣每一列中非零元素的個(gè)數(shù)。(2)待轉(zhuǎn)置矩陣每一列中第一個(gè)非零元素在三元組表B中的正確位置?？焖俎D(zhuǎn)置方法：為此，需要設(shè)兩個(gè)數(shù)組num[col]——用來(lái)存放A中第col列非零元素個(gè)數(shù)cpot[col]——用來(lái)存放A中第col列中第一個(gè)非零元素在三元組表B中的正確位置。col90781687531Position[col]01222num[col]54321-746815167182562434514634-3133931212211ecolrow14368-7647244369135185241212315612-3311ecolrow(a)三元組表A(b)三元組表B(1)num[col]的計(jì)算方法：將三元組表A掃描一遍，對(duì)于其中列號(hào)為k的元素，給相應(yīng)的num[k]加1。(2)position[col]的計(jì)算方法：position[1]=1，position[col]=position[col-1]+num[col-1]，其中2≤col≤A.nu。

算法如下：SPMatrix*FastTM(TSMatrix*A){SPMatrix*B;intcol,t,p，q;//p為A下標(biāo)，q為B下標(biāo)

intnum[MAXSIZE],cpot[MAXSIZE];B->tu=A->tu;B->nu=A->mu;B->mu=A->nu;if(B->tu>0){for(col=1;col<=A->nu;col++)num[col]=0;//num初始化

for(t=1;t<=A->tu;t++)num[A->data[t].col]++;//計(jì)算num

cpot[1]=1;for(col=2;col<=A->nu;col++)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<A.tu；p++){col=A.data[p].col;q=cpot[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].ecpot[col]++;//下一個(gè)col行非零元素位置加1}//for}//if}快速轉(zhuǎn)置算法時(shí)間耗費(fèi)在四個(gè)并列的單循環(huán)上，這四個(gè)并列的單循環(huán)分別執(zhí)行了A.nu，A.tu，A.nu，A.tu次；因而總的時(shí)間復(fù)雜度為O(A.nu)+O(A.tu)+O(A.nu)+O(A.tu)。當(dāng)待轉(zhuǎn)置矩陣M中非零元素個(gè)數(shù)接近于A.mu×A.nu時(shí)，其時(shí)間復(fù)雜度接近于經(jīng)典算法的時(shí)間復(fù)雜度O(A.mu×A.nu)?？臻g耗費(fèi)上除了三元組表所占用的空間外，還需要兩個(gè)輔助向量空間，即num[1..A->nu]，cpot[1..A->nu]?？梢?jiàn)，算法在時(shí)間上的節(jié)省，是以更多的存儲(chǔ)空間為代價(jià)的。歲月靜好，是因?yàn)橛腥嗽谔嫖覀冐?fù)重前行三元組表存儲(chǔ)的稀疏矩陣，在進(jìn)行矩陣加法、減法和乘法等操作時(shí)，有時(shí)矩陣中的非零元素的位置和個(gè)數(shù)會(huì)發(fā)生很大的變化。如A?=?A?+?B，將矩陣B加到矩陣A上，此時(shí)若還用三元組表表示法，勢(shì)必會(huì)為了保持三元組表“以行序?yàn)橹餍颉倍罅恳苿?dòng)元素。為此引入了鏈?zhǔn)酱鎯?chǔ)稀疏矩陣。矩陣中，每一個(gè)矩陣元素aij，受兩個(gè)線性關(guān)系的約束，行關(guān)系、列關(guān)系；每一個(gè)關(guān)系都是線性的，我們可以用線性鏈表來(lái)存儲(chǔ)行關(guān)系、列關(guān)系；這樣，aij就處于第i行的單鏈表中，也處于第j列的單鏈表中，就像處于十字路口一樣，所以我們將這種存儲(chǔ)結(jié)構(gòu)稱之為“十字鏈表”。稀疏矩陣—壓縮存儲(chǔ)在十字鏈表中，矩陣的每一個(gè)非零元素用一個(gè)結(jié)點(diǎn)表示，該結(jié)點(diǎn)除了(row，col，value)以外，還要有以下兩個(gè)鏈域：

right：用于連接同一行中的下一個(gè)非零元素；

down：用于連接同一列中的下一個(gè)非零元素。同一行的非零元素通過(guò)right域連接成一個(gè)單鏈表，同一列中的非零元素通過(guò)down域連接成一個(gè)單鏈表。同時(shí)，再附設(shè)一個(gè)存放所有行鏈表的頭指針的一維數(shù)組和一個(gè)存放所有列鏈表的頭指針的一維數(shù)組。rowcolvaluedownright稀疏矩陣—壓縮存儲(chǔ)稀疏矩陣十字鏈表十字鏈表的結(jié)構(gòu)類型說(shuō)明如下：1typedefstructOLNode2{3introw,col; 4datatypevalue;5structOLNode*right,*down;6}OLNode;*OLink;7typedefstruct8{9OLink*row_head,*col_head; 10intm,n,len; 11}CrossList;/*非零元素的行和列下標(biāo)*//*非零元素*//*非零元素所在行表、列表的后繼鏈域*//*行、列鏈表的頭指針向量*//*稀疏矩陣的行數(shù)、列數(shù)、非零元素的個(gè)數(shù)*/稀疏矩陣—壓縮存儲(chǔ)十字鏈表的結(jié)構(gòu)類型說(shuō)明如下：1typedefstructOLNode2{3introw,col; 4datatypevalue;5structOLNode*right,*down;6}OLNode;*OLink;7typedefstruct8{9OLink*row_head,*col_head; 10intm,n,len; 11}CrossList;/*非零元素的行和列下標(biāo)*//*非零元素所在行表、列表的后繼鏈域*//*行、列鏈表的頭指針向量*//*稀疏矩陣的行數(shù)、列數(shù)、非零元素的個(gè)數(shù)*/稀疏矩陣—壓縮存儲(chǔ)廣義表是線性表的推廣，也有人稱其為列表。線性表是由n個(gè)數(shù)據(jù)元素組成的有限序列。(a1，a2，…，ai，…，an)其中每個(gè)組成元素被限定為單元素。廣義表將這種限制突破了，表中的元素可以是單元素，也可以是一個(gè)表。廣義表—邏輯結(jié)構(gòu)中國(guó)舉辦的某體育項(xiàng)目國(guó)際邀請(qǐng)賽，參賽隊(duì)清單可采用如下的表示形式：(俄羅斯，巴西，(國(guó)家，河北，四川)，古巴，美國(guó)，()，日本)韓國(guó)隊(duì)?wèi)?yīng)排在美國(guó)隊(duì)的后面，但由于某種原因未參加，成為空表。國(guó)家隊(duì)、河北隊(duì)、四川隊(duì)均作為東道主的參賽隊(duì)參加，構(gòu)成一個(gè)小的線性表，成為原線性表的一個(gè)數(shù)據(jù)項(xiàng)。這就是廣義表。廣義表是n(n≥0)個(gè)數(shù)據(jù)元素a1，a2，…，ai，…，an的有序序列，一般記作：ls?=?(a1，a2，…，ai，…，an)其中：ls是廣義表的名稱，n是它的長(zhǎng)度。每個(gè)ai?(1≤i≤n)是ls的成員，它可以是單個(gè)元素，也可以是一個(gè)廣義表，分別稱為廣義表ls的單元素和子表。當(dāng)廣義表ls非空時(shí)，稱第一個(gè)元素a1為ls的表頭(head)；稱其余元素組成的表a2，…，ai，…，an)為ls的表尾(tail)。廣義表—邏輯結(jié)構(gòu)通常用大寫字母表示廣義表，用小寫字母表示單個(gè)數(shù)據(jù)元素，廣義表用括號(hào)括起來(lái)，括號(hào)內(nèi)的數(shù)據(jù)元素用逗號(hào)分隔開。廣義表的例子：D?=?(?) 空表，其長(zhǎng)度為零A?=?(a，(b，c))表長(zhǎng)度為2的廣義表 B?=?(A，A，D) 長(zhǎng)度為3的廣義表C?=?(a，C)長(zhǎng)度為2遞歸定義的廣義表C相當(dāng)于無(wú)窮表C?=?(a，(a，(a，(…))))

廣義表—邏輯結(jié)構(gòu)廣義表的重要性質(zhì)：(1)廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表。A?=?(a，(b，c))