excise2.cpp

在数据结构中实现两个一元多项式的相加、相减和相乘

//函数结果状态代码
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#define TRUE 1
#define FALSE 0
#define OK 1 
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

typedef struct PNode
{
	int coef;    //系数                       
	int exp;     //指数                    
	struct PNode *next;               
}PNode,*LinkPN;

void AddPolyn(LinkPN pa,LinkPN pb,LinkPN &pc)      //实现两个多项式相加
{
	PNode *qa,*qb,*qc,*q;
	qa=pa->next;
	qb=pb->next;
	qc=pc;
	while(qa&&qb)
	{
			if(qa->exp>qb->exp)
		{
			q=(LinkPN)malloc(sizeof(PNode));
            q->coef=qb->coef;
			q->exp=qb->exp;
			qb=qb->next;
			qc->next=q;
			q->next=NULL;
			qc=qc->next;
		}
		else if(qa->exp==qb->exp)
		{
            q=(LinkPN)malloc(sizeof(PNode));
			q->coef=qa->coef+qb->coef;
			q->exp=qa->exp;
			qa=qa->next;
			qb=qb->next;
			qc->next=q;
			q->next=NULL;
            qc=qc->next;
		}
		else
		{ 
			q=(LinkPN)malloc(sizeof(PNode));
            q->coef=qa->coef;
			q->exp=qa->exp;
			qa=qa->next;
			qc->next=q;
			q->next=NULL;
			qc=qc->next;
		}
	}
    while(qa)
	{
		q=(LinkPN)malloc(sizeof(PNode));
		q->coef=qa->coef;
		q->exp=qa->exp;
		qc->next=q;
		q->next=NULL;
		qc=qc->next;
		qa=qa->next;
	}

	while(qb)
	{
		q=(LinkPN)malloc(sizeof(PNode));
		q->coef=qb->coef;
		q->exp=qb->exp;
		qc->next=q;
		q->next=NULL;
		qc=qc->next;
		qb=qb->next;
	}

}
	
void SubtractPolyn(LinkPN &pa,LinkPN &pb,LinkPN &pc)        //实现两个多项式相减
{
	PNode *qa,*qb,*qc,*q;
	qa=pa->next;
	qb=pb->next;
	qc=pc;
	while(qa&&qb)
	{
		if(qa->exp>qb->exp)
		{
			q=(LinkPN)malloc(sizeof(PNode));
            q->coef=0-qb->coef;
			q->exp=qb->exp;
			qb=qb->next;
			qc->next=q;
			q->next=NULL;
			qc=qc->next;
		}
		else if(qa->exp==qb->exp)
		{
            q=(LinkPN)malloc(sizeof(PNode));
			q->coef=qa->coef-qb->coef;
			q->exp=qa->exp;
			qa=qa->next;
			qb=qb->next;
			qc->next=q;
			q->next=NULL;
            qc=qc->next;
		}
		else
		{
			q=(LinkPN)malloc(sizeof(PNode));
            q->coef=qa->coef;
			q->exp=qa->exp;
			qa=qa->next;
			qc->next=q;
			q->next=NULL;
			qc=qc->next;
		}
	}
    while(qa)
	{
		q=(LinkPN)malloc(sizeof(PNode));
		q->coef=qa->coef;
		q->exp=qa->exp;
		qc->next=q;
		q->next=NULL;
		qc=qc->next;
		qa=qa->next;
	}

	while(qb)
	{
		q=(LinkPN)malloc(sizeof(PNode));
		q->coef=0-qb->coef;
		q->exp=qb->exp;
		qc->next=q;
		q->next=NULL;
		qc=qc->next;
		qb=qb->next;
	}

}

void main()
{
	LinkPN pa,pb,pc1,pc2;                   //pa用来存储第一个多项式，pb存储第二个多项式，pc1、pc2存储两式之和和差
	PNode *qa1,*qb1,*qa2,*qb2,*qc;          //qa1、qa2分别指向pa、pb中的元素，qb1、qb2存储输入元素，qc用于和和差的输出
	int i,j;
	pa=(LinkPN)malloc(sizeof(PNode));
	pb=(LinkPN)malloc(sizeof(PNode));
	pc1=(LinkPN)malloc(sizeof(PNode));
	pc2=(LinkPN)malloc(sizeof(PNode));
	if(!pa||!pb||!pc1||!pc2)
		exit(OVERFLOW);
	qa1=pa;
	qb1=pb;
	pa->next=NULL;
	pb->next=NULL;
	cout<<"请输入第一个多项式的项数：";
	cin>>i;
	cout<<endl;
	cout<<"请按提示输入第一个多项式的系数项和指数项："<<endl;
	for(j=0;j<i;j++)
	{
		qa2=(LinkPN)malloc(sizeof(PNode));
		cout<<"第"<<j+1<<"项的系数：";
		cin>>qa2->coef;
		cout<<endl;
		cout<<"第"<<j+1<<"项的指数：";
		cin>>qa2->exp;
		cout<<endl;
		qa1=pa;
		if(pa->next==NULL)
		{
		  pa->next=qa2;
		  qa2->next=NULL;
		  qa1=qa1->next;
		}
         int flag=1;		
		while(qa1->next!=NULL&&flag)
		{
          if(qa1->next->exp>qa2->exp)
		  {
			  qa2->next=qa1->next;
			  qa1->next=qa2;
			  flag=0;
		  }
		  else 
			  if (qa1->next->exp==qa2->exp)
			  {
                 qa1->next->coef+=qa2->coef;
				 flag=0;
			  }
		  else
		      qa1=qa1->next;
		}
		if(flag)
		{
		  qa1->next=qa2;
		  qa2->next=NULL;
		}

	}

	cout<<"请输入第二个多项式的项数：";
	cin>>i;
	cout<<endl;
	cout<<"请按提示输入第二个多项式的系数项和指数项："<<endl;
	for(j=0;j<i;j++)
	{
		qb2=(LinkPN)malloc(sizeof(PNode));
		cout<<"第"<<j+1<<"项的系数：";
		cin>>qb2->coef;
		cout<<endl;
		cout<<"第"<<j+1<<"项的指数：";
		cin>>qb2->exp;
		cout<<endl;
        qb1=pb;
		if(pb->next==NULL)
		{
		  pb->next=qb2;
		  qb2->next=NULL;
		  qb1=qb1->next;
		}
	    int flag=1;
		while(qb1->next!=NULL&&flag)
		{
          if(qb1->next->exp>qb2->exp)
		  {
			  qb2->next=qb1->next;
			  qb1->next=qb2;
			  flag=0;
		  }
		  else 
			  if (qb1->next->exp==qb2->exp)
			  {
                 qb1->next->coef+=qb2->coef;
				 flag=0;
			  }
		  else
		      qb1=qb1->next;
		}
		if(flag)
		{
		  qb1->next=qb2;
		  qb2->next=NULL;
		}
	}

	cout<<"下面将输出两个多项式的和："<<endl;
	AddPolyn(pa,pb,pc1);
	qc=pc1->next;
	j=1;
	while(qc)
	{
		cout<<"第"<<j<<"项的系数："<<qc->coef<<endl;
		cout<<"第"<<j<<"项的指数："<<qc->exp<<endl<<endl;
		j++;
		qc=qc->next;
	}

	cout<<"下面将输出两个多项式的差："<<endl;
	SubtractPolyn(pa,pb,pc2);
	qc=pc2->next;
	j=1;
	while(qc)
	{
		cout<<"第"<<j<<"项的系数："<<qc->coef<<endl;
		cout<<"第"<<j<<"项的指数："<<qc->exp<<endl<<endl;
		j++;
		qc=qc->next;
	}
}

/*程序结果
请输入第一个多项式的项数：4

请按提示输入第一个多项式的系数项和指数项：
第1项的系数：3

第1项的指数：2

第2项的系数：2

第2项的指数：0

第3项的系数：4

第3项的指数：3

第4项的系数：1

第4项的指数：1

请输入第二个多项式的项数：5

请按提示输入第二个多项式的系数项和指数项：
第1项的系数：-5

第1项的指数：2

第2项的系数：-2

第2项的指数：4

第3项的系数：3

第3项的指数：0

第4项的系数：6

第4项的指数：3

第5项的系数：2

第5项的指数：1

下面将输出两个多项式的和：
第1项的系数：5
第1项的指数：0

第2项的系数：3
第2项的指数：1

第3项的系数：-2
第3项的指数：2

第4项的系数：10
第4项的指数：3

第5项的系数：-2
第5项的指数：4

下面将输出两个多项式的差：
第1项的系数：-1
第1项的指数：0

第2项的系数：-1
第2项的指数：1

第3项的系数：8
第3项的指数：2

第4项的系数：-2
第4项的指数：3

第5项的系数：2
第5项的指数：4

Press any key to continue*/