Indexation
Accès(T[i]) = O(1)
Temps constant d'accès à un élément
Définition :
Indexation : système d'attribution d'identifiants numériques (indices) aux éléments d'une structure de données pour permettre un accès direct.
Caractéristiques :
🏷️ Indices numériques
⚡ Accès instantané
📍 Position fixe
📏 Bornes définies
⚡ Accès instantané
📍 Position fixe
📏 Bornes définies
Structures concernées :
✅ Tableaux
✅ Listes
✅ Matrices
✅ Chaînes de caractères
✅ Listes
✅ Matrices
✅ Chaînes de caractères
Accès direct
O(1) : temps constant
Adresse calculée : position = base + i*taille
Accès immédiat : T[i]
Efficacité maximale : algo optimal
Indices et positions
Premier élément : indice 0
Dernier élément : indice n-1
Taille de la structure : n
Algorithmes efficaces
Accès direct à un élément
Calcul d'adresse
Accès aléatoire
Recherche par indice
Exemples de code
# Tableau statique
T = [10, 20, 30, 40, 50]
# Accès direct en O(1)
element = T[2] # Récupère 30
T[2] = 100 # Modifie à 100
# Chaîne de caractères
chaine = "NSI"
lettre = chaine[1] # 'S'
# Matrice 2D
matrice = [[1,2],[3,4]]
element = matrice[0][1] # 2
Limites et contraintes
Dépassement : indices valides seulement
Immuabilité : certaines structures
Taille fixe : tableaux
Erreurs fréquentes
Erreur 1 :
Dépassement d'indice
T = [1, 2, 3]
val = T[3] # IndexError!
T = [1, 2, 3]
val = T[3] # IndexError!
Erreur 2 :
Indices négatifs mal utilisés
T[-1] # Dernier élément (OK)
T[-4] # IndexError si taille = 3
T[-1] # Dernier élément (OK)
T[-4] # IndexError si taille = 3
Erreur 3 :
Confusion entre indice et valeur
for i in range(len(T)): # Indice
for element in T: # Valeur
for i in range(len(T)): # Indice
for element in T: # Valeur
