數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版DS05-數(shù)組和廣義表

1、第 章 數(shù) 組 和 廣 義 表 第五章 數(shù)組q數(shù)組的類型定義和表示方法數(shù)組的類型定義和表示方法q特殊矩陣和稀疏矩陣存儲(chǔ)方法特殊矩陣和稀疏矩陣存儲(chǔ)方法 及運(yùn)算的實(shí)現(xiàn)及運(yùn)算的實(shí)現(xiàn)q廣義表的結(jié)構(gòu)特點(diǎn)廣義表的結(jié)構(gòu)特點(diǎn)第 章 數(shù) 組 和 廣 義 表 5.1.1 二維數(shù)組的定義二維數(shù)組的定義n定義定義mnmmnnnmaaaaaaaaaA.212222111211數(shù)組特點(diǎn)數(shù)組特點(diǎn)數(shù)組結(jié)構(gòu)固定數(shù)組結(jié)構(gòu)固定數(shù)據(jù)元素同構(gòu)數(shù)據(jù)元素同構(gòu)數(shù)組運(yùn)算數(shù)組運(yùn)算給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素給定一組下標(biāo)，修改數(shù)據(jù)元素的值給定一組下標(biāo)，修改數(shù)據(jù)元素的值( )( )( )( )( )( )( )(

2、 )( )數(shù)組是一組有固定數(shù)組是一組有固定（一（一旦定義了數(shù)組的維數(shù)和旦定義了數(shù)組的維數(shù)和每一維的上下限個(gè)數(shù)）每一維的上下限個(gè)數(shù)）的元素的集合。的元素的集合。由于這由于這個(gè)性質(zhì)，使得對(duì)數(shù)組的個(gè)性質(zhì)，使得對(duì)數(shù)組的操作不像對(duì)線性表的操操作不像對(duì)線性表的操作那樣可以在表中任意作那樣可以在表中任意一個(gè)合法的位置插入或一個(gè)合法的位置插入或刪除一個(gè)元素。對(duì)于數(shù)刪除一個(gè)元素。對(duì)于數(shù)組的操作一般只有兩類：組的操作一般只有兩類： 數(shù)組可以看成是一種特殊的線性表，即線數(shù)組可以看成是一種特殊的線性表，即線性表中數(shù)據(jù)元素本身也是一個(gè)線性表性表中數(shù)據(jù)元素本身也是一個(gè)線性表第 章 數(shù) 組 和 廣 義 表 矩陣矩陣A Am

3、 mn n看成看成n n個(gè)列向量的線性表個(gè)列向量的線性表 第 章 數(shù) 組 和 廣 義 表 矩陣矩陣A Am mn n看成看成m m個(gè)行向量的線性表個(gè)行向量的線性表 第 章 數(shù) 組 和 廣 義 表 5.1.2 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)次序約定次序約定n以行序?yàn)橹餍蛞孕行驗(yàn)橹餍騨以列序?yàn)橹餍蛞粤行驗(yàn)橹餍?a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序?yàn)橹餍虼娣虐葱行驗(yàn)橹餍虼娣?amn . am2 am1 a2n . a22 a21 a1n a12 a1101n-1m*n-1 n 二維數(shù)組按列

4、序?yàn)槎S數(shù)組按列序?yàn)橹餍虼娣胖餍虼娣牛ㄏ聵?biāo)從（下標(biāo)從1開(kāi)始）開(kāi)始）01m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*L L為每一個(gè)數(shù)組元素所占的存儲(chǔ)單元個(gè)數(shù)為每一個(gè)數(shù)組元素所占的存儲(chǔ)單元個(gè)數(shù)第 章 數(shù) 組 和 廣 義 表 共有共有120個(gè)元素個(gè)元素三維數(shù)組的邏輯結(jié)構(gòu)圖三維數(shù)組的邏輯結(jié)構(gòu)圖 下標(biāo)從下標(biāo)從0開(kāi)始開(kāi)始頁(yè)行列第 章 數(shù) 組 和 廣 義 表 m m1 1, m, m2 2, m,

