l5_2.cpp

《数据结构（C++描述）》-李根强-源代码

//稀疏矩阵的快速转置
#include <iostream.h>
const int maxsize=100;//定义非零元的最大数目
struct  node          //定义一个三元组  
 {           
int      i , j;         //非零元行、列号
int      v;             //非零元值
};  
struct   sparmatrix        //定义稀疏矩阵
{   
int rows,cols ;           //稀疏矩阵行\列数
int  terms;              //稀疏矩阵非零元个数
node data [maxsize];      //三元组表
};

void  fastrans(sparmatrix a,sparmatrix b)//稀疏矩阵的快速转置
{
	int pot[100],col,ano,bno;
b.rows=a.cols;  b.cols=a.rows;
b.terms=a.terms;
if   (b.terms>0)
{
	for(col=0;col<a.cols;col++)
		pot[col]=0;
	for(int t=0;t<a.terms;t++)
	{ col=a.data[t].j;
	  pot[col+1]=pot[col+1]++;
	}
	pot[0]=0;
	for(col=1;col<a.cols;col++)
		pot[col]=pot[col-1]+pot[col];
  for( ano=0;ano<a.terms;ano++)
  { col=a.data[ano].j;
    bno=pot[col];
  b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
b.data[bno].v=a.data[ano].v;
pot[col]=pot[col]+1;
}
}
cout<<"输出转置后的三元组表"<<endl; 
for(int i=0;i<a.terms;i++)
	 cout<<b.data[i].i<<"  "<<b.data[i].j<<"  "<<b.data[i].v<<endl;
 }
void main()
{ sparmatrix a,b;
cout<<"请输入稀疏矩阵的行、列数及非零元个数"<<endl;
 cin>>a.rows>>a.cols>>a.terms;
 cout<<"输出转置前的三元组表"<<endl;
 for( int i=0;i<a.terms;i++)
	 cin>>a.data[i].i>>a.data[i].j>>a.data[i].v;
 for(i=0;i<a.terms;i++)
	 cout<<a.data[i].i<<"  "<<a.data[i].j<<"  "<<a.data[i].v<<endl;
 fastrans( a,b);
}