第5章數(shù)組廣義表ppt課件

1、第第5章章 數(shù)組和廣義表數(shù)組和廣義表 元素的值并非原子類型，可以再分解，表中元素的值并非原子類型，可以再分解，表中 元素也是一個線性表（即線性表的推廣）。元素也是一個線性表（即線性表的推廣）。數(shù)組和廣義表的特點：數(shù)組和廣義表的特點：特殊的線性表特殊的線性表5.1 數(shù)組的定義數(shù)組的定義5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)5.3 矩陣的壓縮存儲矩陣的壓縮存儲5.4 廣義表的定義廣義表的定義5.5 廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)第第5章章 數(shù)組和廣義表數(shù)組和廣義表5.1 數(shù)組的定義 數(shù)組：數(shù)組： 由一組名字相同、下標不同的同類型的元素由一組名字相同、下標不同的同類型的元素 組成組成 數(shù)

2、組特點數(shù)組特點 數(shù)組結(jié)構(gòu)固定,下標一般具有下標一般具有固定的上界和下界固定的上界和下界 數(shù)據(jù)元素具有具有統(tǒng)一的類型統(tǒng)一的類型 數(shù)組運算數(shù)組運算 給定一組下標，取取相應的數(shù)據(jù)元素. 給定一組下標，修修改數(shù)據(jù)元素的值.數(shù)組的處理比其它復雜的結(jié)構(gòu)要簡單數(shù)組的處理比其它復雜的結(jié)構(gòu)要簡單與高級語言中數(shù)組的區(qū)別：與高級語言中數(shù)組的區(qū)別： 1、本章所討論的數(shù)組是一種、本章所討論的數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)，而高級語，而高級語言言 中數(shù)組是一種中數(shù)組是一種數(shù)據(jù)類型數(shù)據(jù)類型。2、高級語言高級語言中的數(shù)組是中的數(shù)組是順序結(jié)構(gòu)順序結(jié)構(gòu)；而本章的數(shù)組；而本章的數(shù)組 既可以是既可以是順序的，順序的，也可以是也可以是鏈式

3、結(jié)構(gòu)鏈式結(jié)構(gòu)，用戶可，用戶可根根 據(jù)需要選擇。據(jù)需要選擇。1m10mnaaaa二維數(shù)組的特點：二維數(shù)組的特點：一維數(shù)組的特點：一維數(shù)組的特點： 1個下標，個下標，ai是是ai+1的直接前驅(qū)的直接前驅(qū)2 2個下標，個下標，每個元素每個元素aij受到兩個關系受到兩個關系（行關系和列關系）的約束：（行關系和列關系）的約束：一個一個m mn n的二維數(shù)組可以的二維數(shù)組可以看成是由看成是由m m行的一維數(shù)組組行的一維數(shù)組組成或由成或由n n列的一維數(shù)組組成。列的一維數(shù)組組成。a0a1.am-1ai=(ai0, ai1, , ai,n-1) i=0,1,2,m-11n1,m1,1m1,0m1n1,1110

4、1n0,0100mnaaaaaaaaaa)aa(a)aa(a)aa(aa1n1,m1,1m1,0m1n1,11101n0,0100mn5.1 數(shù)組的定義 1n1,m1n1,1n0,1,1m11011,0m1000mnaaaaaaaaaa b0 b1 bn-11n10mnbbba二維數(shù)組是一個數(shù)據(jù)元素為線性表的線性表二維數(shù)組是一個數(shù)據(jù)元素為線性表的線性表j1,m1j0jjaaabj=0,1,n-1qaij(1i m-2，1 j n-2)有有兩個前驅(qū)兩個前驅(qū)結(jié)點結(jié)點ai,j-1和和ai-1,j 兩個后繼兩個后繼結(jié)點結(jié)點ai,j+1和和 ai+1,jqa00沒有前驅(qū)結(jié)點沒有前驅(qū)結(jié)點,稱之為開始結(jié)點稱

5、之為開始結(jié)點. qam-1,n-1沒有后繼結(jié)點沒有后繼結(jié)點,稱之為終端結(jié)點稱之為終端結(jié)點.q第第0行的元素行的元素a0j(j=1,n-1)q第第0列的元素列的元素ai0(i=1,m-1)只有一個前驅(qū)只有一個前驅(qū)只有一個后繼只有一個后繼我們可以把二維數(shù)組中的元素我們可以把二維數(shù)組中的元素aij看成是屬于兩個線性表看成是屬于兩個線性表:即即第第i行的線性表行的線性表ai和和第第j列的線性表列的線性表bjq第第m-1行的元素行的元素am-1,j(j=1,n-2)q第第n-1列的元素列的元素ai,n-1(i=1,m-2)同理，三維數(shù)組同理，三維數(shù)組amn l中每個元素屬于三個線性表，每個元素中每個元素

6、屬于三個線性表，每個元素最多有三個前驅(qū)和三個后繼。最多有三個前驅(qū)和三個后繼。ai1,i2,i3 前驅(qū)：前驅(qū)： ai1-1,i2,i3 ，ai1,i2-1,i3， ai1,i2,i3-1 后繼：后繼： ai1+1,i2,i3 ， ai1,i2+1,i3， ai1,i2,i3+1推而廣之推而廣之 ，一個一個n n維數(shù)組可以看成是維數(shù)組可以看成是由若干個由若干個n1維數(shù)組組成的線維數(shù)組組成的線性表性表，在，在n維數(shù)組維數(shù)組ab1 b2 bn中中, 每個元素每個元素ai1,i2,in(0 ij bi-1,j=1,2,n)屬于屬于n個線性表個線性表, 每個元素每個元素最多有最多有n個前驅(qū)和個前驅(qū)和n個后

7、繼。個后繼。ai1,i2,in 前驅(qū)：前驅(qū)：ai1-1,i2,in， ai1,i2-1,in，,，ai1,i2,in-1 后繼：后繼：ai1+1,i2,in， ai1,i2+1,in，ai1,i2,in+1數(shù)據(jù)對象數(shù)據(jù)對象: : d = aij | aij elemset ，0ib1-1, 0 jb2-1數(shù)據(jù)關系數(shù)據(jù)關系: : r = row, col row = | 0ib1-1, 0jb2-2 col = | 0ib1-2, 0jb2-1二維數(shù)組的二維數(shù)組的 定義定義:2b1ba initarray(&a, n, bound1, ., boundn) 操作結(jié)果：操作結(jié)果：若維數(shù)若維

8、數(shù) n 和各維長度合法，則構(gòu)造相應和各維長度合法，則構(gòu)造相應 的數(shù)組的數(shù)組a，并返回，并返回ok?；静僮鳎夯静僮鳎?destroyarray(&a) 操作結(jié)果：操作結(jié)果：銷毀數(shù)組銷毀數(shù)組a。value(a, &e, index1, ., indexn)/取數(shù)組元素取數(shù)組元素 初始條件：初始條件：a是是n維數(shù)組，維數(shù)組，e為元素變量，隨后是為元素變量，隨后是n 個下標值。個下標值。 操作結(jié)果：操作結(jié)果：若各下標不超界，則若各下標不超界，則e賦值為所指定的賦值為所指定的 a 的元素值，并返回的元素值，并返回ok?；静僮鳎夯静僮鳎篴ssign(&a, e, index

9、1, ., indexn)/修改數(shù)組元素修改數(shù)組元素 初始條件：初始條件：a是是n維數(shù)組，維數(shù)組，e為元素變量，隨后是為元素變量，隨后是 n 個下標值。個下標值。 操作結(jié)果：操作結(jié)果：若下標不超界，則將若下標不超界，則將e的值賦給所指的值賦給所指 定的定的a的元素，并返回的元素，并返回ok。5.2 數(shù)組的順序存儲表示和實現(xiàn)問題：問題：計算機的存儲結(jié)構(gòu)一般是一維的，而計算機的存儲結(jié)構(gòu)一般是一維的，而n n維數(shù)組維數(shù)組(n2)(n2)一般是多維的，怎樣存放？一般是多維的，怎樣存放？解決辦法：解決辦法：事先約定按某種次序?qū)?shù)組元素排成一序事先約定按某種次序?qū)?shù)組元素排成一序 列，然后將這個線性序列存

10、入存儲器中。列，然后將這個線性序列存入存儲器中。例如：例如：在二維數(shù)組中，我們既可以規(guī)定按在二維數(shù)組中，我們既可以規(guī)定按行行存儲，也存儲，也可以規(guī)定按可以規(guī)定按列列存儲存儲。若規(guī)定好了次序，則數(shù)組中任意一個元素的存放地址便有若規(guī)定好了次序，則數(shù)組中任意一個元素的存放地址便有規(guī)律可尋，可形成地址計算公式；規(guī)律可尋，可形成地址計算公式；約定的次序不同，則計算元素地址的公式也有所不同；約定的次序不同，則計算元素地址的公式也有所不同；c c和和pascalpascal中一般采用行優(yōu)先順序；中一般采用行優(yōu)先順序；fortranfortran采用列優(yōu)先。采用列優(yōu)先。 按行序為主序存放按行序為主序存放 am

11、-1,n-1 . am-1,1 am-1,0 . a1n-1 . a11 a10 a0,n-1 . a01 a00 a00 a01 . a0,n-1 a10 a11 . a1,n-1 am-1,0 am-1,1 am-1,n-1 .01n-1m*n-1n am-1,n-1 . a1,n-1 a0,n-1 . am-1,1 . a11 a01 am-1,0 . a10 a00 a00 a01 . a0n-1 a10 a11 . a1n-1 am-10 am-11 . am-1n-1 . 按列序為主序存放按列序為主序存放01m*n-1m-1m計算二維數(shù)組元素地址的通式計算二維數(shù)組元素地址的通式二維

