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)?

[zozo77]

Je pensais utiliser le tri par insertion c'est la méthode avec laquelle je suis le plus familier.
Mon énoncé est celui-ci : "Ecrire un programme qui transforme un tableau d’entiers non trié en une liste d’entiers triés."
Je suppose donc que je peux utiliser la méthode que je souhaite, mais je voudrais trier ma liste en même temps que je la créé.

Sinon, comme je n'arrive pas à le faire j'avais pensé à trier mon tableau, puis ensuite le transformer en liste, mais je bloque également.

[CosmoKnacki]

Oui, reste à savoir ce qu'on attend vraiment de toi derrière cette question, ça peut être l'un comme l'autre. Quoi qu'il en soit, c'est juste un prétexte pour manipuler une liste chaînée.
On va partir sur: créer une liste directement triée à partir d'un tableau. Le tri par insertion s'impose donc.

Ça nécessite deux boucles imbriquées, la première boucle sur les items du tableau et la seconde sur les éléments de la liste. L'idée est que la seconde boucle doit s'interrompre à deux conditions:

• soit elle a atteint la fin de la liste.
• soit l'item du tableau est supérieur à la valeur de l'élément courant.

C'est juste après cette deuxième boucle que doit s'opérer l'insertion, car on a atteint la bonne position dans la liste. Bien entendu, pour pouvoir faire cette insertion, il faut garder trace de l'élément précédent car c'est sur sa propriété next (suivant) que s'effectue l'amarrage du nouvel élément dont la valeur est celle de l'item du tableau et l'élément suivant est l'élément courant.

Petite subtilité, au départ de la deuxième boucle, il n'y a pas d'élément précédent. Donc au moment de l'amarrage, il faut vérifier que celui-ci existe et, si ce n'est pas le cas, alors le nouvel élément devient la racine de la liste.

Exemple d'implémentation:

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
class Element
{
    public $value;
    public $next;
 
    public function __construct($value = null, $next = null) {
        $this->value = $value;
        $this->next = $next;
    }
}
 
class SortedList
{
    public $root;
 
    public function __construct(Array $array) {
        $this->root = null;
        $this->_buildFromArray($array);
    }
 
    protected function _buildFromArray(Array $array) {
        foreach ($array as $item) { // pour chaque item du tableau
 
            $current = $this->root; // position courante
            $previous = null; // au départ il n'y a pas d'élément précédent
 
            while ( $current && $item > $current->value ) { // on avance dans la liste tant que l'item est supérieur
                $previous = $current;
                $current = $current->next;
            }
 
            if ( $previous ) // si on est pas au début de la liste
                $previous->next = new Element($item, $current);
            else // dans le cas contraire, l'élément devient la racine
                $this->root = new Element($item, $current);
 
        }
    }
 
    public function __toString() {
        $current = $this->root;
        $string = '';
 
        while ( $current ) {
            $string .= $current->value . ' '; 
            $current = $current->next;
        }
 
        return rtrim($string);
    }
}
 
$l = new SortedList([8,1,13,14,13,8,5]);
 
echo $l;

[badaze]

@cosmoknacki

Pour moi les listes chaînées ça remonte à quelques décennies.

