Bonjour,  
 
ca fait des jours que j'essaie de trouver une solution, mais c'est trop pour moi j'y arrive pas :'( ...
 
voila j'ai une liste chainees avec des maillons de ce type :  
 

 
non triée biensur,  
 
Si qqun pouvais m'aider a faire un algo pour trié cette sdfsdffsd de liste chainee par ordre de nom ascendant ca serait super cool, parce qeu la je m'emmele les pinceau et je dois remettre mon projet cette semaine    
 
Merci d'avance pour votre aide

bin tu peux faire un tri à bulle (version avec sélection ou je sais plus comment), du style:
 
pour i du premier à l'avant dernier
 
  m <- rien de mieux
 
  pour j du suivant de i au dernier
      si j est "<" à i
        m <- j
      fin si
  fin pour
 
  si m n'est pas "rien de mieux"
    injecter m avant i
  fin si
 
fin pour
 
voilà, démerdes toa avec ça

 
Salut,  
 
mais dans ma liste chainée, il n'y a pas d'indice, dois-je tout remettre dans un tableau normal avant de proceder au tri a bulle??  
 
aussi j'ai pas compris ce que signifie le "rien de mieux"    
 
merci

spa plus simple d'utiliser qsort ?

 
J'avais trouvé cette fonction qsort, mais je dois avouer que j'ai rien capté a son utilisation :'(
y a moyen de trier DIRECTEMENT une liste chainées du type que je viens de donné avec ca?  
 
Le principe serait d'echanger les adresse de pSuivant et pPrecedent de la structure pour trier la liste chainee...  
 

 
i peut être un pointeur

je sais plus si ça marche avec les listes chaînées en fait... ça date d'y a longtemps pour moi ces trucs-là

qsort ça implique un tableau d'objets (linéaire)

 
ok mais je vois vraiment pasdu tout comment faire....

bin j'ai déjà fait 40% de ton taf....

bon aide:
 
les "pour" se traduiront certainement en parcours via le "suivant" de chaque élément de la liste chainée.
 
beaucoup de variables seront des pointeurs.
 
l'injection aura ptet des cas particulier à prendre en compte.

Ben déjà tu fais une fonction magique qui gère l'inversion de deux maillons de ta liste. Simplement en lui filant en paramètre les deux adresses. Vu que ta liste est doublement chaînée c'est nickel y'a rien d'autre à faire.
 
Ensuite tu pourras te concentrer sur le tri de ta liste ...

Dans la méthode bjone, le i et le j correspondent au rang des "enregistrements" dans la "base de données".
Y a bien un premier, un second objet entré ? puis un troisième, etc..
 
Faut appliquer son algo en mettant à jour les *pSuivant et *pPrecedent à chaque comparaison.
 
En faisant le truc avec un exemple sur une feuille de papier, ça permet de voir le principe, ensuite la machine le fera pour le fichier une fois mis au point.

 
Merci j'avais compris pour les pour, la je suis occupé a essayer de le faire en C, ùmais je n'ai pas compris comment traduire ca "m <- rien de mieux"
ca fait quoi exactement? Merci

 
Yep je commence a y voir plus clair, mais chui pas encore sur du tout de ce que je fais, quand j'aurai fait l'algo je le posterai ( je suppose kil foirera au premier coup )  
 

en fait:
 
faire les échanges d'éléments via les pointeurs  
suivant/précédent à chaque fois c'est du pure tri à bulle (ou à plomb )
 
mais si tu maintiens l'élement qui est plus "petit" (ou plus "grand" ), tu as juste à balayer tous les éléments suivant le courant, et faire un échange d'élements à la fin une fois que tu sais kicékiestmieuxplacé, c'est du tri par sélection/insertion (en principe plus rapide).
 
en gros ce que j'ai donné c'est:
 
pour chaque élement sauf le dernier
     pour chaque élement à partir du "suivant du courant"
          si l'élement il me plait mieux je le "mémorise"
     fin pour
     
     si il y a un élément qui me plait mieux
          je le DEPLACE devant le  courant
     fin si
fin pour

peux pas faire plus simple.

a oui en fait y'aura un problème
 
dans le:
 
si il y a un élément qui me plait mieux  
    je le DEPLACE devant le courant  
fin si  
 
faut faire attention à repartir du courant (et pas du meilleur élément déplacé ou du suivant du courant ) à la prochaine itération générale.

Si j'ai bien capté, ton M c'est le courant c ca?

 
cad?    

dans le truc initial:
 
i -> le courant
j -> permet de balayer du suivant du courant au dernier
m -> élément à insérer devant i

honte à moi, le vilain bug que je te fait faire:
 
pour i du premier à l'avant dernier  
 
 m <- i
 
 pour j du suivant de i au dernier  
     si j est "<" à m  
       m <- j  
     fin si  
 fin pour  
 
 si m est différent de i
   injecter m avant i  
 fin si  
 
fin pour  

 
lol s'pas grave,  
 
bon je v essayer avec ca... des que c fini je poste mon code
tkx

Bon voila ce que donne le code de ma fonction mais comme prevu ca foire   , j'ai du loupé qque chose, en fait quand j'affiche ma liste chainee apres ca, non seulement c pas trié mais en plus il manque plein de maillon ... qu'est ce qeu j'ai encore foutu moi...  
 
 

bon jai corrigé ce qu'il y avait dans la derniere conditrion c t pas bon, mais ca marche tjrs pas  
 

Mon code vous fait peur? Zetes tous parti? :'(  
 
help plz m'en sort plus je test pas a pas mon code avec des printf partout, je vois pas ce qui cloche si la logique est bonne
 
 

alors dans le while, il faut:
 
while( pI->pSuivant != NULL && pI->pSuivant->pSuivant!=NULL )
 
qui est équivalent à:
 
while( pI->pSuivant && pI->pSuivant->pSuivant )
 
et encore par sécurité:
 
while( pI && pI->psuivant....
 
ça protège des bugs plus bas, et ça protège du cas ou il y a q'un seul élément....
 
pour le if:
 
if(strcmp(pMem, pI)!=0)
            {
                 pI->pSuivant=pMem->pSuivant;
                 pMem->pSuivant=pI;
         
}
 
vo mieux:
 
if( pMem != pI )
{
   
}
 
ensuite ton insertion est "fausse"
 
ton insertion doit faire:
 
// meilleur devant courant
courant->précédent->suivant = meilleur
courant->précédent = meilleur
 
// on "enlève" meilleur
meilleur->précédent->suivant = meilleur->suivant
meilleur->suivant->précédent = meilleur->précédent
 
// meilleur devant courant (suite)
meilleur->suivant=courant
 
et ceci doit gérer les cas spéciaux:
 
insetion devant le premier élément où le pointeur précédent est à NULL ( modifer le pointeur "racine" )
 
cas ou le meilleur est le dernier élément où le pointeur suivant est à NULL (sinon crash)

et comme tu fais un courant=courant->suivant en fin de while
 
dans le if en cas d'insertion, il faut à la fin faire courant=meilleur, comme ça le courant pris au prochain coup sera le MEME que celui de ce tour là, et si il y a encore des élements mieux placés il seront insérés devant.
 

Bon voila j'ai fais ce que tu as dis, enfin je crois :  
 

 
maintenant a TOUT les coup il manques un enregistrement.... c'est deja mieux, mais ca trie encore n'importe comment.
 
j'ai essaié de mettre pI=pMem; a la place de pI=pI->pSuivant; mais alrso il boucle a l'infini...  
 
désolé de t'ennuyé encore mais chui un peu largué la... stressé, car c'est la seule fonction de mon prog ki marche pas encore , et je dois remettre le projet demain
 
gros stress :'(
 
thkx

Algorithme de tri en O(n log n) pour les listes chaînées :
 
http://www.chiark.greenend.org.uk/ [...] tsort.html
 
Avec du code en C.
 
PS: Vive

 
Je v voir ca merci, puis, j'ai passé des heures sans trouver sur google... avec les criteres "tri de liste chainee" "langage C"
et rien
 
edit: un rien complexe a comprendre leur exemple

dans mon dernier code tu vois qque chose qui cloche    
chai plus quoi faire pour ke ca marche :'(

Il faut savoir parler anglais parfois. Je l'ai trouvé en tapant "sort linked list".

Si tu veux une solution simple ... une liste chaînée n'est qu'un container de données. Le container le plus simple à trier est le tableau - tu vas donc ranger tous les pointeurs de ta liste chaînée dans un tableau de DATA* temporaire. Ensuite, un qsort() sur ce tableau, puis recréation de la liste chaînée (simple parcours du tableau qui met pointeur suivant = case suivante, etc).
 
la fonction à passer à qsort va te filer deux pointeurs void* (en fait des pointeurs vers tes DATA*)
 
void fn(void* d1, void* d2)
 
tu n'as qu'à les caster puis faire ta comparaison dessus :
 
return strcmp((DATA*)d1->nom, (DATA*)d2->nom);

 
bon j'ai commencé mais je suis deja bloqué
 

 
j'parie que chui a coté de la plaque completement...

void TriNom(struct DATA *LC_result)
{
 struct DATA *pMem, *pTmp, *pI, *pJ;
   struct *DATA TabDATA[];
   int i=0;
/*
  manque l'allocation du tableau ...
*/
 
 while(pI->pSuivant!=NULL)
 {
    TabDATA[i++]=pI;
 }
 
/*
  regarde l'aide de qsort (ou google). il faut un tableau, donc ici TabData, le nombre de ses éléments, la taille d'un élément (ici sizeof(DATA*)), puis la fonction de comparaison (regarde l'aide, compile un exemple et debugge-le pour voir comment la fonction est appelée).
*/
 qsort(*base, i, malloc(sizeof(struct DATA)), fn(/* que mettre ici*/));
}
 
/*
  manque la mise à jour des pointeurs. le quicksort a 'trié les pointeurs' vers les éléments de ta liste, suffit de parcourir le tableau et de faire TabData[i].pSuivant = TabData[i+1], etc. et faire gaffe aux valeurs de i.
 
donc le premier élément de ta liste sera TabData[0].
*/
 
/*
  pareil, regarde l'aide. maîtriser qsort() & ses mécanismes est indispensable.
*/
void fn(void* d1, void* d2)
{
 return strcmp((DATA*)d1->nom, (DATA*)d2->nom);
}

boh j'essayais de le mettre sur la voie

 
bjone, qu'est ce qui cloche alors dans ce que j'ai fait??  
 
capte pas  
 
merci

v devenir singléééé  

si tu détaillais un peu les endroits où tu es bloqué ... j'ai mis tout ce que tu avais à corriger dans mon post précédent. le code final ne devrait pas prendre plus d'une trentaine de lignes.
 
et quand je dis de recopier & debugger les exemples qsort() & co, c'est pas pour faire joli, c'est crucial. cf l'exemple dans la msdn : http://msdn.microsoft.com/library/ [...] _qsort.asp  
 
si tu veux comprendre l'algo, http://www.google.com/search?q=quicksort+explained . ce n'est pas indispensable pour son utilisation.