Implémenter des TADs à l'aide de tableaux
Introduit| English | Sens |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | débordement |
| underflow/ˌʌndəˈfləʊ/ | débordement vers le bas |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | tableau circulaire |
| free list/friː lɪst/ | liste libre |
Il n'existe pas de pile en mémoire
- Ouvrir un ordinateur et chercher la pile. Vous n'en trouverez pas. La mémoire est un immense tableau de cellules numérotées, et c'est tout.
- Chaque pile, chaque file, chaque liste chaînée est ce tableau plus deux ou trois variables entières qui se souviennent où se trouvent les choses. Push est « ajouter un à un nombre et stocker » ; dequeue est « lire une cellule et ajouter un à un autre nombre ».
- Tout ce cours est de la tenue de registre : quels pointeurs, quelles vérifications, et ce qui arrive aux bords.
- L'examen vous demande de décrire les déclarations, parcourir les pointeurs à travers quelques opérations, et dire pourquoi les vérifications sont là.
Une pile dans un tableau
- Garder les éléments dans
Stack[1:MaxSize]avec un entierTop, 0 quand la pile est vide. - Push(x) : si
Top = MaxSizela pile est pleine, c'est une débordement ; sinonTop ← Top + 1etStack[Top] ← x. - Pop() : si
Top = 0la pile est vide, c'est une indébordement ; sinon retournerStack[Top]etTop ← Top − 1.

Le tableau ne bouge jamais ; seul Top fait
Empiler un élément sur une pile déjà pleine provoque un dépassement de pile ______.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Dépassement = empiler lorsque Top = MaxSize ; dépiler depuis une pile vide (Top = 0) est une sous-dépassement.
Associez chaque condition de pile à base de tableau à sa signification.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Top compte les éléments : 0 = vide, MaxSize = plein ; les deux cas d'erreur sont le sous-dépassement et le dépassement.
Exemple résolu : déclarer et initialiser la pile
- Décrire les déclarations et l'initialisation nécessaires pour implémenter une pile de jusqu'à 50 entiers utilisant un tableau. [5]
- Un tableau de 50 éléments de type
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, pour garder les éléments. - Une constante ou variable
MaxSizefixée à 50, afin que push puisse tester pour plein. - Un
INTEGERpointeur de haut-de-pile,Top, initialisé à 0 pour montrer que la pile est vide ; pop le teste pour sous-charge, et push le compare avecMaxSizepour surcharge.
Quels éléments appartiennent à la déclaration et l'initialisation d'une pile à base de tableau ? Sélectionnez tous ceux qui s'appliquent.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Une pile a besoin d'un seul pointeur, Top. Un pointeur front appartient à une file.
Une file dans un tableau simple
- Deux pointeurs :
Frontpour le prochain élément à partir,Rearpour le prochain espace libre. Enqueue stocke àRearet le déplace ; dequeue lit àFrontet le déplace. - Les deux pointeurs ne bougent jamais qu'en avant, donc après quelques opérations ils marchent hors de fin du tableau tandis que les cellules au début restent vides et inutilisables.
- La solution est de laisser les pointeurs faire un tour.
Le tableau circulaire
- Un tableau circulaire renvoie un pointeur à la première cellule lorsqu'il dépasse la dernière : avec des indices basés sur 1,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x) : vérifier non plein ;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue() : vérifier non vide ; retournerQueue[Front];Front ← (Front MOD MaxSize) + 1. - Garder un count séparé : quand la file est complètement pleine et complètement vide, les deux pointeurs sont dans la même position relative, donc les pointeurs seuls ne peuvent pas les distinguer.

