第10章多維數(shù)組和廣義表

主要內(nèi)容10.1多維數(shù)組邏輯結(jié)構(gòu)存儲結(jié)構(gòu)10.2特殊矩陣的壓縮存儲10.3稀疏矩陣稀疏矩陣的存儲——三元組、十字鏈表稀疏矩陣的算法10.4廣義表廣義表的定義和運(yùn)算廣義表的存儲結(jié)構(gòu)廣義表的算法2重難點特殊矩陣的壓縮存儲需要一定的數(shù)學(xué)知識多維數(shù)組的一維存儲確定多維數(shù)組元素與其一維存儲單元之間的對應(yīng)關(guān)系稀疏矩陣的三元組存儲基于三元組存儲的矩陣運(yùn)算310.1多維數(shù)組——邏輯結(jié)構(gòu)一般把三維以上的數(shù)組稱為多維數(shù)組，n維的多維數(shù)組可以視為n-1維數(shù)組元素組成的線性結(jié)構(gòu)。一維數(shù)組可以看作一個線性表；二維數(shù)組可以看做“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組；三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組。4

10.1多維數(shù)組——邏輯結(jié)構(gòu)多維數(shù)組是一維數(shù)組的推廣。一維數(shù)組是線性結(jié)構(gòu)，然而多維數(shù)組則是一種非線性結(jié)構(gòu)。其特點是每一個數(shù)據(jù)元素可以有多個直接前驅(qū)和多個直接后繼。二維數(shù)組可以看成每一個數(shù)組元素為一維數(shù)組的一維數(shù)組，但從整體來看，每一個數(shù)組元素同時處于兩個向量（行、列），它可能有兩個直接前驅(qū)，有兩個直接后繼。數(shù)組元素的下標(biāo)一般具有固定的下界和上界，因此比其他復(fù)雜的非線性結(jié)構(gòu)簡單。在數(shù)組中經(jīng)常做的兩種操作取值操作：給定一組下標(biāo)，讀取其對應(yīng)的數(shù)據(jù)元素。賦值操作：給定一組下標(biāo)，存儲或修改與其相對應(yīng)的數(shù)據(jù)元素。510.1多維數(shù)組——存儲結(jié)構(gòu)當(dāng)數(shù)組的行列固定后，通過一個函數(shù)的映射，就可以根據(jù)數(shù)組元素的下標(biāo)得到它的存儲地址。對于一維數(shù)組只要按下標(biāo)順序分配即可；對多維數(shù)組分配時，要把它的元素存儲在一維的存儲器中。610.1多維數(shù)組——存儲結(jié)構(gòu)多維數(shù)組的存儲方式（1）以行序為主（RowMajorOrder）以行為主的存儲方式也稱為按行優(yōu)先順序方式，實現(xiàn)時按行號從小到大的順序，先存儲第0行的全部元素，再存放第1行的元素、接著存放第2行的元素、……（2）以列為主序（ColumnMajorOrder）以列為主的存儲方式也稱為按列優(yōu)先順序方式，實現(xiàn)時按列號從小到大的順序，先存儲第0列的全部元素，再存儲第1列的元素、接著存放第2列的元素、……7C和類C語言都是以行序為主的方式進(jìn)行數(shù)據(jù)存儲的。10.1多維數(shù)組——存儲結(jié)構(gòu)

8n=6m=4a[i][j]i行j列Loc(a[2][2])=Loc(a[0][0])+(2*6+2)*di=3頁10.1多維數(shù)組——存儲結(jié)構(gòu)

9Loc(a[i][j][k])=Loc(a[0][0][0])+(3*4*6+2*6+2)*dj=4行k=6列10.1多維數(shù)組——存儲結(jié)構(gòu)

1010.2特殊矩陣的壓縮存儲矩陣是一個二維數(shù)組，是眾多科學(xué)與工程問題中研究的數(shù)學(xué)對象。矩陣中非零元素或零元素的分布有一定規(guī)律的矩陣稱為特殊矩陣，如三角矩陣、對稱矩陣、帶狀矩陣、稀疏矩陣等。當(dāng)矩陣的階數(shù)很大時，用普通的二維數(shù)組存儲這些特殊矩陣，將會浪費很多的存儲單元。從節(jié)約存儲空間的角度，需要對這些特殊矩陣采用壓縮存儲。1110.2特殊矩陣的壓縮存儲——對稱矩陣

125階對稱矩陣A的壓縮存儲10.2特殊矩陣的壓縮存儲——對稱矩陣對稱矩陣中元素的存儲位置13

b

a00a10a11a20a21a22a30a31a32……

an-1n-1

012345678n(n+1)/2-1前

i

行的元素總數(shù)+第i

行第j

