結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組

《結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第4章數(shù)組4.1數(shù)組定義及基本操作4.2數(shù)組的存儲結(jié)構(gòu)4.3特殊矩陣的壓縮存儲4.4稀疏矩陣的壓縮存儲4.5數(shù)組的運算7/17/20211數(shù)組是我們最常用的一種數(shù)據(jù)結(jié)構(gòu)，各種計算機語言均有此類型。例如：順序表、順序棧、循環(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ù)組的定義及操作7/17/20212數(shù)組與線性表:相同之處:由若干個相同數(shù)據(jù)類型的數(shù)據(jù)元

2、素組成.不同之處:1.存儲單元連續(xù)與否2.數(shù)據(jù)元素在邏輯意義上可分與否3.操作不同。7/17/20213２.數(shù)組的邏輯結(jié)構(gòu)一維數(shù)組（a0,a1,a2,a3,…an-1）滿足線性關(guān)系；二維或二維以上數(shù)組：（以二維為例）Amxn=aa…..aa00a02…….a0n-110111n-1……...aaam-10m-12m-1n-1看元素a11有兩個直接前趨a10和a02兩個直接后繼a21和a12三維數(shù)組:每個元素有三個直接前趨和三個直接后繼.可見:數(shù)組(除一維數(shù)組外)是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu).7/17/20214但是:1)可將Amxn看成由m個行向量組成的向量,即Amn={

3、(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元素n7/17/20215據(jù)此數(shù)組可看成是線性表的擴展:即線性表中的數(shù)據(jù)元素本身也是一個數(shù)據(jù)結(jié)構(gòu).數(shù)組可表示成兩類線性表:1.以行向量做線

4、性表的一個元素;2.以列向量做線性表的一個元素.7/17/20216３．?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）隨機取（3）隨機存（4）矩陣運算7/17/20217一般數(shù)組:(以二維數(shù)組為例)多采用順序存儲:(1).按行優(yōu)先順序存儲假設(shè)：Am×n=a00a01a02…a0n-1a10…a00a01a02a03…a0n-1a10a11a12a13…a1n-1…am-10

5、am-11am-12am-13…am-1n-1即a00,a01,a02……a0n-1,a10,a11,…...a1n-1……aij的存儲地址:am-1,04.2數(shù)組的存儲結(jié)構(gòu):7/17/20218L:為每個元素所占存儲單元.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ù)組是一種隨

6、機存儲結(jié)構(gòu).存取任意元素的時間相等7/17/20219推廣:假設(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)

7、先順序存儲：7/17/202110特殊矩陣：指有一定量的零元素（或相同元素），并且其分布（非零元素的位置）有一定的規(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)/27/17/2