【Weiss】【第03章】练习3.6：有序多项式相加

【练习3.6】

编写将两个多项式相加的函数。不要毁坏输入数据。用一个链表实现。

如果这两个多项式分别有M项和N项，那么你程序的时间复杂度是多少？

两个按幂次升序的多项式链表，分别维护一个指针。

幂较小者将元素的副本拷贝入节点并加入新链表，指针向后移动。

幂同样大时，将两者的系数相加后的结果加入新链表，两个多项式链表的指针共同向前移动。

其中一个多项式到达尾部时，如另一个未到达尾部，则一边后移一边将相同元素的新节点加入新链表。

时间复杂度O(M+N)。

测试代码如下：

 1 #include <iostream>
 2 #include "linklist.h"
 3 using linklist::List;
 4 using namespace std;
 5 int main(void)
 6 {
 7     //测试多项式加法
 8     List<Poly> a;
 9     a.additem(Poly(3, 1));
10     a.additem(Poly(1, 2));
11     a.additem(Poly(4, 3));
12     a.additem(Poly(7, 4));
13     a.additem(Poly(2, 5));
14     cout << "  ( " << flush;
15     a.traverse();
16     cout << ")  +
" << flush;
17     List<Poly> b;
18     b.additem(Poly(5, 2));
19     b.additem(Poly(2, 3));
20     b.additem(Poly(1, 5));
21     b.additem(Poly(3, 7));
22     b.additem(Poly(1, 11));
23     cout << "  ( " << flush;
24     b.traverse();
25     cout << ") =
" << flush;
26 
27     List<Poly> answer = linklist::polyplus(a, b);
28     cout << "
  ( " << flush;
29     answer.traverse();
30     cout << ") 
" << flush;
31     system("pause");
32 }

View Code

实现方面，首先定义了多项式类，以及必要的构造函数及运算符重载，放在poly.h头文件中

 1 #ifndef POLY
 2 #define POLY
 3 #include <iostream>
 4 using namespace std;
 5 
 6 namespace poly
 7 {
 8 //练习3.6新增，多项式元素定义
 9 class Poly
10 {
11     friend bool operator<(const Poly& poly1, const Poly& poly2);
12     friend bool operator==(const Poly& poly1, const Poly& poly2);
13     friend bool operator!=(const Poly& poly1, const Poly& poly2);
14     friend ostream& operator<<(ostream &os, const Poly& poly);
15     friend Poly operator+(const Poly& poly1, const Poly& poly2);
16 public:
17     Poly() = default;
18     Poly(int coe, int exp) :coefficient(coe), exponent(exp){}
19 private:
20     //多项式系数
21     int coefficient;
22     //多项式指数
23     int exponent;
24 };
25 //练习3.6新增，多项式元素对应操作符重载，包括<<、<、==、!=，+
26 bool operator<(const Poly& poly1, const Poly& poly2)
27 {
28     return poly1.exponent < poly2.exponent;
29 }
30 bool operator==(const Poly& poly1, const Poly& poly2)
31 {
32     return poly1.exponent == poly2.exponent;
33 }
34 bool operator!=(const Poly& poly1, const Poly& poly2)
35 {
36     return !(poly1 == poly2);
37 }
38 ostream& operator<<(ostream &os, const Poly& poly)
39 {
40     cout << poly.coefficient << "x^" << poly.exponent << flush;
41     return os;
42 }
43 Poly operator+(const Poly& poly1, const Poly& poly2)
44 {
45     if (poly1 != poly2)
46         throw runtime_error("Undefined operation!");
47     else
48     {
49         Poly answer;
50         answer.coefficient = poly1.coefficient + poly2.coefficient;
51         answer.exponent = poly1.exponent;
52         return answer;
53     }
54 }
55 }
56 #endif

在原链表例程中包含该头文件，并将Poly类与polyplus函数（该函数不是List的成员函数）设为友元

 1 #ifndef LINKLIST
 2 #define LINKLIST
 3 #include <iostream>
 4 #include "poly.h"　　　　　　//包含poly头文件
 5 using namespace std;
 6 using namespace poly;
 7 
 8 namespace linklist
 9 {
10         /…………/
11  template <typename T> class List
12 {
13     　　/…………/
14         //练习3.6新增，友元声明
15     friend List<Poly> polyplus(const List<Poly> &inorder_a, const List<Poly> &inorder_b);
16     friend struct Poly;   
17        /…………/
18 }
19 
20        /…………/
21 }

最后是具体实现代码：

 1 //练习3.6新增，不覆盖原传入数据，多项式相加
 2 List<Poly> polyplus(const List<Poly> &inorder_a, const List<Poly> &inorder_b)
 3 {
 4     List<Poly> answer;
 5     Node<Poly>* pwrite = answer.front;
 6     Node<Poly>* pread_a = inorder_a.front;
 7     Node<Poly>* pread_b = inorder_b.front;
 8     while (pread_a != nullptr && pread_b != nullptr)
 9     {
10         //为实现升序排列，元素较小者加入新的链表，并向前移动指针
11         if (pread_a->data < pread_b->data)
12         {
13             answer.additem(pread_a->data, pwrite);
14             if (pwrite == nullptr)
15                 pwrite = answer.front;
16             else
17             pwrite = pwrite->next;
18             pread_a = pread_a->next;
19         }
20         else if (pread_b->data < pread_a->data)
21         {
22             answer.additem(pread_b->data, pwrite);
23             if (pwrite == nullptr)
24                 pwrite = answer.front;
25             else
26                 pwrite = pwrite->next;
27             pread_b = pread_b->next;
28         }
29         //元素一样大时共同向前移动指针
30         else
31         {
32             answer.additem(pread_a->data + pread_b->data, pwrite);
33             if (pwrite == nullptr)
34                 pwrite = answer.front;
35             else
36                 pwrite = pwrite->next;
37             pread_a = pread_a->next;
38             pread_b = pread_b->next;
39         }
40     }
41     //如果其中任一链表未遍历，将剩余的元素复制入新的链表
42     while (pread_a != nullptr)
43     {
44         answer.additem(pread_a->data, pwrite);
45         if (pwrite == nullptr)
46             pwrite = answer.front;
47         else
48             pwrite = pwrite->next;
49         pread_a = pread_a->next;
50     }
51     while (pread_b != nullptr)
52     {
53         answer.additem(pread_b->data, pwrite);
54         if (pwrite == nullptr)
55             pwrite = answer.front;
56         else
57             pwrite = pwrite->next;
58         pread_b = pread_b->next;
59     }
60     return answer;
61 }