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

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

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

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

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

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

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ù)組行序為主序5.2數(shù)組的存儲

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列序為主序

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

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

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

a10a11a12…a1j…a1n-1

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

…ain-1

：：：：：：：：：：

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

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

A．5

B．10

C．15

D．25本題二維數(shù)組a[0…4,1…5]行下標(biāo)從0開始，列下標(biāo)從1開始。數(shù)組第一個元素是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]以行為主序存儲，a[21]前面的元素個數(shù)一共有10個，

每個元素的單位長度是1，10*1=10，

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

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

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

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

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

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

aij=aji

1≤i,j≤n

則稱A為n階對稱矩陣

1513750800A=189263025170613存儲下三角：a11a21a22a31a32a33a41a42a43a44a51a52a53a54a55a11a21a22a31。。。a51。。。a55

壓縮存儲：將矩陣下三角中的元素按行優(yōu)先的順序存儲到一維數(shù)組。1）n階對稱矩陣A的壓縮存儲需要一個多大的一維數(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型，壓縮存儲可以節(jié)省多少存儲空間？非壓縮存儲所用存儲空間為4n*n個字節(jié)（即用二維數(shù)組存儲）；壓縮存儲所用存儲空間為2n(n+1)個字節(jié)；可節(jié)省存儲空間為2n(n-1)個字節(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個元素三角矩陣：若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

壓縮存儲：將矩陣下三角中的元素按行優(yōu)先的順序存儲到一維數(shù)組中。常量c或0存儲到數(shù)組的最后一個位置。1）n階三角矩陣A的壓縮存儲需要一個多大的一維數(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型，壓縮存儲可以節(jié)省多少存儲空間？非壓縮存儲所用存儲空間為4n*n個字節(jié)（即用二維數(shù)組存儲）；壓縮存儲所用存儲空間為2n(n+1)+4個字節(jié)；可節(jié)省存儲空間為2n(n-1)-4個字節(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個元素c程序員試題

對矩陣壓縮存儲的主要目的是____。

A．方便運算B．節(jié)省存儲空間

C．降低計算復(fù)雜度D．提高運算速度12472358A=45697891023583469B=56710891011對稱矩陣壓縮存儲應(yīng)用舉例求A+B因為二矩陣都是對稱矩陣，可以采用壓縮存儲，將矩陣存儲到一維數(shù)組中，所需一維數(shù)組的長度是4*（4+1）/2=103.

稀疏矩陣

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

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

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

123456A5x6=1300500

200-2000

3104060

4000000

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

113

145

23-2

311

334

356

53-1

三元組表

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

classTriple{

introw,col;floatvalue;};

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

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

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

2）三元組表的鏈?zhǔn)酱鎯α兄羔榙own指示同一列中的下一個非0元素行指針right指示同一行中的下一個非0元素

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

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

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

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

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

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

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

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

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

廣義表C的長度是2。

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

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

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

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

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

括號的重數(shù)是三重，廣義表B的深度是3。