[C++] Liste chaînée
| Cpl.Bator |
Posté le 27 Déc 2008 à 13:09
|
|
 Messages : 17 GCPoints : 8751 |
Voici une classe qui gère des liste chainée dynamiquement. utilisation : Code : CArray<int> *Maliste = new CArray<int>; Maliste->AddElement(100); etc...
Code : /*******************************************************
CARRAY IS DEVELOPED BY CPL.BATOR
*******************************************************/
#ifndef __CArray_h__
#define __CArray_h__
#include <stdio.h>
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
class CArray_Node
{
public:
CArray_Node(void);
~CArray_Node(void);
CArray_Node * Suivant;
CArray_Node * Precedent;
MyType Valeur;
};
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
//Constructor
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
CArray_Node<MyType>::CArray_Node(void){}
//Destructor
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
CArray_Node<MyType>::~CArray_Node(void){}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
class CArray
{
public:
CArray_Node<MyType> *Liste;//First node
int NbrElement;//Nombre d'éléments
//Constructor
CArray(void);
//Destructor
~CArray(void);
//Some methods
inline void AddElement(MyType Value);
//---------------------------------------------------
inline MyType GetCurrentElement(void);
//---------------------------------------------------
inline int CountElement(void);
//---------------------------------------------------
inline void FirstElement(void);
//---------------------------------------------------
inline void LastElement(void);
//---------------------------------------------------
inline MyType SelectElement(int index); // Le 1° Element est le numero 1 / the first element is n°1
//---------------------------------------------------
inline void SetElementValue(int index,MyType Value);
//---------------------------------------------------
inline void DeleteElement();
//---------------------------------------------------
inline int FindElement(MyType Element); // Renvoi l'index de l'élement , sinon -1
//---------------------------------------------------
inline void SwapElement(int A,int B);
//---------------------------------------------------
inline void ArrayBubbleSort(void);
//---------------------------------------------------
};
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
CArray<MyType>::CArray(void){NbrElement=0;}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
CArray<MyType>::~CArray(void){}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline void CArray<MyType>::AddElement(MyType Value)
{
// Si il n'y a aucun element dans la liste
if(this->NbrElement==0)
{
this->Liste = new CArray_Node<MyType>;
this->Liste->Precedent = NULL;
}
CArray_Node<MyType> *NouveauElement=new CArray_Node<MyType>;
NouveauElement->Precedent = this->Liste;
NouveauElement->Suivant = NULL;
NouveauElement->Valeur = Value;
this->Liste->Suivant = NouveauElement;
this->Liste = NouveauElement;
this->NbrElement++;
}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline MyType CArray<MyType>::GetCurrentElement(void){
return this->Liste->Valeur;
}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline int CArray<MyType>::CountElement(void){
return this->NbrElement;
}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline void CArray<MyType>::FirstElement(void){
while(this->Liste->Precedent!=NULL)
{
this->Liste = this->Liste->Precedent;
}
}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline void CArray<MyType>::LastElement(void){
while(this->Liste->Suivant!=NULL)
{
this->Liste = this->Liste->Suivant;
}
}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline MyType CArray<MyType>::SelectElement(int index){
this->FirstElement();
int iterator=1;
while(this->Liste->Suivant!=NULL)
{
this->Liste = this->Liste->Suivant;
if (iterator==index)
{
return this->Liste->Valeur;
}
iterator++;
}
return (MyType)-1;
}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline void CArray<MyType>::SetElementValue(int index,MyType Value){
this->FirstElement();
int Iterator=1;
while(this->Liste->Suivant!=NULL)
{
this->Liste = this->Liste->Suivant;
if (Iterator==index)
{
this->Liste->Valeur = Value;
break;
}
Iterator++;
}
}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline void CArray<MyType>::DeleteElement(){
CArray_Node<MyType> *Left = this->Liste->Precedent;
CArray_Node<MyType> *Right = this->Liste->Suivant;
if (this->Liste->Suivant!=NULL){ Right->Precedent = Left;}
if (this->Liste->Precedent!=NULL){ Left->Suivant = Right;}
this->Liste = this->Liste->Precedent;
this->NbrElement--;
}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline int CArray<MyType>::FindElement(MyType Element){
this->FirstElement();
int Iterator=1;
while(this->Liste->Suivant!=NULL)
{
this->Liste = this->Liste->Suivant;
if (this->Liste->Valeur==Element)
{
return Iterator;
}
Iterator++;
}
return -1;
}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline void CArray<MyType>::SwapElement(int A,int B){
int PosA,PosB;
int ValA,ValB;
ValA = this->SelectElement(A);
ValB = this->SelectElement(B);
PosA = this->FindElement(ValA);
PosB = this->FindElement(ValB);
this->SetElementValue(PosA,ValB);
this->SetElementValue(PosB,ValA);
}
/*-----------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------*/
template < class MyType >
inline void CArray<MyType>::ArrayBubbleSort(void){
for(int i=1; i<=this->NbrElement-1;i++)
{
for(int j=i+1; j<=this->NbrElement;j++)
{
if(this->SelectElement(i) > this->SelectElement(j))
{
this->SwapElement(j,i);
}
}
}
}
//TODO
// TRI BULLE PAR LA SELECTION D'UN MEMBRE D'UNE CLASSE OU D'UNE STRUCTURE...
#endif
|
|
| freemaul |
Posté le 27 Déc 2008 à 13:43
|
|
 Messages : 174 GCPoints : 50213 |
