Cours d'algorithmique 2 - Intranet 1 8 novembre 2006 Cours dAlgorithmique Listes, piles et files. Arbres. Types de données abstraits. Implantations

Cours d'algorithmique 2 - IntranetCours d'algorithmique 2 - Intranet 118 novembre 20068 novembre 2006

Cours d’AlgorithmiqueCours d’Algorithmique

Listes, piles et files.Listes, piles et files.

Arbres.Arbres.

Types de données abstraits.Types de données abstraits.

Implantations.Implantations.

8 novembre 20068 novembre 2006 Cours d'algorithmique 2 - IntranetCours d'algorithmique 2 - Intranet 22

• Trier et chercherTrier et chercher• Listes et arbresListes et arbres• Le back-trackLe back-track• Arbres équilibrésArbres équilibrés• Récursivité et induction sur la structureRécursivité et induction sur la structure• Divide and conquerDivide and conquer• MinimaxMinimax• DérécursionDérécursion• Divers problèmes particuliersDivers problèmes particuliers• Logique de HoareLogique de Hoare• Programmation dynamiqueProgrammation dynamique• Complexité et calculabilitéComplexité et calculabilité

Les grandes lignes du coursLes grandes lignes du cours


Voici des listes !Voici des listes !

22 22 1144

00 22 44 66 88 1010

2244 22 1122 -1-166 1010

44

TableauTableau


22 22 1144

00 22 44 66 88 1010

2244 22 1122 -1-166 1010

44

TableauTableau




22 22 1144

00 22 44 66 88 1010

2244 22 1122 -1-166 1010

44

TableauTableau



22 22 1144

00 22 44 66 88 1010

2244 22 1122 -1-166 1010

44

TableauTableau



22 22 1144

00 22 44 66 88 1010

2244 22 1122 -1-166 1010

44

TableauTableau



22 22 1144

00 22 44 66 88 1010

2244 22 1122 -1-166 1010

44

TableauTableau

FINFIN


Caractérisations d’une liste !Caractérisations d’une liste !

• Un élément plus un lien vers le suivant.Un élément plus un lien vers le suivant.

• Séquence ordonnée finie.Séquence ordonnée finie.– Suite ordonnée des mathématiques.Suite ordonnée des mathématiques.

• Un tableau peut être vu comme une liste, si on limite les Un tableau peut être vu comme une liste, si on limite les accès aléatoires.accès aléatoires.– On lit T[0], puis T[1], etc, par exemple.On lit T[0], puis T[1], etc, par exemple.

• Une liste est caractérisée parUne liste est caractérisée par– ses propriétés et fonctions d’accèsses propriétés et fonctions d’accès– et non sa réalisation.et non sa réalisation.


Constructeurs et prédicats sur listesConstructeurs et prédicats sur listes----------------------------------------------------------------------------------------------------------------------------------

Soit Soit LTLT le type des listes d’éléments de type le type des listes d’éléments de type TT..

Le constructeur de la liste vide :Le constructeur de la liste vide :

cree_vide : void ->cree_vide : void -> LTLT





cree_vide : void -> cree_vide : void -> LTLT

Le constructeur général :Le constructeur général :

ajout_liste : ajout_liste : T T x x LTLT -> -> LTLT





cree_vide : void -> cree_vide : void -> LTLT

Le constructeur général :Le constructeur général :

ajout_liste : ajout_liste : T T x x LTLT -> -> LTLT

Le prédicat qui distingue les deux cas Le prédicat qui distingue les deux cas ::

est_vide : est_vide : LTLT -> BOOL -> BOOL



Les propriétés vérifiées par ces fonctions :Les propriétés vérifiées par ces fonctions :

est_videest_vide ( cree_vide () ) = ( cree_vide () ) = VraiVrai

est_vide ( ajout_liste ( e , l ) ) = est_vide ( ajout_liste ( e , l ) ) = FauxFaux

• La seule liste vide est celle créée par « cree_vide ».La seule liste vide est celle créée par « cree_vide ».

• Aucune liste obtenue par adjonction d’un élément « a » Aucune liste obtenue par adjonction d’un élément « a » à une liste « l » n’est vide.à une liste « l » n’est vide.

• Salutations de la part de Monsieur de la Palisse !Salutations de la part de Monsieur de la Palisse !


Fonctions d’accès sur listesFonctions d’accès sur listes----------------------------------------------------------------------------------------------------------------------------------

La fonction d’accès à l’élément :La fonction d’accès à l’élément :

tete_liste : tete_liste : LTLT -> -> TT

