Aller au contenu

TNSI : les Tableaux⚓︎

le Type Abstrait Tableau⚓︎

Séquences⚓︎

Séquence / Suite

En informatique, Une Séquence 🇬🇧 🇫🇷, est un conteneur/collection ordonné par des indices entiers, de plusieurs éléments/objets/données.

Exp

Les chaînes, les listes, les tuples, etc.. sont des séquences en Python.

Accès aux Éléments d'une Séquence

On accède aux éléments d'une Séquence :

  • soit par Accès Séquentiel (les uns derrières les autres)
  • soit par Accès Direct ou Accès Aléatoire 🇫🇷, ou Random Access 🇬🇧 (via un indice)

Définition du type Abstrait Tableau⚓︎

Le Type Abstrait Tableau/Array

  • Un Tableau 🇫🇷 ou Array 🇬🇧 (à une dimension) est une structure de données abstraite représentant un conteneur/collection finie d'éléments ordonnés par des indices entiers/clés.
  • La Taille d'un Tableau (à une dimension) est le nombre total d'éléments du Tableau

Récursive, des Tableaux Multidimensionnels

  • Un Tableau de dimension \(n\) est un tableau dont les éléments sont eux-mêmes (tous) des Tableaux de dimension \(n-1\).
  • La Taille d'un tableau de dimension \(n\), est un \(n\)-uplet de \(n\) nombres entiers

Convention Par souci de simplification, dans toute la suite, par défaut, les tableaux étudiés seront de dimension 1.

Primitives du Type Abstrait Tableau⚓︎

Le type abstrait de Tableau n'est pas normalisé, cela veut dire que, selon les auteurs, on peut trouver quelques différences dans les Primitives d'un TAD Tableau :

  • (Dans les cas des Tableaux Dynamiques, i.e. de taille variable), on y trouve au minimum les opérations de CRUD.

Différentes Implémentations possibles⚓︎

Il existe plusieurs implémentations possibles du type abstrait de données Tableau en une structure de données Tableau, notamment (cf. plus bas SVP) :

  • avec des Cellules Contigües : ⚠ C'est l'Implémentation Classique ⚠ : Dans ce cours, dans toute la suite, par défaut, nous choisirons cette implémentation pour un Tableau.
  • avec des Listes Chaînées (cf. cours sur les Listes)

Tableau Statique vs Dynamique⚓︎

Tableau Statique vs Dynamique

  • Dans certains langages (C, Java, OCaml, ...) les tableaux sont de taille \(n\) fixée: On parle dans ce cas de Tableau Statique. Leur implémentation utilise en général des Cellules Contiguës.
  • Certains autres langages de haut niveau autorisent des tableaux qui modifient leur taille en fonction de leur utilisation: On parle dans ce cas de Tableau Dynamique. Leur implémentation utilise en général :
    • soit des Cellules Contiguës (comme en CPython qui est l'implémentation usuelle de Python)
    • soit des Listes Chaînées.

En outre, selon les langages, un tableau peut être implémenté, en tant que Structure de données, de différentes manières :

  • Dans certains langages (C, Java, OCaml, ...), dits à typage statique, tous les éléments d'un tableau doivent être du même type.
  • Certains autres langages, dits à typage dynamique (Python, APL, ...) autorisent que les éléments d'un tableau soient de types différents.

Implémentation Classique : par Cellules Contiguës⚓︎

Implémentation : La Structure de Données Tableau/Array

Dans la plupart des langages (C,Java, OCaml, et même Python..) , un Tableau est représenté en mémoire par des éléments contigüs.

⚠ C'est l'Implémentation Classique ⚠ : Dans toute la suite, par défaut, nous choisirons cette implémentation pour un Tableau.

Accès aux Éléments⚓︎

On en déduit une propriété importante des Tableaux implémentés par des éléments contigüs :

Accès en Temps Constant

Le temps d'accès à n'importe quel élément via son index est en temps constant : en \(O(1)\)

En effet, les éléments étant contigüs, on peut calculer l'adresse mémoire de l'élément auquel on veut accéder, grâce à l'adresse de base du tableau et de l'index. L'accès est direct comme pour une variable simple.

Complexité d'Insertion et/ou Suppression d'éléments⚓︎

  • Les tableaux statiques n'autorisent pas les opérations d'insertion et de suppression d'éléments

  • Les tableaux dynamiques autorisent l'insertion ou la suppression des éléments mais, les cellules devant être contigües, cela oblige à :

    • créer un nouveau tableau, de taille plus grande /ou (respectivement) plus petite : Complexité en \(O(n)\)
    • copier tous les éléments du tableau original dans le nouveau tableau : Complexité en \(O(n)\)
    • puis de libérer l'espace mémoire alloué à l'ancien tableau : Complexité (dans le pire des cas) en \(O(n)\)

    Conclusion : Complexité en \(O(n)\) C'est pourquoi certains langages fournissant de telles possibilités, implémentent leurs tableaux non pas sous forme de tableaux dynamiques traditionnels (cellules adjacentes), mais sous forme de liste chaînée, ou une combinaison des deux structures pour améliorer les performances.

Implémentation par Liste Chaînée⚓︎

Une implémentation d'un Tableau sous forme de Liste Chaînée, est appelée plutôt une Liste Chaînée.

Tableaux Associatifs / Dictionnaires⚓︎

Tableaux Associatifs / Dictionnaires

Un Tableau Associatif, ou Dictionnaire est un type abstrait qui associe des valeurs à des clés : 

# Syntaxe inspirée de Python
dico = { 
  clé_1 : valeur_1,
  clé_2 : valeur_2,
  ...
  clé_n : valeur_n
}

Interface d'un Tableau Associatif / Dictionnaire

Un Tableau Associatif / Dictionnaire est muni des opérations / primitives suivantes:

  • ajout d'une nouvelle valeur associée à une nouvelle clé
  • modification de la valeur associée à une clé existante
  • retrait/suppression d'une clé et de la valeur associée
  • lecture/récupération de la valeur associée à une clé donnée

Un Tableau Associatif, ou Dictionnnaire, pourrait par exemple associer les valeurs couples (prenom, nom) aux clés numeroScecuriteSociale. Contrainte : Chaque clé doit être unique dans le tableau associatif.

Aller Plus Loin : Bibliographie⚓︎