zhuzhenyuansuan.cpp

稀疏矩阵程序源代码

#include<stdlib.h>
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<conio.h>

#define mamrrc  20   //最大的行列数;
#define mamrsize 100 //最大的非零元个数;
//非零元的结点定义
typedef struct lnode{
	int row,col;//row和col分别存储非零元的行下标列下标;
	int value;//非零元的值;
}triple;
//带行逻辑的稀疏矩阵定义
typedef struct {
	int mu,nu,tu;//矩阵的行数,列数,非零元个数;
	int rpos[mamrrc+1];//存放各行的第一个非零元在三元组里的位置;
	triple data[mamrsize+1];//三元组定义;
}rlsmatrimr;
//创建稀疏矩阵函数
void createsmatimr(rlsmatrimr &m)
{   
    int  k=1,flag=1,loop=0,i;
	int hum[mamrrc+1];
    cout<<"请输该距阵的行列数(小于20)"<<endl;
	cout<<"行数:";
	cin>>m.mu;
	for(i=1;i<=m.mu;i++)
		m.rpos[i]=0;
	cout<<"列数:";
    cin>>m.nu;
    cout<<"请按所在行,所在列,元素的值的顺序矩阵的非零元;中间用空格;"<<endl;
    cout<<"若输入结束请输入三个零作为标记;"<<endl;
	//动态获取矩阵的非零元信息
	while(flag)
	{
		cin>>m.data[k].row>>m.data[k].col>>m.data[k].value;
		if(m.data[k].row==0)
			flag=0;//非零元输入结束的标志;
		k++;//动态变化的三元组下标;
	}
	m.tu=k-2;
	//以下程序段实现了对矩阵的rpos数组的值的确定;
	for(i=1;i<=m.mu;i++) hum[i]=0;
	for(i=1;i<=m.tu;i++) ++hum[m.data[i].row]; //统计每一行的非零元个数;
	m.rpos[1]=1;
	for(i=2;i<=m.mu+1;i++) m.rpos[i]=m.rpos[i-1]+hum[i-1]; //当前行的第一个非零元的位置应为它上一的
}                                                          //第一个非零元的位置加上一行的非零元个数;
//把矩阵的三元组形式转化为通常的矩阵输出;
void printsmatimr(rlsmatrimr m)
{
	int result[mamrrc+1][mamrrc+1];
	int i,j;
	//初始化结果矩阵;
	for(i=1;i<=m.mu;i++)
        for(j=1;j<=m.nu;j++)
			result[i][j]=0;
	for(i=1;i<=m.tu;i++)//根据三元组的信息,对结果矩阵设置相应的值;
		result[m.data[i].row][m.data[i].col]=m.data[i].value;
	for(i=1;i<=m.mu;i++)
	{
		printf("| ");
        for(j=1;j<=m.nu;j++)
		   printf("%-5d",result[i][j]);
        cout<<"|"<<endl;
	}
}

//矩阵的加法和减法函数,其中以flag为标记,flag=1为加法,flag=-1为减法,并利用了行逻辑的信息;
void add_or_sub_smatimr(rlsmatrimr m,rlsmatrimr n,int flag)
{
	rlsmatrimr q;//结果矩阵;
	int sum,mr,nr,i=1;
	if(m.mu!=n.mu||m.nu!=n.nu||m.tu==n.tu==0){
		cout<<"两矩阵不符合做加法的法则!!";
		exit(0);
	}

    q.mu=m.mu;q.nu=m.nu;q.tu=0;//初始化结果矩阵;
	//以行为标记作运算;
    for(i=1;i<=m.mu;i++)
	{
	      //n矩阵的当前行没有非零元时;
	   if(m.rpos[i+1]-m.rpos[i]!=0&&n.rpos[i+1]-n.rpos[i]==0)
	   {
          for(mr=m.rpos[i];mr<m.rpos[i+1];mr++)
		  {
          q.tu++;
          q.data[q.tu]=m.data[mr];
		  
		  }
	   }
	    //n矩阵和m矩阵的当前行都有非零元时;
      if(m.rpos[i+1]-m.rpos[i]!=0&&n.rpos[i+1]-n.rpos[i]!=0)
	  {
		  mr=m.rpos[i];nr=n.rpos[i];
          while( mr<m.rpos[i+1]&&nr<n.rpos[i+1])
		  {  
			      //在同一行时利用列下标进行加减法的处理;
			 if(m.data[mr].col<n.data[nr].col)
			 {
			  q.tu++;
               q.data[q.tu]=m.data[mr];
              mr=mr+1;
			 }
			else if(m.data[mr].col>n.data[nr].col)
			 {
			  q.tu++;
              q.data[q.tu]=n.data[nr];
		      q.data[q.tu].value=flag>0?n.data[nr].value:-n.data[nr].value;
              nr=nr+1;
			 }
		  else	 if(m.data[mr].col==n.data[nr].col)
			 {
				 sum=m.data[mr].value+(flag>0?n.data[nr].value:-n.data[nr].value);
				 if(sum)
				 {
				 q.tu++;
                 q.data[q.tu]=n.data[nr];
		         q.data[q.tu].value=sum;
                 }
				 mr=mr+1;nr=nr+1;
			 }
		  }
		  //对当前行还有非零元时的处理;
		  while(mr<m.rpos[i+1])
	        {  
		     q.tu++;
		     q.data[q.tu]=m.data[mr];
			 mr++;
			}
         while(nr<n.rpos[i+1])
	       {  
		    q.tu++;
		    q.data[q.tu]=n.data[nr];
		    q.data[q.tu].value=flag>0?n.data[nr].value:-n.data[nr].value;
			 nr++;
		   }
		 }

	   //m矩阵的当前行没有非零元时;
      if(m.rpos[i+1]-m.rpos[i]==0&&n.rpos[i+1]-n.rpos[i]!=0)
	   {
       for(nr=n.rpos[i];nr<n.rpos[i+1];nr++)
		{
		  q.tu++;
          q.data[q.tu].row=n.data[nr].row;
		  q.data[q.tu].col=n.data[nr].col;
		  q.data[q.tu].value=flag>0?n.data[nr].value:-n.data[nr].value;
		}
		}
	  }
    if(flag>0)
  	 cout<<"两矩阵的和为:"<<endl;
	else
     cout<<"两矩阵差为:"<<endl;
    printsmatimr(q);
}

