稀疏矩陣（sparse matrix）的基本數據結構實現

無論是Matlab、SuiteSparse，還是CSparse，他們的稀疏矩陣的數據結構實現都是相同的。

/* --- primary CSparse routines and data structures ------------------------- */ntypedef struct cs_sparse /* matrix in compressed-column or triplet form */n{n csi nzmax ; /* maximum number of entries */n csi m ; /* number of rows */n csi n ; /* number of columns */n csi *p ; /* column pointers (size n+1) or col indices (size nzmax) */n csi *i ; /* row indices, size nzmax */n double *x ; /* numerical values, size nzmax */n csi nz ; /* # of entries in triplet matrix, -1 for compressed-col */n} cs ;n

簡單解釋一下，就是存儲row和column的行數，然後有三個malloc出來的空間，其中p是每個column的有效起始元素的序號，i是對應的每個column對應的有效row的序號，x存儲的是每個i指向的元素的值。其中p的長度是n+1，而i和x的長度都是nz。

舉個例子，稀疏矩陣如下：

1，2，0，0；

7，0，0，4；

0，0，0，1；

0，9，8，1。

那麼數據結構里的p,i,x的結構分別為：

p：0，2，4，5，8；

i：0，1，0，3，3，1，2，3；

x：1，7，2，9，8，4，1，1。

其中p的含義是，第一col從i[0]開始，第二col從i[2]開始，第三col從i[4]開始，第四col從i[5]開始，i最大index為8-1=7。而i和x分別對應著每個column中row的index和值。

還有一種是triplet方法，就是p和i分別村col和row的index，x存數值，這時候p、i、x三者size是相同的，也就是nz，就不贅述了。

參考header file：

CSparse/include/cs.h, Timothy Davis
推薦閱讀：