Les structures de données en C

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.

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 ;
		}
	}
}
				

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.

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 ;		
	}
}
				

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);
}
				

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;
}
				

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);
}

				

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;
}
				

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 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
				

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);
	}	
}
				

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.

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);
		}
	}
}
				

• Calcul et technologies
• Un peu de géométrie
• Plus de mathématiques
• Jeux mathématiques
• Systèmes électroniques
• Réseaux et télécommunications