數(shù)據(jù)結(jié)構(gòu)（C清華版）

數(shù)據(jù)結(jié)構(gòu)（C++版）二第四章廣義線性表本章的基本內(nèi)容是：數(shù)組的邏輯結(jié)構(gòu)特征數(shù)組的存儲(chǔ)方式及尋址方法特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法廣義表的基本概念和存儲(chǔ)結(jié)構(gòu)第四章廣義線性表線性表——具有相同類型的數(shù)據(jù)元素的有限序列。限制插入、刪除位置線性表——具有相同類型的數(shù)據(jù)元素的有限序列。限制元素類型為字符棧——僅在表尾進(jìn)行插入和刪除操作的線性表。隊(duì)列——在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。串——零個(gè)或多個(gè)字符組成的有限序列。特殊線性表第四章廣義線性表線性表——具有相同類型的數(shù)據(jù)元素的有限序列。將元素的類型進(jìn)行擴(kuò)充廣義線性表（多維）數(shù)組——線性表中的數(shù)據(jù)元素可以是線性表，但所有元素的類型相同。廣義表——線性表中的數(shù)據(jù)元素可以是線性表，且元素的類型可以不相同。數(shù)組的定義數(shù)組是由一組類型相同的數(shù)據(jù)元素構(gòu)成的有序集合，每個(gè)數(shù)據(jù)元素稱為一個(gè)數(shù)組元素（簡(jiǎn)稱為元素），每個(gè)元素受n(n≥1)個(gè)線性關(guān)系的約束，每個(gè)元素在n個(gè)線性關(guān)系中的序號(hào)i1、i2、…、in稱為該元素的下標(biāo)，并稱該數(shù)組為n維數(shù)組。數(shù)組的特點(diǎn)元素本身可以具有某種結(jié)構(gòu)，屬于同一數(shù)據(jù)類型；數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合。廣義線性表——多維數(shù)組廣義線性表——多維數(shù)組

a11a12…a1na21

a22…a2n

…………

am1am2…amnA=例如，元素a22受兩個(gè)線性關(guān)系的約束，在行上有一個(gè)行前驅(qū)a21和一個(gè)行后繼a23，在列上有一個(gè)列前驅(qū)a12和和一個(gè)列后繼a32。數(shù)組示例

a11a12…a1na21a22…a2n

…………

am1am2…amnA=

A=(A1，A2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)數(shù)組——線性表的推廣二維數(shù)組是數(shù)據(jù)元素為線性表的線性表。廣義線性表——多維數(shù)組數(shù)組的基本操作廣義線性表——多維數(shù)組在數(shù)組中插入（或）一個(gè)元素有意義嗎？

a11a12…a1na21a22…a2n

…………

am1am2…amnA=將元素x插入到數(shù)組中第1行第2列。x

a11a12…a1na21a22…a2n

…………

am1am2…amnA=刪除數(shù)組中第1行第2列元素。數(shù)組的基本操作⑴存?。航o定一組下標(biāo)，讀出對(duì)應(yīng)的數(shù)組元素；⑵修改：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)組元素。存取和修改操作本質(zhì)上只對(duì)應(yīng)一種操作——尋址數(shù)組應(yīng)該采用何種方式存儲(chǔ)？數(shù)組沒有插入和刪除操作，所以，不用預(yù)留空間，適合采用順序存儲(chǔ)。廣義線性表——多維數(shù)組數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址——一維數(shù)組設(shè)一維數(shù)組的下標(biāo)的范圍為閉區(qū)間［l，h］，每個(gè)數(shù)組元素占用c個(gè)存儲(chǔ)單元，則其任一元素ai

的存儲(chǔ)地址可由下式確定：Loc(ai)＝Loc(al)＋(i－l)×c

廣義線性表——多維數(shù)組calai-1

ai……ahal+1……Loc(al)Loc(ai)常用的映射方法有兩種：按行優(yōu)先：先行后列，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相同者先存儲(chǔ)列號(hào)較小的元素。

按列優(yōu)先：先列后行，先存儲(chǔ)列號(hào)較小的元素，列號(hào)相同者先存儲(chǔ)行號(hào)較小的元素。

廣義線性表——多維數(shù)組數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址——二維數(shù)組二維數(shù)組內(nèi)存二維結(jié)構(gòu)一維結(jié)構(gòu)廣義線性表——多維數(shù)組l2h2

