多維數(shù)組、矩陣和廣義表課件

多維數(shù)組、矩陣和廣義表二維數(shù)組的特點(diǎn)：一維數(shù)組的特點(diǎn)：1個(gè)下標(biāo)，ai

是ai+1的直接前驅(qū)2個(gè)下標(biāo)，每個(gè)元素ai,j

受到兩個(gè)關(guān)系（行關(guān)系和列關(guān)系）的約束：一個(gè)m×n

的二維數(shù)組可以看成是m行的一維數(shù)組，或者是n列的一維數(shù)組。N維數(shù)組的特點(diǎn)：n個(gè)下標(biāo)，每個(gè)元素受到n個(gè)關(guān)系約束一個(gè)n

維數(shù)組可以看成是由若干個(gè)n-1維數(shù)組組成的線性表。

a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=5.1多維數(shù)組5.1.1數(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}b1=mb2=n抽象數(shù)據(jù)類型多維數(shù)組的定義ADTArray{

數(shù)據(jù)對象：

D＝{aj

1j2,...,ji...,j

n|

ji

=0,...,bi-1,i

=1,2,....,n}

數(shù)據(jù)關(guān)系：

R＝{R1,R2,...,Rn}

Ri＝{<aj1,...,

ji,...,

jn

,aj1,...,ji+1,...,jn

>|0≤

jk

≤

bk-1,1≤

k

≤n

且

k

i,0≤

ji

≤bi-2,i

=1,...,n}

}基本操作:1.

構(gòu)造多維數(shù)組InitArray(&A,n,bound1,...,boundn)操作結(jié)果：

若維數(shù)n

和各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。基本操作:

2.

銷毀數(shù)組

DestroyArray(&A)

操作結(jié)果：釋放數(shù)組A。

3.

將數(shù)組

A的某元素的值賦給變量e

Value(A,&e,index1,...,indexn)

初始條件：A

是n

維數(shù)組，e為元素變量，隨后是n

個(gè)下標(biāo)值。

操作結(jié)果：若各下標(biāo)不超界，則

e

賦值為所指定的A

的元素值，并返回OK。

4.

為數(shù)組A的某元素賦值

Assign(&A,e,index1,...,indexn)

初始條件：A

是n

維數(shù)組，e為元素變量，隨后是n

個(gè)下標(biāo)值。

操作結(jié)果：若下標(biāo)不超界，則將e的值賦給所指定的A的元素，并返回OK。5.1.2

多維數(shù)組的存儲(chǔ)表示類型特點(diǎn):(1)一般不做插入、刪除操作;

數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是一個(gè)一維的結(jié)構(gòu)。

有兩種順序映象的方式:

(1)以行序?yàn)橹餍?低位下標(biāo)優(yōu)先);

(2)以列序?yàn)橹餍?高位下標(biāo)優(yōu)先);例如：

稱為基地址或基址。以“行序?yàn)橹餍颉钡拇鎯?chǔ)映象

二維數(shù)組A中任一元素aij

的存儲(chǔ)位置

LOC(i,j

)=LOC(0,0)+(3×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

設(shè)二維數(shù)組A具有m

行n列,借助矩陣形式給出如下：以行為主序的存儲(chǔ)方式：a00

a01

a0n-1

a10

a11

a1n-1

am-10

am-11

am-1n-101…

n-1nn+1…

2n-1…

mn-1Am

n=a00a01a0n-1a10a11a1

n-1

am-10am-11am-1

n-1以列為主序的方式：a00

a10

am-10

a01

a11

am-11

a0n-1

a1n-1

am-1n-101…

m-1m

m+1…2m-1…

nm-1

數(shù)組元素存儲(chǔ)地址的計(jì)算

假設(shè)二維數(shù)組Am

n

每個(gè)元素占用L個(gè)存儲(chǔ)單元，Loc(i,j

)為元素aij

的存儲(chǔ)地址，Loc(0,0)

是a00存儲(chǔ)位置,也是二維數(shù)組A的基址。

若以行序?yàn)橹餍虻姆绞酱鎯?chǔ)二維數(shù)組，則元素aij

的存儲(chǔ)位置可由下式確定：

Loc(i,j)=Loc(0,0)+(n

i+j)

L

若以列序?yàn)橹餍虻姆绞酱鎯?chǔ)二維數(shù)組，則元素aij

的存儲(chǔ)位置可由下式確定：

Loc(i,j)=Loc(0,0)+（m

j+i)

L

無論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下3要素，便可隨時(shí)求出任一元素的地址。

