數(shù)據(jù)結(jié)構(gòu)課件第五章

第五章數(shù)組和廣義表本章學(xué)習(xí)另外兩種特殊的線性表，數(shù)組和廣義表。數(shù)組是一個(gè)數(shù)據(jù)元素的集合，元素之間具有線性關(guān)系，但是，元素可以參與多個(gè)線性關(guān)系（前面講的都是參與一個(gè)）；廣義表是一個(gè)數(shù)據(jù)元素的集合，元素之間具有線性關(guān)系，但其前驅(qū)后繼可以是一般元素，也可以是一個(gè)表?！?.1數(shù)組的邏輯結(jié)構(gòu)及操作一、數(shù)組的邏輯結(jié)構(gòu)1、數(shù)組(Array):

簡(jiǎn)單說(shuō)是數(shù)據(jù)類型相同的一組數(shù)據(jù)元素的有序集合。元素在集合中的序是由一組稱做“下標(biāo)

”的值確定的，一個(gè)數(shù)據(jù)元素稱為一個(gè)數(shù)組元素。一個(gè)數(shù)據(jù)元素的位置由多個(gè)下標(biāo)值確定，即參與多個(gè)線性關(guān)系，每個(gè)關(guān)系上都有前驅(qū)、后繼！2、數(shù)組的維數(shù):

確定一個(gè)數(shù)據(jù)元素在集合中位置的下標(biāo)的個(gè)數(shù)。3、數(shù)組的邏輯結(jié)構(gòu)定義:

1-ARRAY=(D,R)D={ai|i=c1..d1

aiD0

}

R={N}N={<ai-1,ai>|ai-1,ai

Dc1+1id1

}哇！與一般線性表完全一樣?。∩瞎?jié)課內(nèi)容回顧：1、KMP算法：NEXT值的求法-遞推方法2、改進(jìn)的NEXT值的求法：為什么改進(jìn)？3、串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——結(jié)點(diǎn)的長(zhǎng)度設(shè)置尾指針增加記錄長(zhǎng)度的字段4、存儲(chǔ)密度：它反映了什么？5、數(shù)組是特殊的線性數(shù)據(jù)結(jié)構(gòu)，特殊在什么地方？6、數(shù)組數(shù)據(jù)結(jié)構(gòu)的邏輯定義§5.1數(shù)組的邏輯結(jié)構(gòu)及操作2-ARRAY=(D,R)D={aij|i=c1..d1,j=c2..d2

aijD0

}

R={ROW,COL}ROW={<aij,aij+1>|aij,aij+1

Dc1id1c2jd2-1}COL={<aij,ai+1j>|aij,ai+1j

Dc1id1-1c2jd2

}3-ARRAY=(D,R)

D={aijk|i=c1..d1,j=c2..d2k=c3..d3

aijkD0

}

R={R1,R2,R3}R1={<aijk,aijk+1>|aijk,aijk+1Dc1id1c2jd2c3kd3-1}R2={<aijk,aij+1k>|aijk,ai+1jk

Dc1id1c2jd2-1c3kd3

}R3={<aijk,ai+1jk>|aijk,ai+1jk

Dc1id1-1c2jd2c3kd3

}§5.1數(shù)組的邏輯結(jié)構(gòu)及操作

n-ARRAY=(D,R)D={aj1j2...jn|ji=ci..di

i=1,2...naj1j2...jnD0

}

R={R1,R2,...,Rn}

Ri={<aj1j2...ji...jn,aj1j2...ji+1...jn>|aj1j2...jn

D

ck

jk

dk

1knki

ci

ji

di-1

}ai-1

