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

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

3、。44.1 多維數組多維數組多維數組的知識點組織結構圖多維數組的知識點組織結構圖多維數組的邏輯結構多維數組的邏輯結構數組的定義數組的定義數組的數組的ADT定義定義數組的存儲結構數組的存儲結構順序存儲順序存儲行優先行優先列優先列優先壓縮存儲壓縮存儲特殊矩陣特殊矩陣稀疏矩陣稀疏矩陣5數組的定義數組的定義數組是由一組數組是由一組類型相同類型相同的數據元素構成的的數據元素構成的有序有序集集合，每個數據元素稱為一個數組元素（簡稱為元合，每個數據元素稱為一個數組元素（簡稱為元素），每個元素受素），每個元素受n n( (n n1)1)個個線性關系線性關系的約束，每的約束，每個元素在個元素在n n個線性關系中

4、的序號個線性關系中的序號i i1 1、i i2 2、i in n稱稱為該元素的下標，并稱該數組為為該元素的下標，并稱該數組為 n n 維數組。維數組。 數組的特點數組的特點元素本身可以具有某種結構，屬于同一數據類型；元素本身可以具有某種結構，屬于同一數據類型；數組是一個具有固定格式和數量的數據集合。數組是一個具有固定格式和數量的數據集合。6 a11 a12 a1n a21 a22 a2n am1 am2 amnA=例如，元素例如，元素a a2222受兩個線性關系的約束，在行上有受兩個線性關系的約束，在行上有一個行前驅一個行前驅a a2121和一個行后繼和一個行后繼a a2323，在列上有一個列

5、，在列上有一個列前驅前驅a a1212和和一個列后繼和和一個列后繼a a3232。數組示例數組示例7 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=(A1，A2，An) 其中：其中： Ai=(a1i，a2i，ami) (1in)數組數組線性表的推廣線性表的推廣二維數組是數據元素為線性表的線性表。二維數組是數據元素為線性表的線性表。8數組的基本操作數組的基本操作在數組中插入（或）一個元素有意義嗎？在數組中插入（或）一個元素有意義嗎？ a11 a12 a1n a21 a22 a2n am1 am2 amnA=將元素將元素 x x 插入插入到數組中第到數組中第1 1

6、行第行第2 2列。列。x a11 a12 a1n a21 a22 a2n am1 am2 amnA=刪除數組中刪除數組中第第1 1行第行第2 2列元素。列元素。9數組的基本操作數組的基本操作 存取（讀）：給定一組下標，讀出對應的數組存取（讀）：給定一組下標，讀出對應的數組元素；元素； 修改（寫）：給定一組下標，存儲或修改與其修改（寫）：給定一組下標，存儲或修改與其相對應的數組元素。相對應的數組元素。存取和修改操作本質上只對應一種操作存取和修改操作本質上只對應一種操作尋址尋址數組應該采用何種方式存儲？數組應該采用何種方式存儲？適合采用順序存儲。適合采用順序存儲。數組的數組的ADTADT定義（教材

7、定義（教材P116)P116)10數組的存儲結構與尋址數組的存儲結構與尋址一維數組一維數組設一維數組的設一維數組的下標的范圍下標的范圍為閉區間為閉區間l l，h h，每個，每個數組元素占用數組元素占用 c c 個存儲單元，則其個存儲單元，則其任一元任一元素素 a ai i 的的存儲地址可由下式確定：存儲地址可由下式確定： Loc(ai)Loc(al)(il)c c al ai-1 ai ah al+1 Loc(al)Loc(ai)11常用的映射方法有兩種：常用的映射方法有兩種：按按行行優先：優先：先行后列先行后列，先存儲行號較小的元素，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。行號

8、相同者先存儲列號較小的元素。 按按列列優先：優先：先列后行先列后行，先存儲列號較小的元素，先存儲列號較小的元素，列號相同者先存儲行號較小的元素。列號相同者先存儲行號較小的元素。 二維數組二維數組內內 存存二維結構二維結構一維結構一維結構數組的存儲結構與尋址數組的存儲結構與尋址二維數組二維數組12l2h2 l1h1(a) (a) 二維數組二維數組aij前面的元素個數前面的元素個數= =整行數整行數每行元素個數每行元素個數+ +本行中本行中aij前面的元素個數前面的元素個數=( (i - -l1) )( (h2 - -l21) )( (j - -l2) )本行中本行中a aijij前面的元素個數前

