Recursivité en listes chaînées, comment?

J'utilise C++ Builder depuis quelques mois, j'ai utilisé Delphi depuis que j'ai appris à programmer.
Je sais créer une fonction de création de liste chaînée FIFO en Delphi:
procedure createfile(var L:axe;elt:string);
begin
if L=nil then
begin
new(L);L^.value:=elt;
L^.next:=nil;
end
else createfile(L^.next,elt);
end;

J'ai essayé la même chose en C++ Builder et ça ne se compile même pas:

Code:

---

1 2 3 4 5 6 7 8

void createfile(axe ** L,AnsiString elt){ if (L==NULL){ L=(axe*) malloc(sizeof(axe)); L->value=elt;L->next=NULL; } else createfile(L->next,elt); }

---

Bonsoir,

Ch'tite question ... dans le code en C++Builder, 'axe' est de quel type ?
(c'est peut être idiot, mais je vois pas ...)

@ + ;)

axe est une structure (liste chaînée).

Code:

---

1 2 3 4 5

struct axe{ AnsiString value; struct axe * next; };

---

Je voudrais savoir les erreurs de * ou de -> que j'ai omises dans cette fonction recursive.

bonjour
simplement comme ceci

Code:

---

1 2 3 4 5 6 7 8 9 10 11

void __fastcall TForm1::createfile(axe *L,AnsiString elt) { if (L==NULL) { L=new axe; L->value=elt; L->next=NULL; } else createfile(L->next,elt); }

---

cordialement

Une question:

DjmSoftware,tu as mis un seul *

Code:

---

1 2	void __fastcall TForm1::createfile(axe *L,AnsiString elt)

---

Est-ce que ce n'est pas 2 * => axe **L?
Car le contenu de la liste chaînée risque de rester inchangé!

Ou je me trompe?

En effet :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

void __fastcall TForm1::createfile(axe **pL, AnsiString elt) { if(*pL==NULL) { axe *L = new axe; L->value=elt; L->next=NULL; *pL = L; } else createfile((*pL)->next,elt); }

---

PS: Penser à renvoyer une erreur si pL est NULL...

Bon je vais tester ce code et je donnerai des nouvelles après.

Je n'ai pas BCB maintenant mais je crois bien que j'ai déja essayé ce code!

Salut !

Je ne comprend pas trop ce code.
S'il est récursif... on fait comment pour en sortir ?
Personnellement, j'aurais utilisé une classe avec un constructeur sachant monter une liste liée de n éléments.

Voici un exemple qui se sert de TComponent juste parce que c'est le propriétaire qui détruit les composants qu'il détient...

Code:

---

1 2 3 4 5 6 7 8

class jObject : public TComponent { public : int Code; jObject *Next; __fastcall jObject(TComponent *Owner, int nbObjects); __fastcall ~jObject(); };

---

Le constructeur :

Code:

---

1 2 3 4 5 6 7

__fastcall jObject::jObject(TComponent *Owner, int nbObjects) : TComponent(Owner) { Code = nbObjects-1; Next = NULL; if(Code > 0) Next = new jObject(Owner, Code); }

---

Usage :

Code:

---

1 2 3 4 5 6 7 8

jObject *List;   __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { List = new jObject(this, 10); }

---

Pour voir ce que ça donne, j'ai un TSpeedbutton et un TMemo

Code:

---

1 2 3 4 5 6 7 8 9 10

void __fastcall TForm1::SpeedButton1Click(TObject *Sender) { Memo1->Clear(); jObject *Object = List; while(Object != NULL) { Memo1->Lines->Add(IntToStr(Object->Code)); Object = Object->Next; } }

---

A moins évidemment de n'avoir pas compris le problème...

A plus !

Slt Henderson!

L'utilisation de fonction recursive signifie rapidité.
C'est comme créer un arbre binaire mais ici, on a un arbre unaire (liste chainée FIFO).

Je crois que tu n'as pas compris le problème, il s'agit d'une structure pour stocker des "value" et mon prob est que ma fonction ne marche pas (prob de pointeur)
___________________
Entre temps, ton code fait une erreur [Lieur Erreur] Unresolved external '__fastcall jObject::~jObject()' referenced from D:\...
___________________
Pour Medinoc!
Dans le code que tu as écris, où est-ce qu'on déclare L

Code:

---

if (L==NULL)//if (pL=NULL)

---

Ca fait l'erreur suivante sur

Code:

---

else createfile((*pL)->next,elt);

---

[C++ Erreur] Unit1.cpp(69): E2034 Impossible de convertir 'axe *' en 'axe * *'

En effet, il faut corriger en ceci:

Code:

---

else createfile(&((*pL)->next),elt);

---

Salut !

De temps en temps... j'ai le cerveau lent et aujourd'hui... ça craint !

Je pense qu'un while serait plus rapide.

Code:

---

1 2 3 4

while(*pL != NULL) pL = &(*pL)->next; *pL = new axe; (*pL)->value = elt; (*pL)->next = NULL;

---

Le plus rapide étant bien entendu d'avoir un pointeur sur le dernier entré.

A plus !

(thanks)

Je crois qu'il y a eu un prob dans le forum. Le serveur a posté mon message au mauvais forum.

Désolé bruce-willis d'avoir parlé d'une autre discussion!!!

--------------------------------------------------------------------------------

Pour bruce-willis,

je crois que ça marche maintenant là car j'ai testé le code avec la rectif de Médinoc, c'est OK

Pour henderson, la récursivité est trop rapide par rapport à une itération, je n'ai mêm pas besoin de le prouver, tester ce code de bruce-willis.

Voici comment on va appeler cette fonction:

Code:

---

1 2 3 4

axe * list; list=NULL; createfile(&list,1);createfile(&list,1000);//etc.

---

OK rakoto15

c'est résolu

Merci à tous

Salut

Dans ce contexte précis, je pense qu'un simple while est plus économique (temps d'éxucution + code machine) qu'un appel récursif !

Code:

---

1 2 3 4 5 6 7

void CreateFile(axe **pL, AnsiString elt) { while(*pL != NULL) pL = &(*pL)->next; *pL = new axe; (*pL)->value = elt; (*pL)->next = NULL; }

---

Le while réduit le code de l'appel récursif à ce que cet appel est censé réaliser : la simple recherche d'une adresse nulle, d'adresse en adresse !

Par ailleurs, je ne vois pas pourquoi il faudrait passer le paramètre elt pour cette recherche d'adresse nulle, puisqu'il y est totalement étranger !
On s'oblige juste à devoir le faire à cause du mécanisme que l'on met soi-même en place !

L'usage est le même donc je ne vois pas pourquoi on tire sur l'ambulance !

A titre perso, j'aurais objétisé pour gérér le first_in et le last_in afin d'éviter de passer en revue l'ensemble des éléments juste pour trouver le dernier. :mouarf:

Il semble qu'ici, la récursivité soit plus un sujet de TP qu'une optimisation. Donc c'est fait !

A plus !