aiai+1aijjiai-1jai+1jaij+1aij-1aijkijkaij-1kaij+1kai-1jkai+1jkaijk-1aijk+1一維數(shù)組二維數(shù)組三維數(shù)組上節(jié)課內(nèi)容回顧：1、KMP算法：NEXT值的求法-遞推方法2、改進(jìn)的NEXT值的求法：為什么改進(jìn)？3、串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——結(jié)點(diǎn)的長(zhǎng)度設(shè)置尾指針增加記錄長(zhǎng)度的字段4、存儲(chǔ)密度：它反映了什么？5、數(shù)組是特殊的線性數(shù)據(jù)結(jié)構(gòu)，特殊在什么地方？6、數(shù)組數(shù)據(jù)結(jié)構(gòu)的邏輯定義練習(xí)：已知主串=‘a(chǎn)bcaabbabcabaacbacba’，模式串=‘a(chǎn)bcabaa’，請(qǐng)完成：1、計(jì)算采用BF算法匹配時(shí)的比較次數(shù)；2、計(jì)算模式的失敗函數(shù)值(next)；3、計(jì)算模式的改進(jìn)的失敗函數(shù)值(nextval)；4、計(jì)算采用KMP算法匹配時(shí)的比較次數(shù)；答案：1、（5+1+1+2+3+1+1+7）=212、01112323、01101324、17（16）§5.1數(shù)組的邏輯結(jié)構(gòu)及操作注意：（1）數(shù)組中每個(gè)數(shù)據(jù)元素受多個(gè)線性關(guān)系制約，元素在每個(gè)線性關(guān)系上都有前驅(qū)、后繼。（2）一個(gè)n維數(shù)組可以看作一個(gè)線性表，其每個(gè)數(shù)據(jù)元素是一個(gè)n-1維的數(shù)組。4、數(shù)組的操作:

初始化：

Create(A)

賦值：Store(A,Index,value)取一元素：Get(A,Index)§5.1數(shù)組的邏輯結(jié)構(gòu)及操作二、數(shù)組的ADT描述

ADTArray

datastructure:n-ARRAY=(D,R)D={aj1j2...jn|ji=ci..dii=1,2...naj1j2...jnD0

}

R={R1,R2,...,Rn}

Ri={<aj1j2...ji...jn,aj1j2...ji+1...jn>|aj1j2...jn

D

ck

jk

dk

1knkici

ji

di-1}

operations:Create(A);Store(A,Index,value);Get(A,Index)END§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)一、數(shù)組的順序存儲(chǔ)結(jié)構(gòu)

由于數(shù)組數(shù)據(jù)結(jié)構(gòu)的運(yùn)算較少，且沒(méi)有插入、刪除運(yùn)算，所以一般均采用順序存儲(chǔ)結(jié)構(gòu)。

在所有的高級(jí)語(yǔ)言中，數(shù)組ADT已經(jīng)作為一個(gè)標(biāo)準(zhǔn)數(shù)據(jù)類型物理實(shí)現(xiàn)了！我們僅僅是了解一下它的存儲(chǔ)結(jié)構(gòu)。1、存儲(chǔ)方式：同一般線性表的順序存儲(chǔ)結(jié)構(gòu)完全相同。用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)組的各個(gè)元素。但是：在一般線性表時(shí)是第i個(gè)存儲(chǔ)單元存儲(chǔ)第i個(gè)數(shù)據(jù)元素(由于只有一個(gè)線性關(guān)系)。那么，在數(shù)組中第i存儲(chǔ)單元存儲(chǔ)哪個(gè)數(shù)據(jù)元素呢？因?yàn)樵匚恢檬芏鄠€(gè)線性關(guān)系的制約（即哪個(gè)關(guān)系上的順序號(hào)？？）§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)顯然，在數(shù)組中，數(shù)據(jù)元素的位置是由數(shù)據(jù)元素在各個(gè)關(guān)系上的位置確定的，即下標(biāo)值(i1,i2,...ik);那么，那個(gè)關(guān)系先，那個(gè)關(guān)系后？因此數(shù)組的順序存儲(chǔ)結(jié)構(gòu)分為行主序存儲(chǔ)和列主序存儲(chǔ)。假設(shè)數(shù)組各維的界為:(c1..d1,c2..d2,......,ck..dk)則數(shù)組的元素個(gè)數(shù)

n=(d1-c1+1)*(d2-c2+1)...*(dk-ck+1)每個(gè)數(shù)據(jù)元素占用各l

空間，則占用空間為：

size=n*l==(d1-c1+1)*(d2-c2+1)...*(dk-ck+1)*l

lsizen§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)那么n個(gè)元素以什么樣的順序依次存儲(chǔ)到空間中去呢？即存儲(chǔ)空間的第i個(gè)位置存儲(chǔ)哪個(gè)元素呢？我們先想想二維數(shù)組，顯然，一個(gè)元素按行去數(shù)和按列去數(shù)，數(shù)出來(lái)的序號(hào)是不同的，即可以有兩種不同的存儲(chǔ)順序，a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45例：顯然，存儲(chǔ)它占用20個(gè)空間單元！那么如何存儲(chǔ)呢？a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45a11a21a31a41a12a22a32a42a13a23a33a43a14a24a34a44a15a25a35a45§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)行主序存儲(chǔ)：

首先是所有第一個(gè)下標(biāo)為c1

