数据结构第五章(稀疏矩阵类) - 线性表和数组ADT

#include <iostream>
#include <string>
using namespace std;
/////////////////////////////////////////////////////////////
//比较函数，用来比较x和y的大小，返回 -1 0 1
/////////////////////////////////////////////////////////////
int compare(int x,int y)
{
if(x>y)
return 1;
if(x==y)
return 0;
if(x<y)
return -1;
}

/////////////////////////////////////////////////////////////
//判断数字函数，判断给定的string是否是数字
/////////////////////////////////////////////////////////////
bool IsDigit(string& x)
{
int len=x.length();
int i=0;
while(i<len)
{
if(x[i]<'0'||x[i]>'9')
return false;
++i;
}
return true;
}

/////////////////////////////////////////////////////////////
//稀疏矩阵的三元组元素
/////////////////////////////////////////////////////////////
template <class T>
struct Entry
{
int row,col;
T value;
Entry& operator =(const Entry& x)
{
  row=x.row;
  col=x.col;
  value=x.value;
  return *this;
}
};

/////////////////////////////////////////////////////////////
//稀疏矩阵类
/////////////////////////////////////////////////////////////
template <class T>
class SeqTriple
{
public:
SeqTriple(int mSize=20)
{
maxSize=mSize;
t=new Entry<T>[maxSize];
rows=cols=nonZeros=0;
}
~SeqTriple(){delete[] t;}
SeqTriple(const SeqTriple& x);
SeqTriple& Transpose();
SeqTriple& operator = (const SeqTriple& x);
const SeqTriple operator + (const SeqTriple& x);
const SeqTriple operator * (const SeqTriple& x);
protected:
void Output(ostream& out);
void Input(istream& in);
private:
int maxSize;
int rows,cols,nonZeros;
Entry<T>* t;
friend istream& operator >> <>(istream& in,SeqTriple& x);
friend ostream& operator << <>(ostream& out,const SeqTriple& x);
};

/////////////////////////////////////////////////////////////
//拷贝构造函数
/////////////////////////////////////////////////////////////
template <class T>
SeqTriple<T>::SeqTriple(const SeqTriple& x)
{
maxSize=x.maxSize;
t=new Entry<T>[maxSize];
for(int i=0;i<maxSize;i++)
t[i]=x.t[i];
rows=x.rows;
cols=x.cols;
nonZeros=x.nonZeros;
}

/////////////////////////////////////////////////////////////
//重载稀疏矩阵的 = 符号
/////////////////////////////////////////////////////////////
template <class T>
SeqTriple<T>& SeqTriple<T>::operator =(const SeqTriple<T>& x)
{
delete[] t;
maxSize=x.maxSize;
rows=x.rows;
cols=x.cols;
nonZeros=x.nonZeros;
t=new Entry<T>[maxSize];
for(int i=0;i<maxSize;i++)
t[i]=x.t[i];
return *this;
}

/////////////////////////////////////////////////////////////
//稀疏矩阵的转置函数，返回转置后的矩阵
/////////////////////////////////////////////////////////////
template <class T>
SeqTriple<T>& SeqTriple<T>::Transpose()
{
int *k=new int[cols];
int *num=new int[cols];
for(int i=0;i<maxSize;i++)
k[i]=T();
for(int i=0;i<maxSize;i++)
num[i]=T();
for(int i=0;i<nonZeros;i++)
num[t[i].col]++;
for(int i=0;i<cols;i++)
k[i+1]=k[i]+num[i];

Entry<T>* newt=new Entry<T>[maxSize];
for(int i=0;i<nonZeros;i++)
{
int j=k[t[i].col]++;
newt[j].row=t[i].col;
newt[j].col=t[i].row;
newt[j].value=t[i].value;
}
delete t;
t=newt;
return *this;
}

/////////////////////////////////////////////////////////////
///重载稀疏矩阵的 + 符号，返回结果矩阵
/////////////////////////////////////////////////////////////
template <class T>
const SeqTriple<T> SeqTriple<T>::operator + (const SeqTriple<T>& x)
{
SeqTriple temp;
int k=0;
if((x.rows!=rows)||(x.cols!=cols))
cout<<"Size error"<<endl;
else
{
temp.cols=cols;
temp.rows=rows;
for(int i=0,j=0;(i<nonZeros&&j<x.nonZeros);k++)
{
int r=compare(t[i].row,x.t[j].row);
int c=compare(t[i].col,x.t[j].col);
switch(r)
{
case 1:
temp.t[k].row=x.t[j].row;
temp.t[k].col=x.t[j].col;
temp.t[k].value=x.t[j].value;
++j;
break;
case 0:
temp.t[k].row=x.t[j].row;
if(c>0)
{
temp.t[k].col=x.t[j].col;
temp.t[k].value=x.t[j].value;
++j;
}
if(c<0)
{
temp.t[k].col=t[i].col;
temp.t[k].value=t[i].value;
++i;
}
if(c==0)
{
temp.t[k].col=t[i].col;
temp.t[k].value=t[i].value+x.t[j].value;
++i;
++j;
}
break;
case -1:
temp.t[k].row=t[i].row;
temp.t[k].col=t[i].col;
temp.t[k].value=t[i].value;
++i;
break;
}
}
}
temp.nonZeros=k;
return temp;
}

