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

1、第五章第五章 數(shù)組和廣義表數(shù)組和廣義表 限制插入、刪除位置限制插入、刪除位置線性表線性表具有相同類型的數(shù)據(jù)元素的有限序列。具有相同類型的數(shù)據(jù)元素的有限序列。線性表線性表具有相同類型的數(shù)據(jù)元素的有限序列。具有相同類型的數(shù)據(jù)元素的有限序列。限制元素類型為字符限制元素類型為字符棧棧僅在表尾進(jìn)行插入和刪除操作的線性表。僅在表尾進(jìn)行插入和刪除操作的線性表。隊(duì)列隊(duì)列在一端進(jìn)行插入操作，而另一端進(jìn)行在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。刪除操作的線性表。串串零個(gè)或多個(gè)字符組成的有限序列零個(gè)或多個(gè)字符組成的有限序列 。特特殊殊線線性性表表回憶：回憶：特點(diǎn)：特點(diǎn)：數(shù)據(jù)元素都是非數(shù)據(jù)元素都是非結(jié)構(gòu)的原

2、子類型，元素結(jié)構(gòu)的原子類型，元素的值是不再分割的。的值是不再分割的。什么是線性表？什么是線性表？線性表線性表具有相同類型的數(shù)據(jù)元素的有限序列。具有相同類型的數(shù)據(jù)元素的有限序列。將元素的類型進(jìn)行擴(kuò)充將元素的類型進(jìn)行擴(kuò)充廣廣義義線線性性表表（多維）數(shù)組（多維）數(shù)組線性表中的數(shù)據(jù)元素可以是線性表中的數(shù)據(jù)元素可以是線性表，但所有元素的類型相同。線性表，但所有元素的類型相同。廣義表廣義表線性表中的數(shù)據(jù)元素可以是線性表，線性表中的數(shù)據(jù)元素可以是線性表，且元素的類型可以不相同。且元素的類型可以不相同。數(shù)組和廣義表數(shù)組和廣義表 本章討論的兩種數(shù)據(jù)結(jié)構(gòu)本章討論的兩種數(shù)據(jù)結(jié)構(gòu)數(shù)組和廣義表數(shù)組和廣義表可以看成是線性

3、表的擴(kuò)展，即表中的數(shù)據(jù)元素可以看成是線性表的擴(kuò)展，即表中的數(shù)據(jù)元素本身也是一個(gè)線性表。本身也是一個(gè)線性表。5.1 數(shù)組數(shù)組的定義的定義5.3 矩陣矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ) 5.2 數(shù)組數(shù)組的順序表示和實(shí)現(xiàn)的順序表示和實(shí)現(xiàn)5.4 廣義表廣義表的類型定義的類型定義5.5 廣義表廣義表的表示方法的表示方法第第5章章 數(shù)組和廣義表數(shù)組和廣義表 5.1 數(shù)組的定義數(shù)組的定義n數(shù)組的定義數(shù)組的定義q數(shù)組是由一組類型相同的數(shù)據(jù)元素構(gòu)成的有序集合，每數(shù)組是由一組類型相同的數(shù)據(jù)元素構(gòu)成的有序集合，每個(gè)數(shù)據(jù)元素稱為一個(gè)數(shù)組元素（簡(jiǎn)稱為元素），每個(gè)元個(gè)數(shù)據(jù)元素稱為一個(gè)數(shù)組元素（簡(jiǎn)稱為元素），每個(gè)元素受素受n(n1)

4、個(gè)線性關(guān)系的約束，每個(gè)元素在個(gè)線性關(guān)系的約束，每個(gè)元素在n個(gè)線性關(guān)個(gè)線性關(guān)系中的序號(hào)系中的序號(hào)i1、i2、in稱為該元素的下標(biāo)，并稱該數(shù)稱為該元素的下標(biāo)，并稱該數(shù)組為組為 n 維數(shù)組。維數(shù)組。 n數(shù)組的特點(diǎn)數(shù)組的特點(diǎn)q元素本身可以具有某種結(jié)構(gòu)，屬于同一數(shù)據(jù)類型；元素本身可以具有某種結(jié)構(gòu)，屬于同一數(shù)據(jù)類型；q數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合。數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合。 a11 a12 a1n a21 a22 a2n am1 am2 amnA=例如，元素例如，元素a22受兩個(gè)線性關(guān)系的約束，在行上有受兩個(gè)線性關(guān)系的約束，在行上有一個(gè)行前驅(qū)一個(gè)行前驅(qū)a21和一個(gè)行后繼和一個(gè)行后繼

5、a23，在列上有一個(gè)列，在列上有一個(gè)列前驅(qū)前驅(qū)a12和和一個(gè)列后繼和和一個(gè)列后繼a32。數(shù)組示例數(shù)組示例5.1 數(shù)組的定義數(shù)組的定義 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=(A1，A2，An) 其中：其中： Ai=(a1i，a2i，ami) (1in)數(shù)組數(shù)組線性表的推廣線性表的推廣二維數(shù)組是二維數(shù)組是數(shù)據(jù)元素為線性表的線性表。數(shù)據(jù)元素為線性表的線性表。5.1 數(shù)組的定義數(shù)組的定義數(shù)組的基本操作數(shù)組的基本操作在數(shù)組中插入（或刪除）一個(gè)元素有意義嗎在數(shù)組中插入（或刪除）一個(gè)元素有意義嗎？ a11 a12 a1n a21 a22 a2n am1 am2 a

6、mnA=將元素將元素 x 插入插入到數(shù)組中第到數(shù)組中第1行第行第2列。列。x a11 a12 a1n a21 a22 a2n am1 am2 amnA=刪除數(shù)組中刪除數(shù)組中第第1行第行第2列元素。列元素。5.1 數(shù)組的定義數(shù)組的定義數(shù)組一旦被定義，數(shù)組一旦被定義，它的維數(shù)和維界就它的維數(shù)和維界就不再改變，一般不不再改變，一般不做插入和刪除操作做插入和刪除操作數(shù)組的基本操作（存取）數(shù)組的基本操作（存?。?讀取：給定一組下標(biāo)，讀出對(duì)應(yīng)的數(shù)組元素；讀?。航o定一組下標(biāo)，讀出對(duì)應(yīng)的數(shù)組元素； 修改：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的修改：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)組元素。數(shù)組元素。讀取和修

7、改操作本質(zhì)上只對(duì)應(yīng)一種操作讀取和修改操作本質(zhì)上只對(duì)應(yīng)一種操作尋址尋址數(shù)組應(yīng)該采用何種方式存儲(chǔ)？數(shù)組應(yīng)該采用何種方式存儲(chǔ)？數(shù)組沒有插入和刪除操作，所以，不用預(yù)留空間，數(shù)組沒有插入和刪除操作，所以，不用預(yù)留空間，適合采用順序存儲(chǔ)。適合采用順序存儲(chǔ)。5.1 數(shù)組的定義數(shù)組的定義數(shù)組的類型定義：p90設(shè)設(shè)一維數(shù)組一維數(shù)組的下標(biāo)的范圍為閉區(qū)間的下標(biāo)的范圍為閉區(qū)間l，h，每個(gè)每個(gè)數(shù)組元素占用數(shù)組元素占用 c 個(gè)存儲(chǔ)單元，則個(gè)存儲(chǔ)單元，則其其任一元任一元素素 ai 的的存儲(chǔ)地址可由下式確定：存儲(chǔ)地址可由下式確定： Loc(ai)Loc(al)(il)c c al ai-1 ai ah al+1 Loc(al

8、)Loc(ai)5.2 數(shù)組數(shù)組的順序表示和實(shí)現(xiàn)的順序表示和實(shí)現(xiàn)一維數(shù)組一維數(shù)組常用的映射方法有兩種：常用的映射方法有兩種：按按行行優(yōu)先：優(yōu)先：先行后列先行后列，先存儲(chǔ)行號(hào)較小的元素，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相同者先存儲(chǔ)列號(hào)較小的元素行號(hào)相同者先存儲(chǔ)列號(hào)較小的元素。PASCAL、C;按按列列優(yōu)先：優(yōu)先：先列后行先列后行，先存儲(chǔ)列號(hào)較小的元素，先存儲(chǔ)列號(hào)較小的元素，列號(hào)相同者先存儲(chǔ)行號(hào)較小的元素。列號(hào)相同者先存儲(chǔ)行號(hào)較小的元素。FORTRAN;二維數(shù)組二維數(shù)組內(nèi)內(nèi) 存存二維結(jié)構(gòu)二維結(jié)構(gòu)一維結(jié)構(gòu)一維結(jié)構(gòu)5.2 數(shù)組數(shù)組的順序表示和實(shí)現(xiàn)的順序表示和實(shí)現(xiàn)二維數(shù)組二維數(shù)組l2h2 l1h1(a) 二維

9、數(shù)組二維數(shù)組aij前面的元素個(gè)數(shù)前面的元素個(gè)數(shù)=陰影部分表示的元素個(gè)數(shù)陰影部分表示的元素個(gè)數(shù)=整行數(shù)每行元素個(gè)數(shù)整行數(shù)每行元素個(gè)數(shù)+本行中本行中aij前面的元素個(gè)數(shù)前面的元素個(gè)數(shù)=( (i - -l1) )( (h2 - -l21) )( (j - -l2) )本行中本行中aij前面的元素個(gè)數(shù)前面的元素個(gè)數(shù)每行元素個(gè)數(shù)每行元素個(gè)數(shù)整整行行數(shù)數(shù)aij按行優(yōu)先存儲(chǔ)的尋址按行優(yōu)先存儲(chǔ)的尋址5.2 數(shù)組數(shù)組的順序表示和實(shí)現(xiàn)的順序表示和實(shí)現(xiàn)二維數(shù)組二維數(shù)組第第l1行行第第l1+1行行al1l2 al1h2 a(l1+1)l2 a(l1+1)h2 aij ah1h2Loc( (aij) )Loc( (al

10、1l2) )( (i - -l1) )( (h2 - -l21) )( (j - -l2) )個(gè)元素個(gè)元素Loc(aij)Loc(al1l2)(il1)(h2l21)(jl2)c按列優(yōu)先存儲(chǔ)的尋址方法與此類似。按列優(yōu)先存儲(chǔ)的尋址方法與此類似。按行優(yōu)先存儲(chǔ)的尋址按行優(yōu)先存儲(chǔ)的尋址5.2 數(shù)組數(shù)組的順序表示和實(shí)現(xiàn)的順序表示和實(shí)現(xiàn)二維數(shù)組二維數(shù)組例例5.2.1：以矩陣形式表示的：以矩陣形式表示的m行行n列的二維數(shù)組如下列的二維數(shù)組如下：若每個(gè)數(shù)組元素占用若每個(gè)數(shù)組元素占用 L 個(gè)存儲(chǔ)單元，個(gè)存儲(chǔ)單元，計(jì)算分別以計(jì)算分別以行序、列序?yàn)橹餍驎r(shí)行序、列序?yàn)橹餍驎r(shí)數(shù)據(jù)元素?cái)?shù)據(jù)元素aij的存儲(chǔ)位置。的存儲(chǔ)位置

