c++課件數(shù)組和廣義表

第五章

數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)

5.3.1特殊矩陣

5.3.2稀疏矩陣

5.4廣義表的定義

5.5廣義表的存儲(chǔ)結(jié)構(gòu)由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡(jiǎn)單。多維數(shù)組是向量的推廣。例如，二維數(shù)組A：可以看成是由一個(gè)行向量組成的向量，也可以看成是一個(gè)列向量組成的向量。()()()()()()()()()數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的元素本身也是一種線性表。5.1數(shù)組的定義數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。在C語(yǔ)言中，一個(gè)二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說(shuō)，typedef

elemtypearray2[m][n];等價(jià)于：

typedef

elemtypearray1[n];

typedef

array1array2[m];由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來(lái)表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中。又由于數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲(chǔ)的方法來(lái)表示數(shù)組。

通常有兩種順序存儲(chǔ)方式：以行序?yàn)橹餍蛞粤行驗(yàn)橹餍?.2數(shù)組的順序表示和實(shí)現(xiàn)

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….

按行序?yàn)橹餍虼娣?/p>

amn

……..

am2

am1

……….a2n

……..

a22a21a1n

…….a12

a1101n-1m*n-1nLoc(aij)=Loc(a11)+[(i-1)n+(j-1)]*L

按列序?yàn)橹餍虼娣?1m-1m*n-1m

amn

……..

a2n

a1n……….

am2

……..

a22

a12

am1

…….

a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..

amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*L

[補(bǔ)充：]多維數(shù)組元素地址的計(jì)算(以行序?yàn)橹餍?：①三維數(shù)組：a[b1][b2][b3]Loc(a[i][j][k])=Loc(a[0][0][0])+(i*b2*b3+j*b3+k)*l②多維數(shù)組：a[b1][b2]…[bn]Loc[(a[j1][j2]…[jn])=Loc[a[0][0]…[0])+(j1*b2*b3*…*bn+j2*b3*…*bn+j3*b4*…*bn+…+jn-1*bn+jn)*l縮寫為：Loc[(a[j1][j2]…[jn])＝Loc[a[0][0]…[0])＋其中cn=l,ci-1=bi*ci此式稱為n維數(shù)組的映象函數(shù)。一旦確定了數(shù)組的各維長(zhǎng)度ci就是常數(shù)。為了節(jié)省存儲(chǔ)空間，我們可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)：即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。5.3矩陣的壓縮存儲(chǔ)在科學(xué)與工程計(jì)算問(wèn)題中，矩陣是一種常用的數(shù)學(xué)對(duì)象，在高級(jí)語(yǔ)言編制程序時(shí)，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，則占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)造成極大的浪費(fèi)。

5.3.1特殊矩陣

特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。

(1)對(duì)稱矩陣(2)三角矩陣(3)對(duì)角矩陣

在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)：

aij=aji

0≦i,j≦n-1

則稱A為對(duì)稱矩陣，如圖5.1。(1)對(duì)稱矩陣:

15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1

圖5.1對(duì)稱矩陣

對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失一般性，我們按“行優(yōu)先順序”存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素.

15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1

圖5.1對(duì)稱矩陣

在這個(gè)下三角矩陣中，第i行恰有i+1個(gè)元素，元素總數(shù)為：n(n+1)/2

因此，我們可以按從上到下、從左到右將這些元素存放在一個(gè)向量sa[0..n(n+1)/2-1]中。為了便于訪問(wèn)對(duì)稱矩陣A中的元素，我們必須在aij和sa[k]之間找一個(gè)對(duì)應(yīng)關(guān)系。若i≧j，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）一共有1+2+…+i=i(i+1)/2個(gè)元素，在第i行上，aij之前恰有j個(gè)元素（即ai0,ai1,ai2,…,aij-1），因此有：

k=i*(i+1)/2+j0≦k<n(n+1)/2若i<j，則aij是在上三角矩陣中。因?yàn)閍ij=aji，所以只要交換上述對(duì)應(yīng)關(guān)系式中的i和j即可得到：

