第4章 廣義線性表

1、第四章第四章 廣義線性表廣義線性表本章的基本內(nèi)容是：本章的基本內(nèi)容是：數(shù)組的邏輯結(jié)構(gòu)特征數(shù)組的邏輯結(jié)構(gòu)特征數(shù)組的存儲方式及尋址方法數(shù)組的存儲方式及尋址方法特殊矩陣和稀疏矩陣的壓縮存儲方法特殊矩陣和稀疏矩陣的壓縮存儲方法廣義表的基本概念和存儲結(jié)構(gòu)廣義表的基本概念和存儲結(jié)構(gòu)第四章第四章 廣義線性表廣義線性表線性表線性表具有相同類型的數(shù)據(jù)元素的有限序列。具有相同類型的數(shù)據(jù)元素的有限序列。限制插入、刪除位置限制插入、刪除位置線性表線性表具有相同類型的數(shù)據(jù)元素的有限序列。具有相同類型的數(shù)據(jù)元素的有限序列。限制元素類型為字符限制元素類型為字符棧棧僅在表尾進行插入和刪除操作的線性表。僅在表尾進行插入和刪除操

2、作的線性表。隊列隊列在一端進行插入操作，而另一端進行在一端進行插入操作，而另一端進行刪除操作的線性表。刪除操作的線性表。串串零個或多個字符組成的有限序列零個或多個字符組成的有限序列 。特殊線性表特殊線性表第四章第四章 廣義線性表廣義線性表線性表線性表具有相同類型的數(shù)據(jù)元素的有限序列。具有相同類型的數(shù)據(jù)元素的有限序列。將元素的類型進行擴充將元素的類型進行擴充廣義線性表廣義線性表（多維）數(shù)組（多維）數(shù)組線性表中的數(shù)據(jù)元素可以是線性表中的數(shù)據(jù)元素可以是線性表，但所有元素的類型相同。線性表，但所有元素的類型相同。廣義表廣義表線性表中的數(shù)據(jù)元素可以是線性表，線性表中的數(shù)據(jù)元素可以是線性表，且元素的類型可

3、以不相同。且元素的類型可以不相同。數(shù)組的定義數(shù)組的定義數(shù)組是由一組數(shù)組是由一組類型相同類型相同的數(shù)據(jù)元素構(gòu)成的的數(shù)據(jù)元素構(gòu)成的有序有序集集合合，每個數(shù)據(jù)元素稱為一個數(shù)組元素（簡稱為元每個數(shù)據(jù)元素稱為一個數(shù)組元素（簡稱為元素），每個元素受素），每個元素受n(n1)個個線性關(guān)系線性關(guān)系的約束，的約束，每每個元素在個元素在n個線性關(guān)系中的序號個線性關(guān)系中的序號i1、i2、in稱為稱為該元素的下標，并稱該數(shù)組為該元素的下標，并稱該數(shù)組為 n 維數(shù)組。維數(shù)組。 數(shù)組的特點數(shù)組的特點元素本身可以具有某種結(jié)構(gòu)，屬于同一數(shù)據(jù)類型；元素本身可以具有某種結(jié)構(gòu)，屬于同一數(shù)據(jù)類型；數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集

4、合。數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合。廣義線性表廣義線性表多維數(shù)組多維數(shù)組廣義線性表廣義線性表多維數(shù)組多維數(shù)組 a11 a12 a1n a21 a22 a2n am1 am2 amna=例如，元素例如，元素a22受兩個線性關(guān)系的約束，在行上有受兩個線性關(guān)系的約束，在行上有一個行前驅(qū)一個行前驅(qū)a21和一個行后繼和一個行后繼a23，在列上有一個列，在列上有一個列前驅(qū)前驅(qū)a12和和一個列后繼和和一個列后繼a32。數(shù)組示例數(shù)組示例 a11 a12 a1n a21 a22 a2n am1 am2 amna= a=(a1，a2，an) 其中：其中： ai=(a1i，a2i，ami) (1in)數(shù)組數(shù)

5、組線性表的推廣線性表的推廣二維數(shù)組是數(shù)據(jù)元素為線性表的線性表。二維數(shù)組是數(shù)據(jù)元素為線性表的線性表。廣義線性表廣義線性表多維數(shù)組多維數(shù)組數(shù)組的基本操作數(shù)組的基本操作廣義線性表廣義線性表多維數(shù)組多維數(shù)組在數(shù)組中插入（或刪除）一個元素有意義嗎？在數(shù)組中插入（或刪除）一個元素有意義嗎？ a11 a12 a1n a21 a22 a2n am1 am2 amna=將元素將元素 x 插入插入到數(shù)組中第到數(shù)組中第1行第行第2列。列。x a11 a12 a1n a21 a22 a2n am1 am2 amna=刪除數(shù)組中刪除數(shù)組中第第1行第行第2列元素。列元素。數(shù)組的基本操作數(shù)組的基本操作 存?。航o定一組下標，

6、讀出對應(yīng)的數(shù)組元素；存?。航o定一組下標，讀出對應(yīng)的數(shù)組元素； 修改：給定一組下標，存儲或修改與其相對應(yīng)的修改：給定一組下標，存儲或修改與其相對應(yīng)的數(shù)組元素。數(shù)組元素。存取和修改操作本質(zhì)上只對應(yīng)一種操作存取和修改操作本質(zhì)上只對應(yīng)一種操作尋址尋址數(shù)組應(yīng)該采用何種方式存儲？數(shù)組應(yīng)該采用何種方式存儲？數(shù)組沒有插入和刪除操作，所以，不用預(yù)留空間，數(shù)組沒有插入和刪除操作，所以，不用預(yù)留空間，適合采用順序存儲。適合采用順序存儲。廣義線性表廣義線性表多維數(shù)組多維數(shù)組數(shù)組的存儲結(jié)構(gòu)與尋址數(shù)組的存儲結(jié)構(gòu)與尋址一維數(shù)組一維數(shù)組設(shè)一維數(shù)組的下標的范圍為閉區(qū)間設(shè)一維數(shù)組的下標的范圍為閉區(qū)間l，h，每個每個數(shù)組元素占用數(shù)

7、組元素占用 c 個存儲單元，則個存儲單元，則其其任一元任一元素素 ai 的的存儲地址可由下式確定：存儲地址可由下式確定： loc(ai)loc(al)(il)c 廣義線性表廣義線性表多維數(shù)組多維數(shù)組c al ai-l ai ah al+1 loc(al)loc(ai)常用的映射方法有兩種：常用的映射方法有兩種：按按行行優(yōu)先：優(yōu)先：先行后列先行后列，先存儲行號較小的元素，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。行號相同者先存儲列號較小的元素。 按按列列優(yōu)先：優(yōu)先：先列后行先列后行，先存儲列號較小的元素，先存儲列號較小的元素，列號相同者先存儲行號較小的元素。列號相同者先存儲行號較小的

8、元素。 廣義線性表廣義線性表多維數(shù)組多維數(shù)組數(shù)組的存儲結(jié)構(gòu)與尋址數(shù)組的存儲結(jié)構(gòu)與尋址二維數(shù)組二維數(shù)組二維數(shù)組二維數(shù)組內(nèi)內(nèi) 存存二維結(jié)構(gòu)二維結(jié)構(gòu)一維結(jié)構(gòu)一維結(jié)構(gòu)廣義線性表廣義線性表多維數(shù)組多維數(shù)組l2h2 l1h1(a) 二維數(shù)組二維數(shù)組aij前面的元素個數(shù)前面的元素個數(shù)=陰影部分的面積陰影部分的面積=整行數(shù)每行元素個數(shù)整行數(shù)每行元素個數(shù)+本行中本行中aij前面的元素個數(shù)前面的元素個數(shù)=( (i - -l1) )( (h2 - -l21) )( (j - -l2) )本行中本行中aij前面的元素個數(shù)前面的元素個數(shù)每行元素個數(shù)每行元素個數(shù)整整行行數(shù)數(shù)aij按行優(yōu)先存儲的尋址按行優(yōu)先存儲的尋址廣義線

