數(shù)據(jù)結(jié)構(gòu)chapter5數(shù)組和廣義表

1、第第5 5章章 數(shù)組數(shù)組(Arrays)(Arrays)和廣義表和廣義表(Lists)(Lists)5.1 5.1 數(shù)組的定義和運算數(shù)組的定義和運算 5.2 5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲 5.4 5.4 廣義表的定義廣義表的定義5.5 5.5 廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu) 數(shù)組是我們很熟悉的一種數(shù)據(jù)類型，很多高級語言都支持數(shù)組是我們很熟悉的一種數(shù)據(jù)類型，很多高級語言都支持這種數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上看，數(shù)組可以看作一般線性表的這種數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上看，數(shù)組可以看作一般線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)，其特點是結(jié)構(gòu)中的元素本

2、身可推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)，其特點是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個線性表，二維數(shù)組可以看作數(shù)組可以看作一個線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一數(shù)據(jù)元素是一維數(shù)組維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)數(shù)據(jù)元素是二維數(shù)組組”的一維數(shù)組，依次類推。的一維數(shù)組，依次類推。第第5 5章章 數(shù)組數(shù)組(Arrays)(Arrays)和廣義表和廣義表(Lists)(Lists)3以二維數(shù)組為例討論。將二維數(shù)組看成是一個定長的線以二維數(shù)組為例討論。將二

3、維數(shù)組看成是一個定長的線性表性表，其每個元素又是一個定長的線性表。其每個元素又是一個定長的線性表。 設(shè)二維數(shù)組設(shè)二維數(shù)組A=(aij)m n，則則 A=(1，2，p) (p=m或或n)其中每個數(shù)據(jù)元素其中每個數(shù)據(jù)元素j是一個列向量是一個列向量(線性表線性表) ： j =(a1j ，a2j ，amj) 1jn或或是一個行向量是一個行向量： i =(ai1 ，ai2 ，ain) 1im如圖如圖5.1所示。所示。4 a00 a01 a0n-1 a10 a11 a1n-1 am-10 am-11 am-1n-1A= A=a00 a01 a0n-1a10 a11 a1n-1am-10 am-11 am-

4、1n-1a00a10 am-10a01 a11 am-11a0n-1 a1n-1 am-1n-1A=圖圖5.1 二維數(shù)組圖二維數(shù)組圖例例(a) 矩陣矩陣表示形式表示形式(b) 行向量的一維數(shù)組形式行向量的一維數(shù)組形式(c)列向量的一維數(shù)組形式列向量的一維數(shù)組形式5.15.1數(shù)組的定義和運算數(shù)組的定義和運算 許多高級語言中都有數(shù)組類型，下面結(jié)合我們熟知的二維數(shù)組，來討許多高級語言中都有數(shù)組類型，下面結(jié)合我們熟知的二維數(shù)組，來討論論n維數(shù)組的概念和特點：維數(shù)組的概念和特點： 數(shù)組是由數(shù)組是由同類型同類型的數(shù)據(jù)元素的數(shù)據(jù)元素 aj1j2jn 組成。組成。 在在n維數(shù)組中，共有維數(shù)組中，共有 b1b2

5、bn 個數(shù)據(jù)元素。個數(shù)據(jù)元素。 數(shù)組一旦定義，它的維數(shù)和維界就不再改變。數(shù)組一旦定義，它的維數(shù)和維界就不再改變。 特別地，當特別地，當n=1時，時，n維數(shù)組即為一維數(shù)組，一維數(shù)組可認為是定長維數(shù)組即為一維數(shù)組，一維數(shù)組可認為是定長的線性表。的線性表。 正如正如二維數(shù)組可以看作是以一維數(shù)組為元素構(gòu)成的一維數(shù)組，二維數(shù)組可以看作是以一維數(shù)組為元素構(gòu)成的一維數(shù)組， n維數(shù)維數(shù)組可以看作是以組可以看作是以n-1維數(shù)組為元素構(gòu)成的一維數(shù)組。維數(shù)組為元素構(gòu)成的一維數(shù)組。 這樣一來，這樣一來，n維數(shù)組看起來很像一個線性表。但由于每個元素又是一維數(shù)組看起來很像一個線性表。但由于每個元素又是一個個n-1維數(shù)組，

6、維數(shù)組，因此，因此，n維數(shù)組被認為是擴展的線性表。維數(shù)組被認為是擴展的線性表。 在前幾章討論的線性結(jié)構(gòu)中，數(shù)據(jù)元素作為一個不再分解的整體出現(xiàn)在前幾章討論的線性結(jié)構(gòu)中，數(shù)據(jù)元素作為一個不再分解的整體出現(xiàn)在各種基本操作中。但是，在有些數(shù)據(jù)結(jié)構(gòu)中，其數(shù)據(jù)元素本身又是一個在各種基本操作中。但是，在有些數(shù)據(jù)結(jié)構(gòu)中，其數(shù)據(jù)元素本身又是一個數(shù)據(jù)結(jié)構(gòu)，下面要介紹的數(shù)組和廣義表就是這樣的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)，下面要介紹的數(shù)組和廣義表就是這樣的數(shù)據(jù)結(jié)構(gòu)。 每個數(shù)據(jù)元素對應于一組下標（每個數(shù)據(jù)元素對應于一組下標（j1，j2，jn），其中），其中 n稱為數(shù)組稱為數(shù)組的的維數(shù)維數(shù)，ji的取值范圍是的取值范圍是0jibi-