/////////////////////////////////////////////////////////////
//重载稀疏矩阵的 * 符号，返回结果矩阵
/////////////////////////////////////////////////////////////
template <class T>
const SeqTriple<T> SeqTriple<T>::operator * (const SeqTriple<T>& x)
{
SeqTriple y=x;
y.Transpose();
SeqTriple temp;
int current_row=t[0].row;//结果的行
int current_col=y.t[0].row;//结果的列
int row_begin=0;//当前行的开始row数;
int sum=0;//乘积值
int k=0;//结果的非零个数
int i=0;
int j=0;
for(;i<nonZeros;)//从被乘数的每行作为结果的每行进行扫描
{
for(;j<y.nonZeros;)//从乘数的每行作为结果的每列进行扫描
{
if(current_row!=t[i].row)//如果扫描已经不是当前行
{
if(sum!=0)
{
  temp.t[k].row=current_row;
  temp.t[k].col=current_col;
  temp.t[k].value=sum;
  ++k;
}
sum=0;
i=row_begin;//从下一行的起始位置开始扫描
current_row=t[i].row;
}
else //如果仍然是扫描乘数的当前行
{
if(y.t[j].row==current_col)//找到当前列所包括的行
{
if(y.t[j].col==t[i].col)//如果这些行正好是乘法的对应相乘项
{
    sum=sum+y.t[j].value*t[i].value;
       ++i;
       ++j;
    continue;
}
if(y.t[j].col>t[i].col)//如果不是，继续搜索
{
       ++i;
       continue;
}
if(y.t[j].col<t[i].col)//向下遍历乘数
{
   ++j;
   continue;
}
}
else
{
if(sum!=0)
{
temp.t[k].row=current_row;
temp.t[k].col=current_col;
temp.t[k].value=sum;
++k;
}
sum=0;
i=row_begin;
current_col=y.t[j].row;//计算当前行下一列
}

}
}
for(;t[i].row==current_row;i++);//如果乘数的列已经遍历完毕，则当前行所有元素已经计算，进入下行
row_begin=i;
j=0;                            //列从最小开始重新扫描转置矩阵
current_col=y.t[j].row;         //当前列重新归到最小值
}
if(sum!=0)                 //处理最后一行最后一列元素
{
  temp.t[k].row=current_row;
  temp.t[k].col=current_col;
  temp.t[k].value=sum;
  ++k;
}
temp.nonZeros=k;
temp.rows=rows;
temp.cols=y.cols;
return temp;
}

/////////////////////////////////////////////////////////////
//重载矩阵的 >> 运算符号，以从键盘输入
/////////////////////////////////////////////////////////////
template <class T>
istream& operator >> (istream& in,SeqTriple<T>& x)
{
string input1,input2,input3;
int i=0;
int cols=0;
int rows=0;
cout<<"please input the row number value in SeqTriple"<<endl;
while(true)
{
in>>input1>>input2>>input3;
if(IsDigit(input1)&&IsDigit(input2)&&IsDigit(input3))
{
  x.t[i].row=atoi(input1.c_str());
  x.t[i].col=atoi(input2.c_str());
  x.t[i].value=atoi(input3.c_str());
     if(x.t[i].row>rows)
   rows=x.t[i].row;
  if(x.t[i].col>cols)
   cols=x.t[i].col;
++i;
}
else
{
  break;
}

}
x.nonZeros=i;
x.cols=cols+1;
x.rows=rows+1;
return in;
}

/////////////////////////////////////////////////////////////
//重载矩阵的 << 运算符号，打印稀疏三元组
/////////////////////////////////////////////////////////////
template <class T>
ostream& operator << (ostream& out,const SeqTriple<T>& x)
{

out<<"the SeqTriple contains:"<<endl;
for(int i=0;i<x.nonZeros;i++)
{
out<<x.t[i].row<<" ";
out<<x.t[i].col<<" ";
out<<x.t[i].value<<endl;
}
return out;
}

int main()
{

SeqTriple<int> x;
SeqTriple<int> y;
SeqTriple<int> z;
cin>>x;
cout<<x;
cin>>y;
cout<<y;
z=x*y;
cout<<z;
system("pause");
return 0;

}