數(shù)據(jù)結(jié)構(gòu)-第5章-數(shù)組和廣義表

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

內(nèi)容提要：

本章主要內(nèi)容是：數(shù)組的類型定義和存儲結(jié)構(gòu)；特殊矩陣和稀疏矩陣的壓縮存儲方法；廣義表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。重點要求掌握數(shù)組轉(zhuǎn)置等基本運算、稀疏矩陣的三元組形式的順序表示和十字鏈表的表示方法、用三元組的形式來實現(xiàn)稀疏矩陣的轉(zhuǎn)置運算。1一維數(shù)組具有線性表的結(jié)構(gòu)，但操作簡單，一般不進行插入和刪除操作，只定義給定下標讀取元素和修改元素的操作二維數(shù)組中，每個數(shù)據(jù)元素對應一對數(shù)組下標，在行方向上和列方向上都存在一個線性關(guān)系，即存在兩個前驅(qū)（前件）和兩個后繼（后件）。也可看作是以線性表為數(shù)據(jù)元素的線性表。n維數(shù)組中，每個數(shù)據(jù)元素對應n個下標，受n個關(guān)系的制約，其中任一個關(guān)系都是線性關(guān)系?？煽醋魇菙?shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。因此，多維數(shù)組和廣義表是對線性表的擴展：線性表中的數(shù)據(jù)元素本身又是一個多層次的線性表。25.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲5.4廣義表的定義35.1數(shù)組的定義

數(shù)組（array）是n（n>1）個相同類型數(shù)據(jù)的有序組合，數(shù)組中的數(shù)據(jù)是按順序存儲在一塊地址連續(xù)的存儲單元中。數(shù)組中的每一個數(shù)據(jù)通常稱為數(shù)組元素，數(shù)組元素用下標區(qū)分，其中下標的個數(shù)由數(shù)組的維數(shù)決定。

45.1數(shù)組的定義一個二維數(shù)組的邏輯結(jié)構(gòu)可以定義成如下形式：Array_2=(D,R)其中D={aij

|i=c1,c1+1,…，d1,j=c2,c2+1,…,d2,aij∈D0} R={ROW,COL} ROW={<aij,ai,j+1>|c1≤i≤d1,c2≤j≤d2-1,aij,ai,j+1∈D} COL={<aij,ai+1,j>|c1≤i≤d1-1,c2≤j≤d2,aij,ai+1,j∈D}55.1數(shù)組的定義在C語言中，一個二維數(shù)組類型可以定義為其數(shù)據(jù)元素是一維數(shù)組類型的一維數(shù)組類型，即下面的二維數(shù)組類型的定義：

typedef

ElemTypeArray2[m][n];

相當于下面兩條語句的定義：

typedef

ElemTypeArray1[n];

typedefArray1Array2[m];65.2數(shù)組的順序表示和實現(xiàn)

數(shù)組在計算機中是采用順序存儲結(jié)構(gòu)來實現(xiàn)數(shù)組元素的存放，即在計算機內(nèi)存中采用一片連續(xù)的存儲單元來存放數(shù)組元素。

75.2數(shù)組的順序表示和實現(xiàn)對于二維數(shù)組，有兩種排列形式，一種是以行序為主（RowMajorOrder），即先存儲第一行，然后是第二行，依次向下存儲，直到最后一行的最后一個元素；另一種是以列序為主（ColumnMajorOrder），即先存儲第一列，然后是第二列，依次向下直到最后一列的最后一個元素。高級語言中，PASCAL、COBOL、C、PL/1、BASIC等語言均是采用以行序為主的存儲形式，而高級語言FORTORN是采用以列序為主的存儲形式。

85.2數(shù)組的順序表示和實現(xiàn)由于數(shù)組在內(nèi)存中是按順序存放的，因此就很容易根據(jù)一個數(shù)組元素的地址求出其他數(shù)組元素的地址。例如，只要知道了第一個元素的存儲地址（即基地址）、數(shù)組維數(shù)、排列順序和每個元素所占存儲單元數(shù)，就可以計算出數(shù)組中其他任意一個數(shù)組元素的存儲地址。

95.2數(shù)組的順序表示和實現(xiàn)二維數(shù)組元素地址的計算

元素aij的地址LOC(i,j)為：

以行序為主LOC(i,j)=LOC(0,0)+(i*n+j)*L

以列序為主LOC(i,j)=LOC(0,0)+(j*m+i)*L

其中，LOC(0,0)為元素a00的地址，L為每個數(shù)據(jù)元素所占的存儲單元。105.2數(shù)組的順序表示和實現(xiàn)n維數(shù)組元素地址的計算