9、性表廣義線性表多維數(shù)組多維數(shù)組第第l1行行第第l1+1行行al1l2 al1h2 a(l1+1)l2 a(l1+1)h2 aij ah1h2loc( (aij) )loc( (al1l2) )( (i - -l1) )( (h2 - -l21) )( (j - -l2) )個元素個元素loc(aij)loc(al1l2)(il1)(h2l21)(jl2)c按行優(yōu)先存儲的尋址按行優(yōu)先存儲的尋址按列優(yōu)先存儲的尋址方法與此類似。按列優(yōu)先存儲的尋址方法與此類似。loc(aijk ) = loc(a000) +( im2m3 + jm3 + k )c 廣義線性表廣義線性表多維數(shù)組多維數(shù)組 n（n2）維維

10、數(shù)組一般也采用數(shù)組一般也采用按行優(yōu)先和按列按行優(yōu)先和按列優(yōu)先兩種存儲方優(yōu)先兩種存儲方法。法。請自行推導(dǎo)請自行推導(dǎo)任一元素存儲地任一元素存儲地址的計算方法。址的計算方法。數(shù)組的存儲結(jié)構(gòu)與尋址數(shù)組的存儲結(jié)構(gòu)與尋址多維數(shù)組多維數(shù)組矩陣的壓縮存儲矩陣的壓縮存儲特殊矩陣：特殊矩陣：矩陣中很多值相同的元素并且它們的分布矩陣中很多值相同的元素并且它們的分布有一定的規(guī)律。有一定的規(guī)律。稀疏矩陣：稀疏矩陣：矩陣中有很多零元素。矩陣中有很多零元素。壓縮存儲的基本思想是：壓縮存儲的基本思想是： 為多個值為多個值相同相同的元素只分配的元素只分配一個一個存儲空間；存儲空間； 對對零零元素元素不分配不分配存儲空間。存儲空

11、間。 特殊矩陣和稀疏矩陣特殊矩陣和稀疏矩陣特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對稱矩陣對稱矩陣 3647862842481697460582957a對稱矩陣特點：對稱矩陣特點：aij=aji如何壓縮存儲？如何壓縮存儲？只存儲下三角部分的元素。只存儲下三角部分的元素。矩陣的壓縮存儲矩陣的壓縮存儲(a) 下三角矩陣下三角矩陣 (b) 存儲說明存儲說明 (c) 計算方法計算方法aij在一維數(shù)組中的序號在一維數(shù)組中的序號=陰影部分的面積陰影部分的面積= i( (i+1) )/2+ j+1一維數(shù)組下標從一維數(shù)組下標從0開始開始aij在一維數(shù)組中的下標在一維數(shù)組中的下標k= i( (i+1) )/2+ j

12、 0 in- -10 j n- -1 aij每行元素個數(shù)每行元素個數(shù)12iaij在本行中的序號在本行中的序號aij第第0行行第第1行行第第i-1行行對稱矩陣的壓縮存儲對稱矩陣的壓縮存儲 矩陣的壓縮存儲矩陣的壓縮存儲對于下三角中的元素對于下三角中的元素aij（ij），在數(shù)組，在數(shù)組sa中的下標中的下標k與與i、j的關(guān)系為：的關(guān)系為：ki(i1)/2j 。上三角中的元素上三角中的元素aij（ij），），因為因為aijaji，則訪問和則訪問和它對應(yīng)的元素它對應(yīng)的元素aji即可，即：即可，即：kj(j1)/2i 。對稱矩陣的壓縮存儲對稱矩陣的壓縮存儲 第第1行行第第n-1行行第第0行行 a00 a10

13、 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-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)上三角矩陣上三角矩陣如何壓縮存儲？如何壓縮存儲？只存儲上三角（或下三角）部分的元素。只存儲上三角（或下三角）部分的元素。矩陣的壓縮存儲矩陣的壓縮存儲矩陣中任一元素矩陣中任一元素aij在在

14、數(shù)組數(shù)組中的下標中的下標k與與i、j的對應(yīng)關(guān)系：的對應(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矩陣的壓縮存儲矩陣的壓縮存儲存儲存儲下三角下三角元素元素對角線上方的常數(shù)對角線上方的常數(shù)只存一個只存一個矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標中的下標k與與i、j的對應(yīng)關(guān)系：的對應(yīng)關(guān)系： i( (2ni1) )/2ji 當(dāng)當(dāng)ijn( (n1) ) /2 當(dāng)當(dāng)ij

15、k=上三角矩陣的壓縮存儲上三角矩陣的壓縮存儲矩陣的壓縮存儲矩陣的壓縮存儲存儲存儲上三角上三角元素元素對角線上方的常數(shù)對角線上方的常數(shù)只存一個只存一個特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對角矩陣對角矩陣 對角矩陣：對角矩陣：所有非零元素都集中在以主對角線為中心所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，除了主的帶狀區(qū)域中，除了主對角線和它的上下方若干條對對角線和它的上下方若干條對角線的元素外，所有其他元素都為零。角線的元素外，所有其他元素都為零。 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44a=矩

16、陣的壓縮存儲矩陣的壓縮存儲a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44a=將帶狀區(qū)將帶狀區(qū)域立起來域立起來0 a00a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a44 0b=sj- -i+1t=i映射到二維數(shù)組映射到二維數(shù)組b中，映射關(guān)系中，映射關(guān)系對角矩陣的壓縮存儲對角矩陣的壓縮存儲矩陣的壓縮存儲矩陣的壓縮存儲按行按行存儲存儲 元素元素aij在一維數(shù)組中的序號在一維數(shù)組中的序號=2 + 3( (i1) )+( ( ji + 2) )=2i+ j+1 一維數(shù)組下標從

17、一維數(shù)組下標從0開始開始元素元素aij在一維數(shù)組中的下標在一維數(shù)組中的下標=2i+ j(b) 尋址的計算方法尋址的計算方法(c) 壓縮到一維數(shù)組中壓縮到一維數(shù)組中a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a440 1 2 3 4 5 6 7 8 9 10 11 12矩陣的壓縮存儲矩陣的壓縮存儲對角矩陣的壓縮存儲對角矩陣的壓縮存儲(a) 三對角矩陣三對角矩陣 0 0 0 0 00 00 0 0 0 0 a=a00 a01a10 a11 a12a21 a22 a23a32 a33 a34a43 a44稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 15

18、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=如何只存儲非零元素？如何只存儲非零元素？矩陣的壓縮存儲矩陣的壓縮存儲注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。template struct element int row, col; /行號，列號行號，列號 t item /非零元素值非零元素值;將稀疏矩陣中的每個非零元素表示為將稀疏矩陣中的每個非零元素表示為：( (行號，列號，非零元素值行號，列號，非零元素值) )三元組三元組矩陣的壓縮存儲矩陣的壓縮存儲稀疏矩陣的壓縮存儲稀疏矩陣的

19、壓縮存儲 定義三元組定義三元組：三元組表三元組表：將稀疏矩陣的非零元素對應(yīng)的三元組所將稀疏矩陣的非零元素對應(yīng)的三元組所構(gòu)成的集合，構(gòu)成的集合，按行優(yōu)先的順序排列成一個線性表。按行優(yōu)先的順序排列成一個線性表。矩陣的壓縮存儲矩陣的壓縮存儲稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 三元組表三元組表( (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=如何存儲三元組表？如何存儲三元組表？稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲三元組順序表三元組順序表采用順序存

20、儲結(jié)構(gòu)存儲三元組表采用順序存儲結(jié)構(gòu)存儲三元組表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=矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表是否三元組順序表是否需要預(yù)留存儲空間？需要預(yù)留存儲空間？稀疏矩陣的修改操作稀疏矩陣的修改操作三元組順序表的插入三元組順序表的插入/ /刪除操作刪除操作稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲三元組順序表三元組順序表采用順序存儲結(jié)構(gòu)存儲三元組表采用順序存儲結(jié)構(gòu)存儲三元組表 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空

21、空 空空 閑閑 閑閑 閑閑row col item0123456maxterm- -1矩陣的壓縮存儲矩陣的壓縮存儲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=7（非零元個數(shù)）（非零元個數(shù)）是否對應(yīng)惟一的稀疏矩陣？是否對應(yīng)惟一的稀疏矩陣？5（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）存儲結(jié)構(gòu)定義：存儲結(jié)構(gòu)定義： const int maxterm=100; template struct sparsematrix t datamaxterm; /存儲非零元素存儲非零元素 int mu, n

22、u, tu; /行數(shù)，列數(shù)，非零元個數(shù)行數(shù)，列數(shù)，非零元個數(shù) ;矩陣的壓縮存儲矩陣的壓縮存儲稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲三元組順序表三元組順序表三元組順序表操作三元組順序表操作轉(zhuǎn)置操作轉(zhuǎn)置操作例：例： 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=矩陣的壓縮存儲矩陣的壓縮存儲矩陣的壓縮存儲矩陣的壓縮存儲 0 0 15 0 3 22 0 5 - -15 1 1

23、 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456maxterm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(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（非零元個數(shù)）（非零元個數(shù)）三元組順序表轉(zhuǎn)置算法三元組順序表轉(zhuǎn)置算法算法算法 基本思想：基本思想：直接取，順序存直接

24、取，順序存。即。即在在a的三元組順序的三元組順序表中表中依次依次找第找第0列、第列、第1列、列、直到最后一列的三元直到最后一列的三元組，并將找到的每個三元組的行、列交換后組，并將找到的每個三元組的行、列交換后順序順序存存儲到儲到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（非零元個數(shù)）（非

25、零元個數(shù)） row col item0123456maxterm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）設(shè)置矩陣設(shè)置矩陣b的行數(shù)、列數(shù)、非零元個數(shù)的行數(shù)、列數(shù)、非零元個數(shù)矩陣的壓縮存儲矩陣的壓縮存儲 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（非零元個數(shù)）（非零元個數(shù)） row col item0123456maxterm-

26、-16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣a中查找第中查找第0列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣b中中 0 0 15 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（非零元個數(shù)）（非零元個數(shù)） row col item0123456maxterm- -16（矩陣的行數(shù)）

27、（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣a中查找第中查找第1列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣b中中 0 0 15 0 4 91 1 1 11矩陣的壓縮存儲矩陣的壓縮存儲 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（非零元個數(shù)）（非零元個數(shù)） row col item0123456maxterm- -16（矩陣的行數(shù)）（矩陣

28、的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣a中查找第中查找第2列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣b中中 0 0 15 0 4 91 1 1 11 2 1 3矩陣的壓縮存儲矩陣的壓縮存儲 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（非零元個數(shù)）（非零元個數(shù)） row col item0123456maxterm- -16（矩陣的行數(shù)）

29、（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣a中查找第中查找第3列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣b中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6矩陣的壓縮存儲矩陣的壓縮存儲 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（非零元個數(shù)）（非零元個數(shù)） row col item0123456max

30、term- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣a中查找第中查找第4列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣b中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6矩陣的壓縮存儲矩陣的壓縮存儲 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（非零元個數(shù)）（非零元個數(shù)） row co

31、l item0123456maxterm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣a中查找第中查找第5列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣b中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15矩陣的壓縮存儲矩陣的壓縮存儲 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ù)）（矩陣的列

32、數(shù)）7（非零元個數(shù)）（非零元個數(shù)） row col item0123456maxterm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）在矩陣在矩陣a中查找第中查找第6列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣b中中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -151. 設(shè)置轉(zhuǎn)置后矩陣設(shè)置轉(zhuǎn)置后矩陣b的行數(shù)、列數(shù)和非零元個數(shù)；的行數(shù)、列數(shù)和非零元個數(shù)；2. 在在b中設(shè)置初始存儲位置中設(shè)置初始存儲位置pb；3. for (col=最小列號最小列號; col=最大列號最大列號; col+) 3.1

33、 在在a中查找列號為中查找列號為col的三元組；的三元組； 3.2 交換其行號和列號，存入交換其行號和列號，存入b中中pb位置；位置； 3.3 pb+；矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表轉(zhuǎn)置算法三元組順序表轉(zhuǎn)置算法偽代碼偽代碼分析分析：a中第中第0列的第一個非零元素一定存儲在列的第一個非零元素一定存儲在b中下中下標為標為0的位置上，該列中其它非零元素應(yīng)存放在的位置上，該列中其它非零元素應(yīng)存放在b中中后面連續(xù)的位置上，那么第后面連續(xù)的位置上，那么第1列的第一個非零元素在列的第一個非零元素在b中的位置便等于第中的位置便等于第0列的第一個非零元素在列的第一個非零元素在b中的位中的位置加上第置加

34、上第0列的非零元素的個數(shù)，以此類推。列的非零元素的個數(shù)，以此類推。 基本思想：基本思想：順序取，直接存。順序取，直接存。即即在在a中依次取三元中依次取三元組，交換其行號和列號放到組，交換其行號和列號放到b 中中適當(dāng)適當(dāng)位置。位置。矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表轉(zhuǎn)置算法三元組順序表轉(zhuǎn)置算法算法算法如何確定當(dāng)前從如何確定當(dāng)前從a中取出的三元組在中取出的三元組在b中的位置？中的位置？矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表轉(zhuǎn)置算法三元組順序表轉(zhuǎn)置算法算法算法 row col item0123456maxterm- -16（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個

35、數(shù)）（非零元個數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 -15第第0列第列第1個非零元素個非零元素第第0列有列有2個非零元素個非零元素第第1列第列第1個非零元素個非零元素引入兩個數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：引入兩個數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：numnu：存儲矩陣存儲矩陣a中某列的非零元素的個數(shù)；中某列的非零元素的個數(shù)；cpotnu：初值表示矩陣初值表示矩陣a中某列的第一個非零元素中某列的第一個非零元素在在b中的位置。中的位置。 數(shù)據(jù)結(jié)構(gòu)設(shè)計：數(shù)據(jù)結(jié)構(gòu)設(shè)計：cpot0=0；cpotcol=cpotcol- -1+numcol- -1； 1colnunum與

36、與cpot存在如下遞推關(guān)系：存在如下遞推關(guān)系：矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表轉(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 item0123456maxterm- -15（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲 col 0 1 2 3 4 5 numcol 2 1 1 2 0 1 cpotcol 0 2 3 4 6 6根據(jù)矩陣根據(jù)矩陣a計算計算num和和cpot 0 0

37、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（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣a中中col列元素存放在列元素存放在b中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot0cpot1cpot2cpot3cpot4 cpot5 0 0 15cpot0 0 0

38、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（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣a中中col列元素存放在列元素存放在b中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot1cpot2cpot3cpot4 cpot5 0 0 15cpot0 3 0 22cpo

39、t3 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（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣a中中col列元素存放在列元素存放在b中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot1cpot2cpot4 0 0 15cpot0 3 0 22cpot3 5

40、 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（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣a中中col列元素存放在列元素存放在b中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot1cpot2cpot4 0 0 15cpot0

41、 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（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣a中中col列元素存放在列元素存放在b中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(shù)）cpot2c

42、pot4 0 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（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣a中中col列元素存放在列元素存放在b中下標為中下標為cpotcol的位置的位置 row col item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣

43、的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(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（非零元個數(shù)）（非零元個數(shù)）矩陣的壓縮存儲矩陣的壓縮存儲將矩陣將矩陣a中中col列元素存放在列元素存放在b中下標為中下標為cpotcol的位置的位置 row c

44、ol item01234566（矩陣的行數(shù)）（矩陣的行數(shù)）5（矩陣的列數(shù)）（矩陣的列數(shù)）7（非零元個數(shù)）（非零元個數(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ù)和非零元素的個數(shù)；的行數(shù)、列數(shù)和非零元素的個數(shù)；2. 計算計算a中每一列的非零元素個數(shù)；中每一列的非零元素個數(shù)；3. 計算計算a中每一列的第一個非零元素在中每一列的第一個非零元素在b中的下標；中的下標；4. 依次取依次取a中的每一個非零元素對應(yīng)的三元組；中的每一個非零

45、元素對應(yīng)的三元組； 4.1 確定該元素在確定該元素在b中的下標中的下標pb； 4.2 將該元素的行號列號交換后存入將該元素的行號列號交換后存入b中中pb的位置；的位置； 4.3 預(yù)置該元素所在列的下一個元素的存放位置；預(yù)置該元素所在列的下一個元素的存放位置；矩陣的壓縮存儲矩陣的壓縮存儲三元組順序表轉(zhuǎn)置算法三元組順序表轉(zhuǎn)置算法偽代碼偽代碼采用采用鏈接鏈接存儲結(jié)構(gòu)存儲三元組表，每個非零元素對應(yīng)存儲結(jié)構(gòu)存儲三元組表，每個非零元素對應(yīng)的三元組存儲為一個鏈表結(jié)點，結(jié)構(gòu)為：的三元組存儲為一個鏈表結(jié)點，結(jié)構(gòu)為： rowcolitemdownrightrow：存儲非零元素的行號存儲非零元素的行號col：存儲非

46、零元素的列號存儲非零元素的列號item：存儲非零元素的值存儲非零元素的值right：指針域，指向同一行中的下一個三元組指針域，指向同一行中的下一個三元組down：指針域，指向同一列中的下一個三元組指針域，指向同一列中的下一個三元組矩陣的壓縮存儲矩陣的壓縮存儲稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲十字鏈表十字鏈表 2 0 2m=3 0 0 50 1 0 02 0 0 0矩陣的壓縮存儲矩陣的壓縮存儲 0 0 3 0 3 5 1 1 1稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲十字鏈表十字鏈表廣義表：廣義表：n（n0）個數(shù)據(jù)元素的有限序列，記作：個數(shù)據(jù)元素的有限序列，記作： ls(a1，a2，an)其中：其

47、中：ls是廣義表的名稱，是廣義表的名稱，ai（1in）是是ls的成員的成員（或直接元素），它可以是單個的數(shù)據(jù)元素，也可以（或直接元素），它可以是單個的數(shù)據(jù)元素，也可以是一個廣義表，分別稱為是一個廣義表，分別稱為ls的單元素（或原子）和子的單元素（或原子）和子表。表。 廣義線性表廣義線性表廣義表廣義表廣義表的邏輯結(jié)構(gòu)：直接元素之間是線性關(guān)系。廣義表的邏輯結(jié)構(gòu)：直接元素之間是線性關(guān)系。廣義表的基本概念廣義表的基本概念通常用大寫字母表示廣義表，用小寫字母表示單元素。通常用大寫字母表示廣義表，用小寫字母表示單元素。 長度：長度：廣義表廣義表ls中的直接元素的個數(shù)；中的直接元素的個數(shù)；深度：深度：廣義表

48、廣義表ls中括號的最大嵌套層數(shù)。中括號的最大嵌套層數(shù)。表頭：表頭：廣義表廣義表ls非空時，稱第一個元素為非空時，稱第一個元素為ls的表頭；的表頭；表尾：表尾：廣義表廣義表ls中除表頭外其余元素組成的廣義表。中除表頭外其余元素組成的廣義表。廣義線性表廣義線性表廣義表廣義表廣義表廣義表( )( )和廣義表和廣義表( )( )不同？不同？ 廣義表的基本概念廣義表的基本概念a ( )b (e)c (a, (b，c，d)d (a, b, c) e (a, e)f ( )廣義線性表廣義線性表廣義表廣義表廣義表的示例廣義表的示例長度？深度？表頭？表尾？長度？深度？表頭？表尾？a ( )b (e)c (a,

49、(b，c，d)d (a, b, c) e (a, e)f ( )廣義線性表廣義線性表廣義表廣義表廣義表的圖形表示廣義表的圖形表示abecabcdd廣義線性表廣義線性表廣義表廣義表廣義表可以采用順序存儲結(jié)構(gòu)嗎？廣義表可以采用順序存儲結(jié)構(gòu)嗎？由于廣義表中的數(shù)據(jù)元素的類型不統(tǒng)一，因此難以由于廣義表中的數(shù)據(jù)元素的類型不統(tǒng)一，因此難以采用順序存儲結(jié)構(gòu)來存儲。采用順序存儲結(jié)構(gòu)來存儲。 若廣義表不空，則可分解為表頭和表尾；反之，一若廣義表不空，則可分解為表頭和表尾；反之，一對確定的表頭和表尾可唯一地確定一個廣義表。對確定的表頭和表尾可唯一地確定一個廣義表。 采用頭尾表示法存儲廣義表采用頭尾表示法存儲廣義表 如何采用鏈接