D2:EPITA:Atelier:C:TP:2013:2014

Structures de données

Et voila, on va jouer avec les structures !

Listes

Voici l'en-tête de notre module de listes chaînées:

/* list.h: classical linked list (of integer) */
 
#ifndef _LIST_H_
#define _LIST_H_
 
struct list {
  struct list *next;
  int          value;
};
 
struct list *list_empty();
int list_is_empty(struct list *l);
 
/* usual operations */
 
/* list_len(l) return the size of the list */
size_t  list_len        (struct list *l);
 
/* list_add(l,x) return a list with head x and tail l */
struct list *list_add        (struct list *l, int x);
 
/* list_destroy(l) completely free every element of l */
void list_destroy    (struct list *l);
 
/* list_insert(l,x) insert x in a sorted list l */
void list_insert     (struct list **l,int x);
 
/* list_print(l) print every element in l *
 * with format: [ x0; ..; xn; ]           */
void list_print      (struct list *l);
 
/* list_iter(l, f) generic iterator       *
 * f is a pointer to some function on int */
void list_iter       (struct list *l, void(*f)(int));
 
/* list_duplicate(l) return a complete copy of l */
struct list *list_duplicate  (struct list *l);
 
#endif
 
/* list.h : end */

• Écrire le fichier list.c correspondant.

Debug et Gestion d'erreurs

Le but ici est d'insérer des contrôle d'erreur dans toutes les fonctions précédentes à l'aide de la fonction assert (voir la page de man.)

Pour les listes, il y a peu d'erreurs potentiels, mais vous pourrez continuer sur les exercices suivants.

Arbres binaires

L'objectif est d'implémenter l'en-tête suivant:

/* Tree */
 
#ifndef _TREE_H_
#define _TREE_H_
 
typedef struct s_tree  *tree;
 
#define EMPTY_TREE      NULL
#define tree_is_empty(t) (!(t))
 
tree tree_uniform_build(int *key, size_t depth);
 
void tree_free(tree t);
size_t tree_size(tree t);
int tree_height(tree t);
 
void tree_prefix_print(tree t);
void tree_infix_print(tree t);
 
void tree_to_dot(tree t);
 
#endif

Voici un démarrage pour votre fichier tree.c:

/* Tree */
 
#include <stdlib.h>
#include <stdio.h>
 
#include "tree.h"
 
struct s_tree
{
  int                   key;
  tree                  left, right;
};
 
tree tree_uniform_build(int *key, size_t depth)
{
  tree                  t = NULL;
  if (depth > 0)
    {
      t = malloc(sizeof (struct s_tree));
      t->left = tree_uniform_build(key, depth - 1);
      *key += 1;
      t->key = *key;
      t->right = tree_uniform_build(key, depth - 1);
    }
  return t;
}

(on fournit l'implémentation de la fonction de création d'arbre.)

Dimensions

• Commencer par faire les fonctions faciles: tree_size et tree_height

Libération de la mémoire

• Écrire la fonction de destruction tree_free qui libère l'ensemble des nœuds de l'arbre.

Pour s'assurer que la libération a bien eu lieu, vous pouvez essayer un outil tel que valgrind.

Affichage en profondeur

• Écrire les deux fonctions d'affichage en profondeur tree_prefix_print et tree_infix_print: l'objectif est d'afficher en profondeur avec les clefs en prefixe (avant les fils) ou en infixe (entre les fils) séparées par des ;.

Affichage en largeur: format dot

• Écrire tous les opérations de manipulation de file.

• Écrire la fonction d'affichage dans la format dot (tree_to_dot.) Cette affichage devra se faire en largeur (chaque nœud suivi de ces fils)