Tableau de capacité fixe¶

Tableau de capacité fixe

In [2]:

class Tableau:   
    def __init__(self,capacite):
        
        self.data = [None]*capacite
        
        self.capacite = capacite
        
        self.taille = 0
        
# Methodes de tableau de taille fixe
    __str__     = h.convertir_en_texte
    __len__     = h.taille
    __getitem__ = h.lire_valeur
    __setitem__ = h.ecrire_valeur

La taille variable permet d'ajouter 4 modificateurs

inserer_en_queue

supprimer_en_queue

inserer_en_position

supprimer_en_position

Avant d'insérer, il faut vérifier si la capacité est suffisante pour insérer n éléments

In [3]:

def capacite_suffisante(T,n = 1):
    
    return T.taille + n <= T.capacite

Insertion en queue¶

vérifier si la capacité est suffisante
écrire dans le premier emplacement libre
incrémenter la taille

In [4]:

def inserer_en_queue(T,valeur): 
    if not capacite_suffisante(T):
        raise Exception("")
        
    T.data[T.taille] = valeur
    T.taille += 1

In [5]:

T = Tableau(4); print(T)

try:
    while True:
        inserer_en_queue(T,T.taille)
        print(T)

except Exception: print("Tableau plein")

T(0/4): [None, None, None, None]
T(1/4): [0, None, None, None]
T(2/4): [0, 1, None, None]
T(3/4): [0, 1, 2, None]
T(4/4): [0, 1, 2, 3]
Tableau plein

Suppression en queue¶

vérifier que le tableau n'est pas vide
retirer l'élément en dernière position
décrémenter la taille

In [6]:

def supprimer_en_queue(T): 
    if len(T)==0: 
        raise IndexError("")
        
    T.taille -= 1
    T.data[T.taille] = None

In [7]:

T = Tableau(4)
for i in range(4):
    inserer_en_queue(T,i*i)
print(T)

try:
    while True:
        supprimer_en_queue(T); 
        print(T)
except IndexError: print("Tableau vide")

T(4/4): [0, 1, 4, 9]
T(3/4): [0, 1, 4, None]
T(2/4): [0, 1, None, None]
T(1/4): [0, None, None, None]
T(0/4): [None, None, None, None]
Tableau vide

Suppression à l'indice `i`¶

vérifier si l'indice est valide
déplacer vers la gauche les éléments suivants
décrémenter la taille

Et selon le language de programmation, détruire l'élément excédentaire.

In [8]:

def indice_valide(T,indice):
    
    return indice >= 0 and indice < T.taille

In [9]:

def supprimer_en_position(T,ind):
    if not indice_valide(T,ind):
        raise IndexError("")
    
    for i in range(ind,T.taille-1):
        T.data[i] = T.data[i+1]
        
    T.taille -= 1
    
    T.data[T.taille] = None

In [25]:

T = Tableau(5)
for i in range(5): inserer_en_queue(T,i*i)
print(T)

try:
    supprimer_en_position(T,1); print(T)
    supprimer_en_position(T,2); print(T)
    supprimer_en_position(T,3); print(T)
    
except IndexError: print("Indice invalide")

T(5/5): [0, 1, 4, 9, 16]
T(4/5): [0, 4, 9, 16, None]
T(3/5): [0, 4, 16, None, None]
Indice invalide

Insertion à l'indice `i`¶

vérifier si la capacité est suffisante
vérifier si la position est valide
libérer l'emplacement demandé
écrire dans l'emplacement libéré
incrémenter la taille

In [11]:

def indice_insertion_valide(T,indice):
    return indice >= 0 and indice <= T.taille

In [12]:

def inserer_en_position(T,indice,valeur):
    if not capacite_suffisante(T): 
        raise Exception("")
    if not indice_insertion_valide(T,indice):
        raise IndexError("")
    
    for i in range(T.taille,indice,-1):
        T.data[i] = T.data[i-1]
        
    T.data[indice] = valeur
    
    T.taille += 1

In [13]:

try:
    T = Tableau(5)
    inserer_en_position(T,0,1); print(T)
    inserer_en_position(T,0,2); print(T)
    inserer_en_position(T,2,3); print(T)
    inserer_en_position(T,1,4); print(T)
    inserer_en_position(T,5,5); print(T)
except IndexError: print("Indice invalide")

T(1/5): [1, None, None, None, None]
T(2/5): [2, 1, None, None, None]
T(3/5): [2, 1, 3, None, None]
T(4/5): [2, 4, 1, 3, None]
Indice invalide

In [14]:

try: 
    while True:
        inserer_en_position(T,1,6)
        print(T)
        
except Exception: print("Tableau plein")

T(5/5): [2, 6, 4, 1, 3]
Tableau plein

Opérations en tête¶

In [15]:

def inserer_en_tete(T,valeur):
    
    inserer_en_position(T,0,valeur)

In [16]:

def supprimer_en_tete(T):
    
    supprimer_en_position(T,0)

Complexités¶

Opérations en queue: $\Theta(1)$

Opérations en position quelconque: $\Theta(m)$ avec $m$ la distance entre la position d'insertion et la taille.

Insérer loin de la queue est donc très inefficace

En C++¶

Ces opération s'appèlent push_back, pop_back, insert et erase.

En python¶

Ces opérations s'appelent append, insert et pop. Cette dernière a pour valeur par défaut la queue du tableau

In [19]:

T = [ 1, 3, 5, 7, 9 ]; print(T)

T.append(11); print(T)

T.pop(2); print(T)

T.insert(3,42); print(T)

T.pop(); print(T)

[1, 3, 5, 7, 9]
[1, 3, 5, 7, 9, 11]
[1, 3, 7, 9, 11]
[1, 3, 7, 42, 9, 11]
[1, 3, 7, 42, 9]

ASD1 Notebooks on GitHub.io