11、。Amn=a00 a01 a02 a0,n-1a10 a11 a12 a1,n-1 am-1,0 am-1,1 am-1,2 am-1,n-1行序?yàn)橹餍虻拇鎯?chǔ)示圖：行序?yàn)橹餍虻拇鎯?chǔ)示圖：a00 a01 a0n-1 a10 a11a1n-1 am-1,0 am-1,1 am-1,n-1數(shù)據(jù)元素?cái)?shù)據(jù)元素aij的存儲(chǔ)位置：的存儲(chǔ)位置： loc(i,j)=loc(0,0)+aij之前的元素個(gè)數(shù)之前的元素個(gè)數(shù)LAmn=a00 a01 a02 a0,n-1a10 a11 a12 a1,n-1 am-1,0 am-1,1 am-1,2 am-1,n-1(i*n+j)列序?yàn)橹餍虻拇鎯?chǔ)示圖：列序?yàn)橹餍虻拇鎯?chǔ)示圖

12、：a00 a10 am-10 a01 a11am-1,1 a0,n-1 a1,n-1 am-1,n-1Amn=a00 a01 a02 a0,n-1a10 a11 a12 a1,n-1 am-1,0 am-1,1 am-1,2 am-1,n-1數(shù)據(jù)元素的存儲(chǔ)位置：數(shù)據(jù)元素的存儲(chǔ)位置： loc(i,j)=loc(0,0)+aij之前的元素個(gè)數(shù)之前的元素個(gè)數(shù)Lj*m+in特殊矩陣：特殊矩陣：包括對(duì)稱矩陣、三角矩陣、對(duì)角矩陣包括對(duì)稱矩陣、三角矩陣、對(duì)角矩陣和稀疏矩陣等。和稀疏矩陣等。 n稀疏矩陣：稀疏矩陣：矩陣中有很多零元素。矩陣中有很多零元素。n壓縮存儲(chǔ)壓縮存儲(chǔ)的基本思想是：的基本思想是：q為多個(gè)值

13、相同的元素只分配一個(gè)存儲(chǔ)空間；為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；q對(duì)零元素不分配存儲(chǔ)空間。對(duì)零元素不分配存儲(chǔ)空間。 5.3 矩陣矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ) 3647862842481697460582957A對(duì)稱矩陣特點(diǎn)：對(duì)稱矩陣特點(diǎn)：aij=aji如何壓縮存儲(chǔ)？如何壓縮存儲(chǔ)？只存儲(chǔ)下三角部分的元素。只存儲(chǔ)下三角部分的元素。5.3.1 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)對(duì)稱矩陣對(duì)稱矩陣 (a) 下三角矩陣下三角矩陣 (b) 存儲(chǔ)說明存儲(chǔ)說明 (c) 計(jì)算方法計(jì)算方法aij在一維數(shù)組中的序號(hào)在一維數(shù)組中的序號(hào)=陰影部分的元素個(gè)數(shù)陰影部分的元素個(gè)數(shù)= i( (i+1) )/2+ j+1一維數(shù)組

14、下標(biāo)從一維數(shù)組下標(biāo)從0開始開始aij在一維數(shù)組中的下標(biāo)在一維數(shù)組中的下標(biāo)k= i( (i+1) )/2+ j 0 in- -10 j n- -1 aij每行元素個(gè)數(shù)每行元素個(gè)數(shù)12iaij在本行中的序號(hào)在本行中的序號(hào)aij第第0行行第第1行行第第i-1行行5.3.1 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)對(duì)稱矩陣對(duì)稱矩陣 對(duì)于下三角中的元素對(duì)于下三角中的元素aij（ij），在數(shù)組，在數(shù)組SA中的下標(biāo)中的下標(biāo)k與與i、j的關(guān)系為：的關(guān)系為：ki(i1)/2j 。上三角中的元素上三角中的元素aij（ij），），因?yàn)橐驗(yàn)閍ijaji，則訪問和則訪問和它對(duì)應(yīng)的元素它對(duì)應(yīng)的元素aji即可，即：即可，即：k

