1、關(guān)于數(shù)據(jù)結(jié)構(gòu)數(shù)組與廣義表第一張，PPT共四十六頁，創(chuàng)作于2022年6月第五章 數(shù)組和廣義表本章前討論的線性結(jié)構(gòu)數(shù)據(jù)元素都是非結(jié)構(gòu)的原子類型，元素值不可再分。本章討論了兩種數(shù)據(jù)結(jié)構(gòu)數(shù)組和廣義表。作為線性表的擴(kuò)展，表中的數(shù)據(jù)元素也是一種數(shù)據(jù)結(jié)構(gòu)。數(shù)組這種數(shù)據(jù)結(jié)構(gòu)可以看成是線性表的推廣。廣義表是另一種推廣形式的線性表，是一種靈活的數(shù)據(jù)結(jié)構(gòu)，在許多方面有廣泛的應(yīng)用。第二張，PPT共四十六頁，創(chuàng)作于2022年6月2知識結(jié)構(gòu)圖數(shù)組與廣義表 數(shù) 組廣義表類型定義表示方法稀疏矩陣特殊矩陣存儲結(jié)構(gòu)邏輯結(jié)構(gòu) 應(yīng)用壓縮存儲各種運(yùn)算第三張，PPT共四十六頁，創(chuàng)作于2022年6月35.1 數(shù)組數(shù)組是n(n1)個相同數(shù)據(jù)

2、類型的數(shù)據(jù)元素a0,a1,a2,.,an-1構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限序列。數(shù)組中任意一個元素可以用該元素在數(shù)組中的位置來表示，數(shù)組元素的位置通常稱作數(shù)組的下標(biāo)。第四張，PPT共四十六頁，創(chuàng)作于2022年6月45.1.1 數(shù)組的概念及其與線性表的關(guān)系 由定義知，n維數(shù)組中有b1b2 bn個數(shù)據(jù)元素，每個數(shù)據(jù)元素都受到n維關(guān)系的約束。直觀的n維數(shù)組 以二維數(shù)組為例討論。將二維數(shù)組看成是一個定長的線性表，其每個元素又是一個定長的線性表。 設(shè)二維數(shù)組A=(aij)mn，則 A=(1，2，p) (p=m或n)其中每個數(shù)據(jù)元素j是一個列向量(線性表) ： j =(a1j ，a2j ，amj)

3、 1jn或是一個行向量： i =(ai1 ，ai2 ，ain) 1im如圖5-1所示。第五張，PPT共四十六頁，創(chuàng)作于2022年6月5 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=a11 a12 a1na21 a22 a2nam1 am2 amna11 a21 am1a12 a22 am2a1n a2n amnA=圖5-1 二維數(shù)組圖例形式(a) 矩陣表示形式(b)行向量的一維數(shù)組形式(c)列向量的一維數(shù)組形式第六張，PPT共四十六頁，創(chuàng)作于2022年6月6n維數(shù)組的特點(diǎn)每個數(shù)據(jù)元素都受著n個關(guān)系的約束；在每個關(guān)系中，元素 (0=ji=bi-2)都有一個直接

4、后繼;數(shù)據(jù)元素都必須屬于同一數(shù)據(jù)類型;n=1時，退化為定長的線性表；n維數(shù)組可以看成是線性表的推廣。數(shù)組一旦被定義，則維數(shù)已定，對于數(shù)組的操作只有存取元素和修改元素。(一旦建立了數(shù)組，數(shù)組中的元素個數(shù)和元素之間的關(guān)系就不再發(fā)生變動)數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。（存儲時需要一個次序約定）第七張，PPT共四十六頁，創(chuàng)作于2022年6月75.1.2 數(shù)組的順序存儲結(jié)構(gòu)數(shù)組的實(shí)現(xiàn)機(jī)制a的內(nèi)存單元地址每個元素所需的字節(jié)個數(shù)第八張，PPT共四十六頁，創(chuàng)作于2022年6月8行向量 下標(biāo) i 頁向量 下標(biāo) i列向量 下標(biāo) j 行向量 下標(biāo) j 列向量 下標(biāo) k二維數(shù)組 三維數(shù)組第九張，PPT

5、共四十六頁，創(chuàng)作于2022年6月9數(shù)組的順序表示-小結(jié)n維數(shù)組的特點(diǎn):數(shù)據(jù)元素同屬于一種數(shù)據(jù)類型；數(shù)組一旦被定義，則維數(shù)和各維長度不能改變；數(shù)組操作只有引用型操作，沒有加工型操作；數(shù)組是多維結(jié)構(gòu)，但存儲空間是一維結(jié)構(gòu)。數(shù)組順序表示的特點(diǎn)存儲單元地址連續(xù)（需要一段連續(xù)空間）存儲規(guī)則（以行（列）為主序）決定元素實(shí)際存儲位置隨機(jī)存取存儲密度最大（100%）第十張，PPT共四十六頁，創(chuàng)作于2022年6月105.2 矩陣的壓縮存儲 在科學(xué)與工程計算問題中，矩陣是一種常用的數(shù)學(xué)對象，在高級語言編程時，通常將一個矩陣描述為一個二維數(shù)組。這樣，可以對其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡單。 對于高階矩陣，

6、若其中非零元素呈某種規(guī)律分布或者矩陣中有大量的零元素，若仍然用常規(guī)方法存儲，可能存儲重復(fù)的非零元素或零元素，將造成存儲空間的大量浪費(fèi)。對這類矩陣進(jìn)行壓縮存儲： 多個相同的非零元素只分配一個存儲空間； 零元素不分配空間。第十一張，PPT共四十六頁，創(chuàng)作于2022年6月115.2.1 特殊矩陣的壓縮存儲1.對稱矩陣n階矩陣A中元素滿足性質(zhì)aij=aji (1i,jn)。（即aij=aji,1=i,j=n）a11a21a22aijannLTA0.n(n+1)/2-1k= 0 1 2 n(n+1)/2-1第十二張，PPT共四十六頁，創(chuàng)作于2022年6月12k的含義：按行優(yōu)先，是第k個（從0開始）156

7、75289683079041526837904i=3j=2k=4公式的推導(dǎo)（下三角）i=3，j=2則前面有一個i-1行的完整三角形，共有元素 (1+i-1)(i-1)/2 = i(i-1)/2個另外，同一行，前面還有j-1個元素所以，k = i(i-1)/2+j-1第十三張，PPT共四十六頁，創(chuàng)作于2022年6月132、三角矩陣 以主對角線劃分， n階三角矩陣有n階上三角矩陣和n階下三角矩陣兩種。 n階上三角矩陣的下三角（不包括主對角線）中的元素均為0（或常數(shù)）。n階下三角矩陣正好相反，它的主對角線上方均為0（或常數(shù)）。 注：在大多數(shù)情況下， n階三角矩陣常數(shù)為零。第十四張，PPT共四十六頁，

8、創(chuàng)作于2022年6月14 下三角矩陣元素ai j保存在向量sa中時的下標(biāo)值k與（i,j）之間的對應(yīng)關(guān)系是：i(i-1)/2+j 當(dāng)ij時n(n+1)/2 當(dāng)ij 時K=1i,jn (5-5)第十五張，PPT共四十六頁，創(chuàng)作于2022年6月155.2.2 稀疏矩陣的壓縮存儲稀疏矩陣：設(shè)m行n列的矩陣含t個非零元素，則=t/(m*n)稱為稀疏因子，通常認(rèn)為 0.05 的矩陣為稀疏矩陣。(1)、稀疏矩陣矩陣中非零元素的個數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素個數(shù)。(2) 、稠密矩陣 一個不稀疏的矩陣。(3) 、稀疏矩陣壓縮存儲方法 只存儲稀疏矩陣中的非零元素，實(shí)現(xiàn)方法是:將每個非零元素用一個三元組（i，j，aij）來表

9、示，則每個稀疏矩陣可用一個三元組線性表來表示。第十六張，PPT共四十六頁，創(chuàng)作于2022年6月161、三元組順序表稀疏矩陣和對應(yīng)的三元組線性表 若把稀疏矩陣的三元組線性表按順序存儲結(jié)構(gòu)存儲，則稱為稀疏矩陣的三元組順序表。第十七張，PPT共四十六頁，創(chuàng)作于2022年6月17三元組表表示的稀疏矩陣轉(zhuǎn)置18稀疏矩陣的轉(zhuǎn)置 Tij= Mji 0 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 24 0 0 0 0 18 0 0 0 0 0 0 -3 0 012 0 0 0 18 9 0 0 24 0 0 0 0 0 0 0 18 0 0 0 0 0 14 0 05661

10、21213931-336144324521865613-32112251831934246314第十八張，PPT共四十六頁，創(chuàng)作于2022年6月18稀疏矩陣用三元組表示的轉(zhuǎn)置行數(shù)和列數(shù)交換i、j的值相互交換重排三元組之間的次序566121213931-336144324521865613-32112251831934246314656211231913-3631434242518第十九張，PPT共四十六頁，創(chuàng)作于2022年6月19用三元組表示，求稀疏矩陣M的轉(zhuǎn)置矩陣TM566121213931-3361443245218T1.行數(shù)和列數(shù)交換，總個數(shù)不變: T.m = M.n; T.n = M.

11、m; T.t = M.t;2.讓q定位T中的第一條記錄: q=1;6 5 6q第二十張，PPT共四十六頁，創(chuàng)作于2022年6月20M566121213931-3361443245218T3.讓col取M的每一列: for(col=1; col=M.n; col+) 4.讓p掃描三元組M的每一條記錄: for (p=1; p=M.t; p+)6 5 6qcol = 1p第二十一張，PPT共四十六頁，創(chuàng)作于2022年6月21M566121213931-3361443245218T6 5 6qcol = 1p5.如果p指向的記錄的j下標(biāo)與col相等: if (M.datap.j = col)ije第

12、二十二張，PPT共四十六頁，創(chuàng)作于2022年6月22M566121213931-3361443245218T6 5 6qcol = 1p6.把M中的記錄p復(fù)制到T中的記錄q: T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.v = M.datap.v;7.讓q下移: q+;1 3 -3第二十三張，PPT共四十六頁，創(chuàng)作于2022年6月23M566121213931-3361443245218T6 5 6qcol = 2p1 3 -32 1 122 5 18第二十四張，PPT共四十六頁，創(chuàng)作于2022年6月24M566121213931

13、-3361443245218T6 5 6qcol = 3p1 3 -32 1 122 5 183 1 93 4 24第二十五張，PPT共四十六頁，創(chuàng)作于2022年6月25M566121213931-3361443245218T6 5 6qcol = 6p1 3 -32 1 122 5 183 1 93 4 246 3 14第二十六張，PPT共四十六頁，創(chuàng)作于2022年6月26（1）稀疏矩陣的轉(zhuǎn)置：“按需查找”法簡單算法的分析稀疏矩陣轉(zhuǎn)置算法復(fù)雜度 = O(n*t)比較一般矩陣的轉(zhuǎn)置算法：其復(fù)雜度 = O(m*n)如果t和m*n一個數(shù)量級，則稀疏矩陣轉(zhuǎn)置算法復(fù)雜度=O(m*n2)所以此算法只適用

