Algorithmique et Structures de Données

Mini-projet

Le mini-projet du cours Algorithmique et Structures de Données (année 2024/2025). Les ressources sont disponibles ci-dessous :

Side-project-ADS-2024

Cliquez sur les deux images ci-dessous pour les télécharger :

---

Opérations sur les pointeurs/tableaux

Exercice 0 : (pointeurs sous forme de tableaux et leur arithmétique)

Ecrire un programme qui lit deux tableaux d’entiers A et B et leurs dimensions N et M au clavier et qui ajoute les éléments de B à la fin de A. Utiliser deux pointeurs PA et PB pour le transfert et afficher le tableau résultant A.

Solution

---

Structure de données Liste

Exercice 1 : (listes simplement chaînées)

Nous proposons maintenant une nouvelle structure de liste chainée il s’agit de suivre la liste des produits achetés par un client au niveau d’une supérette.

Chaque élément de la liste est composé des champs suivants :

code_prod(9 alphanumérique),
Désignation(50 car),
UM (3 car), // Unité de mesure (U, Kg, L, bout, cart, …)
PUA_HT(réel), // Prix Unitaire d’Achat Hors Taxe
Qte(réel), // Quantité achetée
TVA(9% ou 21%) // Taxe sur Valeur Ajoutée

Ce programme affichera le menu suivant :

1. AJOUTER des produits Au début de la liste
2. AFFICHER la liste des produits achetés
3. Afficher le nombre total des produits achetés ainsi que les montants total HT, total TVA et total TTC(net à payé)
4. Demander au client le paiement et calculer la différence entre le montant payé et le net à payé
5. SUPPRIMER des produits
6. Afficher le prix max et le prix min
7. VIDER la liste.
8. ARRÊT du programme.

Et effectuera le traitement (fonctions/ procédures) correspondant au choix effectué.

Solution

Exo1-serie2

---

Exersise 2 : (chaînage arrière d’une liste doublement chaînée)

Concevoir un algorithme qui réalise le chaînage arrière d’une liste doublement chaînée dont seul le chaînage avant a été effectué.

Solution

Exo2-serie2

---

Exercice 3 : (liste doublement chaînée)

Insérer et supprimer dans une liste doublement chaînée :

• Écrire un algorithme d’insertion dans une liste doublement chaînée.
• Écrire un algorithme de suppression dans une liste doublement chaînée.

Solution

Exo3-serie2

---

Exercice 4 : (liste de listes simplement chaînées)

Fonction de calcul de moyenne des étudiants :

Le département dans lequel vous êtes inscrit souhaite gérer les notes de ses étudiants. Les étudiants ont pour identifiant leur numéro d’étudiant. Ils ont un nom et un prénom. Ces informations sont stockées dans une liste chaînée dont chaque élément comporte aussi un champ moy pour la moyenne de l’étudiant et un champ eval qui est un pointeur sur sa liste de notes. La liste de notes de chaque étudiant est aussi une liste chaînée dont la tête est le champ eval de la cellule de l’étudiant. On dispose des déclarations suivantes :

Etudiant = Structure
No: Ch10
Nom: Ch30
Prenom: Ch30
moy: Nb
eval: Pn
suivatn: Pe

Note = Structure
note: Nb
coeff : Ent
suivant: Pn

Types :
Ch10 = Chaine de 10 caractères
Ch30 = Chaine de 30 caractères
Ent = entier
Nb = réel
Pe = *Etudiant
Pn = *Note

Questions:

Faire un schéma de cette structure.

On suppose que tous les champs de la liste des étudiants sont remplis sauf le champ moy. On suppose que toutes les notes des étudiants et tous les coefficients sont remplis.

Écrire une procédure moyennesEtudiants qui parcourt la liste des étudiants, et qui calcule et met à jour le champ moy de chaque étudiant à l’aide de la liste des notes sur laquelle pointe le champ eval. La procédure moyennesEtudiants prend en paramètre la tête de la liste des étudiants.

Solution

Exo4-serie2

---

Exercice 5 : (listes doublement chaînées circulaires)

implémenter une liste doublement chaînée circulaire en c++. La liste doit permettre les opérations suivantes :

1. Ajouter un élément à la fin de la liste.
2. Supprimer un élément de la liste.
3. Afficher tous les éléments de la liste.
4. Rechercher un élément dans la liste.

Solution

Exo5-serie2

---

Structure de données Pile et File

Exercice 1 : (création d’une pile avec ses fonctions)

On vous demande d’implémenter (par liste), une Pile permettant de représenter des piles d’entiers. Pour cela vous développerez les fonctions et opérateurs de base permettant de manipuler les piles, à savoir:

