第5章 數(shù)組和廣義表

本文格式為Word版，下載可任意編輯——第5章數(shù)組和廣義表第五章數(shù)組和廣義表

講課提要

1．多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)2．特別矩陣的壓縮存儲(chǔ)

3．廣義表的定義及其與線性表的關(guān)系4．廣義表的存儲(chǔ)結(jié)構(gòu)

5．廣義表運(yùn)算實(shí)現(xiàn)中遞歸的應(yīng)用

1．把握多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)2．把握特別矩陣的壓縮存儲(chǔ)方法

3．把握廣義表的定義及其與線性表的關(guān)系4．把握廣義表的存儲(chǔ)結(jié)構(gòu)

5．了解廣義表運(yùn)算實(shí)現(xiàn)中遞歸的應(yīng)用

學(xué)習(xí)指導(dǎo)

1．多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)

對于多維數(shù)組，有兩種存儲(chǔ)方式：

一是以行為主序（或先行后列）的順序存放，如BASIC、PASCAL、C等程序設(shè)計(jì)語言中用的是以行為主的順序分派，即一行分派完了接著分派下一行。

另一種是以列為主序（先列后行）的順序存放，如FORTRAN語言中，用的是以列為主序的分派順序，即一列一列地分派。

以行為主序的分派規(guī)律是：最右邊的下標(biāo)先變化，即最右下標(biāo)從小到大，循環(huán)一遍后，右邊其次個(gè)下標(biāo)再變，?，從右向左，最終是左下標(biāo)。以列為主序分派的規(guī)律是：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊其次個(gè)下標(biāo)再變，?，從左向右，最終是右下標(biāo)。

不管按何種方式存儲(chǔ)，只要確定了數(shù)組的首地址以及每個(gè)數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存儲(chǔ)地址表示為其下標(biāo)的線性函數(shù)。設(shè)有m×n二維數(shù)組Amn，以“以行為主序〞的分派為例，依照元素的下標(biāo)確定其地址的計(jì)算方法如下。

設(shè)數(shù)組的基址為LOC(a11)，每個(gè)數(shù)組元素占據(jù)L個(gè)地址單元，計(jì)算aij的物理地址的函數(shù)為：

LOC(aij)=LOC(a11)+((i-1)*n+j-1)*L

同理，對于三維數(shù)組Amnp，即m×n×p數(shù)組，對于數(shù)組元素aijk其物理地址為：

LOC(aijk)=LOC(a111)+((i-1)*n*p+(j-1)*p+k-1))*L

注意：在C語言中，數(shù)組中每一維的下界定義為0，則：

LOC(aij)=LOC(a00)+(i*n+j)*L

二維數(shù)組A的每一個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo)i=0，1，?，8，列下標(biāo)j=1，2，?，10。若A以行為主序存儲(chǔ)元素，A[8][5]的物理地址與當(dāng)A按列為主序存

儲(chǔ)時(shí)的元素（）的物理地址一致。設(shè)每個(gè)字符占一個(gè)字節(jié)。

A．A[8][5]B．A[3][10]C．A[5][8]D．A[0][9]

解：二維數(shù)A是一個(gè)9行10列的矩陣，即A[9][10]。按行存儲(chǔ)時(shí)，A[8][5]是第85個(gè)元素存儲(chǔ)的元素。而按列存儲(chǔ)時(shí)，第85個(gè)存儲(chǔ)的元素是A[3][10]。即正確答案為B。

2．特別矩陣壓縮存儲(chǔ)的意義

在好多科學(xué)計(jì)算與工程應(yīng)用中，經(jīng)常要使用矩陣的概念。矩陣具有與數(shù)組相像的性質(zhì)，如元素?cái)?shù)目固定、元素按下標(biāo)關(guān)系有序地排列，所以在編程時(shí)可以利用二維數(shù)組來存儲(chǔ)矩陣，也可以利用程序設(shè)計(jì)語言中的各種矩陣運(yùn)算。

在某些狀況下，特別是在數(shù)值分析中，經(jīng)常會(huì)出現(xiàn)一些階數(shù)很高的矩陣，其中含有大量值一致的元素或零元素，如三角矩陣、對稱矩陣、稀疏矩陣等，從儉約存儲(chǔ)空間的角度考慮，此時(shí)若用二維數(shù)組存儲(chǔ)會(huì)造成空間的極大浪費(fèi)。為了節(jié)省存儲(chǔ)空間，可以對這類矩陣進(jìn)行壓縮存儲(chǔ)。即為對多個(gè)一致值的元素只分派一個(gè)存儲(chǔ)空間，而對零元素可以不分派空間。

3．對稱矩陣壓縮存儲(chǔ)的方法

對稱矩陣的特點(diǎn)是：在一個(gè)n階方陣中，有aij=aji，其中1≤i,j≤n。對稱矩陣關(guān)于主對角線對稱，因此只需存儲(chǔ)上三角或下三角部分即可。

對于對稱矩陣中的任意元素aij，若令I(lǐng)=max(i,j)，J=min(i,j)，則將上面兩個(gè)式子綜合起來得到：k=I*(I-1)/2+J-1。給出對稱矩陣A中任意元素aij，依據(jù)它的下標(biāo)i和j就可由上述對應(yīng)關(guān)系式確定其在數(shù)組M中的位置K，因此aij的地址可由下式計(jì)算。

Loc(aij)=Loc(M[K])=Loc(M[0])+K*L=Loc(M[0])+[I*(I+1)/2+J]*L其中：L為每個(gè)數(shù)據(jù)元素所占的存儲(chǔ)單元長度。I=max(i,j)。J=min(i,j)。K=I*(I+1)/2+J。

若對n階對稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑兀òㄖ鲗蔷€上所有元素）依次存放于一維數(shù)組B[n（n+1）/2]中，則在B中確定的位置k的關(guān)系為（）。

A．

i*(i?1)j*(j?1)i*(i?1)j*(j?1)?jB．?iC．?jD．?i2222解：假使aij按行存儲(chǔ)，那么它的前面有i-1行，其有元素個(gè)數(shù)為：

1+2+3+…+（i-1）=i（i-1）/2。同時(shí)它又是所在行的第j列，因此它排列的順序還得加上j，一維數(shù)組B[n(n+1)/2]中的位置k與其下標(biāo)的關(guān)系是：

i*(i?1)?j。2因此答案為A。

4．三角矩陣壓縮存儲(chǔ)的方法

形如圖的矩陣稱為三角矩陣，其中c為某個(gè)常數(shù)。其中下面圖(a)為下三角矩陣：主對角線以上均為同一個(gè)常數(shù)；(b)為上三角矩陣，主對角線以下均為同一個(gè)常數(shù)；下面探討它們的壓縮存儲(chǔ)方法。

3cccc34810

62cccc2946

481cccc157

7460cccc08

cccc782957

(a)下三角矩陣(b)上三角矩陣圖4-1三角矩陣

三角矩陣中的重復(fù)元素c可以共享一個(gè)存儲(chǔ)空間，其余的元素有n(n+1)/2個(gè)，因此可壓縮存儲(chǔ)到向量sa[0..n(n+1)/2]中，c存放在向量的最終一個(gè)分量中，排列時(shí)以行序?yàn)橹?。aij和sa[k]的對應(yīng)關(guān)系是：下三角矩陣：

i*(i-1)/2+j-1當(dāng)i≥jk=n*(n+1)/2-1當(dāng)ij

已知n階下三角矩陣A，依照壓縮存儲(chǔ)的思想，可以將其主對角線以下所有元素（包括主對角線上元素）依次存放于一維數(shù)組B中。請寫出從第一列開始以列序?yàn)橹餍蚍峙煞绞綍r(shí)在B中確定元素aij的存放位置的公式。

解：假使aij按列存儲(chǔ)，那么它的前面有j-1列，共有元素：n+(n-1)+(n-2)+?+[n-(j-2)]=(j-1)*n-

(j?2)(j?1)

2而它又是所在列的第i行，因此在它前的元素個(gè)數(shù)還得加上i。因此它在一維數(shù)組B中的存儲(chǔ)順序?yàn)椋?/p>

(j-1)*n-

(j?2)(j?1)+i

25．稀疏矩陣及其壓縮存儲(chǔ)的特點(diǎn)

設(shè)m*n矩陣中有t個(gè)非零元素且t=j)，在一維數(shù)組B的下標(biāo)位置k的值是（B）。

A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j13、廣義表A=((a),a)的表頭是（B）。

A.aB.(a)C.bD.((a))14、稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（C）。

A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表

15、假設(shè)以三元組表表示稀疏矩陣，則與如下圖三元組表對應(yīng)的4×5的稀疏矩陣是（注：矩陣的行列下標(biāo)均從1開始）（B）。

?0?8?0?7A.?00???50??0?8?0?0C.?70???50?060??000?

000??400??060??003?

000??400???0?8?0?7B.??50??00?060??003?

400??000??060??000?

403??000??

?0?8?0?7D.??50??00?16、以下有關(guān)廣義表的表述中，正確的是（A）。

A.由0個(gè)或多個(gè)原子或子表構(gòu)成的有限序列B.至少有一個(gè)元素是子表

C.不能遞歸定義D.不能為空表17、對廣義表L=((a,b),((c,d),(e,f)))執(zhí)行head(tail(head(tail(L))))操作的結(jié)果是（D）。

A.的B.eC.(e)D.（e,f）二、判斷題

（×）1、廣義表中原子個(gè)數(shù)即為廣義表的長度。

（×）2、一個(gè)稀疏矩陣采用三元組表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把mu和nu的值進(jìn)行互換，則完成了矩陣轉(zhuǎn)置。（√）3、稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。（×）4、廣義表的長度是指廣義表中括號(hào)嵌套的層數(shù)。（√）5、廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)，其元素可以是單原子也可以是子表。三、填空題

1、已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A[0][0])，則A[i][j]的地址是___Loc(A[0][0])+(i*N+j)*k____。

2、廣義表運(yùn)算式HEAD(TAIL((a,b,c),(x,y,z)))的結(jié)果是：(x,y,z)。3、二維數(shù)組，可以依照列序?yàn)橹骱托行驗(yàn)橹鲀煞N不同的存儲(chǔ)方式。

4、稀疏矩陣的壓縮存儲(chǔ)方式有：三元組和十字鏈表。四、綜合題

1、現(xiàn)有一個(gè)稀疏矩陣，請給出它的三元組表。

?0?1??0??03100210?20?0??0??0?答案：

i112334j231233v31121-2

一、基本概念

1、數(shù)組地址的計(jì)算（一維數(shù)組，二維數(shù)組）

2、稀疏矩陣的壓縮存儲(chǔ)方法：三元組表和十字鏈表（要求會(huì)稀疏矩陣的三元組表示）3、廣義表的概念

4、求廣義表的深度和長度、求廣義表的表頭和表尾二、練習(xí)題

3.二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A[0][0