#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct mono
{
    int degre;
    float coeff;
    struct mono *pg;
    struct mono *pd;
}monome;
typedef struct poly
{
    monome *first;
    monome *last;
}polycreux;
polycreux init(polycreux p)
{
    p.first=NULL;
    p.last=NULL;
    return p;
}
polycreux supprimer(polycreux p, int deg)
{
    monome *m1;
    if(p.first==NULL)
    {
        printf("erreur");
    }
    else
    {
        if(p.first->degre==deg)
        {
            p.first=p.first->pd;
            free(p.first->pg);
            p.first->pg=NULL;
        }
        else if(p.last->degre==deg)
        {
            p.last=p.last->pg;
            free(p.last->pd);
            p.last->pd=NULL;
        }
        else
        {
            m1=p.first;
            while(m1!=NULL && m1->degre!=deg)
            {
                m1=m1->pd;
            }
            if(m1==NULL)
            {
               printf("element n existe pas!!");
            }
            else
            {
                m1->pg->pd=m1->pd;
                m1->pd->pg=m1->pg;
                free(m1);
            }
        }
    }
    return p;

}
polycreux  inserer(polycreux p , float coef,int deg)
{
    monome *m1,*m2;
    m1=p.first;
    while(m1!=NULL && m1->degre!=deg)
    {
        m1=m1->pd;
    }
    if(m1!=NULL)
    {
        m1->coeff=m1->coeff+coef;
        if(m1->coeff==0)
        {
            p=supprimer(p,deg);
        }
    }
    else
    {
        m1=(monome*)malloc(sizeof(monome));
        m1->coeff=coef;
        m1->degre=deg;
        if(p.first==NULL)
        {
            m1->pd=NULL;
            m1->pg=NULL;
            p.first=m1;
            p.last=m1;
        }
        else
        {
            if(p.first->degre<deg)
            {
                m1->pg=NULL;
                m1->pd=p.first;
                p.first->pg=m1;
                p.first=m1;
            }
            else if (p.last->degre>deg)
            {
                m1->pd=NULL;
                m1->pg=p.last;
                p.last->pd=m1;
                p.last=m1;
            }
            else
            {
                m2=p.first->pd;
                while(m2->pd!=NULL && deg<m2->degre)
                {
                    m2=m2->pd;
                }
                m1->pd=m2;
                m1->pg=m2->pg;
                m2->pg->pd=m1;
                m2->pg=m1;
            }
        }
    }
    return p;

}
void affichage1(polycreux p)
{
    monome* m;
    m=p.first;
    while(m!=NULL)
    {
        printf("%.1fX%d    ",m->coeff,m->degre);
        printf("\n");
        m=m->pd;
    }
}
void affichage2(polycreux p)
{
    monome* m;
    m=p.last;
    while(m!=NULL)
    {
        printf("%.fX%d    ",m->coeff,m->degre);
        printf("\n");
        m=m->pg;
    }
}
polycreux destruction(polycreux p)
{
    monome *m;
    while(p.first==NULL)
    {
        m=p.first;
        p.first=p.first->pd;
        free(m);
    }
    init(p);
    return p;
}
polycreux multipscal(polycreux p,float s)
{
    monome *m;
    m=p.first;
    while(m!=NULL)
    {
        m->coeff=m->coeff*s;
        m=m->pd;
    }
    return p;
}
polycreux multipmono(polycreux p,float c,int d)
{
    monome *m;
    m=p.first;
    while(m!=NULL)
    {
        m->coeff=m->coeff*c;
        m->degre=m->degre+d;
        m=m->pd;
    }
    return p;
}

polycreux somme(polycreux p1,polycreux p2,polycreux p3)
{
     monome *m;
     m=p1.first;
     while(m!=NULL)
     {
         p3=inserer(p3,m->coeff,m->degre);
         m=m->pd;
     }
     m=p2.first;
     while(m!=NULL)
     {
         p3=inserer(p3,m->coeff,m->degre);
         m=m->pd;
     }
     return p3;
}

