Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2785 connectés 

  FORUM HardWare.fr
  Programmation
  C

  fonction récursive et liste doublement chainée

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

fonction récursive et liste doublement chainée

n°1665471
Profil sup​primé
Posté le 03-01-2008 à 20:37:23  answer
 

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
mood
Publicité
Posté le 03-01-2008 à 20:37:23  profilanswer
 

n°1665473
gilou
Modérateur
Modzilla
Posté le 03-01-2008 à 21:07:56  profilanswer
 

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é!  --
n°1665483
Profil sup​primé
Posté le 03-01-2008 à 21:30:06  answer
 

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:

n°1665625
Ace17
Posté le 04-01-2008 à 08:23:19  profilanswer
 


 
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?

n°1666537
Profil sup​primé
Posté le 05-01-2008 à 20:22:55  answer
 

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
n°1668070
Profil sup​primé
Posté le 08-01-2008 à 23:41:05  answer
 

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
n°1668093
gilou
Modérateur
Modzilla
Posté le 09-01-2008 à 00:18:03  profilanswer
 

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é!  --
n°1668115
Profil sup​primé
Posté le 09-01-2008 à 01:31:23  answer
 

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
n°1668116
gilou
Modérateur
Modzilla
Posté le 09-01-2008 à 02:19:06  profilanswer
 

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é!  --
n°1668298
Profil sup​primé
Posté le 09-01-2008 à 14:43:05  answer
 

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

mood
Publicité
Posté le 09-01-2008 à 14:43:05  profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

  fonction récursive et liste doublement chainée

 

Sujets relatifs
Créer une liste de ligne[Resolu] Transformation d'un fichier en liste doublement chainée
Fonction upload php[c#] Liste des connexions réseau
ma fonction ne fonctionne pasRecherche une fonction
AS3 : appeler une fonction a partir d'une fonction...Probléme avec fonction foreach
Plus de sujets relatifs à : fonction récursive et liste doublement chainée

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.097 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR