數(shù)據(jù)結(jié)構(gòu)課件05

1、第五章第五章 數(shù)組和廣義表數(shù)組和廣義表 精英專升本精英專升本 5.1 數(shù)組的類型定義數(shù)組的類型定義 5.3 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn) 5.4 廣義表的類型定義廣義表的類型定義 5.5 廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu) 本節(jié)所討論的數(shù)組與高級語言中的數(shù)組區(qū)別：本節(jié)所討論的數(shù)組與高級語言中的數(shù)組區(qū)別： 高級語言中的數(shù)組是高級語言中的數(shù)組是順序結(jié)構(gòu)順序結(jié)構(gòu)； 而本章的數(shù)組既可以是而本章的數(shù)組既可以是順序順序的，也可以是的，也可以是鏈?zhǔn)芥準(zhǔn)浇Y(jié)構(gòu)，結(jié)構(gòu)， 用戶可根據(jù)需要選擇。用戶可根據(jù)需要選擇。 一、一、數(shù)組的概念數(shù)組的概念 5.1 數(shù)組的定

2、義數(shù)組的定義 一維數(shù)組可以看成是一個線性表，但操作簡單，一般不進一維數(shù)組可以看成是一個線性表，但操作簡單，一般不進 行行操作，只定義給定下標(biāo)讀取元素和修改元素操作，只定義給定下標(biāo)讀取元素和修改元素 的操作。的操作。 二維數(shù)組可以看成是二維數(shù)組可以看成是。 例如，設(shè)例如，設(shè)A是一個有是一個有m行行n列的二維數(shù)組，則列的二維數(shù)組，則A可以表示為：可以表示為： 可以將二維數(shù)組可以將二維數(shù)組A看成是由看成是由n個列向量個列向量A=1, 2, , n組成，組成， 其中其中 i=(a1i, a2i, .,ami)， 0in。 n個元素的線性表個元素的線性表 也可以將二維數(shù)組也可以將二維數(shù)組A看成是由看成是

3、由m個行向量個行向量B=1，2， ， mT組成，其中，組成，其中，i=( ai1, ai2, .,ain)， 0im m個元素的線性表個元素的線性表 可以把三維以上的數(shù)組稱為多維數(shù)組?？梢园讶S以上的數(shù)組稱為多維數(shù)組。 n維數(shù)組中，每個數(shù)據(jù)元素對應(yīng)維數(shù)組中，每個數(shù)據(jù)元素對應(yīng)n個下標(biāo)。個下標(biāo)。 可看作是可看作是數(shù)據(jù)元素為數(shù)據(jù)元素為n-1維數(shù)組維數(shù)組的一維的一維 數(shù)組。數(shù)組。 基本操作基本操作: (1) InitArray ( /該非零元的行下標(biāo)和列下標(biāo) ElemType e; / 該非零元的值 Triple; / 三元組類型三元組類型 一、三元組順序表一、三元組順序表 typedef union

4、 Triple data0未占用 int mu, nu, tu; TSMatrix; / 稀疏矩陣類型稀疏矩陣類型 0000015 00390170 000000 0006022 2800000 0000110 0910000 B 00002800 00000091 03900000 0006000 017000110 150022000 A 67 76 data data data data data data data data 如何求轉(zhuǎn)置矩陣？如何求轉(zhuǎn)置矩陣？ 0280036 00070 500140 005 2800 000 0714 3600 M矩陣 T矩陣 用常規(guī)的二維數(shù)組表示時的

5、算法 其時間復(fù)雜度為其時間復(fù)雜度為: O(munu) for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol; 用“三元組”表示時如何實現(xiàn)？ M矩陣 T矩陣 1 2 14 1 5 -5 2 2 -7 3 1 36 3 4 28 2 2 -7 2 1 14 5 1 -5 1 3 36 4 3 28 用“三元組”表示時如何實現(xiàn)？ M矩陣 T矩陣 1 2 14 1 5 -5 2 2 -7 3 1 36 3 4 28 1 3 36 2 1 14 2 2 -7 5 1 -5 4 3 28 用“三元組”表示時如何實現(xiàn)？ M

6、矩陣 T矩陣 1 14 1 5 -5 2 -7 3 1 36 3 28 2 1 14 2 2 -7 為此，需要知道矩陣M的 。 如何確定的第一個 非零元在data中的位置？ 實現(xiàn)：設(shè)兩個數(shù)組實現(xiàn)：設(shè)兩個數(shù)組 numcol：表示矩陣：表示矩陣M中第中第col列中非零元個數(shù)列中非零元個數(shù) cpotcol：指示指示M中第中第col列第一個非零元在列第一個非零元在T.data 中位置中位置。 顯然有：顯然有： cpot1=1; cpotcol=cpotcol-1+numcol-1; (2 col M.data0.j) 1357889 col numcol cpotcol 1 2 2 2 3 2 4 1

7、 5 0 6 1 7 0 76 00070015 00000180 00002400 01400003 0000000 00009120 M 已知一個稀疏矩陣為 0000 5100 0003 0200 ，則對應(yīng)的三元組表表示為（ ） 。 練習(xí)題 已知一個稀疏矩陣用三元組表示為 ，則轉(zhuǎn)置矩陣的三元組表表示為（ ） 。 真題 5.4 廣義表的類型定義廣義表的類型定義 n 廣義表（列表）：廣義表（列表）： n ( 0 )個表元素組成的有限個表元素組成的有限 序列序列， 記作記作LS = (a0, a1, a2, , an-1) LS是表名，是表名，ai是表元素，它可以是表是表元素，它可以是表 (稱為

8、稱為子表子表)， 可以是數(shù)據(jù)元素可以是數(shù)據(jù)元素(稱為稱為原子原子)。 n n為表的長度。為表的長度。n = 0 的廣義表為空表。的廣義表為空表。 ADT Glist 數(shù)據(jù)對象數(shù)據(jù)對象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet為某個數(shù)據(jù)對象 數(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 或為原子 或為廣義表 例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F

9、) B = (a, B) = (a, (a, (a, , ) ) ) 廣義表是一個多層次多層次的線性結(jié)構(gòu)線性結(jié)構(gòu) 例如：例如： D=(E, F) 其中: E=(a, (b, c) F=(d, (e) D EF a( ) d( ) bc e 廣義表廣義表 LS = ( 1, 2, , n )的結(jié)構(gòu)特點的結(jié)構(gòu)特點: 1) 廣義表中的數(shù)據(jù)元素有相對次序次序； 2) 廣義表的長度長度定義為最外層包含元素個數(shù)； 3) 廣義表的深度深度定義為所含括弧的重數(shù)； 注意：“原子”的深度為 0 “空表”的深度為 1 4) 廣義表可以共享共享； 5) 廣義表可以是一個遞歸遞歸的表。 遞歸表的深度是無窮值，長度是有限

10、值。 6) 任何一個非空廣義表非空廣義表 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 ) ) = ( ) 廣義表（a,b,c,d）的表頭是（ ），表尾是（ ）。 A、a B、() C、(a,b,c,d) D、(a,b,c,d) 真題 廣義表A=（ A, B, (C,D) , (E,(F,G) ），則 head( tail( head ( tail (tail (A) ) ) ) )=( ) A、(G) B、(D) C、C D、 D 練習(xí)題 1. 1. 了解數(shù)組的兩種存儲表示方法，并掌了解數(shù)組的兩種存儲表示方法，并掌 握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址 計算方法。計算方法。 2