Explication du code (liste chaînée C)

Ce n’est pas mon code. J’ai pris ce code de ce site:

http://www.macs.hw.ac.uk/~rjp/Coursewww/Cwww/linklist.html

J’utilise comme matériau de référence la création d’une liste chaînée. Je suis un peu confus sur ce qui se passe. Quelqu’un peut-il m’expliquer s’il vous plaît ce qui se passe. Je vais marquer ce qui me trouble avec 1-5.

#include #include struct list_el { int val; struct list_el * next; }; typedef struct list_el item; void main() { item * curr, * head; int i; head = NULL; //1 for(i=1;ival = i; curr->next = head; //2 head = curr; //3 } curr = head; // 4 while(curr) { //5 printf("%d\n", curr->val); curr = curr->next ; } 
  1. head = NULL → Pourquoi la tête est-elle définie sur NULL? Je sais que vous êtes censé le faire (je le fais par habitude) mais je ne sais pas vraiment pourquoi.

  2. curr-> next = head → Je n’ai jamais vraiment compris cela aussi. J’ai peut-être une définition erronée de “tête”, mais dans une liste chaînée, s’agit-il du nœud de départ ou du dernier nœud de la liste? J’ai toujours supposé que c’était le nœud de départ, mais sur cette ligne, il semble que ce soit le dernier nœud.

  3. head = curr → Pourquoi la réglons-nous égale à curr?

  4. curr = head → puis réglez curr = head après la fin de la boucle.

  5. while (curr) → Juste pour être sûr, cela traverse la liste et cela équivaut à while (curr! = NULL), non?

# 1: head = NULL

Initialisation du pointeur . Il est généralement recommandé d’initialiser le pointeur sur NULL soit (1) lors de la déclaration, soit (2) immédiatement après la déclaration. Si les programmeurs déréférencent par erreur des pointeurs non initialisés, des valeurs parasites sont renvoyées. Souvent, il est extrêmement difficile de déboguer si votre parsingur statique et votre compilateur n’affiche pas de messages d’avertissement ou d’erreur pour les pointeurs non initialisés.

Pour plus d’informations, reportez-vous à Code Complete de Steve McConnell : Manuel pratique de construction de logiciels ou à la page Wikipedia sur la programmation défensive .

# 2: curr->next = head

Construire la liste liée . Le nœud curr est “lié” au nœud précédemment créé dans la séquence.

# 3: head = curr

Mise à jour du pointeur principal. Le pointeur principal est en cours de mise à jour pour pointer vers le dernier nœud malloc ed.

Les illustrations ci-dessous illustrent les étapes 2 et 3:

premiersecondetroisièmeen avant et final

# 4: curr = head

Réinitialisation du pointeur. Cette étape est similaire à l’étape 2: curr->next = head . En définissant curr node sur head , curr est “prêt” pour la navigation dans les listes chaînées dans la boucle while. De manière analogue, c’est comme initialiser la variable itérative à 0 au début de la boucle (c’est-à-dire i = 0 ). Pour visualiser cette étape, veuillez vous reporter aux illustrations ci-dessous montrant avant / après l’exécution de cette instruction:

avant

après

# 5: while(curr)

Parcourir la liste. Etant donné que curr pointe vers le premier noeud (à partir de l’étape 4), cette boucle while parcourt la liste jusqu’à curr->next que curr->next renvoie NULL. Sous une forme moins abstraite, nous pouvons réécrire cette déclaration comme tant while(curr != NULL) .

  1. head pointe vers le haut de la liste. Puisque la liste est actuellement vide, elle est définie sur null
  2. Lorsque vous ajoutez un nœud à la liste, vous définissez le pointeur “suivant” sur l’en-tête actuel de la liste. Le met le nouveau noeud en tête de liste.
  3. Vous définissez “head” sur “curr” pour que le nouveau nœud devienne la tête de la liste.
  4. Une fois la boucle terminée, vous réutilisez la variable “curr” pour parcourir la liste.
  5. Vous parcourez la liste en configurant “curr” pour chaque nœud jusqu’à ce que vous descendiez au bas de la liste (où curr-> next est null)

(1). Vous devez définir quelque chose et utiliser NULL est un moyen de dire que cela ne pointe pas vers rien. Généralement, la valeur NULL est identique à 0. Dans certaines langues, il n’est pas nécessaire d’initialiser la variable car elle sera automatiquement définie sur nil. Mais C ne le fait pas, alors vous devez le faire vous-même.

(2). head pointe vers le premier noeud de la liste. Au début, il s’agit de NULL, ce qui signifie que la liste est vide et que la head ne pointe donc pas vers rien. cur est un nouveau nœud qui veut être inséré dans la liste. curr->next veut pointer vers le premier noeud de la liste existante, c’est pourquoi curr->next est défini sur head .

