多项式及其运算

保持战斗力,永远!

思路想法

  1. 用一个结构体来存储多项式每一项的系数和指数;

  2. 多项式求和:创建新的多项式,指数相同的项系数相加;以一个多项式为基准进行遍历,如果指数相同就进行系数相加添加到新的多项式中,如果不同,也就是某一个项的指数只存在一个多项式中则直接添加到新的多项式中

  3. 多项式相乘,以一个多项式为基准进行遍历,每一项和另一个多项式的每一项相乘,但要注意,合并指数相同的项

代码示例

main.cpp

1
2
3
4
5
6
7
#include "polynomial.h"

int main()
{
PLOY::run();
return 0;
}

polynomial.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//
// Created by Gamelife on 2017/4/8.
//

#ifndef DATA_STRUCT_CLION_POLYNOMIAL_H
#define DATA_STRUCT_CLION_POLYNOMIAL_H

#include <iostream>

namespace PLOY {

struct Term {
float ceof;
int exp;
Term * link;

Term (float c, int e, Term * next = NULL) {
ceof = c;
exp = e;
link = next;
}

Term * insert_after(float c, int e);

friend std::ostream & operator<<(std::ostream&, const Term &);
friend std::ostream & operator<<(std::ostream& out, const Term *x)
{
if (x != NULL) {
out << *x;
}
return out;
}
};

class Polynomial
{
private:
Term * first;
void create_or_update_by_asc_order(float ceof, int exp);
friend std::ostream& operator <<(std::ostream&, const Polynomial &);
friend std::istream& operator >>(std::istream&, const Polynomial &);
friend Polynomial operator + (Polynomial &, Polynomial &);
friend Polynomial operator * (Polynomial &, Polynomial &);

public:
Polynomial(){ first = new Term(0, -1);};
Polynomial(Polynomial& R);
int max_order();
Term * get_head() const { return first;};
};

void run();
};

#endif //DATA_STRUCT_CLION_POLYNOMIAL_H

polynomial.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
//
// Created by Gamelife on 2017/4/8.
//

#include <iostream>
#include "polynomial.h"
#include <cmath>

namespace PLOY {

Term * Term::insert_after(float c, int e)
{
// 首先,this.link = NULL, new Term(c, e, link) = new Term(c, e, NULL) = new Term(c, e);
// 然后,this.link 指向新节点
link = new Term(c, e, link);
return link;
}

std::ostream & operator<<(std::ostream& out, const Term & x)
{
if (x.ceof == 0) return out;
out << x.ceof;
switch (x.exp) {
case 0:
break;
case 1:
out << "X";
break;
default: out << "X^" << x.exp;
break;
}
return out;
}

Polynomial::Polynomial(Polynomial &R) {
first = new Term(0, -1);
Term * destptr = first, * srcptr = R.get_head()->link;
while (srcptr != NULL) {
destptr->insert_after(srcptr->ceof, srcptr->exp);
srcptr = srcptr->link;
destptr = destptr->link;
}
}

// 在多项式已经按从小到大顺序排序的情况下
int Polynomial::max_order()
{
Term * current = first;
while (current->link != NULL) {
current = current->link;
}
return current->exp;
}

// 输出多项式
std::ostream& operator<<(std::ostream& out, const Polynomial & x)
{
Term * current = x.get_head()->link;
out << "The polynomial is ";
bool h = true;
while (current != NULL) {
if (!h && current->ceof > 0.0) out << " + ";
h = false;
out << *current;
current = current->link;
}
return out;
}

// 输入多项式
std::istream& operator>>(std::istream& in, const Polynomial & x)
{
Term * rear = x.get_head();
int c, e;
while (true) {
std::cout << "Input a term (ceof, exp):" << std::endl;
in >> c >> e;
if (e < 0) break;
rear = rear->insert_after(c, e);
}
return in;
}

// 多项式相加,具体思路如下
// 同时遍历两个多项式直到其中一个结束或者两个同时结束(前提,多项式已经按阶数从小到大排序)
// 如果当前指针指向的项阶数相等,则将两个项系数相加,插入到新的多项式
// 如果系数a小于b,则将a插入新多项式,并且将a指向下一个项,b保持不变
// 如果系数a大于b,则将b插入新多项式,并且将b指向下一个项,a保持不变
// 将剩余的部分复制到新的多项式中

Polynomial operator + (Polynomial & A, Polynomial & B)
{
Term *pa, *pb, *pc, *p;
float temp;

Polynomial C;
pc = C.first;

pa = A.get_head()->link;
pb = B.get_head()->link;

while (pa != NULL && pb != NULL) {
if (pa->exp == pb->exp) {
temp = pa->ceof + pa->ceof;
if (std::fabs(temp) > 0.001) {
pc = pc->insert_after(temp, pa->exp);
}
pa = pa->link;
pb = pb->link;
} else if (pa->exp < pb->exp) {
pc = pc->insert_after(pa->ceof, pa->exp);
pa = pa->link;
} else {
pc = pc->insert_after(pb->ceof, pb->exp);
pb = pb->link;
}
}

p = pa != NULL ? pa : pb;

while (p != NULL) {
pc = pc->insert_after(p->ceof, p->exp);
p = p->link;
}

return C;
}

// 按从小到大顺序增加项或者更新一个多项式
void Polynomial::create_or_update_by_asc_order(float ceof, int exp)
{
Term * current, *head = get_head();
current = head->link;
if (current == NULL) {
get_head()->insert_after(ceof, exp);
} else {
Term *p1 = head->link, *p2 = p1->link;
if (p1->exp == exp) {
p1->ceof += ceof;
} else {
while (p2 != NULL && p2->exp < exp) {
p1 = p2;
p2 = p2->link;
}
if (p2 != NULL) {
if (p2->exp == exp) {
p2->ceof += ceof;
}
else {
Term * new_ele = new Term(ceof, exp);
new_ele->link = p1->link;
p1->link = new_ele;
}
}
else {
p1->insert_after(ceof, exp);
}
}
}
}

// 多项式相乘
Polynomial operator * (Polynomial & A, Polynomial & B)
{
Term *pa, *pb;

Polynomial C;

pa = A.get_head()->link;
pb = B.get_head()->link;

while (pa != NULL) {
while (pb != NULL) {
C.create_or_update_by_asc_order(pa->ceof * pb->ceof, pa->exp + pb->exp);
pb = pb->link;
}
pb = B.get_head()->link;
pa = pa->link;
}

return C;
}

void run()
{
Polynomial poly1, poly2;
std::cin >> poly1 >> poly2;
std::cout << "product," << poly1 * poly2 << std::endl
<< "plus," << poly1 + poly2 << std::endl;
}
};

编译运行

g++ main.cpp polynomial.cpp -o main.out

结果示例

结果示例