smatrix_ol_op.h

利用三元组顺序表表示稀疏矩阵

Status MultSMatrix_OL(CrossList M,CrossList N,CrossList &Q)
{   
	OLink p,q,r;
	int m,n;
	float total;
	if(M.nu!=N.mu) return ERROR;
	Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;
	if(!(Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink)))) return ERROR;
	if(!(Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink)))) return ERROR;
	for(m=1;m<=Q.mu;m++)
		Q.rhead[m]=NULL;
	for(n=1;n<=Q.nu;n++)
		Q.chead[n]=NULL;
	for(m=1;m<=Q.mu;m++)
	{  
		total=0.0;
		for(n=1;n<=Q.nu;n++)
		{   
			total=0.0;
			q=N.chead[n];
			p=M.rhead[m];
			while(p!=NULL&&q!=NULL)
			{
				if(q->i==p->j)
				{
					total+=q->e*p->e;
					p=p->right;
					q=q->down;
				}
				else if(p->j>q->i)
					q=q->down;
				else if(p->j<q->i)
					p=p->right;
			}//while
			r=(OLink)malloc(sizeof(OLNode));
			r->i=m;
			r->j=n;
			r->e=total;
			InsertNode_OL(Q,r);
		}//for n
	}//for m
    return OK;
}

Status AddSMatrix_OL(CrossList M,CrossList N,CrossList &Q)
{
	int i,j;
	OLink p,q,r;
	if(M.mu!=N.mu||M.nu!=N.nu) {printf("Matrix don't match!\n");return ERROR;}
	Q.mu=M.mu;Q.nu=M.nu;Q.tu=0;
	if(!(Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink)))) return ERROR;
	if(!(Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink)))) return ERROR;
    for(i=1;i<=Q.mu;i++)
		Q.rhead[i]=NULL;
	for(j=1;j<=Q.nu;j++)
		Q.chead[j]=NULL;
    for(i=1;i<=M.mu;i++)
	{
		p=M.rhead[i];
		q=N.rhead[i];
		while(p!=NULL||q!=NULL)
		{
			if(p==NULL)
				while(q!=NULL)
				{
					InsertNode_OL(Q,q);
					q=q->right;
				}//while q
			else if(q==NULL)
				while(p!=NULL)
				{
					InsertNode_OL(Q,p);
					p=p->right;
				}//while p
			else
			{
				if(p->j==q->j) 
				{if(p->e+q->e!=0.0)
					{
						r=(OLink)malloc(sizeof(OLNode));
						r->i=i;
						r->j=p->j;
						r->e=p->e+q->e;
						InsertNode_OL(Q,r);
						
					}
				    p=p->right;
					q=q->right;
				}
				else if(p->j<q->j)
				{InsertNode_OL(Q,p);
				 p=p->right;
				}
				else if(p->j>q->j)
				{InsertNode_OL(Q,q);
				 q=q->right;
				}
			}
		}//while
	}
	return OK;
}

Status SubSMatrix_OL(CrossList M,CrossList N,CrossList &Q)
{
	int i,j;
	OLink p,q,r;
	if(M.mu!=N.mu||M.nu!=N.nu) {printf("Matrix don't match!\n");return ERROR;}
	Q.mu=M.mu;Q.nu=M.nu;Q.tu=0;
	if(!(Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink)))) return ERROR;
	if(!(Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink)))) return ERROR;
    for(i=1;i<=Q.mu;i++)
		Q.rhead[i]=NULL;
	for(j=1;j<=Q.nu;j++)
		Q.chead[j]=NULL;
    for(i=1;i<=M.mu;i++)
	{
		p=M.rhead[i];
		q=N.rhead[i];
		while(p!=NULL||q!=NULL)
		{
			if(p==NULL)
				while(q!=NULL)
				{   r=(OLink)malloc(sizeof(OLNode));
					r->i=q->i;
					r->j=q->j;
					r->e=-q->e;
					InsertNode_OL(Q,r);
					q=q->right;
				}//while q
			else if(q==NULL)
				while(p!=NULL)
				{
					InsertNode_OL(Q,p);
					p=p->right;
				}//while p
			else
			{
				if(p->j==q->j) 
				{if(p->e-q->e!=0.0)
					{
						r=(OLink)malloc(sizeof(OLNode));
						r->i=i;
						r->j=p->j;
						r->e=p->e-q->e;
						InsertNode_OL(Q,r);
						
					}
				    p=p->right;
					q=q->right;
				}
				else if(p->j<q->j)
				{
					InsertNode_OL(Q,p);
					p=p->right;
				}
				else if(p->j<q->j)
				{
					r=(OLink)malloc(sizeof(OLNode));
					r->i=q->i;
					r->j=q->j;
					r->e=-q->e;
					InsertNode_OL(Q,r);
					q=q->right;
				}
			}
		}//while
	}
	return OK;
}

