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

數(shù)據(jù)結(jié)構(gòu)課件數(shù)組和廣義表第一頁，共六十四頁，編輯于2023年，星期三數(shù)組(array)是最常用的數(shù)據(jù)結(jié)構(gòu)之一。幾乎所有的程序設(shè)計(jì)語言都把數(shù)組類型設(shè)定為固有類型。數(shù)組的定義線性結(jié)構(gòu)中的數(shù)據(jù)都是非結(jié)構(gòu)的原子類型，元素的值是不再分解的。而數(shù)組可以看成是線性表在下述含義上的擴(kuò)展：5.1數(shù)組的邏輯結(jié)構(gòu)2數(shù)組的基本操作表中的數(shù)據(jù)元素本身也是一種數(shù)據(jù)結(jié)構(gòu)。第二頁，共六十四頁，編輯于2023年，星期三數(shù)組是由下標(biāo)和值組成的序?qū)稀Ｔ跀?shù)組中，一旦給定下標(biāo)，都存在一個(gè)與其相對(duì)應(yīng)的值，這個(gè)值就稱為數(shù)組元素。也可以說，數(shù)組中的每個(gè)數(shù)據(jù)元素都對(duì)應(yīng)于一組下標(biāo)（j1

,j2

,…,jn），每個(gè)下標(biāo)取值范圍是1≤ji≤bi，bi稱為第i

維的長(zhǎng)度（i=1,2,…,n）。顯然，當(dāng)n=1時(shí)，n維數(shù)組就退化為定長(zhǎng)的線性表。反之，n

維數(shù)組也可以看成是線性表的推廣。3 5.1.1數(shù)組的定義第三頁，共六十四頁，編輯于2023年，星期三

可以把二維數(shù)組看成是這樣一個(gè)定長(zhǎng)線性表：它的每個(gè)數(shù)據(jù)元素也是一個(gè)定長(zhǎng)線性表。Am×n=a11a21…am1a12a22…am2a13a23…am3…………a1.na2,n…am,n4例如，下面是一個(gè)二維數(shù)組，且以m

行n

列的矩陣形式表示。第四頁，共六十四頁，編輯于2023年，星期三 每個(gè)數(shù)據(jù)元素α

j是一個(gè)列向量形式的線性表Am×n=…a1,na2,n…am,na13a23…am,3a12a22…am,2a11a21…am,1

二維數(shù)組A

還可以看成是一個(gè)線性表：A=(α1,α

2,…,α

n)

α

j=(a1j

,a2j

,…,am,j) 1≤j≤n 每個(gè)數(shù)據(jù)元素是一個(gè)行向量形式的線性表

B=(β1β2β3…,

βm)Am×n=((a11

a12

…a1,n

),…,(am,1am,2…am,n

))(a21

a22

…a2,n

),…,βi=(ai1,ai2,…,ai,n) 1≤i≤m5第五頁，共六十四頁，編輯于2023年，星期三數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取數(shù)據(jù)元素和修改數(shù)據(jù)元素值的操作。6第六頁，共六十四頁，編輯于2023年，星期三 5.1.2數(shù)組的抽象類型定義ADTArray{

D={aj1j2j3…..jn|n>0,稱為數(shù)組的維數(shù),ji是數(shù)組的第i維下標(biāo),1≤ji

≤bi,

bi為數(shù)組第i維的長(zhǎng)度，aj1j2j3…..jn∈ElementSet}數(shù)據(jù)關(guān)系：Ｒ

={R1,R2,…….Rn}Ri=<aj1…ji….jn,aj1…ji+1…jn>|1≤jk≤bk,1≤k≤n且k≠i,1≤ji

≤bi-1,aj1…j2….jn,aj1…ji+1…jn∈D,i=1,…n}基本操作:InitArray(A,n,bound1,…,boundn); 操作結(jié)果：如果維數(shù)n

和各維長(zhǎng)度合法，則構(gòu)造 相應(yīng)的數(shù)組A，并且返回TRUE。第七頁，共六十四頁，編輯于2023年，星期三8 5.1.2數(shù)組的抽象類型定義DestroyArray(A):銷毀數(shù)組A。GetValue(A,e,index1,…,indexn):初始條件：A

是n

維數(shù)組，e

為元素變量，隨后是

n

