數(shù)據(jù)結(jié)構(gòu) 第5章數(shù)組和廣義表

1、1,5.1 數(shù)組的定義,數(shù)組： 由一組名字相同、下標(biāo)不同的變量構(gòu)成,注意： 本章所討論的數(shù)組與高級(jí)語言中的數(shù)組有所區(qū)別：高級(jí)語言中的數(shù)組是順序結(jié)構(gòu)；而本章的數(shù)組既可以是順序的，也可以是鏈?zhǔn)浇Y(jié)構(gòu)，用戶可根據(jù)需要選擇。,,答：對(duì)的。因?yàn)椋孩?數(shù)組中各元素具有統(tǒng)一的類型；② 數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素

2、值的操作。,討論：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單”，對(duì)嗎？,2,二維數(shù)組的特點(diǎn)：,一維數(shù)組的特點(diǎn)：,1個(gè)下標(biāo)，ai 是ai+1的直接前驅(qū),2個(gè)下標(biāo)，每個(gè)元素ai,j受到兩個(gè)關(guān)系（行關(guān)系和列關(guān)系）的約束：,一個(gè)m×n的二維數(shù)組可以看成是m行的一維數(shù)組，或者n列的一維數(shù)組。,N維數(shù)組的特點(diǎn)：,n個(gè)下標(biāo)，每個(gè)元素受到n個(gè)關(guān)系約束,一個(gè)n維數(shù)組可以看成是由若干個(gè)n－1維數(shù)組組成的線性表。,,3,N維數(shù)組的數(shù)據(jù)類型定義,n_ARRA

3、Y = (D, R),其中：,Ri = {| aj1,j2,…ji…jn , aj1,j2,…ji+1…jn ?D },數(shù)據(jù)關(guān)系：R = { R1 ,R2，…. Rn },數(shù)據(jù)對(duì)象：D = {aj1,j2…jn| ji為數(shù)組元素的第i 維下標(biāo) ，aj1,j2…jn ?Elemset},數(shù)組的抽象數(shù)據(jù)類型定義略，參見教材P90,構(gòu)造數(shù)組、銷毀數(shù)組、讀數(shù)組元素、寫數(shù)組元素,基本操

4、作：,,4,5.2 數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn),問題：計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)是一維的，而數(shù)組一般是多維的，怎樣存放？解決辦法：事先約定按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存入存儲(chǔ)器中。例如：在二維數(shù)組中，我們既可以規(guī)定按行存儲(chǔ)，也可以規(guī)定按列存儲(chǔ)。,注意：若規(guī)定好了次序，則數(shù)組中任意一個(gè)元素的存放地址便有規(guī)律可尋，可形成地址計(jì)算公式；約定的次序不同，則計(jì)算元素地址的公式也有所不同；C和PASCAL中一般采用行優(yōu)先順序；

5、FORTRAN采用列優(yōu)先。,,5,補(bǔ)充：計(jì)算二維數(shù)組元素地址的通式設(shè)一般的二維數(shù)組是A[c1..d1, c2..d2]，這里c1,c2不一定是0。,無論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時(shí)求出任一元素的地址（這樣數(shù)組中的任一元素便可以隨機(jī)存?。。?二維數(shù)組列優(yōu)先存儲(chǔ)的通式為：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L,單個(gè)元素長度,,aij之前的行數(shù),數(shù)組基址,總列數(shù)，

