Ecrivez les fonctions du fichier avl.c correspondant au fichier avl.h ci-dessous :
#ifndef AVL_H
#include"linkedList.h"
#define AVL_H
typedef struct
{
/*
Pointeur vers une fonction permettant de
recuperer la cle de chaque donnee.
*/
int (*getKey)(void*);
/*
Pointeur vers une fonction permettant de
de detruire chaque donnee.
*/
void (*freeData)(void*);
/*
Pointeur vers la racine de l'arbre.
*/
void* root;
}avl ;
/*------------------------------------------------------*/
/*
Retourne un AVL vide.
*/
avl* avlCreate(int (*getKey)(void*), void (*freeData)(void*));
/*
Modifie la fonction de destruction des donnees.
*/
void avlSetFreeFunction(avl* a, void (*freeData)(void*));
/*
Affiche les cles de l'AVL a dans l'ordre croissant, O(n).
*/
void avlPrintKeys(avl* a);
/*
Insere la donnee v dans l'AVL a, O(log n).
*/
void avlInsert(avl* a, void* v);
/*
Retourne la donnee de cle x si elle se trouve dans l'AVL a,
NULL sinon, O(log n).
*/
void* avlFind(avl* a, int x);
/*
Supprime le noeud de cle k de l'AVL a, applique la fonction
de destruction a la donnee de cle k, O(log n).
*/
void avlRemove(avl* a, int k);
/*
Detruit l'AVL a, applique la fonction de destruction a
toutes les donnees du sous-arbre, O(n).
*/
void avlDestroy(avl* a);
/*
Retourne une liste chainee contenant toutes les donnees
de l'AVL a disposees dans l'ordre croissant, O(n).
*/
linkedList* avlToList(avl* a);
#endif
avl.hfichier source.
Et voici avl.c.
#include<stdio.h>
#include<malloc.h>
#include"avl.h"
/*------------------------------------------------------*/
/*
Noeud de l'ABR.
*/
typedef struct nd
{
/*
key est la cle du noeud courant.
*/
int key;
/*
pointeur vers l'element de cle key
*/
void* data;
/*
hauteur du sous-arbre :
0 si ce noeud est une feuille.
*/
int height;
/*
Pointeur vers le sous-arbre droit.
*/
struct nd * left;
/*
Pointeur vers le sous-arbre gauche.
*/
struct nd * right;
}node;
/*------------------------------------------------------*/
/*
Retourne la hauteur de l'arbre de racine l,
-1 si l est vide.
*/
int getHeight(node* l)
{
}
/*------------------------------------------------------*/
/*
Retourne la plus grande des deux valeurs i et j.
*/
int max(int i, int j)
{
}
/*------------------------------------------------------*/
/*
Met a jour la hauteur de la racine l en fonction des
hauteurs des racines des deux sous-arbres.
*/
void setHeight(node* l)
{
}
/*------------------------------------------------------*/
/*
Cree un noeud contenant la donnee data,
ayant pour sous-arbre gauche l et
pour sous-arbre droit r.
*/
node* nodeCreate(int (*getKey)(void*), node* l, void* data, node* r)
{
}
/*------------------------------------------------------*/
/*
Retourne un avl vide
*/
avl* avlCreate(int (*getKey)(void*), void (*freeData)(void*))
{
}
/*------------------------------------------------------*/
/*
Fait de freeData la fonction de destruction des donnees.
*/
void avlSetFreeFunction(avl* a, void (*freeData)(void*))
{
}
/*------------------------------------------------------*/
/*
Affiche toutes les cles du sous-arbre de racine n dans
l'ordre croissant.
*/
void nodePrintKeys(node* n)
{
}
/*------------------------------------------------------*/
/*
Affiche pour tous les noeuds du sous-arbre de racine n
la difference entre les hauteurs du sous-arbre droit et
gauche.
*/
void nodePrintLevels(node* n)
{
}
/*------------------------------------------------------*/
/*
Effectue une rotation droite de l'arbre de racine x,
retourne la racine de l'arbre apres rotation.
*/
node* rotateRight(node* x)
{
}
/*------------------------------------------------------*/
/*
Effectue une rotation gauche de l'arbre de racine x,
retourne la racine de l'arbre apres rotation.
*/
node* rotateLeft(node* x)
{
}
/*------------------------------------------------------*/
/*
Effectue une rotation gauche-droite de l'arbre de racine x,
retourne la racine de l'arbre apres rotation.
*/
node* rotateLeftRight(node* x)
{
}
/*------------------------------------------------------*/
/*
Effectue une rotation droite-gauche de l'arbre de racine x,
retourne la racine de l'arbre apres rotation.
*/
node* rotateRightLeft(node* x)
{
}
/*------------------------------------------------------*/
/*
Reequilibre l'arbre de racine x, retourne la racine de
l'arbre apres reequilibrage. On part du principe
que les hauteurs des sous-arbres droit et gauche different
de au plus 1.
*/
node* balance(node* x)
{
}
/*------------------------------------------------------*/
/*
Insere la donnee v dans l'arbre de racine n
et reequilibre l'arbre, retourne la racine de
l'arbre apres insertion et reequilibrage.
*/
node* nodeInsert(int (*key)(void*), node* n, void* v)
{
}
/*------------------------------------------------------*/
/*
Insere la donnee v dans l'arbre a, O(log n).
*/
void avlInsert(avl* a, void* v)
{
}
/*------------------------------------------------------*/
/*
Affiche les cles de l'AVL a dans l'ordre croissant, O(n)
*/
void avlPrintKeys(avl* a)
{
}
/*------------------------------------------------------*/
/*
Affiche pour chaque noeud la difference entre les hauteurs
des sous-arbres droit et gauche de l'AVL.
*/
void avlPrintLevels(avl* a)
{
}
/*------------------------------------------------------*/
/*
Retourne la donnee de cle k si elle se trouve dans le sous-arbre
de racine n, NULL sinon.
*/
void* findNode(node* n, int k)
{
}
/*------------------------------------------------------*/
/*
Retourne la donnee de cle x si elle se trouve dans l'AVL a,
NULL sinon, O(log n)
*/
void* avlFind(avl* a, int x)
{
}
/*------------------------------------------------------*/
/*
Fait pointer *max vers le noeud de cle maximale dans
le sous-arbre de racine n, detache le noeud *max de l'arbre
et retourne la racine de l'arbre apres suppression.
*/
node* removeMax(node* n, node** max)
{
}
/*------------------------------------------------------*/
/*
Fait pointer *min vers le noeud de cle minimale dans
le sous-arbre de racine n, detache le noeud *min de l'arbre
et retourne la racine de l'arbre apres suppression.
*/
node* removeMin(node* n, node** min)
{
}
/*------------------------------------------------------*/
/*
Supprime le noeud de cle k du sous-arbre de racine n,
applique la fonction de destruction a la donnee de ce noeud,
et retourne la racine de l'arbre apres la suppression.
*/
node* removeNode(node* n, int k, void (*freeData)(void*))
{
}
/*------------------------------------------------------*/
/*
Supprime le noeud de cle k de l'AVL a, applique la fonction
de destruction a la donnee de cle k, O(log n).
*/
void avlRemove(avl* a, int k)
{
}
/*------------------------------------------------------*/
/*
Place dans la liste chainee l toutes les donnees
du sous-arbre de racine n dans l'ordre croissant.
*/
void nodeToList(node* n, linkedList* l)
{
}
/*------------------------------------------------------*/
/*
Retourne une liste chainee contenant toutes les donnees
de l'AVL a disposees dans l'ordre croissant, O(n).
*/
linkedList* avlToList(avl* a)
{
}
/*------------------------------------------------------*/
/*
Detruit tous les noeuds du sous-arbre de racine n,
applique la fonction de destruction fr a toutes les
donnees du sous-arbre.
*/
void nodeDestroy(node* n, void (*fr)(void*))
{
}
/*------------------------------------------------------*/
/*
Detruit l'AVL a, applique la fonction de destruction a
toutes les donnees du sous-arbre, O(n).
*/
void avlDestroy(avl* a)
{
}
/*------------------------------------------------------*/
/*------------------------------------------------------*/
/*
Pour tester les algorithmes
*/
void destroyInt(void* i)
{
free((int*)i);
}
int getIntKey(void* i)
{
return *((int*)i);
}
void doNothing()
{
}
int main()
{
int i;
int* d;
linkedList* l;
link* m;
avl* a = avlCreate(getIntKey, destroyInt);
for (i = 0 ; i < 40 ; i++)
{
d = (int*)malloc(sizeof(int));
*d = i;
avlInsert(a, d);
}
avlPrintKeys(a);
avlPrintLevels(a);
for(i = 0 ; i < 40 ; i+=5)
avlRemove(a, i);
avlPrintKeys(a);
avlPrintLevels(a);
l = avlToList(a);
for(m = linkedListGetFirst(l); m != NULL ; m = m->next)
printf("%d -> ", *(int*)(m->data));
printf("\n");
linkedListDestroy(l, doNothing);
avlSetFreeFunction(a, destroyInt);
avlDestroy(a);
return 0;
}
avlVide.cfichier source.