Algorithmique et structures de données en C-07122010

8/7/2019 Algorithmique et structures de donnes en C-07122010

1/85

07/12/2010

1

Algorithmique et structuresAlgorithmique et structuresde donnesde donnes

Par Ghislain Akinocho

Ingnieur Services et Solutions

AgendaAgenda

Objectif Programme

Les composants lmentaires des algorithmes Rappel Langage C

Les listes linaires chanes Structures linaires particulires Les piles Les files

La rcursivit Les Arbres binaires Les fichiers squentiels Algorithmes de Tri

Applications : TP Langage C

mardi 7 dcembre 2010 2


2/85

07/12/2010

2

ObjectifObjectif Bonne base algorithme

Matrise des diffrentes structures dedonnes manipules et utiles enprogrammation


Les composants lmentairesLes composants lmentaires

des algorithmesdes algorithmes


3/85

07/12/2010

3

IntroductionIntroduction Dfinition

Lalgorithme est un ensemble de rgles ouune suite dinstructions qui doivent treexcutes dans un ordre bien dfini en vue dersoudre un problme donn.

Lalgorithme doit contenir des instructionscomprhensibles par le dveloppeur qui doit

crire le programme.


IntroductionIntroduction

Pr-requis

Pour crire un bon algorithme, il faut :

Avoir une matrise des rgles de basedcriture dun algorithme.

Etre mthodique et rigoureux et

Avoir une bonne intuition



4/85

07/12/2010

4

IntroductionIntroduction En algorithme on distingue 4 grandes

familles dinstructions

Laffectation des variables

La lecture et lcriture

Les tests de contrle

Les boucles


Lalgorithme et le programmeLalgorithme et le programme

Lalgorithme et le programmeinformatique sont diffrents sur deuxprincipaux points :

1er point :

Un algorithme est indpendant de toutlangage de programmation. Il peut seprsenter sous plusieurs formes :

Diagrammes

Textes



5/85

07/12/2010

5

Lalgorithme et le programmeLalgorithme et le programme Un programme informatique lui dpend

du langage dans lequel il doit tre crit. Ilcorrespond donc une interprtation/traduction de lalgorithme en un langagedonn.

Pascal

Cobol

Php Java

C,


Lalgorithme et le programmeLalgorithme et le programme

2nd point :

Un algorithme ne peut tre excutdirectement sur une machine tandis que

le programme peut tre excut sur unemachine donne. Pour cela il suffit dedisposer de logiciels ncessaires lexcution du programme.



6/85

07/12/2010

6

Notions de baseNotions de base Les variables : Gnralits

En programmation tout comme enalgorithmique une variable est un conteneurdinformations qui peut tre rfrenc par lenom quil porte.

En informatique, ce conteneur est une zone

mmoire alloue au niveau de la mmoire vive du systme lors du lancement duprogramme pour stocker des informations

bien dfinies et manipules par lapplication.


Notions de baseNotions de base

Les variables : Gnralits Pour accder ces informations, on utilise le

nom de la variable qui permet de connaitre

ladresse correspondant lespace alloue lavariable.

Avant dutiliser une variable il faut aupralable la dclarer.



7/85

07/12/2010

7

Notions de baseNotions de base Les variables : Dclaration

La dclaration dune variable seffectuetoujours au dbut de lalgorithme et permet desavoir le type dinformations quelle doitcontenir tout le long du programme.

Il existe plusieurs types de variables prdfinis

qui se divisent en deux grands groupes : Les types numriques

Les types alphanumriques



Les variables : Les types numriques En algorithme, les types numriques que lon

distingue sont :

Les bytes (valeurs entre 0 et 255) Les entiers simples

Les entiers longs

Les rels simples



8/85

07/12/2010

8

Notions de baseNotions de base Les variables : Les types alphanumriques

Les types alphanumriques correspondent auxchanes de caractres et aux caractres eux-mmes.



Les variables : Formalisme de la dclaration

variable nom_variable : type

Le nom dune variable doit toujours commencer

par un caractre alphanumrique

Exemple :

variable age :byte



9/85

07/12/2010

9

Notions de baseNotions de base Les variables :Affectation dune variable

Affecter une valeur une variable cest crire dans lazone mmoire rfrence par le nom de la variable.

On ne doit affecter une variable quune valeurcorrespondant au type dfini pour la variable lors de sadclaration.



Les variables : Formalisme de laffectationnom_variable valeur

Le nom de la variable est suivi dune flche dirige vers la

variable elle-mme suivie de la valeur affecter lavariable.

Exemple :

age 27



10/85

07/12/2010

10

Notions de baseNotions de base Les oprateurs : oprateurs arithmtiques

Laffectation dune valeur une variable peut se fairegalement par le biais dune opration arithmtique.

Il sagira dans ce cas daffecter le rsultat de lopration la variable.

Les diffrents oprateurs arithmtiques existant enalgorithmique sont :

+ : laddition

- :la soustraction

/ : la division

% ou mod: le modulo



Les oprateurs : oprateurs arithmtiques Exemple :

a 15

b 10c a + b



11/85

07/12/2010

11

Notions de baseNotions de base Les fonctions dentre / sortie

En algorithme, pour effectuer certaines tches on abesoin dinformations qui doivent tre fournies parlutilisateur.

Pour rcuprer ces donnes on dispose de fonctionsparticulires et prdfinies dites dentres/sorties quipermettent au systme de lire ces valeurs externes.

La fonction lire permet de lire les informations

venant de lextrieur et de les stocker dans une variable

passe en paramtre.

Exemple :

lire (age)



Les fonctions dentre / sortie De mme il existe des fonctions dentres/sorties

permettant de restituer un rsultat lcran oudafficher une simple information.

La fonction afficher permet dafficher aussi bien le

contenu dune variable quune simple information ou lesdeux la fois.

Exemple :

afficher (age)

afficher(" Salut la compagnie ")

afficher ("Votre age : ", age)



12/85

07/12/2010

12

Notions de baseNotions de base Exemple dalgorithme :

Problme :

Un commerant de la place dsire mettre en place unalgorithme permettant de calculer le prix dachat dunproduit x en connaissant le nombre darticles et le prixunitaire.


Notions de baseNotions de base Exemple dalgorithme :

Rsolution :

Algorithme prix_d_achat

{Cet algorithme permet de calculer le prix

dachat dun produit}

variables pUnit : rel

Qte : entier

Debut

afficher("Donner le nombre darticles : ")

lire(Qte)

afficher("Donner le prix unitaire : ")

lire(pUnit)

afficher("Le prix dachat est : ", pUnit*Qte)

Fin



13/85

07/12/2010

13

Notions de baseNotions de base Les structures conditionnelles

Les structures conditionnelles permettent, danslalgorithme de poser des conditions sur lexcution decertaines instructions.

On distingue :

Les structures conditionnelles simples

Les structures conditionnelles en boucle


Les structures conditionnelles simples Lexcution des instructions conditionnelles ne se

droule quune seule fois lorsque la condition estremplie.

La structure utilise pour cela est :

SI ALORS SINON




14/85

07/12/2010

14


SI ALORS SINON

Formalisme :

SI (condition)

ALORS {la condition est vraie}

SINON {la condition est fausse}

FINSI



Les structures conditionnellesRappel sur les oprateurs logiques:

>: suprieur

=: suprieur ou gal


15/85

07/12/2010

15


Exemple :Variables x, y, max : rels

lire(x)

Lire(y)

SI (x>y)

ALORS

max x

SINON

max y

FINSI



Exercices dapplication Ecrire un algorithme permettant de rsoudre lquation

suivante : aX + b = 0, a != 0 et b != 0.

Ecrire un algorithme qui demande deux nombresentiers un utilisateur et linforme ensuite si leurproduit est ngatif ou positif sans effectuer de calculpralable (le cas nul sera ignor).

Un magasin de reprographie facture 25Fcfa les 10premires photocopies, 20Fcfa les vingt suivantes et15Fcfa au-del. Ecrire un algorithme qui demande lutilisateur le nombre de photocopies effectues et quiaffiche la facture correspondante.



16/85

07/12/2010

16

Les structures conditionnelles en boucle Dans le cas des structures conditionnelles en boucle,

lorsque la condition est vrifie, les instructionsconcernes par cette condition seront excutesautant de fois que la condition restera vraie.

Les structures en boucle utilises sont :

tant que faire

faire tant que

pour



tant que faire

Syntaxe :

tant que () faire

fintq

Le bloc dinstructions seraexcut tant que la condition sera

vraie.




17/85

07/12/2010

17

tant que faire

Exemple :

i 0