個元素前的元素個數(shù)若

i≥j,數(shù)組元素a[i][j]在數(shù)組b中的存放位置為

k=(1+2+

+i)+j=(i+1)*i/2+j若

i≥j

，元素位于下三角；若

i

≤j

，元素位于上三角；若

i==j

，元素位于對角線。思考：若沿副對角線對稱呢？10.2特殊矩陣的壓縮存儲——三角矩陣三角矩陣的特殊性是以主對角線劃分矩陣。主對角線任意一側(cè)（不包括主對角線）的元素均為常數(shù)。三角矩陣又可以分為下三角矩陣（主對角線以上均為同一個常數(shù)和上三角矩陣（主對角線以下均為同一個常數(shù)）。三角矩陣的壓縮存儲方法，和對稱矩陣類似。1410.2特殊矩陣的壓縮存儲——三角矩陣下三角矩陣的存儲15b

a00a10a11a20a21a22a30a31a32……

an-1n-1

012345678n(n+1)/2-1n(n+1)/2c若

i≥j，數(shù)組元素a[i][j]在數(shù)組b中的存放位置為

k=

1+2+

+i+j=(i+1)*i/2+j當(dāng)i<j時，位置k=n(n+1)/210.2特殊矩陣的壓縮存儲——三角矩陣上三角矩陣的存儲16若

i≤j，數(shù)組元素a[i][j]在數(shù)組b中的存放位置為

k=

n+(n-1)+(n-2)++(n-i+1)+j-i

=(2*n-i+1)*i/2+j-i當(dāng)i>j時，位置k=n(n+1)/2b

a00a01a02a03a11a12a13a22a23a33

0123456789cn(n+1)/2-1n(n+1)/210.3稀疏矩陣的壓縮存儲稀疏矩陣17設(shè)矩陣A中有s個非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。10.3稀疏矩陣的壓縮存儲三元組存儲法設(shè)矩陣A中有s個非零元素。令e=s/(m*n)，稱e為矩陣的稀疏因子。一般認(rèn)為e≤0.05時稱之為稀疏矩陣。在存儲稀疏矩陣時，為節(jié)省存儲空間，應(yīng)只存儲非零元素。但通常非零元素的分布沒有規(guī)律，故在存儲非零元素時，必須記下它所在的行和列的位置(i,j)。每一個三元組

(i,j,aij)唯一確定了矩陣A的一個非零元素。因此，稀疏矩陣可由表示非零元素的三元組及其行列數(shù)唯一確定。1810.3稀疏矩陣的壓縮存儲稀疏矩陣及其對應(yīng)的三元組表19稀疏矩陣對應(yīng)的三元組表10.3稀疏矩陣的壓縮存儲稀疏矩陣三元組表的類型定義#defineSMAX100 //定義一個足夠大的三元組表structSPNode //定義三元組{ inti,j,v; //三元組非零元素的行、列和值};structSparseMatrix //定義稀疏矩陣{introws,cols,terms; //稀疏矩陣行、列和非零元素的個數(shù)

SPNodedata[SMAX]; //三元組表};這樣的存儲方法確實會節(jié)約存儲空間，但矩陣運(yùn)算可能會變得復(fù)雜一些。2010.3稀疏矩陣的壓縮存儲帶行指針的鏈表存儲若把具有同一行號的非零元素用一個鏈表連接起來，則稀疏矩陣中的若干行組成若干個單向鏈表，合起來就成為帶行指針的單向鏈表。2110.3稀疏矩陣的壓縮存儲十字鏈表存儲法為稀疏矩陣的每一行設(shè)置一個鏈表，同時也為每一列設(shè)置一個鏈表；方便在行和列兩個方向的搜索。稀疏矩陣的每一個非零元素就同時包含在兩個鏈表中，即每一個非零元素，同時包含在所在行的行鏈表和所在列的列鏈表中。采用十字鏈表存儲稀疏矩陣的三元組表，每個非零元素對應(yīng)的三元組，存儲為鏈表中的一個結(jié)點，其結(jié)構(gòu)為：row：存儲非零元素的行號col：存儲非零元素的列號value：存儲非零元素的值right：指針域，指向同一行中的下一個三元組down：指針域，指向同一列中的下一個三元組22rowcolvaluedownright10.3稀疏矩陣的壓縮存儲稀疏矩陣十字鏈表存儲結(jié)構(gòu)結(jié)點類型的定義typedefstruct_MatNode{ inti,j,v; struct_MatNode*down,*right;}MatNode,*MatLink;2310.3稀疏矩陣的壓縮存儲稀疏矩陣及其十字鏈表存儲結(jié)構(gòu)24最后返回十字鏈表的頭指針10.4廣義表廣義表的定義和運(yùn)算廣義表(GeneralizedLists)是線性表的推廣，也稱其為列表(Lists)線性表中的元素僅限于單個數(shù)據(jù)元素(也稱為原子項)，即不可以再分割；而廣義表中的元素既可以是原子項，也可以是子表。廣義表是n（n≥0）個數(shù)據(jù)元素a1，a2，…，ai，…，an的有序序列，一般記作：LS＝（a1，a2，…，ai，…，an）廣義表通常用圓括號括起來，并用逗號分隔表中的元素。通常用大寫字母表示廣義表，用小寫字母表示單個數(shù)據(jù)元素。