l1h1(a)二維數(shù)組aij前面的元素個(gè)數(shù)=陰影部分的面積=整行數(shù)×每行元素個(gè)數(shù)+本行中aij前面的元素個(gè)數(shù)=(i

-l1)×(h2

-l2＋1)＋(j

-l2)本行中aij前面的元素個(gè)數(shù)每行元素個(gè)數(shù)整行數(shù)aij按行優(yōu)先存儲(chǔ)的尋址廣義線性表——多維數(shù)組第l1行第l1+1行al1l2…al1h2a(l1+1)l2…a(l1+1)h2……aij…ah1h2Loc(aij)Loc(al1l2)(i

-l1)×(h2

-l2＋1)＋(j

-l2)個(gè)元素Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c按行優(yōu)先存儲(chǔ)的尋址按列優(yōu)先存儲(chǔ)的尋址方法與此類似。Loc(aijk)=Loc(a000)+(i×m2×m3+j×m3+k)×c

廣義線性表——多維數(shù)組n（n＞2）維數(shù)組一般也采用按行優(yōu)先和按列優(yōu)先兩種存儲(chǔ)方法。請(qǐng)自行推導(dǎo)任一元素存儲(chǔ)地址的計(jì)算方法。數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址——多維數(shù)組矩陣的壓縮存儲(chǔ)特殊矩陣：矩陣中很多值相同的元素并且它們的分布有一定的規(guī)律。稀疏矩陣：矩陣中有很多零元素。壓縮存儲(chǔ)的基本思想是：⑴為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；⑵

對(duì)零元素不分配存儲(chǔ)空間。

特殊矩陣和稀疏矩陣特殊矩陣的壓縮存儲(chǔ)——對(duì)稱矩陣3647862842481697460582957A＝對(duì)稱矩陣特點(diǎn)：aij=aji如何壓縮存儲(chǔ)？只存儲(chǔ)下三角部分的元素。矩陣的壓縮存儲(chǔ)(a)下三角矩陣(b)存儲(chǔ)說明(c)計(jì)算方法aij在一維數(shù)組中的序號(hào)=陰影部分的面積=

i×(i+1)/2+j+1∵一維數(shù)組下標(biāo)從0開始∴aij在一維數(shù)組中的下標(biāo)k=i×(i+1)/2+j0…

in-10…j…n-1

aij每行元素個(gè)數(shù)12…iaij在本行中的序號(hào)aij第0行第1行…第i-1行對(duì)稱矩陣的壓縮存儲(chǔ)

矩陣的壓縮存儲(chǔ)對(duì)于下三角中的元素aij（i≥j），在數(shù)組SA中的下標(biāo)k與i、j的關(guān)系為：k＝i×(i＋1)/2＋j。上三角中的元素aij（i＜j），因?yàn)閍ij＝aji，則訪問和它對(duì)應(yīng)的元素aji即可，即：k＝j(luò)×(j＋1)/2＋i。對(duì)稱矩陣的壓縮存儲(chǔ)

第1行第n-1行第0行

a00

a10

a11

a20

a21

a22

aij…

an-10

an-11…an-1n-1…第2行012345kn(n+1)/2-1矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)——三角矩陣3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩陣如何壓縮存儲(chǔ)？只存儲(chǔ)上三角（或下三角）部分的元素。矩陣的壓縮存儲(chǔ)矩陣中任一元素aij在數(shù)組中的下標(biāo)k與i、j的對(duì)應(yīng)關(guān)系：i×(i＋1)/2＋j

當(dāng)i≥jn×(n＋1)/2當(dāng)i＜jk=下三角矩陣的壓縮存儲(chǔ)012345

k

n(n+1)/2第1行第0行

a00

a10

a11

a20

a21

aij…an-1n-1…第2行

c

a22矩陣的壓縮存儲(chǔ)存儲(chǔ)下三角元素對(duì)角線上方的常數(shù)——只存一個(gè)矩陣中任一元素aij在數(shù)組中的下標(biāo)k與i、j的對(duì)應(yīng)關(guān)系：

i×(2n－i＋1)/2＋j－i

當(dāng)i≤jn×(n＋1)/2當(dāng)i＞jk=上三角矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)存儲(chǔ)上三角元素對(duì)角線上方的常數(shù)——只存一個(gè)特殊矩陣的壓縮存儲(chǔ)——對(duì)角矩陣

對(duì)角矩陣：所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，除了主對(duì)角線和它的上下方若干條對(duì)角線的元素外，所有其他元素都為零。

a00a01000a10a11

a12000a21

a22

a23000

a32

a33

a34000a43

a44A=矩陣的壓縮存儲(chǔ)a00a010

00a10a11

a12000a21

a22

a23

000

a32

a33

a34000a43

a44A=將帶狀區(qū)域立起來0a00

a01a10a11

a12a21

a22

a23a32a33

a34a43

a440B=s＝j(luò)-i+1t=i映射到二維數(shù)組B中，映射關(guān)系對(duì)角矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)按行存儲(chǔ)元素aij在一維數(shù)組中的序號(hào)=2+3(i－1)+(j－i+2)=2i+j+1

∵一維數(shù)組下標(biāo)從0開始∴元素aij在一維數(shù)組中的下標(biāo)=2i+j(b)尋址的計(jì)算方法(c)壓縮到一維數(shù)組中a00a01a10a11a12a21a22a23a32a33a34a43a440123456789101112矩陣的壓縮存儲(chǔ)對(duì)角矩陣的壓縮存儲(chǔ)(a)三對(duì)角矩陣

0

00

000

000

000

A=a00a01a10a11

a12a21a22

a23a32a33

a34a43a44稀疏矩陣的壓縮存儲(chǔ)1500000

0110000

000600

0000009

00000A=如何只存儲(chǔ)非零元素？矩陣的壓縮存儲(chǔ)注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。template<classT>structelement{

introw,col;//行號(hào)，列號(hào)Titem//非零元素值};將稀疏矩陣中的每個(gè)非零元素表示為：(行號(hào)，列號(hào)，非零元素值)——三元組矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)定義三元組：三元組表：將稀疏矩陣的非零元素對(duì)應(yīng)的三元組所構(gòu)成的集合，按行優(yōu)先的順序排列成一個(gè)線性表。矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)三元組表＝((0,0,15),(1,1,11),(2,3,6),(4,0,9))1500000

0110000

000600

0000009

00000A=如何存儲(chǔ)三元組表？稀疏矩陣的壓縮存儲(chǔ)——三元組順序表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表1500220-15

0113000

000600

00000091

00000A=矩陣的壓縮存儲(chǔ)三元組順序表是否需要預(yù)留存儲(chǔ)空間？稀疏矩陣的修改操作三元組順序表的插入/刪除操作稀疏矩陣的壓縮存儲(chǔ)——三元組順序表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-1矩陣的壓縮存儲(chǔ)1500220-15

0113000

000600

00000091

00000A=7（非零元個(gè)數(shù)）是否對(duì)應(yīng)惟一的稀疏矩陣？5（矩陣的行數(shù)）6（矩陣的列數(shù)）存儲(chǔ)結(jié)構(gòu)定義：constint

MaxTerm=100;template<classT>

struct

SparseMatrix{Tdata[MaxTerm];//存儲(chǔ)非零元素

int

mu,nu,tu;//行數(shù)，列數(shù)，非零元個(gè)數(shù)

};矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)——三元組順序表三元組順序表操作——轉(zhuǎn)置操作例：15000910110000300022060000000-150000B=1500220-15

0113000

000600

00000091

00000A=矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）00150491

1111

213

3022

326

50-15

空空空閑閑閑rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）三元組順序表轉(zhuǎn)置算法——算法Ⅰ基本思想：直接取，順序存。即在A的三元組順序表中依次找第0列、第1列、…直到最后一列的三元組，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B的三元組順序表中。矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）設(shè)置矩陣B的行數(shù)、列數(shù)、非零元個(gè)數(shù)矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）在矩陣A中查找第0列非零元，順序存儲(chǔ)到矩陣B中

0015

0491矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）在矩陣A中查找第1列非零元，順序存儲(chǔ)到矩陣B中

0015

0491

1111矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）在矩陣A中查找第2列非零元，順序存儲(chǔ)到矩陣B中

0015

0491

1111

213矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）在矩陣A中查找第3列非零元，順序存儲(chǔ)到矩陣B中

0015

0491

1111

213

3022

326矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）在矩陣A中查找第4列非零元，順序存儲(chǔ)到矩陣B中

0015

0491

1111

213

3022

326矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）在矩陣A中查找第5列非零元，順序存儲(chǔ)到矩陣B中

0015

0491

1111

213

3022

326

50-15矩陣的壓縮存儲(chǔ)0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）在矩陣A中查找第6列非零元，順序存儲(chǔ)到矩陣B中

0015

0491

1111

213

3022

326