5、 m3 3LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前前i1頁(yè)總頁(yè)總元素個(gè)數(shù)元素個(gè)數(shù)第第i1頁(yè)的頁(yè)的前前i2行行總總元素個(gè)數(shù)元素個(gè)數(shù)第 章 數(shù) 組 和 廣 義 表 m m1 1, m, m2 2, m, m3 3, , , m, mn nlimianjnjknkj*111LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l 第 章 數(shù) 組 和 廣 義 表 1112111012222120111211101002010

6、0nnnnnnnnaaaaaaaaaaaaaaaa對(duì)稱陣下三角矩陣5.2.1 特殊矩陣特殊矩陣第 章 數(shù) 組 和 廣 義 表 11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa對(duì)對(duì)稱稱陣陣的的上上三三角角矩矩陣陣A=第 章 數(shù) 組 和 廣 義 表 對(duì)稱矩陣的存儲(chǔ)對(duì)稱矩陣的存儲(chǔ)11121110122221201112111010020100Annnnnnnnaaaaaaaaaaaaaaaa，aij = aji0 1 2 3 4 5 6 7 8 n(n+1)/2-1B a00 a10 a11 a20 a21 a22 a30 a31 a3

7、2 an-1n-1 存存下下三三角角第 章 數(shù) 組 和 廣 義 表 = j *(j +1) / 2 + i 前i行元素總數(shù) 第i行第j個(gè)元素前元素個(gè)數(shù)第 章 數(shù) 組 和 廣 義 表 33323130232221201312111003020100aaaaaaaaaaaaaaaa上三角矩陣B a00 a01 a02 a03 a11 a12 a13 a22 a23 a33 0 1 2 3 4 5 6 7 8 9若若i j，數(shù)組元素，數(shù)組元素Aij在數(shù)組在數(shù)組B中的存放位置中的存放位置為為n + (n- -1) + (n- -2) + + (n- -i+1) + j- -i前i行元素總數(shù) 第i行第j

8、個(gè)元素前元素個(gè)數(shù)n = 4第 章 數(shù) 組 和 廣 義 表 若若 i j，數(shù)組元素，數(shù)組元素Aij在數(shù)組在數(shù)組B中的存放位置為中的存放位置為 n + (n- -1) + (n- -2) + + (n- -i+1) + j- -i = = (2*n- -i+1) * i / 2 + j- -i = = (2*n- -i- -1) * i / 2 + j 若若i j，數(shù)組元素，數(shù)組元素Aij在矩陣的下三角部分，在在矩陣的下三角部分，在數(shù)組數(shù)組 B 中沒(méi)有存放。因此，找它的對(duì)稱元素中沒(méi)有存放。因此，找它的對(duì)稱元素Aji。 Aji在數(shù)組在數(shù)組 B 的第的第 (2*n- -j- -1) * j / 2 +

9、 i 的位置中找的位置中找到。到。對(duì)于上三角矩陣第 章 數(shù) 組 和 廣 義 表 n三角矩陣三角矩陣 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0Loc(aij)=Loc(a11)+( +(j-1)*L i(i-1)2a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序?yàn)橹餍颍簀i 時(shí)aij為0一個(gè)元素所占字節(jié)數(shù)一個(gè)元素所占字節(jié)數(shù)下標(biāo)從下標(biāo)從1開(kāi)始開(kāi)始第 章 數(shù) 組 和 廣 義 表 1121122232232221121110010000000000000000000Ann

10、nnnnnnnnaaaaaaaaaaaaaB a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 10對(duì)角陣對(duì)角陣的下標(biāo)的下標(biāo)從從0起起存放對(duì)存放對(duì)角陣元角陣元素的一素的一維數(shù)組維數(shù)組的下標(biāo)的下標(biāo)從從0起起第 章 數(shù) 組 和 廣 義 表 n三對(duì)角矩陣中除主對(duì)角線及在主對(duì)角線上下最臨三對(duì)角矩陣中除主對(duì)角線及在主對(duì)角線上下最臨近的兩條對(duì)角線上的元素外，所有其它元素均為近的兩條對(duì)角線上的元素外，所有其它元素均為0 0。總共有。總共有2+3(2+3(n n-2)+2= 3-2)+2= 3n n-2-2個(gè)非零元素。個(gè)非零

