數(shù)據(jù)結(jié)構(gòu)ch5數(shù)組

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

a11a12…a1na21

a22…a2n

…………

am1am2…amnA=

a11a12…a1na21a22…a2n

…………

am1am2…amnA=

A=(A1，A2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)數(shù)組——線性表的推廣二維數(shù)組是數(shù)據(jù)元素為線性表的線性表。數(shù)組的基本概念

A=(A1，A2，……，Am)其中：Ai=(ai1，ai2，……，ain)(1≤i≤m)數(shù)組的基本操作在數(shù)組中插入（或刪除）一個元素有意義嗎？

a11a12…a1na21a22…a2n

…………

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

a11a12…a1na21a22…a2n

…………

am1am2…amnA=刪除數(shù)組中第1行第2列元素。數(shù)組的基本概念數(shù)組的基本操作⑴存?。航o定一組下標(biāo)，讀出對應(yīng)的數(shù)組元素；⑵修改：給定一組下標(biāo)，存儲或修改與其相對應(yīng)的數(shù)組元素。存取和修改操作本質(zhì)上只對應(yīng)一種操作——尋址數(shù)組應(yīng)該采用何種方式存儲？數(shù)組沒有插入和刪除操作，不用預(yù)留空間，適合采用順序存儲。數(shù)組的基本概念設(shè)一維數(shù)組的下標(biāo)的范圍為閉區(qū)間［0，h］，每個數(shù)組元素占用c個存儲單元，則其任一元素ai的存儲地址可由下式確定：Loc(ai)＝Loc(a0)＋i×c

ca0ai-1ai……aha1……Loc(a0)Loc(ai)數(shù)組的存儲結(jié)構(gòu)——一維數(shù)組二維數(shù)組常用的映射方法有兩種：按行優(yōu)先：先行后列，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。

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

N維數(shù)組內(nèi)存N維結(jié)構(gòu)一維結(jié)構(gòu)數(shù)組的存儲結(jié)構(gòu)事先約定按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存入存儲器中。在二維數(shù)組中，既可以規(guī)定按行優(yōu)先次序存儲，也可以規(guī)定按列優(yōu)先次序存儲。0h2

0h1(a)二維數(shù)組aij前面的元素個數(shù)=陰影部分的面積=整行數(shù)×每行元素個數(shù)+本行中aij前面的元素個數(shù)=i×(h2＋1)＋j

本行中aij前面的元素個數(shù)每行元素個數(shù)整行數(shù)aij按行優(yōu)先存儲的尋址數(shù)組的存儲結(jié)構(gòu)——二維數(shù)組第1行第2行a00…a0h2a10…a1h2……aij…ah1h2Loc(aij)Loc(a00)i×(h2＋1)＋j

個元素Loc(aij)＝Loc(a00)＋(i×(h2＋1)＋j)×c按列優(yōu)先存儲的尋址方法與此類似。數(shù)組的存儲結(jié)構(gòu)——二維數(shù)組按行優(yōu)先存儲的尋址

設(shè)一個10001000的矩陣中有800個非零元素，若用二維數(shù)組存儲存放所有的數(shù)組元素需要106個存儲單元，而最后影響計算結(jié)果的只是那800個非零元素。因此，需要考慮高效的存儲方法，根據(jù)數(shù)據(jù)分布特征進(jìn)行壓縮存儲。矩陣的壓縮存儲

1.特殊矩陣的壓縮存儲

2.稀疏矩陣的壓縮存儲矩陣的壓縮存儲特殊矩陣：值相同的元素或零元素分布具有一定規(guī)律，如對稱矩陣、三角矩陣、對角矩陣等。

稀疏矩陣：矩陣中有很多零元素，且無規(guī)律。壓縮存儲的基本思想是：為多個值相同的元素只分配一個存儲空間；對零元素不分配存儲空間。3647862842481697460582957A＝對稱矩陣特點(diǎn)：aij=aji如何壓縮存儲？只存儲下三角（或上三角）部分的元素。特殊矩陣的壓縮存儲——對稱陣(a)下三角矩陣(b)存儲說明(c)計算方法aij在一維數(shù)組中的序號=陰影部分的面積=

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每行元素個數(shù)12…iaij在本行中的序號aij第0行第1行…第i-1行特殊矩陣的壓縮存儲——對稱陣對于下三角中的元素aij（i≥j），在數(shù)組SA中的下標(biāo)k與i、j的關(guān)系為：k＝i×(i＋1)/2＋j。上三角中的元素aij（i＜j），因為aij＝aji，則訪問和它對應(yīng)的元素aji即可，即：k＝j(luò)×(j＋1)/2＋i。第1行第n-1行第0行

a00

a10

a11

a20

a21

a22

aij…

an-10

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

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

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

當(dāng)i≥jn×(n＋1)/2當(dāng)i＜jk=012345

k

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

a00

a10

a11

a20

a21

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

c

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

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

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

c１578c

c

c

082c

c

c

c71c

c

c

c

c

11500000

011

0000

000600

000000

9

