顺序三元组.cpp

矩阵的一些算法应用

#include "iostream.h"
#define MAXSIZE 12500
typedef int ElemType;
typedef struct {
	int i,j;
	ElemType e;
}Triple;
typedef struct 
{
	Triple data[MAXSIZE];
	int m,n,t;
}SMtrix;
//三元组顺序表的初始化
void Minit(SMtrix &M)
{M.m=M.n=M.t=0;
}
//输出稀疏矩阵（二维形式）
void matrixprint(SMtrix M)
{

int i,j,k,flag=0;
for(i=1;i<=M.m;i++)
{    
	for(j=1;j<=M.n;j++)
{        for(k=1;k<=M.t;k++)
	 	 if(M.data[k].i==i&&M.data[k].j==j)
		 {cout<<M.data[k].e<<"  ";
		flag=1; break;}
		if(!flag) cout<<"0"<<"  ";
		 flag=0;
}
cout<<endl;      
}
}

//建立三元组存储
void createm(SMtrix &M)
{int k;
cout<<"enter 输入行数、列数和非零元素个数：";
cin>>M.m>>M.n>>M.t;
cout<<"请按行、列、非零元素值的顺序输入："<<endl;
for(k=1;k<=M.t;k++)
cin>>M.data[k].i>>M.data[k].j>>M.data[k].e;
}
//求转置
void transmatrix(SMtrix a,SMtrix &b) 
   { 
     int p,q,col; 
     b.m=a.n; 
     b.n=a.m; 
     b.t=a.t; 
     if(b.t<=0) 
         cout<<"A=0"<<endl; 
      q=1; 
for(col=1;col<=a.n;col++) 
        for(p=1;p<=a.t;p++) 
         if(a.data[p].j==col){ 
             b.data[q].i=a.data[p].j; 
             b.data[q].j=a.data[p].i; 
             b.data[q].e=a.data[p].e; 
             q++; 
            } 
    } 
//快速转置
void fasttranstri(SMtrix &b,SMtrix a)
{ 
    int p,q,col,k; 
    int num[1000],cpot[1000]; 
    b.m=a.n; b.n=a.m; b.t=a.t; 
    if(b.t<=0) 
        cout<<"a=0"<<endl; 
	else
	{
    for(col=1;col<=a.n;++col) 
             num[col]=0; 
    for(k=1;k<=a.t;++k) 
            ++num[a.data[k].j]; 
  cpot[1]=1; 
   for(col=2;col<=a.t;++col) 
         cpot[col]=cpot[col-1]+num[col-1]; 
   for(p=1;p<=a.t;++p)
   { 
      col=a.data[p].j;  q=cpot[col]; 
      b.data[q].i=a.data[p].j;  b.data[q].j=a.data[p].i; 
       b.data[q].e=a.data[p].e;  ++cpot[col]; 
    } 
	}
} 


//输出稀疏矩阵的三元组表
void print(SMtrix M)
{
	cout<<"稀疏矩阵的三元组表"<<endl;
cout<<"稀疏矩阵共有"<<M.m<<"行，"<<M.n<<"列"<<endl;
cout<<"行"<<"  "<<"列"<<"  "<<"元素值"<<endl;
for(int i=1;i<=M.t;i++)
    cout<<M.data[i].i<<"  "<<M.data[i].j<<"  "<<M.data[i].e<<endl;
}

void main()
{
	SMtrix a,b;
	Minit(a);Minit(b);
	createm(a);
	matrixprint(a);
	cout<<endl;
	print(a);
//	transmatrix(a,b);
//	matrixprint(b);
//		print(b);
		fasttranstri(b,a);
	    matrixprint(b);
	//			print(b);
	//	cout<<endl;
	//	matrixprint(a);
}