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

數(shù)據(jù)結(jié)構(gòu)第五章數(shù)組和廣義表第1頁(yè)，共48頁(yè)，2023年，2月20日，星期六

第五章

數(shù)組和廣義表

5.1數(shù)組的定義5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)5.3矩陣的壓縮存儲(chǔ)5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)第2頁(yè)，共48頁(yè)，2023年，2月20日，星期六3

前4章介紹的數(shù)據(jù)結(jié)構(gòu)共同特點(diǎn)：▲都屬于線性數(shù)據(jù)結(jié)構(gòu)；▲每種數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，都作為原子數(shù)據(jù)，不再進(jìn)行分解；本章討論的兩種數(shù)據(jù)結(jié)構(gòu)：數(shù)組和廣義表，其共同特點(diǎn)是：▲從邏輯結(jié)構(gòu)上看它們，可看成是線性結(jié)構(gòu)的一種擴(kuò)展；▲數(shù)據(jù)元素本身也是一個(gè)數(shù)據(jù)結(jié)構(gòu)；第五章

數(shù)組和廣義表第3頁(yè)，共48頁(yè)，2023年，2月20日，星期六4

一、數(shù)組的定義(1)數(shù)組的抽象數(shù)據(jù)類(lèi)型定義

ADTArray

{數(shù)據(jù)對(duì)象：D＝{aj1,j2,…,ji,…,jn|ji=0,…,bi-1,i=1,2,…,n(n>0)稱(chēng)為數(shù)組的維數(shù),bi是數(shù)組第i維的長(zhǎng)度，ji是數(shù)組元素的第i維下標(biāo)}

5．1數(shù)組的定義

數(shù)據(jù)關(guān)系：R＝{R1,R2,…

,Rn}第4頁(yè)，共48頁(yè)，2023年，2月20日，星期六5

Ri＝{<aj1…ji…jn,aj1…ji+1

…jn>|0≤jk≤bk-1,1≤k≤n

且ki,0≤ji≤bi-2,aj1…ji…jn,aj1…ji+1

…jn∈D，

i=2,…

,n}

如二維數(shù)組的定義:數(shù)據(jù)對(duì)象:D={aij|0≤i≤b1-1,0≤j≤b2-1}

數(shù)據(jù)關(guān)系:R={ROW,COL}ROW={<ai,j,ai+1,j>|0≤i≤b1-2,0≤j≤b2-1}COL={<ai,j,ai,j+1>|0≤i≤b1-1,0≤j≤b2-2}

第5頁(yè)，共48頁(yè)，2023年，2月20日，星期六6

(2)

二維數(shù)組的解釋a00

a01…

a0n-1a10

a11…

a1n-1┋┋┋am-10

am-11

…

am-1n-1

二維數(shù)組中的每個(gè)元素都受兩個(gè)線性關(guān)系的約束，即行關(guān)系和列關(guān)系，在每個(gè)關(guān)系中，每個(gè)元素aij都有且僅有一個(gè)直接前趨，都有且僅有一個(gè)直接后繼。在行關(guān)系中

aij直接前趨是aij-1aij直接后繼是aij+1在列關(guān)系中

aij直接前趨是ai-1jaij直接后繼是ai+1j第6頁(yè)，共48頁(yè)，2023年，2月20日，星期六7

A=(0,1,2,3,

4,……,p)

p=m-1或n-1

其中每一個(gè)數(shù)據(jù)元素j

是一個(gè)列向量的線性表

j=（a0j,

a1j,a2j,

a3j,……

,am-1j)0≤j≤n-1

二維數(shù)組也可看作這樣的線性表：其每一個(gè)數(shù)據(jù)元素也是一個(gè)線性表。a00

a01…

a0n-1a10

a11…

a1n-1┋┋┋am-10

am-11…

am-1n-1Amn=a00

a10

┋

am-10Amn=第7頁(yè)，共48頁(yè)，2023年，2月20日，星期六8或i

是一個(gè)行向量的線性表

i=（ai0,ai1,ai2,

ai3,……

,ain-1)0≤i≤m-1Amn=((a00a01…

a0n-1),(a10a11…

a1n-1),(am-10am-11…

am-1n-1))(3)C語(yǔ)言中二維數(shù)組類(lèi)型的一種定義

typedefelemtypeArray2[m][n];

等價(jià)于

typedefelemtypeArray1[n];typedefArray1Array2[m];

同理，可以用n-1維數(shù)組的數(shù)據(jù)類(lèi)型來(lái)定義n維數(shù)組。第8頁(yè)，共48頁(yè)，2023年，2月20日，星期六9一、數(shù)組的順序表示和實(shí)現(xiàn)

