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

1、第五章第五章 數(shù)組和廣義表數(shù)組和廣義表本章主要介紹多維數(shù)組的概念及在計(jì)算機(jī)中的存本章主要介紹多維數(shù)組的概念及在計(jì)算機(jī)中的存放，放，特殊矩陣特殊矩陣的壓縮存儲及相應(yīng)運(yùn)算的壓縮存儲及相應(yīng)運(yùn)算，廣義表廣義表的的概念和概念和存儲結(jié)構(gòu)及其相關(guān)運(yùn)算的實(shí)現(xiàn)。通過本章存儲結(jié)構(gòu)及其相關(guān)運(yùn)算的實(shí)現(xiàn)。通過本章學(xué)習(xí)，要求掌握如下內(nèi)容：學(xué)習(xí)，要求掌握如下內(nèi)容：1 1多維數(shù)組的定義及在計(jì)算機(jī)中的存儲表示；多維數(shù)組的定義及在計(jì)算機(jī)中的存儲表示；2 2對稱矩陣、三角矩陣、對角矩陣等特殊矩陣對稱矩陣、三角矩陣、對角矩陣等特殊矩陣在計(jì)算機(jī)中的壓縮存儲表示及地址計(jì)算公式；在計(jì)算機(jī)中的壓縮存儲表示及地址計(jì)算公式；3 3稀疏矩陣的三元

2、組表示及轉(zhuǎn)置算法實(shí)現(xiàn)；稀疏矩陣的三元組表示及轉(zhuǎn)置算法實(shí)現(xiàn)；4 4廣義表存儲結(jié)構(gòu)表示及基本運(yùn)算。廣義表存儲結(jié)構(gòu)表示及基本運(yùn)算。5.1 多維數(shù)組5.1.1多維數(shù)組的定義5.1.2多維數(shù)組的存儲5.2 矩陣的壓縮存儲 5.2.1 特殊矩陣 5.2.2 稀疏矩陣5.3 廣義表5.15.1 多維數(shù)組多維數(shù)組數(shù)組：數(shù)組： 由一組名字相同、下標(biāo)不同的同類型的元素由一組名字相同、下標(biāo)不同的同類型的元素 組成組成 數(shù)組特點(diǎn)數(shù)組特點(diǎn) 數(shù)組結(jié)構(gòu)固定數(shù)組結(jié)構(gòu)固定,下標(biāo)一般具有下標(biāo)一般具有固定的上界和下界固定的上界和下界 數(shù)據(jù)元素?cái)?shù)據(jù)元素具有具有統(tǒng)一的類型統(tǒng)一的類型 數(shù)組運(yùn)算數(shù)組運(yùn)算 給定一組下標(biāo)，給定一組下標(biāo)，取取相

3、應(yīng)的數(shù)據(jù)元素相應(yīng)的數(shù)據(jù)元素. 給定一組下標(biāo)，給定一組下標(biāo)，修修改數(shù)據(jù)元素的值改數(shù)據(jù)元素的值.數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單5.1.15.1.1多維數(shù)組的定義多維數(shù)組的定義與高級語言中數(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ù)組 既可以是既可以是順序的，順序的，也可以是也可以是鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)，用戶可，用戶可 根據(jù)需要選擇。根據(jù)需要選擇。5.1.15.1

4、.1多維數(shù)組的定義多維數(shù)組的定義一維數(shù)組一維數(shù)組一維數(shù)組可以看成是一個(gè)線性表或一個(gè)向量，它在計(jì)算機(jī)內(nèi)一維數(shù)組可以看成是一個(gè)線性表或一個(gè)向量，它在計(jì)算機(jī)內(nèi)是存放在一塊是存放在一塊連續(xù)的存儲單元連續(xù)的存儲單元中，適合于中，適合于隨機(jī)查找隨機(jī)查找。有一個(gè)直接前驅(qū)和一個(gè)直接后繼有一個(gè)直接前驅(qū)和一個(gè)直接后繼二維數(shù)組二維數(shù)組二維數(shù)組可以看成是向量的推廣。二維數(shù)組可以看成是向量的推廣。有兩個(gè)直接前驅(qū)和兩個(gè)直接后繼有兩個(gè)直接前驅(qū)和兩個(gè)直接后繼 例如，設(shè)例如，設(shè)A A是一個(gè)有是一個(gè)有m m行行n n列的二維數(shù)組，則列的二維數(shù)組，則A A可以表示為可以表示為：a00 a01 a0n-1 a10 a11 a1n-1

5、 . A= am-1 0 am-1 1 am-1 n-1 三維數(shù)組三維數(shù)組最多可有三個(gè)直接前驅(qū)和三個(gè)直接后繼最多可有三個(gè)直接前驅(qū)和三個(gè)直接后繼多維數(shù)組多維數(shù)組把三維以上的數(shù)組稱為多維數(shù)組，把三維以上的數(shù)組稱為多維數(shù)組，可有多個(gè)直接前驅(qū)和多個(gè)直接后繼可有多個(gè)直接前驅(qū)和多個(gè)直接后繼是一種非線性結(jié)構(gòu)是一種非線性結(jié)構(gòu)。總結(jié)：總結(jié)： 一維數(shù)組可以看作一個(gè)線性表，一維數(shù)組可以看作一個(gè)線性表， 二維數(shù)組可以看作二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組數(shù)據(jù)元素是一維數(shù)組”的一維的一維數(shù)組，數(shù)組， 三維數(shù)組可以看作三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)的一維數(shù)組，依組，依 此類推。此類推。