15、j(j1)/2i 。第第1行行第第n-1行行第第0行行 a00 a10 a11 a20 a21 a22 aij a n-10 an-11 an-1n-1 第第2行行0 1 2 3 4 5 k n(n+1)/2-15.3.1 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)對(duì)稱矩陣對(duì)稱矩陣 令令 I = maxi,j, = maxi,j,J = mini,j, = mini,j,則則JIIk2) 1(3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5 7(a)下三角矩陣下三角矩陣3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)上三角矩陣上三角矩陣

16、如何壓縮存儲(chǔ)？如何壓縮存儲(chǔ)？只存儲(chǔ)下三角（或上三角）部分的元素。只存儲(chǔ)下三角（或上三角）部分的元素。5.3.2 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)三角矩陣三角矩陣 矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標(biāo)中的下標(biāo)k與與i、j的對(duì)應(yīng)關(guān)系的對(duì)應(yīng)關(guān)系：i( (i1) )/2j 當(dāng)當(dāng)ijn( (n1) )/2 當(dāng)當(dāng)ijk=0 1 2 3 4 5 k n(n+1)/2第第1行行第第0行行 a00 a10 a11 a20 a21 aij an-1n-1 第第2行行 c a22存儲(chǔ)存儲(chǔ)下三角下三角元素元素對(duì)角線上方的常數(shù)對(duì)角線上方的常數(shù)只存一個(gè)只存一個(gè)5.3.2 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的

17、壓縮存儲(chǔ)三角矩陣三角矩陣 矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標(biāo)中的下標(biāo)k與與i、j的對(duì)應(yīng)關(guān)系：的對(duì)應(yīng)關(guān)系： i( (2ni1) )/2ji 當(dāng)當(dāng)ijn( (n1) ) /2 當(dāng)當(dāng)ijk=存儲(chǔ)存儲(chǔ)上三角上三角元素元素對(duì)角線上方的常數(shù)對(duì)角線上方的常數(shù)只存一個(gè)只存一個(gè)5.3.1 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)三角矩陣三角矩陣 例例5.3.1：n假設(shè)以一維數(shù)組作為假設(shè)以一維數(shù)組作為n階對(duì)稱矩陣階對(duì)稱矩陣A的存儲(chǔ)空的存儲(chǔ)空間，以行序?yàn)橹餍虼鎯?chǔ)間，以行序?yàn)橹餍虼鎯?chǔ)A的下三角，則元素的下三角，則元素A56的值存儲(chǔ)在的值存儲(chǔ)在S_中。中。n 6*(6+1)/2+5=26對(duì)角矩陣：對(duì)角矩

18、陣：所有非零元素都集中在以主對(duì)角線為中心所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，除了主的帶狀區(qū)域中，除了主對(duì)角線和它的上下方若干條對(duì)對(duì)角線和它的上下方若干條對(duì)角線的元素外，所有其他元素都為零。角線的元素外，所有其他元素都為零。 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=5.3.3 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)對(duì)角矩陣對(duì)角矩陣 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=將帶狀區(qū)將帶

19、狀區(qū)域立起來域立起來0 a00a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a44 0B=sj- -i+1t=i映射到二維數(shù)組映射到二維數(shù)組B中，映射關(guān)系中，映射關(guān)系5.3.3 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)對(duì)角矩陣對(duì)角矩陣 按行按行存儲(chǔ)存儲(chǔ) 元素元素aij在一維數(shù)組中的序號(hào)在一維數(shù)組中的序號(hào)=2 + 3( (i1) )+( ( ji + 2) )=2i+ j+1 一維數(shù)組下標(biāo)從一維數(shù)組下標(biāo)從0開始開始元素元素aij在一維數(shù)組中的下標(biāo)在一維數(shù)組中的下標(biāo)=2i+ j(b) 尋址的計(jì)算方法尋址的計(jì)算方法(c) 壓縮到一維數(shù)組中壓縮到一維數(shù)組中a00 a01

20、a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a440 1 2 3 4 5 6 7 8 9 10 11 12(a) 三對(duì)角矩陣三對(duì)角矩陣 0 0 0 0 00 00 0 0 0 0 A=a00 a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a445.3.3 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)對(duì)角矩陣對(duì)角矩陣 15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0 A=如何只存儲(chǔ)非零元素？如何只存儲(chǔ)非零元素？注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。注意：稀疏

21、矩陣中的非零元素的分布沒有規(guī)律。5.3.4 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)稀疏矩陣稀疏矩陣 29typedef struct int i, j; /行下標(biāo)，列下標(biāo)行下標(biāo)，列下標(biāo) ElemType e; /非零元素值非零元素值 Triple ;將稀疏矩陣中的每個(gè)非零元素表示為將稀疏矩陣中的每個(gè)非零元素表示為：( (行號(hào)，列號(hào)，非零元素值行號(hào)，列號(hào)，非零元素值) )三元組三元組定義三元組：定義三元組：方法一方法一：稀疏矩陣的壓縮存儲(chǔ)：稀疏矩陣的壓縮存儲(chǔ)三元組三元組5.3.4 特殊矩陣特殊矩陣的壓縮存儲(chǔ)的壓縮存儲(chǔ)稀疏矩陣稀疏矩陣 三元組表三元組表：將稀疏矩陣的非零元素對(duì)應(yīng)的三元組所將稀疏矩陣的

