Construire une pile liée dynamique en C : mise en œuvre et pièges

La plupart des débutants supposent que les structures de données sont statiques. Ce n’est pas le cas. Une pile liée est une bête dynamique. Il grandit et rétrécit à la volée. Vous ne pré-allouez pas de mémoire. Vous le saisissez quand vous en avez besoin. Relâchez-le lorsque vous avez terminé.

Cet exemple utilise des entiers. Remplacez typedef int stack_data par float ou char si vous le souhaitez. La logique reste la même.

L’interface

Regardez l’en-tête. C’est un contrat.

stack_init crée le désordre. stack_clear l’efface. stack_empty vous indique s’il reste quelque chose. push insère les données. pop les extrait.

Simple. Faire le ménage.

Le moteur

Le fichier de code cache les tripes.

top pointe vers l’élément le plus récent. NULL signifie vide.

stack_init réinitialise simplement top à NULL. Fait.

stack_clear apparaît jusqu’à ce qu’il soit vide. C’est une boucle. C’est bon marché.

stack_empty vérifie si top est NULL. Renvoie 1 si vrai. 0 si faux.

stack_push fait le gros du travail.

Il alloue de la mémoire. Définit les données. Le relie à l’ancien sommet. Mises à jour « top ».

stack_pop inverse le processus.

Il récupère les données. Se déplace de haut en bas. Libère l’ancien nœud. Renvoie la valeur.

Si la pile est vide ? Il renvoie les ordures. Ne sortez pas d’une pile vide.

Masquage des informations

C’est la clé.

Vous ne voyez que l’en-tête. Vous ne voyez pas le code.

La pile pourrait utiliser des tableaux. Pointeurs. Fichiers. Une liste chaînée. Cela n’a pas d’importance.

Tant que l’interface fonctionne, peu importe la façon dont elle est construite.

C’est une information cachée. Ce n’est pas seulement un mot à la mode. C’est ainsi que vous créez un logiciel qui ne tombe pas en panne lorsque vous modifiez les composants internes.

C Les pièges

C ne pardonne pas les erreurs.

1. Les parenthèses comptent. (*p).i n’est pas la même chose que *p.i. On déréférence le pointeur en premier. L’autre accède au membre puis déréférence. Si vous vous trompez, vous tombez en panne.
2. Fuites de mémoire. Ne vous contentez jamais de définir top = NULL. Vous êtes orphelin de chaque nœud de la liste. Vous perdez les données. Vous perdez la mémoire. Utilisez « gratuit ». Toujours.
3. Inclure les en-têtes. NULL réside dans stdio.h. Si vous l’oubliez, votre code pourrait être compilé sur certains compilateurs. Ce ne sera pas le cas pour les autres. Ou cela définira « NULL » comme zéro d’une manière étrange. Incluez si vous utilisez des pointeurs.

Quelle est la prochaine étape ?

La pile de base est simple. Les vraies piles ont besoin de plus.

Ajoutez « dup ». Dupliquez l’élément supérieur. Ajoutez « compte ». Renvoie le nombre d’éléments. Ajoutez « ajouter ». Pop les deux premiers, ajoutez-les, poussez le résultat.

Créez un programme de pilote. Écrivez un makefile. Compilez-le. Exécutez-le.

S’il plante, vous avez manqué un « gratuit ». Ou vous avez accédé à la mémoire libérée. Déboguez-le.

Le test de la réalité

L’allocation dynamique est rapide. Jusqu’à ce que ce ne soit pas le cas.

malloc et free ont des frais généraux. En boucles serrées, ça s’additionne.

Mais pour un usage général ? C’est flexible. C’est la norme. C’est ce que vous verrez dans la plupart des bases de code C.

La pile liée est un élément de base.

Vous l’utiliserez pour les appels de fonction. Pour l’évaluation de l’expression. Pour les boutons d’annulation.

C’est partout.

N’oubliez pas : si vous l’attribuez, vous le libérez. Ou bien.

“Le code c’est comme l’humour