Advertisement
Mizuhara_Chizuru

Program of polynomial addition and multiplication using linked list

Jan 25th, 2022
667
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Program of polynomial addition and multiplication using linked list */
  2.  
  3. /*Code by Surya a.k.a Sunny*/
  4. /* by https://www.codechef.com/users/spsc */
  5. #include <bits/stdc++.h>
  6. //#include <boost/multiprecision/cpp_int.hpp>
  7. #define lli long long
  8. #define pb push_back
  9. #define eb emplace_back
  10. #define pi 3.14159265358979323846
  11. #define MOD 1000000007
  12. #define unbuffer cin.clear(); cin.sync();
  13. #define foi(n)  for(lli i=0;i<n;i++)
  14. #define foj(n)  for(lli j=0;j<n;j++)
  15. #define test(T) lli T;cin>>T;while(T--)
  16. #define loop(i, a, b) for(int i = (a); i<= (b); i++)
  17. using namespace std;
  18. //using namespace boost::multiprecision;
  19.  
  20. struct node
  21. {
  22.   float coef;
  23.   int expo;
  24.   struct node *link;
  25. };
  26.  
  27. struct node *create(struct node *);
  28. struct node *insert_s(struct node *, float, int);
  29. struct node *insert(struct node *, float, int);
  30. void display(struct node *ptr);
  31. void poly_add(struct node *, struct node *);
  32. void poly_mult(struct node *, struct node *);
  33.  
  34. int main()
  35. {
  36.   //ios_base::sync_with_stdio(false);
  37.    //cin.tie(NULL);
  38.    //cout.tie(NULL);
  39.  
  40.    struct node *start1=NULL, *start2=NULL;
  41.    cout<<"Enter polynomial 1 :\n";
  42.    start1=create(start1);
  43.    cout<<"Enter polynomial 2 :\n";
  44.    start2=create(start2);
  45.  
  46.    /*---------X------------X-----------X-----------X----------X----------X--------X---------*/
  47.  
  48.    printf("Polynomial 1 is : ");
  49.    display(start1);
  50.    cout<<"Polynomial 2 is : ";
  51.    display(start2);
  52.  
  53.    poly_add(start1,start2);
  54.    poly_mult(start1,start2);
  55.  
  56.    return 0;
  57. }
  58.  
  59. struct node *create( struct node *start)
  60. {
  61.   int n,ex;
  62.   float co;
  63.   cout<<"Enter the number of terms ";
  64.   cin>>n;
  65.   foi(n)
  66.   {
  67.     cout<<"Enter the coefficient for the term : "<<i+1<<' ';
  68.     cin>>co;
  69.     cout<<"Enter exponent for term : "<<i+1<<' ';
  70.     cin>>ex;
  71.     start=insert_s(start,co,ex);
  72.   }
  73.   return start;
  74. }
  75.  
  76. /*---------X------------X-----------X-----------X----------X----------X--------X---------*/
  77.  
  78. struct node *insert_s(struct node *start,float co, int ex)
  79. {
  80.   struct node *ptr, *tmp;
  81.   tmp=(struct node *)malloc(sizeof(struct node));
  82.   tmp->coef=co;
  83.   tmp->expo=ex;
  84.   //list empty or expo greater than the first one
  85.   if(start==NULL || ex>start->expo)
  86.   {
  87.     tmp->link=start;
  88.     start=tmp;
  89.   }
  90.   else
  91.   {
  92.     ptr=start;
  93.     while(ptr->link!=NULL && ptr->link->expo>=ex)
  94.       ptr=ptr->link;
  95.     tmp->link=ptr->link;
  96.     ptr->link=tmp;
  97.   }
  98.   return start;
  99. }
  100.  
  101. /*---------X------------X-----------X-----------X----------X----------X--------X---------*/
  102.  
  103. struct node *insert(struct node *start, float co, int ex)
  104. {
  105.   struct node *ptr,*tmp;
  106.   tmp=(struct node *)malloc(sizeof(struct node));
  107.   tmp->coef=co;
  108.   tmp->expo=ex;
  109.   //if list is empty
  110.   if(start==NULL)
  111.   {
  112.     tmp->link=start;
  113.     start=tmp;
  114.   }
  115.   else
  116.   {
  117.     ptr=start;
  118.     while(ptr->link!=NULL)
  119.       ptr=ptr->link;
  120.     tmp->link=ptr->link;
  121.     ptr->link=tmp;
  122.   }
  123.   return start;
  124. }
  125.  
  126. /*---------X------------X-----------X-----------X----------X----------X--------X---------*/
  127.  
  128. void display(struct node *ptr)
  129. {
  130.   if(ptr==NULL)
  131.     {
  132.       cout<<"Zero polynomial\n";
  133.       return;
  134.     }
  135.     while(ptr!=NULL)
  136.     {
  137.       cout<<setprecision(1)<<fixed<<ptr->coef<<'^'<<ptr->expo;
  138.       ptr=ptr->link;
  139.       if(ptr!=NULL)
  140.         cout<<" + ";
  141.       else
  142.         cout<<"\n";
  143.     }
  144. }
  145.  
  146. /*---------X------------X-----------X-----------X----------X----------X--------X---------*/
  147.  
  148. void poly_add(struct node *p1,struct node *p2)
  149. {
  150.   struct node *start3;
  151.   start3=NULL;
  152.   while(p1!=NULL && p2!=NULL)
  153.   {
  154.     if(p1->expo>p2->expo)
  155.     {
  156.       start3=insert(start3,p2->coef,p2->expo);
  157.       p1=p1->link;
  158.     }
  159.     else if(p2->expo>p1->expo)
  160.     {
  161.       start3=insert(start3,p2->coef,p2->expo);
  162.       p2=p2->link;
  163.     }
  164.     else if(p1->expo==p2->expo)
  165.     {
  166.       start3=insert(start3,p1->coef,p1->expo);
  167.       p1=p1->link;
  168.       p2=p2->link;
  169.     }
  170.   }
  171.   //if poly2 has finished and elements left in poly 1
  172.   while(p1!=NULL)
  173.   {
  174.     start3=insert(start3,p1->coef,p1->expo);
  175.     p1=p1->link;
  176.   }
  177.   //if poly1 has finished and elements left in poly2
  178.   while(p2!=NULL)
  179.   {
  180.     start3=insert(start3,p2->coef,p2->expo);
  181.     p2=p2->link;
  182.   }
  183.   cout<<"Added polynomial is : "<<&start3;
  184. }
  185.  
  186. /*---------X------------X-----------X-----------X----------X----------X--------X---------*/
  187.  
  188. void poly_mult(struct node *p1, struct node *p2)
  189. {
  190.   struct node *start3;
  191.   struct node *p2_beg=p2;
  192.   start3=NULL;
  193.   if(p1==NULL&&p2==NULL)
  194.   {
  195.     cout<<"Multiplied polynomial is zero polynomial\n";
  196.     return;
  197.   }
  198.   while(p1!=NULL)
  199.   {
  200.     p2=p2_beg;
  201.     while(p2!=NULL)
  202.     {
  203.       start3=insert_s(start3,p1->coef*p2->coef,p1->expo+p2->expo);
  204.       p2=p2->link;
  205.     }
  206.     p1=p1->link;
  207.   }
  208.   cout<<"Multiplied Polynomial is : ";
  209.   display(start3);
  210. }
  211.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement