Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Grand Devoir 1 Structures de données et algorithmes Piles, Files d’attente et L

Grand Devoir 1 Structures de données et algorithmes Piles, Files d’attente et Listes (Stacks, Queues, Lists) Mentions générales • Pour ce projet vous allez travailler par équipes de 2 personnes (ou seuls ). • Le projet est à rendre sur la plateforme Moodle (fils.curs.pub.ro). S'il y a des problèmes lors du téléchargement vers ou depuis la plateforme, contactez par mail votre assistant des travaux pratiques : Iulia Stanica - iulia.stanica@gmail.com • Le projet est à rendre au plus tard le 12.04.2020, à 23:59. Aucun retard ne sera accepté. • Vous recevrez des questions concernant votre solution durant la séance suivante du TP, sur Microsoft Teams. • La rendue finale du projet comportera une archive nommée Etudiant1Nom_Etudiant1Prenom_ Etudiant2Nom_Etudiant2Prenom _HW1 avec: o les fichiers du code source (.cpp et .h) et non pas des fichiers objets (i.e. *.o) ou des fichiers exécutables (i.e. *.exe) ou des fichiers des projets codeblocks (.cbp) ; SVP mettez chaque exercice dans un dossier séparé ! o un fichier de type README où vous allez spécifier toutes les fonctionnalités de votre projet, avec les instructions pour les employer. Au contraire, s'il y aura des exigences qui ne seront pas fonctionnelles, vous allez proposer des idées pour une solution possible (et obtenir des points supplémentaires). • Pour toute question concernant le sujet du projet ou les exigences, envoyer un mail à vos assistants ou utiliser le forum de la plateforme moodle • Attention : notre équipe utilise des logiciels détectant le plagiat (Moss du Stanford). Dans le cas malheureux de plagiat, le projet sera noté par un 0 (zéro). ! Remarque : Les files et les piles utilisées seront représentées par des fichiers en-tête (headers), en utilisant des chablons (<template>). Tâches : 1. Pile (Stack) (3p) Lorsqu'une expression telle que A*B+C/D est donnée, une personne normale peut simplement résoudre et comprendre l'ordre correct des opérations. Malheureusement, les ordinateurs ne peuvent pas simplement comprendre cela; ainsi, ils utilisent quelque chose appelé notation préfixe. Étant donné n'importe quelle expression infixe, nous pouvons obtenir le format préfix équivalent. Votre tâche consiste à utiliser des piles pour: a) Convertir n'importe quelle notation infixe donnée en notation préfixe. En plus, étant donné toute notation préfixe, affichez la notation infixe. Votre algorithme devrait également fonctionner avec les 3 types de parenthèses (, [, { (2p) Ex: Input : Infix : {(A+B)*[C*(D-E)]-F}/G Output : Prefix: /-*+AB*C-DEFG ET vice-versa: Input : Prefix : *+AB-CD Output : Infix : ((A+B)*(C-D)) b) Donnant n'importe quelle paire de (variable, valeur) et une expression infixe ou préfixe, montrer le résultat final après le calcul de l'expression. (1p) Ex: (A,2) (B,2) (C,5) (D,1) + * A B/ C D Resultat: 9 2. File d’attente (Queue) (3.5p) Lara Croft, la plus grande archéologue et chasseuse de trésors du monde, a besoin de votre aide pour résoudre l'une des énigmes des notes mystérieuses de son père. La clé de sa nouvelle aventure est enfermée dans le bureau de son père et elle doit trouver le code pour le déverrouiller. Le message de son père dit que: Tous les mythes sont les fondements de la réalité. Il suffit de continuer à les compter. Lara s'est souvenue d'un jeu auquel elle jouait lorsqu'elle était petite, où elle comptait le nombre d'occurrences de chaque caractère et leur associe des codes uniques, en fonction de leur fréquence d'occurrence. Ces codes sont écrits dans un système binaire, à partir de codes avec un bit pour la lettre la plus fréquente. Tous les codes binaires sont uniques pour chaque caractère et ils augmentent avec la diminution de la fréquence. E.g. Densité des caractères: E – 10 T – 8 S – 8 L – 6 O – 5 . - 2 etc. Les caractères ont les codes suivants: E – 0 T – 1 S – 10 L – 11 O – 100 Attention! 0 et 00 (ou 1 et 01) représentent le même code! 1. Stockez les caractères et leurs fréquences dans une file d'attente prioritaire développée à l'aide d'un tableau. La file d'attente prioritaire doit avoir les méthodes suivantes (2p): a. enqueue (element) - ajoute un élément à la file d'attente prioritaire b. deqeueueHighestPriority() - supprime le caractère avec le plus grand nombre d'occurrences c. getHighestPriority() - affiche le personnage avec le plus grand nombre d'occurrences ET sa fréquence 2. Découvrez le code binaire de chacun des caractères du message ci-dessus en utilisant la file d'attente prioritaire que vous avez créée précédemment (1p). 3. Traduisez le message en additionnant les chiffres des codes des lettres (0.5p). Ex : Si T – 1, O – 100, U – 111, S – 10, « Tous » représente 110011110 et le code final est 6. Obs: Les files d'attente prioritaires (Priority Queues) sont bien connues en programmation, en tant que type spécial de file d'attente dans lequel chaque élément a une priorité associée et est servi en fonction de sa priorité. Si des éléments d’une même priorité apparaissent, ils sont servis selon leur ordre dans la file d'attente (ou dans notre cas, pour les lettres, selon l'ordre lexicographique). Les lettres majuscules et minuscules doivent être comptées ensemble. 3. Listes (3.5p) Créez une structure de données qui contient une liste liée de tableaux (0.5p): chaque nœud de la liste contient un tableau. La dimension maximale d'un tableau est de 5. Pour implémenter cette nouvelle structure de données, vous devez créer une classe, ArrayedList, avec les méthodes suivantes: • ArrayedList () • void add (valeur T): une nouvelle valeur est toujours ajoutée à la dernière position vide du dernier tableau (à la fin de la liste, s’il y a des positions vides). Si ce tableau est plein, un nouvel élément est ajouté à la fin de la liste contenant un nouveau tableau et notre valeur est ajoutée à ce nouveau tableau et ainsi de suite. (1p) • void remove (int i): nous pouvons supprimer une valeur de la position i de la liste, mais nous ne pouvons pas laisser de positions vides dans nos tableaux. Ainsi, lorsque nous supprimons un élément, nous devons déplacer tous les éléments correspondants vers la gauche, afin de ne pas avoir de positions vides dans nos tableaux. (1p) • void display (): nous affichons la liste: chaque élément (tableau) sur une ligne différente. (0.5p) • T getElement (i): on retourne l'élément sur la position i (0.5p) Ex : Supposons que la liste est: Head = | 6 7 1 4 | → NULL - dimension de la liste = 4 add (8) Liste devient Head = | 6 7 1 4 8 | → NULL – dimension de la liste = 5 add (5) Liste devient Head = | 6 7 1 4 8 | → | 5 | → NULL - dimension de la liste = 6 add (2) Liste devient Head = | 6 7 1 4 8 | → | 5 2 | → NULL - dimension de la liste = 7 display () 6 7 1 4 8 5 2 getElement (5) 5 getElement (0) 6 remove (0) Liste devient Head = | 7 1 4 8 5 | → | 2 | → NULL - dimension de la liste = 6 remove (1) Liste devient Head = | 7 4 8 5 2 | → NULL - dimension de la liste = 5 remove (5) ERREUR uploads/Ingenierie_Lourd/ grand-devoir-1-pdf.pdf