EnglishCommencer

Tableau dynamique et liste chaînée

Deux façons de ranger une suite : le tableau qui double sa capacité quand il est plein et la liste chaînée. Pour chacune, le coût de l'accès, de l'insertion et de la suppression en tête, au milieu et en fin, coût amorti compris.

  • 25 cartes
  • 6 thèmes
  • Gratuit
Réviser ce deck

Le programme, thème par thème

Le poids de chaque thème suit celui que lui donne l'examen.

  1. Notions
  2. Questions
  3. Ranger et relier
  4. Les chiffres
  5. Mises en situation
  6. Comprendre

Quelques cartes du deck

  • Tableau dynamique : de quoi s'agit-il ?

    Voir la réponse

    Suite rangée dans une zone mémoire contiguë qui, une fois pleine, est recopiée dans une zone deux fois plus grande.

    C'est le list de Python et l'ArrayList de Java. L'accès par indice est direct, mais insérer en tête décale tous les éléments.

  • Ce code insère nouveau après prec dans une liste chaînée. Que devient la liste ?

    ```python
    nouveau = Maillon(7)
    prec.suivant = nouveau
    nouveau.suivant = prec.suivant
    `

    • nouveau pointe sur lui-même et la suite est perdue
    • Elle est correcte : 7 s'insère après prec
    • nouveau est inséré, mais prec perd son lien vers lui
    • Python lève une exception : suivant n'existe pas encore
    Voir la réponse

    nouveau pointe sur lui-même et la suite est perdue

    À la ligne 3, prec.suivant vaut déjà nouveau : on écrit nouveau.suivant = nouveau, et l'ancien suivant de prec n'est plus référencé. Il faut d'abord nouveau.suivant = prec.suivant, puis prec.suivant = nouveau.

  • Quand un tableau dynamique plein reçoit un ajout, il alloue une zone de capacité … et y … tous ses éléments.

    Voir la réponse

    Quand un tableau dynamique plein reçoit un ajout, il alloue une zone de capacité double et y recopie tous ses éléments.

    Agrandir d'une case seulement à chaque fois forcerait une recopie à chaque ajout : n ajouts coûteraient de l'ordre de n². Le doublement espace les recopies.

  • Capacité d'un tableau dynamique : de quoi s'agit-il ?

    Voir la réponse

    Nombre de cases réservées en mémoire, qui peut dépasser le nombre d'éléments réellement rangés.

    La taille compte les éléments présents, la capacité compte les cases disponibles. La recopie n'a lieu que lorsque la taille atteint la capacité.

Réviser ce deck