第5章 數(shù)據(jù)結(jié)構(gòu)（Ｃ＋＋版）數(shù)組和廣義1表

數(shù)據(jù)結(jié)構(gòu)第5章數(shù)組第1講1第5章數(shù)組數(shù)組是人們所熟悉的一種數(shù)據(jù)結(jié)構(gòu)，幾乎所有的程序設(shè)計(jì)語(yǔ)言都提供數(shù)組類型。在前幾章討論的線性結(jié)構(gòu)中，同一個(gè)線性表的數(shù)據(jù)元素都具有相同數(shù)據(jù)類型。而本章討論的二維數(shù)組可以看成數(shù)據(jù)元素類型為行（或列）向量的線性表。本章討論的廣義表的數(shù)據(jù)元素類型有所擴(kuò)展，允許基本數(shù)據(jù)類型或者子表。本章內(nèi)容是線性表的擴(kuò)展，從線性結(jié)構(gòu)向非線性結(jié)構(gòu)的過渡。2第5章數(shù)組主要內(nèi)容： 數(shù)組的基本概念 特殊矩陣的壓縮存儲(chǔ) 稀疏矩陣的壓縮存儲(chǔ)及實(shí)現(xiàn) 廣義表的基本概念、存儲(chǔ)結(jié)構(gòu)和運(yùn)算3本章分為（2～3）講第1講

5.1

數(shù)組的基本概念

5.2

特殊矩陣

第2講5.3稀疏矩陣5.3.1數(shù)組元素的三元組

5.3.2三元組順序表供教師參考第2講5.3.3十字鏈表5.5廣義表

45.1數(shù)組的基本概念數(shù)組（Array）是相同類型的數(shù)據(jù)元素的有序集合。數(shù)組中的每一個(gè)數(shù)據(jù)元素通常稱為數(shù)組元素，數(shù)組元素用下標(biāo)識(shí)別，下標(biāo)的個(gè)數(shù)取決于數(shù)組的維數(shù)。這里所謂數(shù)組是從數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)的角度進(jìn)行討論。51．一維數(shù)組一般情況下，一維數(shù)組可表示為如下形式：

(a1，a2，…，an)

該組有n個(gè)數(shù)組元素，每個(gè)元素帶一個(gè)下標(biāo)，它是一維數(shù)組。數(shù)據(jù)元素之間的邏輯關(guān)系是線性的，不難看出這實(shí)質(zhì)上是一個(gè)線性表。形式化定義如下：

1_Array=(D,R)

其中：D

=

{ai|ai∈D0,i=c,c+1,…,d;}

R

=

{<ai-1,ai>|ai-1,ai∈≥D,i=c+1,c+2,…,d;}

6一維數(shù)組下標(biāo)范圍：應(yīng)注意到數(shù)組定義還是有別于線性表，其下標(biāo)的記法是從c到d。例如下列數(shù)組的表示都是允許的：（

a1,a2,…,an）

//BASIC（a0,a1,…,an?1）//C/C++（a-3,a-2,a-1,a0,a1,a2,…,a8）//PASCAL

72．二維數(shù)組

一個(gè)m×n階矩陣A，可以用一個(gè)二維數(shù)組來表示。其中每個(gè)數(shù)組元素都有兩個(gè)下標(biāo)，用下標(biāo)變量aij來表示，其中i為行下標(biāo)，j為列下標(biāo)，且1≤i≤m，1≤j≤n。8二維數(shù)組的形式化定義：

2_Array=(D,R)其中：

D={aij

|aij∈D0,i=c1,c1+1,…,d1,

j=c2,c2+1,…d2;}

R={ROW,COL}

ROW={<aij,ai,j+1>|aij,ai,j+1∈D,c1≤i≤d1,

c2≤j≤d2?1;}//行關(guān)系

COL={<aij,ai+1,j>|aij,ai+1,j∈D,c1≤i≤d1?1,

c2≤j≤d2;}//列關(guān)系D0為某個(gè)數(shù)椐對(duì)象，c1,c2,d1,d2均為整數(shù)，表示每一維的下限和上限。9二維數(shù)組的認(rèn)識(shí)：

c1,c2,d1,d2均為整數(shù)，且c1<d1，c2<d2

，它們表示每一維的下限和上限。二維數(shù)組含有(d1?c1+1)*(d2?c2+1)個(gè)數(shù)據(jù)元素。每一個(gè)數(shù)據(jù)元素aij都受到兩個(gè)關(guān)系的約束，它們是行關(guān)系ROW和列關(guān)系COL。

ai,j+1是aij在行關(guān)系中的直接后繼元素；而ai+1,j是aij在列關(guān)系中的直接后繼元素。10把二維數(shù)組看成定長(zhǎng)線性表:

圖（a）中Am×n是m行n列的矩陣，可將其視為一個(gè)二維數(shù)組。以列向量作為基本數(shù)據(jù)元素，可構(gòu)成線性表：A

=

(

p1,p2,…,

pn)