50-151.設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元個(gè)數(shù)；2.在B中設(shè)置初始存儲(chǔ)位置pb；3.for(col=最小列號(hào);col<=最大列號(hào);col++)3.1在A中查找列號(hào)為col的三元組；3.2交換其行號(hào)和列號(hào)，存入B中pb位置；3.3pb++；矩陣的壓縮存儲(chǔ)三元組順序表轉(zhuǎn)置算法Ⅰ——偽代碼分析：A中第0列的第一個(gè)非零元素一定存儲(chǔ)在B中下標(biāo)為0的位置上，該列中其它非零元素應(yīng)存放在B中后面連續(xù)的位置上，那么第1列的第一個(gè)非零元素在B中的位置便等于第0列的第一個(gè)非零元素在B中的位置加上第0列的非零元素的個(gè)數(shù)，以此類推。基本思想：順序取，直接存。即在A中依次取三元組，交換其行號(hào)和列號(hào)放到B中適當(dāng)位置。矩陣的壓縮存儲(chǔ)三元組順序表轉(zhuǎn)置算法——算法Ⅱ如何確定當(dāng)前從A中取出的三元組在B中的位置？矩陣的壓縮存儲(chǔ)三元組順序表轉(zhuǎn)置算法——算法Ⅱ

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）

0015

0491

1111

213

3022

326

50-15第0列第1個(gè)非零元素第0列有2個(gè)非零元素第1列第1個(gè)非零元素引入兩個(gè)數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：num[nu]：存儲(chǔ)矩陣A中某列的非零元素的個(gè)數(shù)；cpot[nu]：初值表示矩陣A中某列的第一個(gè)非零元素在B中的位置。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：cpot[0]=0；cpot[col]=cpot[col-1]+num[col-1]；1≤col＜nunum與cpot存在如下遞推關(guān)系：矩陣的壓縮存儲(chǔ)三元組順序表轉(zhuǎn)置算法——算法Ⅱ0015032205-1511111232364091

空空空閑閑閑rowcolitem0123456MaxTerm-15（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）矩陣的壓縮存儲(chǔ)

col012345

num[col]21

12

01

cpot[col]

023466根據(jù)矩陣A計(jì)算num和cpot

0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）矩陣的壓縮存儲(chǔ)將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[0]cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]

0015cpot[0]0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）矩陣的壓縮存儲(chǔ)將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]

0015cpot[0]

3022cpot[3]0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）矩陣的壓縮存儲(chǔ)將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[1]cpot[2]cpot[4]

0015cpot[0]

3022cpot[3]

50-15cpot[5]cpot[5]0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）矩陣的壓縮存儲(chǔ)將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[1]cpot[2]cpot[4]

0015cpot[0]

3022cpot[3]

50-15cpot[5]

1111cpot[1]0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）矩陣的壓縮存儲(chǔ)將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[2]cpot[4]

0015cpot[0]

3022cpot[3]

50-15cpot[5]

1111cpot[1]

213cpot[2]cpot[1]0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）矩陣的壓縮存儲(chǔ)將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[4]

0015cpot[0]

3022cpot[3]

50-15cpot[5]

1111

213cpot[2]cpot[1]

326cpot[3]0015032205-1511111232364091

空空空閑閑閑rowcolitem01234565（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個(gè)數(shù)）矩陣的壓縮存儲(chǔ)將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個(gè)數(shù)）cpot[4]

0015cpot[0]

3022

50-15cpot[5]

1111

213cpot[2]cpot[1]

326cpot[3]

0491cpot[0]1.設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)；2.計(jì)算A中每一列的非零元素個(gè)數(shù)；3.計(jì)算A中每一列的第一個(gè)非零元素在B中的下標(biāo)；4.依次取A中的每一個(gè)非零元素對(duì)應(yīng)的三元組；4.1確定該元素在B中的下標(biāo)pb；4.2將該元素的行號(hào)列號(hào)交換后存入B中pb的位置；4.3預(yù)置該元素所在列的下一個(gè)元素的存放位置；矩陣的壓縮存儲(chǔ)三元組順序表轉(zhuǎn)置算法Ⅱ——偽代碼采用鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表，每個(gè)非零元素對(duì)應(yīng)的三元組存儲(chǔ)為一個(gè)鏈表結(jié)點(diǎn)，結(jié)構(gòu)為：rowcolitemdownrightrow：存儲(chǔ)非零元素的行號(hào)col：存儲(chǔ)非零元素的列號(hào)item：存儲(chǔ)非零元素的值right：指針域，指向同一行中的下一個(gè)三元組down：指針域，指向同一列中的下一個(gè)三元組矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)——十字鏈表

202∧M=300501002000矩陣的壓縮存儲(chǔ)

003

035∧∧

111∧∧∧稀疏矩陣的壓縮存儲(chǔ)——十字鏈表∧廣義表：n（n≥0）個(gè)數(shù)據(jù)元素的有限序列，記作：

LS＝(a1，a2，……，an)其中：LS是廣義表的名稱，ai（1≤i≤n）是LS的成員（或直接元素），它可以是單個(gè)的數(shù)據(jù)元素，也可以是一個(gè)廣義表，分別稱為LS的單元素（或原子）和子表。

廣義線性表——廣義表廣義表的邏輯結(jié)構(gòu)：直接元素之間是線性關(guān)系。廣義表的基本概念通常用大寫字母表示廣義表，用小寫字母表示單元素。長度：廣義表LS中的直接元素的個(gè)數(shù)；深度：廣義表LS中括號(hào)的最大嵌套層數(shù)。表頭：廣義表LS非空時(shí)，稱第一個(gè)元素為LS的表頭；表尾：廣義表LS中除表頭外其余元素組成的廣義表。廣義線性表——廣義表廣義表()和廣義表(())不同？廣義表的基本概念A(yù)

＝()B

＝(e)C

＝(a,(b，c，d))D

＝(A,B,C)E＝(a,E)F＝(())廣義線性表——廣義表廣義表的示例長度？深度？表頭？表尾？A

＝()B

＝(e)C

＝(a,(b，c，d))D

＝(A,B,C)E＝(a,E)F＝(())廣義線性表——廣義表廣義表的圖形表示ABeCabcdD廣義線性表——廣義表廣義表可以采用順序存儲(chǔ)結(jié)構(gòu)嗎？由于廣義表中的數(shù)據(jù)元素的類型不統(tǒng)一，因此難以采用順序存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)。若廣義表不空，則可分解為表頭和表尾；反之，一對(duì)確定的表頭和表尾可唯一地確定一個(gè)廣義表。采用頭尾表示法存儲(chǔ)廣義表如何采用鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)廣義表？廣義表的存儲(chǔ)結(jié)構(gòu)——頭尾表示法廣義線性表——廣義表廣義表中的數(shù)據(jù)元素既可以是廣義表也可以是單元素頭尾表示法中的結(jié)點(diǎn)結(jié)構(gòu)？表結(jié)點(diǎn)——存儲(chǔ)廣義表；元素結(jié)點(diǎn)——存儲(chǔ)單元素

tag=1hptp

tag=0data表結(jié)點(diǎn)

元素結(jié)點(diǎn)tag：區(qū)分表結(jié)點(diǎn)和元素結(jié)點(diǎn)的標(biāo)志；hp：指向表頭結(jié)點(diǎn)的指針；tp：指向表尾結(jié)點(diǎn)的指針；data：數(shù)據(jù)域，存放單元素。廣義表的存儲(chǔ)結(jié)構(gòu)——頭尾表示法廣義線性表——廣義表結(jié)點(diǎn)結(jié)構(gòu)enum

Elemtag{Atom,List};template<classT>struct

GLNode

{

Elemtagtag;union{Tdata;

struct

{

GLNode*hp,*tp;

}ptr;};};廣義線性表——廣義表廣義表的存儲(chǔ)結(jié)構(gòu)——頭尾表示法定義結(jié)點(diǎn)結(jié)構(gòu)

tag=1hptp

tag=0data廣義線性表——廣義表廣義表的存儲(chǔ)結(jié)構(gòu)——頭尾表示法A

＝()B

＝(e)C

＝(a,(b，c，d))NULLA1B0e∧1C0a∧110b10c∧10d廣義線性表——廣義表廣義表的存儲(chǔ)結(jié)構(gòu)——頭尾表示法1B0e∧1C0a∧110b10c∧10dA

＝()B

＝(e)C

＝(a,(b，c，d))D

＝(A,B,C)1D∧11∧廣義線性表——廣義表廣義表的存儲(chǔ)結(jié)構(gòu)——頭尾表示法E＝(a,E)F＝(())1E0a1∧1F∧∧template<classT>classLists{public:Lists();

Lists(Listsls1,Listsls2);~Lists();

intLength();

int

Depth(GLNode<T>*ls);

GLNode*Head();

GLNode*Tail();private:

GLNode<T>*ls;};廣義表類的聲明廣義線性表——廣義表廣義表的操作——建立廣義表