的數(shù)據(jù)元素，然后是所有第一個(gè)下標(biāo)為c1+1的所有元素......;第一個(gè)下標(biāo)相同的元素，按第二個(gè)下標(biāo)從小到大排列，第二個(gè)下標(biāo)相同的元素，按第三個(gè)下標(biāo)從小到大排列......列主序存儲(chǔ)：

首先是所有最后一個(gè)下標(biāo)為ck

的數(shù)據(jù)元素，然后是所有最后一個(gè)下標(biāo)為ck+1的所有元素......;最后一個(gè)下標(biāo)相同的元素，按倒數(shù)第二個(gè)下標(biāo)從小到大排列，倒數(shù)第二個(gè)下標(biāo)相同的元素，按倒數(shù)第三個(gè)下標(biāo)從小到大排列......§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)例如：數(shù)組A[0..3,1..2,3..6]

元素個(gè)數(shù)n=(3-0+1)*(2-1+1)*(6-3+1)=4*2*4=32

行主序排列：a[0,1,3]a[0,1,4]a[0,1,5]a[0,1,6]a[0,2,3]a[0,2,4]a[0,2,5]a[0,2,6]第1個(gè)下標(biāo)為0第2個(gè)下標(biāo)為1第2個(gè)下標(biāo)為2a[1,1,3]a[1,1,4]a[1,1,5]a[1,1,6]a[1,2,3]a[1,2,4]a[1,2,5]a[1,2,6]第1個(gè)下標(biāo)為1第2個(gè)下標(biāo)為1第2個(gè)下標(biāo)為2§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)a[2,1,3]a[2,1,4]a[2,1,5]a[2,1,6]a[2,2,3]a[2,2,4]a[2,2,5]a[2,2,6]第1個(gè)下標(biāo)為2第2個(gè)下標(biāo)為1第2個(gè)下標(biāo)為2§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)a[3,1,3]a[3,1,4]a[3,1,5]a[3,1,6]a[3,2,3]a[3,2,4]a[3,2,5]a[3,2,6]第1個(gè)下標(biāo)為3第2個(gè)下標(biāo)為1第2個(gè)下標(biāo)為2§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)

列主序排列：

a[0,1,3]a[1,1,3]a[2,1,3]a[3,1,3]a[0,2,3]a[1,2,3]a[2,2,3]a[3,2,3]最后1個(gè)下標(biāo)為3倒數(shù)第2個(gè)下標(biāo)為1倒數(shù)第2個(gè)下標(biāo)為2§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)a[0,1,4]a[1,1,4]a[2,1,4]a[3,1,4]a[0,2,4]a[1,2,4]a[2,2,4]a[3,2,4]最后1個(gè)下標(biāo)為4倒數(shù)第2個(gè)下標(biāo)為1倒數(shù)第2個(gè)下標(biāo)為2§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)a[0,1,5]a[1,1,5]a[2,1,5]a[3,1,5]a[0,2,5]a[1,2,5]a[2,2,5]a[3,2,5]最后1個(gè)下標(biāo)為5倒數(shù)第2個(gè)下標(biāo)為1倒數(shù)第2個(gè)下標(biāo)為2§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)a[0,1,6]a[1,1,6]a[2,1,6]a[3,1,6]a[0,2,6]a[1,2,6]a[2,2,6]a[3,2,6]最后1個(gè)下標(biāo)為6倒數(shù)第2個(gè)下標(biāo)為1倒數(shù)第2個(gè)下標(biāo)為2§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)for(i1=c1;i1<=d1;i1++)

for(i2=c2;i2<=d2;i2++)for(i3=c3;i3<=d3;i3++)…………for(ik=ck;ik<=dk;ik++)

a[i1,i2,i3,…,ik]for(ik=ck;ik<=dk;ik++)…………

for(i2=c2;i2<=d2;i2++)for(i1=c1;i1<=d1;i1++)

a[i1,i2,i3,…,ik]2、數(shù)據(jù)元素的存儲(chǔ)位置

假設(shè)數(shù)組的每個(gè)元素占用l個(gè)存儲(chǔ)單元，第1個(gè)數(shù)據(jù)元素的存儲(chǔ)地址已知，根據(jù)順序存儲(chǔ)的特點(diǎn)，可以容易地求出任意一個(gè)元素的存儲(chǔ)地址！假設(shè)用LOC(a)表示元素a的存儲(chǔ)地址§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)一維數(shù)組：A[c1..d1]

行主序：LOC(a[i])=LOC(a[c1])+(i-c1)*l

列主序：LOC(a[i])=LOC(a[c1])+(i-c1)*la[c1]a[i]............二維數(shù)組：A[c1..d1,c2..d2]

行主序：

LOC(a[i,j])=LOC(a[c1,c2])+(d2-c2+1)*(i-c1)*l+(j-c1)*l

列主序：

LOC(a[i,j])=LOC(a[c1,c2])+(d1-c1+1)*(j-c2)*l+(i-c1)*l§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)aijijc1d1c2d2jaijic1d1c2d2三維數(shù)組：A[c1..d1,c2..d2,c3..d3]

行主序：

LOC(a[i,j,k])=LOC(a[c1,c2,c3])+(d2-c2+1)*(d3-c3+1)*(i-c1)*l+(d3-c3+1)*(j-c2)*l+(k-c3)*l

列主序：

LOC(a[i,j,k])=LOC(a[c1,c2,c3])+(d1-c1+1)*(d2-c2+1)*(k-c3)*l+(d2-c2+1)*(j-c2)*l+(i-c1)*l

§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)ijkaijkijkaijk行主序列主序§5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)3、特點(diǎn)

隨機(jī)存取，即存取任何元素花的時(shí)間相同。二、數(shù)組在順序存儲(chǔ)結(jié)構(gòu)下各運(yùn)算的虛擬實(shí)現(xiàn)4、實(shí)現(xiàn)

根據(jù)數(shù)組說(shuō)明，得到數(shù)組的元素個(gè)數(shù)，及元素類型（每個(gè)元素占用空間），然后，分配連續(xù)空間，空間的首地址存儲(chǔ)在數(shù)組名中。

已知要訪問(wèn)的元素的下標(biāo)，則根據(jù)存儲(chǔ)方式可以計(jì)算出該元素的存儲(chǔ)地址（根據(jù)前面的公式），于是可以存取該元素。§5.3矩陣及特殊矩陣一、矩陣的邏輯結(jié)構(gòu)1、矩陣(Matrix):簡(jiǎn)單說(shuō)就是一個(gè)二維數(shù)組，即是一個(gè)m行、n列的表。它通常用來(lái)組織數(shù)據(jù)。Matrix=(D,R)D={aij|i=1..m,j=1..naijD0

}

R={ROW,COL}ROW={<aij,aij+1>|aij,aij+1

D1im1jn-1}COL={<aij,ai+1j>|aij,ai+1j

D1im-11jn}2、矩陣的操作:

轉(zhuǎn)置加法減法乘法略二、矩陣ADT三、矩陣的存儲(chǔ)結(jié)構(gòu)及操作的實(shí)現(xiàn)§5.3矩陣及特殊矩陣略四、特殊矩陣的存儲(chǔ)及操作的實(shí)現(xiàn)1、特殊矩陣:具有某種特征的矩陣，例如：元素分布有規(guī)律（值相同或零）、零元素很多等。

對(duì)稱矩陣：m(i,j)=m(j,i)

對(duì)角矩陣:當(dāng)i<>j時(shí)m(i,j)=0

上三角矩陣：當(dāng)i>j時(shí)m(i,j)=0

§5.3矩陣及特殊矩陣

對(duì)于一個(gè)矩陣結(jié)構(gòu)顯然用一個(gè)二維數(shù)組來(lái)表示是非常恰當(dāng)?shù)?，但在有些情況下，比如常見(jiàn)的一些特殊矩陣，如三角矩陣、對(duì)稱矩陣、帶狀矩陣、稀疏矩陣等，從節(jié)約存儲(chǔ)空間的角度考慮，這種存儲(chǔ)是不太合適的。下面從這一角度來(lái)考慮這些特殊矩陣的存儲(chǔ)方法。

下三角矩陣：當(dāng)i<j時(shí)m(i,j)=0

三對(duì)角矩陣:當(dāng)|i-j|>1時(shí)m(i,j)=0

帶狀矩陣(帶寬為k):當(dāng)|i-j|>k時(shí)m(i,j)=0

123423453456456710000200003000041234034500560007100023003450456712002340045600671230023450345670567800789k=2§5.3矩陣及特殊矩陣00000100200001000000010000010000020§5.3矩陣及特殊矩陣2、特殊矩陣的存儲(chǔ):

特殊矩陣可以采用二維數(shù)組同樣的存儲(chǔ)方式，占用空間維mxn，但是，由于其特殊性，空間效率不高（存儲(chǔ)了許多零或相同的值），為此，它們一般采用特殊的存儲(chǔ)方式(相同值只存放一個(gè)，零元素不存儲(chǔ)).那么，矩陣的運(yùn)算就變的復(fù)雜了！！3、對(duì)稱矩陣、上三角矩陣、下三角矩陣的存儲(chǔ):