該線性表的每一個(gè)元素也是一個(gè)定長(zhǎng)線性表（可稱為子表），即一個(gè)列向量，如圖（b）。11把二維數(shù)組看成定長(zhǎng)線性表:該還可是，以行向量為基本數(shù)據(jù)元素的線性表：A

=

(q1

,q2

,…,

qn)其中每個(gè)數(shù)據(jù)元素qi又是一個(gè)行向量形式的線性子表：qi

=

(ai1,ai2,…,ain)1≤i≤m以行向量為基本元素的一維數(shù)組A可以詳細(xì)表示：A

=

((a11a12…a1n),(a21a22…a2n),…,(am1am2…amn))12關(guān)于三維數(shù)組：現(xiàn)實(shí)生活中有大量實(shí)例，比如一個(gè)玩具魔方，可以理解為具有三層、每層三行、每行三列的一個(gè)三維數(shù)組。再如一個(gè)班級(jí)，有m個(gè)學(xué)生，每個(gè)學(xué)生有n門課成績(jī)，所構(gòu)成是一個(gè)二維數(shù)組。假設(shè)一個(gè)年級(jí)有6個(gè)班級(jí)，整個(gè)年級(jí)的成績(jī)表也構(gòu)成一個(gè)三維數(shù)組。該數(shù)組的三個(gè)維可看成層、行、列，它們分別代表班級(jí)、學(xué)生和課程。133．n維數(shù)組

n維數(shù)組的形式化定義：n_Array=(D,R)其中：

//具有n維，n種關(guān)系n維數(shù)組含有數(shù)據(jù)元素的總數(shù)為：14對(duì)數(shù)組的操作：（1）給定一組有定義的下標(biāo)，存取相應(yīng)的數(shù)組元素。（2）給定一組有定義的下標(biāo)，修改相應(yīng)數(shù)組元素中的某個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)的值。（3）給定某數(shù)據(jù)元素的值，求出其在數(shù)組中的位置（下標(biāo)）。（4）對(duì)于二維數(shù)組所表示的矩陣，求逆矩陣、求兩個(gè)矩陣的相加和、相減差或者相乘之積。數(shù)組作為一種邏輯結(jié)構(gòu)，它可以選擇順序存儲(chǔ)結(jié)構(gòu)，也可以選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。155.1.2數(shù)組的順序表示數(shù)組的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱順序表示，指的是在計(jì)算機(jī)中，用一組地址連續(xù)的存儲(chǔ)單元來表示數(shù)組。以下列矩陣為例：

A=

該矩陣可以看成是三行三列的二維數(shù)組，共有9個(gè)元素。在計(jì)算機(jī)中它們存放在9個(gè)連續(xù)的存儲(chǔ)單元中（假設(shè)每個(gè)數(shù)組元素占一個(gè)存儲(chǔ)單元）。16數(shù)組的順序表示:一種是以行序?yàn)橹餍虻拇鎯?chǔ)方式，也稱按行優(yōu)先順序。首先存放第1行的各個(gè)元素，然后存放第2行的各個(gè)元素，最后存放第3行的所有元素，如圖(a)所示。一種是以列序?yàn)橹餍虻拇鎯?chǔ)方式，也稱按列優(yōu)先順序。首先存放第1列的各個(gè)元素，然后存放第2列的各個(gè)元素，最后存放第3列的所有元素，如圖（b）所示。

17各種高級(jí)語(yǔ)言的數(shù)組的順序存儲(chǔ)：

在C、C++、BASIC和PASCAL語(yǔ)言中，數(shù)組的數(shù)據(jù)元素均采用以行序?yàn)橹鞯捻樞虼鎯?chǔ)。在FORTRAN語(yǔ)言中數(shù)組的數(shù)據(jù)元素則采用以列序?yàn)橹鞯捻樞虼鎯?chǔ)。在數(shù)組的順序表示中，很容易根據(jù)下標(biāo)值求出數(shù)組元素所在的地址。18按行優(yōu)先順序表示，地址計(jì)算：

約定已知首元素a1

的首地址是LOC(a1)，且每個(gè)元素占一個(gè)存儲(chǔ)單元。（1）一維數(shù)組，元素ai的地址LOC(ai)：LOC(ai)

=

LOC(a1)

+

(i

?

1)（2）二維數(shù)組，數(shù)組元素aij的地址LOC(aij)：LOC(aij)

=

LOC(a11)

+

n(i

?1)

+

(

j

?

1)

FORTRAN語(yǔ)言中，數(shù)組是按列優(yōu)先順序存儲(chǔ)的，二維數(shù)組元素地址：LOC(aij)

=

LOC(a11)

+

m(j

?

1)

+

(i

?

1)詳細(xì)講解公式19（3）三維數(shù)組a[d1][d2][d3]它是一個(gè)具有d1個(gè)層、d2個(gè)行、d3個(gè)列的數(shù)組。三維數(shù)組元素是先按層優(yōu)先、在每層內(nèi)是按行優(yōu)先的順序存放元素，對(duì)于多維數(shù)組而言也可稱為按最左下標(biāo)優(yōu)先原則。數(shù)組元素地址計(jì)算公式為：LOC()

=

LOC(a111)

+

d2d3(i1

?

1)+d3(i2

?

1)