• La fonction permettant de créer une pile vide.
• bool vide() : teste de vacuité.
• int hauteur() : retourne la hauteur de la pile.
• void empiler(int n) : fonction permettant d’empiler un entier au sommet de la pile.
• void depiler() : enlève l’élément au sommet de la pile.
• void remplacer(int n) : remplace le sommet de la pile par n.
• int sommet() : retourne l’élément au sommet de la pile.

Solution

Exo1-serie3

---

Exercice 2 : (création d’une file avec ses fonctions)

On vous demande d’implémenter (dynamiquement : par liste) une File permettant de représenter des files d’entiers. Pour cela vous développerez les fonctions et opérateurs de base permettant de manipuler les files, à savoir :

• La structure permettant de créer une file vide.
• bool vide() : teste de vacuité.
• int longueur() : retourne la longueur de la file.
• void adjq(int n) : adjonction en queue d’un entier n. // Emfiler
• void supt() : suppression de l’élément en tête de la file. // Defiler
• int tete() : retourne l’élément en tête de la file.

Solution

Exo2-serie3

---

Exercice 3 : (Inverser une pile et une file en préservant les originaux)

Concevoir deux algorithmes, qui créent respectivement :

• la file inverse d’une file .
• la pile inverse d’une pile.

Ces deux algorithmes doivent restituer leur entrée inchangée.

Solution

Exo3-serie3

---

Exercice 4 : (Inverser une pile)

Écrire un algorithme utilisant une pile (implémentée sous forme de liste chaînée) qui affiche une liste chaînée d’entiers à l’envers.

Solution

Exo4-serie3

---

Exercice 5 : (vérification de parenthèses)

Un fichier texte peut contenir des parenthèses ( ), des crochets [ ], et des accolades { }. Ces éléments peuvent être imbriqués les uns dans les autres (exemple : {a*(b+c[-d])[{e- f }(-g)]} )

Écrire une fonction qui parcourt le fichier texte et détermine si le fichier est correctement parenthèses, c’est-à-dire si toutes les parenthèses, crochets, etc. sont bien refermés par un caractère du même type, et si les parenthèses, crochets et accolades sont correctement imbriqués. Exemple de fichier incorrect : ({)}.

NB : Pour l’exercice n°5 le fichier texte peut être remplacé par une chaine de caractères si les étudiants(es) ne maitrisent pas la notion et l’utilisation des fichiers.

Solution

Exo5-serie3

---

Structure de données Arbre binaire

Exercice 1 : (vocabulaire des arbres)

exo1-serie4

---

Exercice 2 : (arbres binaires sous forme de tableaux)

Soit le tableau suivant qui représente un arbre binaire T en triplets (info, gauche, droit) :

23	2	3	5	7	11	13	37	41	19
-1	4	3	-1	-1	9	-1	8	6	-1
-1	5	0	-1	-1-	-1	2	1	-1	-1

La première colonne (indice 0) représente le nœud dont le champ info est 23 (valeur du nœud), le champ gauche est -1 (indice du fils gauche) et le champ droit est -1 (indice du fils droit), La seconde colonne (indice 1) représente le nœud dont le champ info est 2, le champ gauche est 4 et le champ droit est 5, et ainsi de suite. La valeur (-1) indique l’absence d’un fils gauche ou droit.

1. Dessiner l’arbre binaire T et donner sa taille.
2. Donner le code C pour représenter l’arbre T de cette manière.
3. Écrire une fonction qui détermine la racine de l’arbre T.
4. Écrire une procédure qui liste toutes les feuilles de l’arbre T.
5. Donner le résultat du parcours de l’arbre T :

I : en ordre infixé,
ii : en ordre préfixé, et
iii : en ordre postfixé.

Solution

exo2-serie4

---

Exercice 3 : (implémenter les arbres binaires et leurs fonctions)

dans un arbre binaire écrire (l’algorithme récursif) :

1. une fonction qui calcule le nombre de noeuds.
2. une fonction qui fait la somme des valeurs contenues.
3. une fonction qui calcule le nombre de feuilles.
4. une fonction qui calcule la hauteur.
5. tester si un arbre est équilibré.
6. fonction de parcours par niveau (en largeur)

Solution

exo3-serie4

---

Exercice 4 : (évaluation des expressions arithmétiques)

a. Donner une fonction récursive pour évaluer une expression arithmétique sous la forme d’un arbre binaire.
b. Une autre pour imprimer l’expression infixe parenthésée.

Solution

exo4-serie4

---

Exercice 5 : (arbre binaire de recherche)

1. Dessiner l’arbre binaire de recherche obtenu en insérant les éléments de la liste suivante dans leur ordre d’arrivée: 30, 40, 23, 58, 48, 26, 11, 13, 20
2. Donner le résultat des parcours préfixe, infixe et postfixe de l’arbre précédent
3. Donner l’arbre précédent après la suppression des clés suivantes : 48 puis 23.
4. Donner l’arbre précédent (avant la suppression) après l’ajout des clés suivantes : 60 puis 17.

Solution

exo5-serie4

---