1 // CPolyn.cpp
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <iostream>
  5 #include <math.h>
  6 #define eps 1e-8
  7 const int nArrA = 5;
  8 const int nArrB = 5;
  9 const int nArrD = 1;
 10 
 11 static int nA[nArrA] ={0, 8, 1, 17, 22};
 12 static float cA[nArrA] ={7, 9, 3, 5, 8};
 13 
 14 static int nB[nArrB] ={0, 1, 7, 8, 22};
 15 static float cB[nArrB] = {-7,8, 22, -9, -8};
 16 
 17 static int nC[nArrB] ={0, 1, 7, 8, 22};
 18 static float cC[nArrB] = {7,-8, -22, 9, 8};
 19 
 20 static int nD[nArrD] ={1};
 21 static float cD[nArrD] = {2};
 22 
 23 class CPolyn;
 24 class CNode{
 25     int expn;
 26     float coef;
 27     CNode *prior;
 28     CNode *next;
 29 public:
 30     friend class CPolyn;
 31     CNode()
 32     {
 33         expn = 0;
 34         coef = 0;
 35         prior = 0;
 36         next = 0;
 37     }
 38     friend CPolyn &operator +(CPolyn &obj1, CPolyn &obj2);
 39     friend CPolyn &operator -(CPolyn &obj1, CPolyn &obj2);
 40     friend CPolyn &MultiplyNode(CPolyn &obj, CNode *NewNode);
 41     friend CPolyn &operator *(CPolyn &obj1, CPolyn &obj2);
 42     friend void operator +=(CPolyn &obj1, CPolyn &obj2);
 43     friend void operator -=(CPolyn &obj1, CPolyn &obj2);
 44     friend void operator *=(CPolyn &obj1, CPolyn &obj2);
 45 };
 46 
 47 class CPolyn{
 48     int Length;
 49     CNode *head;
 50 public:
 51     CPolyn(){Length = 0;head =0;}
 52     int InsertNode(CNode *NewNode);
 53     int CreatePolyn(int *nArr, float *cArr, int N);
 54     int PolynLength();
 55     CNode *GetHead();
 56     void SetHead(CNode *h=0);
 57     CNode *GetTail();
 58     CNode *FindNode(float c);
 59     CPolyn &DeleteNode(CNode *Node);
 60     CPolyn &DeleteZeros();
 61     int CopyCPolyn(CPolyn &src);
 62     friend CPolyn &operator +(CPolyn &obj1, CPolyn &obj2);
 63     friend CPolyn &operator -(CPolyn &obj1, CPolyn &obj2);
 64     friend CPolyn &MultiplyNode(CPolyn &obj, CNode *NewNode);
 65     friend CPolyn &operator *(CPolyn &obj1, CPolyn &obj2);
 66     friend void operator +=(CPolyn &obj1, CPolyn &obj2);
 67     friend void operator -=(CPolyn &obj1, CPolyn &obj2);
 68     friend void operator *=(CPolyn &obj1, CPolyn &obj2);
 69     void PrintPolyn();
 70     void InvPrintPolyn();
 71     void DeletePolyn();
 72 };
 73 
 74     
 75 int CPolyn::CopyCPolyn(CPolyn &src)
 76 {
 77     CNode *tmp;
 78     CNode *p= src.head;
 79     if(head)
 80     {this->DeletePolyn();
 81      this->head =0;}
 82 
 83     if(p==0)
 84      {return 0;}
 85 
 86     while(p)
 87     {
 88         tmp = new CNode;
 89         tmp->coef = p->coef;
 90         tmp->expn = p->expn;
 91         if(this->InsertNode(tmp) == 0)
 92         {
 93             return 0;
 94         }
 95         p = p->next;
 96     }
 97     return 1;
 98 }
 99 
