addmin.c

数据结构程序

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define TURE 1
#define ERROR 0
#define OVERFLOW 0

typedef int Status;
typedef int ElemType;

typedef struct OLNode{
	int i,j;
	ElemType e;
	struct OLNode * right, * down;
}OLNode;

typedef struct OLinkr{
		int i,j;
		struct OLinkr * down;
		struct OLNode * right;
}OLinkr;

typedef struct OLinkc{
		int i,j;
		struct OLinkc * right;
		struct OLNode * down;
}OLinkc;

typedef struct{
	OLinkr * rhead;
	OLinkc * chead;
	int mu,nu,tu;
}CrossList;


CrossList * CreateSMatrix_OL(void){
	CrossList * M;
	int m,n,t,a,b;
	OLinkr * x;
	OLinkc * s;
	printf("请输入矩阵元素的行数（m）、列数（n）、非零元个数（t）\n");
	printf("   m,n,t: ");
	scanf("%d,%d,%d",&m,&n,&t);
	if(!(M=(CrossList *)malloc(sizeof(CrossList))))        //开辟指针整体-M空间
	{printf("内存空间分配失败！\n");exit(OVERFLOW);}
	M->mu=m; M->nu=n; M->tu=t;

	if(!(M->rhead=(OLinkr *)malloc(sizeof(OLinkr))))       //行头结点
	{printf("内存空间分配失败！\n");exit(OVERFLOW);}
	{
		M->rhead->i=0; M->rhead->j=0; M->rhead->down=NULL; M->rhead->right=NULL;
		x=M->rhead;
		for(a=1;a<=M->mu;a++)
		{
			if(!(x->down=(OLinkr *)malloc(sizeof(OLinkr))))
			{printf("内存空间分配失败！\n");exit(OVERFLOW);}
			x=x->down;
			x->right=NULL;
			x->j=0;
			x->i=a;
			x->down=NULL;
		}
	}

	if(!(M->chead=(OLinkc *)malloc(sizeof(OLinkc))))
	{printf("内存空间分配失败！\n");exit(OVERFLOW);}   //列头结点
	{
		M->chead->j=0; M->chead->i=0; M->chead->right=NULL; M->chead->down=NULL;
		s=M->chead;
		for(b=1;b<=M->nu;b++)
		{
			if(!(s->right=(OLinkc *)malloc(sizeof(OLinkc))))
			{printf("内存空间分配失败！\n");exit(OVERFLOW);}
			s=s->right;
			s->down=NULL;
			s->i=0;
			s->j=b;
			s->right=NULL;
		}
	}
	return M;
}//CreateSMatrix_OL


CrossList * InitSMatrix_OL(CrossList * M){
	int i,j,e,t=0;
	OLNode * p,* q;
	OLinkr * k, * x;
	OLinkc * l, * s;

	printf("请输入各非零元所在 行数（i），列数（j），值（e）\n ");
	printf("\ti,j,e: ");
	scanf("%d,%d,%d",&i,&j,&e);
	while(i!=0&&t<=M->tu)
	{				
		if(!(p=(OLNode *)malloc(sizeof(OLNode))))
		{printf("内存空间分配失败！\n");exit(OVERFLOW);}
		{p->i=i; p->j=j; p->e=e;}

		for(x=M->rhead->down; x!=NULL&&x->i!=p->i; x=x->down);
		k=x;
		if(k->right==NULL||(k->right->j)>(p->j))
			{p->right=k->right; k->right=p;}
		else{
			for(q=k->right; (q->right) && (q->right->j)<(p->j); q=q->right)
				;
			p->right=q->right;
			q->right=p;
		}

		for(s=M->chead->right; s!=NULL&&s->j!=p->j; s=s->right);
		l=s;
		if(l->down==NULL||(l->down->i)>(p->i))
			{p->down=l->down; l->down=p;}
		else{
			for(q=l->down; (q->down) && (q->down->i)<(p->i); q=q->down)
				;
			p->down=q->down;
			q->down=p;
		}

		t++;
		if(t>M->tu)
		{printf("        该矩阵初始化错误！\n");
		exit(ERROR);}

		printf("\ti,j,e: ");
		scanf("%d,%d,%d",&i,&j,&e);
	}
	return M;
}//InitSMatrix_OL(CrossList * M)


OLNode * colpred(int a,int b,CrossList * M){
	OLinkc * p;
	OLNode * q;
	for(p=M->chead->right;p!=NULL&&p->j!=b;p=p->right);
	if(p==NULL) printf("shuru ERROR!");
	q=p->down;
	if(q==NULL)return (OLNode *)p;
	while(q->down!=NULL&&q->down->i<a)
		q=q->down;
	return q;
}


CrossList * NagtiveSMatrix_OL(CrossList * M){
	OLinkr * r;
	OLNode * p;
	r=M->rhead->down;
	while(r!=NULL)
	{
		while(r->right!=NULL){
			p=r->right;
			p->e=-(p->e);
			p=p->right;
			if(p==NULL)break;
		}
		r=r->down;
	}
	return M;
}



CrossList * AddSMatrix_OL(CrossList * ha,CrossList * hb){
	OLinkr * x,* l;
	OLNode * p,* q,* pa,* n,* h;
	if(ha->mu!=hb->mu||ha->nu!=hb->nu)
	{printf("两个矩阵不是同类型的，不能相加！\n");
	exit(ERROR);}
	else
	{
		x=ha->rhead->down;
		l=hb->rhead->down;
		while(x!=NULL)
		{
			p=x->right;
			q=l->right;
			(OLinkr *)pa=x;
			while(q!=NULL&&q->j!=0)
				if(p!=NULL&&p->j<q->j)
				{
					pa=p;
					p=p->right;
				}
				else if(p==NULL||(p->j)>(q->j))
				{
					if(!(n=(OLNode *)malloc(sizeof(OLNode))))
					{printf("内存空间分配失败！\n");exit(OVERFLOW);}
					n->i=q->i;
					n->j=q->j;
					n->e=q->e;
					n->right=p;
					pa->right=n;
					pa=n;
					h=colpred(n->i,n->j,ha);
					n->down=h->down;
					h->down=n;
					q=q->right;
				}
				else
				{
					(p->e)+=q->e;
					if(p->e==0)
					{
						pa->right=p->right;
						h=colpred(p->i,p->j,ha);
						h->down=p->down;
						free(p);
					}
					else pa=p;
					p=p->right;
					q=q->right;
				}
				x=x->down;
				l=l->down;
		}
	}
	return ha;
}



CrossList * MultipleSMatrix_OL(CrossList * ha,CrossList * hb){
	CrossList * Q;
	int a,b;
	OLinkr * x,* r;
	OLinkc * s;
	OLNode * p,* q,* y,* N,* h;

	if(ha->nu!=hb->mu)
	{printf("两个矩阵类型不匹配，不能相乘！\n");
	exit(ERROR);}

	if(!(Q=(CrossList *)malloc(sizeof(CrossList))))
	{printf("内存空间分配失败！\n");exit(OVERFLOW);}
       Q->mu=ha->mu; Q->nu=hb->nu;

	if(!(Q->rhead=(OLinkr *)malloc(sizeof(OLinkr))))             //行头结点
	{printf("内存空间分配失败！\n");exit(OVERFLOW);}
	{
		Q->rhead->i=0; Q->rhead->j=0; Q->rhead->down=NULL; Q->rhead->right=NULL;
		x=Q->rhead;
		for(a=1;a<=Q->mu;a++)
		{
			if(!(x->down=(OLinkr *)malloc(sizeof(OLinkr))))
			{printf("内存空间分配失败！\n");exit(OVERFLOW);}
			x=x->down;
			x->right=NULL;
			x->j=0;
			x->i=a;
			x->down=NULL;
		}
	}

	if(!(Q->chead=(OLinkc *)malloc(sizeof(OLinkc))))
	{printf("内存空间分配失败！\n");exit(OVERFLOW);}   //列头结点
	{
		Q->chead->j=0; Q->chead->i=0; Q->chead->right=NULL; Q->chead->down=NULL;
		s=Q->chead;
		for(b=1;b<=Q->nu;b++)
		{
			if(!(s->right=(OLinkc *)malloc(sizeof(OLinkc))))
			{printf("内存空间分配失败！\n");exit(OVERFLOW);}
			s=s->right;
			s->down=NULL;
			s->i=0;
			s->j=b;
			s->right=NULL;
		}
	}

	x=ha->rhead->down;
	s=hb->chead->right;
	while(x!=NULL)
	{
	s=hb->chead->right;
		while(s!=NULL)
		{
			if(!(N=(OLNode *)malloc(sizeof(OLNode))))
			{printf("内存空间分配失败！\n");exit(OVERFLOW);}
			N->i=0;N->j=0;N->e=0;N->right=NULL;N->down=NULL;
			p=x->right;
			q=s->down;
			while(p!=NULL && q!=NULL)
			{
				N->i=p->i;N->j=q->j;
				if(p->j<q->i) p=p->right;
				else if(p->j>q->i) q=q->down;
				else
				{
					N->e=(N->e)+(p->e)*(q->e);
					p=p->right;
					q=q->down;
				}
			}
			if(N->e==0) free(N);
			else
			{
				h=colpred(N->i,N->j,Q);
				N->down=h->down;
				h->down=N;
				for(r=Q->rhead->down; r!=NULL&&r->i!=N->i; r=r->down);
				{
					if(r->right==NULL||(r->right->j)>(N->j))
					{N->right=r->right; r->right=N;}
					else
					{
						for(y=r->right; (y->right) && (y->right->j)<(N->j); y=y->right)
							;
						N->right=y->right;
						y->right=N;
					}
				}
			}
			s=s->right;
		}
		x=x->down;
	}
	return Q;
}//MultipleSMatrix_OL

 