個(gè)下標(biāo)值。 操作結(jié)果：若各下標(biāo)合法，則用e返回?cái)?shù)組Ａ中由由index1,…indexn所指定的元素的值.SetValue(A,e,index1,…,indexn); 初始條件：A

是n

維數(shù)組，e

為元素變量，隨后是

n

個(gè)下標(biāo)值。 操作結(jié)果：若各下標(biāo)合法，則將數(shù)組A中由index1,…indexn所指定的元素的值置為e.第八頁，共六十四頁，編輯于2023年，星期三由于內(nèi)存儲(chǔ)器的結(jié)構(gòu)是一維的。一維數(shù)組可直接采用順序存儲(chǔ)。用一維的內(nèi)存存儲(chǔ)表示多維數(shù)組時(shí)，需按某種次序?qū)?shù)組中元素排成一線性序列，再將這個(gè)線性序列存放在一維的內(nèi)存中，即數(shù)組的順序存儲(chǔ)結(jié)構(gòu)表示。順序存儲(chǔ)的定位公式5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)9數(shù)組的順序存儲(chǔ)表示基本操作的算法描述第九頁，共六十四頁，編輯于2023年，星期三

用順序存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)數(shù)組中的元素，一定要按照某種次序?qū)⒃嘏懦梢粋€(gè)線性序列。有兩種存儲(chǔ)方式：(1)以列為主序(columnmajororder)的存儲(chǔ)方式，即按列優(yōu)先，逐列順序存儲(chǔ)。(2)以行為主序(rowmajororder)的存儲(chǔ)方式，即按行優(yōu)先，逐行順序存儲(chǔ)。10 5.2.1順序存儲(chǔ)的定位公式第十頁，共六十四頁，編輯于2023年，星期三a21a11…am,1a22a12…am,2a1,n…a2,n…am,na21a11…am,1a21a11…Am,1a21a11…am,1a22a12…am,2a22a12…am,2a22a12…am,2………a1,na2,n…am,na1,na2,n…am,na1,na2,n…am

n11列主次序存放第十一頁，共六十四頁，編輯于2023年，星期三a12a11…a1.na22a21…a2,nam,1…am,2…am,na12a11…a1.na22a21…a2,n………am,1am,2…am,na12a11…a1,na12a11…a1,na22a21…a2,na22a21…a2,nam,1am,2…am,nam,1am,2…am,n12行主次序存放第十二頁，共六十四頁，編輯于2023年，星期三對(duì)于數(shù)組，一旦規(guī)定了它的維數(shù)和各維的長(zhǎng)度，便可以為它分配存儲(chǔ)空間。反之，只要給出一組下標(biāo)，便可以求得相應(yīng)數(shù)組的存儲(chǔ)位置。13第十三頁，共六十四頁，編輯于2023年，星期三（１）一維數(shù)組的地址計(jì)算：設(shè)一維數(shù)組為：Ａ=(a1,a2,…,ai,…,an),數(shù)組中每個(gè)元素占size個(gè)存儲(chǔ)單元，則元素ai的存儲(chǔ)地址為：Loc(A[i])=Loc(A[1])+(i-1)*size。

數(shù)組的地址計(jì)算14第十四頁，共六十四頁，編輯于2023年，星期三

⑵二維數(shù)組的地址計(jì)算

假設(shè)每個(gè)數(shù)據(jù)元素占1

個(gè)存儲(chǔ)單元，且以行序?yàn)橹餍虻倪M(jìn)行存儲(chǔ)，則二維數(shù)組A

中任一元素aij

的存儲(chǔ)位置可以由下面定位公式確定LOC(A[i],[j])=LOC(A[1],[1])+n*(i-1)+(j-1)其中：

LOC(A[i[,[j]) 是aij

的存儲(chǔ)位置；

LOC(A[1],[1]) 是a11

的存儲(chǔ)位置，即二維數(shù)組A

的起始存儲(chǔ)位置，也稱為基地址或基址；n 是數(shù)組第二維的長(zhǎng)度。15

假設(shè)每個(gè)數(shù)據(jù)元素占size個(gè)存儲(chǔ)單元，則二維數(shù)組A

中任一元素aij

的存儲(chǔ)位置可以由下面定位公式確定LOC(A[i],[j])=LOC(A[1],[1])+(n*(i-1)+(j-1))*size第十五頁，共六十四頁，編輯于2023年，星期三

⑶三維數(shù)組的地址計(jì)算

三維數(shù)組A(1:r,1:m,1:n)。假設(shè)每個(gè)數(shù)據(jù)元素占size個(gè)存儲(chǔ)單元，且以行序?yàn)橹餍虻倪M(jìn)行存儲(chǔ)，首元素a111的地址為L(zhǎng)oc(A[1][1][1]),求任意元素aijk的地址。

顯然，ai11地址為

Ｌoc(A[i][1][1])=Loc(A[1][1][1])+(i-1)*m*n,因?yàn)樵谠撛刂坝衖-1個(gè)m*n的二維數(shù)組。16不難得到三維數(shù)組任意元素aijk的地址：Loc(A[i][j][k])=Loc(A[1][1][1])+((i-1)*m*n+(j-1)*n+(k-1))*size,其中：１≤i≤r,１≤j≤m,１≤k≤n。第十六頁，共六十四頁，編輯于2023年，星期三矩陣(matrix)是很多科學(xué)與工程計(jì)算問題中研究的數(shù)學(xué)對(duì)象。在數(shù)據(jù)結(jié)構(gòu)中，我們感興趣的不是矩陣本身，而是如何存儲(chǔ)矩陣的元素而使矩陣的各種運(yùn)算能夠有效地進(jìn)行。

特殊矩陣包括兩個(gè)部份：①元素分布有特殊規(guī)律的矩陣,找到規(guī)律對(duì)應(yīng)的公式，實(shí)現(xiàn)壓縮存儲(chǔ)。②非零元素很少的稀疏矩陣，可采用只存非零元素的方法實(shí)現(xiàn)壓縮存儲(chǔ)。5.3矩陣的壓縮存儲(chǔ)17第十七頁，共六十四頁，編輯于2023年，星期三特殊矩陣的壓縮存儲(chǔ)所謂壓縮存儲(chǔ)是指：為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元不分配空間。18稀疏矩陣的邏輯結(jié)構(gòu)稀疏矩陣的存儲(chǔ)結(jié)構(gòu)第十八頁，共六十四頁，編輯于2023年，星期三

假若相同的元素或者零元素在矩陣中的分布有一定規(guī)律，則稱特殊矩陣。特殊矩陣主要有3種：對(duì)稱矩陣、三角矩陣、帶狀矩陣。

在所有這些統(tǒng)稱為“特殊矩陣”的矩陣中，非零元的分布都有一個(gè)明顯的規(guī)律，從而都可以將其壓縮存儲(chǔ)到一維數(shù)組中，并且找到每個(gè)非零元在一維數(shù)組中的對(duì)應(yīng)關(guān)系。19 5.3.1特殊矩陣的壓縮存儲(chǔ)第十九頁，共六十四頁，編輯于2023年，星期三

若一個(gè)n

階矩陣M

中的元素滿足下述性質(zhì)1.對(duì)稱矩陣aij=aji

1≤i，j≤n則稱為n

階對(duì)稱矩陣。20第二十頁，共六十四頁，編輯于2023年，星期三

對(duì)于對(duì)稱矩陣，可以為每一對(duì)對(duì)稱元只分配一個(gè)存儲(chǔ)空間，這樣就可以將n2

個(gè)元壓縮存儲(chǔ)到n(n+1)/2個(gè)元的空間中。假設(shè)以行序?yàn)橹餍虼鎯?chǔ)對(duì)稱矩陣的下三角（包括對(duì)角線）中的元。以一維數(shù)組B[n(n+1)/2]作為n

階對(duì)稱矩陣M

的存儲(chǔ)結(jié)構(gòu)，21a31a22a21a11an,n…an,1…BLoc(A[i][j]=1234……

Loc(A[i][j])=Loc(A[1][1])+i*(i-1)/2+j-1(i>j)第二十一頁，共六十四頁，編輯于2023年，星期三

三角矩陣分為下三角矩陣和上三角矩陣。所謂下(上)三角矩陣是指矩陣的上(下)三角(不包括對(duì)角線)中的元均為常數(shù)c

或?yàn)榱愕膎

階矩陣。2.三角矩陣22下三角矩陣

三角矩陣除了和對(duì)稱矩陣一樣，只存儲(chǔ)矩陣的下(上)三角中的元之外，再加上一個(gè)存儲(chǔ)常數(shù)c

