Salut! Voici quelque temps que je suis bloqué sur mon programme. En effet mon programme a pour but d'additionner deux polynomes, programme écrit en c et basé sur les listes chaînées. Mon code a l'air correct mais présente une erreur de segmentation lors de son exécution,pouvez vous m'aider? Lors de l'insertion de mon code j'ai choisis le langage c# à défaut du c dans la liste.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct Polynome *Poly;
struct Polynome{
    int degre;
    float coef;
    struct Polynome *suivant;
};

Poly new(Poly y)
{
    y->coef=0;
    y->degre=0;
    y=y->suivant;
}
int vide(Poly p)        // tester si un polynome est vide
{
    return p == NULL;   // renvoi 1 si c'est vide
}


Poly ajouteMonome(Poly polynome,float coef,int degre)
{
    Poly tmp;
    tmp=malloc(sizeof *tmp);
    tmp->coef=coef;
    tmp->degre=degre;
    tmp->suivant=polynome;
    return tmp;
}


Poly somme(Poly polynome1,Poly polynome2)
{
   Poly polynome2copie=polynome2;
   Poly sommeu=malloc(sizeof(Poly));
   new(sommeu);
    if(polynome1!=NULL)
    {
        if(polynome2!=NULL)
        {
            if(polynome1->degre==polynome2->degre)
            {
                ajouteMonome(sommeu,polynome1->coef+polynome2->coef,polynome1->degre);
                polynome1=polynome1->suivant;
                polynome2=polynome2copie;
                somme(polynome1,polynome2);
            }
            else
            {
                //polynome1=polynome1->suivant;
                polynome2=polynome2->suivant;
                somme(polynome1,polynome2);
            }
        }
        else if(polynome2==NULL)
        {
            ajouteMonome(sommeu,polynome1->coef,polynome1->degre);
            polynome1=polynome1->suivant;
            polynome2=polynome2copie;
            somme(polynome1,polynome2);
        }

    }
    else if(polynome1==NULL)
    {
        polynome2=polynome2copie;
        while(polynome2!=NULL)
        {
            if(polynome2->degre!=sommeu->degre)
            {
                ajouteMonome(sommeu,polynome2->coef,polynome2->degre);
                polynome2=polynome2->suivant;
                sommeu=sommeu->suivant;
            }
            else
            {
                polynome2=polynome2->suivant;
                sommeu=sommeu->suivant;
            }
        }
    }

    return sommeu;
}

void afficher(Poly polynome)
{
    if (vide(polynome))
    {
        printf(" Liste vide \n");
        exit(EXIT_FAILURE);
    }
    if(polynome->suivant==NULL)
    {
        if(polynome->coef!=0 && polynome->degre>1)
        {
            printf("%fX^%d ",polynome->coef,polynome->degre); 
        }   
        else if(polynome->coef!=0 && polynome->degre==1)
        {
            printf("%fX ",polynome->coef); 
        }
    }
    else
    {
        if(polynome->coef!=0 && polynome->degre>1)
        {
            printf("%fX^%d+ ",polynome->coef,polynome->degre);
            afficher(polynome->suivant);    
        } 
        else if(polynome->coef!=0 && polynome->degre==1)
        {
            printf("%fX+ ",polynome->coef);
            afficher(polynome->suivant);  
        }
    }  
}

/*void saisie(Poly *polynome)
{
    int rep;
    float coef;
    int degre;
    do{
        printf("Coefficient: ");
        scanf("%f",&coef);
        if(coef!=0)
        {
            printf("Dégré: ");
            scanf("%d",&degre);
            polynome=ajouteMonome(polynome,coef,degre);
        }
        printf("Continuer? 0/1 : ");
        scanf("%d",&rep);
    }while(rep==1);
}*/