11、元素。n將三對(duì)角矩陣將三對(duì)角矩陣A A中三條對(duì)角線上的元素按行存放中三條對(duì)角線上的元素按行存放在一維數(shù)組在一維數(shù)組 B B 中，且中，且a a0000存放于存放于B0B0。n在三條對(duì)角線上的元素在三條對(duì)角線上的元素a aijij 滿足滿足 0 0 i i n n-1, -1, i i-1 -1 j j i i+1+1n在一維數(shù)組在一維數(shù)組 B B 中中 Aij Aij 在第在第 i i 行，它前面行，它前面有有 3 3* *i-1 i-1 個(gè)非零元素個(gè)非零元素, , 在本行中第在本行中第 j j 列前面有列前面有 j-i+1 j-i+1 個(gè)，所以元素個(gè)，所以元素 Aij Aij 在在 B B

12、中位置為中位置為 k k = 2 = 2* *i i + + j j第 章 數(shù) 組 和 廣 義 表 若已知三對(duì)角矩陣中某元素若已知三對(duì)角矩陣中某元素 Aij 在數(shù)組在數(shù)組 B 存存放于第放于第 k 個(gè)位置，則有個(gè)位置，則有 i = (k + 1)/3 j = k - - 2 * i例如，當(dāng)例如，當(dāng) k = 8 時(shí)，時(shí)， i = (8+1)/3 = 3, j = 8 - - 2*3= 2 當(dāng)當(dāng) k = 10 時(shí)，時(shí)， i = (10+1)/3 = 3, j = 10-2*3 = 4不第 章 數(shù) 組 和 廣 義 表 5.2.2 稀疏矩陣稀疏矩陣定義：定義：非零元較零元少，且分非零元較零元少，且分布

13、沒(méi)有一定規(guī)律的矩陣布沒(méi)有一定規(guī)律的矩陣壓縮存儲(chǔ)原則：壓縮存儲(chǔ)原則：只存矩陣的行只存矩陣的行列維數(shù)和每個(gè)非零元的行列下列維數(shù)和每個(gè)非零元的行列下標(biāo)及其值標(biāo)及其值第 章 數(shù) 組 和 廣 義 表 7600070015000001800000240001400003000000000009120MM由(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ù)（6,7,8）唯一確定例如：例如：第 章 數(shù) 組 和 廣 義 表 稀疏矩陣的壓縮存儲(chǔ)方法稀疏矩陣的壓縮存儲(chǔ)方法n三元組表三元組表#defin

14、e M 20typedef struct node /*三元組表中元素類型*/ int i,j; /*非零元所在行號(hào)和列號(hào)*/ int v; /*非零元素值*/ TriTupleNode ;TriTupleNode maM; mai j v0 1 2 3 4 5 6 7 8第 章 數(shù) 組 和 廣 義 表 7600070015000001800000240001400003000000000009120Amai j v0 1 2 3 4 5 6 7 86 7 8 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ù) 組 和 廣

15、義 表 n求轉(zhuǎn)置矩陣求轉(zhuǎn)置矩陣Y問(wèn)題描述：已知一個(gè)稀疏矩陣的三元組表，問(wèn)題描述：已知一個(gè)稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表求該矩陣轉(zhuǎn)置矩陣的三元組表Y問(wèn)題分析問(wèn)題分析一般矩陣轉(zhuǎn)置算法：一般矩陣轉(zhuǎn)置算法：for(col=0;coln;col+) for(row=0;rowm;row+) Bcolrow=Arowcol;時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：T(n)=O(m n)第 章 數(shù) 組 和 廣 義 表 7600070015000001800000240001400003000000000009120A6700000000014000000007000000024009018000121500

