creatematrix.cpp

稀疏矩阵 1、 应用程序 直接可以实现矩阵的各项操作。 2、 查看原代码VC++6.0打开“稀疏矩阵creatematrix.dsp”或者用记事本打开“稀疏矩阵creatematrix

// creatematrix.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream.h>

#define MAXSIZE 100

struct triple 
{
	int row,col,val;
};

struct tsmat//三元组顺序结构体
{  

    triple data[MAXSIZE+1];
    int mu,nu,tu;
};
 int temp[3];
///////////////////////////////////////////////////////////////////////////////
struct matnode  //十字链表节点的结构体
{
	int row,col;
	struct matnode *right,*down;
	union 
	{
		int val;
		struct matnode *next;
	} tag;
};

  int m,n;

struct matnode *createmat()//十字链表创建稀疏矩阵
{
	int t,i,s,r,c,v;
	struct matnode *h[100],*p,*q;
	 cout<<"<---------------------------->"<<endl;
	 cout<<"    请输入矩阵的信息:"<<endl;
	cout<<"请输入矩阵行数mu，列数nu，非零个数tu."<<endl;
	cin>>m>>n>>t;
	p=new matnode;
	h[0]=p;
	
	p->row=m;
	p->col=n;
	s=m>n?m:n;
	
	for(i=1;i<=s;i++)
	{
		p=new matnode;
		h[i]=p;
		h[i-1]->tag.next=p;
		p->row=p->col=0;
		p->down=p->right=p;
	}

	h[s]->tag.next=h[0];
	

	for(i=1;i<=t;i++)
	{
		cout<<"请输入第"<<i<<"元素的行号row,列号col,与该元素的值val:"<<endl;
			cin>>r>>c>>v;
	
		p=new matnode;
		p->row=r;
		p->col=c;
		p->tag.val=v;
		q=h[r];

		while(q->right!=h[r]&&q->right->col<c)
			q=q->right;

		p->right=q->right;
		q->right=p;

		q=h[c];

		while(q->down!=h[c]&&q->down->row<r)
			q=q->down;

		p->down=q->down;
		q->down=p;
	}
	return(h[0]);


}


void prmat(struct matnode *hm)//输出十字链表稀疏矩阵
{   
	struct matnode *q,*p;
	int i,j,k;
	cout<<"row="<<hm->row<<endl;
	cout<<"col="<<hm->col<<endl;

     p=hm->tag.next;

	k=1;
	while(p!=hm)
	{    
	q=p->right;
	while(p!=q)
		{
        cout<<"第"<<k<<"个元素:";
		cout<<"row="<<q->row<<", "<<"col="<<q->col<<", "<<"val="<<q->tag.val<<"; "<<endl;
			q=q->right;
             k++;
		}
         p=p->tag.next;
	}
 /////////////////////////////////////////////////////
	 cout<<"<---------------------------->"<<endl;
      cout<<"稀疏矩阵:"<<endl<<endl;
        p=hm->tag.next;
		for(i=1;i<=m;i++)
		{
			q=p->right;
			
			for(j=1;j<=n;j++)
			{
				if(q->col==j)
				{
					cout<<"   "<<q->tag.val;
					q=q->right;
				}
				else
					cout<<"   0";
			}
			cout<<endl<<endl;
			p=p->tag.next;
		}

}
///////////////////////////////////////////////////////////////////////////////

   

void printsmat(tsmat &T,int t)//输出三元组顺序稀疏矩阵
{  
	int i,j,k;
    
	cout<<endl<<endl<<"   row="<<T.mu<<endl;
	cout<<"   col="<<T.nu<<endl<<endl;

	for(j=1;j<=t;j++)
	{   cout<<"第"<<j<<"个元素: ";
		cout<<"row="<<T.data[j].row<<",";
		cout<<"col="<<T.data[j].col<<",";
		cout<<"val="<<T.data[j].val<<";"<<endl;
	}


        cout<<endl;
	    cout<<"稀疏矩阵:"<<endl;

	     j=1;
		for(i=1;i<=T.mu;i++)
		{
			for(k=1;k<=T.nu;k++)
			{
				if(T.data[j].col==k&&T.data[j].row==i)
				{
					cout<<"   "<<T.data[j].val;
					j++;
				}
				else
					cout<<"   0";
			}
			cout<<endl<<endl;
		}
}

 int locate(tsmat &T, int i)//查找输入元素所应该在的矩阵位置
{
	int j;
	for(j=1;j<i;j++)
	{
		if(T.data[j].row>T.data[i].row)
			return(j);
		else 
			if(T.data[j].row==T.data[i].row)
			{
				if(T.data[j].col>T.data[i].col)
					return(j);
				else 
					if(T.data[j].col<T.data[i].col)
						return(j+1);
			}
	}
	return 1;
}

