济南大学数据结构 第五章.docx

济南大学数据结构 第五章.docx

《济南大学数据结构 第五章.docx》由会员分享，可在线阅读，更多相关《济南大学数据结构 第五章.docx（13页珍藏版）》请在冰点文库上搜索。

济南大学数据结构第五章

第五章数组和广义表

数组和广义表均是元素为复合结构的线性结构。

5.1数组的定义

以二维数组为例，

二维数组通常可以描述为两种形式:

以行序为主序:

PASCAL、C

可以看成A=（α0，α1，...，αm-1）T

其中αi是一个行向量形式的线性表，0≤i≤m-1

αi=（ai0，ai1，...，ain-1）

以列序为主序:

FORTRAN

可以看成A=（α0，α1，……，αn-1）

其中αj是一个列向量形式的线性表，0≤j≤n-1

αj=（a0j，a1j，……，am-1j）T

5.2数组的表示和实现

数组一旦被定义，其维数和维界就不再改变，故通常采用顺序存储结构。

如何将多维数组结构转换对应一组连续的存储单元？

以列序为主序

以行序为主序

对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置?

设数组以行序为主序。

二维数组A[m][n]

数组元素aij的存储位置为

LOC（i，j）=LOC（0，0）+（n×i+j）L

LOC（0，0）是a00的存储位置；

L是每个数组元素占用的存储单元数；

例，LOC（1，1）=LOC（0，0）+（n×1+1）L

三维数组A（b1，b2，b3）

LOC（0，0，0）是a000的存储位置；

L是每个数组元素占用的存储单元数；

LOC（1，1，1）=LOC（0，0，0）+（b2×b3×1+b3×1+1）L

数组元素aijk的存储位置为:

LOC（i，j，k）=LOC（0，0，0）+（b2×b3×i+b3×j+k）L

n维数组A（b1，b2，…，bn）的元素存储位置可计算为:

LOC（j1,j2,……,jn）

=LOC（0,0,……,0）+

（b2×……×bn×j1+b3×……×bn×j2+……+bn×jn-1+jn）L

5.3矩阵的压缩存储

矩阵元素如何存储？

通常利用二维数组来存储矩阵元素。

B[m][n]

aijbi-1,j-1

实际中，存在许多特殊矩阵，例如在矩阵中有许多值相同的元素或者零元素。

用定长数组存储造成浪费。

为了节省存储空间，需要对这类矩阵进行压缩存储。

压缩存储是指为多个值相同的元素只分配一个存储空间；对零元素不分配空间。

Ø对称矩阵

Ø三角矩阵

Ø对角矩阵

Ø稀疏矩阵

n阶对称矩阵

n阶矩阵A满足:

aij=aji

通常表示为:

n2个矩阵元素只需占用n（n+1）/2个存储空间

设计用一维数组SA[n（n+1）/2]存储n阶对称矩阵A。

关键问题:

如何建立数组元SA[k]和矩阵元aij之间的一一对应关系。

K一定是i，j的函数

ai+bj+c

=ai+j+c

=an+1+c

=

a=

b=1,c=-1

三角矩阵

所谓下（上）三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元均为常数c的n阶矩阵。

下三角矩阵

和对称矩阵基本一样，只需除存储其下（上）三角中的元之外，再增加一个存储单元存放c。

关键问题:

如何建立数组元SA[k]和矩阵元aij之间的一一对应关系。

对角矩阵

所有的非零元都集中在以主对角线为中心的带状区域中。

一般情况三对角矩阵

关键问题:

如何建立数组元SA[k]和矩阵元aij之间的一一对应关系。

K一定是i，j的函数

ai+bj+c

=ai+j+c

=a（n-1）+（n-2）+c

=3n-7

代入解得：

a=2,b=1,c=-3

K=2i+j-3

（|i-j|≤1）

作业:

五对角矩阵

稀疏矩阵

非零元很少的矩阵。

稀疏因子:

设m×n的矩阵，有t个非零元，令

通常认为δ≤0.05时称为稀疏矩阵。

稀疏矩阵的压缩存储

Ø三元组顺序表

Ø行逻辑链接顺序表

Ø十字链表

三元组顺序表

三元组（i，j，aij）表示非零元素

i行数，j列数，aij非零元。

5.4广义表的定义

广义表（列表）LS=（a1，a2，，an）

LS:

列表名称

n:

列表长度（元素的个数）

ai:

可以是单个数据，也可以是子列表，分别称为原子和子表。

a1:

LS的表头（第一个元素）。

（a2，a3，，an）:

LS的表尾（列表）。

列表的举例:

（1）A=（）——A是一个空列表，长度为0。

（2）B=（e）——B中只有一个原子e，长度为1。

（3）C=（a,（b,c,d））——C有两个元素，原子a和子表（b,c,d），长度为2。

（4）D=（（）,（e）,（a,（b,c,d）））——D有三个元素，都是子表，长度为3。

（5）E=（a,E）——E为一个递归的表，长度为2。

例E=（a,（a,（a,……）））。

列表的性质:

（1）列表是一个多层次的结构。

例D=（（）,（e）,（a,（b,c,d）））

（2）列表可为其它列表的子表所调用。

例，D=（A,B,C）

（3）列表可以是一个递归的表。

例，E=（a,E）

（4）任何一个非空列表，其表头可能是原子或列表，而表尾一定是列表。

例，B=（e）表头为原子e；表尾为空表（）。

例，B=（（a,b）,c）表头为列表（a,b）；表尾为列表（c）。

（5）（）==（（））？

（）为空表，长度0；

（（））长度为1的列表，可分解得到表头、表尾。

5.5广义表的存储结构

由于广义表中的数据元素可以具有不同的结构（原子、列表），难以用顺序存储结构表示，通常采用链式存储结构。

结点结构:

tag:

标志域，1为表结点，0为原子结点。

hp:

指向表的表头元素结点。

atom:

原子结点的值域。

tp:

指向下一个元素域。

例D=（（）,（e）,（a,（b,c,d）））

作业：

求（（a,b）,（c,d）,（e,f））的表头和表尾