Liste doublement chaînée générique avec itérateurs

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 155 fois - Téléchargée 33 fois

Contenu du snippet

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 / Exemple :


/* 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().

A voir également

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.