Chapitre 9
Structures en C et
Applications aux structures de données fondamentales

A – Les structures en C

9.1. Définition d'une structure.

Une structure regroupe un ensemble de données, de n'importe quel type, en un nouveau type.
On appelle membre tout élément de la structure.
Chaque membre dispose d'un nom unique dans la classe.
Cependant un même nom peut désigner plusieurs membres de structures différentes.

Syntaxe :
struct NomDeLaStructure {
Type1 membre1 ;
Type2 membre2 ;
…………….
Typen membren ;
} ;

Exemples de définitions  de structure
struct NombreComplexe {
double Reel,
            Imaginaire ;} ;

 #define Taille_Nom 20
#define Taille_Prenom 15
struct Personne {
     
	char nom[Taille_Nom], //membre nom
	  prenom[Taille_Prenom]; //membre prenom
     unsigned age;
	      } ;

ATTENTION
Le C  standard interdit que les membres d'une structure soient initialisées lors de leur déclaration.

Exemple.
struct Personnes {
const unsigned Taille_Nom=20;
 //  ERREUR DE COMPILATION
const unsignedTaille_Prenom=15; 
// ERREUR DE COMPILATION
char nom[Taille_Nom], //membre nom
prenom[Taille_Prenom]; //membre prenom
unsigned age;
	      } ;

 Les structures que l'on vient de voir peuvent contenir des membres de n'importe quel type à l'exclusion de la structure que l'on veut définir (récursion interdite, il faudra utiliser des pointeurs). Les structures  peuvent contenir des membres qui sont d'autres structures etc..

Exemple  
enum Dimension {Taille_Nom=20,Taille_Prenom=15} ;
enum  Niveau {Bacc,Licence,Maitrise} niveau;
//+++++++++++++++++++++++++++++++++++++++++++++
struct Personne {
//****************************
				struct Etude {
				enum Niveau niveau;
				char* universite;
                                          };
//*******************************	
    char nom[Taille_Nom], //membre nom
    prenom[Taille_Prenom]; //membre prenom
     unsigned age;
     struct Etude degre;	      } ;

9.2. Déclaration d'une structure.

 Les définitions des structures peuvent être indépendantes. 
Toute structure, avant d'être utilisée, doit être déclarée.
Cependant, contrairement aux fonctions, la déclaration d'une structure ne suffit pas toujours pour que le compilateur résolve toutes les ambiguïtés.

Exemple de déclarations:

struct domicile;
struct graphe;

9.3. Accès aux membres d'une structure.

On peut manipuler chaque membre d'une structure au moyen de l'opérateur de sélection d'un membre, afin de pouvoir avoir accès aux données. C’est le point . qui permet d’accéder aux membres d’une structure.
Exemple
struct Rationnel
 {
 	   int num; //  numérateur
	   int denum; // dénominateur  
    }  ;

void main()
{     struct Rationnel v;
 v.num=5 ;
v.denum=7 ;
}

B- Applications aux structures de données fondamentales

9.4. Application aux files séquentielles

Les bandes magnétiques, mais aussi les enregistrements dans un processus d'événements temporels, constituent des exemples de structures de files séquentielles.

9.4.1. spécification fonctionnelle

Une file séquentielle est une suite dont on sait repérer le début, et pour laquelle on dispose d'une station de traitement (tête d'accès) qui se déplace le long de la structure. Les opérations de base sont le positionnement de la tête d'accès au début de la file, la lecture ou l'écriture de l'élément courant, suivi du déplacement de la tête d'une position en avant.

9.4.2. Spécification logique et physique( en mémoire centrale)

A ) Représentation par tableau.

L'information utile est contenue dans un tableau.
Les données sont rangées dans l'ordre croissant des indices du tableau.

Exemple
// file d'entiers non négatifs
//------------------------------------------------------------------
#define Taille 20 // taille du tableau
struct FileSeq {
int tab[Taille] ; // le tableau
int  acces; // index
};

