tmatrix.cpp

三元组表方法建立矩阵和基本操作.例如,相乘,相加,插入等.

#include <stdio.h>
#include"Tmatrix.h"
//产生稀疏矩阵A的三元组表示
void CreatTmatrix(struct TMatrix &T,Elemtype A[M][N])
{
	int k=0;
	for(int row=0;row<M;row++)
		for(int col=0;col<N;col++)
		{  if(A[row][col]!=0)
			{T.data[k].d=A[row][col];
		     T.data[k].r=row;
			 T.data[k].c=col;
			 k++;
			}
		}
		T.cols=N;
		T.rows=M;
		T.num=k;
 //printf("\t%d\t%d\t%d.........\n",T.rows,T.cols,T.num);
}




//三元组T中找到适当的位置k,将新值插入进去.
//先在三元组中找到适当的位置k(下标),将K~T.num-1(下标)元素后移1为,将指定元素插入到K(下标)处.
//    考虑插入位置存在情况(和不为0,直接加,否则,删除该元素节点),考虑插入位置不在改矩阵范围情况(扩大矩阵).
int InsertTmatrix(struct TMatrix &T,Elemtype x,int rs,int cs)
{
	int k=0;
	int i=0,j=0;
	Elemtype temp;
	while(rs-1>T.data[k].r&& k<T.num)//>
		k++;
	while(cs-1>T.data[k].c&& k<T.num)
		k++;
	if(T.data[k].r==rs-1&&T.data[k].c==cs-1)
	{//求和,若为0,删除.否则,相加
        temp=T.data[k].d+x;
		if(temp!=0)
			T.data[k].d=temp;
		else
		{
		  for(int m=k;m<=T.num-2;m++)
		  {
			  T.data[m].d=T.data[m+1].d;
			  T.data[m].r=T.data[m+1].r;
			  T.data[m].c=T.data[m+1].c;
		  }
		  //T.rows=T.data[T.num-2].r+1;
	      //T.cols=T.data[T.num-2].c+1;//a简单和符合实际其间,行列数不变.
		  T.num--;
		}
	}

	else
	{
		for(int m=T.num;m>=k+1;m--)
		{
			T.data[m].d=T.data[m-1].d;
			T.data[m].r=T.data[m-1].r;
			T.data[m].c=T.data[m-1].c;
		}
		T.data[k].d=x;
		T.data[k].r=rs-1;
		T.data[k].c=cs-1;
		T.num++;
		T.rows=T.rows>rs?T.rows:rs;
		T.cols=T.cols>cs?T.cols:cs;
		return 1;
	}
}

//删除指定位置元素.
int DelectTmatrix(struct TMatrix &T,int rs,int cs)
{   
	int k=0;
	while( k<T.num && T.data[k].r<rs-1 )
		k++;
	while( k<T.num && T.data[k].c<cs-1)
		k++;
	if(k==T.num)
	{printf("Can not find.\n");
	 return 0;
	}

	else if(T.data[k].r==rs-1&&T.data[k].c==cs-1)
	{
		for(int m=k;m<=T.num-2;m++)
		{
			T.data[m].d=T.data[m+1].d;
			T.data[m].r=T.data[m+1].r;
			T.data[m].c=T.data[m+1].c;
		}
		T.rows=T.data[T.num-2].r+1;
		T.num--;
		int colmax=0;
        for(m=1;m<T.num;m++)
        {
			if(T.data[m].c>colmax)
				colmax=T.data[m].c;
		}
		T.cols=colmax+1;
		return 1;
	}
}
			

//查找指定位置的元素的值
Elemtype ValueTmatrix(struct TMatrix &T,int rs,int cs)
{   
	int k=0;
	if(rs>T.rows||cs>T.cols||rs<=0||cs<=0)
	{printf("The parameter is wrong .\n");
	 return 0;
	}

	while(k<T.num && T.data[k].r<rs-1)
		k++;
	while(k<T.num && T.data[k].c<cs-1)
		k++;
	if(T.data[k].r==rs-1&&T.data[k].c==cs-1)
	{
       	return T.data[k].d;
	}
	else
		return 0;
}



