Tri par insertion sur liste simplement chainée [Résolu]

Jordy89
Messages postés
4
Date d'inscription
jeudi 3 janvier 2008
Dernière intervention
4 janvier 2008
- 3 janv. 2008 à 17:00 - Dernière réponse : cs_amar901130
Messages postés
1
Date d'inscription
dimanche 14 septembre 2008
Dernière intervention
27 avril 2009
- 27 avril 2009 à 19:08
Bonjour,

Dans le cadre de la manipulation d'une liste chaînée, je suis amené à effectuer un tri; Je me suis renseigné à gauche et à droite, et il apparait que le tri par insertion serait particulièrement bien adapté.

Cependant, je n'arrive pas à mettre au point l'algorithme réalisant ce tri !
J'ai déjà effectué des tris par insertion sur des vecteurs, et ça ne pose aucun problème.

Quelqu'un pourrait-il m'aider ?

Merci
Afficher la suite 

Votre réponse

8 réponses

Meilleure réponse
acx01b
Messages postés
281
Date d'inscription
dimanche 7 septembre 2003
Dernière intervention
8 juillet 2014
- 4 janv. 2008 à 10:42
3
Merci
salut

créer une liste chainée se fait en 2 temps (enfin tu peux faire les 2 en même temps aussi)

allouer de la mémoire ou simplement créer les noeuds, puis les connecter ensembles

dans ton cas tu as les noeuds qui sont déja créés suffit de les connecter ensemble

liste trier_liste(liste l) {
  liste liste_tree = NULL;
  while(l) {
    element *e = l;
    l = l->suivant;
    liste_triee = inserer_element(liste_triee, e);
  }
  return liste_triee;
}

tu considères simplement ta liste non triée comme une liste d'éléments à insérer successivement au bon endroit dans la liste vide

c'est pour ça que la fonction trier_liste se résume en fait à inserer_element (le reste est trivial)
si tu comprends pas dis moi

Merci acx01b 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 94 internautes ce mois-ci

Commenter la réponse de acx01b
cs_amar901130
Messages postés
1
Date d'inscription
dimanche 14 septembre 2008
Dernière intervention
27 avril 2009
- 27 avril 2009 à 19:08
1
Merci
Bonjour,
voici une réponse détallée sur le Tri par insertion sur liste simplement chainée

#include
using namespace std;

struct boite{
    char val;
    boite* lien;};
typedef boite* liste;
/*************************************/
void creliste(liste &l){
    l=0;
}
/********************************************/
bool appartient(liste l,char x){
    if(!l) return false;
    else
        if(l->val==x) return true;
        else
            if(l->val>x) return false;
            else return appartient(l->lien,x);
}
/****************************************/
void ajouter_trier(liste &l, char x){
    if(!appartient(l,x)){
        liste aux=new boite;
        aux->val=x;
        if(l==0) { l=aux; aux->lien=0; }
        else
        if(l->val>x) { aux->lien=l; l=aux; }
        else {
            liste prec=l;
            bool fini=false;
            while(!fini){
                if(prec->lien==0) fini=true;
                else
                if(prec->lien->val>x) fini=true;
                else prec=prec->lien;
            }
            //inserer aux aprés prec
            aux->lien=prec->lien;
            prec->lien=aux;
        }
    }
}
/*********************************/
void detruire(liste &l){
    while(l){
    liste aux=l;
    aux = l;
    l= l->lien;
    delete aux;
    }
}
/**********************************/
void trie(liste &l){
liste liste_vide_a_remplir=0; // on cree notre liste vide a remplir
    liste aux=l;             // aux est le pointeur qui va parcourir la liste non triee
    while(aux!=0){
        ajouter_trier(liste_vide_a_remplir,aux->val);// on ajoute en ordre dans liste_vide_a_remplir
        aux=aux->lien;
    }
    liste ptr=l;
    l=liste_vide_a_remplir;
    detruire(ptr); // on detruit ptr pour effacer la liste non triee
}
/************************************/
void affiche(liste l){
    while(l){
        cout<<l->val<<" ";
        l=l->lien;
        }
        cout<<endl;
        }