La fonction d’accès à la suite de la La fonction d’accès à la suite de la liste :liste :

queue_liste : queue_liste : LTLT -> -> LTLT



La fonction d’accès à l’élément :La fonction d’accès à l’élément :

tete_liste : tete_liste : LTLT -> -> TT

La fonction d’accès à la suite de la La fonction d’accès à la suite de la liste :liste :

queue_liste : queue_liste : LTLT -> -> LTLTLes propriétés vérifiées par ces fonctions :Les propriétés vérifiées par ces fonctions :

tete_listetete_liste ( ajout_liste ( a , l ) ) = ( ajout_liste ( a , l ) ) = a a

queue_listequeue_liste ( ajout_liste ( a , l ) ) ( ajout_liste ( a , l ) ) = l= l



Les limitations d’application de ces fonctions,Les limitations d’application de ces fonctions,les appels suivants sont interdits :les appels suivants sont interdits :

tete_listetete_liste ( cree_vide () )( cree_vide () )

queue_listequeue_liste ( cree_vide () )( cree_vide () )






Ce qui est vraiment caractéristique d’une liste Ce qui est vraiment caractéristique d’une liste ::







On parle d’une structureOn parle d’une structure

Ce qui est vraiment caractéristique d’une liste Ce qui est vraiment caractéristique d’une liste ::


LLast ast IIn - n - FFirst irst OOut ut (LIFO)(LIFO)


Types de données abstraitsTypes de données abstraits----------------------------------------------------------------------------------------------------------------------------------

• Nous nous sommes donné des noms de types :Nous nous sommes donné des noms de types :– un type de base un type de base T T,,– un type de liste un type de liste LT LT sur ce type de base.sur ce type de base.




• Nous nous sommes donné des fonctions et leurs propriétés :Nous nous sommes donné des fonctions et leurs propriétés :– cree_vide , ... ,cree_vide , ... ,– est_vide ( cree_vide () ) = Vrai , … .est_vide ( cree_vide () ) = Vrai , … .





• Nous n’avons pas besoin de devenir plus concrets.Nous n’avons pas besoin de devenir plus concrets.





• Nous n’avons pas besoin de devenir plus concrets.Nous n’avons pas besoin de devenir plus concrets.

C’est un C’est un type de données abstrait.type de données abstrait.


Exemple d’implantationExemple d’implantation----------------------------------------------------------------------------------------------------------------------------------

22 11ajout_listeajout_liste ( ( 55 , , ) )

22 1155

ajout_listeajout_liste ( ( 55 , , cree_vide cree_vide ()() ) )

55


Exemple d’implantationExemple d’implantation----------------------------------------------------------------------------------------------------------------------------------

22 11

tete_listetete_liste ( )( )

22 1155

5

queue_listequeue_liste ( ( ) )

22 1155


L I S T E S L I S T E S E TE T

P I L E S ! ! !P I L E S ! ! !

Listes et pilesListes et piles----------------------------------------------------------------------------------------------------------------------------------



22 1155



22 1155

22

11

55



22 1155

22

11

55

Pile ( d’assiettes )Pile ( d’assiettes )stack en anglaisstack en anglais



22 1155

22

11

55


ajout_liste = push = ajout_liste = push = empilerempiler

tete_liste = top = sommettete_liste = top = sommet

queue_liste = pop = queue_liste = pop = dépilerdépiler



22 1155

22

11

55


ajout_liste = push = ajout_liste = push = empilerempiler

tete_liste = top = sommettete_liste = top = sommet

queue_liste = pop = queue_liste = pop = dépilerdépiler

LIFO !LIFO !


Listes et piles : les différencesListes et piles : les différences----------------------------------------------------------------------------------------------------------------------------------

• Les piles sont restreintes aux opérations :Les piles sont restreintes aux opérations :– top , pop et push ( et la détection de la pile vide ),top , pop et push ( et la détection de la pile vide ),– celles-ci sont réalisées de façon efficace dans le celles-ci sont réalisées de façon efficace dans le

processeur,processeur,– par le biais d’un tableau !!!par le biais d’un tableau !!!



• Les piles sont restreintes aux opérations :Les piles sont restreintes aux opérations :– top , pop et push ( et la détection de la pile vide ),top , pop et push ( et la détection de la pile vide ),– celles-ci sont réalisées de façon efficace dans le processeur,celles-ci sont réalisées de façon efficace dans le processeur,– par le biais d’un tableau !!!par le biais d’un tableau !!!

• Les listes peuvent comporter entre autres :Les listes peuvent comporter entre autres :– en plus de ajout_liste , tete_liste et queue_liste (+ liste vide),en plus de ajout_liste , tete_liste et queue_liste (+ liste vide),– des fonctions comme inserer_liste , supprimer_liste, … ,des fonctions comme inserer_liste , supprimer_liste, … ,– être doublement chaînées ( cf. TD ) ou circulaires,être doublement chaînées ( cf. TD ) ou circulaires,– et ne sont plus des tableaux !et ne sont plus des tableaux !





22 66 44





22 66 44


Listes en langage CListes en langage C----------------------------------------------------------------------------------------------------------------------------------

#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <assert.h>

typedef int type_base;

typedef struct moi_meme {type_base valeur; struct moi_meme *suivant; }t_maillon, *ptr_liste;






Le nom du type de base.Le nom du type de base.







La structure elle-même.La structure elle-même.







La structure elle-même.La structure elle-même.

La structure s’appelle t_maillon.La structure s’appelle t_maillon.






Le nom du type de baseLe nom du type de base

La structure elle-mêmeLa structure elle-même

La structure s’appelle t_maillon.La structure s’appelle t_maillon.

Le type du pointeur sur une tellestructure s’appelle ptr_liste.



S o y o n s S o y o n s p l u sp l u s

c o n c r e t s !!!c o n c r e t s !!!



ptr_liste cree_vide (void)

{ return( (ptr_liste)NULL ); }

int est_vide (ptr_liste liste)

{ return( liste == (ptr_liste)NULL ); }

type_base tete_liste (ptr_liste liste)

{assert( liste != (ptr_liste)NULL );

return( liste->valeur ); }

ptr_liste queue_liste (ptr_liste liste)


return( liste->suivant ); }













Création de la liste vide.Création de la liste vide.














Le prédicat de listeLe prédicat de liste vide ou non.vide ou non.















Rendre la tête d’uneliste non vide.
















On s’assure que la liste n’estOn s’assure que la liste n’estpas la liste vide.pas la liste vide.

Préférable : Préférable :

( liste != cree_vide() ) ( liste != cree_vide() )
















Rendre la queueRendre la queued’une liste non vide.d’une liste non vide.



ptr_liste ajout_liste (type_base elt, ptr_liste liste)

{ptr_liste ptr_auxil;

ptr_auxil = (ptr_liste)malloc(sizeof(t_maillon));

ptr_auxil->valeur = elt;

ptr_auxil->suivant = liste;

return( ptr_auxil );}









ptr_liste ??? ???









ptr_liste elt ???









ptr_liste elt liste


Compilation séparéeCompilation séparée----------------------------------------------------------------------------------------------------------------------------------

C O M P I L A T I O N C O M P I L A T I O N

S E P A R E ES E P A R E E


Exporter les types --- fichier adt_liste.cExporter les types --- fichier adt_liste.c----------------------------------------------------------------------------------------------------------------------------------

...#include <assert.h>

typedef int type_base;typedef struct moi_meme {type_base valeur; struct moi_meme *suivant; } t_maillon, *ptr_liste;



...





ptr_liste cree_vide (void);int est_vide (ptr_liste liste);ptr_liste ajout_liste (type_base elt, ptr_liste liste);type_base tete_liste (ptr_liste liste);ptr_liste queue_liste (ptr_liste liste);



...

Nous inséronsNous inséronsles prototypes.les prototypes.








...

type_liste.h

#include ‘’type_liste.h ’’








...

type_liste.h

#include ‘’type_liste.h ’’

adt_liste.h

#include ‘’adt_liste.h’’




#include ‘’type_liste.h’’




...

Les définitions viennent ici !Les définitions viennent ici !

Le fichier adt_liste.cLe fichier adt_liste.c


prog.c qui utilise le type de données liste :prog.c qui utilise le type de données liste :----------------------------------------------------------------------------------------------------------------------------------




int main (void)...

L’utilisateur voit la structureL’utilisateur voit la structuredu type de liste.du type de liste.

L’utilisateur voit les signaturesL’utilisateur voit les signaturesdes fonctions sur les listes.des fonctions sur les listes.


prog.c qui utilise le type de données liste :prog.c qui utilise le type de données liste :----------------------------------------------------------------------------------------------------------------------------------




int main (void)...

L’utilisateur voit la structureL’utilisateur voit la structuredu type de liste.du type de liste.

L’utilisateur voit les signaturesL’utilisateur voit les signaturesdes fonctions sur les listes.des fonctions sur les listes.

L’utilisateur ne voit pas la réalisation desL’utilisateur ne voit pas la réalisation desfonctions, c’est-à-dire le contenu de adt_liste.c !fonctions, c’est-à-dire le contenu de adt_liste.c !

Souvent, c’est mieux fait dans d’autres langagesSouvent, c’est mieux fait dans d’autres langagescomme Ada , Modula , C++ et plein d’autres.comme Ada , Modula , C++ et plein d’autres.



• gcc –o executable prog.cgcc –o executable prog.c– On ne peut pas générer l’exécutable.On ne peut pas générer l’exécutable.– On connaît les signatures des fonctions sur les listes.On connaît les signatures des fonctions sur les listes.– Mais, on ne connaît pas leurs réalisations !Mais, on ne connaît pas leurs réalisations !




• gcc –o executable prog.c adt_liste.cgcc –o executable prog.c adt_liste.c– On peut compiler les deux fichiers en même temps.On peut compiler les deux fichiers en même temps.





• gcc gcc –c–c prog.c prog.c– Nous compilons prog.c pour générer « prog.o » .Nous compilons prog.c pour générer « prog.o » .– Nous n’avons pas besoin des définitions sur les listes, car Nous n’avons pas besoin des définitions sur les listes, car

nous ne créons pas encore l’exécutable.nous ne créons pas encore l’exécutable.– De même, gcc De même, gcc –c–c adt_liste.c crée « adt_liste.o ». adt_liste.c crée « adt_liste.o ».





• gcc gcc –c–c prog.c prog.c– Nous compilons prog.c pour générer « prog.o » .Nous compilons prog.c pour générer « prog.o » .– Nous n’avons pas besoin des définitions sur les listes, car Nous n’avons pas besoin des définitions sur les listes, car

nous ne créons pas encore l’exécutable.nous ne créons pas encore l’exécutable.– De même, gcc De même, gcc –c–c adt_liste.c crée « adt_liste.o ». adt_liste.c crée « adt_liste.o ».

• gcc –o executable prog.o adt_liste.ogcc –o executable prog.o adt_liste.o


Les fichiers .hLes fichiers .h----------------------------------------------------------------------------------------------------------------------------------

• Les fichiers « .h » donnent les « types » et/ou les Les fichiers « .h » donnent les « types » et/ou les « prototypes ».« prototypes ».




• #include <file.h>#include <file.h>– file.h est cherché dans les répertoires standard,file.h est cherché dans les répertoires standard,– mais aussi dans tout répertoire indiqué par -mais aussi dans tout répertoire indiqué par -IIrép.rép.– Exemple : gcc … -Exemple : gcc … -II. -. -II../local/include …../local/include …





• #include ‘’file.h’’#include ‘’file.h’’– file.h est cherché dans le répertoire courant.file.h est cherché dans le répertoire courant.





• #include ‘’file.h’’#include ‘’file.h’’– file.h est cherché dans le répertoire courant.file.h est cherché dans le répertoire courant.

• gcc -Wmissing-prototypes …gcc -Wmissing-prototypes …– L’absence de prototypes est signalée par un avertissement.L’absence de prototypes est signalée par un avertissement.


Créer et utiliser les librairiesCréer et utiliser les librairies----------------------------------------------------------------------------------------------------------------------------------

• Il existe des librairies statiques, dynamiques et archives.Il existe des librairies statiques, dynamiques et archives.– « ar r libadtl.a adt_liste.o » crée la librairie « libadtl.a » « ar r libadtl.a adt_liste.o » crée la librairie « libadtl.a »

à partir du contenu de « adt_liste.o »,à partir du contenu de « adt_liste.o »,– « ar t libadtl.a » affiche le contenu de la librairie.« ar t libadtl.a » affiche le contenu de la librairie.





• « gcc -o executable -L« gcc -o executable -L.. prog.c -l prog.c -ladtl adtl » compile prog.c» compile prog.c– Le répertoire Le répertoire .. est inspecté lors de la recherche des librairies, est inspecté lors de la recherche des librairies,– on recherche la librairie on recherche la librairie libadtl.alibadtl.a





• « gcc -o executable -L« gcc -o executable -L.. prog.c -l prog.c -ladtl adtl » compile prog.c» compile prog.c– Le répertoire Le répertoire .. est inspecté lors de la recherche des librairies, est inspecté lors de la recherche des librairies,– on recherche la librairie on recherche la librairie libadtl.alibadtl.a

• L’ordre des arguments importe :L’ordre des arguments importe :– OK : gcc prog-math.c -lmOK : gcc prog-math.c -lm– KO : gcc -lm prog-math.cKO : gcc -lm prog-math.c