16、300B6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v7 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 0 1 2 3 4 5 6 7 8mb按行序存放按行序存放第 章 數(shù) 組 和 廣 義 表 解決思路：解決思路：將矩陣行、列維數(shù)互換將矩陣行、列維數(shù)互換將每個(gè)三元組中的將每個(gè)三元組中的i和和j相互調(diào)換相互調(diào)換重排三元組次序，使重排三元組次序，使mb中元素以中元素以B的行的行(A的列的列)為主

17、序?yàn)橹餍虻?章 數(shù) 組 和 廣 義 表 5.3 廣義表 廣義表廣義表(Lists)(Lists)也稱為也稱為列表列表，它是線性表，它是線性表的推廣。大家知道，線性表是的推廣。大家知道，線性表是n n（n n0 0）個(gè)）個(gè)元素元素a a1 1，a a2 2，a ai i，a an n的有限序列。的有限序列。其中，線性表的元素僅限于原子項(xiàng)，所謂其中，線性表的元素僅限于原子項(xiàng)，所謂原原子子，指的是結(jié)構(gòu)上不可再分割的一種成分，指的是結(jié)構(gòu)上不可再分割的一種成分，它可以是一個(gè)數(shù)，或者是一個(gè)結(jié)構(gòu)。如果放它可以是一個(gè)數(shù)，或者是一個(gè)結(jié)構(gòu)。如果放松對(duì)線性表元素的這種限制，允許它們具有松對(duì)線性表元素的這種限制，允許

18、它們具有其自身獨(dú)立的類型結(jié)構(gòu)，那么就產(chǎn)生了廣義其自身獨(dú)立的類型結(jié)構(gòu)，那么就產(chǎn)生了廣義表的概念。表的概念。第 章 數(shù) 組 和 廣 義 表 LS = (a0, a1, a2, , an-1) LS第 章 數(shù) 組 和 廣 義 表 廣義表通常用圓括號(hào)括起來(lái)，用逗號(hào)廣義表通常用圓括號(hào)括起來(lái)，用逗號(hào)分隔其中的元素。分隔其中的元素。n為區(qū)分原子和廣義表，用大寫(xiě)字母表示為區(qū)分原子和廣義表，用大寫(xiě)字母表示廣義表，用小寫(xiě)字母表示原子。廣義表，用小寫(xiě)字母表示原子。n表尾一定是子表。但表頭可以是原子，表尾一定是子表。但表頭可以是原子，也可以是子表。也可以是子表。n廣義表是遞歸定義的，因?yàn)樵诙x廣義廣義表是遞歸定義的，

19、因?yàn)樵诙x廣義表時(shí)又用到了廣義表的概念。表時(shí)又用到了廣義表的概念。 需要注意的是：需要注意的是：第 章 數(shù) 組 和 廣 義 表 廣義表是一個(gè)廣義表是一個(gè)多層次多層次的的線性結(jié)構(gòu)線性結(jié)構(gòu)。例如。例如:有有A、B、C、D、E五個(gè)廣義表的描述如下：五個(gè)廣義表的描述如下： A = ( ) A是一個(gè)空表是一個(gè)空表,它的長(zhǎng)度為零它的長(zhǎng)度為零 B = (e) 列表列表B只有一個(gè)原子只有一個(gè)原子e,B的長(zhǎng)度為的長(zhǎng)度為1. C = (a,(b,c,d) 列表列表C的長(zhǎng)度為的長(zhǎng)度為2,兩個(gè)元素分別為兩個(gè)元素分別為原子原子a和子表和子表(b,c,d) D = (A,B,C) 列表列表D的長(zhǎng)度為的長(zhǎng)度為3,三個(gè)元素都

20、是列表三個(gè)元素都是列表,顯然顯然,將子表的值代入后將子表的值代入后,則有則有D=(),(e),(a,(b,c,d) E = (a,E) 這是一個(gè)遞歸的表這是一個(gè)遞歸的表,它的長(zhǎng)度為它的長(zhǎng)度為2,E相當(dāng)于一個(gè)無(wú)限的列表相當(dāng)于一個(gè)無(wú)限的列表E=(a,(a,(a,.)第 章 數(shù) 組 和 廣 義 表 1) 1) 廣義表中的數(shù)據(jù)元素有相對(duì)廣義表中的數(shù)據(jù)元素有相對(duì)次序次序; ;2) 2) 廣義表的廣義表的長(zhǎng)度長(zhǎng)度定義為最外層包含的元素個(gè)數(shù)定義為最外層包含的元素個(gè)數(shù); ;3) 3) 廣義表的廣義表的深度深度定義為所含括弧的重?cái)?shù)定義為所含括弧的重?cái)?shù); ; 注意注意: “: “原子原子”的深度為的深度為“0”;

