给出cpp解决稀疏矩阵问题的代码
时间: 2023-06-02 12:05:24 浏览: 67
以下是一个用C++解决稀疏矩阵问题的示例代码:
```
#include <iostream>
using namespace std;
class SparseMatrix {
private:
int row, column, count;
int *rpos, *cpos, *values;
public:
SparseMatrix(int r, int c, int cnt) : row(r), column(c), count(cnt) {
rpos = new int[count];
cpos = new int[count];
values = new int[count];
}
~SparseMatrix() {
delete[] rpos;
delete[] cpos;
delete[] values;
}
void Set(int r, int c, int v) {
if (r < 0 || r >= row) return;
if (c < 0 || c >= column) return;
int i = 0, j = count - 1, k = -1;
while (i <= j) {
int mid = (i + j) / 2;
if (rpos[mid] == r && cpos[mid] == c) {
k = mid; break;
}
if (rpos[mid] < r || (rpos[mid] == r && cpos[mid] < c)) {
i = mid + 1;
} else {
j = mid - 1;
}
}
if (k == -1 && v == 0) return;
if (k != -1 && v == 0) {
for (int i = k; i < count - 1; i++) {
rpos[i] = rpos[i + 1];
cpos[i] = cpos[i + 1];
values[i] = values[i + 1];
}
count--;
return;
}
if (k == -1) {
if (count == 0) {
rpos[0] = r;
cpos[0] = c;
values[0] = v;
count = 1;
} else {
int p = count;
for (int i = 0; i < count; i++) {
if (rpos[i] > r || (rpos[i] == r && cpos[i] > c)) {
p = i; break;
}
}
for (int i = count; i > p; i--) {
rpos[i] = rpos[i - 1];
cpos[i] = cpos[i - 1];
values[i] = values[i - 1];
}
rpos[p] = r;
cpos[p] = c;
values[p] = v;
count++;
}
} else {
values[k] = v;
}
}
int Get(int r, int c) {
if (r < 0 || r >= row) return 0;
if (c < 0 || c >= column) return 0;
int i = 0, j = count - 1;
while (i <= j) {
int mid = (i + j) / 2;
if (rpos[mid] == r && cpos[mid] == c) {
return values[mid];
}
if (rpos[mid] < r || (rpos[mid] == r && cpos[mid] < c)) {
i = mid + 1;
} else {
j = mid - 1;
}
}
return 0;
}
};
int main() {
SparseMatrix m(3, 4, 4);
m.Set(0, 1, 2);
m.Set(1, 2, 3);
m.Set(2, 3, 4);
m.Set(0, 1, 0);
m.Set(1, 2, 0);
m.Set(2, 3, 0);
cout << m.Get(0, 0) << endl;
cout << m.Get(0, 1) << endl;
cout << m.Get(1, 2) << endl;
cout << m.Get(2, 3) << endl;
return 0;
}
```
示例代码中定义了一个 SparseMatrix 类用于表示稀疏矩阵,通过 Set() 方法设置矩阵元素的值,通过 Get() 方法获取矩阵元素的值,主函数中给出了一个示例用法。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)