3.1 Opérations sur les données: insertion, suppression, recherche
Insertion (Insert):
Opération d'ajout d'un nouvel élément dans une structure de données. L'insertion peut se faire au début, à la fin ou à une position arbitraire de la structure de données.
Suppression (Delete):
Opération de suppression d'un élément d'une structure de données. La suppression peut se faire par la valeur de l'élément, par l'index ou par la position de l'élément dans la structure de données.
Recherche (Search):
Opération de localisation d'un élément dans une structure de données. La recherche peut se faire par valeur ou selon d'autres critères.
Exemples d'opérations :
- Tableaux: Insertion et suppression nécessitent le déplacement des éléments, ce qui peut être coûteux en temps —
O(n). - Listes chaînées: Insertion et suppression peuvent s'effectuer en
O(1)si la position du nœud est connue. - Hash tables: Recherche, insertion et suppression se font généralement en
O(1)en moyenne. - Arbres: Les opérations de recherche, d'insertion et de suppression peuvent se faire en
O(log n)dans des arbres équilibrés.
3.2 Concepts de base: tableau, liste, pile, file d'attente
Tableau
Tableau — c'est une séquence d'éléments du même type, accessible via un index.
Complexité des opérations : Accès par index — O(1), insertion et suppression — O(n).
Exemple : Création d'un tableau, modification d'un élément et affichage du résultat
# Création d'un tableau de nombres
arr = [1, 2, 3, 4, 5]
# Modifier l'élément à l'index 2 (troisième élément, car l'indexation commence à 0)
arr[2] = 10
# Afficher le tableau modifié
print(arr) # Affiche : [1, 2, 10, 4, 5]
# Ajouter un nouvel élément à la fin du tableau
arr.append(6)
print(arr) # Affiche : [1, 2, 10, 4, 5, 6]
# Supprimer un élément par index
del arr[1]
print(arr) # Affiche : [1, 10, 4, 5, 6]
Liste
Liste — c'est une collection d'éléments où chaque élément contient un lien vers le suivant (liste simplement chaînée) ou vers le suivant et le précédent (liste doublement chaînée).
Complexité des opérations : Insertion et suppression — O(1) si la position est connue, recherche — O(n).
Exemple : Création d'une simple liste simplement chaînée et son parcours
# Définir la structure d'un nœud de liste
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Création d'une liste simplement chaînée
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")
# Lier les nœuds
node1.next = node2
node2.next = node3
# Définir le début de la liste
list_head = node1
# Parcourir la liste et afficher les données
current = list_head
while current:
print(current.data)
current = current.next
# Affichage :
# 101
# 102
# 103
Stack (Pile)
Stack — c'est une collection d'éléments avec le principe LIFO (Last In, First Out): le dernier ajouté est le premier sorti.
Complexité des opérations : Insertion (push) et suppression (pop) — O(1).
Exemple : Implémentation et utilisation d'une pile pour vérifier l'équilibrage des parenthèses
def is_balanced(expression):
stack = []
opening = "({["
closing = ")}]"
pairs = {")": "(", "}": "{", "]": "["}
for char in expression:
if char in opening:
stack.append(char)
elif char in closing:
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
# Tester différentes expressions
print(is_balanced("({[]})")) # Affiche : True
print(is_balanced("([)]")) # Affiche : False
print(is_balanced("((")) # Affiche : False
Queue (File d'attente)
Queue — c'est une collection d'éléments avec le principe FIFO (First In, First Out): le premier ajouté est le premier sorti.
Complexité des opérations : Insertion (enqueue) et suppression (dequeue) — O(1).
Exemple : Implémentation et utilisation d'une file d'attente pour simuler le traitement des tâches
from collections import deque
class TaskQueue:
def __init__(self):
self.queue = deque()
def add_task(self, task):
self.queue.append(task)
print(f"Tâche '{task}' ajoutée à la file d'attente")
def process_task(self):
if self.queue:
task = self.queue.popleft()
print(f"Traitement de la tâche : '{task}'")
else:
print("La file d'attente est vide")
def display_queue(self):
print("File d'attente actuelle des tâches :", list(self.queue))
# Créer et utiliser une file d'attente de tâches
task_queue = TaskQueue()
task_queue.add_task("Envoyer un email")
task_queue.add_task("Mettre à jour la base de données")
task_queue.add_task("Créer un rapport")
task_queue.display_queue()
task_queue.process_task()
task_queue.process_task()
task_queue.display_queue()
# Affiche :
# Tâche 'Envoyer un email' ajoutée à la file d'attente
# Tâche 'Mettre à jour la base de données' ajoutée à la file d'attente
# Tâche 'Créer un rapport' ajoutée à la file d'attente
# File d'attente actuelle des tâches : ['Envoyer un email', 'Mettre à jour la base de données', 'Créer un rapport']
# Traitement de la tâche : 'Envoyer un email'
# Traitement de la tâche : 'Mettre à jour la base de données'
# File d'attente actuelle des tâches : ['Créer un rapport']
3.3 Différences entre les différents types de structures de données
Voici les principales différences entre les différents types de structures de données :
Tableaux :
- Accès : Accès rapide par index —
O(1). - Changement de taille : Taille fixe, l'augmentation nécessite de copier tous les éléments —
O(n). - Adapté à : Accès aléatoire aux éléments, lorsque la taille des données est connue à l'avance.
Listes chaînées :
- Accès : Accès lent par index —
O(n). - Changement de taille : Taille facilement modifiable, insertion et suppression prennent
O(1). - Adapté à : Ajout et suppression fréquents d'éléments.
Stack :
- Principe de fonctionnement :
LIFO. - Opérations : Insertion et suppression à une seule extrémité —
O(1). - Adapté à : Gestion des tâches dans l'ordre inverse, gestion des appels de fonctions.
Queue :
- Principe de fonctionnement :
FIFO. - Opérations : Insertion et suppression à des extrémités différentes —
O(1). - Adapté à : Gestion des tâches dans l'ordre de leur arrivée.
3.4 Applications des différentes structures de données
Exemples d'application des différentes structures de données en pratique :
Tableaux
Stockage de données de longueur fixe, comme les jours de la semaine ou les mois de l'année.
Exemple: Utilisation d'un tableau pour gérer les jours de la semaine
# Créer un tableau avec les jours de la semaine
days = ["Lundi", "Mardi", "Mercredi", "Jeudi", "Vendredi", "Samedi", "Dimanche"]
# Obtenir le jour de la semaine par index (par exemple, le troisième jour)
print(days[2]) # Affiche : Mercredi
# Modifier le nom du jour
days[0] = "Lundi (début de semaine)"
print(days[0]) # Affiche : Lundi (début de semaine)
# Parcourir tous les jours de la semaine
for day in days:
print(day)
# Affichage :
# Lundi (début de semaine)
# Mardi
# Mercredi
# Jeudi
# Vendredi
# Samedi
# Dimanche
Listes chaînées
Implémentation de collections dynamiques, où les éléments peuvent être ajoutés et supprimés du milieu de la collection.
Exemple: Implémentation et utilisation d'une liste chaînée pour stocker une liste de tâches
class TodoItem:
def __init__(self, task):
self.task = task
self.next = None
class TodoList:
def __init__(self):
self.head = None
def add_task(self, task):
new_item = TodoItem(task)
if not self.head:
self.head = new_item
else:
current = self.head
while current.next:
current = current.next
current.next = new_item
def display_tasks(self):
current = self.head
if not current:
print("La liste de tâches est vide")
else:
while current:
print(f"- {current.task}")
current = current.next
# Créer et utiliser une liste de tâches
todo = TodoList()
todo.add_task("Acheter des provisions")
todo.add_task("Appeler maman")
todo.add_task("Préparer une présentation")
print("Ma liste de tâches:")
todo.display_tasks()
# Affichage :
# Ma liste de tâches:
# - Acheter des provisions
# - Appeler maman
# - Préparer une présentation
Stack
Exécution des tâches dans l'ordre inverse, par exemple, traitement des appels de fonction en récursion, annulation d'opérations (undo).
Exemple: Utilisation d'une pile pour inverser une chaîne de caractères
def reverse_string(s):
stack = []
# Mettre chaque caractère de la chaîne dans la pile
for char in s:
stack.append(char)
reversed_s = ''
# Extraire les caractères de la pile, formant ainsi la chaîne inversée
while stack:
reversed_s += stack.pop()
return reversed_s
# Exemple d'utilisation
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"Chaîne originale: {original}")
print(f"Chaîne inversée: {reversed_str}")
# Affichage :
# Chaîne originale: Hello, World!
# Chaîne inversée: !dlroW ,olleH
Queue
Gestion des tâches dans l'ordre de leur arrivée, par exemple, les tâches d'impression, les files d'attente dans le service client.
Exemple: Simulation d'une file d'attente d'impression de documents
from collections import deque
class PrinterQueue:
def __init__(self):
self.queue = deque()
def add_document(self, document):
self.queue.append(document)
print(f"Document '{document}' ajouté à la file d'attente d'impression")
def print_document(self):
if self.queue:
document = self.queue.popleft()
print(f"Impression du document : '{document}'")
else:
print("La file d'attente d'impression est vide")
def display_queue(self):
print("File d'attente d'impression actuelle :", list(self.queue))
# Créer et utiliser une file d'attente d'impression
printer = PrinterQueue()
printer.add_document("Rapport")
printer.add_document("Présentation")
printer.add_document("Contrat")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()
# Affichage :
# Document 'Rapport' ajouté à la file d'attente d'impression
# Document 'Présentation' ajouté à la file d'attente d'impression
# Document 'Contrat' ajouté à la file d'attente d'impression
# File d'attente actuelle d'impression : ['Rapport', 'Présentation', 'Contrat']
# Impression du document : 'Rapport'
# Impression du document : 'Présentation'
# File d'attente actuelle d'impression : ['Contrat']
Dans cet exemple, nous avons créé une simple simulation de file d'attente d'impression. Les documents sont ajoutés à la fin de la file d'attente et imprimés dans l'ordre de leur arrivée, ce qui démontre le principe FIFO (First In, First Out).
GO TO FULL VERSION