polynomial calculator.cpp

数据结构实验

#include <stdio.h>
#include <malloc.h>
#include <math.h>


typedef struct{
	double	coef;
	int		expn;
}ElemType;

typedef struct LNode{
	ElemType	data;
	struct		LNode *next;
}LNode, *LinkList;

void CreatPolyn(LinkList &P , int n);
void print(LinkList P);
int Compare(LinkList a, LinkList b);
void MultiPolyn(LinkList &Pa, LinkList &Pb);
void AddPolyn(LinkList &Pa, LinkList &Pb);
void MinuPolyn(LinkList &Pa, LinkList &Pb);

void main()
{
	int i,j,k;
	LinkList Pa,Pb;
p:	printf("***************************\n");
	printf("*   一元稀疏多项式计算器  *\n");
	printf("*                         *\n");
	printf("*       1:多项式相加      *\n");
	printf("*       2:多项式相减      *\n");
	printf("*       3.多项式相乘      *\n");
	printf("*          4:退出         *\n");
	printf("***************************\n\n");
	printf("请选择相应的操作:");
	scanf("%d",&k);
	if(k<4)
	{
		printf("请输入第一个多项式的项数 n1:");
		scanf("%d",&i);
		printf("输入其各项系数及指数:\n");
		CreatPolyn(Pa, i);
		printf("\n");
		print(Pa);
		printf("\n-----------------------------------");
		printf("\n请输入第二个多项式的项数 n2:");
		scanf("%d",&j);
		printf("输入其各项系数及指数:\n");
		CreatPolyn(Pb, j);
		printf("\n");
		print(Pb);
		printf("\n-----------------------------------");
	}
	switch(k)
	{
	case 1:
		AddPolyn(Pa, Pb);
		printf("\n计算结果:\n");
		print(Pa);
		printf("\n-----------------------------------\n");
		break;
	case 2:
		MinuPolyn(Pa, Pb);
		printf("\n计算结果:\n");
		print(Pa);
		printf("\n---------------------------------\n");
		break;
	case 3:
		MultiPolyn(Pa, Pb);
		printf("\n计算结果:\n");
		print(Pa);
		printf("\n---------------------------------\n");
		break;
	default:
		break;
	}
	if(k!=4)goto p;
}


void CreatPolyn(LinkList &P , int n)
{
	P = (LinkList)malloc(sizeof(LNode));
	P->next = NULL;
	LinkList h,q,p2;
	h=P;
	p2=h->next;
	P->data.coef=0.0;
	P->data.expn=n;
	int i;
	{
		q=(LinkList)malloc(sizeof(LNode));
		scanf("%lf%d",&q->data.coef,&q->data.expn);
		h->next = q; q->next = NULL;
	}
	for(i=1;i<=n-1;i++)
	{
		q=(LinkList)malloc(sizeof(LNode));
		scanf("%lf%d",&q->data.coef,&q->data.expn);
		if(q->data.coef)
		{
			h = P;
			p2 = h->next;
			while(p2)
			{
				if(q->data.expn == p2->data.expn)
				{
					p2->data.coef=p2->data.coef + q->data.coef;
					free(q);
					P->data.expn--;
					break;
				}
				else
					if(q->data.expn > p2->data.expn)
					{
						h->next = q;
						q->next = p2;
						h=q;break;
					} 
					else
						{h = h->next; p2 = h->next;}
			}
			if(p2==NULL)
			{h->next= q; 
			q->next=NULL;
			}
		}
	}
}



int Compare(LinkList a, LinkList b)
{
	if (a->data.expn < b->data.expn) return -1;
	if (a->data.expn > b->data.expn) return 1;
	return 0;
}


void AddPolyn(LinkList &Pa, LinkList &Pb)
{
	double sum;
	LinkList qa, qb, ha, hb, p;

	ha = Pa; hb = Pb;
	qa = ha->next; qb = hb->next;

	while(qa && qb)
	{
		switch(Compare(qa, qb))
		{
		case -1:
			hb->next = qb->next;
			p = ha->next;
			ha->next = qb;
			qb->next = p;
			qb = hb->next;
			qa = ha->next;
			break;

		case 0:
			sum = qa->data.coef + qb->data.coef;
			if(sum)
			{
				qa->data.coef = sum;
				ha = qa;
				Pb->data.expn--;
			}
			else
			{
				ha->next = qa->next;
				free(qa);
				Pa->data.expn--;
				Pb->data.expn--;
			}
			hb->next = qb->next;
			free(qb);
			
			qa = ha->next;
			qb = hb->next;
			
			break;

		case 1:
			ha = qa;
			qa = qa->next;
			break;
		}
	}
	if(qb)	ha->next = qb;
	Pa->data.expn = Pa->data.expn + Pb->data.expn;
	free(hb);
}


void MinuPolyn(LinkList &Pa, LinkList &Pb)
{
	LinkList p = Pb;
	while(p)
	{
		p->data.coef *= -1;
		p = p->next;
	}
	AddPolyn(Pa,Pb);
}


void print(LinkList P)
{
	LinkList current;
	current = P->next;
	if(!current)
	{
		printf("0");
	}
	else
		if(!current->data.coef)
		{
			printf("0");
		}
	else
	{
		if(current->data.expn)
		printf("%.1f * x^%d", current->data.coef, current->data.expn);
		else printf("%.1f", current->data.coef);
		while(current->next)
		{
			current = current -> next;
			if(current->data.coef>0)
			{if(current->data.expn)
			printf(" + %.1f * x^%d", current->data.coef, current->data.expn);
			else printf(" + %.1f", current->data.coef);
			}
			else
				if(!current->data.coef)continue;
			else
			{if(current->data.expn)
			printf(" - %.1f * x^%d", fabs(current->data.coef), current->data.expn);
			else printf(" - %.1f", current->data.coef);
			}
		}
	}
}


void MultiPolyn(LinkList &Pa, LinkList &Pb)
{
	LinkList pa = Pa,pb=Pb, p, q, r, s, t;

	r = p = (LinkList)malloc(sizeof(LNode));
	while(pa)
	{
		p->data.coef = pa->data.coef;
		p->data.expn = pa->data.expn;
		q = p;
		p = (LinkList)malloc(sizeof(LNode));
		q->next = p;
		pa = pa->next;
	}
	q->next = NULL;
	free(p);

	pa = Pa;
	t = s = (LinkList)malloc(sizeof(LNode));
	while(pa)
	{
		q = s;
		s = (LinkList)malloc(sizeof(LNode));
		q->next = s;
		pa = pa->next;
	}
	q->next = NULL;
	free(s);

	pa = Pa;
	while(pa)
	{
		pa->data.coef *= pb->data.coef;
		pa->data.expn += pb->data.expn;
		pa = pa->next;
	}

	pb = pb->next;
	while(pb)
	{
		p = r;
		s = t;
		while(p)
		{
			s->data.coef = p->data.coef * pb->data.coef;
			s->data.expn = p->data.expn + pb->data.expn;
			p = p->next;
			s = s->next;
		}
		AddPolyn(Pa,t);
		pb = pb->next;

		pa = r;
		t = s =(LinkList)malloc(sizeof(LNode));
		while(pa)
		{
			q = s;
			s =  (LinkList)malloc(sizeof(LNode));
			q->next = s;
			pa = pa->next;
		}
		q->next = NULL;
		free(s);
	}
}