polycreux soustraction(polycreux p1,polycreux p2,polycreux p3)
{
     monome *m;
     m=p1.first;
     while(m!=NULL)
     {
         p3=inserer(p3,m->coeff,m->degre);
         m=m->pd;
     }
     m=p2.first;
     while(m!=NULL)
     {
         p3=inserer(p3,-m->coeff,m->degre);
         m=m->pd;
     }
     return p3;
}

int main()
{
    int choix,d;
    float c,s;
    polycreux p1,p2,p3;
    do
  {
    printf("entrer votre choix");
    printf("\n");
    printf("entrer 1 pour initialiser le polynome");
    printf("\n");
    printf("entrer 21 pour  l insertion dans p1 ");
    printf("\n");
    printf("entrer 22 pour l insertion dans p2");
    printf("\n");
    printf("entrer 31 pour la suppression dans p1");
    printf("\n");
    printf("entrer 32 pour la suppression dans p2");
    printf("\n");
    printf("entrer 41 pour affichage p1 par ordre decroissant");
    printf("\n");
    printf("entrer 42cpour affichage p2 par ordre decroissant");
    printf("\n");
    printf("entrer 51 pour affichage p1 par ordre croissant");
    printf("\n");
    printf("entrer 52 pour affichage p2 par ordre croissant");
    printf("\n");
    printf("entrer 61 pour la destruction p1");
    printf("\n");
    printf("entrer 62 pour la destruction p1");
    printf("\n");
    printf("entrer 71 pour la multiplication par scalaire *p1");
    printf("\n");
    printf("entrer 72 pour la multiplication par scalaire*p2");
    printf("\n");
    printf("entrer 81 pour la multiplication par un monome *p1");
    printf("\n");
    printf("entrer 82 pour la multiplication par un monome *p2");
    printf("\n");
    printf("entrer 9 pour la somme de p1 et p2 ");
    printf("\n");
    printf("entrer 10 pour la soustraction de p1 et p2");
    printf("\n");
    printf("enter 0 pour sortir");
    printf("\n");
    scanf("%d",&choix);
    clrscr();
    switch(choix)
    {
    case 1 :
        init(p1);
        init(p2);
        init(p3);
        break;
    case 21 :
        printf("enter le degre est le coeff");
        scanf("%d",&d);
        scanf("%f",&c);
        p1=inserer(p1,c,d);
        break;
    case 22 :
        printf("enter le degre est le coeff");
        scanf("%d",&d);
        scanf("%f",&c);
        inserer(p2,c,d);
        break;
    case 31 :
        printf("enter le degre");
        scanf("%d",&d);
        p1=supprimer(p1,d);
        break;
    case 32 :
        printf("enter le degre");
        scanf("%d",&d);
        p2=supprimer(p2,d);
        break;
    case 41 :
        affichage1(p1);
        break;
    case 42 :
        affichage1(p2);
        break;
    case 51 :
        affichage2(p1);
        break;
    case 52 :
        affichage2(p2);
        break;
    case 61 :
        p1=destruction(p1);
        break;
    case 62 :
        p2=destruction(p2);
        break;
    case 71 :
        printf("entrer le scalaire");
        scanf("%f",&s);
        p1=multipscal(p1,s);
        break;
    case 72 :
        printf("entrer le scalaire");
        scanf("%f",&s);
        p2=multipscal(p2,s);
        break;
    case 81 :
        printf("entrer le degre du monome et le coeff");
        scanf("%d",&d);
        scanf("%f",&c);
        p1=multipmono(p1,c,d);
        break;
    case 9 :
        p3=somme(p1,p2,p3);
        break;
    case 10 :
        p3=soustraction(p1,p2,p3);
        break;
    }
    clrscr();
  }while(choix!=0);
  return 0;
}