tant que (i


18/85

07/12/2010

18

faire tant que

Exemple :

i 0

faire

i i + 1

tant que (i


19/85

07/12/2010

19

pour

Exemple :

pour i 0 jusqu 9 faire

n n + 1

afficher ("Bonjour ", i, "fois")

finpour



Quand utiliser la structure :

- tant que faire ou faire tant que

- Lorsque le nombre de fois quon veut excuter lebloc dinstructions nest pas connu.

NB :

- En ce qui concerne la structure tant que faire, lebloc dinstructions peut ne jamais tre excut car letest se fait avant lentre dans la boucle.

- En ce qui concerne la structure faire tant que, lebloc dinstructions sera toujours excut (au moinsune fois) car le test se fait aprs la premireexcution du bloc.




20/85

07/12/2010

20

Quand utiliser la structure :

- pour

- Lorsque le nombre de fois quon veut excuter lebloc dinstructions est bien connu.




Exercices dapplication Ecrire un algorithme qui demande lutilisateur un

nombre compris entre 1 et 3(inclus) tant que larponse est incorrecte.

Ecrire un algorithme qui demande lutilisateur unnombre de dpart et qui ensuite affiche les dix nombressuivants. Par exemple, si lutilisateur entre le nombre12, le programme affichera les nombres de 13 22(inclus).

Ecrire un algorithme permettant de calculer le factorieldun nombre

Ecrire un algorithme qui permet de rsoudre unequation du second degr :

Rappel : a X + b X + c = 0.



21/85

07/12/2010

21

Notions de baseNotions de base Exercices dapplication

Ecrire un algorithme qui demande un nombre comprisentre 10 et 20 tant que la rponse est incorrecte. En casde rponse suprieure 20, on fera apparatre unmessage Plus petit ! et inversement, Plus grand ! si le nombre est infrieur 10.

Ecrire un algorithme qui demande un nombre dedpart et qui ensuite affiche la table de multiplicationde ce nombre.

Exemple : cas o lutilisateur saisit 7 Table de 7 :

7 x 1 = 7

7 x 2 = 14

7 x 10 = 70


Les Tableaux et Pointeurs

Les tableaux

Une variable de type tableau est une variable pouvant contenirplusieurs donnes de mme type un instant t donn.

On en distingue deux types :

Les tableaux 1 dimension

Les tableaux plusieurs dimensions




22/85

07/12/2010

22

Les Tableaux 1 dimension

Ces tableaux disposent dune seule ligne et deplusieurs colonnes.

Les tableaux une dimension sont encore appelsdesvecteurs.

Dclaration dun tableau 1D:

Variable nom_variable [taille] : type

Exemple :

variable tab[8] : entier



1 2 3 4 5 6 7 8

Les Tableaux 1 dimension

Affectation dans un tableau 1D:

nom_variable [indice] valeur

Exemple :

tab[5] 19



19

1 2 3 4 5 6 7 8


23/85

07/12/2010

23

Les Tableaux plusieurs dimensions

Ces tableaux disposent de plusieurs lignes et deplusieurs colonnes.

Les tableaux 2 dimensions sont encore appels desmatrices.


Variable nom_variable [nbLignes] [nbColonnes] : type

Exemple :

variable tab[3][4] : entier





Variable nom_variable [nbLignes] [nbColonnes] : type

Exemple :

variable tab[3][4] : entier



1 2 3 4

1

2

3


24/85

07/12/2010

24


Affectation dans un tableau 2D:

nom_variable [numLign] [numCol]valeur

Exemple :

tab[2][3] 5



1 2 3 4

1

2 53


Exercices dapplication Ecrire un algorithme qui initialise les lments dun

tableau 1D et dun tableau 2D dentiers par des 1 .

Ecrire un algorithme qui demande lutilisateur une

srie de 20 valeurs et affiche : La somme des lments

La moyenne des lments

Le maximum

Le minimum

Et le produit

Ecrire un algorithme qui inverse les lments duntableau 1D.

Ecrire un algorithme qui permet de dterminer lemaximum et le minimum dans un tableau 2D dentiers



25/85

07/12/2010

25

EXERCICESEXERCICES Matrice

Ecrire un algorithme qui calcule le produit et la somme de matrices.

Enchainement de lexcution :

1- On demandera lutilisateur les dimensions respectives desmatrices A[n, m] et B[o,p].

2- On demandera ensuite lopration effectuer

3- On vrifiera suivant les valeurs de n, m, o et p que lopration est

possible.

4-Si oui on fait le calcul et affiche le rsultat sinon on affiche unmessage expliquant limpossibilit deffectuer lopration.


Les pointeursLes pointeurs

Un pointeur est une variable spciale qui peut contenirladresse dune autre variable.

Il faut noter que le pointeur ne contient que ladressedune variable dont le type correspond au type spcifilors de sa dclaration.

Remarque Les pointeurs et les noms de variables ont le mme rle : Ils donnent

laccs un emplacement mmoire interne de lordinateur. Parailleurs il faut bien faire la diffrence :

Un pointeur est une variable qui peut 'pointer' sur diffrentesadresses.

Le nom dune variable reste toujours li la mme adresse.



26/85

07/12/2010

26

Les pointeursLes pointeurs Il existe deux modes dadressage principaux

Ladressage direct

Ladressage indirect

Ladressage direct Dans la programmation les variables sont utilises pour

stocker des informations. La valeur dune variable se trouve un endroit spcifique dans la mmoire de lordinateur.

Le nom de la variable nous permet daccder directementcette valeur.



Ladressage indirect Si nous ne voulons ou ne pouvons pas utiliser le nom dune

variable A, nous pouvons copier ladresse de cette variabledans une variable spciale P appele pointeur.

Ensuite, nous pouvons retrouver linformation de la variableen passant par le pointeur P.

Exemple :

Soit A une variable contenant la valeur 19 et P un pointeur quicontient ladresse de A. En mmoire, A et P peuvent seprsenter comme suit :



27/85

07/12/2010

27

Les pointeursLes pointeurs Formalisme de dclaration dun pointeur

variable * :

Exemple : variable *ptr : entier Dclaration dune variable de type pointeur sur un entier.

La variable ptr (de type pointeur) contiendra ladresse dune variablede type entier.

Exemple :Algorithme pointeur

variable *ptr : entier

variable n : entierDEBUT

n 10

ptr&n {On dit que ptr pointe sur n / n est point par ptr}

afficher(*ptr) { 10 sera affich }

FIN



Vocabulaire

Soit la dclaration suivante :

variable *ptr, n : entier

Dans lalgorithme :-> *ptr dsignera le contenu de la variable pointe par

ptr

-> &n dsignera ladresse de n

-> ptr dsignera la variable contenant ladresse duneautre variable de type entier



28/85

07/12/2010

28

Les pointeursLes pointeurs Oprations lmentaires sur les pointeurs

Priorits de * et &Les oprateurs * et & ont la mme priorit que les autres oprateurs unaires(!, ++,--).

Dans une mme expression ces oprateurs sont valus de droite gauche.

Si un pointeur P pointe sur une variable X, alors *P peut tre utilis partouto on peut crire X.

Exemple :

Aprs linstruction P=&X;

les expressions suivantes sont quivalentes :

Y *P+1YX+1

*P *P+10XX+10*P +=2X +=2

++*P ++X

(*P)++X++


ExercicesExercicesExercice :

A 1

B2

C3

variable *P1, *P2 : entiers

P1&A

P2&C

P1 P2

P2&B

*P1 -= *P2

A++*P2**P1

P1&A

*P2*P1/=*P2

Rsumez dans un tableau le rsultat de chaque instruction duprogramme ci-dessus



29/85

07/12/2010

29

ExercicesExercicesExercice :

Soit P un pointeur qui 'pointe' sur un tableau A dentiers contenantles valeurs suivantes : {12, 23, 34, 45, 56, 67, 78, 89, 90};

variable *P : entier

P = A;

Quelles valeurs ou adresses fournissent ces expressions:

a) *P+2

b) *(P+2)

c) &P+1

d) &A[4]-3

e) A+3

f) &A[7]-P

g) P+(*P-10)

h) *(P+*(P+8)-A[7])


Les fonctions et les procduresLes fonctions et les procdures

Gnralits

Les fonctions et les procdures sont des sous-algorithmespermettant de simplifier llaboration de lalgorithme

principal et de mieux le structurer.

Un sous-algorithme contient le code permettantdexcuter un traitement particulier qui pourraitapparatre plusieurs fois dans lalgorithme principal.



30/85

07/12/2010

30

Les fonctions et les procduresLes fonctions et les procdures Gnralits

La plupart des langages de programmation nouspermettent de subdiviser nos programmes en sous-programmes, fonctions ou procdures plus simples et pluscompacts.

A l'aide de ces structures nous pouvonsmodulariser nos programmes pour obtenir des

solutions plus lgantes et plus efficientes.



Gnralits

Modules (en C : les fonctions) Dans ce contexte, un module dsigne une entit de donnes et

d'instructions qui fournissent une solution une (petite) partie biendfinie d'un problme plus complexe.

Un module peut faire appel d'autres modules, leur transmettredes donnes et recevoir des donnes en retour. L'ensemble desmodules ainsi relis doit alors tre capable de rsoudre le problmeglobal.



31/85

07/12/2010

31

Les fonctions et les procduresLes fonctions et les procdures Avantages

Voici quelques avantages d'un programmemodulaire:

Meilleure lisibilit

Diminution du risque d'erreurs

Dissimulation des mthodesLors de l'utilisation d'un module il faut seulement connatre soneffet, sans devoir s'occuper des dtails de sa ralisation.

Rutilisation de modules dj existantsIl est facile d'utiliser des modules qu'on a crits soi-mme ou quiont t dvelopps par d'autres personnes.



Avantages

Voici quelques avantages d'un programmemodulaire:

Simplicit de l'entretien Un module peut tre chang ou remplac sans devoir toucher aux

autres modules du programme.

Favorisation du travail en quipeUn programme peut tre dvelopp en quipe par dlgation de laprogrammation des modules diffrentes personnes ou groupes depersonnes. Une fois dvelopps, les modules peuvent constituer une

base de travail commune.



32/85

07/12/2010

32

Les fonctions et les procduresLes fonctions et les procduresContrairement aux procdures, les fonctions retournenttoujours une valeur lissue de leur excution.

Syntaxe de dclaration dune fonction: fonction ( param_i,)

{Zone de dclaration des variables}

DEBUT

{Contenu du sous-algorithme}

retourner valeur_de_retour {obligatoire}

FIN



Syntaxe de dclaration dune procdure :procdure ( param_i, )

{Zone de dclaration des variables}

DEBUT


FIN



33/85

07/12/2010

33

Les fonctions et les procduresLes fonctions et les procduresSyntaxe d un algorithme principal contenant des sous-algorithmes

Algorithme exemple

procdure ( param_i, )

{Zone de dclaration des variables de la

procdure}

DEBUT


FIN

() {Mettre les autres sous algorithmes ici}

{Zone de dclaration des variables de lalgorithme

principal}

DEBUT

{Contenu de lalgorithme principal}

FIN


EXERCICESEXERCICES La pendule 1

Ecrivez un algorithme qui demande un nombre de secondes et affichelheure correspondante sous la forme suivante -> Hh:Mmn:Ss

Exemple : 78 -> 0h1mn18s avec H =0, M = 1 et S = 18

La pendule 2

Ecrivez un algorithme qui demande sous forme de nombres l'heure

qu'il est (un nombre pour les heures, un pour les minutes et un pour lessecondes). Cet algorithme indiquera ensuite s'il s'agit d'une heure

valide ou non.

Boule de cristal

Cet algorithme est destin prdire l'avenir, et il doit tre infaillible ! Illira au clavier lheure et les minutes, et il affichera lheure quil sera uneminute plus tard. Par exemple, si l'utilisateur tape 21 puis 32,l'algorithme doit rpondre : "Dans une minute, il sera 21 heure(s) 33".

NB : on suppose que l'utilisateur entre une heure valide. Pas besoindonc de la vrifier.



34/85

07/12/2010

34

STRUCTURESSTRUCTURES Dclaration dune structure Une structure est un type qui permet de stocker plusieurs donnes,

de mme type ou de types diffrents, dans une mme variable detype structure.

Exemple : Dclaration dune structure Point qui contient deuxchamps x et y de type rel (float en C)

struct Point{

float x;

float y;

};

La dclaration dune variable de type struct Point se fait ensuite

comme pour toute autre variable : struct Point P; {Dclaration dune variable P}


STRUCTURESSTRUCTURES Utilisation dune structure

Une fois la variable dclare, on accde aux donnes x et y du pointP par un point. Ces donnes sont dsignes dans le programme parP.x, P.y. Ces donnes, ici de type float, sont traites commenimporte quelle autre donne de type float dans le programme.

Lon pourrait rajouter dautres donnes des types que lon souhaite la suite des donnes x, y dans la structure.

Exemple de programme avec une structure Point.



35/85

07/12/2010

35

STRUCTURESSTRUCTURES Utilisation dune structureint main(){

struct Point{

float x;

float y;

}; {ne pas oublier le point-virgule}

struct Point P;

puts("Coordonnes dun Point 2D :");

scanf("%f %f ", &P.x, &P.y);

tmp = (P.x * P.x) + (P.y * P.y);

printf("Distance OP = %f", sqrt(tmp));return 0;

}


STRUCTURESSTRUCTURES Utilisation dune structure Pour viter la rptition du mot struct, lors de la dclaration des

variables de type struct Point, on peut dfinir un raccourci parun typedef lors de la dfinition de la structure pour donner un

nouveau nom ce type :

typedef struct Point{

float x;

float y;

}Point2D;

La dclaration dune variable de type struct Point est alors

simplifie comme suit :

Point2D P;

NB : Les donnes x et y du Point2D sont toujours dsignes par P.x

et P.y



36/85

07/12/2010

36

STRUCTURESSTRUCTURES Utilisation dune structure Reprenons lexemple suivant considrant la nouvelle forme de

dclaration :

int main(){

struct Point{

float x;

float y;

}Point2D; {ne pas oublier le point-virgule}

Point2D P;

puts("Coordonnes dun Point 2D :");

scanf("%f %f ", &P.x, &P.y);

tmp = (P.x * P.x) + (P.y * P.y);

printf("Distance OP = %f", sqrt(tmp));

return 0;

}


STRUCTURESSTRUCTURES Utilisation dune structure

typedef struct Point{

float x;

float y;

}Point2D; {ne pas oublier le point-virgule}

{La procdure suivante prend un Point2D en paramtre}

voidAfficherPoint2D (Point2D P){printf(" abs = %f , ord = %f " , P.x, P.y);

}

{La fonction suivante rend un Point2D}

Point2D SaisiePoint2D(){

Point2D P;

afficher("Coordonnes dun Point 2D :")

scanf ("%f %f" , &P.x, &P.y);

return P;

}



37/85


38/85

07/12/2010

38

LISTES CHAINEESLISTES CHAINEES Quest ce quune liste chane ?

Une liste chane est un ensemble de cellules lies entre elles par des

pointeurs.Chaque cellule est une structure contenant :

- Une ou plusieurs donnes comme dans nimporte quelle structure

- Un pointeur suivantsur la cellule suivante.

On accde la liste par un pointeur L sur la premire cellule, puis enparcourant la liste dune cellule lautre en suivant les pointeurs suivant.Le dernier pointeur suivantvaut NULL (cest--dire pointe sur RIEN), cequi indique la fin de la liste .


Donne 1 Donne 2 Donne 3 Donne 4 L

Cellules

Pointeurs suivant Pointeur NULL

Figure 1 Exemple de liste chane avec 4 cellules

LISTES CHAINEESLISTES CHAINEES Dclarer une liste chane

Pour dclarer une liste chane, il faut dclarer une nouvelle structure de

donnes : la structure qui reprsentera une cellule.

{Les donnesdans les cellules sont des rels (float)}

typedef float TypeDonnee;

{Dfinition du type cellule}

typedef struct Cell{

/* Dfinition des donnes */

TypeDonnee donnee ;

/* Pointeur sur la structure suivante de mme type que celle quon est

entrain de dfinir */

struct Cell *suivant;

}TypeCellule;

NB: La structure TypeCellule contient un pointeur sur TypeCellule. On ne peutpas dclarer directement un pointeur sur le type TypeCellule qui est en coursde dfinition.



39/85

07/12/2010

39

LISTES CHAINEESLISTES CHAINEES Dclarer une liste chane

On dclare ensuite le pointeur qui donne ladresse de la premire cellule

(NULL si la liste est vide)

TypeCellule *L; /* Dclaration dune liste */

voidAfficheDonnee (TypeCellule *cellule){

printf(" %f " , cellule->donnee);

}

TypeDonnee SaisieDonnee (){

TypeDonnee donnee;

puts ("Saisissez la donnee :" );

scanf("%f", &donnee);

return donnee;

}


LISTES CHAINEESLISTES CHAINEES Insertion en tte de liste

La fonction suivante prend en paramtres une liste et une donne, et ajoute

en tte de liste. La fonction renvoie la nouvelle adresse de la tte de liste. (Cf.Figure 2).

TypeCellule * InsererEnTete (TypeCellule *OldListe, TypeDonnee

donnee){

TypeCellule *NewListe ; /* Nouvelle tte de liste *//*Allocation de mmoire pour la nouvelle cellule*/

NewListe = (typeCellule*) malloc (sizeof(TypeCellule)):

/*On met la donne ajouter dans la cellule*/

NewListe->donnee = donnee;

/*Le pointeur suivant de la nouvelle cellule pointe

maintenant sur lancienne liste */

NewListe->suivant = OldListe;

/*On retourne la nouvelle liste */

return NewListe;

}



40/85

07/12/2010

40

LISTES CHAINEESLISTES CHAINEES Insertion en tte de liste

Schma rcapitulatif


newData

Donne 1 Etc . Donne n OldListe

NewListe

Figure 2 Insertion en tte de liste

NB : Faut pas confondre lutilisation du point (.) et lutilisation de la flche pouraccder aux champs dune structure. On utilise le point pour une variable detype structure et la flche pour une variable de type pointeur surstructure.

