TP1 (rappels)

Informatique - Deug S4 MIAS

Cette feuille d'exercice a pour but de rappeler rapidement les principes suivants: allocation et désallocation de mémoire, manipulation des pointeurs (arithmétique), structures récursives, passage de paramètre par adresse. Pour illustrer ces notions, nous nous appuierons, d'une part, sur l'exemple des tableaux à 2 dimensions et, d'autre part, sur l'exemple des listes, simplement ou doublement chaînées.

Exercice 1 - Matrice et typage de la mémoire

On désire représenter par un pointeur une matrice d'éléments de type double (tableau à deux dimensions). Le faire par une allocation statique est plutôt simple:

double tab[MAXLIG][MAXCOL];

Pour allouer dynamiquement un tel tableau, il est possible de s'aider de la figure ci-dessous qui présente la manière dont les informations devront être stockées.

Écrire les instructions nécessaires à l'allocation dynamique d'un tableau de MAXLIG lignes et MAXCOL colonnes d'éléments de type double, représenté par un pointeur.

Écrire une fonction double element() qui accepte en argument un pointeur sur une matrice m et deux indices i et j, et qui retourne l'élément correspondant à m[i][j] sans utiliser cette expression ni aucun accès utilisant les crochets ([]), mais en utilisant l'arithmétique sur les pointeurs.

Exercice 2 - Type structure

Donner la définition d'un type Matrice permettant de représenter des matrices à deux dimensions d'éléments de type double, dont la taille de chaque dimension n'est pas connue statiquement. Les informations nécessaires sont donc un pointeur et la taille de chaque dimension.

Écrire des méthodes Matrice *alloueMatrice(int maxLig, int maxCol), double elementMatrice(Matrice *m, int i, int j) et void afficheMatrice(Matrice *m).

Exercice 3 - Type structure récursive

Définir les types nécessaires à la gestion d'une liste chaînée d'entiers. On rappelle que leur implantation peut être illustrée par le schéma ci-dessous.

Exercice 4 - Liste simplement chaînée

1. Écrire deux méthodes d'allocation d'une cellule de liste chaînée (qui placent dans la cellule une valeur entière passée en argument). La première, alloueUneCellule(), retourne la nouvelle cellule en résultat de la fonction. La seconde, alloueCetteCellule(), effectue l'allocation d'une cellule qu'elle a reçu en argument.
   Pour chacune des fonctions, préciser les instructions d'appel et justifier l'usage des pointeurs.
2. Écrire une fonction libereCellule() réalisant la désallocation d'une cellule.
   
3. Écrire deux fonctions d'affichage d'une liste, l'une itérative et l'autre récursive.
4. Écrire une fonction libereListe() réalisant la désallocation de toutes les cellules d'une liste.
5. Écrire une fonction insereEnTete(), acceptant une liste et une valeur, et insérant une nouvelle cellule ayant cette valeur en tête de la liste.
6. Écrire une fonction insereEnPlace() qui accepte les mêmes arguments, mais qui insère la nouvelle cellule de sorte que la liste reste triée par ordre croissant des valeurs entières.
7. Écrire une fonction recherche() qui, étant donnés une liste et une valeur entière, retourne un pointeur sur la cellule de la liste contenant cette valeur, ou NULL si la valeur n'est pas dans la liste.
8. Écrire une fonction supprime() qui, étant donnés une liste et une valeur entière, supprime la première cellule de la liste contenant cette valeur. Si une telle cellule est supprimée, la fonction retourne 1, sinon elle retourne 0.

Exercice 5 - Liste doublement chaînée

Définir les types nécessaires à la gestion d'une liste doublement chaînée d'entiers. On rappelle que leur implantation peut être illustrée par le schéma ci-dessous.

Écrire les fonctions pour ce type permettant d'obtenir les mêmes fonctionnalités que pour les listes simplement chaînées.