Structure de données linéaires

Les exercices taggés du symbole sont à faire sur machine.

Les exercices taggés du symbole doivent être résolus par écrit.

On choisit l'implémentation des listes avec des tuples:

🐍 Script Python
""" Implémentation du type abstrait "liste" avec des tuples"""

def creer() -> tuple:
    """Retourne une liste vide"""
    return ()


def ajouter(element: all, liste: tuple) -> tuple:
    """Retourne la liste avec l'élément ajouté en tête de liste"""
    return (element, liste)


def est_vide(liste: tuple) -> bool:
    """Retourne True si la liste est vide et False sinon"""
    return liste == ()


def tete(liste: tuple) -> all:
    """Retourne la tête de la liste"""
    assert not est_vide(liste), "Erreur : liste vide"
    return liste[0]


def queue(liste: tuple) -> tuple:
    """Retourne la queue de la liste"""
    assert not est_vide(liste), "Erreur : liste vide"
    return liste[1]


def longueur(liste: tuple) -> int:
    """Retourne le nombre d'éléments de la liste"""
    if est_vide(liste):
        return 0
    else:
        return 1 + longueur(liste[1])

Prévoir l'effet et l'affichage en console des instructions suivantes, puis vérifier en exécutant ces instructions dans la console interactive après avoir créé et importé un fichier contenant le code du cours :

🐍 Console Python
>>> L = creer()
>>> est_vide(L)
>>> L = ajouter(5, ajouter(4, ajouter(3, ajouter(2, ajouter(1, ajouter(0,()))))))
>>> est_vide(L)
>>> longueur(L)
>>> L = ajouter(6,L)
>>> longueur(L)
>>> tete(L)
>>> queue(L)
>>> longueur(queue(L))

Soit la suite d'instructions suivantes :

🐍 Script Python
L = creer()
L = ajouter(2, ajouter(15, ajouter (23, L)))
L1 = queue(L)
a = tete(L1)
L1 = ajouter(4, ajouter(3, L1))

Donnez le contenu des listes L et L1 et la valeur de a.

Soit une pile P initialement vide. Soit les instructions suivantes (implémentation des piles avec des listes Python) :

🐍 Console Python
>>> empiler(P,4)
>>> empiler(P,7)
>>> a = depiler(P)
>>> b = taille(P)
>>> c = depiler(P)
>>> empiler(P,3)
>>> empiler(P,2)
>>> d = taille(P)

Donnez le contenu de la pile P, la valeur de a, la valeur de b, la valeur de c et la valeur de d.

Soit le programme Python suivant (on utilise l'implémentation des piles en POO) :

🐍 Script Python
pile = Pile()
tab = [5,8,6,1,3,7]
for k in tab:
    pile.empiler(k)
pile.empiler(5)
pile.empiler(10)
pile.empiler(8)
pile.empiler(15)
for k in tab:
    if k > 5:
        pile.depiler()

Donnez l'état de la pile pile après l'exécution de ce programme.

Ce problème propose une application concrète des piles. Il s'agit d'écrire une fonction qui contrôle si une expression mathématique, donnée sous forme d'une chaîne de caractères, est bien parenthésée, c'est- à-dire s'il y a autant de parenthèses ouvrantes que de fermantes, et qu'elles sont bien placées

Par exemple :

  • (..(..)..) est bien parenthésée
  • (...(..(..)...) ne l'est pas

L'algorithme :

📋 Texte
* On crée une pile
* On parcourt l'expression de gauche à droite.
* À chaque fois que l'on rencontre une parenthèse ouvrante "( " on l'empile
* Si on rencontre une parenthèse fermante " ) " et que la pile n'est pas vide on dépile ( sinon
on retourne faux )
* À la fin la pile doit être vide...
  1. En utilisant l'une des structures pile du cours, écrire une fonction verification(expr) qui vérifie si une expression mathématique passée en paramètre est correctement parenthésée.
  2. Faire en sorte que le programme tienne compte également des [.

Soit une file F initialement vide. Soit les instructions suivantes :

🐍 Script Python
enfiler(F,6)
enfiler(F,3)
a = defiler(F)
enfiler(F,9)
b = taille_file(F)
enfiler(F,17)
c = defiler(F)
enfiler(F,2)
d = taille_file(F)

Donnez le contenu de la file F, la valeur de a, la valeur de b, la valeur de c et la valeur de d.

Soit le programme Python suivant :

🐍 Script Python
file = File()
tab = [2,78,6,89,3,17]
file.enfiler(5)
file.enfiler(10)
file.enfiler(8)
file.enfiler(15)
for i in tab:
    if i > 50:
        file.defiler()

Donnez l'état de la file file après l'exécution de ce programme

Les exercices au bac