Théorie des graphes : Analyse et conception d'un programme de gestion des étudian
Télécharger PDFUniversité Cadi Ayyad
Faculté Polydisciplinaire de Safi
Filière SMI/SMA – Structures de Données (2019−2020)
Exercice I : Liste et structures
On considère les structures suivantes pour caractériser un étudiant :
typedef struct {
int j;
int m;
int a;
} date;
typedef struct {
int CNE;
char nom[25];
date ddn;
} etudiant;
typedef struct cellule {
etudiant val;
struct cellule *suivant;
} *ListeEtd;
Fonctions à programmer
1. SaisieDate et AfficheDate pour saisir et afficher une date.
2. SaisieEtudiant et AfficheEtudiant pour saisir et afficher un étudiant.
3. AjouterEtudiant pour ajouter un étudiant à la fin de la liste.
4. ChercherEtudiant pour chercher un étudiant.
5. SupprimerEtudiant pour supprimer un étudiant.
6. AfficheListeEtudiant pour afficher la liste des étudiants.
Exercice II : Manipulation d’un ensemble d’entiers
Un ensemble mathématique est un groupement d’objets distincts, appelés éléments de cet ensemble. La théorie des ensembles étudie les propriétés et les opérations sur des ensembles (appartenance, inclusion, réunion, etc.). Elle représente une branche essentielle des mathématiques.
Dans ce problème, on se propose de représenter des ensembles finis d’entiers strictement positifs par des listes chaînées définies en langage C comme suit :
typedef struct ens {
int nombre; // nombre entier strictement positif
struct ens *suivant; // adresse de l'élément suivant
} *EnsembleListe;
Fonctions à programmer
1. InsereEnDebut pour insérer une valeur au début de l’ensemble.
2. InsereEnFin pour insérer une valeur à la fin de l’ensemble.
3. SupprimerElt pour supprimer un élément de l’ensemble.
4. verifierEnsemble qui retourne 1 si les éléments sont distincts et 0 sinon.
5. appartientEnsemble qui retourne 1 si un élément appartient à un ensemble et 0 sinon.
6. Inclusion pour vérifier si un ensemble est inclus dans un autre.
7. Union pour fusionner deux ensembles.
8. Intersection pour trouver les éléments communs entre deux ensembles.
Exercice III : Liste doublement chaînée
On dispose d’une liste doublement chaînée contenant des entiers classés dans l’ordre décroissant. La structure de données utilisée pour représenter un élément de la chaîne est la suivante :
typedef struct cellule {
int data;
struct cellule *svt; // pointeur vers l'élément suivant
struct cellule *prec; // pointeur vers l'élément précédent
} *PtrCell;
Fonctions à programmer
1. Insert pour insérer un nouvel entier dans la liste en respectant le classement. Si cet entier est déjà présent, la fonction renvoie un message d’erreur.
2. Suppr pour rechercher et éliminer un entier dans la liste. Si cet entier n’existe pas, la fonction renvoie un message d’erreur.
3. Affiche pour afficher les éléments de la liste.
FAQ
1. Qu’est-ce qu’une liste chaînée en C ?
Une liste chaînée est une structure de données linéaire composée de nœuds (cellules) où chaque nœud contient une valeur et un pointeur vers le nœud suivant. Elle permet de stocker des éléments dynamiquement sans contrainte de taille fixe.
2. Comment vérifier l’appartenance d’un élément à un ensemble ?
La fonction appartientEnsemble parcourt la liste chaînée de l’ensemble et compare chaque élément avec la valeur recherchée. Si elle est trouvée, elle retourne 1 ; sinon, elle retourne 0.
3. Pourquoi utiliser un ordre décroissant dans une liste doublement chaînée ?
L’ordre décroissant facilite la recherche et l’insertion d’éléments tout en maintenant un classement cohérent. Cela permet d’optimiser certaines opérations comme la suppression ou l’ajout de nouveaux éléments.