第五章數(shù)組和廣義表-ppt課件

1、第五章第五章 數(shù)組和廣義表數(shù)組和廣義表第一節(jié) 數(shù)組的定義數(shù)組的概念數(shù)組的概念 數(shù)組是由一組個(gè)數(shù)固定，類(lèi)型一樣的數(shù)據(jù)元素組成的陣列。數(shù)組是由一組個(gè)數(shù)固定，類(lèi)型一樣的數(shù)據(jù)元素組成的陣列。 以二維數(shù)組為例：二維數(shù)組中的每個(gè)元素都受兩個(gè)線性關(guān)系的以二維數(shù)組為例：二維數(shù)組中的每個(gè)元素都受兩個(gè)線性關(guān)系的約束即行關(guān)系和列關(guān)系，在每個(gè)關(guān)系中，每個(gè)元素約束即行關(guān)系和列關(guān)系，在每個(gè)關(guān)系中，每個(gè)元素aijaij都有且僅有都有且僅有一個(gè)直接前趨，都有且僅有一個(gè)直接后繼。一個(gè)直接前趨，都有且僅有一個(gè)直接后繼。 二維數(shù)組也可看作這樣的線性表，其每一個(gè)數(shù)據(jù)元素也是一個(gè)二維數(shù)組也可看作這樣的線性表，其每一個(gè)數(shù)據(jù)元素也是一個(gè)線

2、性表。線性表。a00a01a02a0,n-1a10a11a12a1,n-1am-1,0am-1,1am-1,2am-1,n-1Amn=Amn=(a00, a01 a0,n-1)，(a10, a11 a1,n-1)，(am-1,0, am-1,1 am-1,n-1)v根本操作根本操作vInitArray(&A,n,bound1,boundn)構(gòu)造一個(gè)構(gòu)造一個(gè)n維維數(shù)組數(shù)組vDestroyArray(&A)銷(xiāo)毀數(shù)組銷(xiāo)毀數(shù)組AvValue(A,&e,index1,indexn)取元素值到取元素值到evAssign(&A,e,index1,indexn)存存e的值到數(shù)組

3、的值到數(shù)組A第二節(jié)第二節(jié) 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)v由于存儲(chǔ)單元是一維構(gòu)造，而數(shù)組是個(gè)多維的構(gòu)造，那么用一組由于存儲(chǔ)單元是一維構(gòu)造，而數(shù)組是個(gè)多維的構(gòu)造，那么用一組延續(xù)存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素就有個(gè)次序商定即行列存儲(chǔ)。延續(xù)存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素就有個(gè)次序商定即行列存儲(chǔ)。a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1第第1行行第第2行行第第m行行Loc(a00)Loc(a10)Loc(am-1,0)以行為主序以行為主序a00a10am-1,0a01a11am-1,1a0,n-1a1,n-1am-1,n-1第第1列列第第2列列第第n列

4、列Loc(a00)Loc(a01)Loc(a0,n-1)以列為主序以列為主序 數(shù)組元素存儲(chǔ)地址的計(jì)算數(shù)組元素存儲(chǔ)地址的計(jì)算 假設(shè)二維數(shù)組假設(shè)二維數(shù)組Amn每個(gè)元素占用每個(gè)元素占用L 個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元， Loc(aij)為元素為元素aij 的存儲(chǔ)地址，的存儲(chǔ)地址，Loc(a00 ) 是是a00存儲(chǔ)位置存儲(chǔ)位置, 也是二維數(shù)組也是二維數(shù)組A的基址。的基址。 假設(shè)以行序?yàn)橹餍虻姆绞酱鎯?chǔ)二維數(shù)組，那么元假設(shè)以行序?yàn)橹餍虻姆绞酱鎯?chǔ)二維數(shù)組，那么元素素aij 的存儲(chǔ)位置可由下式確定：的存儲(chǔ)位置可由下式確定： Loc(aij ) = Loc(a00 ) +n i+j ) L 假設(shè)以列序?yàn)橹餍虻姆绞酱鎯?chǔ)二

5、維數(shù)組，那么元假設(shè)以列序?yàn)橹餍虻姆绞酱鎯?chǔ)二維數(shù)組，那么元素素aij 的存儲(chǔ)位置可由下式確定：的存儲(chǔ)位置可由下式確定： Loc(aij ) = Loc(a00) +m j+i ) L第三節(jié)第三節(jié) 矩陣的緊縮存儲(chǔ)矩陣的緊縮存儲(chǔ)v矩陣是許多科學(xué)與工程計(jì)算問(wèn)題中經(jīng)常涉及到的一矩陣是許多科學(xué)與工程計(jì)算問(wèn)題中經(jīng)常涉及到的一種運(yùn)算對(duì)象。種運(yùn)算對(duì)象。 一個(gè)一個(gè)m m行行n n列的矩陣是一平面陣列，有列的矩陣是一平面陣列，有m mn n個(gè)元素。通常程序員是用二維數(shù)組存儲(chǔ)矩陣。個(gè)元素。通常程序員是用二維數(shù)組存儲(chǔ)矩陣。由于這種存儲(chǔ)方法可以隨機(jī)地訪問(wèn)矩陣的每個(gè)元素，由于這種存儲(chǔ)方法可以隨機(jī)地訪問(wèn)矩陣的每個(gè)元素，因此能

6、較為容易地實(shí)現(xiàn)矩陣的各種運(yùn)算。因此能較為容易地實(shí)現(xiàn)矩陣的各種運(yùn)算。v運(yùn)用中常遇到一些階數(shù)很高的矩陣，矩陣中有許多運(yùn)用中常遇到一些階數(shù)很高的矩陣，矩陣中有許多值一樣的元素或零元素。二維數(shù)組存儲(chǔ)矩陣會(huì)浪費(fèi)值一樣的元素或零元素。二維數(shù)組存儲(chǔ)矩陣會(huì)浪費(fèi)很多的存儲(chǔ)單元。因此，需求運(yùn)用高效的存儲(chǔ)方法，很多的存儲(chǔ)單元。因此，需求運(yùn)用高效的存儲(chǔ)方法，減少數(shù)據(jù)的存儲(chǔ)量，即對(duì)原矩陣，根據(jù)數(shù)據(jù)分布特減少數(shù)據(jù)的存儲(chǔ)量，即對(duì)原矩陣，根據(jù)數(shù)據(jù)分布特征進(jìn)展緊縮存儲(chǔ)。征進(jìn)展緊縮存儲(chǔ)。一、特殊矩陣值一樣元素或者零元素分布有一定規(guī)律的矩陣稱(chēng)為特殊矩陣 例如對(duì)稱(chēng)矩陣、上下三角矩陣都是特殊矩陣。特殊矩陣緊縮存儲(chǔ) (以對(duì)稱(chēng)矩陣為例)

7、對(duì)稱(chēng)矩陣是滿足下面條件的n 階矩陣: aij= aji 0 i,j n-1a11a12a1,na21a22a2,nan,1an,2an,n對(duì)稱(chēng)矩陣元素可以只存儲(chǔ)下三對(duì)稱(chēng)矩陣元素可以只存儲(chǔ)下三角部分，共需角部分，共需 n(n+1)/2 個(gè)單個(gè)單元的空間元的空間( 三角矩陣的存儲(chǔ)方三角矩陣的存儲(chǔ)方式類(lèi)似式類(lèi)似a11a21a22a31a32a33an,1an,n K= 0 1 2 n(n+1)/2-1v以一維數(shù)組以一維數(shù)組sa 作為作為n 階對(duì)稱(chēng)矩陣階對(duì)稱(chēng)矩陣A的存儲(chǔ)構(gòu)造，的存儲(chǔ)構(gòu)造，A中恣意一元素中恣意一元素 aij與它的存儲(chǔ)位置與它的存儲(chǔ)位置 sak 之間存在之間存在著如下對(duì)應(yīng)關(guān)系：著如下對(duì)應(yīng)關(guān)

8、系：k =i(i-1)/2 +j -1 當(dāng)當(dāng) i jj(j-1)/2 +i -1 當(dāng)當(dāng) i j 例如，例如， a32 在在 sa 中的存儲(chǔ)位置是：中的存儲(chǔ)位置是：k=3*(3-1)/2+2-1=4 那么那么sa4= a32a11a21a22a31a32a33an,1an,n K= 0 1 2 3 4 n(n+1)/2-1v緊縮存儲(chǔ)的對(duì)稱(chēng)矩陣的取值算法緊縮存儲(chǔ)的對(duì)稱(chēng)矩陣的取值算法vint get_M(int i, int j)v if(i=j) return(sai*(i+1)/2+j);v else return(saj*(j+1)/2+i);v緊縮存儲(chǔ)的對(duì)稱(chēng)矩陣的緊縮存儲(chǔ)的對(duì)稱(chēng)矩陣的 賦值算

9、法賦值算法void assign_M(int i, int j, int value) if(i=j) sai*(i+1)/2+j=value; else saj*(j+1)/2+i=value;二、稀疏矩陣 有較多值一樣元素或較多零元素，且值一樣元素或者零元素分布沒(méi)有一定規(guī)律的矩陣稱(chēng)為稀疏矩陣。根本操作CreateSMatrix(&M) 創(chuàng)建稀蔬矩陣M；DestroySMatrix(&M) 銷(xiāo)毀稀蔬矩陣M；PrintSMatrix(M) 輸出稀蔬矩陣M；CopySMatrix(M,&T) 復(fù)制稀蔬矩陣M到T；AddSMatrix(M,N,&Q) 求Q=M+N；

10、SubtSMatrix(M,N,&Q) 求Q=M-N;MultSMatrix(M,N,&Q) 求Q=M*N;TransposeSMatrix(M,&T) 求M的轉(zhuǎn)置陣Tv稀疏矩陣的緊縮存儲(chǔ)稀疏矩陣的緊縮存儲(chǔ)v 只存儲(chǔ)稀疏矩陣的非零元，可由表示非零元的三元組及其行列數(shù)只存儲(chǔ)稀疏矩陣的非零元，可由表示非零元的三元組及其行列數(shù)獨(dú)一確定獨(dú)一確定(i,j,aij)(i,j,aij)。012900000000000-3000014000240000018000001500-7000M=ijv121213931-3361443245218611564-7M= ( (1,2,12),

11、(1,3,9), (3,1,-3),(3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) )加上行、列數(shù)加上行、列數(shù)6，7 v三元組的順序表v 假設(shè)以順序存儲(chǔ)構(gòu)造來(lái)表示三元組表，那么可得稀疏矩陣的一種緊縮存儲(chǔ)方式我們稱(chēng)之為三元組順序表(行序表示)。#define MAXSIZE 12500 /假設(shè)非零元個(gè)數(shù)的最大值假設(shè)非零元個(gè)數(shù)的最大值typedef struct int i,j; /非零元的行列下標(biāo)非零元的行列下標(biāo) ElemType e; Triple;typedef struct Triple dataMAXSIZE+1;/非零元三元組表，非零元

12、三元組表，data0未用未用 int mu,nu,tu; /矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù) TSMatrix;munutuije轉(zhuǎn)置運(yùn)算算法轉(zhuǎn)置運(yùn)算算法 轉(zhuǎn)置運(yùn)算是一種最常用的矩陣運(yùn)算。對(duì)于一個(gè)轉(zhuǎn)置運(yùn)算是一種最常用的矩陣運(yùn)算。對(duì)于一個(gè) m 行行 n 列的矩陣列的矩陣 M，它的轉(zhuǎn)，它的轉(zhuǎn)置矩陣置矩陣 T是一個(gè)是一個(gè)n行行m列的矩陣。列的矩陣。 例如，以下圖中的矩陣?yán)?，以下圖中的矩陣M和和T互為轉(zhuǎn)置矩陣?；檗D(zhuǎn)置矩陣。012900000000000-3000014000240000018000001500-7000M=T=00-300151200018090024000

