《数组和广义表》PPT课件.ppt

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

1、第三章广义线性表——数组和广义表本章的基本内容是：数组的逻辑结构特征；数组的存储方式及寻址方法；特殊矩阵和稀疏矩阵的压缩存储方法；广义表的基本概念和存储结构。第三章广义线性表——数组和广义表3.1.1数组的定义是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、…、in称为该元素的下标，并称该数组为n维数组。3.1多维数组数组的特点:元素本身可以具有某种结构,但属于同一数据类型；数组是线性表的推广;数组是一个具有固定格式和数量

2、的数据集合。a11a12…a1na21a22…a2n…………am1am2…amnA=A=(A1，A2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)数组示意图数组的基本操作⑴存取：给定一组下标，读出对应的数组元素；⑵修改：给定一组下标，存储或修改与其相对应的数组元素。它们本质上只对应一种操作——寻址数组的基本操作与线性表的基本操作有何不同？3.1.2数组的存储结构与寻址采用顺序存储结构存储数组首先需要将多维结构映射到一维结构。常用的映射方法有两种：按行优先和按列优先。按行优先存储的基本思想是：先行后列，先存储行号较小

3、的元素，行号相同者先存储列号较小的元素。1.一维数组的存储与寻址设一维数组的下标的范围为闭区间［l，h］，则其的任一元素ai的存储位置可由下式确定：LOC(ai)＝LOC(al)＋(i－l)×c2.二维数组的存储与寻址二维数组按行优先存储寻址示意图第l1行第l1+1行al1l2…al1h2a(l1+1)l2…a(l1+1)h2…ail2…aij…ah1h2LOC(aij)LOC(al1l2)第i行(i-l1)×(h2-l2＋1)＋(j-l2)个元素本行中aij前面的元素个数每行元素个数整行数aij前面的元素个数=阴影部分的面积=整行数×每行

4、元素个数+本行中aij前面的元素个数=(i-l1)×(h2-l2＋1)＋(j-l2)二维数组寻址的计算方法l2h2l1h1(a)二维数组aij按列优先存储的基本思想：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。任一元素存储地址的计算方法你能推导出来吗？n（n＞2）维数组，一般也采用按行优先和按列优先两种存储方法。请给出基本思想和寻址计算方法，好吗？下标为i1,i2,i3的数组元素的存储地址：按页/行/列存放各维元素个数为m1,m2,m3LOC(aijk)=Loc(a000)+(i*m2*m3+j*m3+k)*l3.2矩阵

5、的压缩存储在矩阵中很多值相同的元素并且它们的分布有一定的规律，我们将这样的矩阵称为特殊矩阵。若矩阵中有很多零元素称为稀疏矩阵压缩存储的基本思想是：⑴为多个值相同的元素只分配一个存储空间；⑵对零元素不分配存储空间。3.2.1特殊矩阵的压缩存储——对称矩阵36　4　7　8628　4　24　816　97　4　6058　2　9　57A＝5阶对称矩阵对称矩阵特点：在一个n阶方阵中，有aij=aji，其中1≤i,j≤n。只需要n×（n＋1）/2个存储单元。如何只存储下三角部分的元素呢？(a)下三角矩阵(b)存储说明(c)计算方法aij在一维数组中的序号

6、=阴影部分的面积=i×(i+1)/2+j+1∵一维数组下标从0开始∴aij在一维数组中的下标k=i×(i+1)/2+j0…in-10…j…n-1aij每行元素个数12…iaij在本行中的序号aij第0行第1行…第i-1行对称矩阵按行优先存储寻址示意图结论：将下三角中的所有元素按行优先存储到一维数组中SA，下三角中的元素aij（i≥j）在数组SA中的下标k与i、j的关系为：k＝i×(i＋1)/2＋j。同理我们可以得到：上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：k＝j×(j＋1)/2＋i。第1行第n

7、-1行第0行a00a10a11a20a21a22aij…an-10an-11…an-1n-1…第2行012345kn(n+1)/2-1对称矩阵的压缩存储3.2.1特殊矩阵的压缩存储——三角矩阵3cccc6　2ccc48　1cc7　4　6　0c8　2　9　5　7(a)下三角矩阵34　8　10c2　9　4　6cc１57ccc0　8cccc7(b)上三角矩阵如何只存储下三角部分或上三角部分的元素呢？只需存储n×(n＋1)/2＋1012345kn(n+1)/2第1行第n-1行第0行a00a10a11a20a21a22aij…an-10an-11…a

8、n-1n-1…第2行c下三角矩阵的压缩存储既要存储下三角中的元素，还要存储对角线上方的常数。因为是同一个常数，所以只存一个即可。对于上三角矩阵，其存储思想与下三角类似，按行存储上