LISTES CHAINEESLISTES CHAINEES Construction dune liste chane

Les listes chanes se construisent par des insertions successives. La fonction suivante

ralise la saisie dune liste chane au clavier.

TypeCellule * SaisieListe (){

char choix;

TypeDonnee donnee;

/*Dclaration dune liste vide, initialisation NULL obligatoire */

TypeCellule *L =NULL;

do{

donnee = SaisieDonnee();

L = InsererEnTete (L, donnee); /*Insertion en tte */

puts("Voulez-vous insrer un lment ?");

getchar (choix);

} while(choix == o || choix == O);

return L;

}



41/85

07/12/2010

41

LISTES CHAINEESLISTES CHAINEES Parcours de liste

Lide de parcours de liste chane est de prendre un pointeur auxilliaire p.

On fait pointer p sur la premire cellule, puis le pointeur p passe la cellulesuivante (par une affectation p = p->suivant) , etc . Le parcours sarrtelorsque p vaut le suivant de la dernire cellule, cest--dire lorsque p vautNULL.



P Pointeur p->suivant

Figure 3 Parcours de la liste chane

LISTES CHAINEESLISTES CHAINEES Parcours de liste

En guise dexemple, considrons la procdure suivante qui ralise laffichage

dune liste chane.

voidAfficheListe (TypeCellule *L){

TypeCellule *P;

P = L /* On pointe sur la premire cellule */

while (P != NULL){

AfficheDonnee (P);

P = P->suivant

}

}

Lors du parcours, on sarrte lorsque p vaut NULL et non pas quandp->suivant vaut NULL. En effet, p->suivant vaut NULL lorsque p pointesur la dernire cellule. Il faut bien videmment traiter galement cettedernire.



42/85

07/12/2010

42

LISTES CHAINEESLISTES CHAINEES Insertion en fin de liste

Avec des insertions en tte de liste, la liste obtenue est classe lenvers, le

dernier lment saisi est le premier lment de la liste. Pour obtenir leslments lendroit, il faut faire les insertions en fin de liste.

Lajout dune cellule en fin de liste est un peu plus compliqu que linsertionen tte de liste. Notamment, elle ncessite un parcours de la liste pourrechercher ladresse du dernier lment. (Cf. figure 4)

TypeCellule * InsererEnFin (TypeCellule *L, TypeDonnee donnee){

TypeCellule *NewCell ; /* Nouvelle cellule */

/*Allocation de mmoire pour la nouvelle cellule*/

NewCell = (typeCellule *) malloc (sizeof(TypeCellule));

NewCell->donnee = donnee ;

NewCell->suivant = NULL;

if (L == NULL){

/* Cas particulier : liste vide */



(Suite )

L = NewCell;

} else {

/*On recherche la dernire cellule */

p = L;

while (p->suivant != NULL){

p = p->suivant;

} /* fin while */

p->suivant = NewCell; /*chanage*/

} /* fin if */

return L;

} /* fin main */



43/85

07/12/2010

43


Schma rcapitulatif :



P

NewCell

Figure 4 Insertion en fin de liste

Donne 5

Chanage


Linsertion en fin de liste permet de saisie une liste chane lendroit :

TypeCellule * SaisieListe (){

char choix;

TypeDonnee donnee;

/*Dclaration dune liste vide, initialisation

NULL obligatoire */

TypeCellule *L =NULL;

do{

donnee = SaisieDonnee();

L = InsererEnFin (L, donnee); /* Insertion en

tte */

puts("Voulez-vous insrer un lment ?");

getchar (choix);

} while(choix == o || choix == O);

return L;

}mardi 7 dcembre 2010 86


44/85

07/12/2010

44

LISTES CHAINEESLISTES CHAINEES Libration de mmoire

Pour librer la mmoire occupe par une liste chane, il faut dtruire

chacune des cellules avec la fonction free. Pour viter les ventuels

bugs, il vaut mieux que la fonction rinitialise la tte de la liste NULL (listevide). Pour cela la fonction doit modifier le pointeur de tte de liste, et il fautdonc passer ce pointeur par adresse.

void Liberation (TypeCellule **pL){

/*Passage dun pointeur par adresse*/

/*Pointeur sur Pointeur*/

typeCellule *p;

while (*pL != NULL) {

p = *pL;

*pL = (*pL)->suivant

free(p)

}

*pL = NULL;

}


LISTES CHAINEESLISTES CHAINEES Libration de mmoire

Exemple global :

Programme FreeMemory

int main(){

typeCellule *L;

L = SaisieListeEndroit ();

AfficheListe (L);

Liberation (&L); /*passage de ladresse du

pointeur*/

return 0;

}

NB: Aprs lappel de la procdure Liberation, la liste est vide (pointeurNULL)



45/85

07/12/2010

45

EXERCICESEXERCICESExercice 1 :

Ecrire un programme qui :

Initialise une liste chaine de nombres entiers par insertion successive en finavec laide de lutilisateur.

Affiche toute la liste ainsi cre.

Insre la valeur "0" aprs tout nombre pair rencontre dans la liste.

Affiche ensuite la chane rsultante.

On pourra crer une fonction AfficheListe qui affichera le contenu de laliste.

Par exemple :

Chaine initialise : 1 5 8 9 0 2 8 7

Chane rsultante : 1 5 8 0 9 0 0 2 0 8 0 - 7


PILESPILES Quest ce quune pile ?

Une pile est une structure de donnes dans laquelle on peut ajouter et

supprimer des lments suivant la rgle du dernier arriv premier sortiouencore LIFO (LastInFirstOut).

Le nom de pile vient dune analogie avec une pile dassiettes (par exemple)

o lon poserait toujours les assiettes sur le dessus de la pile, et o lonprendrait toujours les assiettes sur le dessus de la pile. Ainsi la dernireassiette pose sera utilise avant toutes les autres.

Une pile peut tre implmente par un tableau ou par une liste chane.Dans les deux cas, il est commode de raliser sur les piles des oprations de

base, appeles primitives de gestion des piles.



46/85

07/12/2010

46

PILESPILES Les primitives de gestion des piles

- Initialiser

Cre une pile vide

- EstVide

Renvoie 1 si la pile est vide, 0 sinon

- Empiler

Permet dajouter un lment au sommet de la pile. La fonction renvoie uncode derreur si besoin au cas de manque de mmoire.

- Depiler

Supprime le sommet de la pile. Llment supprim est retourn par lafonction Depilerpour pouvoir tre utilis.


PILESPILES Les primitives de gestion des piles

Le principe de gestion des piles est que, lorsquon utilise une pile, on ne se

proccupe pas de la manire dont elle a t implmente, mais on utiliseuniquement les primitives qui sont toujours les mmes.

Dans les prochains slides, nous tudierons limplmentation des primitives

de gestion des piles sous forme de liste chane.



47/85

07/12/2010

47

PILESPILES Types

Pour implmenter une pile sous forme de liste chane, on cre la structure

de donnes suivante.



TypeDonnee donnee;

/* pointeur sur la cellule prcdente */

struct Cell *suivant;

}TypeCellule;

typedef TypeCellule* Pile;

/* La Pile est un pointeur sur la tte de liste */


PILESPILES Crer une pile vide

La fonction permettant de crer une pile vide est la suivante :

Pile Initialiser(){

return NULL; /*On retourne une liste vide*/

}



48/85

07/12/2010

48

PILESPILES Pile vide

La fonction permettant de savoir si la pile est vide est la suivante. Elle

renvoie 1 si la pile est vide, 0 sinon.

int EstVide(Pile P){

P == NULL ? return 1 : return 0 ;

}


PILESPILES Ajouter un lment au sommet

La fonction dajout dun lment est une fonction dinsertion en tte de liste.

void Empiler(Pile* pP, TypeDonnee elt){

Pile NewCell;

NewCell = (TypeCellule*)malloc(sizeof(TypeCellule));/*ajout de llment empiler*/

NewCell ->donnee = elt;

/*Insertion en tte de liste*/

NewCell ->suivant = *pP;

/*Mise jour de la tte de liste*/

*pP NewCell;

}



49/85


50/85

07/12/2010

50

FILESFILES Quest ce quune file ?

Une file est une structure de donnes dans laquelle on peut ajouter et

supprimer des lments suivant la rgle du premier arriv premier sorti, ouencore FIFO (FirstInFirstOut).

Le nom de file vient de lanalogie avec une file dattente un guichet, danslaquelle le premier arriv sera le premier servi. Les usagers arrivent en fin defile et sortent de la file sa tte.

Une file peut tre implmente par une liste chane, ou par un tableau avecune gestion circulaire. Comme dans le cas des piles, la gestion par tableauxprsente linconvnient que la file a une capacit limite, contrairement lagestion par listes chanes.

Comme dans le cas des piles, on gre les files laide des primitives.


FILESFILES Les primitives de gestion des files

- Initialiser

Cre une file vide

- EstVide

Renvoie 1 si la file est vide, 0 sinon

- Enfiler

