JS实现数据结构:稀疏矩阵的十字链表存储表示

  1 /** 
  2  * 十字链表 
  3  * 
  4  * 当矩阵的非零个数和位置在操作过程中变化大时，就不宜采用顺序存储结构来表示三元组的线性表。例如，在作“将矩阵B加到矩阵A上”的操作时，由于非零元的插入或删除将会引起A.data中元素的移动。为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。 
  5  * 
  6  * 在链表中，每个非陵园可用一个含5个域的结点表示，其中i，j和e这3个域分别表示该非零元所在的行，列和非零元的值，向右域right用以链接同一行中下一个非零元，向下域down用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性表，同一列中的非零元通常down域链接成一个线性链表，每一个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表。 
  7  * 
  8  * 可用两个分别存储行链表的头指针和列链表的头指针的一维数组来表示。 
  9  */ 
 10  
 11     // 稀疏矩阵的十字链表存储表示 
 12  
 13 function OLNode(i, j, e) { 
 14     // 该非零元的行和列下标 
 15     this.i = i || 0; 
 16     this.j = j || 0; 
 17     this.e = e; 
 18     // 该非零元所在行表和列表的后继链域 
 19     this.right = null;  // type: OLNode 
 20     this.down = null;   // type: OLNode 
 21 } 
 22  
 23 function CrossList() { 
 24     // 行和列链表头指针向量基址由CreateSMatrix分配 
 25     this.rhead = []; 
 26     this.chead = []; 
 27     // 稀疏矩阵的行数，列数 
 28     this.mu = 0; 
 29     this.nu = 0; 
 30     this.tu = 0; 
 31 } 
 32 /** 
 33  * 矩阵初始化 
 34  * @param m 
 35  * @param n 
 36  * @param t 
 37  * @param {Array} list 二维数组，每行的元素分别是[i, j, e] 
 38  */ 
 39 CrossList.prototype.createSMatrix = function (m, n, t, list) { 
 40     this.mu = m; 
 41     this.nu = n; 
 42     this.tu = t; 
 43  
 44     for (var row = 0; row < list.length; row++) { 
 45         var p = {}; 
 46         OLNode.apply(p, list[row]); 
 47         var i = list[row][0]; 
 48         var j = list[row][1]; 
 49         var q; 
 50  
 51         if (this.rhead[i] == null || this.rhead[i].j > j) { 
 52             p.right = this.rhead[i]; 
 53             this.rhead[i] = p; 
 54         } else { 
 55             // 查询在行表中的插入位置 
 56             for (q = this.rhead[i]; q.right && q.right.j < j; q = q.right); 
 57             p.right = q.right; 
 58             q.right = p; 
 59         } 
 60  
 61         if (this.chead[j] == null || this.chead[j].i > i) { 
 62             p.down = this.chead[j]; 
 63             this.chead[j] = p; 
 64         } else { 
 65             for (q = this.chead[j]; q.down && q.down.i < i; q = q.down); 
 66             p.down = q.down; 
 67             q.down = p; 
 68         } 
 69     } 
 70 }; 
 71  
 72 // 矩阵相加 
 73 CrossList.prototype.addMatrix = function (crossList) { 
 74     var hl = []; 
 75     //hl初始化 
 76     for (var j = 0; j <= this.nu; j++) 
 77         hl[j] = this.chead[j]; 
 78  
 79     for (var i = 0; i <= this.mu; i++) { 
 80         //pa和pb指向每一行的第一个非0元结点，直至最后一行 
 81         var pa = this.rhead[i]; 
 82         var pb = crossList.rhead[i]; 
 83         var pre = null; 
 84  
 85         //处理B的一行，直至本行中无非0元素的结点 
 86         while (pb) { 
 87             var p, q; 
 88             // 新插入一个结点到pa的左侧 
 89             if (!pa || pa.j > pb.j) { 
 90                 p = new OLNode(pb.i, pb.j, pb.e); 
 91  
 92                 //行表的指针变化 
 93                 if (!pre) this.rhead[p.i] = p; 
 94                 else pre.right = p; 
 95  
 96                 p.right = pa; 
 97                 pre = p; 
 98  
 99                 //列表的指针变化 
100                 if (hl[p.j]) { 
101                     // 从hl[p.j]开始找到新结点在同一列中的前驱结点，并让hl[p.j]指向它 
102                     for (q = hl[p.j]; q && q.i < p.i;q = q.down) 
103                         hl[p.j] = q; 
104                 } 
105  
106                 //在列表中插入新结点，根据行数判断插入前面还是后面 
107                 if (!this.chead[p.j] || this.chead[p.j].i > p.i) { 
108                     p.down = this.chead[p.j]; 
109                     this.chead[p.j] = p; 
110                 } else { 
111                     p.down = hl[p.j].down; 
112                     hl[p.j].down = p; 
113                 } 
114  
115                 hl[p.j] = p; 
116                 pb = pb.right; 
117             } else if (pa.j < pb.j) { 
118                 pre = pa; 
119                 pa = pa.right; 
120             } else { 
121                 //当pa.j === pb.j时，将B中当前结点的值加到A中当前结点上 
122                 pa.e += pb.e; 
123  
124                 //当pa.e === 0时，删除该结点 
125                 if (pa.e === 0) { 
126                     // 若无前驱结点，将第一个非0元结点置为当前结点的后继结点， 
127                     // 否则前驱结点的后继结点为当前结点的后继结点 
128                     if (!pre) this.rhead[pa.i] = pa.right; 
129                     else pre.right = pa.right; 
130  
131                     p = pa; 
132                     pa = pa.right; 
133  
134                     //列表的指针变化 
135                     if (hl[p.j]) { 
136                         //从hl[p.j]开始找到新结点在同一列中的前驱结点，并让hl[p.j]指向它 
137                         for (q = hl[p.j]; q && q.i < p.i; q = q.down) 
138                             hl[p.j] = q; 
139                     } 
140  
141                     if (this.chead[p.j] == p) 
142                         this.chead[p.j] = hl[p.j] = p.down; 
143                     else 
144                         hl[p.j].down = p.down; 
145                 } 
146  
147                 pb = pb.right; 
148             } 
149         } 
150     } 
151 }; 
152  
153 var lists = [ 
154     [1, 4, 5], 
155     [2, 2, -1], 
156     [1, 1, 3], 
157     [3, 1, 2] 
158 ]; 
159 var a = new CrossList(); 
160 a.createSMatrix(4, 4, 4, lists); 
161 console.log(a); 
162  
163 var lists2 = [ 
164     [1, 4, -5], 
165     [2, 3, 1], 
166     [1, 1, 3], 
167     [3, 2, 2] 
168 ]; 
169 var b = new CrossList(); 
170 b.createSMatrix(4, 4, 4, lists2); 
171 console.log(b); 
172  
173 a.addMatrix(b); 
174 console.log(a);