D1:EPITA:Atelier:C:TP:2013:2014

D1: Des pointeurs dans tous les sens !

Notre objectif est de manipuler des pointeurs le plus possible: passage par adresse, chaînes de caractères, tableaux …

Passage par adresse

L'un des utilisations les plus courantes des pointeurs est le passage de paramètre par adresse pour modification (ou stockage de résultat.)

Un exemple pour la forme

Nous allons utiliser un simple calcul de factorielle itératif et au lieu de renvoyer le résultat, celui-ci sera stocké dans la variable dont l'adresse est passé en paramètre.

// compute n! and store result in *res
void fact_proc(unsigned n, unsigned *res);

Le classique: swap

L'exemple le plus courant de passage par adresse: swap(a,b)

void swap(int *a, int *b);

Récursion et passage par adresse

Nous allons utiliser le passage par adresse dans une fonction récursive pour pouvoir avoir deux résultats, la valeur renvoyée et celle stockée dans le paramètre passé par adresse.

Le calcul suivant est un prétexte, il est donc important d'écrire la fonction suivante de manière récursive, même s'il est possible de le faire en itératif.

La fonction suivante calcule la somme des cases du tableau (tab) et la somme des carrés des cases du tableau, la fonction renvoie la somme et stocke le résultat dans la variable passée par adresse. Pour ce déplacer dans le tableau, il suffit de faire avancer le pointeur: vous appelez la fonction avec tab+1. La fonction s'arrête lorsque la case courante contient un entier négatif.

int sum_and_squaresum(int tab[], int *squared_sum);

Chaînes de caractères

Nous allons faire les manipulations classiques, décrites dans string.h, voici la liste des fonctions à écrire, vous irez lire les pages de manuel correspondantes pour avoir les détails.

Voici l'en-tête, vous écrirez le code correspondant:

/* Recoding libc strings functions ! */
 
#ifndef _MYSTRING_H_
#define _MYSTRING_H_
 
/*
 * For more precise definition of these functions read their man pages.
 */
 
// string length
size_t mystrlen(const char *s);
 
// copy atmost n bytes from src to dest
// 0 pad dest if src contains less than n bytes
char *mystrncpy(char *dest, const char *src, size_t n);
 
// copy atmost n bytes of src at the end of dest
// always add the final 0 at the end of dest
char *mystrncat(char *dest, const char *src, size_t n);
 
// compare lexicographically atmost n bytes of s1 and s2
// returns: 0 equal, negative s1 is smaller, positive otherwise
int mystrncmp(const char *s1, const char *s2, size_t n);
int mystrncasecmp(const char *s1, const char *s2, size_t n);
 
// returns the pointer to first occurrence of c in s
// returns NULL if c is not found
char *mystrchr(const char *s, int c);
// Same as above but return the last occurrence
char *mystrrchr(const char *s, int c);
 
// returns a copy of s allocated with malloc(3)
char *mystrdup(const char *s);
 
#endif

Tableaux et tris

Nous allons maintenant faire du tris. Mais pour commencer, créons et manipulons quelques tableaux.

Allocation et remplissage

Pour créer un tableau, il faut réserver de la mémoire, suffisamment, et dans certains cas remplir le tableau.

Pour calculer la bonne taille, il vous faut le nombre de cases mais aussi leur taille.

Nous allons écrire une fonction qui réalise l'allocation générique d'un tableau à partir du nombre de cases et de la taille de ces cases. Cette fonction n'est pas vraiment utile, mais attention, bien que ses paramètres soient les mêmes, elle ne fait pas la même chose que la fonction calloc(3) (qui elle en plus d'allouer la mémoire initialise celle-ci à 0.)

void *allocate_array(size_t size, size_t cell_size);

Nous allons maintenant écrire une fonction qui remplit un tableau à partir d'une valeur passée en argument.

void fill_array(int tab[], size_t size, int value);

Remplissage aléatoire

Nous allons maintenant écrire une fonction de remplissage aléatoire:

void random_fill(int tab[], size_t size, int max_value);

Remplissez le tableau à l'aide de la fonction random(3) (lisez bien la page de manuel.) Vous utiliserez un modulo entre le résultat de la fonction et la valeur maximale passée en argument.

Insertion dans un vecteur

Nous allons manipuler les tableaux comme des vecteurs (au sens de conteneur), nos tableaux auront une taille maximale (la taille allouée) et une taille courante (l'index de la prochaine case libre.) Comme nous n'avons pas encore de structure, toutes ces valeurs seront fournies en argument de notre fonction.

Pour gérer les problèmes de place, nous feront appel à realloc(3) qui permet de redimensionner une zone mémoire allouée par malloc(3). Comme realloc(3) renvoie un nouveau pointeur, nous devrons passer le tableau par adresse (nous allons donc passer un pointeur sur une tableau) ainsi que la taille et la taille maximale.

void add(int *(tab[]), size_t *max_size, size_t *size, int value);

Notez que le fait de déclarer le paramètre sous la forme int *(tab[]) n'est là que pour insister sur le fait qu'il s'agisse d'un pointeur sur un tableau, mais nous aurions pu utiliser int **tab

Recherche dichotomique

Utiliser la technique dite dichotomique pour chercher une valeur dans un tableau trié. La fonction prend en argument le tableau, l'index de la case la plus à gauche et celle de la plus à droite et enfin la valeur à chercher. La fonction renvoie finalement l'index de la valeur recherchée si celle-ci appartient au tableau et -1 sinon.

int find(int tab[], int left, int right, int value);

Pour mettre en pratique l'arithmétique des pointeurs, on va maintenant réécrire cette fonction en utilisant uniquement un pointeur de début et un pointeur de fin. On renverra le pointeur sur la valeur dans le tableau.

int *find2(int *left, int *right, int value);

Tri

Faites un peu de recherche et implémentez un quicksort en utilisant l'algorithme en-place.

Vous devrez écrire deux fonctions:

// sort(tab,len) is the recursive quick sort function
void quick_sort(int tab[], size_t len);
// partition(tab, len) is the partition function
int *partition(int tab[], size_t len);

Vous noterez que l'on utilise l'approche pointeur plutôt que tableau: vous devez appeler votre fonction avec le pointeur positionné sur la borne gauche du tableau et le bon nombre de cases à considérer en paramètre. Pour la fonction partition, vous retournerez le pointeur sur la position finale du pivot dans le tableau.

Dans notre version, le choix du pivot doit se faire au début de la fonction partition (les classiques marchent bien comme le milieu ou le médian entre le premier le dernier et le milieu … )

Histogramme

On va maintenant compter les occurrences des différentes valeurs possible dans un buffer. On s'intéresse à la valeur possible de chaque octet et au nombre de fois que celle-ci apparaît dans le tableau. La fonction renvoie le nombre valeurs différentes qui apparaissent dans les données.

// data: the original data buffer
// len : size of the data
// hist: array for the result (allocated but not initialized.)
// length of hist is, of course, 256
size_t compute_hist(char data[], size_t len, size_t hist[]);

Vous testerez votre fonction sur un tableau rempli aléatoirement ou rempli avec un texte.

Pour aller plus loin

Le calcul d'un histogramme est la première étape pour réaliser le codage de Huffman, vous pouvez essayer de trouver la suite de la méthode et terminer le travail …