cs_poppyto
Messages postés540Date d'inscriptiondimanche 29 décembre 2002StatutModérateurDernière intervention13 mai 2011
-
13 juin 2005 à 07:45
Hades53
Messages postés231Date d'inscriptionmercredi 12 février 2003StatutMembreDernière intervention 7 juillet 2009
-
15 juin 2005 à 01:49
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
Hades53
Messages postés231Date d'inscriptionmercredi 12 février 2003StatutMembreDernière intervention 7 juillet 2009 15 juin 2005 à 01:49
C'est bon, j'ai trouvé =] :
int GetSortedPos(const char *cle, int a, int b)
{
b -= 1;
int m , comp;
while (a <= b) {
m = (a + b) / 2;
comp = ListCompare(cle,m);
if (comp > 0) b = m - 1;
else if (comp < 0) a = m + 1;
else return m;
}
return a;
}
cs_poppyto
Messages postés540Date d'inscriptiondimanche 29 décembre 2002StatutModérateurDernière intervention13 mai 2011 14 juin 2005 à 23:01
Désolé :oP
Hades53
Messages postés231Date d'inscriptionmercredi 12 février 2003StatutMembreDernière intervention 7 juillet 2009 14 juin 2005 à 22:53
Ok, j'ai fais une petite fonction dichotomique (en m'inspirant d'exemple de recherche dichotomique) pour obtenir la position qu'un élément devrait avoir dans la listbox, mais la fonction ne donne pas toujours la bonne position.
int ListCompare(const char *cle, int index) {
__int64 comp = 0;
int size = (int)SendMessage(hlist,LB_GETTEXTLEN,index,NULL);
char *elm = new char[size + 1];
SendMessage(hlist,LB_GETTEXT,index,(LPARAM)elm);
switch (tsort) {
case POP_AZSORT: case POP_ZASORT:
comp = lstrcmpi(elm,cle);
delete[] elm;
if (!comp) return 0;
if (comp < 0) return tsort == POP_AZSORT ? -1 : 1;
return tsort == POP_AZSORT ? 1 : -1;
case POP_09SORT: case POP_90SORT:
comp = _atoi64(elm) - _atoi64(cle);
delete[] elm;
if (!comp) return 0;
if (comp < 0) return tsort == POP_09SORT ? -1 : 1;
return tsort == POP_09SORT ? 1 : -1;
case POP_ALSORT: case POP_DLSORT:
comp = size - lstrlen(cle);
delete[] elm;
if (!comp) return 0;
if (comp < 0) return tsort == POP_ALSORT ? -1 : 1;
return tsort == POP_ALSORT ? 1 : -1;
}
return 0;
}
int GetSortedPos(const char *cle, int a, int b, int reserved) {
int m, c, j = 0;
while (a <= b) {
m = ((a + b) / 2);
c = ListCompare(cle,m);
if (!c) return m;
else if (c > 0) {
b = m - 1 ;
j = m ;
}
else {
a = m + 1;
j = m + 1;
}
}
return j != NULL ? j : (int)SendMessage(hlist,LB_GETCOUNT,NULL,NULL);
}
Pour insérer, je fais: SendMessage(hwnd,LB_INSERTSTRING,(WPARAM)GetSortedPos(chaine,0,(int)SendMessage(hwnd,LB_GETCOUNT,NULL,NULL) - 1 ,NULL),(LPARAM)chaine);
Le problème vient bien évidement de la fonction GetSortedPos(), arrive-tu à voir ce qui cloche ?
vecchio56
Messages postés6535Date d'inscriptionlundi 16 décembre 2002StatutMembreDernière intervention22 août 201014 14 juin 2005 à 11:16
Oui, la recherche dichotomique bien sur, tu pourra sans doute pas trouver plus rapide. Si cela doit te servir à faire des insertions, va voir du coté de map (arbre binaire), car un tableau permet la recherche dichotomique mais pas l'insertion, et une liste chainée c'est le contraire
Hades53
Messages postés231Date d'inscriptionmercredi 12 février 2003StatutMembreDernière intervention 7 juillet 2009 13 juin 2005 à 23:38
poppyto: je crois que vecchio56 a tout dis ;)
vecchio56: ok, merci du conseil
Quelqu'un connaitrai-t-il un algo rapide de tri à l'insertion (déterminer la position future qu'aura un élément dans une liste triée) ?
vecchio56
Messages postés6535Date d'inscriptionlundi 16 décembre 2002StatutMembreDernière intervention22 août 201014 13 juin 2005 à 10:26
Hades53, plutot que de disable un warning comme ca, enlève plutot l'option /Wp64 (C/C++ > Général > Détection des problèmes de portabilité 64 bits)
vecchio56
Messages postés6535Date d'inscriptionlundi 16 décembre 2002StatutMembreDernière intervention22 août 201014 13 juin 2005 à 10:23
A sa décharge, son programme est un plus complet que LBS_SORT: tri selon un autre critère que l'ordre alphabétique, et tri d'une partie seulement de la listBox
C'est quand même interessant à mon avis
cs_poppyto
Messages postés540Date d'inscriptiondimanche 29 décembre 2002StatutModérateurDernière intervention13 mai 2011 13 juin 2005 à 07:45
15 juin 2005 à 01:49
int GetSortedPos(const char *cle, int a, int b)
{
b -= 1;
int m , comp;
while (a <= b) {
m = (a + b) / 2;
comp = ListCompare(cle,m);
if (comp > 0) b = m - 1;
else if (comp < 0) a = m + 1;
else return m;
}
return a;
}
14 juin 2005 à 23:01
14 juin 2005 à 22:53
int ListCompare(const char *cle, int index) {
__int64 comp = 0;
int size = (int)SendMessage(hlist,LB_GETTEXTLEN,index,NULL);
char *elm = new char[size + 1];
SendMessage(hlist,LB_GETTEXT,index,(LPARAM)elm);
switch (tsort) {
case POP_AZSORT: case POP_ZASORT:
comp = lstrcmpi(elm,cle);
delete[] elm;
if (!comp) return 0;
if (comp < 0) return tsort == POP_AZSORT ? -1 : 1;
return tsort == POP_AZSORT ? 1 : -1;
case POP_09SORT: case POP_90SORT:
comp = _atoi64(elm) - _atoi64(cle);
delete[] elm;
if (!comp) return 0;
if (comp < 0) return tsort == POP_09SORT ? -1 : 1;
return tsort == POP_09SORT ? 1 : -1;
case POP_ALSORT: case POP_DLSORT:
comp = size - lstrlen(cle);
delete[] elm;
if (!comp) return 0;
if (comp < 0) return tsort == POP_ALSORT ? -1 : 1;
return tsort == POP_ALSORT ? 1 : -1;
}
return 0;
}
int GetSortedPos(const char *cle, int a, int b, int reserved) {
int m, c, j = 0;
while (a <= b) {
m = ((a + b) / 2);
c = ListCompare(cle,m);
if (!c) return m;
else if (c > 0) {
b = m - 1 ;
j = m ;
}
else {
a = m + 1;
j = m + 1;
}
}
return j != NULL ? j : (int)SendMessage(hlist,LB_GETCOUNT,NULL,NULL);
}
Pour insérer, je fais: SendMessage(hwnd,LB_INSERTSTRING,(WPARAM)GetSortedPos(chaine,0,(int)SendMessage(hwnd,LB_GETCOUNT,NULL,NULL) - 1 ,NULL),(LPARAM)chaine);
Le problème vient bien évidement de la fonction GetSortedPos(), arrive-tu à voir ce qui cloche ?
14 juin 2005 à 11:16
13 juin 2005 à 23:38
vecchio56: ok, merci du conseil
Quelqu'un connaitrai-t-il un algo rapide de tri à l'insertion (déterminer la position future qu'aura un élément dans une liste triée) ?
13 juin 2005 à 10:26
13 juin 2005 à 10:23
C'est quand même interessant à mon avis
13 juin 2005 à 07:45