Systèmes informatiques
Fermer ×

Les structures de données en C

Les listes chaînées

Tous les exemples de programmes C ont été compilés avec gcc et make et testés sous linux.

Définitions

Une liste chaînée est une structure de données dynamique, qui peut servir à implémenter d'autres structures de données comme les piles et les files. Elle permet de stocker un ensemble de données de même type. Chaque élément de cette suite est composé de la structure de données, et, au moins d'un pointeur ou indice vers l'élément suivant.

Liste chaînée simple

Le pointeur du dernier élément a la valeur NULL. A la création, le pointeur de tête est NULL, ce qui correspond à une liste vide.

L'accès à cette liste se fait à partir de l'adresse de début de liste, nommée tête. Le dernier élément de la liste se nomme la queue.

Ajouter ou supprimer un élément en tête de liste est immédiat, par contre ajouter ou supprimer un élément en fin de liste impose de parcourir la liste jusqu'au dernier ou à l'avant dernier.

Pour ajouter un élément on crée un élément en mémoire en utilisant l'allocation dynamique, puis on modifie les pointeurs en conséquence.

Pour supprimer un élément on modifie les pointeurs, puis on libère la mémoire allouée.

Il existe d'autres fonctions de gestion de cette liste telle que l'insertion et la suppression d'un élément à un endroit bien précis dans la liste, ou encore le nombre d'éléments dans la liste.

Exemple de liste chaînée de réels double précision, avec les fonctions d'ajout et de suppression en tête et queue de liste, ainsi que l'accès à l'élément de queue ainsi que le nombre d'éléments.

Fichier de prototype listechaine.h


#ifndef __LISTECHAINEE_H
#define __LISTECHAINEE_H

typedef struct s_element {
	double valeur;
	struct s_element *suivant;
} Telement;

typedef Telement *Telement_ptr;

void creerListe(Telement_ptr *) ;
size_t tailleListe(Telement_ptr);
void ajouteentete(Telement_ptr *, double);
void ajoutequeue(Telement_ptr * ,double );
void supprimerentete(Telement_ptr *);
void supprimerqueue(Telement_ptr *);

#endif
				

Ici la structure de données se résume à un réel double précision.

On utilise typedef pour définir l'ensemble des données utilisées et pointeurs vers ces données.

l'identifiant s_element permet de déclarer le pointeur suivant qui point vers cette structure.

La fonction de création initialise à NULL le pointeur de tête pour indiquer que la liste est vide.

Le calcul du nombre d'éléments dans la liste nécessite de parcourir la liste.

Ajouter un élément en tête de liste

  1. Création d'un nouvel élément en mémoire
  2. Affectation de la valeur avec la valeur du paramètre
  3. Affecter l'adresse du suivant du nouvel élément avec l'ancienne valeur du pointeur de tête
  4. Mise à jour du pointeur de tête avec l'adresse du nouvel élément

Ajouter un élément en queue de liste

On crée un nouvel élément, lui affecte la valeur du paramètre puis l'adresse du suivant à NULL. Ensuite il faut traiter plusieurs cas :

  • La liste est vide, on affecte la tête avec l'adresse de l'élément
  • La liste contient un seul élément, on affecte l'adresse du suivant de l'unique élément avec l'adresse du nouvel élément
  • La liste contient plus d'un élément, on parcours la liste jusqu'au dernier élément (adresse du suivant est NULL), on remplace la valeur NULL par l'adresse du nouvel élément

Supprimer un élément en tête de liste

Si la liste n'est pas vide :

  1. Sauvegarde temporaire de l'adresse du deuxième élément (adresse du suivant de l'élémnt de tête)
  2. Libération de la mémoire qui contient l'élément de tête
  3. Affectation de l'adresse de la tête avec l'adresse sauvegardée temporairement

Supprimer un élément en queue de liste

Comme pour l'ajout, il faut traiter plusieurs cas :

  • La liste est vide, il n'y a rien à faire
  • La liste contient un seul élément, on libère la mémoire allouée à l'élément, puis on affecte la valeur NULL à la tête
  • La liste contient plus d'un élément, on parcours la liste jusqu'à l'avant dernier élément (suivant du suivant est NULL), On libère la mémoire allouée au dernier d'adresse suivant, puis on affecte le suivant à NULL

Fichier listechaine.c


#include <stdlib.h>
#include <stdio.h>
#include "listechainee.h"

void creerListe(Telement_ptr *tete) {
	*tete = NULL;
}

size_t tailleListe(Telement_ptr tete) {
	size_t n = 0;
	Telement_ptr p = tete ;
	while (p != NULL) {
		p = p->suivant ;
		n+=1;
	}
	return n;
}

void ajouteentete(Telement_ptr *tete,double valeur) {
	Telement_ptr element = (Telement_ptr )malloc(sizeof(Telement));
	if (element != NULL) {
		element->valeur = valeur ;
		element->suivant = *tete;
		*tete = element ;
	}
}

void ajoutequeue(Telement_ptr *tete,double valeur) {
	Telement_ptr p = *tete ;
	Telement_ptr element = (Telement_ptr )malloc(sizeof(Telement));
	if (element == NULL) {
		return;
	}
	element->valeur = valeur ;
	element->suivant = NULL;
	if ((*tete) != NULL) {
		if ((*tete)->suivant == NULL) {
			(*tete)->suivant = element ;			
		}
		else {
			while (p->suivant != NULL) {
				p = p->suivant ;
			}	
			p->suivant = element ;
		}
	}
	else {
		*tete = element ;
	}
}

void supprimerentete(Telement_ptr *tete) {
	if (*tete == NULL) {
		return;
	}
	Telement_ptr p = (*tete)->suivant;
	free(*tete);
	*tete = p; 
}

