数据结构-数组与广义表.ppt

《数据结构-数组与广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数组和广义表1第五章数组和广义表本章前讨论的线性结构数据元素都是非结构的原子类型，元素值不可再分。本章讨论了两种数据结构—数组和广义表。作为线性表的扩展，表中的数据元素也是一种数据结构。数组这种数据结构可以看成是线性表的推广。广义表是另一种推广形式的线性表，是一种灵活的数据结构，在许多方面有广泛的应用。2知识结构图数组与广义表数组广义表类型定义表示方法稀疏矩阵特殊矩阵存储结构逻辑结构应用压缩存储各种运算35.1数组数组是n(n＞1)个相同数据类型的数据元素a0,a1,a2,...,an-1

2、构成的占用一块地址连续的内存单元的有限序列。数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组的下标。45.1.1数组的概念及其与线性表的关系由定义知，n维数组中有b1b2…bn个数据元素，每个数据元素都受到n维关系的约束。直观的n维数组以二维数组为例讨论。将二维数组看成是一个定长的线性表，其每个元素又是一个定长的线性表。设二维数组A=(aij)mn，则A=(α1，α2，…，αp)(p=m或n)其中每个数据元素αj是一个列向量(线性表)：αj=(a1j，a2j

3、，…，amj)1≦j≦n或是一个行向量：αi=(ai1，ai2，…，ain)1≦i≦m如图5-1所示。5a11a12…a1na21a22…a2n……………am1am2…amnA=……………A=a11a12…a1na21a22…a2nam1am2…amna11a21┆am1a12a22┆am2a1na2n┆amn┆┆┆A=图5-1二维数组图例形式(a)矩阵表示形式(b)行向量的一维数组形式(c)列向量的一维数组形式6n维数组的特点每个数据元素都受着n个关系的约束；在每个关系中，元素(0<=ji<=

4、bi-2)都有一个直接后继;数据元素都必须属于同一数据类型;n=1时，退化为定长的线性表；n维数组可以看成是线性表的推广。数组一旦被定义，则维数已定，对于数组的操作只有存取元素和修改元素。(一旦建立了数组，数组中的元素个数和元素之间的关系就不再发生变动)数组是多维的结构，而存储空间是一个一维的结构。（存储时需要一个次序约定）75.1.2数组的顺序存储结构数组的实现机制a０的内存单元地址每个元素所需的字节个数8行向量下标i页向量下标i列向量下标j行向量下标j列向量下标k二维数组三维数组9数组的顺序

5、表示-小结n维数组的特点:数据元素同属于一种数据类型；数组一旦被定义，则维数和各维长度不能改变；数组操作只有引用型操作，没有加工型操作；数组是多维结构，但存储空间是一维结构。数组顺序表示的特点存储单元地址连续（需要一段连续空间）存储规则（以行（列）为主序）决定元素实际存储位置随机存取存储密度最大（100%）105.2矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编程时，通常将一个矩阵描述为一个二维数组。这样，可以对其元素进行随机存取，各种矩阵运算也非常简单。对于高阶矩

6、阵，若其中非零元素呈某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。对这类矩阵进行压缩存储：◆多个相同的非零元素只分配一个存储空间；◆零元素不分配空间。115.2.1特殊矩阵的压缩存储1.对称矩阵n阶矩阵A中元素满足性质a[i][j]=a[j][i](1≤i,j≤n)。（即aij=aji,1<=i,j<=n）a11a21a22……aij……annLTA[0..n(n+1)/2-1]k=012……n(n+1)/2-11213k的

7、含义：按行优先，是第k个（从0开始）15675289683079041526837904i=3j=2k=4公式的推导（下三角）i=3，j=2则前面有一个i-1行的完整三角形，共有元素(1+i-1)(i-1)/2=i(i-1)/2个另外，同一行，前面还有j-1个元素所以，k=i(i-1)/2+j-114/502、三角矩阵以主对角线划分，n阶三角矩阵有n阶上三角矩阵和n阶下三角矩阵两种。n阶上三角矩阵的下三角（不包括主对角线）中的元素均为0（或常数）。n阶下三角矩阵正好相反，它的主对角线上方均为0（

8、或常数）。注：在大多数情况下，n阶三角矩阵常数为零。下三角矩阵元素aij保存在向量sa中时的下标值k与（i,j）之间的对应关系是：i(i-1)/2+j当i≧j时n(n+1)/2当i