數(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)和運算數(shù)組的邏輯結(jié)構(gòu)和運算 數(shù)組數(shù)組是是線性表的推廣線性表的推廣，其每個元素由一個值和一，其每個元素由一個值和一 組下標組成，其中下標個數(shù)稱為組下標組成，其中下標個數(shù)

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

3、義，它的維數(shù)和維界就不再改變。數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組通常只有因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組通常只有兩種基本運算兩種基本運算： 讀讀給定一組下標，讀取相應(yīng)的數(shù)據(jù)元素；給定一組下標，讀取相應(yīng)的數(shù)據(jù)元素； 寫寫給定一組下標，修改相應(yīng)的數(shù)據(jù)元素；給定一組下標，修改相應(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.存儲結(jié)構(gòu)存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 由于計算機的由

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

5、2.2.存儲方式：存儲方式：（通常有兩種順序存儲方式）（通常有兩種順序存儲方式）行優(yōu)先順序（以行為主存放）行優(yōu)先順序（以行為主存放）將數(shù)組元素按行排將數(shù)組元素按行排列，第列，第i+1i+1個行向量緊接在第個行向量緊接在第i i個行向量后面?zhèn)€行向量后面。以二維數(shù)組。以二維數(shù)組為例，按行優(yōu)先順序存儲的線性序列為：為例，按行優(yōu)先順序存儲的線性序列為： 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)先順序順序存儲的。順序存儲的。列優(yōu)先順序（以列為主存放）列優(yōu)先順序（以列為主存放）將數(shù)組元素按列向?qū)?shù)組元素按列向量排列，第量排列，第j+1j+1個列向量緊接在第個列向量緊接在第j j個列向量之后個列向量之后，A A的的m m* *n n個元素按列優(yōu)先順序存儲的線性序列為：個元素按列優(yōu)先順序存儲的線性序列為： 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)先順序順序存儲的。順序存儲的。7 以上規(guī)則可以推廣到多維數(shù)組的情況：以上規(guī)則可以推廣到多維數(shù)組的情況：行優(yōu)先順序（以行為主存放）行優(yōu)先順序（以行為主存放）以下標最右以下標最右邊變化最快，最左邊變化最慢的規(guī)則存放。邊變化最快，最左邊變化最慢的規(guī)則存放。列優(yōu)先順序（以列為主存放）列優(yōu)先順序（以列為主存放）以下標最左以下標最左邊變化最快，最右邊變化最慢的規(guī)則存放。邊變化最快，最右邊變化最

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

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

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

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

12、01 1、對稱矩陣、對稱矩陣 1.1.定義：定義：在一個在一個n n階方陣階方陣A A中，若元素滿足下述性質(zhì)：中，若元素滿足下述性質(zhì)： a aijij=a=ajiji 0i,jn-1 0i,jn-1 則稱則稱A A為對稱矩陣為對稱矩陣。如下圖便是一個。如下圖便是一個5 5階對稱矩陣。階對稱矩陣。 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ī)律的矩陣律的矩陣。下面我們討論幾種特殊矩陣的壓縮存儲。下面我們討論幾種特殊矩陣的壓縮存儲。一、特殊矩陣一、特殊矩陣11

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