Après la dernière cellule vient la première cellule
Implémenter des TADs avec des tableaux
FIFO
Une fichier est premier-entré-premier-sorti — enfiler à l'arrière, défiler depuis le devant.
Pourquoi utiliser un tableau circulaire pour une file ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Une file linéaire gaspille les cases au début quand Front avance ; le tournant avec MOD les réutilise.
Une file circulaire utilise MOD pour que les pointeurs front/rear fassent le tour et réutilisent les cases libérées au début du tableau.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
(pointer MOD MaxSize) + 1 ramène l'index à la première case, afin qu'une file linéaire ne gaspille plus les cases que Front a dépassées.
Exemple résolu : parcourir les pointeurs
- Avec
MaxSize = 6: siRear = 5, alors(5 MOD 6) + 1 = 6, donc le prochain élément va dans la cellule 6. SiRear = 6, alors(6 MOD 6) + 1 = 1: le pointeur fait un tour vers la cellule 1. - Une file circulaire est contenue dans un tableau de taille 5, indices 0 à 4, avec
Front = 3,Rear = 3et un élément stocké. Deux éléments sont ajoutés, puis deux retirés. Avec indices 0-based chaque mouvement est(pointer + 1) MOD 5. - Ajouter deux fois déplace
Rear: 3 → 4, puis 4 → 0, parce que (4 + 1) MOD 5 = 0. Retirer deux fois déplaceFront: 3 → 4 → 0. Un élément reste, à l'index 0, et la file a réutilisé les cellules libérées au début du tableau.
Une file circulaire utilise les cases 1 à 6 et Rear = 6. Après Rear ← (Rear MOD 6) + 1, où va le prochain élément ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
6 MOD 6 = 0, plus 1 donne 1. Le pointeur fait le tour vers le début du tableau.
Exemple résolu : l'algorithme d'enqueue en mots
- Décrire l'algorithme pour ajouter un élément à une file circulaire. [4]
- Si count égale size, rapport que la file est pleine et arrêter.
- Sinon ajouter un au pointeur rear ; s'il est maintenant passé le dernier index, le fixer au premier index.
- Stocker l'élément au pointeur rear et ajouter un à count.
Mettez les étapes d'ajout dans une file circulaire dans l'ordre.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Vérifier, déplacer, tourner, stocker, compter. Le tournant rend le tableau circulaire.
Une liste chaînée dans un tableau
- Utilisez un tableau d'enregistrements de nœuds, chacun avec un index de
NextIndex;-1marque la fin. Un index deHeadmarque le premier nœud,-1si la liste est vide. - Les cases inutilisées sont chaînées dans une liste libre à partir de
FreeListHead, exactement comme la liste de données chaîne ses éléments utilisés.
TYPE TNode
DECLARE Value : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- Insertion : prendre la case à
FreeListHead, définir sonValueetNextIndex, puis rewire leNextIndexdu nœud précédent ouHead. Suppression : délier le nœud et retourner sa case au début de la free list.

Deux listes partagent un tableau : la liste de données et la free list
Dans une liste chaînée à base de tableau, la liste libre :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
La liste libre relie les emplacements disponibles, donc une insertion peut en prendre une et une suppression peut en retourner une — comme une seconde liste chaînée de vides.
Exemple résolu : insérer dans la liste tenue par tableau
DataetPointertableaux tiennent la liste 1 → 3 → 4, avecStart = 1; index 1 contientD40, index 3 contientD32, index 4 contientD11avec un pointeur null. La free list commence à index 2 et continue 2 → 5. InsérerD6entreD32etD11.- Prendre le premier nœud libre, index 2, et définir
FreeStartvers son pointeur, 5. StockerD6dansData[2]. - Définir
Pointer[2]sur la valeurPointer[3]tenue, qui est 4. Puis définirPointer[3]sur 2. - La liste se lit maintenant 1 → 3 → 2 → 4 et la free list est 5 → null. L'implémentation, si demandée : un tableau pour les données, un tableau parallèle (ou champ record) pour les pointeurs, un pointeur de départ, et un pointeur de free-list.
Dans l'exemple résolu, après l'insertion de D6, la liste libre commence à l'indice ____.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
L'indice 2 a été pris de la liste libre, donc FreeStart passe à ce que l'indice 2 pointait, qui était 5.
Lors de l'insertion dans la liste, le pointeur du nœud précédent doit être modifié avant que le pointeur du nouveau nœud ne soit défini.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Définissez d'abord le pointeur du nouveau nœud sur l'ancien nœud suivant. Rebrancher le nœud précédent en premier fait perdre l'adresse du reste de la liste.
Points qui glissent
- Les vérifications viennent en premier : plein avant push ou enqueue, vide avant pop ou dequeue. Les décrire ; ce sont des points.
- La formule de wrap dépend des indices :
(Rear MOD MaxSize) + 1pour 1-based,(Rear + 1) MOD Sizepour 0-based. Correspondre aux bornes de la question. - Le count est ce qui distingue une file circulaire pleine d'une vide. Les pointeurs seuls ne le peuvent pas.
- Définir le
NextIndexdu nouveau nœud avant de rewire le nœud précédent, et retourner la case d'un nœud supprimé à la free list, sinon le tableau se remplira lentement de cases inaccessibles.
Vous avez compris
- pile dans un tableau :
Stack[1:MaxSize]et unToppointeur commençant à 0 ;Top = MaxSizeest overflow,Top = 0est underflow - file circulaire :
FrontetRearfont un tour avecMOD; un count séparé distingue plein de vide - liste chaînée dans un tableau : records de nœuds avec un
NextIndexindex, unHead, et une free list enchaînant les cases libres - chaque opération est check, ensuite arithmétique de pointeur, ensuite store ou read ; le comportement de l'ADT est inchangé par la façon dont il est stocké