《第五章 数组 new.ppt》由会员分享，可在线阅读，更多相关《第五章 数组 new.ppt（29页珍藏版）》请在金锄头文库上搜索。
1、5 1数组的定义5 2数组的顺序表示和实现5 3矩阵的压缩存储5 3 1特殊矩阵5 3 2稀疏矩阵5 4广义表 第五章数组和广义表 数组可以看成是一种特殊的线性表 即线性表中数据元素本身也是一个线性表5 1数组的定义和特点定义 数组特点数组结构固定数据元素同构数组运算给定一组下标 存取相应的数据元素给定一组下标 修改数据元素的值 5 2数组的顺序存储结构次序约定以行序为主序以列序为主序 5 3矩阵的压缩存储5 3 1对称矩阵 存下三角阵 下三角阵sa k 的下标k和aij的对应关系是 在aij和sa k 之间找一个对应关系 k 0123 n n 1 2 1 对角矩阵 带状矩阵 不讲 对角矩阵中
2、 所有的非零元素集中在以主对角线为中心的带状区域中 即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外 其余元素皆为零 M由 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 和矩阵维数 6 7 唯一确定 定义 非零元较零元少 且分布没有一定规律的矩阵压缩存储原则 只存矩阵的行列维数和每个非零元的行列下标及其值 5 3 2稀疏矩阵 稀疏矩阵的三元组顺序表存储表示 defineMAXSIZE12500 非零元素个数最大值 typedefstruct inti j 非零元素行列下标ElemTypee Triple typedefstr
3、uct Tripledata MAXSIZE 1 非零元素三元组表 data 0 未用 intmu nu tu 矩阵的行数列数非零元素个数 TSMatrix 注意 data域中表示非零元的三元组是以行序顺序排列的 1 三元组表 例 练习 写出M N的三元组表 思考 试写一算法 建立顺序存储稀疏矩阵的三元组表 分析 假设A是一个稀疏矩阵 B存放A矩阵生成的三元组表 在这个算法中要进行二重循环来判定每个矩阵元素是否为零 若不为0 则将其行 列下标及其值存入B中 例如 求转置矩阵问题描述 已知一个稀疏矩阵的三元组表 求该矩阵转置矩阵的三元组表 问题分析一般矩阵转置算法 for col 0 col n
4、 col for row 0 row m row n col row m row col T n O m n 解决思路 只要做到 将矩阵行 列维数互换 将每个三元组中的i和j相互调换 重排三元组次序 使mb中元素以N的行 M的列 为主序 三元组表M的mu nu tu的值分别为 6 7 8三元组表N的mu nu tu的值分别为 7 6 8 即按mb中三元组次序依次在ma中找到相应的三元组进行转置 为找到M中每一列所有非零元素 需对其三元组表ma从第一行起扫描一遍 由于ma中以M行序为主序 所以由此得到的恰是mb中应有的顺序 方法1 按M的列序转置 13 3 1615 2112 2518 319
5、3424 46 7 6314 col 1 col 2 算法描述 StatusTransposMaStattrix TSMatrixM TSMatrix TransposeSMatrix 算法分析 T n O M的列数n 非零元个数t 若t与m n同数量级 则 三元组顺序表虽节省存储空间 但时间复杂度比一般矩阵转置的算法还要复杂 同时还有可能增加算法的难度 因此 此算法仅适用于t m n的情况 方法2 快速转置即按ma中三元组次序转置 转置结果放入b中恰当位置此法关键是要预先确定M中每一列第一个非零元在mb中位置 为确定这些位置 转置前应先求得M的每一列中非零元个数 1 3 5 7 8 8 9
6、13 3 1615 2112 2518 319 3424 46 7 6314 4 6 2 9 7 5 3 算法描述 算法分析 算法中有四个并列的单循环 T n O M的列数n 非零元个数t 若t与m n同数量级 则T n O m n 2 十字链表结点定义 typedefstructnode introw col val structnode down right JD rhead chead 5 4广义表的定义数据对象 D ei i 1 2 n n 0 ADTGlist ei AtomSet或ei GList AtomSet为某个数据对象 数据关系 LR ei 1 ei D 2 i n 广义表
7、是递归定义的线性结构 LS 1 2 n 其中 i或为原子或为广义表换句话说 广义表是一个多层次的线性结构 例如 D E F E a b c F e A B a B a a a C A D F E a E 广义表的结构特点 1 广义表中的数据元素有相对次序 2 广义表的长度定义为最外层包含的元素个数 3 广义表的深度定义为所含括弧的重数 注意 原子 的深度为 0 空表 的深度为14 广义表可以共享 5 广义表可以是一个递归的表 递归表的深度是无穷值 长度是有限值 6 任何一个非空广义表LS 1 2 n 均可分解为表头Head LS 1和表尾Tail LS 2 n 两部分 基本操作 结构的创建和销毁InitGList ADTGList 5 5广义表的表示方法头 尾指针的链表结构 原子结点 tag 0autom 教学目标和要求 掌握数组的定义掌握数组顺序存储结构掌握特殊矩阵的压缩存储 1 对称矩阵的下三角存储2 稀疏矩阵的压缩存储 包括 三元组表 重点掌握三元组实现矩阵转置至少一种算法 十字链表 理解 了解广义表的应用