14、于tm*n時for(col = 1; col = nu; col +) for(row = 1; row 0時,表的第一個表元素表尾(tail):其它表元素組成的表空表:n = 0 的廣義表。廣義表的特性：有長度：n有深度：廣義表中括號的重數(shù)可遞歸可共享表名表元素 表長非空列表表頭可是原子或列表,表尾必定是列表第三十二張，PPT共四十六頁，創(chuàng)作于2022年6月32廣義表的圖形表示 1、A=(/)2、B=(e)3、C=(a,(b,c,d)4、D=(A，B，C)注：表：原子第三十三張，PPT共四十六頁，創(chuàng)作于2022年6月335.3.1廣義表的定義GetHead(L):在廣義表L存在的條件下，取L

15、的表頭。GetTail(L):在廣義表L存在的條件下，取L的表尾。舉例：1 A=() GetHead(A)=NULL,GetTail(A)=NULL2 B=(e) GetHead(B)=e, GetTail(B)=()3 C=(a,(b,c,d) GetHead(C)=a, GetTail(C)=(b,c,d) GetHead(b,c,d)=b, GetTail(b,c,d)=(c,d) GetHead(c,d)=c, GetTail(c,d)=(d)4 D=(A,B,C) GetHead(D)=A, GetTail(D)=(B,C) GetHead(B,C)=B, GetTail(B,C)=

16、(C)5 E=() GetHead(B)=(), GetTail(B)=()第三十四張，PPT共四十六頁，創(chuàng)作于2022年6月345.3.2 廣義表的存儲結(jié)構(gòu)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，元素包括原子和子表，結(jié)點(diǎn)結(jié)構(gòu)： 表結(jié)點(diǎn)： 表示列表 原子結(jié)點(diǎn)： 表示原子1、廣義表的頭尾鏈表存儲表示： typedef enum ATOM,LISTElemTag;/ATOM=0:原子,LIST=1:子表 typedef struct GLNode ElemTag tag;/公共部分，用來區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn) Union/原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分 AtomType atom; Structstruct GLNode *

17、hp,*tp;ptr;/hp指向表頭,tp指向表尾 ; *Glist;tag=1 hp tptag=0 atom第三十五張，PPT共四十六頁，創(chuàng)作于2022年6月35A=(/)B=(e)C=(a,(b,c,d)D=(A，B，C)E=(a，E)5.5 廣義表的存儲結(jié)構(gòu)示例B0e1C110a1110b0d0cD111E110aA=NIL表結(jié)點(diǎn)：原子結(jié)點(diǎn)：tag=1 hp tptag=0 atom第三十六張，PPT共四十六頁，創(chuàng)作于2022年6月365.5 廣義表的存儲結(jié)構(gòu)示例對廣義表：C = (a,(b,c,d)，其頭尾鏈表為：1C 0a11 0b1 0c1 0d第三十七張，PPT共四十六頁，創(chuàng)作

18、于2022年6月372、廣義表的擴(kuò)展線性鏈表存儲表示： typedef enum ATOM,LISTElemTag; /ATOM=0:原子，LIST=1：子表 typedef struct GLNode ElemTag tag; /公共部分，用來區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn) Union/原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分 AtomType atom;/原子結(jié)點(diǎn)的值域 Struct GLNode *hp/表結(jié)點(diǎn)的頭指針 ; GLNode *tp; /指向下一個結(jié)點(diǎn) *Glist;第三十八張，PPT共四十六頁，創(chuàng)作于2022年6月38廣義表的另一種存儲結(jié)構(gòu)示例A=(/)B=(e)C=(a,(b,c,d)D=(A，

19、B，C)E=(a，E)CABD0e1110a0b0c0d11E110a111tag=1 hp tptag=0 atom tp表結(jié)點(diǎn)：原子結(jié)點(diǎn)：第三十九張，PPT共四十六頁，創(chuàng)作于2022年6月395.3.3 廣義表的基本操作與實(shí)現(xiàn) 下面討論頭鏈和尾鏈存儲結(jié)構(gòu)下和原子和子表存儲結(jié)構(gòu)下一些典型操作的算法實(shí)現(xiàn)。/-廣義表的頭尾鏈表存儲表示typedef enum ATOM,LIST ElemTag;/ATOM=0原子，LIST=1子表typedef struct GLNode ElemTag tag;/公共部分，用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn) union AtomType atom;/atom是原子結(jié)點(diǎn)的

20、值域 struct struct GLNode *hp,*tp;ptr; /ptr是表結(jié)點(diǎn)的指針域，ptr.hp和ptr.tp分別指向表頭和表尾 ;*GList; /廣義表類型第四十張，PPT共四十六頁，創(chuàng)作于2022年6月40第五章 數(shù)組和廣義表1、求廣義表深度算法 廣義表的深度是廣義表中所有原子數(shù)據(jù)元素到達(dá)根結(jié)點(diǎn)的最大值。int GListDepth(GList LS) /采用頭尾鏈表存儲結(jié)構(gòu)，求廣義表L的深度 if(!L) return 1;/空表深度為1 if(L-tag=ATOM) return 0;/原子深度為0 for(max=0,pp=L;pp;pp=pp-ptr.tp) /求

21、以pp-ptr.hp為頭指針的子表深度 dep=GListDepth(pp-ptr.hp); if(depmax) max=dep; return max+1;/GListDepth第四十一張，PPT共四十六頁，創(chuàng)作于2022年6月41第五章 數(shù)組和廣義表2、求廣義表的長度算法 在頭鏈和尾鏈存儲結(jié)構(gòu)中，廣義表的長度就是表尾指針構(gòu)成的單鏈表的長度。int GListLength(GList LS) for(p=L; p!=NULL; p=p-ptr.tp) number+; return number;第四十二張，PPT共四十六頁，創(chuàng)作于2022年6月42第五章 數(shù)組和廣義表3、復(fù)制廣義表算法任何非空廣義表都由表頭和表尾構(gòu)成，故可將廣義表分解成表頭和表尾兩部分，分別遞歸復(fù)制求得新的表頭和表尾。Status CopyLS(GList &T,GLi