用一維數(shù)組存放，原來(lái)占用空間n*n，現(xiàn)在為n*(n+1)/2.....................aijaijk要實(shí)現(xiàn)矩陣的操作，必須知道(i,j)與k的關(guān)系！自己分析§5.3矩陣及特殊矩陣10002300456078910

10002300456078910原來(lái)12345678910

現(xiàn)在A、矩陣越大，空間節(jié)省越多??！B、有行主序、列主序之分?。ú僮鲗?shí)現(xiàn)自己寫(xiě)出）§5.3矩陣及特殊矩陣4、帶狀矩陣（三對(duì)角矩陣）的存儲(chǔ):

根據(jù)其特點(diǎn)，每行最多有2K+1個(gè)非0元素，我們按每行2K+1個(gè)元素存儲(chǔ)（還有空間浪費(fèi)?。?。2k+112n.............分配空間大小=[(2k+1)*n-2k]*l節(jié)省空間大小={n*n-[(2k+1)*n-2k]}*l還未利用空間=2*[(k-1)+...+2+1]=k*(k+1)§5.3矩陣及特殊矩陣地址對(duì)應(yīng)關(guān)系：(行主序)

LOC(a[1,1])=baseLOC(a[i,i])=LOC(a[i-1,i-1])+(2k+1)*l=LOC(a[i-2,i-2])+2*{(2k+1)*l}=......=LOC(a[1,1])+(i-1)*(2k+1)*l=base+(i-1)*(2k+1)*laiiai-1i-1ai-2i-2a11............i-1

LOC(a[i,j])=LOC(a[i,i])+(j-i)*l=base+(i-1)*(2k+1)*l+(j-i)*l

§5.3矩陣及特殊矩陣?yán)纾?/p>

n=6k=2123000456700891011120013141516170018192021000222324計(jì)算：（1）占用空間個(gè)數(shù)（2）節(jié)省空間個(gè)數(shù)（3）未利用空間個(gè)數(shù)（4）a55、a66、a64、a45的存儲(chǔ)序號(hào)“五一”過(guò)完了，快樂(lè)中學(xué)習(xí)了嗎？上次的課講到哪兒了？上節(jié)課內(nèi)容回顧：1、數(shù)組的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)，如何存？行主序，列主序元素的存儲(chǔ)位置的計(jì)算：基地址已知，計(jì)算任何元素的存儲(chǔ)地址a[i]a[i,j]a[i,j,k]……上節(jié)課內(nèi)容回顧：2、特殊矩陣存儲(chǔ)的目的是什么？節(jié)省存儲(chǔ)空間。但是，有三個(gè)問(wèn)題注意：（1）如何存儲(chǔ)？有行主序、列主序之分嗎？（2）是不是任何情況下都可以節(jié)省空間？（3）操作變的復(fù)雜了，如何得到地址變換關(guān)系？5、稀疏矩陣的存儲(chǔ):

稀疏矩陣：零元素比較多，且分布不均勻§5.3矩陣及特殊矩陣分析：根據(jù)稀疏矩陣的特點(diǎn)，如果存儲(chǔ)所有元素，顯然存放了很多0，空間利用率低！我們可以考慮只存放非0元素，但如果僅僅存放一個(gè)元素值是不行的，因?yàn)椴荒艽_定它在矩陣中的位置，所以必須存儲(chǔ)其下標(biāo)。所以：每個(gè)非0元素可以用一個(gè)三元組表示(i,j,v)，一個(gè)稀疏矩陣就是這樣一些三元組的集合，考慮它們?cè)诰仃囍械奈恢?，稀疏矩陣就是一個(gè)以三元組為數(shù)據(jù)元素的線性表（線性關(guān)系可以是行或列）?！?.3矩陣及特殊矩陣?yán)缬邢∈杈仃嚕?010200000100000010-1可抽象為線性表：按行：((1,3,1),(1,52),(3,1,1),(4,3,1),(4,5,-1))

按列：((3,1,1),(1,3,1),(4,3,1),(1,5,2),(4,5,-1))線性表的存儲(chǔ)我們已經(jīng)介紹了，有順序和鏈?zhǔn)絻煞N，所以稀疏矩陣也有兩種存儲(chǔ)形式！§5.3矩陣及特殊矩陣（1）稀疏矩陣三元組順序存儲(chǔ):