template<classT>

Lists::Lists(Listsls1,Listsls2){

ls=newGLNode

ls->tag=1;

ls->ptr.hp=ls1;

ls->ptr.tp=ls2;}廣義線性表——廣義表廣義表的操作——求廣義表的深度

template<classT>

int

Lists::Depth(GLNode<T>*ls){if(ls==NULL)return1;if(ls->tag==0)return0;max=0;p=ls;while(p){

dep=Depth(p->ptr.hp);

if(dep>max)max=dep;p=p->ptr.tp;

}returnmax+1;

}廣義線性表——廣義表廣義線性表多維數(shù)組廣義表邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)⑴數(shù)組的定義⑵基本操作⑶ADT定義順序存儲(chǔ)壓縮存儲(chǔ)特殊矩陣·對(duì)稱矩陣·三角矩陣·對(duì)角矩陣稀疏矩陣按行優(yōu)先按列優(yōu)先尋址的計(jì)算方法⑴基本概念·廣義表定義·表頭、表尾·長度、深度⑵ADT定義鏈接存儲(chǔ)頭尾表示法轉(zhuǎn)置算法第四章廣義線性表樹的邏輯結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)樹、森林與二叉樹的轉(zhuǎn)換哈夫曼樹第5章樹和二叉樹本章的主要內(nèi)容是樹的定義樹：n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n＝0時(shí)，稱為空樹；任意一棵非空樹滿足以下條件：⑴

有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；⑵

當(dāng)n＞1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的有限集合T1,T2,…,Tm，其中每個(gè)集合又是一棵樹，并稱為這個(gè)根結(jié)點(diǎn)的子樹。5.1樹的邏輯結(jié)構(gòu)樹的定義是采用遞歸方法(a)一棵樹結(jié)構(gòu)(b)一個(gè)非樹結(jié)構(gòu)(c)一個(gè)非樹結(jié)構(gòu)5.1樹的邏輯結(jié)構(gòu)樹的定義ACBGFEDHIACBGFDACBGFDE樹的應(yīng)用舉例——文件結(jié)構(gòu)5.1樹的邏輯結(jié)構(gòu)MyComputerC:D:E:etcWINDOWSProgramFilesPictureMusic…………………………………………樹的基本術(shù)語結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。樹的度：樹中各結(jié)點(diǎn)度的最大值。5.1樹的邏輯結(jié)構(gòu)CGBDEFKLHMIJA5.1樹的邏輯結(jié)構(gòu)葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。CGBDEFKLHMIJA樹的基本術(shù)語孩子、雙親：樹中某結(jié)點(diǎn)子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。

5.1樹的邏輯結(jié)構(gòu)CGBDEFKLHMIJA樹的基本術(shù)語路徑：如果樹的結(jié)點(diǎn)序列n1,n2,…,nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的雙親（1<=i<k），則把n1,n2,…,nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個(gè)數(shù)稱為路徑長度。CGBDEFKLHMIJA5.1樹的邏輯結(jié)構(gòu)樹的基本術(shù)語祖先、子孫：在樹中，如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y，那么x就稱為y的祖先，而y稱為x的子孫。5.1樹的邏輯結(jié)構(gòu)CGBDEFKLHMIJA樹的基本術(shù)語結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子結(jié)點(diǎn)在第k+1層。樹的深度：樹中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。1層2層4層3層高度＝4CGBDEFKLHMIJC5.1樹的邏輯結(jié)構(gòu)樹的基本術(shù)語CBDEFKLHJA71234568910層序編號(hào)：將樹中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。5.1樹的邏輯結(jié)構(gòu)樹的基本術(shù)語有序樹、無序樹：如果一棵樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹

5.1樹的邏輯結(jié)構(gòu)樹的基本術(shù)語ACBGFEDACBGFEDCBDEFKLHJ森林：m(m≥0)棵互不相交的樹的集合。

