首页 > 代码库 > javascript实现数据结构: 稀疏矩阵之三元组线性表表示
javascript实现数据结构: 稀疏矩阵之三元组线性表表示
稀疏矩阵(Sparse Matrix)：对于稀疏矩阵，目前还没有一个确切的定义。设矩阵A是一个n*m的矩阵中有s个非零元素，设 δ=s/(n*m)，称δ为稀疏因子，
如果某一矩阵的稀疏因子δ满足δ≦0.05时称为稀疏矩阵，
稀疏矩阵的压缩存储
对于稀疏矩阵，采用压缩存储方法时，只存储非0元素。必须存储非0元素的行下标值、列下标值、元素值。因此，一个三元组(i, j, aij)唯一确定稀疏矩阵的一个非零元素。
上图的稀疏矩阵A的三元组线性表为： ( (1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (5,2,18), (6,7,-7), (7,4,-6) )
1 三元组顺序表
若以行序为主序，稀疏矩阵中所有非0元素的三元组，就可以得构成该稀疏矩阵的一个三元组顺序表。
1 function Triple(i, j, elem) { 2 // 该非零元的行下标和列下标 3 this.i = i || 0; 4 this.j = j || 0; 5 this.e = elem || null; 6 } 7 8 function TSMatrix(mu, nu) { 9 // 非零元三元组表 10 this.data =http://www.mamicode.com/ []; 11 // 矩阵的行数，列数 12 this.mu = mu || 0; 13 this.nu = nu || 0; 14 }
下图所示的稀疏矩阵及其相应的转置矩阵所对应的三元组顺序表：
一个m*n的矩阵A，它的转置B是一个n*m的矩阵，且b[i][j]=a[j][i]，0≦i≦n，0≦j≦m，即B的行是A的列，B的列是A的行。
设稀疏矩阵A是按行优先顺序压缩存储在三元组表a.data中，若仅仅是简单地交换a.data中i和j的内容，得到三元组表b.data，
b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组表b.data中元素的顺序。
求转置矩阵的基本算法思想是：
① 将矩阵的行、列下标值交换。即将三元组表中的行、列位置值i 、j相互交换；
② 重排三元组表中元素的顺序。即交换后仍然是按行优先顺序排序的。
方法一： 算法思想：按稀疏矩阵A的三元组表a.data中的列次序依次找到相应的三元组存入b.data中。
每找转置后矩阵的一个三元组，需从头至尾扫描整个三元组表a.data 。找到之后自然就成为按行优先的转置矩阵的压缩存储表示
TSMatrix.prototype = { constructor: TSMatrix, addTriple: function (triple) { if (triple instanceof Triple) { if(triple.i >= this.mu) this.mu = triple.i + 1; if(triple.j >= this.nu) this.nu = triple.j + 1; this.data.push(triple); return true; } return false; }, // 采用三元组表存储表示，求稀疏矩阵的转置矩阵t // 按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置 transposeSMatrix: function () { var t = new TSMatrix(); t.mu = this.nu; t.nu = this.mu; if (this.data.length) { var q = 0; for (var col = 0; col < this.nu; col++) { for (var p = 0; p < this.data.length; p++) { if (this.data[p].j === col) t.data[q++] = new Triple(this.data[p].j, this.data[p].i, this.data[p].e); } } } return t; } };
算法分析：本算法主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(nu * data.length)，即矩阵的列数和非0元素的个数的乘积成正比。
方法二(快速转置的算法) 算法思想：
直接按照稀疏矩阵A的三元组表a.data的次序依次顺序转换，并将转换后的三元组放置于三元组表b.data的恰当位置。
前提：若能预先确定原矩阵A中每一列的(即B中每一行)第一个非0元素在b.data中应有的位置，则在作转置时就可直接放在b.data中恰当的位置。
因此，应先求得A中每一列的非0元素个数。 附设两个辅助向量num[ ]和cpot[ ] 。
◆ num[col]：统计A中第col列中非0元素的个数；
◆ cpot[col] ：指示A中第一个非0元素在b.data中的恰当位置。
显然有位置对应关系：
快速转置算法如下：
1 // 采用三元组表存储表示，求稀疏矩阵的转置矩阵t 2 /* 3 按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。 4 如果能预先确定矩阵M中每一列（即T中每一行）的第一个非零元在b.data中应有的位置， 5 那么在对a.data中的三元组依次做转置时，便可直接放到b.data中恰当的位置上去。 6 为了其额定这些位置，在转置前，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data中应有的位置。 7 在此，需要设num和cpot两个变量。num[col]表示矩阵M中第col列中非零元的个数， 8 cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。显然有： 9 cpot[0] = 1; 10 cpot[col] = cpot[col - 1] + num[col - 1] 2 <= col <= a.nu 11 */ 12 TSMatrix.prototype.fastTransposeSMatrix = function(){ 13 var t = new TSMatrix(); 14 t.mu = this.nu; 15 t.nu = this.mu; 16 17 if(this.data.length){ 18 var num = []; 19 for(var col = 0; col < this.nu; col++) 20 num[col] = 0; 21 for(var i = 0; i < this.data.length; i++) 22 ++num[this.data[i].j]; // 求矩阵中每一列含非零元个数 23 // 求第col列中第一个非零元在b.data中的序号 24 var cpot = [0]; 25 for(col = 1; col < this.nu; col++) 26 // 上一列之前的序号+上一列的非零元个数 = 该列的序号 27 cpot[col] = cpot[col - 1] + num[col - 1]; 28 for(var p = 0; p < this.data.length; p++){ 29 col = this.data[p].j; 30 var q = cpot[col]; 31 t.data[q] = new Triple(this.data[p].j, this.data[p].i, this.data[p].e); 32 // 给该列的序号+1，用作相同列数的情况 33 ++cpot[col]; 34 } 35 } 36 37 return t; 38 }
三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。
然而，若需按行号存取某一行的非零元，则从头开始进行查找。
行逻辑链接的顺序表
为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。
为此可将快速转置矩阵的算法中创建的，指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。
称这种“带行链接信息”的三元组表为行逻辑链接的顺序表
设有两个稀疏矩阵A=(aij)m*n ，B=(bij)n*p ，其存储结构采用行逻辑链接的三元组顺序表。求稀疏矩阵的乘法：
1 function RLSMatrix(mu, nu){ 2 TSMatrix.apply(this, arguments); 3 this.rpos = [0]; 4 } 5 RLSMatrix.MAXSIZE = 100; 6 RLSMatrix.prototype = { 7 constructor: RLSMatrix, 8 __proto__: TSMatrix.prototype, 9 // todo 10 /** 11 * 求矩阵乘积Q = M * N，采用行逻辑链接存储表示 12 * @param nMatrix 13 * @returns {RLSMatrix} 14 */ 15 multSMatrix: function(nMatrix){ 16 if(this.nu !== nMatrix.mu) throw Error(‘nu is not equivalent to mu‘); 17 18 // 初始化Q 19 var qMatrix = new RLSMatrix(this.mu, nMatrix.nu); 20 // Q是非零矩阵 21 if(this.data.length * nMatrix.data.length !== 0){ 22 // 处理M的每一行 23 for(var arow = 0; arow < this.mu; arow++){ 24 // 当前行各元素累加器清零 25 var ctemp = []; 26 qMatrix.rpos[arow] = qMatrix.data.length + 1; 27 var tp, ccol; 28 29 if(arow < this.mu) 30 tp = this.rpos[arow + 1]; 31 else 32 tp = this.data.length + 1; 33 34 //对当前行中每一个非零元找到对应元在N中的行号 35 for(var p = this.rpos[arow]; p < tp; p++){ 36 var brow = this.data[p].j; 37 var t; 38 if(brow < nMatrix.mu) 39 t = nMatrix.rpos[brow + 1]; 40 else 41 t = nMatrix.data.length + 1; 42 43 for(var q = nMatrix.rpos[brow]; q < t; q++){ 44 // 乘积元素在Q中的序号 45 ccol = nMatrix.data[q].j; 46 ctemp[ccol] = (ctemp[ccol] || 0) + this.data[p].e * nMatrix.data[q].e; 47 } 48 } 49 50 // 压缩存储该行非零元 51 for(ccol = 1; ccol < qMatrix.nu; ccol++){ 52 if(ctemp[ccol]){ 53 if(++qMatrix.data.length > RLSMatrix.MAXSIZE) throw Error(‘overflow‘); 54 qMatrix.data[qMatrix.data.length - 1] = new Triple(arow, ccol, ctemp[ccol]); 55 } 56 } 57 } 58 } 59 60 return qMatrix; 61 }, 62 _calcPos: function clcPos(){ 63 var num = []; 64 for(var col = 0; col < this.nu; col++) 65 num[col] = 0; 66 for(var i = 0; i < this.data.length; i++) 67 ++num[this.data[i].j]; // 求矩阵中每一列含非零元个数 68 // 求第col列中第一个非零元在b.data中的序号 69 for(col = 1; col < this.nu; col++) 70 // 上一列之前的序号+上一列的非零元个数 = 该列的序号 71 this.rpos[col] = this.rpos[col - 1] + num[col - 1]; 72 } 73 };
所有代码：
1 /** 2 * 系数矩阵的三元组顺序表存储表示 3 */ 4 5 6 function Triple(i, j, elem) { 7 // 该非零元的行下标和列下标 8 this.i = i || 0; 9 this.j = j || 0; 10 this.e = elem || null; 11 } 12 13 function TSMatrix(mu, nu) { 14 // 非零元三元组表 15 this.data =http://www.mamicode.com/ []; 16 // 矩阵的行数，列数 17 this.mu = mu || 0; 18 this.nu = nu || 0; 19 } 20 TSMatrix.prototype = { 21 constructor: TSMatrix, 22 addTriple: function (triple) { 23 if (triple instanceof Triple) { 24 if(triple.i >= this.mu) 25 this.mu = triple.i + 1; 26 if(triple.j >= this.nu) 27 this.nu = triple.j + 1; 28 29 this.data.push(triple); 30 return true; 31 } 32 return false; 33 }, 34 // 采用三元组表存储表示，求稀疏矩阵的转置矩阵t 35 // 按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置 36 transposeSMatrix: function () { 37 var t = new TSMatrix(); 38 t.mu = this.nu; 39 t.nu = this.mu; 40 41 if (this.data.length) { 42 var q = 0; 43 for (var col = 0; col < this.nu; col++) { 44 for (var p = 0; p < this.data.length; p++) { 45 if (this.data[p].j === col) 46 t.data[q++] = new Triple(this.data[p].j, this.data[p].i, this.data[p].e); 47 } 48 } 49 } 50 51 return t; 52 }, 53 // 采用三元组表存储表示，求稀疏矩阵的转置矩阵t 54 /* 55 按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。 56 如果能预先确定矩阵M中每一列（即T中每一行）的第一个非零元在b.data中应有的位置， 57 那么在对a.data中的三元组依次做转置时，便可直接放到b.data中恰当的位置上去。 58 为了其额定这些位置，在转置前，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data中应有的位置。 59 在此，需要设num和cpot两个变量。num[col]表示矩阵M中第col列中非零元的个数， 60 cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。显然有： 61 cpot[0] = 1; 62 cpot[col] = cpot[col - 1] + num[col - 1] 2 <= col <= a.nu 63 */ 64 fastTransposeSMatrix: function(){ 65 var t = new TSMatrix(); 66 t.mu = this.nu; 67 t.nu = this.mu; 68 69 if(this.data.length){ 70 var num = []; 71 for(var col = 0; col < this.nu; col++) 72 num[col] = 0; 73 for(var i = 0; i < this.data.length; i++) 74 ++num[this.data[i].j]; // 求矩阵中每一列含非零元个数 75 // 求第col列中第一个非零元在b.data中的序号 76 var cpot = [0]; 77 for(col = 1; col < this.nu; col++) 78 // 上一列之前的序号+上一列的非零元个数 = 该列的序号 79 cpot[col] = cpot[col - 1] + num[col - 1]; 80 for(var p = 0; p < this.data.length; p++){ 81 col = this.data[p].j; 82 var q = cpot[col]; 83 t.data[q] = new Triple(this.data[p].j, this.data[p].i, this.data[p].e); 84 // 给该列的序号+1，用作相同列数的情况 85 ++cpot[col]; 86 } 87 } 88 89 return t; 90 } 91 }; 92 93 var a1 = new Triple(1, 2, 12); 94 var a2 = new Triple(1, 3, 9); 95 var a3 = new Triple(3, 1, -3); 96 var a4 = new Triple(3, 6, 14); 97 var a5 = new Triple(4, 3, 24); 98 var a6 = new Triple(5, 2, 18); 99 var a7 = new Triple(6, 1, 15); 100 var a8 = new Triple(6, 4, -7); 101 102 var matrix = new TSMatrix(); 103 matrix.addTriple(a1); 104 matrix.addTriple(a2); 105 matrix.addTriple(a3); 106 matrix.addTriple(a4); 107 matrix.addTriple(a5); 108 matrix.addTriple(a6); 109 matrix.addTriple(a7); 110 matrix.addTriple(a8); 111 112 console.log(matrix.transposeSMatrix()); 113 console.log(matrix.fastTransposeSMatrix()); 114 115 /* 116 三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。 117 然而，若需按行号存取某一行的非零元，则从头开始进行查找。 118 */ 119 120 /** 121 * 行逻辑链接的顺序表 122 * 123 * 为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。 124 * 为此可将快速转置矩阵的算法中创建的，指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。 125 * 称这种“带行链接信息”的三元组表为行逻辑链接的顺序表 126 */ 127 128 function RLSMatrix(mu, nu){ 129 TSMatrix.apply(this, arguments); 130 this.rpos = [0]; 131 } 132 RLSMatrix.MAXSIZE = 100; 133 RLSMatrix.prototype = { 134 constructor: RLSMatrix, 135 __proto__: TSMatrix.prototype, 136 // todo 137 /** 138 * 求矩阵乘积Q = M * N，采用行逻辑链接存储表示 139 * @param nMatrix 140 * @returns {RLSMatrix} 141 */ 142 multSMatrix: function(nMatrix){ 143 if(this.nu !== nMatrix.mu) throw Error(‘nu is not equivalent to mu‘); 144 145 // 初始化Q 146 var qMatrix = new RLSMatrix(this.mu, nMatrix.nu); 147 // Q是非零矩阵 148 if(this.data.length * nMatrix.data.length !== 0){ 149 // 处理M的每一行 150 for(var arow = 0; arow < this.mu; arow++){ 151 // 当前行各元素累加器清零 152 var ctemp = []; 153 qMatrix.rpos[arow] = qMatrix.data.length + 1; 154 var tp, ccol; 155 156 if(arow < this.mu) 157 tp = this.rpos[arow + 1]; 158 else 159 tp = this.data.length + 1; 160 161 //对当前行中每一个非零元找到对应元在N中的行号 162 for(var p = this.rpos[arow]; p < tp; p++){ 163 var brow = this.data[p].j; 164 var t; 165 if(brow < nMatrix.mu) 166 t = nMatrix.rpos[brow + 1]; 167 else 168 t = nMatrix.data.length + 1; 169 170 for(var q = nMatrix.rpos[brow]; q < t; q++){ 171 // 乘积元素在Q中的序号 172 ccol = nMatrix.data[q].j; 173 ctemp[ccol] = (ctemp[ccol] || 0) + this.data[p].e * nMatrix.data[q].e; 174 } 175 } 176 177 // 压缩存储该行非零元 178 for(ccol = 1; ccol < qMatrix.nu; ccol++){ 179 if(ctemp[ccol]){ 180 if(++qMatrix.data.length > RLSMatrix.MAXSIZE) throw Error(‘overflow‘); 181 qMatrix.data[qMatrix.data.length - 1] = new Triple(arow, ccol, ctemp[ccol]); 182 } 183 } 184 } 185 } 186 187 return qMatrix; 188 }, 189 _calcPos: function clcPos(){ 190 var num = []; 191 for(var col = 0; col < this.nu; col++) 192 num[col] = 0; 193 for(var i = 0; i < this.data.length; i++) 194 ++num[this.data[i].j]; // 求矩阵中每一列含非零元个数 195 // 求第col列中第一个非零元在b.data中的序号 196 for(col = 1; col < this.nu; col++) 197 // 上一列之前的序号+上一列的非零元个数 = 该列的序号 198 this.rpos[col] = this.rpos[col - 1] + num[col - 1]; 199 } 200 }; 201 202 var b1 = new Triple(1, 1, 3); 203 var b2 = new Triple(1, 3, 5); 204 var b3 = new Triple(2, 2, -1); 205 var b4 = new Triple(3, 1, 2); 206 207 var t1 = new RLSMatrix(); 208 t1.addTriple(b1); 209 t1.addTriple(b2); 210 t1.addTriple(b3); 211 t1.addTriple(b4); 212 t1._calcPos(); 213 214 var c1 = new Triple(1, 2, 2); 215 var c2 = new Triple(2, 1, 1); 216 var c3 = new Triple(3, 1, -2); 217 var c4 = new Triple(3, 2, 4); 218 219 var t2 = new RLSMatrix(); 220 t2.addTriple(c1); 221 t2.addTriple(c2); 222 t2.addTriple(c3); 223 t2.addTriple(c4); 224 t2._calcPos(); 225 226 t1.multSMatrix(t2);
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。