float HangLieShi_OL(CrossList M);

float YuZiShi_OL(CrossList M,int m,int n)
{
	CrossList B;
	OLink p,r;
	int i,j;
	float result;
	B.mu=M.mu-1;
	B.nu=M.nu-1;
	if(!(B.rhead=(OLink*)malloc((B.mu+1)*sizeof(OLink)))) return ERROR;
	if(!(B.chead=(OLink*)malloc((B.nu+1)*sizeof(OLink)))) return ERROR;
	for(i=1;i<=B.mu;i++)
		B.rhead[i]=NULL;
	for(j=1;j<=B.nu;j++)
		B.chead[j]=NULL;
	for(i=1;i<=M.mu;i++)
	{
		p=M.rhead[i];
		if(i<m)
			while(p!=NULL)
			{
				if(p->j<n)
					InsertNode_OL(B,p);
				else if(p->j>n)
				{
					r=(OLink)malloc(sizeof(OLNode));
					r->e=p->e;
					r->i=p->i;
					r->j=p->j-1;
					InsertNode_OL(B,r);
				}
				p=p->right;
			}//while p
		else if(i>m)
			while(p!=NULL)
			{
				if(p->j>n)
				{
					r=(OLink)malloc(sizeof(OLNode));
					r->e=p->e;
					r->i=p->i-1;
					r->j=p->j-1;
					InsertNode_OL(B,r);
				}
				else if(p->j<n)
				{
					r=(OLink)malloc(sizeof(OLNode));
					r->e=p->e;
					r->i=p->i-1;
					r->j=p->j;
					InsertNode_OL(B,r);
				}
				p=p->right;
			}//while p
	}//for i 
	result=HangLieShi_OL(B);
	return result;
}


float HangLieShi_OL(CrossList M)
{//求行列式
	int i,j;
	float result;
	OLink p;
	if(M.mu!=M.nu) {printf("Can't Solve this Matrix!\n");return 0;}
	p=M.rhead[1];
	i=1;
	result=0.0;
	if (M.mu==1&&M.nu==1) {
		if(p=M.rhead[1])
			return p->e;
		else 
			return 0.0;
	}
  	for(j=1;j<=M.nu;j++)
	{
		if(p!=NULL&&j==p->j)
		{
			if((i+j)%2==0)
				result+=p->e*YuZiShi_OL(M,1,j);
			else
				result+=(-1)*p->e*YuZiShi_OL(M,1,j);
			p=p->right;
		}
		else
			result+=0;
	}//for j
	return result;
}

Status InvSMatrix_OL(CrossList M,CrossList &Q)
{
	int i,j;
	float t,det;
	OLink p;
	if(M.mu!=M.nu){printf("Can't Invese this Matrix!\n");return ERROR;}
	Q.mu=M.mu;
	Q.nu=M.nu;
	Q.tu=0;
	if(!(Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink)))) return ERROR;
	if(!(Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink)))) return ERROR;
    for(i=1;i<=Q.mu;i++)
		Q.rhead[i]=NULL;
	for(j=1;j<=Q.nu;j++)
		Q.chead[j]=NULL;
	det=HangLieShi_OL(M);
	if(det==0.0) {printf("Invese don't exist!\n");return ERROR;}
	for(i=1;i<=Q.mu;i++)
		for(j=1;j<=Q.nu;j++)
		{
			if((i+j)%2==0)
				t=YuZiShi_OL(M,i,j)/det;
			else
				t=(-1)*YuZiShi_OL(M,i,j)/det;
			if(t!=0.0)
			{
				p=(OLink)malloc(sizeof(OLNode));
				p->i=i;
				p->j=j;
				p->e=t;
				InsertNode_OL(Q,p);
			}
		}
		return OK;
}