元素a[j1][j2]…[jn]的存儲位置為：LOC(j1,j2,…,jn)=LOC(0,0,…,0)+(d2*d3*…*dn*j1+d3*d4*…*dn*j2+…+dn*jn-1+jn)*L=LOC(0,0,…,0)+115.3矩陣的壓縮存儲

矩陣在科學計算和工程應用中廣泛使用。然而在某些特殊情況下，經(jīng)常會出現(xiàn)一些階數(shù)很高的矩陣，其中含有很多值相同的元素或者零元素。為了節(jié)省存儲空間，經(jīng)常需要對這些矩陣進行壓縮存儲。所謂壓縮存儲是對矩陣中值相同的元素只分配一個存儲空間，而對零元素則不分配空間。

125.3矩陣的壓縮存儲對于需要壓縮存儲的矩陣可以分為特殊矩陣和稀疏矩陣。對那些具有相同值元素或零元素在矩陣中分布具有一定規(guī)律的矩陣，我們稱之為特殊矩陣（specialmatrices）；而對于那些零元素數(shù)目遠遠多于非零元素數(shù)目，并且非零元素的分布沒有規(guī)律的矩陣稱為稀疏矩陣。下面我們就對這兩種矩陣及其壓縮存儲進行介紹。

135.3.1特殊矩陣在一個n階方陣a中，若元素滿足如下性質(zhì)：aij=aji (0≤i,j≤n-1)

則稱A為n階對稱矩陣。對稱矩陣中的元素關(guān)于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，這樣，能節(jié)約近一半的存儲空間。145.3.1特殊矩陣按“行優(yōu)先順序”存儲主對角線（包括對角線）以下的元素，其存儲形式如圖所示：

15137a11

50800a21a22

18926a31a32a33

30251………………..

70613an1an2an3…ann

在下三角矩陣中，第i行恰有i個元素，元素總數(shù)為：n(n+1)/2.因此，我們可以將這些元素存放在一個向量sa[0..n(n+1)/2-1]中155.3.1特殊矩陣

sa[k]與a[i][j])的對應關(guān)系：

i*(i-1)/2+j-1當i≥j k=j*(j-1)/2+i-1當i<ji,j=1,2,…,n;k=0,1,…,n(n+1)/2-1思考：給定一個k,如何求i和j？ 165.3.1特殊矩陣除了對稱矩陣以外，三角矩陣也屬于特殊矩陣，三角矩陣又可分為上三角矩陣和下三角矩陣。上三角矩陣是指矩陣的下三角（除對角線以外）中的元素均為常數(shù)或零的矩陣，而下三角矩陣則與上三角矩陣相反。三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個分量中。175.3.1特殊矩陣上三角矩陣

185.3.1特殊矩陣下三角矩陣

195.3.2稀疏矩陣在通常的數(shù)值處理過程中，經(jīng)常遇到矩陣非零元素較少，但又沒有一定的分布規(guī)律，這種情況稱為稀疏矩陣。人們無法給出稀疏矩陣的確切定義，一般都是憑一個人的直覺來理解這個概念，簡單說，設(shè)矩陣A中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。205.3.2稀疏矩陣稀疏矩陣M215.3.2稀疏矩陣由于稀疏矩陣中非零元素較少，零元素較多，因此可以采用只存儲非零元素的方法來進行壓縮存儲。又由于非零元素分布沒有規(guī)律，所以在進行壓縮存儲的時候需要在存儲非零元素值的同時還要存儲非零元素在矩陣中的位置，即非零元素所在的行和列號。也就是在存儲某個元素aij值的同時，還需要存儲該元素所在的行號i和它的列號j，這樣就構(gòu)稱了一個三元組（

i,j,aij

）的形式。

225.3.2稀疏矩陣一個三元組表能夠唯一確定一個矩陣中的非零元素，例如下面的三元組是對前面矩陣M中非零元的表示。（0，0，2），（0，4，6），（0，7，7），（1，2，1），（2，2，－2），（2，6，3），（3，5，8），（4，3，5），（5，1，9）

以上是按照行號順序，將三元組9個非零元素按順序進行排列（當然也可以按照列號的順序進行排列），如果再加上一個表示矩陣行數(shù)、列數(shù)和總的非零元素數(shù)目的特殊三元組（6，8，9），就可以唯一的確定一個矩陣。

