Structures de données dynamiques

 

Les variables statiques:

Pour réserver de la mémoire dans nos programmes, nous devions jusqu'à présent déclarer des variables.

Ces variables pouvaient être globales ou locales.

Lorsqu'elles sont globales, la mémoire est allouée (réservée) au  début du programme et est libérée lorsque le programme se termine.

Lorsque les variables sont locales à une procédure ou fonction, la mémoire est allouée au début de la procédure ou fonction et la mémoire est libérée à la fin de celle-ci.

 

L'allocation dynamique de la mémoire va nous permettre de réserver de la mémoire pour une variable quand on le désire et de la libérer quand on le souhaite.

Il y aura donc gestion plus fine de la mémoire et donc moins de gaspillage (plus besoin de surdimensionner des tableaux).

 

La Pile ou la mémoire vive:

Chaque programme réserve une partie de la mémoire vive pour son usage personnel:

Le stockage des variables globales se fait dans le tas et le stockage des variables locales se fait dans la pile.

Cette quantité de mémoire réservée pour le programme peut être modifiée.

 

 Sous bc++ builder elle se paramètre comme ceci:

Projet  option  lieur  pile  taille minimale & taille maximale

Question: Notez ici les tailles de piles maximales et minimale de votre projet.

 

Plus vous avez besoin de mémoire plus la taille maximale de la pile doit être élevée.

 

Faisons abstraction de la notion de mot mémoire.

La mémoire est constituée de cellules d'un octet chacune. Chaque cellule a une adresse. (son numéro).

Les variables locales sont stockées dans la pile. Chaque variable a une adresse: l'adresse de la première cellule qui lui est réservée.

Prenons par exemple une variable de type réel "prix" Admettons que le réel est stocké sur 8 octets .Son adresse sera l'adresse de la première cellule qui lui est réservée. "6825300".

6825308

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6825300

 

6825299

 

En jaune, vous voyez l'ensemble de la zone mémoire réservée et en rouge l'adresse de notre variable.

Une variable déclarée ensuite aura comme adresse: 6825308 l'adresse de la première cellule libre de la pile.

Remarque alors que les variables globales sont stockées en montant du bas du tas vers le haut du tas. Les variables locales sont elles stockées depuis le sommet de la pile vers le milieu.

 

Exercice sous c++ Builder:

Déclarez dans une fonction deux variables locales de type "int".

Faire afficher les adresses des deux variables.

 

On utilisera l’opérateur & nom de variable qui fournit l'adresse de la variable dont le nom suit l’opérateur

 

Calculer la différence entre les deux adresses qu'en déduit-on sur la taille réservée pour un entier?

Faire la même chose avec 2 variables globales.

 

#pragma hdrstop

#include <condefs.h>

#include <conio.h>

#include <stdio.h>

 

 

//---------------------------------------------------------------------------

#pragma argsused

int nb1,nb2;

int main(int argc, char **argv)

{

        int nb4,nb5;

        printf("nb1 commence en %d et nb2 commence en %d\n",&nb1,&nb2);

        printf("nb4 commence en %d et nb5 commence en %d\n",&nb4,&nb5);

        getch();

        return 0;

}

 

Faire de même pour deux variables de type "float"  sur combien d'octets tient un float ?

 

puis deux clients du type TClient où :

struct TEnrClient {

char nom[25];

char prenom[10];

               }

 

 

Notion de pointeur:

Pour allouer dynamiquement de la mémoire au fur et à mesure des besoins, réserver des zones dans la pile, nous avons besoin de la notion de  pointeur.

 

Qu'est-ce que c'est ?

Un pointeur est une variable donc il faut le déclarer.

Un pointeur pointe sur quelque chose ou sur rien.

Lorsqu'un pointeur pointe sur rien il est égal à NULL.

La valeur d'un pointeur est l'adresse de début  de la zone mémoire sur laquelle il pointe.

 

Un pointeur est une variable:

Et oui, tout pointeur doit être déclaré.

Void * monpointeur ;  ici on ne sait pas sur quel type de donnée il pointe.

Int * Monpointeur;                   se lit "pointeur sur entier"

Struct TenrClient *Monpointeur;                   se lit pointeur sur TEnrClient.(type structuré)

 

Exercice:

Void essai(void)

{

Int monentier,resultat;

            Int *  monpointeur;

monentier=4;

                  monpointeur=&monentier; //on fait pointer monpointeur sur la zone réservée à

monentier

      if (*monpointeur ==4)

      { // se lit si la zone référencée par monpointeur est égale à 4 …

            printf( '’j’ai bien l'’impression qu’il pointe sur monentier'’);

            *monpointeur =8; la zone référencée par monpointeur reçoit 8

            resultat= monentier;

       }

}

Question indiquez la valeur de résultat après exécution de ce code

 

Faites afficher l'adresse de monentier et faites afficher monpointeur.

 

Qu'a-t-on appris:

Monpointeur est en fait l'adresse de début de la variable qu'il référence.

Afficher(*Monpointeur) affiche le contenu de la zone mémoire dont l'adresse est Monpointeur.

*Monpointeur <-25; écrit 25 dans la zone mémoire référencée par Monpointeur.

 

 

La déclaration d'un pointeur:

Déclaration simple:

   Int * P_val_min, P_val_max;

Se lit: P_val_min, P_val_max: pointeurs sur entier;

Cela signifie que dans les zones réservées aux deux pointeurs, on ne pourra mettre que des entiers.

Cela signifie aussi que les zones de mémoire réservées auront une taille permettant d'y stocker des entiers(quand elles seront réservées).

 

 

 

Lorsqu'un pointeur est déclaré il ne pointe sur rien.

Ces deux pointeurs sur entiers sont donc déclarés mais ils sont encore = à NULL

Ils ne pointent pour l'instant sur rien.

Pour qu'ils pointent sur quelque chose, il faut soit leur donner comme valeur l'adresse d'une variable existante comme  dans le code précédent: ptr_entier1=&monentier;

Allocation Dynamique de mémoire malloc (stdlib.h)

Soit allouer dynamiquement un ensemble de cellule dans le tas.

ptr_entier1=(int *)malloc(sizeof(int));

Entrons dans les détails. La procédure new fait trois choses:

1.      Elle recherche la première cellule vide du tas
exemple 62405000.

2.      Elle met son adresse dans le pointeur qui vaudra maintenant 62405000.

3.       Elle réserve dans le tas le nombre de cellule nécessaire au stockage du contenu.

 

 Elle réservera donc une cellule si ptr_entier1 est un pointeur sur char, 4 cellules si ptr-entier1 est un pointeur sur INT et par exemple 26 cellules si ptr_entier1 est un pointeur sur chaîne(25).

 

 

Examinons cet exemple

int main(int argc, char **argv)

{

        int *nb4,*nb5;

        nb4=(int *)malloc(sizeof(int));

        nb5=(int *)malloc(sizeof(int));

        *nb4 =1;

        *nb5 =2;

        //printf("nb1 commence en %d et nb2 commence en %d\n",*pnb1,*pnb2);

        printf("nb4 pointe sur %d et nb5 pointe sur %d\n",nb4,nb5);

        printf("nb4 vaut %d et nb5 vaut %d\n",*nb4,*nb5);

        printf("nb4 est en %d et nb5 est en %d\n",&nb4,&nb5);

        free(nb4);

        free(nb5);

        getch();

        return 0;

}

 

Libération dynamique de mémoire free:

 

Free(LePointeur) ceci va libérer la zone de la pile référencée par LePointeur .

Attention: Toute allocation dynamique doit être libérée sinon vous obtenez un programme qui plante au bout d'un certain temps(heap overflow error).

La  mise à NULL du pointeur doit  être forcée afin que le programme n’essaie plus d’écrire dans la zone référencée.

LePointeur=NULL;

 

Utilisation des pointeurs:

Voici un exemple d'utilisation des pointeurs.

 

Soit le type suivant:

 

Struct TEnrClient{

            Nom:string;

            Pnom:string;

}* PtrMonCli;

 

 

{

   //Réservation de mémoire pour un client:

PtrMonCli=(TenrClient *) malloc(sizeof(TenrClient)); //la quantité de mémoire à réserver doit être spécifiée.

 *Ptr_moncli.nom=dupond;

  *Ptr_moncli.prenom=dupond;

  Afficher(*PtrMonCli.nom)

  Afficher(*PtrMonCli.prenom)

  //ne pas oublier de libérer la mémoire allouée:

  free(PtrMonCli);

End;

 

 

On voit dans cet exemple qu'un pointeur peut pointer sur un type utilisateur structuré.

 

Afin de ne pas avoir à déclarer autant de pointeurs sur client que l'on a de client on doit créer des structures dynamiques de données.

 

On pourra créer des piles, des files, des listes chainées doublement chainées et circulaires ou des arbres .

 

Les Listes chaînées:

struct TEnrClient{

            char Nom[25];

            char Pnom[25];

    TEnrClient*  P_suiv;

};

 

//Tout client pointe sur le client suivant grâce à p_suiv.

 

//Déclaration du premier pointeur sur client

TEnrClient * P_prem,*P_nouv,*p_cli;

 

void ajoutclient(void)

{

  //Création de  client :

  if (P_prem==NULL)

  {

    P_prem=(TEnrClient *)malloc(sizeof(TEnrClient));

    scanf("%s",P_prem->Nom);

    scanf("%s",(*P_prem).Pnom);

  }

  else

  {

       //Ajout d'un client

 

    P_nouv=(TEnrClient *)malloc(sizeof(TEnrClient));

    scanf("%s",(*P_nouv).Nom);

    scanf("%s",(*P_nouv).Pnom);

    //

    p_cli=P_prem;

    while ((*p_cli).P_suiv!=NULL)

    {

       p_cli=(*p_cli).P_suiv;

    }

    (*p_cli).P_suiv=P_nouv;

  }

}

void listeclient(void)

{

  p_cli=P_prem;

  while(p_cli!=NULL)

  {

    printf("nom:%s, prénom:%s\n",(*p_cli).Nom,(*p_cli).Pnom);

    p_cli=(*p_cli).P_suiv;

  }

}

 

int main(int argc, char **argv)

{

 

 

        ajoutclient();

        ajoutclient();

        ajoutclient();

        listeclient();

        getch();

 

        return 0;

}

 

Exercices:

Ecrire la procédure de suppression d'un élément de la liste.

Ecrire une fonction renvoyant le nombre d'élément d'une liste.