xp.cpp

该程序用于进行多项式的四则运算

#include<stdio.h>
#include<stdlib.h>
#define  SIZE  50
struct  dx
{
	float a;
	char ch;
	int b;
};
struct	stack
{
	int top;
	struct dx ele[SIZE];
};
void Makenull(stack *);
void Push(dx *,stack *);
void Pop(stack *);
void Input(dx *,stack *);
void Figure(stack *,stack *);
void Output(stack);
void Add(stack *,stack*);
void Cut(stack *,stack *);
void Mutiply(stack *,stack *);
void Devide(stack *,stack *);
void Bigsearch(dx *,stack *);
main()
{
	dx dxs1,dxs2;
	stack *p,*q,s1,s2;
	dx *e,*f;
	p=&s1;q=&s2;
	e=&dxs1;f=&dxs2;
	Input(e,p);
	Input(f,q);
	Figure(p,q);
	Output(s2);
	getchar();
	getchar();
	return 0;
}
void Makenull(stack *sl)//将栈置空
{
	sl->top=SIZE;
}
void Input(dx *dxs,stack *sr)//建立栈的内容
{
	int n,z,k,i;
	char c,choice;
	printf("你的多项式有几项 ");
	scanf("%d",&n);
	Makenull(sr);
	printf("请输入一个多项式的%d项,指数前加^区分 dxs=",n);
	for(i=0;i<=n-1;i++)		//时间复杂度为O(n)							
	{
		scanf("%d%c^%d",&z,&c,&k);
		dxs->a=(float)z; 
		dxs->ch=c;
		dxs->b=k;
		Push(dxs,sr);//压栈
	}
	printf("你要修改你的输入吗？(Y/N)");
	while(getchar()!='\n');
	choice=getchar();
	if(choice=='Y'||choice=='y')
		Input(dxs,sr);
}
void Push(dx *dxst,stack *str)//将数据压入栈中,时间复杂度为O(1)
{
	if(str->top==0)

		printf("栈满。\n");
	else
	{
		str->top=str->top-1;
		str->ele[str->top].a=dxst->a;
		str->ele[str->top].ch=dxst->ch;
		str->ele[str->top].b=dxst->b;
	}
}
void Pop(stack *sq)//弹栈,时间复杂度为O(1)
{
	if(sq->top==SIZE)
		printf("栈为空。\n");
	else
	{
		sq->top=sq->top+1;
	}
}	
void Output(stack s)//将保存于栈s中的结果输出
{
	int j,l;
	l=SIZE-s.top;
	stack *g;
	g=&s;
	printf("dxst=");
	for(j=0;j<=l-1;j++)//时间复杂度为O(l)
	{
		if(s.ele[s.top].a>0)
			printf("+");
		if(s.ele[s.top].a==0)//删除栈中空项
			Pop(g);
		else
		{
			printf("%2.3f*%c^%d",s.ele[s.top].a,s.ele[s.top].ch,s.ele[s.top].b);
			Pop(g);
		}
	}
	printf("\n");
}
void Figure(stack *s,stack *st)//进行四则运算
{
	char q,op;
	dx *u,dxs4;
	u=&dxs4;
	while(q!='n')
	{
		printf("你想进行什么运算？");	
		while(getchar()!='\n')
			;
		op=getchar();
		switch(op)
		{	
			case '+':
				Add(s,st);
				break;
			case '-':
				Cut(s,st);
				break;
			case '*':
				Mutiply(s,st);
				break;
			case '/':														
				Devide(s,st);
				break;
			default:
				printf("输入错误\n");
				break;
		}
				printf("还有多项式要输入吗?'n'退出。");
				while(getchar()!='\n');
				q=getchar();
				if(q!='n')
					Input(u,s);//再输入一个多项式并压入栈s中
	}
}
void Add(stack *sf,stack *dj)//加法，栈sf存储加数，栈dj存储被加数
{
	int  i,j,b;
	dx dxs3,*w;
	w=&dxs3;
	b=SIZE-sf->top;
    for(i=sf->top;i<=SIZE-1;i++)
	{
		for(j=dj->top;j<=SIZE-1;j++)
		{
			if(sf->ele[i].b==dj->ele[j].b)
			{
				dj->ele[j].a=sf->ele[i].a+dj->ele[j].a;
				sf->ele[i].a=0;
				break;
			}
		}
		if(sf->ele[i].a!=0)
		{
			dxs3.a=sf->ele[i].a;
			dxs3.ch=sf->ele[i].ch;
			dxs3.b=sf->ele[i].b;
			Push(w,dj);
		}
	}
}
void Cut(stack *zp,stack *gr)//减法运算
{
	int  i;
	for(i=zp->top;i<SIZE;i++)
		zp->ele[i].a=-zp->ele[i].a;
	Add(zp,gr);
}
void Mutiply(stack *ar,stack *br)//乘法，栈ar存储乘数，栈br存储被乘数
{
	int  i,j,m,v;
	dx dxs3,*w;
	stack *n,s3;
	w=&dxs3;n=&s3;
	Makenull(n);
	for(i=ar->top;i<=SIZE-1;i++)
	{	
		for(j=br->top;j<=SIZE-1;j++)
		{
			dxs3.a=ar->ele[i].a*br->ele[j].a;
			dxs3.ch=ar->ele[i].ch;
			dxs3.b=ar->ele[i].b+br->ele[j].b;
			Push(w,n);
		}
	}
	Makenull(br);
	while(n->top!=SIZE)//将结果进行同类项合并并将结果拷贝到栈st中
	{
		for(m=n->top;m<SIZE;m++)
		{
			for(v=m+1;v<SIZE;v++)
			{
				if(n->ele[m].b==n->ele[v].b)
				{
					n->ele[m].a=n->ele[m].a+n->ele[v].a;
					n->ele[v].a=0;
				}
			}
		}
		br->top=br->top-1;
		if(n->ele[n->top].a==0)//弹出空白项
			Pop(n);
		else
		{
			br->ele[br->top].a=n->ele[n->top].a;
			br->ele[br->top].ch=n->ele[n->top].ch;
			br->ele[br->top].b=n->ele[n->top].b;
			Pop(n);
		}
	}
}
void Devide(stack *cr,stack *er)//除法，栈cr存储除数，栈er存储被除数
{
	int t,x,m,n,k,sold;
	float so;
	dx dxs7,*kr,*jr,*vr;
	stack *ap,*num,*rest,s4,s5,s6;
	ap=&s4;kr=&dxs7;num=&s5;rest=&s6;
	Makenull(ap);
	Makenull(rest);
	jr=(dx *)malloc(sizeof(dx));//为jr申请内存
	Bigsearch(jr,er);
	vr=(dx *)malloc(sizeof(dx));
	Bigsearch(vr,cr);
	while(jr->b>=vr->b)
	{
		Makenull(num);
		so=dxs7.a=jr->a/vr->a;//so存储被除数最高项除于除数最高项的商
		dxs7.ch=jr->ch;
		sold=dxs7.b=jr->b-vr->b;//sold存储被除数与除数的差
		Push(kr,ap);
		for(t=cr->top;t<=SIZE-1;t++)//将除数的每一项乘于dxs7,dxs7为存储被除数除于除数得到的项
		{
			kr->a=so*cr->ele[t].a;
			kr->ch=cr->ele[t].ch;
			kr->b=sold+cr->ele[t].b;
			Push(kr,num);
		}
		for(m=s5.top;m<SIZE;m++)//用被除数减于上面for循环中得到的多项式
		{
			for(n=er->top;n<SIZE;n++)
			{
				if(er->ele[n].b==s5.ele[m].b)
				{
					er->ele[n].a=er->ele[n].a-s5.ele[m].a;
					if(er->ele[n].a<0.4)
					{
						er->ele[n].a=0;
						er->ele[n].b=-1;
					}
					dxs7.b=s5.ele[m].b;
					break;
				}
			}
			if(s5.ele[m].b!=dxs7.b)//将cr中不是er中任一项的同类项压入栈er中
			{
				dxs7.a=-s5.ele[m].a;
				dxs7.ch=s5.ele[m].ch;
				dxs7.b=s5.ele[m].b;
				Push(kr,er);
			}
		}
		Bigsearch(jr,er);
	}
	if(jr->b<vr->b)
	{
		for(k=er->top;k<SIZE;k++)
		{
			if(er->ele[k].b<vr->b&&er->ele[k].a!=0)
			{
				dxs7.a=er->ele[k].a;
				dxs7.ch=er->ele[k].ch;
				dxs7.b=er->ele[k].b;
				Push(kr,rest);
			}
		}
	}
	if(rest->top<SIZE)
	{
		printf("余数为");
		Output(s6);
	}
	Makenull(er);
	for(x=ap->top;x<SIZE;x++)//将存于栈ap中的商拷贝到栈er中以便输出
	{
		dxs7.a=ap->ele[x].a;
		dxs7.ch=ap->ele[x].ch;
		dxs7.b=ap->ele[x].b;
		Push(kr,er);
	}
}
void Bigsearch(dx *dxsp,stack *sp)//找出栈sp中指数最大的多项式
{
	int m;
	dxsp->a=sp->ele[sp->top].a;
	dxsp->b=sp->ele[sp->top].b;
	dxsp->ch=sp->ele[sp->top].ch;
	for(m=sp->top+1;m<SIZE;m++)
	{
		if(sp->ele[m].b>dxsp->b)
		{	
			dxsp->b=sp->ele[m].b;
			dxsp->a=sp->ele[m].a;
		}
	}
}