Salut,

Pour mon projet, on m'a demandé de créer une fonction tri d'une liste doublement chainée issue d'un fichier txt contenant dans chaque ligne des descripteurs d'une image (prix, titre, source...).
La fonction tri doit être en fonction de prix.
Quelqu'un peut me donner un prototype de la fonction tri pour une liste doublement chainée, car je suis vraiment bloqué.

Merci d'avance.

Salut,

La liste chainée ne pouvant pas être accesible en randomaccess, adieu le quicksort.

Mais tu as d'autres algorithmes pour ça, comme le tri par insertion.
http://fr.wikipedia.org/wiki/Tri_par_i [...] ur_des_listes

Quant au critère sur lequel tu veux trier, peu importe : tu auras une fonction de comparaison qui prendra 2 noeuds, a toi de dire si l'un est plus grand que l'autre. ici, et seulement ici, tu mettras qu'il faut considérer le prix.

un tri par insertion avec une liste chainé !!!!!

Déjà le tri par insertion est déjà pas en pire cas en O(nlogn) mais je te dis pas les accès mémoire...

Heureusement, il existe un tri qui est en O(nlogn) et adapté au listes chainés (simplement lié en plus), il s'agit du tri fusion.

L'implémentation peut être un peu laide parfois car on peut s'amuser à trimballer un pointeur de pointeur pour ne pas avoir à cherche le milieu de la liste et l'obtenir implicitement, mais bon

Citation : galopin_

un tri par insertion avec une liste chainé !!!!!

Déjà le tri par insertion est déjà pas en pire cas en O(nlogn) mais je te dis pas les accès mémoire...

Heureusement, il existe un tri qui est en O(nlogn) et adapté au listes chainés (simplement lié en plus), il s'agit du tri fusion.

L'implémentation peut être un peu laide parfois car on peut s'amuser à trimballer un pointeur de pointeur pour ne pas avoir à cherche le milieu de la liste et l'obtenir implicitement, mais bon

En même temps, si on veut un conteneur trié, la liste n'est pas le meilleur choix...

Citation : int21h

Citation : galopin_

un tri par insertion avec une liste chainé !!!!!

Déjà le tri par insertion est déjà pas en pire cas en O(nlogn) mais je te dis pas les accès mémoire...

Heureusement, il existe un tri qui est en O(nlogn) et adapté au listes chainés (simplement lié en plus), il s'agit du tri fusion.

L'implémentation peut être un peu laide parfois car on peut s'amuser à trimballer un pointeur de pointeur pour ne pas avoir à cherche le milieu de la liste et l'obtenir implicitement, mais bon

En même temps, si on veut un conteneur trié, la liste n'est pas le meilleur choix...

Ou alors, il faut qu'elle soit constamment triée Si quand on insère le nième élément dans sa position triée, les n-1 précédents sont triés, alors la liste est triée

J'ai programmé une fonction de tri pour ma liste, mais j'ai eu une résultat bizarre.
Par exemple j'ai 5 valeurs a trier:
2
7
4
5
3

et la fonction tri comme ça:
0
2
3
4

Voila le code si quelqu'un peut me dire ce ça marche pas:

void Tri_liste(Element** Entete)

{
Element *courant;
courant=*Entete;
    if (courant->suivant==NULL)
    return;
    Element *ptr,*tmp;
    courant=courant->suivant;
    while(courant!=NULL)
    {
    ptr=courant;
    tmp=courant->precedent;
    courant=courant->suivant;
    while (tmp!=NULL && tmp->prix>ptr->prix)
    {
    tmp=tmp->precedent;
    }
    ptr->precedent->suivant=ptr->suivant;
    if (ptr->suivant!=NULL)
    ptr->suivant->precedent=ptr->precedent;
    if (tmp==NULL)
    {
    tmp=*Entete;
    ptr->precedent=NULL;
    ptr->suivant=tmp;
    ptr->suivant->precedent=ptr;
    *Entete=ptr;
    }
    else
    {
    tmp=tmp->suivant;
    tmp->precedent->suivant=ptr;
    ptr->precedent=tmp->precedent;
    tmp->precedent=ptr;
    ptr->suivant=tmp;
}
}
}

Slt!!!, aidez moi a trouvé la solution de ce problème: Ecrire une fonction CreerListesClients, qui creer une file de clients, le nombre de clients etant saisi au clavier. Cette fonction initialise aussi la date d'arrivée et la durée d'attente de chacun des clients. On supposera que le premier client est arrivé a h

Ça c'est du déterrage!

Petit problème, tu t'es trompé de site, ici on n'est pas sur www.faismesdevoirs.com. On peut expliquer des choses, orienter vers des solutions, mais il faut pour cela qu'on sache ce que tu as déjà fait. D'ailleurs tout indique qu'il s'agit d'un exercice d'application d'un cours, donc si tu as bossé le cours en question, tu es censé être capable de faire l'exercice.

Bonjour,

Déterrage

Citation des règles générales du forum :

Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.

Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre.
En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.

Au lieu de déterrer un sujet il est préférable :

• soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
• soit de créer un nouveau sujet décrivant votre propre contexte
• ne pas répondre à un déterrage et le signaler à la modération

Je ferme ce sujet. Me contacter par MP si besoin.