《数组顺序表示》PPT课件.ppt

一 教学内容 1 数组的定义和顺序存储方式 2 特殊矩阵的压缩存储 3 稀疏矩阵4 广义表的概念 表示及基本操作 广义表存储结构的实现 二 教学要求 1 了解数组的两种存储表示方法 并掌握数组在以行为主的存储结构中的地址计算方法 2 掌握对特殊矩阵进行压缩存储时的下标变换公式 3 了解稀疏矩阵的两种压缩存储方法的特点和适用范围 理解以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法 4 掌握广义表的结构特点及其存储表示方法 会对非空广义表进行分解 第五章数组和广义表 知识结构图 知识结构图 数组与广义表 数组 广义表 压缩存储 类型定义 顺序表示 稀疏矩阵 特殊矩阵 存储结构 类型定义 基本操作 基本操作 应用 递归算法 压缩存储 各种运算 第五章数组和广义表 简介 线性表的扩展 表中数据元素也是一种数据结构 数组的定义 顺序表示稀疏矩阵的压缩存储广义表的定义 存储结构和递归算法重点 数组的顺序表示稀疏矩阵的压缩存储结构和其上矩阵运算的实现广义表的递归算法难点 n维数组元素存储地址的计算稀疏矩阵的压缩存储结构及其上的运算的实现广义表的递归算法 第五章数组和广义表 5 1数组的定义5 2数组的顺序表示和实现5 3矩阵的压缩存储5 4广义表的定义5 5广义表的存储结构 5 1数组的定义 本章之前讨论的线性结构的数据元素都是非结构的原子类型 元素值不可再分 本章讨论的两种数据结构 数组和广义表 作为线性表的扩展 表中的数据元素本身也是一种数据结构 抽象数据类型数组的定义数组的顺序表示n维数组的存储方式n维数组的数据元素存储位置的计算公式 5 1数组的定义 n维数组是线性表的推广当n 1 n维数组退化成顺序表当n 1 n维数组可看成表中数据元素仍是线性表的线性表 A 0 1 p p m 1或n 1 5 1数组的定义 C语言中二维数组的类型定义 typedefElemTypeArray2 m n 等价于typedefElemTypeArray1 n typedefArray1Array2 m 因此定义二维数组A可如右 Array2A 二维的数组 定长的线性表 Amxn a11 a12 a13 a1n a21 a22 a23 a2n am1 am2 am3 amn 二维数组的二种理解方式 视作多个一维数组视作一个一维数组 数组是n n 1 个相同类型数据元素a1 a2 an构成的有限序列 且该有限序列存储在一块地址连续的内存单元中 由此可见 数组的定义类似于采用顺序存储结构的线性表 数组具有以下性质 1 数组中的数据元素数目固定 一旦定义了一个数组 其数据元素数目不再有增减变化 2 数组中的数据元素具有相同的数据类型 3 数组中的每个数据元素都和一组惟一的下标值对应 4 数组是一种随机存储结构 可随机存取数组中的任意数据元素 数组的抽象数据类型 ADTArray 数据对象 D aj1j2 jn ji 0 bi 1 i 1 2 nn 0 称为数组的维数 bi是数组第i维的长度 ji是数组元素的第i维下标 aj1j2 jn Elemset 数据关系 R R1 R2 Rn Ri aj1 ji jn aj1 ji 1 jn 0 jk bk 1 1 k n且k i 0 ji bi 2 i 2 n aj1 ji jn aj1 ji 1 jn D 基本操作 InitArray 取数组元素值Assign A e index1 index2 indexn 给数组元素赋值 ADTArray 数组一旦定义后 其维数和维界不再改变 因此除了结构的初始化和销毁之外 只有存取和修改元素值的操作 n维数组的特点 n维数组中含有 bi个数据元素 每个数据元素都受着n个关系的约束 在每个关系中 元素aj1j2 jn 0 ji bi 2 都有一个直接后继 数据元素都必须属于同一数据类型 n 1时 退化为定长的线性表 n维数组可以看成是线性表的推广 数组一旦被定义 则维数已定 对于数组的操作只有存取元素和修改元素 一旦建立了数组 数组中的元素个数和元素之间的关系就不再发生变动 数组是多维的结构 而存储空间是一个一维的结构 存储时需要一个次序约定 补充 不讲 类型特点 1 只有引用型操作 没有加工型操作 2 数组是多维的结构 而存储空间是一个一维的结构 二维及以上数组有两种顺序映象的方式 1 以行序为主序 低下标优先 2 以列序为主序 高下标优先 5 2数组的顺序表示和实现 在一维数组中 一旦a1的存储地址LOC a1 确定 并假设每个数据元素占用k个存储单元 则任一数据元素ai的存储地址LOC ai 就可由以下公式求出 LOC ai LOC a1 i 1 k 0 i n 上式说明 一维数组中任一数据元素的存储地址可直接计算得到 即一维数组中任一数据元素可直接存取 因此 一维数组是一种随机存储结构 同样 二维及多维数组也满足随机存储特性 C PASCAL 等 FORTRAN 二维数组的两种存储方式 5 2数组的顺序表示 计算数组任一元素 的地址需要的三要素 数组的起始地址 即基地址 数组维数和各维的长度 数组中每个元素所占的存储单元已知二维数组Ab1 b2 每个元素占L个存储单元 LOC 0 0 是数组第一个元素的起始地址 以行序为主存储 求LOC i j 行主序 LOC i j LOC 0 0 b2 i j L 列主序 LOC i j LOC 0 0 b1 j i L 设一般的二维数组是A c1 d1 c2 d2 这里c1 c2不一定是0 二维数组列优先存储的通式为 LOC aij LOC ac1 c2 j c2 d1 c1 1 i c1 L 单个元素长度 aij之前的行数 数组基址 总列数 即第2维长度 aij本行前面的元素个数 则行优先存储时的地址公式为 LOC aij LOC ac1 c2 i c1 d2 c2 1 j c2 L 计算二维数组元素地址的通式 补充 不讲 数组元素的存储位置是其下标的线性函数 由于计算各个元素存储位置的时间相等 所以存储数组中任一元素的时间也相等 我们称具有这一特点的存储结构为随机存储结构 5 2数组的顺序表示和实现 n维数组元素存储地址的计算公式 教材93页设各维长度分别为b1 b2 b3 bn 每个元素占L个存储单元 起始地址是LOC 0 0 0 求元素的存储位置 Cn L ci 1 bi ci 1 i n LOC j1 j2 jn LOC 0 0 0 b2 b3 bn j1 b3 b4 bn j2 bn jn 1 jn L 5 2数组的顺序表示 小结 n维数组的特点 数据元素同属于一种数据类型 数组一旦被定义 则维数和各维长度不能改变 数组操作只有引用型操作 没有加工型操作 数组是多维结构 但存储空间是一维结构 数组顺序表示的特点存储单元地址连续 需要一段连续空间 存储规则 以行 列 为主序 决定元素实际存储位置随机存取存储密度最大 100