k=j*(j+1)/2+i0≦k<n(n+1)/2(2)三角矩陣以主對(duì)角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對(duì)角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對(duì)角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。

a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…..……………..cc…an-1n-1an-10an-11…an-1n-1

(a)上三角矩陣(b)下三角矩陣

三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n(n+1)/2個(gè)，因此，三角矩陣可壓縮存儲(chǔ)到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個(gè)分量中.上三角矩陣中，主對(duì)角線之上的第i行(0≦i<n)恰有n-i個(gè)元素，按行優(yōu)先順序存放上三角矩陣中的元素aij時(shí)，aij之前的i行一共有

i(2n-i+1)/2個(gè)元素，在第i行上，aij前恰好有j-i個(gè)元素：aii,aii+1,…aij-1。因此，sa[k]和aij的對(duì)應(yīng)關(guān)系是：

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

當(dāng)i≦j

n(n+1)/2

當(dāng)i>j(即常數(shù)C的存儲(chǔ)位置)k=下三角矩陣的存儲(chǔ)和對(duì)稱矩陣類似，sa[k]和aij對(duì)應(yīng)關(guān)系是：

i(i+1)/2+j

i≧j

n(n+1)/2i<jk=

(3)對(duì)角矩陣對(duì)角矩陣中，所有的非零元素集中在以主對(duì)角線為中心的帶狀區(qū)域中，即除了主對(duì)角線和主對(duì)角線相鄰兩側(cè)的若干條對(duì)角線上的元素之外，其余元素皆為零。下圖給出了一個(gè)三對(duì)角矩陣，

a00a01a10a11a12a21a22a23….…..….圖5.3對(duì)角矩陣

an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1非零元素僅出現(xiàn)在主對(duì)角(aii,0≦i≦n-1)上，緊鄰主對(duì)角線上面的那條對(duì)角線上(aii+1,0≦i≦n-2)和緊鄰主對(duì)角線下面的那條對(duì)角線上(ai+1i,0≦i≦n-2)。顯然，當(dāng)∣i-j∣>1時(shí)，元素aij=0。對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。由此可知，一個(gè)k對(duì)角矩陣(k為奇數(shù))A是滿足下述條件的矩陣：若∣i-j∣>(k-1)/2，則元素aij=0。在三對(duì)角矩陣?yán)锍凉M足條件i=0，j=0、1，或i=n-1,j=n-2、n-1或1<i<n-1,j=i-1、i、i+1的元素aij外，其余元素都是零。a00a01

a10a11a12a21

……an-1n-2an-1n-1K=012345……3n-23(n-1)

若按行優(yōu)序?yàn)橹餍騺?lái)存儲(chǔ)，則除第0行和第n-1行是2個(gè)元素外，其余每行的非零元素都要是3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為3n-2。

LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d=LOC(0,0)+(2i+j)*d

數(shù)組sa中的元素sa[k]與三對(duì)角帶狀矩陣中的元素aij存在一一對(duì)應(yīng)關(guān)系，在aij之前有i行,共有3*i-1個(gè)非零元素，在第i行，aij

前面有j-i+1個(gè)非零元素，這樣，非零元素aij的地址為：

上例中，a34對(duì)應(yīng)著sa[10]。

k=2*i+j=2*3+4=10a21對(duì)應(yīng)著sa[5]k=2*2+1=5上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的。因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)向量中，并且一般都能找到矩陣中的元素與該向量的對(duì)應(yīng)關(guān)系，通過(guò)這個(gè)關(guān)系，仍能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。

5.3.2稀疏矩陣

