# 數組和稀疏矩陣
數組是由相同類型的數據元素構成的一個有序序列。數組按維來劃分，對于 m（m大于等于1） 維數組，每個元素受到 m 個線性關系的約束，所以數組是線性表的推廣。
n 維數組的數據元素存儲位置的計算公式：
$LOC(j_i,j_2,\dots ,j_n)\\=LOC(0,0,\dots ,0)+(b_2\dots b_nj_1+b_3\dots b_nj_2+\dots+b_nj_{n-1}+j_n)L\\=LOC(0,0,\dots ,0)+(\sum \limits_{i=1}^{n-1}j_i\prod \limits _{k=i+1}^nb_k+j_n)L\\=LOC(0,0,\dots ,0)+\sum \limits_{i=1}^nc_ij_i, \quad where\quad c_n=L, \quad c_{i-1}=b_ic_i,\quad1<i\leq n$
稀疏矩陣是非零元素相對于所有元素總數十分小的階數較大的矩陣。
### 稀疏矩陣的三元組表示法
數據類型定義
```C
#define MaxSize 100
typedef struct{
int r; //行號
int c; //列號
ElemType d; //元素值
}Triple;
typedef struct{
int rows;//行數
int cols;//列數
int nums;//非零元素個數
Triple data[MaxSize];
} TSMatrix;
```
轉置矩陣（復雜度O(rows*cols^2)）
```C
void TranTat(TSMatrix t, TSMatrix &tb) //tb 為 t 的轉置矩陣
{
int p, q=0,v;
tb.rows=t.cols;
tb.cols=t.rows;
tb.nums=t.nums;
if(t.nums!=0){
for(v=0;v<t.cols;v++)
for(p=0;p<t.nums;p++){
if(t.data[p].c==v){
tb.data[q].r=t.data[p].c;
tb.data[q].c=t.data[p].r;
tb.data[q].d=t.data[p].d;
q++;
}
}
}
}
```
快速轉置（復雜度O(rows*cols)）
```C
void FastTranTat(TSMatrix t, TSMatrix &tb)
{
int col, p, q, v;
int num[t.cols+1], cpot[t.cols+1];
tb.rows=t.cols;
tb.cols=t.rows;
tb.nums=t.nums;
if(t.nums!=0){
// 求 t 中每一列含非零元素的個數
for(col=1;col<=t.cols;++col)
num[col]=0;
for(v=1;v<=t.nums;++t)
num[t.data[v].c]++;
// 求第 col 列中第一個非零元素在 tb.data 中的序號
cpot[1] = 1;
for(col=2;col<=t.cols;++col)
cpot[col] = cpot[col-1] + num[col-1];
for(p=1;p<=t.nums;++p){
col = t.data[p].c;
q = cpot[col];
tb.data[q].r = t.data[p].c;
tb.data[q].c = t.data[p].r;
tb.data[q].d = t.data[p].d;
++cpot[col];
}
}
}
```
### 稀疏矩陣的行邏輯鏈接順序表
為了便于隨機存取任一行的非零元素，則需知道每一行的第一個非零元在三元組中是位置。
定義
```C
typedef struct{
Triple data[MaxSize];
int rpos[MaxSize]; //各行第一個非零元素的位置表
int rows, cols, nums;
}RLSMatrix;
```
兩稀疏矩陣相乘
```C
int MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q)
{
if(M.cols!=N.rows)
return 0;
Q.rows = M.rows;
Q.cols = N.cols;
Q.nums = 0;
int arow, brow, tp, p, t, q, ccol;
int ctemp[M.rows];
if(M.nums*N.nums!=0){ // Q 是非零矩陣
for(arow=1; arow<=M.rows; ++arow){
ctemp[arow] = 0;
Q.rpos[arow] = Q.nums + 1;
if(arow<M.rows)
tp = M.rpos[arow+1];
else
tp = M.nums + 1;
// 對當前行中每個非零元
for(p=M.rpos[arow];p<tp;++p){
// 找到對應元在 N 中的行號
brow = M.data[p].c;
if(brow<N.rows)
t = N.rpos[brow+1];
else
t.N.nums + 1;
for(q=N.rpos[brow];q<t;++q){
// 乘積元素在 Q 中的列號
ccol = N.data[q].c;
ctemp[ccol] += M.data[p].d * N.data[q].d;
}
}// 求得 Q 中第 arow 行的非零元
for(ccol=1;ccol<Q.cols;++ccol){
if(ctemp[ccol]){
if(++Q.nums>MaxSize)
return 0;
Q.data[Q.nums].r = arow;
Q.data[Q.nums].c = ccol;
Q.data[Q.nums].d = ctemp[ccol];
}
}
}
}
return 1;
}
```
### 稀疏矩陣的十字鏈表表示法
十字鏈表為稀疏矩陣的每一行和每一列設置一個單獨的鏈表，即每個非零元素包含在兩個鏈表里。
表節點和頭節點的定義
```C
#define M 3
#define N 4
#define Max ((M)>(N)?(M):(N))
typedef struct mtxn{
int row, col;
struct mtxn *right, *down;
union{
int value;
struct mtxn *link;
}tag;
}MatNode;
```
