Programmation:C:Algorithmes

Introduction

Dans cette partie nous allons voir rapidement quelques notions d'algorithmique de bases (listes, vecteurs, arbres ... )

Structures de données classiques

La plus part des structures de données décrites dans les cours/livres d'algorithmique s'écrivent simplement et rapidement en C.

Listes chaînées

Nous avons déjà écrit de nombreuse fois des listes chaînées, il s'agit donc d'un résumé:

/* liste.h : Integer Linked List */
 
#include <stdlib.h>
#include <unistd.h>
 
#ifndef _LISTE_H
#define _LISTE_H
 
typedef struct s_list  *t_list;
 
#define empty_list() (NULL)
#define list_is_empty(l) (!l)
 
t_list  add     (int x, t_list l);
size_t  len     (t_list l);
int     head    (t_list l);
t_list  tail    (t_list l);
t_list  index   (int x, t_list l);
void    destroy (t_list l);
void    insert  (int x, t_list *l);
 
#endif

/* liste.c : Integer Linked List */
 
#include <stdlib.h>
#include <unistd.h>
 
#include "liste.h"
 
struct s_list
{
  int                   val;
  t_list                next;
};
#define LSIZE (sizeof (struct s_list))
 
t_list add(int x, t_list l)
{
  t_list                t;
  t = malloc(LSIZE);
  t->val = x;
  t->next = l;
  return t;
}
 
size_t len(t_list l)
{
  size_t                i;
  for (i=0; l; l = l->next)
    ++i;
  return i;
}
 
int head(t_list l)
{
  return (l->val);
}
 
t_list tail(t_list l)
{
  return (t->next);
}
 
t_list index(int x, t_list l)
{
  for (; l && l->val <> x; l = l->next) ;
  return l;
}
 
void destroy(t_list l)
{
  t_list                t;
  while (l)
    {
      t = l;
      l = l->next;
      free(t);
    }
}
 
void insert(int x, t_list *l)
{
  t_list                t1,t2;
  if (!(*l) || (*l)->val >= x)
    *l = add(x,*l);
  else
    {
      for (t1 = l; t1 && t1->val < x; t1 = t1->next)
	t2 = t1;
      t2->next = add(x, t1);
    }
}

File

/* queue.h : simple queue */
 
#include <stdlib.h>
#include <unistd.h>
 
#ifndef _QUEUE_H
#define _QUEUE_H
 
typedef struct s_queue *t_queue;
 
#define empty_queue() (NULL)
#define queue_is_empty(q) (!q)
 
t_queue push    (void *x, t_queue q);
void   *take    (t_queue *q);
t_queue clear   (t_queue q);
 
#endif

/* queue.c : simple queue */
 
#include <stdlib.h>
#include <unistd.h>
 
#include "queue.h"
 
struct s_queue
{
  void                 *value;
  t_queue               next;
};
#define QSIZE (sizeof (struct s_queue))
 
t_queue push(void *x, t_queue q)
{
  t_queue               tmp=NULL;
  tmp = malloc(QSIZE);
  tmp->value = x;
  if (q)
    {
      tmp->next = q->next;
      q->next = tmp;
    }
  else
    tmp->next = tmp;
  return tmp;
}
 
void *take(t_queue *q)
{
  void                 *x;
  t_queue               tmp;
  tmp = (*q)->next;
  x = tmp->value;
  (*q)->next = tmp->next;
  if (tmp == *q)
    *q = NULL;
  free(tmp);
  return x;
}
 
t_queue clear(t_queue q)
{
  while (q)
    (void)take(&q);
  return q;
}

Arbres Binaires

/* tree.h : basic binary tree */
 
#include <stdlib.h>
#include <unistd.h>
 
#ifndef _TREE_H
#define _TREE_H
 
typedef struct s_tree  *t_tree;
 
t_tree  make_tree       (int k, t_tree lson, t_tree rson);
size_t  height          (t_tree t);
size_t  size            (t_tree t);
void    depth_print     (t_tree t);
void    level_print     (t_tree t);
 
#endif

/* tree.c : basic binary tree */
 
#include <stdlib.h>
#include <unistd.h>
 
#include "queue.h"
#include "tree.h"
 
struct s_tree
{
  int                   key;
  t_tree                left, right;
};
#define TSIZE (sizeof (struct s_tree))
 
t_tree make_tree(int k, t_tree lson, t_tree rson)
{
  t_tree                t;
  t = malloc(TSIZE);
  t->key = k;
  t->left = lson;
  t->right = rson;
  return t;
}
 