int  createtsmat(tsmat &T)//创建三元组顺序稀疏矩阵
{  
	
    int m,n,t;
	cout<<"请输入行数mu，列数nu，非零个数tu:"<<endl;
	cin>>m>>n>>t;

	T.mu=m;
    T.nu=n;
	T.tu=t;

	T.data[0].row=T.data[0].col=T.data[0].val=0;
       int r,c,v,i,j,pos;

	for(i=1;i<=t;i++)
	{
		cout<<"请输入第"<<i<<"个元素的行号row，列号col，数值val"<<endl;
        cin>>r>>c>>v;
		T.data[i].row=r;
		T.data[i].col=c;
		T.data[i].val=v;
/////////////////////////////////////////////////////////////////////////
		
		if(T.data[i].row<T.data[i-1].row||T.data[i].row==T.data[i-1].row)
		{  
			pos=locate(T,i);
/////////////////////////////////////////////
			 temp[0]=T.data[i].row;
	         temp[1]=T.data[i].col;
	          temp[2]=T.data[i].val;
/////////////////////////////////////////////
			for(j=i-1;j>=pos;j--)
			{
				T.data[j+1].row=T.data[j].row;
                T.data[j+1].col=T.data[j].col;
	            T.data[j+1].val=T.data[j].val;
			}
////////////////////////////////////////////////
                    T.data[pos].row=temp[0];
	             T.data[pos].col=temp[1];
	             T.data[pos].val=temp[2];
///////////////////////////////////////////////			
		}
		else 
		{}
	}
    
          printsmat(T,t);//输出稀疏矩阵	
	return 1;
}
               
//////////////////////////////////////////////////////////////////////////
int transpose(tsmat &A)//求稀疏矩阵的转置矩阵
{
	tsmat M;
	M.mu=A.nu;
	M.nu=A.mu;
	M.tu=A.tu;

	int q,col;

   
	q=1;
		
		for(col=1;col<=A.nu;++col)
		{
			for(int p=1;p<=M.tu;++p)
			{
				if(A.data[p].col==col)
				{
					M.data[q].col=A.data[p].row;
					M.data[q].row=A.data[p].col;
					M.data[q].val=A.data[p].val;
				    ++q;
				}
				
								
			}

		}
   
		cout<<"<---------------------------->"<<endl;
		cout<<"          转置矩阵为:"<<endl;
		printsmat(M,M.tu);
		
	return 1;
}


////////////////////////////////////////////////////////////////////

int matadd(tsmat &A,tsmat &B)// 三元组稀疏矩阵的加法
{   
	tsmat C;
	int i,j,k;
	i=1;j=1;k=1;

	while(i<=A.tu&&j<=B.tu)        
	{   
		 if(A.data[i].row==B.data[j].row)
		{	if(A.data[i].col<B.data[j].col)
			{
				C.data[k].row=A.data[i].row;
				C.data[k].col=A.data[i].col;
				C.data[k].val=A.data[i].val;
				
				k++;
				i++;
			}
		    else
			   if(A.data[i].col>B.data[j].col)
				{
					C.data[k].row=B.data[j].row;
					C.data[k].col=B.data[j].col;
					C.data[k].val=B.data[j].val;

					k++;
					j++;
				}
		    else
			    if(A.data[i].col=B.data[j].col)
				{
					C.data[k].row=B.data[j].row;
					C.data[k].col=B.data[j].col;
					C.data[k].val=A.data[i].val+B.data[j].val;
					
					if(C.data[k].val!=0)
                          k++;

					i++;
					j++;
				}
		}
		
		else
			if(A.data[i].row<B.data[j].row)
			{
                C.data[k].row=A.data[i].row;
				C.data[k].col=A.data[i].col;
				C.data[k].val=A.data[i].val;

				k++;
				i++;
			}
		else
			if(A.data[i].row>B.data[j].row)
			{
				C.data[k].row=B.data[j].row;
				C.data[k].col=B.data[j].col;
				C.data[k].val=B.data[j].val;

				k++;
				j++;
			}
	
			
	}     
	while(i<=A.tu)
	{
		C.data[k].row=A.data[i].row;
		C.data[k].col=A.data[i].col;
		C.data[k].val=A.data[i].val;
		  ++i;
		  ++k;
	}
	while(j<=B.tu)
	{
		C.data[k].row=B.data[j].row;
		C.data[k].col=B.data[j].col;
		C.data[k].val=B.data[j].val;
		++j;
		++k;
	}
	        C.mu=A.mu;
			C.nu=A.nu;
			C.tu=k-1;
            
			cout<<"<------------------------------>"<<endl;
			cout<<"         两矩阵之和为:"<<endl;
	        printsmat(C,C.tu);
	      
       return 1;
}
    
   

