Pointeur int dans fonction récursive

Question

J'ai un problème pour récupérer un entier qui est paramètre d'une
fonction récursive. Cette fonction me renvoie une liste chainée et
la valeur de l'entier doit être modifiée à chaque appel de fonction
et me sert dans des boucles de la fonction; c'est pour ça que j'utilise
un pointeur sur cet entier. Mon problème est que le programme me renvoie
dans ma liste chainée un entier qui n'a rien à voir (-81265478 ou
quelque chose du genre au lieu de 0 ou 1). Voici mon code complet.
J'espère qu'il n'est pas trop long. Avec N=1, ça déconne et
avec N>1, ça plante.

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#include<math.h>

constint N=3;

typedefstruct antichaine{
int tab[N];
struct antichaine *prec;
struct antichaine *suiv;
}chaine;

double fact(int n);
chaine chainer(int n, int c, int val[], int *max, chaine *debinf);
void affichage(chaine ch[], int n, int nb_ch);

void main(){
int n=N;
int taille_esp=(int)pow((double)2,(double)n);
int m=(int)n/2;
int nb_ch=fact(n)/(fact(n-m)*fact(m)); //nombre de chaînes
n=N;

chaine *temp=NULL;
temp=(chaine*)malloc(sizeof(struct antichaine));

int val[2]={0,1};
int i=0, j=0, k=0, c=n, max=2;

chaine *ch=(chaine*)calloc(nb_ch,sizeof(struct antichaine));
chaine *debinf=NULL;
for(i=0;i<nb_ch;i++){

ch[i]=chainer(n,c,val,&max,debinf);
}
affichage(ch,n,nb_ch);
}

double fact(int n){
if(n<0){
exit (EXIT_FAILURE);
}
elseif(n==1 || n==0){
return1;
}return n*fact(n-1);
}

chaine chainer (int n,int c, int val[], int *max, chaine *debinf){
int k,l;
chaine *deb=(chaine*)malloc(sizeof(struct antichaine));
chaine *parcours;
chaine *parcoursinf;
chaine *tmp;
deb->prec=NULL;
deb->suiv=NULL;
parcours=deb;

if(debinf==NULL || (*max)<0){
(*max)=2;
if(n>1){
debinf=(chaine*)malloc(sizeof(struct antichaine));
*debinf=chainer(n-1,c,val,max,debinf);
}
elseif(n=1){
for(k=0;k<2;k++){
tmp=(chaine*)malloc(sizeof(struct antichaine));
tmp->prec=NULL;
tmp->suiv=NULL;
tmp->tab[n-1]=val[k];
parcours->suiv=tmp;
tmp->prec=parcours;
tmp->suiv=NULL;
parcours=parcours->suiv;
}
while(parcours->prec!=NULL){
parcours=parcours->prec;
}
return *parcours;
}
elseif(n==0){
exit (EXIT_FAILURE);
}
}
elseif(debinf!=NULL){
parcoursinf=debinf;
for(k=0;k<(*max);k++){
tmp=(chaine*)malloc(sizeof(struct antichaine));
tmp->prec=NULL;
tmp->suiv=NULL;
for(l=0;l<n-1;l++){
tmp->tab[l]=parcoursinf->tab[l];
}
tmp->tab[n-1]=val[k];
parcours->suiv=tmp;
tmp->prec=parcours;
tmp->suiv=NULL;
parcours=parcours->suiv;
}
parcoursinf=parcoursinf->suiv;

while(parcoursinf!=NULL){
tmp=(chaine*)malloc(sizeof(struct antichaine));
tmp->prec=NULL;
tmp->suiv=NULL;
for(l=0;l<n-1;l++){
tmp->tab[l]=parcoursinf->tab[l];
}
tmp->tab[n-1]=val[(*max)];
parcours->suiv=tmp;
tmp->prec=parcours;
tmp->suiv=NULL;
parcours=parcours->suiv;
parcoursinf=parcoursinf->suiv;
}
debinf=debinf->suiv;
free(debinf->prec);
(*max)=(*max)-1;
}
while(parcours->prec!=NULL){
parcours=parcours->prec;
}
return *parcours;
}

void affichage(chaine ch[], int n, int nb_ch){
int i,j;
for(i=0;i<nb_ch;i++){
while(ch[i].suiv!=NULL){
for(j=0;j<n;j++){
printf("%d",ch[i].tab[j]);
}
ch[i]=*ch[i].suiv;
printf(" ");
}
printf("\n");
}
}

cs_jfrancois · Answer

Bonjour,

Un petit point qui ne règle pas le problème mais qui existe !

elseif(n=1){       <--- (n == 1)
for(k=0;k<2;k++){

Jean-François

cs_jfrancois · Answer

Je ne sais pas ce que ce code fait, ou est sensé faire, car c'est incompréhensible et ça plante dès le début. Si c'est une gestion de liste chaînée (les pointeurs "prec" et "suiv" le laisse penser) alors il ne doit pas y avoir d'allocation mémoire de l'ensemble de la chaîne ("calloc" dans "main"), ça c'est pour un tableau pas pour une liste ! Et il ne devrait y avoir qu'une seule allocation mémoire, quand on ajoute un élément à la liste, pas 6 comme ici (sans compter l'allocation de "temp" dans "main" qui n'est pas utilisé).

Ce programme est sensé faire quoi au juste ? Un exemple de liste ?
Jean-François

Utilisateur anonyme · Answer

En fait, il s'agit d'un tableau de listes doublement chainées. Chaque élément de la liste contient un tableau. Pour que le travail à faire par le programme soit plus clair, je vais donner un exemple (c'est un problème mathématique) après une courte présentation. L'espace est une combinaison de plusieurs vecteurs de taille 2 dont les valeurs possibles sont 0 ou 1. Le nombre de vecteur est N. Le but étant de trouver un nombre minimum d'antichaine pour représenter l'espace. Une antichaine se compose de combinaisons des vecteurs de départ. Chaque antichaine est représentée par une liste doublement chainée et l'ensemble de l'espace sera le tableau qui contiendra les listes doublement chainées.

Exemple: si N=2, il existe 2 antichaines (nb_ch dans le code) qui seront
                * 00-01-11
                * 10
      
               si N=3, il existe 3 antichaines qui seront
               * 000-001-011-111
               * 010-110
               * 100-101 

               si N=4, il existe 6 antichaines

               si N=5, il existe 10 antichaines, puis ça augmente de plus en plus avec N (mais ça ne peut pas être multiplier par plus que 2 quand on passe de N à N+1)

cs_jfrancois · Answer

Un tableau de listes chaînées ok je comprends mieux comme ça, par contre je ne vois pas la logique de la construction de chacune des listes chaînées ! Je découvre ce sujet des "antichaînes" et j'ai rien trouvé de clair sur Google !

Jean-François

Utilisateur anonyme · Answer

Merci pour ton intérêt, Jean-François. J'ai déjà réussi à régler une partie du problème qui était l'affichage de -8452368664 (un truc du genre mais je pense que c'était toujours la même valeur). Pour cela, j'ai mis le deuxième élément de la liste chainée en première position et j'ai bien le résultat escompté, c'est-à-dire 0 et 1 pour N=1. Mais je ne comprend pas pourquoi le premier élément de ma liste avait une valeur aléatoire car je pensais y affecter la bonne valeur directement et je vois pas d'où peut venir ce premier élément aléatoire. Mais bon, c'est réglé, donc je ne vais pas trop me plaindre. Le plus gros problème, c'est que ça plante pour N>1, or  pour N=1, le résultat est immédiat et le programme est donc inutile. C'est bien les N plus grands que 1 qu'il y a un intérêt au programme.

Pour ce qui est des antichaines, je peux te dire que c'est un domaine assez étroit des mathématiques et que peu de gens travaillent dessus. En conséquence, il n'y a pas grand chose sur internet et il n'y a que les mathématiciens qui ont des travaux là-dessus qui s'échangent des informations sur le sujet lors de séminaires ou de rencontre de travail. Si tu veux, je peux te donner le lien du site où se trouve l'article scientifique traitant des antichaines et qui contient l'algorithme que j'essaye d'implémenter. Ça se trouve sur Numdam, un site d'articles mathématiques et un des auteurs a pour nom Lenca.

Pointeur int dans fonction récursive

5 réponses

Votre réponse

Discussions similaires