稀疏矩阵(Sparse Matrix)的java实现

小飞爱使申华

看看这里不像C坛这么热闹，过来给大家捧捧场。
下面是我过去做过的一个assignment，一共有4个class（其中一个inner class），请大家多指教：

   

1. Background
   
2. 
   
3. 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.
   
4. 
   
5. 有时候出于某种原因我们需要一个非常大的二维数组，但是这数组并不是经常满的，这样就很浪费内存，因此我们可以用稀疏矩阵来代替它，这稀疏矩阵就是用二维链表把非零的节点连起来。
   

复制代码

小飞爱使申华

class SparseMatrix & inner class Element:

   

1. import java.io.*;
   
2. 
   
3. /****************************************************************
   
4. This class provides functionality for storing, solving, and
   
5. managing sparce matrices. Only the non-zero elements are stored.
   
6. It represents the sparse matrix as a two-dimensional linked list
   
7. of the non-zero elements. The elements of Matrix are all of type
   
8. float.
   
9. ****************************************************************/
   
10. public class SparseMatrix
    
11. {
    
12.    // This class provides the list node for the linked list. with
    
13.    //        references to the next non-zero element in the same row and
    
14.    //        the next non-zero element in the same column.
    
15.    class Element
    
16.    {
    
17.       private int row;
    
18.       private int column;
    
19.       private float value;
    
20.       private Element right;
    
21.       private Element down;
    
22.    }
    
23. 
    
24.    private Element[] rowHead;
    
25.    private Element[] columnHead;
    
26. 
    
27. 
    
28.    /*************************************************************
    
29.     Create an m-by-n SparseMatrix with storing it in the linked
    
30.     list.
    
31.    
    
32.     @param m the number of rows in <code>;this</code>; Matrix.
    
33.    
    
34.     @param n the number of columns in <code>;this</code>; Matrix.
    
35.    **************************************************************/
    
36.    public SparseMatrix (int m, int n)                //constructor
    
37.    {       
    
38.            if(m <= 0)
    
39.            {
    
40.                    System.out.println("The rows of the matrix must be greater than zero.");
    
41.                    System.exit(1);
    
42.            }
    
43.           
    
44.            if(n <= 0)
    
45.            {
    
46.                    System.out.println("The columns of the matrix must be greater than zero.");
    
47.                    System.exit(1);
    
48.            }
    
49.           
    
50.            rowHead = new Element[m];
    
51.       columnHead = new Element[n];
    
52.    }
    
53. 
    
54.    
    
55.         /*************************************************************
    
56.          Add the passed SparseMatrix to <code>;this</code>; SparseMatrix.
    
57.          
    
58.          @param B the SparseMatrix to add to <code>;this</code>;
    
59.          SparseMatrix.
    
60.          
    
61.          @return a reference to a new SparseMatrix object that is equal
    
62.          to the sum of <code>;this</code>; SparseMatrix and the passed one.
    
63.          If the passed SparseMatrix is null or the number of rows and
    
64.          columns of <code>;this</code>; SparseMatrix is not equal to the
    
65.          passed one, null will be returned.
    
66.         **************************************************************/
    
67.    public SparseMatrix add (SparseMatrix B)
    
68.    {       
    
69.            SparseMatrix C = null;
    
70.            if (B != null && rowHead.length == B.rowHead.length && columnHead.length == B.columnHead.length)
    
71.            {       
    
72.                    C = new SparseMatrix(rowHead.length, columnHead.length);
    
73.                    SparseList[] scaleOne = new SparseList[rowHead.length * columnHead.length];
    
74.                   
    
75.                    Element aNext, bNext, rowNext, newNode;
    
76.                   
    
77.                    for (int i = 0; i < rowHead.length; i++)
    
78.                    {       
    
79.                            if (rowHead[i] != null || B.rowHead[i] != null)
    
80.                            {
    
81.                                    aNext = rowHead[i];                        //trace Matrix this' row linked list
    
82.                                    bNext = B.rowHead[i];                //trace Matrix B's row linked list
    
83.                                    newNode = new Element();        //obtain node for new value
    
84.                                    C.rowHead[i] = newNode;       
    
85.                                   
    
86.                                    do
    
87.                                    {
    
88.                                            if (aNext == null)
    
89.                                            {
    
90.                                                    rowNext = bNext;
    
91.                                                    bNext = bNext.right;
    
92.                                            } else if (bNext == null)
    
93.                                            {
    
94.                                                    rowNext = aNext;
    
95.                                                    aNext = aNext.right;
    
96.                                            } else
    
97.                                            {       
    
98.                                                    if (bNext.column < aNext.column)
    
99.                                                    {       
    
100.                                                            rowNext = bNext;
     
101.                                                            bNext = bNext.right;
     
102.                                                    } else if (bNext.column >; aNext.column)
     
103.                                                    {       
     
104.                                                            rowNext = aNext;
     
105.                                                            aNext = aNext.right;
     
106.                                                    } else if (Math.abs(aNext.value + bNext.value) >; 0.0001)
     
107.                                                    {       
     
108.                                                            rowNext = new Element();
     
109.                                                            rowNext.row = aNext.row;
     
110.                                                            rowNext.column = aNext.column;
     
111.                                                            rowNext.value = aNext.value + bNext.value;
     
112.                                                            aNext = aNext.right;
     
113.                                                            bNext = bNext.right;
     
114.                                                    }else        // at the same position && sum of the values = 0
     
115.                                                    {       
     
116.                                                            aNext = aNext.right;
     
117.                                                            bNext = bNext.right;
     
118.                                                            continue;
     
119.                                                    }
     
120.                                            }
     
121.                                                                                      
     
122.                                            newNode.row = rowNext.row;
     
123.                                            newNode.column = rowNext.column;
     
124.                                            newNode.value = rowNext.value;
     
125.                                                   
     
126.                                            C.insertColumn(newNode);
     
127.                                           
     
128.                                            rowNext = rowNext.right;
     
129.                                            if (aNext != null || bNext != null)
     
130.                                            {
     
131.                                                           newNode.right = new Element();
     
132.                                                           newNode = newNode.right;
     
133.                                                 } else        // the last node
     
134.                                                 {        newNode.right = null;
     
135.                                                         newNode.down = null;
     
136.                                                 }
     
137.                                         }while (aNext != null || bNext != null);
     
138.                                 }
     
139.                    }
     
140.            }
     
141.            return C;
     
142.    }
     
143. 
     
144. 
     
145.    /*************************************************************
     
146.          Multiply the passed number to all elements in
     
147.          <code>;this</code>; SparseMatrix.
     
148.          
     
149.          @param k the number to multiply <code>;this</code>; SparseMatrix
     
150.          by.
     
151.          
     
152.          @return a reference to a new Matrix object that is equal to
     
153.          the product of <code>;this</code>; SpaseMatrix and the passed
     
154.          number.
     
155.         **************************************************************/
     
156.    public SparseMatrix scale (float k)
     
157.    {       
     
158.            SparseMatrix C = new SparseMatrix(rowHead.length, columnHead.length);
     
159.            Element newNode, rowNext;
     
160.           
     
161.            if (k != 0.) // if k is equal to zero, no new node is added
     
162.            {
     
163.                    for (int i = 0; i < rowHead.length; i++)
     
164.                    {       
     
165.                            if (rowHead[i] != null)
     
166.                            {
     
167.                                    rowNext = rowHead[i];        //trace this row linked list
     
168.                                    newNode = new Element();        //obtain node for new value
     
169.                                    C.rowHead[i] = newNode;       
     
170.                                   
     
171.                                    do
     
172.                                    {
     
173.                                            int rowNo = rowNext.row;
     
174.                                            int columnNo = rowNext.column;
     
175.                                           
     
176.                                            newNode.row = rowNo;
     
177.                                            newNode.column = columnNo;
     
178.                                            newNode.value = k * rowNext.value;
     
179.                                           
     
180.                                            C.insertColumn(newNode);
     
181.                                           
     
182.                                            rowNext = rowNext.right;
     
183.                                            if (rowNext != null)
     
184.                                            {
     
185.                                                    newNode.right = new Element();
     
186.                                                    newNode = newNode.right;
     
187.                                            } else        // the last node
     
188.                                                 {        newNode.right = null;
     
189.                                                         newNode.down = null;
     
190.                                                 }
     
191.                                    }while (rowNext != null);
     
192.                            }
     
193.                    }
     
194.                 }
     
195.            return C;
     
196.    }
     
197. 
     
198. 
     
199.         /*************************************************************
     
200.          Return the maximum absolute row sum of <code>;this</code>;
     
201.          SparseMatrix.
     
202.          
     
203.          @return the infinity norm of <code>;this</code>; SparseMatrix.
     
204.         **************************************************************/
     
205.    public float norm ()
     
206.    {       
     
207.            double max = 0.;
     
208.            double sum;
     
209.            Element newNode;
     
210.           
     
211.            for (int i = 0; i < rowHead.length; i++)
     
212.            {       
     
213.                    sum = 0.;
     
214.                    // add the value in the same row list
     
215.                    for (newNode = rowHead[i]; newNode != null; newNode = newNode.right)
     
216.                    {       
     
217.                            sum += Math.abs(newNode.value);
     
218.                    }
     
219.                    if (sum >; max)
     
220.                            max = sum;
     
221.            }
     
222.            return (float)max;
     
223.    }
     
224. 
     
225. 
     
226.         /*************************************************************
     
227.          Initialize <code>;this</code>; SparseMatrix with the values
     
228.          from the passed array.
     
229.          
     
230.          @param a the array to be initialized <code>;this</code>; SparseMatrix.
     
231.         **************************************************************/
     
232.    public void setMatrix (SparseList[] a)
     
233.    {       
     
234.       for (int i = 0; i < rowHead.length; i++)
     
235.          rowHead[i] = null;
     
236. 
     
237.       for (int j = 0; j < columnHead.length; j++)
     
238.          columnHead[j] = null;
     
239.           
     
240.            Element newNode, rowPrevious, rowNext, columnPrevious, columnNext;
     
241.           
     
242.            for (int i = 0; i < a.length; i++)
     
243.            {       
     
244.                    //        test if this element is in this matrix and the element's value is not equal to zero
     
245.                    if (a[i].getRow() < rowHead.length && a[i].getColumn() < columnHead.length && a[i].getValue() != 0)
     
246.                    {       
     
247.                            int rowNo = a[i].getRow();
     
248.                            int columnNo = a[i].getColumn();
     
249.                           
     
250.                            newNode = new Element();        //obtain node for new value
     
251.                            newNode.right = null;
     
252.                            newNode.down = null;
     
253.                            newNode.row = rowNo;
     
254.                            newNode.column = columnNo;
     
255.                            newNode.value = a[i].getValue();
     
256.                           
     
257.                                   // the later one will overwrite the former one if at the same position
     
258.                                   if (rowHead[rowNo] != null && columnNo == rowHead[rowNo].column)
     
259.                                    rowHead[rowNo].value = a[i].getValue();
     
260.                                   else        //        no former one at the same position
     
261.                                           insertRow(newNode);
     
262.                            insertColumn(newNode);
     
263.                    }
     
264.            }
     
265.    }
     
266. 
     
267.         /*************************************************************
     
268.          Display <code>;this</code>; SparseMatrix as a rectangular grid
     
269.          of values on the screen. It prints all the elements in the
     
270.          matrix, including the implicit zeros.
     
271.         **************************************************************/
     
272.    public void displayMatrix ()
     
273.    {       
     
274.            int count;
     
275.            Element newNode;
     
276.            for (int i = 0; i < rowHead.length; i++)
     
277.            {       
     
278.                    count = 0; //        count the number of the printed elements       
     
279.                    for (newNode = rowHead[i]; newNode != null; newNode = newNode.right)
     
280.                    {       
     
281.                            //        print the 0's before and between the nodes
     
282.                            for (int j = count; j < newNode.column; j++)
     
283.                                    System.out.print("0.000    ");
     
284.                            System.out.print(newNode.value);
     
285.                            for (int j = 0; j < 9 - new Float(newNode.value).toString().length(); j++)
     
286.                                    System.out.print(" ");
     
287.                            count = newNode.column + 1;
     
288.                    }
     
289.                   
     
290.                    //        print the 0's after the last node or in the empty linked list.
     
291.                    for (int j = count; j < columnHead.length; j++)
     
292.                            System.out.print("0.000    ");
     
293.                         System.out.println();
     
294.                 }
     
295.                 System.out.println();
     
296.    }
     
297.    
     
298.                         
     
299.    // insert to the row linked list
     
300.    private void insertRow (Element node)
     
301.    {          
     
302.            Element rowPrevious, rowNext;
     
303.                 int rowNo = node.row;
     
304.       int columnNo = node.column;       
     
305.                           
     
306.            // see if the node goes first in the list
     
307.            if (rowHead[rowNo] == null || columnNo < rowHead[rowNo].column)
     
308.            {       
     
309.                    node.right = rowHead[rowNo];
     
310.                    rowHead[rowNo] = node;
     
311.            } else        // find place to link the node
     
312.            {       
     
313.                    rowPrevious = rowHead[rowNo];
     
314.                    rowNext = rowHead[rowNo].right;
     
315.                    while (rowNext != null && columnNo >; rowNext.column)
     
316.                    {       
     
317.                            rowPrevious = rowNext;
     
318.                            rowNext = rowNext.right;
     
319.                    }
     
320.                                   
     
321.                    // adjust links to complete insertion
     
322.                    rowPrevious.right = node;
     
323.                    node.right = rowNext;
     
324.            }
     
325.         }
     
326.    
     
327.        
     
328.         // insert to the column linked list
     
329.         private void insertColumn (Element node)
     
330.         {
     
331.                 Element columnPrevious, columnNext;
     
332.                 int rowNo = node.row;
     
333.       int columnNo = node.column;
     
334.                
     
335.                 // see if the node goes first in the list
     
336.                 if (columnHead[columnNo] == null || rowNo < columnHead[columnNo].row)
     
337.                 {       
     
338.                    node.down = columnHead[columnNo];
     
339.                         columnHead[columnNo] = node;
     
340.                 } else        // find place to link the node
     
341.                 {       
     
342.                         columnPrevious = columnHead[columnNo];
     
343.                         columnNext = columnHead[columnNo].down;
     
344.                    while (columnNext != null && rowNo >; columnNext.row)
     
345.                    {       
     
346.                            columnPrevious = columnNext;
     
347.                            columnNext = columnNext.down;
     
348.                    }
     
349.                                           
     
350.                           // adjust links to complete insertion
     
351.                    columnPrevious.down = node;
     
352.                    node.down = columnNext;
     
353.                 }
     
354.         }
     
355. }

