IN3R11-1 - TD C

Listes simplement chaînées

On se donne une structure de liste chaînée de données de type zone_t définie ainsi :

  1. typedef struct sliste {
  2. zone_t elmt;
  3. struct sliste * suivante;
  4. } sliste_t;
  5.  

Nous verrons dans la deuxième partie ce qu'est le type zone_t, pour l'instant, ce n'est pas important.

Exercice 1

Écrire une fonction sliste_t * liste_vide (void) qui renvoie la valeur de pointeur que vous aurez choisie pour représenter la liste vide. Écrire la fonction int est_vide (sliste_t * l) qui teste si une liste est vide.

Exercice 2

Écrire deux fonctions d'affichage des éléments d'une liste. L'une itérative, l'autre récursive. On peut afficher un zone_t à l'aide de la fonction void print_zone_t(zone_t z);.

Exercice 3

Écrire une fonction sliste_t * ajoute(zone_t data, sliste_t * l) qui renvoie une liste ayant comme premier élément data et dont la suite est constituée par la liste l ainsi que la fonction sliste_t* enleve_tete(sliste_t * l) qui prend une liste non vide l, lui enlève sa tête et renvoie la suite de la liste.

Exercice 4

Écrire une fonction void libere_liste(sliste_t * l) qui libère toute la mémoire occupée par une liste l.

Exercice 5

Écrire une fonction sliste_t * enleve_element(zone_t data, sliste_t * l) qui enlève la première occurrence de data dans la liste l. On suppose qu'on dispose déjà d'une fonction int equals(zone_t a, zone_t b); qui renvoit 1 si a et b sont égaux, 0 sinon.

Stratégie d'allocation mémoire

On se donne une structure de données memoire_t pour modéliser la mémoire d'un système d'exploitation et les procédures d'allocation et de désallocation dynamiques de la mémoire.

memoire est un tableau d'octets correspondant à l'ensemble des octets de la mémoire. Certaines zones de ce tableau peuvent être allouées. On stocke alors dans une liste d'entiers zones_allouees, une description de cette zone mémoire. Lorsqu'on libère une zone mémoire, on rajoute sa description dans la liste d'entiers zones_libres. Au début du processus, zones_allouees et zones_libres sont vides. taille_occupation est l'indice du tableau d'octets à partir duquel la mémoire est vierge, c'est à dire sans zone allouée ni zone libérée.

Pour décrire une zone mémoire, on utilise une structure contenant deux entiers, l'un correspond à son indice dans memoire et l'autre à sa taille. Ce type de donnée est nommé zone_t. Voici la définition en C de ces types :


  1. #define TAILLE_MEMOIRE 1024
  2.  
  3. typedef struct{
  4. int adr;
  5. int taille;
  6. }zone_t;
  7.  
  8. typedef struct memoire {
  9. char memoire [TAILLE_MEMOIRE];
  10. int taille_occupation;
  11. sliste_t * zones_libres;
  12. sliste_t * zones_allouees;
  13. } memoire_t;
  14.  

Exercice 7

Écrire une fonction void ajoute_zone_libre( int adr, int taille, memoire_t * mem) qui ajoute dans la liste des zones libres une zone d'adresse adr et de taille taille, en utilisant les fonctions définies dans la partie 1. De même, écrivez une fonction void ajoute_zone_allouee( int adr, int taille, memoire_t * mem)

Exercice 8

Écrire une fonction int utilise_zone_libre ( int taille, memoire_t * mem) qui parcourt la liste des zones libres à la recherche d'une zone dont la taille est supérieure à taille. Si elle n'en trouve pas, la fonction renvoie TAILLE_MEMOIRE, sinon elle enlève t de la taille de la zone et renvoie l'indice dans le tableau de la mémoire libre utilisable.

Exercice 9

Écrire une fonction char * alloue_zone( int taille, memoire_t * mem) qui utilise la fonction précédente pour chercher une zone libre utilisable. S'il n'existe pas de telle zone, on alloue une zone à la fin de la mémoire utilisée pour l'instant. Si la mémoire n'est pas suffisante, le programme est arrêté. Cette fonction renvoie un char*, qui pointe vers le début de la zone allouée.

Exercice 10

Écrire une fonction void libere_zone(char * ptr, memoire_t * mem) qui cherche si ptr correspond bien à un pointeur sur une zone allouée. Si c'est le cas, la fonction l'enlève des zones allouées pour la placer dans la liste des zones libres.