关键字:数据结构,链表,一元多项式
代码清单:
- main.cpp
- Elem.h
- Elem.cpp
- List.h
- List.cpp
- Polyn.h
- Polyn.cpp
Windows7 64位下 Code::Blocks12.11 GCC 编译运行通过。
原文地址:http://www.cnblogs.com/fengzy/archive/2013/06/01/3113039.html
欢迎交流学习,转载请注明出处。如有问题,请留言。
下面是源代码。
- main.cpp
1 //----- main.cpp ------
2 #include <iostream>
3 #include <cassert>
4 #include <stdlib.h>
5 #include "Polyn.h"
6
7 using namespace std;
8
9 #define PRINT(x) cout << #x << " = " << (x)
10 #define READ(x) cout << #x << "'s SIZE: "; (x).read()
11
12 int main()
13 {
14 Polyn Pa, Pb;
15
16 READ(Pa);
17 READ(Pb);
18
19 system("cls");
20
21 PRINT(Pa);
22 PRINT(Pb);
23
24 PRINT(Pa + Pb);
25 PRINT(Pa - Pb);
26 PRINT(Pb - Pa);
27 PRINT(Pa * Pb);
28
29 return 0;
30 }
View Code
- Elem.h
1 //----- Elem.h -----
2 #ifndef ELEM_H
3 #define ELEM_H
4
5 #include <iostream>
6 using namespace std;
7
8 class Elem
9 {
10 public:
11 Elem()
12 : coef(0.0), expn(0)
13 {
14 }
15
16 Elem(float co, int ex)
17 : coef(co), expn(ex)
18 {
19 }
20
21 ~Elem() {}
22
23 float getCoef() {
24 return coef;
25 }
26
27 void setCoef(float val) {
28 coef = val;
29 }
30
31 int getExpn() {
32 return expn;
33 }
34
35 void setExpn(int val) {
36 expn = val;
37 }
38
39 const bool operator==(const Elem rightSide);
40
41 const bool operator<=(const Elem rightSide);
42 // 仅比较指数
43
44 const bool operator>=(const Elem rightSide);
45 // 仅比较指数
46
47 const bool similar(const Elem rightSide);
48 //判断是否同类项,即指数相同
49
50 void display(ostream &out) const;
51 // 打印本项(为了方便多项式输出打印系数的绝对值)
52
53 protected:
54 private:
55 float coef; //!< 系数 "coef"
56 int expn; //!< 指数 "expn"
57 };
58
59 ostream &operator<<(ostream &out, const Elem &aElem);
60 //istream &operator>>(istream &in, Elem &aElem);
61
62 #endif // ELEM_H
View Code
- Elem.cpp
1 //----- Elem.cpp -----
2 #include <iostream>
3 #include <cmath>
4 using namespace std;
5 #include "Elem.h"
6
7 const bool Elem::operator==(const Elem rightSide)
8 {
9 return rightSide.coef == coef && rightSide.expn == expn;
10 }
11
12 const bool Elem::operator<=(const Elem rightSide)
13 {
14 return expn <= rightSide.expn;
15 }
16 // 仅比较指数
17
18 const bool Elem::operator>=(const Elem rightSide)
19 {
20 return expn >= rightSide.expn;
21 }
22 // 仅比较指数
23
24 const bool Elem::similar(const Elem rightSide)
25 {
26 return expn == rightSide.expn;
27 }
28 //判断是否同类项,即指数相同
29
30 void Elem::display(ostream &out) const
31 {
32 if (abs(coef))
33 {
34 if (abs(coef) == 1.0)
35 {
36 if (expn)
37 {
38 if (expn > 0)
39 { // 指数 > 0
40 if (expn == 1)
41 {
42 out << "x";
43 }
44 else
45 {
46 out << "x^" << expn;
47 }
48 }
49 else
50 { // 指数 < 0
51 out << "x^(" << expn << ")";
52 }
53 }
54 else out << 1; // 指数 = 0
55 }
56 else
57 {
58 if (expn)
59 {
60 if (expn > 0)
61 { // 指数 > 0
62 if (expn == 1)
63 {
64 out << abs(coef) << "x";
65 }
66 else
67 {
68 out << abs(coef) << "x^" << expn;
69 }
70 }
71 else
72 { // 指数 < 0
73 out << abs(coef) << "x^(" << expn << ")";
74 }
75 }
76 else out << abs(coef); // 指数 = 0
77 }
78 }
79 else out << "0";
80 }
81
82 ostream &operator<<(ostream &out, const Elem &aElem)
83 {
84 aElem.display(out);
85 return out;
86 }
87
88 //istream &operator>>(istream &in, Elem &aElem)
89 //{
90 // in
91 // return in;
92 //}
View Code
- List.h
1 //----- List.h -----
2 #ifndef LINKEDLIST
3 #define LINKEDLIST
4
5 #include <iostream>
6 #include "Elem.h"
7
8 using namespace std;
9
10
11 class List
12 {
13 protected:
14 class Node
15 {
16 public:
17 //------ Node 数据成员
18 Elem data;
19 Node *next;
20
21 //------ Node 成员函数
22 //-- 默认构造函数: 头结点为 0
23 Node()
24 : next(0)
25 { }
26
27 //-- 赋值构造函数,用给定的值初始化,并将头结点置为 0
28 Node(Elem dataValue)
29 : data(dataValue), next(0) // TODO maybe problems
30 { }
31 }; //--- end of Node class
32
33 typedef Node *NodePointer;
34
35 public:
36 //------ List 成员函数
37 List();
38 //默认构造函数: 创建一个空链表。
39
40 List(const List &origList);
41 //复制构造函数
42
43 ~List();
44
45 const List &operator=(const List &rightSide);
46 //重载赋值运算符
47
48 bool empty();
49 //判空函数
50
51 void insert(Elem dataVal, int index);
52 //向链表的指定位置插入一个元素
53
54 void erase(int index);
55 //删除指定位置的元素
56
57 int search(Elem dataVal);
58 /*--------------------------------------------------------------------
59 查找链表中找的元素
60 前置条件: 元素类型需重载 “==”
61 后置条件: 返回给定元素在链表中首次出现的位置(从 0 开始)
62 如果链表中不存在该元素,则返回 -1
63 --------------------------------------------------------------------*/
64
65 Elem getElem(int index) const;
66 /*-------------------------------------------------------------------
67 取得链表中指定位置的元素
68 前置条件:指定位置 index 需满足 0< index < mySize
69 后置条件:返回给定位置的元素
70 --------------------------------------------------------------------*/
71
72 void setElem(Elem dataVal, int index);
73 /*-------------------------------------------------------------------
74 改变链表中指定位置的元素
75 前置条件:指定位置 index 需满足 0 < index < mySize,元素类型需重载
76 赋值符号 “=”
77 后置条件:返回给定位置的元素
78 --------------------------------------------------------------------*/
79
80 void display(ostream &out) const;
81
82 int nodeCount() const;
83 // 查询链表中节点的个数
84
85 void reverse();
86 // 逆序
87
88 bool ascendingOrder();
89 /*--------------------------------------------------------------------
90 检查链表中元素是否升序排列
91 前置条件: 元素类型需重载 “<=” 和 “>=”
92 --------------------------------------------------------------------*/
93
94 bool descendingOrder();
95 /*--------------------------------------------------------------------
96 检查链表中元素是否降序排列
97 前置条件: 元素类型需重载 “<=” 和 “>=”
98 --------------------------------------------------------------------*/
99
100 protected:
101 //------ 数据成员
102 NodePointer first;
103 int mySize;
104 }; //--- end of List class
105
106 ostream &operator<<(ostream &out, const List &aList);
107 //istream &operator>>(istream &in, List &aList);
108
109 #endif
View Code
- List.cpp
1 //----- List.cpp -----
2 #include <iostream>
3 #include <cassert>
4
5 using namespace std;
6 #include "List.h"
7
8 //-- 默认构造函数
9 List::List()
10 : first(0), mySize(0)
11 { }
12
13 //-- 复制构造函数
14 List::List(const List &origList)
15 {
16 mySize = origList.mySize;
17 first = 0;
18
19 if (mySize == 0) return;
20
21 List::NodePointer origPtr, lastPtr;
22 first = new Node(origList.first->data); // 复制头结点
23 lastPtr = first;
24 origPtr = origList.first->next;
25
26 while (origPtr != 0)
27 {
28 lastPtr->next = new Node(origPtr->data);
29 origPtr = origPtr->next;
30 lastPtr = lastPtr->next;
31 }
32 }
33
34 //-- 析构函数
35 List::~List()
36 {
37 List::NodePointer prev = first,
38 ptr;
39
40 while (prev != 0)
41 {
42 ptr = prev->next;
43 delete prev;
44 prev = ptr;
45 }
46 }
47
48 bool List::empty()
49 {
50 return mySize == 0;
51 }
52
53 //-- 赋值运算符
54 const List &List::operator=(const List &rightSide)
55 {
56 mySize = rightSide.mySize;
57 first = 0;
58
59 if (mySize == 0) return *this;
60
61 if (this != &rightSide)
62 {
63 this->~List();
64 List::NodePointer origPtr, lastPtr;
65 first = new Node(rightSide.first->data); // 复制头结点
66 lastPtr = first;
67 origPtr = rightSide.first->next;
68
69 while (origPtr != 0)
70 {
71 lastPtr->next = new Node(origPtr->data);
72 origPtr = origPtr->next;
73 lastPtr = lastPtr->next;
74 }
75 }
76
77 return *this;
78 }
79
80 void List::insert(Elem dataVal, int index)
81 {
82 if (index < 0 || index > mySize)
83 {
84 cerr << "Illegal location to insert -- " << index
85 << ", size of the link is " << mySize << ".n";
86
87 assert (index >= 0 && index <= mySize);
88 }
89
90 mySize++;
91 List::NodePointer newPtr = new Node(dataVal),
92 predPtr = first;
93
94 if (index == 0)
95 {
96 newPtr->next = first;
97 first = newPtr;
98 }
99 else
100 {
101 for(int i = 1; i < index; i++)
102 predPtr = predPtr->next;
103
104 newPtr->next = predPtr->next;
105 predPtr->next = newPtr;
106 }
107 }
108
109 void List::erase(int index)
110 {
111 if (index < 0 || index >= mySize)
112 {
113 cerr << "Illegal location to delete -- " << index
114 << ", size of the link is " << mySize << ".n";
115
116 assert (index >= 0 && index <= mySize);
117 }
118
119 mySize--;
120 List::NodePointer ptr,
121 predPtr = first;
122
123 if (index == 0)
124 {
125 ptr = first;
126 first = ptr->next;
127 delete ptr;
128 }
129 else
130 {
131 for(int i = 1; i < index; i++)
132 predPtr = predPtr->next;
133
134 ptr = predPtr->next;
135 predPtr->next = ptr->next;
136 delete ptr;
137 }
138 }
139
140 int List::search(Elem dataVal)
141 {
142 int loc;
143 List::NodePointer tempP = first;
144
145 for (loc = 0; loc < mySize; loc++)
146 if (tempP->data == dataVal)
147 return loc;
148 else
149 tempP = tempP->next;
150
151 return -1;
152 }
153
154 void List::display(ostream &out) const
155 {
156 List::NodePointer ptr = first;
157
158 while (ptr != 0)
159 {
160 out << ptr->data << " ";
161 ptr = ptr->next;
162 }
163 }
164
165 ostream &operator<<(ostream &out, const List &aList)
166 {
167 aList.display(out);
168 return out;
169 }
170
171 int List::nodeCount() const
172 {
173 // or simply, { return mySize; }
174 int count = 0;
175 List::NodePointer ptr = first;
176
177 while (ptr != 0)
178 {
179 count++;
180 ptr = ptr->next;
181 }
182
183 return count;
184 }
185
186 void List::reverse()
187 {
188 NodePointer prevP = 0,
189 currentP = first,
190 nextP;
191
192 while (currentP != 0)
193 {
194 nextP = currentP->next;
195 currentP->next = prevP;
196 prevP = currentP;
197 currentP = nextP;
198 }
199
200 first = prevP; // new head of (reversed) linked list
201 }
202
203 bool List::ascendingOrder()
204 {
205 if (mySize <= 1)
206 //empty or one element list
207 return true;
208
209 //else
210 NodePointer prevP = first,
211 tempP = first->next;
212
213 while (tempP != 0 && prevP->data <= tempP->data)
214 {
215 prevP = tempP;
216 tempP = tempP->next;
217 }
218
219 if (tempP != 0)
220 return false;
221
222 // else
223 return true;
224 }
225
226 bool List::descendingOrder()
227 {
228 if (mySize <= 1)
229 //empty or one element list
230 return true;
231
232 //else
233 NodePointer prevP = first,
234 tempP = first->next;
235
236 while (tempP != 0 && prevP->data >= tempP->data)
237 {
238 prevP = tempP;
239 tempP = tempP->next;
240 }
241
242 if (tempP != 0)
243 return false;
244
245 // else
246 return true;
247 }
248
249 Elem List::getElem(int index) const
250 {
251 if (index < 0 || index >= mySize)
252 {
253 cerr << "Illegal location to get element -- " << index
254 << ", size of the link is " << mySize << ".n";
255
256 assert (index >= 0 && index <= mySize);
257 }
258
259
260
261 if (index == 0)
262 return first->data;
263 else
264 {
265 List::NodePointer ptr = first;
266
267 for(int i = 1; i < index; i++)
268 ptr = ptr->next;
269
270 return ptr->next->data;
271 }
272 }
273
274 void List::setElem(Elem dataVal, int index)
275 {
276 if (index < 0 || index >= mySize)
277 {
278 cerr << "Illegal location to set element -- " << index
279 << ", size of the link is " << mySize << ".n";
280
281 assert (index >= 0 && index <= mySize);
282 }
283
284 if (index == 0)
285 first->data = dataVal;
286 else
287 {
288 List::NodePointer ptr = first;
289
290 for(int i = 1; i < index; i++)
291 ptr = ptr->next;
292
293 ptr->next->data = dataVal;
294 }
295
296 }
View Code
- Polyn.h
1 //----- Polyn.h ------
2 #ifndef POLYN_H
3 #define POLYN_H
4
5 #include "List.h"
6
7 class Polyn : public List
8 {
9 public:
10 void read();
11 void display(ostream &out) const;
12 void mergerCo(); // 合并指数相同的项
13 void sort(); // 按指数降序排序
14 Polyn operator+(const Polyn &b);
15 Polyn operator-(const Polyn &b);
16 Polyn operator*(const Polyn &b);
17
18 protected:
19 private:
20 };
21
22 ostream &operator<<(ostream &out, const Polyn &aPolyn);
23
24 #endif // POLYN_H
View Code
- Polyn.cpp
1 //----- Polyn.h ------
2 #ifndef POLYN_H
3 #define POLYN_H
4
5 #include "List.h"
6
7 class Polyn : public List
8 {
9 public:
10 void read();
11 void display(ostream &out) const;
12 void mergerCo(); // 合并指数相同的项
13 void sort(); // 按指数降序排序
14 Polyn operator+(const Polyn &b);
15 Polyn operator-(const Polyn &b);
16 Polyn operator*(const Polyn &b);
17
18 protected:
19 private:
20 };
21
22 ostream &operator<<(ostream &out, const Polyn &aPolyn);
23
24 #endif // POLYN_H
View Code
测试数据:
测试用例:
(1)
3
2 1 5 8 -3.1 11
3
7 0 -5 8 11 9
(2)
4
6 -3 -1 1 4.4 2 -1.2 9
4
-6 -3 5.4 2 -1 2 7.8 15
(3)
6
1 0 1 1 1 2 1 3 1 4 1 5
2
-1 3 -1 4
(4)
2
1 1 1 3
2
-1 1 -1 3
(5)
2
1 1 1 100
1 100 1 200
(6)
3
1 1 1 2 1 3
1
0 0
View Code
原文链接: https://www.cnblogs.com/fengzy/archive/2013/06/01/3113039.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/90756
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!