/*********************************************************   
  TD d'Algorithmique IN202    
  ENSTA   
    
  Polynomes creux   
      
                                        Guillaume Poupard   
*********************************************************/    
#include <stdio.h>  
#include <stdlib.h> /*contient notamment "malloc"*/   
  
struct monome{   
  int degre;  
  double coeff;   
  struct monome *suiv;  
};   
  
typedef struct monome *polynome;   
  polynome cons(polynome P, int d, double c)   
{  
  polynome nouv;   
  nouv=(polynome) malloc(sizeof(struct monome));  
  nouv->degre=d;   
  nouv->coeff=c;  
  nouv->suiv=P;   
  return nouv;  
}   
  
polynome copiepoly(polynome P)   
{  
  if (P==NULL)   
    return NULL;  
  else   
    return cons(copiepoly(P->suiv),P->degre,P->coeff);  
}   
  
void freepoly(polynome *P)   
{  
  polynome T;   
  
  if (*P!=NULL)   
    {  
      T=*P;   
      freepoly(&((*P)->suiv));  
      free(T);   
    }  
  *P=NULL;   
}  
     
void imprime(polynome P)  
{   
  if (P==NULL)  
    printf("\n");   
  else  
    {   
      if (P->degre==0)  
        printf("%.2f",P->coeff);   
      else  
      if (P->degre==1)   
        printf("%.2f*x",P->coeff);  
      else   
        printf("%.2f*x^%d",P->coeff,P->degre);  
      if (P->suiv!=NULL)   
        if (P->suiv->coeff>=0)  
          printf("+");   
      imprime(P->suiv);  
    }   
}  
   
void multscal(polynome *P, double s)  
{   
  if (s==0)  
    freepoly(P);   
  else  
  if (*P!=NULL)   
    {  
      (*P)->coeff*=s;

     multscal(&((*P)->suiv),s);  
    }   
}  
   
void addmonome(polynome *P,int d, double c)  
{   
  polynome T;  
   
  if (*P==NULL)  
    *P=cons(*P,d,c);   
  else  
  if ((*P)->degre>d)   
    *P=cons(*P,d,c);  
  else   
  if ((*P)->degre==d)  
    if (c+(*P)->coeff==0)   
      {  
        T=*P;   
        *P=(*P)->suiv;  
        free(T);   
      } 
    else  
      (*P)->coeff+=c; 
  else  
    addmonome(&((*P)->suiv),d,c); 
}  
 
void multmonome(polynome *P, int d, double c)  
{ 
  if (c==0)  
    freepoly(P); 
  else  
  if (*P!=NULL) 
    {  
      (*P)->coeff*=c; 
      (*P)->degre+=d;  
      multmonome(&((*P)->suiv),d,c); 
    }  
} 
  
void addpoly(polynome P1, polynome *P2) 
{  
  if (P1!=NULL) 
    {  
      addmonome(P2,P1->degre,P1->coeff); 
      addpoly(P1->suiv,P2);  
    } 
}  
 
polynome sommepoly(polynome P1, polynome P2)  
{ 
  polynome P;  
  P=copiepoly(P2); 
  addpoly(P1,&P);  
  return P; 
}  
 
polynome multpoly(polynome P1, polynome P2)  
{ 
  polynome P,T;  
  P=NULL; 
  while (P1!=NULL)  
    { 
      T=copiepoly(P2);  
      multmonome(&T,P1->degre,P1->coeff); 
      addpoly(T,&P);  
      freepoly(&T); 
      P1=P1->suiv;  
    } 
  return P;  
} 
  
int main(int argc, char * argv[]) 
{  
  polynome P1,P2; 
  P1=NULL;  
  addmonome(&P1,2,3); 
  addmonome(&P1,1,-2);
  addmonome(&P1,0,9); 
  addmonome(&P1,2,-1);  
  addmonome(&P1,12,3.14); 
  imprime(P1);  
  imprime(copiepoly(P1)); 
  multscal(&P1,2.5);  
  imprime(P1); 
  P2=NULL;  
  addmonome(&P2,2,1); 
  addmonome(&P2,4,-8);  
  addmonome(&P2,0,1); 
  imprime(P2);  
  multmonome(&P2,2,3); 
  imprime(P2);  
  imprime(sommepoly(P1,P2)); 
  imprime(multpoly(P1,P2));  
  exit(0); 
}