fonction récursive et liste doublement chainée

fonction récursive et liste doublement chainée - C - Programmation

Marsh Posté le 03-01-2008 à 20:37:23    

Salut, je cherche à faire une liste doublement chainée via une fonction récursive, le problème c'est qu'à chaque appel de la fonction les variables sont réinitialisées, donc comment faire pour remplir les champs de l' "élément précédent" ?
 
Typiquement :
 

Code :
  1. typedef struct elt{
  2. /* champs */
  3. struct elt* suivant;
  4. struct elt* precedent;
  5. }element;
  7. typedef element* liste;


 
Puis la fonction (on va dire que chaque élément est un caractère tiré d'une chaine caractère) :
 

Code :
  1. int remplissage(char* phrase,liste* destination){
  2. if(*phrase=='\0'){
  3.   return 0;
  4. }
  5. else{
  6.   (*destination)->caractere=*phrase;
  7.   (*destination)->suivant=malloc(sizeof(element));
  8.   remplissage(phrase++,&((*destination)->suivant));
  9. }
  10. }


 
Que faut-il modifier pour qu'un champ "precedent" soit rempli ?

Message cité 1 fois
Reply

Marsh Posté le 03-01-2008 à 20:37:23   

Reply

Marsh Posté le 03-01-2008 à 21:07:56    

après cette ligne (*destination)->suivant=malloc(sizeof(element));
il faudrait faire quelque chose comme
(*destination)->suivant->precedent = *destination;
 
A+,

Message cité 1 fois

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 03-01-2008 à 21:30:06    

gilou a écrit :

après cette ligne (*destination)->suivant=malloc(sizeof(element));
il faudrait faire quelque chose comme
(*destination)->suivant->precedent = *destination;
 
A+,


 
Ca marche merci. J'aurai dû y penser.
 
J'y retourne, faut que je transforme tout ça en arbre maintenant  :wahoo:

Reply

Marsh Posté le 04-01-2008 à 08:23:19    


 
Il me semble que si tu appelles remplissage de cette facon, c'est la valeur de phrase avant l'incrementation qui va etre passee en parametre. Donc si ta chaine commence par autre chose que '\0' tu as une recursion infinie. Me trompe-je?

Reply

Marsh Posté le 05-01-2008 à 20:22:55    

Non c'est si je fais ++phrase je crois. Enfin en tout cas comme ça ça marche.

 

Edit : non en fait je fais pas comme ça. Il y a des sous conditions, genre j'ai 2 types de caractères : les nombres et les opérateurs ('(', ')', '+', '-' etc). Si c'est un nombre je prends tout le nombre et j'incrémente phrase jusqu'au prochain opérateur, si c'est un opérateur je prends juste l'opérateur et un seul phrase++. Ensuite seulement j'apelle remplissage(phrase, &((*dest)->suivant));.


Message édité par Profil supprimé le 05-01-2008 à 20:27:18
Reply

Marsh Posté le 08-01-2008 à 23:41:05    

Salut tout le monde, j'ai un nouveau problème. Si je tape :

 
Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  5. int main(int argc,char *argv[]){
  6.   char* str=(char *)malloc(sizeof(char)*20);
  7.   fgets(str,20,stdin);
  8.   int i=0;
  9.   int n=0;
  10.   printf("strlen : %d\n",strlen(str));
  11.   for(;i<strlen(str);i++){
  12.     if(*(str+i)=='(' || *(str+i)==')'){
  13.       n++;
  14.     }
  15.     printf("%f\n",atoi(str+i));
  16.     str++;
  17.   }
  18.   printf("str : %s\n",str);
  19.   printf("nbpar : %d",n);
  20. }
 

puis dans la console :
(32+32)+(32+32)

 

Il me sort un peu n'imp. Genre seulement 8 valeurs (alors qu'il en faudrait strlen(str) soit le double), il va clairement pas jusqu'au bout, c'est ça qui m'embête. Par exemple j'ai par ailleurs un algo pour retrouver des parenthèses, et comme ça apelle d'autres fonctions après et que le résultat correspond pas à celui attendu mon prog bug de partout. Voilà si quelqu'un a une réponse..  :hello:


Message édité par Profil supprimé le 08-01-2008 à 23:41:45
Reply

Marsh Posté le 09-01-2008 à 00:18:03    

Le str++ a la 16e ligne doit foutre le bordel, non?
Parce que si tu parcours str en regardant ce sur quoi pointe str+i, vaut mieux que str soit fixe.
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 09-01-2008 à 01:31:23    

Ok en fait il avance 2 fois trop vite c'est ça ?

 

En fait j'ai ça :

 
Code :
  1. int ver_ex(char* strex){
  2.   int n_pouv=0; /* nombre de parentheses ouvrantes et fermentes */
  3.   int n_pferm=0;
  4.   int val=0; /* var de controle : s'incrémente à chaque caractère invalide trouvé */
  5.   int n=strlen(strex);
  6.   int i=0;
  7.   while(i<n-1){
  8.     if(*(strex+i)!='0' && *(strex+i)!='1' && *(strex+i)!='2' && *(strex+i)!='3'
  9.        && *(strex+i)!='4' && *(strex+i)!='5' && *(strex+i)!='6' && *(strex+i)!='7'
  10.        && *(strex+i)!='8' && *(strex+i)!='9'){
  11.       if(*(strex+i)!='+' && *(strex+i)!='-' &&  *(strex+i)!='*' && *(strex+i)!='/'
  12.  && *(strex+i)!='%' && *(strex+i)!='(' &&  *(strex+i)!=')' && *(strex+i)!='{'
  13.  && *(strex+i)!='}' && *(strex+i)!='^' && *(strex+i)!='\0'){
  14. val++;
  15.       }
  16.     }
  17.     if(*(strex+i)=='(' || *(strex+i)=='{'){
  18.       n_pouv++;
  19.     }
  20.     if(*(strex+i)==')' || *(strex+i)=='}'){
  21.       n_pferm++;
  22.     }
  23.     i++;
  24.   }
  25.   if(val!=0 || n_pouv!=n_pferm){ /* il y a des carac invalides OU des parentheses ouvrantes sans parentheses fermantes */
  26.     printf("erreurs trouvees : %d\nparentheses ouvrantes : %d, parentheses fermantes : %d\n",val,n_pouv,n_pferm);
  27.     return -1;
  28.   }
  29.   else return 0;
  30. }
 

Ca teste si chaque caractère est un nombre ou un opérateur ou une parenthèse. Sauf que si je tape (32+32)+(32+32) ça bugge. Et là ça avance pas 2 fois trop vite. Par contre ça le fait dans la fonction d'après, je vérifie et je repost. Merci en tout cas.


Message édité par Profil supprimé le 09-01-2008 à 01:32:38
Reply

Marsh Posté le 09-01-2008 à 02:19:06    

Oui, il avançait deux fois trop vite.
 
Dans ton code, ton while est bien trop complexe et fait une kyrielle de tests inutiles.
 
Je procederais ainsi, ou on ne teste *(strex+i) qu'une fois [en apparence, apres ca depend de ce que le compilo fait comme code généré pour un petit switch]:  

Code :
  1. for (i=0; i<n-1; i++)
  2.     {
  3.       switch(*(strex+i))
  4.         {
  5.         case '0': case '1':
  6.         case '2': case '3':
  7.         case '4': case '5':
  8.         case '6': case '7':
  9.         case '8': case '9':
  10.         case '+': case '-':
  11.         case '*': case '/':
  12.         case '%': case '^':
  13.           break;
  15.         case '(': case '{': n_pouv++;
  16.           break;
  18.         case ')': case '}': n_ferm++;
  19.           break;
  21.         default: val++;
  22.           break;
  23.         }
  24.     }


Et cela me semble être du code plus facile a comprendre a la lecture.
J'ai viré le cas '\0' car il ne peut survenir si l'on a n=strlen(strex).
A+,


Message édité par gilou le 09-01-2008 à 02:33:55

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 09-01-2008 à 14:43:05    

C'est plus lisible en effet, je vais m'en inspirer merci :)

Reply

Marsh Posté le 09-01-2008 à 14:43:05   

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed