Bonjour,

Toujours dans mon enorme tp sur les listes (derniere question ), j'ai un probleme pour le tri rapide (quicksort).
On a un pseudo algo :
Pour le tri rapide :
Le tri rapide avec les listes utilise les fonctions void extraire_element
(qui extrait un element) et void concat qui concatène deux listes
(fonctions définies en Q5 et Q7).
si la liste n'est pas réduite à un el ou vide :
- prendre comme pivot le premier elmnt de la liste (c'est plus
adapté pour la liste où on a directement accès au premier élément).
- créér deux listes liste_inf et liste_sup contenant respectivement
les élémnts inférieurs et supéreurs au pivot. Pour ce faire on parcourt la
liste et on extrait chaque elmnt en le ventilant ds la bonne liste.
- trier les deux sous-listes récursivement
- concaténer liste_inf, pivot , et liste_sup ( en modifiant
éntuellemnt la tete de liste).
Voila le code que j'ai pu en tiré :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* Fonction qui trie une liste avec l'algo de tri rapide */
void tri_rapide (P_un_element *liste)
{
    P_un_element pivot, tete, liste_inf, liste_sup;
    if ( *liste && ((*liste)->suiv) )
    {
        pivot = *liste;
        tete = *liste;
        while ( *liste )
        {
            if ( pivot->elem_val < (*liste)->elem_val )
                inserer_element_fin(&liste_sup,rechercher_element(*liste,(*liste)->elem_val));
            else
                inserer_element_fin(&liste_inf,rechercher_element(*liste,(*liste)->elem_val));
            *liste = (*liste)->suiv;
        }
        *liste = tete;
        tri_rapide(&liste_sup);
        tri_rapide(&liste_inf);
        concat (liste,liste_inf);
        *liste = tete;
        concat(liste,pivot);
        *liste = tete;
        concat(liste,liste_sup);
        *liste = tete;
    }
}
Qui utilise donc les fonctions concat, inserer_element et rechercher_element ecrites plus tot :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/* fonction qui ajoute L2 dans le liste L1 */
void concat (P_un_element *l1, P_un_element l2)
{
    /* si l2 est vide, rien a faire */
    if ( !l2 )
        return;
    else
    {
        /* on ajoute l2 */
        while ( l2 )
        {
            inserer_element_fin(l1,creer_element(l2->elem_val));
            l2 = l2->suiv;
        }
    }
}
 
/* fonction retourne un certain element s'il est dans la liste */
P_un_element rechercher_element (P_un_element liste, Tval val )
{
    /*while ( liste && ( cmpval(liste->elem_val,val) != 0 ) ) */
    while ( liste && ( liste->elem_val != val ) )
    {
        liste = liste->suiv;
    }
    if ( !liste )
    {
        printf("L'element n'est pas dans la liste !\n");
        return NULL;
    }
    else
        return liste;
}
 
/* fonction qui insere un element a la fin de la liste */
void inserer_element_fin (P_un_element *liste, P_un_element el)
{
    if ( !(*liste) )
    {
        /* la liste est vide, il suffit de creer un element */
        *liste = creer_element(el->elem_val);
    }
    else
    {
        /* on garde en memoire la tete */
        P_un_element tete = *liste;
        /* on se deplace jusqu'au dernier element */
        while ( (*liste)->suiv )
            *liste = (*liste)->suiv;
        /* on insere l'element a la fin */
        (*liste)->suiv = el;
        *liste = (*liste)->suiv;
        (*liste)->suiv = NULL;
        /* on remet liste sur la tete */
        *liste = tete;
    }
}
Voila je tombe sur un segmentation fault
Mes yeux tombent par terre, j'espere que vous y verez plus clair.
Merci pour votre aide

Sorry