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

第五章數(shù)組回憶前面幾章學(xué)習(xí)的線性結(jié)構(gòu):線性表、棧、隊(duì)列、串要求數(shù)據(jù)結(jié)構(gòu)中的元素必須有相同的屬性，即數(shù)據(jù)類型其中元素的數(shù)據(jù)類型只要相同即可，當(dāng)然也可以就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。問(wèn)題：數(shù)組與線性表的區(qū)別與聯(lián)系

相同之處：它們都是若干個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,…，an-1構(gòu)成的有限序列。

不同之處：

(1)數(shù)組要求其元素占用一塊地址連續(xù)的內(nèi)存單元空間，而線性表無(wú)此要求；(2)線性表的元素是邏輯意義上不可再分的元素，而數(shù)組中的每個(gè)元素還可以是一個(gè)數(shù)組；(3)數(shù)組的操作主要是向某個(gè)下標(biāo)的數(shù)組元素中存放數(shù)據(jù)和取某個(gè)下標(biāo)的數(shù)組元素，這與線性表的插入和刪除操作不同。本講內(nèi)容5.1數(shù)組的定義1.數(shù)組2.數(shù)組的邏輯定義5.2數(shù)組的順序存儲(chǔ)5.3矩陣的壓縮存儲(chǔ)1.特殊矩陣2.稀疏矩陣數(shù)組數(shù)組邏輯上是線性結(jié)構(gòu)的推廣；數(shù)組是以線性表為元素的線性結(jié)構(gòu)，而且元素的結(jié)構(gòu)相同；數(shù)組可以看作是下標(biāo)和值的偶對(duì)的集合；數(shù)組是一種邏輯結(jié)構(gòu)。高級(jí)語(yǔ)言中的數(shù)組inta[10];a[0]a[1]a[2]a[3]……a[10-1]charB[4][5];B[0][0]B[0][1]B[0][2]B[0][3]B[0][5-1]B[1][0]B[1][1]……B[1][5-1]B[2][0]B[2][1]……B[2][5-1]B[3][0]B[3][1]……B[3][5-1]二維數(shù)組inta[2][3];兩個(gè)變量組成的一個(gè)數(shù)組，其中每一個(gè)變量都是數(shù)組。其中a[0]，a[1]都是數(shù)組的名字，也就是地址。

a[0][1]a[0][0]a[1][2]a[1][1]a[1][0]a[0][2]數(shù)組的邏輯定義

n（n＞1）維數(shù)組是一個(gè)向量，它的每個(gè)元素是n-1維數(shù)組，且具有相同的上限和下限。

()nAaaa,,,21=……()mjjjjaaaa,,,21=……()mAbbb,,,21=……()iniii,,,21=……bbbbúúúú?ùêêêê?é=mnmmnnnmaaaaaaaaaA212222111211………………………………[][[[]]]×úúúúú?ùêêêêê?éúúúú?ùêêêê?éúúúú?ùêêêê?éúúúú?ùêêêê?é=mnnnmmnmaaaaaaaaaA212221212111…………………×數(shù)組的抽象數(shù)據(jù)類型ADTArray{

數(shù)據(jù)對(duì)象：ji=0,…,bi-1,i=1,2,…,n,D={aj1j2…,jn|n(>0)稱為數(shù)組的維數(shù)，bi是數(shù)組第i維的長(zhǎng)度,ji是第i維的下標(biāo),aj1j2…,jn∈ElemSet}

數(shù)據(jù)關(guān)系：

R={R1,R2,R3,……,Rn}Ri={<aj1…ji……jn,aj1…ji+1……jn>|0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2

基本操作：

Value(A,&e,index1,…,indexn)

Assign(&A,e,index1,…,indexn)}ADTArray數(shù)組的操作對(duì)于數(shù)組的操作一般只有兩類：(1)給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素(2)給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素的值。數(shù)組一般不做插入和刪除操作數(shù)組的存儲(chǔ)實(shí)現(xiàn)機(jī)制１、一維數(shù)組（n個(gè)元素）中任一元素ai的內(nèi)存單元地址LOC(ai)=LOC(a０)+i*k(0≤i<n)２、一個(gè)m行n列的二維數(shù)組LOC(aij)=LOC(a00)+(i*n+j)*k(0≤i<m，0≤j<n)注：C語(yǔ)言中數(shù)組元素采用行主序的存放方法，即行優(yōu)先順序。順序存儲(chǔ)時(shí)按行序和列序的約定數(shù)組順序存儲(chǔ)時(shí)，必須確定按行序或列序存儲(chǔ)：（1）PASCAL、C以行序?yàn)橹鞔鎯?chǔ)（2）FORTRAN以列序?yàn)橹鞔鎯?chǔ)a11

a12

…

a1n

a21

a22

…

a2n

…

am1

am2

…

amn

a11

a21

…

am1

a12

a22

…

am2

…

a1n

a2n

…

amn

以行為主序以列為主序例如：

稱為基地址或基址。以“行序?yàn)橹餍颉钡拇鎯?chǔ)映象二維數(shù)組A中任一元素ai,j的存儲(chǔ)位置LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

設(shè)二維數(shù)組A[c1..d1][c2..d2]

其中c1、c2和d1、d2分別為二維數(shù)組A的下標(biāo)的下界和上界，每個(gè)數(shù)組元素占L個(gè)存儲(chǔ)單元，設(shè)第一個(gè)元素A[c1][c2]的存儲(chǔ)位置為L(zhǎng)OC(c1,c2)，則該二維數(shù)組中任一元素A[i][j]

(

c1≤i≤d1,c2≤j≤d2)的存儲(chǔ)位置可由下式確定：

LOC(i,j)=LOC(c1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L在C語(yǔ)言中，下標(biāo)從零開(kāi)始,即:A[0..d1][0..d2]，則數(shù)組元素A[i][j]的存儲(chǔ)位置是

LOC(i,j)=LOC(0,0)+(i*(d2+1)+j)*L

矩陣的壓縮存儲(chǔ)壓縮存儲(chǔ)思想當(dāng)矩陣的階數(shù)較高，而且矩陣中的一些元素有特殊的性質(zhì)時(shí)，可以采用節(jié)省空間的存儲(chǔ)辦法（壓縮存儲(chǔ)）。兩類矩陣1.特殊矩陣：值相同的元素或非零元素分布有一定的規(guī)律；2.稀疏矩陣：非零元素少且分布無(wú)規(guī)律；對(duì)稱矩陣、上（下）三角矩陣、對(duì)角矩陣特殊矩陣——對(duì)稱矩陣若n階方陣A中的元素滿足下述性質(zhì)：

aij=aji

1≤i,j≤n則稱A為n階對(duì)稱矩陣。a11

a21

a22

a31

…

an1

…

ann

k=0123

n2個(gè)元素可以壓縮到n(n+1)/2個(gè)空間中；以行序?yàn)橹餍驅(qū)⑵湎氯牵ò▽?duì)角線）中的元素存儲(chǔ)到一個(gè)向量B[n(n+1)/2]中:特殊矩陣——對(duì)稱矩陣向量B[k]和矩陣中的元素aij之間存在著一一對(duì)應(yīng)關(guān)系：

下面按下標(biāo)從0開(kāi)始討論。

向量B[k]和矩陣中的元素aij之間的關(guān)系：由i和j推導(dǎo)k：特殊矩陣——對(duì)稱矩陣下標(biāo)變換公式三角矩陣:

下三角矩陣是指矩陣的上三角（不包括對(duì)角線）中的元素均為零或常數(shù)的n階方陣。特殊矩陣——三角矩陣下三角矩陣存儲(chǔ)公式和對(duì)稱矩陣存儲(chǔ)主對(duì)角線以下元素的公式基本相同，只需額外再增加一個(gè)存儲(chǔ)常數(shù)或零的存儲(chǔ)空間即可，即壓縮存儲(chǔ)空間為1+n(n+1)/2

。特殊矩陣——對(duì)角矩陣對(duì)角矩陣:

所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中。即除了主對(duì)角線上和直接在對(duì)角線上、下方若干條對(duì)角線上的元素之外，所有其它的元素均為零。b條對(duì)角線n行n列(a)a11

a12

a21

a22

a23

an-1,n

an,n

an,n-1

OO(b)a11

a12

a21

a22

a23

an-1,n

an,n

an,n-1

OO

三對(duì)角矩陣:共3n-2個(gè)非零元素，存入B[3n-2]中,元素在一維數(shù)組B中的下標(biāo)k和元素在矩陣中的下標(biāo)i和j的對(duì)應(yīng)關(guān)系為：

k=3(i-1)-1(主對(duì)角線左下角，即i=j+1)

k=3(i-1)(主對(duì)角線上，即i=j)

k=3(i-1)+1(主對(duì)角線上，即i=j-1)由以上三式，得

k=2(i-1)+(j-1)(1≤

i,j≤

n;0≤

k≤

3n-1)特殊矩陣——對(duì)角矩陣稀疏矩陣的定義稀疏矩陣的定義非零元素較少，分布無(wú)規(guī)律。稀疏因子假設(shè)m行n列的矩陣含t個(gè)非零元素，則稀疏因子為δ=t/(m*n)<=0.05。稀疏矩陣的存儲(chǔ)結(jié)構(gòu)二維數(shù)組？壓縮存儲(chǔ)？以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時(shí)產(chǎn)生的問(wèn)題:(1)零值元素占了很大空間;(2)計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。(1)盡可能少存或不存零值元素；解決問(wèn)題的原則:(2)盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；(3)操作方便。即：能盡可能快地找到與下標(biāo)值(i，j)對(duì)應(yīng)的元素，能盡可能快地找到同一行或同一列的非零值元。壓縮存儲(chǔ)時(shí)，對(duì)零元素不分配存儲(chǔ)空間，只存儲(chǔ)稀疏矩陣中的非零元。稀疏矩陣的壓縮存儲(chǔ)順序存儲(chǔ)結(jié)構(gòu)——三元組表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——十字鏈表ije12616-2

34-8

42346751-12539三元組順序表úúúúúú?ùêêêêêê?é---=0009012700030008000000000200060A

#defineMAXSIZE12500

typedefstruct{

inti,j;

//該非零元的行下標(biāo)和列下標(biāo)

ElemTypee;

//該非零元的值

}

Triple;

//三元組類型typedefstruct{

Triple

data[MAXSIZE+1];

intmu,nu,tu;

}TSMatrix;//三元組順序表表示稀疏矩陣三元組順序表例：下面的三元組順序表表示一個(gè)稀疏矩陣，試還原出它的稀疏矩陣。12221123134445366116ije0123450

0000

00000000

0000

0000

0000

20012

000

3

0000

0040

06016

000646datatumunu十字鏈表中非零元結(jié)點(diǎn)的結(jié)構(gòu):rowcoledownright元素結(jié)點(diǎn)十字鏈表同一列下一個(gè)非零元同一行下一個(gè)非零元十字鏈表的結(jié)構(gòu)類型typedefstructOLNode{int