L E S L E S

F I L E SF I L E S

Les filesLes files----------------------------------------------------------------------------------------------------------------------------------



• LIFO : listes et piles.LIFO : listes et piles.– Les accès en « ajout », « lecture » et « suppression » Les accès en « ajout », « lecture » et « suppression »

se font en tête de liste :se font en tête de liste :

InsertionInsertion

LectureLecture

SuppressionSuppression

…



• LIFO : listes et piles.LIFO : listes et piles.– Les accès en « ajout », « lecture » et « suppression » Les accès en « ajout », « lecture » et « suppression »

se font en tête de liste :se font en tête de liste :

InsertionInsertion

LectureLecture


• FIFO : files.FIFO : files.– First In – First Out, c’est plus équitable !First In – First Out, c’est plus équitable !– L’insertion se fait à la fin et c’est la seule L’insertion se fait à la fin et c’est la seule

différence.différence.

LectureLecture


InsertionInsertion

…

…


Les files en langage CLes files en langage C----------------------------------------------------------------------------------------------------------------------------------

ptr_liste ajout_file (type_base elt, ptr_file file)

{ptr_file ptr_auxil;

ptr_auxil = (ptr_file)malloc(sizeof(t_maillon));


ptr_auxil->suivant = (ptr_file)NULL;

if ( file == (ptr_file)NULL )

return( ptr_auxil );

else

{ptr_file ptr_local = file;

while ( ptr_local->suivant != (ptr_file)NULL )

ptr_local = ptr_local->suivant;

ptr_local->suivant = ptr_auxil;

return( file ); }}










else





return( file ); }}

Création du nouveauCréation du nouveaumaillon qui sera le dernier.maillon qui sera le dernier.










else





return( file ); }}

Il est peut-être le seul !Il est peut-être le seul !










else





return( file ); }}

Nous avançons jusqu’auNous avançons jusqu’audernier maillon,dernier maillon,










else





return( file ); }}

Nous chaînons etNous chaînons etrendons le résultat !rendons le résultat !



• Souvent, on maintient deux pointeurs :Souvent, on maintient deux pointeurs :

têtetête

queuequeue

…



• Souvent, on maintient deux pointeurs :Souvent, on maintient deux pointeurs :

têtetête

queuequeue

• C’est plus pratique d’avoir une structure de synthèse :C’est plus pratique d’avoir une structure de synthèse :

filefile

…

…


Les arbresLes arbres----------------------------------------------------------------------------------------------------------------------------------

E TE TP O U RP O U R

T E R M I N E R ,T E R M I N E R ,L E SL E S

A R B R E S !A R B R E S !


Les arbres enracinésLes arbres enracinés----------------------------------------------------------------------------------------------------------------------------------

racineracine



racineracine

Il y a un nœud qui est la « racine ».Il y a un nœud qui est la « racine ».

Il y a une orientation de laIl y a une orientation de laracine vers les autres.racine vers les autres.



autre racineautre racine


Les arbres NON enracinésLes arbres NON enracinés----------------------------------------------------------------------------------------------------------------------------------

Les liens sont bi-directionnels.Les liens sont bi-directionnels.

Il n’y a pas de racine.Il n’y a pas de racine.


Les arbres NON enracinésLes arbres NON enracinés----------------------------------------------------------------------------------------------------------------------------------

Pourquoi d’ailleurs faire laPourquoi d’ailleurs faire ladistinction entre feuillesdistinction entre feuilles

et nœuds ?et nœuds ?

C’est ainsi que nousC’est ainsi que nousverrons un arbreverrons un arbre

en théorie desen théorie desgraphes.graphes.



racineracine

Les feuilles sont les extrémités de Les feuilles sont les extrémités de l’arbre.l’arbre.

Du point de vue de l’arbre, ellesDu point de vue de l’arbre, ellessont atomiques (sanssont atomiques (sans

successeur).successeur).

Concernant l’application,Concernant l’application,elles comportentelles comportent

souvent dessouvent desvaleurs.valeurs.

5 13



racineracine

Il y a des nœuds (internes)Il y a des nœuds (internes)qui ont des « fils » enqui ont des « fils » en

nombre variable.nombre variable.

Chaque fils est à sonChaque fils est à sontour un arbre.tour un arbre.

ConcernantConcernantl’application,l’application,

les nœudsles nœudspeuventpeuvent

comportercomporterdes valeurs,des valeurs,

