Licence 3-IF7 TD Algorithmes no 1
Correction
fevrier 2005
Version pdf.



Notions abordées: tableaux dynamiques, complexité d'une recherche

Présentation

Le projet du semestre consiste à réaliser un jeu de stratégie temps réél. Un instant de réflexion permet de mettre en évidence la nécessitée de représenter de nombreuses informations. Une solution simple en C consiste à utiliser des tableaux dynamiques.

Allocation dynamique

realloc défini dans stdlib.h permet de modifier la taille d'une allocation dynamique réalisée par malloc. Voici un extrait du manuel :
#include <stdlib.h>

void * malloc (size_t size);
void free (void * ptr);
void * realloc (void * ptr, size_t size);

description

malloc() alloue size octets, et renvoie un pointeur sur la mémoire allouée. Le contenu de la zone de mémoire n'est pas initialisé.

free() libère l'espace mémoire pointée par ptr, qui a été obtenu lors d'un appel antérieur à malloc(), ou realloc(). Si le pointeur ptr n'a pas été obtenu par l'un de ces appels, ou si il a déjà été libéré avec free(), le comportement est indéterminé.

realloc() modifie la taille du bloc de mémoire pointé par ptr pour l'amener à une taille de size octets. realloc() conserve le contenu de la zone mémoire minimum entre la nouvelle et l'ancienne taille. Le contenu de la zone de mémoire nouvellement allouée n'est pas initialisé. Si ptr est NULL, l'appel de realloc() est équivalent à malloc(size). Si size vaut zéro, l'appel est équivalent à free(ptr). Si ptr n'est pas NULL, il doit avoir été obtenu par un appel antérieur à malloc(), ou realloc().

valeur renvoyée

Pour malloc(), la valeur renvoyée est un pointeur sur la mémoire allouée, qui est correctement alignée pour n'importe quel type de variable, ou NULL si la demande échouée.

free() ne renvoie pas de valeur.

realloc() renvoie un pointeur sur la mémoire nouvellement allouée, qui peut être différent de ptr, ou NULL si la demande à échouée. Si size vaut zéro, realloc renvoie NULL ou un pointeur acceptable pour free(). Si realloc() échoue, le bloc mémoire original reste intact, il n'est ni libéré ni déplacé.

Utilisation de realloc

L'utilisation classique de malloc pour allouer un tableau de n éléments de type ELEM :

 ELEM *ptr;

 ptr= (ELEM *) malloc(sizeof(ELEM) * n);
 if(ptr==NULL)
  // renvoyer une erreur
ptr est maintenant manipulable comme un tableau de n éléments. Il est également possible de demander d'agrandir la réservation pour pouvoir stocker n+10 éléments :

 n= n + 10;
 ptr= (ELEM *) realloc((void *) ptr, sizeof(ELEM) * n);
 if(ptr==NULL)
  // renvoyer une erreur
Ce mécanisme va nous permettre d'ajuster la taille de l'allocation dynamique au nombre d'éléments que doit stocker le tableau.

Type de donnée abstrait : ensemble dynamique

On peut construire une abstraction décrivant le comportement d'un tableau capable d'adapter sa taille au nombre d'éléments qu'on lui demande de stocker. Définir les opérations sur le type de données abstrait ensemble dynamique.

Rédiger la version C de ces opérations pour un type quelconque ELEM.

Solution:  
#include <stdlib.h>
#include <assert.h>

/* tableaux dynamiques
 modifie la taille du tableau afin de rendre le rang n accessible.

 l'allocation se fait par blocs de e_more elements

 entree :
  n : le rang a definir
  e_size : taille, en octets, d'un element du tableau
  e_more : allocation par blocs de e_more elements

 entree/sortie :
  size : taille physique du tableau
  parray : adresse d'un pointeur sur le premier element du tableau
 */

void array_add(void **parray, int *size, int n, int e_size, int e_more)
{
 if(n >= *size)
 {
  *size= ((n / e_more) + 1) * e_more;

  *parray= realloc(*parray, *size * e_size);
  assert(*parray!=NULL);
 }
}

Complexité d'une recherche dans un ensemble dynamique

Dans le cas d'un ensemble non ordonné, donner la complexité de l'insertion d'un élément, de la suppression d'un élément, de la recherche. Mêmes questions dans le cas d'un ensemble ordonné.

This document was translated from LATEX by HEVEA.