|
 Trouver une ressource
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !
 LISTE DOUBLEMENT CHAÎNÉE GÉNÉRIQUE AVEC ITÉRATEURS
 Information sur la source
 Description
Voici un conteneur d'objets, une liste doublement chaînée.
Vous pourrez ajouter, insérer, supprimer, modifier, permuter et parcourir les éléments de la liste.
Pour des traitements plus rapides, des itérateurs sont à disposition.
Cette source est à but éducative, car si vous utilisez la STL, il est nettement préférable d'utiliser la librairie <list>.
 Source
- /* Container; liste doublement chaînée
- fichier listc.h */
-
- #include <windows.h> //Pour allocation/suppression de mémoire dans le tas
- //#include <stdio.h>
-
- template <class T> class listc;
- template <class T> class i_listc;
-
- template <class M> class engine { //classe de l'objet contenu
- private:
- engine<M>*next; //pointeur sur l'objet suivant
- engine<M>*prev; //pointeur sur l'objet précédant
- M data; //l'objet
- friend listc<M>; //l'accès aux membres privés est autorisé pour le conteneur
- friend i_listc<M>;//l'accès aux membres privés est autorisé pour l'itérateur
- };
- template <class T> class i_listc { //classe de l'itérateur
- private:
- engine<T>*elm;
- listc<T> *parent;
- friend listc<T>;
- public:
- typedef i_listc<T> iter;
- i_listc(void *); //pour les conversions
- i_listc(); //constructeur par défaut
- T get(); //retourne l'objet
- bool Delete(); //efface l'objet
- bool InsertA(T);
- bool InsertB(T);
- bool set(T);
- iter operator++ (); //passe à l'élément suivant
- iter operator++ (int);
- iter operator-- (); //passe à l'élément précédent
- iter operator-- (int);
- bool operator==(const iter&) const;
- bool operator!=(const iter&) const;
- listc<T> *ptr();
- };
- template <class T> class listc { //classe générale du conteneur de la liste chaînée
- private:
- engine<T> *head; //pointeur sur le premier objet
- engine<T> *queue;//pointeur sur le dernier objet
- int total; //nombre total d'objets contenus dans la liste chaînée
- i_listc<T> cur;
- bool New(T);
- public:
- typedef i_listc<T> iterator; //on crée un alias
- iterator begin();
- iterator end();
- iterator ptr(int); //on revoit un itérateur sur le Nième objet de la liste
- listc(); //constructeur par défaut
- ~listc();
- bool Swap(iterator &, iterator &); //échange la place des éléments
- bool AddFront(T); //ajoute un nouveau élément en début de liste
- bool AddBack(T); //ajoute un nouveau élément en fin de liste
- bool Delete(int i); //supprime le Nième objet
- bool Delete(iterator &); //supprime l'objet pointé par l'itérateur
- bool InsertA(iterator &, T); //Insert un nouveau élément après l'objet pointé
- bool InsertB(iterator &, T); //Insert un nouveau élément avant l'objet pointé
- bool set(iterator &, T); //modifie l'objet
- Free(); //Efface tous les objets
- T operator [] (int); //opérateur d'indexation
- int Total(); //nombre total d'objets contenus
- size_t size() const; //taille du conteneur
- //aff();
- };
-
- /*
- template <class T>listc<T>::aff() {
- engine<T> *elm = head;
- cout << "-\n";
- while (elm) {
- cout << "ptr: " << elm
- << " next: " << elm->next
- << " prev: " << elm->prev
- << " data: " << elm->data << endl;
- elm = elm->next;
- }
- cout << "\n<head>\tptr: " << head << " next: " << head->next
- << " prev: " << head->prev
- << " data: " << head->data << endl;
- cout << "<queue>\tptr: " << queue << " next: " << queue->next
- << " prev: " << queue->prev
- << " data: " << queue->data << endl;
- cout << "-\n";
- }
- */
- template <class T> listc<T>* i_listc<T>::ptr() {
- return parent;
- }
- template <class T> i_listc<T>::i_listc(void *ptr) {
- elm = (engine<T>*)ptr;
- }
- template <class T> bool i_listc<T>::operator ==(const i_listc<T> &source) const {
- if (elm == source.elm) return 1;
- return 0;
- }
- template <class T> bool i_listc<T>::operator !=(const i_listc<T> &source) const {
- if (elm != source.elm) return 1;
- return 0;
- }
- template <class T> i_listc<T>::i_listc():elm(NULL){; }
- template <class T> i_listc<T> i_listc<T>::operator ++() { // ++x
- if (!elm) return *this;
- elm = elm->next;
- return *this;
- }
- template <class T> i_listc<T> i_listc<T>::operator ++(int) { // x++
- if (!elm) return *this;
- i_listc<T> tmp = *this;
- elm = elm->next;
- return tmp;
- }
- template <class T> i_listc<T> i_listc<T>::operator --() { // --x
- if (!elm) return *this;
- elm = elm->prev;
- return *this;
- }
- template <class T> i_listc<T> i_listc<T>::operator --(int) { // x--
- if (!elm) return *this;
- i_listc<T> tmp = *this;
- elm = elm->prev;
- return tmp;
- }
- template <class T> bool i_listc<T>::set(T data) {
- return parent->set(*this,data);
- }
- template <class T> bool i_listc<T>::InsertA(T data) {
- return parent->InsertA(*this,data);
- }
- template <class T> bool i_listc<T>::InsertB(T data) {
- return parent->InsertB(*this,data);
- }
- template<class T>bool listc<T>::Swap(iterator &elm1, iterator &elm2) {
- if (elm1 == NULL || elm2 == NULL) return 0;
- iterator first, second;
- engine<T> *ptr1, *ptr2;
- if (elm1.elm->next == elm2.elm) first = elm1, second = elm2;
- else if (elm2.elm->next == elm1.elm) first = elm2, second = elm1;
- else goto next;
- /*les deux éléments se suivent directement, donc nous n'échangerons
- pas bêtement les pointeurs des deux éléments, en effet cela
- pourrait conduire à un bogue (élément qui pointerait sur lui-même) */
- ptr1 = first.elm->prev, ptr2 = second.elm->next;
- second.elm->next = first.elm;
- second.elm->prev = ptr1;
- if (ptr1) ptr1->next = second.elm;
-
- first.elm->prev = second.elm;
- first.elm->next = ptr2;
- if (ptr2) ptr2->prev = first.elm;
- goto end;
- next:
- /*les deux éléments ne se suivent pas, nous utiliserons donc
- une technique qui consistera à échanger tous les pointeurs
- des deux éléments */
- ptr1 = elm1.elm->next, ptr2 = elm1.elm->prev;
- if (elm1.elm->prev) elm1.elm->prev->next = elm2.elm;
- if (elm1.elm->next) elm1.elm->next->prev = elm2.elm;
- elm1.elm->next = elm2.elm->next;
- elm1.elm->prev = elm2.elm->prev;
-
- if (elm2.elm->prev) elm2.elm->prev->next = elm1.elm;
- if (elm2.elm->next) elm2.elm->next->prev = elm1.elm;
- elm2.elm->next = ptr1;
- elm2.elm->prev = ptr2;
- end:
- //on met à jour le pointeur de début de liste et de fin de liste
- if (head == elm1.elm) head = elm2.elm;
- else if (head == elm2.elm) head = elm1.elm;
- if (queue == elm1.elm) queue = elm2.elm;
- else if (queue == elm2.elm) queue = elm1.elm;
- return 1;
- }
- template <class T>i_listc<T> listc<T>::ptr(int i) {
- engine<T> *elm = head;
- for (int o = 1;(elm && elm->next) && o != i;o++) elm = elm->next;
- if (o == i && elm) {
- cur.elm = elm;
- cur.parent = this;
- return cur;
- }
- cur.elm = NULL;
- cur.parent = this;
- return cur;
- }
- template <class T>T i_listc<T>::get() {
- return elm->data;
- }
- template <class T> i_listc<T> listc<T>::begin() {
- cur.elm = head;
- cur.parent = this;
- return cur;
- }
- template <class T> i_listc<T> listc<T>::end() {
- cur.elm = queue;
- cur.parent = this;
- return cur;
- }
- template <class T> bool i_listc<T>::Delete() {
- return parent->Delete(*this);
- }
- template <class T> bool listc<T>::New(T data) {
- engine<T> *elm = (engine<T>*)HeapAlloc(GetProcessHeap(),0,sizeof(engine<T>));
- elm->next = NULL;
- elm->prev = NULL;
- elm->data = data;
- queue = head = elm;
- total++;
- return 1;
- }
- template <class T> bool listc<T>::set(iterator &iter, T data) {
- if (iter.parent != this || iter.elm == NULL) return 0;
- iter.elm->data = data;
- return 1;
- }
- template <class T> bool listc<T>::AddFront(T data) {
- if (!head) return New(data); /* si la liste est vide, on la crée */
- iterator iter = begin();
- return InsertB(iter,data);
- }
- template <class T> bool listc<T>::AddBack(T data) {
- if (!head) return New(data);
- iterator iter = end();
- return InsertA(iter,data);
- }
- template <class T> bool listc<T>::InsertA(iterator &iter, T data) {
- if (iter.parent != this || iter.elm == NULL) return 0;
- engine<T> *elm = (engine<T>*)HeapAlloc(GetProcessHeap(),0,sizeof(engine<T>));
- if (!elm) return 0;
-
- if (queue == iter.elm) {
- queue = elm;
- elm->next = NULL;
- }
- else {
- elm->next = iter.elm->next;
- iter.elm->next->prev = elm;
- }
- iter.elm->next = elm;
- elm->prev = iter.elm;
-
- elm->data = data;
- total++;
- return 1;
- }
- template <class T> bool listc<T>::InsertB(iterator &iter, T data) {
- if (iter.parent != this || iter.elm == NULL) return 0;
- engine<T> *elm = (engine<T>*)HeapAlloc(GetProcessHeap(),0,sizeof(engine<T>));
- if (!elm) return 0;
-
- if (head == iter.elm) {
- head = elm;
- elm->prev = NULL;
- }
- else {
- elm->prev = iter.elm->prev;
- iter.elm->prev->next = elm;
- }
- iter.elm->prev = elm;
- elm->next = iter.elm;
-
- elm->data = data;
- total++;
- return 1;
- }
- template <class T> bool listc<T>::Delete(iterator &iter) {
- engine<T>*elm;
- if (iter.parent != this) return 0;
- if (iter.elm == NULL) return 0;
- elm = iter.elm->next;
- if (iter.elm == head) {
- head = elm;
- if (head) head->prev = NULL;
- }
- else {
- if (queue == iter.elm) queue = iter.elm->prev;
- iter.elm->prev->next = elm;
- if (iter.elm->next) iter.elm->next->prev = iter.elm->prev;
- }
- HeapFree(GetProcessHeap(),0,iter.elm);
- total--;
- iter.elm = elm;
- return 1;
- }
- template <class T> bool listc<T>::Delete(int i) {
- listc<T>::iterator iter = ptr(i);
- return Delete(iter);
- }
- template <class T>T listc<T>::operator[](int i) {
- engine<T> *elm = head;
- for (int o = 0;(elm && elm->next) && o != i;o++) elm = elm->next;
- if (o == i && elm) return elm->data;
- return NULL;
- }
-
- template <class T> listc<T>::listc():head(NULL),queue(NULL),total(0){ ; }
- template <class T> listc<T>::~listc() {
- Free();
- }
- template <class T>int listc<T>::Total() {
- return total;
- }
- template <class T>listc<T>::Free() {
- engine <T> *elm = head;
- while (head) {
- head = elm->next;
- engine<T> *del = elm;
- HeapFree(GetProcessHeap(),0,del);
- elm = head;
- }
- head = queue = NULL;
- total = 0;
- }
- template <class T>size_t listc<T>::size() const {
- return sizeof(listc<T>) + sizeof(engine<T>) * total;
- }
/* Container; liste doublement chaînée
fichier listc.h */
#include <windows.h> //Pour allocation/suppression de mémoire dans le tas
//#include <stdio.h>
template <class T> class listc;
template <class T> class i_listc;
template <class M> class engine { //classe de l'objet contenu
private:
engine<M>*next; //pointeur sur l'objet suivant
engine<M>*prev; //pointeur sur l'objet précédant
M data; //l'objet
friend listc<M>; //l'accès aux membres privés est autorisé pour le conteneur
friend i_listc<M>;//l'accès aux membres privés est autorisé pour l'itérateur
};
template <class T> class i_listc { //classe de l'itérateur
private:
engine<T>*elm;
listc<T> *parent;
friend listc<T>;
public:
typedef i_listc<T> iter;
i_listc(void *); //pour les conversions
i_listc(); //constructeur par défaut
T get(); //retourne l'objet
bool Delete(); //efface l'objet
bool InsertA(T);
bool InsertB(T);
bool set(T);
iter operator++ (); //passe à l'élément suivant
iter operator++ (int);
iter operator-- (); //passe à l'élément précédent
iter operator-- (int);
bool operator==(const iter&) const;
bool operator!=(const iter&) const;
listc<T> *ptr();
};
template <class T> class listc { //classe générale du conteneur de la liste chaînée
private:
engine<T> *head; //pointeur sur le premier objet
engine<T> *queue;//pointeur sur le dernier objet
int total; //nombre total d'objets contenus dans la liste chaînée
i_listc<T> cur;
bool New(T);
public:
typedef i_listc<T> iterator; //on crée un alias
iterator begin();
iterator end();
iterator ptr(int); //on revoit un itérateur sur le Nième objet de la liste
listc(); //constructeur par défaut
~listc();
bool Swap(iterator &, iterator &); //échange la place des éléments
bool AddFront(T); //ajoute un nouveau élément en début de liste
bool AddBack(T); //ajoute un nouveau élément en fin de liste
bool Delete(int i); //supprime le Nième objet
bool Delete(iterator &); //supprime l'objet pointé par l'itérateur
bool InsertA(iterator &, T); //Insert un nouveau élément après l'objet pointé
bool InsertB(iterator &, T); //Insert un nouveau élément avant l'objet pointé
bool set(iterator &, T); //modifie l'objet
Free(); //Efface tous les objets
T operator [] (int); //opérateur d'indexation
int Total(); //nombre total d'objets contenus
size_t size() const; //taille du conteneur
//aff();
};
/*
template <class T>listc<T>::aff() {
engine<T> *elm = head;
cout << "-\n";
while (elm) {
cout << "ptr: " << elm
<< " next: " << elm->next
<< " prev: " << elm->prev
<< " data: " << elm->data << endl;
elm = elm->next;
}
cout << "\n<head>\tptr: " << head << " next: " << head->next
<< " prev: " << head->prev
<< " data: " << head->data << endl;
cout << "<queue>\tptr: " << queue << " next: " << queue->next
<< " prev: " << queue->prev
<< " data: " << queue->data << endl;
cout << "-\n";
}
*/
template <class T> listc<T>* i_listc<T>::ptr() {
return parent;
}
template <class T> i_listc<T>::i_listc(void *ptr) {
elm = (engine<T>*)ptr;
}
template <class T> bool i_listc<T>::operator ==(const i_listc<T> &source) const {
if (elm == source.elm) return 1;
return 0;
}
template <class T> bool i_listc<T>::operator !=(const i_listc<T> &source) const {
if (elm != source.elm) return 1;
return 0;
}
template <class T> i_listc<T>::i_listc():elm(NULL){; }
template <class T> i_listc<T> i_listc<T>::operator ++() { // ++x
if (!elm) return *this;
elm = elm->next;
return *this;
}
template <class T> i_listc<T> i_listc<T>::operator ++(int) { // x++
if (!elm) return *this;
i_listc<T> tmp = *this;
elm = elm->next;
return tmp;
}
template <class T> i_listc<T> i_listc<T>::operator --() { // --x
if (!elm) return *this;
elm = elm->prev;
return *this;
}
template <class T> i_listc<T> i_listc<T>::operator --(int) { // x--
if (!elm) return *this;
i_listc<T> tmp = *this;
elm = elm->prev;
return tmp;
}
template <class T> bool i_listc<T>::set(T data) {
return parent->set(*this,data);
}
template <class T> bool i_listc<T>::InsertA(T data) {
return parent->InsertA(*this,data);
}
template <class T> bool i_listc<T>::InsertB(T data) {
return parent->InsertB(*this,data);
}
template<class T>bool listc<T>::Swap(iterator &elm1, iterator &elm2) {
if (elm1 == NULL || elm2 == NULL) return 0;
iterator first, second;
engine<T> *ptr1, *ptr2;
if (elm1.elm->next == elm2.elm) first = elm1, second = elm2;
else if (elm2.elm->next == elm1.elm) first = elm2, second = elm1;
else goto next;
/*les deux éléments se suivent directement, donc nous n'échangerons
pas bêtement les pointeurs des deux éléments, en effet cela
pourrait conduire à un bogue (élément qui pointerait sur lui-même) */
ptr1 = first.elm->prev, ptr2 = second.elm->next;
second.elm->next = first.elm;
second.elm->prev = ptr1;
if (ptr1) ptr1->next = second.elm;
first.elm->prev = second.elm;
first.elm->next = ptr2;
if (ptr2) ptr2->prev = first.elm;
goto end;
next:
/*les deux éléments ne se suivent pas, nous utiliserons donc
une technique qui consistera à échanger tous les pointeurs
des deux éléments */
ptr1 = elm1.elm->next, ptr2 = elm1.elm->prev;
if (elm1.elm->prev) elm1.elm->prev->next = elm2.elm;
if (elm1.elm->next) elm1.elm->next->prev = elm2.elm;
elm1.elm->next = elm2.elm->next;
elm1.elm->prev = elm2.elm->prev;
if (elm2.elm->prev) elm2.elm->prev->next = elm1.elm;
if (elm2.elm->next) elm2.elm->next->prev = elm1.elm;
elm2.elm->next = ptr1;
elm2.elm->prev = ptr2;
end:
//on met à jour le pointeur de début de liste et de fin de liste
if (head == elm1.elm) head = elm2.elm;
else if (head == elm2.elm) head = elm1.elm;
if (queue == elm1.elm) queue = elm2.elm;
else if (queue == elm2.elm) queue = elm1.elm;
return 1;
}
template <class T>i_listc<T> listc<T>::ptr(int i) {
engine<T> *elm = head;
for (int o = 1;(elm && elm->next) && o != i;o++) elm = elm->next;
if (o == i && elm) {
cur.elm = elm;
cur.parent = this;
return cur;
}
cur.elm = NULL;
cur.parent = this;
return cur;
}
template <class T>T i_listc<T>::get() {
return elm->data;
}
template <class T> i_listc<T> listc<T>::begin() {
cur.elm = head;
cur.parent = this;
return cur;
}
template <class T> i_listc<T> listc<T>::end() {
cur.elm = queue;
cur.parent = this;
return cur;
}
template <class T> bool i_listc<T>::Delete() {
return parent->Delete(*this);
}
template <class T> bool listc<T>::New(T data) {
engine<T> *elm = (engine<T>*)HeapAlloc(GetProcessHeap(),0,sizeof(engine<T>));
elm->next = NULL;
elm->prev = NULL;
elm->data = data;
queue = head = elm;
total++;
return 1;
}
template <class T> bool listc<T>::set(iterator &iter, T data) {
if (iter.parent != this || iter.elm == NULL) return 0;
iter.elm->data = data;
return 1;
}
template <class T> bool listc<T>::AddFront(T data) {
if (!head) return New(data); /* si la liste est vide, on la crée */
iterator iter = begin();
return InsertB(iter,data);
}
template <class T> bool listc<T>::AddBack(T data) {
if (!head) return New(data);
iterator iter = end();
return InsertA(iter,data);
}
template <class T> bool listc<T>::InsertA(iterator &iter, T data) {
if (iter.parent != this || iter.elm == NULL) return 0;
engine<T> *elm = (engine<T>*)HeapAlloc(GetProcessHeap(),0,sizeof(engine<T>));
if (!elm) return 0;
if (queue == iter.elm) {
queue = elm;
elm->next = NULL;
}
else {
elm->next = iter.elm->next;
iter.elm->next->prev = elm;
}
iter.elm->next = elm;
elm->prev = iter.elm;
elm->data = data;
total++;
return 1;
}
template <class T> bool listc<T>::InsertB(iterator &iter, T data) {
if (iter.parent != this || iter.elm == NULL) return 0;
engine<T> *elm = (engine<T>*)HeapAlloc(GetProcessHeap(),0,sizeof(engine<T>));
if (!elm) return 0;
if (head == iter.elm) {
head = elm;
elm->prev = NULL;
}
else {
elm->prev = iter.elm->prev;
iter.elm->prev->next = elm;
}
iter.elm->prev = elm;
elm->next = iter.elm;
elm->data = data;
total++;
return 1;
}
template <class T> bool listc<T>::Delete(iterator &iter) {
engine<T>*elm;
if (iter.parent != this) return 0;
if (iter.elm == NULL) return 0;
elm = iter.elm->next;
if (iter.elm == head) {
head = elm;
if (head) head->prev = NULL;
}
else {
if (queue == iter.elm) queue = iter.elm->prev;
iter.elm->prev->next = elm;
if (iter.elm->next) iter.elm->next->prev = iter.elm->prev;
}
HeapFree(GetProcessHeap(),0,iter.elm);
total--;
iter.elm = elm;
return 1;
}
template <class T> bool listc<T>::Delete(int i) {
listc<T>::iterator iter = ptr(i);
return Delete(iter);
}
template <class T>T listc<T>::operator[](int i) {
engine<T> *elm = head;
for (int o = 0;(elm && elm->next) && o != i;o++) elm = elm->next;
if (o == i && elm) return elm->data;
return NULL;
}
template <class T> listc<T>::listc():head(NULL),queue(NULL),total(0){ ; }
template <class T> listc<T>::~listc() {
Free();
}
template <class T>int listc<T>::Total() {
return total;
}
template <class T>listc<T>::Free() {
engine <T> *elm = head;
while (head) {
head = elm->next;
engine<T> *del = elm;
HeapFree(GetProcessHeap(),0,del);
elm = head;
}
head = queue = NULL;
total = 0;
}
template <class T>size_t listc<T>::size() const {
return sizeof(listc<T>) + sizeof(engine<T>) * total;
}
 Conclusion
Si vous ne voulez pas utiliser <windows.h> pour la gestion dynamique de la mémoire, remplacez HeapAlloc() et HeapFree() par leur équivalent (new et add si vous utilisez les librairies C++).
Pour voir comment parcourir les éléments de la liste à l'aide d'itérateurs, regardez la fonction aff().
 Historique
- 29 janvier 2005 21:33:53 :
- Correction d'un problème dans la fonction swap (erreur syntaxique).
- 29 janvier 2005 21:34:45 :
- Correction d'un problème dans la fonction swap (erreur syntaxique).
 Sources du même auteur
 Sources de la même categorie
 Commentaires et avis
|
Comparez les prix Nouvelle version
|