+

(i3

?

1)其中，1≤i1≤d1，1≤i2≤d2，1≤i3≤d3。參照教材，詳細(xì)講解公式20（4）n維數(shù)組a[d1][d2]…[dn]，

在內(nèi)存中是按最左下標(biāo)優(yōu)先，然后按次左下標(biāo)優(yōu)先……最后按右下標(biāo)的順序存放。假設(shè)每個(gè)數(shù)組元素占用一個(gè)存儲(chǔ)單元，且1≤i1≤d1，1≤i2≤d2,…,1≤in≤dn，則數(shù)組元素的地址：LOC()

=

LOC(a11…1)

+

d2d3…dn(i1?1)

+

d3d4…dn(i2?1)

+

…

+

dn(in?1

?

1)

+

(in

?

1)參照教材，詳細(xì)講解公式21n維數(shù)組地址計(jì)算公式：LOC()

=

LOC(a11…1)

+

d2d3…dn(i1?1)

+

d3d4…dn(i2?1)

+

…

+

dn(in?1

?

1)

+

(in

?

1)

上述公式可以寫成如下形式：

LOC()=LOC(a11…1)+其中：ar=,an=1詳細(xì)講解公式22思考以上討論的前提是數(shù)組的每維下標(biāo)取值范圍為從1到n（n>0）。

C/C++語(yǔ)言允許下標(biāo)取值范圍為：從0到n?1。

PASCAL允許下標(biāo)下界為負(fù)整數(shù)、0或正整數(shù)，如：下標(biāo)取值范圍可以從?3到5。數(shù)組的下標(biāo)值范圍從0到n?1，上述公式應(yīng)該如何改寫？數(shù)組的下標(biāo)值范圍從c到d（c<d，c、d為整數(shù)），上述公式又應(yīng)該如何改寫？23二維數(shù)組b[m][n]為例：

b數(shù)組行下標(biāo)下界c1上界d1；列下標(biāo)下界c2上界d2；要求c1≤d1，c2≤d2。假設(shè)m=d1?c1+1,n=d2?c2+1，二維數(shù)組地址計(jì)算公式為：LOC(bij)

=

LOC(b11)

+

(d2?c2+1)(i

?

1)

+

(j

?

1)

公式的第2項(xiàng)中，i?1是整行的行數(shù)，d2?c2+1是每行數(shù)據(jù)元素的個(gè)數(shù)。那么n維數(shù)組呢？245.2特殊矩陣當(dāng)數(shù)組具有完整的矩陣結(jié)構(gòu)時(shí)（即數(shù)組中大部分?jǐn)?shù)據(jù)元素值不為零），上節(jié)的順序表示方法是適用的。存在另外一些特殊的矩陣，如對(duì)稱矩陣、下（上）三角矩陣、三對(duì)角陣等。這些矩陣中的數(shù)據(jù)元素分布具有一定的規(guī)律，因此稱為特殊矩陣。在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，為了節(jié)省存儲(chǔ)空間可對(duì)其進(jìn)行壓縮存儲(chǔ)。為了方便討論，假定一個(gè)數(shù)據(jù)元素占L個(gè)存儲(chǔ)單元。這里的順序存儲(chǔ)結(jié)構(gòu)采用高級(jí)語(yǔ)言中的一維數(shù)組B來表示。251．對(duì)稱矩陣對(duì)稱矩陣，以主（或輔）對(duì)角線元素為對(duì)稱的矩陣。它們的特點(diǎn)是：aij

=

aji。

An×n=

26對(duì)稱矩陣采用按行優(yōu)先順序存儲(chǔ)：僅存儲(chǔ)矩陣A的下三角部分，則等價(jià)于將A壓縮存儲(chǔ)在一個(gè)一維數(shù)組B中：B[1]=a11，B[2]=a21,B[3]=a22

…….B[n×(n?1)/2+1]=an1

，…,B[n×(n+1)/2]=ann

27對(duì)稱矩陣采用按行優(yōu)先順序存儲(chǔ)：矩陣A的下三角部分在數(shù)組B中：B[1]=a11，B[2]=a21,B[3]=a22

…….B[n×(n?1)/2+1]=an1

，…,B[n×(n+1)/2]=ann

已知某數(shù)組元素下標(biāo)i,

j值時(shí)，那么aij在B中的存放位置k計(jì)算：

B[k]=aij

（5-1）

282．上(下)三角矩陣指以主對(duì)角線元素為界，下三角部分的數(shù)據(jù)元素均為零元素的矩陣。反之上三角部分的數(shù)據(jù)元素均為零元素則稱為下三角矩陣。下三角矩陣實(shí)例：

An×n=

當(dāng)i

<

j時(shí)，aij

=

029下三角矩陣壓縮存儲(chǔ)

在一維數(shù)組B中按行優(yōu)先順序存儲(chǔ)下三角矩陣A的非零元素，則有如圖的壓縮存儲(chǔ)序列。30對(duì)于上三角矩陣，根據(jù)式（5-1）的第2個(gè)公式可以求出aij在B數(shù)組中位置k：

B[k]=aij

k