第4节 一元多项式的相加和相乘

  1 #include "linked_dclist.h"    // for class linked_dclist<T>
  2 /* 主题: 一元多项式的相加和相乘
  3 * 作者: chinazhangjie(邮箱:[email protected])
  4 * 开发语言: C++
  5 * 开发环境: Microsoft Visual Studio 2008
  6 * 日期: 2010.08.29
  7  */
  8 　
  9 
 10 // 项的表示
 11 struct item {
 12     float    ceof;    // 系数
 13     int        expn;    // 指数
 14     item():ceof(0.0),expn(0) { }
 15     item(float c,int e) 
 16         : ceof(c),expn(e) {}
 17     
 18     bool operator < (const item& rhs) {
 19         return expn < rhs.expn;
 20     }
 21     bool operator > (const item& rhs) {
 22         return expn > rhs.expn;
 23     }
 24     bool operator == (const item& rhs) {
 25         return expn == rhs.expn;
 26     }
 27 };
 28 
 29 class polynomial {
 30     typedef linked_dclist<item>    value_type;
 31     typedef unsigned int        p_size;
 32 public:
 33     // 构造函数
 34     polynomial() {
 35     }
 36     // 拷贝构造函数
 37     polynomial(const polynomial& rhs) {
 38         elem = rhs.elem;
 39     }
 40     
 41     // 返回一元多项式的项数
 42     p_size size() const {
 43         return elem.size();
 44     }
 45     
 46     // 销毁一元多项式
 47     void destroy() {
 48         elem.clear();
 49     }
 50     
 51     // 按指数排序
 52     void sort() {
 53         elem.sort_increase();
 54     }
 55     
 56     // 增加项
 57     void add_polyn(float ceof,int expn) {
 58         if (ceof == 0.0f) 
 59             return ;
 60         item im(ceof,expn);
 61         p_size location = __search(im);
 62         if (location == -1)
 63             elem.push_back(im);
 64         else {
 65             float ceof = elem[location].ceof + im.ceof;
 66             if (ceof == 0.0f)
 67                 elem.remove(location);
 68             else 
 69                 elem[location].ceof = ceof;
 70         }
 71     }
 72 
 73     item& operator[] (p_size location) {
 74         return elem[location];
 75     }
 76 
 77     // 相加
 78     void subtract_polyn(const polynomial& rhs) {
 79         if (rhs.size() == 0) {
 80             this->sort();
 81             return ;
 82         }
 83         polynomial other(rhs);
 84         other.sort();
 85         if (this->size() == 0) {
 86             (*this) = other;
 87         }
 88         polynomial new_poly(*this);
 89         p_size i = 0;
 90         while (i < other.size()) {
 91             new_poly.add_polyn(other[i].ceof,other[i].expn);
 92             ++ i;
 93         }
 94         (*this) = new_poly;
 95         this->sort();
 96         return;
 97         
 98     }
 99     // 相乘
100     void multiply_polyn(const polynomial& rhs) {
101         if (rhs.size() == 0) {
102             return;
103         }
104         if (this->size() == 0) {
105             return ;
106         }
107         p_size i = 0;
108         polynomial new_poly;
109         while (i < this->size()) {
110             item im = (*this)[i];
111             polynomial pl(rhs);
112             p_size j = 0;
113             while (j < pl.size()) {
114                 pl[j].ceof *= im.ceof;    
115                 pl[j].expn += im.expn;
116                 ++ j;
117             }
118             new_poly.subtract_polyn(pl);
119             ++ i;
120         }
121         new_poly.sort();
122         (*this) = new_poly;
123     }
124 
125     // 重载 "="
126     polynomial& operator = (const polynomial& rhs) {
127         if (this == &rhs)
128             return *this;
129         this->destroy();
130         elem = rhs.elem;
131         return *this;
132     }
133     // 重载 " << "
134     friend 
135     ostream& operator << (ostream& out,polynomial& rhs) {
136         p_size i = 0;
137         while (i < rhs.size()-1) {
138             if (rhs[i].expn == 0)
139                 out << rhs[i].ceof << " + " ;
140             else {
141                 if (rhs[i].expn == 1) {
142                     if (rhs[i].ceof == 1.0f)
143                         out << "x" << " + "; 
144                     else
145                         out << rhs[i].ceof << "*x" << " + ";
146                 }
147                 else {
148                     if (rhs[i].ceof == 1.0f)
149                         out << "x^" << rhs[i].expn << " + "; 
150                     else
151                         out << rhs[i].ceof << "*x^" << rhs[i].expn << " + "; 
152                 }
153             }
154             ++ i;
155         }
156         if (i == rhs.size() - 1) {
157             if (rhs[i].expn == 0)
158                 out << rhs[i].ceof;
159             else 
160                 out << rhs[i].ceof << "*x^" << rhs[i].expn; 
161         }
162         cout << endl;
163         return out;
164     }
165 private:
166     // 查找指数相同的项，找到返回位置，如果没有找到返回-1
167     p_size __search(const item& im) {
168         p_size i = 0;
169         while (i < this->size()) {
170             if (elem[i] == im)
171                 return i;
172             ++ i;
173         }
174         if (i == this->size()) 
175             return -1;
176         return -1;
177     }
178 
179 private:
180     value_type elem;
181 };