的存儲(chǔ)空間即可。上三角矩陣第二十二頁，共六十四頁，編輯于2023年，星期三一個(gè)n

階方陣，若它的全部非零元素落在一個(gè)以對(duì)角線為中心的帶狀區(qū)域中，則稱該矩陣為帶狀矩陣，或?qū)蔷仃?。這個(gè)帶狀區(qū)域若包含主對(duì)角線上下各b

條對(duì)角線道上元素，那么，b

稱為該帶狀矩陣的半帶寬，或稱該帶狀矩陣的帶寬為(2b+1)。3.帶狀矩陣00b

條b

條23第二十三頁，共六十四頁，編輯于2023年，星期三在帶狀矩陣中，當(dāng)|i-j|>b

時(shí)，aij=0。該方陣共有(2b+1)n-(b+1)b

個(gè)非零元素。a11D=a12a1300a21a22a23a240a31a32a33a34a350a42a43a44a4500a53a54a55

D

矩陣是一個(gè)5階、半帶寬為2的帶狀矩陣，在其主對(duì)角線a11、a22、a33、a44、a55上下各有2條對(duì)角線，共有(2b+1)n-(b+1)b=19個(gè)非零元素。24例如：第二十四頁，共六十四頁，編輯于2023年，星期三帶狀矩陣中最常見的是三對(duì)角帶狀矩陣。25特點(diǎn)：當(dāng)i=1j=1,21<i<n,j=i-1,i,i+1

i=n,j=n-1,n

aij非零，其它元素均為零

a11Ann=a12０00a21a22a23０00a32a33a34０0０a43a44a4500………第二十五頁，共六十四頁，編輯于2023年，星期三

1.確定存儲(chǔ)該矩陣所需的一維向量空間的大小除第一行和最后一行只有兩個(gè)元素外，其余各行均有3個(gè)非零元素，由此得到一維向量所需的空間大小為：３n-2

2.確定非零元素在一維數(shù)組空間中的位置Ｌoc(a[i][j])=Loc(a[1][1])+2(i-1)+j-126

三對(duì)角帶狀矩陣的壓縮存儲(chǔ)，以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)，且只存儲(chǔ)非零元素。其方法為第二十六頁，共六十四頁，編輯于2023年，星期三27一般來說，當(dāng)矩陣中非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)時(shí)，稱之為稀疏矩陣。假設(shè)在m×n

的矩陣中，若有t

個(gè)元素不為零，令=t/(m×n)，則稱為矩陣的稀疏因子。通常認(rèn)為≤25%-30%時(shí)稱為稀疏矩陣。 5.3.2稀疏矩陣的邏輯結(jié)構(gòu)1.稀疏矩陣的定義第二十七頁，共六十四頁，編輯于2023年，星期三按照壓縮存儲(chǔ)的概念，只存儲(chǔ)稀疏矩陣的非零元素。因此，除了存儲(chǔ)非零元素的值aij

之外，還必須同時(shí)記下非零元素所在矩陣的行i號(hào)和列j號(hào)。反之，一個(gè)三元組(i,j,aij)唯一確定了矩陣的一個(gè)非零元素。因此，稀疏矩陣可以由表示非零元的三元組及其矩陣的總的行列數(shù)唯一確定。假設(shè)以順序存儲(chǔ)結(jié)構(gòu)表示三元組表，則可以得到稀疏矩陣的一種壓縮存儲(chǔ)方式，這種方式稱之為三元組順序表。28 5.3.3稀疏矩陣的存儲(chǔ)結(jié)構(gòu)1.三元組順序表第二十八頁，共六十四頁，編輯于2023年，星期三012900000000000-3000014000240000018000001500-7000M=矩陣M

可以由三元組表(1,3,-3)，(1,6,15)，(2,1,12)，(2,5,18)，(3,1,9)，(3,4,24)，(4,6,-7)，(6,3,14)再加上（7,6）這一對(duì)總的行列值來描述。29第二十九頁，共六十四頁，編輯于2023年，星期三#defineMAXSIZE 1000//假設(shè)非零元個(gè)數(shù)的最大值為1000typedefstruct{ //三元組順序表的元素結(jié)構(gòu)定義int row,;col //該非零元的行下標(biāo)和列下標(biāo)

ElementTypee; //該非零元的值}Triple;typedefstruct{ //三元組順序表存儲(chǔ)結(jié)構(gòu)定義Tripledata[MAXSIZE+1];//非零元三元組表，data[0]未用

