數(shù)組和廣義表課件

一、教學內(nèi)容：

1、 數(shù)組的定義和順序存儲方式；

2、 特殊矩陣的壓縮存儲；

3、 稀疏矩陣

4、 廣義表的概念、表示及基本操作；廣義表存儲結(jié)構的實現(xiàn)。

二、教學要求：

1、 了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構中的地址計算方法；

2、 掌握對特殊矩陣進行壓縮存儲時的下標變換公式；

3、 了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍，理解以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法；

4、 掌握廣義表的結(jié)構特點及其存儲表示方法，會對非空廣義表進行分解。

第五章數(shù)組和廣義表一、教學內(nèi)容：

1、 數(shù)組的定義和順序存儲方式；

2、 特殊第五章數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲5.3.1特殊矩陣5.3.2稀疏矩陣5.4廣義表的定義5.5廣義表的存儲結(jié)構第五章數(shù)組和廣義表5.1數(shù)組的定

數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的數(shù)據(jù)元素本身也是一種線性表。

5.1數(shù)組的定義由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標一般具有固定的上界和下界，因此，數(shù)組的處理比其它復雜的結(jié)構更為簡單。多維數(shù)組是向量的推廣。例如，二維數(shù)組：

()()()()()()()()()數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表

可以看成是由一個行向量組成的向量，也可以看成是由一個列向量組成的向量。在C語言中，一個二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說，typedefelemtypearray2[m][n];等價于：typedefelemtypearray1[n];typedefarray1array2[m];數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作?？梢钥闯墒怯梢粋€行向量組成的向量，也可以看成是由一個

5.2數(shù)組的順序表示和實現(xiàn)

由于計算機的內(nèi)存結(jié)構是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。又由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構中的元素個數(shù)和元素間的關系就不再發(fā)生變化。因此，一般都是采用順序存儲的方法來表示數(shù)組。

5.2數(shù)組的順序表示和實現(xiàn)通常有兩種順序存儲方式：以行序為主序以列序為主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序為主序存放amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n

按列序為主序存放01m-1m*n-1mamn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

通常有兩種順序存儲方式：a11計算二維數(shù)組元素地址的通式

設一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是0。無論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時求出任一元素的地址（這樣數(shù)組中的任一元素便可以隨機存取?。憾S數(shù)組列優(yōu)先存儲的通式為：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

Amn=單個元素長度aij之前的行數(shù)數(shù)組基址總列數(shù)，即第2維長度aij本行前面的元素個數(shù)①開始結(jié)點的存放地址（即基地址）②維數(shù)和每維的上、下界；③每個數(shù)組元素所占用的單元數(shù)則行優(yōu)先存儲時的地址公式為：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L計算二維數(shù)組元素地址的通式

設一般的二維數(shù)組是A[c1..d例2：已知二維數(shù)組Am,m按行存儲的元素地址公式是：

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,按列存儲的公式是？Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K（盡管是方陣，但公式仍不同）例1〖軟考題〗：一個二維數(shù)組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是

個字節(jié)。288例3：〖00年某?？佳蓄}〗設數(shù)組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為

。8950LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝8950答：請注意審題！利用列優(yōu)先通式：答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例2：已知二維數(shù)組Am,m按行存儲的元素地址公式是：

Lo5.3矩陣的壓縮存儲

在科學與工程計算問題中，矩陣是一種常用的數(shù)學對象，在高級語言編制程序時，簡單而又自然的方法，就是將一個矩陣描述為一個二維數(shù)組。矩陣在這種存儲表示之下，可以對其元素進行隨機存取，各種矩陣運算也非常簡單，并且存儲的密度為1。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來存儲密度仍為1，但實際上占用了許多單元去存儲重復的非零元素或零元素，這對高階矩陣會造成極大的浪費，為了節(jié)省存儲空間，我們可以對這類矩陣進行壓縮存儲：即為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。5.3矩陣的壓縮存儲5.3.1特殊矩陣