(1)類(lèi)型特點(diǎn)

①只有引用型操作，一般不作插入或刪除操作；

②數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是一個(gè)一維的結(jié)構(gòu)。(2)兩個(gè)策略----兩種順序映象的方式①以行序?yàn)橹餍?低下標(biāo)優(yōu)先)；②以列序?yàn)橹餍?高下標(biāo)優(yōu)先)。5．2數(shù)組的順序存貯結(jié)構(gòu)第9頁(yè)，共48頁(yè)，2023年，2月20日，星期六10a00

a01…

a0n-1a10

a11…

a1n-1┋┋┋am-10

am-11…

am-1n-1Amn=以行為主序的方式：a00a01a0n-1

a10a11a1n-1a(m-1)n-1amn-101n-1nn+12n-1mn-1第10頁(yè)，共48頁(yè)，2023年，2月20日，星期六1101m-1mm+12m-1nm-1a00a10am-10

a01

a11am-11

a0n-1a1n-1

amn-1以列為主序的方式：第11頁(yè)，共48頁(yè)，2023年，2月20日，星期六1212(4)存儲(chǔ)位置的公式

假設(shè)二維數(shù)組A每個(gè)元素占用L個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍虻姆绞酱鎯?chǔ)二維數(shù)組，二維數(shù)組A中任一元素ai,j的存儲(chǔ)位置為：

LOC(i,j)=LOC(0,0)+(b2×i＋j)×

L

三維數(shù)組A中任一元素ai,j,k的存儲(chǔ)位置為：

LOC(i,j,k)=LOC(0,0,0)+(b2×b3×i＋b3×j+k)×L若以列序?yàn)橹餍虻姆绞酱鎯?chǔ)二維數(shù)組，則元素aij

的存儲(chǔ)位置可由下式確定：Loc(aij)=Loc(a00)+（b1

j+i)L第12頁(yè)，共48頁(yè)，2023年，2月20日，星期六1313三維二維一維123123412a111a121a131a141a211a231a241a221a331a341a321a311a142a132a122a112a242a342第13頁(yè)，共48頁(yè)，2023年，2月20日，星期六141414推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系:P93稱(chēng)為n維數(shù)組的映象函數(shù)。數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。

▲

是隨機(jī)存儲(chǔ)結(jié)構(gòu)。三維二維一維123123412a111a121a131a141a211a231a241a221a331a341a321a311a142a132a122a112a242a342其中cn=L,ci-1=bi*ci,1<i<=n第14頁(yè)，共48頁(yè)，2023年，2月20日，星期六151515(5)結(jié)構(gòu)定義

#definemaxarraydim8typedefstruct{elemtype*base;//數(shù)組元素基址

intdim;//數(shù)組維數(shù)

int*bounds;//數(shù)組維界基址(各維容量)

int*constants;//數(shù)組映象函數(shù)常量基址｝array;第15頁(yè)，共48頁(yè)，2023年，2月20日，星期六5.3矩陣的壓縮存儲(chǔ)

一特殊矩陣的壓縮存儲(chǔ)二稀疏矩陣的壓縮存儲(chǔ)

1三元組表的存儲(chǔ)結(jié)構(gòu)2十字鏈表的存儲(chǔ)結(jié)構(gòu)第16頁(yè)，共48頁(yè)，2023年，2月20日，星期六(1)矩陣壓縮存儲(chǔ)的必要性矩陣是許多科學(xué)與工程計(jì)算問(wèn)題中常常涉及到的一種運(yùn)算對(duì)象。通常程序員是用二維數(shù)組存儲(chǔ)矩陣。由于這種存儲(chǔ)方法可以隨機(jī)地訪問(wèn)矩陣的每個(gè)元素，因而能較為容易地實(shí)現(xiàn)矩陣的各種運(yùn)算。應(yīng)用中常遇到一些階數(shù)很高的矩陣，矩陣中有許多值相同的元素或零元素。二維數(shù)組存儲(chǔ)矩陣會(huì)浪費(fèi)很多的存儲(chǔ)單元。例如，設(shè)一個(gè)10001000的矩陣中有800個(gè)非零元素，若用二維數(shù)組存儲(chǔ)需要106個(gè)存儲(chǔ)單元。因此，需要使用高效的存儲(chǔ)方法，減少數(shù)據(jù)的存儲(chǔ)量，即對(duì)原矩陣，根據(jù)數(shù)據(jù)分布特征進(jìn)行壓縮存儲(chǔ)。1、矩陣的壓縮存儲(chǔ)5．3矩陣的壓縮存儲(chǔ)第17頁(yè)，共48頁(yè)，2023年，2月20日，星期六(2)壓縮存儲(chǔ)的有關(guān)概念①

壓縮存儲(chǔ)：為多個(gè)值相同的元素分配一個(gè)存儲(chǔ)空間，對(duì)零元不分配空間。②

特殊矩陣：值相同的元素或零元素在矩陣中的分布有一定規(guī)律。③稀疏矩陣：值相同的元素或者零元素在矩陣中的分布無(wú)規(guī)律。第18頁(yè)，共48頁(yè)，2023年，2月20日，星期六a11a11a1na21a22a2nan1an2anna11a21a22a31a32a33

an1an2an3ann②壓縮存儲(chǔ)方法為每一對(duì)對(duì)稱(chēng)元分配一個(gè)存儲(chǔ)空間，則可將n2個(gè)元壓縮存儲(chǔ)到n(n+1)/2個(gè)元的空間中。(3)特殊矩陣①概念：若n階矩陣A中的元滿足：aij=aji1≤i,j≤n，則稱(chēng)為n階對(duì)稱(chēng)矩陣。a11a21

a22

a31

a32

a33

an1

an2

annk=012345n(n+1)/2-1第19頁(yè)，共48頁(yè)，2023年，2月20日，星期六③下標(biāo)對(duì)應(yīng)關(guān)系k=當(dāng)i≥j當(dāng)ij矩陣的上(下)三角(不含對(duì)角線)中的元均為常數(shù)C或0的n階矩陣(三角矩陣)，其存儲(chǔ)方法相同。例如，

a32在sa[]中的存儲(chǔ)位置是：k=3*(3-1)/2+2-1=4sa[4]=a32(4)對(duì)角矩陣①概念：非零元都集中在以主對(duì)角線為中心的帶狀區(qū)域中。②存儲(chǔ)：這種矩陣可以某個(gè)原則(以行為主，或以對(duì)角線的順序)將其壓縮存儲(chǔ)到一維數(shù)組上。第20頁(yè)，共48頁(yè)，2023年，2月20日，星期六

壓縮存儲(chǔ)的對(duì)稱(chēng)矩陣的取值算法intget_M(inti,intj){if(i>=j)return(sa[i*(i+1)/2+j])elsereturn(sa[j*(j+1)/2+i]);}壓縮存儲(chǔ)的對(duì)稱(chēng)矩陣的賦值算法voidassign_M(inti,intj,intvalue){if(i>=j)sa[i*(i+1)/2+j]=value;elsesa[j*(j+1)/2+i]=value;}第21頁(yè)，共48頁(yè)，2023年，2月20日，星期六

帶狀矩陣

所有非0元素都集中在以主對(duì)角線為中心的帶狀區(qū)域，半帶寬為d時(shí),非0元素有(2d+1)*n-(1+d)*d個(gè)a00a01a020

0

0

0

0

0

0

0

0

a10a11a12a130

0

00

0

0

0

0a20a21a22a23a24000

0

0

0

00

a31a32a33a34a3500

0

0

0

00

0

a42a43a44a45a460

0

0

0

00

0

0a53a54a55a56a5700

0

0

0

0

00

a64a65a66a67a680

0

00

00

0

0

a75a76a77a78a790

0

00

0

0

0

0a86a87a88a89a810

0

00

0

0

0

0

0

a97

a98a99a910a91100

0

0

0

0

0

0

a108a109a1010a101100

0

0

0

0

0

0

0

a119a1110a1111d第22頁(yè)，共48頁(yè)，2023年，2月20日，星期六a00a010

0

0

a10a11a1200

0

a21a22a2300

0

a32a33a340

0

0a43a44為計(jì)算方便，認(rèn)為每一行都有2d+1個(gè)非0元素，若少則用0補(bǔ)足，所以，存放矩陣的數(shù)組sa[]有n(2d+1)個(gè)元素?cái)?shù)組元素sa[k]與矩陣元素aij

之間有關(guān)系：

k=i*(2d+1)+d+(j-i)0

a00

a01

a10

a11a12a21a22a23a32a33a34a43a440K=01234567891011121314第23頁(yè)，共48頁(yè)，2023年，2月20日，星期六

壓縮存儲(chǔ)的帶狀矩陣的取值算法intget_Md(inti,intj){if(abs(i-j)<=d）return(sa[i*(2*d+1)+d+(j-i)])；elsereturn(0);}壓縮存儲(chǔ)的帶狀矩陣的賦值算法voidassign_Md(inti,intj,intvalue){if(abs(i-j)<=d）sa[i*(i+1)/2+j]=value;}第24頁(yè)，共48頁(yè)，2023年，2月20日，星期六(5)稀疏矩陣①含義：在m×n的矩陣中，有t個(gè)元素不為零，令：稱(chēng)δ為矩陣的稀疏因子，通常認(rèn)為δ≤0.05時(shí)稱(chēng)稀疏矩陣②抽象數(shù)據(jù)類(lèi)型稀疏矩陣的定義③分析按常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時(shí)產(chǎn)生的問(wèn)題:

I零值元素占了很大空間；

II計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。

第25頁(yè)，共48頁(yè)，2023年，2月20日，星期六解決問(wèn)題的原則:

I盡可能少存或不存零值元素；

II

盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；

III

操作方便。即：能盡可能快地找到與下標(biāo)值(i，j)對(duì)應(yīng)的元素，能盡可能快地找到同一行或同一列的非零值元。

為此提出一種存儲(chǔ)方法：為了能找到相應(yīng)的元素，僅存儲(chǔ)非零元素的值是不夠的，還要記下它所在的行和列。于是采取將非零元素所在的行、列以及它的值構(gòu)成一個(gè)三元組(i,j,v)，然后再按某種規(guī)律存儲(chǔ)這些三元組，這種方法可以節(jié)約存儲(chǔ)空間。第26頁(yè)，共48頁(yè)，2023年，2月20日，星期六例如：稀疏矩陣：

A

=012900000000000-3000014000240000018000001500-7000可用三元組表(i,j,aij)A=((0,1,12),(0,2,9),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(5,0,15),(5,3,-7))加上行、列數(shù)、非零元個(gè)數(shù)6，7,8表示。

▲用三元組表存儲(chǔ)稀疏矩陣有三種方法：

I三元組順序表

II行邏輯鏈接的順序表

III十字鏈表第27頁(yè)，共48頁(yè)，2023年，2月20日，星期六④三元組順序表

I概念：以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表，得稀疏矩陣的一種壓縮存儲(chǔ)方式——稱(chēng)之為三元組順序表。如：

A

=

012900000000000-3000014000240000018000001500-7000

i

jV01234567831-3611512125218139432464-73614678第28頁(yè)，共48頁(yè)，2023年，2月20日，星期六如：ma[1].row=1,ma[1].col=1,ma[1].value=12

II結(jié)構(gòu)定義#definemaxsize1024typedefstruct{inti,j;elemtypev;}triple;typedefstruct{tripledata[maxsize+1];intmu,nu,tu;}tsmatrix;

III轉(zhuǎn)置運(yùn)算算法

轉(zhuǎn)置運(yùn)算是一種最常用的矩陣運(yùn)算。對(duì)于一個(gè)m

行n列的矩陣A，它的轉(zhuǎn)置矩陣B是一個(gè)n行m

列的矩陣。如，下圖中的矩陣A

和B

互為轉(zhuǎn)置矩陣。第29頁(yè)，共48頁(yè)，2023年，2月20日，星期六

A第0列第一列第二列第三列第四列第五列第六列

….

B第0行第一行第二行第三行第四行第五行第六行

….轉(zhuǎn)置運(yùn)算算法第30頁(yè)，共48頁(yè)，2023年，2月20日，星期六B

=00-3001512000180

900240000000-70000000014000000000

分析：

◆

將矩陣的行列數(shù)的值交換

◆將每一個(gè)三元組的i和j相互調(diào)換

◆重排三元組之間的次序

A

=

012900000000000-3000014000240000018000001500-7000第31頁(yè)，共48頁(yè)，2023年，2月20日，星期六

算法一

i

j

v01234567831-3611512125218139432464-73614678

i

j

v012345678211246-713-33424161531963142518768第32頁(yè)，共48頁(yè)，2023年，2月20日，星期六按照A的列序來(lái)進(jìn)行轉(zhuǎn)換的基本思想

對(duì)ma[]從頭至尾掃描：第一次掃描時(shí)，將ma[]中列號(hào)為0的所有元組交換行列值后，依次賦值到mb[]中；第二次掃描時(shí)，將ma[]中列號(hào)為1的所有元組交換行列值后，依次賦值到mb[]中；依此類(lèi)推，直至將ma[]的所有三元組賦值到mb[]中。第33頁(yè)，共48頁(yè)，2023年，2月20日，星期六

ijv121213931-3361443245218611564-7ijv31-3251813-3611516151212211252181393194324342464-746-736146314A矩陣B矩陣對(duì)A六次掃描完成轉(zhuǎn)置運(yùn)算第一次掃描查找第1列元素第一次掃描結(jié)束第二次掃描結(jié)束第二次掃描查找第2列元素第三次掃描查找第3列元素第四次掃描查找第4列元素第五次掃描查找第5列元素第六次掃描查找第6列元素轉(zhuǎn)置運(yùn)算算法圖示012345678678768第34頁(yè)，共48頁(yè)，2023年，2月20日，星期六

算法一描述(保持以行序?yàn)橹餍虼鎯?chǔ))inttpm(tsmatrixm,tsmatrix*t){t->mu=m.nu;t->nu=m.mu;t->tu=m.tu;if(t->tu){q=1;for(col=1;col<=m.nu;col++)for(p=1;p<=m.tu;p++)if(m.data[p].j==col){t->data[q].i=m.data[p].j;t->data[q].j=m.data[p].i;t->data[q].v=m.data[p].v;q++;}}returnok;}▲