2510.4廣義表廣義表的定義和運(yùn)算廣義表的長度——廣義表第一層所包含的元素（包括原子和子表）的個數(shù)。廣義表的深度——廣義表展開后所包含括號的層數(shù)（嵌套數(shù)）。2610.4廣義表【例10-3】廣義表的例子。（1）A=()，廣義表A是長度為0的空表。（2）B=(a,b)，廣義表B的長度為2，深度為1。

由于表中的元素全部是原子項，B實質(zhì)上就是線性表。（3）C=(c,(d,e))，廣義表C的長度為2，深度為2。

其中第一項為原子項，第二項為子表，C實質(zhì)是一種與樹對應(yīng)的廣義表，也稱之為純表。（4）D=(B,f)，廣義表D的長度為2的，其中第一項為子表，第二項為原子項。

把B展開可知，廣義表D的深度為2。（5）E=(B,D)，廣義表E的長度為2的，其中兩項都是子表，且廣義表D的第一項又恰好是B。這種表也稱為再入表，是一種與圖對應(yīng)的廣義表。（6）F=(g,h,F)，廣義表F的長度為3，其中第一、第二項為原子項，第三項是其本身，這樣的廣義表又稱為遞歸表，它的深度為∞。廣義表相當(dāng)靈活，它可以兼容線性表、數(shù)組、樹和有向圖等各種常用數(shù)據(jù)結(jié)構(gòu)。2710.4廣義表【例10-4】例10-3中廣義表的表頭和表尾。（1）A=()，A為空表，沒有表頭和表尾。（2）B=(a,b)， head(B)=a tail(B)=(b)（3）C=(c,(d,e))， head(C)=c tail(C)=((d,e))（4）D=(B,f)， head(D)=B tail(D)=(f)（5）E=(B,D)， head(E)=B tail(E)=(D)（6）F=(g,h,F)， head(F)=g tail(F)=(h,F)2810.4廣義表廣義表的定義和運(yùn)算(1)創(chuàng)建廣義表：createGL(GL)操作結(jié)果：創(chuàng)建一個廣義表GL(2)求廣義表的長度：getLength(GL)初始條件：廣義表存在。操作結(jié)果：返回廣義表的長度。(3)求廣義表的深度：depth(GL)初始條件：廣義表存在。操作結(jié)果：返回廣義表的深度。2910.4廣義表(4)查找操作：search(GL，x)初始條件：廣義表GL存在，ｘ是給定的一個數(shù)據(jù)元素或子表。操作結(jié)果：查找成功返回1；否則返回0。(5)求廣義表頭部：head(LS)初始條件：廣義表存在。操作結(jié)果：返回廣義表的頭元素。(6)求廣義表尾部：tail(LS)初始條件：廣義表存在。操作結(jié)果：返回廣義表的尾元素。3010.4廣義表廣義表的存儲結(jié)構(gòu)根據(jù)表示方式的不同，廣義表的存儲結(jié)構(gòu)有兩種：一種是頭尾鏈表存儲法，另一種是擴(kuò)展線性表存儲法。頭尾鏈表存儲結(jié)構(gòu)廣義表的表結(jié)點由3個域構(gòu)成，分別是：標(biāo)志域（tag=1）、表頭指針域（hp）、表尾指針域（tp）；相應(yīng)的原子結(jié)點由2個域構(gòu)成，分別是：標(biāo)志域（tag=0）和值域（data）。3110.4廣義表頭尾鏈表存儲結(jié)構(gòu)的類型定義32typedefstructGeneralListNode{

ElemTagtag;//用以區(qū)分原子結(jié)點和表結(jié)點

union//原子結(jié)點和表結(jié)點的共用體

{

AtomTypeatom;//atom是原子結(jié)點的值，AtomType由用戶定義

struct{structGeneralListNode*hp,*tp;}ptr;//ptr是表結(jié)點的指針域，ptr.hp

和ptr.tp分別指向表頭和表尾

};}GLNode;//廣義表的類型typedefenum{ATOM, //ATOM==0表示原子

LIST //LIST==1表示子表}ElemTag;//定義枚舉類型1