[C++] Template & Liste chaîné

Template & Liste chaîné [C++] - C++ - Programmation

Marsh Posté le 18-06-2005 à 10:38:08    

Hello, je suis en train de coder une template de liste chaînée. Celle ci va contenir des objets divers.
Mais je n'y arrive pas. J'ai beucoup de souci de compilation au niveau de mes malloc. Pouvez vous m'aider??  
Voivi ma classe :

Code :
  1. #ifndef LISTE_H
  2. #define LISTE_H
  4. #include <string.h>
  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include <iostream.h>
  9. template <class T>
  10. class Liste
  11. {
  12.    typedef struct listeC
  13.     {
  14.       T _element ;
  15.       struct liste *precedent ;
  16.       struct liste *suivant ;
  17.     }liste; 
  19.    liste *debut ; 
  20.    int nbElement ;
  22. public:
  23.    Liste() ;
  24.    Liste( const T &element ) ;
  26.    int ajouteElement( const T &element ) ;
  28.    int getNbElement() ;
  30. };
  32. template <class T>
  33. Liste<T>::Liste()
  34. {
  35.    debut = NULL ;
  36.    nbElement = 0 ;
  37. }
  39. template <class T>
  40. Liste<T>::Liste( const T &element )
  41. {
  42.    debut = ( struct liste * ) malloc( sizeof( T ) );
  44.    _element = element ;
  45.    debut.precedent = NULL ;
  46.    debut.suivant = NULL ;
  48.    nbElement = 1;
  49. }
  51. template <class T>
  52. int Liste<T>::ajouteElement( const T &element )
  53. {
  54.    liste *courant ;
  55.  
  56.    if( debut == NULL )
  57.    {
  58.       debut = ( struct liste * ) malloc( sizeof( T ) );
  59.       _element = element ;
  60.       nbElement = 1;
  61.    }
  62.    else
  63.    {
  64.       while( courant->suivant != debut )
  65.       {
  66.          courant = courant->suivant ;
  67.       }
  68.       if( courant->suivant == debut )
  69.       {
  70.          courant->suivant = ( struct liste * ) malloc( sizeof( T ) );
  71.          courant->suivant->_element = element;
  72.          courant->suivant->suivant = debut;
  73.       }
  74.    }
  75.    return 1;
  76. }
  78. template <class T>
  79. int Liste<T>::getNbElement()
  80. {
  81.    return nbElement;
  82. }
  84. #endif


 
Dans ma classe pour l'instant j'ai donc fait :
 
 
      un conctructeur
      un conctructeur de recopie
      une méthode permettant d'ajouter une élément dans ma liste chaîné
      un accesseur qui retourne le nombre d'élément de ma liste chaîné
 
 
 
J'ai en attribut de classe une structure : ma liste chainé
l'adresse du début de ma liste chainé
et un entier qui correspond au nombre d'élément de ma liste chainé.
Ma liste chainé est une liste doublement chainé avec un lien vers le chainon suivant et un lien vers le chainon précédent.
C'est donc une liste chainé circulaire.
 
Cette ligne de code pose problème par exemple :

Code :
  1. debut = ( struct liste * ) malloc( sizeof( T ) );


Je ne sais pas quoi mettre dans le malloc et dans le typage :
struct liste * ou T?
struct liste * parait le plus évident. Mais je dois surement fournir aussi le type de liste? enfin je veux dire le type de l'élément de ma liste non?
C'est un peu compliqué...
Aidez moi s'il vous plait  :pfff:

Reply

Marsh Posté le 18-06-2005 à 10:38:08   

Reply

Marsh Posté le 18-06-2005 à 10:51:31    

qu'est ce que tu fous avec des malloc ? t'es en C++, les malloc n'ont rien à faire ici !


---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le 18-06-2005 à 10:53:27    

Je fais un new alors??

Code :
  1. debut = new struct liste ( T );


Comme ca?

Reply

Marsh Posté le 18-06-2005 à 10:54:05    

voila


---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le 18-06-2005 à 10:55:44    

En C++, on utilise new: debut = new T;
 
Rassure-moi, c'est juste à titre d'exercice que tu crées cette classe ? Tu n'as pas l'intention de l'utiliser par la suite ?


Message édité par el muchacho le 18-06-2005 à 11:03:26
Reply

Marsh Posté le 18-06-2005 à 10:58:50    

Oui oui c'est un projet débile de fin d'année. je suis obligé d'utiliser ce que j'ai vu pendant l'année. Je mélange donc C et C++... C'est un petit projet.

Reply

Marsh Posté le 18-06-2005 à 11:01:45    

Mon code devien donc :