Primitives d'accès :

Positionnement de la tête d'accès au début de la file :

void Premier(struct FileSeq* f) {
	f->acces=0; // première place dans la file
}
//------------------------------------------------------------------

Prédicat de fin de file.
La fin de file sera marquée par l'entier -1
Prédicat de fin de file (prend la valeur -1 si la tête d'accès se trouve en fin de file.)
  
int Fin(struct FileSeq f) {
	return (f.tab[f.acces] );
}

Prise de la donnée placée sous la  tête d'accès et avance d'une position la tête d'accès.

void Prendre(struct FileSeq* f,int* data) {
	*data=f->tab[f->acces]; // prise
	f->acces=f->acces+1; // avance
}

Mettre un élément dans la file : le placer sous la tête d'accès, avancer la tête d'une position, puis écrire –1 (fin de file).

void Mettre(struct FileSeq* f,int data) {
	f->tab[f->acces]=data; // mettre sous la tête d'accès
	f->acces=f->acces+1; // avance la position de la tête
	f->tab[f->acces]=-1; // marquer la fin de file
}

B ) Représentation par pointeurs

Les données constituent une suite (liste) non contrainte.
Nous devons disposer de deux pointeurs :
l'un pour désigner le début de la liste et l'autre pour désigner la tête d'accès.

       0

Début

Acces

Les maillons de la suite d'entiers (dans cet exemple) sont :

info       suiv

info       suiv

//*****************************
struct Maillon {
int info;
struct Maillon* suiv;
};
//*****************************
La structure de file séquentielle dynamique devient :
struct  FileSeqDyn {
struct Maillon* Debut;
struct Maillon *Acces ;
};

Les primitives sont :      

 // placer la tête d'accès au debut de la file
void PremierDyn(struct FileSeqDyn* f) {
	f->Acces=f->Debut; 
}  
//------------------------------------------------------------------

// Retourne –1 si fin de file d'entiers non négatifs
//------------------------------------------------------------------
int FinDyn(struct FileSeq f) {
	return (f.tab[f.acces] );}

// Prendre une donnée sur la file
//------------------------------------------------------------------
void PrendreDyn(struct FileSeqDyn* f,int* data) {
	*data=f->Acces->info; // prise de la donnée 
	f->Acces=f->Acces->suiv; // avance
};
//------------------------------------------------------------------
// Mettre dans la file une donnée sous la tête d'accés
//------------------------------------------------------------------
void MettreDyn(struct FileSeqDyn* f,int data) {
f->Acces->info=data; // mettre sous la tête d'accès
f->Acces=f->Acces->suiv; // avance la position de la tête
f->Acces->info=-1; // marquer la fin de file
}

9.5. Application aux files d'attentes

9.5.1. Introduction

La structure d'une file d'attente ressemble à celle des file séquentielle. Les files d'attentes sont fréquements utilisées dans la vie courante : file d'attente de clients devant un guichet… En informatique, ce sont par les files d'attentes que sont gérés le traitements par lots de commandes, les messages en attentes dans un commutateur téléinformatique  tel Transpac…

Une file attente est une structure de données (dynamiques) homogènes avec un accès en entrée et un accès en sortie. Les données sont ajoutées au moyen d'une tête d'écriture appelé queue, et prélévés par une tête de lecture appelé tête.

queue

tête

Ajout

Retrait

Une file d'attente est une structure FIFO (first in, first out), c'est à dire premier entré, premier sorti.

Une file d'attente ne dispose pas, comme une séquentielle, d'un mécanisme de déplacement de la tête d'accès, et les points d'entrée et de sortie d'une file d'attente sont distincts.

Dans le cas d'une file séquentielle on fait des lectures sans modifications, alors que dans le cas des files d'attentes on effectue des retraits effectifs de données.