6、即第2維長度,aij本行前面的元素個(gè)數(shù),①開始結(jié)點(diǎn)的存放地址（即基地址）②維數(shù)和每維的上、下界；③每個(gè)數(shù)組元素所占用的單元數(shù),則行優(yōu)先存儲(chǔ)時(shí)的地址公式為：LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L,6,例2：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K , 按列存儲(chǔ)的公式是？,Loc(aij)=Loc(

7、a11)+[(j-1)*m+(i-1)]*K （盡管是方陣，但公式仍不同）,例1〖軟考題〗：一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是 個(gè)字節(jié)。,288,例3：〖00年計(jì)算機(jī)系考研題〗設(shè)數(shù)組a[1…60, 1…70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為

8、 。,8950,LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝8950,答：請注意審題！,利用列優(yōu)先通式：,,,答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288,7,Loc(j1,j2,…jn)=LOC(0,0,…0)＋,若是

9、N維數(shù)組，其中任一元素的地址該如何計(jì)算？,其中Cn=L, Ci-1=bi×Ci， 1<i≤n,一個(gè)元素長度,數(shù)組基址,前面若干元素占用的地址字節(jié)總數(shù),第i維長度,與所存元素個(gè)數(shù)有關(guān)的系數(shù)，可用遞推法求出,,教材已給出低維優(yōu)先的地址計(jì)算公式，見P93（5-2）式該式稱為n維數(shù)組的映像函數(shù)：,8,#define MAX_ARRAY_DIM 8 //假設(shè)最大維數(shù)為8 typedef struct{

10、 ELemType *base; //數(shù)組元素基址 int dim; //數(shù)組維數(shù) int *bound; //數(shù)組各維長度信息保存區(qū)基址 int *constants; //數(shù)組映像函數(shù)常量的基址 }Array;,,即Ci信息保存區(qū),數(shù)組的基本操作函數(shù)說明（有5個(gè)）（請閱讀教材P93

11、-95）,N維數(shù)組的順序存儲(chǔ)表示（見教材P93）,9,Status InitArray(Array &A,int dim,…){ //若維數(shù)dim和各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A并返回OK if(dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim * sizeof(int)); if(!a.bounds) e

12、xit(OVERFLOW); //若各維長度合法，則存入A.bounds,并求出A的元素總數(shù)elemtotal elemtotal=1; va_start(ap.dim); //ap為va_list類型，是存放變長參數(shù)表信息的類型,數(shù)組的基本操作函數(shù)說明（5個(gè)） （見教材P93-95）,,10,for(i=0;i=0;--i) A.constants[i]=A.bounds[i+1]*A.constant

13、s[i+1]; return OK; },,11,,數(shù)組基址指針,各維長度保存區(qū)指針,映像函數(shù)Ci保存區(qū)指針,Status DestroyArray(Array &A){ //銷毀數(shù)組A if ( ! A . base ) return ERROR; free( A . base ); A . base = NULL; if ( ! A.bounds )

14、 return ERROR; free( A . bounds ); A . bounds = NULL; if ( !A.constants ) return ERROR; free ( A. constants ) ; A. constants = NULL; return OK; },12,Status Locate(Array A,va_list ap,int &off

15、){ //若ap指示的各下標(biāo)值合法，則求出該元素在A中，相對(duì)地址off off=0; for(i=0;iA.bounds[i]) return OVERFLOW; off+=A.constants[i] *ind; } return OK; },,13,Status Value(Array A,ElemType &e,…){ //A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值

16、，若各下標(biāo)不超界，則e賦值為所指定的A的元素值，即將指定元素值讀到e變量中。 va_start(ap,e); if((result=Locate(A,ap,off))<=0) return result; e=*(A.base+off); return OK; },,14,Status Assign(Array &A,ElemType e,…){ //A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)

17、值，若各下標(biāo)不超界，則e的值賦為所指定的A的元素值，即：將e值寫入指定數(shù)組單元。 va_start(ap,e); if((result=Locate(A,ap,off))<=0) return result; *(A.base+off)=e; return OK; },15,順序存儲(chǔ)方式：按低地址優(yōu)先（或高地址優(yōu)先）順序存入一維數(shù)組。,行指針向量,,補(bǔ)充：鏈?zhǔn)酱鎯?chǔ)方式：用帶行指針向量的單鏈表來表示。,注

18、：數(shù)組的運(yùn)算參見下一節(jié)實(shí)例（稀疏矩陣的轉(zhuǎn)置）,（難點(diǎn)是多維數(shù)組與一維數(shù)組的地址映射關(guān)系）,16,5.3 矩陣的壓縮存儲(chǔ),討論：1. 什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2. 所有二維數(shù)組（矩陣）都能壓縮嗎？未必，要看矩陣是否具備以上壓縮條件。3. 什么樣的矩陣具備以上壓縮條件？ 一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。4. 什么叫稀疏

19、矩陣？矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）,重點(diǎn)介紹稀疏矩陣的壓縮和相應(yīng)的操作。,,17,例：對(duì)稱矩陣的壓縮存儲(chǔ),設(shè)有一個(gè) n?n 的對(duì)稱矩陣 A。,,在矩陣中，aij = aji,18,,,,,,為節(jié)約存儲(chǔ)，只存對(duì)角線及對(duì)角線以上的元素，或者只存對(duì)角線及對(duì)角線以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。,下三角矩陣,19,,,,,,上三角矩陣,把它們按行存放于一個(gè)一維數(shù)組 B 中，稱之為對(duì)稱矩陣 A 的壓縮存儲(chǔ)方式。數(shù)