Code :
  1. #ifndef LISTE_H
  2. #define LISTE_H
  4. #include <string.h>
  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include <iostream.h>
  9. template <class T>
  10. class Liste
  11. {
  12. typedef struct listeC
  13.     {
  14.  T _element ;
  15.  struct liste *precedent ;
  16.  struct liste *suivant ;
  17.     }liste;
  19. liste *debut ;
  20. int nbElement ;
  22. public:
  23. Liste() ;
  24. Liste( const T &element ) ;
  26. int ajouteElement( const T &element ) ;
  28. int getNbElement() ;
  30. };
  32. template <class T>
  33. Liste<T>::Liste()
  34. {
  35. debut = NULL ;
  36. nbElement = 0 ;
  37. }
  39. template <class T>
  40. Liste<T>::Liste( const T &element )
  41. {
  42. debut = new T;
  44. _element = element ;
  45. debut.precedent = NULL ;
  46. debut.suivant = NULL ;
  48. nbElement = 1;
  49. }
  51. template <class T>
  52. int Liste<T>::ajouteElement( const T &element )
  53. {
  54. liste *courant ;
  56. if( debut == NULL )
  57. {
  58.  debut = new T;
  59.  _element = element ;
  60.  nbElement = 1;
  61. }
  62. else
  63. {
  64.  while( courant->suivant != debut )
  65.  {
  66.   courant = courant->suivant ;
  67.  }
  68.  if( courant->suivant == debut )
  69.  {
  70.   courant->suivant = new T;
  71.   courant->suivant->_element = element;
  72.   courant->suivant->suivant = debut;
  73.   debut->precedent = courant->suivant;
  74.  }
  75. }
  76. return 1;
  77. }
  79. template <class T>
  80. int Liste<T>::getNbElement()
  81. {
  82. return nbElement;
  83. }
  85. #endif


 

Reply

Marsh Posté le 18-06-2005 à 11:02:52    

Tu mélanges tellement que tu t'y perds, et nous avec... Ca fait 3 fois que j'édite mon post pour la bonne syntaxe du new...

Reply

Marsh Posté le 18-06-2005 à 11:03:22    

ah oui, liste est un template, j'avais pas fait gaffe. c'est donc bien liste <T> et pas liste (T). mais de toute façon, comme muchacho et moi te l'avons dit, en C++ les allocations se font avec new


---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le 18-06-2005 à 11:06:22    

Mais c'est une nouvelle liste de type T. Et non pas un nouvel objet de type T.
Donc ca ne devrait pas être comme ceci plutôt:

Code :
  1. debut = new Liste<T>;

Reply

Marsh Posté le 18-06-2005 à 11:06:22   

Reply

Marsh Posté le 18-06-2005 à 11:09:41    

En fait, sans compilo pour essayer, je dirais qu'il faut que liste soit une classe avec un constructeur que tu initialises en appelant le new:
liste<T> *debut = new liste(T, prec, suiv);
 
Là, tu mélanges debut : premier élément de la liste et le type objet T.  
ton malloc était faux : c'était sizeof(struct listeC) et non sizeof(T).
D'où la confusion que tout le monde a faite.


Message édité par el muchacho le 18-06-2005 à 11:11:42
Reply

Marsh Posté le 18-06-2005 à 11:11:26    

non c'est new T : tu ajoutes un élément à ta liste, pas une liste !
 
edit: ptain, je m'y perds les pinceaux à son truc :pt1cable:


Message édité par Harkonnen le 18-06-2005 à 11:12:18

---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le 18-06-2005 à 11:11:46    

C'est ca en fait le gros problème.
Comment initialisé mon debut?
debut est un pointeur sur une structure :

Code :
  1. typedef struct listeC
  2.      {
  3.          T _element ;
  4.          struct liste *precedent ;
  5.          struct liste *suivant ;
  6.      }liste;


la structure peut contenir un objet de type T.
Donc quand j'initialise debut je dois faire ceci :
debut = new liste;
Mais il faut focément que je précise le type que ma liste va contenir (T donc).
Comment faire ca?
debut = new liste<T>; ??

Reply

Marsh Posté le 18-06-2005 à 11:12:24    

Harko > Non. Lis mon post.


Message édité par el muchacho le 18-06-2005 à 11:13:09
Reply

Marsh Posté le 18-06-2005 à 11:15:09    

Spir a écrit :

C'est ca en fait le gros problème.
Comment initialisé mon debut?
debut est un pointeur sur une structure :

Code :
  1. typedef struct listeC
  2.      {
  3.          T _element ;
  4.          struct liste *precedent ;
  5.          struct liste *suivant ;
  6.      }liste;


la structure peut contenir un objet de type T.
Donc quand j'initialise debut je dois faire ceci :
debut = new liste;
Mais il faut focément que je précise le type que ma liste va contenir (T donc).
Comment faire ca?
debut = new liste<T>; ??


 
liste<T> *debut = new liste(T, 0, 0);
 
cf mon post précédent


Message édité par el muchacho le 18-06-2005 à 11:17:10
Reply

Marsh Posté le 18-06-2005 à 11:18:08    

Ouais mais il y a confusion entr le nom de la classe et le nom de la structure.
Ma classe s'appel Liste la structure liste.
debut est un attribut de la classe Liste.
C'est un pointent sur une structure liste.
Donc si je fais ce que tu dis :

Code :
  1. liste<T> *debut = new liste(T, prec, suiv);


ca fais spé... liste est une structure pas une classe?!

Reply

Marsh Posté le 18-06-2005 à 11:19:31    

je veux dire si je fais :

Code :
  1. liste<T> *debut = new liste(T, prec, suiv);


Je dois créé un constructeur de liste??? je ne capte pas.

Reply

Marsh Posté le 18-06-2005 à 11:19:51    

Ben t'en fais une classe, et tu renommes ListeC en Element, et comme ça, on arrête de tout mélanger. Parce qu'au fonds, ce que tu appelles liste * n'est qu'un élément de l'objet Liste.


Message édité par el muchacho le 18-06-2005 à 11:20:55
Reply

Marsh Posté le 18-06-2005 à 11:21:16    

C'est ps compliqué ce que je veux faire. je veux juste faire un classe template qui manipule une liste chainé.
J'ai donc en attribut la déclaration de la structure de ma liste chainé, et un pointeur debut qui pointe sur l'adresse du début de ma liste chainé.

Reply

Marsh Posté le 18-06-2005 à 11:22:11    

Ben oui mais tu mélanges tout parce que tu raisonnes à la C.

Reply

Marsh Posté le 18-06-2005 à 11:22:30    

Ok donc je fais un classe template ListeC qui décrit une liste chainé.
Et après je fais une classe Liste qui manipule ma liste chainé template.

Reply

Marsh Posté le 18-06-2005 à 11:24:25    

J'ai trouvé quelque chose sur le net qui ressemble à ce que je veux faire :
liste.h :

Code :
  1. #ifndef _LISTE
  2. #define _LISTE
  3. #include <stdio.h>
  4. template <class T>
  5. class Cellule
  6. {
  7. public:
  8. T valeur;
  9. Cellule *suivant;
  11. Cellule();
  12. Cellule(T);
  13. // ~Cellule();
  15. T recValeur();
  16. Cellule<T> *recSuivant();
  18. affSuivant(Cellule<T> *);
  19. supprSuivant();
  20. };
  22. template <class T>
  23. class Liste
  24. {
  25. public:
  26. Cellule<T> *debut;
  28. Liste();
  29. Liste(T);
  30. // ~Liste();
  32. int recNbElements();
  33. T *recElement(int);
  36. inserer(int, T);
  37. int *rechercher(T);
  38. supprimer(int);
  40. // int afficher();
  41. };
  43. #endif


 
 
liste.cpp

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <iostream.h>
  4. #include <string.h>
  6. #include "liste.h"
  8. template <class T>
  9. Cellule<T>::Cellule()
  10. {
  11. suivant=NULL;
  12. }
  14. template <class T>
  15. Cellule<T>::Cellule(T v)
  16. {
  17. valeur=v;
  18. suivant=NULL;
  19. }
  20. /*
  21. template <class T>
  22. Cellule<T>::~Cellule()
  23. {
  24. if(suivant!=NULL)
  25.  suivant->~Cellule();
  26. free(suivant);
  27. }
  28. */
  29. template <class T>
  30. T Cellule<T>::recValeur()
  31. {
  32. return(valeur);
  33. }
  35. template <class T>
  36. Cellule<T> *Cellule<T>::recSuivant()
  37. {
  38. return(suivant);
  39. }
  41. template <class T>
  42. Cellule<T>::affSuivant(Cellule<T> *s)
  43. {
  44. if(s==NULL)
  45.  suivant=NULL;
  46. else
  47. {
  48.  suivant=new Cellule;
  49.  *suivant=*s;
  50. }
  51. }
  53. template <class T>
  54. Cellule<T>::supprSuivant()
  55. {
  56. suivant->~Cellule();
  57. free(suivant);
  58. }
  60. template <class T>
  61. Liste<T>::Liste()
  62. {
  63. debut=NULL;
  64. }
  66. template <class T>
  67. Liste<T>::Liste(T v)
  68. {
  69. debut=new Cellule(v);
  70. }
  71. /*
  72. template <class T>
  73. Liste<T>::~Liste()
  74. {
  75. if(debut!=NULL)
  76.  debut->~Cellule();
  77. free(debut);
  78. }
  79. */
  80. template <class T>
  81. int Liste<T>::recNbElements()
  82. {
  83. int n;
  84. Cellule<T> *pc;
  86. n=0;
  87. pc=debut;
  89. while(pc!=NULL)
  90. {
  91.  pc=pc->recSuivant();
  92.  n++;
  93. }
  95. return(n);
  96. }
  98. template <class T>
  99. T *Liste<T>::recElement(int p)
  100. {
  101. int i;
  102. Cellule<T> *pc;
  103. T *e;
  105. i=1;
  106. pc=debut;
  107. e=NULL;
  109. if(p>0)
  110. {
  111.  while(pc!=NULL && i<p)
  112.  {
  113.   pc=pc->recSuivant();
  114.   i++;
  115.  }
  116.  if(pc!=NULL)
  117.  {
  118.   e=new T;
  119.   *e=pc->recValeur();
  120.  }
  121. }
  123. return(e);
  124. }
  126. template <class T>
  127. Liste<T>::inserer(int p ,T v)
  128. {
  129. int i;
  130. Cellule<T> c(v), *pc;
  132. if(p==1)
  133. {
  134.  if(recNbElements()!=0)
  135.   c.affSuivant(debut);
  136.  debut=new Cellule<T>;
  137.  *debut=c;
  138. }
  139. else if(p>1)
  140. {
  141.  i=1;
  142.  pc=debut;
  143.  while(pc->recSuivant()!=NULL && i<p-1)
  144.  {
  145.   pc=pc->recSuivant();
  146.   i++;
  147.  }
  148.   c.affSuivant(pc->recSuivant());
  150.  pc->affSuivant(&c);
  151. }
  152. }
  154. template <class T>
  155. int *Liste<T>::rechercher(T e)
  156. {
  157. int *pos, n, i;
  159. pos=NULL;
  160. i=1;
  161. n=recNbElements();
  163. while(pos==NULL && i<=n)
  164. {
  165.  if(*recElement(i)==e)
  166.  {
  167.   pos=new int;
  168.   *pos=i;
  169.  }
  170.  i++;
  171. }
  173. return(pos);
  174. }
  177. template <class T>
  178. Liste<T>::supprimer(int p)
  179. {
  180. int i;
  181. Cellule<T> *pc, *tampon
  183. if(p==1)
  184.  debut=debut->recSuivant();
  185. else if(i>1)
  186. {
  187.  i=1;
  188.  pc=debut;
  189.  while(pc->recSuivant()!=NULL && i<p-1)
  190.  {
  191.   pc=pc->recSuivant();
  192.   i++;
  193.  }
  194.  if(pc->recSuivant()!=NULL)
  195.  {
  196.   tampon=pc->recSuivant();
  197.   pc->affSuivant(tampon->recSuivant());
  198.   tampon->~Cellule();
  199.  }
  200. }
  201. }
  203. /*template <class T>
  204. int Liste::afficher()
  205. */

Reply

Marsh Posté le 18-06-2005 à 11:26:08    

Déjà, fais-en une version non template qui marche...
 
 - une classe Liste qui est celle que tu as définie
 - une classe Element de la liste qui sera une sorte de wrapper du type T, définie comme ta struct ListeC, et qui n'a besoin comme méthodes qu'un constructeur et un destructeur.


Message édité par el muchacho le 18-06-2005 à 11:27:52
Reply

Marsh Posté le 18-06-2005 à 11:27:24    

Spir a écrit :

J'ai trouvé quelque chose sur le net qui ressemble à ce que je veux faire :
liste.h :

Code :



 
C'est très exactement ce que je viens de te décrire: ici Cellule est ma classe Element.

Reply

Marsh Posté le 18-06-2005 à 11:28:27    

Voilà bon bah je vais essayer de faire ca. Un classe qui décrit ma liste chainé.
Et une classe qui exploite cette liste chainé.

Reply

Marsh Posté le 27-06-2005 à 18:45:59    

Juste unt truc :

el muchacho a écrit :

Rassure-moi, c'est juste à titre d'exercice que tu crées cette classe ? Tu n'as pas l'intention de l'utiliser par la suite ?


 
Pourquoi ? C'est mal ?

Reply

Marsh Posté le 27-06-2005 à 18:48:07    

En un mot, oui. Y'a une lib standard qui fait ça très bien, et probablement mieux que tout ce que vous pourrez pondre, alors autant l'utiliser.


Message édité par el muchacho le 27-06-2005 à 18:49:08
Reply

Marsh Posté le 27-06-2005 à 18:50:04    

aukey

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

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