第4章数据结构广义线性表ppt课件.ppt

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

1、第四章广义线性表本章的基本内容是：数组的逻辑结构特征数组的存储方式及寻址方法特殊矩阵和稀疏矩阵的压缩存储方法广义表的基本概念和存储结构第四章广义线性表线性表——具有相同类型的数据元素的有限序列。限制插入、删除位置线性表——具有相同类型的数据元素的有限序列。限制元素类型为字符栈——仅在表尾进行插入和删除操作的线性表。队列——在一端进行插入操作，而另一端进行删除操作的线性表。串——零个或多个字符组成的有限序列。特殊线性表第四章广义线性表线性表——具有相同类型的数据元素的有限序列。将元素的类型进行扩充广义线性表（多维）数组——线性表中的数据元素可以是线性表，

2、但所有元素的类型相同。广义表——线性表中的数据元素可以是线性表，且元素的类型可以不相同。数组的定义数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、…、in称为该元素的下标，并称该数组为n维数组。数组的特点元素本身可以具有某种结构，属于同一数据类型；数组是一个具有固定格式和数量的数据集合。广义线性表——多维数组广义线性表——多维数组a11a12…a1na21a22…a2n…………am1am2…amnA=例如，元素a22受两个线性关系

3、的约束，在行上有一个行前驱a21和一个行后继a23，在列上有一个列前驱a12和和一个列后继a32。数组示例a11a12…a1na21a22…a2n…………am1am2…amnA=A=(A1，A2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)数组——线性表的推广二维数组是数据元素为线性表的线性表。广义线性表——多维数组数组的基本操作广义线性表——多维数组在数组中插入（或）一个元素有意义吗？a11a12…a1na21a22…a2n…………am1am2…amnA=将元素x插入到数组中第1行第2列。xa11a12…a1na21a22…

4、a2n…………am1am2…amnA=删除数组中第1行第2列元素。数组的基本操作⑴存取：给定一组下标，读出对应的数组元素；⑵修改：给定一组下标，存储或修改与其相对应的数组元素。存取和修改操作本质上只对应一种操作——寻址数组应该采用何种方式存储？数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。广义线性表——多维数组数组的存储结构与寻址——一维数组设一维数组的下标的范围为闭区间［l，h］，每个数组元素占用c个存储单元，则其任一元素ai的存储地址可由下式确定：Loc(ai)＝Loc(al)＋(i－l)×c广义线性表——多维数组calai-1ai

5、……ahal+1……Loc(al)Loc(ai)常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。广义线性表——多维数组数组的存储结构与寻址——二维数组二维数组内存二维结构一维结构广义线性表——多维数组l2h2l1h1(a)二维数组aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数=(i-l1)×(h2-l2＋1)＋(j-l2)本行中aij前面的元素个数每行元素个数整行数aij按行优先存储的寻址广义

6、线性表——多维数组第l1行第l1+1行al1l2…al1h2a(l1+1)l2…a(l1+1)h2……aij…ah1h2Loc(aij)Loc(al1l2)(i-l1)×(h2-l2＋1)＋(j-l2)个元素Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c按行优先存储的寻址按列优先存储的寻址方法与此类似。Loc(aijk)=Loc(a000)+(i×m2×m3+j×m3+k)×c广义线性表——多维数组n（n＞2）维数组一般也采用按行优先和按列优先两种存储方法。请自行推导任一元素存储地址的计算方法。数组的存储

7、结构与寻址——多维数组矩阵的压缩存储特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一定的规律。稀疏矩阵：矩阵中有很多零元素。压缩存储的基本思想是：⑴为多个值相同的元素只分配一个存储空间；⑵对零元素不分配存储空间。特殊矩阵和稀疏矩阵特殊矩阵的压缩存储——对称矩阵36　4　7　8628　4　24　816　97　4　6058　2　9　57A＝对称矩阵特点：aij=aji如何压缩存储？只存储下三角部分的元素。矩阵的压缩存储(a)下三角矩阵(b)存储说明(c)计算方法aij在一维数组中的序号=阴影部分的面积=i×(i+1)/2+j+1∵一维数组下标从0开始∴a

8、ij在一维数组中的下标k=i×(i+1)/2+j0…in-10…j…n-1aij每行元素个数1