9、面的元素個數每行元素個數每行元素個數整整行行數數aij按行優先存儲的尋址按行優先存儲的尋址13按行優先存儲的尋址按行優先存儲的尋址第第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按列優先存儲的尋址方法與此類似。按列優先存儲的尋址方法與此類似。a(0,0)a(0,1)a(0,3)a(1,0)a(1,1)a(1,3)a(3

10、,2)a(6,0)a(6,3) 012 3例例1 1：如何求出：如何求出的存儲地址？的存儲地址？要事先確定：要事先確定：是行優先方式還是列優先方式？是行優先方式還是列優先方式？數組的首地址是多少？數組的首地址是多少？每個元素的長度？每個元素的長度？否則無法否則無法求出結果求出結果15111101121202111101101000mnananamaaamaaamaaaa設數組開始存放位置設數組開始存放位置 LOC( 0, 0 ) = a, 每個元素占用每個元素占用 l 個存儲單元個存儲單元 則則aij的存儲地址：的存儲地址： LOC ( i, j ) = a + ( j *n +i ) * l

11、按列優先存儲的尋址按列優先存儲的尋址例例2：例例3 3：一個二維數組：一個二維數組A A，行下標的范圍是，行下標的范圍是1 1到到6 6，列下標的，列下標的范圍是范圍是0 0到到7 7，每個數組元素用相鄰的，每個數組元素用相鄰的6 6個字節存儲，存個字節存儲，存儲器按字節編址。那么，這個數組的體積是儲器按字節編址。那么，這個數組的體積是 個字節。個字節。 288288答：答： Volume=mVolume=m* *n n* *L=(6-1L=(6-1+1+1) )* *(7- 0 (7- 0 +1+1) )* *6=486=48* *6=2886=288例例4 4：已知二維數組：已知二維數組A