12、數(shù)組二維數(shù)組列優(yōu)先列優(yōu)先存儲的通式為：存儲的通式為：loc(aij)=loc(a00)+(b1*j+i)*l則則行優(yōu)先行優(yōu)先存儲時的地址公式為：存儲時的地址公式為：loc(aij)=loc(a00)+(b2*i+j)*l設一般的二維數(shù)組是設一般的二維數(shù)組是a0.ba0.b1 1-1, 0.b-1, 0.b2 2-1-11b21,b11,0b11b2i,iji01b20,00mna.a.a.a.a.a.aa計算三維數(shù)組元素地址的通式計算三維數(shù)組元素地址的通式設一般的設一般的三維數(shù)組是維數(shù)組是a0.ba0.b1 1-1, 0.b-1, 0.b2 2-1-1，0.b0.b3 3-1-1按按“行優(yōu)先順

13、序行優(yōu)先順序”存儲，其任一元素存儲，其任一元素a aijkijk地地址計算函數(shù)為：址計算函數(shù)為：loc(aloc(aijkijk)=loc(a)=loc(a000000)+()+(i i* *b b2 2* *b b3 3+ +j j* *b b3 3+k)+k)* *l l若是若是n n維數(shù)組，其中任一元素的地址該如何計算？維數(shù)組，其中任一元素的地址該如何計算？ljbjalocljjbjbbbjbbbalocalocniniknkinnnnnnjjj1110.0012431320.00,.,21)()().()()(開始結(jié)點的存放地址（即基地址）開始結(jié)點的存放地址（即基地址）維數(shù)和每維的上、

14、下界；維數(shù)和每維的上、下界；每個數(shù)組元素所占用的單元數(shù)每個數(shù)組元素所占用的單元數(shù)其中其中cn=l, ci-1=bici， 1in（遞歸）（遞歸）loc(jloc(j1 1,j,j2 2, ,j jn n)=loc(0,0,)=loc(0,0,0)0)niii1jc5.3 矩陣的壓縮存儲矩陣的壓縮存儲 在科學與工程計算問題中，矩陣是一種常用在科學與工程計算問題中，矩陣是一種常用的數(shù)學對象，在高級語言編制程序時，將一個矩的數(shù)學對象，在高級語言編制程序時，將一個矩陣描述為一個二維數(shù)組。矩陣在這種存儲表示之陣描述為一個二維數(shù)組。矩陣在這種存儲表示之下，可以對其元素進行隨機存取，各種矩陣運算下，可以對其

15、元素進行隨機存取，各種矩陣運算也非常簡單。也非常簡單。 但是在矩陣但是在矩陣中非零元素呈某種規(guī)律分布中非零元素呈某種規(guī)律分布或者或者矩陣中出現(xiàn)大量的零元素矩陣中出現(xiàn)大量的零元素的情況下，占用了許多的情況下，占用了許多單元去存儲重復的非零元素或零元素，這對高階單元去存儲重復的非零元素或零元素，這對高階矩陣會造成極大的浪費，為了節(jié)省存儲空間，矩陣會造成極大的浪費，為了節(jié)省存儲空間， 我們可以對這類矩陣進行我們可以對這類矩陣進行壓縮存儲壓縮存儲：即為多個相即為多個相同的非零元素只分配一個存儲空間；對零元素不同的非零元素只分配一個存儲空間；對零元素不分配空間分配空間。并非所有的矩陣都可以壓縮并非所有的

16、矩陣都可以壓縮對稱矩陣對稱矩陣三角矩陣三角矩陣稀疏矩陣稀疏矩陣5.3.1 5.3.1 特殊矩陣特殊矩陣在一個在一個n n階方陣階方陣a a中，若元素滿足下述性質(zhì)：中，若元素滿足下述性質(zhì)： a aijij=a=ajiji 0i,jn-1 0i,jn-1 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a22 3 0 2 5 1 . 7 0 6 1 3 an-1 0 an-1 1 an-1 2 an-1 n-1 對稱矩陣對稱矩陣1 1、對稱矩陣、對稱矩陣sak按行序為主序按行序為主序：a00a10a11a20a21a22an-1,0an-1,n

17、-1012345n(n-1)n(n+1)/2-11）對稱矩陣的存儲方式）對稱矩陣的存儲方式在對稱矩陣中，第在對稱矩陣中，第i i行恰有行恰有i+1i+1個元素，元素總數(shù)為：個元素，元素總數(shù)為： 可以將這些元素存放在一個向量可以將這些元素存放在一個向量 中中1 1、對稱矩陣、對稱矩陣1n0i21)n(n1)(i 12/ ) 1(.0nnsa2）為了便于訪問對稱矩陣為了便于訪問對稱矩陣a a中的元素，我們必須在中的元素，我們必須在a aijij和和saksak之間找一個對應關系之間找一個對應關系。v若若ijij，則，則a aijij在下三角形中。在下三角形中。a aijij之前的之前的i i行（從

18、第行（從第0 0行行到第到第i-1i-1行）一共有行）一共有1+2+1+2+i=i+i=i* *(i+1)/2(i+1)/2個元素，在第個元素，在第i i行上，行上，a aijij之前恰有之前恰有j j個元素（即個元素（即a ai0i0,a,ai1i1,a,ai2i2, ,a,aij-1ij-1），），因此有：因此有： k=ik=i* *(i+1)/2+j(i+1)/2+j 0kn(n+1)/2-10kn(n+1)/2-1 v若若ijij，則，則a aijij是在上三角矩陣中。因為是在上三角矩陣中。因為a aijij=a=ajiji，所以只，所以只要交換上述對應關系式中的要交換上述對應關系式中

19、的i i和和j j即可得到：即可得到： k=jk=j* *(j+1)/2+i(j+1)/2+i 0kn(n+1)/2-10kn(n+1)/2-1 1 1、對稱矩陣、對稱矩陣 2、三角矩陣、三角矩陣以主對角線劃分，三角矩陣有以主對角線劃分，三角矩陣有上三角上三角和和下三角下三角兩種。兩種。上三角矩陣中主對角線以下的元素均為常數(shù)上三角矩陣中主對角線以下的元素均為常數(shù)(a) 。下三角矩陣正好相反，主對角線以上的元素均為常數(shù)下三角矩陣正好相反，主對角線以上的元素均為常數(shù)(b)。 a00 a01 . a0,n-1 c a11 . a1,n-1 c c c am-1,n-1 (a) 上三角矩陣上三角矩陣

20、a00 c . c a10 a11 c.c am-10 am-11 am-1,n-1 (b) 下三角矩陣下三角矩陣可以用向量可以用向量sa0.n(n+1)/2sa0.n(n+1)/2存儲，將常量存入存儲，將常量存入第一或最后一個單元第一或最后一個單元 5.3.2 5.3.2 稀疏矩陣稀疏矩陣1 1、什么是稀疏矩陣？、什么是稀疏矩陣？ 設矩陣設矩陣a a中有中有s s個非零元素，若個非零元素，若s s遠遠小于矩遠遠小于矩陣元素的總數(shù)（即陣元素的總數(shù)（即smsmn),n),則稱則稱a a為稀疏矩為稀疏矩陣。陣。 有有s s個非零元素。令個非零元素。令e=s/(me=s/(mn)n)，稱，稱e e為

21、矩陣為矩陣的的稀疏因子稀疏因子。通常認為。通常認為e0.05e0.05時為稀疏矩時為稀疏矩陣。陣。稀疏矩陣的壓縮存儲方法稀疏矩陣的壓縮存儲方法一、三元組順序表一、三元組順序表二、行邏輯聯(lián)接的順序表二、行邏輯聯(lián)接的順序表三、三、 十字鏈表十字鏈表存儲稀疏矩陣時，為了節(jié)省存儲單元，使用存儲稀疏矩陣時，為了節(jié)省存儲單元，使用壓縮壓縮 存儲方法。存儲方法。非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的分布一般是沒有規(guī)律的，因此在存儲 非零元素的同時，還必須同時記下它所在的非零元素的同時，還必須同時記下它所在的行和行和 列的位置（列的位置（i,j)i,j)。一個一個三元組三元組(i,j,a(i,j

22、,aijij) )唯一確定了矩陣唯一確定了矩陣a a的一個非零的一個非零 元。因此，稀疏矩陣可由元。因此，稀疏矩陣可由表示非零元的三元組表示非零元的三元組及及 其其行列數(shù)行列數(shù)唯一確定。唯一確定。一、三元組順序表一、三元組順序表例如，下列稀疏矩陣例如，下列稀疏矩陣 5.3.2 5.3.2 稀疏矩陣稀疏矩陣可由三元組表可由三元組表(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩陣和矩陣維數(shù)（維數(shù)（6,7）唯一確定）唯一確定 760007001500000180000024000140000300000

23、0000009120m=123456 1 2 3 4 5 6 7 一、三元組順序表一、三元組順序表 #define maxsize 12500 typedef struct int i, j; /該非零元的行下標和列下標該非零元的行下標和列下標 elemtype e; / 該非零元的值該非零元的值 triple; / 三元組類型三元組類型typedef struct triple datamaxsize+1; int mu, nu, tu; (mu行數(shù)行數(shù),nu列數(shù)列數(shù),tu非零元個數(shù)非零元個數(shù)) tsmatrix; / 稀疏矩陣類型稀疏矩陣類型三元組表表示法：三元組表表示法：12121393

24、1-3351443245218611564-7注意：注意：三元組表中的三元組表中的元素按行（或列）排元素按行（或列）排列。列。668ije稀疏矩陣壓縮存儲的稀疏矩陣壓縮存儲的缺點：將失去隨機存取功能缺點：將失去隨機存取功能0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0求轉(zhuǎn)置矩陣算法求轉(zhuǎn)置矩陣算法028003600070500140m005280000007143600t用常規(guī)的二維數(shù)組表示時的算法用常規(guī)的二維數(shù)組表示時的算法 其時間復雜度為其時間復雜度為: o(munu) for (c=1;

25、c=nu; +c) for (r=1; r=mu; +r) tcr = mrc;三元組表示的轉(zhuǎn)置(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)(1, 3, -3)(1, 6, 15)(2, 1, 12)(2, 5, 18)(3, 1, 9)(3, 4, 24)(4, 6, -7)(5, 3, 14)三三元元組組表表m.data三三元元組組表表t.data轉(zhuǎn)置后轉(zhuǎn)置后0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0

26、015 0 0 -7 0 0m=0 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0t=?不正確！不正確?。? 1）每個元素的行下標和列下標互換（即三元組中的）每個元素的行下標和列下標互換（即三元組中的i i和和j j 互換互換）；）；（2 2）t t的總行數(shù)的總行數(shù)mumu和總列數(shù)和總列數(shù)nunu與與m m值不同值不同（互換）；互換）；（3 3）重排重排三元組內(nèi)元素順序三元組內(nèi)元素順序，使轉(zhuǎn)置后的三元組也按行，使轉(zhuǎn)置后的三元組也按行 （或列）為主序有規(guī)律的排列。（或列）為主序有規(guī)律的排列。上述（上述

27、（1 1）和（）和（2 2）容易實現(xiàn)，難點在）容易實現(xiàn)，難點在（3 3）。提問：提問：若采用三元組壓縮技術存儲稀疏矩陣，只要把每個若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的元素的行下標和列下標互換行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運，就完成了對該矩陣的轉(zhuǎn)置運算，這種說法正確嗎？算，這種說法正確嗎？ 有兩種實現(xiàn)方法有兩種實現(xiàn)方法壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置( (壓縮壓縮) )快速轉(zhuǎn)置快速轉(zhuǎn)置方法方法1 1：壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置思路：思路：反復掃描反復掃描m.datam.data中的中的列序列序，從小到大依次進行轉(zhuǎn)置。，從小到大依次進行轉(zhuǎn)置。6 7 8 1 2 12 1 3 9 3 1 -3 3

28、6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8m7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j e0 1 2 3 4 5 6 7 8tqppppppppqqqqppppppppcol=1col=2qqqstatus transposesmatrix(tsmatrix m, tsmatrix &t)/用三元組表存放稀疏矩陣用三元組表存放稀疏矩陣m m，求，求m m的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣t tt.mu=m.nu; t.nu=m.mu; t.tu=m

29、.tu; /nu/nu是列數(shù)是列數(shù),mu,mu是行數(shù)是行數(shù),tu,tu是非零元素個數(shù)是非零元素個數(shù)if (t.tu) q=1; /q/q是轉(zhuǎn)置矩陣是轉(zhuǎn)置矩陣t t的結(jié)點編號的結(jié)點編號 for(col=1; col=m.nu; col+) for(p=1; p=m.tu; p+) /p/p是是m m三元表中結(jié)點編號三元表中結(jié)點編號 if (m.datap.j=col) t.dataq.i=m.datap.j; t.dataq.j=m.datap.i; t.dataq.e=m.datap.e; q+; return ok; /tranposesmatrix壓縮轉(zhuǎn)置算法描述壓縮轉(zhuǎn)置算法描述：1 1、

30、主要時間消耗在主要時間消耗在查找查找m.datap.j=colm.datap.j=col的元素的元素，由兩重循，由兩重循環(huán)完成環(huán)完成: : for(col=1; col=m.nu; col+) 循環(huán)次數(shù)循環(huán)次數(shù)nu for(p=1; p=m.tu; p+) 循環(huán)次數(shù)循環(huán)次數(shù)tu所以該算法的時間復雜度為所以該算法的時間復雜度為o(o(nu*tu) ) - -即即m m的列數(shù)與的列數(shù)與m m中非零元素的個數(shù)之中非零元素的個數(shù)之積積最壞情況最壞情況：m m中全是非零元素，此時中全是非零元素，此時tu=mutu=mu* *nunu， 時間復雜度為時間復雜度為 o(o(nu2 2*mu ) )注：注：若

31、若m m中基本上是非零元素時，即使用非壓縮傳統(tǒng)轉(zhuǎn)置算法中基本上是非零元素時，即使用非壓縮傳統(tǒng)轉(zhuǎn)置算法的時間復雜度也不過是的時間復雜度也不過是o(o(nu*mu) )結(jié)論：結(jié)論：壓縮轉(zhuǎn)置算法不能濫用。壓縮轉(zhuǎn)置算法不能濫用。前提前提：僅適用于非零元素個數(shù)很少（即僅適用于非零元素個數(shù)很少（即tutumumu* *nunu）的情況。）的情況。壓縮轉(zhuǎn)置算法的效率分析壓縮轉(zhuǎn)置算法的效率分析方法方法2 2 快速轉(zhuǎn)置快速轉(zhuǎn)置三三元元組組表表m.data三三元元組組表表t.data(1, 3, -3)(2 ,1, 12)(2, 5, 18)(3, 1, 9)(4, 6, -7)(5, 3, 14)(1, 6,

32、15)(3, 4, 24)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)思路：思路：依次依次把把m.datam.data中的元素直接送入中的元素直接送入t.datat.data的恰當位的恰當位置上（置上（即即m m三元組的三元組的p p指針不回溯指針不回溯）。）。關鍵：關鍵：怎樣尋找怎樣尋找t.datat.data的的“恰當恰當”位置？位置？ p1234 q 3 5如果能預知如果能預知m矩陣中每一列矩陣中每一列( (即即t的每一行的每一行) )的非零元的非零元素個數(shù)，又能預知每一列

33、第一個非零元素在素個數(shù)，又能預知每一列第一個非零元素在t.datat.data中中的位置的位置, ,則掃描則掃描m.data時便可以將每個元素準確定位。時便可以將每個元素準確定位。設計思路：設計思路：注意：注意：根據(jù)根據(jù)m.datam.data的特征，每列第一個非零元素必的特征，每列第一個非零元素必 定先被掃描到。定先被掃描到。令令：m中的列變量用中的列變量用col表示；表示； num col ：存放存放m中第中第col 列中非列中非0 0元素個數(shù)，元素個數(shù)， cpot col ：存放存放m中第中第col列的第一個非列的第一個非0 0元素的位置，元素的位置， （即（即t.data中待計算的中待

34、計算的“恰當恰當”位置所需參考點位置所需參考點）col123456numcol222110cpotcol1規(guī)律規(guī)律: cpot(1)1 cpotcol cpotcol-1 + numcol-10 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0m= 3 col 1 2 3 4 5 6 5 9 8 7 6 6 8 1 2 12 1 3 9 3 1 -3 3 5 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8m6 6 8 1 3 -3 1 6

35、15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 5 3 14 pppppppp4629753col123456numcol222110cpotcol135789i j v0 1 2 3 4 5 6 7 8tstatus fasttransposesmatrix（tsmatirx m, tsmatirx &t） t.mu = m.nu ;t.nu = m.mu ; t.tu = m.tu ; if (t.tu) for(col = 1; col =m.nu; col+) numcol =0; for( i = 1; i =m.tu; i +) col =m.da

36、ta i .j ; +num col ; cpot 1 =1; for(col = 2; col =m.nu; col+) cpotcol=cpotcol-1+numcol-1 ; for( p =1; p =m.tu ; p + ) col =m.data p . j ; q =cpot col ; t.dataq.i = m.datap. j; t.dataq.j = m.datap. i; t.dataq. e = m.datap.e; /for /if return ok; /fasttranposesmatrix;快速轉(zhuǎn)置算法描述快速轉(zhuǎn)置算法描述：/m/m用順序存儲表示，求用順序存儲

37、表示，求m m的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣t t/先統(tǒng)計每列非零元素個數(shù)先統(tǒng)計每列非零元素個數(shù)/再生成每列首元位置輔助向量表再生成每列首元位置輔助向量表/p/p指向指向a.dataa.data，循環(huán)次數(shù)為非，循環(huán)次數(shù)為非0 0元素總個數(shù)元素總個數(shù)tutu/查輔助向量表得查輔助向量表得q q，即，即t t中位置中位置/修改向量表中列坐標值，供同一列下一修改向量表中列坐標值，供同一列下一非零元素定位之用！非零元素定位之用！1.1. 與常規(guī)算法相比，增加了與常規(guī)算法相比，增加了2 2個長度為列長的輔助數(shù)個長度為列長的輔助數(shù)組組( (num 和和cpot ）?？焖俎D(zhuǎn)置算法的效率分析快速轉(zhuǎn)置算法的效率分析：2.

38、2. 從時間上，此算法用了從時間上，此算法用了4 4個并列的單循環(huán)，而且其個并列的單循環(huán)，而且其中前中前3 3個單循環(huán)都是用來產(chǎn)生輔助數(shù)組的。個單循環(huán)都是用來產(chǎn)生輔助數(shù)組的。 for(col = 1; col =m.nu; col+) 循環(huán)次數(shù)循環(huán)次數(shù)nu;nu; for( i = 1; i =m.tu; i +) 循環(huán)次數(shù)循環(huán)次數(shù)tu;tu; for(col = 2; col =m.nu; col+) 循環(huán)次數(shù)循環(huán)次數(shù)nu;nu; for( p=1; p =m.tu ; p + ) 循環(huán)次數(shù)循環(huán)次數(shù)tu;tu; 該算法的時間復雜度該算法的時間復雜度(nu(nu* *2)+(tu2)+(tu*

39、 *2)=o(2)=o(nu+tunu+tu） 傳統(tǒng)轉(zhuǎn)置：傳統(tǒng)轉(zhuǎn)置：o(o(mumu* *nunu) ) 壓縮轉(zhuǎn)置：壓縮轉(zhuǎn)置：o(o(mumu* *tutu) ) 壓縮快速轉(zhuǎn)置：壓縮快速轉(zhuǎn)置：o(o(nu+tunu+tu) )犧牲空間效率換時犧牲空間效率換時 間效率。間效率。小結(jié)：小結(jié)：討論：討論：最壞情況是最壞情況是tu=nutu=nu* *mumu( (即矩陣中全部是非零元即矩陣中全部是非零元素），而此時的時間復雜度也只是素），而此時的時間復雜度也只是o(o(mumu* *nunu) )，并未超，并未超過傳統(tǒng)轉(zhuǎn)置算法的時間復雜度。過傳統(tǒng)轉(zhuǎn)置算法的時間復雜度。 三元組順序表又稱有序的雙下標法

40、，它的特點三元組順序表又稱有序的雙下標法，它的特點是，非零元在表中按行序有序存儲，因此是，非零元在表中按行序有序存儲，因此便于進行便于進行依行順序處理的矩陣運算。依行順序處理的矩陣運算。然而，然而，若需隨機存取某若需隨機存取某一行中的非零元，則需從頭開始進行查找一行中的非零元，則需從頭開始進行查找。二、行邏輯聯(lián)接的順序表二、行邏輯聯(lián)接的順序表 #define maxsize 500 typedef struct triple datamaxsize + 1; /三元組表三元組表 int rposmaxmn + 1; /每一行非零元的位置表每一行非零元的位置表 int mu, nu, tu; r

41、lsmatrix; / 行邏輯鏈接順序表類型行邏輯鏈接順序表類型二、行邏輯聯(lián)接的順序表二、行邏輯聯(lián)接的順序表0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0m=121213931-3351443245218611564-7668ijerow123456numrow202112rposrow133567例如：給定一組下標，求矩陣的元素值例如：給定一組下標，求矩陣的元素值elemtype value(rlsmatrix m, int r, int c) p=m.rposr;/第第r行第一個非零值的位

42、置行第一個非零值的位置 while (m.datap.i=r &m.datap.j i=i; p-j=j; p-e=e; if(m.rheadi=null|m.rheadi-jj) p-right=m.rheadi; m.rheadi =p; /插入到第一個插入到第一個else for(q=m.rheadi; (q-right)&(q-right-jright); p-right=q-right;q-right=p; if(m.cheadj=null|m.cheadj-ii) p-down=m.cheadj; m.cheadj =p; else for(q=m.cheadj;(

43、q-down)& q-down-idown); p-down=q-down;q-down=p;/end forreturn ok;/createsmtrix_ol418234輸入：輸入：m=4,n=31,1,32,2,52,3,44,1,82,1,7113217225rhead1rhead2rhead3rhead4chead1 chead2chead33 0 0 50 -1 0 02 0 0 0矩陣相加算法矩陣相加算法a=0 2 0 -10 1 0 20 0 0 4b=a=a+ba=3 2 0 40 0 0 22 0 0 4對于每一行做如下處理對于每一行做如下處理a.cheada.rh

44、ead1131 452 2 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadabpa=a.rhead1;pb=b.rhead1;pre=null;for(j=1;jjj) pre=pa;pa=pa-right;a.cheada.rhead1131 452 2 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadabprepbh1h3h4h2if(pa-jpb-j) 復制復制pb所指的結(jié)點賦值為所指的結(jié)點賦值為p； if(pre=null) a.rheadp-i=p; else pre-right=p; p-right=pa;

45、pre=p; pb=pb-right;paa.cheada.rhead1131 4522 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadmnpapb1 2 2prehl1hl3hl4hl2if(a.cheadp-j=null & hlp-j=a.cheadp-j)a.cheadp-j=p;p-down=hlp-j;else p-down=hlp-j-down; hlp-j-down=p; hlp-j=p;pa.cheada.rhead1131 4522 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.che

46、adabpapb1 2 2prehl1hl3hl4hl2a.cheada.rhead1131 4522 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadabpapb1 2 2prehl1hl3hl4hl2if(pa-j=pb-j) pa-e+=pa-e; if(e!=0)pre=pa; pa=pa- right;pb=pb-right; else 刪除刪除a中該結(jié)點中該結(jié)點a.cheada.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadabpa=null1 2 2hl1hl3

47、hl4hl2prepb=nulla.cheada.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadab1 2 2hl1hl3hl4hl2papba.cheada.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadab1 2 2hl1hl3hl4hl2papba.cheada.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadab1 2 2hl1hl3hl4hl2ppbpa=nul

48、la.cheada.rhead1131 4422 -13 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadab1 2 2hl1hl3hl4hl2ppbpa=nulla.cheada.rhead1131 443 122 2 11 4 -11 2 22 4 23 4 4b.rheadb.cheadab1 2 2hl1hl3hl4hl2pbpa=null5.4 5.4 廣義表的定義廣義表的定義廣義表是線性表的推廣，也稱為列表（廣義表是線性表的推廣，也稱為列表（lists）廣義表中元素既）廣義表中元素既可以是原子類型，也可以是列表?？梢允窃宇愋?，也可以是列表。記為

49、：記為： ls = ( a1 , a2 , ， an ) 廣義表名廣義表名 a1是表頭是表頭(head） （ a2 ,an ）是表尾）是表尾 (tail)1、定義：、定義：n n是表長是表長 第一個第一個元素是表頭元素是表頭，而其余元素組成的，而其余元素組成的表表稱為表稱為表尾尾； 所以任何一個非空表，表頭可能是原子，也可能是所以任何一個非空表，表頭可能是原子，也可能是 列表；但列表；但表尾一定是列表。表尾一定是列表。 約定：用小寫字母表示原子類型，用約定：用小寫字母表示原子類型，用大寫字母大寫字母表示表示 列表。列表。在廣義表中約定：在廣義表中約定：2、特點：、特點：1）次序性：）次序性：一

50、個直接前驅(qū)和一個直接后繼一個直接前驅(qū)和一個直接后繼2）長度：）長度：表中表中最外層最外層包含元素個數(shù)包含元素個數(shù)3）深度：）深度：當廣義表全部用原子代替后，表中括號的最大重數(shù)當廣義表全部用原子代替后，表中括號的最大重數(shù) 空表（空表（ ）的深度為）的深度為1，長度為，長度為0 ，原子的深度為，原子的深度為0.4）可遞歸：）可遞歸：自己可以作為自己的子表。自己可以作為自己的子表。 例例e=(a, e) 遞歸表的深度是無窮值，長度是遞歸表的深度是無窮值，長度是2。5）可共享）可共享: 可以為其它廣義表所共享的表。可以為其它廣義表所共享的表。6 6）任何一個非空廣義表）任何一個非空廣義表 ls = (

51、 ls = ( 1, 1, 2, 2, , , n)n) 均可分解為均可分解為 表頭表頭 gethead(ls) = 1 和和 表尾表尾 gettail(ls) = ( 2, , n) 兩部分兩部分e=(a,e)=(a,(a,e)= (a,(a,(a,.)，e為遞歸表為遞歸表1）a =( )2）b = ( e ) 3）c =( a ,( b , c , d ) ) 4）d=( a , b ,c )5）e=(a, e)例例1：求下列廣義表的長度。求下列廣義表的長度。n=0，因為因為a是空表是空表n=1，表中元素，表中元素e是原子是原子n=2，a 為原子，為原子，(b,c,d)為子表為子表n=3，

52、3個元素都是子表個元素都是子表n=2，a 為原子，為原子，e為子表為子表d=(a,b,c)=( ),(e),(a,(b,c,d)，共享表共享表6)f=( ) n=1gethead(b)= gettail(b)=gethead(c)= gettail(c)=gethead(d)= gettail(d)=gethead(e)= gettail(e)=gethead( )= gettail( )=b = ( e ) c =( a ,( b , c , d ) ) d=( a , b ,c ) e=(a, e)e( )a(b,c,d)a(b,c)a(e)例例2：求下列廣義表的表頭和表尾。求下列廣義表的

53、表頭和表尾。gettail( gethead (a,b),(c,d)（b）( )( )dabceabcd a=( a , (b, a) )例例3 3：試用圖形表示下列廣義表試用圖形表示下列廣義表. .（設設 代表原子，代表原子， 代表子表）代表子表） e d=(a,b,c)=( ( ),(e),( a, (b,c,d) ) )aab的長度為的長度為3，深度為，深度為3的長度為的長度為2，深度為，深度為深度括號的重數(shù)深度括號的重數(shù) 結(jié)點的最大層數(shù)結(jié)點的最大層數(shù)廣義表的抽象數(shù)據(jù)類型定義廣義表的抽象數(shù)據(jù)類型定義adt glist 數(shù)據(jù)對象：數(shù)據(jù)對象：d= ei|i=1，2，n； n0； ei atomset或或 ei glist, atomset為某個數(shù)據(jù)對象為某個數(shù)據(jù)對象 數(shù)據(jù)關系數(shù)據(jù)關系：r1=| ei-l，ei d， 2in 基本操作：基本操作： initglist(&l) 操作結(jié)果操作結(jié)果：創(chuàng)建空的廣義表：創(chuàng)建空的廣義表l createglist(&l，s) 初始條件初始條件：s是廣義表的書寫形式串是廣義表的書寫形式串 操作結(jié)果操作結(jié)果：由：由s創(chuàng)建廣義表創(chuàng)建廣義表l destroyglist(&l) 初始條件初始條