数据结构第5章数组和广义表.ppt

1 第五章数组和广义表 在线性表L a0a1 an 1 中 元素ai是无结构的 称为原子或单元素 即ai本身不再是一个数据结构 本章的数组和广义表是线性结构的推广 在这种结构中 元素本身可以又是一个数据结构 本章讨论多维数组的表示 矩阵压缩存储 广义表的表示等问题 5 1数组的定义及其操作5 1 1数组的定义在算法语言中 如FORTRAN PASCAL C Java等 都有数组类型 前面接触到的是一维数组 本节以C语言为例讨论多维数组 如多维数组的描述 存储映象 地址计算等问题 2 数组描述 设二维数组 其中 m n为行列数 aij为第i行 第j列的元素 0 i m 1 0 j n 1 元素个数为m n 二维数组可用形式化语言描述 即 A 2 D R 其中 D aij aij datatype 0 i m 1 0 j n 1 R Row Col 行关系 Row aij aij 1 D 0 i m 1 0 j n 2 列关系 Col aij ai 1j D 0 i m 2 0 j n 1 3 数组描述 关系集Row和Col表明 除数组A 2 周边元素外的其它任一个元素aij 有两个直接前驱ai 1j aij 1 和两个直接后继ai 1j aij 1 周边元素的前驱或后继可不足两个 n维数组也可按上述方法类似定义 二维数组可如下描述 多维数组是线性表的推广 而线性表是多维数组的特例 4 5 1 1数组的抽象数据类型 在算法语言中 数组一旦生成 其元素的存储空间就固定下来 故数组的运算一般不包括插入和删除这样的操作 ADTArray D aj1j2 jn aj1j2 jn datatype ji 0 bi 1其中i 1 2 n n n 0 为数组维数 bi是第i维长度 ji是数组元素第i维下标 R R1 R2 Rn 其中 Ri 0 jk bk 1 1 k n且k i 0 ji bi 2 aj1 ji jn aj1 ji 1 jn D i 1 2 n PArrayInit A n d1 d2 dn 操作结果 若维数n和各维长度合法 则生成一个n维数组A d1 d2 dn C语言中 1 n 8 ArrayDestroy A 初始条件 数组A存在 操作结果 撤销数组A ArrayGet A i1 in e 初始条件 数组A存在 e datatype 操作结果 若各下标合法 则将元素A i1 i2 in 的值传给变量e 5 数组的抽象数据类型 ArrayAssign A i1 in e 初始条件 数组A存在 e datatype 操作结果 若各下标合法 则将变量e的值传给数组元素A i1 i2 in ADTArray 5 2数组的存储结构由于计算机的存储空间是一维的 或线性的 所以存储数组时 要将多维数组中的元素按某种次序映象到一维存储空间 即解决 降维 问题 5 2 1数组的静态存储方式1 数组的静态存储映像在PASCAL和C等语言中 是按低维下标优先变化 或按行优先 的方式 存储数组中的元素 如在C语言中 二维数组的映像如图5 1所示 但在FORTRAN语言中 数组元素是按高维下标优先变化或按列优先方式 存储数组中的元素 6 数组的存储映像 思考 1 三维以上数组如何映像 2 按列优先 如何映像 7 2 静态数组元素的地址计算 以C语言为例 设数组元素的起始地址为b 每个元素占用L个单元 元素所占单元量由元素的类型而定 元素a的地址用Loc a 表示 1 一维数组 即 Loc a0 b Loc a1 b L Loc ai b i L 规律 任一元素ai的地址 A n a0 a1 ai an 1 起始地址b ai前的元素个数i L 图5 2 8 数组元素的地址计算 2 二维数组 由图5 3知 Loc a00 bLoc ai0 b ai0前元素个数 L b i n LLoc aij b aij前元素个数 L b i n j L例5 1设二维数组A 7 8 起始地址b 1000 每个元素所占单元量L 3 则Loc a5 6 1000 5 8 6 3 1138 9 数组元素的地址计算 3 三维数组 由图5 5可知 Loc a000 b图5 5Loc ai00 b i n p LLoc aij0 b i n p j p LLoc aijk b i n p j p k Laijk前的元素个数 10 数组元素的地址计算 4 n维数组从以上的地址公式推导中得出这样一条规律 数组中任一元素的地址 起址b 该元素前的个数 元素单元量L 故n维数组A u1 u2 un 中任一元素ai1 in的地址为 Loc ai1i2 in b i1 u2 u3 un i2 u3 u4 un in 1 un in L b L元素按 列优先 方式存储时 地址计算方法类似 不再赘述 有了数组元素的地址计算公式 给出相应参数后 能够很快求出任一元素的地址 然后按地址存取相应元素 故对数组的存取是随机存取 或按公式存取 5 2 2数组的动态存储方式 略 11 5 2矩阵的压缩存储 信息的压缩存储是一项专业技术 在当今的多媒体应用中显得尤为重要 但本节只是讨论矩阵 或二维数组 中元素的压缩存储 在矩阵中 往往会出现许多值相同的元素或 元素 为节省存储空间 可以采用某些技术对这类矩阵进行压缩存储 压缩存储的原则是 对多个值相同的元素只存储其中之一 对 元素甚至不分配存储空间 5 3 1特殊矩阵的压缩存储特殊矩阵 值相同的元素或 元素在矩阵中的分布遵循一定规律 1 对称矩阵 满足aij aji 1 i j n a11a22aii ann An n aij aji 12 特殊矩阵的压缩 aij与aji对称相等 二者只需分配一个存储单元 即只存储包括主对角线的下三角 或上三角 元素 于是An n所需单元数为n n 1 2 而不压缩存储需要n2个单元 当n很大时 几乎能压缩原存储空间的一半 具体做法 设置数组S n n 1 2 1 作为An n的存储空间 且按行的次序存放An n中包括主对角线的下三角元素 如图5 5所示 S n n 1 2 1 123 k n n 1 2图5 5 13 特殊矩阵的压缩 2 三角矩阵 下三角矩阵 上三角矩阵 图5 6 而当 i j 时 K 0 对于下三角矩阵 类似于对称矩阵 即只存储包括主对角线的下三角元素 而当i j时 aij取C即可 对于上三角矩阵 压缩方法如图5 6所示 14 特殊矩阵的压缩 3 对角线矩阵 三对角线 按行顺序压缩于S中 如图5 7所示 15 5 3 1稀疏矩阵的压缩存储 特殊矩阵中同值元素的分布有一定的规律可循 而有的矩阵 元素很多 如同一个画面上有几个亮点 其余全是空白 但分布无规律 称这类矩阵为稀疏矩阵 例5 2设一个6 7的矩阵如下 则A6 7可以视为一个稀疏矩阵 对于矩阵Am n 设非0元素个数为t 若 t m n 0 2 则可以将其视为稀疏矩阵 显然 为节省存储空间 须对这类矩阵压缩存储空间 原则是只存储非0元素 一般有 三元组表 和 十字链表 的压缩存储方法 16 1 三元组表 三元组 i j v 其中i j分别为非0元素的行 列号 v存放非0元的数值 以行优先的顺序将矩阵中非0元以三元组形式存入一数组 即所谓的三元组表 三元组表的存储结构的描述 definemaxsize64 最大非0元个数typedefstruct 三元组类型 inti j datatypev tritype 三元组说明符typedefstruct tritypedata maxsize 1 三元组表intmu nu tu 原矩阵的行 列 非0元个数 Tsmtype Tsmlink 三元组表说明符若说明 TsmlinkA A Tsmlink malloc sizeof Tsmtype 则指针变量A指向一个如图5 8所示的三元组表 对例5 2中A6 7 设每个元素占16个字节 若不压缩存储 需6 7 16 672 字节 而压缩成三元组表时 i j为整型 故共需 2 16 8 16 160 字节 A data 1 A data tu 图5 8 17 三元组表的转置 然而 稀疏矩阵的压缩存储会给矩阵运算带来一些不便 算法要复杂些 这里的运算指求矩阵的转置 两矩阵相加和相乘等 我们只讨论矩阵的转置的算法 未压缩前 求矩阵A的转置矩阵B 算法很简单 for col 1 col nu col for row 1 row mu row B col row A row col 例5 3 现在 要通过A的三元组表求其转置矩阵B的三元组表 18 三元组表的转置 算法思路 1 矩阵A的所有列转化成B的所有行 2 对A中的每一列col 1 nu 扫描所有非0元 1 tu 若有非0元的列号j 当前列col 则将该非0元行列互换 送到目标三元组表 如例5 3中矩阵A 当前列col 1时 因A data 3 j 1 故将A data 3 转置 1 2 6 B data 1 又A data 6 j 1 所以A data 6 转置 1 4 3 B data 2 完成第一列的转换 依此类推 算法描述 voidTransm TsmtypeA TsmtypeB intp q col B mu A nu B nu A mu B tu A tu if A tu 0 q 1 目标表的序号for col 1 colnu col for p 1 ptn p if A data p j col B data q i A data p j 行列互换B data q j A data p i B data q v A data p v q 19 三元组表的转置 矩阵A的三元组表 图5 10 转置后的三元组表 算法的时间复杂度 O t n n 列数 t 非0元个数 改进算法的复杂度 O t n 略 20 2 十字链表 十字链表是以链表结构形式存储一个稀疏矩阵 矩阵中非0元设置成如下形式的节点 其中i j分别存放非0元的行列号 head data或作为一非0元的值域 data 或作为头节点的链指针 head down为指向相同列下一个非0元节点的指针 right为指向相同行下一非0元节点的指针 节点类型描述 typedefstructnode inti j union structnode head datatypedata vdata structnode down right nodetype tlink 21 十字链表 例5 4设稀疏矩阵 A的十字链表如图5 11 22 建立十字链表 算法思路 先构造空表 其中S取矩阵行列数的最大值 即S max m n 依次读入每个非0元 i j v 生成一个非0元的节点 对该节点赋读入的值后 将其插入第i行链表和第j列链表的正确位置 算法描述 voidCreattenlink tlinkL intm intn intt L为头指针 m n t分别为行列号和非0元个数 tlinkp q H maxsize inti j k s datatypev if m n s m elses n 确定头节点的个数L tlink malloc sizeof nodetype 申请总的头节点L i m L j n 置行列数H 0 L for i 1 ii p j 0 p down p right p H i p H i 1 vdata head p H s vdata head L 构成循环 23 建立十字链表 for k 1 ki i p j j p vdata data v 赋值q H i 取第i行链表头节点指针while q right H i 非0元节点节点插入q节点之后 24 5 4广义表的定义及其操作 5 4 1广义表的定义广义表又称列表 lists 是线型表的推广 在线型表L a0 ai an 1 中 ai是单元素或原子 即ai本身不再是一个DS 而广义表记为 LS d0d1 di dn 1 其中di 0 i n 1 既可以是一个原子 又可以是另一个表 称为子表 即表中还可以套表 广义表LS的形式化描述为 LS D R 其中 D di di datatypeordi LS 递归定义 i 0 1 n 1 n 0 R di di 1 D 0 i n 2 式中n为表长 n 0时为空表 若di为原子 则称di为LS的单元素 否则di称为LS的子表 满足递归定义 对非空广义表定义两个函数 Gethead LS d0 Gettail LS d1 dn 1 即Gethead LS 是LS的第一元素d0 当然d0可以为子表 而Gettail LS 是LS中d1 dn 1的一个子表 对广义表的其它运算 如查找 插入和删除等 类似于线性表的运算 见5 4 2 25 例5 5广义表的例子 约定 大写字母A Z为表名 小写字母a z为单元素 A 或A 空表 表长 0 无表头 表尾 B a b 或B a b 线性表特例 表长 2 Gethead B a Gettail B b C e B 或C e B 表长 2 Gethead C e Gettail C B a b 表C可以表示为 C e a b D A B C 或D A B C 表长 3 Gethead D A Gettail D B C a b e a b E a E 表长 2 Gethead E a Gettail E E 整个表E为 a a a 它为一个特殊的广义表 称为递归表 或无限表 从例5 5可以看出 广义表有如下特点 1 表可以嵌套 表中元素可以是一个表 称为子表 而子表还可以有子表 如例5 5中表B和表C的结构如图5 13所示 图5 13 26 广义表的例子 2 表可以共享 表可以是其它表的子表 或表中的元素可取自其他表 如例5 5中表D包含表A B C 或A B C为D的子表 如图5 16所示 3 表可以递归 表中元素可以是表本身 如例5 5中表E 另外 表中任一单元素可由Gethead Ls 和Gettail Ls 函数导出 如取表A a b d e 中单元素d的运算为 Gethead Gettail Gethead Gettail A 27 5 5广义表的存储结构 对于广义表LS d0 di dn 1 由于di可以是单元素或子表 故用顺序存储结构表示LS较为困难 一般采用链表存储 称为广义链表 5 5 1广义表的链式存储1 单链表示法元素di的节点形式 其中 0当di为单元素时 data当atom 0时 atom data link 1当di为子表时 link当atom 1时 next意义同线性链表 指向di 1所在节点 节点描述 typedefstructnode intatom union d