什么是稀疏矩陣？簡(jiǎn)單說(shuō)，設(shè)矩陣A中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。精確地說(shuō)，設(shè)在矩陣A中，有s個(gè)非零元素，令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認(rèn)為e≦0.05時(shí)稱之為稀疏矩陣。這樣，一個(gè)三元組(i,j,aij)唯一確定了矩陣A的一個(gè)非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。在存儲(chǔ)稀疏矩陣時(shí)，為了節(jié)省存儲(chǔ)單元，很自然地想到使用壓縮存儲(chǔ)方法。但由于非零元素的分布一般是沒有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（i,j)。例如，下列三元組表((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))加上(6，7，8)這一對(duì)行、列值及非零元數(shù)便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲(chǔ)方法。

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000

圖5.4稀疏矩陣M和TM=T=（1）三元組順序表假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表，則可得到稀疏矩陣的一種壓縮存儲(chǔ)方法——三元順序表。

#definemaxsize10000

//定義數(shù)組的大小

typedef

int

datatype;

//定義矩陣中元素的類型

typedef

struct{

inti,j;

//非零元素所在行、列

datatypev;

//非零元素的值

}triplet;

//定義數(shù)組中每一元素的類型是三個(gè)域的結(jié)構(gòu)體

typedef

struct{tripletdata[maxsize];

int

mu,nu,tu;//矩陣的行、列、稀疏因子的個(gè)數(shù)

}tripletable;//定義三元順序表的類型

tripletableA,M,N,T;

設(shè)A為tripletable型的結(jié)構(gòu)變量。右圖所示為稀疏矩陣的三元順序表的表示。678

121213931-3361443245218611564-7ijvA

012345678

Data域munutu

[例：]矩陣的轉(zhuǎn)置運(yùn)算一個(gè)m×n的矩陣A，它的轉(zhuǎn)置B是一個(gè)n×m的矩陣，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n。將A轉(zhuǎn)置為B，就是將A的三元組表a.data置換為表B的三元組表b.data，如果只是簡(jiǎn)單地交換a.data中i和j的內(nèi)容，那么得到的b.data將是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣B。由于A的列是B的行，因此，按a.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。678

121213931-3361443245218611564-7ijv012345678maijv768

13-3161521122518319342446-76314012345678mb?解決思路：只要做到

將矩陣行、列維數(shù)互換將每個(gè)三元組中的i和j相互調(diào)換重排三元組次序，使mb中元素以N的行(M的列)為主序。

方法一：按M的列序轉(zhuǎn)置

即按mb中三元組次序依次在ma中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。

為找到M中每一列所有非零元素，需對(duì)其三元組表ma從第一行起掃描一遍。由于ma中以M行序?yàn)橹餍?所以由此得到的恰是mb中應(yīng)有的順序算法描述：P99算法5.1或5-1.txt算法分析：T(n)=O(M的列數(shù)n非零元個(gè)數(shù)t)

若t與mn同數(shù)量級(jí)，則678

121213931-3361443245218611564-7ijv012345678M76

8

13-3161521122518319342446-76314ijv012345678Tqppppppppqqqqppppppppcol=1col=26,7,8分別表示mu,nu和tu域矩陣轉(zhuǎn)置算法StatusTranspose(tripletableM，tripletable

&T){

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;//q為轉(zhuǎn)置以后T的行號(hào)//for(col＝1;col<=M.nu;++col)

for(p＝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].v=M.data[p].v；

++q;}

}returnok}方法二：快速轉(zhuǎn)置即按ma中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入mb中恰當(dāng)位置。

此法關(guān)鍵是要預(yù)先確定M中每一列第一個(gè)非零元在mb中位置。

為確定這些位置，轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個(gè)數(shù)。實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組num[col]：表示矩陣M中第col列中非零元個(gè)數(shù)cpot[col]：指示M中第col列第一個(gè)非零元在mb中位置，顯然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colma[0].j)1357889colnum[col]cpot[col]12223241506170246算法分析：T(n)=O(M的列數(shù)n+非零元個(gè)數(shù)t)

若t與mn同數(shù)量級(jí)，則T(n)=O(mn)算法描述：P100算法5.2或5-2.txt6

7

8

121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]1122323524715806817907

6

8

13-3161521122518319342446-76314pppppppp4629753（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第一種鏈?zhǔn)剑簬兄羔樝蛄康膯捂湵肀硎?每行的非零元用一個(gè)單鏈表存放*設(shè)置一個(gè)行指針數(shù)組，指向本行第一個(gè)非零元結(jié)點(diǎn)；若本行無(wú)非零元，則指針為空*表頭結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)類型定義typedef

structnode{int

col;

int

val;

structnode*link;}JD;typedef

structnode*TD;^13573-11-12-242^^^^需存儲(chǔ)單元個(gè)數(shù)為3t+m

valcollink第二種鏈?zhǔn)剑菏宙湵?設(shè)行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個(gè)非零元*結(jié)點(diǎn)定義tpedef

structnode{int

row,col,val;

structnode*down,*right;}JD;

row

col

valdownright113418225234^^^^^^^

5.4廣義表的定義

廣義表（Lists，又稱列表）是線性表的推廣。在第2章中，我們把線性表定義為n>=0個(gè)元素a1,a2,a3,…,an的有限序列。線性表的元素僅限于原子項(xiàng)，原子是作為結(jié)構(gòu)上不可分割的成分，它可以是一個(gè)數(shù)或一個(gè)結(jié)構(gòu)，若放松對(duì)表元素的這種限制，容許它們具有其自身結(jié)構(gòu)，這樣就產(chǎn)生了廣義表的概念。廣義表是n(n>=0)個(gè)元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項(xiàng)，或者是一個(gè)廣義表。通常記作LS=（a1,a2,a3,…,an)。LS是廣義表的名字，n為它的長(zhǎng)度。若ai是廣義表，則稱它為L(zhǎng)S的子表。廣義表的結(jié)構(gòu)特點(diǎn):1)廣義表中的數(shù)據(jù)元素有相對(duì)次序;2)廣義表的長(zhǎng)度定義為最外層包含的元素個(gè)數(shù);3)廣義表的深度定義為所含括弧的重?cái)?shù);

注意:“原子”的深度為“0”;

“空表”的深度為14)表頭可以是原子或列表;表尾必定是列表。5)廣義表可以是一個(gè)遞歸的表;

遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。A=()

//A是一個(gè)空表,它的長(zhǎng)度為零B=(e)//列表B只有一個(gè)原子e,B的長(zhǎng)度為1.C=(a,(b,c,d))//

列表C的長(zhǎng)度為2,兩個(gè)元素分別為原子a和子表(b,c,d)D=(A,B,C)//列表D的長(zhǎng)度為3,三個(gè)元素都是列表,顯然,

將子表的值代入后,則有D=((),(e),(a,(b,c,d)))E=(a,E)//

這是一個(gè)遞歸的表,它的長(zhǎng)度為2,E相當(dāng)于一個(gè)無(wú)限的列表E=(a,(a,(a,...)))[注：]一般用大寫字母表示廣義表，小寫字母表示原子項(xiàng)廣義表是一個(gè)多層次的線性結(jié)構(gòu)。例如:有A、B、C、D、E五個(gè)廣義表的描述如下：

[定義：]

任何一個(gè)非空廣義表

LS=(1,2,…,n)均可分解為兩部分

表頭

Head[LS]=Head[(1,2,…,n)]=1

表尾Tail[LS]=Tail[(1,2,…,n)]=(2,…,n)

若用圓括號(hào)代替方括號(hào)需事先聲明它是head或tail的定界符[例:]Head[(((b,c)))]=((b,c))Tail[(((b,c)))]=()

Head[(a,(b,c))]=aTail[(a,(b,c))]=((b,c))Head[((c))]=(c)Tail[((c))]=()[例:]1.廣義表((a),((b),c),(((d))))的長(zhǎng)度是:3；深度是:42.廣義表((a),((b),c),d,e,((I,j),k))的長(zhǎng)度是:5；深度是:3[例：]廣義表((a),a)的表頭是:(a)，表尾是:(a)廣義表