int m,n,len; //矩陣的行數(shù)、列數(shù)和非零個(gè)數(shù)}TSMatrix; //三元組順序表的類型名30(1)三元組順序存儲(chǔ)表示

在這里，data域中表示非零元的三元組是以行序?yàn)橹餍蝽樞蚺帕械?。第三十頁，共六十四頁，編輯?023年，星期三012900000000000-3000014000240000018000001500-7000M=13-3161521122518319342446-76314rowcoleA.data[1]A.data[2]A.data[3]A.data[4]A.data[5]A.data[6]A.data[7]A.data[8](a)稀疏矩陣(b)三元組順序表31第三十一頁，共六十四頁，編輯于2023年，星期三(2)利用三元組順序表實(shí)現(xiàn)矩陣的轉(zhuǎn)置運(yùn)算 將矩陣的行列值相互交互；在這3點(diǎn)中，最關(guān)鍵的是第3條，即如何使B.data中的三元組以Ｔ的行（Ｍ的列）為主序依次排列。32顯然，一個(gè)稀疏矩陣的轉(zhuǎn)置矩陣仍是稀疏矩陣。假設(shè)A

和B

是TSMatrix（三元組順序表）類型變量，分別表示矩陣Ｍ和其轉(zhuǎn)置矩陣Ｔ。那么，只要做到下面3點(diǎn)就可以由A

得到B，實(shí)現(xiàn)矩陣的轉(zhuǎn)置。 將每三元組中的row

和col

相互調(diào)換； 重排三元組之間的次序。第三十二頁，共六十四頁，編輯于2023年，星期三33原始的三元組表原矩陣012900000000000-3000014000240000018000001500-7000Ｍ=A.data[1]A.data[2]A.data[3]A.data[4]A.data[5]A.data[6]A.data[7]A.data[8]A.data13-3161521122518319342446-76314rowcole轉(zhuǎn)置矩陣00-3001512000180900240000000-70000000014000000000Ｔ=轉(zhuǎn)置的三元組表B.data[1]B.data[2]B.data[3]B.data[4]B.data[5]B.data[6]B.data[7]B.data[8]B.data121213931-3361443245218611564-7rowcole第三十三頁，共六十四頁，編輯于2023年，星期三使b.data中的三元組以T

的行（M

的列）為主序依次排列的方法有如下兩種：34方法一：按照B.data中三元組的次序，依次在a.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。方法二：按照A.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入B.data中恰當(dāng)?shù)奈恢谩２捎梅椒ㄒ坏谌捻?，共六十四頁，編輯?023年，星期三①算法思想在A中按三元組的列域值(col)開始掃描，依序?qū)⑷MA.data的列域值(col

)與行域值(row

)進(jìn)行對(duì)換，并且存入B中。由于A是以M的行序?yàn)橹餍騺泶娣琶總€(gè)非零元的，由此得到轉(zhuǎn)置后矩陣的三元組表B恰是以“行序?yàn)橹餍颉薄?5

按照方法一，即按照“被轉(zhuǎn)置矩陣”M的三元組表A

的“列序”遞增順序進(jìn)行轉(zhuǎn)置。為了找到矩陣M

的每一列中所有的非零元素，需要對(duì)其三元組A.data從第一行起進(jìn)行掃描，方法如下：第三十五頁，共六十四頁，編輯于2023年，星期三

轉(zhuǎn)置的三元組表B->data原始的三元組表A.datar

c

v

1

2

12

1

3

9

3

1

-3

3

6

14

4

3

24

5

2

18

6

1

15

6

4

-736利用三元組順序表存儲(chǔ)實(shí)現(xiàn)矩陣的轉(zhuǎn)置c

36151463r

11223346v

-3151218924-714