#define MAX(a,b) ((a)<(b)?(b):(a))
 
size_t height(t_tree t)
{
  size_t                h=-1, hr, hl;
  if (t)
    {
      hl = height(t->left);
      hr = height(t->right);
      h = 1 + MAX(hl, hr);
    }
  return h;
}
 
size_t size(t_tree t)
{
  return (t ? 1 + size(t->left) + size(t->right): 0);
}
 
void space_writer(size_t nb)
{
  char                 *buf;
  buf = malloc(nb + 1);
  buf[nb] = 0;
  while (nb--)
    buf[nb] = ' ';
  printf("%s", buf);
}
 
void dprint(t_tree t, size_t inc)
{
  if (t)
    {
      space_writer(inc);
      printf("%d(\n", t->key);
      dprint(t->left, inc+1);
      dprint(t->right, inc+1);
      space_writer(inc);
      printf(")\n");
    }
}
 
void depth_print(t_tree t)
{
  dprint(t, 0);
}
 
void level_print(t_tree t)
{
  t_queue               q;
  q = empty_queue();
  q = push(t,q);
  q = push(NULL,q);
  do
    {
      t = take(&q);
      if (t)
	{
          printf("%d ", t->key);
          q = t->left?push(t->left,q):q;
          q = t->right?push(t->right,q):q;
	}
      else
	{
           printf("\n");
           if (!queue_is_empty(q))
             q = push(NULL,q);
	}
    }
  while (!queue_is_empty(q));
}

Du langage algo au C

Il y a peu de chose à voir ici, si ce n'est la traduction du passage par référence (les Paramètres Globaux). Le passage par référence n'existe pas en C, il faut donc utiliser explicitement les pointeurs.

La traduction en soit n'est pas un problème, ce qui nous intéresse surtout ici est de poser des bases pour organiser notre code et faire ainsi la différence entre un passage par adresse et le passage par valeur d'un pointeur ou d'un tableau.

Nous allons tout de même commencer par un exemple classique, l'échange de contenu entre deux variables (vous pouvez tester le code grace à l'interpréteur epi-algo[1]):

algorithme procedure swap
  parametres globaux
    entier              a, b
  variables
    entier              c
debut
  c <- a
  a <- b
  b <- c
fin algorithme procedure swap

variables
  entier                x, y
debut
  x <- 42
  y <- 666
  ecrire("x = ",x,"\ny = ",y,"\n")
  swap(x,y)
  ecrire("x = ",x,"\ny = ",y,"\n")
fin

Ce qui nous donne le programme C suivant:

#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
 
/* swap(a,b) echange le contenu pointe par a et b */
void swap(int *a, int *b)
{
  int                   c;
  c = *a;
  *a = *b;
  *b = c;
}
 
int main()
{
  int                   x=0, y=42;
  printf("x=%d\n y=%d\n",x,y);
  /* referencement de x et y pour etre utilises par swap */
  swap(&x,&y);
  printf("x=%d\n y=%d\n",x,y);
  return 0;
}

On peut même généraliser l'opération swap. Pour ça il faut utiliser le type void*, mais il faut également des informations sur la taille du contenu des variables et surtout il faut utiliser une opération de copie explicitement (ce n'est donc pas forcément la meilleure méthode pour échanger des entiers ... )

void genswap(void *a, void *b, size_t s)
{
  void                 *c;
  c = malloc(s);
  memcpy(c,a,s);
  memcpy(a,b,s);
  memcpy(b,c,s);
  free(c);
}

Considérons maintenant une bonne pratique sur l'utilisation des pointeurs dans les signatures de fonctions. Premièrement, il faut étudier les cas particuliers d'utilisation des pointeurs en tant que paramètres de fonctions:

• Passage par adresse explicite
• Structures de données dont l'implantation est un pointeur (listes, arbres ... )
• Tableaux
• Chaînes de caractères
• Pointeur comme donnée ou pointeurs génériques (void*)

Il est intéressant d'identifier ces différents cas au premier coup d'oeil, c'est à dire en regardant uniquement la signature de la fonction. Pour ça, on peut utiliser quelques conventions:

• Structures de données: la bonne pratique est de cacher le pointeur par un typedef (ce que je fais dans les exemples.) D'autant plus que cette approche favorise une politique de types abstraits, où l'implantation est cachée (si possible) et seules les opérations fournies accèdent à la représentation interne des données. Donc dans ce cas, il n'y a pas d'étoile associée au paramètre.
• Tableaux: les crochets vides ont la même signification que l'étoile dans la signature, on préférera donc la notation int t[] à la notation int *t pour un tableau.
• Chaînes de caractères: la plus part du temps, les chaînes de caractères sont traitées comme des tableaux, on peut donc suivre la même convention (voir la suite pour les tableaux de chaînes.)

