Voir la source de D2:EPITA:Atelier:C:TP:2013:2014

[[category:EPITA:AtelierC: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:

<source lang="C">
/* 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 */
</source>

* '''Écrire le fichier <tt>list.c</tt> 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 <tt>assert</tt> (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:

<source lang="C">
/* 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
</source>

Voici un démarrage pour votre fichier <tt>tree.c</tt>:

<source lang="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;
}
</source>

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

=== Dimensions ===

* '''Commencer par faire les fonctions ''faciles'': <tt>tree_size</tt> et <tt>tree_height</tt>'''

=== Libération de la mémoire ===

* '''Écrire la fonction de ''destruction'' <tt>tree_free</tt> 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 <tt>valgrind</tt>.

=== Affichage en profondeur ===

* '''Écrire les deux fonctions d'affichage en profondeur <tt>tree_prefix_print</tt> et <tt>tree_infix_print</tt>: 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 <tt>;</tt>.'''

=== Affichage en largeur: format dot ===

* '''Écrire tous les opérations de manipulation de file.'''

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