Informatique au lycée Faustin Fleret

Entrainement 1:

Identififer l'adresse de stockage des données pour les variables a = 1 b et b = 2 avec la méthode python id(a)

Dans une liste chaînée, il est impossible de connaître à l’avance l’adresse d’une case en particulier, à l’exception de la première. Pour accéder à la n^ème case il faut donc parcourir les n − 1 précédentes : le coût de l’accès à une case est proportionnelle à la distance qui la sépare de la tête de la liste. En contrepartie, ce type de structure est dynamique : une fois la liste crée, il est toujours possible de modifier un pointeur pour insérer une case supplémentaire.

Contrairement à ce que pourrait laisser croire son nom, la classe list en python n’est pas une liste chaînée au sens qu’on vient de lui donner, mais une structure de donnée plus complexe qui cherche à concilier les avantages des tableaux et des listes chaînées.

La liste est constituée de trois cellules, représentées ici par des rectangles.
Chaque cellule possède une première partie (la tête), nommée car(CAR (Contents of Address Register) : le premier élément de la liste), qui contient l’entier correspondant, et d’une deuxième partie (la queue), nommée cdr (CDR (Contents of Decrement Register) : le reste de la liste), qui contient un lien vers la cellule suivante. On a donc affaire à une chaîne de cellules, ce qui justifie la dénomination courante de liste chaînée. Le champ cdr de la dernière cellule renvoie vers une liste vide, conventionnellement représentée par un hachurage (NIL : Abréviation du latin nihil, rien).

Le premier champ d’une cellule contient ici un entier (car on considère une liste d’entiers) alors que le deuxième est une liste, c’est-à-dire un lien vers une autre cellule.

Voici les opérations qui peuvent être effectuées sur une liste :

L,L1,L2 = vide()
ajoute_entete(4,L)
ajoute_entete(9,L)
ajoute_entete(2,L)
suppr_entete(L)
L1 = vide()
L2 = cons(19, cons(4, cons(10, cons (2, cons(6, cons(0,L1)))))

Implémentation en python

def creer_liste():
    """création d'une liste"""
    return []

def est_vide(liste):
    """teste si liste est vide et renvoie le booléen obtenu"""
    return (liste == [])

def ajoute_entete(e,liste):
    """ajouter un élément e en tête de liste liste"""
    liste.insert(0,e)

def suppr_entete(file):
    """identique à file.pop(0)"""
    del file[0]

def taille(liste):
    """Renvoie le nombre d'élément de la liste"""
    return len(liste)

def get(i,liste):
    """Renvoie le ième élément de la liste"""
	return liste[i]

#########################################################
liste = creer_file()
ajoute_entete(1,f)
print(f)
ajoute_entete(2,f)
ajoute_entete(3,f)
print(f)
est_vide(f)
suppr_entete(f)
print(f)
suppr_entete(f)
suppr_entete(f)
print(f)
print(est_vide(f))

Les piles

Les piles sont fondées sur le principe du « dernier arrivé, premier sorti » ; on les dit de type LIFO (Last In,First Out). C’est le principe même de la pile d’assiette : c’est la dernière assiette posée sur la pile d’assiettes sales qui sera la première lavée.

Une réalisation concrète de la structure pile doit fournir dans l’idéal :

P= creer_pile_vide()
empiler(P,3)
empiler(P,2)
N = depiler(P)
empiler(P,5)
empiler(P,7)
empiler(P,9)

Implémentation en python

def creer_pile_vide():
    """création de la pile vide"""
    return []

def est_vide(pile):
    """teste si pile est vide et renvoie le booléen obtenu."""
    return (pile == [])

def taille (pile):
    """Renvoie le nombre d'élément de la pile"""
    return len(pile)

def depiler(pile):
    """depile l'élément x sur la pile pile
    pile.pop()"""
    if est_vide(pile):
        return print("la pile est déjà vide") 
    else:
        del pile[-1]# on depile


def empiler(pile,e):
    """empile l'élément x sur la pile p
        pile.append(e)
        """
    pile[len(pile):] = [e]# on empile

def sommet(pile):
    """renvoie le sommet de la pile"""
    return pile[-1]


p = creer_pile_vide()
est_vide(p)
empiler(p,1)
empiler(p,2)
empiler(p,3)
print(p)
print(est_vide(p))
depiler(p)
print(p)
print(sommet(p))

Les Files

Les files sont fondées sur le principe du « premier arrivé, premier sorti » ; on les dit de type FIFO (First In,First Out). C’est le principe de la file d’attente devant un guichet.

Une réalisation concrète de ces structures doit fournir dans l’idéal :

• une fonction de création d’une file vide ;
• deux fonctions d’ajout et de suppression;
• une fonction vérifiant si une file est vide.

on peut réaliser les opération ssuivantes sur un objet de type File:

F = creer_file_vide()
enfiler(F,3)
enfiler(F,2)
N = defiler(F)
enfiler(F,5)
enfiler(F,7)
enfiler(F,9)

Implémentation en python

###########################################
#Extrait de la documentation python
from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry")           # Terry arrives
queue.append("Graham")          # Graham arrives
queue.popleft()                 # The first to arrive now leaves
print(queue)
queue.popleft()                 # The second to arrive now leaves
print(queue)                    # Remaining queue in order of arrival
print("-----------------------------------------")


##################################################################

def creer_file():
    """création de la file"""
    return[]

def est_vide(file):
    """teste si file est vide et renvoie le booléen obtenu"""
    return (file == [])

def enfiler(e,file):
    """file.append(e)"""
    file[len(file):] = [e]

def defiler(file):
    """return file.pop(0)"""
    del file[0]

def longeur(file):
    """Renvoie le nombre d'élément de la file"""
    return len(file)

#########################################################
f= creer_file()
enfiler(1,f)
print(f)
enfiler(2,f)
enfiler(3,f)
print(f)
est_vide(f)
defiler(f)
print(f)
defiler(f)
defiler(f)
print(f)
print(est_vide(f))