• 数据结构题 3（一元多项式计算器）

    题目：

                                                    一元多项式运算器

    (1)建立多项式。

    (2)输出多项式。

    (3) +,两个多项式相加，建立并输出和多项式。

    (4) -,两个多项式相减，建立并输出差多项式。

    扩展:

    (5) *,多项式乘法。

    (6) ( ),求多项式的值。

    题解：

    一元多项式运算器的计算中包含加减法，其中一元多项式说明有多个项所以我们可以考虑结构体数组或者链表来存储该数据元素，如果使用结构体数组来存储该数据元素进行计算的话，即要保存其项的个数和各项的系数和指数，在运算加减法时则需要使用多重循环来寻找指数相同的项来进行加减法。但是本篇博客主要简介使用的方法是链表来进行一元多项式的运算。

    在创建链表时则需要考虑其链表中所要的值：指数、系数和指向下一个节点的指针。创建链表则需考虑如果输入的指数值相同则循环次数不加继续进行顺换里面的内容则需要使用的到结束语句continue。

    结构体的内容如下所示：

    1. typedef struct polynomial
    2. {
    3.     float Coef; //系数
    4.     int Index;   //指数
    5.     struct polynomial *next;
    6. } polynomial;

    在创建时需考虑是否可以写进链表的代码如下所示：

    如果指数相同则不写入链表继续进行数据的输入。

    1. while(cp->next && temp->Index > cp->next->Index)
    2.         {
    3.             cp = cp->next;    //找到链表结点的尾部，且指数是递增的
    4.         }
    5.         if(cp->next && temp->Index == cp->next->Index){     // 如果已经存在相同指数的多项式，跳出循环
    6.             continue;
    7.         }
    8.         temp->next = cp->next;
    9.         cp->next = temp;

    若链表输入的数据比下一个数据的指数要小于或等于的时候则跳出while循环进入判断语句if，如果该数据的指数与下一结点的指数相等的时候continue退出不将数据保存在链表之中，若比下一个结点的指数要小的时候则保存在下一个结点之前的位置。

    即如下图所示：

    相同时则不加入该链表之中即可。

     链表创建成功之后我们就可以开始实现其功能，例如一元多项式的加减法，加法与减法的思路大致相同，在此只对一元多项式的加法进行讲述，加法则需要找到指数相同的项相关系数相加即可完成加法的相关操作。创建一个加法的函数，不返回值，使用二级指针指向链表的地址，直接对链表进行修改即可。

    void AddPolyn(polynomial **pa, polynomial **pb);

     然后声明几个指针，其中两个指针分别指向链表的第一个数据，还有一个指针指向一个链表本身的头指针，然后声明一个循环当两个链表其中有一个空了之后退出该循环，首先判断指数的大小，因为我们创建的两个链表的指数都是升序排列的，在此将两个的链表最终和的结果存储在一个链表之中按照升序的方式排列，所以对两个链表的指数开始进行判断，如果指数小（且没有相同指数）的则首先进入结果链表之中，存入结果链表的指针向后移动一位再次与另一个指针指向的结点指数相比较，如果有相同的指数项存在则将其的指数相加然后存入结果链表之中，随后将指针都向后移动一个结点。然后当其中一个链表结束之后说明再也没有相同的指数出现因此我们可以把剩下的链表内容直接存储在结果链表之中。此加法的操作就结束了，一元多项式的减法操作与其相似只不过是把相同指数相加改为相减即可。

    完成上面操作的代码如下所示：

    1. void Add(polynomial **pa, polynomial **pb)
    2. {
    3.     polynomial *cpa, *cpb, *p = (*pa);
    4.     cpa = (*pa)->next;
    5.     cpb = (*pb)->next;
    6.     while(cpa && cpb)       //对每一项进行比较
    7.     {
    8.         if(cpa->Index < cpb->Index)
    9.         {
    10.             p->next = cpa;
    11.             p = cpa;
    12.             cpa = cpa->next;
    13.         }
    14.         else if(cpa->Index > cpb->Index)
    15.         {
    16.             p->next = cpb;
    17.             p = cpb;
    18.             cpb = cpb->next;
    19.         }
    20.         else
    21.         {
    22.             if(cpa->Coef + cpb->Coef == 0)
    23.             {
    24.                 cpa = cpa->next;
    25.                 cpb = cpb->next;
    26.  
    27.             }
    28.             else
    29.             {
    30.                 cpa->Coef += cpb->Coef;
    31.                 p->next = cpa;
    32.                 p = cpa;
    33.                 cpa = cpa->next;
    34.                 cpb = cpb->next;
    35.             }
    36.         }
    37.     }
    38.     if(cpa)
    39.         p->next = cpa;
    40.     else
    41.         p->next = cpb;
    42.     free(*pb);          //*pb已经为空，释放空间
    43. }

    但是减法与其不同的点在于如果减数的链表长度多余被减数的链表长度则不可以直接加入结果链表之中需要将其系数的符号进行改变再加入到结果链表之中。

    该操作的代码如下所示：

    1.     if(cpb){
    2.         p->next = cpb;
    3.         while(cpb){
    4.             cpb->Coef *= -1; // 改变系数的符号，将减数多项式的系数变为负的
    5.             cpb = cpb->next;
    6.         }
    7.     }

    在一元多项式的乘法之中我们利用的函数与其加法函数相同都是使用二级指针，直接对链表本身进行修改，每一项与另一项进行相乘，所以我们才函数开头需创建两个指针，其中一个指针指向链表的头指针，保存链表内容。在乘法进行之前还需要将内容保存在一个函数之中，即将链表内容完全复制在另一个链表中，将此链表重新初始化。然后让此复制的链表与另一链表进行相乘结果保存在复制链表之中，再与之前的链表相加即可得到结果。

    运行乘法的代码如下所示：

    1. void Multiply(polynomial **pa, polynomial **pb)
    2. {
    3.     polynomial *cpa, *ccpa;
    4.     cpa = *pa;                      //保存着原pa的内容
    5.     CreatePolyn(pa, 0);         //从新初始化pa为头结点
    6.     (*pb) = (*pb)->next;
    7.     while(*pb)                      //只要*pb不为NULL一直进行
    8.     {
    9.         Copy(&ccpa, cpa);      //将后者复制给前者
    10.         MultiplyOperate(ccpa, *pb); 
    11.         Add(pa, &ccpa);        //将结果加入到pa中,直到得到最后的结果
    12.         (*pb) = (*pb)->next;
    13.     }
    14.  
    15. }
    16.  
    17. void Copy(polynomial **pa, polynomial *pb)
    18. {
    19.     Create(pa, 0);
    20.     polynomial *temp, *cpa;
    21.     cpa = *pa;
    22.     pb = pb->next; // 移动指针指向第一个节点
    23.     while(pb)
    24.     {
    25.         //进行复制操作
    26.         temp = (polynomial *)malloc(sizeof(polynomial));
    27.         temp->Coef = pb->Coef;
    28.         temp->Index = pb->Index;
    29.         temp->next = NULL;
    30.         cpa->next = temp;
    31.         cpa = temp;
    32.         pb = pb->next;
    33.     }
    34. }
    35.  
    36. void MultiplyOperate(polynomial *pa, polynomial *pb)
    37. {
    38.     pa = pa->next;
    39.     while(pa)
    40.     {
    41.         pa->Coef *= pb->Coef;
    42.         pa->Index += pb->Index;
    43.         pa = pa->next;
    44.     }
    45. }

    乘法结束之后，该一元多项式运算器就到这里了。

    下面附上该题的完整代码：

    1. #include 
    2. #include
    3. using namespace std;
    4.  
    5. typedef struct polynomial
    6. {
    7.     float Coef; //系数
    8.     int Index;   //指数
    9.     struct polynomial *next;
    10. } polynomial;
    11.  
    12. //功能函数声明
    13. void CreatePolyn(polynomial **p, int m);
    14. void Add(polynomial **pa, polynomial **pb);
    15. void Subtract(polynomial **pa, polynomial **pb);
    16. void Multiply(polynomial **pa, polynomial **pb);
    17. void Copy(polynomial **pa, polynomial *pb);
    18. void MultiplyOperate(polynomial *pa, polynomial *pb);
    19. void Print(polynomial *p);
    20.  
    21. int main()
    22. {
    23.  
    24.     polynomial *pa, *pb;    //定义两个结构体指针
    25.     int n,m;                //用来存放多项式的项数
    26.     int choose;             //选择加减乘
    27.     int Flag = 1;
    28.     while (1) {
    29.         if (Flag == 1) {
    30.             cout << "***************** 一元多项式计算器 *****************" << endl;
    31.             cout << "请输入第一个多项式的项数->";
    32.             cin >> n;
    33.             CreatePolyn(&pa, n);
    34.             cout << endl;
    35.             cout << "请输入第二个多项式的项数->";
    36.             cin >> m;
    37.             CreatePolyn(&pb, m);
    38.             cout << endl;
    39.  
    40.  
    41.             cout << "********************************" << endl;
    42.             cout << "本计算器可以进行的计算方式:" << endl;
    43.             cout << "1.相加" << endl;
    44.             cout << "2.相减" << endl;
    45.             cout << "3.相乘" << endl;
    46.             cout << "********************************" << endl;
    47.             cout << endl;
    48.             cout << "请选择计算方式:";
    49.             cin >> choose;
    50.  
    51.             if (choose == 1) {
    52.                 Add(&pa, &pb);         //加法
    53.             } else if (choose == 2) {
    54.                 Subtract(&pa, &pb);    //减法
    55.             } else{
    56.                 Multiply(&pa, &pb);    //乘法
    57.             } 
    58.  
    59.             cout << "结果如下: " << endl;
    60.             Print(pa);
    61.             cout << endl;
    62.         } 
    63. 		else {
    64.  
    65.             cout << "**********************************" << endl;
    66.             cout << "           谢谢使用本系统!            " << endl;
    67.             cout << "**********************************" << endl;
    68.             return 0;
    69.         }
    70.  
    71.         cout << endl;
    72.         cout << "**********************************" << endl;
    73.         cout << "           是否继续使用？            " << endl;
    74.         cout << "1.是" << endl;
    75.         cout << "2.否" << endl;
    76.         cout << "**********************************" << endl;
    77.         cin >> Flag;
    78.     }
    79. }
    80.  
    81. void CreatePolyn(polynomial **p, int m)
    82. {
    83.     int i, data;
    84.     polynomial *cp, *temp;
    85.     (*p) = (polynomial *)malloc(sizeof(polynomial));
    86.     (*p)->Coef = 0.0;
    87.     (*p)->Index = -1;
    88.     (*p)->next = NULL;
    89.     for(i=1; i<=m; ++i){
    90.         cp = *p;        //初始位置
    91.         temp = (polynomial *)malloc(sizeof(polynomial));
    92.         cout << "请输入第" << i << "项的系数: ";
    93.         cin >> temp->Coef;
    94.         cout << "请输入第" << i << "项的指数: ";
    95.         cin >> temp->Index;
    96.  
    97.         while(cp->next && temp->Index > cp->next->Index)
    98.         {
    99.             cp = cp->next;
    100.         }
    101.         if(cp->next && temp->Index == cp->next->Index){     // 如果已经存在相同指数的多项式，跳出循环
    102.             continue;
    103.         }
    104.         temp->next = cp->next;
    105.         cp->next = temp;
    106.     }
    107. }
    108.  
    109. void Add(polynomial **pa, polynomial **pb)
    110. {
    111.     polynomial *cpa, *cpb, *p = (*pa);
    112.     cpa = (*pa)->next;
    113.     cpb = (*pb)->next;
    114.     while(cpa && cpb)       //对每一项进行比较
    115.     {
    116.         if(cpa->Index < cpb->Index)
    117.         {
    118.             p->next = cpa;
    119.             p = cpa;
    120.             cpa = cpa->next;
    121.         }
    122.         else if(cpa->Index > cpb->Index)
    123.         {
    124.             p->next = cpb;
    125.             p = cpb;
    126.             cpb = cpb->next;
    127.         }
    128.         else
    129.         {
    130.             if(cpa->Coef + cpb->Coef == 0)
    131.             {
    132.                 cpa = cpa->next;
    133.                 cpb = cpb->next;
    134.  
    135.             }
    136.             else
    137.             {
    138.                 cpa->Coef += cpb->Coef;
    139.                 p->next = cpa;
    140.                 p = cpa;
    141.                 cpa = cpa->next;
    142.                 cpb = cpb->next;
    143.             }
    144.         }
    145.     }
    146.     if(cpa)
    147.         p->next = cpa;
    148.     else
    149.         p->next = cpb;
    150.     free(*pb);          //*pb已经为空，释放空间
    151. }
    152.  
    153. void Subtract(polynomial **pa, polynomial **pb)
    154. {
    155.     polynomial *cpa, *cpb, *p = (*pa);
    156.     cpa = (*pa)->next;
    157.     cpb = (*pb)->next;
    158.     while(cpa && cpb)   //对每一项进行比较
    159.     {
    160.         if(cpa->Index < cpb->Index)
    161.         {
    162.             p->next = cpa;
    163.             p = cpa;
    164.             cpa = cpa->next;
    165.         }
    166.         else if(cpa->Index > cpb->Index)
    167.         {
    168.             p->next = cpb;
    169.             p = cpb;
    170.             p->Coef *= -1;  // 此时结果为负数，需改变符号
    171.             cpb = cpb->next;
    172.         }
    173.         else                //  此时指数相等
    174.         {
    175.             if(cpa->Coef == cpb->Coef)  //如果两项系数相等，删除该节点
    176.             {
    177.                 cpa = cpa->next;
    178.                 cpb = cpb->next;
    179.  
    180.             }
    181.             else
    182.             {
    183.                 cpa->Coef -= cpb->Coef;
    184.                 p->next = cpa;
    185.                 p = cpa;
    186.                 cpa = cpa->next;
    187.                 cpb = cpb->next;
    188.             }
    189.         }
    190.     }
    191.  
    192.     if(cpa) {
    193.         p->next = cpa;
    194.     }
    195.     if(cpb){
    196.         p->next = cpb;
    197.         while(cpb){
    198.             cpb->Coef *= -1; // 改变系数的符号，将减数多项式的系数变为负的
    199.             cpb = cpb->next;
    200.         }
    201.     }
    202.     free(*pb);      //*pb已经为空，释放空间
    203. }
    204.  
    205. void Multiply(polynomial **pa, polynomial **pb)
    206. {
    207.     polynomial *cpa, *ccpa;
    208.     cpa = *pa;                      //保存着原pa的内容
    209.     CreatePolyn(pa, 0);         //从新初始化pa为头结点
    210.     (*pb) = (*pb)->next;
    211.     while(*pb)                      //只要*pb不为NULL一直进行
    212.     {
    213.         Copy(&ccpa, cpa);      //将后者复制给前者
    214.         MultiplyOperate(ccpa, *pb); 
    215.         Add(pa, &ccpa);        //将结果加入到pa中,直到得到最后的结果
    216.         (*pb) = (*pb)->next;
    217.     }
    218.  
    219. }
    220.  
    221. void Copy(polynomial **pa, polynomial *pb)
    222. {
    223.     CreatePolyn(pa, 0);
    224.     polynomial *temp, *cpa;
    225.     cpa = *pa;
    226.     pb = pb->next; // 移动指针指向第一个节点
    227.     while(pb)
    228.     {
    229.         //进行复制操作
    230.         temp = (polynomial *)malloc(sizeof(polynomial));
    231.         temp->Coef = pb->Coef;
    232.         temp->Index = pb->Index;
    233.         temp->next = NULL;
    234.         cpa->next = temp;
    235.         cpa = temp;
    236.         pb = pb->next;
    237.     }
    238. }
    239.  
    240. void MultiplyOperate(polynomial *pa, polynomial *pb)
    241. {
    242.     pa = pa->next;
    243.     while(pa)
    244.     {
    245.         pa->Coef *= pb->Coef;
    246.         pa->Index += pb->Index;
    247.         pa = pa->next;
    248.     }
    249. }
    250.  
    251. void Print(polynomial *p)
    252. {
    253.     polynomial *temp = p->next;
    254.     int a[100000];
    255.     double b[100000];
    256.     int aid=0,bid=0;
    257.     int cnt=0;
    258.     cout << "升幂情况: " ;
    259.     while(temp){
    260.         if(cnt!=0&& temp->Coef > 0)printf("+");
    261.         b[bid]=  temp->Coef;
    262.         a[aid]=  temp->Index;
    263.         cout << b[bid] << "x^" << a[aid];
    264.         aid++;
    265.         bid++;
    266.         cnt++;
    267.         temp = temp->next;
    268.     }
    269.     if(cnt==0) {    //如果是空的输出0
    270.         cout << "0";
    271.     }
    272.     cout << endl;
    273.     cout << "降幂情况: ";
    274.     int ans=0;
    275.     for(int i=aid-1; i>=0; i--){
    276.         if(ans!=0&&b[i]>0) {
    277.             cout << "+";
    278.         }
    279.         cout << b[i] << "x^" << a[i];
    280.         ans++;
    281.     }
    282. }

    该题的链表方法讲解就结束了，后续我会补充结构体数组对此题的解法，希望大家多多指教！

  • 相关阅读:
    设计模式-原型模式
    C++ Reference: Standard C++ Library reference: C Library: ctime: asctime
    二次创业，都市丽人照旧
    Mybatis-Plus条件构造器QueryWrapper
    Java:泛型
    第四章-串
    硬件及接口学习总结
    设计模式 -- 1：简单工厂模式
    JAVA动漫周边产品销售管理系统计算机毕业设计Mybatis+系统+数据库+调试部署
    开源数据库 PolarDB 为什么能捕获娃哈哈的心?
  • 原文地址：https://blog.csdn.net/m0_61886762/article/details/126864443