數(shù)組和廣義表ppt

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

相同之處：

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

不同之處：

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

-l1)×(h2

-l2＋1)＋(j

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

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

–l2)×(h1

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

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

每列元素個數(shù)

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

思考：

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

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

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

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

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

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

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

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

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

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

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

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

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

。答：根據(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特殊矩陣的壓縮存儲

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

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

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

對零元素不分配存儲空間。

145.2.1特殊矩陣的壓縮存儲——對稱矩陣364786

284248

169746

058295

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

，其中1≤i,j≤n。

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

15(a)下三角矩陣(b)存儲說明(c)計算方法aij在一維數(shù)組中的序號=陰影部分的面積=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每行元素個數(shù)12…iaij在本行中的序號aij第0行第1行…第i-1行對稱矩陣按行優(yōu)先存儲尋址示意圖16結(jié)論：將下三角中的所有元素按行優(yōu)先存儲到一維數(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，則訪問和它對應(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對稱矩陣的壓縮存儲

17總結(jié)：對稱矩陣A中任一元素aij在一維數(shù)組SA中的存儲位置可用如下公式計算：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特殊矩陣的壓縮存儲——三角矩陣3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

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

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

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

20結(jié)論：1.下三角矩陣中任一元素aij在SA中的下標(biāo)k與i、j的對應(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的對應(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特殊矩陣的壓縮存儲——對角矩陣

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

對角矩陣的壓縮存儲方法

0

00

000

000

000

A=a00a01a43

a44a10a11

a12a21a22

a23a32a33

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

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

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

01236000

0006500

00000099

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

空空空閑閑閑567rcd0123456MaxTerm-1矩陣的行數(shù)矩陣的列數(shù)非零元個數(shù)25稀疏矩陣順序存儲——三元組順序表矩陣運(yùn)算包括矩陣轉(zhuǎn)置、矩陣加、矩陣減、矩陣乘等。1.從一個二維矩陣創(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個元素后移一個位置，將指定元素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;}稀疏矩陣順序存儲——三元組元素賦值27答：不正確！除了：（1）每個元素的行下標(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ù)存儲稀疏矩陣，只要把每個元素的行下標(biāo)和列下標(biāo)互換，就完成了對該矩陣的轉(zhuǎn)置運(yùn)算，這種說法正確嗎？提問：28稀疏矩陣三元組順序表存儲操作——轉(zhuǎn)置算法Ⅰ直接取，順序存該算法的基本思想是：在A的三元組順序表中依次找第0列、第1列、…直到最后一列的三元組，并將找到的每個三元組的行、列交換后順序存儲到B的三元組順序表中。例：13000990120000360007806500000001150000B=三元組順序表A的轉(zhuǎn)置29算法的偽代碼描述：1.設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元素的個數(shù)；2.在B中設(shè)置初始存儲位置q；3.for(v=最小列號;v<=最大列號;v++)3.1在A中查找列號為v的三元組；3.2交換其行號和列號，存入B中q位置；3.3q++；30對于一個m×n的矩陣Am×n,其轉(zhuǎn)置矩陣是一個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稀疏矩陣三元組順序表存儲操作——轉(zhuǎn)置算法Ⅱ順序取，直接存分析：如何確定當(dāng)前從A中取出的三元組在B中的位置。注意到A中第0列的第一個非零元素一定存儲在B中下標(biāo)為0的位置上，該列中其它非零元素應(yīng)存放在B中后面連續(xù)的位置上，那么第1列的第一個非零元素在B中的位置便等于第0列的第一個非零元素在B中的位置加上第0列的非零元素的個數(shù)，以此類推。該算法的基本思想：是在A中依次取三元組，交換其行號和列號放到B中適當(dāng)位置。321.引入兩個數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：num[nu]：表示矩陣A中某列的非零元素的個數(shù)；cpot[nu]：初始值表示矩陣A中某列的第一個非零元素在B中的位置。算法設(shè)計：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ù)和非零元素的個數(shù)；2.計算A中每一列的非零元素個數(shù)；3.計算A中每一列的第一個非零元素在B中的下標(biāo)；4.依次取A中的每一個非零元素對應(yīng)的三元組；4.1確定該元素在B中的下標(biāo)pb；4.2將該元素的行號列號交換后存入B中pb的位置；4.3預(yù)置該元素所在列的下一個元素的存放位置；算法的偽代碼：342.稀疏矩陣的十字鏈表表示——十字鏈表稀疏矩陣鏈接存儲的基本思想是：將每個非零