231.三元組順序表用順序存儲結(jié)構(gòu)表示三元組表（TripleTable），來實現(xiàn)對稀疏矩陣的一種壓縮存儲形式，就稱為三元組順序表，簡稱三元組表。#defineMAXSIZE10000typedef

struct{typedef

struct{Tripledata[MAXSIZE+1];

inti,j;int

mu,nu,tu;

ElemTypee;}TsMatrix;}Triple;

241.三元組順序表下面以矩陣的轉(zhuǎn)置為例，說明在這種壓縮存儲結(jié)構(gòu)上如何實現(xiàn)矩陣的運算。一個m×n的矩陣A，它的轉(zhuǎn)置B是一個n×m的矩陣，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n，即A的行是B的列，A的列是B的行。將A轉(zhuǎn)置為B，就是將A的三元組表a.data置換為表B的三元組表b.data.

由于A的列是B的行，因此，按a.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。251.三元組順序表ijv121213931-3361443245218611564-7ijv13-3161521122518319342446-76314其基本思想是：對A中的每一列col(0≦col≦n-1)，通過從頭至尾掃描三元表a.data，找出所有列號等于col的那些三元組，將它們的行號和列號互換后依次放入b.data中，即可得到B的按行優(yōu)先的壓縮存儲表示。a.datab.data261.三元組順序表StatusTransposeSMatrix(TSMatrixM,TSMatrixT){

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;

for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}}returnOK;}27快速轉(zhuǎn)置算法方法：按a.data中三元組的次序進行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入b中恰當?shù)奈恢?。建立輔助數(shù)組num和cpot，num[col]表示矩陣第col列中非零元的個數(shù)，cpot[col]指示第col列的第一個非零元素在b.data中的恰當位置。按行掃描矩陣三元組表，根據(jù)某項的列號，確定它轉(zhuǎn)置后的行號，查cpot表，按查到的位置直接將該項存入轉(zhuǎn)置三元組表中。轉(zhuǎn)置時間復雜度為

O(nu+tu+nu+tu)=O(tu)。若矩陣有200列，10000個非零元素，總共需10000次處理。28表5.1(教材99頁)cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]29稀疏矩陣的快速轉(zhuǎn)置(算法5.2)StatusFastTransposeSMatrix(TSMatrix

M,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0; for(t=1;t<=M.tu;++t)++num[M.data[t].j]; cpot[1]=1; for(col=2;col<=M.nu;++col)

cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){ col=M.data[p].j; q=cpot[col];

T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e; ++cpot[col];} }returnOK;}302.十字鏈表當矩陣中非零元素的個數(shù)和位置經(jīng)過運算后變化較大時，就不宜采用順序存儲結(jié)構(gòu)，而應采用鏈式存儲結(jié)構(gòu)來表示三元組。稀疏矩陣的鏈接表示采用十字鏈表：行鏈表與列鏈表十字交叉。行鏈表與列鏈表都是帶表頭結(jié)點的單鏈表。用表頭結(jié)點表征是第幾行，第幾列。31元素結(jié)點(有5個域)right——指向同一行中下一個非零元素的指針（向右域）down——指向同一列中下一個非零元素的指針（向下域）表頭結(jié)點行表頭結(jié)點列表頭結(jié)點next用于表示頭結(jié)點的鏈接rowcolvaldownrightcol=0nextrightrow=0nextdown32由于行、列表頭結(jié)點互相不沖突，所以可以合并起來：總表頭結(jié)點：row=0col=0nextdownrightrowcolnext33稀疏矩陣的十字鏈表表示的示例見104頁的圖5.6。需要輔助結(jié)點作鏈表的表頭，同時每個結(jié)點要增加兩個指針域，所以只有在矩陣較大和較稀疏時才能起到節(jié)省空間的效果。分別用兩個一維數(shù)組存儲行鏈表的頭指針和列鏈表的頭指針，可加快訪問速度。34十字鏈表的類型定義typedef

struct

OLNode{//元素結(jié)點

int

i,j;//非零元的行和列下標

ElemTypee;

struct

OLNode*right,*down;

//該非零元所在行表和列表的后繼鏈域

}OLNode,*OLink;typedef

struct{

OLink*rhead,*chead;//行和列鏈表頭指針數(shù)組

int

mu,nu,tu;}CrossList;35十字鏈表的建立(算法5.4)自學365.4廣義表的定義

廣義表（GeneralizedLists）是線性表的推廣，又簡稱表（Lists）。廣義表是n(n>=0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項，或者是一個廣義表。通常記作LS=（a1,a2,a3,…,an)LS是廣義表的名字，n為它的長度。若ai是廣義表，則稱它為LS