/*
Name: 三元組稀疏矩陣類
始發于goal00001111的專欄；允許自由轉載，但必須注明作者和出處
Author: goal00001111
Date: 07-05-10 09:51
Description: 三元組稀疏矩陣類：實現了矩陣的轉置，加法和乘法運算
*/
#include <cstdlib>
#include <iostream>
using namespace std;
const int MAXTERMS = 10000;
template <typename T> class SparseMatrix;//前置聲明
template <typename T>
class Trituple //三元組類
{
friend class SparseMatrix<T>;
private:
Trituple<T> & operator = (const Trituple<T> & b);
int row, col;
T value;
};
template <typename T> //重載賦值運算符
Trituple<T> & Trituple<T>::operator = (const Trituple<T> & b)
{
if (this != &b)
{
row = b.row;
col = b.col;
value = b.value;
}
return *this;
}
template <typename T>
class SparseMatrix //三元組稀疏矩陣類
{
public:
SparseMatrix(int maxRow, int maxCol, int maxTerms = 0); //構造函數1
SparseMatrix(const T a[], int maxRow, int maxCol); //構造函數2
SparseMatrix(const SparseMatrix<T> & b); //拷貝構造函數
SparseMatrix<T> & operator = (const SparseMatrix<T> & b);//重載賦值運算符
void Display(); //輸出三元組
void DisArray();//輸出矩陣
SparseMatrix<T> Transpose();//三元組順序表：轉置矩陣
SparseMatrix<T> FastTranspose();//三元組順序表：快速轉置矩陣
SparseMatrix<T> Add(SparseMatrix<T> b);//矩陣相加
SparseMatrix<T> Multiply(SparseMatrix<T> b);//矩陣相乘
private:
int rows, cols, terms;//矩陣的行數，列數和非零元素個數
Trituple<T> smArray[MAXTERMS];//三元組順序表
};
template <typename T> //構造函數1
SparseMatrix<T>::SparseMatrix(int maxRow, int maxCol, int maxTerms):rows(maxRow), cols(maxCol), terms(maxTerms)
{
}
template <typename T> //構造函數2：將二維數組轉換為三元組
SparseMatrix<T>::SparseMatrix(const T a[], int maxRow, int maxCol):rows(maxRow), cols(maxCol), terms(0)
{
for (int i=0; i<rows; i++)
{
for (int j=0; j<cols; j++)
{
if (a[i*cols+j] != 0)
{
smArray[terms].row = i;
smArray[terms].col = j;
smArray[terms++].value = a[i*cols+j];
}
if (terms > MAXTERMS)
return;
}
}
}
template <typename T> //拷貝構造函數
SparseMatrix<T>::SparseMatrix(const SparseMatrix<T> & b)
{
rows = b.rows;
cols = b.cols;
terms = b.terms;
for (int i=0; i<terms; i++)
smArray[i] = b.smArray[i];
}
template <typename T>//重載賦值運算符
SparseMatrix<T> & SparseMatrix<T>::operator = (const SparseMatrix<T> & b)
{
if (this != &b)
{
rows = b.rows;
cols = b.cols;
terms = b.terms;
for (int i=0; i<terms; i++)
smArray[i] = b.smArray[i];
}
return *this;
}
template <typename T>//輸出三元組
void SparseMatrix<T>::Display()
{
cout << "rows = " << rows << ", cols = " << cols << ", terms = " << terms << endl;
for (int i=0; i<terms; i++)
cout << i+1 << "(" << smArray[i].row << ", " << smArray[i].col << ", " << smArray[i].value << ")\t";
cout << endl;
}
template <typename T>//輸出矩陣：包括非零元素
void SparseMatrix<T>::DisArray()
{
int top = 0;
for (int i=0; i<rows; i++)
{
for (int j=0; j<cols; j++)
{
if (i == smArray[top].row && j == smArray[top].col)
cout << smArray[top++].value << " ";
else
cout << "0 ";
}
cout << endl;
}
cout << endl;
}
template <typename T>
SparseMatrix<T> SparseMatrix<T>::Transpose()//三元組順序表：轉置矩陣
{
SparseMatrix<T> t(cols, rows, terms);
if(terms > 0)
{
int top = 0;
for(int j=0; j<cols; j++) //按照T的行序（M的列序）為主序依次排列
for(int i=0; i<terms; i++)//掃描M的所有元素
if(smArray[i].col == j)
{
t.smArray[top].row = smArray[i].col;
t.smArray[top].col = smArray[i].row;
t.smArray[top++].value = smArray[i].value;
}//if
} //else
return t;
}
template <typename T>
SparseMatrix<T> SparseMatrix<T>::FastTranspose()//三元組順序表：快速轉置矩陣
{
SparseMatrix<T> t(cols, rows, terms);
int * colSize = new int[cols];//存儲每列的非零元素個數
int * colStart = new int[cols];//存儲每列第一個非零元素在三元組中的位置（下標）
if(terms > 0)
{
for(int i=0; i<cols; i++)
colSize[i] = 0;
for(int i=0; i<terms; i++)//掃描M的所有元素
colSize[smArray[i].col]++; //確定矩陣M每一列中非零元素的個數
colStart[0] = 0;// 確定矩陣M第i列中第一個非零元素在t.smArray中的位置
for(int i=1; i<cols; i++)
colStart[i] = colStart[i-1] + colSize[i-1];
for(int i=0; i<terms; i++)//掃描M的所有元素
{
int k = colStart[smArray[i].col]; //k即矩陣M第col列中第一個非零元素在t.smArray中的位置
t.smArray[k].row = smArray[i].col;
t.smArray[k].col = smArray[i].row;
t.smArray[k].value = smArray[i].value;
colStart[smArray[i].col]++; //矩陣M第col列中第一個非零元素在t.smArray中的位置向前移動一位
}//for
}//if
delete []colSize;
delete []colStart;
return t;
}
template <typename T>
SparseMatrix<T> SparseMatrix<T>::Add(SparseMatrix<T> b)//矩陣相加：采用合并算法，行序優先
{
SparseMatrix<int> c(cols, rows);
int i = 0, j = 0, k = 0;
while (i < terms && j < b.terms)
{
if (smArray[i].row == b.smArray[j].row && smArray[i].col == b.smArray[j].col)
{
c.smArray[k].row = smArray[i].col;
c.smArray[k].col = smArray[i].row;
c.smArray[k].value = smArray[i++].value + b.smArray[j++].value;
if (c.smArray[k].value != 0)
k++;
}
else if ((smArray[i].row < b.smArray[j].row) ||(smArray[i].row == b.smArray[j].row && smArray[i].col < b.smArray[j].col))
c.smArray[k++] = smArray[i++];
else
c.smArray[k++] = b.smArray[j++];
}//while
if (i > terms) //A結束，若B還有元素，則將B的元素直接放入C中
{
while (j < b.terms)
c.smArray[k++] = b.smArray[j++];
}
else //B結束，若A還有元素，則將A的元素直接放入C中
{
while (i < terms)
c.smArray[k++] = smArray[i++];
}
c.terms = k;
return c;
}
template <typename T> //矩陣相乘：快速乘法
SparseMatrix<T> SparseMatrix<T>::Multiply(SparseMatrix<T> b)
{
SparseMatrix<T> t(0, 0 , 0);
if(b.rows != cols)
return t;
SparseMatrix<T> c(rows, b.cols);
int * rowSize = new int[b.rows]; //存儲b每行的非零元素個數
int * rowStart = new int[b.rows];//存儲b每行的首個非零元素位置
int * ctemp = new int[b.cols]; //存儲b中與a某個元素做乘法運算的第col列元素的累積值
if(terms * b.terms != 0)//若C是非零矩陣
{
for(int i=0; i<b.rows; i++)
rowSize[i] = 0;
for(int i=0; i<b.terms; i++)//掃描b的所有元素
rowSize[b.smArray[i].row]++; //確定矩陣b每一行中非零元素的個數
rowStart[0] = 0;// 確定矩陣b第i行中第一個非零元素在b.smArray中的位置
for(int i=1; i<b.rows; i++)
rowStart[i] = rowStart[i-1] + rowSize[i-1];
int k = 0, top = 0;
for(int i=0; i<rows; i++)//對A進行逐行處理，即對C進行逐行處理
{
for(int j=0; j<b.cols; j++)//當前各元素累加器清零
ctemp[j] = 0;
while (k < terms && smArray[k].row == i)//處理A的第i行元素
{
int tc = smArray[k].col;
for (int j=rowStart[tc]; b.smArray[j].row == tc; j++)//處理B的第tc行數據：進行累積
{
ctemp[b.smArray[j].col] += smArray[k].value * b.smArray[j].value;
}
k++;
}
for(int j=0; j<b.cols; j++)//得到C的第i行中每一個元素的值
{
if(ctemp[j] != 0)//壓縮存儲該行非零元
{
if(top == MAXTERMS)
return t;
c.smArray[top].row = i;
c.smArray[top].col = j;
c.smArray[top++].value = ctemp[j];//C的元素值等于A的行數ctemp[j]的累積值
} //if(ctemp[j] != 0)
}
}//for arow
c.terms = top;
}
delete []rowSize;
delete []rowStart;
delete []ctemp;
return c;
} // MultSMatrix
int main(int argc, char *argv[])
{
SparseMatrix<int> obja(2, 3);
obja.Display();
int arr[100] = {0};
int r = 3, c = 3;
for (int i=0; i<r; i++)
for (int j=0; j<c; j++)
cin >> arr[i*c+j];
//
// for (int i=0; i<r; i++)
// {
// for (int j=0; j<c; j++)
// cout << arr[i*c+j] << " ";
// cout << endl;
// }
// cout << endl;
SparseMatrix<int> objb(arr, r, c);
objb.DisArray();
SparseMatrix<int> objc = objb.Transpose();
objc.DisArray();
//obja = objc;
// objc.Display();
// objc.DisArray();
//
// SparseMatrix<int> objd = obja.Transpose();
// objd.Display();
// objd.DisArray();
//
SparseMatrix<int> obje = objb.Multiply(objc);
obje.Display();
obje.DisArray();
system("PAUSE");
return EXIT_SUCCESS;
}