实现两个多项式的加法 ---------------------------------优先队列版本
#include<iostream>
#include<queue>
#include<string>
using namespace std;
class Multiploy{
double x; //系数
int y; //指数
public:
Multiploy(double x,int y)
{
this->x =x;
this->y=y;
}
Multiploy()
{
}
double GetX(){return x;}
int GetY() const{return y;}
void setX(double x){this->x=x;}
void setY(int y){this->y=y;}
bool operator<(const Multiploy& M)const
{
if(M.GetY()<y) return true;
return false;
}
};
void main()
{
Multiploy m0[]={Multiploy(3,1),Multiploy(9,8),Multiploy(5,17),Multiploy(7,0)};
Multiploy m1[]={Multiploy(8,1),Multiploy(22,7),Multiploy(-9,8)};
priority_queue<Multiploy>pr0(m0,m0+4);
priority_queue<Multiploy>pr1(m1,m1+3);
priority_queue<Multiploy>pr;
//对上述两个多项式进行操作
Multiploy mu1,mu2;
while((!pr0.empty())&&(!pr1.empty()))
{
mu1=pr0.top();
mu2=pr1.top();
if(mu1.GetY()>mu2.GetY())
{
//mu2入队，
pr.push(mu2);
pr1.pop();
}
else if(mu1.GetY()<mu2.GetY())
{
pr.push(mu1);
pr0.pop();
}
else
{
double sumX=mu1.GetX()+mu2.GetX();
int sumY=mu1.GetY()+mu2.GetY();
mu1.setX(sumX);
mu1.setY(sumY);
if(mu1.GetX()!=0)
pr.push(mu1); //如果结果系数不为零，就将该节点压入队列中
pr0.pop();
pr1.pop();
}
}
while(!pr0.empty())
{
mu1=pr0.top();
pr.push(mu1);
pr0.pop();
}
while(!pr1.empty())
{
mu2=pr1.top();
pr.push(mu2);
pr1.pop();
}
while(!pr.empty())
{
Multiploy& m=pr.top();
cout<<m.GetX()<<"X^"<<m.GetY()<<endl;
pr.pop();
}
}
-------------------------------------------------数据结构 链表实现版
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct Node{
double x; //系数
int y; //指数
struct Node *next;
}Node;
typedef struct{
Node *head;
Node *tail;
}Link;
/**************************************
初始化链表
***************************************/
void InitLink(Link &L)
{
L.tail=L.head=(Node *)malloc(sizeof(Node));
if(!L.head) exit(0);
L.head->next=NULL;
}
/**************************************
创建多项式的函数
***************************************/
void CreatLink(Link &L,int n)
{
int y;
double x;
Node *p;
InitLink(L);
for(int i=0;i<n;i++)
{
cout<<"请输入多项式的系数和指数："<<endl;
cin>>x>>y;
p=(Node *)malloc(sizeof(Node));
p->x=x;
p->y=y;
//if() //按指数的顺序添加节点
p->next=NULL;
//将节点p插入链表的尾节点处
if(L.head->next==NULL) L.head->next=p; //如果链表为空，则变动头节点
else L.tail->next=p;
L.tail=p; //节点插入成功
}
}
/**************************************
判断多项式是否为空
***************************************/
bool Empty(Link& L)
{
if(L.head==L.tail) return true;
return false;
}
/**************************************
计算多项式的和
***************************************/
void AddPoly(Link& L1,Link& L2,Link& L3)
{
Node *pa,*pb,*pc;
pa=L1.head->next;
pb=L2.head->next;
pc=L3.head=L1.head;
while((pa!=NULL)&&(pb!=NULL))
{
if(pa->y==pb->y)
{
pa->x=pa->x+pb->x;
if(pa->x!=0)
{
pc->next=pa;
pc=pc->next; //节点后移
}
pa=pa->next;
pb=pb->next;
}
else if(pa->y<pb->y)
{
pc->next=pa;
pc=pc->next;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pc->next;
pb=pb->next;
}
}
if((pa==NULL)&&(pb==NULL)) //如果两链表同时计算完，则要将pc的next置空
{
L3.tail=pc;
pc->next=NULL;
}
if(pa!=NULL) pc->next=pa;
if(pb!=NULL) pc->next=pb;
}
/**************************************
输出多项式
***************************************/
void print(Link L)
{
Node *p;
p=L.head->next;
while(p)
{
cout<<p->x<<"X^"<<p->y<<" ";
p=p->next;
}
cout<<endl;
}
void main()
{
Link L1,L2,L3;
int n;
cout<<"请输入多项式L1的项数"<<endl;
cin>>n;
CreatLink(L1,n);
//print(L1);
cout<<"请输入多项式L2的项数"<<endl;
cin>>n;
CreatLink(L2,n);
AddPoly(L1,L2,L3);
print(L3);
}