數(shù)據(jù)結(jié)構(gòu)課件數(shù)組與廣義表

一、教學(xué)內(nèi)容：

1、數(shù)組的定義和順序存儲(chǔ)方式；

2、特殊矩陣的壓縮存儲(chǔ)；

3、稀疏矩陣

4、廣義表的概念、表示及基本操作；廣義表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)。

二、教學(xué)要求：

1、了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法；

2、掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式；

3、了解稀疏矩陣的兩種壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍，理解以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法；

4、掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法，會(huì)對(duì)非空廣義表進(jìn)行分解。第五章數(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ù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的數(shù)據(jù)元素本身也是一種線性表。5.1數(shù)組的定義由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡(jiǎn)單。多維數(shù)組是向量的推廣。例如，二維數(shù)組：

()()()()()()()()()M個(gè)行向量N個(gè)列向量在C語(yǔ)言中，一個(gè)二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說(shuō)，

typedefelemtypearray2[m][n];

等價(jià)于：

typedefelemtypearray1[n];typedefarray1array2[m];

數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。

5.2數(shù)組的順序表示和實(shí)現(xiàn)

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

通常有兩種順序存儲(chǔ)方式：以行序?yàn)橹餍蛞粤行驗(yàn)橹餍?/p>

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

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

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

amn

……..

am2

am1

……….

a2n……..

a22

a21

a1n

…….

a12

a1101n-1m*n-1n

按列序?yàn)橹餍虼娣琶總€(gè)元素占一個(gè)單元01m-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

計(jì)算二維數(shù)組元素地址的通式

設(shè)一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是0。無(wú)論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時(shí)求出任一元素的地址（這樣數(shù)組中的任一元素便可以隨機(jī)存?。。憾S數(shù)組列優(yōu)先存儲(chǔ)的通式為：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L

ac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

Amn=單個(gè)元素長(zhǎng)度aij之前的行數(shù)數(shù)組基址總列數(shù)，即第2維長(zhǎng)度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例2：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,按列存儲(chǔ)的公式是？

Loc(aij)=Loc(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ǔ)地址為

。8950LOC(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答：請(qǐng)注意審題！利用列優(yōu)先通式：答：

Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288

5.3矩陣的壓縮存儲(chǔ)

在科學(xué)與工程計(jì)算問題中，矩陣是一種常用的數(shù)學(xué)對(duì)象，在高級(jí)語(yǔ)言編制程序時(shí)，簡(jiǎn)單而又自然的方法，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡(jiǎn)單，并且存儲(chǔ)的密度為1。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來(lái)存儲(chǔ)密度仍為1，但實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)造成極大的浪費(fèi)，為了節(jié)省存儲(chǔ)空間，我們可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)：即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。5.3.1特殊矩陣

所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。1、對(duì)稱矩陣在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)：

aij=aji0≦i,j≦n-1則稱A為對(duì)稱矩陣。對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失一般性，我們按“行優(yōu)先順序”存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素，其存儲(chǔ)形式如圖所示：

15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1在這個(gè)下三角矩陣中，第i行恰有i+1個(gè)元素，元素總數(shù)為：n(n+1)/2

