trie d'une liste chainée

Version imprimable

18/02/2012, 16h10
abdelghani666

trie d'une liste chainée

bonjour
j'ai juste une question :
est ce que les tris (tri par selection , tri par insertion , tri a bulle) qui s'appliquent sur les tableaux sont valables pour les listes chainées ??
j'ai appliqué le tri par selection mais ca ne donne rien
et merci

tri par selection d'une liste chainée

bonjour
je veux trier une liste chainée et j'ai choisis le tri par selection que j'ai bien assimilé
voila le code que j'ai proposé mais ca marche pas je suis sur qu'il ya un probleme

Code:

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
58
59
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct element{
       int val ;
       struct element *next ;
       }element ;
int main(){
    element *p , *l , *s ,*m , *k , *aide  ;
 
    int i , n , max ;
    printf("entrez le nombre d'elements");
    scanf("%d",&n);
    l=(element *)malloc(sizeof(element));
    scanf("%d",&l->val);
    l->next=NULL ;
    p=l ;
    for(i=0 ; i<(n-1) ; i++)
    {
            s=(element*)malloc(sizeof(element));
            scanf("%d",&s->val);
            p->next=s ; 
            s->next=NULL ;
            p=p->next ;
            }
 
    p=l ;
    while(p->next!=NULL)
    {
 
                    p=p->next ;
 
                        }
 
                printf("\n");
 
     for(s=l ; (s!=NULL) ; s=s->next)
     {
               m=s ;
               for(k=s->next ; k!=NULL ; k=k->next)
               {
                         if((k->val)>(m->val)) m=k ;
                         }
               *aide=*m;
               *m=*s ;
               *s=*aide ;
 
               }
       p=l ;
 
 
        do
        {
            printf("%d",p->val);
            p=p->next ;
            }while(p!=NULL);
 
    getch();
}

merci d'avance

18/02/2012, 18h58
Trademark
Code:

1 2 3 4 5 6 7 p=l ; while(p->next!=NULL) { p=p->next ; }
Tu assignes p au début de la liste et tu vas à la fin alors que p était déjà à la fin...

Enfin ça c'est le détail qui prouve que t'as même pas pris la peine de relire ton code.
Pire encore, as-tu vu l'indentation du code que tu nous proposes ? C'est illisible, d'autant plus que tes noms de variable ne veulent strictement rien dire. Un code dégueulasse c'est ne pas respecter celui qui le maintiendra, mais encore pire ici, celui qui t'aidera !

Donc tu nous fait le plaisir d'éditer ton commentaire avec un code clair que tu as relu et dont tu as réfléchi à l'algorithmique sur un papier avec ton crayon et ta gomme. En plus, avec un peu de chance, tu trouveras ton erreur comme un grand (bien que tu ne nous ai pas dit pourquoi ton code ne marchait pas, encore du non-respect, on doit chercher ce qui ne marche pas).

Code:

1
2
3
4
5
6
7
8
9
10
11
12
     for(s=l ; (s!=NULL) ; s=s->next)
     {
        m=s ;
        for(k=s->next ; k!=NULL ; k=k->next)
        {
           if((k->val)>(m->val)) m=k ;
        }
        *aide=*m;
        *m=*s ;
        *s=*aide ;
 
     }

Aucun champ next n'a été modifié et la liste reste inchangée.
Attention, pour échanger la position de deux cellules, il faut ici modifier le champ next des cellules qui précèdent les cellules à déplacer.

Illustration : échanger les cellules n et p. Les champs next en rouge sont à modifier.
Avant :

  -->n-1 >--->  n >--> n+1>--...--> p-1 ---->  p >-->  p+1>-- ...

Après :

                 --------------------------------------
                |        ---------------------         |
                |       |                     |        |
                ^       v                     ^        v
  -->n-1        n      n+1>-- ...-->p-1       p       p+1>-- ...
       v        ^                   v         ^
       |        |                   |         |
       |         -------------------          |
        --------------------------------------