复制代码

小飞爱使申华

class SparseList:

   

1. // This class holds the (i,j) co-ordinates and values of the non-zero elements
   
2. public class SparseList
   
3. {
   
4.    private int row;
   
5.    private int column;
   
6.    private float value;
   
7. 
   
8.    public void setRow (int row)
   
9.    {  this.row = row;
   
10.    }
    
11. 
    
12.    public void setColumn (int column)
    
13.    {        this.column = column;
    
14.    }
    
15. 
    
16.    public void setValue (float value)
    
17.    {  this.value = value;
    
18.    }
    
19.    
    
20.    public int getRow ()
    
21.    {        return row;
    
22.         }
    
23. 
    
24.         public int getColumn ()
    
25.         {        return column;
    
26.         }
    
27. 
    
28.         public float getValue ()
    
29.         {        return value;
    
30.         }
    
31. }

复制代码

class SparseMatrixDriver:

1. import java.io.*;
   
2. 
   
3. /***********************************************
   
4. This is the test driver for the Matrix class.
   
5. ***********************************************/
   
6. public class SparseMatrixDriver
   
7. {
   
8.    public static void main (String[] args)
   
9.    {
   
10.       // create SparseMatrix A
    
11.                 System.out.print("Input the command ");
    
12.                 System.out.println("(\"i\" for inputting from keyboard or another key for default):");
    
13.       BufferedReader In = new BufferedReader(new InputStreamReader(System.in));
    
14.       String inputText;
    
15.                 try
    
16.                 {
    
17.                         inputText = In.readLine();
    
18.                 } catch (IOException IOE)
    
19.                 {
    
20.                         System.out.println(IOE.toString());
    
21.                         return;
    
22.                 }      
    
23.       SparseList[] a;
    
24.       SparseMatrix A;
    
25.       
    
26.       if (inputText.equals("i"))
    
27.       {       
    
28.               int row, column, num;
    
29.                         try
    
30.                         {
    
31.                                 System.out.print("Input the rows of the SparseMatrix A: ");
    
32.                                 row = Integer.parseInt(In.readLine());
    
33.                                 System.out.print("Input the columns of the SparseMatrix A: ");
    
34.                                 column = Integer.parseInt(In.readLine());
    
35.                                 System.out.print("Input the number of elements in SparseMatrix A: ");
    
36.                                 num = Integer.parseInt(In.readLine());
    
37.                         } catch (IOException IOE)
    
38.                         {
    
39.                                 System.out.println(IOE.toString());
    
40.                                 System.out.println("Unable to get the integer data.");
    
41.                                 return;
    
42.                         }
    
43.               A = new SparseMatrix(row, column);
    
44.               a = new SparseList[num];
    
45.               for (int i = 0; i < num; i++)
    
46.               {       
    
47.                       System.out.println("The element " + i + ":");
    
48.                       a[i] = new SparseList();
    
49.                       int row_num, column_num;
    
50.                                 try
    
51.                                 {
    
52.                                         System.out.print("Input the row:");
    
53.                                         row_num = Integer.parseInt(In.readLine());
    
54.                                         System.out.print("Input the column:");
    
55.                                         column_num = Integer.parseInt(In.readLine());
    
56.                                 } catch (IOException IOE)
    
57.                                 {
    
58.                                         System.out.println(IOE.toString());
    
59.                                         System.out.println("Unable to get the integer data.");
    
60.                                         return;
    
61.                                 }
    
62.                       a[i].setRow(row_num);
    
63.                       a[i].setColumn(column_num);
    
64.                       System.out.print("Input the value:");
    
65.                       float value;
    
66.                                 try
    
67.                                 {
    
68.                                         value = Float.parseFloat(In.readLine());
    
69.                                 } catch (IOException IOE)
    
70.                                 {
    
71.                                         System.out.println(IOE.toString());
    
72.                                         System.out.println("Unable to get the double data.");
    
73.                                         return;
    
74.                                 }
    
75.                               a[i].setValue(value);
    
76.                      }
    
77.       } else
    
78.       {
    
79.               a = new SparseList[3];
    
80.        
    
81.               a[0] = new SparseList();
    
82.               a[0].setRow(4);
    
83.               a[0].setColumn(6);
    
84.               a[0].setValue(4.0f);
    
85.        
    
86.               a[1] = new SparseList();
    
87.               a[1].setRow(5);
    
88.               a[1].setColumn(3);
    
89.               a[1].setValue(6.0f);
    
90.        
    
91.               a[2] = new SparseList();
    
92.               a[2].setRow(9);
    
93.               a[2].setColumn(5);
    
94.               a[2].setValue(7.0f);
    
95.        
    
96.               A = new SparseMatrix(10,15);
    
97.            }
    
98. 
    
99.       A.setMatrix(a);
    
100.       
     
101.       System.out.println("Matrix A:");
     
102.       A.displayMatrix();
     
103.       
     
104.       System.out.println("k * Matrix A:");
     
105.       A.scale(5.2f).displayMatrix();
     
106.       
     
107.       System.out.print("norm |A| = ");
     
108.       System.out.println(A.norm() + "\n");
     
109.       
     
110.       // create SparseMatrix B
     
111.                 System.out.print("Input the command ");
     
112.                 System.out.println("(\"i\" for inputting from keyboard or another key for default):");
     
113.                 try
     
114.                 {
     
115.                         inputText = In.readLine();
     
116.                 } catch (IOException IOE)
     
117.                 {
     
118.                         System.out.println(IOE.toString());
     
119.                         return;
     
120.                 }
     
121.       SparseList[] b;
     
122.       SparseMatrix B;
     
123.       
     
124.       if (inputText.equals("i"))
     
125.       {       
     
126.               int row, column, num;
     
127.                         try
     
128.                         {
     
129.                                 System.out.print("Input the rows of the SparseMatrix B: ");
     
130.                                 row = Integer.parseInt(In.readLine());
     
131.                                 System.out.print("Input the columns of the SparseMatrix B: ");
     
132.                                 column = Integer.parseInt(In.readLine());
     
133.                                 System.out.print("Input the number of elements in SparseMatrix B: ");
     
134.                                 num = Integer.parseInt(In.readLine());
     
135.                         } catch (IOException IOE)
     
136.                         {
     
137.                                 System.out.println(IOE.toString());
     
138.                                 System.out.println("Unable to get the integer data.");
     
139.                                 return;
     
140.                         }
     
141.               B = new SparseMatrix(row, column);
     
142.               b = new SparseList[num];
     
143.               for (int i = 0; i < num; i++)
     
144.               {       
     
145.                       System.out.println("The element " + i + ":");
     
146.                       b[i] = new SparseList();
     
147.                       int row_num, column_num;
     
148.                                 try
     
149.                                 {
     
150.                                         System.out.print("Input the row:");
     
151.                                         row_num = Integer.parseInt(In.readLine());
     
152.                                         System.out.print("Input the column:");
     
153.                                         column_num = Integer.parseInt(In.readLine());
     
154.                                 } catch (IOException IOE)
     
155.                                 {
     
156.                                         System.out.println(IOE.toString());
     
157.                                         System.out.println("Unable to get the integer data.");
     
158.                                         return;
     
159.                                 }
     
160.                       b[i].setRow(row_num);
     
161.                                 b[i].setColumn(column_num);
     
162.                       System.out.print("Input the value:");
     
163.                       float value;
     
164.                                 try
     
165.                                 {
     
166.                                         value = Float.parseFloat(In.readLine());
     
167.                                 } catch (IOException IOE)
     
168.                                 {
     
169.                                         System.out.println(IOE.toString());
     
170.                                         System.out.println("Unable to get the double data.");
     
171.                                         return;
     
172.                                 }
     
173.                               b[i].setValue(value);
     
174.                      }
     
175.       } else
     
176.       {
     
177.               b = new SparseList[4];
     
178.        
     
179.               b[0] = new SparseList();
     
180.               b[0].setRow(3);
     
181.               b[0].setColumn(7);
     
182.               b[0].setValue(14.45f);
     
183.        
     
184.               b[1] = new SparseList();
     
185.               b[1].setRow(5);
     
186.               b[1].setColumn(3);
     
187.               b[1].setValue(76.23f);
     
188.        
     
189.               b[2] = new SparseList();
     
190.               b[2].setRow(3);
     
191.               b[2].setColumn(5);
     
192.               b[2].setValue(5.0f);
     
193.              
     
194.               b[3] = new SparseList();
     
195.               b[3].setRow(6);
     
196.               b[3].setColumn(5);
     
197.               b[3].setValue(0.34f);
     
198.              
     
199.               B = new SparseMatrix(10,15);
     
200.                 }
     
201. 
     
202.       B.setMatrix(b);
     
203.       
     
204.       System.out.println("Matrix B:");
     
205.       B.displayMatrix();
     
206.       
     
207.       System.out.print("norm |B| = ");
     
208.       System.out.println(B.norm() + "\n");
     
209.       
     
210.       System.out.println("Matrix (A + B):");
     
211.       if (A.add(B) != null)
     
212.               A.add(B).displayMatrix();
     
213.       else
     
214.               System.out.println("null\n");
     
215.    }
     
216. }

复制代码

rollingpig

欢迎常来讨论哦

无双

那如果不用链表呢
也就是查找时直接查找它的下标

因为链表的左指针与右指针不知道有没有用

小飞爱使申华

原帖由 "无双" 发表：
那如果不用链表呢
也就是查找时直接查找它的下标

因为链表的左指针与右指针不知道有没有用

   

无双老大，没懂你的意思。不用链表？费内存啊。

无双

哦
看错

我原来意思就是创建成一个数组形式

每个数组元素里面都有行号列号值

只是如果这样的话添加新元素不方便