Discussion :

[zozo77]

Bonsoir !
Je bloque depuis une semaine sur un problème : je cherche à trier dans l'ordre croissant une liste chainée, en PHP.
En gros mon but est de passer d'un tableau non trié à une liste triée.
J'ai utilisé pour ça les fonctions, mais au final je me retrouve avec pleins de fonctions, un programme assez long... et un programme qui ne marche pas (je ne sais pas pourquoi).
J'espère que vous pourrez m'aider, ou au moins m’éclairer, merci

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
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
<?php 
 
function liste()
{
echo "creation 10 éléments <BR>";
$pTete=new element();
$i=0;
$tab= array (6,2,95,5,8547,154,157,98);
$cpt=count($tab)-1;
$pTete->valeur= $tab[$i];
$pPrec=$pTete;
do
{
$i++;
$pEncours=new element();
$pEncours->valeur=$tab[$i];
if ($pEncours<$pPrec){
ajout_element($tab[$i-1], $tab[$i],$pTete );
}
if ($pEncours>$pPrec){
$pPrec->pSuiv=$pEncours;
$pPrec=$pEncours;}
}
while($i<$cpt);
$pPrec->pSuiv=null;
return $pTete;
}
 
 
function parcours_liste($pTete)
{ echo "parcours <BR>";
$pEncours=$pTete;
    while ($pEncours != null)
    {
        echo $pEncours->valeur . "<BR>";
        $pEncours = $pEncours->pSuiv;  
    }
 
}
 
 
 
 
function recherche_liste($val, $pTete)
{ echo "recherche <BR>";  
$pPrec = null;
$pEncours = $pTete;
 
while ($pEncours != null && $pEncours->valeur != $val)
{
    $pPrec=$pEncours;
 $pEncours = $pEncours->pSuiv;}
return $pPrec;
}
 
function ajout_element($vrech, $nouveau,$pTete )
{
$pPrec=null;
$pEncours=null;
 
$pNouveau =new element;
$pNouveau->valeur = $nouveau;
 
$pPrec=recherche_liste($vrech,$pTete);
 
//Si $pEncours != null, on va insérer l'élément juste avant $pEncours
//Si $pPrec= null, c'est que l'élément doit être inséré en tête
 
if($pPrec!=null ) {$pEncours=$pPrec->pSuiv;}
if ($pPrec==null) $pTete=ajout_debut($pNouveau,$pTete);
else ajout_milieu($pNouveau,$pPrec,$pEncours);
 
return $pTete;
}
function ajout_milieu($pNouveau, $pPrec, $pEncours)
{
    $pPrec->pSuiv = $pNouveau;
    $pNouveau->pSuiv= $pEncours;
}
 
function ajout_debut($pNouveau, $pTete)
{
$pNouveau->pSuiv = $pTete;
$pTete = $pNouveau;
return $pTete;
}
 
 
?>

[kevin254kl]

Bonjour,

Voici sur github https://github.com/Doc999tor/Sorted-LinkedList-PHP un script qui fonctionne.
(Ne pas réinventer la roue)

[zozo77]

Merci, mais pour le coup ça ne marche pas du tout...
Les données ne semblent pas s'enregistrer comme une liste & quand bien même ce n'est pas trié par ordre croissant

[CosmoKnacki]

Où est le code de ta classe element? Montre le.
S'agit-il d'une liste simplement chaînée ou doublement chaînée?

[zozo77]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
class element {
public $valeur;
public $pSuiv=null;
}

Du coup simplement chainée

[CosmoKnacki]

Quelle méthode de tri comptes-tu utiliser?

Et aussi pour que tout soit totalement clair, dois-tu trier une liste chaînée (c'est à dire partir d'une liste chaînée dans le désordre puis en effectuer le tri), ou dois-tu constituer une liste chaînée directement ordonnée à partir d'un tableau (donc sans passer par le stade liste chaînée désordonnée)?