7、1 bi稱為數(shù)組第稱為數(shù)組第i維的維的長度長度/維界維界第5章 數(shù)組(Arrays)和廣義表(Lists)二維數(shù)組的抽象數(shù)據(jù)類型二維數(shù)組的抽象數(shù)據(jù)類型 P90用抽象數(shù)據(jù)類型用抽象數(shù)據(jù)類型 Array 描述了描述了n維數(shù)組及其基本操作。維數(shù)組及其基本操作。 為便于為便于理解起見，這里給出二維數(shù)組的抽象數(shù)據(jù)類型理解起見，這里給出二維數(shù)組的抽象數(shù)據(jù)類型 。ADT Array 數(shù)據(jù)對象：數(shù)據(jù)對象：D=aij|aijElemSet，b11，b210ib1-1，0jb2-1 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R=R1,R2R1=|0i b1-2，0jb2-1R2=|0i b1-1，0jb2-2 基本操作：基本操作： I

8、nitArray(&A, n, bound1, , boundn) 操作結(jié)果：若維數(shù)和各維維界合法，則構(gòu)造數(shù)組操作結(jié)果：若維數(shù)和各維維界合法，則構(gòu)造數(shù)組A。 ADT Array因此，在因此，在n維數(shù)組中，每一維上都有維數(shù)組中，每一維上都有一個關(guān)系，每個數(shù)據(jù)元素都受到一個關(guān)系，每個數(shù)據(jù)元素都受到n個個關(guān)系的約束。關(guān)系的約束。 數(shù)組的基本操作數(shù)組的基本操作 InitArray(&A, n, bound1, ,boundn)操作結(jié)果：若維數(shù)操作結(jié)果：若維數(shù)n和各維維界合法，構(gòu)造相應的數(shù)組和各維維界合法，構(gòu)造相應的數(shù)組A.1.1.初始化操作初始化操作 DestroyArray(&

9、;A)操作結(jié)果：銷毀數(shù)組操作結(jié)果：銷毀數(shù)組A。2.2.銷毀操作銷毀操作 Value(A, &e, index1, ,indexn)初始條件：若數(shù)組初始條件：若數(shù)組A已存在。已存在。操作結(jié)果：用操作結(jié)果：用e返回下標為（返回下標為（index1, ,indexn）的）的元素的值。元素的值。3.3.取值操作取值操作 Assign(A, e, index1, ,indexn)初始條件：若數(shù)組初始條件：若數(shù)組A已存在。已存在。操作結(jié)果：把操作結(jié)果：把e賦值給下標為（賦值給下標為（index1, ,indexn）的元素。的元素。4.4.賦值操作賦值操作5.1 數(shù)組的定義和運算數(shù)組的定義和運算可以

10、看出，除了初始化和銷毀操作外，數(shù)組僅有取值操作可以看出，除了初始化和銷毀操作外，數(shù)組僅有取值操作和賦值操作。由于沒有插入和賦值操作。由于沒有插入/刪除操作，所以一旦建立了數(shù)組，刪除操作，所以一旦建立了數(shù)組，數(shù)組中的元素個數(shù)以及元素之間的關(guān)系不再發(fā)生變化。因此，數(shù)組中的元素個數(shù)以及元素之間的關(guān)系不再發(fā)生變化。因此，數(shù)組適宜用順序存儲結(jié)構(gòu)來表示。數(shù)組適宜用順序存儲結(jié)構(gòu)來表示。 0 1 2 35.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn) 對于數(shù)組對于數(shù)組A，一旦規(guī)定了它的維數(shù)和各維的維界，也就知，一旦規(guī)定了它的維數(shù)和各維的維界，也就知道了元素的個數(shù)，可以為它分配地址連續(xù)的存儲區(qū)域。道了元素的個數(shù)

11、，可以為它分配地址連續(xù)的存儲區(qū)域。 但是，由于存儲區(qū)域是一維的，而數(shù)組是多維的，于是，但是，由于存儲區(qū)域是一維的，而數(shù)組是多維的，于是，用順序存儲方案來存儲數(shù)組的元素就有一個用順序存儲方案來存儲數(shù)組的元素就有一個次序約定問題次序約定問題。即。即必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放到內(nèi)存中。列存放到內(nèi)存中。 低下標優(yōu)先低下標優(yōu)先 (以行序為主序以行序為主序)高下標優(yōu)先高下標優(yōu)先 (以列序為主序以列序為主序) 常用的次序有兩種常用的次序有兩種一、低下標優(yōu)先一、低下標優(yōu)先 ( (以行序為主序以行序為主序) ) 5.2 數(shù)組

12、的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)a00a01a02a03a10a11a12a13a20a21a22a2301234567891011a00a01a02a03a10a11a12a13a20a21a22a23b0 xxb1xxb2xxb3xx1. a342. b434b00 xb01xb02xb000b001b002b003b023b022b021b020b013b012b011b010b003b002b001b000ijk二、高下標優(yōu)先二、高下標優(yōu)先 ( (以列序為主序以列序為主序) ) 5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)a00a01a02a03a10a11a12a13a20a

13、21a22a2301234567891011bxx0bxx1bxx2bxx31. a342. b434bx00bx10bx20b000b100b200b300a00a10a20a01a11a21a02a12a22a03a13a23b023b022b021b020b013b012b011b010b003b002b001b000ijk 今后除非特別聲明，將按今后除非特別聲明，將按低下標優(yōu)先次序低下標優(yōu)先次序 ( (以行序為主序以行序為主序) ) 來存儲數(shù)來存儲數(shù)組元素。這樣一來，二維數(shù)組組元素。這樣一來，二維數(shù)組abab1 1bb2 2 的存儲映像如下圖所示。的存儲映像如下圖所示。 如果用如果用L