Permet dajouter un lment en fin de la file. La fonction renvoie uncode derreur si besoin au cas de manque de mmoire.

- Defiler

Supprime la tte de la file. Llment supprim est retourn par lafonction Defilerpour pouvoir tre utilis.



51/85

07/12/2010

51

FILESFILES Types

Pour implmenter une file sous forme de liste chane, on introduit un

pointeur sur la tte de liste et un pointeur sur la queue de liste (Cf. figure 5).Ceci permet de faire les insertion en queue de liste sans avoir parcourir laliste pour trouver ladresse de la dernire cellule.



TypeDonnee donnee;

struct Cell *suivant; /* pointeur sur la cellule suivante */

}TypeCellule;

typedef struct {

TypeCellule *tete, *queue; /* pointeur sur la premire etdernire cellule */

}File;


FILESFILES Pointeur en tte et en queue de file

Schma illustratif :


Donne 1 Donne 2 Donne 3 Donne 4

tte queue

Figure 4 Gestion dune file


52/85


53/85

07/12/2010

53

FILESFILES Accder en tte de file

Le tte de la file est le premier lment entr dans la liste. La fonction renvoie

1 en cas de liste vide, 0 sinon.

intAccederTete(File F, TypeDonnee *pelt){

if (estVide(F) == 1){

return 1; /*code derreur, la file est vide*/

}

/* On renvoie la donne de la tte*/

*pel = F.tete->donnee

return 0;

}


FILESFILES Ajouter un lment la fin de la file

La fonction dajout dun lment est une fonction dinsertion en fin de liste.

void Enfiler(File* pF, TypeDonnee elt){

TypeCellule *NewCell;

NewCell = (TypeCellule*)malloc(sizeof(TypeCellule));

NewCell->donnee = elt; /*ajout de llment enfiler*/

NewCell->suivant = NULL;

if (pF->tete == NULL){ /* si file vide */

pF->queue = pF->tete = NewCell;

} else {

pF->queue->suivant = NewCell; /* insertion en finde file */

pF->queue = NewCell;

}

}



54/85

07/12/2010

54

FILESFILES Supprimer un lment de la file

La fonction Defiler supprime la tte de liste en cas de file non vide. La fonction

renvoie 1 en cas derreur, et 0 en cas de succs. La file est passe par adresse, ona donc un double pointeur.

int Defiler(File* pF, TypeDonnee *pelt){

TypeCellule *p;

if (EstVide(*pF) == 1)

return 1; /*On ne peut pas supprimer dlment*/

*pelt = pF->tete->donnee; /*On renvoie llment*/

p = pF->tete; /*Mmorisation de la tete de file*/

pF->tete = pF->tete->suivant; /*passage au suivant*/free(p); /*Destruction de lancienne tete de file*/

return 0;

}


FILESFILES Dtruire

La destruction de la liste doit librer toute la mmoire de la liste chane

(destruction individuelle des cellules).

void Detruire(File *pF){

TypeCellule *p, *q;

p = pF->tete /*Initialisation pour parcourir la liste*/

while (p!= NULL){ /* Parcours de la liste */

q = p; /* Mmorisation de ladresse */

p = p->suivant; /* Passage au suivant */

free (q);

}

*pF = p;

}



55/85

07/12/2010

55

EXERCICESEXERCICESExercice 1

Ecrire une fonction capable de comparer le contenu dune file et le contenu dune

pile. Dans le cas o la pile contient de son sommet vers sa base, les mmes

lments que la file de son dbut vers sa fin, la fonction doit retourner Vrai. Dans

le cas contraire elle retourne Faux.


LA RECURSIVITELA RECURSIVITE Introduction

Une procdure rcursive est une procdure rcursive

Une procdure rcursive est une procdure qui sappelle elle-mme. Larcursivit utilise toujours la pile du programme en cours.

Une "pile" est une zone mmoire rserve chaque programme; sa taille

peut tre fixe manuellement par l'utilisateur. Son rle est de stocker lesvariables locales et les paramtres d'une procdure de sorte pouvoir yrevenir au cas o un appel modulaire aurait interrompu lexcution encours.

Dans une procdure rcursive, toutes les variables locales sont stockes dansla pile, et empiles autant de fois qu'il y a d'appels rcursifs. Donc la pile seremplit progressivement, et si on ne fait pas attention on arrive un"dbordement de pile". Ensuite, les variables sont dsempiles.

Une procdure rcursive comporte un appel elle-mme, alors qu'uneprocdure non rcursive ne comporte que des appels d'autres procdures.



56/85

07/12/2010

56

LA RECURSIVITELA RECURSIVITE Construction dun algorithme rcursif

Un peu comme pour dfinir une suite par rcurrence enmaths, il faut :

1. Un (ou plusieurs) cas de base, dans lequel lalgorithme nesappelle pas lui-mme.

Sinon lalgorithme ne peut pas terminer.

2. Si on ne se situe pas dans un cas de base, lalgorithme faitappel lui-mme (appel rcursif).

Chaque appel rcursif doit en principe se rapprocher dun

cas de base, de faon permettre la terminaison duprogramme.


LA RECURSIVITELA RECURSIVITE Introduction

Exemple :

void recursive (/*paramtres*/) {

/*dclarations des variables locales*/

if( /*test darrt*/){

/*instructions du point darrt*/

} else {

/* instructions*/

recursive(/*paramtres changs*/);

/*instructions*/

}

}



57/85

07/12/2010

57

LA RECURSIVITELA RECURSIVITE Exemple avec factorielint factorielle (int n) {

if(n==0)

return 1 ; {cas de base}

{point terminal}

else

return n * factorielle (n-1);

}

Cette fonction retourne n! si n est positif ou nul, et ne termine pas si nest ngatif (appels rcursifs infinis).

Note : Concrtement, si n est ngatif le programme provoque (le plussouvent) une erreur lexcution pour cause de dpassement demmoire autoris dans les appels de fonctions (pile dappel).


LA RECURSIVITELA RECURSIVITE Commentaires

On constate, et il le faut, que les paramtres de l'appel rcursifchangent.

En effet, chaque appel, l'ordinateur stocke dans la pile les variables locales; le fait de ne rien changer dans les paramtres

ferait que l'ordinateur effectuerait un appel infini cette procdure,ce qui se traduirait en ralit par un dbordement de pile, et d'arrtde l'excution de la procdure en cours.

Grce ces changements, tt ou tard l'ordinateur rencontrera unensemble de paramtres vrifiant le test d'arrt, et donc cemoment la procdure rcursive aura atteint le "fond" (pointterminal).

Ensuite les paramtres ainsi que les variables locales sontdsempiles au fur et mesure qu'on remonte les niveaux.



58/85

07/12/2010

58

LA RECURSIVITELA RECURSIVITE Commentaires

On constate, et il le faut, que les paramtres de l'appel rcursifchangent.

En effet, chaque appel, l'ordinateur stocke dans la pile les variables locales; le fait de ne rien changer dans les paramtresferait que l'ordinateur effectuerait un appel infini cette procdure,ce qui se traduirait en ralit par un dbordement de pile, et d'arrtde l'excution de la procdure en cours.

Grce ces changements, tt ou tard l'ordinateur rencontrera unensemble de paramtres vrifiant le test d'arrt, et donc cemoment la procdure rcursive aura atteint le "fond" (pointterminal).

Ensuite les paramtres ainsi que les variables locales sontdsempiles au fur et mesure qu'on remonte les niveaux.

Note (Point essentiel) : chaque appel rcursif dispose de sespropres variables locales.


LA RECURSIVITELA RECURSIVITE Itrations contre rcursion


while (C){

/* bloc */

}

void fonctionRecur (){

if (C){

/* bloc */

fonctionRecur();

}

}

Rciproque :Tout algorithme itratif peut tre transform en algorithme rcursif sansboucle (en grant convenablement les variables). Mais : a peut tre moins lisible ; chaque itration prend un peu de place en mmoire (occupe la pile) ; la gestion des variables peut tre plus complique.


59/85

07/12/2010

59

LA RECURSIVITELA RECURSIVITE Intrt des algorithmes rcursifs

Essentiellement, deux intrts (pas si diffrents) :

1. dcomposer une action rptitive en sous-actions identiques de petites tailles :

pour rechercher un lment dans un tableau tri, ou pourtrier un tableau (tri fusion), on parle de diviser pourrgner .

2. pour explorerun ensemble de possibilits (par exempledes coups dans un jeu), on peut faire un appel rcursif surchaque possibilit.


EXERCICESEXERCICESExercice 1

Recrire les solutions des exercices du slide 93 enutilisant une mthode itrative.

Exercice 2

Soient les suite un et vn suivantes :

, pour n > 0

, pour n > 1

Ecrire des modules itratifs et rcursifs permettant decalculer llment dindice n pour chaque srie.


=

=

+ nnuu

u

74

2

1

0

+=

==

++ 12

101

nnnvvv

vv


60/85

07/12/2010

60

ARBRES BINAIRESARBRES BINAIRES Reprsentations arborescentes

Les arborescences sont utilises : Dans la vie de tous les jours pour reprsenter des hirarchies,

des classifications.

Dans le domaine de linformatique : pour reprsenter lesinformations ci-dessus et aussi :

Lorganisation interne des fichiers en mmoire

Le mode de calcul dune expression

Lorganisation de donnes tries


ARBRES BINAIRESARBRES BINAIRES Exemple


Signification du lien :-Du plus gnrique au plus spcifique

Autres significations possibles :-Du plus ancien au plus rcent-De la plus haute priorit la moindre-Du plus complexe au plus simple


61/85

07/12/2010

61

ARBRES BINAIRESARBRES BINAIRESComment caractriser un arbre :

Par sa racine

Par ses sommets

Par les arcs reliant les sommets entre eux

Par ses feuilles


ARBRES BINAIRESARBRES BINAIRES Dfinition rcursive dun arbre binaire

Un arbre binaire est : Soit un arbre binaire vide

Soit un arbre binaire avec deux sous arbres binaires (appels fils gauche

et fils droit )

Dfinition rcursive car un arbre binaire est dfinipar un arbre binaire.

La rgle "soit un arbre binaire vide" assure larrtet donc la cohrence de la dfinition.



62/85

07/12/2010

62

ARBRES BINAIRESARBRES BINAIRES Primitives de gestion des arbres binaires

Soit ArbreBinaire une structure dfinissant un lmentdun arbre binaire et une rfrence gauche et droit ses deuxfils.


typedef struct arbre {

TypeDonnee info;

struct arbre *gauche;

struct arbre *droit;

} ArbreBinaire;

int estVide (ArbreBinaire *cible);

/*Retourne 1 (VRAI) si larbre est vide et 0 (FAUX)

sinon*/


ARBRES BINAIRESARBRES BINAIRES Primitives de gestion des arbres binaires

int info (ArbreBinaire *cible, TypeDonnee *eltA);

/*Ecrit dans la zone pointe par eltA la valeur

enrgistre dans la racine, retourne un code derreur

si larbre est vide*/

ArbreBinaire* filsG(ArbreBinaire *cible); /*Retourne larbre binaire form par le sous arbre

gauche (fils gauche)*/

ArbreBinaire* filsD(ArbreBinaire *cible);

/*Retourne larbre binaire form par le sous arbre

droit (fils droit)*/

ArbreBinaire* newArbreBinaire (ArbreBinaire

*Gauche, typeDonnee info, ArbreBinaire *Droit);

/*Retourne larbre binaire cr*/



63/85

07/12/2010

63

ARBRES BINAIRESARBRES BINAIRES Primitive : estVide

int estVide (ArbreBinaire *cible){

/*Retourne 1 (VRAI) si larbre est vide et 0 (FAUX)

sinon*/

if(cible == NULL) return 1;

else return 0;

}


ARBRES BINAIRESARBRES BINAIRES Primitive : info

int info (ArbreBinaire *cible, TypeDonnee *eltA){

/*Ecrit dans la zone pointe par eltA la valeur

enrgistre dans la racine, retourne un code derreur si

larbre est vide*/

if(estVide(cible)) return -1; /*code derreur*/

else *eltA = cible->info;

return 0;

}



64/85

07/12/2010

64

ARBRES BINAIRESARBRES BINAIRES Primitive : filsG

ArbreBinaire* filsG (ArbreBinaire *cible){

/*Retourne larbre binaire form par le sous arbre gauche

(fils gauche)*/

if(!estVide(cible)){

return cible->gauche;

}

}


ARBRES BINAIRESARBRES BINAIRES Primitive : filsD

ArbreBinaire* filsD (ArbreBinaire *cible){

/*Retourne larbre binaire form par le sous arbre droit

(fils droit)*/

if(!estVide(cible)){

return cible->droit;

}

}



65/85

07/12/2010

65

ARBRES BINAIRESARBRES BINAIRES Cration dun arbre binaire

ArbreBinaire* newArbreBinaire (ArbreBinaire *Gauche,

typeDonnee info, ArbreBinaire *Droit){

ArbreBinaire *newArbre;

newArbre = (ArbreBinaire *) malloc (sizeof(ArbreBinaire));

newArbre->info = info;

newArbre->droit = Droit;

newArbre->gauche = Gauche;

return newArbre;

}


ARBRES BINAIRESARBRES BINAIRES Affichages : ordres possibles

Soit larbre suivant :


Affichage- ordre prfixe : 3 3 7 4 8 0 1 5 2 6 7 9 (racine, gauche, droite)- ordre postfixe : 4 8 7 3 1 6 7 2 9 5 0 3 (gauche, droite, racine)- ordre infixe : 4 8 7 3 3 1 0 6 7 2 5 9 (gauche, racine, droite)


66/85

07/12/2010

66

ARBRES BINAIRESARBRES BINAIRES Larbre prcdent est alors cr par :


ArbreBinaire *arbreB;

arbreB =

newArbreBinaire(

newArbreBinaire(

newArbreBinaire(

newArbreBinaire(NULL, 4, NULL), 7,

newArbreBinaire(NULL, 8, NULL)

), 3, NULL ), 3,

newArbreBinaire(

newArbreBinaire(NULL, 1, NULL), 0,

newArbreBinaire(newArbreBinaire( newArbreBinaire(NULL, 6, NULL),

2, newArbreBinaire(NULL,7, NULL)), 5,

newArbreBinaire(NULL, 9, NULL) )));

ARBRES BINAIRESARBRES BINAIRES Affichage : PREFIXE

void affichePrefixe (ArbreBinaire *unArbre){

/*

Affiche les valeurs portes par les sommets de

l'arbre binaire, en affichant la valeur porte par

la racine avant les valeurs portes par les sous-

arbres gauche et droit.

*/

if(!estVide(unArbre)){

printf("%.0f ", unArbre->info);

affichePrefixe(unArbre->gauche);

affichePrefixe(unArbre->droit);

}

}



67/85

07/12/2010

67

ARBRES BINAIRESARBRES BINAIRES Affichage : POSTFIXE

void affichePostfixe (ArbreBinaire *unArbre){

/*



la racine aprs les valeurs portes par les sous-

arbres gauche et droit

*/


affichePostfixe(unArbre->gauche);

affichePostfixe(unArbre->droit);


}

}


ARBRES BINAIRESARBRES BINAIRES Affichage : INFIXE

void afficheInfixe (ArbreBinaire *unArbre){

/*



la racine entre les valeurs portes par les sous-

arbres gauche et droit.

*/


afficheInfixe(unArbre->gauche);


afficheInfixe(unArbre->droit);

}

}



68/85

07/12/2010

68

ARBRES BINAIRESARBRES BINAIRES Compte le nombre de sommets dun arbreCas de base : (cas particulier) : arbre vide : rsultat = 0

Cas gnral : 1 (sommet de larbre courant)

+ nb Sommets dans FilsG

+ nb Sommets dans FilsD

int compteSommet (ArbreBinaire *unArbre){

/*

Compte le nombre de sommets dun arbre binaire

*/

if(estVide(unArbre))

return 0;else return (1 + compteSommet(unArbre->gauche) +

compteSommet(unArbre->droit));

}


ARBRES BINAIRESARBRES BINAIRESAPPLICATION

Arbres binaires de recherche (ABR)

Un arbre binaire de recherche est un arbre binairedans lequel la valeur de chaque sommet est :

Suprieure [ou gale] toutes les valeurs tiquetant lessommets du sous-arbre gauche de ce sommet,

Et Infrieure toutes les valeurs tiquetant les sommetsdu sous-arbre droit de ce sommet.

Note: Dans un arbre binaire de recherche, leparcours infixe fournit les contenus des nuds enordre croissant.



69/85

07/12/2010

69


Algorithme de construction dun ABR

Soit info la valeur placer dans lABR (lajout se fera toujourssur une feuille : arbre binaire dont le FilsG et le FilsD sontvides)

Si larbre est vide

Alors

En crer un, rduit sa racine, tiquete avec info.

Sinon

Si info valeur porte par la racine

Alors lajouter au sous-arbre gauche : si cet arbre nest pas vide,

reprendre lalgorithme sur ce sous-arbre.

Sinon lajouter au sous-arbre droit : si cet arbre nest pas vide,reprendre lalgorithme sur ce sous-arbre.

Finsi

Finsi


ARBRES BINAIRESARBRES BINAIRES APPLICATION

Ajout dune valeur dans un ABR

void ajoutABR(ArbreBinaire **cible, typeDonnee info){

if(estVide(*cible))

*cible = newArbreBinaire (NULL, info, NULL);

else

if(info info)

ajoutABR(&(*cible)->gauche, info);

else

ajoutABR(&(*cible)->droit, info);

}



70/85

07/12/2010

70


Utilisation dun ABR : trier une liste

TP :

- Crer une liste chaine quelque.

- Ajouter les lments de la liste dans un ABR

- Afficher laide de la primitive afficheInfixe les lments delarbre.