void PrintSMatrix_OL(CrossList * M){
	ElemType T[8][8];
	CrossList * m;
	OLinkr * p;
	OLNode * q;
	int r,c,R,C;	
	m=M;
	R=m->mu;C=m->nu;
	for(r=0;r<R;r++){
		for(c=0;c<C;c++)
			T[r][c]=0;
	}
	for(p=m->rhead;p!=NULL;p=p->down){
		for(q=p->right;q!=NULL;q=q->right)
			T[(q->i)-1][(q->j)-1]=q->e;
	}
	for(r=0;r<R;r++){
		printf("-----------------  ");
		for(c=0;c<C;c++)
			printf("%4d",T[r][c]);
		printf("\n\n");
	}
}



int main()
{
	CrossList * M,* N;
	int s;
	printf("\t\t\t稀疏矩阵运算器\n\n");
	printf("姓名：李炜    学号（后四位）：4274     智能系——2007级\n\n");
	printf("请选择运算种类（1.矩阵加法 2.矩阵减法 3.矩阵乘法）： ");
	scanf("%d",&s);
	printf("\n");
	while(s)
	{
		switch(s)
		{
		case 1:
			M=CreateSMatrix_OL();
			printf("\n");
			M=InitSMatrix_OL(M);
			printf("                   您输入的矩阵为：\n");
			PrintSMatrix_OL(M);
			N=CreateSMatrix_OL();
			printf("\n");
			N=InitSMatrix_OL(N);
			printf("                   您输入的矩阵为：\n");
			PrintSMatrix_OL(N);
			M=AddSMatrix_OL(M,N);
			printf("*******************加法运算后所得矩阵为：\n");
			PrintSMatrix_OL(M);
			break;
		case 2:
	        M=CreateSMatrix_OL();
			printf("\n");
			M=InitSMatrix_OL(M);
			printf("                   您输入的矩阵为：\n");
			PrintSMatrix_OL(M);
			N=CreateSMatrix_OL();
			printf("\n");
			N=InitSMatrix_OL(N);
			printf("                   您输入的矩阵为：\n");
			PrintSMatrix_OL(N);
			N=NagtiveSMatrix_OL(N);
			M=AddSMatrix_OL(M,N);
			printf("*******************减法运算后所得矩阵为：\n");
			PrintSMatrix_OL(M);
			break;
		case 3:
			M=CreateSMatrix_OL();
			printf("\n");
			M=InitSMatrix_OL(M);
			printf("                   您输入的矩阵为：\n");
			PrintSMatrix_OL(M);
			N=CreateSMatrix_OL();
			printf("\n");
			N=InitSMatrix_OL(N);
			printf("                   您输入的矩阵为：\n");
			PrintSMatrix_OL(N);
			M=MultipleSMatrix_OL(M,N);
			printf("*******************乘法运算后所得矩阵为：\n");
			PrintSMatrix_OL(M);
			break;
		default:
			printf("运算类型输入错误！\n");
			exit(0);
		}
		printf("请选择运算种类（1.矩阵加法 2.矩阵减法 3.矩阵乘法）： ");
		scanf("%d",&s);
		printf("\n");
	}
	return 0;
}