int main()
{
    Poly polynome1=malloc(sizeof(Poly));
    Poly polynome2=malloc(sizeof(Poly));
    Poly sommefinale=malloc(sizeof(Poly));
    new(polynome1);
    new(polynome2);
    new(sommefinale);
    //int rep;
    //float coef;
    //int degre;
    //printf("Entrez les coefficients et dégré du premier polynôme:\n");
    polynome1=ajouteMonome(polynome1,2,4);
    polynome1=ajouteMonome(polynome1,3,3);
    polynome1=ajouteMonome(polynome1,7,2);
    polynome1=ajouteMonome(polynome1,8,1);
    polynome1=ajouteMonome(polynome1,1,5);
    //if(polynome1==NULL){printf("P1 est vide");}else{printf("P1 n'est pas vide");}
    //saisie(polynome1);
    /*do{
        printf("Coefficient: ");
        scanf("%f",&coef);
        if(coef!=0)
        {
            printf("Dégré: ");
            scanf("%d",&degre);
            polynome1=ajouteMonome(polynome1,coef,degre);
        }
        printf("Continuer? 0/1 : ");
        scanf("%d",&rep);
    }while(rep==1);*/

    printf("\nP1: ");
    afficher(polynome1);
    
    //printf("\nEntrez les coefficients et dégré du deuxième polynôme:\n");
    polynome2=ajouteMonome(polynome2,5,3);
    polynome2=ajouteMonome(polynome2,4,2);
    polynome2=ajouteMonome(polynome2,8,1);
    //saisie(polynome2);
    /*do{
        printf("Coefficient: ");
        scanf("%f",&coef);
        if(coef!=0)
        {
            printf("Dégré: ");
            scanf("%d",&degre);
            polynome2=ajouteMonome(polynome2,coef,degre);
        }
        printf("Continuer? 0/1 : ");
        scanf("%d",&rep);
    }while(rep==1);*/

    printf("\nP2: ");
    afficher(polynome2);

    sommefinale=somme(polynome1,polynome2);
    printf("\nLa somme donne : ");
    //if(sommefinale==NULL){printf("Sfinale est vide");}else{printf("Sfinale n'est pas vide");}
    afficher(sommefinale);
    printf("\n");
    return 0;
}

Ce n'est pas une bonne idée que de définir une structure comme un pointeur vers une structure. On ne sait pas qui fait quoi.
Dans ta fonction new(), je note:
    y=y->suivant;
C'est un bon moyen de tourner en rond ...
D'autant plus qu'on ne sait pas ce que vaut y->suivant.
Tu annules ton pointeur de cette façon.
Je verrais plutôt:
    y->suivant = NULL;

Je mettrais le malloc dans la fonction new().

Je ne sais pas si j'ai bien compris ta logique, mais j'ajouterais les puissances dans la liste en ordre décroissant.

La fonction somme() semble récursive, mais il me semble que je le ferais autrement en profitant des puissances identiques.

Elle retournerait un pointeur vers l'élément suivant.

Et tu ne fais jamais de free()

edit:
Voici comment je conçois la fonction somme() avec une définition correcte de la structure et qui retournerait la somme dans polynome1:
polynome1 = somme(polynome1, polynome2);
Je suppose que les éléments sont placés par ordre décroissants de degré ou puissance.
-
Poly *somme(Poly *polynome1, Poly *polynome2) {
    if(polynome1 && polynome2) {
        if(polynome1->degre == polynome2->degre) {
            polynome1->coeff += polynome2->coeff;
            Poly *scratch = polynome2;
            polynome2 = polynome2->suivant;
            free(scratch);
            polynome1->suivant = somme(polynome1->suivant, polynome2);
            return polynome1;
        } else if(polynome1->degre > polynome2->degre) {
            polynome1->suivant = somme(polynome1->suivant, polynome2);
            return polynome1;
        } else {
            polynome2->suivant = somme(polynome1, polynome2->suivant);
            return polynome2;
        }
    }
    if(polynome1) {
        return polynome1;
    } else {
        return polynome2;
    }
}

-
Edité par PierrotLeFou 10 janvier 2022 à 7:51:08

Bonjour,

La première chose à faire est de compiler en mode debug et en demandant d'afficher plus de warnings →

$ gcc -Wall -Wextra -o t t.c
t.c: In function ‘new’:
t.c:16:1: warning: control reaches end of non-void function [-Wreturn-type]
   16 | }
      | ^

Bon, sans lire ton code je trouve déjà certainement une erreur …

Ensuite comme le souligne Pierrot il y a pas mal de problèmes provenant de ta phase d'analyse et conception.

On aura beau appeler ça des polynômes, ça reste des listes simplement chaînées.
Il n'y a pas de descripteur de liste, même aussi simple qu'un simple pointeur.
Pour que ça marche, il faut pouvoir ajouter les éléments en ordre de degré descendant (ou peut-être ascendant?)
Or sans descripteur de liste, c'est difficile d'ajouter au début d'une telle liste.

En dehors de tout ce qui a été dit, il y a un autre probème: quid si les polynomes contiennent plus d'une variable (x et y par exemple) ? Ou une constante ? Mais comme on n'a pas l'énoncé de l'exercice, ce n'est peut-être pas le cas.

Je retire ce que j'ai dit, la manière de fournir les données montre qu'il n'y a qu'une variable.

-
Edité par edgarjacobs 10 janvier 2022 à 19:48:25

Et une constante c'est avec l'exposant 0
Ça se fait peut-être avec deux variables. Je pense que l'ordre de tri serait le suivant:
+ ordre descendant pour la première variable.
+ ordre ascendant pour la seconde variable s'il y a égalité pour la première.

