📄 sparsematrix.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>稀疏矩阵</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 稀疏矩阵</a></h1>
<h2>说明</h2>
如果在矩阵中，多数的元素并没有资料，称此矩阵为稀疏矩阵（sparse
matrix），由于矩阵在程式中常使用二维阵列表示，二维阵列的大小与使用的记忆体空间成正比，如果多数的元素没有资料，则会造成记忆体空间的浪费，为
此，必须设计稀疏矩阵的阵列储存方式，利用较少的记忆体空间储存完整的矩阵资讯。<br>
<h2>解法</h2>
在这边所介绍的方法较为简单，阵列只储存矩阵的行数、列数与有资料的索引位置及其值，在需要使用矩阵资料时，再透过程式运算加以还原，例如若矩阵资料如下 ，其中0表示矩阵中该位置没有资料：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">0 0 0 0 0 0 </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">0 3 0 0 0 0 </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">0 0 0 6 0 0 </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">0 0 9 0 0 0 </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">0 0 0 0 12 0</span><br>
</div>
<br>
这个矩阵是5X6矩阵，非零元素有4个，您要使用的阵列第一列记录其列数、行数与非零元素个数：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">5 6 4 </span><br>
</div>
<br>
阵列的第二列起，记录其位置的列索引、行索引与储存值：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">1 1 3 </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">2 3 6 </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">3 2 9 </span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;">4 4 12 </span><br>
</div>
<br>
所以原本要用30个元素储存的矩阵资讯，现在只使用了15个元素来储存，节省了不少记忆体的使用。 <br>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br><br>int main(void) { <br> int num[5][3] = {{5, 6, 4}, <br> {1, 1, 3}, <br> {2, 3, 6}, <br> {3, 2, 9}, <br> {4, 4, 12}}; <br> int i, j, k = 1; <br><br> printf("sparse matrix：\n"); <br> for(i = 0; i < 5; i++) { <br> for(j = 0; j < 3; j++) { <br> printf("%4d", num[i][j]); <br> } <br> putchar('\n'); <br> } <br><br> printf("\nmatrix还原：\n"); <br> for(i = 0; i < num[0][0]; i++) { <br> for(j = 0; j < num[0][1]; j++) { <br> if(k < num[0][2] && <br> i == num[k][0] && j == num[k][1]) { <br> printf("%4d ", num[k][2]); <br> k++; <br> } <br> else <br> printf("%4d ", 0); <br> } <br> putchar('\n'); <br> } <br><br> return 0; <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class SparseMatrix {<br> public static int[][] restore(int[][] sparse) {<br> int row = sparse[0][0];<br> int column = sparse[0][1];<br> <br> int[][] array = new int[row][column];<br> <br> int k = 1;<br> for(int i = 0; i < row; i++) { <br> for(int j = 0; j < column; j++) { <br> if(k <= sparse[0][2] && <br> i == sparse[k][0] && j == sparse[k][1]) { <br> array[i][j] = sparse[k][2]; <br> k++; <br> } <br> else <br> array[i][j] = 0; <br> } <br> } <br> <br> return array;<br> }<br><br> public static void main(String[] args) {<br> int[][] sparse = {{5, 6, 4}, <br> {1, 1, 3}, <br> {2, 3, 6}, <br> {3, 2, 9}, <br> {4, 4, 12}};<br> <br> int[][] array = SparseMatrix.restore(sparse);<br> <br> for(int i = 0; i < array.length; i++) { <br> for(int j = 0; j < array[i].length; j++) { <br> System.out.print(array[i][j] + " ");<br> } <br> System.out.println();<br> } <br> }<br>}</pre>
<br>
<br>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -