第4章數組

4.1數組定義及基本操作

4.2數組的存儲結構

4.3特殊矩陣的壓縮存儲

4.4稀疏矩陣的壓縮存儲

4.5數組的運算

2/1/20231第4章數組

數組是我們最常用的一種數據結構，各種計算機語言均有此類型。例如：順序表、順序棧、循環隊列等。１．數組的定義：數組：是ｎ（ｎ＞１）個相同數據類型的數據元素a0,a1…an-1,構成的占用一塊連續的內存單元的有限序列。數組特點：

1.有限個元素的集合；

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

3.元素名由數組名和下標組成；

4.下標值與元素對應（代表元素的位置）。4.1數組的定義及操作2/1/20232第4章數組

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

2.數據元素在邏輯意義上可分與否

3.操作不同。2/1/20233第4章數組２.數組的邏輯結構

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

a

…..

aa00

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

a

am-10m-11m-1n-1看元素a11有兩個直接前趨a10和a01兩個直接后繼a21和a12三維數組:每個元素有三個直接前趨和三個直接后繼.可見:數組(除一維數組外)是一種復雜的非線性數據結構.2/1/20234第4章數組但是: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章數組

據此數組可看成是線性表的擴展:即線性表中的數據元素本身也是一個數據結構.

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

各種高級程序設計語言的操作各不相同，必備的操作有：（1）求數組元素個數（2）隨機取（3）隨機存（4）矩陣運算2/1/20237第4章數組

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

假設：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數組的存儲結構:2/1/20238第4章數組

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

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

aij存儲地址:

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

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和常數C第1行：1個第2行：2個第3行：3個……第n行：n個1+2+3+4+5+…+n=n(n+1)/22/1/202311第4章數組非零元素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章數組假設：以一維數組sb[n(n+1)/2+1]作為n階下三角矩陣A的存儲結構，A中任意元素aij與sb[k]對應關系如下：

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

aij

=aji

0≤i,j≤n-1存儲：可只存儲上三角矩陣或下三角矩陣將n*n個元素壓縮存儲到n(n+1)/2個元素空間中（sa數組）。以按行優先存儲為例。A矩陣與sa[k]關系：上三角矩陣的存儲類似下三角矩陣，上三角矩陣自推i(i+1)/2+ji≥jj(j+1)/2+ii<jk=2/1/202314第4章數組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章數組例：三對角陣

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

非零元素aij的地址關系式：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章數組以上數組存儲方式與順序存儲線性表類似數組元素的存儲位置是其下標的線性函數。總之：特殊矩陣的壓縮存儲方法：找出特殊矩陣的非零元素的分布規律，將其存儲到一個存儲空間，只需在算法中按公式計算即可實現矩陣元素的隨機存取。2/1/202317第4章數組稀疏因子：設在m*n的矩陣中，有t個非零元素，令稱為矩陣的稀疏因子。通常認為<=0.05時為稀疏矩陣。我們在存儲的時候，除了存儲非零元的值之外，還得存儲它所在的行號和列號。由此構成一個三元組(i,j,aij)，該三元組唯一確定了該矩陣元素。

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

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

a.非零元素行下標;b.非零元素列下標;c.非零元素值.2/1/202319第4章數組

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章數組2.鏈接存儲結構:(1)三元組(單)鏈表.

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

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

(2)行指針數組結構的三元組鏈表.

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

以A為例:行指針數組

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

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

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

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

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

A5×5=2/1/202325第4章數組4400303721-212-120-1headh1h1h2h2h3h3h4h4300700-10-1-20000002/1/202326第4章數組轉置運算：設稀疏矩陣A以三元組表順序存儲結構存放。三元組順序表結構定義如下：#defineMAX100typedef

struct{inti;/*行*/

intj;/*列*/

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

struct{int

md;/*總行數*/

int

nd;/*總列數*/

inttd;/*總非零元素數*/

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

struct{inti;/*行*/

intj;/*列*/

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

struct{int

md;/*總行數*/

int

nd;/*總列數*/

inttd;/*總非零元素數*/

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

sa;sa.ndsa.tdsa.data[].isa.data[].j2/1/202328第4章數組例：將稀疏矩陣A進行轉置A=0011017000250000000000000000000037000000000025676021104171125301943375650sa:p=0766031911252011343740176550sb:q=0轉置v=02/1/202329第4章數組轉置算法：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;