數(shù)組和廣義表ppt

第5章數(shù)組和廣義表---廣義線性表5.1數(shù)組的概念和存儲(chǔ)5.2特殊矩陣的壓縮存儲(chǔ)5.3稀疏矩陣的壓縮存儲(chǔ)5.4廣義表15.1數(shù)組一、數(shù)組的定義數(shù)組：它是n（n>1)個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,…,an-1構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限序列。數(shù)組的下標(biāo)：數(shù)組元素的位置。注意：（1）C語(yǔ)言的數(shù)組定義下標(biāo)從0開始。①數(shù)組中各元素具有統(tǒng)一的類型；②數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡(jiǎn)單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。(2)一個(gè)二維數(shù)組可以看作每個(gè)數(shù)據(jù)元素是一個(gè)一維數(shù)組的一維數(shù)組。二維數(shù)組是兩維的，內(nèi)存單元是一維的，存在向內(nèi)存存儲(chǔ)時(shí)二維數(shù)組中數(shù)據(jù)元素的存儲(chǔ)方法問題，C語(yǔ)言采用以行序?yàn)橹餍虻姆椒ù鎯?chǔ)。2討論：數(shù)組與線性表的區(qū)別與聯(lián)系

相同之處：

它們都是若干個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,…，an-1構(gòu)成的有限序列。

不同之處：

(1)數(shù)組要求其元素占用一塊地址連續(xù)的內(nèi)存單元空間，而線性表無此要求；(2)線性表的元素是邏輯意義上不可再分的元素，而數(shù)組中的每個(gè)元素還可以是一個(gè)數(shù)組；(3)數(shù)組的操作主要是向某個(gè)下標(biāo)的數(shù)組元素中存放數(shù)據(jù)和取某個(gè)下標(biāo)的數(shù)組元素，這與線性表的插入和刪除操作不同。3二、數(shù)組的實(shí)現(xiàn)機(jī)制１、一維數(shù)組（n個(gè)元素）中任一元素ai的內(nèi)存單元地址LOC(ai)=LOC(a０)+i*k(0≤i<n)２、一個(gè)m行n列的二維數(shù)組LOC(aij)=LOC(a00)+(i*n+j)*k(0≤i<m，0≤j<n)注：C語(yǔ)言中數(shù)組元素采用行主序的存放方法，即行優(yōu)先順序。a０的內(nèi)存單元地址每個(gè)元素所需的字節(jié)個(gè)數(shù)每個(gè)元素所需的字節(jié)個(gè)數(shù)a０0的內(nèi)存單元地址一個(gè)m×n的二維數(shù)組可以看成是m行的一維數(shù)組，或者n列的一維數(shù)組。a0,0a0,1…a0,n-1

a1,0a1,1…a1,n-1

…………

am-1,0am-1,1…am-1,n-1

Amn=4本行中aij前面的元素個(gè)數(shù)每行元素個(gè)數(shù)整行數(shù)aij前面的元素個(gè)數(shù)=陰影部分的面積=整行數(shù)×每行元素個(gè)數(shù)+本行中aij前面的元素個(gè)數(shù)=(i

-l1)×(h2

-l2＋1)＋(j

-l2)二維數(shù)組尋址的計(jì)算方法（行序優(yōu)先）l2h2

l1h1(a)二維數(shù)組aij5aij前面的元素個(gè)數(shù)=陰影部分的面積=整列數(shù)×每列元素個(gè)數(shù)+本列中aij前面的元素個(gè)數(shù)=(j

–l2)×(h1

–l1＋1)＋(i-l1)二維數(shù)組尋址的計(jì)算方法（列序優(yōu)先）l2h2

l1h1(a)二維數(shù)組aij整列數(shù)

每列元素個(gè)數(shù)

本列中aij前面的元素個(gè)數(shù)6對(duì)于行優(yōu)先順序：先變化多維數(shù)組中最右邊的下標(biāo)，從右往左，最后變化最左邊的下標(biāo)；對(duì)于列優(yōu)先順序：先變化數(shù)組中最左邊的下標(biāo)，從左往右，最后變化最右邊的下標(biāo)；數(shù)組尋址的計(jì)算方法結(jié)論：7思考：任一元素存儲(chǔ)地址的計(jì)算方法你能推導(dǎo)出來嗎？

思考：

n（n＞2）維數(shù)組，一般也采用按行優(yōu)先和按列優(yōu)先兩種存儲(chǔ)方法。請(qǐng)給出基本思想和尋址計(jì)算方法？8

下標(biāo)為i1,i2,i3的數(shù)組元素的存儲(chǔ)地址：按頁(yè)/行/列存放

各維元素個(gè)數(shù)為m1,m2,m3LOC(aijk)=Loc(a000)+(i*m2*m3+j*m3+k)*l

三維數(shù)組尋址的計(jì)算方法：（按行序優(yōu)先）9

可將以上規(guī)則推廣到n維數(shù)組：

n維數(shù)組A[t1][t2]…[tn]，可看成是由t1個(gè)（n1）維數(shù)組組成的特殊線性表：a1[t2][t3]…[tn]，a2[t2][t3]…[tn]，…，at1[t2][t3]…[tn]可按線性表的順序存儲(chǔ)方法，先存儲(chǔ)第一個(gè)n1維數(shù)組a1[t2][t3]…[tn]，緊接著存儲(chǔ)第二個(gè)n1維數(shù)組a2[t2][t3]…[tn]，……，最后存儲(chǔ)第t1個(gè)n1維數(shù)組at1[t2][t3]…[tn]。

對(duì)于每個(gè)n1維數(shù)組，又可看成是由t2個(gè)n2維的數(shù)組組成的特殊線性表，其余類推，直到最后看成是tn個(gè)數(shù)組元素組成的一維數(shù)組。10

同理，若n維數(shù)組第一個(gè)元素的存儲(chǔ)位置為L(zhǎng)OC(a00…0)，那么對(duì)于任何一組有效的下標(biāo)i1,i2,…,in，其對(duì)應(yīng)的數(shù)組元素ai1,i2,…,in的存儲(chǔ)位置LOC(ai1,i2,…,in)為：LOC(ai1,i2,…,in)=LOC(a00…0)+d[i1t2t3…tn+i2t3t4…tn+in1tn+in]=LOC(a00…0)+d式中11注：只要知道以下三要素便可隨時(shí)求出任一元素的地址（意義：數(shù)組中的任一元素可隨機(jī)存?。?/p>

①開始結(jié)點(diǎn)的存放首字節(jié)地址（即基地址）；

②維數(shù)和每維的上、下界；

③每個(gè)數(shù)組元素所占用的單元數(shù)。例１一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是

個(gè)字節(jié)。答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例２

設(shè)數(shù)組a[０…60,０…70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為

。答：根據(jù)行優(yōu)先公式LOC(aij)=LOC(a00)+(i*n+j)*k(0≤i<m，0≤j<n)得：LOC(a32,58)=2048+(32*71+58)*2＝67082886708125.2特殊矩陣的壓縮存儲(chǔ)

特殊矩陣:指有許多值相同的元素或有許多零元素、且值相同的元素或零元素的分布有一定規(guī)律的矩陣。下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。1、n階對(duì)稱矩陣在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)：aij=aji（1≦i,j≦n）則稱A為n階對(duì)稱矩陣。15137a1150800a21a2218926a31a32a3330251………………..70613an1an2an3…ann

圖5.1對(duì)稱矩陣n階對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失一般性，我們按“行優(yōu)先順序”存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素。135.2特殊矩陣的壓縮存儲(chǔ)在矩陣中很多值相同的元素并且它們的分布有一定的規(guī)律，我們將這樣的矩陣稱為特殊矩陣。若矩陣中有很多零元素稱為稀疏矩陣

壓縮存儲(chǔ)的基本思想是：⑴為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；⑵

對(duì)零元素不分配存儲(chǔ)空間。

145.2.1特殊矩陣的壓縮存儲(chǔ)——對(duì)稱矩陣364786

284248

169746

058295

7A＝5階對(duì)稱矩陣對(duì)稱矩陣特點(diǎn)：在一個(gè)n階方陣中，有aij=aji

，其中1≤i,j≤n。

只需要n×（n＋1）/2個(gè)存儲(chǔ)單元。討論：如何只存儲(chǔ)下三角部分的元素呢？

15(a)下三角矩陣(b)存儲(chǔ)說明(c)計(jì)算方法aij在一維數(shù)組中的序號(hào)=陰影部分的面積=i×(i+1)/2+j+1∵一維數(shù)組下標(biāo)從0開始∴aij在一維數(shù)組中的下標(biāo)k=i×(i+1)/2+j0…

in-10…j…n-1

aij每行元素個(gè)數(shù)12…iaij在本行中的序號(hào)aij第0行第1行…第i-1行對(duì)稱矩陣按行優(yōu)先存儲(chǔ)尋址示意圖16結(jié)論：將下三角中的所有元素按行優(yōu)先存儲(chǔ)到一維數(shù)組SA中，下三角中的元素aij（i≥j）在數(shù)組SA中的下標(biāo)k與i、j的關(guān)系為：k＝i×(i＋1)/2＋j。同理我們可以得到：上三角中的元素aij（i＜j），因?yàn)閍ij＝aji，則訪問和它對(duì)應(yīng)的元素aji即可，即：k＝j(luò)×(j＋1)/2＋i。即將i,j下標(biāo)互換。第1行第n-1行第0行a00a10a11a20a21a22aij…an-10an-11…an-1n-1…第2行012345kn(n+1)/2-1對(duì)稱矩陣的壓縮存儲(chǔ)

