第6章矩阵与广义表

1 第六章矩阵与广义表 2 教学内容 6 1矩阵的定义和操作6 2矩阵的Java类实现6 3矩阵的压缩存储6 4特殊矩阵的压缩存储6 5稀疏矩阵及其存储结构6 6广义表 3 6 1矩阵的定义和操作 4 矩阵的定义 矩阵是由m n个数排列成m行 横向 n列 纵向 所形成的矩形数表 称为m n矩阵 简记为A aij m n 其中aij为A的第i行第j列的元素 5 矩阵是工程上常用的数学工具 它是由若干个数据按n行m列构成的一种数据结构 矩阵通常被用来组织数据 工程上通过对矩阵的计算实现对工程问题的计算 由于矩阵是由m行n列组成 逻辑上与二维数组相同 故通常用二维数组来做矩阵的存储结构 6 a11a12 a1 na21a22 a2 n am 1am 2 am n Am n 注意 矩阵中每个数据元素受多个线性关系制约 元素在每个线性关系上都有前驱 后继 在行关系中aij直接前趋是aij直接后继是在列关系中aij直接前趋是aij直接后继是 ai j 1 ai j 1 a i 1 j a i 1 j 7 1 取第i行第j列元素 2 获取矩阵的行数 3 获取矩阵的列数 4 获取元素的位置 5 矩阵相加 6 矩阵相乘 7 求矩阵的转置 8 转换为字符串 9 转换为二维数组 2 矩阵的操作 8 设 有设 有设 有设 有 矩阵的操作 9 矩阵加法矩阵相减 10 转置矩阵 M矩阵 T矩阵 11 矩阵乘法 12 相乘 C AB 结论 1 由m行n列乘以n行m列 的到m行m列矩阵 2 13 6 2矩阵的Java类实现 14 6 2 1矩阵接口 publicinterfaceIMatrix publicdoubleget inti intj publicintgetRowDimension publicintgetColumnDimension publicint location doubleobj publicMatrixplus MatrixB publicMatrixtimes MatrixB publicMatrixtranspose publicStringtoString publicdouble toTwoDimArray 15 publicclassMatriximplementsIMatrix privateint a privateintm n 行 列数 6 2 2普通矩阵类的实现 由于矩阵是由m行n列组成 逻辑上与二维数组相同 故通常用二维数组来做矩阵的存储结构 如int x newint m n 来描述一个mXn的矩阵M 其中x i j 表示矩阵元素M i 1 j 1 这里假设矩阵的行列值从1开始计数 矩阵从M 1 1 开始排列 16 1 矩阵初始化publicMatrix int b 初始化a b m b length 行数n b 0 length 列数 6 2 2矩阵的基本操作的实现 17 1 矩阵初始化2publicMatrix int b intm intn 初始化a b this m m 行数this n n 列数 6 2 2矩阵的基本操作的实现 18 2 取第i行j列的元素publicintget inti intj 取元素if i 0 6 2 2矩阵的基本操作的实现 19 3 获取矩阵行数publicintgetRowCount 获取行数returnm 4 获取矩阵列数publicintgetColCount 获取列数returnn 6 2 2矩阵的基本操作的实现 20 5 获取元素位置publicint location intobj 元素定位int result newint 2 result 0 result 1 1 for inti 0 i m i for intj 0 j n j if obj a i j result 0 i 1 result 1 j 1 returnresult returnnull 6 2 2矩阵的基本操作的实现 21 6 矩阵相加publicMatrixplus Matrixb 矩阵相加if m b m n b n returnnull int result newint m n for inti 0 i m i for intj 0 j n j result i j get i 1 j 1 b get i 1 j 1 Matrixc newMatrix result returnc 6 2 2矩阵的基本操作的实现 22 7 矩阵相乘算法描述 1 判断矩阵B的行 列是否等于A的列 行数2 创建A的行数B的列数的矩阵C3 计算C的元素值 6 2 2矩阵的基本操作的实现 23 7 矩阵相乘publicMatrixmultiplication Matrixb 矩阵相乘if n b m returnnull int result newint m b n for inti 0 i m i for intj 0 j b n j intsum 0 for intk 0 k n k sum a i k b get k 1 j 1 result i j sum Matrixc newMatrix result returnc 24 8 矩阵转置publicMatrixtranspose 求转置int b newint n m for inti 0 i m i for intj 0 j n j b j i a i j Matrixresult newMatrix b returnresult 6 2 2矩阵的基本操作的实现 25 9 矩阵转变成字符串publicStringtoString Stringresult for inti 0 i m i for intj 0 j n j result a i j result n returnresult 6 2 2矩阵的基本操作的实现 26 10 矩阵转变成二维数组publicint toTwoDimArray returna 6 2 2矩阵的基本操作的实现 27 矩阵应用举例 P147 28 6 3矩阵的压缩存储 29 Note 数组 一维数组Loc ai Loc a0 i c多维数组 1 静态顺序存储行主序列主序 30 Note 二维数组的顺序表示和实现 由于计算机的内存结构是一维的 因此用一维内存来表示多维数组 就必须按某种次序将数组元素排成一列序列 然后将这个线性序列存放在存储器中 又由于对数组一般不做插入和删除操作 也就是说 数组一旦建立 结构中的元素个数和元素间的关系就不再发生变化 因此 一般都是采用顺序存储的方法来表示数组 31 二维数组的两种存储方式 行优先顺序 将数组元素按行排列 以二维数组为例 按行优先顺序存储的线性序列为 a00 a01 a0n 1 a10 a11 a1n 1 am 10 am 11 am 1n 1 列优先顺序 将数组元素按列向量排列 A的m n个元素按列优先顺序存储的线性序列为 a00 a10 am 10 a01 a11 am 11 a0n 1 a1n 1 am 1n 1 32 6 3矩阵的压缩存储在科学与工程计算问题中 矩阵是一种常用的数学对象 在高级语言编制程序时 将一个矩阵描述为一个二维数组 矩阵在这种存储表示之下 可以对其元素进行随机存取 各种矩阵运算也非常简单 并且存储密度为1 但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下 许多单元去存储重复的非零元素或零元素 这对高阶矩阵会造成极大的浪费 为了节省存储空间 我们可以对这类矩阵进行压缩存储 即为多个相同的非零元素只分配一个存储空间 对零元素不分配空间 33 6 4特殊矩阵及其压缩存储说明 矩阵M 有的书或图上从M 0 0 开始 有的从M 1 1 开始 大家学习时候 不要迷糊 要看好上下文环境 看准确m n的取值范围 1 i m 1 j n0 i m 1 0 j n 1 34 35 6 4 1特殊矩阵 特殊矩阵 指非零元素或零元素的分布有一定规律的矩阵 下面我们讨论几种特殊矩阵的压缩存储 方阵 当m n时 矩阵A称为方阵 36 若一个n阶方阵A中元素满足下列条件 aij aji其中1 i j n 则称A为对称矩阵 例如 图 1是一个3 3的对称矩阵 1 对称矩阵 37 2 三角矩阵 1 上三角矩阵即矩阵上三角部分元素是随机的 而下三角部分元素全部相同 为某常数C 或全为0 具体形式见图 a 2 下三角矩阵即矩阵的下三角部分元素是随机的 而上三角部分元素全部相同 为某常数C 或全为0 具体形式见图 b 38 3 对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中 区域外的值全为0 则称为对角矩阵 i不等于j 则M i j 0 39 4 特殊对角矩阵 常见的有三对角矩阵 五对角矩阵 七对角矩阵等 例如 图5 3为7 7的三对角矩阵 即有三条对角线上元素非0 40 6 4 2特殊矩阵的压缩存储 41 1 对称矩阵 若矩阵An n是对称的 对称的两个元素可以共用一个存储单元 这样 原来n阶方阵需n2个存储单元 若采用压缩存储 仅需n n 1 2个存贮单元 将近节约一半存贮单元 这就是实现压缩的好处 但是 将n阶对称方阵存放到一个向量空间s 0 到s 1 中 我们怎样找到s k 与a i j 的一一对称应关系呢 使我们在s k 中直接找到a i j 我们仅以行优先存放分两种方式讨论 42 1 只存放下三角部分由于对称矩阵关于主对角线对称 故我们只需存放主对角线及主对角线以下的元素 这时 a 0 0 存入s 0 a 1 0 存入s 1 a 1 1 存入s 2 具体参见图5 4 这时s k 与a i j 的对应关系为 i i 1 2 j当i jk j j 1 2 i当i j 上面的对应关系读者很容易推出 当i j时 aij在下三角部分中 aij前面有i行 共有1 2 3 i个元素 而aij是第i行的第j个元素 即有k 1 2 3 i j i i 1 2 j 当i j时 aij在上三角部分中 但与aji对称 故只需在下三角部分中找aij即可 故只需将i与j交换即可 即k j j 1 2 i 43 44 2 只存放上三角部分对于对称阵 除了用下三角形式存放外 还可以用上三角形式存放 这时a 0 0 存入s 0 a 0 1 存入s 1 a 0 2 存入s 2 具体参见图5 5 这时s k 与a i j 的对应关系可以按下面方法推出 当i j时 aij在上三角部分中 前面共有i行 共有n n 1 n i 1 i n 个元素 而aij是本行第j i个元素 故k i n j i 当i j时 交换i与j即可 故s k 与a i j 的对应关系为 i n j i当i jk j n i j当i j 45 46 三角矩阵中的重复元素c可共享一个存储空间 其余的元素正好有n n 1 2个 因此 三角矩阵可压缩存储到向量sa n n 1 2 1 中 其中c存放在向量的最后一个分量中 2 三角矩阵 47 2 三角矩阵 1 下三角矩阵下三角矩阵的压缩存放与对称矩阵用下三角形式存放类似 但必须多一个存储单元存放上三角部分元素 与P152有点不一样 使用的存储单元数目为n n 1 2 1 故可以将n n的下三角矩阵压缩存放到只有n n 1 2 1个存储单元的向量中 假设仍按行优先存放 这时s k 与a i j 的对应关系为 i i 1 2 ji jk n n 1 2i j 48 2 上三角矩阵和下三角矩阵的存储类似 共需n n 1 2 1个存贮单元 与P152有点不一样 假设仍按行优先顺序存放 这时s k 与a i j 的对应关系为 i n i i 1 2 j i当i jk n n 1 2i j 49 3 对角矩阵 在一个n n的对角矩阵中 只有n个对角线上非零元素 故只需n个存储单元即可 零不占用存储单元 故可将n n对角矩阵A压缩存放到只有n个存储单元的s向量中 假设仍按行优先顺序存放 书上就是把向量更换为长度为n的线性表来存储对角矩阵上的非0元素 线性表的第i个元素存储对角矩阵元素D i i 书上这里的矩阵从M 1 1 开始 线性表也是从1开始计数 对角矩阵的Java实现 P150 50 对角矩阵的Java实现 P150代码分析 51 4 三对角矩阵 在一个n n的三对角矩阵中 只有n n 1 n 1个非零元素 故只需3n 2个存储单元即可 零元已不占用存储单元 故可将n n三对角矩阵A压缩存放到只有3n 2个存储单元的s向量中 假设仍按行优先顺序存放 则 s k 与a i j 的对应关系为 M从M 0 0 开始 k从0开始 3i 1当i j 1k 3i当i j3i 1当i j 1 52 4 三对角矩阵 书上k 2 i j 2来源 条件 M从M 1 1 开始 k从1开始 1 2 3 i 2 1当i j 1k 2 3 i 2 2当i j2 3 i 2 3当i j 1分别对应 3i 3 3i 2 3i 1 分别把一个i带入得到 2i j 1 3 2i j 2 2i j 1 1 53 4 三对角矩阵 书上k 2 i j 2来源 条件 M从M 1 1 开始 k从1开始 2 2 3 i 2 j i 2 2i j 2 54 6 5稀疏矩阵及其存储结构 55 稀疏矩阵定义 在上节提到的特殊矩阵中 元素的分布呈现某种规律 故一定能找到一种合适的方法 将它们进行压缩存放 但是 在实际应用中 我们还经常会遇到一类矩阵 其矩阵阶数很大 非零元个数较少 零元很多 但非零元的排列没有一定规律 我们称这一类矩阵为稀疏矩阵 简单说 设矩阵M中有s个非零元素 若s远远小于矩阵元素的总数 即s m n 则称A为稀疏矩阵 56 精确的来说 设在矩阵A中 有s个非零元素 令e s m n 称e为矩阵的稀疏因子 通常认为e 0 05时称之为稀疏矩阵 P152书上要求 非0元素的数目应小于矩阵总元素数目的1 3 主要考虑稀疏矩阵压缩存储的三元组方案 57 稀疏矩阵的压缩存储按照压缩存储的概念 要存放稀疏矩阵的元素 由于没有某种规律 除存放非零元的值外 还必须存贮适当的辅助信息 才能迅速确定一个非零元是矩阵中的哪一个位置上的元素 下面将介绍稀疏矩阵的几种存储方法及一些算法的实现 58 1 三元组表 顺序存储 在压缩存放稀疏矩阵的非零元同时 若还存放此非零元所在的行号和列号 则称为三元组表法 一个三元组 i j value 能唯一确定矩阵的一个非零元素 稀疏矩阵可用三元组表进行压缩存储 但它是一种顺序存贮 按行优先顺序存放 一个非零元有行号 列号 值 为一个三元组 整个稀疏矩阵中非零元的三元组合起来称为三元组表 数据元素为三元组的线性表 需要花费额外存储空间来保存行号和列号 59 稀疏矩阵M和N的三元组表见图5 8 60 三元组存储矩阵类的Java实现 1 P153代码分析 publicclassElement privateinti j 非零元的行下标和列下标privateintv 非零元 publicclassSeqSpaMatrix privateintm n t 行 列 非零元个数privateArrayListvalues 用于存储非零元三元组表 61 我们以矩阵的转置为例 说明在这种压缩存储结构上如何实现矩阵的运算 一个m n的矩阵A 它的转置B是一个n m的矩阵 且a i j b j i 1 i m 1 j n 即A的行是B的列 A的列是B的行 publicSeqSpaMatrixtanspose SeqSpaMatrixresult newSeqSpaMatrix n m t for inti 1 i t i Elemente Element datas get i result set element getCol element getRow e getValue returnresult 62 2 链式存储 当稀疏矩阵中非零元的位置或个数经常变动时 三元组就不适合于作稀疏矩阵的存储结构 此时 采用链表作为存储结构更为恰当 两种链式存储方法 带行指针向量的链式存储十字链表 63 2 1带行指针的链表 把具有相同行号的非零元用一个单链表连接起来 稀疏矩阵中的若干行组成若干个单链表 合起来称为带行指针的链表 实现方法多种 P158描述及Java实现 其它 如图5 6的稀疏矩阵M的带行指针的链表描述形式见图5 9 64 2 1带行指针的链表 优缺点 部分解决了三元组方式的缺点 查找矩阵元素费时遍历 它可以很轻易的遍历同一行中的所有元素 但却很难遍历同一列中的所有数据 为了解决这个缺点 出现了十字链表存储方式 65 2 2十字链表 十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法 在该方法中 每一个非零元用一个结点表示 结点中除了表示非零元所在的行 列和值的三元组 i j v 外 还需增加两个链域 行指针域 rptr 用来指向本行中下一个非零元素 列指针域 cptr 用来指向本列中下一个非零元素 66 2 2十字链表 稀疏矩阵中同一行的非零元通过向右的行指针链接成一个带表头结点的循环链表 同一列的非零元也通过列指针链接成一个带表头结点的循链链表 因此 每个非零元既是第i行循环链表中的一个结点 又是第j列循环链表中的一个结点 相当于处在一个十字交叉路口 故称链表为十字链表 67 另外 为了运算方便 我们规定行 列循环链表的表头结点和表示非零元的结点一样 也定为五个域 且规定行 列 域值为0 并且将所有的行 列链表和头结点一起链成一个循环链表 在行 列 表头结点中 行 列域的值都为0 故两组表头结点可以共用 即第i行链表和第i列链表共用一个表头结点 这些表头结点本身又可以通过V域 非零元值域 但在表头结点中为next 指向下一个表头结点 相链接 另外 再增加一个附加结点 由指针hm指示 行 列域分别为稀疏矩阵的行 列数目 附加结点指向第一个表头结点 则整个十字链表可由hm指针唯一确定 68 例子 假设矩阵行列值m n从0开始计算 矩阵从M 0 0 开始 用十字链表表示如下页所示 69 70 6 6广义表 71 基本概念 广义表是第二章提到的线性表的推广 线性表中的元素仅限于原子项 即不可以再分 而广义表中的元素既可以是原子项 也可以是子表 另一个线性表 1 广义表的定义 广义表是n n 0 个元素a1 a2 a3 an的有限序列 其中ai或者是原子项 或者是一个广义表 通常记作LS a1 a2 a3 an LS是广义表的名字 n为它的长度 若ai是广义表 则称它为LS的子表 习惯上用大写字母表示广义表的名称 用小写字母表示原子 72 当广义表非空时 称第一个元素a1为LS的表头 表头可能是原子 也可能是列表 其余元素组成的表 a2 a3 an 是LS的表尾 表尾一定是列表 例如 若C a b c d D A B C 则 Head D ATail D B C Head C aTail C b c d 以上是广义表的两个操作 取表头Head 取表尾Tail这些操作还可以嵌套调用 Head Tail D Head B C B 73 注意 广义表 和广义表 不同 为空表 长度n 0 不能分解成表头和表尾 不是空表 其长度n 1 可以分解得到表头是空表 表尾是空表 74 2 举例 A A是一个空表 其长度为0 B e B只有一个原子 其长度为1 表头为e 表尾为空表 C a b c d 长度为2D A B C 其长度为3E a E 递归表 长度为2 75 3 广义表的表示方法 1 用LS a1 a2 an 形式 其中每一个ai为原子或广义表例如 A b c B a A E a E 都是广义表 2 将广义表中所有子表写到原子形式 并利用圆括号嵌套例如 上面提到的广义表A B C可以描述为 A b c B a A b c E a E a E 76 3个重要结论 列表的元素可以是子表 而子表的元素还可以是子表 由此列表是一个多层次结构 可用图形象的表示 用图示表