第三十六頁，共六十四頁，編輯于2023年，星期三voidTransposeTSMatrix(TSMatrixA,TSMatrix*B){//采用三元組表結(jié)構(gòu)，求稀疏矩陣A

的轉(zhuǎn)置矩陣B。在程序中，inti,j,k;//j

指示B->data中三元組的序號(hào)，//i

指示A.data中三元組的序號(hào)，//k指示A的列號(hào)（即B的行號(hào)）

B->m=A.n; //將稀疏矩陣A

的列數(shù)值作為其轉(zhuǎn)置矩陣B

的行數(shù)值B->n=A.m; //將稀疏矩陣A

的行數(shù)值作為其轉(zhuǎn)置矩陣B

的列數(shù)值B->len=A.len; //轉(zhuǎn)置矩陣B與稀疏矩陣A的非零元個(gè)數(shù)相等②算法編(稀疏矩陣“列序”遞增轉(zhuǎn)置算法)

if(B->len>0){

j=1;37第三十七頁，共六十四頁，編輯于2023年，星期三for(k=1;k<=A.n;k++) for(i=1;i<=A.len;i++) if(A.data[i].col==k){ //進(jìn)行轉(zhuǎn)置

returnOK;}//TransposeSMatrix B->data[j].row=A.data[i].col; //稀疏矩陣A的列域值成為其轉(zhuǎn)置矩陣B

的行域值 B->data[j].col=A.data[i].row; //稀疏矩陣A

的行域值成為其轉(zhuǎn)置矩陣M

的列域值 B->data[j].e=A.data[i].e; //將稀疏矩陣M

的非零元值賦給其轉(zhuǎn)置矩陣T

j++; //B->data中三元組的序號(hào)加1 }//if(A.data)結(jié)束}//if(B->len>0)結(jié)束38第三十八頁，共六十四頁，編輯于2023年，星期三③算法分析一般矩陣的轉(zhuǎn)置算法（經(jīng)典算法）為：39for(col=0;col<n;++col) for(row=0;row<m;++row)

dest[col][row]=source[row][col];時(shí)間復(fù)雜度為O(m×n)。

前面給出的求轉(zhuǎn)置矩陣算法的主要工作是在i

和k的兩重循環(huán)中完成的，所以此算法的時(shí)間復(fù)雜度為O(A.n×A.len)即和矩陣A

的列數(shù)和非零元的個(gè)數(shù)的乘積成正比。第三十九頁，共六十四頁，編輯于2023年，星期三40當(dāng)矩陣M

中非零元個(gè)數(shù)幾乎和矩陣元素個(gè)數(shù)相等時(shí)，即len

和m×n等數(shù)量級(jí)時(shí)，算法時(shí)間復(fù)雜度就為O(m×n2)，雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度提高了。由此可見，上述求轉(zhuǎn)置矩陣算法只適合于len<<m×n

的情況。第四十頁，共六十四頁，編輯于2023年，星期三當(dāng)矩陣非零元素的位置或個(gè)數(shù)經(jīng)常變動(dòng)時(shí)，就不易采用順序存儲(chǔ)結(jié)構(gòu)表示三元組的線性表。例如，在進(jìn)行“將矩陣

B

加到矩陣A

上”的操作時(shí)，由于非零元素的插入或刪除將會(huì)引起A.data中元素的大量移動(dòng)。為此，對(duì)這種類型的矩陣，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示三元組的線性表更為恰當(dāng)。412.十字鏈表第四十一頁，共六十四頁，編輯于2023年，星期三(1)稀疏矩陣的十字鏈表存儲(chǔ)表示

矩陣中非零元的行號(hào)row；

矩陣中非零元的列號(hào)col；

矩陣中非零元的值e；

向右域right，用以鏈接同一行中下一個(gè)非零元；

向下域down，用以鏈接同一列中下一個(gè)非零元。42rowdowncolvalueright非零元行號(hào)非零元列號(hào)非零元的值向下域向右域在鏈表中，矩陣的非零元素可用如下結(jié)點(diǎn)表示：同一行的非零元通過right域鏈接成一個(gè)線性鏈表，同一列的非零元通過down域鏈接成一個(gè)線性鏈表，每個(gè)非零元Mij既是第i個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，又是第j個(gè)列鏈表中的一個(gè)結(jié)點(diǎn)，整個(gè)矩陣構(gòu)成了一個(gè)十字交叉的鏈表，故稱這樣的存儲(chǔ)結(jié)構(gòu)為十字鏈表。第四十二頁，共六十四頁，編輯于2023年，星期三typedefstructOLNode{ //結(jié)點(diǎn)定義int row,col; //該非零元的行和列下標(biāo)ElementTypevalue; //該非零元的值

structOLNode *right,*down;//該非零元所在的行表和列表的后繼鏈域}OLNode;*Olink;typedefstruct{ //十字鏈表定義int m,n,len; //稀疏矩陣行數(shù)、列數(shù)和非零元個(gè)數(shù)Olink *row_head,*col_head;//行和列鏈表頭指針向量，由CreateSMatrix分配}CrossList; //十字鏈表存儲(chǔ)結(jié)構(gòu)的類型名43將行鏈表的頭指針存儲(chǔ)在一維數(shù)組M.row_head中將列鏈表的頭指針存儲(chǔ)在一維數(shù)組M.col_head中第四十三頁，共六十四頁，編輯于2023年，星期三3020-10500000113145∧22-1∧312∧M.col_headM.row_head∧∧∧∧44第四十四頁，共六十四頁，編輯于2023年，星期三CreateSMatrix_OL(CrossList*M){//創(chuàng)建稀疏矩陣M。采用十字鏈表存儲(chǔ)表示。(2)利用十字鏈表實(shí)現(xiàn)創(chuàng)建稀疏矩陣的運(yùn)算if(!(M->row_head=(Olink*)malloc((m+1)*sizeof(Olink))))exit(OVERFLOW);if(!(M->col_head=(Olink*)malloc((n+1)*sizeof(Olink))))exit(OVERFLOW);if(M)free(M);scanf(&m,&n,&t); //輸入M

的行數(shù)、列數(shù)和非零元個(gè)數(shù)

M->m=m;M->n=n;M->len=t;45①算法編寫第四十五頁，共六十四頁，編輯于2023年，星期三for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){//按任意次序輸入非零元if(!(p=(OLNode*)malloc(sizeof(OLNode)))) exit(OVERFLOW);p->row=i; //生成新結(jié)點(diǎn)的行號(hào)域p->col=j; //生成新結(jié)點(diǎn)的列號(hào)域p->value=e; //生成新結(jié)點(diǎn)的值域46M->row_head[]=NULL;//初始化行頭指針向量；令各行鏈表為空鏈表M->col_head[]=NULL;//初始化列頭指針向量；令各列鏈表為空鏈表第四十六頁，共六十四頁，編輯于2023年，星期三if(M->row_head[i]==NULL){M->row_head[i]=p;p->right=NULL;}else{for(q=M->row_head[i];(q->right)&&q->right->col<j; q=q->right); p->right=q->right;q->right=p;}//完成行插入elseif(M->row_head[i]->col>j){//尋找在行表中的插入位置 p->right=M->row_head[i];M->row_head[i]=p;}47第四十七頁，共六十四頁，編輯于2023年，星期三if(M->col_head[j]==NULL){ M_col_head[j]=p;p->down=NULL;}else{for(q=M->col_head[j];(q->down)&&q->down->row<i; q=q->down); p->down=q->down;q->down=p;}//完成列插入elseif(M->col_head[j]->row>i){//尋找在列表中的插入位置p->down=M->row_head[j];M->col_head[j]=p;}}//for結(jié)束

returnOK;}//CreateSMatrix_OL48第四十八頁，共六十四頁，編輯于2023年，星期三∧∧∧∧∧∧∧M->col_headM->row_head(1)輸入(1,1,3)1∧13∧p(2)輸入(1,3,5)p135q∧(3)輸入(1,4,9)∧149pq∧∧(4)輸入(3,1,2)312∧p∧q49(5)輸入(2,3,4)234q∧∧(6)輸入(2,2,8)q創(chuàng)建稀疏矩陣M

的十字鏈表if(M.rhead[i]==NULL){M.rhead[i]=p;p->right=NULL;}for(q=M->col_head[i];(q->down)&&q->down->row<i; q=q->down);p->down=q->down;q->down=p;if(M->row_head[i]->j>j){p->right=M->row_head[i];M->row_head[i]=p;}if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}pq∧p228if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}for(q=M->row_head[i];(q->right)&&q->right->col<j; q=q->right);p->right=q->right;q->right=p;if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}for(q=M->row_head[i];(q->right)&&q->right->col<j; q=q->right);p->right=q->right;q->right=p;if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}if(M->row_head[i]==NULL){M->row_head[i]=p;p->right=NULL;}for(q=M->col_head[i];(q->down)&&q->down->row<i; q=q->down);p->down=q->down;q->down=p;if(M->row_head[i]==NULL){M->row_head[i]=p;p->right=NULL;}第四十九頁，共六十四頁，編輯于2023年，星期三對(duì)于一個(gè)m