這樣數(shù)組中的任一元素便可以隨機(jī)存?。、匍_始結(jié)點(diǎn)的存放地址（即基地址）②維數(shù)和每維的上、下界；③每個(gè)數(shù)組元素所占用的存儲(chǔ)單元數(shù)Am

n=a00

a01a0n-1a10a11a1

n-1

am-10am-11am-1

n-1LOC(j1,j2,…,jn

)=LOC(0,0,…,0)＋若是n

維數(shù)組，其中任一元素的地址該如何計(jì)算？其中：Cn=L,Ci-1=bi×Ci

，

1<i≤n一個(gè)元素的長度

數(shù)組基址前面若干元素占用的地址字節(jié)總數(shù)第i維長度與所存元素個(gè)數(shù)有關(guān)的系數(shù)，可用遞推法求出

教材已給出低維(行優(yōu)先)優(yōu)先的地址計(jì)算公式。

見（5-2）式,該式稱為n維數(shù)組的映像函數(shù)。#defineMaxArrarDim8

//假設(shè)最大維數(shù)為8

typedefstruct

{

ELemType

*base;

//數(shù)組元素基址

int

dim;

//數(shù)組的維數(shù)

int

*bound;//數(shù)組各維長度bi的保存數(shù)組基址

int

*constants;

//地址函數(shù)常量Ci的保存數(shù)組基址

}Array;n

維數(shù)組的順序存儲(chǔ)表示

5.2特殊矩陣

－－非零元素或零元素的分布有一定規(guī)律的矩陣。

1.對稱矩陣

－－在一個(gè)n

階方陣A中，若元素滿足下述性質(zhì)：

aij

=aji

1≤i,j≤n

則稱A為對稱矩陣。

只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每兩個(gè)對稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。

i(i-1)/2+j-1

當(dāng)i≥j

j

(j-1)/2+i-1

當(dāng)i<jK=以存儲(chǔ)下三角矩陣中元素為例，第i

行恰有i個(gè)元素，元素總數(shù)為：n(n+1)/2。

因此，可將這些元素存放在一個(gè)向量(一維數(shù)組）sa[0..n(n+1)/2-1]中。為了便于訪問對稱矩陣A中的元素，我們必須在aij和

sa[k]之間找一個(gè)對應(yīng)關(guān)系。a11a21a22a31a32a33……

an,nk=012345….….n(n+1)/2-1

2.

三角矩陣

上三角或下三角。

a11

a11…a

1n

a11

c…c

c

a11…a

1n

a21

a22

…c

……………..…………

….

cc…

an

n

an1an2…an

n

(a)上三角矩陣(b)下三角矩陣下（上）三角矩陣的存儲(chǔ)和對稱矩陣類似。3.對角矩陣（帶狀矩陣）在對角矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中。即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。主對角線上面的帶下面的帶

對角矩陣，可按行為主序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對應(yīng)關(guān)系。例：三對角矩陣

a11

a12

a21

a22

a23

a32

a33

a34….

an-1n-2

an-1n-1

an-1n

ann-1

an

n

假設(shè)m

行n

列的矩陣含

t

個(gè)非零元素，則稱表達(dá)式的值為稀疏因子。通常認(rèn)為:

≤

0.05

的矩陣為稀疏矩陣。5.3稀疏矩陣

以常規(guī)方法－－二維數(shù)組來表示高階的稀疏矩陣時(shí)有以下問題:(1)零值元素占了很大空間;(2)計(jì)算中進(jìn)行了很多和零值的運(yùn)算，遇除法，還需判別除數(shù)是否為零。(1)盡可能少存或不存零值元素;解決問題的原則:(2)盡可能減少?zèng)]有實(shí)際意義的運(yùn)算;(3)操作方便;如:

能盡可能快地找到

與下標(biāo)值(i,j)對應(yīng)的元素;

能盡可能快地找到

同一行或同一列的非零值元;(1)特殊矩陣

非零元在矩陣中的分布有一定規(guī)則.

例如：對稱矩陣、三角矩陣。(2)隨機(jī)稀疏矩陣

非零元在矩陣中隨機(jī)出現(xiàn)。有兩類矩陣適合壓縮存儲(chǔ)：例如：如下稀疏矩陣M－－非零元個(gè)數(shù)＜＜m×n例如：

