Les adresses et les pointeurs

Les adresses

.

.

.

.

.

.

012

34

max

Les cases mémoires ont toutes un numéro qui les distingue lesune des autres: ce numéro est appelé adresse.

C’est par cette adresse que le processeur peut communiqueravec la mémoire.

Les adresses et les variablesLe nom que l’on donne au cases mémoires est traduit en une adresse juste avant l’exécution d’un programme. Cela est nécessaire afin que le processeur sache à quelle case mémoire est associée chaque variable.

En général il est impossible de prévoir à quelle adresse sera placée une variable. Le nom des variables est donc nécessaire.

.

.

.

.

.

.

1324

0c1: 1

2

c2: 34

max

char

char

c1 = c2;Lire le contenu de la case 3.Mettre ce qui a été lu dans la case 1.

Le partage de la mémoireSur les systèmes modernes, il peut y avoir plusieurs usagers se partageant la mémoire et chaque usager peut exécuter plusieurs programmes simultanément.

Cela signifie que l’on n’est pas libre d’utiliser toutes les cases mémoires comme on le veut. Une case peut être occupée par un programme à un certain moment et libre à un autre. Cette situation est aléatoire.

Pour cette raison, on ne mentionne jamais explicitement une adresse dans un programme même si cela est théoriquement possible.

Adresses valides et non valides

Exemple. Dans le pseudo-code suivant:

Lire le contenu de la case 3.Mettre ce qui a été lu dans la case 1.

Que se passe t-il si au moment de l’exécution la case mémoire 1 est déja utilisée par un autre programme.La case est alors non valide et il y aura erreur à l’exécution.

C’est pour cette raison que l’on utilise des variables.Avant l’exécution, une adresse valide est associée à chaque variable. Seul notre programme pourra utiliser ces cases mémoire.

Position des variables dans la mémoire

Sauf pour les tableaux, il n’y a aucune garantie que les variables occupent des cases adjacentes en mémoire.

Exemple.int a,b[4],c,d[3];

......

a

b[0]

b[1]

b[2]

b[3]

......

d[1]

d[2]

......

d[0]

c

int

int

int

int

intint

int

int

int

Les adresses et les types

Une des principales fonctions des types est d’indiquer le nombre d’octets utilisés par une variable.

Par exemple nous avons vu que:un caractère prend 1 octet (8 bits) un entier prend 4 octets (32 bits).

Cela signifie que si on divise la mémoire en case d’un octet alors: un char utilise 1 case un int utilise 4 cases adjacentes

.

.

.

n: 0 1

2

3

c2: 5

max

char

int00000000

00001101

00000000

00011100

00011011

.

.

.

.

.

.

00000000

c1: 4char

c1: 4

Remarque

.

.

.

n: 0

c2: 5

max

char

int00000000000000000000000000001101

00011100

00011011

.

.

.

.

.

.

char

int

On peut aussi voir la mémoire comme une suite de cases de taille variable.

Les adresses et les tableaux

Le nom d’un tableau correspond à l’adresse du début du tableau.

Exemple:

char tab[5];printf(“%p\n”, tab);

4027630992 printf(“%p\n”, tab+1);

4027630993printf(“%p\n”, tab+2);

4027630994

Note: ‘%p’ sert à afficher les pointeurs.

Les tableaux d’entiers

Exemple:

int tab[5];printf(“%p\n”, tab);

4027630976printf(“%p\n”, tab+1);

4027630980printf(“%p\n”, tab+2);

4027630984

Question: Pourquoi?

+4

+4

L’incrémentation d’une adresse

Incrémenter une adresse ne veux pas dire ajouter 1, cela veut dire aller à l’adresse suivant la variable courante.

En général cela n’a du sens que si on est dans un tableau.

......

a: 16216

b[0]: b=24600b[1]: b+1=24604

b[2]: b+2=24608

b[3]: b+3=24612

......

d[1]: d+1=54317

d[2]: d+2=54318

......

d[0]: d=54316

int

int

int

int

int

char

char

char

L’adresse a+1n’est pas valide

Remarque

Si Tab est un tableau alors

L’adresse de Tab[0] est Tab,l’adresse de Tab[1] est Tab + 1,l’adresse de Tab[2] est Tab + 2,etc.

Cela est vrai quelque soit le type des éléments de Tab.

L’opérateur &

Il est possible de connaître, pendant l’exécution d’un programme, l’adresse associée à une variable.

En C, cela est possible à l’aide de l’opérateur unaire &

Exemple:

char c;int n, tab[1000];

L’adresse de c est &cL’adresse de n est &nL’adresse de tab[3] est &tab[3]

L’opérateur *

Il est aussi possible de connaître, pendant l’exécution d’un programme, le contenu de la case mémoire située à une adresse donnée.

En C, cela est possible à l’aide de l’opérateur unaire *

Exemple:char c;int tab[1000];

• Le contenu de l’adresse tab + 25 est *(tab + 25)• *(tab + 25) est donc identique à tab[25]• *(&c) est identique à c• *c n’a aucun sens

