數(shù)據(jù)結(jié)構(gòu)2331第4章數(shù)組和廣義表

1、124.1 數(shù)組數(shù)組4.2 廣義表廣義表3 數(shù)組可看成是一種特殊的線性表，其特殊在于，表中的數(shù)組元數(shù)組可看成是一種特殊的線性表，其特殊在于，表中的數(shù)組元素本身也是一種線性表。素本身也是一種線性表。Amn=a0 0 a0 1 a0 2 a0 n-1a1 0 a1 1 a1 2 a1 n-1a2 0 a2 1 a2 2 a2 n-1 am-1 0 am-1 1 am-1 2 am-1 n-14.1 數(shù)數(shù) 組組4.1.1 數(shù)組的邏輯結(jié)構(gòu)和運(yùn)算數(shù)組的邏輯結(jié)構(gòu)和運(yùn)算 數(shù)組數(shù)組是是線性表的推廣線性表的推廣，其每個(gè)元素由一個(gè)值和一，其每個(gè)元素由一個(gè)值和一 組下標(biāo)組成，其中下標(biāo)個(gè)數(shù)稱為組下標(biāo)組成，其中下標(biāo)個(gè)數(shù)

2、稱為數(shù)組的維數(shù)數(shù)組的維數(shù)。 數(shù)組是我們最熟悉的數(shù)據(jù)類型，在早期的高級(jí)語言中，數(shù)組是數(shù)組是我們最熟悉的數(shù)據(jù)類型，在早期的高級(jí)語言中，數(shù)組是唯一可供使用的數(shù)據(jù)類型。由于唯一可供使用的數(shù)據(jù)類型。由于數(shù)組中各元素具有統(tǒng)一的類型數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡單。多維數(shù)組是線性表的推廣。例處理比其它復(fù)雜的結(jié)構(gòu)更為簡單。多維數(shù)組是線性表的推廣。例如，二維數(shù)組：如，二維數(shù)組： 4 二維數(shù)組Amn可以看成是由m個(gè)行向量組成的向量，也可以看成是n個(gè)列向量組成的向量。 數(shù)組一旦被定

3、義，它的維數(shù)和維界就不再改變。數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組通常只有因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組通常只有兩種基本運(yùn)算兩種基本運(yùn)算： 讀讀給定一組下標(biāo)，讀取相應(yīng)的數(shù)據(jù)元素；給定一組下標(biāo)，讀取相應(yīng)的數(shù)據(jù)元素； 寫寫給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素；給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素； Amn=a0 0 a0 1 a0 2 a0 n-1a1 0 a1 1 a1 2 a1 n-1a2 0 a2 1 a2 2 a2 n-1 am-1 0 am-1 1 am-1 2 am-1 n-151.1.存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 由于計(jì)算機(jī)的由

4、于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存放在存儲(chǔ)器排成一列序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中。中。 又由于對(duì)數(shù)組一般不做插入和刪除操作，也就是又由于對(duì)數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存采用順序存儲(chǔ)儲(chǔ)的方法來表示數(shù)組。的方法來表示數(shù)組。 4.1.2 數(shù)組的存儲(chǔ)結(jié)構(gòu)數(shù)組的存儲(chǔ)結(jié)構(gòu)6

5、2.2.存儲(chǔ)方式：存儲(chǔ)方式：（通常有兩種順序存儲(chǔ)方式）（通常有兩種順序存儲(chǔ)方式）行優(yōu)先順序（以行為主存放）行優(yōu)先順序（以行為主存放）將數(shù)組元素按行排將數(shù)組元素按行排列，第列，第i+1i+1個(gè)行向量緊接在第個(gè)行向量緊接在第i i個(gè)行向量后面?zhèn)€行向量后面。以二維數(shù)組。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為：為例，按行優(yōu)先順序存儲(chǔ)的線性序列為： a a0 00 0，a a0 10 1,a,a0 20 2, ,a,a0 n-10 n-1, a, a1 01 0，a a1 11 1,a,a1 21 2, ,a a1 n-11 n-1, , ,a ,am-1 0m-1 0, , a am-1 1m-

6、1 1, a, am-1 2m-1 2 ， ,a ,am-1 n-1m-1 n-1 在在PASCALPASCAL、C C語言語言中，數(shù)組就是按中，數(shù)組就是按行優(yōu)先順序行優(yōu)先順序順序存儲(chǔ)的。順序存儲(chǔ)的。列優(yōu)先順序（以列為主存放）列優(yōu)先順序（以列為主存放）將數(shù)組元素按列向?qū)?shù)組元素按列向量排列，第量排列，第j+1j+1個(gè)列向量緊接在第個(gè)列向量緊接在第j j個(gè)列向量之后個(gè)列向量之后，A A的的m m* *n n個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為：個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為： a a0 00 0,a,a1 01 0, ,a,am-1 0m-1 0,a,a0 10 1,a,a1 11 1, ,a

7、 am-1 1m-1 1, ,a,a0 n-10 n-1,a,a1 n-11 n-1, , , a, am-m-1 n-11 n-1 在在FORTRANFORTRAN語言中，數(shù)組就是按語言中，數(shù)組就是按列優(yōu)先順序列優(yōu)先順序順序存儲(chǔ)的。順序存儲(chǔ)的。7 以上規(guī)則可以推廣到多維數(shù)組的情況：以上規(guī)則可以推廣到多維數(shù)組的情況：行優(yōu)先順序（以行為主存放）行優(yōu)先順序（以行為主存放）以下標(biāo)最右以下標(biāo)最右邊變化最快，最左邊變化最慢的規(guī)則存放。邊變化最快，最左邊變化最慢的規(guī)則存放。列優(yōu)先順序（以列為主存放）列優(yōu)先順序（以列為主存放）以下標(biāo)最左以下標(biāo)最左邊變化最快，最右邊變化最慢的規(guī)則存放。邊變化最快，最右邊變化最

8、慢的規(guī)則存放。 按上述兩種方式順序存儲(chǔ)的數(shù)組，只要知道開始元素的存放地按上述兩種方式順序存儲(chǔ)的數(shù)組，只要知道開始元素的存放地址（即基地址），維數(shù)和每維的上、下界，以及每個(gè)數(shù)組元素所占址（即基地址），維數(shù)和每維的上、下界，以及每個(gè)數(shù)組元素所占用的單元數(shù)，就可以用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)數(shù)。因此，數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取，即。因此，數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取，即順序存順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。83.3.尋址公式（以行為主存放）尋址公式（以行為主存放） 例如，例如，

9、二維數(shù)組二維數(shù)組A Amnmn按按“行優(yōu)先順序行優(yōu)先順序”存儲(chǔ)在內(nèi)存中存儲(chǔ)在內(nèi)存中，假設(shè)，假設(shè)每個(gè)元素占用每個(gè)元素占用k k個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元。 元素元素a aijij的存儲(chǔ)地址應(yīng)是數(shù)組的基地址加上排在的存儲(chǔ)地址應(yīng)是數(shù)組的基地址加上排在a aijij前面的元素所占用的單元數(shù)。因?yàn)榍懊娴脑厮加玫膯卧獢?shù)。因?yàn)閍 aijij位于第位于第i i行、第行、第j j列，前面列，前面i i行一共有行一共有i in n個(gè)元素，第個(gè)元素，第i i行上行上a aijij前面又有前面又有j j個(gè)元素，故它前面一共有個(gè)元素，故它前面一共有i in+jn+j個(gè)元素，因此，個(gè)元素，因此，a aijij的的地址計(jì)算函

10、數(shù)為：地址計(jì)算函數(shù)為： LOC(aLOC(aijij)=LOC(a)=LOC(a0000)+(i)+(i* *n+j)n+j)* *k k 9 在科學(xué)與工程計(jì)算問題中，矩陣是一種常用的數(shù)學(xué)在科學(xué)與工程計(jì)算問題中，矩陣是一種常用的數(shù)學(xué)對(duì)象，在高級(jí)語言編制程序時(shí)，簡單而又自然的方法，對(duì)象，在高級(jí)語言編制程序時(shí)，簡單而又自然的方法，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡單，并且存儲(chǔ)的密度為也非常簡單，并且存儲(chǔ)的密度為1 1。但是在矩陣中非零

11、。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來存儲(chǔ)密度仍為況下，看起來存儲(chǔ)密度仍為1 1，但實(shí)際上占用了許多單，但實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)造元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)造成極大的浪費(fèi)，為了節(jié)省存儲(chǔ)空間，成極大的浪費(fèi)，為了節(jié)省存儲(chǔ)空間， 我們可以對(duì)這類我們可以對(duì)這類矩陣進(jìn)行矩陣進(jìn)行壓縮存儲(chǔ)壓縮存儲(chǔ)：即為多個(gè)相同的非零元素只分配一即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。4.1.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)1

12、01 1、對(duì)稱矩陣、對(duì)稱矩陣 1.1.定義：定義：在一個(gè)在一個(gè)n n階方陣階方陣A A中，若元素滿足下述性質(zhì)：中，若元素滿足下述性質(zhì)： a aijij=a=ajiji 0i,jn-1 0i,jn-1 則稱則稱A A為對(duì)稱矩陣為對(duì)稱矩陣。如下圖便是一個(gè)。如下圖便是一個(gè)5 5階對(duì)稱矩陣。階對(duì)稱矩陣。 1 5 1 3 7 5 0 8 0 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 特殊矩陣特殊矩陣即即指非零元素或零元素的分布有一定規(guī)指非零元素或零元素的分布有一定規(guī)律的矩陣律的矩陣。下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。一、特殊矩陣一、特殊矩陣11

13、 在這個(gè)下三角矩陣中，第在這個(gè)下三角矩陣中，第i i行恰有行恰有i i個(gè)元素，元素總個(gè)元素，元素總數(shù)為：數(shù)為： (i)=n(n+1)/2(i)=n(n+1)/2 因此，我們可以按圖中箭頭所指的次序?qū)⑦@些元素存放在因此，我們可以按圖中箭頭所指的次序?qū)⑦@些元素存放在一個(gè)一維數(shù)組一個(gè)一維數(shù)組S1.n(n+1)/2S1.n(n+1)/2中。為了便于訪問對(duì)稱矩陣中。為了便于訪問對(duì)稱矩陣A A中的中的元素，我們必須在元素，我們必須在a aijij和和SkSk之間找一個(gè)對(duì)應(yīng)關(guān)系。之間找一個(gè)對(duì)應(yīng)關(guān)系。 2.2.物理存儲(chǔ)：物理存儲(chǔ)： 對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存

14、儲(chǔ)矩陣只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每兩個(gè)對(duì)稱的元素共享一個(gè)中上三角或下三角中的元素，讓每兩個(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失一般性，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失一般性，我們按我們按“行優(yōu)先行優(yōu)先順序順序”存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素，其存儲(chǔ)形式如圖所示元素，其存儲(chǔ)形式如圖所示：a0 0a1 0 a 1 1a2 0 a2 1 a2 2 .an-1 0 a n-1 1 a n-1 2 a n-1 n -1 12 (1) 若若ij，則，則ai j在在下三角形下三角形中。中。ai j之前的之前的i行（從第行

15、（從第0 行到第行到第i-1行）一共有行）一共有1+2+i=i(i+1)/2個(gè)元素，在第個(gè)元素，在第i行上，行上， ai j之前恰有之前恰有j個(gè)元素（即個(gè)元素（即ai 0,ai 1,ai 2,ai 3,ai j-1），）， 因此有：因此有：(2) 若若ij，則，則aij是在上三角矩陣中。因?yàn)槭窃谏先蔷仃囍?。因?yàn)閍ij=aji，所以只，所以只 要交換上述對(duì)應(yīng)關(guān)系式中的要交換上述對(duì)應(yīng)關(guān)系式中的i和和j即可得到：即可得到： k=j*(j+1)/2+i 0kn(n+1)/2 -1下標(biāo)變換公式下標(biāo)變換公式：（以：（以下三角下三角表示）表示）即：即： ai jSSi*(i+1)/2+j k=i*(i+1

16、)/2+j 0k n(n+1)/2-1 令令 I=max(i,j)， J=min(i,j)，則，則k和和 i, j的對(duì)應(yīng)關(guān)系的對(duì)應(yīng)關(guān)系 可統(tǒng)一為：可統(tǒng)一為： k=I*(I-1)/2+J 0kn(n+1)/2 -113 有了上述的下標(biāo)交換關(guān)系，對(duì)于任意給定一組下標(biāo)有了上述的下標(biāo)交換關(guān)系，對(duì)于任意給定一組下標(biāo)(i(i，j)j)，均可在，均可在SkSk中找到矩陣元素中找到矩陣元素a aijij，反之，對(duì)所有，反之，對(duì)所有的的k=0,1,2,3,k=0,1,2,3,n(n+1)/2-1n(n+1)/2-1，都能確定，都能確定SkSk中的元素在中的元素在矩陣中的位置矩陣中的位置(i,j)(i,j)。由此

17、，稱。由此，稱Sn(n+1)/2Sn(n+1)/2為對(duì)稱矩陣為對(duì)稱矩陣A A的壓縮存儲(chǔ)，見下圖：的壓縮存儲(chǔ)，見下圖：a00a10a12a21an-1 1 an-1 n-1k=0 1 2 3 n(n+1)/2-1 例如例如a31和和a13均存儲(chǔ)在均存儲(chǔ)在 sa4中，這是因?yàn)椋褐?，這是因?yàn)椋?k=I*(I-1)/2+J=3*(3-1)/2+1=4142、三角矩陣、三角矩陣 以主對(duì)角線劃分，三角矩陣有上三角和下三角兩種。以主對(duì)角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對(duì)角線）上三角矩陣如圖所示，它的下三角（不包括主對(duì)角線）中的元素均為常數(shù)。下三角矩陣正好相反，它

18、的主對(duì)中的元素均為常數(shù)。下三角矩陣正好相反，它的主對(duì)角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。角矩陣常數(shù)為零。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)(a)上三角矩陣上三角矩陣 (b)(b)下三角矩下三角矩15 三角矩陣中的重復(fù)元素三角矩陣中的重復(fù)元素c c可共享一個(gè)存儲(chǔ)空間，其余的可共享一個(gè)存儲(chǔ)空間，其余的元素正好有元素正好有n(n+1)/2n(n+1)/2個(gè)，因此，三角矩陣可壓縮存

19、儲(chǔ)到個(gè)，因此，三角矩陣可壓縮存儲(chǔ)到向量向量s0.n(n+1)/2s0.n(n+1)/2中，其中中，其中c c存放在向量的最后一個(gè)分存放在向量的最后一個(gè)分量中。量中。 上三角矩陣中上三角矩陣中，主對(duì)角線之上的第，主對(duì)角線之上的第p p行行(0pn)(0pjijk= 下三角矩陣下三角矩陣的存儲(chǔ)和對(duì)稱矩陣類似，的存儲(chǔ)和對(duì)稱矩陣類似，sksk和和a aijij對(duì)應(yīng)對(duì)應(yīng)關(guān)系是：關(guān)系是： i i(i+1)/2+j (i+1)/2+j ijij n(n+1)/2n(n+1)/2 i ij jk=163 3、對(duì)角矩陣、對(duì)角矩陣 對(duì)角矩陣中，所有的非零元素集中在以主對(duì)角線對(duì)角矩陣中，所有的非零元素集中在以主對(duì)角

20、線為了中心的帶狀區(qū)域中，即除了主對(duì)角線和主對(duì)角線為了中心的帶狀區(qū)域中，即除了主對(duì)角線和主對(duì)角線相鄰兩側(cè)的若干條對(duì)角線上的元素之外，其余元素皆相鄰兩側(cè)的若干條對(duì)角線上的元素之外，其余元素皆為零。下圖給出了一個(gè)為零。下圖給出了一個(gè)三對(duì)角矩陣三對(duì)角矩陣: : a00 a01 a10 a11 a12 a21 a22 a23 . . . an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-10 00 017 在三對(duì)角矩陣中非0元素的分布有明顯的規(guī)律，可將它們壓縮存儲(chǔ)到一維數(shù)組中，并找到每個(gè)非0元素在一維數(shù)組中的對(duì)應(yīng)關(guān)系。 可按行優(yōu)序?yàn)橹餍騺泶鎯?chǔ)三對(duì)角矩陣。除第0行和第n

21、-1行是2個(gè)元素外，每行的非零元素都要是3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為3n-2。a00a01 a10a11a12a21 a n-1 n-2a n-1 n-1K=0 1 2 3 4 5 3n-2 3n-1 數(shù)組數(shù)組s中的元素中的元素sk與三對(duì)角帶狀矩陣中的元素與三對(duì)角帶狀矩陣中的元素aij存在存在一一對(duì)應(yīng)關(guān)系，在一一對(duì)應(yīng)關(guān)系，在aij之前有之前有i行行,共有共有3*i-1個(gè)非零元素，在個(gè)非零元素，在第第i行，有行，有j-i+1個(gè)非零元素，這樣，非零元素個(gè)非零元素，這樣，非零元素aij的地址為：的地址為： LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*L =LOC(0,0)+(2

22、i+j)*L18 上例中，上例中，a a3434對(duì)應(yīng)著對(duì)應(yīng)著s10s10。 k=k=2 2* *i+ji+j=2=2* *3+4=103+4=10 a a2121對(duì)應(yīng)著對(duì)應(yīng)著s5 s5 k=2 k=2* *2+1=52+1=5 由此，我們稱由此，我們稱s0.3s0.3* *n-2n-2是三對(duì)角是三對(duì)角帶狀矩陣帶狀矩陣A A的壓縮存儲(chǔ)表示。的壓縮存儲(chǔ)表示。 上述的各種特殊矩陣，其非零元素的分布都是有規(guī)上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)律的，因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)向量中，并且一般都能找到矩陣中的元素與該向量的向量中，并且一般

23、都能找到矩陣中的元素與該向量的對(duì)應(yīng)關(guān)系，通過這個(gè)關(guān)系，仍能對(duì)矩陣的元素進(jìn)行隨對(duì)應(yīng)關(guān)系，通過這個(gè)關(guān)系，仍能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。機(jī)存取。19 什么是稀疏矩陣？簡單說，什么是稀疏矩陣？簡單說，設(shè)矩陣設(shè)矩陣A A中有中有s s個(gè)非零元素，個(gè)非零元素，若若s s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，則稱遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，則稱A A為稀疏矩陣為稀疏矩陣。稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)即只存儲(chǔ)稀疏矩陣中的非零元即只存儲(chǔ)稀疏矩陣中的非零元素。有兩種存儲(chǔ)方法。素。有兩種存儲(chǔ)方法。 精確點(diǎn)，設(shè)在的矩陣精確點(diǎn)，設(shè)在的矩陣A A中，有中，有s s個(gè)非零元素。令個(gè)非零元素。令 e=s/(me=s/(m* *n)n)

24、，稱，稱e e為矩陣的稀疏因子。通常認(rèn)為為矩陣的稀疏因子。通常認(rèn)為e0.05e0.05時(shí)稱之為稀疏矩陣。在存時(shí)稱之為稀疏矩陣。在存儲(chǔ)稀疏矩陣時(shí)，為了節(jié)省存儲(chǔ)單元，很自然地想到使用壓縮存儲(chǔ)儲(chǔ)稀疏矩陣時(shí)，為了節(jié)省存儲(chǔ)單元，很自然地想到使用壓縮存儲(chǔ)方法。方法。 由于非零元素的分布一般是沒有規(guī)律的，因此在存儲(chǔ)非零元素由于非零元素的分布一般是沒有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（i,j)i,j)。反之，。反之，一個(gè)三元組一個(gè)三元組(i,j,a(i,j,aijij) )唯一確定了矩陣唯一確定了矩陣A A的一個(gè)非零元。因此，稀疏

25、的一個(gè)非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。二、稀疏矩陣的壓縮存儲(chǔ)二、稀疏矩陣的壓縮存儲(chǔ)20 例如，下列三元組表例如，下列三元組表 ( (1,2,12)，(1,3,9)，(3,1,- 3)，(3,6,14)，(4,3,24), (5,2,18)，(6,1,15)，(6,4,-7) ) 加上加上(6,7)(6,7)這一對(duì)行、列值便可作為下列矩陣這一對(duì)行、列值便可作為下列矩陣M M的另的另一種描述。而由上述三元組表的不同表示方法可引出一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲(chǔ)方法。稀疏矩陣不同的壓縮存

26、儲(chǔ)方法。 0 12 9 0 0 0 0 0 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 0 18 0 0 0 0 0 15 0 0 15 0 0 7 0 0 0 7 0 0 0 M=T=0 0 -3 0 0 150 0 -3 0 0 1512 0 0 0 18 012 0 0 0 18 09 0 0 24 0 09 0 0 24 0 00 0 0 0 0 0 0 0 0 0 7 70 0 14 0 0 0

27、 0 0 14 0 0 0 0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0211 1、三元組順序表、三元組順序表 稀疏矩陣的三元組順序表表示法稀疏矩陣的三元組順序表表示法將矩陣中的非零元將矩陣中的非零元素化成三元組形式并按行的不減次序（同行按列的遞增素化成三元組形式并按行的不減次序（同行按列的遞增次序）存放在內(nèi)存中。次序）存放在內(nèi)存中。1).1).三元組表結(jié)構(gòu)：三元組表結(jié)構(gòu)： 假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來表示三元組表，則可得到稀疏假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲(chǔ)方法矩陣的一種壓縮存儲(chǔ)方法三元組順序表。三元組順序表。 #defin

28、e maxnum 10#define maxnum 10 typedef struct node typedef struct node int i, j; / int i, j; /* *非零元的行下標(biāo)和列下標(biāo)非零元的行下標(biāo)和列下標(biāo)* */ / DataType v; / DataType v; /* *非零元素的值非零元素的值* */ / NODENODE; ;三元組三元組 22 typedef struct spmatrix typedef struct spmatrix NODE datamaxnum+1; NODE datamaxnum+1; / /* *非零元三元組表非零元三元組表

29、* */ / int mu,nu,tu; int mu,nu,tu; / /* *矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)* */ / SpMatrixTp;SpMatrixTp;稀疏矩陣三元組表存儲(chǔ)類型稀疏矩陣三元組表存儲(chǔ)類型 設(shè)設(shè):SpMatrixTp M ; :SpMatrixTp M ; 則下圖中所示的稀疏矩陣的三則下圖中所示的稀疏矩陣的三元組的表示如右：元組的表示如右： 0 12 9 0 0 0 0 0 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 -3 0 0 0 0 14 0 0 0 24 0 0

30、 0 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 0 18 0 0 0 0 0 15 0 0 15 0 0 7 0 0 07 0 0 0 i j v i j v 1 1 2 12 1 1 2 12 2 1 3 9 2 1 3 9 3 3 1 -3 3 3 1 -3 4 3 6 14 4 3 6 14 5 4 3 24 5 4 3 24 6 5 2 18 6 5 2 18 7 6 1 15 7 6 1 15 8 6 4 -78 6 4 -7 三元組表三元組表M.datap.iM.datap.jM.datap.v 232). 稀疏矩陣的轉(zhuǎn)置運(yùn)算稀疏矩陣的轉(zhuǎn)置運(yùn)算 設(shè)：稀疏矩陣采

31、用三元組表存儲(chǔ)表示，現(xiàn)求稀疏矩陣設(shè)：稀疏矩陣采用三元組表存儲(chǔ)表示，現(xiàn)求稀疏矩陣M M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣T T（M M、T T均是三元組表）。均是三元組表）。轉(zhuǎn)置的含義轉(zhuǎn)置的含義： m mn n的矩陣的矩陣M M轉(zhuǎn)置轉(zhuǎn)置方法方法：將將M M轉(zhuǎn)置為轉(zhuǎn)置為T T，就是將，就是將M M的三元組表的三元組表M.dataM.data置換為置換為T T的三元組表的三元組表T.dataT.data，如果只是簡單地交換，如果只是簡單地交換M.dataM.data中中i i和和j j的內(nèi)容，那么得到的的內(nèi)容，那么得到的T.dataT.data將是一個(gè)按列優(yōu)先順序存儲(chǔ)將是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣的稀疏矩陣T

32、 T，要得到按行優(yōu)先順序存儲(chǔ)的，要得到按行優(yōu)先順序存儲(chǔ)的T.dataT.data，就必，就必須重新排列三元組的順序。須重新排列三元組的順序。 由于由于M M的列是的列是T T的行，因此，按的行，因此，按M.dataM.data的列序轉(zhuǎn)置，所的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣得到的轉(zhuǎn)置矩陣B B的三元組表的三元組表T.dataT.data必定是按行優(yōu)先存放必定是按行優(yōu)先存放的。的。 n nm m的矩陣的矩陣T T， 且：且： Mij=Tji Mij=Tji （1 1i im m，1 1j jn n）24 按這種方法設(shè)計(jì)的算法，按這種方法設(shè)計(jì)的算法，其基本思想是其基本思想是：對(duì)對(duì)M M中的每一列中的每一

33、列 col(1col(1colcoln)n)，通過從頭至尾掃描三元表，通過從頭至尾掃描三元表M.dataM.data，找出，找出所有列號(hào)等于所有列號(hào)等于colcol的那些三元組，將它們的行號(hào)和列號(hào)互換的那些三元組，將它們的行號(hào)和列號(hào)互換后依次放入后依次放入T.dataT.data中，即可得到中，即可得到T T的按行優(yōu)先的壓縮存儲(chǔ)表的按行優(yōu)先的壓縮存儲(chǔ)表示。示。 r c v r c v 1 1 2 12 1 1 2 12 2 1 3 9 2 1 3 9 3 3 1 -3 3 3 1 -3 4 3 6 14 4 3 6 14 5 4 3 24 5 4 3 24 6 5 2 18 6 5 2 18

