多维数组、矩阵和广义表课件

多维数组、矩阵和广义表二维数组的特点：一维数组的特点：1个下标，ai

是ai+1的直接前驱2个下标，每个元素ai,j

受到两个关系（行关系和列关系）的约束：一个m×n

的二维数组可以看成是m行的一维数组，或者是n列的一维数组。N维数组的特点：n个下标，每个元素受到n个关系约束一个n

维数组可以看成是由若干个n-1维数组组成的线性表。

a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=5.1多维数组5.1.1数组的定义数据对象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}数据关系:

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抽象数据类型多维数组的定义ADTArray{

数据对象：

D＝{aj

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

n|

ji

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

=1,2,....,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.

构造多维数组InitArray(&A,n,bound1,...,boundn)操作结果：

若维数n

和各维长度合法，则构造相应的数组A，并返回OK。基本操作:

2.

销毁数组

DestroyArray(&A)

操作结果：释放数组A。

3.

将数组

A的某元素的值赋给变量e

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

初始条件：A

是n

维数组，e为元素变量，随后是n

个下标值。

操作结果：若各下标不超界，则

e

赋值为所指定的A

的元素值，并返回OK。

4.

为数组A的某元素赋值

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

初始条件：A

是n

维数组，e为元素变量，随后是n

个下标值。

操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。5.1.2

多维数组的存储表示类型特点:(1)一般不做插入、删除操作;

数组是多维的结构，而存储空间是一个一维的结构。

有两种顺序映象的方式:

(1)以行序为主序(低位下标优先);

(2)以列序为主序(高位下标优先);例如：

称为基地址或基址。以“行序为主序”的存储映象

二维数组A中任一元素aij

的存储位置

LOC(i,j

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

L

设二维数组A具有m

行n列,借助矩阵形式给出如下：以行为主序的存储方式：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

数组元素存储地址的计算

假设二维数组Am

n

每个元素占用L个存储单元，Loc(i,j

)为元素aij

的存储地址，Loc(0,0)

是a00存储位置,也是二维数组A的基址。

若以行序为主序的方式存储二维数组，则元素aij

的存储位置可由下式确定：

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

i+j)

L

若以列序为主序的方式存储二维数组，则元素aij

的存储位置可由下式确定：

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

j+i)

L

无论规定行优先或列优先，只要知道以下3要素，便可随时求出任一元素的地址。

这样数组中的任一元素便可以随机存取！①开始结点的存放地址（即基地址）②维数和每维的上、下界；③每个数组元素所占用的存储单元数Am

n=a00

a01a0n-1a10a11a1

n-1

am-10am-11am-1

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

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

维数组，其中任一元素的地址该如何计算？其中：Cn=L,Ci-1=bi×Ci

，

1<i≤n一个元素的长度

数组基址前面若干元素占用的地址字节总数第i维长度与所存元素个数有关的系数，可用递推法求出

教材已给出低维(行优先)优先的地址计算公式。

见（5-2）式,该式称为n维数组的映像函数。#defineMaxArrarDim8

//假设最大维数为8

typedefstruct

{

ELemType

*base;

//数组元素基址

int

dim;

//数组的维数

int

*bound;//数组各维长度bi的保存数组基址

int

*constants;

//地址函数常量Ci的保存数组基址

}Array;n

维数组的顺序存储表示

5.2特殊矩阵

－－非零元素或零元素的分布有一定规律的矩阵。

1.对称矩阵

－－在一个n

阶方阵A中，若元素满足下述性质：

aij

=aji

1≤i,j≤n

则称A为对称矩阵。

只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。

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

当i≥j

j

(j-1)/2+i-1

当i<jK=以存储下三角矩阵中元素为例，第i

行恰有i个元素，元素总数为：n(n+1)/2。

因此，可将这些元素存放在一个向量(一维数组）sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和

sa[k]之间找一个对应关系。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)下三角矩阵下（上）三角矩阵的存储和对称矩阵类似。3.对角矩阵（带状矩阵）在对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中。即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。主对角线上面的带下面的带

对角矩阵，可按行为主序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。例：三对角矩阵

a11

a12

a21

a22

a23

a32

a33

a34….

an-1n-2

an-1n-1

an-1n

ann-1

an

n

假设m

行n

列的矩阵含

t

个非零元素，则称表达式的值为稀疏因子。通常认为:

≤

0.05

的矩阵为稀疏矩阵。5.3稀疏矩阵

以常规方法－－二维数组来表示高阶的稀疏矩阵时有以下问题:(1)零值元素占了很大空间;(2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。(1)尽可能少存或不存零值元素;解决问题的原则:(2)尽可能减少没有实际意义的运算;(3)操作方便;如:

能尽可能快地找到

与下标值(i,j)对应的元素;

能尽可能快地找到

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

非零元在矩阵中的分布有一定规则.

例如：对称矩阵、三角矩阵。(2)随机稀疏矩阵

非零元在矩阵中随机出现。有两类矩阵适合压缩存储：例如：如下稀疏矩阵M－－非零元个数＜＜m×n例如：

M的存储，由矩阵的行列数（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)）惟一确定。存储原则：只存矩阵的行、列数和每个非零元的行、列下标及其值。称为三元组

对稀疏矩阵三元组表的不同的存储方法，对应稀疏矩阵不同的压缩存储方法。常见的有：一、三元组顺序表二、十字链表

#defineMaxSize12500

typedefstruct{int

i,j;//该非零元的行下标和列下标

ElemType

e;//该非零元的值

}

Triple;//三元组类型一、三元组顺序表typedefstruct{

Triple

data

[MaxSize+1];

//0号单元不用

int

mu,nu,tu;//行数,列数,非0元个数.}TSMatrix;

//稀疏矩阵类型

M的三元组顺序表图示

M

=

012

900000000000-3000014000240000018000001500-7000

设M是TSMatrix

类型的结构变量，则M有4

个域，其中M.data用于存储矩阵M的三元组表，如右图所示:

ije01234567831

-361

1512

1252

1813

943

2464

-736

14M.data678M.muM.nuM.tu按行序有序矩阵的运算－－如何求转置矩阵？矩阵MM的转置矩阵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

?用常规的二维数组表示时的算法

其时间复杂度为:O(n×m

)

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

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

矩阵转置算法－－

算法5.6

基本思想:

对三元组表的M.data

从头至尾扫描：第1次扫描时，将M.data中所有列号为

1的三元组赋值到T.data中；第2次扫描时，将M.data中所有列号为

2的三元组赋值到T.data中；

依此类推，直至第M.nu

次扫描，将M.data中所有所有列号为

n

的三元组赋值到T.data中。用“三元组”表示时，实现矩阵转置。121515-522-731363428211551-522-713364328M.dataT.data算法

5.1（P.99）图示用三元组表示，实现矩阵快速转置。121515-522-731363428211551-522-713364328算法

5.2（P.100）图示12345

快速转置算法思想：

为了求得M.data

各列第1个三元组在T.data中的位置,

设置两个辅助向量:num[]、cpos[]。

num[col

]：存储第col

列非零元个数。

cpos[col

]：存储第col

列第1个三元组在T.data中的位置。

cpos[col

]的计算方法是：

cpos[1]=1

cpos[col

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

≤

col

≤

ncolnum[col]cpot[col]1234567

22811001352784539上一列的起始位置上一列非零元个数

快速转置算法主要步骤：1.求M

中各列非零元个数，在于

num[]数组;2.求M中各列第1个非零元在T.data中的下标cpos[].3.对M.data

进行1

次扫描，遇到col

列的第1个三元组时，按cpos[col

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

中，当再次遇到col

列的三元组时，只须顺序放到T.data

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

12345678a.dataije

12345678b.datacolnum[col]cpot[col]11223235247158068179013-3161521122518319342446-76314pppppppp4629753快速转置算法图示：

分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为: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)……二、十字链表－－稀疏矩阵的链式存储设行指针数组和列指针数组，分别指向每行、每列的第1

个非零元结点。用途：方便稀疏矩阵的加减运算。方法：每个非0

元素用5个域组成的结点表示.

十字链表的特点：（1）每行非零元素链接成一个行链表；

每列非零元素链接成一个列链表。（2）每个非零元素既是行链表中的一个结点,

又是列链表中的一个结点。

即结构成呈十字链状。typedefstruct

//十字链表结点结构

{int

i,j;

//该非零元的行和列下标

ElemType

e;

//非零元素值

struct

OLNode

*right,

*down;//该非零元所在

}OLNode,*OLink;//行表和列表的后继链域

typedefstruct

//十字链表结构

{

Olink*rhead,*chead;//行列链表头指针向量基址

int

mu,nu,tu;

//稀疏矩阵的行列数和非零元个数

}CrossList;十字链表类型定义十字链表结点示意：right

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

chead

rhead

mu

行数

nu

列数

tu十字链表结构示意：非零元个数十字链表示例：5.4

广义表广义表是线性表的推广，也称为列表（lists）记为：LS=(a1,a2,……，an)

广义表名表头(Head）

表尾(Tail)1.概念①第1个元素是表头，而其余元素组成的表称为表尾；②用小写字母表示原子类型，用大写字母表示列表。n是表长

在广义表中约定：

广义表与线性表的区别和联系？

广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型相同时，就是线性表。(a2,……，

an

)单个元素2.特点有次序性有长度有深度可递归可共享一个直接前驱和一个直接后继定义为表中最外层包含的元素个数为表中括号的重数。原子深度为0，空表深度为1广义表可以作为自己的子表。长度有限,深度无穷广义表可以为其他广义表所共享。注意：

任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。

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，因为A是空表。h=1n=1，表中元素e

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

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

个元素都是子表。h=3n=2，a

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

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

共享表ABDCeabcd②A=(a,(b,A))例2：试用图形表示下列广义表。

设代表原子，代表子表。

①

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

)))Aab①的长度为3，深度为3②的长度为2，深度为∞深度＝最大括号的重数＝结点的层数ADTGlist

{数据对象：

D＝{ei

|

i

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

ei∈AtomSet

或

ei∈GList,

AtomSet

为某个数据对象集}

数据关系：

LR＝{<ei-1,ei>|

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

基本操作：……}ADTGlist3.广义表的抽象数据类型定义两种最基本的操作：

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：求下列广义表的操作结果。(k,p,h)(b)(a,b)5.GetTail

(e)＝

;6.GetHead(())＝

;7.GetTail(())＝

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

广义表的存储结构

由于广义表的元素可以是原子或列表，所以通常采用链式存储结构，每个元素用一个结点表示。

1.原子结点－－表示原子atomtag=0

标志域