數(shù)據(jù)結(jié)構(gòu)4數(shù)組

第4章數(shù)組

4.1數(shù)組定義及基本操作

4.2數(shù)組的存儲結(jié)構(gòu)

4.3特殊矩陣的壓縮存儲

4.4稀疏矩陣的壓縮存儲

4.5數(shù)組的運(yùn)算

2/1/20231第4章數(shù)組

數(shù)組是我們最常用的一種數(shù)據(jù)結(jié)構(gòu)，各種計算機(jī)語言均有此類型。例如：順序表、順序棧、循環(huán)隊列等。１．?dāng)?shù)組的定義：數(shù)組：是ｎ（ｎ＞１）個相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1…an-1,構(gòu)成的占用一塊連續(xù)的內(nèi)存單元的有限序列。數(shù)組特點：

1.有限個元素的集合；

2.所有元素具有相同的特性；

3.元素名由數(shù)組名和下標(biāo)組成；

4.下標(biāo)值與元素對應(yīng)（代表元素的位置）。4.1數(shù)組的定義及操作2/1/20232第4章數(shù)組

數(shù)組與線性表:相同之處:由若干個相同數(shù)據(jù)類型的數(shù)據(jù)元素組成.不同之處:1.存儲單元連續(xù)與否

2.數(shù)據(jù)元素在邏輯意義上可分與否

3.操作不同。2/1/20233第4章數(shù)組２.數(shù)組的邏輯結(jié)構(gòu)

一維數(shù)組（a0,a1,a2,a3,…an-1）滿足線性關(guān)系；二維或二維以上數(shù)組：（以二維為例）Amxn=a

a

…..

aa00

a01…….a0n-110111n-1……...a

a

am-10m-11m-1n-1看元素a11有兩個直接前趨a10和a01兩個直接后繼a21和a12三維數(shù)組:每個元素有三個直接前趨和三個直接后繼.可見:數(shù)組(除一維數(shù)組外)是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu).2/1/20234第4章數(shù)組但是:1)可將Amxn看成由m個行向量組成的向量,即

Amn={(a00,a01,……a0n-1),(a10,a11,……a1n-1),……(am-10,

am-11,……am-1n-1)}2)將Amxn看成由n個列向量組成的向量,即

Amn=((a00,a10,……am-10),(a01,a11,……am-11)……

(a0n-1,a1n-1,……am-1n-1))

列向量為線性.元素1元素2元素m看(ai0,ai1,…..ain-1),除ai0,ain-1

外只有一個直接前趨和一個直接后繼.元素1元素2元素n2/1/20235第4章數(shù)組

據(jù)此數(shù)組可看成是線性表的擴(kuò)展:即線性表中的數(shù)據(jù)元素本身也是一個數(shù)據(jù)結(jié)構(gòu).

數(shù)組可表示成兩類線性表:1.以行向量做線性表的一個元素;2.以列向量做線性表的一個元素.2/1/20236第4章數(shù)組３．?dāng)?shù)組抽象數(shù)據(jù)類型：數(shù)據(jù)集合：數(shù)組的數(shù)據(jù)集合可表示為a0,a1…an-1,每個數(shù)據(jù)元素的類型為抽象數(shù)據(jù)類型:DataType．（限定順序存儲）數(shù)據(jù)關(guān)系:線性關(guān)系.操作集合：

各種高級程序設(shè)計語言的操作各不相同，必備的操作有：（1）求數(shù)組元素個數(shù)（2）隨機(jī)?。?）隨機(jī)存（4）矩陣運(yùn)算2/1/20237第4章數(shù)組

一般數(shù)組:(以二維數(shù)組為例)多采用順序存儲:(1).按行優(yōu)先順序存儲

假設(shè)：Am×n=a00a01a02…a0n-1a10…a00a01a02a03…a0n-1

a10a11a12a13…a1n-1…am-10am-11am-12am-13…am-1n-1即a00,a01,a02……a0n-1,a10,a11,…...a1n-1……aij的存儲地址:am-1,04.2數(shù)組的存儲結(jié)構(gòu):2/1/20238第4章數(shù)組

L:為每個元素所占存儲單元.Pascal和C語言中數(shù)組存儲為此方式.Loc(aij)=Loc(a00)+(i*n+j)*L(2).列優(yōu)先順序存儲,即

a00,a10,a20……am-10,a01,a11,…...am-11……

aij存儲地址:

Loc(aij)=Loc(a00)+(j*m+i)*LFortran語言采用此方法.a00a10a20…am-10a01…可見:數(shù)組是一種隨機(jī)存儲結(jié)構(gòu).存取任意元素的時間相等2/1/20239第4章數(shù)組推廣:假設(shè):A[c1--d1][c2--d2]例：二維數(shù)組floata[4][3].計算（1）數(shù)組元素數(shù)目？（2）若數(shù)組Loc(a00)=1000,且L=4,數(shù)組元素a[3][2]的地址?(按行優(yōu)先存儲)4*3=12Loc(a32)=Loc(a00)+(i*n+j)*L=1000+(3*3+2)*4=1044Loc(aij)=Loc(ac1c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L按行優(yōu)先順序存儲：Loc(aij)=Loc(ac1c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*L按列優(yōu)先順序存儲：2/1/202310第4章數(shù)組特殊矩陣：指有一定量的零元素（或相同元素），并且其分布（非零元素的位置）有一定的規(guī)律。采用壓縮順序存儲方式:只存非零元素,節(jié)省空間.

1.下三角矩陣:

存放形式:{a00,a10,a11,a20,a21,…an-10,an-11,…an-1n-1}4.3特殊矩陣的壓縮存儲a0000……..0a10a110…….0……………….0an-10an-11…..an-1n-1Ann=可以是0和常數(shù)C第1行：1個第2行：2個第3行：3個……第n行：n個1+2+3+4+5+…+n=n(n+1)/22/1/202311第4章數(shù)組非零元素aij存儲地址:Loc(aij)=Loc(a00)+[i*(i+1)/2+j]*L（0≤j≤i≤n-1）K0123…n(n-1)/2…n(n+1)/2-1sb[k]a00a10a11a20…an-11…an-1n-12/1/202312第4章數(shù)組假設(shè)：以一維數(shù)組sb[n(n+1)/2+1]作為n階下三角矩陣A的存儲結(jié)構(gòu)，A中任意元素aij與sb[k]對應(yīng)關(guān)系如下：

i(i+1)/2+j當(dāng)i≥j時(非零元素)k=n(n+1)/2當(dāng)i<j時(零或常數(shù))其中：sb[k]:sb[0]~sb[n(n+1)/2-1]sb[n(n+1)/2]存放常數(shù)或零2/1/202313第4章數(shù)組2.對稱矩陣對稱矩陣：n階方陣A中的元素滿足：

aij

=aji

0≤i,j≤n-1存儲：可只存儲上三角矩陣或下三角矩陣將n*n個元素壓縮存儲到n(n+1)/2個元素空間中（sa數(shù)組）。以按行優(yōu)先存儲為例。A矩陣與sa[k]關(guān)系：上三角矩陣的存儲類似下三角矩陣，上三角矩陣自推i(i+1)/2+ji≥jj(j+1)/2+ii<jk=2/1/202314第4章數(shù)組K0123…n(n-1)/2…n(n+1)/2-1sa[k]a00a10a11a20…an-11…an-1n-1隱含a01a02…a1n-13.對角矩陣：形狀：Ann=非零元素帶2/1/202315第4章數(shù)組例：三對角陣

An×n=其中非零元素按行優(yōu)先順序存放：{a00,a01,a10,a11,a12,a21,a22,a23,…,an-1,n-2,an-1,n-1}

非零元素aij的地址關(guān)系式：Loc(aij)=Loc(a00)+2*i+j(i=0,j=0,1或i=n-1,j=n-2,n-1或0<i<n-1,j=i-1,i,i+1)推廣：n階對角陣有（2h-1）條非零元素帶。h2/1/202316第4章數(shù)組以上數(shù)組存儲方式與順序存儲線性表類似數(shù)組元素的存儲位置是其下標(biāo)的線性函數(shù)。總之：特殊矩陣的壓縮存儲方法：找出特殊矩陣的非零元素的分布規(guī)律，將其存儲到一個存儲空間，只需在算法中按公式計算即可實現(xiàn)矩陣元素的隨機(jī)存取。2/1/202317第4章數(shù)組稀疏因子：設(shè)在m*n的矩陣中，有t個非零元素，令稱為矩陣的稀疏因子。通常認(rèn)為<=0.05時為稀疏矩陣。我們在存儲的時候，除了存儲非零元的值之外，還得存儲它所在的行號和列號。由此構(gòu)成一個三元組(i,j,aij)，該三元組唯一確定了該矩陣元素。

4.4稀疏矩陣:2/1/202318第4章數(shù)組含有大量零元素的矩陣,且無規(guī)律。僅存非零元素,可省空間,避免大量無意義運(yùn)算,提高運(yùn)算效率.例:A=000700-100-1-20000000000020

1.順序存儲:按行優(yōu)先順序排列.(1).三元組順序表:每個結(jié)點由三個域組成

a.非零元素行下標(biāo);b.非零元素列下標(biāo);c.非零元素值.2/1/202319第4章數(shù)組

A的三元組順序表表示:(0,0,3)(0,4,7)(1,2,-1)(2,0,-1)(2,1,-2)(4,3,2)若有N個非零元素則需要3N個存儲單元

00304712-120-121-2432行列值6552/1/202320第4章數(shù)組2.鏈接存儲結(jié)構(gòu):(1)三元組(單)鏈表.

三元組線性表采用鏈接存儲結(jié)構(gòu)。(0,0,3)(0,4,7)(1,2,-1)(2,0,-1)(2,1,-2)(4,3,2)A=3000700-100-1-20000000000020

缺點：算法事件復(fù)雜度高300740-121-102-2122∧34h552/1/202321第4章數(shù)組01234/\

(2)行指針數(shù)組結(jié)構(gòu)的三元組鏈表.

設(shè)置一個行指針數(shù)組,數(shù)組中每個元素為指針類型,它指向本行矩陣的第一個非零元素,若該行無非零元素,則指針為空.

以A為例:行指針數(shù)組

0347/\2-1/\32/\1-2/\0-1A=3000700-100-1-20000000000020

2/1/202322第4章數(shù)組(3).三元組十字鏈表:上面介紹的行指針數(shù)組結(jié)構(gòu)的三元組鏈表形式容易實現(xiàn)按行找某列元素,不容易實現(xiàn)按列找某行元素.改進(jìn):按照行指針數(shù)組結(jié)構(gòu)的三元組鏈表形式構(gòu)造出相同結(jié)構(gòu)的列指針數(shù)組.例:A=000700-100-1-20000000000020

003/\-1/\/\12341234/\-1/\7/\/\-2/\/\2/\2/1/202323第4章數(shù)組為了方便算法中對矩陣的行方向和列方向的搜索。

采用動態(tài)存儲結(jié)構(gòu):每個非零元素用一個結(jié)點由五個數(shù)據(jù)域組成:三個數(shù)值,兩個指針.三個數(shù)值：i，j，value.表示非零元素的行號、列號和元素值。兩個指針：Down：向下指針

Right：向右指針行鏈表的頭結(jié)點與列鏈表的頭結(jié)點共用一個結(jié)點.ijValueDownRight十字鏈表設(shè)置：行頭結(jié)點、列頭結(jié)點和鏈表頭結(jié)點.linkDownRight行頭結(jié)點列頭結(jié)點(4).十字鏈表:2/1/202324第4章數(shù)組鏈表頭結(jié)點mnlink300700-10-1-2000000例:

A5×5=2/1/202325第4章數(shù)組4400303721-212-120-1headh1h1h2h2h3h3h4h4300700-10-1-20000002/1/202326第4章數(shù)組轉(zhuǎn)置運(yùn)算：設(shè)稀疏矩陣A以三元組表順序存儲結(jié)構(gòu)存放。三元組順序表結(jié)構(gòu)定義如下：#defineMAX100typedef

struct{inti;/*行*/

intj;/*列*/

DataTyped;/*元素值*/}tupletype;/*三元組*/typedef

struct{int

md;/*總行數(shù)*/

int

nd;/*總列數(shù)*/

inttd;/*總非零元素數(shù)*/

tupletypedata[MAX];}tabletype;/*三元組表*/4.5數(shù)組運(yùn)算：2/1/202327第4章數(shù)組mdndtdijdijdijdijdsa.md#defineMAX10typedef

struct{inti;/*行*/

intj;/*列*/

DataTyped;/*元素值*/}tupletype;/*三元組*/typedef

struct{int

md;/*總行數(shù)*/

int

nd;/*總列數(shù)*/

inttd;/*總非零元素數(shù)*/

tupletypedata[MAX];}tabletype;/*三元組表*/tabletype

sa;sa.ndsa.tdsa.data[].isa.data[].j2/1/202328第4章數(shù)組例：將稀疏矩陣A進(jìn)行轉(zhuǎn)置A=0011017000250000000000000000000037000000000025676021104171125301943375650sa:p=0766031911252011343740176550sb:q=0轉(zhuǎn)置v=02/1/202329第4章數(shù)組轉(zhuǎn)置算法：Voidtrantup(tabletype

sa,tabletype*sb){intp,q,v;

sb->md=sa.nd;

sb->nd=sa.md;

sb->td=sa.td;

if(sb->td!=0){q=0;for(v=0;v<sa.nd;v++){for(p=0;p<sa.td;p++){if(sa.data[p].j==v){sb->data[q].i=sa.data[p].j;

sb->data[q].j=sa.data[p].i;

sb->data[q].d=sa.data[p].d;