《數(shù)據(jù)結構與算法》第五章-數(shù)組和廣義表學習指導材料

《數(shù)據(jù)結構與算法》第五章數(shù)組和廣義表

本章介紹的數(shù)組與廣義表可視為線性表的推廣，其特點是數(shù)據(jù)元素仍然是一個表。本章

討論多維數(shù)組的邏輯結構和存儲結構、特殊矩陣、矩陣的壓縮存儲、廣義表的邏輯結構和存

儲結構等。

5.1多維數(shù)組

5.1.1數(shù)組的邏輯結構

數(shù)組是我們很熟悉的一種數(shù)據(jù)結構，它可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結

構其特點是結構中的元素本身可以是具有某種結構的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一

維數(shù)組可以看作一個線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維

數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。圖5.1是一個m行n列的二

維數(shù)組。

廠anai2...ain、

321322...a2n

A=......

amI3m2...Hmn

I

圖5.1m行n列的二維數(shù)組

5.1.2數(shù)組的內(nèi)存映象

現(xiàn)在來討論數(shù)組在計算機中的存儲表示。通常，數(shù)組在內(nèi)存被映象為向量，即用向量

作為數(shù)組的一種存儲結構，這是因為內(nèi)存的地址空間是一維的，數(shù)組的行列固定后，通過一

個映象函數(shù)，則可根據(jù)數(shù)組元素的下標得到它的存儲地址。

對于一維數(shù)組按下標順序分配即可。

對多維數(shù)組分配時，要把它的元素映象存儲在一維存儲器中，一般有兩種存儲方式：一

是以行為主序(或先行后列)的順序存放，如BASIC.PASCAL.COBOL.C等程序設計

語言中用的是以行為主的順序分配，即一行分配完了接著分配下一行。另一種是以列為主序

(先列后行)的順序存放，如FORTRAN語言中，用的是以列為主序的分配順序，即一列

一列地分配。以行為主序的分配規(guī)律是：最右邊的下標先變化，即最右下標從小到大，循環(huán)

一遍后，右邊第二個下標再變，…，從右向左，最后是左下標。以列為主序分配的規(guī)律恰好

相反：最左邊的下標先變化，即最左下標從小到大，循環(huán)一遍后，左邊第二個下標再變，…，

從左向右，最后是右下標。

例如一個2x3二維數(shù)組，邏輯結構可以用圖5.2表示。以行為主序的內(nèi)存映象如圖5.3

(a)所示。分配順序為：an,a12,a13,a2I,a22,a23;以列為主序的分配順序為:an,

321,ai2，322，3|3,223；它的內(nèi)存映象如圖5.3(b)所不。

ananai3

321322323

圖5.22x3數(shù)組的邏輯狀態(tài)(a)以行為主序(b)以列為主序

圖5.32x3數(shù)組的物理狀態(tài)

設有mxn二維數(shù)組A?，下面我們看按元素的下標求其地址的計算：

以“以行為主序”的分配為例：設數(shù)組的基址為LOC(au),每個數(shù)組元素占據(jù)1個地址

單元，那么aij的物理地址可用一線性尋址函數(shù)計算：

LOC(aij)=LOC(an)+((i-l)*n+j-l)*1

這是因為數(shù)組元素au的前面有i-1行，每一行的元素個數(shù)為n,在第i行中它的前面還

有j-1個數(shù)組元素。

在C語言中，數(shù)組中每一維的下界定義為0,則：

LOC(aij)=LOC(aoo)+(i*n+j)*1

推廣到一般的二維數(shù)組：A[c1..d1][c2..d2],則aij的物理地址計算函數(shù)為：

LOC(aij)=LOC(aCiC2)+((i-ct)*(d2-C2+1)+(j-ci))*1

例5.1若矩陣Amxn中存在某個元素aij滿足：a”是第i行中最小值且是第j列中的最大值,

則稱該元素為矩陣A的一個鞍點。試編寫一個算法，找出A中的所有鞍點。

基本思想：在矩陣A中求出每一行的最小值元素，然后判斷該元素它是否是它所在列

中的最大值，是則打印出，接著處理下一行。矩陣A用一個二維數(shù)組表示。

算法如下：

voidsaddle(intA[][],intm,intn)

Z*m,n是矩陣A的行和列*/

{inti,j,min;

for(i=0;i<m;i++)/*按行處理*/

{min=A[i][0]

for(j=l;j<n;j++)

if(A[i]|jkmin)min=A[IJ[jJ;/*找第I行最小值*/

for(j=0;j<n;j++)/*檢測該行中的每一個最小值是否是鞍點*/

if(A[I][j]==min)

{k=j;p=0;

while(p<m&&A[p][j]<min)

P++；

if(p>=m)printf("%d,%d,%d\n",i,k,min);

}/*if*/

}/*fori*/

)

算法的時間性能為0(m*(n+m*n))o

5.2特殊矩陣的壓縮存儲

對于一個矩陣結構顯然用一個二維數(shù)組來表示是非常恰當?shù)?，但在有些情況下，比如

常見的一些特殊矩陣，如三角矩陣、對稱矩陣、帶狀矩陣、稀疏矩陣等，從節(jié)約存儲空間的

角度考慮，這種存儲是不太合適的。下面從這一角度來考慮這些特殊矩陣的存儲方法。

5.2.1對稱矩陣

對稱矩陣的特點是：在一個n階方陣中，有@尸斯，其中l(wèi)Wi,jWn,如圖5.5所示是

一個5階對稱矩陣。對稱矩陣關于主對角線對稱，因此只需存儲上三角或下三角部分即可，

比如，我們只存儲下三角中的元素ay,其特點是中jWi且1WiWn,對于上三角中的元素aij,

它和對應的即相等，因此當訪問的元素在上三角時，直接去訪問和它對應的下三角元素即

可，這樣，原來需要n*n個存儲單元，現(xiàn)在只需要n(n+l)/2個存儲單元了，節(jié)約了n(n-l)/2

個存儲單元，當n較大時，這是可觀的一部分存儲資源。

廠

3647

62842

A=48169

74605

、82957

362481746082957

圖5.55階對稱方陣及它的壓縮存儲

如何只存儲下三角部分呢？對下三角部分以行為主序順序存儲到一個向量中去，在下三

角中共有n*(n+l)/2個元素，因此，不失一般性，設存儲到向量SA［n(n+l)/2］中，存儲順序

可用圖5.6示意，這樣，原矩陣下三角中的某一個元素aij則具體對應一個sak，下面的問題

是要找到k與i、j之間的關系。

012345.….加+1)/2?1

Iana2ia22aaia32@33...anian2...an

第［行t'j/2I__IJ)

第2行第3行第n行

圖5.6一般對稱矩陣的壓縮存儲

對于下三角中的元素a.,其特點是：i'j且IWiWn,存儲到SA中后，根據(jù)存儲原則，

它前面有i-1行，共有1+2+…+i-l=i*(i-l)/2個元素，而a.又是它所在的行中的第j個，所以

在上面的排列順序中，a.是第i*(i-l)/2+j個元素，因此它在SA中的下標k與i、j的關系為:

k=i*(i-l)/2+j-l(0Wk<n*(n+1)/2)

若i<j,則aij是上三角中的元素，因為a產(chǎn)即，這樣，訪問上三角中的元素aij時則去訪

問和它對應的下三角中的即即可，因此將上式中的行列下標交換就是上三角中的元素在SA

中的對應關系：

k=j*(j-l)/2+i-l(0Wk<n*(n+l)/2)

綜上所述，對于對稱矩陣中的任意元素ay,若令I=max(i,j),J=min(i,j),則將上面兩個

式子綜合起來得到：k=I*(I-l)/2+J-l。

5.3稀疏矩陣

設m*n矩陣中有t個非零元素且t?m*n,這樣的矩陣稱為稀疏矩陣。很多科學管理及

工程計算中，常會遇到階數(shù)很高的大型稀疏矩陣。如果按常規(guī)分配方法，順序分配在計算機

內(nèi)，那將是相當浪費內(nèi)存的。為此提出另外一種存儲方法，僅僅存放非零元素。但對于這類

矩陣，通常零元素分布沒有規(guī)律，為了能找到相應的元素，所以僅存儲非零元素的值是不夠

的，還要記下它所在的行和列。于是采取如下方法：將非零元素所在的行、列以及它的值構

成一個三元組（i,j,v）,然后再按某種規(guī)律存儲這些三元組，這種方法可以節(jié)約存儲空間。

下面討論稀疏矩陣的壓縮存儲方法。

5.3.1稀疏矩陣的三元組表存儲

將三元組按行優(yōu)先的順序，同一行中列號從小到大的規(guī)律排列成一個線性表，稱為三

