学步园

#include <stdio.h><br /> #include <stdlib.h></p> <p>int main(){</p> <p> int num[5][3] = { {5,6,4}, //稀疏矩阵共有5行,6列,4个元素<br /> {1,1,3}, //第1行第1列的元素为3<br /> {2,3,6},<br /> {3,2,9},<br /> {4,4,12}};<br /> int i, j, k = 1;//k用来标志元素的个数<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 /> }</p> <p> printf("还原后: /n");<br /> for(i = 0; i < num[0][0]; i++){<br /> for(j = 0; j < num[0][1]; j++){<br /> //k<=元素的个数,i等于行数,j等于列数,i,j从0开始计数<br /> if( k <= num[0][2] && 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 /> }</p> <p> return 0;<br /> }

在這邊所介紹的方法較為簡單，陣列只儲存矩陣的行數、列數與有資料的索引位置及其值，在需要使用矩陣資料時，再透過程式運算加以還原，例如若矩陣資料如下 ，其中0表示矩陣中該位置沒有資料：

這個矩陣是5X6矩陣，非零元素有4個，您要使用的陣列第一列記錄其列數、行數與非零元素個數：

陣列的第二列起，記錄其位置的列索引、行索引與儲存值：

所以原本要用30個元素儲存的矩陣資訊，現在只使用了15個元素來儲存，節省了不少記憶體的使用。

总结：

稀疏矩阵的存储方式有：

1、压缩顺序存储. (1)用三元组表示  （2）带辅助向量的二元组表示

2、链式存储。 （1）行链表表示   （2）正交表表示

用三元组表示的ADT：

template <class T><br /> class Term{<br /> private:<br /> int row, col;<br /> T value;<br /> };</p> <p>#include "term.h"</p> <p>template <class T><br /> class SparseMatrix{</p> <p> public:<br /> SparseMatrix(int maxTerms = 20);<br /> ~SparseMatrix(){ delete[] a;}<br /> void Transpose(SparseMatrix<T>&b) const;<br /> void Add(const SparseMatrix<T>& c, SparseMatrix<T>& d) const;</p> <p> friend ostream& operator <<(ostream&, const SparseMatrix<T>&);<br /> friend istream& operator <<(istream&, SparseMatrix<T>&);</p> <p> private:<br /> void Append(const Term<T>& t);<br /> int m, n; //稀疏矩阵的维数<br /> int N; //当前稀疏矩阵中非零元个数<br /> Term <T> * a; //用数组a用来存放稀疏矩阵三元组优先顺序序列<br /> int maxTerms; //稀疏矩阵允许最大非零元个数</p> <p>};</p> <p>