(3). À ce stade, la head ne pointe plus vers le premier nœud. La première fois dans la boucle, cela ressemble à ceci:

 curr -> node1 -> NULL
          tête - ^

Mais en général, cela ressemblerait à ceci

 curr -> node3 -> node2 -> node1 -> NULL
           tête - ^

Nous devons donc mettre à jour la head pour pointer vers le premier noeud. Puisque curr pointe vers le nœud nouvellement créé, qui est placé à l’avant, nous venons de définir head to point sur le même nœud que curr .

(4). La première partie du programme est terminée. curr n’est plus nécessaire car il a été utilisé pour suivre le nouveau nœud que nous avons créé. C’était une variable temporaire. Cette ligne curr = head signifie que nous allons initialiser curr au début de la liste. Nous aurions pu utiliser une autre variable pour la rendre plus lisible, mais vous constaterez généralement la réutilisation de variables temporaires.

(5). Droite. Vous verrez probablement NULL défini comme (void*)0 , c’est donc la même chose que 0. Vous ne verrez probablement jamais d’autre valeur que 0 sauf pour les très vieilles machines des années 60 ou 70. Donc logiquement, cela équivaut à: while (curr != 0) qui est identique à while (curr) .

1. tête = NULL → pourquoi la tête est-elle définie sur NULL?
C’est une bonne pratique pour initialiser vos variables. Sur certains systèmes, les variables déclarées ont tout ce qui s’est passé en mémoire lorsque l’espace d’adressage est saisi.

2. curr-> next = head → Je n’ai jamais vraiment compris cela aussi. J’ai peut-être une définition erronée de “tête”, mais dans une liste chaînée, s’agit-il du nœud de départ ou du dernier nœud de la liste? J’ai toujours supposé que c’était le nœud de départ, mais sur cette ligne, il semble que ce soit le dernier nœud.
Oui, la tête est le nœud de départ.

3. head = curr → Pourquoi la réglons-nous égale à curr?
Cette boucle ajoute ici de nouveaux noeuds en tête. Comme une stack. D’autres façons de le faire ajoutent de nouveaux noeuds sur la queue. Les deux méthodes sont toujours des “listes chaînées”.

4. curr = head → puis réglez curr = head après la fin de la boucle.
curr agit comme un index, une variable de travail afin de ne pas perturber la structure de données. Il le réinitialise après avoir fini. “Rembobiner la bande” si vous voulez.

5. while (curr) → Juste pour être sûr, cela traverse la liste et cela équivaut à while (curr! = NULL), non?
Oui, c’est l’une de ces choses que vous trouvez implicitement dans C. Tout dans une boucle while est implicitement while(whatnot != 0) et null == 0.

Premièrement, vous pouvez trouver la réponse à la question de savoir pourquoi head est toujours NULL dans la liste liée. Head is Always Null et la liste chaînée C ++ simple . Un tutoriel pour débutant que vous pouvez trouver sur une liste chaînée dans c . L’instruction head = curr a associé la valeur de l’en-tête du pointeur NULL à la valeur du pointeur actuel qui reçoit une valeur différente de zéro en allouant de la mémoire. while (curr) est une boucle qui s’exécute tant que curr diffère de NULL, NULL en tant que macro associé à une valeur zéro pour l’adresse de pointage.

Nous commençons avec rien. C’est ce que

 head = NULL; 

nous dit. Nous n’avons pas encore de liste, nous ne pouvons donc pas y accéder.

Nous passons maintenant de 1 à 10. Nous construisons une liste de l’arrière en avant. HEAD est NULL, donc le “dernier” (le premier créé) pointe sur NULL:

 curr->next = head; // head is NULL in the first loop 

HEAD est maintenant défini sur ce nouvel élément:

 head = curr; 

Lors de la deuxième exécution de cette boucle, head stocke le pointeur sur le dernier élément créé. Celui qui vient d’être créé le pointera ensuite. Nous plaçons ce nouvel élément devant le dernier élément.

Réglage

 head = curr; 

doit être fait pour que cette tête contienne le bon pointeur dans la prochaine boucle. C’est ce qu’on appelle tête, car il stocke toujours le début de la liste créée jusqu’alors.

// 4 n’est pas vraiment nécessaire.

La dernière opération avant était:

 head = curr; 

Alors

 curr = head; 

est insensé.

Et le cinquième parcourt la liste. “curr” pointe sur le premier élément (avec une adresse non NULL) et est réglé sur curr-> next dans chaque boucle. Une fois que curr est NULL (au dernier élément), l’instruction n’est plus vraie.

Dans le 4ème problème, je ne pense pas que curr=head est nécessaire.Parce que la boucle est terminée, curr et head avaient le même pointeur (noeud de i = 10). Mais c’est une bonne habitude.