Skip to main content
 首页 » 编程设计

JS实现数据结构:稀疏矩阵之三元组线性表表示

2022年07月16日28傻小

稀疏矩阵(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 = []; 
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 = []; 
 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);

本文参考链接:https://www.cnblogs.com/webFrontDev/p/3762951.html