/*
Les principales STRUCTURES DYNAMIQUES sont :
---------------------------------
- les files d'attente
- les piles
- les graphes (les arbres en sont un cas particulier)
Pour gerer ces structures, utilisation des pointeurs.
Les files d'attente (QUEUE):
---------------------
- ex : travaux, guichet bancaire,...)
- suite ordonnée d'éléments à traiter
- le critère d'ordre le plus utilisée est l'ordre d'arrivée dans la file (avec un second
critere, éventuellement : critère d'urgence, ou priorité, statique ou dynamique)
- file d'attente classique de type FIFO (First In First Out)
Les piles (STACK):
-----------
- utilisé en informatique, par les interpretation /compilation
(necessité d'évaluation des expressions dans une formule, par ex.), pile d'execution,
pile d'appel (calling stack)
- suite d'éléments empilés de type LIFO (Last In First Out)
Les graphes (GRAPH):
-------------
- noeuds liés par des arcs (ex stations,noeuds, et reseau,arcs)
- ensemble de sommets, ou noeuds, reliés entre eux par des arcs
- les arcs sont parfois orientés (sinon on les appelle des arêtes)
- les graphes s'appliquent à divers domaines : réseaux routiers, ferroviaires, téléphoniques,
neurones, informatique, web...
- les arbres sont des cas particuliers des graphes (strictement hiérarchiques)
- relations de voisinage, de chemin permettant de relier les noeuds d'un graphe( X-->--Y-->--Z )
via les arcs.
(tete_de_file)-->element-->element-->element-->...
element = structure composée d'un contenu et d'une information de chainage vers le voisin
une structure (enregistrement, record,...) est un ensemble d'éléments simples ou composés
regroupés dans une même entité identifiée par un nom.
en C, C++ :
struct cel / cel : nom du type de cellule
{ int info; ...; /données
cel *voisin; /reference recursive, pointeur vers le voisin = NULL si par de voisin
};
[struct] cel *tlist; / tete de liste vers structure de type cel
[struct] cel cel1, cel2, cel3; / declaration de structures de type cel
[struct] cel *surf; / pointeur pour parcourir la liste
cf exo_0
*/#include <stdio.h> #include <stdafx.h>
/* EXO_0 : LISTE ET PARCOUR DE LISTE */
void exo_0 ()
{
// DECLARATION
struct cel // cel : nom du type de cellule
{ int info; //données
cel *voisin; //reference recursive, pointeur vers le voisin = NULL si par de voisin
};
struct cel *tliste, *tlistesv; // tete de liste vers structure de type cel
struct cel cel1, cel2, cel3; // declaration de structures de type cel
struct cel *surf; // pointeur pour parcourir la liste
int i = 1;
int saisie=0;
// INITIALISATION
cel1.info=110;
cel2.info=170;
cel3.info=246;
cel1.voisin=&cel2;
cel2.voisin=&cel3;
cel3.voisin=NULL;
tliste=&cel1;
// PARCOURS
printf("\nAffichage des éléments en attente :");
surf=tliste;
while (surf != NULL)
{
printf("\n %ieme element de la file %i",i,surf->info);
surf=surf->voisin;
i++;
};
// NOUVELLE VALEUR
printf("\nSaisir une nouvelle donnée :");
surf=new cel; // creation d'une nouvelle structure cel et stockage de son adresse dans surf
scanf("%i",&surf->info);
tlistesv=tliste; // memo tete de liste /on met dans le pointeur tliste_sv, le pointeur de tliste (adr de cel1)
tliste=surf; // nouvelle tete de liste / on ecrase le pointeur tliste avec l'adresse de la nouvelle cellule créée
surf->voisin=tlistesv; // nouvelle cellule pointe vers l'ancienne tete de liste / on met la cellule
// PARCOURS
printf("\nAffichage des éléments en attente :");
surf=tliste;
i=1;
while (surf != NULL)
{
printf("\n %ieme element de la file %i",i,surf->info);
surf=surf->voisin;
i++;
};
};
/* EXO_1 : SAISIE D'ELEMENTS, LISTE ET PARCOUR DE LISTE */
void exo_1 ()
{
// DECLARATION
struct cel // cel : nom du type de cellule
{ int info; //données
cel *voisin; //reference recursive, pointeur vers le voisin = NULL si par de voisin
};
struct cel *tliste, *fliste; // tete et fin de liste vers structure de type cel
struct cel *surf, *tri, *triav; // pointeur pour parcourir la liste
int i = 1;
int saisie=0;
char rep='y';
char reppos='t';
// INITIALISATION
tliste=NULL;
fliste=NULL;
// NOUVELLE VALEUR
printf("\nSaisie des éléments :");
printf("\n Trié ou non (t ou n)");
getchar(); // prise de l'entree RC issue du message precedent
reppos=getchar();
while ((rep=='y')||(rep=='Y'))
{
printf("\nSaisir une nouvelle donnée :");
surf=new cel; // creation d'une nouvelle structure de type cel et stockage de son adresse dans surf
scanf("%i",&surf->info);
surf->voisin=NULL;
if (tliste==NULL)
{
tliste=surf;
fliste=surf;
}
else
{ if (reppos=='t')
{ if (tliste->suivant=NULL) {}
else
{triav=null;
tri=tliste;
while((surf->info>tri->info))
{
triav=tri;
tri=tri->voisin;
}
triav->suivant=surf;
surf->suivant=tri;
}
}
else
{
printf("\n en fin ou debut ? (f ou d)");
getchar(); // prise de l'entree RC issue du message precedent
reppos=getchar();
if (reppos=='f')
{
fliste->voisin=surf;
fliste=surf;
}
else
{
surf->voisin=tliste;
tliste=surf;
}
}
};
printf("\nNouvelle valeur à saisir ? (y ou Y)");
getchar(); // prise de l'entree RC issue du message precedent
rep=getchar();
};
// PARCOURS
printf("\nAffichage des éléments en attente :");
surf=tliste;
i=1;
while (surf != NULL)
{
printf("\n %ieme element de la file %i",i,surf->info);
surf=surf->voisin;
i++;
};
};
void main()
{
printf("\nDebut de programme");
//exo_0();
exo_1();
printf("\nFin de programme\n");
}