//矩阵的乘法运算;
void mul_smatimr(rlsmatrimr m,rlsmatrimr n)
{
  rlsmatrimr q;//结果矩阵的定义;
  int arow,brow,ccol,tp,t,i,j;
  int ctemp[mamrrc+1];
  if(m.nu!=n.mu) 
  {
	  cout<<"这两个矩阵不符合作乘法的法则!!";
	  exit(0);
  }
  q.mu=m.mu;q.nu=n.nu;q.tu=0;//初始化结果矩阵;
  
  if(m.tu*n.tu!=0)
  {
	 for(arow=1;arow<=m.mu;arow++)//以m矩阵的行数为循环的控制;
	 {
		 for(i=1;i<=n.nu;i++)//当前行的各累加器清零;
	        ctemp[i]=0;
		 q.rpos[arow]=q.tu+1;
		 if(arow<m.mu)
			 tp=m.rpos[arow+1];
		 else
			 tp=m.tu+1;
		 for(i=m.rpos[arow];i<tp;i++)//对m中当前行的每一个非零元进行处理;
		 {
			 brow=m.data[i].col;//得出对应元在n中的行号;
			 if(brow<n.mu)
				 t=n.rpos[brow+1];
			 else
				 t=n.tu+1;
			 for(j=n.rpos[brow];j<t;j++)
			 {
				 ccol=n.data[j].col; //乘积在结果矩阵中的列号;
				 ctemp[ccol]+=m.data[i].value*n.data[j].value;
				 cout<<"u="<<ctemp[ccol]<<endl;				
			 }
			
		 }  //以上的一次循环可求得q中的第arow行的非零元;
		 for(ccol=1;ccol<=q.nu;ccol++)//压缩存储该行的非零元;
		 {
			 if(ctemp[ccol])
			 {
				 if(++q.tu>mamrsize) exit(0);
				 q.data[q.tu].row=arow;
				 q.data[q.tu].col=ccol;
				 q.data[q.tu].value=ctemp[ccol];
			 }
		}
	 }
  }
  
  cout<<"两矩阵的乘积为:"<<endl;
  printsmatimr(q);
}
//主函数,实现对各功能函数的调用;
void main()
{
	int choice;
	int flag=100,flag1=0;
    rlsmatrimr A,B;
	
   while(flag)
	{
	cout<<"*****************欢迎使用稀疏矩阵运算器*****************"<<endl;
	cout<<"*                   请选择你要的运算                   *"<<endl;
	cout<<"*                        1.加法                        *"<<endl;
    cout<<"*                        2.减法                        *"<<endl;
	cout<<"*                        3.乘法                        *"<<endl;
	cout<<"*                        0.退出系统                    *"<<endl;
	cout<<"********************************************************"<<endl;
	cout<<"请选择你要的功能:";
	cin>>choice;
	if(choice!=0&&choice<4&&flag<100)
	{
		cout<<endl<<"是否运用原先的矩阵?是按1  / 否按0";
		cin>>flag1;
	}
	switch(choice)
	{
	case 1:if(flag1==0){
		   cout<<"创建矩阵一"<<endl;
		   createsmatimr(A);
           cout<<"创建矩阵二"<<endl;
           createsmatimr(B);
		   }
		   add_or_sub_smatimr(A,B,1);
		   break;
    case 2:if(flag1==0){
		   cout<<"创建矩阵一"<<endl;
		   createsmatimr(A);
           cout<<"创建矩阵二"<<endl;
           createsmatimr(B);
		   }
           add_or_sub_smatimr(A,B,-1);
		   break;
	case 3:if(flag1==0){
		   cout<<"创建矩阵一"<<endl;
		   createsmatimr(A);
           cout<<"创建矩阵二"<<endl;
           createsmatimr(B);
		   }
		   mul_smatimr(A,B);
		   break;
	case 0: exit(0);
	}
	flag--;
	flag1=1;
	}
}