Dans mon souvenir la partie "suivant" contient un "pointeur" vers l'élément suivant. Or dans ton exemple, la partie suivant contient l'élément suivant qui lui même etc... (voir partie gauche de l'image) alors que je me serais attendu à voir une structure ressemblant à celle de la partie droite.

[foetus]

Dans mon souvenir la partie "suivant" contient un "pointeur" vers l'élément suivant.

Effectivement , l'esprit de la liste chainée c'est le pointeur, qui permet, contrairement à une structure contiguë (comme un tableau), de casser la chaîne et/ ou de rechaîner à loisir.
Et donc ceci évite de devoir déplacer des blocs pour libérer ou supprimer une case vide ... au prix d'un pointeur par élément (4 ou 8 octets) et d'un accès élément qui n'est plus direct.

[CosmoKnacki]

@badaze

Pour moi aussi, les listes chaînées sont un lointain souvenir (de l'époque où je faisais du C sur un machine de récup cadencée a 20Mhz), et j'ai du me replonger dedans pour répondre à cette question. Mais la partie gauche de ton image est bien ce qui est attendu pour une liste chaînée. Bien sûr, en dehors du cadre d'un exercice il y a dix mille façons de résoudre un simple problème de tri de valeurs, mais là, la structure est imposée. Donc pas question d'utiliser des tableaux: il faut jouer avec les passages par référence de PHP.

Cette structure imbriquée est donc parfaitement normale. Ta partie de droite n'est en aucun cas une liste chaînée (autant que ça puisse avoir un sens en PHP): c'est un tableau d'objets où de plus, il n'y a pas de lien entre les items.

[Sparky95]

bonjour,
Sauf erreur de ma part il me semblait qu'il n'y à pas de pointeurs en PHP contrairement au C,...
Il faudrait donc comme dit au dessus passer par 2 boucles et au lieu d'utiliser un pointeur utiliser un attribue id à chacun de tes éléments
avant de commencer ton tri
bonne année

[ekieki]

D'abord, on ne te demande pas de trier une liste chainée construite à partir d'un tableau, mais de créer une liste ordonnée à partir des valeurs d'un tableau. Ce n'est pas pareil. Il suffit (1) de créer une liste vide, et d'y insérer les élements un par un.

Ensuite, tu te compliques énormément la vie. Une des causes de cette complication, c'est que tu confonds la notion de _liste_ avec celle de référence à un élément. Pour partir sur des bases saines, on définit un type _liste_:

Code :

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

1
2
3
4
5
6
7
8
class Element {
    public $valeur;
    public $pSuiv = null;
}
 
class Liste {
    public $premier = null;    // référence du premier, ou null
}

Ensuite, la répartition du travail entre les fonctions. Ta fonction liste() doit retourner une liste ordonnée fabriquée à partir des valeurs prises dans un tableau. C'est pas à elle de fabriquer les éléments. On va donc demander à une fonction d'agir sur une liste, en y ajoutant une valeur.

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
function liste()
{
    echo "creation 10 éléments <BR>";
    $tableau =  [ 6,2,95,5,8547,154,157,98 ];
 
    $ma_liste = new Liste();
    foreach($tableau as $valeur) {
         inserer_valeur( $ma_liste, $valeur );
   }
   return ma_liste;
}
 
function inserer_valeur($liste, $valeur) {
     /// à compléter
}

Et c'est tout. Idéalement, insérer_valeur(), ça devrait être une méthode de la classe Liste, mais on va supposer qu'on ne t'en a pas encore parlé.

Que fait-on pour insérer ?

1. on cherche à quel endroit ça se passe
2. on crée un nouvel élément, que l'on accroche à cet endroit

Mais quand on accroche quelque chose, c'est _après_ un élément, ou alors au début. Après quel élément ? pour le savoir, il faut parcourir la liste, et s'arreter quand on tombe sur le premier qui est plus grand. Quelque chose comme ça :

Code :

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

1
2
3
4
$element = $ma_liste->premier;
 while(   $element != null     &&     $element->valeur < $valeur) {
           $element = $element->suivant;
 }

sauf que non, c'est pas tout à fait ça. Parce qu'il faut accrocher au _prédécesseur_ du premier qui est plus grand. Mais ça c'est pas grave, on modifie le code pour le noter dans une variable

Code :

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

1
2
3
4
5
6
     $predecesseur = null;                      // hop
     $element = $ma_liste->premier;
     while(   $element != null      &&      $element->valeur < $valeur)  {
          $predecesseur = $element;            // et hop
          $element = $element->suivant;
     }

Et voila, deux cas à la sortie de la boucle

• soit le $predecesseur est nul, et dans ce cas il faut accrocher en tête de liste
• soit il ne l'est pas et on accroche à cet endroit.

Note 1: pour des débutants c'est suffisant, même si ça donne un algorithme quadratique. Sinon on trie le tableau et on construit, où on construit et on trie la liste, mais avec un algo en complexité N log N (le tri-fusion est facile à faire sur les listes).