多项式的相加
多项式的相加
⼀、案例分析
  假如说我们现在有下⾯两个多项式：
  ①A(x)=3x2+4x5+5x3-x1
  ②B(x)=4x3+7x2+3x1
  这两个多项式在计算机中⽤链表的来存储
根据多项式相加的运算规则：对两个多项式中所有指数相同的项，对应系数想加，若其和不为零，则作为“和多项式”中的⼀项插⼊到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数较⼩的项插⼊到“和多项式”链表中去。“多项式”链表中的节点⽆需⽣成，⽽应该从两个多项式的链表中摘取。
⼆、案例实现
（⼀）代码分析
1.预处理部分
#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define ElemType int
int flag = 1;    //定义⼀个标志变量，来区分输出的F(x)
2.结构体
链表的每个节点都有三个，系数（data）、指数（index）和⼀个指针域（next）。
typedef struct Polyn    //定义⼀个结构体，包括三个成员变量
{
ElemType data;        //系数
ElemType index;      //指数printf怎么加endl
struct Polyn *next;  //结构体指针
}Polyn,*LinkList;
3.输出链表
输出链表是为了便于观察我们创建的链表，以及后⾯输出同类型和的链表。
  具体实现：①⾸先声明⼀个指针指向⾸元结点
      　②while，在p不为空的情况下按照多项式的形式输出节点，并按照系数的正负，分情况输出
void Printf_Polyn(LinkList L)  //输出链表
{
Polyn *p = L->next;        //定义⼀个指向⾸节点的指针
cout<<"F(x"<<flag<<")=";  //使输出美观
while(p)                  //while循环遍历链表，逐个输出
{
if(p->data > 0)      //判断系数是否为正，若为正数则加上"+"，负数的话，只需正常输出即可
{
cout<<"+"<<p->data<<"X^"<<p->index;
}
else cout<<p->data<<"X^"<<p->index;
p=p->next;            //指针下移
}
cout<<endl;
}
4.对链表进⾏排序
使⽤选择排序，对链表每个元素进⾏排序
  具体实现：①定义⼀个中间变量，便于后⾯的数据交换。
      　②排序时，⾸先取到第⼀个结点的指数，逐个与后⾯结点的指数⽐较，第⼆次⽤第⼆个结点的指数与后⾯结点指数⽐较，依次类推。
      　③如果前⾯的指数⽐后⾯的指数⼤，就交换，这样⽐下去即可实现排序
void Sort_Polyn(LinkList &L)    //使⽤选择法对链表进⾏排序
{  int temp_data,temp_index;    //定义⼀个中间变量，便于后⾯的数据交换
Polyn *k,*r,*p = L->next;
for(;p;p=p->next)            //从链表第⼀个节点开始，逐个与后⾯的节点⽐较
{
k = p;                  //k指向第⼀个节点的，⽐较完⼀轮之后，将会指向第⼆个节点，依次往后推
for(r=p->next;r;r=r->next)  //从第⼆节点值开始与k所指节点值进⾏⽐较，⽐较完⼀轮之后，就是第三节点与k⽐较，依次类推
{
if(k->index > r->index)  //如果k指向的节点的值⼤，就交换系数和指数
{
temp_index = r->index;
temp_data = r->data;
r->data = k->data;
r->index = k->index;
k->data = temp_data;
k->index = temp_index;
}
}
}
Printf_Polyn(L);              //输出链表
flag++;
}
5.创建链表
采⽤尾插法创建链表。
具体实现参考我上篇博客：单链表的基本操作和实现wwwblogs/953-zjf/p/LinkList.html
void Creat_Polyn(LinkList &L)      //尾插法创建链表
{
int n;                        //项数n
if(flag % 2)                  //为了使程序更直观⽽设⽴的标志变量
{
cout<<"现在输⼊第⼀个多项式"<<endl;
}
else cout<<"现在输⼊第⼆个多项式"<<endl;
cout<<"请输⼊你要创建的项数：";
cin>>n;                      //输⼊项数
Polyn *p,*r;                //⼀个新建节点的指针和⼀个尾指针
L = new Polyn;              //初始化头节点
L->next = NULL;
r = L;
cout<<"请输⼊系数和指数（系数和指数之间⽤空格隔开）:";
for(int j = 1;j <= n;j++)    //循环n次，每次新建⼀个节点
{
p = new Polyn;
cin>>p->data>>p->index;  //输⼊新节点的系数和指数
p->next = r->next;      //接尾
r->next = p;            //接头
r = p;                  //尾指针后移
}
}
6.链表的合并
基本的思想就是分别先定义两个指针分别指向两个链表，⾄于两个链表的和，可以新建⼀个链表来存放，
也可以直接⽤两个链表的其中⼀个来存储。我这⾥⽤的La存储，那么也需要⼀个指针来指向它，就是r。做好这些我们就可以来进⾏⽐较了，La中每个结点与Lb的每个结点进⾏⽐较，会出现三种情况，第⼀种：La的⼤于Lb，就将La的结点接到r上，然后指La的指针下移。第⼆种，La的⼩于Lb，就将Lb的结点接到r上，然后Lb的指针下移。第三种：La等于Lb，那就将两个结点之和相加，这时候先判断两个之和是否为0，不为0，就将两者之和赋给La的结点，并将该结点接上，然后删除Lb的节点。如果两者之和为0.则将两个节点都删除。
void Addit_Polyn(LinkList L1,LinkList L2)  //将两个链表相加的函数
{
Polyn *p1,*p2,*r,*s;          //定义四个结构体指针
p1 = L1->next;                //p1指向第⼀个链表
p2 = L2->next;                //p2指向第⼆个链表
r = L1;                        //r指向p1，p1指得链条接下来也将成为和的链表的
while(p1 != NULL&&p2 != NULL) //当p1、p2不指向空时，循环继续
{
if(p1->index < p2->index) //判断——如果p1的指数⼩于p2的指数，就将p1插到L1所指的链表
{
r->next = p1;
r = p1;
p1 = p1->next;      //指针p1下移
}
else if(p1->index > p2->index)//判断——如果p1的指数⼤于p2的指数，就将p2插到L1所指的链表
{
r->next = p2;
r = p2;
p2  = p2->next;    //指针p2下移
}
else if(p1->index == p2->index)      //判断——如果p1的指数等于p2的指数
{
if(p1->data + p2->data)//就先判断系数之和是否为0，如果不是0
{
p1->data = p1->data+p2->data;  //将p1、p2系数之和赋值给p1
r->next = p1;                  //p1接⼊L1
r = p1;                        //r后移
p1 = p1->next;                //p1后移
s = p2;                        //记录p2，记录之后，后⾯可以释放该节点
p2 = p2->next;                //记录之后，p2下移
delete s;                      //释放上⼀节点
}
else//如果p1、p2系数之和为0
{
s = p1;            //先分别⽤s记录p1、p2，p1、p2下移，再分别释放s，即删除了前⾯p1和p2相等的两个节点
p1 = p1->next;
delete s;
s = p2;
p2 = p2->next;
delete s;
}
}
r->next = NULL;      //结束循环时，先让链表和的链表的尾部指向空
}
if(p1 != NULL)          //判断剩余的p1是否为空
{
r->next = p1;        //如果剩余的p1不是空，就接到L1的后边
}
else if(p2!=NULL)      //判断剩余的p2是否为空
{
r->next = p2;      //如果剩余的p1不是空，就接到L1的后边
}
Printf_Polyn(L1);      //输出链表
}
7.主程序
⾸先新建两个链表头指针，然后只需分别调⽤上⾯的函数即可
int main()
{
LinkList La,Lb;        //定义两个链表指针
Creat_Polyn(La);      //创建链表La
Sort_Polyn(La);        //链表La排序
Merge_Polyn(La);
Creat_Polyn(Lb);      //创建链表Lb
Sort_Polyn(Lb);
Merge_Polyn(Lb);        //链表Lb排序
cout<<"合并之后的多项式为:";
Addit_Polyn(La,Lb);    //将两个链表相加
return0;
}
8.完整代码
#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define ElemType int
int flag = 1;            //定义⼀个标志变量，来区分输出的F(x)
typedef struct Polyn    //定义⼀个结构体，包括三个成员变量
{
ElemType data;        //系数
ElemType index;      //指数
struct Polyn *next;  //结构体指针
}Polyn,*LinkList;
void Printf_Polyn(LinkList L)  //输出链表
{
Polyn *p = L->next;        //定义⼀个指向⾸节点的指针
cout<<"F(x"<<flag<<")=";  //使输出美观
while(p)                  //while循环遍历链表，逐个输出
{
if(p->data > 0)      //判断系数是否为正，若为正数则加上"+"，负数的话，只需正常输出即可
{
cout<<"+"<<p->data<<"X^"<<p->index;
}
else cout<<p->data<<"X^"<<p->index;
p=p->next;            //指针下移
}
cout<<endl;
}
void Sort_Polyn(LinkList &L)    //使⽤选择法对链表进⾏排序
{  int temp_data,temp_index;    //定义⼀个中间变量，便于后⾯的数据交换
Polyn *k,*r,*p = L->next;
for(;p;p=p->next)            //从链表第⼀个节点开始，逐个与后⾯的节点⽐较
{
k = p;                  //k指向第⼀个节点的，⽐较完⼀轮之后，将会指向第⼆个节点，依次往后推
for(r=p->next;r;r=r->next)  //从第⼆节点值开始与k所指节点值进⾏⽐较，⽐较完⼀轮之后，就是第三节点与k⽐较，依次类推        {
if(k->index > r->index)  //如果k指向的节点的值⼤，就交换系数和指数
{
temp_index = r->index;
temp_data = r->data;
r->data = k->data;
r->index = k->index;
k->data = temp_data;
k->index = temp_index;
}
}
}
Printf_Polyn(L);              //输出链表
flag++;
}
void Creat_Polyn(LinkList &L)      //尾插法创建链表
{
int n;                        //项数n
if(flag % 2)                  //为了使程序更直观⽽设⽴的标志变量
{
cout<<"现在输⼊第⼀个多项式"<<endl;
}
else cout<<"现在输⼊第⼆个多项式"<<endl;
cout<<"请输⼊你要创建的项数：";
cin>>n;                      //输⼊项数
Polyn *p,*r;                //⼀个新建节点的指针和⼀个尾指针
L = new Polyn;              //初始化头节点
L->next = NULL;
r = L;
cout<<"请输⼊系数和指数（系数和指数之间⽤空格隔开）:";
for(int j = 1;j <= n;j++)    //循环n次，每次新建⼀个节点
{
p = new Polyn;
cin>>p->data>>p->index;  //输⼊新节点的系数和指数
p->next = r->next;      //接尾
r->next = p;            //接头
r = p;                  //尾指针后移
}
}
void Addit_Polyn(LinkList L1,LinkList L2)  //将两个链表相加的函数
{
Polyn *p1,*p2,*r,*s;          //定义四个结构体指针
p1 = L1->next;                //p1指向第⼀个链表
p2 = L2->next;                //p2指向第⼆个链表
r = L1;                        //r指向p1，p1指得链条接下来也将成为和的链表的
while(p1 != NULL&&p2 != NULL) //当p1、p2不指向空时，循环继续
{
if(p1->index < p2->index) //判断——如果p1的指数⼩于p2的指数，就将p1插到L1所指的链表
{
r->next = p1;
r = p1;
p1 = p1->next;      //指针p1下移
}
else if(p1->index > p2->index)//判断——如果p1的指数⼤于p2的指数，就将p2插到L1所指的链表
{
r->next = p2;
r = p2;
p2  = p2->next;    //指针p2下移
}
else if(p1->index == p2->index)      //判断——如果p1的指数等于p2的指数
{
if(p1->data + p2->data)//就先判断系数之和是否为0，如果不是0
{
p1->data = p1->data+p2->data;  //将p1、p2系数之和赋值给p1
r->next = p1;                  //p1接⼊L1
r = p1;                        //r后移
p1 = p1->next;                //p1后移
s = p2;                        //记录p2，记录之后，后⾯可以释放该节点
p2 = p2->next;                //记录之后，p2下移
delete s;                      //释放上⼀节点
}
else//如果p1、p2系数之和为0
{
s = p1;            //先分别⽤s记录p1、p2，p1、p2下移，再分别释放s，即删除了前⾯p1和p2相等的两个节点                p1 = p1->next;
delete s;
s = p2;
p2 = p2->next;
delete s;
}
}
r->next = NULL;      //结束循环时，先让链表和的链表的尾部指向空
}
if(p1 != NULL)          //判断剩余的p1是否为空
{
r->next = p1;        //如果剩余的p1不是空，就接到L1的后边
}
else if(p2!=NULL)      //判断剩余的p2是否为空
{
r->next = p2;      //如果剩余的p1不是空，就接到L1的后边
}
Printf_Polyn(L1);      //输出链表
}
int main()
{
LinkList La,Lb;        //定义两个链表指针
Creat_Polyn(La);      //创建链表La
Sort_Polyn(La);        //链表La排序
Merge_Polyn(La);
Creat_Polyn(Lb);      //创建链表Lb
Sort_Polyn(Lb);
Merge_Polyn(Lb);        //链表Lb排序
cout<<"合并之后的多项式为:";
Addit_Polyn(La,Lb);    //将两个链表相加
return0;
}
三、运⾏结果
如有什么不对的地⽅，欢迎⼤家指正！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。