17總結(jié)：對(duì)稱矩陣A中任一元素aij在一維數(shù)組SA中的存儲(chǔ)位置可用如下公式計(jì)算：Loc(aij)=Loc(sa[k])=Loc(sa[0])+k*d=Loc(sa[0])+[I*(I+1)/2+J)]*d其中，I=max(i,j)J=min(i,j)185.2.2特殊矩陣的壓縮存儲(chǔ)——三角矩陣3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩陣思考：如何只存儲(chǔ)下三角部分或上三角部分的元素？

只需存儲(chǔ)n×(n＋1)/2＋119012345kn(n+1)/2第1行第n-1行第0行a00a10a11a20a21a22aij…an-10an-11…an-1n-1…第2行c下三角矩陣的壓縮存儲(chǔ)既要存儲(chǔ)下三角中的元素，還要存儲(chǔ)對(duì)角線上方的常數(shù)。因?yàn)槭峭粋€(gè)常數(shù)，所以只存一個(gè)即可。

對(duì)于上三角矩陣，其存儲(chǔ)思想與下三角類似，按行存儲(chǔ)上三角部分，最后存儲(chǔ)對(duì)角線下方的常數(shù)。

20結(jié)論：1.下三角矩陣中任一元素aij在SA中的下標(biāo)k與i、j的對(duì)應(yīng)關(guān)系為：i×(i＋1)/2＋j當(dāng)i≥jn×(n＋1)/2當(dāng)i＜jk=2.上三角矩陣中任一元素aij在SA中的下標(biāo)k與i、j的對(duì)應(yīng)關(guān)系為：

i×(2n－i＋1)/2＋j－i當(dāng)i≤jn×(n＋1)/2當(dāng)i＞jk=215.2.3特殊矩陣的壓縮存儲(chǔ)——對(duì)角矩陣

所謂對(duì)角矩陣是指所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，除了主對(duì)角線和它的上下方若干條對(duì)角線的元素外，所有其他元素都為零。

對(duì)角矩陣的壓縮存儲(chǔ)方法

0

00

000

000

000

A=a00a01a43

a44a10a11

a12a21a22

a23a32a33

a34(a)三對(duì)角矩陣按行存儲(chǔ)非零元素a00a01a10a11a12a21a22a23a32a33a34a43a440123456789101112元素aij在一維數(shù)組中的序號(hào)=2+3(i－1)+(j－i+2)=2i+j+1

∵一維數(shù)組下標(biāo)從0開始∴元素aij在一維數(shù)組中的下標(biāo)=2i+j思考：一般的，對(duì)于矩陣半寬帶為b的對(duì)角矩陣按行優(yōu)先存儲(chǔ)到一維數(shù)組的通項(xiàng)公式為？225.3稀疏矩陣什么是稀疏矩陣?它有哪些特征?1、稀疏矩陣矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）。2、稠密矩陣

一個(gè)不稀疏的矩陣。說明：稀疏矩陣的壓縮存儲(chǔ)結(jié)構(gòu)主要有三元組順序表和三元組鏈表兩大類型。三元組定義:將稀疏矩陣中的每個(gè)非零元素表示為：(行號(hào)，列號(hào)，非零元素值)稱為三元組表示法。23三元組表：將稀疏矩陣的非零元素對(duì)應(yīng)的三元組所構(gòu)成的集合，按行優(yōu)先的順序排列成一個(gè)線性表。注意：data數(shù)組中表示的非零元素以行序?yàn)橹餍蝽樞蚺帕?，它是一種下標(biāo)按行有序的存儲(chǔ)結(jié)構(gòu)。C中，用結(jié)構(gòu)類型來描述三元組：typedefstructthree{intr,c;ElemTyped;}TupNode;把稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)定義成三元組順序表的控制數(shù)據(jù)結(jié)構(gòu)體：typedefstructthreelist{introws,columns,nums;TupNodedata[MAXSize];}TSMatrix;1.稀疏矩陣的三元組順序表24稀疏矩陣順序存儲(chǔ)——三元組順序表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的三元組表稱為三元組順序表。稀疏矩陣1300780115

01236000

0006500

00000099

00000A=A的三元組順序表00130378051151112123623654099

空空空閑閑閑567rcd0123456MaxTerm-1矩陣的行數(shù)矩陣的列數(shù)非零元個(gè)數(shù)25稀疏矩陣順序存儲(chǔ)——三元組順序表矩陣運(yùn)算包括矩陣轉(zhuǎn)置、矩陣加、矩陣減、矩陣乘等。1.從一個(gè)二維矩陣創(chuàng)建其三元組表示以行序方式掃描二維矩陣a,將其非零元素插入到三元組t中。voidCreatMat(TSMatrix&t,ElemTypeA[M][N]){inti,j;t.rows=M;t.cols=N;t.nums=0;for(i=0;i<M;i++){for(j=0;j<N;j++)if(A[i][j]!=0){t.data[t.nums].r=i;t.data[t.nums].c=j;t.data[t.nums].d=A[i][j];t.nums++;}}}26先在三元組t中找到適當(dāng)?shù)奈恢胟,將k~t.nums個(gè)元素后移一個(gè)位置，將指定元素x插入到t.data[k]處。intValue(TSMatrix&t,ElemTypex,intrs,intcs){inti,k=0;if((rs>=t.rows)||(cs>=t.cols))return0;while(k<t.nums&&rs>t.data[k].r)k++;while(k<t.nums&&rs==t.data[k].r&&cs>t.data[k].c)k++;if(t.data[k].r==rs&&t.data[k].c==cs)t.data[k].d=x;else{for(i=t.nums-1;i>=k;i--){t.data[i+1].r=t.data[i].r;t.data[i+1].c=t.data[i].c;t.data[i+1].d=t.data[i].d;}t.data[k].r=rs;t.data[k].c=cs;t.data[k].d=x;t.nums++;}return1;}稀疏矩陣順序存儲(chǔ)——三元組元素賦值27答：不正確！除了：（1）每個(gè)元素的行下標(biāo)和列下標(biāo)互換（即三元組中的r和c互換）；還需要：（2）T的總行數(shù)rows和總列數(shù)columns也要互換；（3）重排三元組內(nèi)各元素順序，使轉(zhuǎn)置后的三元組也按行（或列）為主序有規(guī)律的排列。上述（1）和（2）容易實(shí)現(xiàn)，難點(diǎn)在（3）。

若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種說法正確嗎？提問：28稀疏矩陣三元組順序表存儲(chǔ)操作——轉(zhuǎn)置算法Ⅰ直接取，順序存該算法的基本思想是：在A的三元組順序表中依次找第0列、第1列、…直到最后一列的三元組，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B的三元組順序表中。例：13000990120000360007806500000001150000B=三元組順序表A的轉(zhuǎn)置29算法的偽代碼描述：1.設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)；2.在B中設(shè)置初始存儲(chǔ)位置q；3.for(v=最小列號(hào);v<=最大列號(hào);v++)3.1在A中查找列號(hào)為v的三元組；3.2交換其行號(hào)和列號(hào)，存入B中q位置；3.3q++；30對(duì)于一個(gè)m×n的矩陣Am×n,其轉(zhuǎn)置矩陣是一個(gè)n×m的矩陣。voidTranTat(TSMatrixt,TSMatrix&tb){intp,1=0,v;tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if(t.nums!=0){for(v=0;v<t.cols;v++)for(p=0;p<t.nums;p++)if(t.data[p].c==v){tb.data[q].r=t.data[p].c;tb.data[q].c=t.data[p].r;tb.data[q].d=t.data[p].d;q++;}}}31稀疏矩陣三元組順序表存儲(chǔ)操作——轉(zhuǎn)置算法Ⅱ順序取，直接存分析：如何確定當(dāng)前從A中取出的三元組在B中的位置。注意到A中第0列的第一個(gè)非零元素一定存儲(chǔ)在B中下標(biāo)為0的位置上，該列中其它非零元素應(yīng)存放在B中后面連續(xù)的位置上，那么第1列的第一個(gè)非零元素在B中的位置便等于第0列的第一個(gè)非零元素在B中的位置加上第0列的非零元素的個(gè)數(shù)，以此類推。該算法的基本思想：是在A中依次取三元組，交換其行號(hào)和列號(hào)放到B中適當(dāng)位置。321.引入兩個(gè)數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：num[nu]：表示矩陣A中某列的非零元素的個(gè)數(shù)；cpot[nu]：初始值表示矩陣A中某列的第一個(gè)非零元素在B中的位置。算法設(shè)計(jì)：cpot[1]=1；cpot[col]=cpot[col-1]+num[col-1]；2≤col＜n2.num與cpot遞推關(guān)系：331.設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)；2.計(jì)算A中每一列的非零元素個(gè)數(shù)；3.計(jì)算A中每一列的第一個(gè)非零元素在B中的下標(biāo)；4.依次取A中的每一個(gè)非零元素對(duì)應(yīng)的三元組；4.1確定該元素在B中的下標(biāo)pb；4.2將該元素的行號(hào)列號(hào)交換后存入B中pb的位置；4.3預(yù)置該元素所在列的下一個(gè)元素的存放位置；算法的偽代碼：342.稀疏矩陣的十字鏈表表示——十字鏈表稀疏矩陣鏈接存儲(chǔ)的基本思想是：將每個(gè)非零