分析:对于一元多项式加减运算,我们直接从数学角度去思考这个问题,它的本质其实就是指数相同时系数进行加减运算,那么我们怎么知道指数是否相同呢?这是其实就是用到了比较的办法,我们把第一个多项式的每一项跟第二个多项式的每一项进行比较,得出结论进行运算。(这里我们的前提是每一个多项式的每一项的指数是不同的,意思是同一个多项式不存在同类项)
这里的多项式创建全部用的头插法
暴力破解
分析:回归到本质的运算中-----“比较”,那我们如何去比较是一个重要的问题,刚开始写我想到的就是暴力循环,也就是第一个多项式的每一项跟第二个多项式的每一项就行比较。在这里我们就能发现一个明显的问题,我们第一个跟第二个多项式进行比较之后我们可以得到两个式子相同的部分并进行一个加减操作,那么剩下的不相同的部分又该如何呢?我们拿一个式子进行举例:6x+4x2+3x4和3x+x2+2x5进行相加,首先第一轮6x跟3x比较,这里正好发现了与6x指数相同的项3x,那么得到6x与3x相加得到9x添加到新的链表中,这时候我们就直接跳出循环(因为前提我们已经说了这两个多项式的每一项的指数都是不同的,所以后面不会找到和6x一样的)。第二轮循环同理4x2和x2相加得到5x2添加到新的链表中。当3x4比较时我们会发现并没有和它可以进行运算,那么我们怎么把这项添加进去呢?也就是如何告诉计算机这时候应该添加进去了呢?我们分析可发现,如果第二个多项式有和第一个多项式指数一样的,第二个多项式一定是没有循环到链表尾部的,所以我们可以去判断第二个多项式有没有循环到链表尾去判断第一个多项式的某一项在第二个多项式中是否存在指数相同的一项,这样我们就可以把第一个多项式不可和第二个多项式和并的部分添加到新链表中去了。做到这我们又会发现,那第二个多项式不可和第一个多项式合并的部分呢?同理:我们是不是可以把第二个多项式的每一项和第一个多项式去比较,这个时候相同的部分直接用break跳出第二层循环(因为前面第一个多项式和第二个多项式进行比较时已经添加过了),然后再将第二个多项式的后面每一项以此类推与第一个多项式每一项比较,如果第二个多项式的某一项和第一个多项式的所有进行比较后都没有发现相同的,也就是来到了第一个多项式的链表尾,这时候就把第二个多项式的这项加入到新链表即可。
代码部分:
include<iostream>
using namespace std;
//多项式定义
typedef struct Dxs {
int xishu;
int zhishu;
Dxs *next;
}Dxs,*LinkDxs;
//初始化
void InitListDxs(LinkDxs &L){
L=new Dxs;
L->next=NULL;
}
//创建多项式
void CreateDxs(LinkDxs &L,int n){
LinkDxs p;
while(n){
p=new Dxs;
cin>>p->xishu;
cin>>p->zhishu;
p->next=L->next;
L->next=p;
n--;
}
cout<<"创建成功**"<<endl;
}
//打印多项式
void PrintDxs(LinkDxs L){
L=L->next;
if(L->zhishu==0)
cout<<L->xishu;
else
cout<<L->xishu<<"(x"<<"^"<<L->zhishu<<")";
L=L->next;
while(L){
if(L->xishu<0)
cout<<L->xishu<<"(x"<<"^"<<L->zhishu<<")";
else if(L->zhishu==0)
cout<<"+"<<L->xishu;
else
cout<<"+"<<L->xishu<<"(x"<<"^"<<L->zhishu<<")";
L=L->next;
}
cout<<endl;
cout<<"******************************"<<endl;
}
//多项式相加
void AddDxs(LinkDxs L1,LinkDxs L2){
LinkDxs add;
InitListDxs(add);
LinkDxs p;
LinkDxs f1=L1->next;
LinkDxs f2=L2->next;
LinkDxs L3;
L3=L1->next;
LinkDxs L4;
L4=L2->next;
L1=L1->next;
L2=L2->next;
while(L1){
L2=f2;
while(L2){
if(L1->zhishu==L2->zhishu){
if(L1->xishu+L2->xishu==0){
break;
}else{
p=new Dxs;
p->xishu=L1->xishu+L2->xishu;
p->zhishu=L1->zhishu;
p->next=add->next;
add->next=p;
}
break;
}
L2=L2->next;
}
if(!L2){
p=new Dxs;
p->xishu=L1->xishu;
p->zhishu=L1->zhishu;
p->next=add->next;
add->next=p;
}
L1=L1->next;
}
while(L4){
L3=f1;
while(L3){
if(L3->zhishu==L4->zhishu){
break;
}
L3=L3->next;
}
if(!L3){
p=new Dxs;
p->xishu=L4->xishu;
p->zhishu=L4->zhishu;
p->next=add->next;
add->next=p;
}
L4=L4->next;
}
PrintDxs(add);
}
//多项式长度
int LengthDxs(LinkDxs L){
LinkDxs p;
int i=0;
p=L->next;
while(p){
i++;
p=p->next;
}
return i;
}
//多项式相减
void SubDxs(LinkDxs L1,LinkDxs L2){
LinkDxs sub;
InitListDxs(sub);
LinkDxs p;
LinkDxs f1=L1->next;
LinkDxs f2=L2->next;
LinkDxs L3;
L3=L1->next;
LinkDxs L4;
L4=L2->next;
L1=L1->next;
L2=L2->next;
while(L1){
L2=f2;
while(L2){
if(L1->zhishu==L2->zhishu){
if(L1->xishu==L2->xishu){
break;
}else{
p=new Dxs;
p->xishu=L1->xishu-L2->xishu;
p->zhishu=L1->zhishu;
p->next=sub->next;
sub->next=p;
break;