14、OC(j1,j2) 表示表示aj1j2的存儲位置，則的存儲位置，則LOC(0,0)表示表示a00的存儲位置，它恰是數(shù)組存儲區(qū)域的基地址。的存儲位置，它恰是數(shù)組存儲區(qū)域的基地址。 假設(shè)每個數(shù)組元素占假設(shè)每個數(shù)組元素占L個字節(jié)，則個字節(jié)，則aj1j2的存儲位置的存儲位置LOC(j1，j2)= LOC(0，0) (j1b2+j2) L = LOC(0，0)j1b2L j2 La00 a0b2-1aj10 aj1b2-1 ab1-10 ab1-1b2-1第第0行行第第j1行行第第b1-1行行LOC(0,0)aj10aj11 aj1j2-1aj1j2 aj1b2-15.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序

15、表示和實現(xiàn) 推廣到推廣到n n維數(shù)組，如果用維數(shù)組，如果用LOC(jLOC(j1 1,j,j2 2,j jn n) )表示元素表示元素a aj j1 1j j2 2j jn n的存儲位置，則不難推得的存儲位置，則不難推得: :LOC(j1,j2,jn)= LOC(0,0,0)j1b2b3bnL j2 b3bnL jn-1 bnL jn L 若令若令cn=Lci-1=bici (1in)則則LOC(j1,j2,jn)= LOC(0,0,0) niiijc1此公式稱為此公式稱為n維數(shù)組的映象函數(shù)維數(shù)組的映象函數(shù)。請注意：。請注意： ji的取值范圍是的取值范圍是0jibi1； ci是利用各維維界是利

16、用各維維界bi計算出的常數(shù)。計算出的常數(shù)。 5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn) 由映像函數(shù)可以看出，由映像函數(shù)可以看出，數(shù)組元素的存儲位置是其下標的數(shù)組元素的存儲位置是其下標的線性函數(shù)線性函數(shù)。 另外，對于任一數(shù)組元素另外，對于任一數(shù)組元素 aj1j2jn，利用該函數(shù)容易計算，利用該函數(shù)容易計算其存儲位置，進而存取該元素，而且存取不同元素所花費的其存儲位置，進而存取該元素，而且存取不同元素所花費的時間相同。因此，時間相同。因此，n維數(shù)組的順序存儲結(jié)構(gòu)具有維數(shù)組的順序存儲結(jié)構(gòu)具有隨機存取隨機存取的特的特點點。 5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)LOC(j1,j2,jn

17、)= LOC(0,0,0)niiijc15.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn) 我們用如下的數(shù)據(jù)類型來描述我們用如下的數(shù)據(jù)類型來描述n維數(shù)組的順序存儲結(jié)構(gòu)。維數(shù)組的順序存儲結(jié)構(gòu)。#define MAX_ARRAY_DIM8 /數(shù)組維數(shù)的最大值數(shù)組維數(shù)的最大值typedef structElemType *base;/數(shù)組基地址數(shù)組基地址int dim;/數(shù)組維數(shù)數(shù)組維數(shù)int *bounds;/數(shù)組維界的基地址數(shù)組維界的基地址int *constants;/數(shù)組映象函數(shù)中常數(shù)的基地址數(shù)組映象函數(shù)中常數(shù)的基地址Array; Aconstantsboundsdimbasecnc1bnb1

18、a01a005.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn) 在結(jié)束數(shù)組的討論之前，可能有人會問，我們用的高級在結(jié)束數(shù)組的討論之前，可能有人會問，我們用的高級語言中幾乎都有現(xiàn)成的數(shù)組類型可供使用，我們?yōu)槭裁催€在語言中幾乎都有現(xiàn)成的數(shù)組類型可供使用，我們?yōu)槭裁催€在這兒討論數(shù)組的表示與實現(xiàn)呢這兒討論數(shù)組的表示與實現(xiàn)呢? 原因在于我們不僅要知道如何使用數(shù)組，還要懂得數(shù)組原因在于我們不僅要知道如何使用數(shù)組，還要懂得數(shù)組結(jié)構(gòu)的實現(xiàn)原理。這樣一來，當你在設(shè)計一種新的程序設(shè)計結(jié)構(gòu)的實現(xiàn)原理。這樣一來，當你在設(shè)計一種新的程序設(shè)計語言時，你也能設(shè)計出數(shù)組類型供程序員使用。語言時，你也能設(shè)計出數(shù)組類型供程序員使用

19、。 165.3 矩陣的壓縮存儲矩陣的壓縮存儲 在科學與工程計算問題中，矩陣是一種常用的數(shù)學對在科學與工程計算問題中，矩陣是一種常用的數(shù)學對象，在高級語言編程時，通常將一個矩陣描述為一個二維象，在高級語言編程時，通常將一個矩陣描述為一個二維數(shù)組。這樣，可以對其元素進行隨機存取，各種矩陣運算數(shù)組。這樣，可以對其元素進行隨機存取，各種矩陣運算也非常簡單。也非常簡單。 對于高階矩陣，若其中非零元素呈某種規(guī)律分布或者對于高階矩陣，若其中非零元素呈某種規(guī)律分布或者矩陣中有大量的零元素，若仍然用常規(guī)方法存儲，可能存矩陣中有大量的零元素，若仍然用常規(guī)方法存儲，可能存儲重復的非零元素或零元素，將造成存儲空間的大

20、量浪費儲重復的非零元素或零元素，將造成存儲空間的大量浪費。對這類矩陣進行壓縮存儲：。對這類矩陣進行壓縮存儲： 多個相同的非零元素只分配一個存儲空間多個相同的非零元素只分配一個存儲空間； 零元素不分配空間。零元素不分配空間。175.3.1 特殊矩陣特殊矩陣特殊矩陣特殊矩陣：是指非零元素或零元素的分布有一定規(guī)律是指非零元素或零元素的分布有一定規(guī)律的矩陣。的矩陣。1 對稱矩陣對稱矩陣 若一個若一個n階方陣階方陣A=(aij)n n中的元素滿足性質(zhì)：中的元素滿足性質(zhì)：aij=aji 1i,jn且且ij則稱則稱A為對稱矩陣，如圖為對稱矩陣，如圖5.3所示。所示。圖圖5.3 對稱矩陣示例對稱矩陣示例1 5

21、 1 3 73 0 2 5 17 0 6 1 35 0 8 0 01 8 9 2 6A= a11 a21 a22 a31 a32 a33 an1 an2 annA=18 對稱矩陣中的對稱矩陣中的元素關(guān)于主對角線對稱元素關(guān)于主對角線對稱，因此，讓，因此，讓每一對對稱元素每一對對稱元素aij和和aji(ij)分配一個存儲空間，則分配一個存儲空間，則n2個個元素壓縮存儲到元素壓縮存儲到n(n+1)/2個存儲空間，能節(jié)約近一半的個存儲空間，能節(jié)約近一半的存儲空間。存儲空間。 不失一般性，假設(shè)按不失一般性，假設(shè)按“行優(yōu)先順序行優(yōu)先順序”存儲下三角存儲下三角形形( (包括對角線包括對角線) )中的元素。中

22、的元素。 設(shè)用一維數(shù)組設(shè)用一維數(shù)組( (向量向量) )san(n+1)/2存儲存儲n階對稱矩階對稱矩陣，如圖陣，如圖5.4所所示。為了便于訪問，必須找出矩陣示。為了便于訪問，必須找出矩陣A中中的元素的下標值的元素的下標值（i,j）和向量和向量sak的的下標值下標值k之間的對之間的對應關(guān)系。應關(guān)系。sa a11 a21 a22 a31 a32 a33 an1 an2 annK 1 2 3 4 n(n-1)/2 n(n+1)/2圖圖5.4 對稱矩陣的對稱矩陣的壓縮存儲示例壓縮存儲示例19 若若ij：ai j在下三角形中，直接保存在在下三角形中，直接保存在sa中。中。ai j之之前的前的i-1行共有

23、元素個數(shù)：行共有元素個數(shù)： 1+2+(i-1)=i (i-1)/2而在第而在第i行上，行上，ai j之前恰有之前恰有j-1個元素個元素，因此因此，元素元素ai j保保存存在向量在向量sa中時的中時的下標值下標值k之間的對應關(guān)系之間的對應關(guān)系是：是： k=i (i-1)/2+j-1 ij 若若ij：則：則aij是在上三角矩陣中。因為是在上三角矩陣中。因為aij=aji，在向在向量量sa中保存的是中保存的是aji 。依上述分析可得：依上述分析可得： k=j (j-1)/2+i-1 ij 對稱矩陣元素對稱矩陣元素ai j保存保存在向量在向量sa中時的中時的下標值下標值k與與（i,j）之間的對應關(guān)系之

24、間的對應關(guān)系是：是： i (i-1)/2+j-1 當當ij時時j (j-1)/2+i-1 當當ij時時K=1i,j n (5-4)20 根據(jù)上述的下標對應關(guān)系，對于矩陣中的任意元根據(jù)上述的下標對應關(guān)系，對于矩陣中的任意元素素aij，均可在一維數(shù)組，均可在一維數(shù)組sa中唯一確定其位置中唯一確定其位置k；反之，反之，對所有對所有k=1,2, ,n(n+1)/2，都能確定都能確定sak中的元素在矩中的元素在矩陣中的位置陣中的位置(i,j)。 稱稱san(n+1)/2為為n階對稱矩陣階對稱矩陣A的的壓縮存儲壓縮存儲。2 三角矩陣三角矩陣 以主對角線劃分，三角矩陣有上三角和下三角兩以主對角線劃分，三角矩

25、陣有上三角和下三角兩種。種。 上三角矩陣的下三角（不包括主對角線）中的元上三角矩陣的下三角（不包括主對角線）中的元素均為常數(shù)素均為常數(shù)c或或0。下三角矩陣正好相反，它的主對角。下三角矩陣正好相反，它的主對角線上方均為常數(shù)，如圖線上方均為常數(shù)，如圖5.5所示。所示。21a11 a12 a1nc a22 a2nc c ann a11 c ca21 a22 can1 an2 ann 圖圖5.5 三角矩陣三角矩陣示例示例(b) 下下三角矩陣三角矩陣示例示例(a) 上上三角矩陣三角矩陣示例示例 三角矩陣中的重復元素三角矩陣中的重復元素c可共享一個存儲空間，其可共享一個存儲空間，其余的元素正好有余的元素正