00000A=如何進(jìn)行壓縮存儲？注意：稀疏矩陣中的非零元素或相同值元素的分布沒有規(guī)律。特殊矩陣的壓縮存儲——稀疏矩陣僅存儲非零元素。元素值元素的位置typedefstruct{

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

0110000

000600

0000009

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

0113000

000600

00000091

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

空空空閑閑閑rowcolitem0123456MaxTerm-11500220-15

0113000

000600

00000091

00000A=7（非零元個數(shù)）是否對應(yīng)惟一的稀疏矩陣？5（矩陣的行數(shù)）6（矩陣的列數(shù)）稀疏矩陣的壓縮存儲——三元組存儲結(jié)構(gòu)定義：typedefstruct{

introw,col;//行號，列號ElemTypeitem;//非零元素值}Triple;typedefstruct{Tripledata[MAXSIZE];//存儲非零元素intmu,nu,tu;//行數(shù)，列數(shù)，非零元個數(shù)}TSMatrix;稀疏矩陣的壓縮存儲——三元組例：15000910110000300022060000000-150000B=1500220-15

0113000

000600

00000091

00000A=三元組順序表操作——轉(zhuǎn)置操作0015032205-1511111232364091

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

1111

213

3022

326

50-15

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

0015032205-1511111232364091

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

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個數(shù)）三元組順序表操作——轉(zhuǎn)置算法10015032205-1511111232364091

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

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

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

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

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

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

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

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

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

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

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

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

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

rowcolitem0123456MaxTerm-16（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個數(shù)）001504911111213302232650-15在矩陣A中查找第6列非零元，順序存儲到矩陣B中1.設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元個數(shù)；2.在B中設(shè)置初始存儲位置q；3.for(col=最小列號;col<=最大列號;col++)3.1在A中依次查找所有列號為col的三元組；3.1.1交換其行號和列號，存入B中q位置；3.1.2q++；三元組順序表操作——轉(zhuǎn)置算法1轉(zhuǎn)置算法（采用三元組表存儲表示）：StatusTranspose(TSMatrixA,TSMatrix&B){B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;if(B.tu)

{q=1;

//q為M.data[]中三元組的下標(biāo)

for(col=1;col<=A.nu;++col)//掃描M.data[]M.nu遍

for(p=1;p<=A.tu;++p){//p為T.data[]中三元組的下標(biāo)

if(A.data[p].j==col){B.data[q].i=A.data[p].j;B.data[q].j=A.data[p].i;B.data[q].e=A.data[p].e;++q;}

}

returnOK;}

算法的基本操作為將A.data[]中的三元組賦值到B.data[]，是在p和col兩重循環(huán)中完成的，故算法的時間復(fù)雜度為

O(nt),

其中n為矩陣的列數(shù)，

t為矩陣M非零元素個數(shù)。時間復(fù)雜度分析

該算法效率不高的原因是：為實(shí)現(xiàn)矩陣A到矩陣B的轉(zhuǎn)置，對A.data[]進(jìn)行了多次掃描。能否在對A.data[]一次掃描的過程中，完成A

到B

的轉(zhuǎn)置？分析：A中第0列的第一個非零元素一定存儲在B中下標(biāo)為0的位置上，該列中其它非零元素應(yīng)存放在B中后面連續(xù)的位置上，那么第1列的第一個非零元素在B中的位置便等于第0列的第一個非零元素在B中的位置加上第0列的非零元素的個數(shù)，以此類推?；舅枷耄喉樞蛉。苯哟?。即在A中依次取三元組，交換其行號和列號放到B中適當(dāng)位置。如何確定當(dāng)前從A中取出的三元組在B中的位置？三元組順序表操作——轉(zhuǎn)置算法2引入兩個數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：cnum[cols]：存儲矩陣A中某列的非零元素的個數(shù)；cpot[clos]：初值表示矩陣A中某列的第一個非零元素在B中的位置。數(shù)據(jù)結(jié)構(gòu)設(shè)計：cpot[0]=0；cpot[col]=cpot[col-1]+cnum[col-1]；1≤col＜colscnum與cpot存在如下遞推關(guān)系：三元組順序表操作——轉(zhuǎn)置算法20015032205-1511111232364091

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

col012345cnum[col]21

12

01cpot[col]

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

0015032205-1511111232364091

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

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

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

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個數(shù)）cpot[1]cpot[2]cpot[3]cpot[4]cpot[5]0015cpot[0]3022cpot[3]0015032205-1511111232364091

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

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個數(shù)）cpot[1]cpot[2]cpot[4]0015cpot[0]3022cpot[3]50-15cpot[5]cpot[5]0015032205-1511111232364091

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

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個數(shù)）cpot[1]cpot[2]cpot[4]0015cpot[0]3022cpot[3]50-15cpot[5]1111cpot[1]0015032205-1511111232364091

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

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個數(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（非零元個數(shù)）將矩陣A中col列元素存放在B中下標(biāo)為cpot[col]的位置

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個數(shù)）cpot[4]0015cpot[0]3022cpot[3]50-15cpot[5]1111213cpot[2]cpot[1]326cpot[3]0015032205-1511111232364091

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

rowcolitem01234566（矩陣的行數(shù)）5（矩陣的列數(shù)）7（非零元個數(shù)）cpot[4]0015cpot[0]302250-15cpot[5]1111213cpot[2]cpot[1]326cpot[3]0491cpot[0]1.設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元素的個數(shù)；2.計算A中每一列的非零元素個數(shù)cnum[col]；3.計算A中每一列的第一個非零元素在B中的下標(biāo)cpot[col]；4.依次取A中的每一個非零元素對應(yīng)的三元組；