void supprimerqueue(Telement_ptr *tete) {
	Telement_ptr p = *tete ;
	if (*tete == NULL) {
		return;
	}
	if ((*tete) != NULL) {
		if ((*tete)->suivant == NULL) {
				free(*tete);
		}
		else {
			while ((p->suivant)->suivant != NULL) {
				p = p->suivant ;
			}	
			free(p->suivant);
			p->suivant = NULL ;
		}
	}
}
				
Voir un exemple de programme de test de la liste chaînée

Fichier de test


#include <stdlib.h>
#include <stdio.h>
#include "listechainee.h"

void printListe(Telement_ptr tete) {
	Telement_ptr p = tete ;
	while (p != NULL) {
		printf("%.0lf,",p->valeur);
		p = p->suivant ;
	}
	printf("\n");
}

int main(int argc, char **argv) {
	
	Telement_ptr tete;
	size_t n;
	
	creerListe(&tete);
	
	for(int i=0;i<10;i+=1) {
		ajouteentete(&tete,(double)i);
	}
	n = tailleListe(tete);
	printf("taille %ld\n",n);
	printListe(tete);
	for(int i=0;i<4;i+=1) {
		supprimerentete(&tete);
	}
	n = tailleListe(tete);
	printf("taille %ld\n",n);
	printListe(tete);
	for(int i=0;i<3;i+=1) {
		ajoutequeue(&tete,(double)i);
	}
	n = tailleListe(tete);
	printf("taille %ld\n",n);
	printListe(tete);		
	
	return EXIT_SUCCESS;
}
					

La fonction d'affichage permet d'afficher tous les éléments de la liste en partant de la tête et tant que la liste contient des éléments.

Le fait d'ajouter des éléments en tête de liste fait que la tête contient le dernier élément ajouté, et la queue le premier élément ajouté.

Le fait d'ajouter des éléments en queue de la liste produit l'effet inverse, la tête contient le dernier élément ajouté.

Le résultat de l'affichage du programme de test confirme ces faits.

taille 10
9,8,7,6,5,4,3,2,1,0,
taille 6
5,4,3,2,1,0,
taille 9
5,4,3,2,1,0,0,1,2,
					

Liste à chaînage double

La structure précédente, impose de parcourir la liste lors de l'utilisation de ajout et suppression en queue de liste, ou encore pour obtenir le nombre d'éléments. Ce qui fait que ce temps de traitement dépend du nombre d'éléments dans la liste. La solution est d'ajouter un pointeur de queue, mais cela ne suffit pas lors de la suppression de l'élément de queue car il faut l'avant dernier élément. Ce dernier problème peut être résolu en ajoutant un deuxième chaînage avec les adresses des précédents. On construit ainsi une liste à chaînage double.

Une liste à chaînage double comprend une structure de données qui contient le nombre d'éléments, les adresses de tête et de queue de la liste. Une structure qui définit l'élément qui contient les données ainsi qu'un pointeur vers le suivant et le précédent.

Le suivant du dernier élément est NULL, ainsi que le précédent du premier élément.

Exemple de liste chaînée de données génériques, avec les fonctions d'ajout et de suppression en tête et queue de liste.

Fichier de prototype listechaine.h


#ifndef __LISTECHAINEE_H
#define __LISTECHAINEE_H

typedef struct s_element {
	void *datas;
	size_t taille;
	struct s_element *precedent;
	struct s_element *suivant;
} Telement;

typedef Telement * Telement_ptr;

typedef struct s_liste {
	Telement_ptr tete;
	Telement_ptr queue;
	size_t taille;
} Tliste ;

typedef Tliste *Tliste_ptr ; 

void creerListe(Tliste_ptr) ;
void ajouteentete(Tliste_ptr, void *, int);
void ajoutequeue(Tliste_ptr, void *, int);
void supprimerentete(Tliste_ptr);
void supprimerqueue(Tliste_ptr);

#endif
				

On crée une liste dont la donnée est un pointeur non typé, ce qui permet de traiter n'importe quel type de donnée : entier, réel, tableau, structure, .... Ce qui impose d'avoir une information sur la taille de la donnée pour l'allocation dynamique de la donnée en plus de l'allocation dynamique de l'élément.

La fonction de création crée une liste vide de taille 0 avec des pointeurs de tête et de queue NULL.

Ajouter un élément en tête de liste

  1. Création du nouvel élément en lui allouant de la mémoire
  2. Création de la donnée de l'élément, en lui allouant également la mémoire nécessaire
  3. Copie des octets du paramètre dans la donnée allouée avec memcpy défini dans string.h
  4. Affecter l'adresse de tête au suivant de ce nouvel élément
  5. Affecter la valeur NULL au précédent de ce nouvel élément
  6. S'il n'y a aucun élément, affecter ua pointeur de queue l'adresse du nouvel élément
  7. S'il y a au moins un élément, remplacer la valeur NULL de l'élément de tête avec l'adresse du nouvel élément
  8. Affecter l'adresse de tête avec l'adresse du nouvel élément
  9. Incrémenter de 1 la taille

Ajouter un élément en queue de liste

  1. Création du nouvel élément en lui allouant de la mémoire
  2. Création de la donnée de l'élément, en lui allouant également la mémoire nécessaire
  3. Copie des octets du paramètre dans la donnée allouée avec memcpy défini dans string.h
  4. Affecter l'adresse de queue au précédent de ce nouvel élément
  5. Affecter la valeur NULL au suivant de ce nouvel élément
  6. S'il n'y a aucun élément, affecter ua pointeur de tête l'adresse du nouvel élément
  7. S'il y a au moins un élément, remplacer la valeur NULL de l'élément de queue avec l'adresse du nouvel élément
  8. Affecter l'adresse de queue avec l'adresse du nouvel élément
  9. Incrémenter de 1 la taille

