Tri

Résumé du document

Programmation en Pascal

Algorithme de Tri

Les pointeurs

Les listes Chainées

Extraits

[...] Read ; Si l'on rentre ‘Lille' au clavier, cela aura pour effet d'affecter la valeur ‘Lille' à la variable pointée Q^. ; Cette affectation a pour effet que contient la même valeur que la variable Q^. Les pointeurs associés contiennent aux des valeurs différentes. Attention : On voit qu'il ne faut pas confondre et P Q. Dispose ; Dispose a pour effet de libérer la place préalablement occupée par P^. La case P reste réservée mais l'adresse qui y est stockée n'a plus de signification. [...]

[...] Exemple : Intérêts de la liste chaînée Souplesse de manipulation des éléments (insertion, suppression ) 1 Insertion 2 Suppression Manipulation d'une liste chaînée Attention : Dans les opérations de réorientation des pointeurs internes, il faut faire attention à l'ordre des ces opérations de manière à ne pas perdre une adresse avant d'avoir effectué le branchement voulu Création de liste chaînée Dépend de l'ordre dans lequel on désire pouvoir la lire. Deux structures de données possibles : La Pile La File 1 Création d'une pile Point de départ : NIL On ajoute l'élément Eric. On ajoute l'élément Anne. On ajoute l'élément Marie. On ajoute le pointeur Prem de début de liste. La lecture se fait donc en partant de Prem, de gauche à droite : LIFOC (Last In First Out) Création d'une file Point de départ : Prem On ajoute l'élément Eric. [...]

[...] Leur adressage est direct : elles sont accessibles directement par leur identifiant. Améliorer l'utilisation de l'espace mémoire Il est souhaitable de pouvoir créer et utiliser des variables uniquement au fur et à mesure des besoins. On veut pouvoir récupérer l'espace mémoire devenu inutile. Il serait bon de pouvoir supprimer et insérer des éléments sans toucher au reste des données. Variable dynamique Propriétés : Elle peut être générée et détruite pendant l'exécution du bloc, ce qui permet de libérer la place mémoire. [...]

[...] Déclaration d'une liste chaînée Exemple : déclaration d'une liste chaînée de prénoms Type Point = ^Element ; Element = Record Prenom : String[20] ; Suivant : Point ; end ; var Prem, Paux : Point ; Attention : On voit que la définition du type Point comporte le mot élément qui n'est pas encore défini. Si l'on essaie de définir le type élément en premier, on retrouve le même problème. Le Pascal autorise cette exception. Accès aux éléments Pour accéder à un élément, il faut parcourir la chaîne jusqu'à cet élément. Pour accéder directement aux éléments, il faudrait utiliser autant de pointeurs externes que d'éléments. On privilégie ici l'espace mémoire utilisé par rapport au facteur temps. Le dernier élément contient généralement la valeur NIL. [...]

[...] P Q Une belle affectation suppose que la variable Q a été déclarée auparavant comme une variable pointeur qui pointe vers un élément de même type que celui pointé par P. var Q : Point ; Avant : (après initialisation supposée des pointeurs) Après : L'affectation P Q fait que les deux pointeurs P et Q contiennent la même adresse, celle de Q. Elle signifie que désormais P pointe vers la même variable que i.e Q^. Attention : Après P l'ancienne valeur de n'est pas accessible par la variable pointeur P. [...]