Exemple

Les expressions logiques suivantes sont vraies:

• &n == 12556• *(12560) == 60• *(12560) < c2• *(&r) == 12.345

61

......

12.345

60

5000000

......

char

double

n: 12556 int

c1: 12560 char

r: 12562

c2: 12561

Résumé des opérations sur les adresses

On peut:

• Additionner une adresse et un entier• Déterminer l’adresse d’une variable• Déterminer le contenu d’une adresse

Mais, on ne peut pas

• Additionner deux adresses (mais on peut soustraire deux adresses d’un même tableau)

Les pointeurs

Un pointeur est une variable pouvant contenir une adresse.

Exemple:

int *pn; pointeur sur une valeur entièrechar *pc; pointeur sur un caractèredouble *pr; pointeur sur un réel

Les pointeurs: exemple

Exemple:

int *pn, m;

......

pn: 12556

m: 65710

int*

......

int

Les pointeurs: exemple

Exemple:

int *pn, m;

pn = &m;

65710

......

pn: 12556

m: 65710

int*

......

int

Les pointeurs: exemple

Exemple:

int *pn, m;

pn = &m;m = 6;

65710

......

6

pn: 12556

m: 65710

int*

......

int

Les pointeurs: exemple

Exemple:

int *pn, m;

pn = &m;m = 6;*pn = 38;

65710

......

38

pn: 12556

m: 65710

int*

......

int

Les pointeurs et les tableaux

En C les pointeurs sont intimement liés aux tableaux.

Exemple:int tab[10], *p;p=tab;

tab[3] = 70;*(tab + 3) = 70;p[3] = 70;*(p + 3) = 70;

tous équivalents:

RemarqueLe nom d’un tableau est une adresse constante et non pas un pointeur qui est une variable.

Exemple:int tab[10], *p;p=tab;

p = tab; /* Valide */tab = p; /* Non valide */

tab:

0 1 2 3 4 5 6 7 8 9 10

p:

Quelques utilités des pointeurs

• Pour implanter le passage de paramètres par référence

• Pour implanter le passage de tableaux en paramètre

• Pour utiliser des indices négatifs au tableaux

• Fondamental en structure de données

Les pointeurs comme paramètres

void echanger( int &x, int &y){ int tmp;

tmp = x; x = y; y = tmp;}

En C++: echanger(a, b)

Les pointeurs comme paramètres

void echanger( int *x, int *y){ int tmp;

tmp = *x; *x = *y; *y = tmp;}

En C: echanger(&a, &b)

Les tableaux passés en paramètre

Une des plus importantes utilisation des pointeurs réside dans le passage des tableaux en paramètre.

Lorsque l’on passe le nom d’un tableau en paramètre, on passe une adresse.

La fonction appelée reçoit donc une adresse qu’elle met dans une variable: cette variable doit donc être un pointeur.

Les tableaux passés en paramètre

void liretab(int tab[] , int max) { int c; int i=0;

while ((c=getchar()) != EOF){ tab[i] = c; i = i + 1; } }

Les tableaux passés en paramètre

void liretab(int *tab, int max) { int c; int i=0;

while ((c=getchar()) != EOF){ *(tab+i) = c; i = i + 1; } }

Les indices de tableauxExemple 1

Tableau d’entiers dont les indices vont de -5 à 5:int tab[11];int *ptab;ptab = tab + 5;

ptab[0] est identique à tab[5]ptab[-5] est identique à tab[0]ptab[5] est identique à tab[10]

tab:

0 1 2 3 4 5 6 7 8 9 10

ptab:

Les indices de tableauxExemple 2

Tableau d’entiers dont les indices vont de ‘A’ à ‘Z’:int tab[26];int *ptab;ptab = tab - ‘A’; /* A vaut 65 en ASCII */

ptab[‘A’] est identique à tab[0]ptab[‘Z’] est identique à tab[25]

tab:

0 1 2 3 4 21 22 23 24 25

ptab:

-65

Allocation statique et dynamique

Jusqu’à maintenant, toutes la mémoire que nous avons utilisée dans nos programmes devait avoir été allouée avantl'exécution à l’aide des déclarations de variables.

Il est parfois utile d’allouer une partie de l’espace mémoireen cours d’exécution.

Exemple 1

Par exemple, si on a besoin de mémoriser un certain nombre d’objets mais que ce nombre n’est pas connu avant l’exécution du programme.

Il faut alors allouer suffisamment d’espace au cas où le nombre d’objets est grand.

Si le nombre d’objets est petit, on gaspille inutilement de l’espace mémoire.

Le fichier d’entête stdlib.h

Le fichier d’entête stdlib.h contient des déclarations de fonctions traitant, entre autres, de l’allocation de la mémoire:

- malloc- free- calloc- realloc

(void *)malloc(size_t size)

size_t est un type d’entiers positifs.

malloc retourne un pointeur sur un espace mémoire réservé à un objet de taille size, ou bien NULL si cette demande ne peut être satisfaite. La mémoire allouée n’est pas initialisée.

Bien entendu, quand on travaille avec des pointeurs en C, ces derniers possédent chacun un type. Par conséquent, le type de données (void *) retourné par malloc doit toujours être mis dans le type de donnée avec lequel nous voulons travailler..

Exemple 2

int *p;

*p = 10; /* INVALIDE puisque p ne pointe sur *//* aucune case mémoire valide */

p = (int*) malloc(sizeof(int))

*p = 10; /* VALIDE */

p:

p:

Avant malloc

Après malloc

Exemple 2

int *p;

*p = 10; /* INVALIDE puisque p ne pointe sur *//* aucune case mémoire valide */

p = (int) malloc(sizeof(int))

*p = 10; /* VALIDE */

p:

p:

Avant malloc

Après malloc

Pourquoi?

Pointeurs sur void

La fonction malloc ne sait pas à quoi servira l’espace mémoire qui lui est demandé.

Elle ne sait pas quel type d’objet utilisera cet espace.

Alors, elle retourne un pointeur générique qui peut être converti en n’importe quel type de pointeur: un pointeur sur void

Conversion implicite

En C, certaines conversions de type sont implicites:

double x;int n;char c;

n = c; /* un char est converti en un int */c = n; /* un int est converti en un char */x = n; /* un int est converti en un double */n = x; /* un double est converti en un int */

Conversion explicite

Dans toute expression, on peut forcer explicitementdes conversions de types grâce à un opérateur unaire appelé cast.

Dans la construction(nom de type) expression

l’expression est convertie dans le type précisé (selon certaines règles).

Exemple 3

printf(“%d”, pow(2,3)); /* mauvaise façon */

printf(“%d”, (int) pow(2,3)); /* bonne façon */

int *p;struct complexe *cplx;p = (int *) malloc(sizeof(int));cplx = (struct complexe *) malloc(sizeof(struct complexe));

void free(void * p)

free libère l’espace mémoire pointé par p; elle ne fait rien si p vaut NULL.

p doit être un pointeur sur un espace mémoire alloué par malloc, calloc ou realloc.

void *calloc(size_t nobj, size_t size)

calloc retourne un pointeur sur un espace mémoire réservé à un tableau de nobj objets, tous de taille size, ou bien NULL si cette demande ne peut pas être satisfaite.

La mémoire allouée est initialisée par des zéros.

void *realloc(void *p, size_t size)

realloc change en size la taille de l’objet pointé par p.

Si la nouvelle taille est plus petite que l’ancienne, seul le début du contenu de l’objet est conservé.

Si la nouvelle taille est plus grande, le contenu de l’objet est conservé, et l’espace mémoire supplémentaire n’est pas initialisé.

realloc retourne un pointeur sur un nouvel espace mémoire, ou bien NULL si cette demande ne peut pas être satisfaite, auquel cas *p n’est pas modifié.

Exemple 4On veut lire des entiers et les mettre en mémoire.

Plutôt que de créer un tableau avant l’exécution, on utilisecalloc pendant l’exécution.

int *p, n;scanf(“%d”, &n);p = (int *) calloc(n, sizeof(int));

si plus tard cet espace n’est plus suffisant, alors on utilise:

p = (int *) realloc(p, 2*n);

p: …

Exemple 5Liste chaînée

struct noeud{ int valeur; noeud *suivant;};

struct noeud *chaine, *p;

chaine:

p:

Exemple 5

chaine = (struct noeud) malloc(sizeof(struct noeud));

chaine:

p:

valeur suivant

Exemple 5

chaine = (struct noeud) malloc(sizeof(struct noeud));chaine -> valeur = 8;

chaine: 8

p:

Exemple 5

chaine -> suivant = (struct noeud) malloc(sizeof(struct noeud));

chaine: 8

p:

Exemple 5

p = chaine -> suivant;

chaine: 8

p:

Exemple 5

p -> valeur = 5;

chaine: 8 5

p:

Exemple 5

p -> suivant = (struct noeud) malloc(sizeof(struct noeud));

chaine: 8 5

p:

Exemple 5

p = p -> suivant;

chaine: 8 5

p:

Exemple 5

p -> valeur = 13;p -> suivant = NULL;

chaine: 8 5

p:

13 0

• Nous venons ainsi de créer une liste de valeurs qui sont liées entre elles par des pointeurs. Autrement dit, ces valeurs en mémoire peuvent être dans des endroits non contigues. Pou accéder ces valeurs, il suffit d’avoir l’adresse de la première valeur qui est dans le pointeur chaine.

Impression des valeurs d’un chaine

• Soit une liste chainée en mémoire centrale, dont le premier élément est à l’adresse chaine.

• Question: Imprimer toutes les valeurs constiuant cette liste.

Exemple 6

p = chaine;while (p != NULL){ printf(“%d\n”, p->valeur); p = p->suivant; }

chaine: 8 5

p:

13 0

Exemple 6

• La solution précédente consiste à mettre l’adresse du premier élément dans le pointeur p. La valeur p->valeur est alors affichée; pour aller à l’élément suivant, il suffit d’avoir son adresse qui est dans

p->suivant. Ce processus est répété jusqu’à atteindre l fin de la chaine qui est donnée par le pointeur NULL.

Suppression d’un élément dans une liste chainée

• Soit une liste chainée en mémoire centrale, dont le premier élément est à l’adresse chaine.

• Question: Supprimer l’élément de valeur X s’il existe.

• Solution: Dans un premier temps, nous devons rehercher cette valeur dans la liste. Si elle n’existe pas, alors il n’y a rien à faire.

• Maintenant, si elle existe. Nous devons avoir l’adresse de son emplacement en mémoire (supposons que cette adresse soit donnée par p), et ensuite distinguer les deux cas suivants :

chaine: 8 5 13 0

PQ

chaine: 8 5 13 0

P

Q->Suivant = P->suivantfree(P)

Chaine = chaine->suivantFree(P)

L’élément à supprimer n’est pas le premier de la liste

L’élément à supprimer est le le premier de la liste

• Si cette valeur est en première position de la liste. Dans ce cas, en la supprimant, le début de cette liste va changer. Autrement dit, c’est le deuxième élément qui va devenir le premier élément. Ceci s’exprime par l’instruction suivante:

chaine = p->suivant ou alors par chaine = chaine->suivant

• Maintenant, si cette valeur n’est pas le premier élément, alors on doit mettre dans l’élément précédent cette valeur l’adresse de l’élément suivant cette valeur. Si Q est l’adresse de l’élément qui précéde cette valeur, alors cette idée est exprimée comme suit:

• Q->suivant = p->suivant• Ensuite, on supprime physiquement de la liste

l’emplacement de cette valeur pour la rendre disponible pour d’eventuels appels d’allocation mémoire ultérieurs. Ceci est fait par

• free(p)

L’algorithme est alors comme suit:

• p = chaine; trouve = 0• while ((p != NULL) && (!trouve))• if (p->valeur = x)• trouve =1;• else { • q = p; /* sauvegarde l’adresse actuelle • avant d’aller à l’élément suivant • p = p->suivant;• }• If (trouve) /* l’élément existe*/ {• if (p == chaine) /* cet élément est le premier de la liste• chaine = p->suivant;• else q->suivant = p->suivant;• free(p);• }• else printf(“élément inexistant”); •

Ajout un élément X dans une liste chaînée

• L’insertion d’un élément peut se faire de deux manières:

• 1. Après un élément donné de valeur V

• 2. Avant un élément donné de valeur V

1. Après un élément de valeur V:

La solution consiste dans un premier temps à chercher si cet élément de valeur V existe dans la liste. Si cet élément n’existe pas, il n’y a rien à faire. Sinon, on procède comme suit:

- soit P l’adresse de cet élément

- allouer un espace mémoire pour ce nouvel élément à l’aide de la fonction malloc; soit Q l’adresse de cet espace mémoire

- après insertion, l’élément X sera entre l’élément de valeur V et le suivant de V. Autrment dit, le suivant de V sera maintenant le nouvel élément X; et le suivant de X sera le suivant de V de tantôt. En termes algoritmiques, on exprime cette idée comme suit:

• Q.suivant = P->suivant (mettre comme suivant de X le suivant de V

• P.suivant = Q (mettre comme suivant de V l’élément X

chaine: 8 V 13 0

P X

Q

L’algorithme est alors comme suit:

• p = chaine; trouve = 0

• while ((p != NULL) && (!trouve))

• if (p->valeur = V)

• trouve =1;

• else p = p->suivant;

• If (trouve) /* l’élément existe */

• {• Q = (struct noeud) malloc(sizeof (struct noeud));/* alloue une addresse mémoire

• Q->valeur = X; /* y mettre la valeur X */

• Q-> suivant = p->suivant;

• P->suivant = Q;

• }

• else printf(‘élément inexistant’);

•

2. Insertion avant un élément de valeur V: La solution consiste dans un premier temps à chercher si cet élément

de valeur V existe dans la liste. Si cet élément n’existe pas, il n’y a rien à faire. Sinon, on procède comme suit:

- soit P l’adresse de cet élément - allouer un espace mémoire pour ce nouvel élément à l’aide de la

fonction malloc; soit Q l’adresse de cet espace mémoire. - après insertion, l’élément X sera entre l’élément de valeur V et le

l’élément précédent de V. Autrment dit, le précédent de V aura pour élément suivant l’élément X et le précédent de V sera maintenant le nouvel élément X. Pour effectuer ces opérations, on aura besoin de l’adresse de l’élément précédent de V. Soit preced cette adresse. Notons que si V est le premier élément, alors après insertion de X, ce sera X qui sera le nouveau premier élément de la liste.

En termes algoritmiques, on exprime cette idée comme suit:

• Si p == chaine (signifie que V est le premier élément de la liste)

l’insertion va se faire comme suit:

Q->suivant = chaine (le suivant de X est V)

chaine = Q (X devient le premier élément de la liste chaînée)

• Sinon (V n’est pas le premier élément de la liste)

precedent->suivant = Q (le suivant du précédent de V est X)

Q->suivant = p (le suivant de X est V)

L’algorithme est alors comme suit:

• p = chaine; /* initialiser p au début de la liste */• trouve = 0• while ((p != NULL) && (!trouve))• if (p->valeur = x)• trouve =1; /* élément trouvé */• else { preced = p;• p = p->suivant; • }• If (trouve) /* l’élément existe• {• Q = (struct noeud) malloc(sizeof (struct noeud));/* alloue une addresse mémoire • Q->valeur = X; • if (chaine == p) /* élément V est en première position de la liste*/ {• Q->suivant = chaine; /* (le suivant de X est V) */ chaine = Q; /* (X devient le premier élément de la liste chaînée)*/ }• else {• Q->valeur = X; /* mettre la valeur X dans la case mémoire référencée par Q */• preced-> suivant = Q; /* mettre le suivant du précédent de V l’élément X */• Q->suivant = p; /* mettre le précédent de V lélément X */• } • }

chaine: 8 V 13 0

Ppreced

chaine: V 5 13 0

P Q->suivant = chaineChaine = Q

L’élément V n’est pas le le premier de la listePrecedent->suivant = QQ->suivant = P

L’élément V est le le premier de la liste

X

Q

X

Q

Avantages des pointeurs sur les tableaux

• La suppression et l’ajout d’un élément se font sans déplacer les autres éléments comme dans les tableaux

• Le nombre d’éléments n’a pas besoin d’être connu à l’avance.

• La longeur de la liste n’est pas figée (peut augmenter ou diminuer)

• Mais, demande plus d’espace mémoire que le tableaux.

Listes doublement chainées

• Une liste est dite doublement chainée si chaque élément contient l’adresse de l’élément suivant et celle de l’élément précédent.

chaine: Null

• La déclaration de cette structure de données est comme suit:

Liste doublement chaînée

typedef struct listelement{ int valeur; struct listelement *suivant; struct listelement *preced;} noeud;

noeud *chaine, *p;

Création de la listetypedef fin -1;noeud *creation(void){ /* construit la liste d’entiers jusqu’à lecture de fin int donnee; noeud *nouveaupoint, *debut, *derriere; /* construit le premier élément, sil y en a un */ scanf(‘’%d’’,&donnee); if (data==fin) debut = NULL; else { debut = (noeud *) malloc(sizeof (noeud)); debut-> valeur= donnee; debut->suivant = NULL; debut->preced = NULL; derriere = debut; /* continuer la création */ for (scanf (“%d”, &donnee); donnee != fin; scanf (“%d”, &donnee)) { nouveaupoint = (noeud *) malloc(sizeof (noeud)); /* alloue de la mémoire */ nouveaupoint->valeur = donnee; /* remlissage de la mémoire*/ nouveaupoint->suivant = NULL; /* cet élément ne pointe vers aucun autre élément*/ nouveaupoint->preced = derriere; /*l’adresse du précédent est mise dans ce pointeur*/ derriere = nouveaupoint; /*sauvegarde de l’adresse de cet élément } return (debut) /* retourne l’adresse du premeir élément */ }

Impression de la liste

void impression (noeud *debut)

{

noeud *pointeur;

pointeur = debut;

while (pointeur != NULL)

{

printf(“%d\n”, pointeur->valeur);

pointeur = pointeur->suivant;

}

Ajout d’une valeur avant une autrevoid ajouteravant(noeud *debut, int valeur, int data){ /* ajouter d’un élément valeur avant l’élément data s’il existe */ noeud *pointeur, *debut, *nouveau, *avant;pointeur = debut; trouve = 0;while ((nouveaupoint !=NULL) && (!trouve)) if pointeur->valeur = data trouve = 1; else pointeur = pointeur->suivant; /* aller à l’élément suivant*/ if (trouve) /* élément existe */ { nouveaupoint = (noeud *) malloc(sizeof (noeud)); /* alloue de la mémoire pour le nouvel élément*/ nouveaupoint->valeur = valeur; /* tester maintenant si l’élément est le premier de la liste if (pointeur == debut) { nouveaupoint->suivant = debut; nouveaupoint->preced = NULL; debut = nouveaupoint; } else { avant = pointeur->preced; nouveaupoint->suivant = pointeur; nouveaupoint->preced = avant; avant->suivant = nouveaupoint; pointeur->preced = nouveaupoint; } } } /* fin de la fonction */

Ajout d’une valeur après une autrevoid ajouterapres(noeud *debut, int valeur, int data){ /* ajouter l’élément valeur avant l’élément data s’il existe */ noeud *pointeur, *debut, *nouveaupoint, *apres;

pointeur = debut; trouve = 0; while ((pointeur !=NULL) && (!trouve)) if pointeur->valeur = data trouve = 1; else pointeur = pointeur->suivant; /* aller à l’élément suivant*/ if (trouve) /* élément existe */ { nouveaupoint = (noeud *) malloc(sizeof (noeud)); /* alloue de la mémoire pour le nouvel élément*/

nouveaupoint->valeur = valeur; apres = pointeur->suivant; nouveaupoint->suivant = apres; nouveaupoint->preced = pointeur; apres->preced = nouveaupoint; pointeur->suivant = nouveaupoint; }} /* fin de la fonction */

Suppression d’une valeur

void suppression (noeud *debut, int data){ /* supprimer l’élément data s’il existe */

noeud *pointeur, *debut, *avant, *apres;

pointeur = debut; trouve = 0; while ((nouveaupoint !=NULL) && (!trouve)) if pointeur->valeur = data trouve = 1; else pointeur = pointeur->suivant; /* aller à l’élément suivant*/ if (trouve) /* élément existe */ { /* tester si cet élément est premier dans la liste */ avant = pointeur->preced; apres = pointeur->suivant; if (debut == pointeur){ apres->preced = NULL; debut = apres; } else { avant->suivant = apres; apres->preced = avant; }} /* fin de la fonction */

Récursivité dans les listes chaînées

• Reprenons les liste chainées et essayons de donner des versions récursives.

Création d’une liste

#include <stdlib.h> /* donne accès à malloc */typedef fin -1;noeud *creation(void){ /* construit la liste d’entiers jusqu’à lecture de fin int donnee; noeud *ansp; /* construit le premier élément, sil y en a un */ scanf(‘’%d’’,&donnee); if (data==fin) debut = NULL; else { debut = (noeud *) malloc(sizeof (noeud)); debut-> valeur= donnee; debut ->suivant = creation (); /* faire la même chose que précédemement*/ } return (debut) /* retourne l’adresse du premier élément */ }

Rechercher un élément

/* cette fonction recherche un élément dans une liste */

noeud *recherche (noeud *debut, int data){

noeud *pointeur;

pointeur = debut;

if pointeur->valeur = data

return (pointeur);

else pointeur = recherche(pointeur->suivant, data);

return(NULL);

}

Les arbres

Définition: Un arbre binaire est un ensemble de noeuds qui est, soit vide, soit composé d’une racine et de deux arbres binaires disjoints, appelés sous-arbre droit et sous-arbre gauche.

1

2 5

Définition: Un arbre binaire est dit de recherche (binary search tree) si, pour chaque noeud V, tous les éléments qui aont dans sous arbre gauche de V ont des valeurs inférieures à celle de V, et tous les éléments du sous-arbres droit de V sont supérieurs à celle de V.

Exemple: 8

6

4 7

10

15

13

• Remarqez que pour une suite de nombres, il existe différentes arbres binaires de recherche correspondant à cette liste. Tout dépend de la manièe dont sont présentés ces nombres.

• La déclaration de cette structure de données est comme suit:

Arbre binaire

typedef struct listelement{ int valeur; struct listelement *droit; strcut listelement *gauche;} noeud;

noeud *racine, *p;

Création de l’arbre

• La fonction de création consiste à lire les données destinées à êre introduites dans les noeuds de l’arbre.

• La création de l’arbre revient à insérer, à tour de rôle, des éléments dans l’arbre existant, en partant d’uin arbre vide.

EXEMPLE• SUPPOSONS QUE LA SUITE DE NOMBRES SUIVANTS EST INTRODUITE DANS CET

ORDRE:

• 4 5 0 28 45 7

• L’ARBRE DE RECHERCHE OBTENU EST COMME SUIT:

Version non récursive

noeud *inserer(noeud *racine, int data){ noeud *p, *q; if (racine == NULL){/* arbre vide*/ racine = (noeud *) malloc(sizeof (noeud)); racine->valeur = data; racine->droit = NULLl; racine->gauche = NULL; return(racine); } p = racine; while (p != NULL){ /* trouver l’emplacement pour l’insertion */ q = p; /* sauvegarder le parent avant d’aller vers les enfants */ if (data < p->valeur) p = p->gauche; /* aller vers les enfants de gauche */ else p = p ->droit; /* aller les enfants de droite */ } p = (noeud *) malloc(sizeof (noeud)); p ->valeur = data; if (data < q->valeur) q->gauche = p; /* relier le parent référencé par q au nouvel élément comme enfant gauche */ else q->droite = p; /* relier le parent référencé par q au nouvel élément comme enfant droit */ return(p);}

noeud *inserer(noeud *racine, int data) { noeud *p, *q; if (racine == NULL){ racine = debut = (noeud *) malloc(sizeof (noeud));/* allouer de l’espace et mettre

l’adresse dans racine racine->valeur = new; racine->gauche = NULL; racine->droit = NULL; } else if data < racine->valeur inserer(racine->gauche, data); else inserer(racine->droit, data);

return(racine);

}

Version récursive

typede fin = -999;noeud *creation(noeud *racine){ *racine = NULL; for (scanf (“%d”, &donnee); donnee != fin; scanf

(“%d”, &donnee)) inserer(racine, donnee); return (racine) /* retourne l’adresse du premier

élément */ }

Recherche d’un élément dans un arbre binaire de recherche

Parce que l’arbre possède la propriété d’un arbre de recherche, la manière d’y rechercher un élément est comem suit:

1. commencer à la racine

2. si la valeur de ce noeud est l’élément recherché, stop

3. si la valeur du noeud courant est plus grande que la valeur recherchée, alors continuer la recherche dans la partie gauche de l’arbre.

4. si la valeur du noeud courant est plus petite que la valeur recherchée, alors continuer la recherche dans la partie droite de l’arbre.

Cela nous consuit à l’algorithme suivant

noeud * rechercher (noeud * racine, int data){ noeud *p; int trouve; p = racine; trouve = 0 while (( p != NULL) && (!trouve)) if (p->valeur == data) trouve =1; else if (p->gauche > data) p = p->gauche; else p = p->droit;

if (trouve) printf(‘élément trouvé’); else printf(élément inexistant’); return(p)}

La version récursive est comme suit:

noeud * rechercher (noeud * racine, int data){ if (racine == NULL) p = NULL; else if (racine->valeur == data) p = racine; else if (racine->valeur > data) p = recherche(racine->gauche,data); else p = recherche(racine->droit,data); if (p ==NULL) printf(‘élément inexistant ‘); else printf(‘élément existe’); return(p);

}

Suppression d’un élément dans un arbre binaire de recherche

Cette opération doit être telle que l’arbre qui va en résulter doit toujours rester un arbre binaire de recherche.

Cette opération est un peu plus complexe et plus longue que celle de l’insertion bien qu’elle ne consiste qu’en quelques miouvements de pointeurs

On peut penser que la suppression d’un élément consiste à le trouver, puis à relier la structure sous-jacente à celle qui subsiste.

La structure de la fonction supprimer semble similaire à celle de la fonction rechercher.

Elle l’est effectivement, mais dans le cas où l’élément à supprimer est trouvé, il convient de dsitinguer plusiers cas de figures:

CAS 1: on enl`ve un élément situé à la racine illustré par la figure suivante:

B

A C

Élément àsupprimer

D’après la fonction de création, tous les éléments de C sont plus grands que ceux de A.

Premier cas particulier: celui où C est vide. Dans ce cas, A devient la racine.

Dans la cas contraire, on al choix entre A et C, pour la racine.

Choisit-on A? L’élément le plus grand de A est alors inférieur à l’élément le plus petit de B.

Il faut donc rechercher l’élément le plus grand de A, en parcourant ses branches de droite jusqu’à ce qu’on atteigne une feuille de l’arbre, puis remplacer le pointeur de droite de cet éléemnt par l’ancien pointeur droit, qui pointait aupravent vers B.

• racine = ancien pointeur gauche de B

A

Ancien pointeur droit de B

C

• racine = ancien pointeur droit de B

C

Ancien pointeur gacuhe de B

A

Avec C comme racine, nous aurions:

• CAS 2: C’est le cas où l’élément enlevé n’est pas la racine de l’arbre.dans ce cas, il faut alors anticiper la recherche de cet élément pour pouvoir raccrocher les pointeurs de la structure sous-jacente à ceux de la structure sus-jacente à l’élément concerné.

• Soit par exemple, la suppression de B dans la structure suivante:

D

B

A C

On a: A < B < C < D

Si on supprime B, on a donc:

A < C < D

Élément à supprimer

• Ceci implique, soit une structure du type suivant, qui réalise un chagement de racine et une rotation de toute la structure à droite:

C

A D

• Soit une structure de cet autre type, où la structure sus-jacente n’est pas modifiée:

D

C

A

• Dans le cas où C, on a simplement

D

A

• Nous retiendrons, et programmerons, la deuxième solution.

• L’ancien pointeur droit de B devient le pointeur gauche de D. Tandis que le pointeur de l’élément le plus à gauche de C est maintenant égal à l’ancien pointeur gauche de B.

• Le cas où C est vide est traité par le simple remplacement de l’ancien pointeur gauche de D par l’ancien pointeur gauche de B.

• CAS 3.• Ce cas est symétrique au précédent. Soit une structure

du type:

D

F

E G

Élément à supprimer

• Dans ce cas, nous avons:

D < E < F < G

Si on supprime F, on a:

D < E < G

Ce qui donne deux possibilités :

E

D G

Ou bien:

D

E

G

• Le raisonnement est tout à fait similaire, et symétrique, à celui qui a été vu à gauche.

• Nous obtenons alors la fonction récursive suivante:

noeud * supprimer(noeud racine, int data){

noeud *PG, *PT, *POINTD;

if (racine == NULL)

printf(‘mot inexistant’);

else

if (racine->valeur == data){/* supprimer la racine*/

PT = racine->droite;

if (PT != NULL){

while(PT != NULL){

PG = PT;

PT = PT->gauche; /* aller chercher le plus petitélément de la partie droite */

}

PG->gauche =racine->gauche;

racine = racine->droite;

} /* fin du if

else

racine = racine ->gauche;

else /*de racine-> != data */

{

if (data == racine->gauche->valeur) {

printf(‘élément trouvé à gauche);

PT = racine->gauche->droite;

if (PT != NULL){

while (PT!= NULL){

PG = PT;

PT = PT->gauche;

}

PG->gauche = racine->gauche->gauche;

racine->gauche = racine->gauche->droite;

} */fin du if */

else racine ->gauche = racine ->gauche->gauche;

}

else /* data != racine->gauche->valeur */

If (data == racine ->droite->valeur){

printf(‘élément trouvé à droite’);

PT = racine->droite->gauche;

If (PT != NULL){

while (PT != NULL){

POINTD = PT;

PT = PT->droite;

}

POINTD->droite = racine->droite->droite;

racine->droite racine ->droite->gauche;

}

else racine ->droite = racine ->droite->droite;

}

else /* data != racine->droite->valeur */

if (data < racine->valeur)

supprimer(racine->gauche,data)

else

supprimer(racine->droite,data)

}

Parcours dans un arbre

• Il existe différentes manière de parcourir un arbre:

Parcours postfix

Parcours infix

Parcours prefix

Exemple

• Dans la parcours postfix, pour un noeud donné, il est visité aprés les noeuds de sa partie gauche et de sa partie droite.

• Dans le parcours infix; la partie gauche d’un noeud est visité, ensuite le noeud lui-même, et enfin sa partie droite.

• Dans le parcours, le noeud en question est visité, ensuite sa partie gauche et enfin sa partie droite.

Exemple21

12 23

8 15 27

69

20

14

Le parcours en postfixe

6 9 8 14 15 12 20 27 23 21

Le parcours en infixe

6 8 9 12 14 15 20 21 23 27

Le parcours en prefixe

21 12 8 6 9 15 14 23 20 27

void postfixe(noeud *racine){ if (racine != NULL){ postfixe(racine->gauche); postfixe(racine ->droite); printf(‘%d’,racine->valeur); }}

void infixe(noeud *racine){ if (racine != NULL){ infixe(racine->gauche); printf(‘%d’,racine->valeur); postfixe(racine ->droite); }}

void prefixe(noeud *racine){

if (racine != NULL){

printf(‘%d’,racine->valeur);

prefixe(racine->gauche);

prefixe(racine ->droite);

}

}

Les arbres (suite)

• Soit l’arbre suivant:

N

........

T1 T2 T3Tk

• Le parcours en prefixe des noeuds de cet arbre est la racine n suivie des neouds de T1 en prefixe, puis ceux de T2, T3, ... Et Tk en prefixe

• Le parcours en infixe des noeuds de cet arbre est lesnoeuds de T1 en infixe, suivi de la racine n, suivies des noeuds de T2, T3, ... et Tk en infixe

• Le parcours en postfixe des noeuds de cet arbre est les noeuds de T1, puis de T2, T3, ... et Tk en postfixe, ensuite la racine n

Le parcours en postfixe se fait comme suit:

• Prefixe(V)

• Pour chaque enfant C de V, de gauche à droite, faire prefixe(C);

• Visiter C;

• Le parcours en infixe se fait comme suit:

Infixe(V) if V est une feuille visiter V;else{ infixe(enfent gauche de V) visiter V pour chaque enfant C de V, de gauche à droire, excepté le plus à gauche, faire infixe(C) }

• Le parcours en postfixe est comme suit:

• Pour chaque enfant C de V, de gauche à droite, faire postfixe(C);

• Visiter C;

Exemple

1

2

5

10 11 12

6

3 4

7 8 9

13 14

• En prefixe, le parcours de cet arbre est comme suit:

• En postfixe, le parcours de cet arbre est comme suit:

• En infixe, le parcours de cet arbre est comme suit:

Implantation des arbres dans le cas général

Comme le nombre de descendants varie d’un noeud à un autre, la déclaration d’un noeud se fera comme suit:

Chaque noeud comprendra: 1. la valeur de ce noeud 2. un pointeur vers le descendant le plus à

gauche 3. un pointeur vers le frère/soeur (de même

niveau) de droite.

• typedef struct listelement{

• int valeur;

• struct listelement *freredroit;

• strcut listelement *enfantgauche;

• } noeud;

• noeud *racine, *p;

• Si par exemple, les fonctions suivantes existaient déjà:

• noeud *enfant_gauche(noeud *n) retournant l’adresse du descendant le plus à gauche de n

• noeud *frere_droit(noeud *n) retournant l’adresse du frère droit de n, alors la fonction prefixe peut être comme suit:

• void prefixe(noeud *racine){• noeud *C;• prinf(‘%d’,racine->valeur);• C = enfant_gauche(racine)• while (C != NULL){• prefixe(C)• C = frere_droit(C);• } /* fin de la fonction */