所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲。1、對稱矩陣在一個n階方陣A中，若元素滿足下述性質(zhì)：aij=aji0≦i,j≦n-1則稱A為對稱矩陣。如圖5.1便是一個5階對稱矩陣。對稱矩陣中的元素關于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，這樣，能節(jié)約近一半的存儲空間。不失一般性，我們按“行優(yōu)先5.3.1特殊矩陣順序”存儲主對角線（包括對角線）以下的元素，其存儲形式如圖所示：

15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1圖5.1對稱矩陣

在這個下三角矩陣中，第i行恰有i+1個元素，元素總數(shù)為：n(n+1)/2因此，我們可以按從上到下、從左到右將這些元素存放在一個向量sa[0..n(n+1)/2-1]中。為了便于訪問對稱矩陣A中的元素，我們必須在aij和sa[k]

順序”存儲主對角線（包括對角線）以下的元素，其存儲形式如圖所之間找一個對應關系。若i≧j，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）一共有1+2+…+i=i(i+1)/2個元素，在第i行上，aij之前恰有j個元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j0≦k<n(n+1)/2若i<j，則aij是在上三角矩陣中。因為aij=aji，所以只要交換上述對應關系式中的i和j即可得到：k=j*(j+1)/2+i0≦k<n(n+1)/2

之間找一個對應關系。2、三角矩陣以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…..……………..cc…an-1n-1an-10an-11…an-1n-1

(a)上三角矩陣(b)下三角矩陣

2、三角矩陣

三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個分量中，上三角矩陣中，主對角線之上的第i行(0≦i<n)恰有n-i個元素，按行優(yōu)先順序存放上三角矩陣中的元素aij時，aij之前的i行一共有i(2n-i+1)/2個元素，在第i行上，aij前恰好有j-i個元素：aii,aii+1,…aij-1。因此，sa[k]和aij的對應關系是：

k=i(2n-i+1)/2+j-i當i≦jn(n+1)/2當i>j三角矩陣中的重復元素c可共享一個存儲空間，其余的元

下三角矩陣的存儲和對稱矩陣類似，sa[k]和aij對應關系是：i(i+1)/2+ji≧jn(n+1)/2i<j3、對角矩陣對角矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。下圖給出了一個三對角矩陣，

a00a01a10a11a12a21a22a23….…..….圖5.3對角矩陣an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1k=下三角矩陣的存儲和對稱矩陣類似，sa[k]和aij對應關非零元素僅出現(xiàn)在主對角(aii,0≦i≦n-1上，緊鄰主對角線上面的那條對角線上(aii+1,0≦i≦n-2)和緊鄰主對角線下面的那條對角線上(ai+1i,0≦i≦n-2)。顯然，當∣i-j∣>1時，元素aij=0。由此可知，一個k對角矩陣(k為奇數(shù))A是滿足下述條件的矩陣：若∣i-j∣>(k-1)/2，則元素aij=0。對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標的對應關系。

非零元素僅出現(xiàn)在主對角(aii,0≦i≦n-1上，緊鄰主對角

在三對角矩陣里除滿足條件i=0，j=0、1，或i=n-1j=n-2、n-1或1<i<n-1,j=i-1、i、i+1的元素aij外，其余元素都是零。對這種矩陣，我們也可按行優(yōu)序為主序來存儲。除第0行和第n-1行是2個元素外，每行的非零元素都要是3個，因此，需存儲的元素個數(shù)為3n-2。a00a01

a10a11a12a21

……an-1n-2an-1n-1K=012345……3n-23n-1

數(shù)組sa中的元素sa[k]與三對角帶狀矩陣中的元素aij存在一一對應關系，在aij之前有i行,共有3*i-1個非零元素，在第i行，有j-i+1個非零元素，這樣，非零元素aij的地址為：在三對角矩陣里除滿足條件i=0，j=0、1，或i=n-1

LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d=LOC(0,0)+(2i+j)*d

上例中，a34對應著sa[10]。k=2*i+j=2*3+4=10a21對應著sa[5]k=2*2+1=5由此，我們稱sa[0..3*n-3]是階三對角帶狀矩陣A的壓縮存儲表示。LOC(i,j)=LOC(0,0)+[3*i-1+(j-i上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲到一個向量中，并且一般都能找到矩陣中的元素與該向量的對應關系，通過這個關系，仍能對矩陣的元素進行隨機存取。5.3.2稀疏矩陣什么是稀疏矩陣？簡單說，設矩陣A中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找

精確地說，設在的矩陣A中，有s個非零元素。令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認為e≦0.05時稱之為稀疏矩陣。在存儲稀疏矩陣時，為了節(jié)省存儲單元，很自然地想到使用壓縮存儲方法。但由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置（i,j)。反之，一個三元組(i,j,aij)唯一確定了矩陣A的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。精確地說，設在的矩陣A中，有s個非零元素。令e例如，下列三元組表((1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))

加上(6,7，8)這一對行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000圖5.4稀疏矩陣M和TM=T=例如，下列三元組表M=T=一、三元組順序表

假設以順序存儲結(jié)構來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法——三元順序表。#definemaxsize10000typedefintdatatype;typedefstruct{inti,j;datatypev;}triplet;

一、三元組順序表

typedefstruct{tripledata[maxsize];intm,n,t;}tripletable;設A為tripletable型的結(jié)構變量，圖5.4中所示的稀疏矩陣的三元組的表示如下：ijv121213931-3361443245218611564-7

typedefstruct{

下面以矩陣的轉(zhuǎn)置為例，說明在這種壓縮存儲結(jié)構上如何實現(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.data中i和j的內(nèi)容，那么得到的b.data將是一個按列優(yōu)先順序存儲的稀疏矩陣B，要得到按行優(yōu)先順序存儲的b.data，就必須重新排列三元組的順序。由于A的列是B的行，因此，按a.data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。下面以矩陣的轉(zhuǎn)置為例，說明在這種壓縮存儲結(jié)構上如6

7

8

121213931-3361443245218611564-7ijv012345678maijv7

6

8

13-3161521122518319342446-76314012345678mb?67812解決思路：只要做到

將矩陣行、列維數(shù)互換將每個三元組中的i和j相互調(diào)換重排三元組次序，使mb中元素以N的行(M的列)為主序方法一：按M的列序轉(zhuǎn)置即按mb中三元組次序依次在ma中找到相應的三元組進行轉(zhuǎn)置。為找到M中每一列所有非零元素，需對其三元組表ma從第一行起掃描一遍。由于ma中以M行序為主序,所以由此得到的恰是mb中應有的順序算法描述：P99算法5.1算法分析：T(n)=O(M的列數(shù)n非零元個數(shù)t)若t與mn同數(shù)量級，則解決思路：只要做到方法一：按M的列序轉(zhuǎn)置算法描述：P99算6

7

8

121213931-3361443245218611564-7ijv012345678ma7

6

8

13-3161521122518319342446-76314ijv012345678mbqppppppppqqqqppppppppcol=1col=267812方法二：快速轉(zhuǎn)置即按ma中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入b中恰當位置此法關鍵是要預先確定M中每一列第一個非零元在mb中位置，為確定這些位置，轉(zhuǎn)置前應先求得M的每一列中非零元個數(shù)實現(xiàn)：設兩個數(shù)組num[col]：表示矩陣M中第col列中非零元個數(shù)cpot[col]：指示M中第col列第一個非零元在mb中位置顯然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colma[0].j)1357889colnum[col]cpot[col]12223241506170方法二：快速轉(zhuǎn)置實現(xiàn)：設兩個數(shù)組cpot[1]=1;1357算法分析：T(n)=O(M的列數(shù)n+非零元個數(shù)t)若t與mn同數(shù)量級，則T(n)=O(mn)算法描述：P100算法5.2算法分析：T(n)=O(M的列數(shù)n+非零元個數(shù)t)算法描述：6

7

8

121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]1122323524715806817907

6

8

13-3161521122518319342446-76314pppppppp462975367812鏈式存儲結(jié)構帶行指針向量的單鏈表表示每行的非零元用一個單鏈表存放設置一個行指針數(shù)組，指向本行第一個非零元結(jié)點；若本行無非零元，則指針為空表頭結(jié)點與單鏈表結(jié)點類型定義typedefstructnode{intcol;intval;structnode*link;}JD;typedefstructnode*TD;^13573-11-12-242^^^^需存儲單元個數(shù)為3t+m鏈式存儲結(jié)構typedefstructnodety十字鏈表設行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個非零元結(jié)點定義tpedefstructnode{introw,col,val;structnode*down,*right;}JD;rowcolvaldownright113418225234^^^^^^^十字鏈表tpedefstructnoderowcolv5.4廣義表

廣義表的基本概念廣義表的鏈接存儲結(jié)構廣義表的基本運算廣義表的應用舉例5.4廣義表廣義表的基本概念一、基本概念廣義表是第二章提到的線性表的推廣。線性表中的元素僅限于原子項(單個數(shù)據(jù)元素)，即不可以再分，而廣義表中的元素既可以是原子項，也可以是子表(另一個線性表)。(如果ai是單個數(shù)據(jù)元素,則稱ai為廣義表的原子)1．廣義表的定義廣義表是n≥0個元素a0，a1，…，an-1的有限序列，其中每一個ai或者是原子，或者是一個子表。廣義表通常記為GL=(a0,a1,…,an-1)，其中GL為廣義表的名字，n為廣義表的長度，每一個ai為廣義表的元素。但在習慣中，一般用大寫字母表示廣義表，小寫字母表示原子。稱第一個元素a0為廣義表GL的表頭,其余部分(a1,...an-1)為GL的表尾,分別記作head(GL)=a0和tail(GL)=(a1,...an-1)一、基本概念1．廣義表的定義廣義表是n≥0個元素a0，a1，說明:1.廣義表是線性表的一種推廣。2.廣義表的定義是遞歸的。因為在描述廣義表的時候又用到了廣義表的概念.3.廣義表是多層次結(jié)構。4.一個廣義表可以為其它廣義表所共享。說明:2．廣義表舉例(1)A=(),A為空表，長度為0。(2)B=(a,（b,c)),B是長度為2的廣義表，第一項為原子，第二項為子表。(3)C=(x,y,z)C是長度為3的廣義表，每一項都是原子。D=(B,C)，D是長度為2的廣義表，每一項都是上面提到的子表。E=(a,E)是長度為2的廣義表，第一項為原子，第二項為它本身。

2．廣義表舉例(1)A=(),3．廣義表的深度一個廣義表的深度是指該廣義表展開后所含括號的層數(shù)。例如，A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為3。3．廣義表的深度一個廣義表的深度是指該廣義表展開后所含括號4．取表頭運算head若廣義表LS=(a1，a2，…，an)，則head(LS)=a1。取表頭運算得到的結(jié)果可以是原子，也可以是一個子表。例如，head((a1,a2,a3,a4))=a1，head(((a1,a2),(a3,a4),a5))=(a1,a2)。5．取表尾運算tail若廣義表LS=(a1，a2，…，an)，則tail(LS)=(a2，a3，…，an)。即取表尾運算得到的結(jié)果是除表頭以外的所有元素，取表尾運算得到的結(jié)果一定是一個子表。值得注意的是廣義表()和(())是不同的，前者為空表，長度為0，后者的長度為1，可得到表頭、表尾均為空表，即head((()))=()，tail((()))=()。4．取表頭運算head若廣義表LS=(a1，a2，…，an1.GetTail【(b,k,p,h)】＝

;2.GetHead【((a,b),(c,d))】＝

;3.GetTail【((a,b),(c,d))】＝

;4.GetTail【GetHead【((a,b),(c,d))】】＝

;例：求下列廣義表操作的結(jié)果（嚴題集5.10②）(k,p,h)（b）(a,b)5.GetTail【（e）】＝

;6.GetHead【(())】＝

.7.GetTail【(())】＝

.()(a,b)()()((c,d))1.GetTail【(b,k,p,h)】＝二、

廣義表的鏈接存儲結(jié)構由于廣義表的元素類型不一定相同，因此，難以用順序結(jié)構存儲表中元素，通常采用鏈接存儲方法來存儲廣義表中元素，并稱之為廣義鏈表。1、結(jié)點結(jié)構形式是：tag為標志字段，若tag=0表示該結(jié)點為原子結(jié)點，第二個域data存放相應原子元素的信息。若tag=1為子表結(jié)點,第二個域為sublist存放相應子表第一個元素對應的結(jié)點的地址。link存放本元素同一層的下一個元素所在鏈結(jié)點的地址。二、廣義表的鏈接存儲結(jié)構1、結(jié)點結(jié)構形式是：tag為標志字用C語言描述結(jié)點的類型如下：typedefstructnode{inttag;union{structnode*sublist;chardata;}dd;structnode*link;}NODE;用C語言描述結(jié)點的類型如下：2、結(jié)點的鏈接(1)一般的鏈接方法廣義表的每個元素有一個結(jié)點表示，同一層每個結(jié)點按其在表中的次序用link指針鏈接起來，每個表結(jié)點的sublist指向子表的第一個元素對應的結(jié)點。(2)帶附加表頭鏈接方法在每個廣義表的表頭結(jié)點之前增加一個表結(jié)點。相對于一般的鏈接方法，這種鏈接方法在進行元素的插入、刪除和表的共享等處理時會顯得更為方便。2、結(jié)點的鏈接0a0b0c^BA=NULL0a1^C11^1^0a^1^1^DE一般的廣義表鏈接存儲結(jié)構0a0b0c^BA=NULL00a0b0c^BA0a1^C11^1^0a^1^1^DE1^^1^1^1^1^0a0b0c^BA0a1三、

基本運算廣義表有許多運算，其基本運算有：建立廣義表、打印廣義表、求一個子表或元素、查找、插入、刪除、復制、求長度、求深度等。由于廣義表是一種遞歸的數(shù)據(jù)結(jié)構，所以實現(xiàn)廣義表的運算一般采用遞歸算法。1、廣義表的建立creat_GL(s)假設廣義表以單鏈表的形式存儲，廣義表的元素類型elemtype為字符型char，廣義表GL由鍵盤輸入，假定全部為字母，輸入格式為：元素之間用逗號分隔，表元素的起止符號分別為左、右圓括號。函數(shù)creat_GL(s)根據(jù)廣義表表達式字符串，建立相應帶附加表頭結(jié)點的鏈接存儲廣義表，并返回表頭指針。三、基本運算1、廣義表的建立creat_GL(s)NODE*creat_GL(char**s){ NODE*h; charch; ch=*(*s); (*s)++; if(ch!='\0') { h=(NODE*)malloc(sizeof(NODE)); if(ch=='(') { h->tag=1; h->dd.sublist=creat_GL(s); } else { h->tag=0; h->dd.data=ch; } }

NODE*creat_GL(char**s)else h=NULL; ch=*(*s); (*s)++; if(h!=NULL) if(ch==',') h->link=creat_GL(s); else h->link=NULL; return(h);}該算法的時間復雜度為O(n)。else2.輸出廣義表prn_GL(p)對于廣義表的表頭結(jié)點p，若為表結(jié)點，輸出空表或遞歸輸出子表的內(nèi)容，否則，輸出元素值；若當前的結(jié)點還有后續(xù)結(jié)點，則遞歸輸出后續(xù)表的內(nèi)容。下面的函數(shù)把按鏈接存儲的廣義表以字符串形式輸出。voidprn_GL(NODE*p){ if(p!=NULL) { if(p->tag==1) { printf("("); if(p->dd.sublist==NULL) printf("");2.輸出廣義表prn_GL(p)voidprn_GL(NOelse prn_GL(p->dd.sublist); } else printf("%c",p->dd.data); if(p->tag==1) printf(")"); if(p->link!=NULL) { printf(","); prn_GL(p->link); } }}該算法的時間復雜度為O(n)。else3.廣義表的復制對于廣義表的頭結(jié)點p，若為空，返回空指針；若為表結(jié)點，遞歸復制子表；否則，復制原子結(jié)點；然后遞歸復制后續(xù)表。NODE*copy_GL(NODE*p){ NODE*q; if(p==NULL)return(NULL); q=(NODE*)malloc(sizeof(NODE)); q->tag=p->tag; if(p->tag) q->dd.sublist=copy_GL(p->dd.sublist);else q->dd.data=p->dd.data; q->link=copy_GL(p->link); return(q);}3.廣義表的復制NODE*copy_GL(NODE*p)四、幾個運算的調(diào)用下列主函數(shù)的功能是:創(chuàng)建帶表頭結(jié)點鏈式存儲的廣義表然后復制一個新的廣義表,并把廣義表按字符串的方式輸出.main(){ NODE*hd,*hc; chars[100],*p; p=gets(s); hd=creat_GL(&p); hc=copy_GL(hd); printf("copyafter:"); prn_GL(hc);}四、幾個運算的調(diào)用求廣義表深度求廣義表原子結(jié)點個數(shù)求廣義表原子結(jié)點數(shù)據(jù)域之和求廣義表深度深度公式:maxdh(p)=0p->tag=1maxdh(p)=1空表(p->tag=1&&p->dd.sublist=NULL)maxdh(p)=max(maxdh(p1),...,maxdh(pn))+1其余情況p=(p1,p2,...,pn)深度公式:maxdh(p)=0p->tag=1intdepth(NODE*p)/*求表的深度函數(shù)*/{inth,maxdh;NODE*q;if(p->tag==0)return(0);else if(p->tag==1&&p->dd.sublist==NULL)return1; else { maxdh=0; while(p!=NULL) { if(p->tag==0)h=0; else {q=p->dd.sublist; h=depth(q); }intdepth(NODE*p)/*求表的深度函數(shù)if(h>maxdh)maxdh=h; p=p->link; } return(maxdh+1); }}if(h>maxdh)maxdh=h;原子結(jié)點個數(shù)公式:(f(p)=0p=NULLf(p)=1+f(p->link)p->tag=0f(p)=f(p->dd.sublist)+f(p->link)

p->tag=1原子結(jié)點個數(shù)公式:(f(p)=0p=NULLintcount(NODE*p)/*求原子結(jié)點的個數(shù)函數(shù)*/{ intm,n; if(p==NULL)return(0); else { if(p->tag==0)n=1; else n=count(p->dd.sublist); if(p->link!=NULL) m=count(p->link); elsem=0; return(n+m); }}intcount(NODE*p)/*求原子結(jié)點的個原子結(jié)點數(shù)據(jù)域之和公式:(f(p)=0p=NULLf(p)=p->data+f(p->link)p->tag=0f(p)=f(p->dd.sublist)+f(p->link)

p->tag=1原子結(jié)點數(shù)據(jù)域之和公式:(f(p)=0p=NULintsum(NODE*p)/*求原子結(jié)點數(shù)據(jù)域之和函數(shù)*/{ intm,n; if(p==NULL)return(0); else { if(p->tag==0)n=p->dd.data-’0’; else n=sum(p->dd.sublist); if(p->link!=NULL) m=sum(p->link); elsem=0; return(n+m); }}intsum(NODE*p)/*求原子結(jié)點數(shù)據(jù)域之一、教學內(nèi)容：

1、 數(shù)組的定義和順序存儲方式；

2、 特殊矩陣的壓縮存儲；

3、 稀疏矩陣

4、 廣義表的概念、表示及基本操作；廣義表存儲結(jié)構的實現(xiàn)。

二、教學要求：

1、 了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構中的地址計算方法；

2、 掌握對特殊矩陣進行壓縮存儲時的下標變換公式；

3、 了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍，理解以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法；

4、 掌握廣義表的結(jié)構特點及其存儲表示方法，會對非空廣義表進行分解。

第五章數(shù)組和廣義表一、教學內(nèi)容：

1、 數(shù)組的定義和順序存儲方式；

2、 特殊第五章數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲5.3.1特殊矩陣5.3.2稀疏矩陣5.4廣義表的定義5.5廣義表的存儲結(jié)構第五章數(shù)組和廣義表5.1數(shù)組的定

數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的數(shù)據(jù)元素本身也是一種線性表。

5.1數(shù)組的定義由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標一般具有固定的上界和下界，因此，數(shù)組的處理比其它復雜的結(jié)構更為簡單。多維數(shù)組是向量的推廣。例如，二維數(shù)組：

()()()()()()()()()數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表

可以看成是由一個行向量組成的向量，也可以看成是由一個列向量組成的向量。在C語言中，一個二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說，typedefelemtypearray2[m][n];等價于：typedefelemtypearray1[n];typedefarray1array2[m];數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。可以看成是由一個行向量組成的向量，也可以看成是由一個

5.2數(shù)組的順序表示和實現(xiàn)

由于計算機的內(nèi)存結(jié)構是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。又由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構中的元素個數(shù)和元素間的關系就不再發(fā)生變化。因此，一般都是采用順序存儲的方法來表示數(shù)組。

5.2數(shù)組的順序表示和實現(xiàn)通常有兩種順序存儲方式：以行序為主序以列序為主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序為主序存放amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n

按列序為主序存放01m-1m*n-1mamn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

通常有兩種順序存儲方式：a11計算二維數(shù)組元素地址的通式

設一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是0。無論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時求出任一元素的地址（這樣數(shù)組中的任一元素便可以隨機存?。。憾S數(shù)組列優(yōu)先存儲的通式為：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

Amn=單個元素長度aij之前的行數(shù)數(shù)組基址總列數(shù)，即第2維長度aij本行前面的元素個數(shù)①開始結(jié)點的存放地址（即基地址）②維數(shù)和每維的上、下界；③每個數(shù)組元素所占用的單元數(shù)則行優(yōu)先存儲時的地址公式為：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L計算二維數(shù)組元素地址的通式

設一般的二維數(shù)組是A[c1..d例2：已知二維數(shù)組Am,m按行存儲的元素地址公式是：

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,按列存儲的公式是？Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K（盡管是方陣，但公式仍不同）例1〖軟考題〗：一個二維數(shù)組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是

個字節(jié)。288例3：〖00年某?？佳蓄}〗設數(shù)組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為

。8950LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝8950答：請注意審題！利用列優(yōu)先通式：答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例2：已知二維數(shù)組Am,m按行存儲的元素地址公式是：

Lo5.3矩陣的壓縮存儲

在科學與工程計算問題中，矩陣是一種常用的數(shù)學對象，在高級語言編制程序時，簡單而又自然的方法，就是將一個矩陣描述為一個二維數(shù)組。矩陣在這種存儲表示之下，可以對其元素進行隨機存取，各種矩陣運算也非常簡單，并且存儲的密度為1。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來存儲密度仍為1，但實際上占用了許多單元去存儲重復的非零元素或零元素，這對高階矩陣會造成極大的浪費，為了節(jié)省存儲空間，我們可以對這類矩陣進行壓縮存儲：即為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。5.3矩陣的壓縮存儲5.3.1特殊矩陣

所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲。1、對稱矩陣在一個n階方陣A中，若元素滿足下述性質(zhì)：aij=aji0≦i,j≦n-1則稱A為對稱矩陣。如圖5.1便是一個5階對稱矩陣。對稱矩陣中的元素關于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，這樣，能節(jié)約近一半的存儲空間。不失一般性，我們按“行優(yōu)先5.3.1特殊矩陣順序”存儲主對角線（包括對角線）以下的元素，其存儲形式如圖所示：

15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1圖5.1對稱矩陣

在這個下三角矩陣中，第i行恰有i+1個元素，元素總數(shù)為：n(n+1)/2因此，我們可以按從上到下、從左到右將這些元素存放在一個向量sa[0..n(n+1)/2-1]中。為了便于訪問對稱矩陣A中的元素，我們必須在aij和sa[k]

順序”存儲主對角線（包括對角線）以下的元素，其存儲形式如圖所之間找一個對應關系。若i≧j，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）一共有1+2+…+i=i(i+1)/2個元素，在第i行上，aij之前恰有j個元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j0≦k<n(n+1)/2若i<j，則aij是在上三角矩陣中。因為aij=aji，所以只要交換上述對應關系式中的i和j即可得到：k=j*(j+1)/2+i0≦k<n(n+1)/2

之間找一個對應關系。2、三角矩陣以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…..……………..cc…an-1n-1an-10an-11…an-1n-1

(a)上三角矩陣(b)下三角矩陣

2、三角矩陣

三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個分量中，上三角矩陣中，主對角線之上的第i行(0≦i<n)恰有n-i個元素，按行優(yōu)先順序存放上三角矩陣中的元素aij時，aij之前的i行一共有i(2n-i+1)/2個元素，在第i行上，aij前恰好有j-i個元素：aii,aii+1,…aij-1。因此，sa[k]和aij的對應關系是：

k=i(2n-i+1)/2+j-i當i≦jn(n+1)/2當i>j三角矩陣中的重復元素c可共享一個存儲空間，其余的元

下三角矩陣的存儲和對稱矩陣類似，sa[k]和aij對應關系是：i(i+1)/2+ji≧jn(n+1)/2i<j3、對角矩陣對角矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。下圖給出了一個三對角矩陣，

a00a01a10a11a12a21a22a23….…..….圖5.3對角矩陣an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1k=下三角矩陣的存儲和對稱矩陣類似，sa[k]和aij對應關非零元素僅出現(xiàn)在主對角(aii,0≦i≦n-1上，緊鄰主對角線上面的那條對角線上(aii+1,0≦i≦n-2)和緊鄰主對角線下面的那條對角線上(ai+1i,0≦i≦n-2)。顯然，當∣i-j∣>1時，元素aij=0。由此可知，一個k對角矩陣(k為奇數(shù))A是滿足下述條件的矩陣：若∣i-j∣>(k-1)/2，則元素aij=0。對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標的對應關系。

非零元素僅出現(xiàn)在主對角(aii,0≦i≦n-1上，緊鄰主對角

在三對角矩陣里除滿足條件i=0，j=0、1，或i=n-1j=n-2、n-1或1<i<n-1,j=i-1、i、i+1的元素aij外，其余元素都是零。對這種矩陣，我們也可按行優(yōu)序為主序來存儲。除第0行和第n-1行是2個元素外，每行的非零元素都要是3個，因此，需存儲的元素個數(shù)為3n-2。a00a01

a10a11a12a21

……an-1n-2an-1n-1K=012345……3n-23n-1

數(shù)組sa中的元素sa[k]與三對角帶狀矩陣中的元素aij存在一一對應關系，在aij之前有i行,共有3*i-1個非零元素，在第i行，有j-i+1個非零元素，這樣，非零元素aij的地址為：在三對角矩陣里除滿足條件i=0，j=0、1，或i=n-1

LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d=LOC(0,0)+(2i+j)*d

上例中，a34對應著sa[10]。k=2*i+j=2*3+4=10a21對應著sa[5]k=2*2+1=5由此，我們稱sa[0..3*n-3]是階三對角帶狀矩陣A的壓縮存儲表示。LOC(i,j)=LOC(0,0)+[3*i-1+(j-i上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲到一個向量中，并且一般都能找到矩陣中的元素與該向量的對應關系，通過這個關系，仍能對矩陣的元素進行隨機存取。5.3.2稀疏矩陣什么是稀疏矩陣？簡單說，設矩陣A中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找

精確地說，設在的矩陣A中，有s個非零元素。令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認為e≦0.05時稱之為稀疏矩陣。在存儲稀疏矩陣時，為了節(jié)省存儲單元，很自然地想到使用壓縮存儲方法。但由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置（i,j)。反之，一個三元組(i,j,aij)唯一確定了矩陣A的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。精確地說，設在的矩陣A中，有s個非零元素。令e例如，下列三元組表((1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))

加上(6,7，8)這一對行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000圖5.4稀疏矩陣M和TM=T=例如，下列三元組表M=T=一、三元組順序表

假設以順序存儲結(jié)構來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法——三元順序表。#definemaxsize10000typedefintdatatype;typedefstruct{inti,j;datatypev;}triplet;

一、三元組順序表

typedefstruct{tripledata[maxsize];intm,n,t;}tripletable;設A為tripletable型的結(jié)構變量，圖5.4中所示的稀疏矩陣的三元組的表示如下：ijv121213931-3361443245218611564-7

typedefstruct{

下面以矩陣的轉(zhuǎn)置為例，說明在這種壓縮存儲結(jié)構上如何實現(xiàn)矩陣的運算。一個m×n的矩陣A，它的轉(zhuǎn)置B是一個n×m的矩陣，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n，即A的行是B