12、 Am,mm,m按行存儲的元素地址公式是：按行存儲的元素地址公式是： Loc(aLoc(aijij)= Loc(a)= Loc(a1111)+(i-1)+(i-1)* *m+(j-1)m+(j-1)* *K , K , 請問請問按列存儲的公式相同嗎？按列存儲的公式相同嗎？答：盡管是方陣，但公式仍不同。應為：答：盡管是方陣，但公式仍不同。應為： Loc(aLoc(aijij)=Loc(a)=Loc(a1111)+(j-1)+(j-1)* *m+(i-1)m+(i-1)* *K K 例例5 5 ：設數組：設數組a1a160, 160, 17070的基地址為的基地址為20482048，每個，每個元素

13、占元素占2 2個存儲單元，若以列序為主序順序存儲，則元個存儲單元，若以列序為主序順序存儲，則元素素a32,58a32,58的存儲地址為的存儲地址為 。根據列優先公式根據列優先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K得：得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950答：請注意審題！答：請注意審題！想一想：若數組是想一想：若數組是a059, 069，結果是否仍為結果是否仍為8950？維界雖未變，但此時的維界雖未變，但此時的a32, 58不再是原來的不再是原來的a32, 5819 n（n2）維數組一般維數組一般也采用按行優先和按列也

14、采用按行優先和按列優先兩種存儲方法。優先兩種存儲方法。（1 1）按行優先：最右邊）按行優先：最右邊的下標先變化，即最右的下標先變化，即最右邊下標從小到大，循環邊下標從小到大，循環一遍后，右邊第一遍后，右邊第2 2個下標個下標再變，再變，最后是最左，最后是最左下標。下標。（2 2）按列優先：）按列優先：P118P118數組的存儲結構與尋址數組的存儲結構與尋址多維數組多維數組三維數組且列優三維數組且列優先時的元素地址先時的元素地址要會計算！要會計算！例例6 6：假設有三維數組假設有三維數組A A7 79 98 8，每個元素用相鄰的，每個元素用相鄰的6 6個個字節存儲，存儲器按字節編址。已知字節存儲

15、，存儲器按字節編址。已知A A的起始存儲位的起始存儲位置（基地址）為置（基地址）為10001000，末尾元素，末尾元素A687A687的第一的第一個字節地址為多少？若按個字節地址為多少？若按列優先（高地址優先）列優先（高地址優先）存存儲時，元素儲時，元素A476A476的第一個字節地址為多少？的第一個字節地址為多少？ 答：答： 末尾元素末尾元素A687A687的第的第1 1個字節地址個字節地址 1000 +(798)66=4018 按高地址優先存儲時，元素按高地址優先存儲時，元素A476A476的第的第1 1個字節個字節地址地址? ?A476=1000+(7 9 6) 6+(7 7+4 ) 6

16、=3586214.2 矩陣的壓縮存儲矩陣的壓縮存儲特殊矩陣：特殊矩陣：矩陣中很多值相同的元素并且它們的分布矩陣中很多值相同的元素并且它們的分布有一定的規律。有一定的規律。稀疏矩陣：稀疏矩陣：矩陣中有很多零元素。矩陣中有很多零元素。壓縮存儲的基本思想是：壓縮存儲的基本思想是： 為多個值為多個值相同相同的元素只分配的元素只分配一個一個存儲空間；存儲空間； 對對零零元素元素不分配不分配存儲空間。存儲空間。 特殊矩陣和稀疏矩陣特殊矩陣和稀疏矩陣22特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對稱矩陣對稱矩陣 3647862842481697460582957A對稱矩陣特點對稱矩陣特點：aij=aji如何壓縮存

17、儲？如何壓縮存儲？只存儲下三角（或上三角）部分的元素。只存儲下三角（或上三角）部分的元素。23特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對稱矩陣對稱矩陣 (a) (a) 下三角矩陣下三角矩陣 (b) (b) 存儲說明存儲說明 (c) (c) 計算方法計算方法一維數組下標從一維數組下標從0開開始始aij在一維數組中的下在一維數組中的下標標k= i( (i+1) )/2+ j 0 in- -10 j n- -1 aij每行元素個數每行元素個數12iaij在本行中的序號在本行中的序號aij第第0行行第第1行行第第i-1行行24特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對稱矩陣對稱矩陣 對于對于下三角中的元素下三

18、角中的元素aij（ij），），在數組在數組SASA中的下標中的下標k與與i、j的關系為的關系為：ki(i1)/2j 。上三角中的元素上三角中的元素aij（ij），），因為因為aijaji，則訪問和則訪問和它對應的元素它對應的元素aji即可，即即可，即：kj(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-125特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲三角矩陣三角矩陣 3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5

19、 7(a)(a)下三角矩陣下三角矩陣3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)(b)上三角矩陣上三角矩陣如何壓縮存儲？如何壓縮存儲？只存儲上三角（或下三角）部分的元素。只存儲上三角（或下三角）部分的元素。26下三角矩陣的壓縮存儲下三角矩陣的壓縮存儲矩陣中任一元素矩陣中任一元素aij在在數組數組中的下標中的下標k與與i、j的對應關系：的對應關系：i( (i1) )/2j 當當ijn( (n1) )/2 當當ijk=0 1 2 3 4 5 k n(n+1)/2第第1行行第第0行行 a00 a10 a11 a20 a21 aij an-1n-1 第第2行行

20、c a22存儲存儲下三角下三角元素元素對角線上方的常數對角線上方的常數只存一個只存一個27上三角矩陣的壓縮存儲上三角矩陣的壓縮存儲矩陣中任一元素矩陣中任一元素aij在在數組數組中的下標中的下標k與與i、j的對應關系：的對應關系： i( (2ni1) )/2ji 當當ijn( (n1) ) /2 當當ijk=存儲存儲上三角上三角元素元素對角線上方的常數對角線上方的常數只存一個只存一個28特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對角矩陣對角矩陣 對角矩陣：對角矩陣：所有非零元素都集中在以主對角線為中心所有非零元素都集中在以主對角線為中心的帶狀區域中，除了主對角線和它的上下方若干條對的帶狀區域中，除了主

21、對角線和它的上下方若干條對角線的元素外，所有其他元素都為零。角線的元素外，所有其他元素都為零。 a00 a01 0 0 0a10 a11 a12 0 00 a21 a22a23 00 0 a32a33 a340 0 0 a43 a44A=29特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對角矩陣對角矩陣 按行按行存儲存儲 元素元素aij在一維數組中的序號在一維數組中的序號 一維數組下標從一維數組下標從0開始開始元素元素aij在一維數組中的下標在一維數組中的下標=2 + 3(i1)+( ji + 1)=2i+ j(b) 尋址的計算方法尋址的計算方法(c) 壓縮到一維數組中壓縮到一維數組中a00 a01 a

22、10 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 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=如何只存儲非零元素？如何只存儲非零元素？注意：稀疏矩陣中的非零元素的分布沒有規律。注意：稀疏矩陣中的非零元素的分布沒有規律

23、。template struct element int row, col; /行號，列號行號，列號 T item /非零元素值非零元素值;將稀疏矩陣中的每個非零元素表示為將稀疏矩陣中的每個非零元素表示為：( (行號，列號，非零元素值行號，列號，非零元素值) )三元組三元組定義三元組定義三元組： 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 三元組表三元組表：將稀疏矩陣的非零元素對應的三元組所將稀疏矩陣的非零元素對應的三元組所構成的集合，構成的集合，按按行優先行優先的順序排列成一個線性表。的順序排列成一個線性表。三元組表三元組表( (0,0,15), (1,1,11), (2,3,6), (4,0,9

24、) )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=如何存儲三元組表？如何存儲三元組表？ 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲三元組順序表三元組順序表采用順序存儲結構存儲三元組表采用順序存儲結構存儲三元組表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=三元組順序表是否三元組順序表是否需要預留存儲空間？需要預留存儲空間？稀疏矩陣的修改操作稀疏矩陣的修改操作三元組順序表的插入三元組順序表的插

25、入/ /刪除操作刪除操作采用順序存儲結構存儲三元組表采用順序存儲結構存儲三元組表 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 0 0A=7（非零元個數）（非零元個數）是否對應惟一的稀疏矩陣？是否對應惟一的稀疏矩陣？5（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲三元組順序表

26、三元組順序表存儲結構定義：存儲結構定義： const int MaxTerm=100; struct SparseMatrix element dataMaxTerm; /存儲非零元素存儲非零元素 int mu, nu, tu; /行數，列數，非零元個數行數，列數，非零元個數 ;稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲三元組順序表三元組順序表三元組順序表操作三元組順序表操作轉置操作轉置操作例：例： 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

27、0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=三元組順序表操作三元組順序表操作轉置操作轉置操作 A第第1 1列列第第2 2列列 第第3 3列列第第4 4列列 第第5 5列列第第6 6列列 第第7 7列列 . . B B第第1 1行行第第2 2行行 第第3 3行行第第4 4行行 第第5 5行行第第6 6行行 第第7 7行行 . .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 00 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0

28、 -70 0 14 0 0 00 0 0 0 0 0(0, 1, 12)(0, 2, 9 )(2, 0, -3)(2, 4, 14)(3, 2, 24)(4, 1, 18)(5, 0, 15)(5, 3, -7)(0, 2, -3)(0, 5, 15)(1, 0, 12)(1, 4, 18)(2, 0, 9)(2, 3, 24)(3, 5, -7)(4, 2, 14)已知已知三三元元組組順順序序表表A.data求求三三元元組組順順序序表表B.data轉置后轉置后AB目的：目的：答：肯定不正確！答：肯定不正確！除了：除了： （1 1）每個元素的行下標和列下標互換（即）每個元素的行下標和列下標互換

29、（即三元組中的三元組中的i i和和j j互換互換）；）；還需要：還需要：（2 2）T T的總行數的總行數mumu和總列數和總列數nunu也要也要互換；互換； 若采用三元組順序表，只要把每個元素的若采用三元組順序表，只要把每個元素的行行下標和列下標互換下標和列下標互換，就完成了對該矩陣的轉置運，就完成了對該矩陣的轉置運算，這種說法正確嗎？算，這種說法正確嗎？ 提問：提問：矩陣 B矩陣 A（3 3）重排重排三元組順三元組順序表內各元素順序序表內各元素順序，使轉置后的三元，使轉置后的三元組順序表也按行（組順序表也按行（或列）為主序有規或列）為主序有規律的排列。律的排列。( (B.dataB.data

30、相對矩陣相對矩陣B B來說仍以行序為主來說仍以行序為主序序進行排列，即進行排列，即相相對對A A按列序為主序按列序為主序進進行排列，即按列號行排列，即按列號從小到大，列號一從小到大，列號一樣的按行號從小到樣的按行號從小到大進行排列大進行排列) )(0, 1, 12)(0, 2, 9 )(2, 0, -3)(2, 4, 14)(3, 2, 24)(4, 1, 18)(5, 0, 15)(5, 3, -7)(0, 2, -3)(0, 5, 15)(1, 0, 12)(1, 4, 18)(2, 0, 9)(2, 3, 24)(3, 5, -7)(4, 2, 14)除了：除了： （1 1）每個元素的行

31、下標和列下標互換（即三元組中的）每個元素的行下標和列下標互換（即三元組中的i i和和j j互換互換）；）；還需要：（還需要：（2 2）B B的總行數的總行數mumu和總列數和總列數nunu也要也要互換；互換； （3 3）重排重排三元組順序表內各元素順序三元組順序表內各元素順序，使轉置后的三元，使轉置后的三元組順序表也按行（或列）為主序有規律的排列。組順序表也按行（或列）為主序有規律的排列。( ( B.dataB.data相對矩陣相對矩陣B B來說仍以行序為主序進行排列，來說仍以行序為主序進行排列，即相對即相對A A按列序為主序進行排列，即按列號從小到按列序為主序進行排列，即按列號從小到大，列號

32、一樣的按行號從小到大進行排列大，列號一樣的按行號從小到大進行排列) )上述（上述（1 1）和（）和（2 2）容易實現，）容易實現，難點在（難點在（3 3）。有兩種實現有兩種實現轉置的方法轉置的方法反復掃描反復掃描A A表，順序存表，順序存掃描一次掃描一次A A表，直接存表，直接存三元組順序表轉置算法三元組順序表轉置算法算法算法 基本思想：基本思想：反復掃描反復掃描A A表，順序存表，順序存。即。即在在A A的三元組的三元組順序表中順序表中依次依次找第找第0 0列、第列、第1 1列、列、直到最后一列的直到最后一列的三元組，并將找到的每個三元組的行、列交換后三元組，并將找到的每個三元組的行、列交換

33、后順順序序存儲到存儲到B 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（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數） row col item0123456MaxTerm- -16（矩陣的行數）（矩陣的行數）5（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）設置矩陣設置矩陣B B的行數、列數、非零元個數的行數、列數、非零元個數 0 0 15 0 3 22

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

35、1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數） row col item0123456MaxTerm- -16（矩陣的行數）（矩陣的行數）5（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）在矩陣在矩陣A A中查找第中查找第1 1列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B 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

36、 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數） row col item0123456MaxTerm- -16（矩陣的行數）（矩陣的行數）5（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）在矩陣在矩陣A A中查找第中查找第2 2列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B 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

37、91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數） row col item0123456MaxTerm- -16（矩陣的行數）（矩陣的行數）5（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）在矩陣在矩陣A A中查找第中查找第3 3列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B 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

38、3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數） row col item0123456MaxTerm- -16（矩陣的行數）（矩陣的行數）5（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）在矩陣在矩陣A A中查找第中查找第4 4列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B 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

39、1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -15（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數） row col item0123456MaxTerm- -16（矩陣的行數）（矩陣的行數）5（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）在矩陣在矩陣A A中查找第中查找第5 5列非零元，順序存儲到矩陣列非零元，順序存儲到矩陣B 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

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

41、算法算法I I的的C+C+描述不做要求描述不做要求三元組順序表轉置算法三元組順序表轉置算法時間復雜度時間復雜度分析該算法的時間復雜度：分析該算法的時間復雜度：對三元組順序表對三元組順序表A A掃描多少趟？掃描多少趟？共掃描列數共掃描列數nunu趟趟某趟（假設為第某趟（假設為第colcol趟）掃描的操作是什么？趟）掃描的操作是什么？查找列號為查找列號為colcol的三元組，行列號交換后存儲到的三元組，行列號交換后存儲到B B表中表中算法算法I I的時間復雜度為的時間復雜度為O(nuO(nu* *tutu) ), ,與常規存儲方式下與常規存儲方式下矩陣轉置算法（矩陣轉置算法（O(nuO(nu* *

42、mu)mu)）相比，當）相比，當tutumumu時，算時，算法的時間性能更差一些。法的時間性能更差一些。分析分析：A A表中第表中第0 0列的第一個非零元素一定存儲在列的第一個非零元素一定存儲在B B表表中下標為中下標為0 0的位置上，該列中其它非零元素應存放在的位置上，該列中其它非零元素應存放在B B表中后面連續的位置上，那么第表中后面連續的位置上，那么第1 1列的第一個非零列的第一個非零元素在元素在B B表中的位置便等于第表中的位置便等于第0 0列的第一個非零元素列的第一個非零元素在在B B表中的位置加上第表中的位置加上第0 0列的非零元素的個數，以此列的非零元素的個數，以此類推。類推。

43、基本思想：基本思想：掃描一次掃描一次A A表，直接存。表，直接存。即即在在A A表中依次表中依次取三元組，交換其行號和列號放到取三元組，交換其行號和列號放到B B 表中表中適當適當位置。位置。三元組順序表轉置算法三元組順序表轉置算法算法算法如何確定當前從如何確定當前從A A表中取出的三元組在表中取出的三元組在B B表中的位表中的位置？置？關鍵：關鍵：怎樣尋找怎樣尋找B B表中的表中的“恰當恰當”位置？位置？如果能如果能預知預知A矩陣矩陣每一列每一列( (即即B的每一行的每一行) )的的非零元素個非零元素個數數，又能很快得知，又能很快得知每列第一個非零元素每列第一個非零元素在在B B表中的表中的

44、位置位置, ,則掃描則掃描A表表時便可以將每個元素準確定位時便可以將每個元素準確定位( (因已知若干因已知若干參考點參考點) )請注意請注意A A表特征表特征：每列首個非零元素必定先被掃描到。：每列首個非零元素必定先被掃描到。技巧：技巧：為實現轉置運算，應當按列生成為實現轉置運算，應當按列生成A A矩陣的矩陣的兩個輔兩個輔助數組助數組，讓它攜帶每列的非零元素個數，讓它攜帶每列的非零元素個數 num(inum(i) ) 以及每以及每列的第一個非零元素在三元組表中的位置列的第一個非零元素在三元組表中的位置cpot(icpot(i) ) 等信等信息。息。引入兩個數組作為輔助數據結構：引入兩個數組作為

45、輔助數據結構：numnunumnu ：存儲矩陣：存儲矩陣A A中某列的非零元素的個數；中某列的非零元素的個數；cpotnucpotnu ：初值初值表示矩陣表示矩陣A A中某列的第一個非零元中某列的第一個非零元素在素在B B中的位置。中的位置。 數據結構設計：數據結構設計：cpot0=0cpot0=0；cpotcolcpotcol=cpotcol-1+numcol-1=cpotcol-1+numcol-1；1col1colnununumnum與與cpotcpot存在如下遞推關系：存在如下遞推關系：三元組順序表轉置算法三元組順序表轉置算法算法算法討論：討論：求出求出按列優先按列優先的的輔助數組輔助

46、數組后，后，如何實現快速轉置？如何實現快速轉置？col012345numcol222110cpotcol0計算式：計算式： cpot(0)0cpotcol cpotcol-1 + numcol-1 2 4 6 7 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 0Mcol 0 1 2 3 4 5三三元元組組表表A(5, 3, -7)(5, 0, 15)(4, 1, 18)(3, 2, 24)(2, 4, 14)(2, 0, -3)(0, 2, 9 )(0, 1, 12)col p1234想一想：是

47、從原始矩陣想一想：是從原始矩陣A A中統計中統計numcol方便些，還是從對應的三元組順序表方便些，還是從對應的三元組順序表A A中中統計更方便？統計更方便？ 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（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數） col 0 1 2 3 4 5 numcol 2 1 1 2 0 1 cpotcol 0 2 3 4 6 6根據矩陣根據矩陣A A的三元組順序表計算的三元

48、組順序表計算numnum和和cpotcpot 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 閑閑 閑閑 閑閑row col item01234565（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）將矩陣將矩陣A A中中colcol列元素存放在列元素存放在B B中下標為中下標為cpotcolcpotcol 的位置的位置 row col item01234566（矩陣的行數）（矩陣的行數）5（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）cpot0cpot1cpot2cpot3

49、cpot4 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（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）將矩陣將矩陣A A中中colcol列元素存放在列元素存放在B B中下標為中下標為cpotcolcpotcol 的位置的位置 row col item01234566（矩陣的行數）（矩陣的行數）5（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）cpot1cpot2cpot3cpot

50、4 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（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）將矩陣將矩陣A A中中colcol列元素存放在列元素存放在B B中下標為中下標為cpotcolcpotcol 的位置的位置 row col item01234566（矩陣的行數）（矩陣的行數）5（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）cpot1cpot2c

51、pot4 0 0 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（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）將矩陣將矩陣A A中中colcol列元素存放在列元素存放在B B中下標為中下標為cpotcolcpotcol 的位置的位置 row col item01234566（矩陣的行數）（矩陣的行數）5（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）cpot1cpot2cpot4 0 0 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（矩陣的行數）（矩陣的行數）6（矩陣的列數）（矩陣的列數）7（非零元個數）（非零元個數）將矩