rang d'une liste triée et non triéeRésolu

Question

bonjour,

J'ai lu un peu ce qui se fait sur le forum au sujet des listes et des tris, j'ai relu mes cours mais je n'ai toujours pas de solutions à mon petit problème.

Ce que je cherche à faire est en apparence très simple : je chercher à créer une fonction en CPP (pour C++ builder 3.0 développement en RAD) qui, lorsqu'on lui passe en argument le rang dans une liste triée, renvoie le rang qu'occupait l'élément dans la liste non triée.

un petit exemple pour mieux comprendre :
liste triée : aa, ab, ac, ad ; avec les rangs 0, 1, 2 et 3.
liste non triée (par exemple) : ab, ac, aa, ad.

Ici, si je rentre en entrée 1, la fonction doit pouvoir me retourner 0. si je rentre 2, la valeur retournée sera 1. etc.
je sais le faire de façon statique (il suffit de créer une matrice de correspondance) mais je souhaiterais que ce soit dynamique, indépendament du nombre d'éléments dans la liste, de leur ordre.

si quelqu'un avait la solution, d'avance merci.

---------------------
tout ce qui ne tue pas rend plus fort !

pinderlot · Accepted Answer

Le code final qui marche et résoud mon problème. Il y avait un dernier souci avec les caractères accentués, c'est pour celà que j'ai dû utiliser la fonction AnsiCompare.


int multi::permutation (AnsiString langue_interface, int rang_trie)
{
AnsiString truc[maxlangue], poubelle;
int param;

if (langue_interface=="français")
   param=0;
if (langue_interface=="anglais")
   param=1;
if (langue_interface=="allemand")
   param=2;

for (int i=0; i<maxlangue; i++)
   truc=tablangue[param][i];

// trier la liste tablangue[param][];
for (int i=0; i<maxlangue-1; i++)
   {
   for (int j=i+1; j<maxlangue; j++)
      {
      if (truc[i].AnsiCompare(truc[j]) > 0)
         {
         poubelle=truc[i];
         truc[i]=truc[j];
         truc[j]=poubelle;
         }
      }
   }

// la liste triée se retrouve dans le tableau truc [maxlangue];

int rang_non_trie=0;
while (tablangue[param][rang_non_trie].AnsiCompare(truc[rang_trie])!=0)
   rang_non_trie++;
return (rang_non_trie);
}



Et merci à tous.
-----------------------------------------------
[i]Tout ce qui ne tue pas rend plus fort !

cs_JCDjcd · Answer

He bien dans ta stucture des elements tu rajoutes un entier qui est le rang non trié, ainsi quand tu va chercher l'element quand il est trié, tu a directement le rang non-trié.

Un petite question : comment est l'ordre quand il ne sont pas encore triés tes elements ?

pinderlot · Answer

Voici à peu près le code de la fonction que j'avais écrit... il est probablement incorrect dans les déclarations... mais de toute façon, il ne répond pas correctement à mon problème !

int permutation (AnsiString pt[][], int index)
{
int tableau[max]; // max est défini ailleurs comme une constante
AnsiString truc[max];

for (int i=0; i++; i<max)
   {
   tableau[i]=i;
   truc[i]=pt[param][i]; // param est défini ailleurs
   }
   
for (int i=0; i++; imax)
   {
   for (int j=i+1; j++; j<max)
      {
      if (truc[i]>truc[j])
         {
         poub=truc[i];
         truc[i]=truc[j];
         truc[j]=poub;
         int temp = j;
         }
      tableau[temp]=i;
      }
   }
   
int k=0;
while (tableau[i]!=index)
   k++;
return (k);
}
       
En fait dans mon besoin, le programme manipule le contenu de ListBox... Je charge la ListBox à partir d'un tableau non trié (dont l'ordre correspond à celui des éléments du tableau pt[0][] quelle que soit la langue). La ListBox trie automatiquement les éléments et les classes par ordre alphabétique (c'est plus conviviable pour l'utilisateur à l'écran).
J'ai ainsi un tableau pt[4][max] avec :
pt[0][max] qui contient les éléments en français et triés en français
pt[1][max] qui contient les éléments traduits en allemand et triés en allemand
pt[2][max] qui contient les éléments traduits en anglais et triés en anglais
pt[3][max] etc...
si on analyse la situation, un élément qui se trouvait en pt[0][12] se trouve maintenant en pt[1][5]... et il faut donc que ma fonction, quand je lui rentre 5 en entrée me retourne la valeur 12.

L'idée de la structure me paraît intéressante mais difficile à mettre en oeuvre sans modifier de façon importante mon programme... mais je vais y réfléchir. Merci.

cs_JCDjcd · Answer

Au lieu d'avoir un type AnsiString pour pt, tu assignes un nouveau type TOTO par exemple

typedef struct
{
AnsiString str;
int oldRank;
}TOTO;

donc au debut quans tu rempli tout tes mots en differentes langue, tu rempli en meme temp oldRank pour chaque mot

donc tu auras :
int permutation (TOTO pt[][], int index)
{
...
}

et au lieu de faire : truc[i]=pt[param][i];
tu feras : truc[i]=pt[param][i].str;

pinderlot · Answer

Je pense avoir trouvé la solution et comme souvent... la réponse vient du fait que le problème était mal posé.

int permutation (AnsiString pt[][], int index)
{
AnsiString truc[maxlangue];

// stocke la liste non triée dans le tableau truc[maxlangue]
for (int i=0; i<maxlangue; i++)
  truc=pt[param][i]; // param est défini ailleurs

// trier la liste pt[param][];
for (int i=0; i<maxlangue; i++)
  {
  for (int j=i+1; j<maxlangue; j++)
    {
    if (truc[i]>truc[j])
      {
      poub=truc[i];
      truc[i]=truc[j];
      truc[j]=poub;
      }
    }
  }

// la liste triée se retrouve dans le tableau truc [max];

int k=0;
while (pt[param][k]!=truc[index])
   k++;
return (k);
}

Il suffit en fait de comparer, on pas les index, mais les valeurs du tableau et d'en déduire le rang initial pour le retourner. Je n'ai pas encore tester le code mais je pense que ca doit marcher.

[i]tout ce qui ne tue pas rend plus fort !

Rang d'une liste triée et non triée

5 réponses

Votre réponse

Discussions similaires