多项式的相加

多项式的相加

一、案例分析

　　假如说我们现在有下面两个多项式：

　　①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;       //指数
    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.创建链表

采用尾插法创建链表。

具体实现参考我上篇博客：单链表的基本操作和实现https://www.cnblogs.com/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);    //将两个链表相加
    return 0;
}

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);    //将两个链表相加
    return 0;
}

三、运行结果

如有什么不对的地方，欢迎大家指正！

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/953-zjf/p/13860821.html