Point de départ

// Une cellule : une valeur, un lien. Rien d'autre.
const cellule = (valeur, suivant = null) => ({ valeur, suivant });

function creerListe() {
  return { tete: null, taille: 0 };
}

// ── Insertion en tête ─────────────────────────────────────────────────────
function insererEnTete(L, valeur) {
  const n = cellule(valeur);
  // ← ces deux lignes sont dans le MAUVAIS ordre : la liste sera perdue
  L.tete = n;
  n.suivant = L.tete;
  L.taille++;
  return L;
}

function versTexte(L) {
  const bouts = [];
  let c = L.tete, garde = 0;
  while (c !== null && garde++ < 50) { bouts.push(c.valeur); c = c.suivant; }
  return (bouts.length ? bouts.join(" -> ") : "(vide)") + " -> nul";
}

// ── Suppression de la première occurrence ─────────────────────────────────
function supprimer(L, valeur) {
  let precedente = null, c = L.tete;
  while (c !== null && c.valeur !== valeur) { precedente = c; c = c.suivant; }
  if (c === null) return false;
  // ← à écrire : décrocher c, en distinguant le cas où c est la tête
  L.taille--;
  return true;
}

// ── Inversion récursive ───────────────────────────────────────────────────
// Une liste est vide, ou une cellule suivie d'une liste : l'inversion
// s'écrit donc récursivement, au prix de O(n) de pile.
function inverserRec(c) {
  if (c === null || c.suivant === null) return c;
  const nouvelleTete = inverserRec(c.suivant);
  c.suivant.suivant = c;   // la suivante pointe désormais sur moi
  c.suivant = null;        // et moi sur rien : je deviens la dernière
  return nouvelleTete;
}