//输出三元组运算算法.
void DispTmatrix(struct TMatrix &T)
{
 if(T.num==0)
	{printf("The matrix is all zeros.\n");
     return;
	}
  printf("\t%d\t%d\t%d\n",T.rows,T.cols,T.num);
  printf("     ........................ \n");
  for(int k=0;k<T.num;k++)
  {  
	  printf("\t%d\t%d\t%d\n",T.data[k].r,T.data[k].c,T.data[k].d);
  }
  printf("     ........................ \n");
}


//矩阵转置运算.
void TransTmatrix(struct TMatrix T,struct TMatrix &Tb)
{
	int k=0;
    if(T.num==0)
		printf("The matrix is empty.\n");
	else
	{
	 while(k<T.num)
	 {
	  for(int col=0;col<T.cols;col++)
		 for(int d=0;d<T.num;d++)
			 if(T.data[d].c==col)
			 {Tb.data[k].r=T.data[d].c;
			  Tb.data[k].c=T.data[d].r;
			  Tb.data[k].d=T.data[d].d;
			  k++;
			 }
	 }
	 Tb.cols=T.rows;
	 Tb.rows=T.cols;
	 Tb.num=T.num;
	}
}
	

//设计两个矩阵相加运算.
int AddTmatrix(struct TMatrix &A,struct TMatrix &B,struct TMatrix &C)
{
	int ka=0,kb=0,k=0;
	Elemtype temp;
	if(A.cols!=B.cols||A.rows!=B.rows)
	{printf("The parameter is wrong.\n");
	 return 0;
	}

	while(ka<A.num && kb<B.num)
	{
		if(A.data[ka].r<B.data[kb].r)
		{
			C.data[k].d=A.data[ka].d;
			C.data[k].r=A.data[ka].r;
			C.data[k].c=A.data[ka].c;
			k++;
			ka++;
		}
		else if(A.data[ka].r>B.data[kb].r)
		{ 
			C.data[k].d=B.data[kb].d;
			C.data[k].r=B.data[kb].r;
			C.data[k].c=B.data[kb].c;
            k++;
			ka++;
		}
		else
		{
			if(A.data[ka].c<B.data[kb].c)
			{
             C.data[k].d=A.data[ka].d;
			 C.data[k].r=A.data[ka].r;
			 C.data[k].c=A.data[ka].c;
			 k++;
			 ka++;
			}
			else if(A.data[ka].c>B.data[kb].c)
			{
	         C.data[k].d=B.data[kb].d;
			 C.data[k].r=B.data[kb].r;
			 C.data[k].c=B.data[kb].c;
             k++;
			 kb++;
			}
			else
			{
				temp=A.data[ka].d+B.data[kb].d;
				if(temp==0)
				{ka++;
				 kb++;
				}
				else
				{C.data[k].d=temp;
				 C.data[k].r=A.data[ka].r;
				 C.data[k].c=A.data[ka].c;
				 k++;
				 ka++;
				 kb++;
				}
			}
		}
	}
		if(ka<A.num)//A 有剩余
			while(ka<A.num)
			{
			 C.data[k].d=A.data[ka].d;
			 C.data[k].r=A.data[ka].r;
			 C.data[k].c=A.data[ka].c;
			 k++;
			 ka++;
			}

	  	else if(kb<B.num)
			while(kb<B.num)
			{
			 C.data[k].d=B.data[kb].d;
			 C.data[k].r=B.data[kb].r;
			 C.data[k].c=B.data[kb].c;
             k++;
			 kb++;
			}
        C.cols=A.cols;
		C.rows=A.rows;
		C.num=k;
		return 1;
}

//设计两个矩阵相乘的算法.
int MultTmatrix( struct TMatrix &A, struct TMatrix &B,struct TMatrix &C)
{   int k=0;
    if(A.cols!=B.rows)
	{
		printf("Wrong parameter.\n");
		return 0;
	}
	for(int i=0;i<A.rows;i++)
		for(int j=0;j<B.cols;j++)
		{ C.data[k].d=0;
		  for(int m=0;m<A.cols;m++)
		  {
			C.data[k].d=C.data[k].d+ValueTmatrix(A,i+1,m+1)*ValueTmatrix(B,m+1,j+1);
		  }
		  C.data[k].r=i;
          C.data[k].c=j;
		  if(C.data[k].d!=0)
			  k++;
		}
	C.num=k;
    C.rows=A.rows;
	C.cols=B.cols;
	return 1;
}