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

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

不同之處：

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

a[0][1]a[0][0]a[1][2]a[1][1]a[1][0]a[0][2]數組的邏輯定義

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

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

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

數據關系：

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

a12

…

a1n

a21

a22

…

a2n

…

am1

am2

…

amn

a11

a21

…

am1

a12

a22

…

am2

…

a1n

a2n

…

amn

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

稱為基地址或基址。以“行序為主序”的存儲映象二維數組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

設二維數組A[c1..d1][c2..d2]

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

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

矩陣的壓縮存儲壓縮存儲思想當矩陣的階數較高，而且矩陣中的一些元素有特殊的性質時，可以采用節省空間的存儲辦法（壓縮存儲）。兩類矩陣1.特殊矩陣：值相同的元素或非零元素分布有一定的規律；2.稀疏矩陣：非零元素少且分布無規律；對稱矩陣、上（下）三角矩陣、對角矩陣特殊矩陣——對稱矩陣若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：特殊矩陣——對稱矩陣下標變換公式三角矩陣:

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

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

所有非零元素都集中在以主對角線為中心的帶狀區域中。即除了主對角線上和直接在對角線上、下方若干條對角線上的元素之外，所有其它的元素均為零。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]中,元素在一維數組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)特殊矩陣——對角矩陣稀疏矩陣的定義稀疏矩陣的定義非零元素較少，分布無規律。稀疏因子假設m行n列的矩陣含t個非零元素，則稀疏因子為δ=t/(m*n)<=0.05。稀疏矩陣的存儲結構二維數組？壓縮存儲？以常規方法，即以二維數組表示高階的稀疏矩陣時產生的問題:(1)零值元素占了很大空間;(2)計算中進行了很多和零值的運算，遇除法，還需判別除數是否為零。(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