多项式加乘.cpp

实现了多项式的加法和乘法

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct LNode
{ float coef;
  int expn;
  struct LNode *next;
}LNode,*LinkList;
int CreatList(LinkList);                 
int ChangeOrder(LinkList ,int m);
void CCreatList(LinkList,int  );                    //乘法中新多项式的创建
void MultiL1L2(LinkList L1,LinkList L2,int n);
void AddL3L4(LinkList L1,LinkList L2);              //乘法中的加法调用
void AddL1L2(LinkList L1,LinkList L2);
int compare(int ,int );

int main()
{   LinkList L1=(LinkList)malloc(sizeof(LNode));            
    LinkList L2=(LinkList)malloc(sizeof(LNode));   //建立两个链表头指针
    int m=0,n=0;
	cout<<"说明："<<endl;
    cout<<"1.多项式的系数在前，指数在后，中间空格，即a b"<<endl;
    cout<<"2.每输入完一项请按回车."<<endl;
	cout<<"3.结束标志为-100000000 -100000000,表示该项无效！"<<endl;
	cout<<endl;
    cout<<"第一个多项式:"<<endl;
    m=CreatList(L1);
	m=ChangeOrder(L1,m);    // 多项式L1排序
    cout<<"第二个多项式:"<<endl;
    n=CreatList(L2);
	n=ChangeOrder(L2,n);     // 多项式L2排序
    MultiL1L2(L1,L2,n);
    AddL1L2(L1,L2);
   
	return 0;
}
int CreatList(LinkList L3)   //创建两个多项式,
{  
	int i; int k=0;
    float a=0.0; int b=0;
	LNode *p,*q;
    p=(LNode*)malloc(sizeof(LNode));
    L3->next=p;
	for(i=1;i<=100;i++)
	{   k++;        
		cout<<"请输入多形式的第"<<k<<"项："<<endl;
	    cin>>a;
        cin>>b;
		if(a==0)
		{cout<<endl;
		  cout<<"该项为0无意义,请重新输入"<<endl;k--; 
		  cout<<endl;
		  continue;}
		p->coef=a;
        p->expn=b;
		if(b==-100000000)    // 多项式终止符号
		{ cout<<"该多项式第"<<k<<"项无效,该多项式终止输入!!!"<<endl;
		  cout<<"该多项式共"<<k-1<<"项"<<endl;break;}  
        q=p;
		p=(LNode*)malloc(sizeof(LNode));
		q->next=p;
	}
	free(p);
	q->next=NULL;
	return k;                //返回新建多项式的项数
}

int ChangeOrder(LinkList L,int m)       //实现对指数无序多项式的排序
{
	LNode *p,*q,*r;
	int i=0;
	m=m-1;   //需排序的最多次数
	r=L;
    do
	{
		r=L;
		p=L->next;      //p为第一项的指针                       
		q=p->next;      //q为第二项的指针
		while(p&&q)     //实现两项指数比较，大的排后
		{
			switch(compare(p->expn,q->expn))
			{
			case -1:q=q->next;p=p->next;r=r->next;break;
			case 0:p->coef=p->coef+q->coef;
				   if(p->coef==0)  {r->next=q->next;p=r->next;q=p->next;break;}
					q=q->next;p->next=q;break;
			case 1:r->next=q;p->next=q->next;q->next=p;q=p->next;r=r->next; break;
			}
		}
     m--;  //控制比较次数
	}while(m);
	r=L->next;
    cout<<endl;
	cout<<"排序后的多项式："<<endl;
	while(r)
	{     
		i++;
		cout<<r->coef<<" "<<r->expn<<endl;
	    r=r->next;

	} 
	cout<<endl;
	return i;
		
}