......ijvmaxnumlen§5.3矩陣及特殊矩陣稀疏矩陣三元組順序存儲(chǔ)的虛擬實(shí)現(xiàn):

defineSMAX1024/*一個(gè)足夠大的數(shù)*/typedefstruct

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

datatypev;/*非零元素值*/}SPNode;/*三元組類型*/typedefstruct

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

SPNodedata[SMAX];/*三元組表*/}SPMatrix;/*三元組表的存儲(chǔ)類型*/§5.3矩陣及特殊矩陣（2）稀疏矩陣三元組的鏈?zhǔn)酱鎯?chǔ)——十字鏈表:

每個(gè)三元組用一個(gè)如下的結(jié)點(diǎn)存儲(chǔ)：rowcolval

downrightrow,col:非0元素的行、列值val:非0元素的值down:指向同列的下一個(gè)非0元素結(jié)點(diǎn)right:指向同行的下一個(gè)非0元素結(jié)點(diǎn)§5.3矩陣及特殊矩陣結(jié)點(diǎn)的結(jié)構(gòu)定義如下:

typedefstructnode{introw,col;

structnode*down,*right;

unionv_next{datatypev;

structnode*next;}}MNode，*MLink;

§5.3矩陣及特殊矩陣所以：所有非0元素的結(jié)點(diǎn)按行看或按列看都是一些單鏈表！............^^§5.3矩陣及特殊矩陣............^^每個(gè)單鏈表加上頭結(jié)點(diǎn)（行、列），且構(gòu)成環(huán)000000§5.3矩陣及特殊矩陣............^^000000頭結(jié)點(diǎn)形成鏈表，加一個(gè)頭結(jié)點(diǎn)，且形成環(huán)。mnht§5.3矩陣及特殊矩陣0010200000100000010-1例如：ht00000000004513115231143145-1§5.3矩陣及特殊矩陣矩陣操作肯定比原來(lái)復(fù)雜了！實(shí)習(xí)題三：稀疏矩陣處理§5.4廣義表邏輯結(jié)構(gòu)及操作一、廣義表的邏輯結(jié)構(gòu)1、廣義表(Lists、Multilist):

它是一個(gè)特殊的線性表。前面我們學(xué)習(xí)的線性表，無(wú)論操作特殊（棧、隊(duì)列），元素特殊（字符串），參與多個(gè)線性關(guān)系（數(shù)組）等，有一個(gè)共同點(diǎn)：數(shù)據(jù)元素都具有相同的類型，如果允許數(shù)據(jù)元素有可以是線性表，這就是廣義表！

在廣義表中，數(shù)據(jù)元素可以是下面類型之一：?jiǎn)卧兀ㄔ覣tom）：某數(shù)據(jù)對(duì)象的一個(gè)數(shù)據(jù)元素；子表（Sublist）：一些數(shù)據(jù)元素構(gòu)成的線性表；Lists=(D,R)D={di|i=1,2,...,nn

0d0D0或d0Lists}

R={LR}LR={<di-1,di>|di-1,di

D2in}§5.4廣義表邏輯結(jié)構(gòu)及操作2、有關(guān)術(shù)語(yǔ):長(zhǎng)度：元素個(gè)數(shù)n(注意子表是一個(gè)數(shù)據(jù)元素)；單元素：一般用小寫(xiě)字母表示；

子表：一般用大寫(xiě)字母表示；表頭：d1

表尾：除去d1

后剩余元素組成的表深度：簡(jiǎn)單說(shuō)就是表的嵌套層次，定義為：

LS=(d1,d2,...,dn)depth(LS)=max{depth(d1),depth(d2),...,depth(dn)}+10di

是單元素

depth(di)=1di

是空表§5.4廣義表邏輯結(jié)構(gòu)及操作⑴廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表，…。3、廣義表的重要性質(zhì)：⑵廣義表可以是遞歸的表。廣義表的定義并沒(méi)有限制元素的遞歸，即廣義表也可以是其自身的子表。⑶廣義表可以為其他表所共享?！?.4廣義表邏輯結(jié)構(gòu)及操作4、操作:初始化求長(zhǎng)度取表頭取表尾求深度插入刪除復(fù)制

略二、廣義表ADT§5.4廣義表邏輯結(jié)構(gòu)及操作二、廣義表舉例

A=()長(zhǎng)度0深度1

B=(e)長(zhǎng)度1深度1

C=(a,(b,c,d))長(zhǎng)度2深度2

D=(A,B,C)長(zhǎng)度3深度3