20、組 B 共有 n + ( n - 1 ) + ??? + 1 = n*(n+1)/2 個(gè)元素。,20,,,,,,下三角矩陣,,B a11 a21 a22 a31 a32 a33 a41 a42 a43 …… ann,,,,,,,,,,,0 1 2 3 4 5 6 7 8 n(n+1)

21、/2-1,,若 i ? j, 數(shù)組元素A[i][j]在數(shù)組B中的存放位置為 1 + 2 + ??? + (i-1) + (j-1) = (i - 1)* i / 2 + j-1,,,前i行元素總數(shù) 第i行第j個(gè)元素前元素個(gè)數(shù),,,21,若 i < j，數(shù)組元素 A[i][j] 在矩陣的上三角部分, 在數(shù)組 B 中沒有存放，可以找它的對(duì)稱元素A[j][i] 一維數(shù)組B中的數(shù)據(jù)元素和方陣A中的元素之間存在著下列一一對(duì)應(yīng)

22、的關(guān)系,22,,,,,上三角矩陣,,B a11 a12 a13 a14 a22 a23 a24 a33 a34 a44,,,,,,,,,,,0 1 2 3 4 5 6 7 8 9,若i ? j，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為n + (n-1) + (n-2) + ??? + (n-i+1) + j-i,,前i行元素

23、總數(shù) 第i行第j個(gè)元素前元素個(gè)數(shù),,,n = 4,23,,若 i ? j，數(shù)組元素A[i][j]在數(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ù)組元素A[i][j]在矩陣的下三角部分，在數(shù)組 B 中沒有存放。因此，找它的對(duì)稱

24、元素A[j][i]。 A[j][i]在數(shù)組 B 的第 (2*n-j-1) * j / 2 + i 的位置中找到。,24,5.3.2 稀疏矩陣,問題：如果只存儲(chǔ)稀疏矩陣中的非零元素，那這些元素的位置信息該如何表示？解決思路：對(duì)每個(gè)非零元素增開若干存儲(chǔ)單元，例如存放其所在的行號(hào)和列號(hào)，便可準(zhǔn)確反映該元素所在位置。實(shí)現(xiàn)方法：將每個(gè)非零元素用一個(gè)三元組（i，j，aij）來表示，則每個(gè)稀疏矩陣可用一個(gè)三元組表來表示。,問題：稀

25、疏矩陣的存儲(chǔ)和操作 ？,,,25,例1 ：,三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 、 和 。,行下標(biāo),列下標(biāo),元素值,例2：寫出右圖所示稀疏矩陣的壓縮存儲(chǔ)形式。,,(( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)， (4,3,24)， (5,2,18)

26、 ，(6,1,15)， (6,4,-7)),法1：用線性表表示：,(6,6),26,法2：用三元組順序表表示：P.98,,注意：為更可靠描述，通常再加一行“總體”信息：即總行數(shù)、總列數(shù)、非零元素總個(gè)數(shù),稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)：將失去隨機(jī)存取功能 :-(,27,#define MAXSIZE 125000 //設(shè)非零元素最大個(gè)數(shù)125000 typedef struct{ int i; //元素行號(hào)

27、int j; //元素列號(hào) ElemType e; //元素值}Triple; typedef struct{ Triple data[MAXSIZE+1]; //三元組表，以行為主序存入一維向量 data[ ]中 int mu; //矩陣總行數(shù) int nu; //矩陣總列數(shù) int tu; //矩陣中非零元素總

28、個(gè)數(shù)}TsMatrix;,,三元組表的順序存儲(chǔ)表示（見教材P98）：,//一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義,//整個(gè)三元組表的定義,28,法三：用帶輔助向量的三元組表示。,方法： 增加1個(gè)輔助向量： 記錄稀疏矩陣中每行第一個(gè)非0元素在三元組中的行號(hào)，用POS（i）表示。,,7,6,5,3,1,3,用途：通過三元組高效訪問稀疏矩陣中任一非零元素。,規(guī)律：POS(1)＝1 POS(i)＝POS(i-1)+NUM(i-1)

