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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| package ListeChainee;
import java.util.Random;
/**
*
* @author yotta
*/
public class Main {
static int min = 1, max = 99;
static Fibo2 listeTriee = null;
static Random calc = new Random();
public static void main(String args[]) {
// Fabrication d'une liste chaînée de 10 éléments Fibo2.
Fibo2 test = fabriqueListeChainee(10);
// Affichage sous forme de liste du chaînage
afficheListeChainnee(test);
// Tri du chaînage par ordre croissant selon la technique "du plus petit".
Fibo2 testTrie = triFinal(test);
// Affiche sous forme de liste le chaînage résultant du tri.
afficheListeChainnee(testTrie);
}
static Fibo2 getLstChaine() {
// Renvoie un Fibo2 avec une valeur aléatoire pour sa propriété data comprise entre 1 et 99.
Fibo2 lst = new Fibo2();
lst.data = calc.nextInt(max - min + 1) + min;
return lst;
}
static Fibo2 fabriqueListeChainee(int NbrTermes) {
// Construit une liste chaînée de NbrTermes séquentiellement.
Fibo2 premier = null;
Fibo2 memo, reponse;
reponse = getLstChaine();
for (int i = 1 ; i <= NbrTermes-1 ; i++) {
memo = premier;
premier = getLstChaine();
if (memo != null) memo.jepointevers = premier;
else reponse.jepointevers = premier;
}
return reponse;
}
@SuppressWarnings("UnusedAssignment")
static Fibo2 trouvePlusPetit(Fibo2 aTrier) {
// Ici, on extrait le premier Fibo2 trouvé possédant la plus petite valeur data et on le soustrait de la liste chaînée pour le renvoyer avec un suivant null.
Fibo2 cible;
Fibo2 suivant, precedent = null, memoPrecedent = null;
cible = aTrier;
suivant = cible.jepointevers;
if (cible.jepointevers != null) precedent = cible;
while (suivant != null) {
if (suivant.data < cible.data) {
// Changement de cible car on a trouvé un élément avec un data plus petit.
cible = suivant;
// On mémorise son précédent pour modifier son chaînage, ce qui revient à dire, le retirer de la liste chaînée.
memoPrecedent = precedent;
}
// suivant devient le précédent avant le glissement.
precedent = suivant;
// Glissement du 'pointeur' de notre liste chaînée.
suivant = suivant.jepointevers;
}
if (memoPrecedent != null) {
memoPrecedent.jepointevers = cible.jepointevers;
cible.jepointevers = null;
}
// Dans le cas particulier où le plus petit élément est le premier, il faut faire glisser notre 'pointeur' de liste chaînée principale pour occulter le premier.
else aTrier = aTrier.jepointevers;
return cible;
}
static void afficheListeChainnee(Fibo2 lst) {
Fibo2 valTmp = lst;
System.out.println(valTmp.data);
while (valTmp.jepointevers != null) {
valTmp = valTmp.jepointevers;
System.out.println(valTmp.data);
}
System.out.println();
}
static Fibo2 triFinal(Fibo2 org) {
Fibo2 valTmp;
Fibo2 memoListeTriee = null;
while (org.jepointevers != null) {
valTmp = trouvePlusPetit(org);
// Ici, j'utilise la propriété suivant de valTmp comme d'un boolean pour savoir si le plus petit renvoyé serait par hasard le premier de la liste.
// Tel que si valTmp.jepointevers est null, ce n'est pas le premier, mais si valTmp.jepointevers n'est pas null, alors il l'est.
if (valTmp.jepointevers != null) {
// Cas où valTmp, le plus petit, représente aussi le premier de la liste.
// Puisqu'il s'agit du premier élément, il suffit de faire glisser org sur son deuxième élément, puis de mettre suivant de son premier élément à null pour l'occulter complètement de la liste chapinée d'origine.
org = org.jepointevers;
valTmp.jepointevers = null;
}
if (listeTriee == null) {
// Si listeTriee est null, c'est que nous sommes sur le premier élément de notre liste triée.
// Il est alors impératif de mémoriser ce dernier dans une autre classe, car nous allons le faire glisser tout au long de son remplissage.
listeTriee = valTmp;
memoListeTriee = listeTriee;
}
else {
// listeTriee existe, on se contente de remplir.
listeTriee.jepointevers = valTmp;
listeTriee = listeTriee.jepointevers;
}
}
// En sortie de boucle, il ne reste naturellement dans org que le dernier élément qu'il suffit d'ajouter à la fin de notre liste triée en ayant pris soin de mettre son suivant à null.
listeTriee.jepointevers = org;
return memoListeTriee;
}
} |
trier une liste chaîné simple
Répondre avec citation
La plupart des réponses à vos questions sont déjà dans les 
Envoyé par yotta
Partager