// 稀疏矩陣.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include<malloc.h>
#include<iostream.h>
#define OVERFLOW -1
#define ERROR 0
#define OK 1
#define MAXSIZE 10000
#define MAXRC 100
typedef int ElemType;

typedef struct
{	
    int i;
	int j;
	ElemType e;
}Triple;

typedef struct
{
	Triple data[MAXSIZE+1];
	int rpos[MAXRC+1];
	int mu;
	int nu;
	int tu;
}RLSMatrix;

void PrintSMatrix(RLSMatrix);



void CreateSMatrix(RLSMatrix &M,int m,int n)
{

	
	cout<<"輸入矩陣的值"<<endl;
	 M.tu=0;
	int k=1;
    int p=1;
	int num[100];
	int i,j;
	ElemType e;
	M.mu=m;
	M.nu=n;
    M.rpos[1]=1;
	for(int z=1;z<=100;z++)num[z]=0;
	for(cin>>i>>j>>e;i!=0;cin>>i>>j>>e)
	{M.data[k].j=j;
	M.data[k].i=i;
	M.data[k].e=e;
	k++;
		}//for
	M.tu=k-1;

	for(int a=1;a<=M.tu;++a)++num[M.data[a].i];

	for(int b=2;b<=M.mu;++b)M.rpos[b]=M.rpos[b-1]+num[b-1];



}//CreateSMatrix


bool MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)
{

	int ctemp[100];

	int tp,t,ccol,brow,p,q,arow,lie;

	if(M.nu!=N.mu)return ERROR;

	Q.mu=M.mu;

	Q.nu=N.nu;

	Q.tu=0;

	if(M.tu*N.tu!=0)
	{
	for(arow=1;arow<=M.mu;++arow)
	{
       int w=arow;
            
		for(lie=1;lie<=N.nu;++lie)
			
			ctemp[lie]=0;
	
		  Q.rpos[arow]=Q.tu+1;
	
		 
			  if(arow<M.mu)tp=M.rpos[arow+1];

		  
		  else {tp=M.tu+1;}

		  
        

		  for(p=M.rpos[arow];p<tp;++p)
		  {
		      
			  
			  brow=M.data[p].j;
		
	  
		   if(brow<N.mu)t=N.rpos[brow+1];
	
		      else {
				  t=N.tu+1;
			  }//else

	    for(q=N.rpos[brow];q<t;++q)
		{
		  ccol=N.data[q].j;
	     
		  ctemp[ccol]+=M.data[p].e*N.data[q].e;
	
		}//for q;

			
	
		  }//for p;求得Q中第crow（＝arow）行的非零元

			  
		  
	//壓縮存儲
	for(ccol=1;ccol<=Q.nu;++ccol)

		if(ctemp[ccol])
		{
			Q.tu++;

			if(Q.tu>MAXSIZE)return ERROR;
		      
			   Q.data[Q.tu].i=arow;
		         
			     Q.data[Q.tu].j=ccol;

		           Q.data[Q.tu].e=ctemp[ccol];
		
		}//if

	
	
	}//for arow
	
	}//if

return OK;
}//MultSMatrix


void Rmove(RLSMatrix &M,int p)

{for(int a=M.tu+1;a>=p;a--)

{M.data[a].e=M.data[a-1].e;

M.data[a].i=M.data[a-1].i;

M.data[a].j=M.data[a-1].j;}

}


void Lmove(RLSMatrix &M,int p)

{for(int a=p;a<M.tu;a++)

{M.data[a].e=M.data[a+1].e;

M.data[a].i=M.data[a+1].i;

M.data[a].j=M.data[a+1].j;
}
}



bool PlusSMatrix(RLSMatrix &M,RLSMatrix N)
{


	int tp,t,p,q,arow,e;

	if(M.mu!=N.mu&&M.nu!=N.nu)return ERROR;

	
	if(M.tu*N.tu!=0)
	{
	for(arow=1;arow<=M.mu;++arow)
	
	{
       	
		  if(arow<M.mu)
			  
		  {
		   tp=M.rpos[arow+1];
		  
		   t=N.rpos[arow+1];
		  
		  }

		  else 
		  {tp=M.tu+1;
		   
		  t=N.tu+1;
		  }

		  for(p=M.rpos[arow],q=M.rpos[arow];p<tp||q<t;)

		  {int a=M.data[p].j;

		  int b=N.data[q].j;

		  if(a<b)p++;

		  else if(a>b)

		  {Rmove(M,p);

		  M.data[p].e=N.data[q].e;

		  M.data[p].i=N.data[q].i;

		  M.data[p].j=N.data[q].j;

		  M.tu++;

		  }

		  else 
		  
		  {e=M.data[p].e+N.data[q].e;
		  
		  if(e==0)
		  
		  { Lmove(M,p);M.tu--;}

		 
		  else M.data[p].e=e;

		  p++;
		  
		  q++;}//else 

		   while(p<tp)p++;

		  while(q<t)
			   
		  {Rmove(M,p);

		  M.data[p].e=N.data[q].e;

		  M.data[p].i=N.data[q].i;

		  M.data[p].j=N.data[q].j;

		  M.tu++;

		  q++;

		  }
		  
		  }//for q,p

		 

		  }//for arow
	}//if
			
return OK;
}	
		  





ElemType Search(RLSMatrix M,int i,int j)
{
	
	for(int k=1;k<=M.tu;k++)
		if(M.data[k].i==i&&M.data[k].j==j)
			return M.data[k].e;
		return 0;
}



void PrintSMatrix(RLSMatrix M)
{   

	
	ElemType Search(RLSMatrix ,int ,int);
	for(int i=1;i<=M.mu;i++)
	{for(int j=1;j<=M.nu;j++)
		{ElemType e=Search(M,i,j);
   printf("%d ",e);}
	cout<<endl;}

}



	


void main(int argc, char* argv[])
{
	RLSMatrix M,N,Q;
	int m,n;
	cout<<"請輸入第一個矩陣，先輸入行數m再輸入列數n"<<endl;
	cout<<"m=";
	cin>>m;
	cout<<"n=";
	cin>>n;
	CreateSMatrix(M,m,n);
    cout<<"第一個矩陣為："<<endl;
	PrintSMatrix(M);
	cout<<"請輸入第二個矩陣，先輸入行數m再輸入列數n"<<endl;
	cout<<"m=";
	cin>>m;
	cout<<"n=";
	cin>>n;
	CreateSMatrix(N,m,n);
	cout<<"第二個矩陣為："<<endl;
	PrintSMatrix(N);
	//MultSMatrix(M,N,Q);
	//cout<<"運算結果為："<<endl;
   // PrintSMatrix(Q);
	cout<<"M+N的結果為："<<endl;
	PlusSMatrix(M,N);
	PrintSMatrix(M);
    cout<<"press any key to contine:"<<endl;
    cin.get();
   
}