1、第5章 數(shù)組和廣義表,5.1 數(shù)組的定義和運(yùn)算 5.2 數(shù)組的順序存儲和實(shí)現(xiàn) 5.3 特殊矩陣的壓縮存儲 5.4 廣義表,數(shù)組是n(n1)個相同類型數(shù)據(jù)元素a0,a1,an-1構(gòu)成的有限序列,且該有限序列存儲在一塊地址連續(xù)的內(nèi)存單元中。 數(shù)組的定義類似于采用順序存儲結(jié)構(gòu)的線性表，是線性表在維數(shù)上的擴(kuò)張，也就是線性表中的元素又是一個線性表。 n維數(shù)組，bi是第i維的長度，則n維數(shù)組共有 個數(shù)據(jù)元素，每個元素受n個關(guān)系的制約，就單個關(guān)系而言，這n個關(guān)系仍然是線性的。,1. 數(shù)組的定義和運(yùn)算,數(shù)組具有以下性質(zhì)： (1)數(shù)組中的數(shù)據(jù)元素數(shù)目固定。一旦定義了一個 數(shù)組,其數(shù)據(jù)元素數(shù)目不再有增減變化。 (

2、2)數(shù)組中的數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。 (3)數(shù)組中的每個數(shù)據(jù)元素都和一組惟一的下標(biāo)值對 應(yīng)。 (4)數(shù)組是一種隨機(jī)存儲結(jié)構(gòu)?？呻S機(jī)存取數(shù)組中的 任意數(shù)據(jù)元素。,數(shù)組的基本操作 (1)取值 Value(A, k=2(i-1)+j-1;,稀疏矩陣 非零元較零元少，且沒有一定規(guī)律。 mn的矩陣，有t個非零元， 矩陣的稀疏因子：=t/(m*n)，當(dāng)0.05時為稀疏矩陣。 壓縮存儲，只存儲非零元 三元組順序表(i，j，ai,j) 行邏輯鏈接的順序表 十字鏈表 (1,2,12),(1,3,9),(3,1,-3),(3,6,14), (4,3,24),(5,2,18),(6,1,15),(6,4,-7)

3、,#define MaxSize 100 /*矩陣中非零元素最多個數(shù)*/ typedef struct int i; /*行號*/ int j; /*列號*/ ElemType e; /*元素值*/ Triple; /*三元組定義*/ typedef struct int rows; /*行數(shù)*/ int cols; /*列數(shù)*/ int nums; /*非零元素個數(shù)*/ Triple dataMaxSize+1; /*data0未用*/ TSMatrix; /*三元組順序表定義*/,用三元組表實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置運(yùn)算 一個6*7的矩陣A，以行序為主序順序排列,矩陣的轉(zhuǎn)置，方法一：,Status

4、 TransposeSMatrix(TSMatrix A, TSMatrix ,方法1時間復(fù)雜度： O(cols*nums) 當(dāng)非零元個數(shù)nums和cols*rows同數(shù)量級時， O(rows*cols2) 僅適用于numsrows*cols. 常規(guī)存儲方式時， 實(shí)現(xiàn)矩陣轉(zhuǎn)置的經(jīng)典算法如下： for(i=0; im; i+) for (j=0; j n; j+) Ti j = Mji; O(cols*rows),方法二： 依次按三元組表A(6*7)的次序進(jìn)行轉(zhuǎn)置，轉(zhuǎn)置后直接放到三元組表B的正確位置上。這種轉(zhuǎn)置算法稱為快速轉(zhuǎn)置算法。,col 1 2 3 4 5 6 7,numcol,cpotco

5、l,2,2,2,1,0,1,0,1,3,5,7,8,8,9,numcol: A中第col列非零元的個數(shù)。 cpotcol: B中第col行第一個非零元 在B中的位置,Status FastTranSMatrix(TSMatrix A, TSMatrix ,O(cols+nums) 當(dāng)nums和cols*rows同數(shù)量級時 O(rows*cols),row col e,1 2 3 4 5 6 7 8,1 3 -3,3 1 9,2 1 12,cpot1 cpot2 cpot2 cpot3 cpot3 cpot4 cpot6,6 3 14,3 4 24,2 5 18,1 6 15,4 6 -7,小結(jié)

6、 基本學(xué)習(xí)要點(diǎn)如下： (1)理解數(shù)組和一般線性表之間的差異。 (2)重點(diǎn)掌握數(shù)組的順序存儲結(jié)構(gòu)和元素地址計算方法。 (3)掌握各種特殊矩陣如對稱矩陣、上、下三角矩陣和對角矩陣的壓縮存儲方法。 (4)掌握稀疏矩陣的各種存儲結(jié)構(gòu)以及基本運(yùn)算實(shí)現(xiàn)算法。 (5)靈活運(yùn)用數(shù)組這種數(shù)據(jù)結(jié)構(gòu)解決一些綜合應(yīng)用問題。,練習(xí)： 將一個A1.100, 1.100的三對角矩陣，按行優(yōu)先存入一維數(shù)組B1.298，A中元素a66,65在B數(shù)組中的位置k=?。 在主對角線左下方，65*3-1+1 = 195。,作業(yè)： 5.2 5.25,1. 廣義表的定義（列表） 廣義表是線性表的推廣，是由零個或多個單元素或子表所 組成的有

7、限序列。 LS=(a1,a2,ai,an) ai：是單個數(shù)據(jù)元素,則ai是廣義表的原子；如果ai是一個廣義表,則ai是廣義表的子表。 規(guī)定用小寫字母表示原子,用大寫字母表示廣義表的 表名。 廣義表與線性表的區(qū)別： 線性表的成份都是結(jié)構(gòu)上不可分的單個數(shù)據(jù)元素，而廣 義表的成份即可以是單元素，也可以是有結(jié)構(gòu)的表，其定義 是遞歸的定義。,5.4 廣義表,廣義表的長度：廣義表中所含元素的個數(shù)n,n0。 廣義表的深度：廣義表展開后所含的括號的最大層數(shù)。（廣義表中括號嵌套的最大次數(shù)，廣義表中括弧的重數(shù)）,D=( )空表，長度為0，深度為1。 A=(a, (b, c) 長度為2，第一個元素為原子a，第二個元

8、素為子表(b, c)，深度為2。 B=(A, A, D) 長度為3， 其前兩個元素為表A， 第三個元素為空表D，深度為3。 C=(a, C) 長度為2遞歸定義的廣義表，C相當(dāng)于無窮表C=(a,(a, (a,)，深度無限。 遞歸表的深度是無窮值,長度是有限值。 F=(a, (a, b), (a, b), c) 長度為1，深度為4。,廣義表的表頭(Head)和表尾(Tail)： 當(dāng)廣義表非空時，稱第一個元素a1為廣義表的表頭， 其余元素組成的表(a2, a3, ,an)稱為廣義表的表尾。 表頭可能是原子，也可能是廣義表，但表尾一定是廣 義表。 廣義表的圖形表示 用方框表示原子，用圓圈表示廣義表。,

9、A=( ); B=(e); C=(a, (b, c, d) D=(A, B, C); E=(a, (a, b), (a, b), c),2. 廣義表的基本操作 取表頭 GetHead(LS) = a1。 取表尾 GetTail(LS) = (a2,a3,an)。 B=(e) GetHead(B) = e; GetTail(B) = ( ). A=(a, (b, c), d, e) GetHead( GetHead( GetTail(A) = GetHead( GetHead( ( (b, c), d, e) ) ) = GetHead( (b, c), d, e) ) = (b, c). A=( ); B = ( ( ) ) A空表，長度0，深度1，無表頭和表尾； B長度1，深度2，表頭( )，表尾( )。,3. 廣義表的存儲結(jié)構(gòu) 廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu),因此很難為每個廣義表分配固定大小的存儲空間,所以其存儲結(jié)構(gòu)只好采用動態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。 廣義表的頭尾鏈表存儲