示例一
1 2 3 4 5 6
^Z
1 * x ^ 2 + 3 * x ^ 4 + 5 * x ^ 6
1 2 3 4 5 6
^Z
1 * x ^ 2 + 3 * x ^ 4 + 5 * x ^ 6
2 * x ^ 2 + 6 * x ^ 4 + 10 * x ^ 6
示例二
1 2 100 10000
^Z
1 * x ^ 2 + 100 * x ^ 10000
1 3 1000 1000
^Z
1 * x ^ 3 + 1000 * x ^ 1000
1 * x ^ 2 + 1 * x ^ 3 + 1000 * x ^ 1000 + 100 * x ^ 10000
1 #include <iostream>
2 #include <vector>
3 #include <cmath>
4 using namespace std;
5
6 struct node
7 {
8 double coe;
9 double exp;
10 node* next;
11 node(double c = 0.0, double e = 0.0, node* n = 0)
12 : coe(c), exp(e), next(n) {}
13 };
14
15 void init(node*& poly)
16 {
17 poly = new node;
18 }
19
20 void create(node* poly, const vector<int>& v)
21 {
22 node* p = poly;
23 for (vector<int>::size_type i = 0; i != v.size(); i += 2)
24 {
25 node* temp = new node(v[i], v[i + 1]);
26 p->next = temp;
27 p = temp;
28 }
29 }
30
31 void display(node* poly)
32 {
33 poly = poly->next;
34 while (poly != 0)
35 {
36 cout << poly->coe << " * x ^ " << poly->exp;
37 if (poly->next != 0)
38 {
39 if (poly->coe > 0)
40 {
41 cout << " + ";
42 }
43 else
44 {
45 cout << " ";
46 }
47 }
48 poly = poly->next;
49 }
50 cout << endl;
51 }
52
53 node* add(node* ret, node* poly1, node* poly2)
54 {
55 node* p1 = poly1->next;
56 node* p2 = poly2->next;
57 node* r = ret;
58 while (p1 != 0 && p2 != 0)
59 {
60 if (p1->exp == p2->exp)
61 {
62 double c = p1->coe + p2->coe;
63 if (abs(c) > 1e-6)
64 {
65 node* t = new node(c, p1->exp);
66 r->next = t;
67 r = t;
68 }
69 p1 = p1->next;
70 p2 = p2->next;
71 }
72 else if (p1->exp < p2->exp)
73 {
74 node* t = new node(p1->coe, p1->exp, 0);
75 r->next = t;
76 r = t;
77 p1 = p1->next;
78 }
79 else
80 {
81 node* t = new node(p2->coe, p2->exp, 0);
82 r->next = t;
83 r = t;
84 p2 = p2->next;
85 }
86 }
87 while (p1 != 0)
88 {
89 node* t = new node(p1->coe, p1->exp, 0);
90 r->next = t;
91 r = t;
92 p1 = p1->next;
93 }
94 while (p2 != 0)
95 {
96 node* t = new node(p2->coe, p2->exp, 0);
97 r->next = t;
98 r = t;
99 p2 = p2->next;
100 }
101 return ret;
102 }
103
104 void clear(node* poly)
105 {
106 node* p = poly->next, *q;
107 while (p != 0)
108 {
109 q = p->next;
110 delete p;
111 p = q;
112 }
113 }
114
115 void destroy(node*& poly)
116 {
117 clear(poly);
118 delete poly;
119 poly = 0;
120 }
121
122 int main()
123 {
124 vector<int> v;
125 int n;
126 while (cin >> n)
127 {
128 v.push_back(n);
129 }
130 node* p1;
131 init(p1);
132 create(p1, v);
133 display(p1);
134
135 v.clear();
136 cin.clear();
137 while (cin >> n)
138 {
139 v.push_back(n);
140 }
141 node* p2;
142 init(p2);
143 create(p2, v);
144 display(p2);
145 cin.clear();
146
147 node* p3;
148 init(p3);
149 add(p3, p1, p2);
150 display(p3);
151
152 destroy(p1);
153 destroy(p2);
154 destroy(p3);
155 }
posted on 2011-09-11 09:43
unixfy 閱讀(136)
評論(0) 編輯 收藏 引用