M的存儲(chǔ)，由矩陣的行列數(shù)（6,7）和三元組表:((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)）惟一確定。存儲(chǔ)原則：只存矩陣的行、列數(shù)和每個(gè)非零元的行、列下標(biāo)及其值。稱為三元組

對稀疏矩陣三元組表的不同的存儲(chǔ)方法，對應(yīng)稀疏矩陣不同的壓縮存儲(chǔ)方法。常見的有：一、三元組順序表二、十字鏈表

#defineMaxSize12500

typedefstruct{int

i,j;//該非零元的行下標(biāo)和列下標(biāo)

ElemType

e;//該非零元的值

}

Triple;//三元組類型一、三元組順序表typedefstruct{

Triple

data

[MaxSize+1];

//0號(hào)單元不用

int

mu,nu,tu;//行數(shù),列數(shù),非0元個(gè)數(shù).}TSMatrix;

//稀疏矩陣類型

M的三元組順序表圖示

M

=

012

900000000000-3000014000240000018000001500-7000

設(shè)M是TSMatrix

類型的結(jié)構(gòu)變量，則M有4

個(gè)域，其中M.data用于存儲(chǔ)矩陣M的三元組表，如右圖所示:

ije01234567831

-361

1512

1252

1813

943

2464

-736

14M.data678M.muM.nuM.tu按行序有序矩陣的運(yùn)算－－如何求轉(zhuǎn)置矩陣？矩陣MM的轉(zhuǎn)置矩陣TM

=T

=3×55×3

ije01234522

-71

2

141

5

-53

4

283

1

36

ije01234522

-721

1451

-543

2813

36

ije01234522

-713

3621

1451

-543

28M.dataT.dataT.data

?用常規(guī)的二維數(shù)組表示時(shí)的算法

其時(shí)間復(fù)雜度為:O(n×m

)

for(col=1;col<=n;++col)

for(row=1;row<=m;++row)T[col][row]=M[row][col];列數(shù)行數(shù)

矩陣轉(zhuǎn)置算法－－

算法5.6

基本思想:

對三元組表的M.data

從頭至尾掃描：第1次掃描時(shí)，將M.data中所有列號(hào)為

1的三元組賦值到T.data中；第2次掃描時(shí)，將M.data中所有列號(hào)為

2的三元組賦值到T.data中；

依此類推，直至第M.nu

次掃描，將M.data中所有所有列號(hào)為

n

的三元組賦值到T.data中。用“三元組”表示時(shí)，實(shí)現(xiàn)矩陣轉(zhuǎn)置。121515-522-731363428211551-522-713364328M.dataT.data算法

5.1（P.99）圖示用三元組表示，實(shí)現(xiàn)矩陣快速轉(zhuǎn)置。121515-522-731363428211551-522-713364328算法

5.2（P.100）圖示12345

快速轉(zhuǎn)置算法思想：

為了求得M.data

各列第1個(gè)三元組在T.data中的位置,

設(shè)置兩個(gè)輔助向量:num[]、cpos[]。

num[col

]：存儲(chǔ)第col

列非零元個(gè)數(shù)。

cpos[col

]：存儲(chǔ)第col

列第1個(gè)三元組在T.data中的位置。

cpos[col

]的計(jì)算方法是：

cpos[1]=1

cpos[col

]=cpos[col-1]+num[col-1]，2

≤

col

≤

ncolnum[col]cpot[col]1234567

22811001352784539上一列的起始位置上一列非零元個(gè)數(shù)

快速轉(zhuǎn)置算法主要步驟：1.求M

中各列非零元個(gè)數(shù)，在于

num[]數(shù)組;2.求M中各列第1個(gè)非零元在T.data中的下標(biāo)cpos[].3.對M.data

進(jìn)行1

次掃描，遇到col

列的第1個(gè)三元組時(shí)，按cpos[col

]的位置，將其放至T.data

中，當(dāng)再次遇到col

列的三元組時(shí)，只須順序放到T.data

中col列元素的后面。121213931-3361443245218611564-7ije

12345678a.dataije

12345678b.datacolnum[col]cpot[col]11223235247158068179013-3161521122518319342446-76314pppppppp4629753快速轉(zhuǎn)置算法圖示：

分析算法FastTransposeSMatrix的時(shí)間復(fù)雜度：時(shí)間復(fù)雜度為:O(

M.nu+M.tu)

for(col=1;col<=M.nu;++col)……for(t=1;t<=M.tu;++t)……for(col=2;col<=M.nu;++col)……for(p=1;p<=M.tu;++p)……二、十字鏈表－－稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)設(shè)行指針數(shù)組和列指針數(shù)組，分別指向每行、每列的第1

個(gè)非零元結(jié)點(diǎn)。用途：方便稀疏矩陣的加減運(yùn)算。方法：每個(gè)非0

元素用5個(gè)域組成的結(jié)點(diǎn)表示.

十字鏈表的特點(diǎn)：（1）每行非零元素鏈接成一個(gè)行鏈表；

每列非零元素鏈接成一個(gè)列鏈表。（2）每個(gè)非零元素既是行鏈表中的一個(gè)結(jié)點(diǎn),

又是列鏈表中的一個(gè)結(jié)點(diǎn)。

即結(jié)構(gòu)成呈十字鏈狀。typedefstruct

//十字鏈表結(jié)點(diǎn)結(jié)構(gòu)

{int

i,j;

//該非零元的行和列下標(biāo)

ElemType

e;

//非零元素值

struct

OLNode

*right,

*down;//該非零元所在

}OLNode,*OLink;//行表和列表的后繼鏈域

typedefstruct

//十字鏈表結(jié)構(gòu)

{

Olink*rhead,*chead;//行列鏈表頭指針向量基址

int

mu,nu,tu;

//稀疏矩陣的行列數(shù)和非零元個(gè)數(shù)

}CrossList;十字鏈表類型定義十字鏈表結(jié)點(diǎn)示意：right

downeji同一列中下一非零元素的指針同一行中下一非零元素的指針

chead

rhead

mu

行數(shù)

nu

列數(shù)

tu十字鏈表結(jié)構(gòu)示意：非零元個(gè)數(shù)十字鏈表示例：5.4

廣義表廣義表是線性表的推廣，也稱為列表（lists）記為：LS=(a1,a2,……，an)

廣義表名表頭(Head）

表尾(Tail)1.概念①第1個(gè)元素是表頭，而其余元素組成的表稱為表尾；②用小寫字母表示原子類型，用大寫字母表示列表。n是表長

在廣義表中約定：

廣義表與線性表的區(qū)別和聯(lián)系？

廣義表中元素既可以是原子類型，也可以是列表；當(dāng)每個(gè)元素都為原子且類型相同時(shí)，就是線性表。(a2,……，

an

)單個(gè)元素2.特點(diǎn)有次序性有長度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼定義為表中最外層包含的元素個(gè)數(shù)為表中括號(hào)的重?cái)?shù)。原子深度為0，空表深度為1廣義表可以作為自己的子表。長度有限,深度無窮廣義表可以為其他廣義表所共享。注意：

任何一個(gè)非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。

E=(a,E)=(a,(a,E))=(a,(a,(a,…….)))

E為遞歸表(1)A=()(2)B=(e)(3)C=(a,(b,c,d))(4)D

=(A,B,C)(5)E

=(a,E)例1：求下列廣義表的長度

n、深度

h

。n=0，因?yàn)锳是空表。h=1n=1，表中元素e

是原子。h=1n=2，a

為原子,(b,c,d)為子表.h=2n=3，3

個(gè)元素都是子表。h=3n=2，a

為原子，E為子表。h=∞

D=(A,B,C)=((),(e),(a,(b,c,d)))

共享表ABDCeabcd②A=(a,(b,A))例2：試用圖形表示下列廣義表。

設(shè)代表原子，代表子表。

①

D=(A,B,C)=((),(e),(a,(b,c,d

)))Aab①的長度為3，深度為3②的長度為2，深度為∞深度＝最大括號(hào)的重?cái)?shù)＝結(jié)點(diǎn)的層數(shù)ADTGlist

{數(shù)據(jù)對象：

D＝{ei

|

i

=1,2,…,n;n≥0;

ei∈AtomSet

或

ei∈GList,

AtomSet

為某個(gè)數(shù)據(jù)對象集}

數(shù)據(jù)關(guān)系：

LR＝{<ei-1,ei>|

ei-1,ei∈D,2≤i≤n}

基本操作：……}ADTGlist3.廣義表的抽象數(shù)據(jù)類型定義兩種最基本的操作：

GetHead(

L)－－取表頭（可能是原子或列表）

GetTail(L)

－－取表尾（一定是列表）。1.GetTail(b,k,p,h)＝

;2.GetHead

((a,b),(c,d))

＝

;3.GetTail

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

;4.GetTail

(GetHead

((a,b),(c,d)))

＝

;例3：求下列廣義表的操作結(jié)果。(k,p,h)(b)(a,b)5.GetTail

(e)＝

;6.GetHead(())＝

;7.GetTail(())＝

;()(a,b)()()((c,d))表尾定是列表

廣義表的存儲(chǔ)結(jié)構(gòu)

由于廣義表的元素可以是原子或列表，所以通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)元素用一個(gè)結(jié)點(diǎn)表示。

1.原子結(jié)點(diǎn)－－表示原子atomtag=0

標(biāo)志域