元組表，采用順序存儲方法存儲該表。如圖5.11稀疏矩陣對應的三元組表為圖5.12。

顯然，要唯一的表示一個稀疏矩陣，還需要存儲三元組表的同時存儲該矩陣的行、歹U,

為了運算方便，矩陣的非零元素的個數(shù)也同時存儲。這種存儲的思想實現(xiàn)如下：

ijv

「1500220-15~^

0113000

11115

000600

A二21422

000000

316-15

910000042211

Lo00000J

5233

6346

圖5.11稀疏矩陣

75191

define

/*一個足夠大的數(shù)*/

SMAX1024圖5.12三元組表

typedefstruct

inti,j;/*非零元素的行、列*/

datatypev;/*非零元素值*/

JSPNode;/*三元組類型*/

typedefstruct

{inimu,nu,tu;/*矩陣的行、列及非零元素的個數(shù)*/

SPNodedatalSMAX];/*三元組表*/

}SPMatrix;/*三元組表的存儲類型*/

這樣的存儲方法確實節(jié)約了存儲空間，但矩陣的運算從算法上可能變的復雜些。下面

我們討論這種存儲方式下的稀疏矩陣的兩種運算：轉置和相乘。

1.稀疏矩陣的轉置

設SPMatrixA;表示一m*n的稀疏矩陣，其轉置B則是一個n*m的稀疏矩陣，因此

也有SPMatrixB;由A求B需要：

A的行、列轉化成B的列、行；

將A.data中每一三元組的行列交換后轉化到B.data中；

看上去以上兩點完成之后，似乎完成了B,沒有。因為我們前面規(guī)定三元組的是按一行

一行且每行中的元素是按列號從小到大的規(guī)律順序存放的，因此B也必須按此規(guī)律實現(xiàn)，A

的轉置B如圖5.13所示，圖5.14是它對應的三元組存儲，就是說，在A的三元組存儲基礎

上得到B的三元組表存儲（為了運算方便，矩陣的行列都從1算起，三元組表data也從1

單元用起）。

算法思路：

①A的行、列轉化成B的列、行；

②在A.data中依次找第一列的、第二列的、直到最后一列，并將找到的每個三元組的

行、列交換后順序存儲到B.data中即可。

廠15000910、

ijv

0110000—

03000011115

R-

220600021591

00000032211

11500000J

4323

54122

圖5.13A的轉置B6436

761-15

圖5.14B的三元組表

算法如下：

voidTransMl(SPMatrix*A)

{SPMatrix*B;

intp,q,col;

B=malloc(sizeof(SPMatrix));/*申請存儲空間*/

B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;

/*稀疏矩陣的行、歹I」、元素個數(shù)*/

if(B->tu>0)/*有非零元素則轉換*/

{q=o；

for(col=l;col<=(A->nu);col++)/*按A的列序轉換*/

for(p=1;p<=(A->tu);p++)/*掃描整個三元組表*/

if(A->data[p].j==col)

{B->data[q].i=A->data[p].j;

B->data[q].j=A->data[p].i;

B->data[q].v=A->data[p].v;

q++;}/*i//

}/*if(B->tu>0)*/

returnB;/*返回的是轉置矩陣的指針刃

}/*TransMl*/

算法5.1稀疏矩陣轉置

分析該算法，其時間主要耗費在col和p的二重循環(huán)上，所以時間復雜性為O(n*t),

(設m、n是原矩陣的行、歹U,t是稀疏矩陣的非零元素個數(shù))，顯然當非零元素的個數(shù)t和

m*n同數(shù)量級時，算法的時間復雜度為O(m*n2),和通常存儲方式下矩陣轉置算法相比，可

能節(jié)約了一定量的存儲空間，但算法的時間性能更差一些。

算法5.1的效率低的原因是算法要從A的三元組表中尋找第一列、第二列、…，要反復

搜索A表，若能直接確定A中每一三元組在B中的位置，則對A的三元組表掃描一次即可。

這是可以做到的，因為A中第一列的第一個非零元素一定存儲在如果還知道第

一列的非零元素的個數(shù)，那么第二列的第一個非零元素在B.data中的位置便等于第一列的

第一個非零元素在B.data中的位置加上第一列的非零元素的個數(shù)，如此類推，因為A中三

元組的存放順序是先行后列，對同一行來說，必定先遇到列號小的元素，這樣只需掃描一遍

A.data即可。

根據(jù)這個想法,需引入兩個向量來實現(xiàn)：num[n+l]和cpot[n+l],num[col]表示矩陣A

中第col列的非零元素的個數(shù)（為了方便均從1單元用起），cpot[col]初始值表示矩陣A

中的第col列的第一個非零元素在B.data中的位置。于是cpot的初始值為：

cpot[l]=l；

cpot[col]=cpot[col-1]+num[col-1]；2WcolWn

例如對于矩陣圖5.11矩陣A的num和cpot的值如下：

Col123456

num[col]211201

cpotfcoll134577

圖5.15矩陣A的num與cpot值

依次掃描A.data,當掃描到一個col列元素時，直接將其存放在B.data的cpotfcol]位置

上，cpotfcol]力口1,cpot[col]中始終是下一個col列元素在B.data中的位置。

