Data structures

Algorithmics – Session 3

  • Qu’est-ce qu’une structure de données ?
  • Structures de données intégrées
  • Listes chaînées
  • Piles
  • Files
  • Récapitulatif de la session

What is a data structure?

Definitions

Data Struture

  • Façon d’organiser les données pour qu’elles puissent être traitées plus facilement

Abstract data type

  • Structures de données qui ne sont pas des types de données intégrés
  • Un type de données abstrait est associé à des opérations à effectuer dessus

Why it is called abstract?

  • Parce qu’il ne spécifie pas comment les données sont représentées ni comment les opérations sont implémentées

What is a data structure?

A few common abstract data types

  • Linked list – Les éléments sont liés à l’aide de pointeurs

    • Initialisation, insertion/suppression, recherche, tri, etc.

  • Stack – Les opérations sont effectuées selon l’ordre LIFO (Last In First Out)

    • Initialisation, push, pop

  • Queue – Les opérations sont effectuées selon l’ordre FIFO (First In First Out)

    • Initialisation, push (enqueue), pop (dequeue)

  • Tree – Les éléments sont arrangés en une structure arborescente

    • Initialisation, insertion/suppression, recherche, parcours, équilibrage, etc.

  • Graph – Ensemble fini de sommets et ensemble d’arêtes qui connectent une paire de nœuds

    • Initialisation, insertion/suppression (sommet, arête), recherche, partition, etc.

Built-in data structures

List: for ordered collections

  • Les valeurs sont ordonnées de l’indice 0 à size-1
  • Permet des valeurs dupliquées
  • Elle est mutable et dynamique
  • Elle permet la sélection par tranche
# Define a list
my_structure = [1, 2, 3, 4, 5]
print(f"Initial list: {my_structure} with id {id(my_structure)}")

# Illustration of dynamic property
my_structure.append(6)

# Illustration of mutable property
my_structure[0] = 2
print(f"Modified list: {my_structure} still with id {id(my_structure)}")

# Illustration of slice selection
print(f"Two last elements: {my_structure[-2:]}")
Initial list: [1, 2, 3, 4, 5] with id 138495927307072
Modified list: [2, 2, 3, 4, 5, 6] still with id 138495927307072
Two last elements: [5, 6]

Built-in data structures

Set: for unordered collections

  • N’autorise pas les valeurs dupliquées
  • Elle est mutable et dynamique
# Define a set
my_structure = {1, 3, 5, 5}
print(f"Initial set: {my_structure} with id {id(my_structure)}")

# Add an element
my_structure.add(6)
print(f"Modified set: {my_structure} with id {id(my_structure)}")

# Test if an element belongs to the set
print(f"Contains 4: {4 in my_structure}")
Initial set: {1, 3, 5} with id 127760255235264
Modified set: {1, 3, 5, 6} with id 127760255235264
Contains 4: False

Built-in data structures

Tuple: for fixed collections

  • Les valeurs dans un tuple sont ordonnées
  • Il permet des valeurs dupliquées
  • Il n’est pas mutable
# Initialize a tuple
my_structure = (1, "3", 3.14)
print(f"Initial tuple: {my_structure} with id {id(my_structure)}")
print(f"Second element: {my_structure[1]}")

# Extend the tuple into a new variable
my_structure += ("4",)
print(f"New tuple: {my_structure} with id {id(my_structure)}")
Initial tuple: (1, '3', 3.14) with id 132604205639104
Second element: 3
New tuple: (1, '3', 3.14, '4') with id 132604205672832

Built-in data structures

Dictionary: For indexed collections

  • Il stocke des paires clé/valeur
  • Il n’autorise pas la duplication des clés
  • Il est mutable et dynamique
# Initialize a dictionary
my_dict = {'jack': 4098, 'sape': 4139}
print(f"Initial dict: {my_dict} with id {id(my_dict)}")

# Add a new entry and remove one
my_dict['guido'] = 4127
del my_dict['sape']
print(f"Modified dictionary: {my_dict} with id {id(my_dict)}")

# Check if an entry exists
print(f"Available entries: {list(my_dict)}")
print('guido' in my_dict)
Initial dict: {'jack': 4098, 'sape': 4139} with id 4408760320
Modified dictionary: {'jack': 4098, 'guido': 4127} with id 4408760320
Available entries: ['jack', 'guido']
True

Linked list

Definition and primitives

Linked list

  • Une structure de données composée de nœuds, chaque nœud ayant deux éléments, c’est-à-dire des données et une référence à un autre nœud.

Doubly-linked list

  • Une liste chaînée où chaque valeur stockée est liée à ses valeurs précédentes et suivantes
  • Deux pointeurs d’entrée sont fournis : un vers la tête de la liste et un vers sa queue
  • Primitives – Initialiser, insérer au début/à la fin, extraire du début/de la queue, vérifier si vide

Stacks

Definition and primitives

  • Une pile est une structure de données dans laquelle le premier élément ajouté est le dernier élément retiré
  • C’est la stratégie d’accès LIFO (Last In, First Out)

  • Les détails d’implémentation des données sont abstraits
  • Primitives – Initialiser, push, pop, vérifier si vide

Queues

Definition and primitives

  • Une file est une structure de données dans laquelle les éléments sont retirés dans l’ordre dans lequel ils ont été ajoutés
  • C’est la stratégie d’accès FIFO (First In, First Out)

  • Les détails d’implémentation des données sont abstraits
  • Primitives – Initialiser, enqueue, dequeue, vérifier si vide

Recap of the session

What’s next?

Activité pratique (~2h30)

Implémentation de solutions algorithmiques avec piles et files

  • Comprendre diverses implémentations des piles et files
  • Comparer différentes implémentations
  • Faire les activités optionnelles si vous avez le temps

Après la session

  • Revoir les articles de la session
  • Vérifier votre compréhension avec le quiz
  • Compléter l’activité pratique
  • Consulter la section “Avant le cours” de la prochaine session