6、在在C C語言中的描述語言中的描述typedeftypedef intint datatypedatatype; ;datatypedatatype array1N; array1N; datatypedatatype array2array2MN;MN;datatypedatatype array3XYZ;array3XYZ; 數(shù)組一旦被定義，它的維數(shù)和維界就不再數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，數(shù)組只有存取元素和修改元素值改變。因此，數(shù)組只有存取元素和修改元素值的操作。的操作。考慮問題的基本出發(fā)點(diǎn)：考慮問題的基本出發(fā)點(diǎn)： 計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的。因此用一維內(nèi)存來存多計(jì)算機(jī)的

7、內(nèi)存結(jié)構(gòu)是一維的。因此用一維內(nèi)存來存多維數(shù)組，就必須維數(shù)組，就必須按某種次序?qū)?shù)組元素排成線性序列按某種次序?qū)?shù)組元素排成線性序列，然后將這個(gè)線性序列順序存放在存儲器中然后將這個(gè)線性序列順序存放在存儲器中。數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，不再發(fā)生變化。因此，一般都是采用順序存儲的方法一般都是采用順序存儲的方法來表示數(shù)組來表示數(shù)組。5.2 5.2 多維數(shù)組的存儲多維數(shù)組的存儲兩種順序存儲方式兩種順序存儲方式行優(yōu)先順序行優(yōu)先順序?qū)?shù)組元素按行排列將數(shù)組元素按行排列在在PASCALPASCAL、C C語言中，數(shù)組就是按行

8、優(yōu)先順序存儲的。語言中，數(shù)組就是按行優(yōu)先順序存儲的。列優(yōu)先順序列優(yōu)先順序?qū)?shù)組元素按列向量排列將數(shù)組元素按列向量排列在在FORTRANFORTRAN語言中，數(shù)組就是按列優(yōu)先順序存儲的。語言中，數(shù)組就是按列優(yōu)先順序存儲的。推廣到多維數(shù)組的情況：推廣到多維數(shù)組的情況：行優(yōu)先順序：先排最右下標(biāo)，從右到左，最后排最左下標(biāo)。行優(yōu)先順序：先排最右下標(biāo)，從右到左，最后排最左下標(biāo)。 因此，在算法中，最左邊下標(biāo)可以看成是外循環(huán)，最右邊下標(biāo)可因此，在算法中，最左邊下標(biāo)可以看成是外循環(huán)，最右邊下標(biāo)可以看以看 成是最內(nèi)循環(huán)。成是最內(nèi)循環(huán)。列優(yōu)先順序：先排最左下標(biāo)，從左向右，最后排最右下標(biāo)。列優(yōu)先順序：先排最左下標(biāo)，從

9、左向右，最后排最右下標(biāo)。 因此，在算法中，最右邊下標(biāo)可以看成是外循環(huán)，最左邊下標(biāo)可以看因此，在算法中，最右邊下標(biāo)可以看成是外循環(huán)，最左邊下標(biāo)可以看成是最內(nèi)循環(huán)。成是最內(nèi)循環(huán)。 按行序?yàn)橹餍虼娣虐葱行驗(yàn)橹餍虼娣?am-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

10、a01 . a0n-1 a10 a11 . a1n-1 am-10 am-11 . am-1n-1 . 按列序?yàn)橹餍虼娣虐戳行驗(yàn)橹餍虼娣?1m*n-1m-1m計(jì)算機(jī)如何實(shí)現(xiàn)數(shù)組元素的隨機(jī)存??？計(jì)算機(jī)如何實(shí)現(xiàn)數(shù)組元素的隨機(jī)存??？ 按上述兩種方式順序存儲的序組，只要知道：按上述兩種方式順序存儲的序組，只要知道：開始結(jié)點(diǎn)的存放地址（即基地址），開始結(jié)點(diǎn)的存放地址（即基地址），維數(shù)維數(shù)每維的上、下界每維的上、下界每個(gè)數(shù)組元素所占用的單元數(shù)，每個(gè)數(shù)組元素所占用的單元數(shù)， 就可以將數(shù)組元素的就可以將數(shù)組元素的存放地址表示為存放地址表示為其下標(biāo)的線其下標(biāo)的線性函數(shù)性函數(shù)。因此，數(shù)組中的任一元素可以在相同的時(shí)

11、間。因此，數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取，即順序存儲的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。內(nèi)存取，即順序存儲的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。如何計(jì)算數(shù)組元素的地址？如何計(jì)算數(shù)組元素的地址？計(jì)算二維數(shù)組元素地址的通式計(jì)算二維數(shù)組元素地址的通式二維數(shù)組二維數(shù)組列優(yōu)先列優(yōu)先存儲的通式為：存儲的通式為：LOC(aij)=LOC(a00)+(j*b1+i)*L則則行優(yōu)先行優(yōu)先存儲時(shí)的地址公式為：存儲時(shí)的地址公式為：LOC(aij)=LOC(a00)+(i*b2+j)*L設(shè)一般的二維數(shù)組是設(shè)一般的二維數(shù)組是A0.bA0.b1 1-1, 0.b-1, 0.b2 2-1-11b21,b11,0b11b2i,iji01b

12、20,00mna.a.a.a.a.a.aAbi稱為第稱為第i維維的長度的長度計(jì)算三維數(shù)組元素地址的通式計(jì)算三維數(shù)組元素地址的通式設(shè)一般的三維數(shù)組是設(shè)一般的三維數(shù)組是A0.b1-1, 0.b2-1，0.b3-1按按“行優(yōu)先順序行優(yōu)先順序”存儲，其任一元素存儲，其任一元素A Aijkijk地址計(jì)地址計(jì)算函數(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按按“列優(yōu)先順序列優(yōu)先順序”存儲，其任一元素存儲，其任一元素A Aijkijk地址計(jì)地址計(jì)算函數(shù)為：算

13、函數(shù)為：LOC(aLOC(aijkijk)=LOC(a)=LOC(a000000)+()+(k k* *b b1 1* *b b2 2+ +j j* *b b1 1+i)+i)* *L L若是若是N N維數(shù)組，其中任一元素的地址該如何計(jì)算？維數(shù)組，其中任一元素的地址該如何計(jì)算？LjbjaLOCLjjbjbbbjbbbaLOCaLOCniniknkinnnnnnjjj1110.0012431320.00,.,21)()().()()(開始結(jié)點(diǎn)的存放地址（即基地址）開始結(jié)點(diǎn)的存放地址（即基地址）維數(shù)和每維的上、下界；維數(shù)和每維的上、下界；每個(gè)數(shù)組元素所占用的單元數(shù)每個(gè)數(shù)組元素所占用的單元數(shù)其中其中

14、Cn=L, Ci-1=biCi， 1in（遞歸）遞歸）Loc(jLoc(j1 1,j,j2 2, ,j jn n)=LOC(0,0,)=LOC(0,0,0)0)niii1jC最基本的原理最基本的原理Ai1in的起始地址=第一個(gè)元素的起始地址該元素前面的元素個(gè)數(shù)單位長度+對于二維數(shù)組對于二維數(shù)組Ac1:d1,c2:d2,設(shè)每個(gè)元素占用設(shè)每個(gè)元素占用k個(gè)存儲單元，個(gè)存儲單元，LOC(c1,c2)是第一個(gè)元素是第一個(gè)元素ac1c2的存儲位置，則的存儲位置，則按行存放時(shí)按行存放時(shí)，aij的存儲位置為：的存儲位置為：LOC(i,j)=LOC(c1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*

15、k按列存放時(shí)按列存放時(shí),aij的存儲位置為：的存儲位置為：LOC(i,j)=LOC(c1,c2)+(j-c2)*(d1-c1+1)+(i-c1)*k2006-12006-1對于二維數(shù)組a04,15，設(shè)每個(gè)元素占1個(gè)存儲單元，且以行為主序存儲，則元素a2,1相對于數(shù)組空間起始地址的偏移量是()。 A5 B10 C15D25 20032003設(shè)數(shù)組a3.16，5.20的元素以列為主序存放，每個(gè)元素占用兩個(gè)存儲單元，則數(shù)組元素ai,j(3i16，5j20)的地址計(jì)算公式為_。 Aa-118+2i+28jBa-116+2i+28j Ca-144+2i+28j Da-146+2i+28j5.25.2 矩

16、陣的壓縮存儲矩陣的壓縮存儲在編程時(shí)，簡單而又自然的方法，是在編程時(shí)，簡單而又自然的方法，是將矩陣描述為將矩陣描述為一個(gè)二維數(shù)組一個(gè)二維數(shù)組。矩陣在這種存儲表示之下，可以對。矩陣在這種存儲表示之下，可以對其元素進(jìn)行隨機(jī)存取。其元素進(jìn)行隨機(jī)存取。 但是在一些特殊矩陣中，但是在一些特殊矩陣中，非零元素呈某種規(guī)律分布非零元素呈某種規(guī)律分布或者或者矩陣中有大量的零元素矩陣中有大量的零元素，如果仍用二維數(shù)組存，如果仍用二維數(shù)組存，會(huì)造成極大的浪費(fèi)，尤其是處理高階矩陣的時(shí)候。會(huì)造成極大的浪費(fèi)，尤其是處理高階矩陣的時(shí)候。 為了節(jié)省存儲空間，為了節(jié)省存儲空間， 我們可以對這類矩陣進(jìn)行壓縮我們可以對這類矩陣進(jìn)行壓

17、縮存儲。存儲。5.2.15.2.1 幾種常見的特殊矩陣幾種常見的特殊矩陣1 12 23 34 45 52 23 34 45 56 63 34 45 56 67 74 45 56 67 78 85 56 67 78 89 9對稱矩陣在一個(gè)在一個(gè)n n階方陣階方陣A A中，若元素滿足下中，若元素滿足下述性質(zhì)：述性質(zhì)：a aij ij= =a aji ji 0i,jn-1 0i,jn-1，則稱，則稱A A為對稱矩陣。為對稱矩陣。特征特征：元素關(guān)于主對角線對稱：元素關(guān)于主對角線對稱壓縮存儲的辦法：壓縮存儲的辦法： 只存矩陣中上三角或下三角中只存矩陣中上三角或下三角中的元素。的元素。所需空間：所需空間：

18、2) 1() 1(10nniNni三角矩陣三角矩陣特征：特征：上三角矩陣上三角矩陣中，主對角中，主對角線的線的下三角中的元素均下三角中的元素均為常數(shù)為常數(shù)。在大多數(shù)情況。在大多數(shù)情況下，常數(shù)為下，常數(shù)為零零。下三角矩陣下三角矩陣正好相反。正好相反。壓縮方法：壓縮方法：只存上只存上( (下下) )三角陣中上三角陣中上( (下下) )三角中的元素三角中的元素常數(shù)常數(shù)c c可共享一個(gè)存儲可共享一個(gè)存儲空間空間所需空間：所需空間：1 12 23 34 45 50 03 34 45 56 60 00 05 56 67 70 00 00 07 78 80 00 00 00 09 91 12 23 34 4

19、5 54 43 34 45 56 64 44 45 56 67 74 44 44 47 78 84 44 44 44 49 91 10 00 00 00 02 23 30 00 00 03 36 65 50 00 04 47 79 97 70 05 58 81 12 29 91 14 44 44 44 42 23 34 44 44 43 36 65 54 44 44 47 79 97 74 45 58 81 12 29 912) 1(nnN上三角上三角下三角下三角對角矩陣對角矩陣特征：特征：所有的非零元素集中在以所有的非零元素集中在以主對角線主對角線為中心的帶狀區(qū)域中，為中心的帶狀區(qū)域中， 即

20、除了主對角線和主對角線相鄰兩即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，側(cè)的若干條對角線上的元素之外，其余元素皆為零。其余元素皆為零。壓縮存儲的辦法：壓縮存儲的辦法： 只存對角線以及相鄰兩側(cè)的若干只存對角線以及相鄰兩側(cè)的若干條對角線上的元素。條對角線上的元素。存存三對角矩陣三對角矩陣所需的空間：所需的空間：1 11 10 00 00 02 23 37 70 00 00 04 45 53 30 00 00 06 67 75 50 00 00 08 89 9三對角矩陣三對角矩陣23 nN特征：只有特征：只有少量少量非零元素，且非非零元素，且非零元素的零元素的分布沒有規(guī)律分布沒有規(guī)律

21、。壓縮存儲的辦法：壓縮存儲的辦法： 只存非零元素。只存非零元素。所需空間：與非零元素的個(gè)數(shù)和所需空間：與非零元素的個(gè)數(shù)和存儲方式有關(guān)。存儲方式有關(guān)。稀疏矩陣稀疏矩陣1 12 20 00 05 50 03 30 00 00 00 04 40 00 00 00 00 06 60 00 00 00 00 08 80 05.2.25.2.2 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲矩陣類型矩陣類型對稱矩陣對稱矩陣三角矩陣三角矩陣三對角矩陣三對角矩陣壓縮的基本思想：壓縮的基本思想：只存有用的元素只存有用的元素由用二維數(shù)組改為用一維數(shù)組來存放由用二維數(shù)組改為用一維數(shù)組來存放說明：說明：按按C C語言中規(guī)定，下

22、標(biāo)從語言中規(guī)定，下標(biāo)從0 0開始開始不失一般性，按不失一般性，按“行優(yōu)先順序行優(yōu)先順序”存儲存儲關(guān)鍵問題關(guān)鍵問題如何確定一維數(shù)組的大??？如何確定一維數(shù)組的大小？如何確定矩陣元素在一維數(shù)組中的位置？從如何確定矩陣元素在一維數(shù)組中的位置？從而保證對矩陣元素的隨機(jī)存取而保證對矩陣元素的隨機(jī)存取A Aijij的位置的位置 = 該元素前的元素個(gè)數(shù)該元素前的元素個(gè)數(shù)= = 所需空間所需空間12334545671 12 23 34 45 52 23 34 45 56 63 34 45 56 67 74 45 56 67 78 85 56 67 78 89 9存儲下三角存儲下三角矩陣矩陣注意存儲矩陣元素注意存

23、儲矩陣元素的一維數(shù)組的下標(biāo)的一維數(shù)組的下標(biāo)是從是從0 0開始開始1 1 . . 對稱矩陣對稱矩陣如何確定一維數(shù)組的大??？如何確定一維數(shù)組的大??？2) 1( nnN設(shè)：存放下三角陣中的元素，設(shè)：存放下三角陣中的元素，則：如何確定元素則：如何確定元素A Aijij在一維數(shù)組中在一維數(shù)組中的位置？的位置？12334545671 1 2 2 3 3 4 4 5 52 2 3 3 4 4 5 5 6 63 3 4 4 5 5 6 6 7 74 4 5 5 6 6 7 7 8 85 5 6 6 7 7 8 8 9 9(1),2(1),2(A)()ijijijjiiijij Aijjjiij AALoc A

24、當(dāng)在下三角陣中當(dāng)在上三角陣中根據(jù)2. 2. 三角矩陣三角矩陣1 14 44 44 44 42 23 34 44 44 43 36 65 54 44 44 47 79 97 74 45 58 81 12 29 912) 1(nnN1233654如何確定一維數(shù)組的大??？如何確定一維數(shù)組的大??？設(shè)：在下三角陣中，設(shè)：在下三角陣中，則：如何確定元素則：如何確定元素A Aijij在一維數(shù)在一維數(shù)組中的位置？組中的位置？(1), 2(1) 2()iijijijnnijLoc A 當(dāng)， 即下三角陣中的元素，當(dāng)，即上三角陣中的常數(shù)3.3.三對角矩陣三對角矩陣1 11 10 00 00 02 23 37 70

25、00 00 04 45 53 30 00 00 06 67 75 50 00 00 08 89 923 nN如何確定一維數(shù)組的大小？如何確定一維數(shù)組的大??？如何確定元素如何確定元素A Aijij在一維數(shù)組中在一維數(shù)組中的位置？的位置？1123745367589)(ijALoc在在A Aijij之前有之前有i i行行, ,共有共有3 3* *i-1i-1個(gè)非零元素個(gè)非零元素, ,在第在第i i行，行， a aijij之前有之前有j-i+1j-i+1個(gè)非零元素，個(gè)非零元素，3*i-1+(j-i+1) = 2*i+j程序員試題程序員試題2004-1 對矩陣壓縮存儲的主要目的是_。 A方便運(yùn)算B節(jié)省存

26、儲空間 C降低計(jì)算復(fù)雜度D提高運(yùn)算速度2003 將一個(gè)三對角矩陣Al.100，1.100中的元素按行存儲在一維數(shù)組Bl.298中，矩陣A中的元素A66,65在數(shù)組B中的下標(biāo)為_。 A195 B196C197D1985.2.3 5.2.3 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲順序存儲：順序存儲：三元組表三元組表鏈?zhǔn)酱鎯Γ菏宙湵礞準(zhǔn)酱鎯Γ菏宙湵?.1.三元組表存稀疏矩陣三元組表存稀疏矩陣考慮：考慮：只存非零元素只存非零元素一個(gè)非零元素的必需信息有：一個(gè)非零元素的必需信息有： (i, j, aij)記錄一個(gè)稀疏矩陣的必需信息有：記錄一個(gè)稀疏矩陣的必需信息有：行數(shù)行數(shù)M，列數(shù)，列數(shù)N，非零元素個(gè)數(shù)

27、，非零元素個(gè)數(shù)T1 12 20 00 05 50 03 30 00 00 00 04 40 00 00 00 00 06 60 00 00 00 00 08 80 0i ij jA Aijij0 00 01 10 01 12 20 04 45 51 11 13 32 21 14 43 32 26 64 43 38 8M=5N=5T=7三元組表的三元組表的C C語言描述語言描述typedef struct TriTupleNode datamaxsize; / /* *三元組表三元組表* */ / int m, n, t; ; / /* *m m行數(shù)行數(shù),n,n列數(shù)列數(shù),t,t非零元素個(gè)數(shù)非零元

28、素個(gè)數(shù)* */ / TriTupleTable; / 稀疏矩陣類型稀疏矩陣類型 i ij jV V#define maxsize 10000typedef int Elemtype;typedef struct /*三元組結(jié)點(diǎn)三元組結(jié)點(diǎn)*/ int i, j; /該非零元的行下標(biāo)和列下標(biāo)該非零元的行下標(biāo)和列下標(biāo) Elemtype e; / 該非零元的值該非零元的值 TriTupleNode; / 三元組類型三元組類型三元組表表示法：三元組表表示法：1 12 212121 13 39 93 31 1-3-33 35 514144 43 324245 52 218186 61 115156 64

29、4-7-7注意：注意：三元組表中的三元組表中的元素按行（或列）排元素按行（或列）排列。列。m=6m=6n=6n=6t=8t=8i ij jv v稀疏矩陣壓縮存儲的稀疏矩陣壓縮存儲的缺點(diǎn)：將失去隨機(jī)存取功能缺點(diǎn)：將失去隨機(jī)存取功能1 12 23 34 45 56 67 78 80 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 05.2.45.2.4應(yīng)用舉例：應(yīng)用舉例： 稀疏矩陣的轉(zhuǎn)置稀疏矩陣的轉(zhuǎn)置1.矩陣轉(zhuǎn)置的數(shù)學(xué)解釋矩陣轉(zhuǎn)置的數(shù)學(xué)解釋 一個(gè)一個(gè)mn的矩陣的矩陣A，它的轉(zhuǎn)置，它的轉(zhuǎn)置B是一個(gè)是一個(gè)nm

30、的的矩陣，且矩陣，且aij=bji，0im，0jn。007650020060052700Aij=Bji求轉(zhuǎn)置矩陣算法求轉(zhuǎn)置矩陣算法028003600070500140M005280000007143600T用常規(guī)的二維數(shù)組表示時(shí)的算法用常規(guī)的二維數(shù)組表示時(shí)的算法 其時(shí)間復(fù)雜度為其時(shí)間復(fù)雜度為: O(mn) for (col=1; col=n; +col) for (row=1; row=m; +row) Tcolrow = Mrowcol;不正確！不正確?。? 1）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的i i和和j j 互換互換）；）；（2 2）

31、T T的總行數(shù)的總行數(shù)m m和總列數(shù)和總列數(shù)n n與與M M值不同值不同（互換）；互換）；（3 3）重排重排三元組內(nèi)元素順序三元組內(nèi)元素順序，使轉(zhuǎn)置后的三元組也按行，使轉(zhuǎn)置后的三元組也按行 （或列）為主序有規(guī)律的排列。（或列）為主序有規(guī)律的排列。上述（上述（1 1）和（）和（2 2）容易實(shí)現(xiàn)，難點(diǎn)在）容易實(shí)現(xiàn)，難點(diǎn)在（3 3）。提問：提問：若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個(gè)若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個(gè)元素的元素的行下標(biāo)和列下標(biāo)互換行下標(biāo)和列下標(biāo)互換，就完成了對該矩陣的轉(zhuǎn)置運(yùn)，就完成了對該矩陣的轉(zhuǎn)置運(yùn)算，這種說法正確嗎？算，這種說法正確嗎？ 有二種實(shí)現(xiàn)方法有二種實(shí)現(xiàn)方法

32、壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置( (壓縮壓縮) )快速轉(zhuǎn)置快速轉(zhuǎn)置( (1, 2, 121, 2, 12) )( (1, 3, 91, 3, 9 ) )(3, 1, -3)(3, 1, -3)(3, 5, 14)(3, 5, 14)(4, 3, (4, 3, 24)24)(5, 2, 18)(5, 2, 18)(6, 1, 15)(6, 1, 15)(6, 4, -7)(6, 4, -7)(1, 3, -3)(1, 3, -3)(1, 6, 15)(1, 6, 15)( (2, 1, 122, 1, 12) )(2, 5, 18)(2, 5, 18)( (3, 1, 93, 1, 9) )(3, 4, 24

33、)(3, 4, 24)(4, 6, -7)(4, 6, -7)(5, 3, 14)(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 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=?2.2.利用三元組表實(shí)現(xiàn)轉(zhuǎn)置利用三元組表實(shí)現(xiàn)轉(zhuǎn)置思想一：直接交換思想一：直接交換a.data中中i和和j的內(nèi)容的內(nèi)容 問題：問題

34、：b.data是一個(gè)按列優(yōu)先順序存儲的稀疏矩陣是一個(gè)按列優(yōu)先順序存儲的稀疏矩陣B 解決方法：重新排列解決方法：重新排列B中三元組的順序。中三元組的順序。0 02 25 50 03 30 00 04 40 00 00 06 6i ij jA Aijij0 01 12 20 02 25 51 11 13 32 21 14 43 32 26 6M=4N=2T=50 00 00 00 02 23 34 40 05 50 00 06 6i ij jB Bijij1 10 02 22 20 05 51 11 13 31 12 24 42 23 36 6Aij=Bjii ij jB Bijij1 10 02

35、 21 11 13 31 12 24 42 20 05 52 23 36 6ji 按按i i排序排序M=2N=4T=5行優(yōu)先行優(yōu)先列優(yōu)先列優(yōu)先b.mb.m= =a.na.n; ; b.nb.n= =a.ma.m; ; b.tb.t= =a.ta.t; ; / /* *基本信息的賦值基本信息的賦值* */ / /* *按交換按交換i i、j j的方式給的方式給B B的三元組賦值的三元組賦值* */ /for ( i=0; ifor ( i=0; ib.tb.t; i+ ) ; i+ ) b.datai.ib.datai.i= =a.datai.ja.datai.j; ; b.datai.jb.d

36、atai.j= =a.datai.ia.datai.i; ; b.datai.eb.datai.e= =a.datai.ea.datai.e;/ /* *掃描掃描B B，按，按i i排序排序* */ /i ij jA Aijij0 01 12 20 02 25 51 11 13 32 21 14 43 32 26 6M=4N=2T=5i ij jB Bijij1 10 02 22 20 05 51 11 13 31 12 24 42 23 36 6i ij jB Bijij1 10 02 21 11 13 31 12 24 42 20 05 52 23 36 6ji 按按i i排序排序M=2N

37、=4T=5思想二：在思想二：在A A中按列序找中按列序找三元組，寫入三元組，寫入B BB B的行優(yōu)先即的行優(yōu)先即A A的列優(yōu)先的列優(yōu)先對對B B的第的第colcol列列 ，掃描掃描三元組表三元組表a.dataa.data，找出所有列號等于，找出所有列號等于colcol的三元組，將它們的行號和列號互換后依次放入的三元組，將它們的行號和列號互換后依次放入b.datab.data中，即可得到中，即可得到B B的按行優(yōu)先的壓縮存儲表示。的按行優(yōu)先的壓縮存儲表示。0 02 25 50 03 30 00 04 40 00 00 06 6i ij jA Aijij0 01 12 20 02 25 51 11

38、 13 32 21 14 43 32 26 6M=4N=2T=50 00 00 00 02 23 34 40 05 50 00 06 6Aij=Bjii ij jB Bijij1 10 02 21 11 13 31 12 24 42 20 05 52 23 36 6M=2N=4T=5col=0，沒有匹配的三元組，沒有匹配的三元組col=1，找到，找到2，3，4col=2，找到，找到5，6 思路：思路：反復(fù)掃描反復(fù)掃描A.dataA.data中的中的列序列序，從小到大從小到大依次進(jìn)行轉(zhuǎn)置。依次進(jìn)行轉(zhuǎn)置。6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18

39、6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8A7 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 8Bqppppppppqqqqppppppppcol=1col=2qqqVoid transmatrix(tripletable a,tripletable &b) int pa, pb, col; b.m=a.n; b.n=a.m; b.t=a.t; /*基本信息的賦值基本信息的賦值*/ if(b.t=0) printf(“A=0n”); retur

40、n 0; /*無非零元素?zé)o非零元素*/ pb=0; /*pb指向三元組表指向三元組表B中的當(dāng)前位置中的當(dāng)前位置*/ for(col=0; cola.n; col+) /*按列按列col掃描表掃描表A*/ for(pa=0; pa=a.t; pa+) /*pa指向表指向表A中的當(dāng)前位置中的當(dāng)前位置*/ /*找所有列號等于找所有列號等于col的三元組，的三元組，i,j互換寫放入互換寫放入B*/ if(a.datapa.j=col) b.datapb.i=a.datapa.j; b.datapb.j=a.datapa.i; b.datapb.e=a.datapa.e; pb+; 1 1、主要時(shí)間消耗

41、在主要時(shí)間消耗在查找查找A.datapa.jA.datapa.j= =colcol的元素的元素，由兩重循，由兩重循環(huán)完成環(huán)完成: : for(col=0; cola.n; col+) 循環(huán)次數(shù)循環(huán)次數(shù)n for(pa=0; pa=a.t; pa+) 循環(huán)次數(shù)循環(huán)次數(shù)t所以該算法的時(shí)間復(fù)雜度為所以該算法的時(shí)間復(fù)雜度為O(O(n*t) ) - -即即M M的列數(shù)與的列數(shù)與M M中非零元素的個(gè)數(shù)之中非零元素的個(gè)數(shù)之積積最壞情況最壞情況：M M中全是非零元素，此時(shí)中全是非零元素，此時(shí)t=mt=m* *n n， 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(O(n2 2*m ) )注：注：若若M M中基本上是非零元素時(shí)

42、，即使用中基本上是非零元素時(shí)，即使用非壓縮傳統(tǒng)轉(zhuǎn)置算法非壓縮傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度也不過是的時(shí)間復(fù)雜度也不過是O(O(n*m) )結(jié)論：結(jié)論：壓縮轉(zhuǎn)置算法不能濫用。壓縮轉(zhuǎn)置算法不能濫用。前提前提：僅適用于非零元素個(gè)數(shù)很少（即僅適用于非零元素個(gè)數(shù)很少（即t tm m* *n n）的情況。的情況。算法的效率分析算法的效率分析三三元元組組表表A.data三三元元組組表表B.data(1, 3, -3)(2 ,1, 12)(2, 5, 18)(3, 1, 9)(4, 6, -7)(5, 3, 14)(1, 6, 15)(3, 4, 24)( (1, 2, 121, 2, 12) )( (1, 3,

43、91, 3, 9 ) )(3, 1, -3)(3, 1, -3)(3, 5, 14)(3, 5, 14)(4, 3, 24)(4, 3, 24)(5, 2, 18)(5, 2, 18)(6, 1, 15)(6, 1, 15)(6, 4, -7)(6, 4, -7)基本思想：基本思想：在在A A中按行序找三元組，確定該三元組在中按行序找三元組，確定該三元組在B B中的中的位置，寫入位置，寫入B B中適當(dāng)位置。中適當(dāng)位置。 即依次即依次把把A.dataA.data中的元素直接送入中的元素直接送入B.dataB.data的恰當(dāng)位置上的恰當(dāng)位置上 p0123 q 2 4思想三：思想三：快速轉(zhuǎn)置快速轉(zhuǎn)置

44、關(guān)鍵問題：如何確定每個(gè)三元組在關(guān)鍵問題：如何確定每個(gè)三元組在B B中的位置中的位置A A中某個(gè)三元組在中某個(gè)三元組在B B的中位置的中位置= = 每列的第一個(gè)非零元素在數(shù)組每列的第一個(gè)非零元素在數(shù)組B B中應(yīng)有的位置中應(yīng)有的位置 + + 每一列在它之前非零元素的個(gè)數(shù)每一列在它之前非零元素的個(gè)數(shù)注意：注意：根據(jù)根據(jù)M.dataM.data的特征，每列第一個(gè)非零元素必的特征，每列第一個(gè)非零元素必 定先被掃描到。定先被掃描到。為了求得每列的第一個(gè)非零元素在數(shù)組為了求得每列的第一個(gè)非零元素在數(shù)組B B中應(yīng)有的位置需先求中應(yīng)有的位置需先求1.1. 矩陣矩陣M M中的每一列中非零元的個(gè)數(shù)中的每一列中非零元

45、的個(gè)數(shù)令令：A A中的列變量用中的列變量用colcol表示；表示； cnumcnum colcol ：存放存放A A中第中第colcol 列中非列中非0 0元素個(gè)數(shù)元素個(gè)數(shù) cposcpos colcol ：存放存放A A中第中第colcol列的第一個(gè)非列的第一個(gè)非0 0元素的位置元素的位置 （即（即A.dataA.data中待計(jì)算的中待計(jì)算的“恰當(dāng)恰當(dāng)”位置所需參考點(diǎn)）位置所需參考點(diǎn)）colcol123456cnumcolcnumcol 222110cposcolcposcol 0規(guī)律規(guī)律: cpos00 cposcol cposcol-1 + cnumcol-10 12 9 0 0 00

46、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= 2 col 1 2 3 4 5 6 4 8 7 6 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 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 5 3 14 pppppppp4629753colcol1 12 23 34 45 56 6cnumcolcnumcol 2 22 22 21 1

47、1 10 0cposcolcposcol 1 13 35 57 78 89 9i j v0 1 2 3 4 5 6 7 8Tvoid fasttranstri(tritupletable a, tritupletable &b) int col；/*當(dāng)前列號當(dāng)前列號*/ int pa,pb; /*分別表示分別表示a,b的當(dāng)前位置的當(dāng)前位置*/ int cnumn, cposn; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0n”); return 0; for(col=0;cola.n;col+) cnumcol=0; /每列元素的個(gè)數(shù)

48、初始化每列元素的個(gè)數(shù)初始化 /*統(tǒng)計(jì)統(tǒng)計(jì)a中每列非零元素的個(gè)數(shù)；中每列非零元素的個(gè)數(shù)；*/ for(pa=0; paa.t; pa+) col=a.datapa.j; cnumcol+; /*由遞推關(guān)系計(jì)算由遞推關(guān)系計(jì)算cpos的值的值*/ cpos0=0; for(col=1;col=a.n;col+) cposcol = cposcol-1 + cnumcol-1; /*掃描掃描a，將元素交換，將元素交換i,j寫入寫入b*/ for( pa=0; paa.t; pa+ ) col = a.datapa.j; pb = cposcol; b.datapb.i = a.datapa.j; b.

49、datapb.j = a.datapa.i; b.datapb.v = a.datapa.v; cposcol+; /修改向量表中列坐標(biāo)值，供同一修改向量表中列坐標(biāo)值，供同一列下一非零元素定位之用！列下一非零元素定位之用！ 1.1. 與常規(guī)算法相比，增加了與常規(guī)算法相比，增加了2 2個(gè)長度為列長的輔助數(shù)個(gè)長度為列長的輔助數(shù)組組( (cnum 和和cpos ）?？焖俎D(zhuǎn)置算法的效率分析快速轉(zhuǎn)置算法的效率分析：2.2. 從時(shí)間上，此算法用了從時(shí)間上，此算法用了4 4個(gè)并列的單循環(huán)，而且其個(gè)并列的單循環(huán)，而且其中前中前3 3個(gè)單循環(huán)都是用來產(chǎn)生輔助數(shù)組的。個(gè)單循環(huán)都是用來產(chǎn)生輔助數(shù)組的。 for(co

50、l = 0; col a.n; col+) 循環(huán)次數(shù)循環(huán)次數(shù)n;n; for( pa = 0; pa a.t; pa +) 循環(huán)次數(shù)循環(huán)次數(shù)t;t; for(col = 1; col a.n; col+) 循環(huán)次數(shù)循環(huán)次數(shù)n;n; for( pa=0; pa a.t ; pa + ) 循環(huán)次數(shù)循環(huán)次數(shù)t;t; 該算法的時(shí)間復(fù)雜度該算法的時(shí)間復(fù)雜度( (n n* *2)+(t2)+(t* *2)=2)=O(O(n+tn+t） 傳統(tǒng)轉(zhuǎn)置：傳統(tǒng)轉(zhuǎn)置：O(O(m m* *n n) ) 壓縮轉(zhuǎn)置：壓縮轉(zhuǎn)置：O(O(m m* *t t) ) 壓縮快速轉(zhuǎn)置：壓縮快速轉(zhuǎn)置：O(O(n+tn+t) )犧牲空間效

51、率換時(shí)犧牲空間效率換時(shí) 間效率。間效率。小結(jié)：小結(jié)：討論：討論：最壞情況是最壞情況是t=nt=n* *m m( (即矩陣中全部是非零元素），即矩陣中全部是非零元素），而此時(shí)的時(shí)間復(fù)雜度也只是而此時(shí)的時(shí)間復(fù)雜度也只是O(O(m m* *n n) )，并未超過傳統(tǒng)轉(zhuǎn)并未超過傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度。置算法的時(shí)間復(fù)雜度。鏈?zhǔn)酱鎯Y(jié)構(gòu)o 帶行指針向量的單鏈表表示Y每行的非零元用一個(gè)單鏈表存放 Y設(shè)置一個(gè)行指針數(shù)組，指向本行第一個(gè)非零元結(jié)點(diǎn)；若本行無非零元，則指針為空Y表頭結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)類型定義typedef struct node int col; int val; struct node *lin

52、k;JD;typedef struct node *TD;0200000000000210010070003A1 35 73 -11 -12 -24 2需存儲單元個(gè)數(shù)為3t+mo 十字鏈表Y設(shè)行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個(gè)非零元Y結(jié)點(diǎn)定義tpedef struct node int row,col,val; struct node *down, *right;JD;row col valdownright34008000450003A113418225234廣義表是第廣義表是第2 2章提到的線性表的推廣。線性表中的元素僅限于章提到的線性表的推廣。線性表中的元素僅限于原子項(xiàng)，即不

53、可以再分，而廣義表中的元素既可以是原子項(xiàng)原子項(xiàng)，即不可以再分，而廣義表中的元素既可以是原子項(xiàng)，也可以是子表（另一個(gè)線性表）。，也可以是子表（另一個(gè)線性表）。5.3 5.3 廣義表廣義表5.4 5.4 廣義表的定義廣義表的定義廣義表是線性表的推廣，也稱為列表（廣義表是線性表的推廣，也稱為列表（lists）。廣義表中元素。廣義表中元素既可以是原子類型，也可以是列表。既可以是原子類型，也可以是列表。記為：記為： LS = ( a1 , a2 , ， an ) 廣義表名廣義表名 a1是表頭是表頭(Head） （ a2 ,an ）是表尾是表尾 (Tail)1、定義：、定義：n n是表長是表長 ai可以是

54、單個(gè)元素，也可以是廣義表，分別稱為廣義表可以是單個(gè)元素，也可以是廣義表，分別稱為廣義表LS的的原原子子和和子表子表；第一個(gè)第一個(gè)元素是表頭元素是表頭，而其余元素組成的，而其余元素組成的表表稱為表尾稱為表尾； 所以任何一個(gè)非空表，表頭可能是原子，也可能是列表；但所以任何一個(gè)非空表，表頭可能是原子，也可能是列表；但表尾表尾一定是列表一定是列表。 約定：用小寫字母表示原子類型，用約定：用小寫字母表示原子類型，用大寫字母大寫字母表示列表。表示列表。在廣義表中約定：在廣義表中約定：2、特點(diǎn)：、特點(diǎn)：1）次序性：）次序性：一個(gè)直接前驅(qū)和一個(gè)直接后繼一個(gè)直接前驅(qū)和一個(gè)直接后繼2）長度：）長度：表中表中最外層

55、最外層包含元素個(gè)數(shù)包含元素個(gè)數(shù)3）深度：）深度：當(dāng)廣義表全部用原子代替后，表當(dāng)廣義表全部用原子代替后，表中中括號的最大重?cái)?shù)括號的最大重?cái)?shù) 空表（空表（ ）的深度為）的深度為1，長度為，長度為0 ，原子的深度為，原子的深度為0.4）可遞歸：）可遞歸：自己可以作為自己的子表。自己可以作為自己的子表。 例例E=(a, E) 遞歸表的深度是無窮值，長度是遞歸表的深度是無窮值，長度是2。5）可共享）可共享: 可以為其它廣義表所共享的表?？梢詾槠渌鼜V義表所共享的表。6 6）任何一個(gè)非空廣義表）任何一個(gè)非空廣義表 LS = ( LS = ( 1, 1, 2, 2, , , n)n) 均可分解為均可分解為 表頭表頭 GetHead(LS) = 1 和和 表尾表尾 GetTa