因此，我們可以按從上到下、從左到右將這些元素存放在一個(gè)向量sa[0..n(n+1)/2-1]中。為了便于訪問對(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

特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)向量中，并且一般都能找到矩陣中的元素與該向量的對(duì)應(yīng)關(guān)系，通過(guò)這個(gè)關(guān)系，仍能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。2.5.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í)稱之為稀疏矩陣。在存儲(chǔ)稀疏矩陣時(shí)，為了節(jié)省存儲(chǔ)單元，很自然地想到使用壓縮存儲(chǔ)方法。但由于非零元素的分布一般是沒有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（i,j)。反之，一個(gè)三元組(i,j,aij)唯一確定了矩陣A的一個(gè)非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。1、三元組表示法例如，下列三元組表((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ì)行、列值便可作為下列矩陣M的另一種描述。

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000

M=T=如果有k個(gè)非零元素，需要3k個(gè)存儲(chǔ)單元?？蓪和j作為關(guān)鍵碼，查找矩陣元素。缺點(diǎn)：當(dāng)數(shù)據(jù)元素值從0變?yōu)榉?，要想表中插入結(jié)點(diǎn)，為了保持行優(yōu)先順序，插入要移動(dòng)后面的元素。三元組順序表假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表，則可得到稀疏矩陣的一種壓縮存儲(chǔ)方法——三元順序表。#definemaxsize10000typedefintdatatype;typedefstruct{inti,j;//該非零元的行下標(biāo)和列下標(biāo)datatypev;}triplet;typedefstruct{tripledata[maxsize];intm,n,t;//矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)}tripletable;帶行指針向量的單鏈表表示每行的非零元用一個(gè)單鏈表存放設(shè)置一個(gè)行指針數(shù)組，指向本行第一個(gè)非零元結(jié)點(diǎn)；若本行無(wú)非零元，則指針為空2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedefstructnode{intcol;intval;structnode*link;}JD;typedefstructnode*TD;^13573-11-12-242^^^^需存儲(chǔ)單元個(gè)數(shù)為3t+m表頭結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)類型定義矩陣的一個(gè)非零元素用一個(gè)結(jié)點(diǎn)表示，每個(gè)結(jié)點(diǎn)包括五個(gè)字段，分別為元素的行下標(biāo)、列下標(biāo)、值以及指向本行和本列下一個(gè)非零元素的指針。需要存儲(chǔ)空間5k+m+n具有鏈表的靈活性（插入、刪除方便）3、行-列表示法（十字鏈表）tpedefstructnode{introw,col,val;structnode*down,*right;}JD;rowcolvaldownright113418225234^^^^^^^第五章廣義表廣義表的基本概念廣義表的鏈接存儲(chǔ)結(jié)構(gòu)一、基本概念廣義表是第二章提到的線性表的推廣。線性表中的元素僅限于原子項(xiàng)(單個(gè)數(shù)據(jù)元素)，即不可以再分，而廣義表中的元素既可以是原子項(xiàng)，也可以是子表(另一個(gè)線性表)。(如果ai是單個(gè)數(shù)據(jù)元素,則稱ai為廣義表的原子)1．廣義表的定義廣義表是n≥0個(gè)元素a0，a1，…，an-1的有限序列，其中每一個(gè)ai或者是原子，或者是一個(gè)子表。廣義表通常記為GL=(a0,a1,…,an-1)，其中GL為廣義表的名字，n為廣義表的長(zhǎng)度，每一個(gè)ai為廣義表的元素。但在習(xí)慣中，一般用大寫字母表示廣義表，小寫字母表示原子。稱第一個(gè)元素a0為廣義表GL的表頭,其余部分(a1,...an-1)為GL的表尾,分別記作head(GL)=a0和tail(GL)=(a1,...an-1)說(shuō)明:1.廣義表是線性表的一種推廣。2.廣義表的定義是遞歸的。因?yàn)樵诿枋鰪V義表的時(shí)候又用到了廣義表的概念.3.廣義表是多層次結(jié)構(gòu)。4.一個(gè)廣義表可以為其它廣義表所共享。2．廣義表舉例(1)A=(),A為空表，長(zhǎng)度為0。(2)B=(a,（b,c)),B是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為子表。(3)C=(x,y,z)C是長(zhǎng)度為3的廣義表，每一項(xiàng)都是原子。(4)D=(B,C)，D是長(zhǎng)度為2的廣義表，每一項(xiàng)都是上面提到的子表。(5)E=(a,E)是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為它本身。（遞歸）3．廣義表的深度

一個(gè)廣義表的深度是指該廣義表展開后所含括號(hào)的層數(shù)。例如，A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為3。4．取表頭運(yùn)算head若廣義表LS=(a1，a2，…，an)，則head(LS)=a1。取表頭運(yùn)算得到的結(jié)果可以是原子，也可以是一個(gè)子表。例如，head((a1,a2,a3,a4))=a1，head(((a1,a2),(a3,a4),a5))=(a1,a2)。5．取表尾運(yùn)算tail若廣義表LS=(a1，a2，…，an)，則tail(LS)=(a2，a3，…，an)。即取表尾運(yùn)算得到的結(jié)果是除表頭以外的所有元素，取表尾運(yùn)算得到的結(jié)果一定是一個(gè)子表。值得注意的是廣義表()和(())是不同的，前者為空表，長(zhǎng)度為0，后者的長(zhǎng)度為1，可得到表頭、表尾均為空表，即head((()))=()，tail((()))=()。1.GetTail【(b,k,p,h)】＝

;2.GetHead【((a,b),(c,d))】＝

;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.Ge