稀疏矩阵.cpp

自己看吧 太简单了我都没什么可说的了 站长我只是学生就学了C++ 没有别的可以上传得

#include<iostream.h>

typedef struct mnode//定义十字链表
{ int row,col;
  struct mnode*down,*right;
  union { int v;
          struct mnode*next;
		  
  } v_next;
}mnode,*mlink;


mlink  creatmlink()//用十字链表建立稀疏矩阵
{
	mlink h;
	mnode*p,*q;
	int i,j,m,n,t,v;
	cout<<"请输入稀疏矩阵的行数列数和非零元素的个数"<<endl;
	cin>>m>>n>>t;
	h=new mnode;                 //申请总头结点
	h->row=m;h->col=n;
    mnode* head[7];
	head[0]=h;
	for(int f=1;f<=6;f++)
	{ p=new mnode;
	  p->row=0;
	  p->col=0;
	  p->right=p;
	  p->down=p;
	  head[f]=p;
	  head[f-1]->v_next.next=p;
	}
	head[6]->v_next.next=h;
	cout<<"请顺次输入非零元素的行号列号及元素的数值"<<endl;
	for(int k=1;k<=t;k++)
	{ cin>>i>>j>>v;     //输入一个三元组
	  p=new mnode;
	  p->row=i;
	  p->col=j;
	  p->v_next.v=v;
	  q=head[i];
	  while(q->right!=head[i]&&q->right->col<j)
	  q=q->right;
	  p->right=q->right;   //插入
	  q->right=p;
	  q=head[j];
	  while(q->down!=head[j]&&q->row<i)     //按行号找位置
		  q=q->down;
	  p->down=q->down;
	  q->down=p;
	}
	return head[0];
}



void out_mlink(mlink h)//输出十字链表稀疏矩阵
{  cout<<"稀疏矩阵如下"<<endl;
   cout<<endl;int sum=0;int col1=0;
   mnode*p;mlink h1=h->v_next.next; 
   for(int i=1;i<=h->row;i++)
   {   
	   p=h1->right;
	   
	   while(col1+1<=h->col)
	   
	   {
		   while(p!=h1)
		   {
	        int k=p->col-sum;
		    sum=sum+k;
	        while(k>1)
			{cout<<" 0"<<" ";k--;col1++;}
	         if(p->v_next.v<0)
			 {cout<<p->v_next.v<<" ";}
			 else
			 {cout<<" "<<p->v_next.v<<" ";}	 
			 col1++;
	         p=p->right;
		   }
		   if(col1<h->col)
		   {cout<<" 0"<<" ";col1++;}
	   }
	   cout<<endl;h1=h1->v_next.next;col1=0;sum=0;
   }
}


mnode*find_jh(mlink h,int j)
{  mnode*p=h->right;
    for(int i=1;i<j;i++)
		p=p->right;
    return p;
}


mlink  add(mlink h1,mlink h2)//稀疏矩阵的相加算法
 {  int flag=1;
	mnode*p,*q,*pa,*pb,*ca,*cb,*q1;int x;
	if(h1->row!=h2->row||h1->col!=h2->col)
	{
		cout<<"这两个矩阵不同型不能相加"<<endl;
	    return NULL;
	}



		ca=h1->v_next.next;       //ca指向矩阵A中第一行表头结点
        cb=h2->v_next.next;    //cb指向矩阵B中第一行表头结点
	    do{
		   pa=ca->right;
		   q1=ca;
		   pb=cb->right;
	       while(pb->col!=0)
		   {
			   if(pa->col<pb->col&&pa->col!=0)
			   {  q1=pa;
			      pa=pa->right;
			   }
			  else
			  
				  if(pa->col>pb->col||pa->col==0)
				  {
					  p=new mnode;p->row=pb->row;
			          p->col=pb->col;
			          p->v_next.v=pb->v_next.v;
			          p->right=pa;
			          q->right=p;
                      pa=p;          //新结点插入*pa的前面
			          q=find_jh(h1,p->col);
				      while(q->down->row!=0&&q->down->row<p->row)
					  { q=q->down;
					    p->down=q->down;
				        q->down=p;
					    pb=pb->right;
					  }
				  }
				   else
				   {  x=pa->v_next.v+pb->v_next.v;
				      if(x==0)
					  {
						 q1->right=pa->right;
						 q=find_jh(h1,pa->col);
						 while(q->down->row<pa->row)
						 q=q->down;
						 q->down=pa->down;
						 delete pa;
						 pa=q1;
					  }
					  else
					  {
						 pa->v_next.v=x;
					     q1=pa;
					  }
					  pa=pa->right;
					  pb=pb->right;
				  }
				   
				 
		   }
		
	
	 
				  ca=ca->v_next.next;
				  cb=cb->v_next.next;
				  flag++;
		}while(flag<=6);
			  
			return h1;
	}




