Bonjour à tous, j'ai besoin de votre aide pour solutionner un algo de tri par insertion en java sur listes chaînées
merci d'avance pour votre temps et votre lecture.
Code java : 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 //methode qui retourne une liste des valeurs <= e public Liste_chaînée Less_or_equals(int e){ Cellule c = tete; Liste_chaînée l = new Liste_chaînée(); while(c!=null){ if (c.valeur <= e) l.Cons(c.valeur); //cons ajoute une valeur en début de liste c = c.suivant; } return l; } //retourne une liste des valeurs > e public Liste_chaînée More_than(int e){ Cellule c = tete; Liste_chaînée l = new Liste_chaînée(); while(c!=null){ if (c.valeur > e) l.Cons(c.valeur); c = c.suivant; } return l; } //methode qui va concaténer toutes les listes crées et triées public Liste_chaînée Concatener (Liste_chaînée l1, Liste_chaînée l2){ Liste_chaînée l = new Liste_chaînée(); if(l1 != null) l = l1; if (l2 != null){ Cellule tmp = l2.tete; while (tmp !=null){ l.Snoc(tmp.valeur); tmp=tmp.suivant; } } return l; } //methode de tri rapide public Liste_chaînée Tri_rapide (){ if (tete == null || tete.suivant == null) return this; else { Liste_chaînée l1 = Less_or_equals(tete.valeur); Liste_chaînée l2 = More_than (tete.valeur); l1 = l1.Tri_rapide(); l2 = l2.Tri_rapide(); return Concatener(l1,l2); } }
l'exe :
Code java : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 System.out.println("\n\n* Tri rapide *"); Liste_chaînée l2 = new Liste_chaînée(); l2.Init(10); // crée une liste de 10 occurrences l2.Afficher(); System.out.println("\nListe triee : "); l2.Tri_rapide(); l2.Afficher();
les classes liste et cellule sont difinies comme suit :
Code java : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13 public class Cellule { public int valeur; public Cellule suivant; //constructeur Cellule(int _valeur){ valeur = _valeur; suivant = null; } }
et
Code java : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11 public class Liste_chaînée { public Cellule tete; //constructeur Liste_chaînée(){ tete = null; }
Bien j'espère avoir mis assez de détails, étant novice en algo !
Partager