26、好有n(n+1)/2個，因此，三角矩陣可壓縮存?zhèn)€，因此，三角矩陣可壓縮存儲到向量儲到向量san(n+1)/2+1中，其中中，其中c存放在向量的第存放在向量的第1個個分量中分量中。 22a11 a12 0 . 0a21 a22 a23 0 . 00 a32 a33 a34 0 . 0 . 0 . 0 0 an n-1 an n0 . 0 an-1 n-2 an-1 n-1 an-1 nA=圖圖5.6 三對角矩陣三對角矩陣示例示例對角矩陣可按對角矩陣可按行優(yōu)先順序行優(yōu)先順序或或?qū)蔷€順序?qū)蔷€順序，將其壓縮存儲到一個，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標的對應關(guān)系。向量中，

27、并且也能找到每個非零元素和向量下標的對應關(guān)系。3 對角矩陣對角矩陣 矩陣中，除了主對角線和主對角線上或下方若干條對角線矩陣中，除了主對角線和主對角線上或下方若干條對角線上的元素之外，其余元素皆為零。即所有的非零元素集中在上的元素之外，其余元素皆為零。即所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，如圖以主對角線為中心的帶狀區(qū)域中，如圖5.6所示。所示。23 上述各種特殊矩陣，其非零元素的分布都是上述各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存有規(guī)律的，因此總能找到一種方法將它們壓縮存儲到一個向量中，并且一般都能找到矩陣中的元儲到一個向量中，并且一般都能找到矩

28、陣中的元素與該向量的對應關(guān)系，通過這個關(guān)系，仍能對素與該向量的對應關(guān)系，通過這個關(guān)系，仍能對矩陣的元素進行隨機存取。矩陣的元素進行隨機存取。 245.3.2 稀疏矩陣稀疏矩陣稀疏矩陣稀疏矩陣(Sparse Matrix)：對于稀疏矩陣，目前還對于稀疏矩陣，目前還沒有一個確切的定義。設(shè)矩陣沒有一個確切的定義。設(shè)矩陣A是一個是一個n m的的矩陣中有矩陣中有s個非零元素，設(shè)個非零元素，設(shè) =s/(n m)，稱稱為為稀疏因子，如果稀疏因子，如果某一矩陣的稀疏因子某一矩陣的稀疏因子滿足滿足0.05時稱為稀疏矩陣，如時稱為稀疏矩陣，如圖圖5.8所示。所示。0 12 9 0 0 0 0 00 0 0 0 0

29、 0 0 0-3 0 0 0 0 0 0 40 0 24 0 0 2 0 00 18 0 0 0 0 0 00 0 0 0 0 0 -7 0A=0 0 0 -6 0 0 0 0圖圖5.8 稀疏稀疏矩陣矩陣示例示例255.3.2.1 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 對于稀疏矩陣，采用壓縮存儲方法時，只存儲非對于稀疏矩陣，采用壓縮存儲方法時，只存儲非0元素。必須存儲非元素。必須存儲非0元素的行下標值、列下標值、元素元素的行下標值、列下標值、元素值。因此，一個三元組值。因此，一個三元組(i, j, aij)唯一確定稀疏矩陣的一唯一確定稀疏矩陣的一個非零元素。個非零元素。 如圖如圖5.8的稀疏矩

30、陣的稀疏矩陣A的三元組線性表為：的三元組線性表為：( (1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (5,2,18), (6,7,-7), (7,4,-6) ) 261 三元組順序表三元組順序表若以行序為主序，稀疏矩陣中所有非若以行序為主序，稀疏矩陣中所有非0元素的三元組，就可以得元素的三元組，就可以得構(gòu)成該稀疏矩陣的一個三元組順序表（構(gòu)成該稀疏矩陣的一個三元組順序表（順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)）。相應）。相應的數(shù)據(jù)結(jié)構(gòu)定義如下：的數(shù)據(jù)結(jié)構(gòu)定義如下： 三元組結(jié)點定義三元組結(jié)點定義 #define MAX_SIZE 101typedef int e

31、lemtype ;typedef struct int row ; /* 行下標行下標 */int col ; /* 列下標列下標 */ElemType value; /* 元素值元素值 */Triple ;27 三元組順序表定義三元組順序表定義 typedef struct int rn ; /* 行數(shù)行數(shù) */int cn ; /* 列數(shù)列數(shù) */int tn ; /* 非非0元素個數(shù)元素個數(shù) */Triple dataMAX_SIZE+1 ; /data0未用未用TSMatrix ; 圖圖5.8所示的稀疏矩陣及其相應的轉(zhuǎn)置矩陣所對應所示的稀疏矩陣及其相應的轉(zhuǎn)置矩陣所對應的三元組順序表如圖

32、的三元組順序表如圖5.9所示。所示。 28圖圖5.9 稀疏矩陣及其轉(zhuǎn)置矩陣的三元組順序表稀疏矩陣及其轉(zhuǎn)置矩陣的三元組順序表798rn行數(shù)行數(shù)cn列數(shù)列數(shù)tn元素個數(shù)元素個數(shù)row col value1 2 121 3 93 1 -33 8 44 3 245 2 186 7 -77 4 -64 6 2(a) 原原矩陣的三元組表矩陣的三元組表897rn行數(shù)行數(shù)cn列數(shù)列數(shù)tn元素個數(shù)元素個數(shù)row col value1 3 -32 1 122 5 183 1 93 4 244 7 -67 6 -78 2 46 4 2(b)轉(zhuǎn)置矩陣的三元組表轉(zhuǎn)置矩陣的三元組表29 矩陣的運算包括矩陣的轉(zhuǎn)置、矩陣求逆

