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

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

1、第4章數(shù)組4.1數(shù)組定義及基本操作4.2數(shù)組的存儲(chǔ)結(jié)構(gòu)4.3特殊矩陣的壓縮存儲(chǔ)4.4稀疏矩陣的壓縮存儲(chǔ)4.5數(shù)組的運(yùn)算10/6/20211數(shù)組是我們最常用的一種數(shù)據(jù)結(jié)構(gòu)，各種計(jì)算機(jī)語言均有此類型。例如：順序表、順序棧、循環(huán)隊(duì)列等。１．?dāng)?shù)組的定義：數(shù)組：是ｎ（ｎ＞１）個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1…an-1,構(gòu)成的占用一塊連續(xù)的內(nèi)存單元的有限序列。數(shù)組特點(diǎn)：1.有限個(gè)元素的集合；2.所有元素具有相同的特性；3.元素名由數(shù)組名和下標(biāo)組成；4.下標(biāo)值與元素對(duì)應(yīng)（代表元素的位置）。4.1數(shù)組的定義及操作10/6/20212數(shù)組與線性表:相同之處:由若干個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)

2、元素組成.不同之處:1.存儲(chǔ)單元連續(xù)與否2.數(shù)據(jù)元素在邏輯意義上可分與否3.操作不同。10/6/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有兩個(gè)直接前趨a10和a02兩個(gè)直接后繼a21和a12三維數(shù)組:每個(gè)元素有三個(gè)直接前趨和三個(gè)直接后繼.可見:數(shù)組(除一維數(shù)組外)是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu).10/6/20214但是:1)可將Amxn看成由m個(gè)行向量組成的向量,即Amn

3、={(a00,a01,……a0n-1),(a10,a11,……a1n-1),……(am-10,am-11,……am-1n-1)}2)將Amxn看成由n個(gè)列向量組成的向量,即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外只有一個(gè)直接前趨和一個(gè)直接后繼.元素1元素2元素n10/6/20215據(jù)此數(shù)組可看成是線性表的擴(kuò)展:即線性表中的數(shù)據(jù)元素本身也是一個(gè)數(shù)據(jù)結(jié)構(gòu).數(shù)組可表示成兩類線性表:1.以行向

4、量做線性表的一個(gè)元素;2.以列向量做線性表的一個(gè)元素.10/6/20216３．?dāng)?shù)組抽象數(shù)據(jù)類型：數(shù)據(jù)集合：數(shù)組的數(shù)據(jù)集合可表示為a0,a1…an-1,每個(gè)數(shù)據(jù)元素的類型為抽象數(shù)據(jù)類型:DataType．（限定順序存儲(chǔ)）數(shù)據(jù)關(guān)系:線性關(guān)系.操作集合：各種高級(jí)程序設(shè)計(jì)語言的操作各不相同，必備的操作有：（1）求數(shù)組元素個(gè)數(shù)（2）隨機(jī)取（3）隨機(jī)存（4）矩陣運(yùn)算10/6/20217一般數(shù)組:(以二維數(shù)組為例)多采用順序存儲(chǔ):(1).按行優(yōu)先順序存儲(chǔ)假設(shè)：Am×n=a00a01a02…a0n-1a10…a00a01a02a03…a0n-1a10a11a12a13…a1n-1…a

5、m-10am-11am-12am-13…am-1n-1即a00,a01,a02……a0n-1,a10,a11,…...a1n-1……aij的存儲(chǔ)地址:am-1,04.2數(shù)組的存儲(chǔ)結(jié)構(gòu):10/6/20218L:為每個(gè)元素所占存儲(chǔ)單元.Pascal和C語言中數(shù)組存儲(chǔ)為此方式.Loc(aij)=Loc(a00)+(i*n+j)*L(2).列優(yōu)先順序存儲(chǔ),即a00,a10,a20……am-10,a01,a11,…...am-11……aij存儲(chǔ)地址:Loc(aij)=Loc(a00)+(j*m+i)*LFortran語言采用此方法.a00a10a20…am-10a01…可見:數(shù)

6、組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu).存取任意元素的時(shí)間相等10/6/20219推廣:假設(shè):A[c1--d1][c2--d2]例：二維數(shù)組floata[4][3].計(jì)算（1）數(shù)組元素?cái)?shù)目？（2）若數(shù)組Loc(a00)=1000,且L=4,數(shù)組元素a[3][2]的地址?(按行優(yōu)先存儲(chǔ))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)先順序存儲(chǔ)：Loc(aij)=Loc(ac1c2)+[(j-c2)*(d1-c1+1)+(i-c1)

7、]*L按列優(yōu)先順序存儲(chǔ)：10/6/202110特殊矩陣：指有一定量的零元素（或相同元素），并且其分布（非零元素的位置）有一定的規(guī)律。采用壓縮順序存儲(chǔ)方式:只存非零元素,節(jié)省空間.1.下三角矩陣:存放形式:{a00,a10,a11,a20,a21,…an-10,an-11,…an-1n-1}4.3特殊矩陣的壓縮存儲(chǔ)a0000……..0a10a110…….0……………….0an-10an-11…..an-1n-1Ann=可以是0和常數(shù)C第1行：1個(gè)第2行：2個(gè)第3行：3個(gè)……第n行：n個(gè)1+2+3+4+5+…+n=n(n+1)/210/6/2