Dans une file d'attente, l'ajout d'éléments s'effectue sans problème, alors que dans le cas d'une file séquentielle l'ajout d'un élément au milieu de la file rend inaccessibles tous les éléments placés derrière.

9.5.2. Spécification logique et physique( en mémoire centrale)

Une file d'attente se décompose en deux parties :
•	la tête qui correspond au premier élément (celui qui peut être retiré)
•	le corps qui comprend tous les autres éléments.

Nous voyons ici que, dans le cas d'une file d'attente, l'élément de tête joue un rôle particulier alors que l'élément de queue n'a pas de rôle particulier dans le fontionnement de cette structure de données.

Représentation chaînée
Cette structure peut être spécifiée en langage C par :
- les éléments composant la chaîne sont données par :

struct Maillon {
	int info;
	struct Maillon* suiv;
};
struct FileAttente {
	struct FileAttente* tete, 
		*queue;};

Il existe trois primitives :
Le prédicat Vide qui permet de savoir si la file d'attente
est vide ou non.

	int Vide ( struct FileAttente f) {
		return (f.tete==NULL);
}
//====================================
La fonction Defiler qui permet de retirer l'élément  de tête.

	void Defiler(struct FileAttente* f, int *data) {
		struct Maillon* p; // temporaire
		if (!Vide(*f)) {

			*data=f->tete->info; // retirer
                      p=f->tete; //sauvegarder
			 f->tete=f->tete->suiv; //avancer
			 free(p); // liberer p
			 if (f->tete==NULL) f->queue=NULL;
		}

	}
//====================================
La fonction Enfiler qui permet de rajouter un élément à la file.

if (f->queue!=NULL) {
f->queue->suiv=calloc(1, sizeof(Maillon)); 
// vers un nouveau maillon
 f->queue=f->queue->suiv;
 // passer sur le nouveau maillon
 f->queue->info=data; // donner la valeur
f->queue->suiv=NULL; // fin de file
							}
else {
	f->queue=calloc(1, sizeof(int));
	f->queue->info=data; 
	f->queue->suiv=NULL;
	f->tete=f->queue;
		}
	}

9.6. Application aux piles

9.6.1. Introduction

Cette structure correspond au concept usuelle de pile d'assiettes, pile de dossiers,…
La caractéristique d'une pile est que l'on retire toujours le dernier élément déposé : l'ordre de sortie est l'inverse de l'ordre d'entrée.
L'utilisation de la structure de pile en informatique se trouve par exemple dans la cascade de sous-programmes, de la récursion…
Une pile est une structure de donnée dynamique homogène à un seul point d'accès : les données sont ajoutées ou enlevées par l'intermédiaire d'une tête d'accès appelée sommet de la pile.

Les primitives sont :
Vide pour savoir si la pile est vide.

Empiler pour ajouter un élément .

Deplier pour retirer un élément.

La gestion d'une pile est dite FIFO (last in, first out) c'est à dire dernier entré, premier sorti.

9.6.2. Spécification logique et physique( en mémoire centrale)

Donnons la représentation chaînée.

     NULL

sommet

struct Maillon {
	int info;
	struct Maillon* suiv;
};

typedef struct Maillon* Sommet; // pointe au sommet //===========================
int PileVide(Sommet sommet) {
	return (sommet==NULL);
}
//===========================
void Empiler(Sommet sommet,int data) {
Sommet q=calloc(1,sizeof(struct Maillon));
 // allouer un nouveau maillon
q->suiv=sommet; // accrocher l'ancien maillon
q->info=data;// passer l'info
sommet=q;// mettre ce maillon au sommet
}
//===========================
void Depiler(Sommet sommet,int* data) {
Sommet q;
	if (!PileVide(sommet)) {
*data=sommet->info; // récuperer la valeur du sommet
q=sommet; // sauvegarder
sommet=sommet->suiv; // déplacer le sommet
free(q); // libérer le maillon dépilé
	}
}
//===========================