4.5.4 特殊矩阵概述
- 特殊矩阵：具有相同的数据或0元素，且数据分布具有一定规律。
- 分类：
- 对称矩阵
- 三级矩阵
- 对角矩阵
- 特殊矩阵只有部分有数据，其他内容为零，使用内存中一维空间（一片连续的存储空间）进行存储时，零元素没有必要进行存储，通常都需要进行压缩存储。
- 压缩存储：多个值相同的矩阵元素分配同一个存储空间，零元素不分配存储空间。
- 存储有效数据，零元素和无效数据不需要存储。
- 不同的举证，有效和无效定义不同。
4.5.5 对称矩阵压缩存储【重点】
1）定义及其压缩方式
- 什么是对称矩阵：a(i,j) = a(j,i)
对称矩阵的压缩方式：共4种
- 下三角部分以行序为主序存储的压缩【学习，掌握】
2）压缩存放及其公式
- 压缩后存放到一维空间（连续的存放空间中）
- 对称矩形 A(i,j) 对应 一维数组 s[k] , k与i和j 公式：
3）练习
- 练习1：
a(8,5) -->索引库1,1表示方式
需要将1,1转化成0,0方式，从而可以使用公式，i和j同时-1
a(7,4) -->索引库0,0表示方式
因为：i >= j
k= i(i+1)/2 +j = 7 * 8 / 2 + 4 = 32
32为索引为0的一维数组的下标
数据b下标是从1开始，对应的下标 32+1=33
b[13] 下标从1开始，归零
b[12] 下标从0开始，k=12
i*(i+1)/2 , 如果i=4，结果为10
12-10 = j
下标0,0时，a(4,2)
下标1,1时，a(5,3)
4.5.6 三角矩阵
1）概述&存储方式
- 三角矩阵分为：上三角矩阵、下三角矩阵
- 上三角矩阵：主对角线（不含主对角线）下方的元素值均为0。只在上三角的位置进行数据存储
- 存储方式：三角矩阵的存放方式，与对称矩阵的存放方式相同。
2）上三角矩阵
- 上三角矩阵实例
3）下三角矩阵
- 下三角矩阵实例
下三角矩阵对应一维数组存放下标，计算公式
4.5.7 对角矩阵
1） 定义&名词
- 对角矩阵：矩阵的所有非零元素都集中在以主对角线为中心的带状区域中，即除主对角线上和直接在主对角线上、下方若干条对角线上的元素之外，其余元素皆为零。
名词：
- 半带宽：主对角线一个方向对角线的个数，个数为d。
- 带宽：所有的对角线的个数。个数为 2d+1
- n阶2d+1对角矩阵非零元素个数：n(2d+1) - d(d+1)
- n(2d+1) ：下图中所有颜色的个数
- d(d+1)/2 ：右下方浅蓝色三角的个数
- d(d+1) ：2个三级的个数（右下方、左上方）
- 一维数组存储个数：n(2d+1) ，若某行没有2d+1个元素，则0补足。
2）压缩存储
4.6 稀疏矩阵
4.6.1 定义&存储方式
- 稀疏矩阵：具有较多的零元素，且非零元素的分布无规律的矩阵。
- 稀疏因子：用于确定稀疏矩阵个数指标
- 常见的2种存放方式：三元组表存储、十字链表存储
4.6.2 三元组表存储
1） 概述
- 使用三元组唯一的标识一个非零元素
- 三元组组成：row行、column列、value值
- 三元组表：用于存放稀疏矩阵中的所有元素
2）相关类及其操作
三元组结点类publicclassTripleNode { //三结点publicintrow; //行号publicintcolumn; //列号publicintvalue; //元素值} 三元组顺序表类：publicclassSparseMatrix { //稀疏矩阵publicTripleNode[] data; //三元组表publicintrows; //行数npublicintcols; //列数mpublicintnums; //非零元素的个数}
- 三元组表初始化操作：
4.6.3 三元组表存储：矩阵转置
1）定义
- 矩阵转置：一种简单的矩阵运算，将矩阵中每个元素的
行列序号互换。
- 特点：矩阵N[m×n] 通过转置 矩阵M[n×m]
/** this转置前的对象，每一个对象中都有一个data数据* tm 转置后的对象，每一个对象中都有一个data数据* return 转置后的稀疏矩阵对象*/publicSparseMatrixtranspose() { //转置// 1 根据元素个数，创建稀疏矩阵SparseMatrixtm=newSparseMatrix(nums); // 2 设置基本信息tm.cols=rows; //2.1 行列交换tm.rows=cols; //2.2 列行交换tm.nums=nums; //2.3 元素个数// 3 进行转置intq=0; //3.1 转置后数据的索引for(intcol=0 ; col<cols; col++) { //3.2 转置之前数据数组的每一个列号for(intp=0; p<nums; p++) { //3.3 依次获得转置前数据数组的每一个数据if (data[p].column==col) { //3.4 获得指定列的数据tm.data[q].row=data[p].column; //3.5 行列交换，值不变tm.data[q].column=data[p].row; tm.data[q].value=data[p].value; q++; //3.6 转置后的指针后移 } } } // 4 返回转置后的稀疏矩阵returntm; }
- 矩阵转置时间复杂度：O(n×t) ，n列数，t非零个数
4.6.4 三元组表存储：快速矩阵转置
1）定义
- 假设：原稀疏矩阵为N、其三元组顺序表为TN，N的转置矩阵为M，其对应的三元组顺序表为TM。
- 快速转置算法：求出N的每一列的第一个非零元素在转置后的TM中的行号，然后扫描转置前的TN，把该列上的元素依次存放于TM的相应位置上。
- 基本思想：分析
原稀疏矩阵的数据,得到与转置后数据关系
- 每一列第一个元素位置：上一列第一个元素的位置 + 上一列非零元素的个数
- 当前列，原第一个位置如果已经处理，第二个将更新成新的第一个位置。
2）公式
- 需要提供两个数组：num[]、cpot[]
- num[] 表示N中第col列的非零元素个数
- cpot[] 初始值表示N中的第col列的第一个非零元素在TM中的位置
3）算法：快速转置
publicSparseMatrixfasttranspose() { // 1 根据元素个数，创建稀疏矩阵SparseMatrixtm=newSparseMatrix(nums); // 2 设置基本信息tm.cols=rows; //2.1 行列交换tm.rows=cols; //2.2 列行交换tm.nums=nums; //2.3 元素个数// 3 校验if(num<=0) { returntm; } // 4 每一列的非零个数intnum=newint[cols]; //4.1 根据列数创建num数组for(inti=0; i<cols; i++) { //4.2 初始数据（可省略）num[i] =0; } for(inti=0; i<nums; i++) { //4.3 遍历转置的数据intj=data[i].column; num[j]++; } // 5 转置后每一列第一个元素的位置数组intcpot=newint[cols]; // 5.1 位置的数组cpot[0] =0; // 5.2 第一列第一个元素为0for(inti=1; i<cols ; i++) { cpot[i] =cpot[i-1] +num[i-1]; // 5.3 当前列第一个元素位置 = 上一列位置+个数 } // 6 转置处理for(inti=0 ; i<nums ; i++) { intj=data[i].column; //6.1 转置前，每一个元素的列数intk=cpot[j]; //6.2 转置后的位置tm.data[k].row=data[i].column; //6.3 原数据 转置后 数据tm.data[k].column=data[i].row; tm.data[k].value=data[i].value; cpot[j]++; //6.4 下一个元素的位置 } } 时间复杂度：O(n+t) ，n列数，t非零个数
4.6.5 十字链表存储
1）定义
- 当稀疏矩阵中非零元素的位置或个数经常发生变化时，不宜采用三元组顺序表存储结构，而该用链式存储结构。
- 十字链表结点由5个域组成：
- row：所在行
- column：所在列
- value：非零元素值
- right：存放与该非零元素==同行==的下一个非零元素结点指针。
- down：存放与该非零元素==同列==的下一个非零元素结点指针。
2）相关类
结点类：classOLNode { publicintrow, col; //行号、列号publicintvalue; //元素值publicOLNoderight; //行链表指针publicOLNodedown; //列链表指针} 十字链表类：classCrossList { publicintmu, nu, tu; //行数、列数、非零元素个数publicOLNode[] rhead, chead; //行、列指针数组}
