《数据结构C语言版第五章严蔚敏ppt课件》由会员分享，可在线阅读，更多相关《数据结构C语言版第五章严蔚敏ppt课件（38页珍藏版）》请在金锄头文库上搜索。
1、 第5章数组和广义表 5 1数组的定义和运算 5 2数组的顺序存储和实现 5 3特殊矩阵的压缩存储5 4广义表 数组是n n 1 个相同类型数据元素a0 a1 an 1构成的有限序列 且该有限序列存储在一块地址连续的内存单元中 数组的定义类似于采用顺序存储结构的线性表 是线性表在维数上的扩张 也就是线性表中的元素又是一个线性表 n维数组 bi是第i维的长度 则n维数组共有个数据元素 每个元素受n个关系的制约 就单个关系而言 这n个关系仍然是线性的 1 数组的定义和运算 数组具有以下性质 1 数组中的数据元素数目固定 一旦定义了一个数组 其数据元素数目不再有增减变化 2 数组中的数据元素具有相同
2、的数据类型 3 数组中的每个数据元素都和一组惟一的下标值对应 4 数组是一种随机存储结构 可随机存取数组中的任意数据元素 数组的基本操作 1 取值Value A e index1 indexn 2 赋值Assign A e index1 indexn 2 数组的存储结构一维数组中 LOC a0 确定 每个数据元素占用L个存储单元 则任一数据元素ai的存储地址LOC ai 就可由以下公式求出 LOC ai LOC a0 i L 0 i n 1 二维数组 由于计算机的存储结构是线性的 如何用线性的存储结构存放二维数组元素就有一个行 列次序排放问题 二维数组通常可以描述为两种形式 以行序为主序 PA
3、SCAL C 以列序为主序 FORTRAN 对于数组 一旦规定了维数和维界 如何计算数组元素的存储位置 设二维数组A m n 其数组元素aij的存储位置为 LOC i j LOC 0 0 其中 LOC 0 0 是a00的存储位置 例 LOC 1 1 LOC 0 0 n 1 1 L n i j L n维数组每一元素对应下标 j1 j2 jn 0 ji bi 1 bi为第i维的长度 以行序为主序 LOC j1 j2 jn LOC 0 0 0 bn b2 j1 bn b3 j2 bnjn 1 jn L 例 对二维数组floata 5 4 计算 1 数组a中的数组元素数目 2 若数组a的起始地址为20
4、00 且每个数组元素长度为32位 即4个字节 数组元素a 3 2 的内存地址 元素数目共有5 4 20个 C语言采用行序为主序的存储方式 则有 LOC a3 2 LOC a0 0 i n j k 2000 3 4 2 4 2056 3 矩阵的压缩存储 特殊矩阵 对称矩阵 三角矩阵 对角矩阵 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵 为了节省存储空间 特别是在高阶矩阵的情况下 可以利用特殊矩阵的规律 对它们进行压缩存储 也就是说 使多个相同的非零元素共享同一个存储单元 对零元素不分配存储空间 对称矩阵的压缩存储若一个n阶方阵A中的元素满足ai j aj i 1 i j n 则称其为n阶
5、对称矩阵 1 只存储对称矩阵中上三角或下三角中的元素 2 将n2个元素压缩存储到n n 1 2个元素的空间中 以一个一维数组作为A的存储空间 n2个元素 n n 1 2个元素aij 1 i j n B n n 1 2 1 2 i 1 j 1 aij aji k 0 1 2 3 下三角矩阵的压缩存储B n n 1 2 1 C k 0 1 2 3 对角矩阵 所有的非零元都集中在以主对角线为中心的带状区域内 半带宽为b的对角矩阵 共有3n 2个非零元 主对角线左下方的元素下标有关系式 i j 1k 3 i 1 1 1 1 3 i 1 1 2 i 1 i 2 2 i 1 j 1 主对角线上的元素下标有
6、关系式 i jk 3 i 1 1 2 1 3 i 1 2 i 1 i 1 2 i 1 j 1 主对角线右上方的元素下标有关系式 i j 1k 3 i 1 1 3 1 3 i 1 1 2 i 1 i 2 i 1 j 1 三对角矩阵 B 3n 2 k 2 i 1 j 1 稀疏矩阵非零元较零元少 且没有一定规律 m n的矩阵 有t个非零元 矩阵的稀疏因子 t m n 当 0 05时为稀疏矩阵 压缩存储 只存储非零元 三元组顺序表 i j ai j 行逻辑链接的顺序表 十字链表 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 defineMax
7、Size100 矩阵中非零元素最多个数 typedefstruct inti 行号 intj 列号 ElemTypee 元素值 Triple 三元组定义 typedefstruct introws 行数 intcols 列数 intnums 非零元素个数 Tripledata MaxSize 1 data 0 未用 TSMatrix 三元组顺序表定义 用三元组表实现稀疏矩阵的转置运算一个6 7的矩阵A 以行序为主序顺序排列 矩阵的转置 方法一 StatusTransposeSMatrix TSMatrixA TSMatrix 方法1时间复杂度 O cols nums 当非零元个数nums和co
8、ls rows同数量级时 O rows cols2 仅适用于nums rows cols 常规存储方式时 实现矩阵转置的经典算法如下 for i 0 i m i for j 0 j n j T i j M j i O cols rows 方法二 依次按三元组表A 6 7 的次序进行转置 转置后直接放到三元组表B的正确位置上 这种转置算法称为快速转置算法 col1234567 num col cpot col 2 2 2 1 0 1 0 1 3 5 7 8 8 9 num col A中第col列非零元的个数 cpot col B中第col行第一个非零元在B中的位置 StatusFastTranS
9、Matrix TSMatrixA TSMatrix O cols nums 当nums和cols rows同数量级时O rows cols rowcole 12345678 13 3 319 2112 cpot 1 cpot 2 cpot 2 cpot 3 cpot 3 cpot 4 cpot 6 6314 3424 2518 1615 46 7 小结基本学习要点如下 1 理解数组和一般线性表之间的差异 2 重点掌握数组的顺序存储结构和元素地址计算方法 3 掌握各种特殊矩阵如对称矩阵 上 下三角矩阵和对角矩阵的压缩存储方法 4 掌握稀疏矩阵的各种存储结构以及基本运算实现算法 5 灵活运用数组这
10、种数据结构解决一些综合应用问题 练习 将一个A 1 100 1 100 的三对角矩阵 按行优先存入一维数组B 1 298 A中元素a66 65在B数组中的位置k 在主对角线左下方 65 3 1 1 195 作业 5 25 25 1 广义表的定义 列表 广义表是线性表的推广 是由零个或多个单元素或子表所组成的有限序列 LS a1 a2 ai an ai 是单个数据元素 则ai是广义表的原子 如果ai是一个广义表 则ai是广义表的子表 规定用小写字母表示原子 用大写字母表示广义表的表名 广义表与线性表的区别 线性表的成份都是结构上不可分的单个数据元素 而广义表的成份即可以是单元素 也可以是有结构的
11、表 其定义是递归的定义 5 4广义表 广义表的长度 广义表中所含元素的个数n n 0 广义表的深度 广义表展开后所含的括号的最大层数 广义表中括号嵌套的最大次数 广义表中括弧的重数 D 空表 长度为0 深度为1 A a b c 长度为2 第一个元素为原子a 第二个元素为子表 b c 深度为2 B A A D 长度为3 其前两个元素为表A 第三个元素为空表D 深度为3 C a C 长度为2递归定义的广义表 C相当于无穷表C a a a 深度无限 递归表的深度是无穷值 长度是有限值 F a a b a b c 长度为1 深度为4 广义表的表头 Head 和表尾 Tail 当广义表非空时 称第一个元
12、素a1为广义表的表头 其余元素组成的表 a2 a3 an 称为广义表的表尾 表头可能是原子 也可能是广义表 但表尾一定是广义表 广义表的图形表示用方框表示原子 用圆圈表示广义表 A B e C a b c d D A B C E a a b a b c 2 广义表的基本操作取表头GetHead LS a1 取表尾GetTail LS a2 a3 an B e GetHead B e GetTail B A a b c d e GetHead GetHead GetTail A GetHead GetHead b c d e GetHead b c d e b c A B A空表 长度0 深度1 无表头和表尾 B长度1 深度2 表头 表尾 3 广义表的存储结构广义表是一种递归的数据结构 因此很难为每个广义表分配固定大小的存储空间 所以其存储结构只好采用动态链式结构 广义表的头尾链表存储表示广义表的扩展线性链表存储表示 C a b c d a b c d b c d b c d c d d 广义表的头尾链表存储表示 C a b c d b c d 广义表的扩展线性链表存储表示 带表头结点 作业 5 10 感谢亲观看此幻灯片 此课件部分内容来源于网络 如有侵权请及时联系我们删除 谢谢配合
