Tri à bulle sur les membres d'une structure

Bonjour , je me suis codé une routine me permettant de gérer une liste chaîné , j'ai aussi inclu une méthode me permettant de faire un tri à bulle sur les éléments de cette liste.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261

#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 void AddElement(MyType Value); //--------------------------------------------------- MyType GetCurrentElement(void); //--------------------------------------------------- int CountElement(void); //--------------------------------------------------- void FirstElement(void); //--------------------------------------------------- void LastElement(void); //--------------------------------------------------- MyType SelectElement(int index); // Le 1° Element est le numero 1 / the first element is n°1 //--------------------------------------------------- void SetElementValue(int index,MyType Value); //--------------------------------------------------- void DeleteElement(); //--------------------------------------------------- int FindElement(MyType Element); // Renvoi l'index de l'élement , sinon -1 //--------------------------------------------------- void SwapElement(int A,int B); //--------------------------------------------------- void ArrayBubbleSort(void); //--------------------------------------------------- void ArrayBubbleSort(size_t member);         }; /*----------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------*/ template < class MyType > CArray<MyType>::CArray(void){NbrElement=0;} /*----------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------*/ template < class MyType > CArray<MyType>::~CArray(void){} /*----------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------*/ template < class MyType > 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 > MyType CArray<MyType>::GetCurrentElement(void){ return this->Liste->Valeur; } /*----------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------*/ template < class MyType > int CArray<MyType>::CountElement(void){ return this->NbrElement; } /*----------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------*/ template < class MyType > void CArray<MyType>::FirstElement(void){   while(this->Liste->Precedent!=NULL) { this->Liste = this->Liste->Precedent; }   } /*----------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------*/ template < class MyType > void CArray<MyType>::LastElement(void){   while(this->Liste->Suivant!=NULL) { this->Liste = this->Liste->Suivant; } } /*----------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------*/ template < class MyType > 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 > 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 > 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 > 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 > 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 > 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);   } } }       } /*----------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------*/ #endif

---

Cette méthode me permet donc de faire le tri sur les éléments de la liste , en admettant que la liste est composé de float , int , double , etc...

Code:

---

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

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);   } } } }

---

je voudrais pouvoir trié cette liste en admettant que la liste contient des éléments d'une structure ou d'une classe.

Par exemple , trier en fonction de Y :

Code:

---

1 2 3 4 5

typedef struct Vector2 Vector2; struct Vector2 { float x,y; };

---

Merci.

Salut,

Si tu veux trier tes éléments de façon 'adaptable', il faut que soit les éléments aient une méthode pour se comparer, soit tu crées une fonction pour comparer deux éléments à et tu la passes en paramètres de ta fonction BubbleSort, soit pour chaque structure tu définis un opérateur de comparaison >, soit tu passes carrément un foncteur en paramètre de ta fonction BubbleSort, etc.

Si tu veux avoir des tutoriels sur les foncteurs tu peux regarder sur developpez.com, il y en a plein ;)

Le problème du Foncteur , c'est qu'il dois être fait en fonction de la structure ou classe qui est dans la liste chainée.
je vais opté pour la piste des pointeurs & l'utilisation d'offsetof() pour me positionné dans la structure.
si quelqu'un est déjà passé par là.

Merci.

Utilise les polices :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

template < class T> class TrieurParDefaut { static bool IsSup(const T& t1, const T& t2) { return t1 > t2; } };   template < class T> class TrieurDeVecteurParY { static bool IsSup(const T& t1, const T& t2) { return t1.y > t2.y; } };   template < class MyType, class Trieur = TrieurParDefaut> class CArray { void CArray<MyType>::ArrayBubbleSort(void){   for(int i=1; i<=this->NbrElement-1;i++) { for(int j=i+1; j<=this->NbrElement;j++) {   if(Trieur::IsSup(this->SelectElement(i), this->SelectElement(j))) { this->SwapElement(j,i);   } } } } };   typedef CArray<Vector2> TableauDeVectorStandard; typedef CArray<Vector2, TrieurDeVecteurParY> TableauDeVectorQuiLesTrieParLesY;

---

Je ne suis pas sûr de la syntaxe