22、非零元素對(duì)應(yīng)的三元組所構(gòu)成的集合，構(gòu)成的集合，按行優(yōu)先的順序排列成一個(gè)線性表。按行優(yōu)先的順序排列成一個(gè)線性表。三元組表三元組表( (0,0,15), (1,1,11), (2,3,6), (4,0,9) )15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0A=如何存儲(chǔ)三元組表？如何存儲(chǔ)三元組表？稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)三元組三元組采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表15 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0

23、0 0A=三元組順序表是否三元組順序表是否需要預(yù)留存儲(chǔ)空間？需要預(yù)留存儲(chǔ)空間？稀疏矩陣的修改操作稀疏矩陣的修改操作三元組順序表的插入三元組順序表的插入/ /刪除操作刪除操作稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)三元組三元組采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -115 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0

24、0 0A=7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）是否對(duì)應(yīng)唯一的稀疏矩陣？是否對(duì)應(yīng)唯一的稀疏矩陣？5（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)三元組三元組三元組順序表以順序存儲(chǔ)結(jié)構(gòu)表示三元組表，是稀疏矩陣的一種壓縮存儲(chǔ)方式。#define MAXSIZE 12500 /非零元個(gè)數(shù)最大值非零元個(gè)數(shù)最大值typedef struct int i, j; /行下標(biāo)和列下標(biāo)行下標(biāo)和列下標(biāo)ElemType e; Triple;typedef structTriple dataMAXSIZE+1; /非零元三元組表非零元三元組表,data0未用未用int mu,n

25、u,tu; /行數(shù)、列數(shù)、非零元個(gè)數(shù)行數(shù)、列數(shù)、非零元個(gè)數(shù)TSMatrix;TSMatrix a,b;例：例： 15 0 0 0 91 0 11 0 0 0 0 3 0 0 0 22 0 6 0 0 0 0 0 0 0 - -15 0 0 0 0 B=15 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=三元組順序表操作三元組順序表操作轉(zhuǎn)置操作轉(zhuǎn)置操作 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0

26、123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）三元組順序表操作三元組順序表操作轉(zhuǎn)置操作轉(zhuǎn)置操作三元組順序表操作三元組順序表操作轉(zhuǎn)置算法轉(zhuǎn)置算法1n基本思想：基本思想：在在A的三元組順序表中依次找第的三元組順序表中依次找第0列、第列、第1列、

27、列、直到最后一列的三元組，并將直到最后一列的三元組，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B的三元組順序表中。的三元組順序表中。 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（

28、非零元個(gè)數(shù)）三元組順序表操作三元組順序表操作轉(zhuǎn)置算法轉(zhuǎn)置算法1 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）在矩陣在矩陣A中查找第中查找第0列非零元，順序存儲(chǔ)到矩陣列非零元，順序存儲(chǔ)到矩陣B中中 0 0 15

29、 0 4 91 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） 0 0 15 0 4 91 1 1 11在矩陣在矩陣A中查找第中查找第1列非零元，順序存儲(chǔ)到矩陣列非零元，順序存儲(chǔ)到矩陣B中中 0 0 15 0

30、3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3在矩陣在矩陣A中查找第中查找第2列非零元，順序存儲(chǔ)到矩陣列非零元，順序存儲(chǔ)到矩陣B中中 0 0 15 0 3 22 0 5 -

31、-15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6在矩陣在矩陣A中查找第中查找第3列非零元，順序存儲(chǔ)到矩陣列非零元，順序存儲(chǔ)到矩陣B中中 0 0 15 0 3 22 0 5

32、- -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 2 6在矩陣在矩陣A中查找第中查找第4列非零元，順序存儲(chǔ)到矩陣列非零元，順序存儲(chǔ)到矩陣B中中 3 0 22 0 0 15 0 3 22 0

33、5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15在矩陣在矩陣A中查找第中查找第5列非零元，順序存儲(chǔ)到矩陣列非零元，順序存儲(chǔ)到矩陣B中中 0 0 15

34、 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） row col item0123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15在矩陣在矩陣A中查找第中查找第6列非零元，順序存儲(chǔ)到矩陣列非零元，順序存儲(chǔ)到矩陣

35、B中中1. 設(shè)置轉(zhuǎn)置后矩陣設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元個(gè)數(shù)；的行數(shù)、列數(shù)和非零元個(gè)數(shù)；2. 在在B中設(shè)置初始存儲(chǔ)位置中設(shè)置初始存儲(chǔ)位置q；3. for (col=最小列號(hào)最小列號(hào); col=最大列號(hào)最大列號(hào); col+) 3.1 在在A中查找列號(hào)為中查找列號(hào)為col的三元組；的三元組； 3.2 交換其行號(hào)和列號(hào)，存入交換其行號(hào)和列號(hào)，存入B中中q位置；位置； 3.3 q+；三元組順序表操作三元組順序表操作轉(zhuǎn)置算法轉(zhuǎn)置算法1稀疏矩陣的轉(zhuǎn)置稀疏矩陣的轉(zhuǎn)置 (算法算法5.1) Status TransposeSMatrix(TSMatrix M,TSMatrix &T) int q,col,

36、p; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if (T.tu) q=1;for (col=1;col=T.mu;+col)for(p=1;p=M.tu;+p)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; 三元組順序表操作三元組順序表操作轉(zhuǎn)置算法轉(zhuǎn)置算法1n該算法的主要時(shí)間耗費(fèi)是在該算法的主要時(shí)間耗費(fèi)是在col和和p的兩重循環(huán)上。的兩重循環(huán)上。n對(duì)于一個(gè)對(duì)于一個(gè)m行行n列且非零元素個(gè)數(shù)為列且非零元素個(gè)數(shù)為t的稀疏矩陣而的稀疏矩陣而

37、言，該算法的時(shí)間復(fù)雜度為言，該算法的時(shí)間復(fù)雜度為O(t*n)。n例：若矩陣有例：若矩陣有200行，行，200列，列，10,000個(gè)非零元素，個(gè)非零元素，總共有總共有2,000,000次處理。次處理。n最壞情況是，當(dāng)稀疏矩陣中的非零元素個(gè)數(shù)最壞情況是，當(dāng)稀疏矩陣中的非零元素個(gè)數(shù)t與與mn同數(shù)量級(jí)時(shí)，上述算法的時(shí)間復(fù)雜度就為同數(shù)量級(jí)時(shí)，上述算法的時(shí)間復(fù)雜度就為O(mn2)。n顯然這種情況下，該算法效率較低。顯然這種情況下，該算法效率較低。 分析分析：A中第中第0列的第一個(gè)非零元素一定存儲(chǔ)在列的第一個(gè)非零元素一定存儲(chǔ)在B中下中下標(biāo)為標(biāo)為0的位置上，該列中其它非零元素應(yīng)存放在的位置上，該列中其它非零元

38、素應(yīng)存放在B中中后面連續(xù)的位置上，那么第后面連續(xù)的位置上，那么第1列的第一個(gè)非零元素在列的第一個(gè)非零元素在B中的位置便等于第中的位置便等于第0列的第一個(gè)非零元素在列的第一個(gè)非零元素在B中的位中的位置加上第置加上第0列的非零元素的個(gè)數(shù)，以此類推。列的非零元素的個(gè)數(shù)，以此類推。 基本思想：基本思想：順序取，直接存。順序取，直接存。即即在在A中依次取三元中依次取三元組，交換其行號(hào)和列號(hào)放到組，交換其行號(hào)和列號(hào)放到B 中中適當(dāng)適當(dāng)位置。位置。如何確定當(dāng)前從如何確定當(dāng)前從A中取出的三元組在中取出的三元組在B中的位置？中的位置？三元組順序表操作三元組順序表操作轉(zhuǎn)置算法轉(zhuǎn)置算法2 row col item0

39、123456MaxTerm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15第第0列第列第1個(gè)非零元素個(gè)非零元素第第0列有列有2個(gè)非零元素個(gè)非零元素第第1列第列第1個(gè)非零元素個(gè)非零元素三元組順序表操作三元組順序表操作轉(zhuǎn)置算法轉(zhuǎn)置算法2引入兩個(gè)數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：引入兩個(gè)數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：cnumcols：存儲(chǔ)矩陣存儲(chǔ)矩陣A中某列的非零元素的個(gè)數(shù)；中某列的非零元素的個(gè)數(shù)；cpotcols：初值表示矩陣初值表示矩陣A中某列的第一個(gè)非零元中某列的第一個(gè)

40、非零元素在素在B中的位置。中的位置。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：cpot0=0；cpotcol=cpotcol- -1+cnumcol- -1； 1colcols-1cnum與與cpot存在如下遞推關(guān)系：存在如下遞推關(guān)系：三元組順序表操作三元組順序表操作轉(zhuǎn)置算法轉(zhuǎn)置算法2 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)） col 0 1 2 3 4 5 cnu

41、mcol 2 1 1 2 0 1 cpotcol 0 2 3 4 6 6根據(jù)矩陣根據(jù)矩陣A計(jì)算計(jì)算cnum和和cpot 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標(biāo)為中下標(biāo)為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)

42、數(shù)）cpot0cpot1cpot2cpot3cpot4 cpot5 0 0 15cpot0 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標(biāo)為中下標(biāo)為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）cpot1cpot2cp

43、ot3cpot4 cpot5 0 0 15cpot0 3 0 22cpot3 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標(biāo)為中下標(biāo)為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）cpot1cpot2cpot4 0 0

44、 15cpot0 3 0 22cpot3 5 0 -15cpot5cpot5 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標(biāo)為中下標(biāo)為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）cpot1cpot2cpot4 0 0

45、 15cpot0 3 0 22cpot3 5 0 -15cpot5 1 1 11cpot1 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標(biāo)為中下標(biāo)為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）cpot2cpot4 0

46、 0 15cpot0 3 0 22cpot3 5 0 -15cpot5 1 1 11cpot1 2 1 3cpot2cpot1 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標(biāo)為中下標(biāo)為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（

47、非零元個(gè)數(shù)）cpot4 0 0 15cpot0 3 0 22cpot3 5 0 -15cpot5 1 1 11 2 1 3cpot2cpot1 3 2 6cpot3 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）將矩陣將矩陣A中中col列元素存放在列元素存放在B中下標(biāo)為中下標(biāo)為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的

48、列數(shù)）（矩陣的列數(shù)）7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）cpot4 0 0 15cpot0 3 0 22 5 0 -15cpot5 1 1 11 2 1 3cpot2cpot1 3 2 6cpot3 0 4 91cpot01. 設(shè)置轉(zhuǎn)置后矩陣設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)；的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)；2. 計(jì)算計(jì)算A中每一列的非零元素個(gè)數(shù)；中每一列的非零元素個(gè)數(shù)；3. 計(jì)算計(jì)算A中每一列的第一個(gè)非零元素在中每一列的第一個(gè)非零元素在B中的下標(biāo)；中的下標(biāo)；4. 依次取依次取A中的每一個(gè)非零元素對(duì)應(yīng)的三元組；中的每一個(gè)非零元素對(duì)應(yīng)的三元組； 4.1 確定該元素在確定該元素在B中的下標(biāo)中的下

49、標(biāo)q； 4.2 將該元素的行號(hào)列號(hào)交換后存入將該元素的行號(hào)列號(hào)交換后存入B中中q的位置；的位置； 4.3 預(yù)置該元素所在列的下一個(gè)元素的存放位置；預(yù)置該元素所在列的下一個(gè)元素的存放位置；三元組順序表操作三元組順序表操作轉(zhuǎn)置算法轉(zhuǎn)置算法2三元組順序表操作三元組順序表操作轉(zhuǎn)置算法轉(zhuǎn)置算法2n該算法中有該算法中有4個(gè)平行的個(gè)平行的for循環(huán)。循環(huán)。n對(duì)于一個(gè)對(duì)于一個(gè)m行行n列且非零元素個(gè)數(shù)為列且非零元素個(gè)數(shù)為t的稀疏矩的稀疏矩陣而言，循環(huán)次數(shù)分別為陣而言，循環(huán)次數(shù)分別為n和和t兩種，故此算法兩種，故此算法時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n+t)。n顯然該算法優(yōu)于轉(zhuǎn)置算法顯然該算法優(yōu)于轉(zhuǎn)置算法1。 方法二

50、：稀疏矩陣的壓縮存儲(chǔ)方法二：稀疏矩陣的壓縮存儲(chǔ)十字鏈表十字鏈表n當(dāng)矩陣中非零元素的當(dāng)矩陣中非零元素的個(gè)數(shù)個(gè)數(shù)和和位置位置經(jīng)過運(yùn)算后經(jīng)過運(yùn)算后變化變化較大較大時(shí)，就不宜采用順序存儲(chǔ)結(jié)構(gòu)，而應(yīng)采用時(shí)，就不宜采用順序存儲(chǔ)結(jié)構(gòu)，而應(yīng)采用鏈鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)式存儲(chǔ)結(jié)構(gòu)來表示三元組。來表示三元組。n稀疏矩陣的鏈接表示采用十字鏈表：稀疏矩陣的鏈接表示采用十字鏈表：行鏈表行鏈表與與列列鏈表鏈表十字交叉。十字交叉。n行鏈表與列鏈表都是行鏈表與列鏈表都是帶表頭結(jié)點(diǎn)的循環(huán)鏈表帶表頭結(jié)點(diǎn)的循環(huán)鏈表。用。用表頭結(jié)點(diǎn)表征是第幾行，第幾列。表頭結(jié)點(diǎn)表征是第幾行，第幾列。n元素結(jié)點(diǎn)元素結(jié)點(diǎn)qrightright指向同一行中下一指向

51、同一行中下一個(gè)非零元素的指針（向右域）個(gè)非零元素的指針（向右域）qdowndown指向同一列中下一指向同一列中下一個(gè)非零元素的指針（向下域）個(gè)非零元素的指針（向下域）n表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)q 行表頭結(jié)點(diǎn)行表頭結(jié)點(diǎn)q 列表頭結(jié)點(diǎn)列表頭結(jié)點(diǎn)q nextnext用于表示頭結(jié)點(diǎn)的鏈接用于表示頭結(jié)點(diǎn)的鏈接rowcolnextrightdownrowcolvalrightdown稀疏矩陣的十字鏈表表示的示例稀疏矩陣的十字鏈表表示的示例51122334455n需要輔助結(jié)點(diǎn)作鏈表的表頭，同時(shí)每個(gè)結(jié)點(diǎn)要需要輔助結(jié)點(diǎn)作鏈表的表頭，同時(shí)每個(gè)結(jié)點(diǎn)要增加兩個(gè)指針域，所以只有在矩陣較大和較稀增加兩個(gè)指針域，所以只有在矩陣較大