E=(a,E)長(zhǎng)度2深度

depth(B)=max{0}+1depth(C)=max{0,max{0,0,0}+1}+1depth(D)=max{1,1,2}+1§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)一、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)之一(n個(gè)并列元素)由于廣義表的數(shù)據(jù)元素又可能是線性表，采用順序存儲(chǔ)結(jié)構(gòu)很難存儲(chǔ)，所以一般采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。1、存儲(chǔ)方式：用任意的存儲(chǔ)單元存儲(chǔ)廣義表的數(shù)據(jù)元素在存儲(chǔ)每個(gè)“元素”的同時(shí)，還存儲(chǔ)其后繼元素的信息。其中，對(duì)于單元素同一般線性表，而對(duì)于子表類數(shù)據(jù)元素用另外一個(gè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)，在該鏈表中存儲(chǔ)其頭指針（子表的存儲(chǔ)同上面一樣，遞歸描述）存儲(chǔ)單元素：存儲(chǔ)子表元素：datanexthpnexttag=0tag=1§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)其中：next：是后繼元素指針

data：是單元素的元素值

hp：是子表元素的頭指針

tag：是標(biāo)志域，區(qū)分是什么結(jié)點(diǎn)（單元素、子表）2、特點(diǎn)：每個(gè)子表都有自己的存儲(chǔ)結(jié)構(gòu)。3、虛擬實(shí)現(xiàn)：

§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)typedefenum{ATOM,LIST}Elemtag;/*ATOM=0：?jiǎn)卧?；LIST=1：子表*/typedefstructGLENode

{Elemtagtag;/*標(biāo)志域，用于區(qū)分元素結(jié)點(diǎn)和表結(jié)點(diǎn)*/

union{/*元素結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分*/

datatypedata;/*元素結(jié)點(diǎn)的值域*/

structGLENode*hp;/*表結(jié)點(diǎn)的表頭指針*/};

structGLENode*next;/*指向下一個(gè)結(jié)點(diǎn)*/}*EGList;/*廣義表類型*/§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)4、舉例：A=()1^^AB=(e)1^B0e^C=(b,c,d)1^C000d^

bc§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)D=(a,(b,c,d))1^D01

a^000d^

bc§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)E=((),(e)(a,(b,c,d)))1^01

a^000d^

bc1^E1^10e^§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)F=(a,F)1^F0a1

^1^F0a二者相同嗎？§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)之二（分解為表頭表尾）1、存儲(chǔ)方式：用任意的存儲(chǔ)單元存儲(chǔ)廣義表的數(shù)據(jù)元素由于數(shù)據(jù)元素的不同，用兩類結(jié)點(diǎn)存儲(chǔ)不同的元素。單元素的存儲(chǔ)只要存儲(chǔ)其元素值就可以了；而對(duì)于子表元素，可以劃分為表頭和表尾分別存儲(chǔ)（因?yàn)橐粚?duì)表頭和表尾可以唯一確定一廣義表）。存儲(chǔ)單元素：存儲(chǔ)子表元素：datahptptag=0tag=1§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)其中data：是單元素的元素值

hp：是指向表頭元素結(jié)點(diǎn)（單元素？子表？）

tp：是指向表尾元素結(jié)點(diǎn)（單元素？子表？）

tag：是標(biāo)志域，區(qū)分是什么結(jié)點(diǎn)（單元素、子表）2、特點(diǎn)：易分清元素所在層次3、虛擬實(shí)現(xiàn)：

§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)typedefenum{ATOM,LIST}Elemtag;/*ATOM=0：?jiǎn)卧?；LIST=1：子表*/typedefstructGLENode{Elemtagtag;/*標(biāo)志域，用于區(qū)分元素結(jié)點(diǎn)和表結(jié)點(diǎn)*/

union{/*元素結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分*/

datatypedata;/*元素結(jié)點(diǎn)的值域*/

structGLENode*hp;/*表結(jié)點(diǎn)的表頭指針*/};

structGLENode*tp;/*指向下一個(gè)結(jié)點(diǎn)*/}*EGList;/*廣義表類型*/§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)4、舉例：A=()B=(e)1^B0eC=(b,c,d)A1

C0

d110

c0

b^§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)D=(a,(b,c,d))1

0

d110

c0

b^1

1

^0aD§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)E=((),(e)(a,(b,c,d)))1

0

d110

c0

b^1

1

^0a1

1

^1

0e1

^E^§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)F=(a,F)1F0a1