Supprimer un élément en tête de liste

Si la liste n'est pas vide, on sauvegarde temporairement l'adresse du deuxième élément, on affecte l'adresse du précédent du deuxième élément à NULL. On libère la mémoire allouée à la donnée de l'élément puis la mémoire allouée à l'élément. Enfin on met à jour le pointeur de tête et on diminue la taille de 1.

Supprimer un élément en queue de liste

On reprend le même principe que pour la suppression de la tête, mise à part que c'est le suivant qui est à NULL, et que c'est le pointeur de queue qui est mis à jour.

Fichier listechaine.c


#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "listechainee.h"

void creerListe(Tliste_ptr liste) {
	liste->tete = NULL;
	liste->queue = NULL;
	liste->taille = 0 ;
}

void ajouteentete(Tliste_ptr liste,void *datas,int taille) {
	Telement_ptr element = (Telement_ptr)malloc(sizeof(Telement));
	if (element != NULL) {
		element->datas = malloc(taille);
		element->taille = taille ;
		memcpy(element->datas,datas,taille);
		element->suivant = liste->tete;
		element->precedent = NULL ;
		if (liste->taille == 0) {
			liste->queue = element;
		}
		else {
			(liste->tete)->precedent = element ;
		}
		liste->tete = element ;
		liste->taille += 1;
	}
}

void ajoutequeue(Tliste_ptr liste,void *datas,int taille) {
	Telement_ptr element = (Telement_ptr )malloc(sizeof(Telement));
	if (element != NULL) {
		element->datas = malloc(taille);
		element->taille = taille ;
		memcpy(element->datas,datas,taille);
		element->suivant = NULL;
		element->precedent = liste->queue ;
		if (liste->taille == 0) {
			liste->tete = element;
		}
		else {
			(liste->queue)->suivant = element ;
		}
		liste->queue = element ;
		liste->taille += 1;
	}
}

void supprimerentete(Tliste_ptr liste) {
	if (liste->tete != NULL) {
		Telement_ptr p = (liste->tete)->suivant;
		p->precedent = NULL ;
		free((liste->tete)->datas);
		free(liste->tete);
		liste->tete = p; 
		liste->taille -= 1 ;
	}
}

void supprimerqueue(Tliste_ptr liste) {
	if (liste->queue != NULL) {
		Telement_ptr p = (liste->queue)->precedent;
		p->suivant = NULL ;
		free((liste->queue)->datas);
		free(liste->queue);
		liste->queue = p; 
		liste->taille -= 1 ;		
	}
}
				
Voir un exemple de programme de test de la liste chaînée

Fichier de test


#include <stdlib.h>
#include <stdio.h>
#include "listechainee.h"

void printListe(Tliste liste) {
	Telement_ptr p = liste.tete ;
	while (p != NULL) {
		printf(" %.0lf,",*(double *)p->datas);
		p = p->suivant;
	}
	printf("\n");
}

int main(int argc, char **argv) {
	
	Tliste liste;
	
	creerListe(&liste);
	for(int i=0;i<10;i+=1) {
		double r = (double)i ;
		ajouteentete(&liste,&r,sizeof(double));
	}
	printf("taille %ld\n",liste.taille);
	printListe(liste);
	for(int i=0;i<4;i+=1) {
		supprimerentete(&liste);
	}
	printf("taille %ld\n",liste.taille);
	printListe(liste);
	for(int i=0;i<3;i+=1) {
		double r = (double)i ;
		ajoutequeue(&liste,&r,sizeof(double));
	}
	printf("taille %ld\n",liste.taille);
	printListe(liste);		
	return EXIT_SUCCESS;
}				

Le programme de test réalise le même test que le précédent.

Le résultat affiché est donc identique.

taille 10
9,8,7,6,5,4,3,2,1,0,
taille 6
5,4,3,2,1,0,
taille 9
5,4,3,2,1,0,0,1,2,
					

On peut d'ores et déjà imaginer comment utiliser les liste chaînées pour l'implémentation des piles et files.

Les piles

Définitions

Une pile est une structure de données accessible uniquement pas la tête nommée sommet. C'est une structure nommée LIFO (Last Input First Output) ou bien DEPS (Dernier Entré Premier Sorti).

Une pile comprend donc l'adresse ou indice du sommet ainsi qu'une fonction empiler qui consiste à ajouter un élément au sommet et dépiler qui consiste à extraire l'élément du sommet. Il peut y avoir une information de pile vide ou bien de taille de la pile.

Une pile peut être implémentée dans un tableau si sa taille est fixée à la compilation ou bien dans une liste chaînée en cas de structure dynamique.

Implémentation dans un tableau

Le sommet correspond à l'indice du tableau qui correspond à la dernière donnée accessible. Lorsque la pile est vide la valeur du sommet est -1.

Empiler consiste à incrémenter la valeur du sommet puis à copier la valeur dans le tableau d'indice sommet.

Dépiler consiste à copier la valeur d'indice sommer depuis le tableau, puis décrémenter la valeur du sommet.

Exemple avec une pile de réels

Fichier de prototypes pile.h


#ifndef __PILE_H
#define __PILE_H

#define TAILLEMAX 10

typedef struct s_pile {
	int sommet;
	double tableau[TAILLEMAX];
} TPile;

typedef TPile *TPile_ptr;

void PILE_init(TPile_ptr);
void Empiler(TPile_ptr,double);
double Depiler(TPile_ptr);
int PILE_pleine(TPile_ptr);
int PILE_vide(TPile_ptr );

#endif
				

La pile est vide lorsque le sommet est -1

La pile est pleine lorsque le sommet est égal à la taille -1

L'initialisation à pile vide consiste à initialiser le sommet à -1

On empile à condition que la pile ne soit pas pleine

On dépile s'il reste au moins un élément dans la pile

Fichier pile.c


#include <stdlib.h>
#include "pile.h"


void PILE_init(TPile_ptr pile) {
	pile->sommet = -1 ;
}

void Empiler(TPile_ptr pile,double valeur) {
	if (pile->sommet < (TAILLEMAX-1)) {
		pile->tableau[++pile->sommet] = valeur ;
	}
}

double Depiler(TPile_ptr pile) {
	double valeur = 0 ;
	if (pile->sommet > -1) {
		valeur = pile->tableau[pile->sommet--] ;
	}
	return valeur ;
}

int PILE_pleine(TPile_ptr pile) {
	return (pile->sommet == (TAILLEMAX-1)) ;
}

int PILE_vide(TPile_ptr pile) {
	return (pile->sommet == -1);
}
				
Voir un exemple de programme de test de la pile

Fichier de test


#include <stdlib.h>
#include <stdio.h>
#include "pile.h"

int main(int argc, char **argv) {
	
	TPile pile;
	double valeur ;
	
	PILE_init(&pile);
	for(int i=0;i<9;i+=1) {
		valeur = i ;
		Empiler(&pile,valeur);
	}
	if (PILE_pleine(&pile)) {
		printf("La pile est pleine\n");
	}
	else {
		printf("On a encore de la place\n");
	}
	while (!PILE_vide(&pile)) {
		valeur = Depiler(&pile);
		printf("%lf\n",valeur);
	}	
	return EXIT_SUCCESS;
}
					

On a une pile de 10 réels.

On empile 9 valeurs, il reste donc une place dans la pile.

Résultat du programme de test

On a encore de la place
8.000000
7.000000
6.000000
5.000000
4.000000
3.000000
2.000000
1.000000
0.000000
					

L'ordre d'empilage est de 0 vers 8.

Lors du dépilage, on affiche de 8 vers 0, on a bien une pile de type dernier entré premier sorti.

Implémentation dans une liste chaînée

On utilise la liste chaînée simple avec la tête qui est le sommet de la pile, la fonction ajouteentete pour empiler une valeur, puis l'accès au pointeur de tête pour lire la donnée du sommet suivi de la fonction supprimerentete pour dépiler.

Fichier de prototypes pile.h


#ifndef __LIFO_H
#define __LIFO_H

typedef struct S_element {
	size_t dataSize;
	void *data;
	struct S_element *suivant;
} TPile_Element;

typedef TPile_Element *TPile_Element_ptr;

void PILE_init(TPile_Element_ptr *);
void PILE_liberer(TPile_Element_ptr *);
void Empiler(TPile_Element_ptr *,void *,size_t);
void *Depiler(TPile_Element_ptr *);
int PILE_vide(TPile_Element_ptr *);

#endif
				

Comme pour la liste chaînée, on a une pile qui peut enregistrer tout type de donnée, en utilisant un pointeur vers un type de donnée non défini.

La seule différence avec la liste chaînée est que la fonction depiler inclut le retour de la structure de donnée de l'élément de tête (sommet) en plus de supprimer l'élément de tête (sommet). Cette structure de donnée est représentée par un pointeur vers une zone mémoire allouée qu'il faudra ne pas oublier de libérer.

Fichier pile.c


#include <malloc.h>
#include <string.h>
#include "pile.h"

void PILE_init(TPile_Element_ptr *sommet) {
	*sommet= NULL;
}

void PILE_liberer(TPile_Element_ptr *sommet) {
	TPile_Element_ptr p = NULL;
	while (*sommet != NULL) {
		p = *sommet ;
		*sommet = p->suivant ;
		free(p->data);
		free(p);
	}
}

int PILE_vide(TPile_Element_ptr *sommet) {
	return (*sommet == NULL) ;
}

void Empiler(TPile_Element_ptr *sommet,void *datas,size_t taille) {
	TPile_Element_ptr element=(TPile_Element_ptr)malloc(sizeof(TPile_Element));
	if (element != NULL) {
		element->taille = taille ;
		element->data = (char*)malloc(taille);
		memcpy(element->data,datas,taille);
		element->suivant = *sommet ;
		*sommet = element ;
	}
}

void *Depiler(TPile_Element_ptr *sommet) {
	char *datas = NULL;
	TPile_Element_ptr p = NULL;
	if (sommet != NULL) {
		p = *sommet ;
		datas = (char*)malloc((*sommet)->taille);
		memcpy(datas,(*sommet)->data,(*sommet)->taille);
		*sommet = (*sommet)->suivant;
		free(p->data);
		free(p);
	}
	return datas;
}
				
Voir un exemple de programme de test de la pile

Fichier de test


#include <stdlib.h>
#include <stdio.h>
#include "pile.h"

int main(int argc, char **argv) {
	
	TPile_Element_ptr pile;
	double valeur;
	
	PILE_init(&pile);
	for(int i=0;i<15;i+=1) {
		valeur = i + 1 ;
		Empiler(&pile,&valeur,sizeof(double));
	}
	while (!PILE_vide(&pile)) {
		double *valeurlue = (double *)Depiler(&pile);
		printf("%lf\n",*valeurlue);
		free(valeurlue);
	}	
	PILE_liberer(&pile);
	return EXIT_SUCCESS;
}
					

Après l'affichage des valeurs la mémoire allouée à la valeur est libérée

Résultat du programme