que l’on appelleque l’on appelleaussi des étiquettes.aussi des étiquettes.

x

+



racineracine

Sous-arbres !



• Un arbre estUn arbre est– soit, simplement une feuille :soit, simplement une feuille :

racineracine



• Un arbre estUn arbre est– soit, simplement une feuille :soit, simplement une feuille :

racineracine

– soit, un nœud (racine) avec un ou plusieurs fils qui soit, un nœud (racine) avec un ou plusieurs fils qui sont des arbres (enracinés) à leur tour :sont des arbres (enracinés) à leur tour :

racineracine

arbre arbre arbrearbre arbre arbre


Les arbres enracinés (binaires) comme ADTLes arbres enracinés (binaires) comme ADT----------------------------------------------------------------------------------------------------------------------------------

• Création d’une feuille :Création d’une feuille :

– cree_feuille : void -> cree_feuille : void -> AA

– cree_feuille : int -> cree_feuille : int -> AApour créer une feuille qui comporte une valeur entière, pour créer une feuille qui comporte une valeur entière,

avec :avec :

valeur_feuille : valeur_feuille : AA -> int -> int



• Création d’une feuille :Création d’une feuille :

– cree_feuille : void -> cree_feuille : void -> AA

– cree_feuille : int -> cree_feuille : int -> AApour créer une feuille qui comporte une valeur entière, avec pour créer une feuille qui comporte une valeur entière, avec

::

valeur_feuille : valeur_feuille : AA -> int -> int

• Création d’un nœud binaire :Création d’un nœud binaire :

– cree_arbre : cree_arbre : A A x x AA -> -> AA

– cree_arbre : cree_arbre : A A x int x x int x AA -> -> AApour créer un nœud qui comporte une étiquette entière, pour créer un nœud qui comporte une étiquette entière,

avec : avec :

etiquette_arbre : etiquette_arbre : AA -> int -> int



• Distinction entre feuilles et noeuds :Distinction entre feuilles et noeuds :

– est_feuille : est_feuille : AA -> BOOL -> BOOL

est_feuille( cree_feuille() ) = Vraiest_feuille( cree_feuille() ) = Vrai

est_feuille( cree_noeud( x , y ) ) = Fauxest_feuille( cree_noeud( x , y ) ) = Faux



• Distinction entre feuilles et noeuds :Distinction entre feuilles et noeuds :

– est_feuille : est_feuille : AA -> BOOL -> BOOL

est_feuille( cree_feuille() ) = Vraiest_feuille( cree_feuille() ) = Vrai

est_feuille( cree_noeud( x , y ) ) = Fauxest_feuille( cree_noeud( x , y ) ) = Faux

• Décomposition d’un nœud binaire :Décomposition d’un nœud binaire :

– fils_gauche : fils_gauche : AA -> -> AA– fils_droit : fils_droit : AA -> -> AA

fils_gauche ( cree_arbre ( g , d ) ) = gfils_gauche ( cree_arbre ( g , d ) ) = g

fils_droit ( cree_arbre ( g , d ) ) = dfils_droit ( cree_arbre ( g , d ) ) = d



arbre_un = cree_arbre ( cree_feuille(5) , cree_feuille(7) );

arbre_deux = cree_arbre ( cree_feuille(2) ,

cree_arbre ( arbre_un ,

cree_feuille(1) ) );

arbre_trois = cree_arbre ( cree_feuille(3) , cree_feuille(7) );

arbre = cree_arbre ( arbre_deux , arbre_trois );









5 7









5 7

1

2









5 7

1

2 3 7









5 7

1

2 3 7


Les arbres en langage CLes arbres en langage C----------------------------------------------------------------------------------------------------------------------------------

• Un pointeur sur un arbre est :Un pointeur sur un arbre est :– soit, un pointeur sur une feuille,soit, un pointeur sur une feuille,– soit, un pointeur sur un nœud.soit, un pointeur sur un nœud.




• Il faut donc une structure capable de contenir les deux :Il faut donc une structure capable de contenir les deux :– les champs d’une feuille,les champs d’une feuille,– les champs d’un nœud,les champs d’un nœud,– un indicateur booléen qui distingue les deux cas de figure.un indicateur booléen qui distingue les deux cas de figure.




• Il faut donc une structure capable de contenir les deux :Il faut donc une structure capable de contenir les deux :– les champs d’une feuille,les champs d’une feuille,– les champs d’un nœud,les champs d’un nœud,– un indicateur booléen qui distingue les deux cas de figure.un indicateur booléen qui distingue les deux cas de figure.