5.1樹的邏輯結(jié)構(gòu)樹的基本術(shù)語A同構(gòu)：對(duì)兩棵樹，若通過對(duì)結(jié)點(diǎn)適當(dāng)?shù)刂孛?，就可以使這兩棵樹完全相等（結(jié)點(diǎn)對(duì)應(yīng)相等，結(jié)點(diǎn)對(duì)應(yīng)關(guān)系也相等），則稱這兩棵樹同構(gòu)。5.1樹的邏輯結(jié)構(gòu)樹的基本術(shù)語ACBGFEDDAECFBG樹結(jié)構(gòu)和線性結(jié)構(gòu)的比較線性結(jié)構(gòu)樹結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素根結(jié)點(diǎn)（只有一個(gè)）無前驅(qū)無雙親最后一個(gè)數(shù)據(jù)元素葉子結(jié)點(diǎn)(可以有多個(gè))無后繼無孩子其它數(shù)據(jù)元素其它結(jié)點(diǎn)一個(gè)前驅(qū),一個(gè)后繼一個(gè)雙親,多個(gè)孩子一對(duì)一一對(duì)多5.1樹的邏輯結(jié)構(gòu)樹的抽象數(shù)據(jù)類型定義ADTTreeData

樹是由一個(gè)根結(jié)點(diǎn)和若干棵子樹構(gòu)成，樹中結(jié)點(diǎn)具有相同數(shù)據(jù)類型及層次關(guān)系Operation

InitTree

前置條件：樹不存在輸入：無功能：初始化一棵樹輸出：無后置條件：構(gòu)造一個(gè)空樹5.1樹的邏輯結(jié)構(gòu)

DestroyTree

前置條件：樹已存在輸入：無功能：銷毀一棵樹輸出：無后置條件：釋放該樹占用的存儲(chǔ)空間

Root

前置條件：樹已存在輸入：無功能：求樹的根結(jié)點(diǎn)輸出：樹的根結(jié)點(diǎn)的信息后置條件：樹保持不變樹的抽象數(shù)據(jù)類型定義5.1樹的邏輯結(jié)構(gòu)Parent

前置條件：樹已存在輸入：結(jié)點(diǎn)x

功能：求結(jié)點(diǎn)x的雙親輸出：結(jié)點(diǎn)x的雙親的信息后置條件：樹保持不變

Depth

前置條件：樹已存在輸入：無功能：求樹的深度輸出：樹的深度后置條件：樹保持不變

樹的抽象數(shù)據(jù)類型定義5.1樹的邏輯結(jié)構(gòu)

PreOrder

前置條件：樹已存在輸入：無功能：前序遍歷樹輸出：樹的前序遍歷序列后置條件：樹保持不變

PostOrder

前置條件：樹已存在輸入：無功能：后序遍歷樹輸出：樹的后序遍歷序列后置條件：樹保持不變endADT樹的抽象數(shù)據(jù)類型定義5.1樹的邏輯結(jié)構(gòu)樹的遍歷操作

樹的遍歷：從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問樹中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。

如何理解訪問?抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù)。如何理解次序?樹通常有前序（根）遍歷、后序（根）遍歷和層序（次）遍歷三種方式。5.1樹的邏輯結(jié)構(gòu)樹結(jié)構(gòu)（非線性結(jié)構(gòu)）→線性結(jié)構(gòu)。遍歷的實(shí)質(zhì)?前序遍歷

樹的前序遍歷操作定義為：若樹為空，則空操作返回；否則⑴訪問根結(jié)點(diǎn)；⑵

按照從左到右的順序前序遍歷根結(jié)點(diǎn)的每一棵子樹。

5.1樹的邏輯結(jié)構(gòu)前序遍歷序列：ABDEHIFCGACBGFEDHI后序遍歷

樹的后序遍歷操作定義為：若樹為空，則空操作返回；否則⑴按照從左到右的順序后序遍歷根結(jié)點(diǎn)的每一棵子樹；⑵

訪問根結(jié)點(diǎn)。

5.1樹的邏輯結(jié)構(gòu)后序遍歷序列：DHIEFBGCAACBGFEDHI層序遍歷

樹的層序遍歷操作定義為：從樹的第一層（即根結(jié)點(diǎn)）開始，自上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。

5.1樹的邏輯結(jié)構(gòu)層序遍歷序列：ABCDEFGHIACBGFEDHI5.2樹的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)樹的存儲(chǔ)結(jié)構(gòu)，關(guān)鍵是什么?什么是存儲(chǔ)結(jié)構(gòu)?樹中結(jié)點(diǎn)之間的邏輯關(guān)系是什么?思考問題的出發(fā)點(diǎn)：如何表示結(jié)點(diǎn)的雙親和孩子如何表示樹中結(jié)點(diǎn)之間的邏輯關(guān)系。數(shù)據(jù)元素以及數(shù)據(jù)元素之間的邏輯關(guān)系在存儲(chǔ)器中的表示。雙親表示法基本思想：用一維數(shù)組來存儲(chǔ)樹的各個(gè)結(jié)點(diǎn)（一般按層序存儲(chǔ)），數(shù)組中的一個(gè)元素對(duì)應(yīng)樹中的一個(gè)結(jié)點(diǎn)，包括結(jié)點(diǎn)的數(shù)據(jù)信息以及該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)。

5.2樹的存儲(chǔ)結(jié)構(gòu)

data

parentdata：存儲(chǔ)樹中結(jié)點(diǎn)的數(shù)據(jù)信息parent：存儲(chǔ)該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)template<classT>struct

PNode{

Tdata;//數(shù)據(jù)域

intparent;//指針域，雙親在數(shù)組中的下標(biāo)};

data

parent5.2樹的存儲(chǔ)結(jié)構(gòu)樹的雙親表示法實(shí)質(zhì)上是一個(gè)靜態(tài)鏈表。雙親表示法下標(biāo)

dataparent012345678

A-1B0C0D1E1F1G2H2I

45.2樹的存儲(chǔ)結(jié)構(gòu)如何查找雙親結(jié)點(diǎn)？時(shí)間性能？雙親表示法ACBHFEDGI5.2樹的存儲(chǔ)結(jié)構(gòu)雙親表示法ACBHFEDGI如何查找孩子結(jié)點(diǎn)？時(shí)間性能？下標(biāo)

dataparentfirstchild136-18-1-1-1-1012345678

A-1B0C0D1E1F1G2H2I

4下標(biāo)

dataparent

rightsib-12-145-17-1-15.2樹的存儲(chǔ)結(jié)構(gòu)雙親表示法012345678

A-1B0C0D1E1F1G2H2I

4ACBHFEDGI如何查找兄弟結(jié)點(diǎn)？時(shí)間性能？鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu)？5.2樹的存儲(chǔ)結(jié)構(gòu)孩子鏈表表示法方案一：指針域的個(gè)數(shù)等于樹的度datachild1child2……childd其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息；

child1~childd：指針域，指向該結(jié)點(diǎn)的孩子。

5.2樹的存儲(chǔ)結(jié)構(gòu)∧缺點(diǎn)：浪費(fèi)空間ACBHFEDGIA∧B∧C∧D∧E∧F∧G∧H∧I∧∧∧∧∧∧∧∧∧∧∧鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu)？5.2樹的存儲(chǔ)結(jié)構(gòu)孩子鏈表表示法方案二：

指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度data

degree

child1

child2

……

childd其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息；

degree：度域，存放該結(jié)點(diǎn)的度；

child1~childd：指針域，指向該結(jié)點(diǎn)的孩子。

5.2樹的存儲(chǔ)結(jié)構(gòu)缺點(diǎn)：結(jié)點(diǎn)結(jié)構(gòu)不一致ACBHFEDGIA2B3C2E1I0G0H0F0D0孩子鏈表表示法基本思想：把每個(gè)結(jié)點(diǎn)的孩子排列起來，看成是一個(gè)線性表，且以單鏈表存儲(chǔ)，則n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表。這n個(gè)單鏈表共有n個(gè)頭指針，這n個(gè)頭指針又組成了一個(gè)線性表，為了便于進(jìn)行查找采用順序存儲(chǔ)。最后，將存放n個(gè)頭指針的數(shù)組和存放n個(gè)結(jié)點(diǎn)的數(shù)組結(jié)合起來，構(gòu)成孩子鏈表的表頭數(shù)組。

5.2樹的存儲(chǔ)結(jié)構(gòu)如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu)？將結(jié)點(diǎn)的所有孩子放在一起，構(gòu)成線性表。childnext孩子結(jié)點(diǎn)struct

CTNode{

intchild;

CTNode*next;};5.2樹的存儲(chǔ)結(jié)構(gòu)template<classT>struct

CBNode{Tdata;

CTNode*firstchild;};孩子鏈表表示法datafirstchild表頭結(jié)點(diǎn)ACBHFEDGI012345678下標(biāo)

datafirstchild

ABCDEFG

H

I

∧∧∧∧5.2樹的存儲(chǔ)結(jié)構(gòu)如何查找孩子結(jié)點(diǎn)？時(shí)間性能？∧12∧345∧7∧68∧ACBHFEDGI012345678下標(biāo)

datafirstchild

ABCDEFG

H

I

∧∧∧∧∧5.2樹的存儲(chǔ)結(jié)構(gòu)12∧345∧