15.000000
14.000000
13.000000
12.000000
11.000000
10.000000
9.000000
8.000000
7.000000
6.000000
5.000000
4.000000
3.000000
2.000000
1.000000
					

La pile est utilisée dans les calculatrices RPN comme la calculatrice dc.

Les files

Définitions

Une file ou file d'attente est une structure de données qui permet de sauvegarder temporairement des données, elle est aussi appelée FIFO (First Input First Output) ou PEPS (Premier Entré Premier Sorti).

Une file comprend un pointeur de tête et un pointeur de queue, ainsi qu'une fonction d'écriture enfiler et une fonction de lecture défiler et, éventuellement une fonction de file vide et file pleine ou encore de taille.

Elle peut être implémentée dans un tableau de taille fixe ou bien dans une liste chaînée.

Implémentation dans un tableau

La première solution est d'ajouter les valeurs dans le tableau, toujours lire la valeur à l'indice 0 et décaler le tableau, cette solution n'est pas optimum, car le décalage dans le tableau prend du temps. L'autre solution est d'utiliser un indice de tête et un indice de queue. On écrit dans le tableau à l'indice de queue puis on incrémente l'indice de queue, on fait de même en lecture, on lit la valeur puis incrémente l'indice de tête. Lorsque l'on arrive en fin de tableau, on revient au début. Il suffit de gérer la taille pour savoir si la file est pleine ou vide. Dans ce cas on parle de file circulaire.

Exemple avec une file de réels

Fichier de prototypes file.h


#ifndef __FILE_H
#define __FILE_H

#define TAILLEMAX 10

typedef struct s_file {
	int tete;
	int queue;
	int taille;
	double tableau[TAILLEMAX];
} TFile;

typedef TFile *TFile_ptr;

void FILE_init(TFile_ptr);
void Enfiler(TFile_ptr,double);
double Defiler(TFile_ptr);
int FILE_pleine(TFile_ptr);
int FILE_vide(TFile_ptr );

#endif
				

La structure de la file est composée de l'indice de tête, de queue, de la taille ainsi que du tableau qui contient les données.

Lors de l'initialisation les indices de tête et de queue sont à 0 et la taille est également à 0.

Pour ajouter ou enfiler une valeur, on écrit la valeur à l'indice queue, puis on incrémente l'indice de queue. Il ne faut pas oublier de revenir en début de tableau lorsque l'on dépasse la fin du tableau. Ensuite on incrémente de 1 la taille de la file.

Pour extraire ou défiler une valeur, on lite la valeur à l'indice de tête, puis on incrémente l'indice de tête sans oublier de revenir en début de tableau lorsque l'on dépasse la fin du tableau, ni de décrémenter la taille.

La pile est pleine lorsque la taille est égale à la taille maximum du tableau, et vide lorsque la taille est nulle.

Fichier file.c


#include <stdlib.h>
#include "file.h"


void FILE_init(TFile_ptr file) {
	file->tete = 0 ;
	file->queue = 0;
	file->taille = 0 ;
}

void Enfiler(TFile_ptr file,double valeur) {
	if (file->taille < TAILLEMAX) {
		file->tableau[file->queue] = valeur ;
		file->queue += 1 ;
		if (file->queue > (TAILLEMAX - 1)) {
			file->queue = 0 ;
		} 
		file->taille += 1 ;
	}
}

double Defiler(TFile_ptr file) {
	double valeur = 0 ;
	if (file->taille > 0) {
		valeur = file->tableau[file->tete] ;
		file->tete += 1 ;
		if (file->tete > (TAILLEMAX - 1)) {
			file->tete = 0 ;
		} 
		file->taille -= 1;
	}
	return valeur ;
}

int FILE_pleine(TFile_ptr file) {
	return (file->taille == TAILLEMAX);
}

int FILE_vide(TFile_ptr file) {
	return (file->taille == 0);
}

				
Voir un exemple de programme de test de la file

Fichier de test


#include <stdlib.h>
#include <stdio.h>
#include "file.h"

int main(int argc, char **argv) {
	
	TFile file;
	double valeur;
	
	FILE_init(&file);
	
	for(int i=0;i<8;i+=1) {
		valeur = i + 1;
		Enfiler(&file,valeur);
	}
	printf("Je lis 4\n");
	for(int i=0;i<4;i+=1) {
		valeur = Defiler(&file);
		printf("%lf\n",valeur);
	}
	for(int i=0;i<4;i+=1) {
		valeur = i + 11;
		Enfiler(&file,valeur);
	}
	printf("Je lis tout\n");
	while (!FILE_vide(&file)) {
		valeur = Defiler(&file);
		printf("%lf\n",valeur);
	}	
	return EXIT_SUCCESS;
}
					

On enfile 8 valeurs de 1 à 8, puis on défile 4 valeurs qui sont les premières de 1 à 4. Il reste les valeurs de 5 à 8. Ensuite on enfile les valeurs 11 à 14. Il reste donc dans l'ordre de sortie les valeurs 5 à 8 puis 11 à 14.

Résultats du programme

Je lis 4
1.000000
2.000000
3.000000
4.000000
Je lis tout
5.000000
6.000000
7.000000
8.000000
11.000000
12.000000
13.000000
14.000000
					

Implémentation dans une liste chaînée

Cette fois-ci, on utilise les pointeurs de tête et de queue ainsi que les fonctions ajouterqueue et supprimerentete après avoir lu la valeur de tête. Le fait que la fonction supprimerqueue n'est pas utilisée, le chaînage double n'est pas nécessaire. On va donc choisir un chaînage simple avec un pointeur de tête et un pointeur de queue.

Exemple avec une file de réels

Fichier de prototypes file.h


#ifndef __FILE_H
#define __FILE_H