• Exemple, (expressions arithmétiques) :Exemple, (expressions arithmétiques) :– toute feuille est un entier,toute feuille est un entier,– chaque nœud comporte :chaque nœud comporte :

• un opérateur parmi « + », « * » et « - »,un opérateur parmi « + », « * » et « - »,

• deux fils qui sont des sous-expressions.deux fils qui sont des sous-expressions.



typedef struct moi_memetypedef struct moi_meme

{int est_feuille;{int est_feuille;

int valeur;int valeur;

char etiq;char etiq;

struct moi_meme *fg;struct moi_meme *fg;

struct moi_meme *fd;struct moi_meme *fd;

}}

t_arbre, *ptr_arbre;t_arbre, *ptr_arbre;




{{int est_feuille; vaudra VRAIint est_feuille; vaudra VRAI

int valeur; aura une int valeur; aura une valeurvaleur




}}


Si c’est une feuille …Si c’est une feuille …




{{int est_feuille; vaudra VRAIint est_feuille; vaudra VRAI

int valeur; aura une int valeur; aura une valeurvaleur




}}


Si c’est une feuille …Si c’est une feuille …

Ces champs n’ont simplementCes champs n’ont simplementaucun sens dans ce contexte !aucun sens dans ce contexte !




{{int est_feuille; vaudra FAUXint est_feuille; vaudra FAUX


char etiq; aura une valeurchar etiq; aura une valeur

struct moi_meme *fg; aura une valeurstruct moi_meme *fg; aura une valeur

struct moi_meme *fd; aura une valeurstruct moi_meme *fd; aura une valeur

}}


Si c’est un noeud …Si c’est un noeud …









}}



Le champ « valeur » n’a simplementLe champ « valeur » n’a simplementaucun sens dans ce contexte !aucun sens dans ce contexte !









}}



Le champ « valeur » n’a simplementLe champ « valeur » n’a simplementaucun sens dans ce contexte !aucun sens dans ce contexte !

En Pascal, ADA et d’autres, il existe des structures variables !En Pascal, ADA et d’autres, il existe des structures variables !



int est_feuille (ptr_arbre arbre)int est_feuille (ptr_arbre arbre)

{return(arbre->est_feuille);{return(arbre->est_feuille);

}}

ptr_arbre cree_feuille (int val)ptr_arbre cree_feuille (int val)

{ptr_arbre arbre;{ptr_arbre arbre;

arbre = (ptr_arbre)malloc(sizeof(t_arbre));arbre = (ptr_arbre)malloc(sizeof(t_arbre));

arbre->est_feuille = 1;arbre->est_feuille = 1;

arbre->valeur = val;arbre->valeur = val;

return(arbre);return(arbre);

}}





}}







}}

C’est précisément un champ quiC’est précisément un champ qui mémorise si c’est une feuille.mémorise si c’est une feuille.





}}







}}

L’allocation de la mémoire.L’allocation de la mémoire.

Définition des champs concernés.Définition des champs concernés.



ptr_arbre cree_noeud (ptr_arbre fg, ptr_arbre fd, char ptr_arbre cree_noeud (ptr_arbre fg, ptr_arbre fd, char symbole)symbole)




arbre->etiq = symbole;arbre->etiq = symbole;

arbre->fg = fg;arbre->fg = fg;

arbre->fd = fd;arbre->fd = fd;


}}



ptr_arbre cree_noeud (ptr_arbre fg, ptr_arbre fd, char ptr_arbre cree_noeud (ptr_arbre fg, ptr_arbre fd, char symbole)symbole)




arbre->etiq = symbole;arbre->etiq = symbole;

arbre->fg = fg;arbre->fg = fg;

arbre->fd = fd;arbre->fd = fd;


}}

L’allocation de la mémoire.L’allocation de la mémoire.

Définition des champs concernés.Définition des champs concernés.



ptr_arbre fils_gauche (ptr_arbre arbre)ptr_arbre fils_gauche (ptr_arbre arbre)

{assert( !est_feuille(arbre) );{assert( !est_feuille(arbre) );

return(arbre->fg);return(arbre->fg);

}}

ptr_arbre fils_droit (ptr_arbre arbre)ptr_arbre fils_droit (ptr_arbre arbre)

{assert( !est_feuille(arbre) );{assert( !est_feuille(arbre) );

return(arbre->fd);return(arbre->fd);

}}



ptr_arbre fils_gauche (ptr_arbre arbre)ptr_arbre fils_gauche (ptr_arbre arbre)