^1F0a二者相同嗎？不一樣的?。『笳卟徽_。三、幾種操作的虛擬實(shí)現(xiàn)（采用第2種存儲(chǔ)結(jié)構(gòu)）§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)1、廣義表的取頭、取尾GListHead(GListls){ifls->tag==1thenp=ls->hp;returnp;}GListTail(GListls){ifls->tag==1thenp=ls->tp;returnp;}§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)2、求深度intDepth(GListls){if(!ls)return1;/*空表深度為1*/

if(ls->tag==0)return0;/*單元素深度為0*/

for(max=0,p=ls;p;p=p->ptr.tp){dep=Depth(p->ptr.hp);/*求以p->ptr.hp尾頭指針的子表深度*/

if(dep>max)max=dep;}returnmax+1;/*非空表的深度是各元素的深度的最大值加1*/}§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)3、復(fù)制intCopyGList(GListls1,GList*ls2){if(!ls1)*ls2=NULL;/*復(fù)制空表*/

else{if(!(*ls2=(Glist)malloc(sizeof(Glnode))))return0;/*建表結(jié)點(diǎn)*/(*ls2)->tag=ls1->tag;if(ls1->tag==0)(*ls2)->data=ls1->data;/*復(fù)制單元素*/

else{CopyGList(&((*ls2)->ptr.hp),ls1->ptr.hp);/*復(fù)制廣義表ls1->ptr.hp的一個(gè)副本*/

CopyGList(&((*ls2)->ptr.tp),ls1->ptr.tp);/*復(fù)制廣義表ls1->ptr.tp的一個(gè)副本*/}}

return1;}練習(xí)1、假設(shè)廣義表為：D=(a,b,D),則其長(zhǎng)度為多少？深度為多少？3

2、廣義表A=((()))的深度是多少？表頭？表尾？3、廣義表A=((x,(a,b)),(x,(a,b),y))，則運(yùn)算

Head(Head(Tail(A)))是什么？x§5.廣義表的應(yīng)用

——m元多項(xiàng)式的表示（存儲(chǔ)）前面，我們討論過(guò)一元n次多項(xiàng)式，多項(xiàng)式的一項(xiàng)可以用（系數(shù)，指數(shù)）來(lái)表示。對(duì)于m元多項(xiàng)式，每一項(xiàng)最多有m個(gè)變?cè)?，每個(gè)變?cè)加兄笖?shù)，所以一項(xiàng)表示為：

(系數(shù)，指數(shù)1，指數(shù)2，...，指數(shù)m)但是每一項(xiàng)的變?cè)遣灰粯佣嗟?，如果都按m個(gè)變?cè)鎯?chǔ)項(xiàng)，則空間利用率不高，如果按實(shí)際變?cè)獢?shù)存儲(chǔ)則結(jié)點(diǎn)大小不同，操作不便！例如：p(x,y,z)=2x5yz-y2z4+z32511-10241003^2511-12413后一種存儲(chǔ)方式還有什么問(wèn)題？§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)為了方便，我們可以對(duì)m元多項(xiàng)式進(jìn)行變換：

先分解出一個(gè)主變?cè)?，然后再分解出第二個(gè)主變?cè)?..，對(duì)于一個(gè)主變?cè)獊?lái)說(shuō)，可以看作一個(gè)一元多項(xiàng)式，只不過(guò)其系數(shù)又是m-1元多項(xiàng)式！例如：P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15=(x10y3+2x6y3+3x5y2)z2+(x4y4+6x3y4+2y)z+15=((x10+2x6)y3+3x5y2)z2+((x4+6x3)y4+2y)z+15§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)P(x,y,z)=(x10y3+2x6y3+3x5y2)z2+(x4y4+6x3y4+2y)z+15

P=z((A,2),(B,1),(15,0))

A=y((C,3),(D,2))

C=x((1,10),(2,6))

E=x((1,4),(6,3))A(x,y)=(x10+2x6)y3+3x5y2B(x,y)=(x4+6x3)y4+2yB=y((E,4),(F,1))C(x)=x10+2x6D(x)=3x5E(x)=x4+6x3F(x)=2D=x((3,5))F=x((2,0))A、B、C、D、E、F都是子表，單元素是（系數(shù)，指數(shù)）§5.5廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作的虛擬實(shí)現(xiàn)如果采用“后繼”的存儲(chǔ)方式，如何存儲(chǔ)？請(qǐng)考慮！至此，第五章結(jié)束小結(jié)：

ADT名稱共性特殊性

一般線性表元素之間線性關(guān)系無(wú)