34、7 6 1 15 7 6 1 15 8 6 4 -78 6 4 -7 r c v r c v 1 1 3 -3 1 1 3 -3 2 1 6 15 2 1 6 15 3 2 1 12 3 2 1 12 4 2 5 18 4 2 5 18 5 3 1 9 5 3 1 9 6 3 4 24 6 3 4 24 7 4 6 -7 7 4 6 -7 8 6 3 148 6 3 14 轉(zhuǎn)置轉(zhuǎn)置25稀疏矩陣三元組表表示下的稀疏矩陣三元組表表示下的轉(zhuǎn)置運(yùn)算算法轉(zhuǎn)置運(yùn)算算法：（見（見P59算法）算法） SpMatrixTp *transmat ( SpMatrixTp *a ) /*用三元組表存儲(chǔ)表示，求稀疏矩

35、陣用三元組表存儲(chǔ)表示，求稀疏矩陣a a的轉(zhuǎn)置矩陣并返回的轉(zhuǎn)置矩陣并返回* */ / int p, q, col; int p, q, col; SpMatrixTp SpMatrixTp * *b ;b ; b=molloc(sizeof(spmatrix); b=molloc(sizeof(spmatrix); / /* *申請(qǐng)三元組申請(qǐng)三元組b b的存儲(chǔ)空間的存儲(chǔ)空間* */ / b-mu=a-nu ; b-nu=a-mu ; b-tu=a-tu ; b-mu=a-nu ; b-nu=a-mu ; b-tu=a-tu ; if (b-tu0) if (b-tu0) q=0 ; /*q指示三

36、元組指示三元組b的當(dāng)前結(jié)點(diǎn)序號(hào)的當(dāng)前結(jié)點(diǎn)序號(hào)*/ for ( col=1; colnu; col+ ) for ( p=1; ptu; p+) if ( a-datap.j=col ) b-dataq.i=a-datap.j; b-dataq.j=a-datap.i; b-dataq.v=a-datap.v ; q+; return b; 26 分析這個(gè)算法，主要的工作是在分析這個(gè)算法，主要的工作是在p p和和colcol的兩的兩個(gè)循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為個(gè)循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為O(nO(n* *t)t)，即矩陣的列數(shù)和非零元的個(gè)數(shù)的乘積，即矩陣的列數(shù)和非零元的個(gè)數(shù)的乘積

37、成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為：成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為： for(col=1;col=n;+col)for(col=1;col=n;+col) for(row=1;row=m;+row) for(row=1;row=m;+row) tcolrow=mrowcol; tcolrow=mrowcol; 其時(shí)間復(fù)雜度為其時(shí)間復(fù)雜度為O(nO(n* *m)m)。當(dāng)非零元素的個(gè)數(shù)。當(dāng)非零元素的個(gè)數(shù)t t和和m m* *n n同數(shù)量級(jí)時(shí)，算法同數(shù)量級(jí)時(shí)，算法TranposeSMatrixTranposeSMatrix的時(shí)的時(shí)間復(fù)雜度為間復(fù)雜度為O(nO(n* *n n2 2) )。27 三

38、元組順序表雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時(shí)還有可能增加算法的難度。因此，此算法僅適用于t=m*n的情況。 下面給出另外一種稱之為快速轉(zhuǎn)置的算法，其算法思想為：對(duì)A掃描一次，按A第二列提供的列號(hào)一次確定位置裝入B的一個(gè)三元組。具體實(shí)施如下：一遍掃描先確定三元組的位置關(guān)系，二次掃描由位置關(guān)系裝入三元組?？梢?，位置關(guān)系是此種算法的關(guān)鍵。28 為了預(yù)先確定矩陣為了預(yù)先確定矩陣M M中的每一列的第一個(gè)非零元素在數(shù)組中的每一列的第一個(gè)非零元素在數(shù)組B B中應(yīng)有的位置，需要先求得矩陣中應(yīng)有的位置，需要先求得矩陣M M中的每一列中非零元素中的每一列中非零元素的個(gè)數(shù)。因?yàn)椋壕仃?/p>

39、的個(gè)數(shù)。因?yàn)椋壕仃嘙 M中第一列的第一個(gè)非零元素在數(shù)組中第一列的第一個(gè)非零元素在數(shù)組B B中應(yīng)有的位置等于前一列第一個(gè)非零元素的位置加上前列中應(yīng)有的位置等于前一列第一個(gè)非零元素的位置加上前列非零元素的個(gè)數(shù)。非零元素的個(gè)數(shù)。 為此，需要設(shè)置兩個(gè)一維數(shù)為此，需要設(shè)置兩個(gè)一維數(shù) num0.nnum0.n和和cpot0.ncpot0.n num0.n num0.n：統(tǒng)計(jì)統(tǒng)計(jì)M M中每列非零元素的個(gè)數(shù)，中每列非零元素的個(gè)數(shù)， numcolnumcol的值可以由的值可以由A A的第二列求得。的第二列求得。 cpot0.ncpot0.n：由遞推關(guān)系得出：由遞推關(guān)系得出M M中的每列第一個(gè)非中的每列第一個(gè)非

40、零元素在零元素在B B中的位置。中的位置。29 算法通過cpot數(shù)組建立位置對(duì)應(yīng)關(guān)系： cpot1=1 cpotcol=cpotcol-1+numcol-1 2=cpl=a.n 例如：圖5.4中的矩陣M和相應(yīng)的三元組A可以求得numcol和 cpotcol的值如下： col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 930 1 2 vqA i j v第一列元素個(gè)數(shù) 第二列元素個(gè)數(shù) 第三列元素個(gè)數(shù)numcpotq=cpotcol2 1 vpp31快速轉(zhuǎn)置算法如下：快速轉(zhuǎn)置算法如下： void fasttranstri(tritu

41、pletable b,tritupletable a) int p,q,col,k; int num0.a.n,copt0.a.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”n); for(col=1;col=a.u;+col) numcol=0; for(k=1;k=a.t;+k) +numa.datak.j;321. C語言中對(duì)數(shù)組元素的存放方式通常采用語言中對(duì)數(shù)組元素的存放方式通常采用( ) A. 按行為主的存儲(chǔ)結(jié)構(gòu)按行為主的存儲(chǔ)結(jié)構(gòu) B.按行或列為主的存儲(chǔ)結(jié)構(gòu)按行或列為主的存儲(chǔ)結(jié)構(gòu) C. 按列為主的存儲(chǔ)結(jié)構(gòu)按列為主的存儲(chǔ)結(jié)構(gòu) D

42、.按行和列為主的存儲(chǔ)結(jié)構(gòu)按行和列為主的存儲(chǔ)結(jié)構(gòu)2. 一個(gè)一個(gè)nn的對(duì)稱矩陣，如果以行為主序壓縮存入內(nèi)存，則其容量的對(duì)稱矩陣，如果以行為主序壓縮存入內(nèi)存，則其容量 為（為（ ） An-1 B. n C. nn D. n(n+1)/2 3. 稀疏矩陣一般采用下列哪種方法壓縮存儲(chǔ)？（稀疏矩陣一般采用下列哪種方法壓縮存儲(chǔ)？（ ） A.三維數(shù)組三維數(shù)組 B.單鏈表單鏈表 C. 三元組表三元組表 D. 散列表散列表 4. 二維數(shù)組在機(jī)器級(jí)的具體實(shí)現(xiàn)，通常均采用二維數(shù)組在機(jī)器級(jí)的具體實(shí)現(xiàn)，通常均采用_ _存存儲(chǔ)結(jié)構(gòu)。儲(chǔ)結(jié)構(gòu)。5. 數(shù)組通常具有兩種基本運(yùn)算，即數(shù)組通常具有兩種基本運(yùn)算，即_。6. 矩陣壓縮存儲(chǔ)

43、的基本思想是為值相同的多個(gè)元素只分配一個(gè)存儲(chǔ)矩陣壓縮存儲(chǔ)的基本思想是為值相同的多個(gè)元素只分配一個(gè)存儲(chǔ)空間，為空間，為_不分配空間。不分配空間。請(qǐng)你給出答案請(qǐng)你給出答案思考題思考題想一想想一想337. 同一數(shù)組中的元素，它們（同一數(shù)組中的元素，它們（ ） A. 長度可以不同長度可以不同 B.類型不限類型不限 C. 類型相同類型相同 D.長度不限長度不限8. 數(shù)組是一個(gè)數(shù)組是一個(gè)( )線性表結(jié)構(gòu)線性表結(jié)構(gòu). A. 不加限制的不加限制的 B. 加了限制的加了限制的 C. 推廣了的推廣了的 D. 非非9. 數(shù)組占用的空間數(shù)組占用的空間( ) A. 必須連續(xù)必須連續(xù) B.可以不連續(xù)可以不連續(xù) C. 不能連續(xù)不能連續(xù) D. 不必連續(xù)不必連續(xù)10. 數(shù)組通常只有數(shù)組通常只有_和和_二種運(yùn)算二種運(yùn)算,因此常采用因此常采用_來存儲(chǔ)數(shù)組。來存儲(chǔ)數(shù)組。請(qǐng)你給出答案請(qǐng)你給出答案思考題思考題想一想想一想廣義表廣義表1廣義表的定義廣義表的定義2廣義表的基本運(yùn)算廣義表的基本運(yùn)算3廣義表的存儲(chǔ)結(jié)構(gòu)廣義