33、、矩陣的加矩陣的運算包括矩陣的轉(zhuǎn)置、矩陣求逆、矩陣的加減、矩陣的乘除等。在此，先討論在這種壓縮存儲結(jié)構(gòu)減、矩陣的乘除等。在此，先討論在這種壓縮存儲結(jié)構(gòu)下的求矩陣的轉(zhuǎn)置的運算。下的求矩陣的轉(zhuǎn)置的運算。 一個一個m n的矩陣的矩陣A，它的轉(zhuǎn)置，它的轉(zhuǎn)置B是一個是一個n m的矩陣，的矩陣，且且bij=aji，0in，0jm，即，即B的行是的行是A的列，的列，B的列是的列是A的行。的行。 設(shè)稀疏矩陣設(shè)稀疏矩陣A是是按行優(yōu)先順序按行優(yōu)先順序壓縮存儲在三元組表壓縮存儲在三元組表a.data中，若僅僅是簡單地交換中，若僅僅是簡單地交換a.data中中i和和j的內(nèi)容，得的內(nèi)容，得到三元組表到三元組表b.dat

34、a，b.data將是一個將是一個按列優(yōu)先順序按列優(yōu)先順序存儲存儲的稀疏矩陣的稀疏矩陣B，要得到按行優(yōu)先順序存儲的，要得到按行優(yōu)先順序存儲的b.data，就，就必須重新排列三元組表必須重新排列三元組表b.data中元素的順序。中元素的順序。30 求轉(zhuǎn)置矩陣的基本算法思想是：求轉(zhuǎn)置矩陣的基本算法思想是： 將矩陣的行將矩陣的行、列下標值交換。即將三元組表中的列下標值交換。即將三元組表中的行行、列位置值列位置值i 、j相互相互交換交換； 重排三元組表重排三元組表中元素中元素的順序。即交換后仍然是的順序。即交換后仍然是按按行優(yōu)先順序行優(yōu)先順序排序的。排序的。方法一方法一：算法思想算法思想：按稀疏矩陣按稀

35、疏矩陣A的的三元組表三元組表a.data中的中的列次列次序依次序依次找到相應的三元組存入找到相應的三元組存入b.data中。中。 每找轉(zhuǎn)置后矩陣的一個三元組，需從頭至尾掃描每找轉(zhuǎn)置后矩陣的一個三元組，需從頭至尾掃描整個三元組表整個三元組表a.data 。找到之后自然就成為按行優(yōu)先的。找到之后自然就成為按行優(yōu)先的轉(zhuǎn)置矩陣的壓縮存儲表示。轉(zhuǎn)置矩陣的壓縮存儲表示。31按方法一求轉(zhuǎn)置矩陣的算法如下：按方法一求轉(zhuǎn)置矩陣的算法如下：void TransMatrix(TSMatrix a , TSMatrix b) int p , q , col ;b.rn= ; =a.rn ; b.tn=a.tn ;/*

36、 置置三元組表三元組表b.data的的行行、列數(shù)和非列數(shù)和非0元素個數(shù)元素個數(shù) */if (b.tn=0) printf(“ The Matrix A=0n” );else q=1;for (col=1; col= ; col+) /* 每循環(huán)一次找到轉(zhuǎn)置后的一個三元組每循環(huán)一次找到轉(zhuǎn)置后的一個三元組 */for (p=1 ;pa.tn ; p+) /* 循環(huán)次數(shù)是非循環(huán)次數(shù)是非0元素個數(shù)元素個數(shù) */ if (a.datap.col=col) b.dataq.row=a.datap.col ; b.dataq.col=a.datap.row ; b.dataq.value=a.datap.v

37、alue; q+ ; 32算法分析算法分析：本算法主要的工作是在本算法主要的工作是在p和和col的兩個循環(huán)的兩個循環(huán)中完成的，故算法的時間復雜度為中完成的，故算法的時間復雜度為O(cn tn)，即矩陣，即矩陣的列數(shù)和非的列數(shù)和非0元素的個數(shù)的乘積成正比。元素的個數(shù)的乘積成正比。33而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為：而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為：for(col=1; col=n ;+col)for(row=0 ; row=m ;+row)bcolrow=arowcol ; 其時間復雜度為其時間復雜度為O(n m)。當非零元素的個數(shù)當非零元素的個數(shù)tn和和m n同數(shù)量級時，算法同數(shù)量級時，算法TransM

38、atrix的時間復雜度為的時間復雜度為O(m n2)。 由此可見由此可見，雖然節(jié)省了存儲空間雖然節(jié)省了存儲空間，但時間復雜度卻但時間復雜度卻大大增加大大增加。所以上述算法只適合于稀疏矩陣中非所以上述算法只適合于稀疏矩陣中非0元素元素的個數(shù)的個數(shù)tn遠遠小于遠遠小于m n的的情況情況。34方法二方法二( (快速轉(zhuǎn)置的算法快速轉(zhuǎn)置的算法) ) 算法思想算法思想：直接按照稀疏矩陣直接按照稀疏矩陣A的的三元組表三元組表a.data的的次序依次順序轉(zhuǎn)換次序依次順序轉(zhuǎn)換，并將轉(zhuǎn)換后的三元組，并將轉(zhuǎn)換后的三元組放置于放置于三元組三元組表表b.data的的恰當位置恰當位置。 前提前提：若能預先確定原矩陣若能預