行n

列，并且有t

個(gè)非零元的稀疏矩陣，CreateSMatrix_OL算法執(zhí)行時(shí)間為O(t×s)，其中s=max{m,n}。這是因?yàn)椋好拷⒁粋€(gè)非零元的結(jié)點(diǎn)時(shí)都需要尋查它在行表和列表中的插入位置，此算法對(duì)非零元輸入的先后次序沒有任何要求。反之，若按以行序?yàn)橹餍虻拇涡蛞来屋斎肴M，即可以將建立十字鏈表表示的算法改寫成O(t)數(shù)量級(jí)的（t

為非零元個(gè)數(shù)）的算法。②算法分析50第五十頁，共六十四頁，編輯于2023年，星期三廣義表(generalizedlist)是線性表的推廣，有時(shí)也稱為列表（lists，用復(fù)數(shù)形式以示與統(tǒng)稱的表list的區(qū)別）。廣泛地應(yīng)用于人工智能等領(lǐng)域的LISP（表處理語言），把廣義表作為基本的數(shù)據(jù)結(jié)構(gòu)，就連程序也表示為一系列的廣義表。515.4廣義表第五十一頁，共六十四頁，編輯于2023年，星期三廣義表的邏輯結(jié)構(gòu)和數(shù)組一樣，廣義表也可以看成是線性表在下述含義上的擴(kuò)展：表中的數(shù)據(jù)元素本身也是一種數(shù)據(jù)結(jié)構(gòu)。52廣義表的存儲(chǔ)結(jié)構(gòu)第五十二頁，共六十四頁，編輯于2023年，星期三53 5.4.1廣義表的邏輯結(jié)構(gòu)廣義表一般記作：GL=(a1,a2,…,an)其中：