13、0000-70000000014000000000算法分析：算法分析：1 1將矩陣的行數(shù)和列數(shù)的值交換將矩陣的行數(shù)和列數(shù)的值交換2 2將每一個(gè)三元組的將每一個(gè)三元組的i i 和和 j j互相互換互相互換3 3重排三元組之間的次序重排三元組之間的次序678MT768ijv121213931-3361443245218611564-7i,j互換互換ijv211231913-3631434242518161546-7重排重排ijv13-3161521122518319342446-76314算法實(shí)現(xiàn)算法實(shí)現(xiàn)Status TransposeSMatrix(TSMatrix M,TSMatrix &am

14、p;T) T.mu=M.nu; T.nu=M.mu;T.tu=M.tu; if (T.tu) q=1; for(col=1;col=M.nu;+col) for(p=1;p=M.tu;+p) if (M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; return OK;算法的時(shí)間重雜度算法的時(shí)間重雜度為：為：O(M.nu*M.tu)n十字鍵表存儲(chǔ)緊縮稀疏矩陣n 在鏈表中，每個(gè)非零元可用一個(gè)含5個(gè)域的結(jié)點(diǎn)表示，其中i,j,e用來(lái)表示非零元的行、列、值，向右域right用以鏈接同一行中

15、下一個(gè)非零元，向下域down用以鏈接同一列中下一個(gè)非零元。再建兩個(gè)頭結(jié)點(diǎn)分別指示行和列。30050-1002000M=11322-1145312M.cheadM.rhead第四節(jié)第四節(jié) 廣義表的定義廣義表的定義v概念概念v 廣義表也稱(chēng)為列表，是線性表的一種擴(kuò)展，也是數(shù)據(jù)元素的有限序廣義表也稱(chēng)為列表，是線性表的一種擴(kuò)展，也是數(shù)據(jù)元素的有限序列。列。 記作：記作：LS= (d0, d1, d2, dn-1)LS= (d0, d1, d2, dn-1)。其中。其中didi既可以是單個(gè)元素，既可以是單個(gè)元素，也可以是廣義表。也可以是廣義表。v闡明闡明v廣義表的定義是一個(gè)遞歸定義，由于在描畫(huà)廣義表時(shí)又用

16、到了廣義表；廣義表的定義是一個(gè)遞歸定義，由于在描畫(huà)廣義表時(shí)又用到了廣義表；v在線性表中數(shù)據(jù)元素是單個(gè)元素，而在廣義表中，在線性表中數(shù)據(jù)元素是單個(gè)元素，而在廣義表中， 元素可以是單個(gè)元元素可以是單個(gè)元素素, , 稱(chēng)為單元素稱(chēng)為單元素( (原子原子) )，也可以是廣義表，稱(chēng)為廣義表的子表；，也可以是廣義表，稱(chēng)為廣義表的子表；vn n 是廣義表長(zhǎng)度；是廣義表長(zhǎng)度；v下面是一些廣義表的例子；下面是一些廣義表的例子； A = ( ) A = ( )空表，表長(zhǎng)為空表，表長(zhǎng)為0 0；E=( a ,E ) E=( a ,E ) 遞歸表遞歸表. . B = (a,(b,c,d) B B = (a,(b,c,d)

17、 B的表長(zhǎng)為的表長(zhǎng)為2 2，兩個(gè)元素分別為，兩個(gè)元素分別為 a a 和子表和子表b,c,d)b,c,d)； C = (e) C C = (e) C中只需一個(gè)元素中只需一個(gè)元素e e，表長(zhǎng)為，表長(zhǎng)為1 1；D=(A,B,C)D=(A,B,C) 假設(shè)廣義表不空，那么可分成表頭和表尾，反之，一對(duì)表頭假設(shè)廣義表不空，那么可分成表頭和表尾，反之，一對(duì)表頭和表尾可獨(dú)一確定廣義表。和表尾可獨(dú)一確定廣義表。 對(duì)非空廣義表：稱(chēng)第一個(gè)元素為對(duì)非空廣義表：稱(chēng)第一個(gè)元素為L(zhǎng)S的表頭，其他元素組成的表頭，其他元素組成的表稱(chēng)為的表稱(chēng)為L(zhǎng)S的表尾；的表尾； B = (a,(b,c,d) 表頭：表頭：a 表尾表尾 (b,c,d) 即即 HEADB=a, TAIL(B)=(b,c,d), C = (e) 表頭：表頭：e 表尾表尾 ( ) D = (A,B,C,f ) 表頭：表頭：A 表尾表尾 (B,C,f )v從上述定義和例子可推出列