29、,,注：書上稱為行邏輯鏈接的三元組順序表。 教材P100,29,行邏輯鏈接的三元組順序表的結(jié)構(gòu)定義,typedef struct { Triple data[MAXSIZE+1]; /* 非零元三元組表,data[0]未用 */ int rpos[MAXRC+1]; /* 各行第一個(gè)非零元素的位置表*/ int mu,nu,tu; /* 矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù) */

30、 }RLSMatrix;,30,法四：用十字鏈表表示 教材P100,,用途：方便稀疏矩陣的加減運(yùn)算；方法：每個(gè)非0元素占用5個(gè)域。,同一列中下一非零元素的指針,同一行中下一非零元素的指針,十字鏈表的特點(diǎn)：①每行非零元素鏈接成帶表頭結(jié)點(diǎn)的循環(huán)鏈表；②每列非零元素也鏈接成帶表頭結(jié)點(diǎn)的循環(huán)鏈表。則每個(gè)非零元素既是行循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)；又是列循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，即呈十字鏈狀。,,31,稀疏矩陣的十字鏈表存儲(chǔ)表示,typedef st

31、ruct OLNode { int i,j; /* 該非零元的行和列下標(biāo) */ ElemType e; /* 非零元素值 */ struct OLNode *right,*down; /* 該非零元所在行表和列表的后繼鏈域 */ }OLNode,*OLink; typedef struct { OLink *rhead,*chead; /* 行和列鏈表頭指針向量基址,由

32、CreatSMatrix_OL()分配 */ int mu,nu,tu; /* 稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù) */ }CrossList;,32,十字鏈表表示稀疏矩陣實(shí)例,33,二、稀疏矩陣的操作,,,三元組表a.data,三元組表b.data,M,T,（以轉(zhuǎn)置運(yùn)算為例）,目的：,,34,答：肯定不正確！除了： （1）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的i和j互換）；還應(yīng)該：（2）T的總行數(shù)mu和

33、總列數(shù)nu與M值不同（互換）； （3）重排三元組內(nèi)元素順序，使轉(zhuǎn)置后的三元組也按行（或列）為主序有規(guī)律的排列。,上述（1）和（2）容易實(shí)現(xiàn)，難點(diǎn)在（3）。,若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種說法正確嗎？,,,有兩種實(shí)現(xiàn)方法,壓縮轉(zhuǎn)置(壓縮)快速轉(zhuǎn)置,,提問：,35,方法1：壓縮轉(zhuǎn)置,思路：反復(fù)掃描a.data中的列序，從小到大依次進(jìn)行轉(zhuǎn)置。,三元組

34、表a.data,三元組表b.data,,1,1,2,2,col,q,1,2,3,4,36,Status TransPoseSMatrix(TSMatrix M, TSMatrix &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

35、=1; p<=M.tu; p++) {if (M.data[p].j==col) {T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].value=M.data[p].value; q++; } } } } retu

36、rn OK;} //TranposeSMatrix;,壓縮轉(zhuǎn)置算法描述：（見教材P99）,,//用三元組表存放稀疏矩陣M，求M的轉(zhuǎn)置矩陣T,//q是轉(zhuǎn)置矩陣T的結(jié)點(diǎn)編號(hào),//col是掃描M三元表列序的變量,//p是M三元表中結(jié)點(diǎn)編號(hào),37,1、主要時(shí)間消耗在查找M.data[p].j=col的元素，由兩重循環(huán)完成: for(col=1; col<=M.nu; col++) 循環(huán)次數(shù)＝nu

37、 {for(p=1; p<=M.tu; p++) 循環(huán)次數(shù)＝tu所以該算法的時(shí)間復(fù)雜度為O(nu*tu) ----即M的列數(shù)與M中非零元素的個(gè)數(shù)之積最惡劣情況：M中全是非零元素，此時(shí)tu=mu*nu， 時(shí)間復(fù)雜度為 O(nu2*mu )注：若M中基本上是非零元素時(shí)，即使用非壓縮傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度也不過是O(nu*mu) （程序見教材P99）結(jié)論：壓縮轉(zhuǎn)置

38、算法不能濫用。前提：僅適用于非零元素個(gè)數(shù)很少（即tu<<mu*nu）的情況。,壓縮轉(zhuǎn)置算法的效率分析：,,38,方法2 快速轉(zhuǎn)置,三元組表a.data,三元組表b.data,思路：依次把a(bǔ).data中的元素直接送入b.data的恰當(dāng)位置上（即M三元組的p指針不回溯）。,,關(guān)鍵：怎樣尋找b.data的“恰當(dāng)”位置？,q,3,5,39,如果能預(yù)知M矩陣每一列(即T的每一行)的非零元素個(gè)數(shù)，又能預(yù)知第一個(gè)非零

39、元素在b.data中的位置,則掃描a.data時(shí)便可以將每個(gè)元素準(zhǔn)確定位（因?yàn)橐阎舾蓞⒖键c(diǎn)）。,,,技巧：利用帶輔助向量的三元組表，它正好攜帶每行（或列）的非零元素個(gè)數(shù) NUM(i)以及每行（或列）的第一個(gè)非零元素在三元組表中的位置POS(i) 等信息。,設(shè)計(jì)思路：,不過我們需要的是按列生成的M矩陣的輔助向量。,規(guī)律：POS(1)＝1POS(i)＝POS(i-1)+NUM(i-1),請回憶：,請注意a.data特征：每列首個(gè)非零元素

40、必定先被掃描到。,40,令：M中的列變量用col表示； num[ col ]：存放M中第col 列中非0元素個(gè)數(shù)， cpot[ col ]：存放M中第col列的第一個(gè)非0元素的位置， （即b.data中待計(jì)算的“恰當(dāng)”位置所需參考點(diǎn)）,討論：按列優(yōu)先的輔助向量求出后，下一步該如何操作？由a.data中每個(gè)元素的列信息，即可直接查出b.data中的重要參考點(diǎn)之位置，進(jìn)而可確定當(dāng)前元素之位置