39、先確定原矩陣A中每一列的中每一列的(即即B中中每一行每一行)第一個非第一個非0元素在元素在b.data中應有中應有的位置，則在作的位置，則在作轉(zhuǎn)置時就可直接放在轉(zhuǎn)置時就可直接放在b.data中恰當中恰當?shù)奈恢?。因此，應的位置。因此，應先先求得求得A中每一列的非中每一列的非0元素個數(shù)元素個數(shù)。附設(shè)兩個輔助向量附設(shè)兩個輔助向量num和和cpot。 numcol：統(tǒng)計統(tǒng)計A中第中第col列列中非中非0元素的個數(shù)元素的個數(shù)； cpotcol ：指示指示A中第中第col列的第一個非列的第一個非0元素元素在在b.data中的恰當中的恰當位置。位置。355.3.2 稀疏矩陣稀疏矩陣稀疏矩陣稀疏矩陣(Spar

40、se Matrix)：對于稀疏矩陣，目前還對于稀疏矩陣，目前還沒有一個確切的定義。設(shè)矩陣沒有一個確切的定義。設(shè)矩陣A是一個是一個n m的的矩陣中有矩陣中有s個非零元素，設(shè)個非零元素，設(shè) =s/(n m)，稱稱為為稀疏因子，如果稀疏因子，如果某一矩陣的稀疏因子某一矩陣的稀疏因子滿足滿足0.05時稱為稀疏矩陣，如時稱為稀疏矩陣，如圖圖5.8所示。所示。0 12 9 0 0 0 0 00 0 0 0 0 0 0 0-3 0 0 0 0 0 0 40 0 24 0 0 2 0 00 18 0 0 0 0 0 00 0 0 0 0 0 -7 0A=0 0 0 -6 0 0 0 0圖圖5.8 稀疏稀疏矩陣

41、矩陣示例示例36顯然有位置對應關(guān)系：顯然有位置對應關(guān)系：cpot1=1cpotcol=cpotcol-1+numcol-1 例圖例圖5.5.8中的矩陣中的矩陣A和表和表5.5.9(a)的的相應的三元組表可相應的三元組表可以求得以求得numcol和和cpotcol的值如表的值如表5.5.1：numcol 1 2 2 1 0 1 1 1 col 1 2 3 4 5 6 7 8cpotcol 1 2 4 6 7 7 8 9表表5.1 numcol和和cpotcol的值表的值表37快速轉(zhuǎn)置算法如下：快速轉(zhuǎn)置算法如下： void FastTransMatrix(TSMatrix a, TSMatrix

42、b) int p , q , col , k ;int numMAX_SIZE , cpotMAX_SIZE ;b.rn= ; =a.rn ; b.tn=a.tn ; /* 置置三元組表三元組表b.data的的行行、列數(shù)和非列數(shù)和非0元素個數(shù)元素個數(shù) */ if (b.tn=0) printf(“ The Matrix A=0n” ) ;else for (col=1 ; col= ; +col) numcol=0 ; /* 向量向量num初始化為初始化為0 */ for (k=1 ; k=a.tn ; +k) +num a.datak.col ; /* 求原求原矩陣中每一列非矩陣中每一列非0

43、元素個數(shù)元素個數(shù) */38for (cpot1=1, col=2 ; col= ; +col) cpotcol=cpotcol-1+numcol-1 ; /* 求第求第col列列中第一個非中第一個非0元在元在b.data中的序號中的序號 */for (p=1 ; p=a.tn ; +p) col=a.datap.col ; q=cpotcol ; b.dataq.row=a.datap.col ; b.dataq.col=a.datap.row ; b.dataq.value=a.datap.value ; +cpotcol ; 393 十字鏈表十字鏈表 對于稀疏矩陣，當非對于稀疏矩陣，當非0

44、元素的個數(shù)和位置在操作過元素的個數(shù)和位置在操作過程中變化較大時，采用鏈式存儲結(jié)構(gòu)表示比三元組的程中變化較大時，采用鏈式存儲結(jié)構(gòu)表示比三元組的線性表更方便。線性表更方便。 矩陣中非矩陣中非0元素的結(jié)點所含的域有：元素的結(jié)點所含的域有：行行、列列、值值、行指針行指針(指向同一行的下一個非指向同一行的下一個非0元元)、列指針列指針(指向同一指向同一列的下一個非列的下一個非0元元)。其次，十字交叉鏈表還有一個頭結(jié)。其次，十字交叉鏈表還有一個頭結(jié)點，結(jié)點的結(jié)構(gòu)如圖點，結(jié)點的結(jié)構(gòu)如圖5.10所示。所示。圖圖5.10 十字鏈十字鏈表結(jié)點結(jié)構(gòu)表結(jié)點結(jié)構(gòu)row col value down right rn c

45、n tn down right(a) 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)(b) 頭頭結(jié)點結(jié)結(jié)點結(jié)構(gòu)構(gòu)40 由定義知，稀疏矩陣中同一行的非由定義知，稀疏矩陣中同一行的非0元素由元素由right指針指針域鏈接成一個行鏈表域鏈接成一個行鏈表， 由由down指針域鏈接成一個列鏈表指針域鏈接成一個列鏈表。則每個非。則每個非0元素既是元素既是某個行鏈表中的一個結(jié)點某個行鏈表中的一個結(jié)點，同時又同時又是是某個列鏈表中的一個結(jié)點某個列鏈表中的一個結(jié)點，所有的，所有的非非0元素構(gòu)成一個十元素構(gòu)成一個十字交叉的鏈表。稱為十字鏈表。字交叉的鏈表。稱為十字鏈表。 此外，還可用兩個此外，還可用兩個一一維數(shù)組分別存儲行維數(shù)組分別存儲行鏈表

