Simulic
Français

Piles, files et listes chaînées – les pointeurs pas à pas

InformatiqueAlgorithmique et résolution de problèmes17–18 ans

Chargement…

Utiliser avec ma classe ✨ Personnaliser avec l'IA Signaler un problème

Empilez et dépilez sur une pile, enfilez et défilez sur des files linéaires, circulaires et à priorité, et insérez, supprimez et cherchez des nœuds dans une liste chaînée, en voyant les pointeurs top, front, rear et head et les liens next changer ligne par ligne en Python ou en pseudo-code, avec débordement et sous-débordement. Comparez les implémentations par tableau statique et par nœuds et pointeurs dynamiques, mémoire comprise, et essayez des applications : vérification des parenthèses, annuler/rétablir, file d'impression et pile d'appels.

Leçon : Structures de données abstraites : piles, files et listes chaînées ; implémentation par tableau et par pointeurs

Ce qu’elle montre

Les piles, les files et les listes chaînées sont des structures de données abstraites. Une pile suit « dernier entré, premier sorti » : empiler et dépiler se font au sommet. Une file suit « premier entré, premier sorti » : les éléments arrivent en queue et sortent en tête ; une file circulaire réutilise les cases libérées grâce à MOD, et une file de priorité sert d'abord la priorité la plus haute. Une liste chaînée range chaque valeur dans un nœud qui pointe vers le suivant et se termine par un pointeur nul. Un tableau statique réserve un bloc fixe et peut déborder ; les nœuds dynamiques grandissent mais coûtent des pointeurs.

Mode d’emploi

Choisissez Pile, File, Liste chaînée ou Applications et une Implémentation. Tapez une Valeur et cliquez sur une opération comme Empiler, Enfiler ou Insérer à la position ; le code avance ligne par ligne à la Vitesse choisie. Cochez Ligne par ligne et cliquez sur Ligne suivante pour aller lentement, ou sur Terminer l'opération. Observez les pointeurs, le panneau Mémoire et le journal Opérations.

Paramètres modifiables

  • Mode Pile, File, Liste chaînée, Applications
  • Implémentation Tableau statique, Nœuds et pointeurs (dynamique)
  • Type de file Linéaire, Circulaire, À priorité
  • Capacité du tableau 3–10 cases
  • Application Vérifier les parenthèses (pile), Annuler / rétablir (deux piles), File d'impression (file), Pile d'appels
  • Langage Python, Pseudo-code
  • Vitesse 0,5–5 lignes/s

Questions à explorer

  1. Pourquoi une file linéaire peut-elle être pleine alors que des cases sont vides en tête, et comment la file circulaire règle-t-elle cela ?
  2. Quels pointeurs changent quand vous insérez un nœud au milieu d'une liste chaînée ?
  3. Combien d'octets six entiers occupent-ils dans un tableau statique et dans des nœuds chaînés, selon ce modèle ?

Simulations associées