// ── Inversion itérative, trois pointeurs ──────────────────────────────────
function inverserIter(L, tracer) {
  let precedente = null, courante = L.tete;
  while (courante !== null) {
    // ← à écrire. Dessinez d'abord : precedente <- courante  suivante
    //   Quelle flèche déplacer en premier sans perdre la suite ?
    break;
  }
  L.tete = precedente;
  return L;
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Remettez insererEnTete dans le bon ordre.
// 2. Écrivez supprimer, sans oublier le cas où la cellule est la tête.
// 3. Écrivez inverserIter, et faites afficher l'état à chaque tour.

const L = creerListe();
for (const v of [5, 43, 7, 12]) insererEnTete(L, v);
console.log("liste :", versTexte(L), "| taille", L.taille);

Solution

const cellule = (valeur, suivant = null) => ({ valeur, suivant });
function creerListe() { return { tete: null, taille: 0 }; }

function insererEnTete(L, valeur) {
  const n = cellule(valeur);
  // D'ABORD raccrocher la suite, ENSUITE déplacer la tête. Dans l'autre
  // ordre, l'ancienne liste devient inatteignable.
  n.suivant = L.tete;
  L.tete = n;
  L.taille++;
  return L;
}

function versTexte(L) {
  const bouts = [];
  let c = L.tete, garde = 0;
  while (c !== null && garde++ < 50) { bouts.push(c.valeur); c = c.suivant; }
  return (bouts.length ? bouts.join(" -> ") : "(vide)") + " -> nul";
}

function supprimer(L, valeur) {
  let precedente = null, c = L.tete;
  while (c !== null && c.valeur !== valeur) { precedente = c; c = c.suivant; }
  if (c === null) return false;
  // Deux cas, et c'est exactement ce qu'une sentinelle ferait disparaître.
  if (precedente === null) L.tete = c.suivant;   // c'était la tête
  else precedente.suivant = c.suivant;            // cas général
  L.taille--;
  return true;
}

function inverserRec(c) {
  if (c === null || c.suivant === null) return c;
  const nouvelleTete = inverserRec(c.suivant);
  c.suivant.suivant = c;
  c.suivant = null;
  return nouvelleTete;
}

function inverserIter(L, tracer) {
  let precedente = null, courante = L.tete;
  while (courante !== null) {
    // L'ordre est imposé par une contrainte : dès qu'on écrit dans
    // courante.suivant, la suite est perdue. On la SAUVE donc d'abord.
    const suivante = courante.suivant;   // 1. sauver la suite
    courante.suivant = precedente;       // 2. retourner la flèche
    precedente = courante;               // 3. avancer les deux repères
    courante = suivante;
    if (tracer) {
      console.log("   inversé jusqu'ici : " +
        versTexte({ tete: precedente }) + "   reste : " + versTexte({ tete: courante }));
    }
  }
  L.tete = precedente;
  return L;
}

const L = creerListe();
for (const v of [5, 43, 7, 12]) insererEnTete(L, v);
console.log("liste       :", versTexte(L), "| taille", L.taille);

console.log("supprimer 7 :", supprimer(L, 7), "->", versTexte(L));
console.log("supprimer 12:", supprimer(L, 12), "->", versTexte(L), " (c'était la tête)");
console.log("supprimer 99:", supprimer(L, 99), "->", versTexte(L), " (absente)");

console.log("");
console.log("— inversion itérative, pas à pas —");
const M = creerListe();
for (const v of [4, 3, 2, 1]) insererEnTete(M, v);
console.log("   départ : " + versTexte(M));
inverserIter(M, true);
console.log("   arrivée : " + versTexte(M));

console.log("");
const N = creerListe();
for (const v of [4, 3, 2, 1]) insererEnTete(N, v);
N.tete = inverserRec(N.tete);
console.log("inversion récursive :", versTexte(N), " (O(n) de pile, contre O(1))");

// Les deux inversions font le même travail. La récursive est plus courte à
// écrire et consomme un cadre par élément : sur une liste d'un million de
// cellules, elle fait déborder la pile. L'itérative tient dans trois
// variables — et c'est le cas typique où l'itération l'emporte, la liste
// étant un objet récursif mais de profondeur LINÉAIRE (chapitre 1).

Avant de commencer

• Les TP 7 et 8 de Programmation : pointeurs et allocation
• valgrind

Énoncé

1. Le type et les bases — Définissez le maillon et écrivez création, insertion en tête, affichage, longueur, libération. Vérifiez à valgrind qu'aucun octet ne fuit.
2. Insérer à la fin — Écrivez l'insertion en queue. Comparez son coût à celui de l'insertion en tête, en nombre de maillons parcourus.
3. Supprimer — Écrivez la suppression d'une valeur. Traitez explicitement les trois cas : liste vide, valeur en tête, valeur au milieu. Testez les trois. Indice : La suppression en tête est le cas qu'on oublie, parce qu'il faut modifier le pointeur de l'appelant.
4. Le double pointeur — Réécrivez la suppression avec un pointeur sur pointeur, de façon à supprimer les trois cas particuliers. Comparez les deux versions.
5. Inverser — Inversez la liste sur place, sans allouer. Faites-le en itératif, puis en récursif, et vérifiez les deux sur une liste vide et à un élément.
6. Le cycle — Créez volontairement une liste circulaire et lancez votre affichage. Écrivez ensuite la détection de cycle avec deux parcours de vitesse différente.
7. Mesurer contre le tableau — Comparez liste et tableau dynamique sur : insertion en tête, insertion en queue, accès au n sur deux, parcours complet. Cent mille éléments.
8. Le résultat qui surprend — Sur le parcours complet, la liste est nettement plus lente malgré une complexité identique. Expliquez, en vous appuyant sur un TP d'Architecture.

C'est réussi quand

• ✓ valgrind annonce zéro fuite après votre libération
• ✓ Votre suppression par double pointeur n'a aucun cas particulier
• ✓ Vous détectez un cycle sans allouer de mémoire supplémentaire
• ✓ Vous expliquez pourquoi le parcours d'une liste est plus lent que celui d'un tableau

Correction

typedef struct Maillon { int valeur; struct Maillon *suivant; } Maillon;

Maillon *inserer_tete(Maillon *tete, int v) {
  Maillon *m = malloc(sizeof *m);
  if (!m) return NULL;             /* le retour est TESTÉ */
  m->valeur = v;
  m->suivant = tete;
  return m;                        /* la nouvelle tête */
}

void liberer(Maillon *tete) {
  while (tete) {
      Maillon *suivant = tete->suivant;   /* AVANT le free */
      free(tete);
      tete = suivant;
  }
}

/* version classique : trois cas */
if (!*tete) return;
if ((*tete)->valeur == v) { Maillon *m = *tete; *tete = m->suivant;
                          free(m); return; }
Maillon *p = *tete;
while (p->suivant && p->suivant->valeur != v) p = p->suivant;
if (p->suivant) { Maillon *m = p->suivant; p->suivant = m->suivant; free(m); }

/* version double pointeur : AUCUN cas particulier */
void supprimer(Maillon **p, int v) {
  while (*p) {
      if ((*p)->valeur == v) {
          Maillon *m = *p;
          *p = m->suivant;
          free(m);
          return;
      }
      p = &(*p)->suivant;
  }
}

Maillon *inverser(Maillon *tete) {
  Maillon *precedent = NULL;
  while (tete) {
      Maillon *suivant = tete->suivant;   /* sauvegarder */
      tete->suivant = precedent;          /* retourner */
      precedent = tete;                   /* avancer */
      tete = suivant;
  }
  return precedent;
}

int a_un_cycle(Maillon *tete) {
  Maillon *lent = tete, *rapide = tete;
  while (rapide && rapide->suivant) {
      lent = lent->suivant;
      rapide = rapide->suivant->suivant;
      if (lent == rapide) return 1;
  }
  return 0;
}

100 000 éléments        liste       tableau dynamique
insertion en tête       0,004 s     2,8 s      ← décalage de tout
insertion en queue      12,4 s      0,003 s    ← parcours complet
                      (0,004 s avec pointeur de queue)
accès à l'élément n/2   0,9 ms      < 1 ns
parcours complet        0,0031 s    0,0004 s   ← MÊME complexité

tableau : éléments CONTIGUS
une ligne de cache de 64 octets = 16 entiers d'un coup
→ 1 défaut de cache pour 16 éléments

liste : maillons DISPERSÉS dans le tas
chaque maillon est ailleurs, imprévisible pour le préchargeur
→ 1 défaut de cache par élément, et 16 octets par maillon
  dont 8 pour le pointeur

Point de départ

// ── Pile par tableau ──────────────────────────────────────────────────────
function creerPile() {
  const T = [];
  return {
    empiler: (x) => T.push(x),
    depiler: () => T.pop(),
    sommet: () => T[T.length - 1],
    estVide: () => T.length === 0,
    taille: () => T.length,
    contenu: () => [...T],
  };
}

// ── File par tampon circulaire ────────────────────────────────────────────
function creerFile(capacite) {
  const T = new Array(capacite).fill(null);
  let tete = 0, queue = 0;
  // ← il manque un compteur : sans lui, plein et vide sont indiscernables
  return {
    enfiler(x) {
      T[queue] = x;
      queue = (queue + 1) % capacite;
      return true;   // ← devrait refuser si la file est pleine
    },
    defiler() {
      const x = T[tete];
      tete = (tete + 1) % capacite;
      return x;      // ← devrait rendre undefined si la file est vide
    },
    estVide: () => false,   // ← à écrire
    estPleine: () => false, // ← à écrire
    contenu: () => T.map((v, i) => (v === null ? "." : v)).join(" "),
  };
}

// ── Application 1 : parenthésage ──────────────────────────────────────────
const PAIRES = { ")": "(", "]": "[", "}": "{" };

function verifier(texte) {
  const p = creerPile();
  for (let i = 0; i < texte.length; i++) {
    const c = texte[i];
    if ("([{".includes(c)) p.empiler({ c, i });
    else if (c in PAIRES) {
      // ← à écrire : trois cas d'erreur distincts à distinguer
    }
  }
  return { ok: true };
}

// ── Application 2 : expression postfixée ──────────────────────────────────
function evaluer(expression) {
  const p = creerPile();
  for (const jeton of expression.split(" ")) {
    if (!isNaN(Number(jeton))) { p.empiler(Number(jeton)); continue; }
    const a = p.depiler();
    const b = p.depiler();
    // ← attention à l'ORDRE : lequel de a et b est l'opérande de gauche ?
    if (jeton === "+") p.empiler(a + b);
    if (jeton === "-") p.empiler(a - b);
    if (jeton === "*") p.empiler(a * b);
    if (jeton === "/") p.empiler(a / b);
  }
  return p.depiler();
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Ajoutez le compteur à la file et faites-la refuser proprement.
// 2. Écrivez verifier() en distinguant les trois erreurs.
// 3. Corrigez l'ordre des opérandes dans evaluer().

for (const e of ["5 1 2 + 4 * + 3 -", "7 3 -", "20 4 /"]) {
  console.log(e.padEnd(22) + "= " + evaluer(e));
}

Solution

function creerPile() {
  const T = [];
  return {
    empiler: (x) => T.push(x),
    depiler: () => T.pop(),
    sommet: () => T[T.length - 1],
    estVide: () => T.length === 0,
    taille: () => T.length,
    contenu: () => [...T],
  };
}

function creerFile(capacite) {
  const T = new Array(capacite).fill(null);
  let tete = 0, queue = 0, nombre = 0;   // le compteur qui manquait
  return {
    enfiler(x) {
      if (nombre === capacite) return false;   // refuser plutôt qu'écraser
      T[queue] = x;
      queue = (queue + 1) % capacite;
      nombre++;
      return true;
    },
    defiler() {
      if (nombre === 0) return undefined;
      const x = T[tete];
      T[tete] = null;
      tete = (tete + 1) % capacite;
      nombre--;
      return x;
    },
    estVide: () => nombre === 0,
    estPleine: () => nombre === capacite,
    nombre: () => nombre,
    contenu: () => T.map((v) => (v === null ? "." : v)).join(" "),
  };
}

const PAIRES = { ")": "(", "]": "[", "}": "{" };

function verifier(texte) {
  const p = creerPile();
  for (let i = 0; i < texte.length; i++) {
    const c = texte[i];
    if ("([{".includes(c)) p.empiler({ c, i });
    else if (c in PAIRES) {
      // Erreur 1 : un fermant alors que rien n'est ouvert.
      if (p.estVide()) return { ok: false, quoi: "fermeture orpheline " + c, position: i };
      const ouvert = p.depiler();
      // Erreur 2 : un fermant qui ne correspond pas au sommet.
      if (ouvert.c !== PAIRES[c]) {
        return { ok: false, quoi: ouvert.c + " fermé par " + c, position: i };
      }
    }
  }
  // Erreur 3 : des ouvertures jamais refermées.
  if (!p.estVide()) {
    const reste = p.sommet();
    return { ok: false, quoi: reste.c + " jamais refermé", position: reste.i };
  }
  return { ok: true };
}

function evaluer(expression) {
  const p = creerPile();
  for (const jeton of expression.split(" ")) {
    if (!isNaN(Number(jeton))) { p.empiler(Number(jeton)); continue; }
    // Le PREMIER dépilé est l'opérande de DROITE : c'est le dernier empilé.
    const droite = p.depiler();
    const gauche = p.depiler();
    if (jeton === "+") p.empiler(gauche + droite);
    if (jeton === "-") p.empiler(gauche - droite);
    if (jeton === "*") p.empiler(gauche * droite);
    if (jeton === "/") p.empiler(gauche / droite);
  }
  return p.depiler();
}

console.log("— file circulaire —");
const f = creerFile(6);
for (const x of ["A", "B", "C", "D"]) f.enfiler(x);
console.log("   après 4 enfilages :", f.contenu(), "| nombre", f.nombre());
f.defiler(); f.defiler(); f.defiler(); f.defiler();
for (const x of ["E", "F", "G"]) f.enfiler(x);
console.log("   après 4 défilages puis 3 enfilages :", f.contenu(),
            "  (les positions 0 et 1 ont été RÉUTILISÉES)");
for (const x of ["H", "I", "J", "K"]) {
  if (!f.enfiler(x)) console.log("   file pleine : " + x + " refusé, rien n'est écrasé");
}

console.log("");
console.log("— parenthésage —");
for (const t of ["(a[b]{c})", "(a]b)", "a)b", "(a[b)", "((a)"]) {
  const r = verifier(t);
  console.log("   " + t.padEnd(12) + (r.ok ? "correct" : "INCORRECT : " + r.quoi + " (position " + r.position + ")"));
}

console.log("");
console.log("— expressions postfixées —");
for (const [e, attendu] of [["5 1 2 + 4 * + 3 -", 14], ["7 3 -", 4], ["20 4 /", 5], ["2 3 4 * +", 14]]) {
  const v = evaluer(e);
  console.log("   " + e.padEnd(22) + "= " + String(v).padStart(4) +
              (v === attendu ? "  ok" : "  X attendu " + attendu));
}
// « 7 3 - » est le test qui compte : en inversant les opérandes on obtient
// −4 au lieu de 4. L'addition et la multiplication ne l'auraient pas révélé,
// ce qui rend l'erreur facile à laisser passer.

Avant de commencer

• Le TP 5 : liste chaînée
• Le TP 1 : la pile d'appels

Énoncé

1. La pile, deux fois — Implémentez une pile sur tableau dynamique, puis sur liste chaînée. Même interface. Comparez les temps sur un million d'opérations.
2. La file, et le piège — Implémentez une file sur tableau simple, en avançant les deux indices. Faites tourner un million d'enfilages et défilages et observez la consommation mémoire.
3. Le tampon circulaire — Corrigez avec un tableau circulaire. Trouvez comment distinguer une file pleine d'une file vide, et implémentez votre choix. Indice : Les deux situations donnent les mêmes indices ; il faut une information de plus.
4. Vérifier un parenthésage — Écrivez la vérification d'une expression contenant trois sortes de délimiteurs. Testez sur des cas corrects, des cas mal fermés, et des cas mal imbriqués.
5. Évaluer une expression postfixée — Écrivez l'évaluateur, puis la conversion de l'infixe vers le postfixe. Testez sur une expression avec priorités et parenthèses.
6. L'échange qui change tout — Écrivez un parcours de labyrinthe en utilisant une pile. Puis remplacez la pile par une file, sans rien changer d'autre. Comparez les chemins trouvés.
7. Comprendre l'écart — Sur un labyrinthe où plusieurs chemins mènent à la sortie, dites laquelle des deux versions trouve le plus court, et pourquoi.
8. Au fil rouge — Ajoutez pile et file à votre bibliothèque, avec un en-tête propre et des tests. Vous les utiliserez telles quelles au TP 9.

C'est réussi quand

• ✓ Votre file circulaire tourne un million de fois sans croître en mémoire
• ✓ Votre évaluateur postfixé donne le bon résultat sur une expression à parenthèses
• ✓ Le passage pile → file change le chemin trouvé, et vous savez dire lequel est optimal

Correction

int file[1000000]; int debut = 0, fin = 0;
enfiler(v)  { file[fin++] = v; }
defiler()   { return file[debut++]; }

/* après un million d'opérations, debut = fin = 1 000 000
 la file est VIDE et le tableau est PLEIN :
 tout l'espace avant debut est perdu */

typedef struct { int *t; size_t cap, debut, taille; } File;

void enfiler(File *f, int v) {
  f->t[(f->debut + f->taille) % f->cap] = v;
  f->taille++;
}
int defiler(File *f) {
  int v = f->t[f->debut];
  f->debut = (f->debut + 1) % f->cap;
  f->taille--;
  return v;
}

int equilibre(const char *s) {
  Pile p; pile_init(&p);
  for (; *s; s++) {
      if (strchr("([{", *s)) empiler(&p, *s);
      else if (strchr(")]}", *s)) {
          if (pile_vide(&p)) return 0;              /* ferme sans ouvrir */
          char o = depiler(&p);
          if ((*s == ')' && o != '(') ||
              (*s == ']' && o != '[') ||
              (*s == '}' && o != '{')) return 0;    /* mal imbriqué */
      }
  }
  return pile_vide(&p);                             /* reste ouvert ? */
}

"3 4 + 2 *"
3    → empiler 3            pile : 3
4    → empiler 4            pile : 3 4
+    → dépiler 4 et 3, empiler 7    pile : 7
2    → empiler 2            pile : 7 2
*    → dépiler 2 et 7, empiler 14   pile : 14
résultat : 14

/* attention à l'ordre pour les opérateurs non commutatifs */
int b = depiler(&p), a = depiler(&p);   /* a AVANT b */
empiler(&p, a - b);

/* le seul changement */
Pile a_visiter;   →   File a_visiter;

avec une PILE : parcours en PROFONDEUR
suit un chemin jusqu'au bout avant d'essayer une autre branche
chemin trouvé : le premier, pas forcément le plus court
mémoire : la profondeur

avec une FILE : parcours en LARGEUR
explore par distance croissante depuis le départ
chemin trouvé : le PLUS COURT en nombre d'étapes — garanti
mémoire : la largeur, souvent bien plus grande