數(shù)據(jù)結(jié)構(gòu) 教學(xué)課件 作者 戴敏4

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

(DATASTRUCTURE)第四章矩陣的壓縮存儲(chǔ)多維數(shù)組

數(shù)組的定義及其基本操作數(shù)組的存儲(chǔ)結(jié)構(gòu)矩陣的壓縮存儲(chǔ)

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

數(shù)組的定義及其基本操作1)數(shù)組的定義數(shù)組是n(n>=0)個(gè)相同數(shù)據(jù)類型數(shù)據(jù)元素構(gòu)成的有限序列。數(shù)組可以看成是一種特殊的線性表，即線性表中數(shù)據(jù)元素本身也是一個(gè)線性表。3二維數(shù)組同樣滿足數(shù)組的定義。一個(gè)二維數(shù)組可以被看成是特殊的一維數(shù)組，其中，每個(gè)元素又是一個(gè)一維數(shù)組。多維數(shù)組可以按同樣的方法類推。()()()()()()()()()42)數(shù)組的特點(diǎn)數(shù)組中的數(shù)據(jù)元素?cái)?shù)目固定(結(jié)構(gòu)固定)

數(shù)組中的數(shù)據(jù)元素具有相同的數(shù)據(jù)類型(元素同構(gòu))

數(shù)組中的每個(gè)數(shù)據(jù)元素都與一組唯一的下標(biāo)值相對(duì)應(yīng)；數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。53)數(shù)組的基本運(yùn)算構(gòu)造n維數(shù)組銷毀n維數(shù)組存取數(shù)組元素值(給定一組下標(biāo)，存取相應(yīng)數(shù)據(jù)元素值)

修改數(shù)組元素值(給定一組下標(biāo)，修改相應(yīng)數(shù)據(jù)元素值)64.1.2

數(shù)組的順序存儲(chǔ)一個(gè)一維數(shù)組，一旦第一個(gè)元素a0的存儲(chǔ)地址Loc(a0)確定，而每個(gè)元素所占用的存儲(chǔ)空間大小為l,則第i個(gè)元素的地址可以由以下公式計(jì)算：LOC(i)=LOC(i-1)+l=α+i*l71）存儲(chǔ)方式計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)是一維的，因而多維數(shù)組必須按某種次序排成一個(gè)線性序列加以存儲(chǔ)。按行優(yōu)先方式順序存儲(chǔ)a11,a12,…a1n,a21,…,a2n,…,am1,am2,…,amn按列優(yōu)先方式順序存儲(chǔ)

a11,a21,…am1,a12,…,am2,…,a1n,a2n,…,amn二維數(shù)組與高維數(shù)組8以二維數(shù)組行優(yōu)先順序存儲(chǔ)為例：假設(shè)每個(gè)元素占用l單元由于任一元素aij

前面有i-1行,每行n個(gè)元素

LOC(aij

)=LOC(a11)+((i-1)*n+(j-1))*l按列優(yōu)先順序存儲(chǔ)：

LOC(aij

)=LOC(a11)+((j-1)*m+(i-1))*l

2）任意元素存儲(chǔ)地址的計(jì)算9推廣到n維數(shù)組

將其中的每一個(gè)元素映射到一維數(shù)組的某一個(gè)位置，各維元素個(gè)數(shù)為

m1,m2,m3,…,mn，下標(biāo)為i1,i2,i3,…,in

的數(shù)組元素的存儲(chǔ)地址：3)數(shù)據(jù)類型定義：書

104.2

特殊矩陣的壓縮存儲(chǔ)高級(jí)語言中一般用二維數(shù)組存儲(chǔ)矩陣，當(dāng)矩陣中存在大量相同的元素或零元素時(shí)，浪費(fèi)空間。矩陣的壓縮存儲(chǔ):為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間,對(duì)零元素不分配空間。

特殊矩陣：值相同的元素或零元素在矩陣中分布有一定規(guī)律。

稀疏矩陣：零元素較多，分布無規(guī)律。114.2.1

對(duì)稱矩陣在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)：則稱A為對(duì)稱矩陣。對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只需要存儲(chǔ)矩陣的上三角或下三角矩陣，這樣可以節(jié)約大約一半的空間。12在此下三角陣中,第i行恰有i個(gè)元素,元素總數(shù)為因此可將這些元素存放在一個(gè)向量S[n(n+1)/2]中a11a21a22a31a32a33.......an,1........an,na11a21a22a31a32an1

ann

…...…...k=01234n(n-1)/2n(n+1)/2-113為了便于訪問方陣A中的元素，必須在aij和S[k]之間建立一個(gè)對(duì)應(yīng)關(guān)系。若aij在下三角矩陣中，則有：若aij在上三角矩陣中，則有：