14、儲矩陣只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間存儲空間，這樣，能節(jié)約近一半的存儲空間。不失一般性，這樣，能節(jié)約近一半的存儲空間。不失一般性，我們按我們按“行優(yōu)先行優(yōu)先順序順序”存儲主對角線（包括對角線）以下的存儲主對角線（包括對角線）以下的元素，其存儲形式如圖所示元素，其存儲形式如圖所示：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個元素，在第個元素，在第i行上，行上， ai j之前恰有之前恰有j個元素（即個元素（即ai 0,ai 1,ai 2,ai 3,ai j-1），）， 因此有：因此有：(2) 若若ij，則，則aij是在上三角矩陣中。因為是在上三角矩陣中。因為aij=aji，所以只，所以只 要交換上述對應(yīng)關(guān)系式中的要交換上述對應(yīng)關(guān)系式中的i和和j即可得到：即可得到： k=j*(j+1)/2+i 0kn(n+1)/2 -1下標變換公式下標變換公式：（以：（以下三角下三角表示）表示）即：即： 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的對應(yīng)關(guān)系的對應(yīng)關(guān)系 可統(tǒng)一為：可統(tǒng)一為： k=I*(I-1)/2+J 0kn(n+1)/2 -113 有了上述的下標交換關(guān)系，對于任意給定一組下標有了上述的下標交換關(guān)系，對于任意給定一組下標(i(i，j)j)，均可在，均可在SkSk中找到矩陣元素中找到矩陣元素a aijij，反之，對所有，反之，對所有的的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為對稱矩陣為對稱矩陣A A的壓縮存儲，見下圖：的壓縮存儲，見下圖：a00a10a12a21an-1 1 an-1 n-1k=0 1 2 3 n(n+1)/2-1 例如例如a31和和a13均存儲在均存儲在 sa4中，這是因為：中，這是因為： k=I*(I-1)/2+J=3*(3-1)/2+1=4142、三角矩陣、三角矩陣 以主對角線劃分，三角矩陣有上三角和下三角兩種。以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對角線）上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣正好相反，它

18、的主對中的元素均為常數(shù)。下三角矩陣正好相反，它的主對角線上方均為常數(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 三角矩陣中的重復元素三角矩陣中的重復元素c c可共享一個存儲空間，其余的可共享一個存儲空間，其余的元素正好有元素正好有n(n+1)/2n(n+1)/2個，因此，三角矩陣可壓縮存

19、儲到個，因此，三角矩陣可壓縮存儲到向量向量s0.n(n+1)/2s0.n(n+1)/2中，其中中，其中c c存放在向量的最后一個分存放在向量的最后一個分量中。量中。 上三角矩陣中上三角矩陣中，主對角線之上的第，主對角線之上的第p p行行(0pn)(0pjijk= 下三角矩陣下三角矩陣的存儲和對稱矩陣類似，的存儲和對稱矩陣類似，sksk和和a aijij對應(yīng)對應(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、對角矩陣、對角矩陣 對角矩陣中，所有的非零元素集中在以主對角線對角矩陣中，所有的非零元素集中在以主對角

20、線為了中心的帶狀區(qū)域中，即除了主對角線和主對角線為了中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。下圖給出了一個為零。下圖給出了一個三對角矩陣三對角矩陣: : 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 在三對角矩陣中非0元素的分布有明顯的規(guī)律，可將它們壓縮存儲到一維數(shù)組中，并找到每個非0元素在一維數(shù)組中的對應(yīng)關(guān)系。 可按行優(yōu)序為主序來存儲三對角矩陣。除第0行和第n

21、-1行是2個元素外，每行的非零元素都要是3個，因此，需存儲的元素個數(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與三對角帶狀矩陣中的元素與三對角帶狀矩陣中的元素aij存在存在一一對應(yīng)關(guān)系，在一一對應(yīng)關(guān)系，在aij之前有之前有i行行,共有共有3*i-1個非零元素，在個非零元素，在第第i行，有行，有j-i+1個非零元素，這樣，非零元素個非零元素，這樣，非零元素aij的地址為：的地址為： LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*L =LOC(0,0)+(2

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

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

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

25、的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。二、稀疏矩陣的壓縮存儲二、稀疏矩陣的壓縮存儲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)這一對行、列值便可作為下列矩陣這一對行、列值便可作為下列矩陣M M的另的另一種描述。而由上述三元組表的不同表示方法可引出一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。稀疏矩陣不同的壓縮存

26、儲方法。 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è)以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法矩陣的一種壓縮存儲方法三元組順序表。三元組順序表。 #defin

28、e maxnum 10#define maxnum 10 typedef struct node typedef struct node int i, j; / int i, j; /* *非零元的行下標和列下標非零元的行下標和列下標* */ / 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ù)和非零元個數(shù)矩陣的行數(shù)、列數(shù)和非零元個數(shù)* */ / SpMatrixTp;SpMatrixTp;稀疏矩陣三元組表存儲類型稀疏矩陣三元組表存儲類型 設(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)置運算稀疏矩陣的轉(zhuǎn)置運算 設(shè)：稀疏矩陣采

31、用三元組表存儲表示，現(xiàn)求稀疏矩陣設(shè)：稀疏矩陣采用三元組表存儲表示，現(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將是一個按列優(yōu)先順序存儲將是一個按列優(yōu)先順序存儲的稀疏矩陣的稀疏矩陣T

32、 T，要得到按行優(yōu)先順序存儲的，要得到按行優(yōu)先順序存儲的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è)計的算法，按這種方法設(shè)計的算法，其基本思想是其基本思想是：對對M M中的每一列中的每一

33、列 col(1col(1colcoln)n)，通過從頭至尾掃描三元表，通過從頭至尾掃描三元表M.dataM.data，找出，找出所有列號等于所有列號等于colcol的那些三元組，將它們的行號和列號互換的那些三元組，將它們的行號和列號互換后依次放入后依次放入T.dataT.data中，即可得到中，即可得到T T的按行優(yōu)先的壓縮存儲表的按行優(yōu)先的壓縮存儲表示。示。 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)置運算算法轉(zhuǎn)置運算算法：（見（見P59算法）算法） SpMatrixTp *transmat ( SpMatrixTp *a ) /*用三元組表存儲表示，求稀疏矩

35、陣用三元組表存儲表示，求稀疏矩陣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); / /* *申請三元組申請三元組b b的存儲空間的存儲空間* */ / 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的當前結(jié)點序號的當前結(jié)點序號*/ 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 分析這個算法，主要的工作是在分析這個算法，主要的工作是在p p和和colcol的兩的兩個循環(huán)中完成的，故算法的時間復雜度為個循環(huán)中完成的，故算法的時間復雜度為O(nO(n* *t)t)，即矩陣的列數(shù)和非零元的個數(shù)的乘積，即矩陣的列數(shù)和非零元的個數(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; 其時間復雜度為其時間復雜度為O(nO(n* *m)m)。當非零元素的個數(shù)。當非零元素的個數(shù)t t和和m m* *n n同數(shù)量級時，算法同數(shù)量級時，算法TranposeSMatrixTranposeSMatrix的時的時間復雜度為間復雜度為O(nO(n* *n n2 2) )。27 三

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

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

40、零元素在零元素在B B中的位置。中的位置。29 算法通過cpot數(shù)組建立位置對應(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第一列元素個數(shù) 第二列元素個數(shù) 第三列元素個數(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語言中對數(shù)組元素的存放方式通常采用語言中對數(shù)組元素的存放方式通常采用( ) A. 按行為主的存儲結(jié)構(gòu)按行為主的存儲結(jié)構(gòu) B.按行或列為主的存儲結(jié)構(gòu)按行或列為主的存儲結(jié)構(gòu) C. 按列為主的存儲結(jié)構(gòu)按列為主的存儲結(jié)構(gòu) D

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

43、的基本思想是為值相同的多個元素只分配一個存儲矩陣壓縮存儲的基本思想是為值相同的多個元素只分配一個存儲空間，為空間，為_不分配空間。不分配空間。請你給出答案請你給出答案思考題思考題想一想想一想337. 同一數(shù)組中的元素，它們（同一數(shù)組中的元素，它們（ ） A. 長度可以不同長度可以不同 B.類型不限類型不限 C. 類型相同類型相同 D.長度不限長度不限8. 數(shù)組是一個數(shù)組是一個( )線性表結(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ù)組通常只有_和和_二種運算二種運算,因此常采用因此常采用_來存儲數(shù)組。來存儲數(shù)組。請你給出答案請你給出答案思考題思考題想一想想一想廣義表廣義表1廣義表的定義廣義表的定義2廣義表的基本運算廣義表的基本運算3廣義表的存儲結(jié)構(gòu)廣義