Insert pour une liste liée pseudo-code

Dans l'Introduction à l'Algorithme Ed 3, j'ai lu le pseudo-code algo pour insérer un élément dans une linkedlist, et je ne comprends pas l'étape intermédiaire.

x.prev = L.head
if L.head != NIL
    L.head.prev = x
L.head = x
x.prev = NIL

et si mon original de la liste chaînée est HEAD -- 4 -- 24, je comprends que les étapes sont les suivantes:

TÊTE -- 4 -- 24
x -- 4 -- 24
TÊTE -- x -- 4 -- 24

avec les 2. correspondant à

x.prev = L.head

Pourquoi nous avons pour insérer x avant de la tête avec

 if L.head != NIL
        L.head.prev = x

Pourrait smbdy préciser ?

Vous avez changé le pseudo-code de PLC, était-il intentionnel? La première ligne doit être x.next = L.head pas x.prev = L.head
oui merci beaucoup

InformationsquelleAutor | 2013-03-27

1

Permet de dire, d'Abord la Tête est orientée vers le nœud [Y], cela signifie que [Y] est l'actuel directeur. Nous allons insérer un nouveau nœud [X], qui deviendra nœud de tête de notre liste, de sorte que la tête pointeur pointera sur [X].

Ici rappeler que, au début des temps (avant d'insérer quoi que ce soit à la liste) directeur de point Nul.

Laisse maintenant aller étape par étape avec le pseudo code pour voir ce qui se passe:

Situation actuelle de notre liste est: Head -> [Y], [Y].prev -> NiL, la tête est orientée vers le à [Y], jusqu'à ce que nous avons de changer le pointeur de Tête, chaque fois que nous utilisons la Tête que vous pouvez penser/lire [Y]. Aujourd'hui à la tête de nœud [Y] fois [X], donc permet de mettre à côté de [X] = [Y]
```
1. x.next = L.head  
```
Après la première déclaration, nous avons [X].next->[Y], Head->[Y], [Y].prev->NiL
```
2. if (L.head != NIL) //At the beginning Head might be pointing to NiL, and of course NiL.prev does not exist and we do not want to access illegal location.
    3. L.head.prev = x //if head is not pointing to Nil then it is pointing to [Y],
                       //in that case [X] will be the prev node of [Y], 
                    //so after this line, have Head->[Y], [X].next->[Y], [Y].prev->[X]  
```
Après la 3e ligne, nous pouvons définir notre liste de Tête pointeur vers le point [X]
```
4. L.head = x    
5. x.prev = NIL //You can write L.head.prev = NIL, as [X] is now the new head
```
InformationsquelleAutor sowrov

Astuce est que

L:tête:pré désigne le pré attribut de l'objet que L':tête
points à

Puis, algo va comme suit

    //HEAD -- 4 -- 24

    x.next = l.head
    if L.head != NIL
        L.head.prev = x

    //x -- 4 -- 24

    L.head = x
    x.prev = NIL

   //HEAD -- x -- 4 --24

InformationsquelleAutor

Vous devez vous connecter pour publier un commentaire.