本文实例讲述了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 0
B 三元组顺序表：((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 99
C=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 99
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 99
C.equals(A)?true
B 三元组顺序表：((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 99
D 三元组顺序表：((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 99
A转置三元组顺序表：((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