21、 “0”; “空表空表”的深度的深度為為1 14) 4) 表頭可以是原子或列表表頭可以是原子或列表; ;表尾必定是列表。表尾必定是列表。5) 5) 廣義表可以是一個(gè)廣義表可以是一個(gè)遞歸遞歸的表的表; ; 遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。廣義表的結(jié)構(gòu)特點(diǎn)廣義表的結(jié)構(gòu)特點(diǎn): :第 章 數(shù) 組 和 廣 義 表 6) 任何一個(gè)非空廣義表任何一個(gè)非空廣義表 LS = ( LS = ( 1 1, , 2 2, , , , n n) ) 均可分解為均可分解為 表頭表頭 Head(LS) = Head(LS) = 1 1 表尾表尾 Tail(LS) = ( Tail(L

22、S) = ( 2 2, , , , n n) ) 兩部分兩部分第 章 數(shù) 組 和 廣 義 表 例如：例如：Head( ( b, c) ) = ( b, c)Tail( ( b, c) ) = ( )Head( a,( b, c) ) = a Tail( a,( b, c) ) = ( b,c )Head( ( c ) ) =(c)Tail( ( c ) ) = ( ) 求出的表頭是原樣，而求出的表尾要再加上一對(duì)圓括號(hào)才為所求第 章 數(shù) 組 和 廣 義 表 Head(Head(LSLS) = A ) = A Tail(Tail(LSLS) = ( D ) = ( D )Head( Head( D

23、 D ) = E ) = E Tail( Tail( D D ) = ( F ) ) = ( F )Head(Head( E E ) = a Tail() = a Tail( E E ) = ( ( b, c) ) ) = ( ( b, c) )Head(Head( ( b, c) ( b, c) ) = ( b, c) Tail( ) = ( b, c) Tail( ( b, c)( b, c) ) = ( ) ) = ( )Head(Head( ( b, c) ( b, c) ) = b Tail( ) = b Tail( ( b, c)( b, c) ) = ( c ) ) = ( c

24、)LS = (A, D ) = ( ), ( E, F ) = ( ), (a, (b, c)LS = (A, D ) = ( ), ( E, F ) = ( ), (a, (b, c)，F(xiàn) )F )例如：例如：第 章 數(shù) 組 和 廣 義 表 廣義表還可以用圖形來(lái)形象的表示，下圖給出廣義表還可以用圖形來(lái)形象的表示，下圖給出了幾個(gè)廣義表的圖形表示，其中的分支結(jié)點(diǎn)對(duì)了幾個(gè)廣義表的圖形表示，其中的分支結(jié)點(diǎn)對(duì)應(yīng)應(yīng)廣義表廣義表，非分支結(jié)點(diǎn)（即，非分支結(jié)點(diǎn)（即葉子葉子）對(duì)應(yīng)原子或）對(duì)應(yīng)原子或者空表。者空表。Lab(a)L=(a,b)AxL(b)A=(x,L)abAxLaByb(c)B=(A,y)AxLaCBb(d)C=(A,B)a