java稀疏矩阵快速转置(精品文档)_共7页.docx

1 单元用起） ， B.data 中的====实习报告二 “稀疏矩阵快速转置 ”演示程序 =====（ 1）、程序的功能和特点1. 程序功能：三元组将稀疏矩阵的行号，列号和元素值作为三元组的三个元素 进行存储，该程序实现对稀疏矩阵的顺序存储，并可以对该稀疏矩阵进行快速实现转置2. 程序特点：采用 java 面向对象语言创建三元组存放稀疏矩阵结合 java 的语言特点，利用稀疏矩阵和三元组的存储特点，交换数组的行号和列号实现数组的快速转置二） 、程序的算法设计算法一： “稀疏矩阵的快速转置方法 ”算法：1. 【逻辑结构与存储结构设计】逻辑结构：线性结构存储结构：顺序存储结构行号 row 列号 col 元素值 value01232. 【基本操作设计】因为 A 中第一列的第一个非零元素一定存储在B.data[1] ，如果还知道第一列的非零元素的个数，那么第二列的第一个非零元素在 B.data 中的位置便等于第一列的第一个非零元素在 B.data 中的位置加上第一列的非零元素的个数， 如此类推，因为 A 中三元组的存放顺序是先行后列，对同一行来说，必定先遇 到列号小的元素，这样只需扫描一遍 A.data 即可。

根据这个想法，需引入两个向量来实现 ： num[n+1]和 cpot[n+1] ，num[col] 表示矩阵 A 中第 col 列的非零元素的个数（为了方便均从cpot ［col ］初始值表示矩阵 A 中的第 col 列的第一个非零元素在位置于是 cpot 的初始值为：cpot[1]=1 ；cpot[col]=cpot[col-1]+num[col-1] ； 2≤col ≤n例如对于矩阵 A 的 num和 cpot 的值如下：Col 1 2 3 4 5 6num[col] cpot[col]2 1 1 2 0 11 3 4 5 7 7矩阵 A 的 num 与 cpot 值依次扫描 A.data ，当扫描到一个 col 列元素时，直接将其存放在 B.data的 cpot[col] 位置上， cpot[col] 加１， cpot[col] 中始终是下一个 col 列元素在 B.data 中的位置。

3. 【算法设计】算法思路：①A 的行、列转化成 B 的列、行；②在 A.data 中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到 B.data 中即可15 0 0 220 11 3 0A=0006000091 0 0 00 0 0 0稀疏矩阵0 -150 010 020 030 040 0567i1112235j v1 154 226 -152 113 34 61 911500B=220 － 150 0 011 0 03 0 00 6 00 0 00 0 0A 的转置 B9100000000000A 的三元组表i1 12 13 24 35 46 47 6j v1 155 912 112 31 223 61 -154. 【高级语言代码】 B 的三元组表// 稀疏矩阵的快速转置方法（将自身转置后送出）public SparseMatrix FastmTrans(){// 转置矩阵的列数 , 行数和非零元素个数（交换行列数）SparseMatrix b= newSparseMatrix( Cols , Rows, Terms); // 构造方法二 // 分配辅助数组int rowSize[] = new int [ this . Cols ];int rowStart[] = new int [ this . Cols];// 统计每列的非零元素个数for ( int i = 0; i < this . Cols ; i++)rowSize[i] = 0;for ( int i = 0; i < this . Terms; i++ )rowSize[ this . smArray[i]. col ]++;// 转置后，每行第一个非零元素在三元组表中的位置rowStart[0] = 0;for ( int i = 1; i < this . Cols ; i++ )rowStart[i] = rowStart[i-1]+rowSize[i-1];// 快速转置for ( int i = 0; i < this . Terms; i++ ) {int j = rowStart[ this . smArray[i]. col ];// 首先遇到的总是本行第一个非零元素b. smArray[j]. row = this . smArray[i]. col ;b. smArray[j]. col = this . smArray[i]. row;b. smArray[j]. value = this . smArray[i]. value ; // 为本行的下一个非零元素定好位置rowStart[ this . smArray[i]. col ]++;}return b;}（三） 、程序中类的设计 “Trituple ” 类：1. 【逻辑结构与存储结构】 逻辑结构：线性结构。

存储结构：顺序存储结构为了运算方便，矩阵的非零元素的个数也同时存储这种存储的思想实现如下：将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，采用顺序存储方法存储该表15 0 0 220 11 3 00006A=000091 0 0 00 0 0 0稀疏矩阵0 -150 010 020 030 040 0567i1112235j v1 154 226 -152 113 34 61 912. 【主要成员变量说明】主要成员变量有：row： 为非零三元素的行号，为三元组表int 类型变量col： 为非零三元数组的列号， int value ：表示非零三元数组的值，为例如如下稀数矩阵，可以存储为三元组15 0 0 22 0 -150 11 3 0 0 0A=00060000000091 0 0 0 0 00 0 0 0 0 0稀疏矩阵类型变量。

float1234567类型的变量i j v1 1 151 4 221 6 -152 2 112 3 33 4 65 1 913. 【主要成员方法说明】 public Trituple( int三元组表r, int c, float v) ： 为 Trituple 类的构造函数该构造函数有三个参数，分别为该非零三元组的行号列号和元素的值4. 【高级语言代码】class Trituple { // 三元组类 Trituplepublic int row; // 非零元素行号 / 列号public int col ;public float value ; // 非零元素的值public Trituple( int r, int c, float v){row=r; col =c; value =v;}}“SparseMatrix ” 类：1. 【逻辑结构与存储结构】 逻辑结构：线性结构。

存储结构：顺序存储结构2. 【主要成员变量说明】主要成员变量有：Rows, Cols , Terms： 稀疏矩阵的行数 / 列数/ 非零元素数 Trituple smArray[] ： 动态分配结构体数组（三元组表）3. 【主要成员。