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

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

第五章

數(shù)組和廣義表

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

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

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

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

ADTArray

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

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

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

,Rn}第4頁，共48頁，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ù)對象: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頁，共48頁，2023年，2月20日，星期六6

(2)

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

a01…

a0n-1a10

a11…

a1n-1┋┋┋am-10

am-11

…

am-1n-1

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

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

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

A=(0,1,2,3,

4,……,p)

p=m-1或n-1

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

是一個列向量的線性表

j=（a0j,

a1j,a2j,

a3j,……

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

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

a01…

a0n-1a10

a11…

a1n-1┋┋┋am-10

am-11…

am-1n-1Amn=a00

a10

┋

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

是一個行向量的線性表

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語言中二維數(shù)組類型的一種定義

typedefelemtypeArray2[m][n];

等價于

typedefelemtypeArray1[n];typedefArray1Array2[m];

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

(1)類型特點

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

②數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。(2)兩個策略----兩種順序映象的方式①以行序為主序(低下標優(yōu)先)；②以列序為主序(高下標優(yōu)先)。5．2數(shù)組的順序存貯結(jié)構(gòu)第9頁，共48頁，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頁，共48頁，2023年，2月20日，星期六1101m-1mm+12m-1nm-1a00a10am-10

a01

a11am-11

a0n-1a1n-1

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

假設(shè)二維數(shù)組A每個元素占用L個存儲單元，若以行序為主序的方式存儲二維數(shù)組，二維數(shù)組A中任一元素ai,j的存儲位置為：

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

L

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

LOC(i,j,k)=LOC(0,0,0)+(b2×b3×i＋b3×j+k)×L若以列序為主序的方式存儲二維數(shù)組，則元素aij

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

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

▲

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

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

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

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

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

一特殊矩陣的壓縮存儲二稀疏矩陣的壓縮存儲

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

壓縮存儲：為多個值相同的元素分配一個存儲空間，對零元不分配空間。②

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

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

a22

a31

a32

a33

an1

an2

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

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

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

帶狀矩陣

所有非0元素都集中在以主對角線為中心的帶狀區(qū)域，半帶寬為d時,非0元素有(2d+1)*n-(1+d)*d個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頁，共48頁，2023年，2月20日，星期六a00a010

0

0

a10a11a1200

0

a21a22a2300

0

a32a33a340

0

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

之間有關(guān)系：

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

a00

a01

a10

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

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

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

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

第25頁，共48頁，2023年，2月20日，星期六解決問題的原則:

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

II

盡可能減少沒有實際意義的運算；

III

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

為此提出一種存儲方法：為了能找到相應(yīng)的元素，僅存儲非零元素的值是不夠的，還要記下它所在的行和列。于是采取將非零元素所在的行、列以及它的值構(gòu)成一個三元組(i,j,v)，然后再按某種規(guī)律存儲這些三元組，這種方法可以節(jié)約存儲空間。第26頁，共48頁，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ù)、非零元個數(shù)6，7,8表示。

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

I三元組順序表

II行邏輯鏈接的順序表

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

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

A

=

012900000000000-3000014000240000018000001500-7000

i

jV01234567831-3611512125218139432464-73614678第28頁，共48頁，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)置運算算法

轉(zhuǎn)置運算是一種最常用的矩陣運算。對于一個m

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

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

和B

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

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

….

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

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

=00-3001512000180

900240000000-70000000014000000000

分析：

◆

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

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

◆重排三元組之間的次序

A

=

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

算法一

i

j

v01234567831-3611512125218139432464-73614678

i

j

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

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

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

算法一描述(保持以行序為主序存儲)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;}▲

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

mb[]

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

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

342416153196314251813-3i

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

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

向下域(down)

鏈接同一列下一個非0元素

向右域(right)

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

第37頁，共48頁，2023年，2月20日，星期六

rowcolvaldownrightII

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

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

=

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

小結(jié)

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