Tri par insertion sur liste simplement chainée [Résolu]
Signaler
Jordy89
cs_amar901130
- Messages postés
- 4
- Date d'inscription
- jeudi 3 janvier 2008
- Statut
- Membre
- Dernière intervention
- 4 janvier 2008
cs_amar901130
- Messages postés
- 1
- Date d'inscription
- dimanche 14 septembre 2008
- Statut
- Membre
- Dernière intervention
- 27 avril 2009
A voir également:
- Tri par insertion liste chainée en c
- Tri par insertion python - Meilleures réponses
- Trier une liste chainée en c - Meilleures réponses
- Tri par insertion sur listes simplement chainées - Forum - C
- [LangageC]Tri d'une liste chainée d'entiers. - Forum - C / C++ / C++.NET
- [C] insertion en fin de liste chainée - Forum - C / C++ / C++.NET
- C / C++ / C++.NET : Gestion d'agenda : listes chainées, malloc, free, tri... (c) - CodeS Sou - Guide
- Liste chainee de nombre trie - Codes sources - C / C++ / C++.NET (Chaînes de caractères)
8 réponses
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
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
cs_amar901130
- Messages postés
- 1
- Date d'inscription
- dimanche 14 septembre 2008
- Statut
- Membre
- Dernière intervention
- 27 avril 2009
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!
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!
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
_____________________________________
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
_____________________________________
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
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
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 ?
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 ?
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é ?
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
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