52、和較稀疏時(shí)才能起到節(jié)省空間的效果。疏時(shí)才能起到節(jié)省空間的效果。十字鏈表的類型定義十字鏈表的類型定義typedef struct OLNode /元素結(jié)點(diǎn)元素結(jié)點(diǎn)int i,j; /非零元的行和列下標(biāo)非零元的行和列下標(biāo)ElemType e;struct OLNode *right,*down; /該非零元所在行表和列該非零元所在行表和列 表的后繼鏈域表的后繼鏈域 OLNode, *OLink;typedef struct OLink *rhead,*chead; /行和列鏈表頭指針數(shù)組行和列鏈表頭指針數(shù)組int mu,nu,tu; CrossList; 2 0 2M=3 0 0 50 1 0 0

53、2 0 0 0 0 0 3 0 3 5 1 1 1稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)十字鏈表十字鏈表n一維數(shù)組具有線性表的結(jié)構(gòu)，操作簡(jiǎn)單，一般不進(jìn)一維數(shù)組具有線性表的結(jié)構(gòu)，操作簡(jiǎn)單，一般不進(jìn)行插入和刪除操作，只定義給定下標(biāo)讀取元素和修行插入和刪除操作，只定義給定下標(biāo)讀取元素和修改元素的操作改元素的操作. .n二維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一對(duì)數(shù)組下標(biāo)，在二維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一對(duì)數(shù)組下標(biāo)，在行方向上和列方向上都存在一個(gè)線性關(guān)系，即存在行方向上和列方向上都存在一個(gè)線性關(guān)系，即存在兩個(gè)前驅(qū)和兩個(gè)后繼。也可看作是以線性表為數(shù)據(jù)兩個(gè)前驅(qū)和兩個(gè)后繼。也可看作是以線性表為數(shù)據(jù)元素的線性表。元素的線性

54、表。nn n維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)n n個(gè)下標(biāo)，受個(gè)下標(biāo)，受n n個(gè)個(gè)關(guān)系的制約，其中任一個(gè)關(guān)系都是線性關(guān)系。可關(guān)系的制約，其中任一個(gè)關(guān)系都是線性關(guān)系?？煽醋魇菙?shù)據(jù)元素為看作是數(shù)據(jù)元素為n-1n-1維數(shù)組的一維數(shù)組。維數(shù)組的一維數(shù)組。n因此，多維數(shù)組和廣義表是對(duì)線性表的擴(kuò)展：線因此，多維數(shù)組和廣義表是對(duì)線性表的擴(kuò)展：線性表中的數(shù)據(jù)元素本身又是一個(gè)多層次的線性表。性表中的數(shù)據(jù)元素本身又是一個(gè)多層次的線性表。5.4 廣義表的類型定義廣義表的類型定義ADT Glist 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D ei | i=1,2,.,n; n0; eiAtomSet 或或 eiGLis

55、t, AtomSet為某個(gè)數(shù)據(jù)對(duì)象為某個(gè)數(shù)據(jù)對(duì)象 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： LR| ei-1 ,eiD, 2in ADT Glist基本操作基本操作:廣義表是廣義表是遞歸遞歸定義的定義的線性結(jié)構(gòu)線性結(jié)構(gòu) LS = ( 1, 2, , n )其中：其中：i 或?yàn)樵踊驗(yàn)樵?或?yàn)閺V義表或?yàn)閺V義表例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) ) /遞歸表遞歸表廣義表是一個(gè)廣義表是一個(gè)多層次多層次的的線性結(jié)構(gòu)線性結(jié)構(gòu)例如：例如：D=(E, F)其中其中: : E=(a, (b

56、, c) F=(d, (e)DEFa( )d( )bce廣義表廣義表 LS = ( 1, 2, , n )的結(jié)構(gòu)特點(diǎn)的結(jié)構(gòu)特點(diǎn):1) 廣義表中的數(shù)據(jù)元素有相對(duì)廣義表中的數(shù)據(jù)元素有相對(duì)次序次序;2) 廣義表的廣義表的長(zhǎng)度長(zhǎng)度定義為最外層包含元素個(gè)數(shù)定義為最外層包含元素個(gè)數(shù);3) 廣義表的廣義表的深度深度定義為所含括弧的重?cái)?shù)定義為所含括弧的重?cái)?shù); 注意注意:“原子原子”的深度為的深度為 0 ; “空表空表”的深度為的深度為 1 。4) 廣義表可以廣義表可以共享共享; 廣義表可以是一個(gè)廣義表可以是一個(gè)遞歸遞歸的表的表 遞歸表的深度是無窮值，長(zhǎng)度是有限值。遞歸表的深度是無窮值，長(zhǎng)度是有限值。6) 任何一個(gè)非空廣義表任何一個(gè)非空廣義表 LS = (1, 2, , n) 均可分解為均可分解為 表頭表頭 Head(LS) = 1 和和 表尾表尾 Tail(LS) = (2, , n) 兩部分兩部分例如例如: D = (E, F) = (a, (b, c)，F(xiàn) )Head(D) = E Tail(D) = (F)Head(E) = a Tail(E) = (b, c)Head(b, c) = (b, c) Tail(b, c) = ( )Head(b, c) = b Tail(b, c) = (c)Head(c) = c Tail(c) = ( ) 結(jié)構(gòu)的創(chuàng)建和銷毀結(jié)構(gòu)的創(chuàng)建和銷毀