100 CPolyn &operator +(CPolyn &obj1, CPolyn &obj2)
101 {
102     CPolyn cpolyn;
103     cpolyn.CopyCPolyn(obj1);
104     CNode *p1, *p2;
105     p1 = obj2.GetHead();
106     while(p1)
107     { 
108        p2 = new CNode;
109        p2->expn = p1->expn;
110        p2->coef = p1->coef;
111        if(cpolyn.InsertNode(p2)==0)
112        {
113          printf("1. error CPolyn operator +(CPolyn &obj1, CPolyn &obj2)\n");
114          exit(1);
115        }
116        p1=p1->next;
117     } 
118     cpolyn.DeleteZeros();
119     return cpolyn;
120 }
121 
122 void operator +=(CPolyn &obj1, CPolyn &obj2)
123 {
124     CNode *p1, *p2;
125     p1 = obj2.GetHead();
126     while(p1)
127     { 
128        p2 = new CNode;
129        p2->expn = p1->expn;
130        p2->coef = p1->coef;
131        if(obj1.InsertNode(p2)==0)
132        {
133          printf("1. error CPolyn operator +=(CPolyn &obj1, CPolyn &obj2)\n");
134          exit(1);
135        }
136        p1=p1->next;
137     } 
138     obj1.DeleteZeros();
139 }
140 
141 
142 CPolyn &operator -(CPolyn &obj1, CPolyn &obj2)
143 {
144     CPolyn polyn;
145     CNode *p;
146     if(polyn.CopyCPolyn(obj2)==0)
147     {printf("operator - error!\n");}
148     p = polyn.head;
149     while(p)
150     {
151         p->coef = -p->coef;
152         p = p->next;
153     }
154     return obj1+polyn;
155 }
156 
157 void operator -=(CPolyn &obj1, CPolyn &obj2)
158 {
159     CNode *p1, *p2;
160     p1 = obj2.GetHead();
161     while(p1)
162     { 
163        p2 = new CNode;
164        p2->expn = p1->expn;
165        p2->coef = -p1->coef;
166        if(obj1.InsertNode(p2)==0)
167        {
168          printf("1. error CPolyn operator +=(CPolyn &obj1, CPolyn &obj2)\n");
169          exit(1);
170        }
171        p1=p1->next;
172     } 
173     obj1.DeleteZeros();
174 }
175 
176 void operator *=(CPolyn &obj1, CPolyn &obj2)
177 {
178     CPolyn cpolyn;
179     CNode *exchange;
180     cpolyn = obj1*obj2;
181     exchange = obj1.head;
182     obj1.head = cpolyn.head;
183     cpolyn.head = exchange;
184     cpolyn.DeletePolyn();
185 
186 } 
187 
188 CPolyn &MultiplyNode(CPolyn &obj, CNode *NewNode)
189 {
190       CPolyn cpolyn;
191      CNode *p;
192      cpolyn.CopyCPolyn(obj);
193      p = cpolyn.head;
194     while (p)
195    {
196      p->coef = p->coef*NewNode->coef;
197      p->expn = p->expn+NewNode->expn;
198      p = p->next;
199    }
200     return cpolyn;
201 }
202 
203 CPolyn &operator *(CPolyn &obj1, CPolyn &obj2)
204 {
205     CPolyn cpolyn, *tmp;
206     CNode *p2;
207 
208     p2 = obj2.head;
209     while (p2)
210     {
211         tmp= new CPolyn; 
212         *tmp = MultiplyNode(obj1, p2);
213         cpolyn+=(*tmp);
214         tmp->DeletePolyn();
215         delete tmp;
216         p2 = p2->next;
217     }
218    return cpolyn;
219 }
220 
221 int CPolyn::InsertNode(CNode *NewNode)
222 {
223     CNode *pPre, *pBac;
224     if(head == 0)
225     {
226         head = NewNode;
227         head->prior = 0;
228         head->next = 0;
229         return 1;
230     }
231     else if(head->expn>NewNode->expn)
232     {
233         head->prior= NewNode;
234         NewNode->next = head;
235         head = NewNode;
236         head->prior = 0;
237         return 1;
238     }
239     else if (head->expn == NewNode->expn)
240     {
241         head->coef+=NewNode->coef;
242         if(head->coef<=eps)
243          {
244            delete NewNode;
245         }
246         return 1;
247     }
248 
249     pPre = head;
250     while(pPre->next)
251     {
252         pBac = pPre->next;
253         if(pPre->expn==NewNode->expn)
254         {
255             pPre->coef+=NewNode->coef;
256             if(pPre->coef<=eps)
257             {
258                 delete NewNode;
259             }
260              return 1;
261         }
262         else if(pPre->expn<NewNode->expn&&pBac->expn>NewNode->expn)
263         {
264             
265             pPre->next = NewNode;
266             NewNode->prior = pPre;
267             NewNode->next = pBac;
268             pBac->prior = NewNode;
269              return 1;
270         }
271         pPre = pPre->next;
272     }
273 
274     if(pPre->expn>NewNode->expn)
275     {
276       NewNode->prior= pPre->prior;
277       NewNode->next=pPre;
278       pPre->prior = NewNode;
279       pPre = NewNode; 
280       return 1;
281     }
282     else if(pPre->expn == NewNode->expn)
283     {
284       pPre->coef+=NewNode->coef;
285       if(pPre->coef<=eps)
286        {
287           delete NewNode;
288        }
289       return 1;      
290     }
291     else
292     {
293         pPre->next = NewNode;
294         NewNode->prior = pPre;
295         NewNode->next = 0;
296         return 1;
297     } 
298     return 0;
299 }
300 
301 
302 int CPolyn::CreatePolyn(int *nArr, float *cArr, int N)
303 {
304     if(head)
305     {this->DeletePolyn();
306       this->head = 0;}
307     CNode *p1;
308     int i;
309     for(i=0; i<N; i++)
310         {
311             p1 = new CNode;
312             p1->expn = nArr[i];
313             p1->coef = cArr[i];
314              if(this->InsertNode(p1)==0)
315                 return 0;
316         }
317     
318     return 1;
319 }
320 
321 int CPolyn::PolynLength()
322 {
323     Length =0;
324     CNode *p;
325     p = this->head;
326     while(p)
327     {
328         Length++;
329         p=p->next;
330     }
331     return Length;
332 }
333 
334 CNode *CPolyn::GetHead()
335 {
336     return this->head;
337 }
338 
339 void CPolyn::SetHead(CNode *h)
340 {
341     this->head = h;
342 }
343 
344 CNode *CPolyn::GetTail()
345 {
346     CNode *h=head; 
347     CNode *tmpNode;
348     if (h==0)
349         return 0;
350     else
351         tmpNode = h;
352     while(tmpNode->next)
353         tmpNode=tmpNode->next;
354     return tmpNode;
355 }
356 
357 
358 CNode *CPolyn::FindNode(float c)
359 {
360     CNode *p;
361     if(head ==0)
362          return 0;
363     else
364         {p=head;}
365 
366     while(p)
367     {
368         if(abs(p->coef -c)<eps)
369             return p;
370         else 
371             p=p->next;
372     }
373     return 0;
374 }
375 
376 CPolyn &CPolyn::DeleteNode(CNode *Node)
377 {
378        CNode *pCur, *pPre;
379     pCur = Node;    
380    if(pCur == head)
381     {
382         head->next->prior = 0;
383         head=head->next;
384         delete pCur;
385     }
386     else if(pCur == this->GetTail())
387     {
388         pPre = pCur->prior;
389         pPre->next = 0;
390         delete pCur;
391     }
392     else
393     {
394         pPre = pCur->prior;
395         pPre->next = pCur->next;
396         pCur->next->prior = pPre; 
397         delete pCur;
398     } 
399     return *this;
400  
401 }
402 CPolyn &CPolyn::DeleteZeros()
403 {
404     CPolyn tmp;
405     CNode *flag;
406     flag = this->FindNode(0);
407     while(flag)
408     {
409         *this = this->DeleteNode(flag);
410         flag = this->FindNode(0);    
411     }
412     return *this;
413 }
414 
415 void CPolyn::PrintPolyn() 
416 {
417     CNode *hptr;
418     hptr =head;
419      
420     if(hptr)
421     { if(hptr->expn==0)
422         printf("%5.0f", hptr->coef);
423         else 
424         printf("%5.0f*x^%d",hptr->coef,hptr->expn);
425     }
426     hptr = hptr->next;
427     while(hptr)
428     {
429         if(hptr->coef>=0)
430         {printf("+%5.0f*x^%d",hptr->coef,hptr->expn);}
431         else
432         { printf("%5.0f*x^%d",hptr->coef,hptr->expn);}
433 
434        hptr = hptr->next;
435     }
436     printf("\n");
437 }
438 
439 void CPolyn::InvPrintPolyn() 
440 {
441     CNode *hptr;
442     hptr =this->GetTail();
443     while(hptr)
444     {
445         if(hptr->coef>=0)
446         {printf("+%3.0f*x^%d",hptr->coef,hptr->expn);}
447         else
448         { printf("%3.0f*x^%d",hptr->coef,hptr->expn);}
449 
450         hptr = hptr->prior;
451     }
452     printf("\n");
453 }
454 
455 void CPolyn::DeletePolyn()
456 {
457    CNode *p, *temp;
458    p =head;
459    while (p)
460    {
461      temp = p;
462      p = p->next;
463      delete temp;
464    }
465 }
466 
467 int main()
468 {
469    CPolyn polynA, polynB, polynC, polynD, polynAdd, polynSubtract;
470    CPolyn polynE, polynF, polynG, polynMulti;
471    int n;
472 
473    if(polynA.CreatePolyn(nA, cA, nArrA)==0||polynB.CreatePolyn(nB, cB, nArrB)==0)
474    {
475     printf("CreatePolyn failed!\n");
476      exit(1);
477    }
478 
479    polynA.PrintPolyn();
480    printf("The Length of headA is %d\n", polynA.PolynLength());
481    
482    polynB.PrintPolyn();
483    printf("The Length of headB is %d\n", polynB.PolynLength());
484 
485    printf("InvPrintPlyn\n");
486    polynA.InvPrintPolyn();
487 
488    polynAdd = polynA + polynB;
489 
490    polynAdd.PrintPolyn();
491    printf("InvPrintPlyn\n");
492    polynAdd.InvPrintPolyn();
493 
494    if(polynC.CreatePolyn(nC, cC, nArrB)==0)
495    {printf("CreatePolynC failed!\n");
496     exit(1);}
497    polynC.PrintPolyn();
498 
499    polynSubtract = polynA - polynC;
500    polynSubtract.PrintPolyn();
501    
502    printf("**********************\n");
503    if(polynD.CreatePolyn(nD, cD, nArrD)==0)
504    {printf("CreatePolynD failed!\n");
505     exit(1);}
506    polynD.PrintPolyn();
507 
508    for(n = 1; n<6; n++)
509    {
510      polynE+=polynD;
511    }
512    polynE.PrintPolyn();
513 
514    for(n = 1; n<4; n++)
515    {
516      polynE-=polynD;
517    }
518    polynE.PrintPolyn();
519 
520    printf("********************\n");
521 
522    if(polynF.CreatePolyn(nA, cA, nArrA)==0||polynG.CreatePolyn(nB, cB, nArrB)==0)
523    {
524     printf("CreatePolyn failed!\n");
525      exit(1);
526    }
527    polynF.PrintPolyn();
528    polynG.PrintPolyn();
529 
530    polynMulti = polynF*polynG;
531    polynMulti.PrintPolyn();
532    
533    printf("********************************\n");
534 
535    polynA.DeletePolyn();
536    polynA.SetHead(new CNode) ;
537 
538    if(polynA.CreatePolyn(nA, cA, nArrA)==1)
539    {polynA.PrintPolyn();}
540    polynB.PrintPolyn();
541 
542    polynA*=polynB;
543    polynA.PrintPolyn();
544 
545    for (n=1; n<5; n++)
546    {
547        polynC*=polynD;   
548    }
549    polynC.PrintPolyn();
550 
551 
552    polynA.DeletePolyn();
553    polynB.DeletePolyn();
554    polynAdd.DeletePolyn();
555    polynC.DeletePolyn();   
556    polynSubtract.DeletePolyn();
557    polynD.DeletePolyn();
558    polynE.DeletePolyn();
559    polynF.DeletePolyn();
560    polynG.DeletePolyn();
561    polynMulti.DeletePolyn();
562 
563     return 0;
564 }