稀疏矩阵(Sparse Matrix)的java实现
看看这里不像C坛这么热闹，过来给大家捧捧场。
下面是我过去做过的一个assignment，一共有4个class（其中一个inner class），请大家多指教：
[code:1:7319eaad99]Background
Very large two-dimensional arrays or matricies often arise in solving problems in areas as diverse as engineering and computer graphics. It is not uncommon for such matrices to have 50,000 rows and 50,000 columns. A tremendous amount of memory would be needed to store such matricies in the conventional manner. For example, if each element is of type float (4 bytes) then 10 GB would be required for the above example! Fortunately, these matricies are often sparse; that is, most elements are zero and only a very few elements are non-zero. To save memory, only the non-zero elements are stored. One way that this can be done is to represent the sparse matrix as a two-dimensional linked list of the non-zero elements.
有时候出于某种原因我们需要一个非常大的二维数组，但是这数组并不是经常满的，这样就很浪费内存，因此我们可以用稀疏矩阵来代替它，这稀疏矩阵就是用二维链表把非零的节点连起来。
[/code:1:7319eaad99]
小飞爱使申华 回复于：2003-08-06 23:57:29
class SparseMatrix & inner class Element:
[code:1:832192578e]import java.io.*;
/****************************************************************
This class provides functionality for storing, solving, and
managing sparce matrices. Only the non-zero elements are stored.
It represents the sparse matrix as a two-dimensional linked list
of the non-zero elements. The elements of Matrix are all of type
float.
****************************************************************/
public class SparseMatrix
{
// This class provides the list node for the linked list. with
// references to the next non-zero element in the same row and
// the next non-zero element in the same column.
class Element
{
private int row;
private int column;
private float value;
private Element right;
private Element down;
}
private Element[] rowHead;
private Element[] columnHead;
/*************************************************************
Create an m-by-n SparseMatrix with storing it in the linked
list.
@param m the number of rows in <code>this</code> Matrix.
@param n the number of columns in <code>this</code> Matrix.
**************************************************************/
public SparseMatrix (int m, int n) //constructor
{
if(m <= 0)
{
System.out.println("The rows of the matrix must be greater than zero.");
System.exit(1);
}
if(n <= 0)
{
System.out.println("The columns of the matrix must be greater than zero.");
System.exit(1);
}
rowHead = new Element[m];
columnHead = new Element[n];
}
/*************************************************************
Add the passed SparseMatrix to <code>this</code> SparseMatrix.
@param B the SparseMatrix to add to <code>this</code>
SparseMatrix.
@return a reference to a new SparseMatrix object that is equal
to the sum of <code>this</code> SparseMatrix and the passed one.
If the passed SparseMatrix is null or the number of rows and
columns of <code>this</code> SparseMatrix is not equal to the
passed one, null will be returned.
**************************************************************/
public SparseMatrix add (SparseMatrix B)
{
SparseMatrix C = null;
if (B != null && rowHead.length == B.rowHead.length && columnHead.length == B.columnHead.length)
{
C = new SparseMatrix(rowHead.length, columnHead.length);
SparseList[] scaleOne = new SparseList[rowHead.length * columnHead.length];
Element aNext, bNext, rowNext, newNode;
for (int i = 0; i < rowHead.length; i++)
{
if (rowHead[i] != null || B.rowHead[i] != null)
{
aNext = rowHead[i]; //trace Matrix this’ row linked list
bNext = B.rowHead[i]; //trace Matrix B’s row linked list
newNode = new Element(); //obtain node for new value
C.rowHead[i] = newNode;
do
{
if (aNext == null)
{
rowNext = bNext;
bNext = bNext.right;
} else if (bNext == null)
{
rowNext = aNext;
aNext = aNext.right;
} else
{
if (bNext.column < aNext.column)
{
rowNext = bNext;
bNext = bNext.right;
} else if (bNext.column > aNext.column)
{
rowNext = aNext;
aNext = aNext.right;
} else if (Math.abs(aNext.value + bNext.value) > 0.0001)
{
rowNext = new Element();
rowNext.row = aNext.row;
rowNext.column = aNext.column;
rowNext.value = aNext.value + bNext.value;
aNext = aNext.right;
bNext = bNext.right;
}else // at the same position && sum of the values = 0
{
aNext = aNext.right;
bNext = bNext.right;
continue;
}
}
newNode.row = rowNext.row;
newNode.column = rowNext.column;
newNode.value = rowNext.value;
C.insertColumn(newNode);
rowNext = rowNext.right;
if (aNext != null || bNext != null)
{
newNode.right = new Element();
newNode = newNode.right;
} else // the last node
{ newNode.right = null;
newNode.down = null;
}
}while (aNext != null || bNext != null);
}
}
}
return C;
}
/*************************************************************
Multiply the passed number to all elements in
<code>this</code> SparseMatrix.
@param k the number to multiply <code>this</code> SparseMatrix
by.
@return a reference to a new Matrix object that is equal to
the product of <code>this</code> SpaseMatrix and the passed
number.
**************************************************************/
public SparseMatrix scale (float k)
{
SparseMatrix C = new SparseMatrix(rowHead.length, columnHead.length);
Element newNode, rowNext;
if (k != 0.) // if k is equal to zero, no new node is added
{
for (int i = 0; i < rowHead.length; i++)
{
if (rowHead[i] != null)
{
rowNext = rowHead[i]; //trace this row linked list
newNode = new Element(); //obtain node for new value
C.rowHead[i] = newNode;
do
{
int rowNo = rowNext.row;
int columnNo = rowNext.column;
newNode.row = rowNo;
newNode.column = columnNo;
newNode.value = k * rowNext.value;
C.insertColumn(newNode);
rowNext = rowNext.right;
if (rowNext != null)
{
newNode.right = new Element();
newNode = newNode.right;
} else // the last node
{ newNode.right = null;
newNode.down = null;
}
}while (rowNext != null);
}
}
}
return C;
}
/*************************************************************
Return the maximum absolute row sum of <code>this</code>
SparseMatrix.
@return the infinity norm of <code>this</code> SparseMatrix.
**************************************************************/
public float norm ()
{
double max = 0.;
double sum;
Element newNode;
for (int i = 0; i < rowHead.length; i++)
{
sum = 0.;
// add the value in the same row list
for (newNode = rowHead[i]; newNode != null; newNode = newNode.right)
{
sum += Math.abs(newNode.value);
}
if (sum > max)
max = sum;
}
return (float)max;
}
/*************************************************************
Initialize <code>this</code> SparseMatrix with the values
from the passed array.
@param a the array to be initialized <code>this</code> SparseMatrix.
**************************************************************/
public void setMatrix (SparseList[] a)
{
for (int i = 0; i < rowHead.length; i++)
rowHead[i] = null;
for (int j = 0; j < columnHead.length; j++)
columnHead[j] = null;
Element newNode, rowPrevious, rowNext, columnPrevious, columnNext;
for (int i = 0; i < a.length; i++)
{
// test if this element is in this matrix and the element’s value is not equal to zero
if (a[i].getRow() < rowHead.length && a[i].getColumn() < columnHead.length && a[i].getValue() != 0)
{
int rowNo = a[i].getRow();
int columnNo = a[i].getColumn();
newNode = new Element(); //obtain node for new value
newNode.right = null;
newNode.down = null;
newNode.row = rowNo;
newNode.column = columnNo;
newNode.value = a[i].getValue();
// the later one will overwrite the former one if at the same position
if (rowHead[rowNo] != null && columnNo == rowHead[rowNo].column)
rowHead[rowNo].value = a[i].getValue();
else // no former one at the same position
insertRow(newNode);
insertColumn(newNode);
}
}
}
/*************************************************************
Display <code>this</code> SparseMatrix as a rectangular grid
of values on the screen. It prints all the elements in the
matrix, including the implicit zeros.
**************************************************************/
public void displayMatrix ()
{
int count;
Element newNode;
for (int i = 0; i < rowHead.length; i++)
{
count = 0; // count the number of the printed elements
for (newNode = rowHead[i]; newNode != null; newNode = newNode.right)
{
// print the 0’s before and between the nodes
for (int j = count; j < newNode.column; j++)
System.out.print("0.000 ");
System.out.print(newNode.value);
for (int j = 0; j < 9 - new Float(newNode.value).toString().length(); j++)
System.out.print(" ");
count = newNode.column + 1;
}
// print the 0’s after the last node or in the empty linked list.
for (int j = count; j < columnHead.length; j++)
System.out.print("0.000 ");
System.out.println();
}
System.out.println();
}
// insert to the row linked list
private void insertRow (Element node)
{
Element rowPrevious, rowNext;
int rowNo = node.row;
int columnNo = node.column;
// see if the node goes first in the list
if (rowHead[rowNo] == null || columnNo < rowHead[rowNo].column)
{
node.right = rowHead[rowNo];
rowHead[rowNo] = node;
} else // find place to link the node
{
rowPrevious = rowHead[rowNo];
rowNext = rowHead[rowNo].right;
while (rowNext != null && columnNo > rowNext.column)
{
rowPrevious = rowNext;
rowNext = rowNext.right;
}
// adjust links to complete insertion
rowPrevious.right = node;
node.right = rowNext;
}
}
// insert to the column linked list
private void insertColumn (Element node)
{
Element columnPrevious, columnNext;
int rowNo = node.row;
int columnNo = node.column;
// see if the node goes first in the list
if (columnHead[columnNo] == null || rowNo < columnHead[columnNo].row)
{
node.down = columnHead[columnNo];
columnHead[columnNo] = node;
} else // find place to link the node
{
columnPrevious = columnHead[columnNo];
columnNext = columnHead[columnNo].down;
while (columnNext != null && rowNo > columnNext.row)
{
columnPrevious = columnNext;
columnNext = columnNext.down;
}
// adjust links to complete insertion
columnPrevious.down = node;
node.down = columnNext;
}
}
}[/code:1:832192578e]
小飞爱使申华 回复于：2003-08-06 23:59:48
class SparseList:
[code:1:ae7a38429a]// This class holds the (i,j) co-ordinates and values of the non-zero elements
public class SparseList
{
private int row;
private int column;
private float value;
public void setRow (int row)
{ this.row = row;
}
public void setColumn (int column)
{ this.column = column;
}
public void setValue (float value)
{ this.value = value;
}
public int getRow ()
{ return row;
}
public int getColumn ()
{ return column;
}
public float getValue ()
{ return value;
}
}[/code:1:ae7a38429a]
class SparseMatrixDriver:
[code:1:ae7a38429a]import java.io.*;
/***********************************************
This is the test driver for the Matrix class.
***********************************************/
public class SparseMatrixDriver
{
public static void main (String[] args)
{
// create SparseMatrix A
System.out.print("Input the command ");
System.out.println("(\"i\" for inputting from keyboard or another key for default):");
BufferedReader In = new BufferedReader(new InputStreamReader(System.in));
String inputText;
try
{
inputText = In.readLine();
} catch (IOException IOE)
{
System.out.println(IOE.toString());
return;
}
SparseList[] a;
SparseMatrix A;
if (inputText.equals("i"))
{
int row, column, num;
try
{
System.out.print("Input the rows of the SparseMatrix A: ");
row = Integer.parseInt(In.readLine());
System.out.print("Input the columns of the SparseMatrix A: ");
column = Integer.parseInt(In.readLine());
System.out.print("Input the number of elements in SparseMatrix A: ");
num = Integer.parseInt(In.readLine());
} catch (IOException IOE)
{
System.out.println(IOE.toString());
System.out.println("Unable to get the integer data.");
return;
}
A = new SparseMatrix(row, column);
a = new SparseList[num];
for (int i = 0; i < num; i++)
{
System.out.println("The element " + i + ":");
a[i] = new SparseList();
int row_num, column_num;
try
{
System.out.print("Input the row:");
row_num = Integer.parseInt(In.readLine());
System.out.print("Input the column:");
column_num = Integer.parseInt(In.readLine());
} catch (IOException IOE)
{
System.out.println(IOE.toString());
System.out.println("Unable to get the integer data.");
return;
}
a[i].setRow(row_num);
a[i].setColumn(column_num);
System.out.print("Input the value:");
float value;
try
{
value = Float.parseFloat(In.readLine());
} catch (IOException IOE)
{
System.out.println(IOE.toString());
System.out.println("Unable to get the double data.");
return;
}
a[i].setValue(value);
}
} else
{
a = new SparseList[3];
a[0] = new SparseList();
a[0].setRow(4);
a[0].setColumn(6);
a[0].setValue(4.0f);
a[1] = new SparseList();
a[1].setRow(5);
a[1].setColumn(3);
a[1].setValue(6.0f);
a[2] = new SparseList();
a[2].setRow(9);
a[2].setColumn(5);
a[2].setValue(7.0f);
A = new SparseMatrix(10,15);
}
A.setMatrix(a);
System.out.println("Matrix A:");
A.displayMatrix();
System.out.println("k * Matrix A:");
A.scale(5.2f).displayMatrix();
System.out.print("norm |A| = ");
System.out.println(A.norm() + "\n");
// create SparseMatrix B
System.out.print("Input the command ");
System.out.println("(\"i\" for inputting from keyboard or another key for default):");
try
{
inputText = In.readLine();
} catch (IOException IOE)
{
System.out.println(IOE.toString());
return;
}
SparseList[] b;
SparseMatrix B;
if (inputText.equals("i"))
{
int row, column, num;
try
{
System.out.print("Input the rows of the SparseMatrix B: ");
row = Integer.parseInt(In.readLine());
System.out.print("Input the columns of the SparseMatrix B: ");
column = Integer.parseInt(In.readLine());
System.out.print("Input the number of elements in SparseMatrix B: ");
num = Integer.parseInt(In.readLine());
} catch (IOException IOE)
{
System.out.println(IOE.toString());
System.out.println("Unable to get the integer data.");
return;
}
B = new SparseMatrix(row, column);
b = new SparseList[num];
for (int i = 0; i < num; i++)
{
System.out.println("The element " + i + ":");
b[i] = new SparseList();
int row_num, column_num;
try
{
System.out.print("Input the row:");
row_num = Integer.parseInt(In.readLine());
System.out.print("Input the column:");
column_num = Integer.parseInt(In.readLine());
} catch (IOException IOE)
{
System.out.println(IOE.toString());
System.out.println("Unable to get the integer data.");
return;
}
b[i].setRow(row_num);
b[i].setColumn(column_num);
System.out.print("Input the value:");
float value;
try
{
value = Float.parseFloat(In.readLine());
} catch (IOException IOE)
{
System.out.println(IOE.toString());
System.out.println("Unable to get the double data.");
return;
}
b[i].setValue(value);
}
} else
{
b = new SparseList[4];
b[0] = new SparseList();
b[0].setRow(3);
b[0].setColumn(7);
b[0].setValue(14.45f);
b[1] = new SparseList();
b[1].setRow(5);
b[1].setColumn(3);
b[1].setValue(76.23f);
b[2] = new SparseList();
b[2].setRow(3);
b[2].setColumn(5);
b[2].setValue(5.0f);
b[3] = new SparseList();
b[3].setRow(6);
b[3].setColumn(5);
b[3].setValue(0.34f);
B = new SparseMatrix(10,15);
}
B.setMatrix(b);
System.out.println("Matrix B:");
B.displayMatrix();
System.out.print("norm |B| = ");
System.out.println(B.norm() + "\n");
System.out.println("Matrix (A + B):");
if (A.add(B) != null)
A.add(B).displayMatrix();
else
System.out.println("null\n");
}
}[/code:1:ae7a38429a]
rollingpig 回复于：2003-08-07 16:03:38
欢迎常来讨论哦
无双 回复于：2003-08-07 21:37:12
那如果不用链表呢
也就是查找时直接查找它的下标
因为链表的左指针与右指针不知道有没有用
小飞爱使申华 回复于：2003-08-08 00:07:12
[quote:39c924788c="无双"]那如果不用链表呢
也就是查找时直接查找它的下标
因为链表的左指针与右指针不知道有没有用[/quote:39c924788c]
无双老大，没懂你的意思。不用链表？费内存啊。
无双 回复于：2003-08-08 13:29:17
哦
看错
我原来意思就是创建成一个数组形式
每个数组元素里面都有行号列号值
只是如果这样的话添加新元素不方便