FICHIERS SEQUENTIELSFICHIERS SEQUENTIELSDfinitions et PropritsFichier

Un fichier(angl.: file) est un ensemble structur de donnes stocken gnral sur un support externe (disquette, disque dur, disqueoptique, bande magntique, ...).

Un fichier structur contient une suite d'enregistre-ments homognes, qui regroupent le plus souvent plusieurscomposantes appartenant un mme ensemble. (champs).

Fichier squentiel

Dans des fichiers squentiels, les enregistrements sont mmorissconscutivement dans l'ordre de leur entre et peuvent seulement trelus dans cet ordre. Si on a besoin d'un enregistrement prcis dans unfichier squentiel, il faut lire tous les enregistrements qui le prcdent,en commenant par le premier.



71/85


72/85

07/12/2010

72

FICHIERS SEQUENTIELSFICHIERS SEQUENTIELSLe type FILE*

Pour pouvoir travailler avec un fichier, un programme a besoin d'un certainnombre d'informations au sujet du fichier :

- adresse de la mmoire tampon, position actuelle de la tte de lecture/criture,type d'accs au fichier : criture, lecture, tat d'erreur, . . .

Ces informations (dont nous n'aurons pas nous occuper), sont rassembles dansune structure du type spcial FILE.

Lorsque nous ouvrons un fichier avec la commande fopen, le systme gnreautomatiquement un bloc du type FILE et nous fournit son adresse.

Tout ce que nous avons faire dans notre programme est :

1. dclarer un pointeur du type FILE* pour chaque fichier dont nous avonsbesoin,

2. affecter l'adresse retourne par fopen ce pointeur,

3. employer le pointeur la place du nom du fichier dans toutes les instructionsde lecture ou d'criture,

4. librer le pointeur la fin du traitement l'aide de fclose.


FICHIERS SEQUENTIELSFICHIERS SEQUENTIELSExemple : Crer et afficher un fichier squentiel

Avant de rentrer dans les dtails du traitement des fichiers, arrtons-nous sur unpetit exemple comparatif qui runit les oprations les plus importantes sur lesfichiers.

Problme

On se propose de crer un fichier qui est form d'enregistrements contenantcomme information le nom d'une personne. Chaque enregistrement est doncconstitu d'une seule rubrique, savoir, le nom de la personne.

L'utilisateur doit entrer au clavier le nom du fichier, le nombre de personnes et lesnoms des personnes. Le programme se chargera de crer le fichier correspondantsur disque dur.

Aprs avoir crit et ferm le fichier, le programme va rouvrir le mme fichier enlecture et afficher son contenu, sans utiliser le nombre d'enregistrements introduitdans la premire partie.



73/85

07/12/2010

73

FICHIERS SEQUENTIELSFICHIERS SEQUENTIELSSolution en langage C

#include

main() {

FILE *P_FICHIER; /* pointeur sur FILE */

char NOM_FICHIER[30], NOM_PERS[30];

int C, NB_ENREG;

/*Premire partie : Crer et remplir le fichier*/

printf("Entrez le nom du fichier crer : ");

scanf("%s", NOM_FICHIER);

P_FICHIER = fopen(NOM_FICHIER, "w"); /* write */

printf("Nombre d'enregistrements crer : ");

scanf("%d", &NB_ENREG);

C = 0;

while (C


74/85

07/12/2010

74

FICHIERS SEQUENTIELSFICHIERS SEQUENTIELSOuvrir et fermer des fichiers squentiels

Avant de crer ou de lire un fichier, nous devons informer lesystme de cette intention pour qu'il puisse rserver la mmoirepour la zone d'change et initialiser les informations ncessaires l'accs du fichier. Nous parlons alors de l'ouverture d'un fichier.

Aprs avoir termin la manipulation du fichier, nous devons viderla mmoire tampon et librer l'espace en mmoire que nousavons occup pendant le traitement. Nous parlons alors delafermeture du fichier.

L'ouverture et la fermeture de fichiers se font l'aide desfonctions fopen et fclose dfinies dans la bibliothquestandard .


FICHIERS SEQUENTIELSFICHIERS SEQUENTIELSOuvrir un fichier en C fopen

Lors de l'ouverture d'un fichier avec fopen, le systme s'occupe de la rservationde la mmoire tampon dans la mmoire centrale et gnre les informations pourun nouvel lment du type FILE.

L'adresse de ce bloc est retourne comme rsultat si l'ouverture s'est droule avecsuccs.

La commande fopen peut ouvrir des fichiers en criture ou en lecture endpendance de son deuxime paramtre ("r" ou "w") :

= fopen ( , "w" );

= fopen ( , "r" );

* est une chane de caractres constante ou une variable de type chanequi reprsente le nom du fichier sur le support physique.



75/85

07/12/2010

75

FICHIERS SEQUENTIELSFICHIERS SEQUENTIELSOuverture en criture

Dans le cas de la cration d'un nouveau fichier, le nom du fichier est ajout aurpertoire du mdium de stockage et la tte de lecture/criture est positionne surun espace libre du mdium.

Si un fichier existantest ouvert en criture, alors son contenu est perdu.

Si un fichier non existant est ouvert en criture, alors il est crautomatiquement. Si la cration du fichier est impossible alors fopen indique uneerreur en retournant la valeur zro.

Autres possibilits d'erreurs signales par un rsultat nul:

- chemin d'accs non valide,

- pas de disque/bande dans le lecteur,- essai d'crire sur un mdium protg contre l'criture,

- . . .

fichier sur le support physique.


FICHIERS SEQUENTIELSFICHIERS SEQUENTIELSOuverture en lecture

Dans le cas de la lecture d'un fichier existant, le nom du fichier doit tre retrouvdans le rpertoire du mdium et la tte de lecture/criture est place sur lepremier enregistrement de ce fichier.

Possibilits d'erreurs signales par un rsultat nul:- essai d'ouvrir un fichier non existant,

- essai d'ouvrir un fichier sans autorisation d'accs,

- essai d'ouvrir un fichier protg contre la lecture,

- . . .



76/85

07/12/2010

76

FICHIERS SEQUENTIELSFICHIERS SEQUENTIELSFermer un fichier en langage C

fclose ( );

est un pointeur du type FILE* reli au nom du fichier que l'on dsirefermer.

La fonction fclose provoque le contraire de fopen:

Si le fichier a t ouvert en criture, alors les donnes non crites de la mmoiretampon sont crites et les donnes supplmentaires (longueur du fichier, date etheure de sa cration) sont ajoutes dans le rpertoire du mdium de stockage.

Si le fichier a t ouvert en lecture, alors les donnes non lues de la mmoiretampon sont simplement 'jetes'.

La mmoire tampon est ensuite libre et la liaison entre le pointeur sur FILE etle nom du fichier correspondant est annule.

Aprs fclose() le pointeur est invalide. Des erreurs graves pourraient doncsurvenir si ce pointeur est utilis par la suite!


FICHIERS SEQUENTIELSFICHIERS SEQUENTIELSLire et crire dans des fichiers squentiels

Fichiers texte

Les fichiers que nous employons dans le cadre de cette prsentation sont desfichiers texte, c.--d. toutes les informations dans les fichiers sont mmorisessous forme de chanes de caractres et sont organises en lignes. Mme les valeursnumriques (types int, float, double, ...) sont stockes comme chanes decaractres.

Pour l'criture et la lecture des fichiers, nous allons utiliser les fonctionsstandard fprintf, fscanf, fputc et fgetc qui correspondent printf, scanf, putchar et getchar si nous indiquons stdout respective-ment stdin comme fichiers de sortie ou d'entre.



77/85

07/12/2010

77


Traitement par enregistrements

Ecrire dans un fichier squentiel en langage C -fprintf

fprintf( , "\n", );

fprintf( , "\n", );

...

fprintf( , "\n", );

* est un pointeur du type FILE* qui est reli au nom du fichier cible.

* , , ... , reprsentent les rubriques qui forment unenregistrement et dont les valeurs respectives sont crites dans le fichier.

, , ... , reprsentent les spcificateurs deformat pour l'criture des diffrentes rubriques.

Remarque

L'instruction :

fprintf(stdout, "Bonjour\n"); est identique

printf("\Bonjour\n");



Traitement par enregistrements

Lire dans un fichier squentiel en langage C -fscanf

fscanf( , "\n", );

fscanf( , "\n", );

...

fscanf( , "\n", );

* est un pointeur du type FILE* qui est reli au nom du fichier lire.

* , , ... , reprsentent les adresses des variables quivont recevoir les valeurs des diffrentes rubriques d'un enregistrement lu dans lefichier.

, , ... , reprsentent les spcificateurs de formatpour la lecture des diffrentes rubriques .

Remarque

L'instruction

fscanf(stdin, "%d\n", &N); est identique :

scanf("%d\n", &N);



78/85

07/12/2010

78


Traitement par caractres

La manipulation de fichiers avec les instructions fprintfet fscanfn'est pas assezflexible pour manipuler de faon confortable des textes crits. Il est alorsavantageux de traiter le fichier squentiellement caractre par caractre.

Ecrire un caractre dans un fichier squentiel - fputc

fputc( , );

fputc transfre le caractre indiqu par dans le fichier rfrenc par etavance la position de la tte de lecture/criture au caractre suivant.

* reprsente un caractre (valeur numrique de 0 255) ou le symbole de fin

de fichier EOF (quon verra par la suite).* est un pointeur du type FILE* qui est reli au nom du fichier cible.




La manipulation de fichiers avec les instructions fprintfet fscanfn'est pas assezflexible pour manipuler de faon confortable des textes crits. Il est alorsavantageux de traiter le fichier squentiellement caractre par caractre.

Ecrire un caractre dans un fichier squentiel - fputcfputc( , );

fputc transfre le caractre indiqu par dans le fichier rfrenc par etavance la position de la tte de lecture/criture au caractre suivant.

reprsente un caractre (valeur numrique de 0 255) ou le symbole de finde fichier EOF (quon verra par la suite).

est un pointeur du type FILE* qui est reli au nom du fichier cible.

Remarque

L'instruction

fputc('a', stdout); est identique

putchar('a');



79/85

07/12/2010

79



Lire un caractre dans un fichier squentiel - fgetc

= fgetc( );

fgetc fournit comme rsultat le prochain caractre du fichier rfrenc par et avance la position de la tte de lecture/criture au caractre suivant. A la fin dufichier, fgets retourne EOF.

reprsente une variable du type int qui peut accepter une valeur numriquede 0 255 ou le symbole de fin de fichier EOF.

est un pointeur du type FILE* qui est reli au nom du fichier lire.

Remarque

L'instructionC = fgetc(stdin); est identique

C = getchar();



Dtection de la fin d'un fichier en langage C - feof

feof( );

feofretourne une valeur diffrente de zro, si la tte de lecture du fichier rfrenc par est arrive la fin du fichier; sinon la valeur du rsultat est zro. est unpointeur du type FILE* qui est reli au nom du fichier lire.

Pour que la fonction feof dtecte correctement la fin du fichier, il faut qu'aprs la

lecture de la dernire donne du fichier, la tte de lecture arrive jusqu' la position de lamarque EOF.

Nous obtenons cet effet seulement si nous terminons aussi la chane de formatde fscanfpar un retour la ligne '\n' (ou par un autre signe d'espacement).

Exemple

Une boucle de lecture typique pour lire les enregistrements d'un fichier squentielrfrenc par un pointeur FP peut avoir la forme suivante:

while (!feof(FP)) {

fscanf(FP, "%s\n ... \n", NOM, ... );

. . .

}



80/85

07/12/2010

80


Exemple

Le programme suivant lit et affiche le fichier "C:\AUTOEXEC.BAT" en leparcourant caractre par caractre:

#include

#include

main() {

FILE *FP;

FP = fopen("C:\\AUTOEXEC.BAT", "r");

if (!FP) {

printf("Impossible d'ouvrir le fichier\n");

exit(-1);

}

while (!feof(FP)) putchar(fgetc(FP));

fclose(FP);

return 0;

}


ExercicesExercicesExercice 1

Crer sur disque (C:\\) puis afficher l'cran le fichier INFORM.TXT dont lesinformations sont structures de la manire suivante :

Numro de matricule (entier)

Nom (chane de caractres)

Prnom (chane de caractres)

Le nombre d'enregistrements crer est entrer au clavier par l'utilisateur.

Exercice 2

Ecrire un programme qui cre sur le disque (C:\\) un fichier INFBIS.TXT quiest la copie exacte (enregistrement par enregistrement) du fichier INFORM.TXT.

Exercice 3

Ajouter un nouvel enregistrement (entr au clavier) la fin de INFORM.TXT et sauver lenouveau fichier sous le nom INFBIS.TXT.



81/85

07/12/2010

81

ExercicesExercicesExercice 4Ecrire un programme qui dtermine dans un fichier un texte dont le nom est entr au clavier :

le nombre de caractres qu'il contient, le nombre de chacune des lettres de l'alphabet( sans distinguerles majuscules et les minuscules), le nombre de mots, le nombre de paragraphes (c.--d.: des retours la ligne),

Les retours la ligne ne devront pas tre comptabiliss dans les caractres. On admettra que deuxmots sont toujours spars par un ou plusieurs des caractres suivants: fin de ligne, espace,ponctuation: (. : , ; ? ! ) , parenthses: ( ), guillemets: ", apostrophe: '.

Utiliser une fonction d'aide SEPA qui dcide si un caractre transmis comme paramtre est l'un dessparateurs mentionns ci-dessus. SEPA restituera la valeur (logique) 1 si le caractre est unsparateur et 0 dans le cas contraire. SEPA utilise un tableau qui contient les sparateurs dtecter.

Exemple:

Nom du fichier texte : A:LITTERA.TXT

Votre fichier contient:

12 paragraphes

571 mots

4186 caractres

dont

279 fois la lettre a

56 fois la lettre b . . .

3 fois la lettre z

et 470 autres caractres


ALGORITHME DE TRIALGORITHME DE TRI

1- TRI A BULLESLe principe du tri bulles est de comparer deux valeurs adjacentes etd'inverser leur position si elles sont mal places (si un premier nombre xest plus grand qu'un deuxime nombre y et que l'on souhaite trierl'ensemble par ordre croissant, alors x et y sont mal placs et il faut lesinverser).

Si, au contraire, x est plus petit que y, alors on ne fait rien et l'on comparey z, l'lment suivant. C'est donc itratif.

Et on parcourt ainsi la liste jusqu' ce qu'on ait ralis n-1 passages (nreprsentant le nombre de valeurs trier) ou jusqu' ce qu'il n'y ait plusrien inverser lors du dernier passage.



82/85

07/12/2010

82


1- TRI A BULLESAu premier passage, le plus grand lment de la liste est plac au bout dutableau, au bon emplacement.

Pour le passage suivant, nous ne sommes donc plus obligs de faire unecomparaison avec le dernire lment ; et c'est bien plus avantageuxainsi. Donc chaque passage, le nombre de valeurs comparer diminuede 1.



1- TRI A BULLESImplmentation en C

void tri_bulles(int tab[], int taille){

int tab_en_ordre = 0;

while(!tab_en_ordre){

tab_en_ordre = 1;

for(int i=0 ; i < taille-1 ; i++){

if(tab[i] > tab[i+1]){

inverser(tab+i, tab+i+1);

tab_en_ordre = 0;

}

}

taille--;

}

}


void inverser(int *a, int *b){

int tmp;

tmp = *a;

*a = *b;

*b = tmp;

}


83/85

07/12/2010

83


1- TRI A BULLESAu premier passage, le plus grand lment de la liste est plac au bout dutableau, au bon emplacement.

Pour le passage suivant, nous ne sommes donc plus obligs de faire unecomparaison avec le dernire lment ; et c'est bien plus avantageuxainsi. Donc chaque passage, le nombre de valeurs comparer diminuede 1.



1- TRI PAR INSERTIONLe tri par insertion est un algorithme de tri classique dont le principeest trs simple.

C'est le tri que la plupart des personnes utilisent naturellement pour trierdes cartes : prendre les cartes mlanges une une sur la table, et formerune main en insrant chaque carte sa place.

Le tri par insertion est cependant considr comme le tri le plus efficacesur des entres de petite taille. Il est aussi trs rapide lorsque les donnessont dj presque tries.



84/85

07/12/2010

84


1- TRI PAR INSERTIONPrincipe

Dans l'algorithme, on parcourt le tableau trier du dbut la fin. Au moment oon considre le i-me lment, les lments qui le prcdent sont dj tris.

Pour faire l'analogie avec l'exemple du jeu de cartes, lorsqu'on est la i-me tapedu parcours, le i-me lment est la carte saisie, les lments prcdents sont lamain trie et les lments suivants correspondent aux cartes encore mlanges surla table.

L'objectif d'une tape est d'insrer le i-me lment sa place parmi ceux quiprcdent. Il faut pour cela trouver o l'lment doit tre insr en le comparantaux autres, puis dcaler les lments afin de pouvoir effectuer l'insertion. Enpratique, ces deux actions sont frquemment effectues en une passe, qui consiste faire remonter l'lment au fur et mesure jusqu' rencontrer un lmentplus petit.



1- TRI PAR INSERTIONImplmentation en C

void tri_insertion(int tab[], int taille){

int i, j, tmp;

for(i = 0; i < taille; i++){

tmp = tab[i];

j = i;

while(j>0 && tab[j-1]> tmp){

tab[j] = tab[j-1];

j--;

}

tab[j] = tmp; /*insertion*/

}

}



85/85

07/12/2010

EXERCICESEXERCICESExercice :

Aprs avoir construit une liste chaine de nombres entiers. Trier la liste laide des algorithmes de tri prsents


-- FINFIN --

Documents

Algorithmique et structures de données en C-07122010