Tri par insertion sur listes simplement chainées

Question

Bonjour,

voilà, je vous explique rapidement mon problème, je dois élaborer
une procédure de tri par insertion sur une liste qui vient en paramètre
de ma procédure.

Le seul petit problème c'est que ma liste est simplement chainée
donc je ne peux pas faire des précédent lors du parcours de ma liste.

J'aimerais savoir si vous avez une idée du codage à faire pour
faire ça. Je dois élaborer cette procédure en C/C++ (c'est à la fac il
l'appelle comme ça, il font un mélange des deux langages, moi-même je
n'ai pas compris pourquoi ^^).

Le prototype que je lui ai mis est le suivant :

     - Void Tri_Insertion_Liste(Liste &l, int Taille);

Merci de m'aider car je ne sais pas trop comment faire là-dessus.

Cordialement, Shinohinata

coucou747 · Answer

salut

dans une liste chainee, la taille est sans importance.

le tri par insertion se fait comme ca :

 Liste * inser_sort(Liste *l){
  Liste *li = NULL;
  while (l != NULL){
     li = inserrer(l->item, li);
     l = l->next;
  }
  return li;
}

il reste a coder la fonction d'insertion.

ichigoZ710 · Answer

la fonction d'insertion ne sera pas à coder à part dans mon cas c'est un des impératifs. Tout doit se résumer en une seule procédure. Donc il faudra que je puisse remplacer le :
li  = insérer(li->item, li); par autre chose enfin par le code de cette fonction.

Si je suppose bien il ne doit pas être bien long.
La fonction insérer doit juste insérer si je ne m'abuse pour ce qui est du tri c'est la présente boucle qui s'en occupe.
Si ce n'est pas le cas je vais devoir prendre l'élément courant de la liste l puis le comparer à tout les éléments de cette même liste pour voir si il y en a un plus petit et si c'est le cas les 2 éléments s'inverse et ce pour chaque élément de la liste jusqu'à avoir tout parcouru ?

J'aime pas ce tri par insertion il m'embrouille -_-

coucou747 · Answer

l'insertion c'est une simple boucle...

Tri par insertion sur listes simplement chainées

3 réponses

Votre réponse

Discussions similaires