下面按以上思路改進轉置算法如下：

SPMatrix*TransM2(SPMatrix*A)

{SPMatrix*B;

inti,j,k;

intnum[n+1],cpot[n+1];

B=malloc(sizeof(SPMatrix));/*申請存儲空間*/

B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;

/*稀疏矩陣的行、歹I」、元素個數(shù)可

if(B->tu>0)/*有非零元素則轉換*/

{for(i=l;i<=A->nu;i++)num[i]=0;

for(i=l;i<=A->tu;i++)/*求矩陣A中每一列非零元素的個數(shù)*/

{j=A->data[i].j;

num[j]++;}

cpot[l]=l；/*求矩陣A中每一列第一個非零元素在B.data中的位置*/

for(i=2;i<=A->nu;i++)

cpot[i]=cpot[i-l]+num[i-l];

for(i=l;i<=(A->tu);i++)/*掃描三元組表*/

{j=A->data[i].j;/*當前三元組的列號*/

k=cpot[j];/*當前三元組在B.data中的位置*/

B->data[k].i=A->data[i].j;

B->data[k].j=A->datafi].i;

B->data[k].v=A->data[i].v;

cpotfj]++;

}/*fori*/

}/*if(B->tu>0)*/

returnB;/*返回的是轉置矩陣的指針*/

}/*TransM2*/

算法5.2稀疏矩陣轉置的改進算法

分析這個算法的時間復雜度：這個算法中有四個循環(huán)，分別執(zhí)行n,t,n-1,t次，在每

個循環(huán)中，每次迭代的時間是一常量，因此總的計算量是O(n+t)。當然它所需要的存儲空

間比前一個算法多了兩個向量。

5.3.2稀疏矩陣的十字鏈表存儲

三元組表可以看作稀疏矩陣順序存儲，但是在做一些操作(如加法、乘法)時，非零

項數(shù)目及非零元素的位置會發(fā)生變化，這時這種表示就十分不便。在這節(jié)中，我們介紹稀疏

矩陣的一種鏈式存儲結構一一十字鏈表，它同樣具備鏈式存儲的特點，因此，在某些情況下,

采用十字鏈表表示稀疏矩陣是很方便的。

圖5.18是一個稀疏矩陣的十字鏈表。

3QO7

0o-1O

2oo0

0oo0

0OO

-8

圖5.18用十字鏈表表示的稀疏矩陣A

用十字鏈表表示稀疏矩陣的基本思想是：對每個非零元素存儲為一個結點，結點由5

個域組成，其結構如圖5.19表示，其中：row域存儲非零元素的行號，col域存儲非零元素

的列號，v域存儲本元素的值，right,down是兩個指針域。

rowcolV

downright

圖5.19十字鏈表的結點結構

5.4廣義表

顧名思義，廣義表是線性表的推廣。也有人稱其為列表(Lists,用復數(shù)形式以示與統(tǒng)稱

的表List的區(qū)別)。

5.4.1廣義表的定義和基本運算

1.廣義表的定義和性質(zhì)

我們知道，線性表是由n個數(shù)據(jù)元素組成的有限序列。其中每個組成元素被限定為單元

素，有時這種限制需要拓寬。例如，中國舉辦的某體育項目國際邀請賽，參賽隊清單可采用

如下的表示形式：

(俄羅斯，巴西，(國家，河北，四川)，古巴，美國，()，日本)

在這個拓寬了的線性表中，韓國隊應排在美國隊的后面，但由于某種原因未參加，成為

空表。國家隊、河北隊、四川隊均作為東道主的參賽隊參加，構成一個小的線性表，成為原

線性表的一個數(shù)據(jù)項。這種拓寬了的線性表就是廣義表。