typedef struct s_element {
	double valeur;
	struct s_element *suivant;
} Telement;

typedef Telement * Telement_ptr;

typedef struct s_file {
	Telement_ptr tete;
	Telement_ptr queue;
	size_t taille;
} TFile;

typedef TFile *Tfile_ptr;

void creerFile(Tfile_ptr ) ;
void Enfiler(Tfile_ptr  ,double );
double Defiler(Tfile_ptr );

#endif
				

L'élément est donc composé de la valeur et du pointeur vers le suivant. La file est composée des pointeurs de tête et de queue, de la taille.

La file vide est initialisée avec un pointeur de tête et de queue de valeur NULL et une taille à 0.

Enfiler consiste à ajouter une valeur en queue de la file en appliquant les mêmes règles que celles utilisées pour la liste chaînée.

Defiler consiste à extraire la valeur de tête, puis de supprimer l'élément de tête en utilisant les mêmes règles que celles utilisées pour la liste chaînée.

Fichier file.c


#include <stdlib.h>
#include <stdio.h>
#include "file.h"

void creerFile(Tfile_ptr file) {
	file->tete = NULL;
	file->queue = NULL;
	file->taille = 0 ;
}


void Enfiler(Tfile_ptr file,double valeur) {
	Telement_ptr element = (Telement_ptr )malloc(sizeof(Telement));
	if (element != NULL) {
		element->valeur = valeur;
		element->suivant = NULL;
		if (file->taille == 0) {
			file->tete = element;
		}
		else {
			(file->queue)->suivant = element ;
		}
		file->queue = element ;
		file->taille += 1;
	}
}

double Defiler(Tfile_ptr file) {
	double valeur=0;
	if (file->tete == NULL) {
		return 0;
	}
	valeur = file->tete->valeur;
	Telement_ptr p = file->tete->suivant;
	free(file->tete);
	file->tete = p; 
	file->taille -= 1 ;
	return valeur;
}
				
Voir un exemple de programme de test de la file

Fichier de test


#include <stdlib.h>
#include <stdio.h>
#include "file.h"

void printFile(TFile file) {
	Telement_ptr element = file.tete ;
	for(int i=0;i<file.taille;i+=1) {
		printf("%.0lf,",element->valeur);
		element = element->suivant;
	}
	printf("\n");
}

int main(int argc, char **argv) {
	TFile file;
	double valeur;
	
	creerFile(&file);
	for(int i=0;i<8;i+=1) {
		valeur = i + 1;
		Enfiler(&file,valeur);
	}
	printFile(file);
	printf("Je lis 4\n");
	for(int i=0;i<4;i+=1) {
		valeur = Defiler(&file);
		printf("%lf\n",valeur);
	}
	printFile(file);
	for(int i=0;i<4;i+=1) {
		valeur = i + 11;
		Enfiler(&file,valeur);
	}
	printFile(file);
	printf("Je lis tout %ld\n",file.taille);
	while (file.taille != 0) {
		valeur = Defiler(&file);
		printf("%lf\n",valeur);
	}
	return EXIT_SUCCESS;
}
					

On affiche le contenu de la file entre chaque opération afin de bien montrer le fonctionnement de la file.

La file contient les valeurs de 1 à 8, on extrait 4 valeurs, il reste les valeurs de 5 à 8.

On ajoute les valeurs de 11 à 14, la file contient donc les valeurs de 5 à 8 suivies des valeurs de 11 à 14.

On lit toutes les valeurs, qui apparaissent dans l'ordre de l'enregistrement, la file est vide.

Résultats du programme :

1,2,3,4,5,6,7,8,
Je lis 4
1.000000
2.000000
3.000000
4.000000
5,6,7,8,
5,6,7,8,11,12,13,14,
Je lis tout 8
5.000000
6.000000
7.000000
8.000000
11.000000
12.000000
13.000000
14.000000
					

Les arbres

Définitions

Un arbre est une structure de données composée de noeuds, où chaque noeud contient une structure de données et possède plusieurs suivants (branches) vers d'autres noeuds. Les derniers noeuds qui ne possèdent pas de branches sont appelés "feuilles". Le premier noeud est la racine.

Un arbre où chaque noeud possède au maximum deux branches est un arbre binaire.

On propose d'implémenter ces noeuds en utilisant une structure de données dynamique, où chaque élément est une structure de données composée de la données et de deux pointeurs vers les deux suivants nommés gauche et droite.

Dans le cas présent, on a un arbre binaire avec un noeud racine suivi de 2 noeuds, chacun suivi de 4 feuilles.

Parcours d'un arbre binaire

Le parcours d'un arbre n'est pas unique, il existe plusieurs méthodes pour parcourir tous les noeuds d'un arbre. Ces méthodes utilisent toutes la récursivité, à chaque noeud on parcours à nouveau un arbre.

Parmi ces algorithmes de parcours, on va en présenter 3 qui se distinguent par la position du traitement de la donnée par rapport aux parcours des suivants : préfixe, infixe ou postfixe.

Parcours préfixe

Traitement avant les parcours

Prefixe
Paramètres en entrée : noeud
Debut traitement
Si noeud non nul Alors
	Traiter donnees;
	Prefixe(noeud gauche);
	Prefixe(noeud droit);
FinSi
Fin traitement
				

Parcours infixe

Traitement entre les parcours

Infixe
Paramètres en entrée : noeud
Debut traitement
Si noeud non nul Alors
	Infixe(noeud gauche);
	Traiter donnees;
	Infixe(noeud droit);
FinSi
Fin traitement
				

Parcours postfixe

Traitement après les parcours

Postfixe
Paramètres en entrée : noeud
Debut traitement
Si noeud non nul Alors
	Postfixe(noeud gauche);
	Postfixe(noeud droit);
	Traiter donnees;