void MultiL1L2(LinkList L1,LinkList L2,int n)  //实现多项式相乘
{   LinkList L3,L4;
    LNode *p1,*p2,*p3,*p4;
	p1=L1->next;                              //p1代表L1中的每项
	p2=L2->next;                              
   	L3=(LinkList)malloc(sizeof(LNode));    
	CCreatList(L3,n);                     //被加多项式L3的建立 
	p3=L3->next;
	L4=(LinkList)malloc(sizeof(LNode));   
    CCreatList(L4,n);                      //加多项式L4的建立
	
	while(p2)                             //L3各基项的建立过程
	{
		p3->coef=p1->coef*p2->coef;
		p3->expn=p1->expn+p2->expn;
		p2=p2->next;
		p3=p3->next;
	}                 
	p1=p1->next;           //转到第一个多项式的第二项，
	p2=L2->next;
	p4=L4->next;
	while(p1)                  //第一个多项式中第二项及其后每项的遍历 被乘项
	{
		while(p2)             //第二多项式中的每一项遍历  乘项
		{
			p4->coef=p1->coef*p2->coef;   
			p4->expn=p1->expn+p2->expn;
			p2=p2->next;
			p4=p4->next;
		}
		AddL3L4(L3,L4);   //基项与新构项的相加 
		p1=p1->next;
		p2=L2->next;
        CCreatList(L4,n);  //重建新的多项式L4,为新的加多项式准备
		p4=L4->next;
	}
	p3=L3->next;
	cout<<"请输出多项式的积："<<endl;
	while(p3)
	{	
	    cout<<"("<<p3->coef<<","<<p3->expn<<"),";
		p3=p3->next;
	}
    cout<<endl;
	
}

void CCreatList(LinkList L3,int n)     //创建新的链表存储乘积
{  
	int i;
	LNode *p,*q;
    p=(LNode*)malloc(sizeof(LNode));
    L3->next=p;
	for(i=1;i<=n;i++)
	{	q=p; 
	    p=(LNode*)malloc(sizeof(LNode));
		q->next=p;
	 }
	free(p);
	q->next=NULL;
}
void AddL3L4(LinkList L1,LinkList L2)   //乘法中的加法调用
{
	float sum;
    LNode *p1,*q1,*p2,*q2;
	q1=L1;
	q2=L2;
    p1=L1->next;
    p2=L2->next;
	while(p1&&p2)
	{
		switch(compare(p1->expn,p2->expn))   //指数比较
		{
		case -1: q1=p1;p1=p1->next;break;
		case 0: sum=p1->coef+p2->coef;
			if(sum!=0.0){p1->coef=sum;q1=p1;p1=p1->next;}
			else {p1=p1->next;q1->next=p1;}
			q2=p2;p2=p2->next;break;
		case 1: p2=p2->next;q1->next=q2->next;
			    q1->next->next=p1;q1=q1->next;q2->next=p2;break;
			    
		}
	}
	if(p2) q1->next=p2;
}


void AddL1L2(LinkList L1,LinkList L2)  //多项式相加的实现
{
	float sum;
    LNode *p1,*q1,*p2,*q2;
	q1=L1;
	q2=L2;
    p1=L1->next;
    p2=L2->next;
	while(p1&&p2)
	{
		switch(compare(p1->expn,p2->expn))
		{
		case -1: q1=p1;p1=p1->next;break;
		case 0: sum=p1->coef+p2->coef;
			if(sum!=0.0){p1->coef=sum;q1=p1;p1=p1->next;}
			else {p1=p1->next;q1->next=p1;}
			q2=p2;p2=p2->next;break;
		case 1: p2=p2->next;q1->next=q2->next;
			    q1->next->next=p1;q1=q1->next;q2->next=p2;break;
			    
		}
	}
	if(p2) q1->next=p2;
  
    q1=L1->next;
	cout<<"请输出多项式的和："<<endl;
	while(q1)
	{
		cout<<"("<<q1->coef<<","<<q1->expn<<"),";
		q1=q1->next;
	}
	cout<<endl;
}

int compare(int a,int b)      //指数比较调用函数
{
	if(a<b) return -1;
	else 
	{if(a==b) return 0;
	else return 1;}
}