n

是廣義表GL

的長(zhǎng)度；

ai 可以是單個(gè)元素，也可以是廣義表，分別稱為廣義表GL

的原子和子表，習(xí)慣上用大寫字母表示廣義表的名稱，用小寫字母表示原子的名稱。GL

是廣義表(a1,a2,…,an)的名稱；1.廣義表的定義第五十三頁，共六十四頁，編輯于2023年，星期三54當(dāng)廣義表GL為非空時(shí)，稱第一個(gè)元素a1

為GL的表頭（head），其余元素組成的表(a2,a3,…,an)是GL的表尾（tail）。顯然，廣義表的定義是一個(gè)遞歸的定義，因?yàn)樵诿枋鰪V義表時(shí)又用到了廣義表的概念。第五十四頁，共六十四頁，編輯于2023年，星期三

例5-1

A=()，A

是一個(gè)空表，它的長(zhǎng)度為零。

例5-2

B=(e)，B

只有一個(gè)原子e，它的長(zhǎng)度為1。

例5-3

C=(a,(b,c,d))，C

的長(zhǎng)度為2，兩個(gè)元素分別為原子a

和子表(b,c,d)。

例5-4

D=(A,B,C)，D

的長(zhǎng)度為3，三個(gè)元素分別為A、B和C，都是廣義表。顯然，將上面所述三個(gè)子表的值代入以后，則有D=((),(e),(a,(b,c,d)))。

例5-5

E=(a,E)，這是一個(gè)遞歸表，它的長(zhǎng)度為2，E相當(dāng)于一個(gè)無限的廣義表E=(a,(a,(a,…)))。552.廣義表的三個(gè)重要結(jié)論第五十五頁，共六十四頁，編輯于2023年，星期三從上述定義和例子推出如下廣義表的三個(gè)重要結(jié)論(1)廣義表的元素可以是子表，而子表的元素還可以是子表，…。由此，廣義表是一個(gè)多層次結(jié)構(gòu)。(2)廣義表可以為其他廣義表所共享。例如在上述例子中，廣義表A、B

和C

為D

的子表，則在D

中可以不必列出廣義表的值，而是通過子表的名稱引用。(3)廣義表可以是一個(gè)遞歸表，即廣義表也可以是其本身的一個(gè)子表。例如廣義表E

就是一個(gè)遞歸的表。56第五十六頁，共六十四頁，編輯于2023年，星期三ecdbaBACD表示廣義表表示原子57第五十七頁，共六十四頁，編輯于2023年，星期三

和線性表相類似，