数据结构课件第4章数组 和广 义表.ppt

《数据结构课件第4章数组 和广 义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第四章广义线性表—多维数组和广义表1本章的基本内容：数组的逻辑结构特征；数组的存储方式及寻址方法；特殊矩阵和稀疏矩阵的压缩存储方法；广义表的基本概念和存储结构。本章学习要求与重点难点2本章学习要求：1)了解数组的两种顺序存储表示方法，掌握数组在以行为主序的存储结构中的地址计算方法2)了解矩阵压缩存储的必要性，掌握特殊矩阵压缩存储时的下标变换公式3)理解稀疏矩阵的两种压缩存储方法的特点和适用范围，理解三元组表示的稀疏矩阵在进行转置等运算处理时使用的处理方法4)掌握广义表的结构特点、存储表示和基本逻辑运算（求表头、

2、求表尾）5)了解有关广义表的递归算法3学习重点与难点：重点：1)数组的寻址方法；2)特殊矩阵、稀疏矩阵的压缩存储方法；3)广义表中求表头和表尾的方法难点：1)稀疏矩阵的压缩存储的转置方法；2)广义表的存储结构44.1.1数组(array)的定义是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、…、in称为该元素的下标，并称该数组为n维数组。4.1多维数组54.1.1数组(array)的定义4.1

3、多维数组数组的特点:元素本身可以具有某种结构,但属于同一数据类型；数组是线性表的推广;数组是一个具有固定格式和数量的数据集合。6a11a12…a1na21a22…a2n…………am1am2…amnA=A=(A1，A2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)数组示意图4.1多维数组7数组的基本操作⑴存取：给定一组下标，存储或读出对应的数组元素；⑵修改：给定一组下标，修改与其相对应的数组元素。它们本质上只对应一种操作——寻址数组的基本操作与线性表的基本操作有何不同？4.1多维数组84

4、.1.2数组的存储结构与寻址▲采用顺序存储结构存储数组首先需要将多维结构映射到一维结构。常用的映射方法有两种：按行优先和按列优先。1.一维数组的存储与寻址设一维数组的下标的范围为闭区间［l，h］，则其的任一元素ai的存储位置可由下式确定：LOC(ai)＝LOC(al)＋(i－l)×c2.二维数组的存储与寻址4.1多维数组9二维数组按行优先存储寻址示意图第l1行第l1+1行al1l2…al1h2a(l1+1)l2…a(l1+1)h2…ail2…aij…ah1h2LOC(aij)LOC(al1l2)第i行(i-l1

5、)×(h2-l2＋1)＋(j-l2)个元素4.1多维数组10本行中aij前面的元素个数每行元素个数整行数aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数=(i-l1)×(h2-l2＋1)＋(j-l2)二维数组寻址的计算方法l2h2l1h1(a)二维数组aij4.1多维数组11按列优先存储的基本思想：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。任一元素存储地址的计算方法你能推导出来吗？n（n＞2）维数组，一般也采用按行优先和按列优先两种存储方法。请给出基本

6、思想和寻址计算方法，好吗？4.1多维数组124.2矩阵的压缩存储▲在矩阵中很多值相同的元素并且它们的分布有一定的规律，我们将这样的矩阵称为特殊矩阵,如对角阵等。若矩阵中有很多零元素称为稀疏矩阵对于这些特殊的矩阵，怎样存储能节省存储空间，同时也能有效地进行运算压缩存储的基本思想是：⑴为多个值相同的元素只分配一个存储空间；⑵对零元素不分配存储空间。134.2.1特殊矩阵的压缩存储——对称矩阵36　4　7　8628　4　24　816　97　4　6058　2　9　57A＝5阶对称矩阵对称矩阵特点：在一个n阶方阵中，有a

7、ij=aji，其中1≤i,j≤n。只需要n×（n＋1）/2个存储单元。如何只存储下三角部分的元素呢？4.2矩阵的压缩存储14(a)下三角矩阵(b)存储说明(c)计算方法aij在一维数组中的序号=阴影部分的面积=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行对称矩阵按行优先存储寻址示意图4.2矩阵的压缩存储15结论：将下三角中的所有元素按行优先存储到一维数组中

8、SA，下三角中的元素aij（i≥j）在数组SA中的下标k与i、j的关系为：k＝i×(i＋1)/2＋j。思考：上三角中如何处理？第1行第n-1行第0行a00a10a11a20a21a22aij…an-10an-11…an-1n-1…第2行012345kn(n+1)/2-1对称矩阵的压缩存储4.2矩阵的压缩存储164.2.1特殊矩阵的压缩存储——三角矩阵3cccc6　2ccc48　1cc7