#define SMAX 10//定义三元组表示稀疏矩阵
typedef struct
{ int i;
  int j;
  int v;
}spnode;
typedef struct
{ int mu,nu,tu;
  spnode data[SMAX];
}spmatrix;

spmatrix*creat()//用三元组表示稀疏矩阵
{   spmatrix*p;int i,j,v;int k=0;int mu,nu,tu;
    p=new spmatrix;
	if(p)
	{
		cout<<"请顺次输入矩阵的行数列数和非零元素的个数"<<endl;
		cin>>mu>>nu>>tu;
		p->mu=mu;p->nu=nu;p->tu=tu;
		cout<<"输入非零元素的行号列号及元素的数值并以0 0 0结束"<<endl;
		cin>>i>>j>>v;
		
	    while(k<tu)
		{
	     p->data[k].i=i;
         p->data[k].j=j;
		 p->data[k].v=v;
		 k++;
	     cin>>i>>j>>v;
         
		}
	}
return p;
}
		

  


spmatrix*trans(spmatrix*a)//稀疏矩阵的转置
{  
	spmatrix*b;
	int p,col;
	b=new spmatrix;
	b->mu=a->mu;
	b->nu=a->nu;
	b->tu=a->tu;
	if(b->tu>0)
	{ int i=0;
	  for(col=1;col<=a->nu;col++)
		for(p=0;p<a->tu;p++)
			if(a->data[p].j==col)
			{
				b->data[i].i=a->data[p].j;
                b->data[i].j=a->data[p].i;
                b->data[i].v=a->data[p].v;
			    i++;
			}
			
	}
	return b;
}


void out_spmatrix(spmatrix*h)  //输出三元组形式的稀疏矩阵
{  int sum=h->tu;int i=1;int flag=1;
   while(i<=sum)
   {for(int k=1;k<=h->mu;k++)
   {
	   if(flag==0)
	   { for(int l=1;l<=h->tu;l++)
	     cout<<" 0"<<" ";
	     cout<<endl;
	   }
	    else
        cout<<endl;
        int j=0;flag=0;
        while(j<h->nu&&h->data[i-1].i==k)
	   {
		   while(h->data[i-1].j>j+1)
		   {cout<<" 0"<<" ";
            j++;
		   }
		   if(h->data[i-1].v>0)
           cout<<" "<<h->data[i-1].v<<" ";
		   else
		   cout<<h->data[i-1].v<<" ";i++;
		   j++;
		   if(h->data[i-1].i!=k)
		   while(j<h->nu)
		   {cout<<" 0"<<" ";j++;}
		  
			flag=1;   
	   
	   }
   
	 
   }
   }
}


  

void main()//主函数
{ mlink head1,head2,head3;spmatrix*head4,*head5;
	while(1)
	{
	 cout<<"                              稀疏矩阵的相关操作                        "<<endl;
   
      cout<<"                               1.创立稀疏矩阵                      "<<endl;
      cout<<"                               2.输出稀疏矩阵                      "<<endl;
      cout<<"                               3.稀疏矩阵相加                      "<<endl;
      cout<<"                               4.稀疏矩阵转置                      "<<endl;
      cout<<"                               5.退出程序                              "<<endl;
      int c;
      cin>>c;
      switch(c)
	  {  case 1:head1=creatmlink();break;
         case 2:out_mlink(head1);break;
	     case 3:{cout<<"请输入顺次相加的两个矩阵"<<endl;
		         head1=creatmlink() ;
		         head2=creatmlink();
			     head3=add(head1,head2);
				 cout<<"相加后的矩阵为："<<endl;
                 out_mlink(head3);

				}break;
		 case 4:{head4=creat();cout<<"转置前的矩阵为："<<endl;
			     out_spmatrix(head4);
			     head5=trans(head4);cout<<endl;
				 cout<<"转置后的矩阵为："<<endl;
				 out_spmatrix(head5);cout<<endl;
				}
				 break;
        case 5:cout<<"                      退出程序欢迎下次使用                 "<<endl;return;
	  }
	}
}