Tableaux

4.1 Définition d'un tableau et ses propriétés

Un tableau est une structure de données qui représente un ensemble ordonné d'éléments d'un seul type, situés dans des cellules de mémoire contiguës. Chaque élément du tableau a un indice unique qui est utilisé pour y accéder.

Ici, un simple tableau de taille 4 contenant les éléments (1, 2, 3 et 4) est montré.

Propriétés du tableau :

• Taille fixe : La taille du tableau est définie lors de sa création et ne peut pas être modifiée pendant l'exécution du programme.
• Homogénéité des éléments : Tous les éléments du tableau doivent être du même type (par exemple, des entiers, des chaînes).
• Disposition séquentielle en mémoire : Les éléments du tableau sont stockés dans des cellules de mémoire contiguës, ce qui permet un accès rapide par indice.
• Accès rapide par indice : L'accès à n'importe quel élément du tableau se fait en temps constant O(1).

4.2 Exemples d'utilisation des tableaux

Voyons des exemples d'utilisation des tableaux que tu connais déjà peut-être :

Stockage de données de longueur fixe

Jours de la semaine, mois de l'année :

# Création d'un tableau avec les jours de la semaine
days_of_week = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
print(days_of_week[2])  # Sortie : Wednesday

Matrices et tableaux multidimensionnels

Matrice 3x3 :

# Création d'une matrice 3x3
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(matrix[1][1])  # Sortie : 5

Utilisation dans les algorithmes de tri

Tri d'un tableau de nombres :

# Tri d'un tableau de nombres
numbers = [5, 2, 9, 1, 5, 6]
numbers.sort()  # Tri du tableau
print(numbers)  # Sortie : [1, 2, 5, 5, 6, 9]

Buffer pour stocker des données temporaires

Buffer pour lire des données à partir d'un fichier :

# Création d'un buffer de taille 1024 octets
buffer = [0] * 1024
print(len(buffer))  # Sortie : 1024

4.3 Principales opérations avec les tableaux

Important ! La classe list en Python est un tableau dynamique, elle peut changer de taille pendant l'exécution. Tu en apprendras plus sur les tableaux dynamiques dans quelques conférences.

Principales opérations : accès par indice, insertion, suppression

Accès par indice

L'accès à un élément du tableau se fait à l'aide d'un indice qui indique sa position.

# Accès aux éléments du tableau par indice
arr = [10, 20, 30, 40, 50]
print(arr[2])  # Sortie : 30
print(arr[-1])  # Sortie : 50 (dernier élément)

Insertion

L'insertion d'un élément dans un tableau peut nécessiter le déplacement de tous les éléments suivants pour libérer de l'espace pour le nouvel élément.

Exemple (insertion d'un élément au milieu du tableau) :

# Insertion d'un élément dans un tableau
arr = [10, 20, 30, 40, 50]
arr.insert(2, 25)  # Insertion de 25 à la position 2
print(arr)  # Sortie : [10, 20, 25, 30, 40, 50]

Suppression

La suppression d'un élément d'un tableau peut nécessiter le déplacement de tous les éléments suivants pour combler l'espace libéré.

Exemple (suppression d'un élément) :

# Suppression d'un élément d'un tableau
arr = [10, 20, 30, 40, 50]
arr.pop(2)  # Suppression de l'élément à la position 2
print(arr)  # Sortie : [10, 20, 40, 50]

4.4 Avantages et inconvénients de l'utilisation des tableaux

Voyons les avantages et les inconvénients de l'utilisation des tableaux :

Avantages :

• Accès rapide par indice : L'accès à n'importe quel élément du tableau se fait en temps constant O(1), ce qui rend les tableaux très efficaces pour la lecture de données.
• Simplicité de mise en œuvre : Les tableaux sont simples à comprendre et à utiliser, ils sont faciles à mettre en œuvre et à appliquer à diverses tâches.
• Faibles surcoûts : Les tableaux occupent moins de mémoire par rapport à des structures de données plus complexes comme les listes chaînées.

Inconvénients :

• Taille fixe : La taille du tableau est définie lors de sa création et ne peut pas être modifiée. Cela signifie qu'il faut connaître à l'avance la taille nécessaire du tableau ou utiliser des tableaux dynamiques qui peuvent croître selon les besoins.
• Coût d'insertion et de suppression : L'insertion et la suppression d'éléments peuvent être coûteuses en temps car elles nécessitent le déplacement des éléments. Dans le pire des cas, l'insertion ou la suppression d'un élément au milieu d'un tableau prend O(n) temps.
• Utilisation inefficace de la mémoire : Si le tableau n'est pas entièrement utilisé, les cellules de mémoire restantes restent inoccupées, ce qui peut conduire à une utilisation inefficace de la mémoire.