數(shù)據(jù)結構數(shù)組

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

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

不同之處：

(1)數(shù)組要求其元素占用一塊地址連續(xù)的內存單元空間，而線性表無此要求；(2)線性表的元素是邏輯意義上不可再分的元素，而數(shù)組中的每個元素還可以是一個數(shù)組；(3)數(shù)組的操作主要是向某個下標的數(shù)組元素中存放數(shù)據(jù)和取某個下標的數(shù)組元素，這與線性表的插入和刪除操作不同。本講內容5.1數(shù)組的定義1.數(shù)組2.數(shù)組的邏輯定義5.2數(shù)組的順序存儲5.3矩陣的壓縮存儲1.特殊矩陣2.稀疏矩陣數(shù)組數(shù)組邏輯上是線性結構的推廣；數(shù)組是以線性表為元素的線性結構，而且元素的結構相同；數(shù)組可以看作是下標和值的偶對的集合；數(shù)組是一種邏輯結構。高級語言中的數(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];兩個變量組成的一個數(shù)組，其中每一個變量都是數(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ù)組是一個向量，它的每個元素是n-1維數(shù)組，且具有相同的上限和下限。

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

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

數(shù)據(jù)關系：

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ù)組的操作對于數(shù)組的操作一般只有兩類：(1)給定一組下標，存取相應的數(shù)據(jù)元素(2)給定一組下標，修改相應的數(shù)據(jù)元素的值。數(shù)組一般不做插入和刪除操作數(shù)組的存儲實現(xiàn)機制１、一維數(shù)組（n個元素）中任一元素ai的內存單元地址LOC(ai)=LOC(a０)+i*k(0≤i<n)２、一個m行n列的二維數(shù)組LOC(aij)=LOC(a00)+(i*n+j)*k(0≤i<m，0≤j<n)注：C語言中數(shù)組元素采用行主序的存放方法，即行優(yōu)先順序。順序存儲時按行序和列序的約定數(shù)組順序存儲時，必須確定按行序或列序存儲：（1）PASCAL、C以行序為主存儲（2）FORTRAN以列序為主存儲a11

a12

…

a1n

a21

a22

…

a2n

…

am1

am2

…

amn

a11

a21

…

am1

a12

a22

…

am2

…

a1n

a2n

…

amn

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

稱為基地址或基址。以“行序為主序”的存儲映象二維數(shù)組A中任一元素ai,j的存儲位置LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

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

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

(

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

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

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

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

aij=aji

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

a21

a22

a31

…

an1

…

ann

k=0123

n2個元素可以壓縮到n(n+1)/2個空間中；以行序為主序將其下三角（包括對角線）中的元素存儲到一個向量B[n(n+1)/2]中:特殊矩陣——對稱矩陣向量B[k]和矩陣中的元素aij之間存在著一一對應關系：

下面按下標從0開始討論。

向量B[k]和矩陣中的元素aij之間的關系：由i和j推導k：特殊矩陣——對稱矩陣下標變換公式三角矩陣:

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

。特殊矩陣——對角矩陣對角矩陣:

所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中。即除了主對角線上和直接在對角線上、下方若干條對角線上的元素之外，所有其它的元素均為零。b條對角線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

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

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

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

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

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

i,j≤

n;0≤

k≤

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

34-8

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

#defineMAXSIZE12500

typedefstruct{

inti,j;

//該非零元的行下標和列下標

ElemTypee;

//該非零元的值

}

Triple;

//三元組類型typedefstruct{

Triple

data[MAXSIZE+1];

intmu,nu,tu;

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

0000

00000000

0000

0000

0000

20012

000

3

0000

0040

06016

000646datatumunu十字鏈表中非零元結點的結構:rowcoledownright元素結點十字鏈表同一列下一個非零元同一行下一個非零元十字鏈表的結構類型typedefstructOLNode{int