k和i、j的對(duì)應(yīng)關(guān)系為：144.2.2

三角矩陣以主對(duì)角線劃分，下三角：在多數(shù)情況下，三角矩陣的常數(shù)c為0。154.3

稀疏矩陣的壓縮存儲(chǔ)如果一個(gè)矩陣的非0元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，則稱這個(gè)矩陣為稀疏矩陣。一般來說，稀疏矩陣非0元素的分布是無規(guī)律的。因此，在存儲(chǔ)非0元素的同時(shí)，還要存儲(chǔ)適當(dāng)?shù)妮o助信息。稀疏矩陣常用的壓縮存儲(chǔ)方式：

三元組表十字鏈表164.3.1三元組表

存儲(chǔ)特點(diǎn)：

對(duì)于矩陣中每個(gè)非0元素，用它的行號(hào)、列號(hào)、元素值，即（i,j,aij）表示。將表示稀疏矩陣的所有非0元素的三元組按行優(yōu)先（列優(yōu)先）順序排列，則可得到一個(gè)其結(jié)點(diǎn)均是三元組的線性表，稱為三元組表。要唯一確定一個(gè)稀疏矩陣，還必須存儲(chǔ)該矩陣的行數(shù)和列數(shù)。17

數(shù)據(jù)類型定義：

#defineSMax1024三元組結(jié)點(diǎn)：typedef

int

datatypetyprdef

struct{inti,j;

datatypev;}SPNode;稀疏矩陣：typedef

struct

{SPNodedata[SMax+1]];

int

mu,nu,tu;/*行、列、非零元素個(gè)數(shù)*/}SPMatrix;18三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1)其中t為非零元個(gè)數(shù)6

7

8

121213931-3361443245218611564-7dataijv012345678data[0].i,data[0].j,data[0].v分別存放矩陣行列維數(shù)和非零元個(gè)數(shù)行列下標(biāo)非零元值例：19基本運(yùn)算舉例：以矩陣的轉(zhuǎn)置為例說明這種壓縮存儲(chǔ)結(jié)構(gòu)是如何實(shí)現(xiàn)矩陣運(yùn)算的。問題描述：已知一個(gè)稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表。(一個(gè)m×n矩陣A，它的轉(zhuǎn)置矩陣是一個(gè)n×m矩陣B，且A[i][j]=B[j][i]）

一般矩陣轉(zhuǎn)置算法：for(col=0;col<n;col++)for(row=0;row<m;row++)

n[col][row]=m[row][col];T(n)=O(mn)20三元組表轉(zhuǎn)置演示：21快速轉(zhuǎn)置算法思想：即按A.data[]中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入B.data[]中恰當(dāng)位置。此法關(guān)鍵是要預(yù)先確定A中每一列第一個(gè)非零元在B.data[]中位置，為確定這些位置，轉(zhuǎn)置前應(yīng)先求得A的每一列中非零元個(gè)數(shù)增設(shè)輔助數(shù)組num和cpot

。

num[col]:表示矩陣A第col列中非0元素的個(gè)數(shù)。

cpot[col]:表示第col列第一個(gè)非0元素在B.data[]中位置Cpot[1]=1Cpot[col]=cpot[col-1]+num[col-1]2<=col<=A.nu22掃描矩陣三元組表，根據(jù)某項(xiàng)的列號(hào)，確定它轉(zhuǎn)置后的行號(hào)，查cpot表，按查到的位置直接將該項(xiàng)存入轉(zhuǎn)置三元組表中。

1357889colnum[col]cpot[col]1222324150617023算法：P100

算法分析：

O(nu+tu)當(dāng)非0元素個(gè)數(shù)->mu*nu時(shí)，接近O(mu*nu)242)十字鏈表

十字鏈表是稀疏矩陣鏈接形式存儲(chǔ)結(jié)構(gòu)的一種（當(dāng)然還有其它形式）。在該方法中每一個(gè)非0元素用一個(gè)結(jié)點(diǎn)表示，結(jié)點(diǎn)中除了表示非0元素的行、列和值的三元組外，還增加了兩個(gè)鏈域：行指針域，用來指向本行中下一個(gè)非0元素；列指針域，用來指向本列中下一個(gè)非0元素。25ijv/next行指針列指針

在每一個(gè)行鏈表和每一個(gè)列鏈表增加一個(gè)和表結(jié)點(diǎn)相同的表頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)中的行、列域置為0，并且將所有的行、列鏈表和他們的頭結(jié)點(diǎn)一起鏈成一個(gè)循環(huán)鏈表。