《数据结构（c清华版）课件》由会员分享，可在线阅读，更多相关《数据结构（c清华版）课件（237页珍藏版）》请在金锄头文库上搜索。
1、数据结构（C+版）二,第四章 广义线性表,本章的基本内容是：数组的逻辑结构特征 数组的存储方式及寻址方法 特殊矩阵和稀疏矩阵的压缩存储方法 广义表的基本概念和存储结构,第四章 广义线性表,线性表具有相同类型的数据元素的有限序列。,限制插入、删除位置,线性表具有相同类型的数据元素的有限序列。,限制元素类型为字符,串零个或多个字符组成的有限序列 。,第四章 广义线性表,线性表具有相同类型的数据元素的有限序列。,将元素的类型进行扩充,数组的定义,数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n1)个线性关系的约束，每个元素在n个线性关系中的序
2、号i1、i2、in称为该元素的下标，并称该数组为 n 维数组。,数组的特点,元素本身可以具有某种结构，属于同一数据类型； 数组是一个具有固定格式和数量的数据集合。,广义线性表多维数组,广义线性表多维数组,a11 a12 a1na21 a22 a2n am1 am2 amn,A=,例如，元素a22受两个线性关系的约束，在行上有一个行前驱a21和一个行后继a23，在列上有一个列前驱a12和和一个列后继a32。,数组示例,a11 a12 a1na21 a22 a2n am1 am2 amn,A=,数组线性表的推广,二维数组是数据元素为线性表的线性表。,广义线性表多维数组,数组的基本操作,广义线性表多
3、维数组,在数组中插入（或）一个元素有意义吗？,将元素 x 插入 到数组中第1行第2列。,删除数组中 第1行第2列元素。,数组的基本操作, 存取：给定一组下标，读出对应的数组元素； 修改：给定一组下标，存储或修改与其相对应的数组元素。存取和修改操作本质上只对应一种操作寻址,数组应该采用何种方式存储？,数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。,广义线性表多维数组,数组的存储结构与寻址一维数组,设一维数组的下标的范围为闭区间l，h，每个数组元素占用 c 个存储单元，则其任一元素 ai 的存储地址可由下式确定： Loc(ai)Loc(al)(il)c,广义线性表多维数组,常用的映
4、射方法有两种： 按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。 按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。,广义线性表多维数组,数组的存储结构与寻址二维数组,广义线性表多维数组,l2,h2,l1,h1,(a) 二维数组,aij前面的元素个数 =阴影部分的面积 =整行数每行元素个数+本行中aij前面的元素个数 =(i -l1)(h2 -l21)(j -l2),按行优先存储的寻址,广义线性表多维数组,第l1行,第l1+1行,(i -l1)(h2 -l21)(j -l2)个元素,Loc(aij)Loc(al1l2)(il1)(h2l21)(
5、jl2)c,按行优先存储的寻址,按列优先存储的寻址方法与此类似。,Loc(aijk ) = Loc(a000) +( im2m3 + jm3 + k )c,广义线性表多维数组,n（n2）维数组一般也采用按行优先和按列优先两种存储方法。请自行推导任一元素存储地址的计算方法。,数组的存储结构与寻址多维数组,矩阵的压缩存储,特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一定的规律。 稀疏矩阵：矩阵中有很多零元素。,压缩存储的基本思想是： 为多个值相同的元素只分配一个存储空间； 对零元素不分配存储空间。,特殊矩阵和稀疏矩阵,特殊矩阵的压缩存储对称矩阵,3 6 4 7 8 6 2 8 4 2 4 8
6、1 6 9 7 4 6 0 5 8 2 9 5 7,A,对称矩阵特点：aij=aji,如何压缩存储？,只存储下三角部分的元素。,矩阵的压缩存储,(a) 下三角矩阵 (b) 存储说明 (c) 计算方法,aij在一维数组中的序号 =阴影部分的面积 = i(i+1)/2+ j+1 一维数组下标从0开始 aij在一维数组中的下标 k= i(i+1)/2+ j,0i n-1,0 j n-1,aij,对称矩阵的压缩存储,矩阵的压缩存储,对于下三角中的元素aij（ij），在数组SA中的下标k与i、j的关系为：ki(i1)/2j 。 上三角中的元素aij（ij），因为aijaji，则访问和它对应的元素aji即
7、可，即：kj(j1)/2i 。,对称矩阵的压缩存储,矩阵的压缩存储,特殊矩阵的压缩存储三角矩阵,3 c c c c 6 2 c c c 4 8 1 c c 7 4 6 0 c 8 2 9 5 7,(a) 下三角矩阵,3 4 8 1 0 c 2 9 4 6 c c 5 7 c c c 0 8 c c c c 7,(b) 上三角矩阵,如何压缩存储？,只存储上三角（或下三角）部分的元素。,矩阵的压缩存储,矩阵中任一元素aij在数组中的下标k与i、j的对应关系：,下三角矩阵的压缩存储,矩阵的压缩存储,矩阵中任一元素aij在数组中的下标k与i、j的对应关系：,上三角矩阵的压缩存储,矩阵的压缩存储,特殊矩
8、阵的压缩存储对角矩阵,对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。,a00 a01 0 0 0 a10 a11 a12 0 0 0 a21 a22 a23 0 0 0 a32 a33 a34 0 0 0 a43 a44,A=,矩阵的压缩存储,将带状区 域立起来,对角矩阵的压缩存储,矩阵的压缩存储,按行 存储,元素aij在一维数组中的序号 =2 + 3(i1)+( ji + 2) =2i+ j+1一维数组下标从0开始 元素aij在一维数组中的下标 =2i+ j,(b) 寻址的计算方法,矩阵的压缩存储,对角矩阵的压缩
9、存储,稀疏矩阵的压缩存储,如何只存储非零元素？,矩阵的压缩存储,注意：稀疏矩阵中的非零元素的分布没有规律。,template struct element int row, col; /行号，列号T item /非零元素值 ;,将稀疏矩阵中的每个非零元素表示为： (行号，列号，非零元素值)三元组,矩阵的压缩存储,稀疏矩阵的压缩存储,定义三元组：,三元组表：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。,矩阵的压缩存储,稀疏矩阵的压缩存储,三元组表( (0,0,15), (1,1,11), (2,3,6), (4,0,9) ),如何存储三元组表？,稀疏矩阵的压缩存
10、储三元组顺序表,采用顺序存储结构存储三元组表,矩阵的压缩存储,三元组顺序表是否 需要预留存储空间？,稀疏矩阵的修改操作,三元组顺序表的插入/删除操作,稀疏矩阵的压缩存储三元组顺序表,采用顺序存储结构存储三元组表,矩阵的压缩存储,7（非零元个数）,是否对应惟一的稀疏矩阵？,存储结构定义：const int MaxTerm=100;template struct SparseMatrixT dataMaxTerm; /存储非零元素int mu, nu, tu; /行数，列数，非零元个数;,矩阵的压缩存储,稀疏矩阵的压缩存储三元组顺序表,三元组顺序表操作转置操作,例：,矩阵的压缩存储,矩阵的压缩存储
11、,0 0 150 3 220 5 -151 1 111 2 32 3 64 0 91空 空 空闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,三元组顺序表转置算法算法,基本思想：直接取，顺序存。即在A的三元组顺序表中依次找第0列、第1列、直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。,矩阵的压缩存储,矩阵的压缩存储,设置矩阵B的行数、列数、非零元个数,矩阵的压缩存储,0 0 150 3 220 5 -151 1 111 2 32 3 64 0 91空 空 空闲 闲 闲,row col item,0
12、1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,row col item,0 1 2 3 4 5 6,MaxTerm-1,6（矩阵的行数）,在矩阵A中查找第0列非零元，顺序存储到矩阵B中,矩阵的压缩存储,0 0 150 3 220 5 -151 1 111 2 32 3 64 0 91空 空 空闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,row col item,0 1 2 3 4 5 6,MaxTerm-1,6（矩阵的行数）,在矩阵A中查找第1列非零元，顺序存储到矩阵B中,矩阵的压缩存储,0 0 150 3 220 5 -151 1 111 2 32 3 64 0 91空 空 空闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,row col item,0 1 2 3 4 5 6,MaxTerm-1,6（矩阵的行数）,在矩阵A中查找第2列非零元，顺序存储到矩阵B中,矩阵的压缩存储,0 0 150 3 220 5 -151 1 111 2 32 3 64 0 91空 空 空闲 闲 闲,row col item,0 1 2 3 4 5 6,MaxTerm-1,5（矩阵的行数）,