FinSi
Fin traitement
				

Exemple avec des noeuds d'entiers.

Résultat des différents parcours de cet arbre avec le traitement des données qui consiste à afficher l'entier contenu dans le noeud.

prefixe
1 2 4 5 3 6 7 
infixe
4 2 5 1 6 3 7 
postfixe
4 5 2 6 7 3 1 
				

Fichier de prototypes arbrebinaire.h


#ifndef __ARBREBINAIRE_H
#define __ARBREBINAIRE_H

typedef struct s_noeud {
	int id;
	struct s_noeud *gauche;
	struct s_noeud *droite ;
} Tnoeud;

typedef Tnoeud *Tnoeud_ptr;

Tnoeud_ptr nouvelarbre(int );
Tnoeud_ptr addnoeudGauche(Tnoeud_ptr *,int );
Tnoeud_ptr addnoeudDroit(Tnoeud_ptr *,int );
void supprimearbre(Tnoeud_ptr *);
void prefixe(Tnoeud_ptr ) ;
void infixe(Tnoeud_ptr ) ;
void postfixe(Tnoeud_ptr);

#endif
				

La fonction nouvelarbre crée un nouveau noeud racine avec la valeur de l'entier et deux suivants gauche et droite NULL

La fonction addnoeudGauche crée un nouveau noeud avec la valeur de l'entier, les deux suivants à NULL et le lie au noeud courant à gauche en affectant l'adresse du nouveau noeud au pointeur gauche du noeud courant.

La fonction addnoeudDroit fait la même chose en liant au noeud courant à droite.

La fonction supprimearbre supprime les noeuds à partir d'un noeud de référence en libérant la mémoire allouée. Cette fonction utilise la récursivité et le parcours postfixe où le traitement consiste à libérer la mémoire allouée au noeud.

Les fonctions de parcours respectent les algorithmes avec comme traitement l'affichage de l'entier du noeud courant.

Fichier arbrebinaire.c


#include <stdlib.h>
#include <stdio.h>
#include "arbrebinaire.h"

Tnoeud_ptr nouvelarbre(int id) {
	Tnoeud_ptr noeud = (Tnoeud_ptr)malloc(sizeof(Tnoeud));
	if (noeud != NULL) {
		noeud->id = id;
		noeud->gauche = NULL ;
		noeud->droite = NULL ;
	}
	return noeud;
}

Tnoeud_ptr addnoeudGauche(Tnoeud_ptr *courant,int id) {
	Tnoeud_ptr noeud = (Tnoeud_ptr)malloc(sizeof(Tnoeud));
	if (noeud != NULL) {
		noeud->id = id;
		noeud->gauche = NULL ;
		noeud->droite = NULL ;
	}
	(*courant)->gauche = noeud ;
	return noeud ;
}

Tnoeud_ptr addnoeudDroit(Tnoeud_ptr *courant,int id) {
	Tnoeud_ptr noeud = (Tnoeud_ptr)malloc(sizeof(Tnoeud));
	if (noeud != NULL) {
		noeud->id = id;
		noeud->gauche = NULL ;
		noeud->droite = NULL ;
	}
	(*courant)->droite = noeud ;
	return noeud;
}

void supprimearbre(Tnoeud_ptr *noeud) {
	if (*noeud != NULL) {
		if ((*noeud)->gauche != NULL) {
			supprimearbre(&(*noeud)->gauche);
		}
		if ((*noeud)->droite != NULL) {
			supprimearbre(&(*noeud)->droite);
		}
		if (((*noeud)->gauche == NULL)&&(((*noeud)->droite == NULL))) {
			free(*noeud);
		}
	}
}

void prefixe(Tnoeud_ptr noeud) {
	if (noeud != NULL) {
		printf("%d ",noeud->id);
		prefixe(noeud->gauche);
		prefixe(noeud->droite);
	}
}

void infixe(Tnoeud_ptr noeud) {
	if (noeud != NULL) {
		infixe(noeud->gauche);
		printf("%d ",noeud->id);
		infixe(noeud->droite);
	}	
}

void postfixe(Tnoeud_ptr noeud) {
	if (noeud != NULL) {
		postfixe(noeud->gauche);
		postfixe(noeud->droite);
		printf("%d ",noeud->id);
	}	
}
				
Voir un exemple de programme de test du parcours de l'arbre

Fichier de test


#include <stdlib.h>
#include <stdio.h<
#include "arbrebinaire.h"

int main(int argc, char **argv) {
	
	Tnoeud_ptr racine ;
	Tnoeud_ptr noeud1 ,noeud2;

	racine = nouvelarbre(1);
	noeud1 = addnoeudGauche(&racine,2);
	addnoeudGauche(&noeud1,4);
	addnoeudDroit(&noeud1,5);
	noeud2 = addnoeudDroit(&racine,3);
	addnoeudGauche(&noeud2,6);
	addnoeudDroit(&noeud2,7);
	printf("prefixe\n");
	prefixe(racine);
	printf("\ninfixe\n");
	infixe(racine);
	printf("\npostfixe\n");
	postfixe(racine);
	printf("\n");
	supprimearbre(&racine);
	return EXIT_SUCCESS;
}
					

Le programme ce test crée l'arbre de l'exemple, puis affiche le contenu de chaque noeud en utilisant les trois parcours.

Exemple avec la calculatrice

Cet exemple montre l'enregistrement d'une expression de calcul avec parenthèses.

L'arbre représente l'expression de calcul (2*(3+4)). Un noeud dont la donnée est une opération ouvre une nouvelle parenthèse. La fin du parcours des suivants d'un noeud ferme la parenthèse.

