《數(shù)據(jù)結(jié)構(gòu)JAVA語言版》課件 第5章 數(shù)組矩陣和廣義表

第五章數(shù)組和廣義表5.1數(shù)組

數(shù)組是最常用的一種數(shù)據(jù)結(jié)構(gòu)，幾乎所有的程序設(shè)計(jì)語言都把數(shù)組設(shè)為固有的數(shù)據(jù)類型。

5.1數(shù)組JAVA語言支持多維數(shù)組int[]array1=newint[N];聲明了一個(gè)一維數(shù)組，有多少個(gè)元素？答：有N個(gè)數(shù)據(jù)元素5.1數(shù)組JAVA語言支持多維數(shù)組int[][]array2=newint[M][N];聲明了一個(gè)二維數(shù)組，有多少個(gè)元素？答：有M*N個(gè)數(shù)據(jù)元素5.1數(shù)組JAVA語言支持多維數(shù)組int[][]array3=newint[X][Y][Z];聲明了一個(gè)三維數(shù)組，有多少個(gè)元素？答：有X*Y*Z個(gè)數(shù)據(jù)元素。

JAVA語言對數(shù)組的維數(shù)沒有嚴(yán)格的界限。但是三維以上的數(shù)組基本不大使用，用得最多的是一、二維數(shù)組。還可以支持更復(fù)雜的數(shù)組一維數(shù)組5.2數(shù)組的存儲(chǔ)a0a1a2…an

內(nèi)存a0a1…an5.2數(shù)組的存儲(chǔ)

a00

a01……a0n-1

a10

a11……a1n-1

………….

am-10

am-11……

am-1n-1

內(nèi)存a00…a0n-1a10…a1n-1…am-10am-1n-1二維數(shù)組行序?yàn)橹餍?.2數(shù)組的存儲(chǔ)

a00

a01……a0n-1

a10

a11……a1n-1

………….

am-10

am-11……

am-1n-1

二維數(shù)組內(nèi)存a00…a0n-1…am-10a01…am-11…am-1n-1列序?yàn)橹餍?/p>

二維數(shù)組a[m,n]每個(gè)元素只占L個(gè)存儲(chǔ)單元，”按行優(yōu)先”存放數(shù)組，首元素a00的地址為

Loc（0,0），求元素aij的地址.

最基本的原理:aij的地址=第一個(gè)元素的起始地址該元素前面的元素個(gè)數(shù)╳單位長度+a00a01a02…a0j…a0n-1

a10a11a12…a1j…a1n-1

：：：：：：：：：：Amxn=ai0ai1ai2…aij

…ain-1

：：：：：：：：：：

am-10am-11am-12…am-1j…am-1n-1i行，每行n個(gè)元素j個(gè)元素Loc（i,j）=Loc（0,0）+（n×i+j）L2006-1程序員考試試題對于二維數(shù)組a[0…4,1…5]，設(shè)每個(gè)元素占1個(gè)存儲(chǔ)單元，且以行為主序存儲(chǔ)，則元素a[2,1]相對于數(shù)組空間起始地址的偏移量是___。

（也就是a[21]前面的元素個(gè)數(shù)*單位長度）

A．5

B．10

C．15

D．25本題二維數(shù)組a[0…4,1…5]行下標(biāo)從0開始，列下標(biāo)從1開始。數(shù)組第一個(gè)元素是a[01]。a[01]a[02]a[03]a[04]a[05]a[11]a[12]a[13]a[14]a[15]a[21]a[22]a[23]a[24]a[25]a[31]a[32]a[33]a[34]a[35]a[41]a[42]a[43]a[44]a[45]以行為主序存儲(chǔ)，a[21]前面的元素個(gè)數(shù)一共有10個(gè)，

每個(gè)元素的單位長度是1，10*1=10，

所以元素a[2,1]相對于數(shù)組空間起始地址的偏移量是10。

矩陣（Matrix）是數(shù)值程序設(shè)計(jì)中經(jīng)常用到的數(shù)學(xué)模型

B3x4=5-27586-1308475.3矩陣的壓縮存儲(chǔ)A3x4=5-28494-190721

求A+B。在編程時(shí)，簡單而又自然的方法，是將矩陣元素存儲(chǔ)到一個(gè)二維數(shù)組中。

但是在一些特殊矩陣中，元素呈某種規(guī)律分布或者矩陣中有大量的零元素，如果仍用二維數(shù)組存，會(huì)造成極大的浪費(fèi)，尤其是處理高階矩陣的時(shí)候。

為了節(jié)省存儲(chǔ)空間，我們可以對這類矩陣進(jìn)行壓縮存儲(chǔ)。5.3.1特殊矩陣的壓縮存儲(chǔ)對稱矩陣：若n階方陣A中的元滿足特性

aij=aji

1≤i,j≤n

則稱A為n階對稱矩陣

1513750800A=189263025170613存儲(chǔ)下三角：a11a21a22a31a32a33a41a42a43a44a51a52a53a54a55a11a21a22a31。。。a51。。。a55

壓縮存儲(chǔ)：將矩陣下三角中的元素按行優(yōu)先的順序存儲(chǔ)到一維數(shù)組。1）n階對稱矩陣A的壓縮存儲(chǔ)需要一個(gè)多大的一維數(shù)組？a11

a21a22

：：：：：：：：

ai-11ai-12……ai-1i-1ai1ai2ai3…aij

…aii

：：：：：：：：：：

an1an2an3…anj…ani

…ann1+2+。。。+n=n(n+1)/22）假設(shè)n階對稱矩陣A中的元素定義為float型，壓縮存儲(chǔ)可以節(jié)省多少存儲(chǔ)空間？非壓縮存儲(chǔ)所用存儲(chǔ)空間為4n*n個(gè)字節(jié)（即用二維數(shù)組存儲(chǔ)）；壓縮存儲(chǔ)所用存儲(chǔ)空間為2n(n+1)個(gè)字節(jié)；可節(jié)省存儲(chǔ)空間為2n(n-1)個(gè)字節(jié)；3）下三角中的元素aij在一維數(shù)組中的下標(biāo)？a11a21a22a31…aij…an1…anna11

a21a22

：：：：：：：：

ai-11ai-12……ai-1i-1ai1ai2ai3…aij

…aii

：：：：：：：：：：

an1an2an3…anj…ani

…anni-1行共:1+2+

…

+i-1j-1個(gè)元素三角矩陣：若n階方陣中下(上)三角(不包括對角線)中的元均為常量c或0，則稱為上(下)三角矩陣.數(shù)組下標(biāo)k=0123n(n-1)/2n(n+1)/2a11a21a22a31…an1…annca11

a21a22

：：：：：：：：

ai-11ai-12……ai-1i-1ai1ai2ai3…aij

…aii

：：：：：：：：：：

an1an2an3…anj…ani

…ann

壓縮存儲(chǔ)：將矩陣下三角中的元素按行優(yōu)先的順序存儲(chǔ)到一維數(shù)組中。常量c或0存儲(chǔ)到數(shù)組的最后一個(gè)位置。1）n階三角矩陣A的壓縮存儲(chǔ)需要一個(gè)多大的一維數(shù)組？a11

a21a22

：：：：：：：：

ai-11ai-12……ai-1i-1ai1ai2ai3…aij

…aii

：：：：：：：：：：

an1an2an3…anj…ani

…ann1+2+。。。+n+1=n(n+1)/2+12）假設(shè)n階三角矩陣A中的元素定義為float型，壓縮存儲(chǔ)可以節(jié)省多少存儲(chǔ)空間？非壓縮存儲(chǔ)所用存儲(chǔ)空間為4n*n個(gè)字節(jié)（即用二維數(shù)組存儲(chǔ)）；壓縮存儲(chǔ)所用存儲(chǔ)空間為2n(n+1)+4個(gè)字節(jié)；可節(jié)省存儲(chǔ)空間為2n(n-1)-4個(gè)字節(jié)；3）下三角中的元素aij在一維數(shù)組中的下標(biāo)？常數(shù)c的下標(biāo)？a11a21a22a31…aij…an1…anna11

a21a22

：：：：：：：：

ai-11ai-12……ai-1i-1ai1ai2ai3…aij

…aii

：：：：：：：：：：

an1an2an3…anj…ani

…anni-1行共:1+2+

…

+i-1j-1個(gè)元素c程序員試題

對矩陣壓縮存儲(chǔ)的主要目的是____。

A．方便運(yùn)算B．節(jié)省存儲(chǔ)空間

C．降低計(jì)算復(fù)雜度D．提高運(yùn)算速度12472358A=45697891023583469B=56710891011對稱矩陣壓縮存儲(chǔ)應(yīng)用舉例求A+B因?yàn)槎仃嚩际菍ΨQ矩陣，可以采用壓縮存儲(chǔ)，將矩陣存儲(chǔ)到一維數(shù)組中，所需一維數(shù)組的長度是4*（4+1）/2=103.

稀疏矩陣

如果矩陣中只有少量的非零值元，并且這些非零值元在矩陣中的分布沒有一定規(guī)律，則稱為隨機(jī)稀疏矩陣，簡稱為稀疏矩陣。假設(shè)在mxn

的矩陣中有t個(gè)非零值元，令δ=t/m*n，稱δ為矩陣的稀疏因子。A的稀疏因子是多少？7/30=0.23=23%。A5x6=30050000-200010406000000000-1000A并不屬于嚴(yán)格意義上的稀疏矩陣，只有稀疏因子小于5%的矩陣才能稱之為稀疏矩陣。A5x6=30050000-200010406000000000-1000

稀疏矩陣的壓縮存儲(chǔ)：只存儲(chǔ)非0元素。描述非0元素的信息有：

123456A5x6=1300500

200-2000

3104060

4000000

500-1000整個(gè)矩陣的存儲(chǔ)：每個(gè)非零元素由（row,col,value）唯一確定，整個(gè)矩陣可表示成一個(gè)三元組表。rowcolvalue

113

145

23-2

311

334

356

53-1

三元組表

如何表示三元組表的一行？三元組表的每一行都是由三個(gè)數(shù)據(jù)項(xiàng)組成的，考慮用類表示。

classTriple{

introw,col;floatvalue;};

如何表示整個(gè)三元組表？用類數(shù)組Triple[]data=newTriple[7];//數(shù)組data中有7個(gè)數(shù)據(jù)元素，每個(gè)元素類型都是Triple型

//java語言中認(rèn)為三元組表的順序存儲(chǔ)就是把三元組表存放到類數(shù)組中。1)三元組表的順序存儲(chǔ)假設(shè)稀疏矩陣A的數(shù)據(jù)元素是浮點(diǎn)型，row

col是整型short，value是浮點(diǎn)型float，稀疏矩陣A采用三元順序表存儲(chǔ)節(jié)省了多少存儲(chǔ)空間？答：稀疏矩陣A采用二維數(shù)組存儲(chǔ)所用的存儲(chǔ)空間=5*6*4=120字節(jié)。稀疏矩陣A采用三元順序表存儲(chǔ)所用的存儲(chǔ)空間=7*8=56字節(jié)。節(jié)省的存儲(chǔ)空間=120-56=64字節(jié)。三元組表的順序存儲(chǔ)下如何實(shí)現(xiàn)稀疏矩陣的相加，相乘，轉(zhuǎn)置？

2）三元組表的鏈?zhǔn)酱鎯?chǔ)列指針down指示同一列中的下一個(gè)非0元素行指針right指示同一行中的下一個(gè)非0元素

結(jié)點(diǎn)結(jié)構(gòu)：rowcolValue列指針down行指針rightA3x4=30050-1003000

矩陣A的十字鏈表稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下(十字鏈表)如何實(shí)現(xiàn)稀疏矩陣的相加，相乘，轉(zhuǎn)置等？作業(yè)：請畫出稀疏矩陣M和N的十字鏈表結(jié)構(gòu)。

5.4廣義表的定義線性表的定義：線性表（LinearList）是由n（n≥0）個(gè)類型相同的數(shù)據(jù)元素組成的有限序列。

L=(a1,a2,...,ai-1,ai,ai+1,...,an)廣義表的定義：廣義表（GeneralizedList）是n（n>=0）個(gè)數(shù)據(jù)元素組成的有限序列。

LS=（α1，α2，α3，…，αn）

幾點(diǎn)說明：1、αi與αj類型可以不同。αi可以是原子元素，也可以是子表。

C=（a，（b，c，d））

C是一個(gè)廣義表，第一個(gè)數(shù)據(jù)元素是一個(gè)原子元素a，第二個(gè)數(shù)據(jù)元素是子表（b，c，d）。LS=（α1，α2，α3，…，αn）幾點(diǎn)說明：2、廣義表的長度：廣義表中的數(shù)據(jù)元素個(gè)數(shù)。

C=（a，（b，c，d））

廣義表C的長度是2。

廣義表A=（）的長度是？LS=（α1，α2，α3，…，αn）幾點(diǎn)說明：3、廣義表的深度：廣義表展開以后所含括號(hào)的重?cái)?shù)。

廣義表C=（a，（b，c，d））的深度是2。

廣義表A=（）的深度是1。

廣義表B=(A,C)的深度？1？

廣義表B的展開式=（（），（a，（b，c，d）））

括號(hào)的重?cái)?shù)是三重，廣義表B的深度是3。