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

Page1 2020 4 5 第五章数组和广义表 Page2 2020 4 5 本章的基本内容是 数组的逻辑结构特征数组的存储方式及寻址方法特殊矩阵和稀疏矩阵的压缩存储方法广义表的基本概念和存储结构 Page3 2020 4 5 学习目标理解多维数组类型的特点及其在高级编程语言中的存储表示和实现方法 并掌握数组在 以行为主 的存储表示中的地址计算方法 掌握特殊矩阵的存储压缩表示方法 理解稀疏矩阵的两类存储压缩方法的特点及其适用范围 领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法 重点和难点重点是学习数组类型的定义及其存储表示 知识点数组的类型定义 数组的存储表示 特殊矩阵的压缩存储表示方法 随机稀疏矩阵的压缩存储表示方法 Page4 2020 4 5 线性表 具有相同类型的数据元素的有限序列 限制插入 删除位置 线性表 具有相同类型的数据元素的有限序列 限制元素类型为字符 串 零个或多个字符组成的有限序列 Page5 2020 4 5 线性表 具有相同类型的数据元素的有限序列 将元素的类型进行扩充 Page6 2020 4 5 5 1数组的定义 数组是线性表的推广数组可以看成是一种特殊的线性表 即线性表中数据元素本身也是一个线性表 Page7 2020 4 5 数组的抽象数据类型定义 ADTArray 数据对象 ji 0 bi 1 i 1 2 nD aj1 j2 jn n 0 为数组的维数 bi为数组第i维的长度 ji为数组元素的第i维下标 aj1 j2 jn ElemSet 数据关系 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 2 n Page8 2020 4 5 基本操作 InitArray A n bound1 boundn 操作结果 若维数n和各维长度合法 则构造相应的数组A DestroyArray A 初始条件 数组A已经存在 操作结果 销毁数组A Value A e index1 indexn 初始条件 A是n维数组 e为元素变量 随后是n个下标值 操作结果 若各下标不超界 则e赋值为所指定的A的元素值 并返回OK Assign A e index1 indexn 初始条件 A是n维数组 e为元素变量 随后是n个下标值 操作结果 若下标不超界 则将e的值赋给A中指定下标的元素 ADTArray Page9 2020 4 5 关于数组的基本操作 在数组中插入 或 一个元素有意义吗 将元素x插入到数组中第1行第2列 删除数组中第1行第2列元素 Page10 2020 4 5 存取 给定一组下标 读出对应的数组元素 修改 给定一组下标 存储或修改与其相对应的数组元素 存取和修改操作本质上只对应一种操作 寻址 数组应该采用何种方式存储 数组没有插入和删除操作 所以 不用预留空间 适合采用顺序存储 关于数组的基本操作 Page11 2020 4 5 数组的存储结构与寻址 一维数组 设一维数组的下标的范围为闭区间 l h 每个数组元素占用c个存储单元 则其任一元素ai的存储地址可由下式确定 Loc ai Loc al i l c 5 2数组的顺序表示和实现 Page12 2020 4 5 常用的映射方法有两种 按行优先 先行后列 先存储行号较小的元素 行号相同者先存储列号较小的元素 按列优先 先列后行 先存储列号较小的元素 列号相同者先存储行号较小的元素 数组的存储结构与寻址 二维数组 Page13 2020 4 5 l2 h2 l1 h1 a 二维数组 aij前面的元素个数 阴影部分的面积 整行数 每行元素个数 本行中aij前面的元素个数 i l1 h2 l2 1 j l2 按行优先存储的寻址 Page14 2020 4 5 假设有60行70列的二维数组a 1 60 1 70 以行序为主序顺序存储 其基地址为10000 每个元素占2个存储单元 那么第32行第58列的元素a 32 58 的存储地址为 无第0行第0列元素 16902B 16904 14454 答案A B C均不对 Page15 2020 4 5 第l1行 第l1 1行 i l1 h2 l2 1 j l2 个元素 Loc aij Loc al1l2 i l1 h2 l2 1 j l2 c 按行优先存储的寻址 按列优先存储的寻址方法与此类似 Page16 2020 4 5 Loc aijk Loc a000 i m2 m3 j m3 k c n n 2 维数组一般也采用按行优先和按列优先两种存储方法 请自行推导任一元素存储地址的计算方法 数组的存储结构与寻址 多维数组 Page17 2020 4 5 5 3矩阵的压缩存储 压缩存储为多个值相同的矩阵元只分配一个存储空间 对零元不分配空间 Page18 2020 4 5 特殊矩阵 矩阵中很多值相同的元素并且它们的分布有一定的规律 稀疏矩阵 矩阵中有很多零元素 压缩存储的基本思想是 为多个值相同的元素只分配一个存储空间 对零元素不分配存储空间 特殊矩阵和稀疏矩阵 Page19 2020 4 5 特殊矩阵的压缩存储 对称矩阵 3647862842481697460582957 A 对称矩阵特点 aij aji 如何压缩存储 只存储下三角部分的元素 5 3 1特殊矩阵 Page20 2020 4 5 a 下三角矩阵 b 存储说明 c 计算方法 aij在一维数组中的序号 阴影部分的面积 i i 1 2 j 1 一维数组下标从0开始 aij在一维数组中的下标k i i 1 2 j 0 in 1 0 j n 1 aij 对称矩阵的压缩存储 Page21 2020 4 5 对于下三角中的元素aij i j 在数组SA中的下标k与i j的关系为 k i i 1 2 j 上三角中的元素aij i j 因为aij aji 则访问和它对应的元素aji即可 即 k j j 1 2 i 对称矩阵的压缩存储 Page22 2020 4 5 特殊矩阵的压缩存储 三角矩阵 3cccc62ccc481cc7460c82957 a 下三角矩阵 34810c2946cc 57ccc08cccc7 b 上三角矩阵 如何压缩存储 只存储上三角 或下三角 部分的元素 Page23 2020 4 5 矩阵中任一元素aij在数组中的下标k与i j的对应关系 下三角矩阵的压缩存储 Page24 2020 4 5 矩阵中任一元素aij在数组中的下标k与i j的对应关系 上三角矩阵的压缩存储 Page25 2020 4 5 特殊矩阵的压缩存储 对角矩阵 对角矩阵 所有非零元素都集中在以主对角线为中心的带状区域中 除了主对角线和它的上下方若干条对角线的元素外 所有其他元素都为零 a00a01000a10a11a12000a21a22a23000a32a33a34000a43a44 A Page26 2020 4 5 按行存储 元素aij在一维数组中的序号 2 3 i 1 j i 2 2i j 1 一维数组下标从0开始 元素aij在一维数组中的下标 2i j b 寻址的计算方法 对角矩阵的压缩存储 k m 1 i j m 1 2 1下标 Page27 2020 4 5 如何只存储非零元素 注意 稀疏矩阵中的非零元素的分布没有规律 5 3 2稀疏矩阵 稀疏矩阵 Page28 2020 4 5 5 3 2稀疏矩阵 稀疏矩阵非零元较零元少 且分布没有一定规律的矩阵 压缩存储原则 只存矩阵的行列维数和每个非零元的行列下标及其值 矩阵维数 6 7 非零元 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 如何存储三元组表 Page29 2020 4 5 压缩存储 稀疏矩阵 三元组顺序表 以顺序存储结构来表示三元组 稀疏矩阵的三元组顺序表存储表示 defineMAXSIZE12500 假设非零元个数的最大值为12500typedefstruct inti j 该非零元的行下标和列下标ElemTypee Triple typedefstruct Tripledata MAXSIZE 1 非零元三元组表 data 0 未用intmu nu tu 矩阵的行数 列数和非零元个数 TSMatrix 行序 Page30 2020 4 5 678 1212 139 31 3 3614 4324 5218 6115 64 7 data ije 012345678 data 0 i data 0 j data 0 e分别存放矩阵行列维数和非零元个数 是否对应惟一的稀疏矩阵 Page31 2020 4 5 求转置矩阵 问题描述已知一个稀疏矩阵的三元组表 求该矩阵转置矩阵的三元组表 解决思路将矩阵行 列维数互换 将每个三元组中的i和j相互调换 重排三元组次序 Page32 2020 4 5 Page33 2020 4 5 方法一 按矩阵的列序转置按T data中三元组次序依次在M data中找到相应的三元组进行转置 768 13 3 1615 2112 2518 319 3424 46 7 6314 col 1 col 2 Page34 2020 4 5 1 设置转置后矩阵T的行数 列数和非零元个数 2 在T中设置初始存储位置q 3 for col 最小列号 col 最大列号 col 3 1在M中查找列号为col的三元组 3 2交换其行号和列号 存入T中q位置 3 3 q Page35 2020 4 5 算法5 1 StatusTransposeSMatrix TSMatrixM TSMatrix TransposeMatrix 时间复杂度为O nu tu 适用于tu mu tu Page36 2020 4 5 方法二 按矩阵的行序转置按M data中三元组次序转置 转置结果放入T data中恰当位置 此法关键是要预先确定M data中每一列第一个非零元在T data中位置 为确定这些位置 转置前应先求得M data的每一列中非零元个数 Page37 2020 4 5 引入两个数组作为辅助数据结构 num col 存储矩阵M中某列的非零元素的个数 cpot col 初值表示矩阵A中某列的第一个非零元素在T中的位置 数据结构设计 num与cpot存在如下递推关系 Page38 2020 4 5 768 13 3 1615 2112 2518 319 3424 46 7 6314 4 6 2 9 7 5 3 8 Page39 2020 4 5 1 设置转置后矩阵T的行数 列数和非零元素的个数 2 计算M中每一列的非零元素个数 3 计算M中每一列的第一个非零元素在T中的下标 4 依次取M中的每一个非零元素对应的三元组 4 1确定该元素在T中的下标q 4 2将该元素的行号列号交换后存入T中q的位置 4 3预置该元素所在列的下一个元素的存放位置 Page40 2020 4 5 算法5 2 StatusFastTransposeSMatrix TSMatrixM TSMatrix FastTransposeMatrix 时间复杂度为O nu tu 用空间换取时间 Page41 2020 4 5 三元组顺序表的特点 优点非零元在表中按行序有序存储 便于进行依行序处理的矩阵运算 缺点若需按行号存取某一行的非零元 则需从头开始进行查找 Page42 2020 4 5 压缩存储 稀疏矩阵 十字链表 引入原因当矩阵的非零元的个数发生变化时 不宜采用三元组表 如A A B 非零元的插入或删除将会引起A data中的数据移动 这是顺序结构三元组的弱势 十字链表结点形式 非零元的行 列 值 同一列下一个非零元 同一行下一个非零元 typedefstructOLNode inti j ElemTypee structOLNode right down OLNod OLink typedefstructOlink rhead chead intmu nu tu CrossList Page43 2020 4 5 列链表头指针 行链表头指针 Page44 2020 4 5 建立十字链表的算法5 4 m 4 n 3 t 5 1 1 3 2 2 5 2 3 4 4 1 8 2 1 7 Page45 2020 4 5 StatusCreateSMatrix OL CrossList CreateSMatrix OL 时间复杂度为O t s s max m n Page46 2020 4 5 广义表 n n 0 个数据元素的有限序列 记作 LS a1 a2 an 其中 LS是广义表的名称 ai 1 i n 是LS的成员 或直接元素 它可以是单个的数据元素 也可以是一个广义表 分别称为LS的单元素 或原子 和子表 广义表的逻辑结构 直接元素之间是线性关系 通常用大写字母表示广义表 用小写字母表示单元素 5 4广义表的定义 广义表 列表 Page47 2020 4 5 长度 广义表LS中的直接元素的个数 深度 广义表LS中括号的最大嵌套层数 表头 广义表LS非空时 称第一个元素为LS的表头 表尾 广义表LS中除表头外其余元素组成的广义表 广义表 和广义表 不同 广义表的基本概念 5 4广义表的定义 Page48 2020 4 5 A B e C a b c d D A B C 广义表的图形表示 Page49 2020 4 5 特性 广义表中的数据元素有固定的相对次序 广义表的元素可以是子表 而子表的元素还可以是子表 广义表可以为其它列表共享 广义表可以是一个递归的表 广义表与数组的区别 Page50 2020 4 5 操作 长度 A F b c d e E b c d e D E A F C A D F B a B a a a v 广义表中元素的 长度 应由最外层括弧中的 逗号 来定 A的长度为0F的长度为2E的长度为3D的长度为3C的长度为3B的长度为2 Page51 2020 4 5 广义表是递归定义的线性结构 LS 1 2 n i可以是单个元素 原子 也可以是广义表 子表 约定 用大写字母表示广义表的名称 用小写字母表示原子 例如 A 长度为0 深度为1F d e 长度为2 深度为2D a b c F 长度为2 深度为3C A D F 长度为3 深度为4B a B a a a 长度为2 广义表的名称 广义表的长度 表头 表尾 注意 表尾 是一个表 广义表的深度 指广义表包含的括号重数 Page52 2020 4 5 广义表是一个多层次的线性结构 广义表的结构特点 广义表中的数据元素有相对次序 广义表的长度定义为最外层包含的元素个数 广义表的深度定义为所含括弧的重数 广义表可以共享 广义表可以是一个递归的表 例如 D E F 其中 E a b c F d e D E F a d b c e 注意 1 原子 的深度为02 空表 的深度为13 递归表的深度是无穷值 长度是有限值 Page53 2020 4 5 任何一个非空广义表LS 1 2 n 均可分解为 表头 Head LS 1和表尾 Tail LS 2 n 两部分 例如 D E F a b c F 则 Head D ETail D F Head E aTail E b c Head b c b c Tail b c Head b c bTail b c c Head c cTail c 操作 取表头 取表尾 Page54 2020 4 5 广义表可以采用顺序存储结构吗 由于广义表中的数据元素的类型不统一 因此难以采用顺序存储结构来存储 若广义表不空 则可分解为表头和表尾 反之 一对确定的表头和表尾可唯一地确定一个广义表 采用头尾表示法存储广义表 如何采用链接存储结构存储广义表 5 5广义表的存储结构 Page55 2020 4 5 广义表中的数据元素既可以是广义表也可以是单元素 头尾表示法中的结点结构 表结点 存储广义表 元素结点 存储单元素 Page56 2020 4 5 广义表的结点结构表结点原子结点 标志域 标志域 表头指针 表尾指针 值域 Page57 2020 4 5 定义上述结点 说明如下 typedefenum ATOM LIST ElemTag ATOM 0 原子 LIST 1 子表structGLNode ElemTagtag 标志域 用于区分元素结点和表结点union 原子结点和表结点的联合部分 AtomTypeatom atom是原子结点的值域 AtomType用户定义struct structGLNode hp tp ptr ptr是表结点的指针域 ptr hp和ptr tp分别指向表头和表尾 Glist 广义表类型 Page58 2020 4 5 广义表的存储结构 头尾表示法 A B e C a b c d D A B C A B C D Page59 2020 4 5 另一种结点结构 标志域 标志域 表头指针 值域 同层下一个元素指针 同层下一个元素指针 Page60 2020 4 5 A B e C a b c d D A B C E a E B C D E A Page61 2020 4 5 本章小结 了解数组的类型定义及其在高级语言中实现的方法 数组的特点是一种多维的线性结构 并只进行存取或修改某个元素的值 因此它只需要采用顺序存储结构 介绍了稀疏矩阵的三种表示方法 至于在具体应用问题中采用哪一种表示法这取决于该矩阵主要进行什么样的运算 广义表是一种递归定义的线性结构 因此它兼有线性结构和层次结构的特点 Page62 2020 4 5 基础知识题 数组部分 假设有二维数组A6 8 每个元素用相邻的6个字节存储 存储器按字节编址 已知A的起始存储位置 基地址 为1000 计算 数组A的存储 数组A的最后一个元素a5 7的第一个字节的地址 按行存储时 元素a1 4的第一个字节的地址 按列存储时 元素a4 7的第一个字节的地址 Page63 2020 4 5 假设按低下标优先存储整数数组A9 3 5 8时 第一个元素的字节地址是100 每个整数占四个字节 问下列元素的存储地址是什么 1 a0000 2 a1111 3 a3125 4 a8247按高下标优先存储方式 以最右的下标为主序 顺序列出数组A2 2 3 3中所有元素ai j k l 为了简化表达 可以只