本文實例講述了Java數據結構之稀疏矩陣定義與用法。分享給大家供大家參考，具體如下：
稀疏矩陣非零元素的三元組類:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
package com.clarck.datastructure.matrix;/** * 稀疏矩陣的壓縮存儲 * * 稀疏矩陣非零元素的三元組類 * * @author clarck * */public class Triple implements Comparable<Triple> { // 行號，列號， 元素值，默認訪問權限 int row, colum, value; public Triple(int row, int colum, int value) { if (row < 0 || colum < 0) { throw new IllegalArgumentException("稀疏矩陣元素三元組的行/列序號非正數"); } this.row = row; this.colum = colum; this.value = value; } /** * 拷貝構造方法，復制一個三元組 * * @param elem */ public Triple(Triple elem) { this(elem.row, elem.colum, elem.value); } @Override public String toString() { return "(" + row + ", " + colum + ", " + value + ")"; } /** * 兩個三元組是否相等，比較位置和元素值 */ public boolean equals(Object obj) { if (!(obj instanceof Triple)) return false; Triple elem = (Triple) obj; return this.row == elem.row && this.colum == elem.colum && this.value == elem.value; } /** * 根據三元組位置比較兩個三元組的大小，與元素值無關，約定三元組排序次序 */ @Override public int compareTo(Triple elem) { //當前三元組對象小 if (this.row < elem.row || this.row == elem.row && this.colum < elem.colum) return -1; //相等，與equals方法含義不同 if (this.row == elem.row && this.colum == elem.colum) return 0; //當前三元組對象大 return 1; } /** * 加法， +=運算符作用 * @param term */ public void add(Triple term) { if (this.compareTo(term) == 0) this.value += term.value; else throw new IllegalArgumentException("兩項的指數不同，不能相加"); } /** * 約定刪除元素 * * @return */ public boolean removable() { //不存儲為0的元素 return this.value == 0; } /** * 返回對稱位置矩陣元素的三元組 * @return */ public Triple toSymmetry() { return new Triple(this.colum, this.row, this.value); } /** * 加法運算，重載運算符+ * @return */ public Triple plus(Triple term) { Triple tmp = new Triple(this); tmp.add(term); return tmp; }} |
三元組順序存儲的稀疏矩陣類:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
|
package com.clarck.datastructure.matrix;import com.clarck.datastructure.linear.SeqList;/** * 稀疏矩陣的壓縮存儲 * * 稀疏矩陣三元組順序表 * * 三元組順序存儲的稀疏矩陣類 * * @author clarck * */public class SeqSparseMatrix { // 矩陣行數、列數 private int rows, columns; // 稀疏矩陣三元組順序表 private SeqList<Triple> list; /** * 構造rows行，colums列零矩陣 * * @param rows * @param columns */ public SeqSparseMatrix(int rows, int columns) { if (rows <= 0 || columns <= 0) throw new IllegalArgumentException("矩陣行數或列數為非正數"); this.rows = rows; this.columns = columns; // 構造空順序表，執行SeqList()構造方法 this.list = new SeqList<Triple>(); } public SeqSparseMatrix(int rows, int columns, Triple[] elems) { this(rows, columns); // 按行主序插入一個元素的三元組 for (int i = 0; i < elems.length; i++) this.set(elems[i]); } /** * 返回矩陣第i行第j列元素，排序順序表的順序查找算法，O(n) * * @param i * @param j * @return */ public int get(int i, int j) { if (i < 0 || i >= rows || j < 0 || j >= columns) throw new IndexOutOfBoundsException("矩陣元素的行或列序號越界"); Triple item = new Triple(i, j, 0); int k = 0; Triple elem = this.list.get(k); // 在排序順序表list中順序查找item對象 while (k < this.list.length() && item.compareTo(elem) >= 0) { // 只比較三元組元素位置，即elem.row == i && elem.column == j if (item.compareTo(elem) == 0) return elem.value; // 查找到(i, j), 返回矩陣元素 k++; elem = this.list.get(k); } return 0; } /** * 以三元組設置矩陣元素 * * @param elem */ public void set(Triple elem) { this.set(elem.row, elem.colum, elem.value); } /** * 設置矩陣第row行第column列的元素值為value，按行主序在排序順序表list中更改或插入一個元素的三元組， O(n) * * @param row * @param column * @param value */ public void set(int row, int column, int value) { // 不存儲值為0元素 if (value == 0) return; if (row >= this.rows || column >= this.columns) throw new IllegalArgumentException("三元組的行或列序號越界"); Triple elem = new Triple(row, column, value); int i = 0; // 在排序的三元組順序表中查找elem對象，或更改或插入 while (i < this.list.length()) { Triple item = this.list.get(i); // 若elem存在，則更改改位置矩陣元素 if (elem.compareTo(item) == 0) { // 設置順序表第i個元素為elem this.list.set(i, elem); return; } // elem 較大時向后走 if (elem.compareTo(item) >= 0) i++; else break; } this.list.insert(i, elem); } @Override public String toString() { String str = "三元組順序表：" + this.list.toString() + "\n"; str += "稀疏矩陣" + this.getClass().getSimpleName() + "(" + rows + " * " + columns + "): \n"; int k = 0; // 返回第k個元素，若k指定序號無效則返回null Triple elem = this.list.get(k++); for (int i = 0; i < this.rows; i++) { for (int j = 0; j < this.columns; j++) if (elem != null && i == elem.row && j == elem.colum) { str += String.format("%4d", elem.value); elem = this.list.get(k++); } else { str += String.format("%4d", 0); } str += "\n"; } return str; } /** * 返回當前矩陣與smat相加的矩陣， smatc=this+smat,不改變當前矩陣，算法同兩個多項式相加 * * @param smat * @return */ public SeqSparseMatrix plus(SeqSparseMatrix smat) { if (this.rows != smat.rows || this.columns != smat.columns) throw new IllegalArgumentException("兩個矩陣階數不同，不能相加"); // 構造rows*columns零矩陣 SeqSparseMatrix smatc = new SeqSparseMatrix(this.rows, this.columns); int i = 0, j = 0; // 分別遍歷兩個矩陣的順序表 while (i < this.list.length() && j < smat.list.length()) { Triple elema = this.list.get(i); Triple elemb = smat.list.get(j); // 若兩個三元組表示相同位置的矩陣元素，則對應元素值相加 if (elema.compareTo(elemb) == 0) { // 相加結果不為零，則新建元素 if (elema.value + elemb.value != 0) smatc.list.append(new Triple(elema.row, elema.colum, elema.value + elemb.value)); i++; j++; } else if (elema.compareTo(elemb) < 0) { // 將較小三元組復制添加到smatc順序表最后 // 復制elema元素執行Triple拷貝構造方法 smatc.list.append(new Triple(elema)); i++; } else { smatc.list.append(new Triple(elemb)); j++; } } // 將當前矩陣順序表的剩余三元組復制添加到smatc順序表最后 while (i < this.list.length()) smatc.list.append(new Triple(this.list.get(i++))); // 將smat中剩余三元組復制添加到smatc順序表最后 while (j < smatc.list.length()) { Triple elem = smat.list.get(j++); if (elem != null) { smatc.list.append(new Triple(elem)); } } return smatc; } /** * 當前矩陣與smat矩陣相加，this+=smat, 改變當前矩陣，算法同兩個多項式相加 * * @param smat */ public void add(SeqSparseMatrix smat) { if (this.rows != smat.rows || this.columns != smat.columns) throw new IllegalArgumentException("兩個矩陣階數不同，不能相加"); int i = 0, j = 0; // 將mat的各三元組依次插入(或相加)到當前矩陣三元組順序表中 while (i < this.list.length() && j < smat.list.length()) { Triple elema = this.list.get(i); Triple elemb = smat.list.get(j); // 若兩個三元組表示相同位置的矩陣元素，則對應元素值相加 if (elema.compareTo(elemb) == 0) { // 相加結果不為0,則新建元素 if (elema.value + elemb.value != 0) this.list.set(i++, new Triple(elema.row, elema.colum, elema.value + elemb.value)); else this.list.remove(i); j++; } else if (elema.compareTo(elemb) < 0) { // 繼續向后尋找elemb元素的插入元素 i++; } else { // 復制elemb元素插入作為this.list的第i個元素 this.list.insert(i++, new Triple(elemb)); j++; } } // 將mat中剩余三元組依次復制插入當前矩陣三元組順序表中 while (j < smat.list.length()) { this.list.append(new Triple(smat.list.get(j++))); } } // 深拷貝 public SeqSparseMatrix(SeqSparseMatrix smat) { this(smat.rows, smat.columns); // 創建空順序表，默認容量 this.list = new SeqList<Triple>(); // 復制smat中所有三元組對象 for (int i = 0; i < smat.list.length(); i++) this.list.append(new Triple(smat.list.get(i))); } /** * 比較兩個矩陣是否相等 */ public boolean equals(Object obj) { if (this == obj) return true; if (!(obj instanceof SeqSparseMatrix)) return false; SeqSparseMatrix smat = (SeqSparseMatrix) obj; return this.rows == smat.rows && this.columns == smat.columns && this.list.equals(smat.list); } /** * 返回轉置矩陣 * @return */ public SeqSparseMatrix transpose() { //構造零矩陣，指定行數和列數 SeqSparseMatrix trans = new SeqSparseMatrix(columns, rows); for (int i = 0; i < this.list.length(); i++) { //插入矩陣對稱位置元素的三元組 trans.set(this.list.get(i).toSymmetry()); } return trans; }} |
測試類：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
package com.clarck.datastructure.matrix;/** * 稀疏矩陣的壓縮存儲 * * 稀疏矩陣三元組順序表 * * 三元組順序表表示的稀疏矩陣及其加法運算 * * @author clarck * */public class SeqSparseMatrix_test { public static void main(String args[]) { Triple[] elemsa = { new Triple(0, 2, 11), new Triple(0, 4, 17), new Triple(1, 1, 20), new Triple(3, 0, 19), new Triple(3, 5, 28), new Triple(4, 4, 50) }; SeqSparseMatrix smata = new SeqSparseMatrix(5, 6, elemsa); System.out.print("A " + smata.toString()); Triple[] elemsb = { new Triple(0, 2, -11), new Triple(0, 4, -17), new Triple(2, 3, 51), new Triple(3, 0, 10), new Triple(4, 5, 99), new Triple(1, 1, 0) }; SeqSparseMatrix smatb = new SeqSparseMatrix(5,6,elemsb); System.out.print("B " + smatb.toString()); SeqSparseMatrix smatc = smata.plus(smatb); System.out.print("C=A+B"+smatc.toString()); System.out.println(); smata.add(smatb); System.out.print("A+=B" + smata.toString()); System.out.println("C.equals(A)?" + smatc.equals(smata)); SeqSparseMatrix smatd = new SeqSparseMatrix(smatb); smatb.set(0,2,1); System.out.print("B " + smatb.toString()); System.out.print("D " + smatd.toString()); System.out.println("A轉置" + smata.transpose().toString()); }} |
運行結果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
A 三元組順序表：((0, 2, 11), (0, 4, 17), (1, 1, 20), (3, 0, 19), (3, 5, 28), (4, 4, 50))稀疏矩陣SeqSparseMatrix(5 * 6): 0 0 11 0 17 0 0 20 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 28 0 0 0 0 50 0B 三元組順序表：((0, 2, -11), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))稀疏矩陣SeqSparseMatrix(5 * 6): 0 0 -11 0 -17 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99C=A+B三元組順序表：((1, 1, 20), (2, 3, 51), (3, 0, 29), (3, 5, 28), (4, 4, 50), (4, 5, 99))稀疏矩陣SeqSparseMatrix(5 * 6): 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99A+=B三元組順序表：((1, 1, 20), (2, 3, 51), (3, 0, 29), (3, 5, 28), (4, 4, 50), (4, 5, 99))稀疏矩陣SeqSparseMatrix(5 * 6): 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 28 0 0 0 0 50 99C.equals(A)?trueB 三元組順序表：((0, 2, 1), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))稀疏矩陣SeqSparseMatrix(5 * 6): 0 0 1 0 -17 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99D 三元組順序表：((0, 2, -11), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))稀疏矩陣SeqSparseMatrix(5 * 6): 0 0 -11 0 -17 0 0 0 0 0 0 0 0 0 0 51 0 0 10 0 0 0 0 0 0 0 0 0 0 99A轉置三元組順序表：((0, 3, 29), (1, 1, 20), (3, 2, 51), (4, 4, 50), (5, 3, 28), (5, 4, 99))稀疏矩陣SeqSparseMatrix(6 * 5): 0 0 0 29 0 0 20 0 0 0 0 0 0 0 0 0 0 51 0 0 0 0 0 0 50 0 0 0 28 99 |
希望本文所述對大家java程序設計有所幫助。
原文鏈接：https://www.cnblogs.com/tanlon/p/4164295.html
