TDAO3-4 : pointeurs, implantations des listes, modules

Exo 0 : Est-ce bien clair ?
Donnez un programme Pascal qui crée en mémoire des deux structures ci-dessous, référencées par les variables liste et arbreBinaire. Quelles sont les complexités en temps et en espace de votre programme ?

Exo 1 : Un type de données abstrait pour les listes
Définissez le profil des cinq primitives suivantes opérant sur le type de données ListeEntiers : vide, cons, tete, reste, test_vide

en vous inspirant des listes de Scheme. Quels sont les axiomes reliant ces opérations ? Donnez, à l'aide de ces primitives, le code Pascal des fonctions egal_liste, concat et renverser (deux versions, une avec concat, l'autre sans).
Exo 2 : L'implantation classique
Programmez un module Liste1 implentant les cinq primitives de l'exo 1. Ce module sera basé sur l'emploi des pointeurs et le primitive new. Testez les neufs fonctions de l'exo 1.
Quelles sont les complexités en temps et en espace des neufs fonctions de l'exo 1 et du programme de test relativement à cette implantation ?
Exo 3 : Une autre implantation
Programmez un module Liste2 implantant les cinq primitives de l'exo 1. Ce module sera basé sur l'emploi d'un unique tableau privé à ce module (ni pointeur, ni new). Testez les neufs fonctions de l'exo 1. Vous devriez n'avoir qu'à :

• échanger le nom du module de la partie USES et
• appeler une procédure d'initialisation en début de programme principal.

Quelles sont les complexités en temps et en espace des neufs fonctions de l'exo 1 et du programme test relativement à cete implantation ?
Exo 4 : Où l'on rend ce que lon prend
Pour une utilisation parcimonieuse de la mémoire, on peut souhaiter disposer d'une procédure rend_mem qui ``désalloue'' les cellules utilisées par une liste. Implantez cette procédure pour le module Liste1.
Pour le module Liste2, il faudra peut-être repenser l'architecture de l'implantation et utiliser deux tableaux. D'autres architectures sont également envisageables. Saurez-vous relever ce défi ?

Àpropos de ce document...

TDAO3-4 : pointeurs, implantations des listes, modules

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 sujet.tex.

The translation was initiated by Jean-Christophe Soulie on mardi, 4 mai 1999, 17:07:54 GMT+4