数据结构第五章(稀疏矩阵类)

#include
#include
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  return -1;
}

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

/////////////////////////////////////////////////////////////
//稀疏矩阵的三元组元素
/////////////////////////////////////////////////////////////
template
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 SeqTriple
{
public:
SeqTriple(int mSize=20)
{
maxSize=mSize;
t=new Entry[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;
 friend istream& operator >> <>(istream& in,SeqTriple& x);
 friend ostream& operator << <>(ostream& out,const SeqTriple& x);
};

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

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

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

Entry* newt=new Entry[maxSize];
for(int i=0;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
const SeqTriple SeqTriple::operator + (const SeqTriple& x)
{
SeqTriple temp;
int k=0;
if((x.rows!=rows)||(x.cols!=cols))
cout<<"Size error"<else
{
temp.cols=cols;
temp.rows=rows;
for(int i=0,j=0;(i  {
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
const SeqTriple SeqTriple::operator * (const SeqTriple& 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{
for(;j {
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  {
   ++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
istream& operator >> (istream& in,SeqTriple& x)
{
string input1,input2,input3;
int i=0;
int cols=0;
int rows=0;
cout<<"please input the row number value in SeqTriple"<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
ostream& operator << (ostream& out,const SeqTriple& x)
{

out<<"the SeqTriple contains:"<for(int i=0;i{
 out< out< out<}
return out;
}

int main()
{

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