edit:
La fonction affiche() n'a pas besoin d'être récursive. Elle peut accepter des exposants négatifs, mais c'est moins joli.
Si les coeeficients étaient des entiers, on pourrait mêm les supprimer s'ils étaient égaux à +1.
-
void affiche(Poly *polynome) {
    char *plus = "";
    while(polynome) {
        if(polynome->coef != 0) {
            if(polynome->coef < 0)
                plus = "-";
            printf("%s%f", plus, polynome->coef);
            plus = "+";
            if(polynome->degre != 0) {
                printf("X");
                if(polynome->degre != 1)
                    printf("^%d", polynome->degre);
            }
        }
        polynome = polynome->suivant;
    }
    printf("\n");
}

-
Edité par PierrotLeFou 11 janvier 2022 à 3:28:17

Merci PierrotLeFou pour ta contribution! Je concevais bien l'idée de classer les coef par ordre décroissant mais je voulais d'abord trouver un algorithme qui fonctionne peu importe l'ordre. Mais je remarque que les classés seraient avantageux. 

Tu as également donné ta conception de la fonction somme()  en disant cites: <Voici comment je conçois la fonction somme() avec une definition correct de la structure>. "Definition correct de la structure", qu'est ce que tu as voulu dire par là? Je n'ai pas compris!

Tu as écrit:
typedef struct Polynome *Poly;
Tu définis un pointeur vers une structure.
si je fais  Poly tralala
Ça peut porter à confusion. Est-ce la structure ou un pointeur ver la structure?
et Poly **tralala ?
C'est une façon de travailler qui amène des problèmes.

Il vaut mieux écrire:

typedef struct Polynome Poly et mettre les * où c'est nécessaire.

-
Edité par PierrotLeFou 11 janvier 2022 à 15:26:03

Les listes chainées sont-elles imposées? Car le problème peut être résolu avec de simples tableaux de structures: poly1[], poly2[] et sumpoly[]. Evidemment, dans ma solution, le nombre d'exposants pour le réultat est limité (à 256, ce qui devrait amplement suffire, mais 16K exposants ne poserait aucun probème), et je suppose qu'il n'y a qu'une variable.

-
Edité par edgarjacobs 11 janvier 2022 à 17:20:34

On pourrait aller plus simple.
Si la puissance maximum est N, on se fait deux tableaux de coefficients de longueur N+1 dans lequel l'indice correspond à la puissance (ou degré).
On met un coefficient de 0 pour les puissances absentes.
L'addition se résume à la somme des élément correspondants dans les deux tableaux.

J'ai utilisé une structure car je voyais la définition des polynômes comme ceci:

struct poly {
	int degree;
	int coef;
};


int main(void) {
	struct poly poly1[]={{8,-6},{11,13},{4,3},{2,6},{0,12}};
	struct poly poly2[]={{7,1},{3,2},{5,2},{4,6},{2,1},{8,4},{9,3}};
	struct poly sum[256];
	....

C'est un extrait de mon code, mais je ne vais pas (déjà) mettre le reste :-)

-
Edité par edgarjacobs 11 janvier 2022 à 18:15:39

Ta méthode a l'avantage de supporter de grandes puissances ou facilement des puissances négatives dans relativement peu d'espace si on a beaucoup de trous.
Cependant, tu dois trier par puissance pour un algorithme d'addition efficace.
Ma méthode ne peut pas facilement supporter de grandes puisssances mais peut supporter des puissances négatives avec un biais.
Je n'ai pas besoin de trier par puissance pour additionner.

PierrotLeFou a écrit:

Cependant, tu dois trier par puissance pour un algorithme d'addition efficace.

Exact. Et j'emploie qsort() sur poly1 et poly2

Extrait de code (suite) :-)

int comp(void const *v1,void const *v2) {
	return(((struct poly *)v1)->degree > ((struct poly *)v2)->degree);
}


size_t SumPoly(struct poly sum[],struct poly p1[],int np1,struct poly p2[],int np2) {
	qsort(p1,np1,sizeof(struct poly),comp);
	qsort(p2,np2,sizeof(struct poly),comp);
	....
}


int main(void) {
    struct poly poly1[]={{8,-6},{-11,13},{4,3},{2,6},{0,12}};
    struct poly poly2[]={{7,1},{3,2},{5,2},{4,6},{2,1},{8,4},{9,3}};
 	struct poly sum[256];

	size_t np1=sizeof(poly1)/sizeof(struct poly);
	size_t np2=sizeof(poly2)/sizeof(struct poly);
	size_t nsum=SumPoly(sum,poly1,np1,poly2,np2);

-
Edité par edgarjacobs 11 janvier 2022 à 19:14:57

@Edgarjacobs, oui les listes chaînées ont été imposées sinon j'avais même commencé par le faire avec des tableaux et c'était assez simple!

@PierrotLeFou, j'ai compris ce que tu veux dire. J'ai apoorté les différentes modifications nécéssaires à mon programme et ça marche! MERCI BEAUCOUP

-
Edité par SteeveIlboudo 12 janvier 2022 à 18:25:22