時(shí)間復(fù)雜度為〇(nu×tu)第35頁(yè)，共48頁(yè)，2023年，2月20日，星期六ijv012345678768

mb[]

算法二——快速轉(zhuǎn)置算法

方法：以A矩陣的三元組為中心,依次取出ma[]中的每一個(gè)三元組，交換行列后，直接將其寫(xiě)入mb[]合適的位置中。

342416153196314251813-3i

jvma[]01234567831-361156785218139432464-736141212211246-7第36頁(yè)，共48頁(yè)，2023年，2月20日，星期六⑤十字鏈表

I概念：以三元組表示的稀疏矩陣，在運(yùn)算中，若非0元素的位置發(fā)生變化，會(huì)引起數(shù)組元素的頻繁移動(dòng)。為解決這個(gè)問(wèn)題，采用十字鏈表的存儲(chǔ)結(jié)構(gòu)在十字鏈表中，表示非0元素結(jié)點(diǎn)除了三元組,還有兩個(gè)指針域：

向下域(down)

鏈接同一列下一個(gè)非0元素

向右域(right)

鏈接同一行下一個(gè)非0元素稀疏矩陣中同一行的非0元素結(jié)點(diǎn)通過(guò)向右域，鏈接成一個(gè)帶頭結(jié)點(diǎn)的行循環(huán)鏈表。同一列的非0元素結(jié)點(diǎn)通過(guò)向下域，鏈接成一個(gè)帶頭結(jié)點(diǎn)的列循環(huán)鏈表。

第37頁(yè)，共48頁(yè)，2023年，2月20日，星期六

rowcolvaldownrightII

十字鏈表的存儲(chǔ)結(jié)構(gòu)(結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu))如下：

structnode{introw,col,val;structnode*down,*right;}第38頁(yè)，共48頁(yè)，2023年，2月20日，星期六例如矩陣A

=

32050-1002000000044500000000000003501200300000000000020211-1head1022221022十字鏈表圖示第39頁(yè)，共48頁(yè)，2023年，2月20日，星期六

小結(jié)

1矩陣壓縮存儲(chǔ)是指為多個(gè)值相同的元素分配一個(gè)存儲(chǔ)空間，對(duì)零元素不分配存儲(chǔ)空間；2特殊矩陣的壓縮存儲(chǔ)是根據(jù)元素的分布規(guī)律，確定元素的存儲(chǔ)位置與元素在矩陣中的位置的對(duì)應(yīng)關(guān)系；3稀疏矩陣的壓縮存儲(chǔ)除了要保存非零元素的值外，還要保存非零元素在矩陣中的位置；第40頁(yè)，共48頁(yè)，2023年，2月20日，星期六1、廣義表的定義(1)廣義表的引入線性表是由n個(gè)數(shù)據(jù)元素組成的有限序列。其中每個(gè)組成元素被限定為單元素，有時(shí)這種限制需要拓寬。例如，中國(guó)舉辦的某體育項(xiàng)目國(guó)際邀請(qǐng)賽，參賽隊(duì)清單可采用如下的表示形式：(俄羅斯，巴西，(國(guó)家，河北，四川)，古巴，美國(guó)，()，日本)在這個(gè)拓寬了的線性表中，韓國(guó)隊(duì)?wèi)?yīng)排在美國(guó)隊(duì)的后面，但由于某種原因未參加，成為空表。國(guó)家隊(duì)、河北隊(duì)、四川隊(duì)均作為東道主的參賽隊(duì)參加，構(gòu)成一個(gè)小的線性表，成為原線性表的一個(gè)數(shù)據(jù)項(xiàng)。這種拓寬了的線性表就是廣義表。5.4廣義表第41頁(yè)，共48頁(yè)，2023年，2月20日，星期六(2)廣義表的定義廣義表（GeneralizedLists）是n（n≥0）個(gè)數(shù)據(jù)元素