///////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{  

	int option,loop2;
   loop2=1;
	option=0;
		while(loop2)
	{
sign1:	loop2=0;
		cout<<"<-----------稀疏矩阵---------->"<<endl;
		cout<<"<============MENU============>"<<endl;
		cout<<"        1、十字链表法"<<endl;
		cout<<"        2、三元组顺序"<<endl;
        cout<<"        3、退出本程序"<<endl;
		cout<<"<============================>"<<endl;
		//用户界面
		cout<<"请输入您的选择：(1~3)"<<endl;
		cin>>option;

		if(option==3)
			break;



   switch(option)
   {
   case 1:
	   { 	int select1,loop1;
     loop1=1;
	select1=0;
		while(loop1)
	{
		loop1=0;
		cout<<"<----------十字链表---------->"<<endl;
		cout<<"<============MENU============>"<<endl;
		cout<<"        1、建立与输入"<<endl;
		cout<<"        2、返回主菜单"<<endl;	
		cout<<"        3、退出本程序"<<endl;
		cout<<"<============================>"<<endl;
		//用户界面
		cout<<"请输入您的选择：(1~2)"<<endl;
		cin>>select1;

		if(select1==3)
			return 0;

		if(select1==2)
			goto sign1;

		switch(select1)
		{
		case 1:
              cout<<"<---------------------------->"<<endl;
			  cout<<"  您当前选的是:"<<"1、建立与输入"<<endl;
			 
              	struct matnode *hm;
          	  hm=createmat();
	           prmat(hm);
			 	break;
		
		default:
			cout<<"ERROR!! Your Selection Is Out Of The Menu!"<<endl;
			loop1=1;
			break;

		
		}

        		if(!loop1)
			{
			cout<<"<============MENU============>"<<endl;
			cout<<"    返回子菜单    请按1"<<endl;
			cout<<"    返回主菜单    请按2"<<endl;
			cout<<"    退出本程序    请按0"<<endl;
			cout<<"<============================>"<<endl;
			cin>>loop1;
			if(loop1==2)
				goto sign1;
		    
			}

		}

	   }

   case 2:
	   {
		   int select,loop;
            loop=1;
	     select=0;


		while(loop)
		{
		loop=0;
		cout<<"<--------三元组顺序表-------->"<<endl;
		cout<<"<============MENU============>"<<endl;
		cout<<"        1、矩阵转置"<<endl;
		cout<<"        2、矩阵加法"<<endl;
		cout<<"        3、返回菜单"<<endl;
		cout<<"        4、退出程序"<<endl;
		cout<<"<============================>"<<endl;
		//用户界面
		cout<<"请输入您的选择：(1~3)"<<endl;
		cin>>select;

		if(select==4)
			break;
		if(select==3)
			goto sign1;


		switch(select)
		{
		case 1:
              cout<<"<---------------------------->"<<endl;
			  cout<<"  您当前选的是:"<<"1、矩阵转置"<<endl;
			  cout<<"<---------------------------->"<<endl;
              tsmat A;
              createtsmat(A);
	          transpose(A);
			 	break;
		case 2: 
			  cout<<"<---------------------------->"<<endl;
		      cout<<"  您当前选的是:"<<"2、矩阵加法"<<endl;
			  cout<<"<---------------------------->"<<endl;
	          tsmat M,N;
			  cout<<"请输入第一个矩阵的信息:"<<endl;
	          createtsmat(M);
			  cout<<"<---------------------------->"<<endl;
			  cout<<"请输入第二个矩阵的信息:"<<endl;
              cout<<"(行号,列号与第一个矩阵完全一样)"<<endl;
			  cout<<"    mu="<<M.mu<<";"<<endl<<"    nu="<<M.nu<<";"<<endl;
              createtsmat(N);
         	  matadd(M,N);
              break;

		default:
			cout<<"ERROR!! Your Selection Is Out Of The Menu!"<<endl;
			loop=1;
			break;
		}
			if(!loop)
			{
			cout<<"<============MENU============>"<<endl;
			cout<<"    返回子菜单    请按1"<<endl;
			cout<<"    返回主菜单    请按2"<<endl;
			cout<<"    退出本程序    请按0"<<endl;
			cout<<"<============================>"<<endl;
			cin>>loop;
			if(loop==2)
				goto sign1;
		    
			}
		
	}

	
	   }
   }
}


   
return 0;


}