java稀疏矩阵快速转置.docVIP

====实习报告二 “稀疏矩阵快速转置”演示程序 ===== 、程序的功能和特点 1. 程序功能：三元组将稀疏矩阵的行号，列号和元素值作为三元组的三个元素进行存储，该程序实现对稀疏矩阵的顺序存储，并可以对该稀疏矩阵进行快速实现转置。 2. 程序特点：采用java面向对象语言。创建三元组存放稀疏矩阵。结合java的语言特点，利用稀疏矩阵和三元组的存储特点，交换数组的行号和列号实现数组的快速转置。 （二）、程序的算法设计 算法一：“稀疏矩阵的快速转置方法”算法： 【逻辑结构与存储结构设计】 逻辑结构：线性结构。 存储结构：顺序存储结构。 行号row 列号col 元素值value 0 1 2 3 【基本操作设计】 因为A中第一列的第一个非零元素一定存储在B.data[1]，如果还知道第一列的非零元素的个数，那么第二列的第一个非零元素在B.data中的位置便等于第一列的第一个非零元素在B.data中的位置加上第一列的非零元素的个数，如此类推，因为A中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这样只需扫描一遍A.data即可。 根据这个想法，需引入两个向量来实现 ：num[n+1]和cpot[n+1]，num[col]表示矩阵A中第col列的非零元素的个数（为了方便均从1单元用起），cpot［col］初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。于是cpot的初始值为： cpot[1]=1； cpot[col]=cpot[col-1]+num[col-1]； 2≤col≤n 例如对于矩阵A的num 和cpot的值如下： 依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的cpot[col]位置上，cpot[col]加１，cpot[col]中始终是下一个col列元素在B.data中的位置。 【算法设计】 算法思路： ①A的行、列转化成B的列、行； ②在A.data中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到B.data中即可。 4.【高级语言代码】 //稀疏矩阵的快速转置方法（将自身转置后送出） public SparseMatrix FastmTrans(){ //转置矩阵的列数,行数和非零元素个数（交换行列数） SparseMatrix b=new SparseMatrix(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”类： 【逻辑结构与存储结构】 逻辑结构：线性结构。 存储结构：顺序存储结构 为了运算方便，矩阵的非零元素的个数也同时存储。这种存储的思想实现如下： 将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，采用顺序存储方法存储该表。