46、的頭指鏈表的頭指針和列鏈表的頭指針針和列鏈表的頭指針。對于圖。對于圖5.5.11(a)的的稀疏矩陣稀疏矩陣A ，對對應的十字交叉鏈表如圖應的十字交叉鏈表如圖5.5.11(b)所示，結(jié)點的描述如下：所示，結(jié)點的描述如下：typedef struct Clnode int row , col ; /* 行號和列號行號和列號 */ ElemType value ; /* 元素值元素值 */struct Clnode *down , *right ;OLNode ; /* 非非0元素結(jié)點元素結(jié)點 */41typedef struct Clnode int rn; /* 矩陣的矩陣的行數(shù)行數(shù) */ in

47、t cn; /* 矩陣的矩陣的列數(shù)列數(shù) */int tn; /* 非非0元素總數(shù)元素總數(shù) */OLNode *rhead ; OLNode *chead ; CrossList ;圖圖5.11稀疏稀疏矩陣矩陣及其及其十字交叉鏈表十字交叉鏈表0 12 0 0 00 0 0 0 -40 5 0 0 00 0 3 0 0A=(a) 稀疏稀疏矩陣矩陣) 稀疏稀疏矩陣的十字交叉鏈表矩陣的十字交叉鏈表A.cheadA.rchead 1 2 12 3 2 5 2 5 -4 4 3 3 42 廣義表是線性表的推廣和擴充廣義表是線性表的推廣和擴充，在人工智能領(lǐng)域在人工智能領(lǐng)域中應用十分廣泛。中應用十分廣泛。 在

48、第在第2章中，我們把線性表定義為章中，我們把線性表定義為n(n0 )個元素個元素a1, a2 , an的有窮序列，該序列中的所有元素具有相的有窮序列，該序列中的所有元素具有相同的數(shù)據(jù)類型且只能是原子項同的數(shù)據(jù)類型且只能是原子項(Atom)。所謂。所謂原子項可原子項可以是一個數(shù)或一個結(jié)構(gòu)，是指結(jié)構(gòu)上不可再分的以是一個數(shù)或一個結(jié)構(gòu)，是指結(jié)構(gòu)上不可再分的。若放。若放松對元素的這種限制，容許它們具有其自身結(jié)構(gòu)，就產(chǎn)松對元素的這種限制，容許它們具有其自身結(jié)構(gòu)，就產(chǎn)生了廣義表的概念。生了廣義表的概念。 5.4 廣義表的定義廣義表的定義5.4 廣義表的定義廣義表的定義 廣義表又稱為廣義表又稱為列表列表（Li

49、sts），它廣泛地應用于人工智能語言），它廣泛地應用于人工智能語言LISP中中.廣義表通常記為：廣義表通常記為：其中，其中， LS= (= (1，2 ， ，n) ) LS稱為廣義表的名字。稱為廣義表的名字。 n稱為廣義表稱為廣義表LS的的長度長度。特別地，當。特別地，當n=0時時LS被稱為被稱為空表空表。 在廣義表在廣義表LS中，中， i 既可以是單個數(shù)據(jù)元素（稱為既可以是單個數(shù)據(jù)元素（稱為LS的的原子原子），也可），也可以又是一個廣義表（稱為以又是一個廣義表（稱為LS的的子表子表）。）。 通常約定用大寫字母表示廣義表，用小寫字母表示原子。通常約定用大寫字母表示廣義表，用小寫字母表示原子。 當

50、廣義表當廣義表LS非空時，首元素非空時，首元素1稱做稱做LS的的表頭，表頭，記作記作Head(LS)；由其；由其余元素組成的表余元素組成的表(2，n) 稱為稱為LS的的表尾，表尾，記作記作Tail(LS) 。 可以看出，對于任何非空廣義表，可以看出，對于任何非空廣義表， 都可以分解為表頭和表尾兩部分。都可以分解為表頭和表尾兩部分。 由于在廣義表的定義中又用到了廣義表的概念，所以說廣義表的定義由于在廣義表的定義中又用到了廣義表的概念，所以說廣義表的定義是一個遞歸的定義。是一個遞歸的定義。 5.4 廣義表的定義廣義表的定義 下面來看幾個廣義表的例子：下面來看幾個廣義表的例子： A=() 列表列表A

51、是一個空表，長度為是一個空表，長度為0。 B=(e) 列表列表B中只有一個原子，長度為中只有一個原子，長度為1，Head(B)=e，Tail(B)=()。 C=(a，(b，c，d) 兩個元素分別為原子兩個元素分別為原子a和子表和子表(b，c，d)，其長度為，其長度為2。Head(C)=a，Tail(C)=(b，c，d)。 D=(A，B，C) 列表列表D的長度為的長度為3，三個元素均為列表。將子表的值代入后，三個元素均為列表。將子表的值代入后，D=()，(e)，(a，(b，c，d) E=(a，E) 這是一個遞歸的列表，長度為這是一個遞歸的列表，長度為2，Head(E)=a，Tail(E)=(E)。 F=() 其長度為其長度為1，Head(F)=()，Tail(F)=()。 5.4 廣義表的定義廣義表的定義 關(guān)于廣義表我們有以下結(jié)論：關(guān)于廣義表我們有以下結(jié)論： 由于列表的元素可以是子表，而子表的元素還可以是子表，因此，由于列表的元素可以是子表，而子表的元素還可以是子表，因此，列表是一個多層次的結(jié)構(gòu)。列表是一個多層次的結(jié)構(gòu)。 例如前面的列表例如前面的列表D可圖示如下：可圖示如下： 一個列表可以被其他列表所共享。一個列表可以被其他列表所共享。 例如例如A、B、C是是D的子表，在的子表，在D中