Projet Informatique Théorique 2016
Instructions et Documentation
|
#include <stdint.h>
#include "avl.h"
Aller au code source de ce fichier.
Définitions de type | |
typedef struct Table | Table |
Définit le type d'une table. Plus de détails... | |
typedef struct avl_traverser | Table_iterateur |
Définit le type d'un itérateur sur les éléments d'une table. | |
Fonctions | |
Table * | creer_table (int(*comparer_cle)(const intptr_t cle1, const intptr_t cle2), intptr_t(*copier_cle)(const intptr_t cle), void(*supprimer_cle)(intptr_t cle)) |
Renvoie une nouvelle table. Plus de détails... | |
void | liberer_table (Table *table) |
Cette fonction détruit une table. La mémoire qui a été allouée par la table pour stocker les clés sont aussi détruites. Attention, la table ne gère pas la mémoire associée aux valeurs. C'est à l'utilisateur de détruire proprement les valeurs. | |
void | add_table (Table *table, const intptr_t cle, const intptr_t valeur) |
La fonction add_table() ajoute une association entre une clé et une valeur. Pour cela, add_table(), crée une copie de la clé passée en paramètre, l'enregistre dans la table et l'associe à la valeur passée en paramètre. La mémoire de la copie de la clé est gérée par la table. La mémoire de la clé passée en paramètre reste à la charge de l'utilisateur. Plus de détails... | |
intptr_t | delete_table (Table *table, const intptr_t cle) |
Supprime une clé de la table. La mémoire de la clé est libérée et la valeur associée à la clé est perdue. Plus de détails... | |
void | vider_table (Table *table) |
Supprime toutes les clés de la table. | |
void | print_table (Table *table, void(*print_cle)(const intptr_t cle), void(*print_valeur)(const intptr_t valeur), const char *text_de_fin) |
Affiche la table. Vous devez donner en paramètres de print_table, des fonctions pour afficher les clés et les valeurs. Plus de détails... | |
void | pour_toute_valeur_table (const Table *table, void(*action)(intptr_t valeur)) |
La fonction passe en revue toutes les valeurs de la table passée en paramètre et apelle la fonction passée en paramètre pour chacune des valeur parcourues. Une valeur est parcourue autant de fois qu'elle apparaît dans la table, et la fonction est executée autant de fois que la valeur apparaît. Plus de détails... | |
void | pour_toute_cle_valeur_table (const Table *table, void(*action)(const intptr_t cle, intptr_t valeur, void *data), void *data) |
La fonction passe en revue toutes les associaitons (clé, valeur) de la table, et apelle la fonction passée en paramètre pour chasune de ces associations. Plus de détails... | |
Table_iterateur | trouver_table (const Table *table, const intptr_t cle) |
Renvoie un itérateur positionné sur l'association dont la clé est identique (pour la fonction de comparaison de clé de la table) à la clé passée en paramètre. | |
Table_iterateur | premier_iterateur_table (const Table *table) |
Renvoie un itérateur positionné sur la première association de la table. Plus de détails... | |
Table_iterateur | iterateur_suivant_table (Table_iterateur iterator) |
Renvoie l'itérateur suivant. Plus de détails... | |
Table_iterateur | iterateur_precedent_table (Table_iterateur iterator) |
Renvoie l'itérateur précédent. Plus de détails... | |
int | iterateur_est_vide (Table_iterateur iterator) |
Renvoie 1 si l'itérateur passé en paramètre est vide. Renvoie 0 sinon. | |
intptr_t | get_cle (Table_iterateur it) |
Renvoie la clé de l'association pointée par l'itérateur passé en paramètre. | |
intptr_t | get_valeur (Table_iterateur it) |
Renvoie la valeur de l'association pointée par l'itérateur passé en paramètre. | |
int | taille_table (Table *t) |
Renvoie la taille de la table. | |
Table* creer_table | ( | int(*)(const intptr_t cle1, const intptr_t cle2) | comparer_cle, |
intptr_t(*)(const intptr_t cle) | copier_cle, | ||
void(*)(intptr_t cle) | supprimer_cle | ||
) |
Renvoie une nouvelle table.
La clé et la valeur peuvent être des entiers ou bien des structures plus compliquées.
La mémoire associée à la clé est gérée par la table, alors que celle de la valeur est laissée à la charge de l'utilisateur. C'est pourquoi, à la création de la table, il faut donner des pointeurs de fonctions à la table pour lui permettre de copier, supprimer et comparer des clés. Si vous choisissez d'utiliser des entiers pour coder la clé, vous pouvez mettre tous les paramètres 'comparer_cle', 'copier_cle' et 'supprimer_cle' à NULL. En effet, dans ce cas, la table se chargera d'utiliser ses propres fonctions pour copier et comparer les clés.
Voici un exemple qui
Table * table = creer_table( NULL, NULL, NULL );
add_table( table, 1, 2 ); add_table( table, 2, 30 );
Table_iterateur it; for( it = premier_iterateur_table( table ); ! iterateur_est_vide( it ); it = iterateur_suivant_table( it ) ){ printf( "cle : %d -> valeur : %d \n", get_cle( it ), get_valeur( it ) ); }
liberer_table( t )
Dans cet exemple, nous montrons comment associer un entier à un couple
typdef struct { int x; int y; } Couple; // On définit le couple
Table * t = creer_table( NULL; NULL, NULL ); // On crée la table
Couple * c = malloc( sizeof(Couple) ): // On crée une valeur c.x = 1; c.y=2;
add_table( t,(intptr_t) c ); // On ajoute la valeur dans la table
... // On utilise la table
pour_toute_valeur_table( t, free ) // On détruit les valeurs // La mémoire des valeurs n'est pas // gérée par la table ! liberer_table( t ); // On détruit la table
Voici maintenant un exemple de table où l'on associe un couple à un entier
typdef struct { int x; int y; } Couple; // On définit la clé
int comparer_couple( Couple* c1, Couple* c2 ){ if( c1.x == c2.x ) return c1.y -c2.y; return c1.x - c2.x; }
Couple* copier_couple( const Couple* c ){ Couple * res = malloc( sizeof(Couple) ); res.x = c->x; res.y = c->y; return res; }
void supprimer_couple( Couple* c ){ free( c ); }
typdef struct { int x; int y; } Couple; // On définit le couple
Table * table = creer_table( // On crée la table ( void(*)( const intptr_t, const intptr_t) ) comparer_couple, ( void(*)( const intptr_t ) ) copier_couple, ( void(*)( intptr_t ) ) supprimer_couple );
Couple c; c.x = 3; c.y = 4;
add_table( table, (intptr_t) &c, 4 ); // On ajoute l'associaiton (3,4) –> 4
... // On utilise la table
liberer_table( table ); // On détruit la table
void add_table | ( | Table * | table, |
const intptr_t | cle, | ||
const intptr_t | valeur | ||
) |
La fonction add_table() ajoute une association entre une clé et une valeur. Pour cela, add_table(), crée une copie de la clé passée en paramètre, l'enregistre dans la table et l'associe à la valeur passée en paramètre. La mémoire de la copie de la clé est gérée par la table. La mémoire de la clé passée en paramètre reste à la charge de l'utilisateur.
Dans une table, il ne peut pas y avoir deux clés identiques en même temps. Si la clé passée en paramètre à add_table() existe déjà dans la table, alors, l'ancienne valeur associée à la clé est remplacée par la nouvelle passée en paramètre à add_table().
intptr_t delete_table | ( | Table * | table, |
const intptr_t | cle | ||
) |
void print_table | ( | Table * | table, |
void(*)(const intptr_t cle) | print_cle, | ||
void(*)(const intptr_t valeur) | print_valeur, | ||
const char * | text_de_fin | ||
) |
Affiche la table. Vous devez donner en paramètres de print_table, des fonctions pour afficher les clés et les valeurs.
Si les clés ou les valeurs sont des entiers, vous pouvez ne pas donner ces fonctions en remplissant les champs par le pointeur vide : NULL .
void pour_toute_valeur_table | ( | const Table * | table, |
void(*)(intptr_t valeur) | action | ||
) |
La fonction passe en revue toutes les valeurs de la table passée en paramètre et apelle la fonction passée en paramètre pour chacune des valeur parcourues. Une valeur est parcourue autant de fois qu'elle apparaît dans la table, et la fonction est executée autant de fois que la valeur apparaît.
La fonction qui sera executée (et qui a été passée en paramètre), doit posséder l'entête suivante : void NON_FONCTION( intptr_t valeur, void* data ), void NON_FONCTION( const intptr_t cle, intptr_t valeur, void* data ), Le pramètre 'valeur' correspond à la valeur qui est en train d'être parcouru. Le paramètre 'data' est un pointeur qui sera identique à celui passé par le paramètre 'data' de la fonction pour_toute_transition().
void pour_toute_cle_valeur_table | ( | const Table * | table, |
void(*)(const intptr_t cle, intptr_t valeur, void *data) | action, | ||
void * | data | ||
) |
La fonction passe en revue toutes les associaitons (clé, valeur) de la table, et apelle la fonction passée en paramètre pour chasune de ces associations.
La fonction qui sera executée (et qui a été passée en paramètre), doit posséder l'entête suivante : void NON_FONCTION( const intptr_t cle, intptr_t valeur, void* data ), Les pramètres 'cle et 'valeur' correspondent à la clé et la valeur de l'association qui est en train d'être parcouru. Le paramètre 'data' est un pointeur qui sera identique à celui passé par le paramètre 'data' de la fonction pour_toute_transition().
Table_iterateur premier_iterateur_table | ( | const Table * | table | ) |
Table_iterateur iterateur_suivant_table | ( | Table_iterateur | iterator | ) |
Renvoie l'itérateur suivant.
C'est-à-dire, l'itérateur renvoyé est positionné sur une nouvelle association qui est la plus petite des associations plus grandes que celle associée à l'itérateur passé en en paramètre.
Deux associations sont comparées en comparant leurs clés et la fonction de comparaison des clés de la table.
S'il n'y a pas d'itérateur suivant (l'itérateur passé en paramètre est associé à la plus grande association), l'itérateur vide est renvoyé.
Table_iterateur iterateur_precedent_table | ( | Table_iterateur | iterator | ) |
Renvoie l'itérateur précédent.
C'est-à-dire, l'itérateur renvoyé est positionné sur une nouvelle association qui est la plus grande des associations plus petites que celle associée à l'itérateur passé en en paramètre.
Deux associations sont comparées en comparant leurs clés par la fonction de comparaison des clés de la table.
S'il n'y a pas d'itérateur précédent (l'itérateur passé en paramètre est associé à la plus petite association), l'itérateur vide est renvoyé.