41、！,規(guī)律： cpot(1)＝1cpot[col] ＝ cpot[col-1] + num[col-1],M,,3 5 7 8 8,,col 1 2 3 4 5 6,41,Status FastTransposeSMatrix（TSMatirx M, TSMatirx &T）{ T.mu = M.nu ;T .nu = M.mu ; T

42、.tu = M.tu ; if ( T.tu ) {for(col = 1; col <=M.nu; col++) num[col] =0; for( i = 1; i <=M.tu; i ++) {col =M.data[ i ] .j ; ++num [col] ;} cpos[ 1 ] =1; for(col = 2; col <=M.nu; col++) cpos[col ]=cpos[col-1

43、]+num [col-1 ] ; for( p =1; p <=M.tu ; p ++ ) { col =M.data[ p ]. j ; q =cpos [ col ]; T.data[q].i = M.data[p]. j; T.data[q].j = M.data[p]. i; T.data[q].

44、 value = M.data[p]. value; + + cpos[col] ; } //for} //ifreturn OK; } //FastTranposeSMatrix;,快速轉(zhuǎn)置算法描述：,//M用順序存儲(chǔ)表示，求M的轉(zhuǎn)置矩陣T,,//先統(tǒng)計(jì)每列非零元素個(gè)數(shù),//再生成每列首元位置輔助向量表,//p指向a.data，循環(huán)次數(shù)為非0元素總個(gè)數(shù)tu,//查輔助向量表得q

45、，即T中位置,//重要語句！修改向量表中列坐標(biāo)值，供同一列下一非零元素定位之用！,42,1. 與常規(guī)算法相比，附加了生成輔助向量表的工作。增開了2個(gè)長度為列長的數(shù)組(num[ ]和cpos[ ]）。,傳統(tǒng)轉(zhuǎn)置：O(mu*nu) 壓縮轉(zhuǎn)置：O(mu*tu) 壓縮快速轉(zhuǎn)置：O(nu+tu)——犧牲空間效率換時(shí)間效率。,快速轉(zhuǎn)置算法的效率分析：,,2. 從時(shí)間上，此算法用了4個(gè)并列的單循環(huán)，而且其中前3個(gè)單循環(huán)都是用來產(chǎn)生輔助

46、向量表的。 for(col = 1; col <=M.nu; col++) 循環(huán)次數(shù)＝nu; for( i = 1; i <=M.tu; i ++) 循環(huán)次數(shù)＝tu; for(col = 2; col <=M.nu; col++) 循環(huán)次數(shù)＝nu; for( p =1; p <=M.tu ; p ++ ) 循環(huán)次數(shù)

47、＝tu; 該算法的時(shí)間復(fù)雜度＝(nu*2)+(tu*2)=O(nu+tu）,討論：最惡劣情況是tu=nu*mu(即矩陣中全部是非零元素），而此時(shí)的時(shí)間復(fù)雜度也只是O(mu*nu)，并未超過傳統(tǒng)轉(zhuǎn)置算法的時(shí)間復(fù)雜度。,小結(jié)：,稀疏矩陣相乘的算法見教材P101-103,43,5.4 廣義表的定義,廣義表是線性表的推廣，也稱為列表（lists）記為： LS = ( a1 , a2 , ……， an ),廣義表名

48、 表頭(Head） 表尾 (Tail),,,1、定義：,① 第一個(gè)元素是表頭，而其余元素組成的表稱為表尾；② 用小寫字母表示原子類型，用大寫字母表示列表。,n是表長,在廣義表中約定：,,,討論：廣義表與線性表的區(qū)別和聯(lián)系？ 廣義表中元素既可以是原子類型，也可以是列表；當(dāng)每個(gè)元素都為原子且類型相同時(shí)，就是線性表。,44,2、特點(diǎn)：,有次序性有長度有深度可遞歸可共享,一個(gè)直接前驅(qū)和一個(gè)直接后繼＝表中元素個(gè)數(shù)

49、＝表中括號(hào)的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享,,特別提示：任何一個(gè)非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。,45,E=(a,E)=(a,(a,E))= (a,(a,(a,…….)))，E為遞歸表,1）A =( )2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(a, E),例1：求下列廣義表的長度。,n=0，因?yàn)锳是空表n

50、=1，表中元素e是原子n=2，a 為原子，(b,c,d)為子表n=3，3個(gè)元素都是子表n=2，a 為原子，E為子表,D=(A,B,C)=(( ),(e),(a,(b,c,d)))，共享表,,46,② A=( a , (b, A) ),例2：試用圖形表示下列廣義表.（設(shè) 代表原子， 代表子表）,,e,① D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) ),,①的長度為3，深度為3,②的長度為2，深度為∞

51、,47,介紹兩種特殊的基本操作：GetHead( L) ——取表頭(可能是原子或列表);GetTail(L ) ——取表尾(一定是列表) 。,,廣義表的抽象數(shù)據(jù)類型定義見教材P107-108,48,1. GetTail【(b, k, p, h)】＝ ; 2. GetHead【( (a,b), (c,d) )】＝ ;

52、3. GetTail【( (a,b), (c,d) )】＝ ; 4. GetTail【 GetHead【((a,b),(c,d))】】＝ ;,例：求下列廣義表操作的結(jié)果（嚴(yán)題集5.10②）,(k, p, h),（b）,(a,b),5. GetTail【（e）】＝ ; 6. GetHead 【 ( ( )

53、 )】＝ .7. GetTail【 ( ( ) ) 】＝ .,( ),(a,b),( ),,( ),((c,d)),49,5.5 廣義表的存儲(chǔ)結(jié)構(gòu),由于廣義表的元素可以是不同結(jié)構(gòu)（原子或列表），難以用順序存儲(chǔ)結(jié)構(gòu)表示 ，通常用鏈?zhǔn)浇Y(jié)構(gòu)，每個(gè)元素用一個(gè)結(jié)點(diǎn)表示。,1.原子結(jié)點(diǎn)：表示原子，可設(shè)2個(gè)域或3個(gè)域，依習(xí)慣而選。,注意：列表的“元素”還可以是列表，所以結(jié)點(diǎn)可能有兩種形式

54、,,法2：標(biāo)志域、值域、表尾指針,指向下一結(jié)點(diǎn),法1：標(biāo)志域，數(shù)值域,50,2.表結(jié)點(diǎn)：表示列表，若表不空，則可分解為表頭和表尾，用3個(gè)域表示：標(biāo)志域，表頭指針，表尾指針。,① A =( ),③ C =( a ,( b , c , d ) ),例：,② B=( e ),,A=NULL,指向子表,指向下一結(jié)點(diǎn),51,⑤ E=(a, E),④ D=( A , B ,C )＝(( ),(e),(a,(b,c,d))),,本章結(jié)束,（參見教