数据结构ds-5

第五章数组和广义表 普通数组的定义和表示特殊矩阵的压缩存储稀疏矩阵的存储和运算广义表的定义 存储和运算 5 1数组的概念 数组 是一种线性数据结构 它是有限个相同类型数据元素的有序集合 数组的数据元素是值和下标的偶对 对每个有定义的下标 都有一个相关连的值 a11a12 a1nAmxn a21a22 a2n am1am2 amn 基本操作 两种主要的运算 1 给定一组下标 读取相应的数据元素 GetValue A e i j 2 修改元素值 ChangeValue A e i j 数组一般不作插入和删除操作 5 2数组的顺序表示和实现 逻辑多维到存储一维的映射 即寻找多维下标和一维下标的关系 存储方式行序为主序的存储方式以列序为主序的存储方式 数组元素的存储位置是其下标的线性函数 存取数组中任一元素的时间相等 所以 数组是随机的存储结构 计算一维下标以二维数组A n m 为例 计算数组元素A i j 的存储空间下标w 以行序为主序的存储方式w i m j以列序为主序的存储方式w j n i有三维数组A 3 4 5 计算数组元素A 2 3 3 的存储空间下标 以行序为主w 2 4 5 3 5 3 58 数组的顺序存储表示和实现typedefstruct ElemType base intdim int bounds 数组维界基址int constants 数组映象函数 Page93的式 5 2 Array 常量Ci基址 Cn L 1 Ci 1 bi Ci 5 3特殊矩阵的压缩存储 特殊矩阵 数值相同的元素或零元素在矩阵中的分布有一定规律 例 对称矩阵的压缩存储 以行序为主序存储下三角中的元素 包括对角线上的元素 aij aji1 i j n 1 二维下标为 i j 存储空间的一维下标为k 给出k与i j的关系 1 j i j 在下三角区k j 1 j 2 i 1 i j return i 1 i 2 j 1 return j 1 j 2 i 1 2 输入并存储对称矩阵的算法 以行序为主序 voidInput ETA intn for k 0 k 0 e A k returnOK elsereturnERROR 4 修改对称矩阵中某元素的算法 StatusChange ETA inti intj ETe if k ij TO k i j 0 A k e returnOK elsereturnERROR 5 输出打印对称矩阵的算法 voidPrintPro ETA intn for i 1 i n i printf n for j 1 j n j GetElem A i j e printf 3d e 思考题 上三角矩阵 下三角矩阵 对角矩阵 等特殊矩阵的压缩存储和相关的算法描述 稀疏矩阵及其存储结构定义 如果一个m n矩阵的非零元素个数r比零元个数少 且非零元的分布没有一定规律 压缩存储 只存储稀疏矩阵的非零元素 稀疏矩阵的三元组表存储方式typedefstruct inti j ElemTypee Triple Triple data data 0 的三元分别用于存放矩阵总的行数 列数和非零元个数 用三元组表示的非零元以行序为主序依次存放在data中 76813 3161521122518319342446 76314 678121213931 3361443245218611564 7 转置算法一aijvbijv由a求其转置矩阵b 需做以下事情 矩阵的行列值互换 即若a为m n 则b为n m 每个三元组的行列号互换 即aij对应于bji a中三元组以原矩阵的行号为序 而b中三元组是以原矩阵的列号为序 StatueTranSM TripleA Triple 该方法实现直观 易理解 时间复杂度为O a nu a tu 快速转置算法思想设置num l a nu 和cpot l a nu 两个辅助向量 在a data中求矩阵M的每一列中非零元素个数 存于辅助向量num的对应列中 用递推公式算出每一列第一个非零元素在b data中的位置 存于辅助向量cpot的对应列中 递推公式为 cpot 1 1cpot col cpot col 1 num col 1 col 2 a nu依次对a data中的三元组进行转置 并按三元组的列号 从cpot的对应列取出该三元组应存放在b data中的位置 然后将cpot该列中的值加1 使其记载该列下一非零元素在b data中的位置 aijv 1234567num2221010cpot1357889 用递推公式算出每一列第一个非零元素在b data中的位置 存于辅助向量cpot的对应列中 cpot 1 1cpot col cpot col 1 num col 1 col 2 a nu ijv 2324 0515 209 5214 1418 mb 各列第一个非零元三元组按先前求出的位置 放至mb 中 各列后续的非零元三元组 顺序放到对应列元素的后面 02 3 1012 35 7 2 2 8 1 1 0 0 1 3 5 2 7 8 9 ijv ijv A矩阵 0112 1012 第1列第一个非零元在mb 中的位置 029 第2列第一个非零元在mb 中的位置 209 20 3 02 3 2514 5214 3224 2324 4118 1418 5015 0515 53 7 35 7 4 第1列第二个非零元在mb 中的位置 6 5 快速转置算法图示 第3列第一个非零元在mb 中的位置 第0列第一个非零元在mb 中的位置 2 7 9 3 第5列第一个非零元在mb 中的位置 求各列第1个非零元在mb 中位置 求各列非零元个数 扫描ma 实现A到B的转置 B矩阵 12345678 StatusFastTranSM TripleA Triple 时间复杂度为O a nu a tu 5 4广义表的定义 广义表 是n n 0 个元素的集合 LS d1 d2 d3 dn LS为表名di D0时 称di为单元素 用小写字母表示 di Lists时 称di为子表 用大写字母表示 n为表的长度 当长度为0时称为空表 n 0时 第一个元素d1为表头 n 0时 d2 dn 称为表尾 广义表的长度和深度长度n 是广义表的元素个数 深度k 广义表的元素之间除了存在次序关系外 还存在层次关系 广义表中元素的最大层次为表的深度 提示 元素的层次就是包括该元素的括号对的数目 广义表举例 A n 0 k 1B e n 1 k 1C a b c d n 2 k 2D A B C n 3 k 3 即D e a b c d E a E n 2 k 定义一个无限表 a a a Gethead C aGethead D AGettail C b c d Gettail B 5 5广义表的链式存储结构 结点结构 typedefstructGLN inttag union AtomTypeatom structGLN hp structGLN tp Glist 广义链表表头表尾结点表示法 Page110 tag 1hptp tag 0atomtp 原子结点 表结点 例 画广义表的存储结构C a b c d n 2 k 3 C 1 0a 1 0b 0c 0d 广义表 F e C 长度 n 3 深度 k 4 F 1 0e 1 1 1 例 用存储结构表示广义表达式A B e C a b c d D A B C e a b c c E a E a a a 1 A C B D 本章重点一般多维数组的存储特殊矩阵的压缩存储稀疏矩阵的三元组表示和运算 初始化和转置 广义表的定义 存储和运算 算法作业 第五章数组 三元组算法练习 1 按照行序为主序的要求 依次输入非零元的三元组存放于动态数组data中 2 输出打印稀疏矩阵 3 求稀疏矩阵A的转置矩阵 Page99 4 实现快速转置 Page100 稀疏矩阵作业 已知稀疏矩阵A 1 画出其三元组的存储表示 2 画出其转置矩阵的三元组的存储表示 并给出数组num pos各项的