J'ai pas tout lut, mais si je comprend bien pour un élément tu occupe en mémoire : la valeur de l'élément, un pointeur vers le précédent, un vers le suivant : pour stocker des int ca gache pas mal de mémoire non ? Si tu créer un tableau dynamiquement, les cases se suivent donc pas besoin d'enregistrer les valeurs des pointeurs suivant et précédent, et même si je ne connait pas d'équivalent à realloc en C++, il doit bien y avoir un moyen de le faire non ?
"La vie n'a pas de prix, mais elle coûte chère"
|
|
| Cpl.Bator |
Posté le 27 Déc 2008 à 15:16
|
|
|
Messages : 17 GCPoints : 8751 |
- Oui , c'est une liste doublement chaînée. int MyArray[10] , n'est pas un tableau dynamique au sens propre du terme. la taille est fixe. |
|
| Darktib |
Posté le 27 Déc 2008 à 17:42
|
|
 Messages : 4017 GCPoints : 347288 |
Sympa comme code  MerciLe probleme des listes, c'est que pour acceder a un élément au milieu de ladite liste c'est lent. D'ailleurs je me suis toujours demandé si en mettant quatres adresses par élément au lieu de deux ( élément n-2, n-1, n+1, n+2) ca améliorerait pas sensiblement la vitesse... |
|
| freemaul |
Posté le 27 Déc 2008 à 18:33
|
|
|
Messages : 174 GCPoints : 50213 |
Citation :
Oui d'accords mais ma question n'était pas là. Mais avec new tu peut bien déclarer un tableau dont tu ne connait pas la taille avant la compilation, et lorsque tu fait un tableau tu n'a pas besoin des adresses suivante et précédente puisqu'elles se suivent, que le tableau soit statique ou dynamique, donc je me demandé si il n'était pas possible d'avoir un équivalent au realloc du C mais en C++ pour ajouter un élément au tableau ?
"La vie n'a pas de prix, mais elle coûte chère"
|
|
| Cpl.Bator |
Posté le 27 Déc 2008 à 18:33
|
|
|
Messages : 17 GCPoints : 8751 |
cela reste relativement rapide , la stl utilise se principe. pour le stockage d'adresses supplémentaires , je te laisse pondre un algo efficace :D |
|
| Cpl.Bator |
Posté le 27 Déc 2008 à 18:40
|
|
|
Messages : 17 GCPoints : 8751 |
On a posté en même temps :D Donc , tu veut qu'a chaque (ajout , suppression) que le tableau soit contiguë en mémoire afin d'avoir des éléments qui se suivent. Cela implique plusieurs chose : - La copie des éléments déjà existants dans le nouvelle espace mémoire contiguë ( en admettant qu'en rajoutant n élément l'espace mémoire déjà alloué n'était pas assez grand) ( un réalloc peut foiré ) - pour le stockage de structure complexe , le transfert de la mémoire fera ramer sans aucun doute l'application. il y a des domaines ou cela est plus gourmand en mémoire , je pense au garbage collector. |
|
| freemaul |
Posté le 27 Déc 2008 à 18:44
|
|
|
Messages : 174 GCPoints : 50213 |
ok je comprend mieux le besoin des listes chainées dynamique du coup ^^ merci
"La vie n'a pas de prix, mais elle coûte chère"
|
|
| chaos |
Posté le 28 Déc 2008 à 09:19
|
|
Messages : 127 GCPoints : 11604 |
J'ai pondue un truc semblable en cours. La structure était imposé mais le principe est plus ou moins le même sauf que ma classe comporte un iterateur. Le but était surtout de passer de java&c a c++ donc gros boulot sur les iterators. listeGen.h Code : /**********************************************************
*
* Auteur : Alexandre Mommers
* listGen.h
*
* Ce fichier est le meme que liste.h a l'exeption du fait
* qu'il a été modifié pour devenir générique via template
**********************************************************/
#ifndef LISTE_H
#define LISTE_H
using namespace std;
template < typename T >class Element;
template < typename T >
class Liste
{
public:
//on inclue la classe iterateur dans liste comme sa elle partageront les memes Elements contenant un type T
class Iterateur;
//constructeur
Liste();
//constructeur par recopie
Liste(const Liste<T>& l);
//destructeur
~Liste();
//operateur d'affecation
Liste& operator=(const Liste<T>& l) ;
//ajouter a la fin de la liste
void ajouter(const T& s);
//ajouter s avant la position pos
void inserer(Iterateur& pos, const T& s);
//suprimer l'element a la position pos
void supprimer(Iterateur& pos);
//la premiere position
Iterateur debut() const;
//la fin de la liste (apres la derniere position)
Iterateur fin() const;
private:
//pointeurs vers le premier et le dernier element
Element<T>* premier;
Element<T>* dernier;
};
template < typename T >
class Liste<T>::Iterateur
{
public:
//constructeur
Iterateur();
//compare deux iterateur
bool egal(const Iterateur & b) const;
//++ -- ==
Iterateur operator++();
Iterateur operator++(int n);
Iterateur operator--();
Iterateur operator--(int n);
T& operator*() const;
bool operator==(const Iterateur& i) const;
bool operator!=(const Iterateur& i) const;
private:
//pointeur vers l'element courant
Element<T>* position;
//pointeur vers le dernier element
Element<T>* dernier;
friend class Liste<T>;
};
#endif
listeGen.cc Code : /**********************************************************
*
* Auteur : Alexandre Mommers
* listGen.cc
*
**********************************************************/
#include "listeGen.h"
#include <iostream>
using namespace std;
template < typename T >class Element
{
public:
//constructeur
Element(const T& s);
private:
T valeur;
//pointeur vers les voisins
Element< T >* precedent;
Element< T >* suivant;
friend class Liste<T>;
friend class Liste<T>::Iterateur;
};
template < typename T >
Element<T>::Element(const T& s)
{
valeur = s;
precedent = suivant = NULL;
}
template < typename T >
Liste<T>::Iterateur::Iterateur()
{
position = dernier = NULL;
}
template < typename T >
T& Liste<T>::Iterateur::operator*() const
{
return position->valeur;
}
template < typename T >
typename Liste<T>::Iterateur Liste<T>::Iterateur::operator++()
{
position = position->suivant;
return *this;
}
template < typename T >
typename Liste<T>::Iterateur Liste<T>::Iterateur::operator++(int n)
{
Iterateur i;
i=*this;
position = position->suivant;
return i;
}
template < typename T >
typename Liste<T>::Iterateur Liste<T>::Iterateur::operator--()
{
if(position == NULL)//fin de la ligne
position = dernier;
else
position = position->precedent;
return *this;
}
template < typename T >
typename Liste<T>::Iterateur Liste<T>::Iterateur::operator--(int n)
{
Iterateur i;
i=*this;
if(position == NULL)//fin de la liggne
position = dernier;
else
position = position->precedent;
return i;
}
template < typename T >bool Liste<T>::Iterateur::operator==(const Iterateur& i) const
{
return position == i.position;
}
template < typename T >bool Liste<T>::Iterateur::operator!=(const Iterateur& i) const
{
return position != i.position;
}
template < typename T >Liste<T>::Liste()
{
premier = dernier = NULL;
}
template < typename T >
Liste<T>::Liste(const Liste& l)
{
Iterateur pos = l.debut();
for(pos = l.debut(); pos != l.fin(); pos++)
ajouter(*pos);
}
template < typename T >Liste<T>::~Liste()
{
Iterateur pos = debut();
while(pos.position != NULL)
supprimer(pos);
}
template < typename T >
typename Liste<T>::Iterateur Liste<T>::debut() const
{
Iterateur it;
it.position = premier;
it.dernier = dernier;
return it;
}
template < typename T >
typename Liste<T>::Iterateur Liste<T>::fin() const
{
Iterateur it;
it.position = NULL;
it.dernier = dernier;
return it;
}
template < typename T >void Liste<T>::ajouter(const T& s)
{
Element<T> *nouveau = new Element<T>(s);
if(premier == NULL)
{
premier = nouveau;
dernier = nouveau;
}
else
{
dernier->suivant = nouveau;
nouveau->precedent = dernier;
dernier = nouveau;
}
}
template < typename T >
void Liste<T>::inserer(Iterateur& pos, const T& s)
{
Element<T> *nouveau = new Element<T>(s);
if(&pos != NULL)
{
nouveau->precedent = pos.position->precedent;
nouveau->suivant = pos.position;
if(nouveau->precedent != NULL)
{
nouveau->precedent->suivant = nouveau;
}
nouveau->suivant->precedent = nouveau;
}
}
template < typename T >
void Liste<T>::supprimer(Iterateur& pos)
{
if(pos.position != NULL)
{
Element< T > *old = pos.position;
if(premier == pos.position)
premier = pos.position->suivant;
if(dernier == pos.position)
dernier = pos.position->precedent;
if(pos.position->precedent != NULL)
pos.position->precedent->suivant = pos.position->suivant;
if(pos.position->suivant != NULL)
pos.position->suivant->precedent = pos.position->precedent;
if(pos.position->precedent != NULL)
pos.position = pos.position->precedent;
else
pos.position = pos.position->suivant;
delete old;
}
}
template < typename T >
Liste<T>& Liste<T>::operator=(const Liste<T>& l)
{
if(this != &l)
{
Iterateur pos = debut();
for(pos = fin(); pos != debut(); pos--)
supprimer(pos);
pos = l.debut();
for(pos = l.debut(); pos != l.fin(); pos++)
ajouter(*pos);
}
return *this;
}
et un exemple Code : /**********************************************************
*
* Auteur : Alexandre Mommers
* test_listGen.cc
*
**********************************************************/
#include <string>
#include "listeGen.h"
#include "listeGen.cc"
#include <iostream>
using namespace std;
int main()
{
Liste<string> personnel;
//ajouter 4 ellements
personnel.ajouter("Balere Bruno");
personnel.ajouter("Costaud Claude");
personnel.ajouter("Doue Damien");
personnel.ajouter("Vaillant Veronique");
//ajoute un ellement a la quatrieme position
Liste<string>::Iterateur pos = personnel.debut();
pos++; pos++; pos++;
personnel.inserer(pos, "Sage Stephan");
//supprimer l'ellement la sa seconde position
pos = personnel.debut();
pos++;
personnel.supprimer(pos);
//afficher tout les ellements
for(pos = personnel.debut(); pos != personnel.fin(); pos++)
cout << *pos << endl;
return 0;
}
"c'est un fait, on obtient plus facilement en demandant poliment une arme a la main qu'en demandant juste poliment."
http://www.doujin-spirit.net/ |
|
| Cpl.Bator |
Posté le 28 Déc 2008 à 13:49
|
|
|
Messages : 17 GCPoints : 8751 |
Sympa les itérateurs Chaos ! c'est du bon code ca :D , je le garde sous le coude 
|
|
| Scotchy |
Posté le 20 Fév 2009 à 22:34
|
|
|
Messages : 1 GCPoints : 206 |
Pourquoi ré-inventer la roue alors que std::vector fait déjà tout ceci ? (et probablement mieux vu que les compilos sont optimisés pour)
Dernière édition le 20 Fév 2009 à 22:35
|
|
| Mod |
Posté le 20 Fév 2009 à 22:54
|
|
 Messages : 4954 GCPoints : 2100823 |
Ca a un intérêt, ne serait-ce que pédagogique. Le genre d'exercices pratiques qui brasse de tout. Reste aussi que les librairies ne sont pas forcément le summum en matière d'optimisation, d'autant moins qu'elles doivent bien souvent prendre en compte une multitude de cas. Je pense par exemple aux recherches dans des listes, qui se font bien souvent par itération pure, alors qu'une recherche dichotomique serait plus efficace et rapide dans le cas d'une liste triée. Et à ce moment là, c'est grâce à ce genre de code bons à avoir sous la main que l'on pourra implémenter ce genre de choses. Et au passage, bienvenue dans le coin ;).
Dernière édition le 20 Fév 2009 à 22:55
|
|
| SEB |
Posté le 21 Fév 2009 à 10:04
|
|
 Messages : 554 GCPoints : 103313 |
J'avais déja survollé rapidement ce sujet au moment ou il avait été créé, et pour répondre à la question de freemaul, le realloc existe en c++ :) tu peut donc utiliser le meme principe qu'en C et ainsi conserver les performances :D j'ai un peu la flemme ce matin d'écrire le code qui irait bien en tant que classe pour te montrer comment l'utiliser mais sache que c'est une des meilleur facon de faire pour les vecteur cependant le probleme du realloc c'est qu'il peut echouer si je ne m'abuse... il faut donc trouver une alternative dans le cas ou il ne fonctionnerais pas. Et pour mod : rien ne t'empêche d'implémenter la dichotomie sur une std::list .. à moins que ce que tu voulais dire c'est stoker une structure de liste appropriée avec des pointeurs dans tous les sens qui permettrai de faire des recherches plus rapides. Cortialement ++ Seb
NextGine : 3D games engine
Nombre de lignes actuel : 77683 |
|
| Mod |
Posté le 21 Fév 2009 à 12:29
|
|
|
Messages : 4954 GCPoints : 2100823 |
C'était juste un exemple prit au hasard ;). | |
| SEB |
Posté le 21 Fév 2009 à 12:48
|
|
|
Messages : 554 GCPoints : 103313 |
Oui ^^ je m'en doute :p mais ce que je veu dire c'est que l'implémentation de ce genre de structure est excellente pour apréhender 1 l'orienté objet, 2 les probleme d'optimisation, 3 ce qui se cache dans le ventre des collections classiques. Cependant je pense personellement que la stl est au début du moins un tres bon compromis efficacité / simplicité :) Sachant que plusieurs version dérivée de la stl existe avec diverses optiques tout en conservant la meme convention de nommage. Voilou voilou :)
NextGine : 3D games engine
Nombre de lignes actuel : 77683 |
|
Voir le profil
Envoyer un message privé
Voir le site