On va appliquer les différentes méthodes de parcours de cet arbre et afficher le résultat.

prefixe
* 2 + 3 4 
infixe
2 * 3 + 4 
postfixe
2 3 4 + * 				
				

Si on ajoute des parenthèses au parcours infixe, on obtient l'expression avec parenthèses.

La méthode postfixe fournit une expression qui est celle des calculatrices RPN. Il est donc facile de passer d'une expression avec parenthèses à une expression RPN.

L'exemple suivant affiche l'expression avec parenthèses à partir de l'arbre en utilisant le parcours infixe qui inclut l'ajout de parenthèses.

Fichier de prototypes arbrebinaire.h


#ifndef __ARBREBINAIRE_H
#define __ARBREBINAIRE_H

typedef struct s_noeud {
	void *datas;
	size_t taille ;
	struct s_noeud *gauche;
	struct s_noeud *droite ;
} Tnoeud;

typedef Tnoeud *Tnoeud_ptr;

Tnoeud_ptr nouvelarbre(void *datas,int taille);
Tnoeud_ptr addnoeudGauche(Tnoeud_ptr *,void *,int );
Tnoeud_ptr addnoeudDroit(Tnoeud_ptr *,void *,int );
void supprimearbre(Tnoeud_ptr *);
void arbreversexpression(Tnoeud_ptr,char *);

#endif
				

La structure de données d'un noeud est un pointeur qui nécessite une allocation dynamique. Cela permet de stocker une chaîne de caractères. Pour les fonctions de gestion des noeuds, on ajoute l'allocation dynamique et la copie des données, comme cela a déjà été fait avec les listes chaînées. Ce qui nécessite d'ajouter le paramètre de taille des données. La valeur de la taille inclut le zéro de fin de chaîne. De même la libération de la mémoire doit également libérer la mémoire allouée aux données avant de libérer la mémoire allouée au noeud.

La fonction arbreversexpression stocke dans la chaîne de caractères transmise en paramètre l'expression avec parenthèses. Cette fonction doit définir si la donnée est un opérateur ou bien une valeur numérique. Avec cette version simplifiée, on considère que si aucun des deux pointeurs gauche et droite n'est nul, alors on a un opérateur, dans le cas contraire on a une valeur numérique.

Fichier arbrebinaire.c


#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "arbrebinaire.h"

Tnoeud_ptr nouvelarbre(void *datas,int taille) {
	Tnoeud_ptr noeud = (Tnoeud_ptr)malloc(sizeof(Tnoeud));
	if (noeud != NULL) {
		noeud->datas = malloc(taille);
		memcpy(noeud->datas,datas,taille);
		noeud->taille = taille ;
		noeud->gauche = NULL ;
		noeud->droite = NULL ;
	}
	return noeud;
}

Tnoeud_ptr addnoeudGauche(Tnoeud_ptr *courant,void *datas,int taille) {
	Tnoeud_ptr noeud = (Tnoeud_ptr)malloc(sizeof(Tnoeud));
	if (noeud != NULL) {
		noeud->datas = malloc(taille);
		memcpy(noeud->datas,datas,taille);
		noeud->taille = taille ;
		noeud->gauche = NULL ;
		noeud->droite = NULL ;
	}
	(*courant)->gauche = noeud ;
	return noeud ;
}

Tnoeud_ptr addnoeudDroit(Tnoeud_ptr *courant,void *datas,int taille) {
	Tnoeud_ptr noeud = (Tnoeud_ptr)malloc(sizeof(Tnoeud));
	if (noeud != NULL) {
		noeud->datas = malloc(taille);
		memcpy(noeud->datas,datas,taille);
		noeud->taille = taille ;
		noeud->gauche = NULL ;
		noeud->droite = NULL ;
	}
	(*courant)->droite = noeud ;
	return noeud;
}

void supprimearbre(Tnoeud_ptr *noeud) {
	if (*noeud != NULL) {
		if ((*noeud)->gauche != NULL) {
			supprimearbre(&(*noeud)->gauche);
		}
		if ((*noeud)->droite != NULL) {
			supprimearbre(&(*noeud)->droite);
		}
		if (((*noeud)->gauche == NULL)&&(((*noeud)->droite == NULL))) {
			free((*noeud)->datas);
			free(*noeud);
		}
	}
}

void arbreversexpression(Tnoeud_ptr noeud,char *expression) {
	Tnoeud_ptr p = noeud ;
	if (p != NULL) {
		if ((p->gauche != NULL)&&(p->droite != NULL)) {
			strcat(expression,"(");
			arbreversexpression(p->gauche,expression);
			strcat(expression,p->datas);
			arbreversexpression(p->droite,expression);
			strcat(expression,")");
		}
		else {
			strcat(expression,p->datas);
		}
	}
}
				
Voir un exemple de programme de test de traitement des expressions

Fichier de test


#include <stdlib.h>
#include <stdio.h>
#include "arbrebinaire.h"

int main(int argc, char **argv) {
	
	Tnoeud_ptr racine ;
	Tnoeud_ptr noeud1 ;
	char expression[20] = "";

	racine = nouvelarbre("*",2);
	addnoeudGauche(&racine,"2",2);
	noeud1 = addnoeudDroit(&racine,"+",2);
	addnoeudGauche(&noeud1,"3",2);
	addnoeudDroit(&noeud1,"4",2);
	arbreversexpression(racine,expression);
	printf("expression : %s\n",expression);
	supprimearbre(&racine);
	return EXIT_SUCCESS;
}
					

La taille de chaque valeur transmise correspond au nombre de caractères + 1 pour inclure le 0 de fin de chaîne.

Le résultat du programme est :

expression : (2*(3+4))