/*********************************/
void ajouter_debut(liste &l, char x){
    liste aux=new boite;
    aux->val=x;
    aux->lien=l;
    l=aux;
}
/********************************/
int main(){
liste maliste;
creliste(maliste);
ajouter_debut(maliste,'C');
ajouter_debut(maliste,'B');
ajouter_debut(maliste,'A');
ajouter_debut(maliste,'E');
affiche(maliste);
trie(maliste);
affiche(maliste);
return 0;
}
test OK!
Commenter la réponse de cs_amar901130
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Dernière intervention
22 août 2010
- 3 janv. 2008 à 22:06
0
Merci
e étant l'élément à insérer au bon endroit dans ta liste.
Tu cherches e1 et e2 tels que e1 <= e et e <= e2 (comme tu le fais avec des vecteurs).
La seule chose qui change est la déplacement de l'élément. Si je n'oublies rien, ca doit donner ca:

e.précédent.suivant = e.suivant
e.suivant.precedent = e.precedent
e1.suivant = e
e2.precedent = e
e.precedent =e1
e.suivant = e2

Ceci est pour une liste chainée dans les deux sens

_____________________________________
Commenter la réponse de vecchio56
acx01b
Messages postés
281
Date d'inscription
dimanche 7 septembre 2003
Dernière intervention
8 juillet 2014
- 4 janv. 2008 à 08:53
0
Merci
salut

typedef struct element {
  struct element *suivant;
   ...
} element, *liste;

en général le prototype de la fonction inserer_element

ça sera

void inserer_element(liste *l, element e);

ou bien

liste inserer_element(liste l, element e);

en effet l'élément peu être rajouté au début de la liste et dans ce cas la liste change d'adresse, il faut donc que inserer_element puisse modifier l'adresse de la liste
Commenter la réponse de acx01b
Jordy89
Messages postés
4
Date d'inscription
jeudi 3 janvier 2008
Dernière intervention
4 janvier 2008
- 4 janv. 2008 à 09:53
0
Merci
Dans mon cas, tous les éléments sont déjà présents dans la liste. Il ne s'agit pas d'effectuer une insertion dans une liste triée, mais de trier une liste chainée d'élément.
Ca revient au même ?
On considère chaque élément et on modifie son pointeur afin de réordonner la totalité de la liste ?
Commenter la réponse de Jordy89
Jordy89
Messages postés
4
Date d'inscription
jeudi 3 janvier 2008
Dernière intervention
4 janvier 2008
- 4 janv. 2008 à 09:57
0
Merci
Ou alors on considère chaque élément, on recherche sa place définitive dans la liste, on le supprime de son ancienne place et on insère un nouvel élément à la bonne place avec l'information de celui qu'on a supprimé ?
Commenter la réponse de Jordy89
Jordy89
Messages postés
4
Date d'inscription
jeudi 3 janvier 2008
Dernière intervention
4 janvier 2008
- 4 janv. 2008 à 13:40
0
Merci
Nickel, ça marche ! Merci beaucoup !
Commenter la réponse de Jordy89
mohboa
Messages postés
9
Date d'inscription
dimanche 2 mars 2008
Dernière intervention
25 novembre 2008
- 20 nov. 2008 à 01:59
0
Merci
j'ai l'algo de trie par insertion vous pouvez convertir en c ou c++  c'est facile
voila mon programe :

procedure
triInsertion( t: tab en entrée sortie )Algorithme

debut

variable
 

i, j, mem: entier

pour
 i de
1 j N-1 faire
/* sélection de l’élément à insérer*/                mem <- t[ i ]

                j <- i

tant que
 

j>0  
et
 t[j-1]>mem   
repeter
/* décalage des éléments plus grands */         t[ j ] <- t[ j-1 ]

          j <- j - 1

fin tant que

        t[ j ] <- mem /* insertion */

fin pour;

fin ;

       merci
Commenter la réponse de mohboa

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.