Rappels

Informatique - Deug S4 MIAS

Exercice 1 - Tableau alloué statiquement

Écrire un petit programme qui déclare un tableau d'entier et en affiche tous les éléments. Ajouter une fonction d'initialisation assurant que tab[i]=i.

Exercice 2 - Tableau alloué dynamiquement

Faire maintenant la même chose en déclarant, pour le tableau, un pointeur sur entier. Vous devez donc allouer l'espace mémoire nécessaire au tableau avant d'utiliser le pointeur. Écrire une fonction d'initialisation comme précédemment.
Donnez au moins deux différences fondamentales entre les deux déclarations int t[5]; et int *t;

Exercice 3 - 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.

représentation d'une matrice

É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 4 - 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), void afficheMatrice(Matrice *m) et libereMatrice(Matrice *m).

Exercice 5 - 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.

liste simplement chaînée

Exercice 6 - 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ées 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 7 - 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.

liste doublement chaînée

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