Comme on le voit, on peut simplement éliminer les étoiles des signatures lorsque les paramètres appartiennent à une catégorie bien définie. Il ne reste que quelques cas, dont le passage par adresse. On choisira donc de considérer qu'un pointeur explicite dans une signature correspond soit à un passag par adresse, soit à un pointeur comme donnée (relativement rare, hormis les pointeurs void*.)

Il reste quand même quelques ambiguïtés:

• char *t[] représente-t-il un tableau de chaînes de chaînes de caractères ou un pointeur sur un tableau de caractères ? La syntaxe du C ne nous permet pas de faire la différence, il faut donc utiliser un commentaire explicite devant la signature.
• De manière générale, le paramètre <type> *t[] peut être vu comme un tableau de pointeurs, un pointeur sur un tableau ou un tableau de tableau, on préférera utiliser un typedef lorsque c'est possible pour minimiser les ambiguïtés.

Quelques exemples:

/*
 * le type t_list est abstrait, il n'est donc pas nécessaire de savoir
 * qu'il s'agit en réalité d'un pointeur.
 */
t_list add(int x, t_list l);
 
/*
 * la tête de la liste l peut être modifiée par la fonction, elle est
 * donc passée par adresse, d'où l'étoile sur le type.
 */
void insert(int x, t_list *l);
 
/*
 * la fonction va directement renvoyer le nouveau point d'entrée de la
 * file, il est donc inutil de la passer par adresse.
 */
t_queue push(void *x, t_queue q);
 
/*
 * la fonction va modifier le point d'entrée de la file, mais la valeur
 * de retour est déjà utilisée, on passe donc la file par adresse.
 */
void *take(t_queue *q);
 
/*
 * dans cette fonction, v est un tableau tandis que sum est un pointeur
 * (semble-t-il) va recevoir un des résultats de la fonction. La bonne
 * nomenclature et la convention d'utilisation des étoiles permet de voir
 * directement que cette fonction devrait renvoyer le compte des éléments
 * et mettre dans l'entier pointé par sum la somme des éléments du vecteur.
 */
size_t sum_count(int v[], int *sum);
/*
 * attention, il reste quand même une ambiguïtés sur cette fonction, en
 * effet, quel est la taille de v ? Comment va-t-on borner la boucle ?
 * dans l'exemple, on peut supposer que notre tableau utilise une valeur
 * particulière pour marquer la fin des données (MAX_INT ou MIN_INT ... )
 */

Structures spécifiques au C

Contrairement au langage Algo, le C permet la définition de tableaux dynamiques (dont la taille est définie à l'exécution.) Plus intéressant, il permet également de ré-allouer les tableaux avec une taille différente.

On peut donc implanter des listes statico-dynamiques, c'est à dire des vecteurs de tailles dynamiques. Voici un exemple d'implantation:

#include <stdlib.h>
#include <unistd.h>
 
typedef struct s_vect  *t_vect;
struct s_vect
{
  size_t                last, size;
  int                  *tab;
};
 
/* create new vector */
t_vect make_vect()
{
  t_vect                v;
  v = malloc(sizeof (struct s_vect));
  v->last = 0;
  v->size = 1;
  v->tab = malloc(sizeof (int));
  return v;
}
 
/* add x at the end of the vector v*/
void add(int x, t_vect v)
{
  if (v->last >= v->size)
    {
      /* size = size * 2 */
      v->size <<= 1;
      v->tab = realloc(v->tab, v->size * sizeof (int));
    }
  v->tab[v->last++] = x;
}

Conclusion

L'étude des algorithmes est fortement liée à la construction des premiers langages de programmation qui sont pour la majeure partie impératif (fortran, algol, BCPL, pascal ... ) Par conséquent, les algorithmes classiques s'écrivent bien dans ces langages. Le C est un héritier direct de certains de ces langages (fortran, algol et BCPL principalement) et par conséquent on retrouve très rapidement les mêmes repères.

L'aspect gestion de la mémoire du C permet également (comme on l'a vu sur le petit exemple des vecteurs) d'agrémenter l'écriture d'algorithme de petites fonctionnalités pratiques.

Cours	Partie
Cours de Programmation EPITA/spé	Programmation:C