Listes-Piles-Files
Partie 3: Liste personnalisée
Dans cette partie, vous allez créer une liste personnalisée à partir du type objet List de python.
Votre liste sera capable de contenir n éléments dans un tableau de taille fixe contenant n+1 cases. La première case ( indice 0) contiendra le nombre d'éléments présents dans la liste et les cases suivantes contiendront les éléments (ou des cases vides qui contiendront 0). Par exemple, la liste [ 8, 5, 2] placée dans une tableau de 6 cases serait représentée ainsi:
Le 3 de la case 0 correspond au nombre d'éléments de la liste.
La liste peut contenir jusqu'à 5 éléments.
On vous donne ci-dessous le pseudo-code qui permet d'insérer un élément dans cette liste:
fonction insérer ( L, x, i):
''' ajoute l'élément x dans la liste L à l'emplacement i, la liste L peut contenir n éléments, la longueur max de L est n+1 '''
Si L[0] == longueur max de L ou i-1 > L[0]:
retourner Faux
Sinon:
# on parcourt le tableau à l'envers à partir de L[0]+1 ce qui demande un pas -1
pour k allant de L[0]+1 à i par pas de -1:
L[k] = L[k-1]
L[i] = x
L[0] = L[0] + 1
retourner Vrai
Question 3.1
- Coder la fonction insérer en python, créer un tableau de 6 cases, ajouter les nombres 8 puis 5 puis 2 dans votre tableau avec la fonction insérer. Afficher le tableau.
- ajouter maintenant le nombre "2" à l'emplacement 1 du tableau. Afficher le tableau. Expliquer comment est traitée l'insertion d'un élément lorsque l'emplacement n'est pas vide notamment que deviennent les autres éléments du tableau dans ce cas.
Partie 4: Liste chaînée ( exercice compliqué pour les costauds)
Création d'une liste chaînée en utilisant la Programmation Orientée Objet
On vous propose la classe Cellule qui permet de créer un maillon de liste chaînée:
class Cellule:
""" construit une cellule de liste chaînée """
def __init__( self, valeur, adresse_cellule_suivante):
self.valeur = valeur
self.suite_liste = adresse_cellule_suivante
Question 4.1
Construire la liste [ 1, 2, 3 , 4] sous forme d'une liste chaînée, vous appellerez votre liste "une_liste"
On dispose de la fonction récursive longueur_liste(la_liste) qui prend en paramètre une liste chaînée. Cette fonction renvoie le nombre de cellules de la liste_chaînée passée en paramètre:
def longueur_liste( la_liste) :
""" renvoie le nombre de cellule de la liste"""
# si la liste est vide :
if la_liste is None :
return 0
else:
return 1 + longueur_liste(la_liste.suite_liste)
Question 4.2
Dessiner les appels récursifs si on applique cette fonction à la liste chaînée de la question 1. Peut-on conclure que la fonction est correcte (renvoie la bonne valeur) ?
Question 4.3
Modifier la fonction longueur_liste pour qu'elle puisse devenir une méthode de la classe Cellule. Ecrire un code qui permette de tester votre méthode.
Question 4.4
Ecrire une fonction qui permettent d'ajouter une cellule en fin de la liste chaînées.
Question 4.5
Ecrire une fonction valeur_element_indice_k(k, une_liste_chainée) qui permettent de renvoyer l'élément d'indice k passé en paramètre d'une liste chaînée également passée en paramètre.
Question 4.6
Ecrire une fonction renverser(une_liste_chainée) qui permettent de renverser les éléments de la liste chaînée passée en paramètre ( pour une liste classique L = [1,2,3] le renversement voudrait dire que L deviendrait [3,2,1], ici c'est à concevoir pour une liste chaînée)
Question 4.7
Ecrire une fonction concaténer (une_liste_chainée_1, une_liste_chainée_2) qui permettent de concaténer deux listes chaînées passées en paramètres.
( appliquée à deux listes classiques L1=[1,2,3] et L2 = [4,5,6], une concaténation donnerait L = [1,2,3,4,5,6], ici c'est à concevoir pour des listes chaînées )
Créé avec HelpNDoc Personal Edition: Produire des livres Kindle gratuitement