Extrait du cours sur les structures de données
INTRODUCTION
Ce document est un résumé concernant les structures les plus classiques rencontrées en informatique pour organiser des données. On suppose que le lecteur connait déjà les tableaux et les enregistrements(exemple: record en Pascal, struct en C). Pour aborder les différentes structures de données présentées ici, le lecteur devra également bien maîtriser la notion de pointeurs et de gestion dynamique de la mémoire.
Les structures de données présentées ici sont:
- les tableaux(arraysen anglais),
- les listes chaînées(linked listsen anglais),
- les piles(stacksen anglais),
- les files(queuesen anglais),
- les arbres binaires(binary treesen anglais).
NOTATIONS
Avant d’entrer dans les détails de chaque structure, nous introduisons ici quelques notations qui seront utilisées tout au long de ce document. Elles permettront de formaliser les modélisations proposées pour les différentes structures de données ainsi que les opérations applicables sur ces structures.
Opérateurs
*p est le contenu pointé par p;
T * est le type pointeur sur un élément de type T;
&x est l’adresse de l’élément x;
x y affecte la valeur y à la variable x;
Fonction
On définit une fonction de la manière suivante.
fonction TR f(TX x, TY y):
…
fin fonction;
Dans cet exemple, f a deux paramètres, xde type TX et yde type TY, et renvoie un élément de type TR.
Instructions
T * ALLOUER(T, ENTIER n) est une instruction qui alloue un espace mémoire pouvant contenir n éléments de type T. Si l’allocation est possible, la fonction retourne l’adresse de l’espace alloué. Dans le cas contraire, la valeur NIL est retournée, indiquant que l’allocation a échouée.
LIBERER(T * p) est une instruction qui libére l’espace mémoire pointé par p. Cet espace doit avoir été alloué auparavant avec l’instruction ALLOUER.
1. TABLEAUX
INTRODUCTION
TRI PAR SELECTION
Dans ce chapitre, nous allons présenter deux méthodes pour trier les éléments d’un tableau.
Nous ne présenterons pas les algorithmes les plus efficaces. Nous avons choisi de présenter tout d’abord la méthode de tri dite « par sélection ». Il s’agit d’une méthode qui n’est pas très rapide. Ensuite, nous présenterons la méthode dite « par fusion » qui est beaucoup plus efficace. Dans ce chapitre, nous utiliserons la fonction PLUS_PETIT(a,b)pour trier. Cette fonction renvoie VRAI si l’élément a est plus petit que l’élément b.Cette méthode est très simple. Supposons que l’on veuille trier les n éléments du tableau t. On commence par parcourir le tableau pour trouver la plus petite valeur. On la place à l’indice 0. Ensuite, on recommence à parcourir le tableau à partir de l’indice 1pour trouver la plus petite valeur que l’on stocke à l’indice 1. Et ainsi de suite pour l’indice 2, 3 jusqu’à n – 2. La figure suivante montre comment l’algorithme fonctionne sur un tableau de 8 éléments. Seulement quelques étapes sont représentées.
……..
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Cours sur les structures les plus classiques rencontrées en informatique (787 KO) (Cours PDF)
