转置.cpp

关于数据结构中矩阵转置的算法。

#include<iostream.h>
#include<stdio.h>
#define maxsize 20
typedef struct{
	int i,j;
	int e;
}triple;
typedef struct{
	triple data[maxsize+1];
	int mu,nu,tu;
}tsmatrix;

void transposesmatrix(tsmatrix M,tsmatrix &T)
{   
    M.mu=5; M.nu=3;
	T.mu=M.nu ;T.nu =M.mu ;T.tu =M.tu ;
	int col,p,q;
	if(T.tu)
	{
		q=1;
		for(col=1;col<=M.nu;++col)
			for(p=1;p<=M.tu;++p)
				if(M.data [p].j==col)
				{
					T.data [q].i=M.data [p].j;
                    T.data [q].j=M.data [p].i;
					T.data [q].e=M.data [p].e;
					++q;
				}
	}
}
void fasttransposesmatrix(tsmatrix M,tsmatrix &T)
{
    M.mu=5; M.nu=3;
	T.mu=M.nu ;T.nu =M.mu ;T.tu =M.tu ;
	int col ,t,p,q,num[20],cpot[20];
   if(T.tu)
	{
	   for(col=1;col<=M.nu;++col)  num[col]=0;
			for(t=1;t<=M.tu;++t)   ++num[M.data[t].j];
			cpot[1]=1;
       for(col=2;col<=M.nu;++col)  cpot[col]=cpot[col-1]+num[col-1];
	        for(p=1;p<=M.tu;++p)
			{
				col=M.data [p].j;
				q=cpot[col];
	            T.data [q].i=M.data [p].j;
                T.data [q].j=M.data [p].i;
			    T.data [q].e=M.data [p].e;
				++cpot[col];
			}
	}
}


void main()
{
   tsmatrix M,T;
   int x,y,p=1;
   int m,n;
   int b[3][5]={0};
   int a[5][3]={{0,5,0},{6,0,0},{0,9,0},{0,3,7},{8,0,0}};
   cout<<"原始矩阵为："<<endl;
	for(x=0;x<5;x++)
	{
		for(y=0;y<3;y++)
		cout<<a[x][y]<<"    ";
		cout<<endl;
	}
   for(x=0;x<5;x++)
	{
		for(y=0;y<3;y++)
		if(a[x][y]!=0)
		{ 
			 
              M.data[p].i=x+1;
              M.data[p].j=y+1;
              M.data[p].e=a[x][y];
			  p++;
		}
   }
    M.tu=p-1;
   
   cout<<"原始矩阵的三元组数组为："<<endl;
  
    for(p=1;p<=M.tu;p++)
	{
		cout<<M.data[p].i<<"   "<<M.data[p].j<<"   "<<M.data[p].e;
		cout<<endl;
		
	}
  transposesmatrix(M,T);
  cout<<"转置后矩阵的三元组数组为："<<endl;
  for(p=1;p<=T.tu;p++)
	{
		cout<<T.data [p].i<<"   "<<T.data [p].j<<"   "<<T.data [p].e;
		m=T.data [p].i-1;
		n=T.data [p].j-1;
		b[m][n]=T.data [p].e;
		cout<<endl;
	}
  cout<<"快速转置后矩阵的三元组数组为："<<endl;
  fasttransposesmatrix(M,T);
  for(p=1;p<=T.tu;p++)
	{
		cout<<T.data [p].i<<"   "<<T.data [p].j<<"   "<<T.data [p].e;
	    cout<<endl;
	}
  cout<<"转置后的矩阵为："<<endl;
	for(x=0;x<3;x++)
	{   
   for(y=0;y<5;y++)
		cout<<b[x][y]<<"    ";
		cout<<endl;
	}
}