【C++算法与数据结构学习笔记------单链表实现多项式】
本文除了polyAdd,polyMul,mergerPoly为原创，其他为本人的老师提供的源代码。
C++单链表实现多项式加法(polyAdd)，多项式乘法(polyMul)，多项式合并同类项(mergerPoly)，多项式减法，多项式除法就不贴出来了。
1 #include<iostream.h>
2 template<class T>
3 class List;
4 template<class T>
5 class Node{
6 friend class List<T>;
7 private:
8 T coef,exp;
9 Node<T> *next;
10 };
11 template<class T>
12 class List{
13 private:
14 Node<T> *first;
15 public:
16 List(){first=0;}
17 ~List();
18 bool Empty() const{return first==0;}
19 int Length()const;
20 int Locate(const T& c,const T& x)const;
21 bool Retrieve(int k,T& c, T& x)const;
22 List<T>& Insert(int k,const T& c, const T& x);
23 List<T>& Delete(int k,T& c,T& x);
24 void PrintList();
25 List<T>& polyAdd(List<T>& poly2);
26 List<T>& polyMul(List<T>& poly2,List<T>& poly3);
27 List<T>& mergerPoly();
28 };
29 template<class T>
30 List<T>::~List()
31 {
32 Node<T> *next;
33 while(first){
34 next=first->next;
35 delete first;
36 first=next;
37 }
38 }
39 template<class T>
40 int List<T>::Length()const
41 {
42 Node<T> *current=first;
43 int len=0;
44 while(current){
45 len++;
46 current=current->next;
47 }
48 return len;
49 }
50 template<class T>
51 int List<T>::Locate(const T& c,const T& x)const
52 {
53 Node<T> *current=first;
54 int index=1;
55 while(current&¤t->coef!=c&¤t->exp!=x){
56 current=current->next;
57 index++;
58 }
59 if(current)return index;
60 return 0;
61 }
62 template<class T>
63 bool List<T>::Retrieve(int k,T& c,T& x)const
64 {
65 if(k<1)return false;
66 Node<T> *current=first;
67 int index=1;
68 while(index<k&¤t){
69 current=current->next;
70 index++;
71 }
72 if(current){
73 c=current->coef;
74 x=current->exp;
75 return true;
76 }
77 return false;
78 }
79 template<class T>
80 List<T>& List<T>::Insert(int k,const T& c,const T& x)
81 {
82 Node<T> *p=first;
83 for(int index=1;index<k&&p;index++)
84 p=p->next;
85
86 Node<T> *y=new Node<T>;
87 y->coef=c;
88 y->exp=x;
89 if(k){
90 y->next=p->next;
91 p->next=y;
92 }
93 else{
94 y->next=first;
95 first=y;
96 }
97 return *this;
98 }
99 template<class T>
100 List<T>& List<T>::Delete(int k,T& c,T& x)
101 {
102 Node<T> *p=first;
103 if(k==1)
104 first=first->next;
105 else{
106 Node<T> *q=first;
107 for(int index=1;index<k-1&&q;index++)
108 q=q->next;
109 if(!q||!q->next) return *this;
110 p=q->next;
111 q->next=p->next;
112 }
113 x=p->exp;
114 c=p->coef;
115 delete p;
116 return *this;
117 }
118 template<class T>
119 void List<T>::PrintList( )
120 {
121 Node<T> *current;
122 for(current=first;current;current=current->next)
123 {
124 if (current->coef>=0&¤t!=first)
125 {
126 if (0==current->exp)
127 cout<<"+"<<current->coef;
128 else if (1==current->exp)
129 cout<<"+"<<current->coef<<"x";
130 else
131 cout<<"+"<<current->coef<<"x^"<<current->exp;
132 }
133 else
134 {
135 if (0==current->exp)
136 cout<<current->coef;
137 else if (1==current->exp)
138 cout<<current->coef<<"x";
139 else
140 cout<<current->coef<<"x^"<<current->exp;
141 }
142 }
143 cout<<endl;
144 }
145 template<class T>
146 List<T>& List<T>::polyAdd(List<T>& poly2)
147 {
148 Node<T> *p=first,*q=poly2.first,*before=first;
149 while(q!=0)
150 {
151 if (p!=0)
152 {
153 if (p->exp<q->exp)
154 {
155 before=p;
156 p=p->next;
157 }
158 else if (p->exp>q->exp)
159 {
160 Insert(Locate(p->coef,p->exp),q->coef,q->exp);
161 q=q->next;
162 }
163 else if (p->exp==q->exp)
164 {
165 p->coef+=q->coef;
166 before=p;
167 p=p->next;
168 q=q->next;
169 }
170 }
171 else
172 {
173 Insert(Length(),q->coef,q->exp);
174 q=q->next;
175 }
176 }
177 return *this;
178 }
179 template <class T>
180 List<T>& List<T>::polyMul(List<T>& poly2,List<T>& poly3)
181 {
182 Node<T> *p=first,*q=poly2.first;
183 int i=0;
184 T c,x;
185 while(p!=0)
186 {
187 while(q!=0)
188 {
189 c=p->coef*q->coef;
190 x=p->exp+q->exp;
191 q=q->next;
192 poly3.Insert(i,c,x);
193 i++;
194 }
195 p=p->next;
196 q=poly2.first;
197 }
198 return *this;
199 }
200 template <class T>
201 List<T>& List<T>::mergerPoly()
202 {
203 Node<T> *p=first,*q=p->next,*beforeQ=first,*temp;
204 while(p!=0&&p->next!=0)
205 {
206 while(q!=0)
207 {
208 if (p->exp==q->exp)
209 {
210 p->coef+=q->coef;
211 temp=q->next;
212 delete q;
213 q=temp;
214 beforeQ->next=q;
215 }
216 else
217 {
218 beforeQ=q;
219 q=q->next;
220 }
221 }
222 p=p->next;
223 beforeQ=p;
224 if (beforeQ!=0) q=p->next;
225 }
226 Node<T> *beforeP=0;
227 p=first;
228 while(p!=0)
229 {
230 if (0==p->coef)
231 {
232 temp=p->next;
233 delete p;
234 p=temp;
235 if (beforeP!=0) beforeP->next=p;
236 else first=p;
237 }
238 else
239 {
240 beforeP=p;
241 p=p->next;
242 }
243 }
244 return *this;
245 }
246 int main()
247 {
248 List<int> poly1,poly2,poly3;
249 int c,x;
250 cout <<"输入第一个多项式，提示：输入0 0，结束多项式输入。"<<endl;
251 while(0!=c||0!=x)
252 {
253 cout <<"请输入多项式的系数:" ;
254 cin >>c;
255 cout <<"请输入多项式的指数:" ;
256 cin >>x;
257 if (c!=0||x!=0)
258 poly1.Insert(poly1.Length(),c,x);
259 }
260 c=1;
261 cout <<"输入第二个多项式，提示：输入0 0，结束多项式输入。"<<endl;
262 while(0!=c||0!=x)
263 {
264 cout <<"请输入多项式的系数:" ;
265 cin >>c;
266 cout <<"请输入多项式的指数:" ;
267 cin >>x;
268 if (c!=0||x!=0)
269 poly2.Insert(poly2.Length(),c,x);
270 }
271 cout<<"A(x)=";
272 poly1.PrintList();
273 cout<<"B(x)=";
274 poly2.PrintList();
275 cout <<"请输入要做的运算，1加法，2乘法：";
276 cin >>c;
277 if (1==c)
278 {
279 poly1.polyAdd(poly2);
280 poly1.mergerPoly();
281 cout <<"A(x)+B(x)=";
282 poly1.PrintList();
283 }
284 else if(2==c)
285 {
286 poly1.polyMul(poly2,poly3);
287 poly3.mergerPoly();
288 cout <<"A(x)*B(x)=";
289 poly3.PrintList();
290 }
291 else cout<<"输入错误";
292
293 return 0;
294 }