{{assert( !est_feuille(arbre) );assert( !est_feuille(arbre) );

return(arbre->fg);return(arbre->fg);

}}

ptr_arbre fils_droit (ptr_arbre arbre)ptr_arbre fils_droit (ptr_arbre arbre)

{{assert( !est_feuille(arbre) );assert( !est_feuille(arbre) );

return(arbre->fd);return(arbre->fd);

}}

Vérification que l’arbre estVérification que l’arbre estbien un nœud interne.bien un nœud interne.

Retour du résultat demandé.Retour du résultat demandé.


Listes, arbres et le pointeur NULLListes, arbres et le pointeur NULL----------------------------------------------------------------------------------------------------------------------------------

• Une liste peut être vide !Une liste peut être vide !

• Elle sera représentée par le pointeur NULL !Elle sera représentée par le pointeur NULL !

• La raison profonde est le fait que l’opération de base est :La raison profonde est le fait que l’opération de base est :– la concaténation,la concaténation,– qui est associativequi est associative– et possède la liste vide comme élément neutre !et possède la liste vide comme élément neutre !



• Une liste peut être vide !Une liste peut être vide !

• Elle sera représentée par le pointeur NULL !Elle sera représentée par le pointeur NULL !

• La raison profonde est le fait que l’opération de base est :La raison profonde est le fait que l’opération de base est :– la concaténation,la concaténation,– qui est associativequi est associative– et possède la liste vide comme élément neutre !et possède la liste vide comme élément neutre !

• Nous avons les fonctions suivantes :Nous avons les fonctions suivantes :

– cree_videcree_vide– ajout_listeajout_liste– est_videest_vide– tete_listetete_liste– queue_listequeue_liste



• Un arbre n’est jamais NULL !Un arbre n’est jamais NULL !

• C’est juste le programmeur qui l’est ! ! !C’est juste le programmeur qui l’est ! ! !

• La raison profonde est le fait que l’opération de base est :La raison profonde est le fait que l’opération de base est :– la construction d’arbre,la construction d’arbre,– qui n’est pas associativequi n’est pas associative– et la question de l’élément neutre ne se pose même pas !et la question de l’élément neutre ne se pose même pas !






Arbre ( A , Arbre ( B , C ) ) Arbre ( A , Arbre ( B , C ) ) == Arbre ( Arbre ( A , B ) , C )Arbre ( Arbre ( A , B ) , C )//

AA

BB CC

CC

AA BB







– cree_feuillecree_feuille– cree_noeudcree_noeud– est_feuilleest_feuille– fils_gauchefils_gauche– fils_droitfils_droit







– cree_feuillecree_feuille– cree_noeudcree_noeud– est_feuilleest_feuille– fils_gauchefils_gauche– fils_droitfils_droit



• Je peux éventuellement écrire ceci :Je peux éventuellement écrire ceci :


{ struct moi_meme fg , fd ; } . . .{ struct moi_meme fg , fd ; } . . .

ptr_arbre cree_feuille (int valeur)ptr_arbre cree_feuille (int valeur)

{{ptr_arbre arbre;ptr_arbre arbre;


arbre->fg = NULL ;arbre->fg = NULL ;

arbre->fd = (int *) valeur ;arbre->fd = (int *) valeur ;

return ( arbre ) ;return ( arbre ) ;

}}












}}

Nous utilisons le champ fgNous utilisons le champ fgpour indiquer que l’arbrepour indiquer que l’arbre

est une feuille,est une feuille,. . . et le fils droit pour. . . et le fils droit pourmémoriser sa valeur !mémoriser sa valeur !












}}

Nous utilisons le champ fgNous utilisons le champ fgpour indiquer que l’arbrepour indiquer que l’arbre

est une feuille,est une feuille,. . . et le fils droit pour. . . et le fils droit pourmémoriser sa valeur !mémoriser sa valeur !


SynthèseSynthèse----------------------------------------------------------------------------------------------------------------------------------

• Listes.Listes.

• Piles.Piles.

• Files.Files.

• Arbres.Arbres.

• Types de données abstraits.Types de données abstraits.


m E r C i e Tm E r C i e Tb O n N e J o U r N é b O n N e J o U r N é

E ! ! !E ! ! !

n ‘ O u B l I e Z p A s D en ‘ O u B l I e Z p A s D ep R é P a R e R v O sp R é P a R e R v O s

T D ! ! !T D ! ! !

Documents

Cours d'algorithmique 2 - Intranet 1 8 novembre 2006 Cours dAlgorithmique Listes, piles et files. Arbres. Types de données abstraits. Implantations