CI3 : L'armée de monstres
Sous prétexte de mettre en œuvre une fonctionnalité d'un petit jeu,
cet exercice a trois buts distincts.
Le premier but est d'apprendre à manipuler des structures de données.
Le second but est de concevoir des tableaux extensibles et des listes chaînées.
Ces structures de données classiques permettent de gérer des ensembles homogènes non bornés.
Le troisième but est de vous amener pas à pas vers une conception modulaire, qui
nous servira à introduire la programmation orientée objet dans les prochains cours.
Durée des exercices obligatoires : 2h en présentiel
Dans notre petit jeu, légèrement influencé par un triple A de 2016,
des joueurs se promènent dans le monde réel avec leur téléphone portable
pour capturer des monstres virtuels géolocalisés.
Ces monstres servent ensuite aux joueurs à conquérir des lieux spéciaux, ce qui permet aux joueurs d'interagir.
Le but de l'exercice n'est pas de mettre entièrement le jeu en œuvre,
mais uniquement la partie du jeu qui gère les armées de monstres.
Cette mise en œuvre est rendue difficile, car les scénaristes fantaisistes du jeu
ont prévu que chaque joueur puisse acquérir un nombre non borné de monstres.
Pour cette raison, utiliser un tableau de taille fixe pour stocker les monstres
est impossible.
Nous allons donc étudier des structures de données permettant de traiter un nombre
non borné d'éléments.
L'exercice est séparé en quatre parties :
- Exercice 1 : obligatoire (facile, ∼40mn)
- Exercice 2 : obligatoire (moyen, ∼1h)
- Exercice 3 : obligatoire (facile, ∼15mn)
- Exercice 4 : entraînement (difficile, ∼45mn)
- Exercice 5 : entraînement (difficile)
- Dans une première partie, nous concevons la structure de données qui représente un monstre.
- Dans une seconde partie, nous utilisons des tableaux extensibles pour stocker nos monstres. Un tableau extensible est une structure de données reposant sur un tableau, mais permettant de réallouer dynamiquement le tableau de façon à l'étendre. Dans cette partie, ainsi que dans la précédente, nous concevons notre application de manière non modulaire, c'est-à-dire que nous mettons en vrac l'ensemble des méthodes de notre programme dans la même classe.
- Dans une troisième partie, nous constatons que cette conception non modulaire ne permet pas de réutiliser le code. Pour cette raison, nous modifions le design de notre application.
- Dans une quatrième partie, nous observons qu'un tableau extensible n'est pas la structure de données la plus efficace en termes de performance si le nombre de monstres devient grand. Pour cette raison, nous modifions notre application de façon à utiliser des listes chaînées pour stocker nos monstres.
Pour les étudiants qui ont déjà l'habitude de la programmation, certains choix de conception
proposés dans cet exercice pourront vous paraître inadéquats. Ces choix sont effectivement
inadéquats, mais visent à montrer aux étudiants qui n'ont pas encore l'habitude de programmer
qu'il faut concevoir une application de façon modulaire.
Les monstres (∼45mn – facile – obligatoire)
Pour commencer, créez un projet nommé monsters contenant
une unique classe nommée Pokedex avec une méthode main.
Créez une nouvelle classe nommée Monster et contenant les champs suivant :
- name : une chaîne de caractères donnant le nom du monstre.
- health : un entier donnant le nombre de points de vie du monstre. Lorsque ce nombre tombe à zéro, le monstre meurt.
Dans la méthode main, allouez un premier monstre que vous stockerez
dans une variable nommée aMonster.
Affectez le nom du monstre à "Pikachu", son nombre de points de vie
à 0, puis affichez le nom du monstre sur le terminal.
Vérifiez que votre programme affiche bien "Pikachu".
Dans la classe Pokedex, écrivez une méthode de classe createMonster
prenant en argument un nom et un nombre de points de vie. Cette méthode doit renvoyer
une référence vers une nouvelle instance de Monster initialisée de façon adéquate.
Supprimez le code qui alloue et initialise un monstre dans la méthode main.
Remplacez ce code par un appel à createMonster pour créer le monstre "Pikachu".
Vérifiez que votre programme affiche toujours "Pikachu".
Dans la classe Pokedex, écrivez une méthode displayMonster
prenant en paramètre un monstre.
Cette méthode doit afficher Monster<name>, où name
est le nom du monstre passé en paramètre.
Au lieu de directement afficher le champ name du monstre dans la méthode
main, utilisez displayMonster pour afficher votre monstre.
Vérifiez que Monster<Pikachu> est bien affiché sur le terminal.
On rappelle qu'il est possible de concaténer deux String avec un +.
On rappelle qu'il est possible de concaténer deux String avec un +.
Avant de mettre en œuvre la structure de données stockant une armée de monstres,
nous allons créer plusieurs monstres.
Remplacez la création et l'affichage de Pikachu par une boucle créant
et affichant 8 monstres dont les noms vont de Pikachu0 à
Pikachu7.
Vérifiez que votre programme affiche bien vos 8 Pikachus dans la console et que leurs noms
sont corrects.
Conservez bien le code qui crée les 8 Pikachus jusqu'à la fin de l'exercice,
car vous en aurez besoin dans les questions suivantes.
Félicitations, vous venez de créer vos premiers objets !
Le tableau extensible (∼60mn – moyen – obligatoire)
Dans cette partie nous utilisons des tableaux extensibles pour stocker nos monstres. Dans un premier temps, avant de nous occuper de rendre nos tableaux extensibles, nous commençons par utiliser des tableaux à taille fixe.
Le principe, à cette étape, est d'allouer un tableau suffisamment grand pour accueillir nos 8 monstres, et d'utiliser un indice indiquant le niveau de remplissage du tableau. Initialement cet indice d'insertion vaut 0. L'ajout du premier monstre se fait donc à cet indice dans le tableau et l'indice d'insertion est augmenté de 1. De façon similaire, si l'indice d'insertion vaut N, l'ajout d'un nouveau monstre se fait dans la case d'indice N du tableau et l'indice d'insertion est ensuite augmenté de 1.
Au début de l'exercice, nous considérons que le tableau a toujours une taille suffisante pour accueillir un nouveau monstre, et nous ne nous préoccuperons de gérer le problème du débordement du tableau qu'à la fin de l'exercice.
Créez une classe nommée Army contenant deux champs : un tableau
de monstres nommé monsters et un entier nommé top indiquant
jusqu'à quel indice le tableau est occupé.
Écrivez aussi une méthode Army createArmy() dans la classe Pokedex.
Cette méthode doit (i) créer une instance de la classe Army,
(ii) allouer un tableau de taille 100 et l'affecter au champ monsters
de l'instance nouvellement créée, (iii) fixer la valeur initiale du champ top de l'instance
à 0 puisque l'armée est initialement vide, et (iv) renvoyer l'instance de la classe Army.
Écrivez, dans la classe Pokedex, une méthode nommée addMonster
prenant en argument une armée et un monstre et
permettant d'ajouter le monstre à l'armée.
Dans cette version préliminaire de addMonster, nous considérons que le tableau
monsters est suffisamment grand pour accueillir un nouveau monstre.
Pour tester addMonster, modifiez la boucle de la méthode main
qui crée les 8 Pikachus de façon à les ajouter à une armée au lieu de les afficher.
Écrivez, dans la classe Pokedex, une méthode nommée void displayArmy(Army army).
Cette méthode doit utiliser displayMonster pour afficher les monstres actuellement
enregistrés dans l'armée.
Vérifiez que votre programme est correct en appelant displayArmy à la fin de la méthode main.
Cet appel devrait afficher les 8 Pikachus qui se trouvent dans l'armée.
Techniquement, displayArmy doit afficher les monstres se trouvant aux indices allant de 0 (inclus) à top (non inclus) du tableau monsters.
Techniquement, displayArmy doit afficher les monstres se trouvant aux indices allant de 0 (inclus) à top (non inclus) du tableau monsters.
Nous pouvons maintenant rendre notre tableau de monstres extensible.
Dans createArmy, au lieu de créer un tableau à 100 entrées lorsque vous créez une armée,
créez un tableau à 4 entrées.
Lancez votre programme, que constatez-vous ?
Affichage d'un ArrayIndexOutOfBoundsException.
Cet affichage indique qu'une erreur s'est produite. Vous apprendrez dans la suite
du module que cette erreur s'appelle une exception. Pour le moment, il vous suffit
de savoir que vous pouvez cliquer sur le message pour trouver l'endroit dans le code qui a généré l'erreur.
Modifiez votre méthode addMonster de façon à traiter le cas où top
est plus grand ou égal que le taille du tableau de monstres. Dans ce cas, vous devez
allouer un tableau plus grand avant de recopier l'ancien contenu.
En détail, vous devez :
- Allouer un nouveau tableau nommé tmp. Ce tableau doit avoir une taille plus grande que le tableau de monstres original (par exemple, en doublant la taille du tableau original).
- Recopier le tableau original de monstres dans le tableau tmp.
- Affecter tmp au champ monsters de l'armée.
Pour les étudiants curieux, vous pouvez remarquer que vous n'avez jamais libéré la mémoire occupée
par l'ancien tableau de monstres.
En Java, le développeur n'a pas à se soucier de libérer la mémoire,
car l'environnement d'exécution s'en occupe pour le développeur.
Pour votre culture, le mécanisme qui libère la mémoire s'appelle
un ramasse-miette (garbage collector en anglais).
Ce mécanisme de libération automatique de la mémoire est présent dans la plupart
des langages modernes (Java, C#, Javascript, Python, Bash...), ce qui est une des raisons qui explique
le succès de ces langages.
Quelle est la complexité de addMonster dans le pire des cas ? Dans le meilleur des cas ?
Dans le pire des cas, il faut recréer un tableau deux fois plus grand et recopier tous les éléments.
La complexité est donc linéaire en la taille du tableau.
Dans le meilleur des cas, il n'y a presque rien à faire : la complexité est constante.
Dans le meilleur des cas, il n'y a presque rien à faire : la complexité est constante.
Avec cet exemple, nous nous rendons compte que la complexité dans le pire des cas n'est pas la plus adaptée pour
décrire la complexité en pratique du tableau extensible.
On a l'intuition que dans la majorité des cas, on aura une complexité constante. Pour mieux traduire la
véritable complexité, nous pouvons utiliser la complexité amortie. Il s'agit de la complexité moyenne quand on
appelle un grand nombre de fois une fonction. Quelle est la complexité amortie de addMonster ?
Considérons que nous avons fait N appels à la fonction addMonster. Estimons tout d'abord le
nombre de fois que nous avons du dupliquer la taille du tableau. Posons:
k est le nombre de fois que nous avons eu une duplication. On a:
La complexité due au nombre de duplications est donc:
La complexité des cas de non duplication est aussi lineaire. Au final, la complexité amortie est:
On aura une complexité amortie constante.
Conception modulaire (∼15mn – facile – obligatoire – exercice très important !)
Face au succès phénoménal de votre jeu, votre PDG, toujours aussi visionnaire, souhaite lancer une nouvelle franchise basée sur le film Black Sheep relatant les passionnantes aventures de moutons zombies. Dans ce nouveau jeu, un joueur se promène dans le monde réel et rencontre des moutons zombies géolocalisés qui se mettent à l'attaquer. Le joueur doit collectionner des pieux en argent pour vaincre les moutons zombies, ce qui lui rapporte des pièces lui permettant d'acheter des vêtements de luxe, le but du jeu étant d'avoir le personnage le plus chic du monde.
Souhaitant limiter le temps de développement,
votre géniale PDG vous suggère de réutiliser la structure de données représentant les monstres
du précédent jeu de façon à modéliser un mouton zombie.
Pour quelle raison le design non modulaire que nous avons choisi se prête mal à cette
opération ?
Car le code qui manipule les instances de Monster
est placé de façon aléatoire en vrac dans d'autres classes (ici Pokedex).
Au résultat, il est difficile d'extraire ce code pour le réutiliser.
Comme vous l'avez probablement compris, le design que nous avons utilisé limite la réutilisabilité du code.
Ce manque de réutilisabilité oblige à re-développer inutilement du code, ce qui
a un coût financier non négligeable.
Pour cette raison, avant de passer à la suite, nous redesignons pas à pas notre application de façon à pouvoir
en extraire facilement des parties pour d'autres projets.
Le problème fondamental du design que nous avons utilisé est que les méthodes qui manipulent
les monstres ou l'armée sont difficiles à identifier puisque ces dernières sont mises en vrac
dans la classe Pokedex.
Pour cette raison, nous allons redesigner notre application de façon modulaire :
nous allons mettre les méthodes qui manipulent les monstres dans la classe Monster
et les méthodes qui manipulent l'armée dans la classe Army.
Dans la suite de l'exercice, nous vous guidons en supposant que vous utilisez Eclipse ou
IntelliJ.
Si vous utilisez un autre logiciel de développement, vous devrez adapter l'énoncé à votre environnement
de développement qui, s'il est moderne et bien fait, devrait vous offrir sensiblement les mêmes
fonctionnalités.
Déplacer les méthodes createMonster et displayMonster
dans la classe Monster. Sous Eclipse, vous pouvez cliquer avec
le bouton de droite de la souris sur la méthode, aller dans le sous-menu Refactor
et sélectionner Move.
Sous IntelliJ, la procédure est la même, mais il vous faut choisir Move Members.. à la
fin.
De la même façon, déplacez createArmy, addMonster et displayArmy
dans la classe Army.
Relisez le code de votre main : vous devriez constater que maintenant,
par exemple, vous appelez Army.createArmy pour créer une armée puisque
la méthode createArmy se trouve dans la classe Army.
Maintenant que nos méthodes sont rangées à leur place, nous pouvons les renommer :
il est inutile que la méthode de création de monstre de la classe Monster
s'appelle createMonster, puisque le suffixe Monster devient maintenant
implicite.
Dans la classe Monster, renommez donc la méthode createMonster en create
et la méthode displayMonster en display.
Lorsque vous souhaitez renommer une méthode avec Eclipse ou IntelliJ, il vous suffit
de cliquer à droite sur le nom de la méthode, d'aller dans le sous-menu Refactor
et de sélectionner Rename.
De façon similaire, dans la classe Army, renommez la méthode createArmy
en create et la méthode displayArmy en display.
Félicitations, vous venez de mettre en œuvre votre première application modulaire !
La liste chaînée (∼45mn – difficile – entraînement)
Avant de commencer,
de façon à conserver le code que vous avez écrit jusqu'à présent, nous vous conseillons
de dupliquer votre projet monster.
Pour cela, sous Eclipse et IntelliJ, il vous suffit de commencer par sélectionner le
projet monster
et de cliquer
avec le bouton de droite de la souris avant de sélectionner Copy.
Ensuite, dans le package explorer, il vous suffit de cliquer avec le bouton de droite
de la souris avant de sélectionner Paste dans la zone vide en dessous des fichiers.
À ce moment, Eclipse ou IntelliJ
va vous demander d'entrer un nouveau nom de projet. Vous pouvez par exemple utiliser
monster-array.
Si vous utilisez IntelliJ, vous pouvez maintenant ouvrir le projet copié en allant dans File, Open et en sélectionnant votre nouveau dossier de projet. Une fois le projet ouvert, cliquez sur le bouton de droite sur le dossier du projet dans l'interface d'IntelliJ, puis Refractor et Rename. Mettez le nouveau nom (monster-array par exemple). Suite à l'extraordinaire succès de votre jeu, vous vous mettez à recevoir des centaines de milliers de mails d'utilisateurs mécontents, car les performances de votre jeu sont désastreuses. Après une analyse de performance poussée, vous vous apercevez que des joueurs monomaniaques collectionnent des centaines de milliers de monstres. Lorsque le tableau extensible est étendu pour accueillir les nouveaux monstres de ces joueurs, des centaines de milliers de cases sont copiées de l'ancien tableau vers le nouveau, ce qui écroule les performances de vos serveurs et impacte l'ensemble des joueurs connectés au même serveur (cette anecdote est bien sûr imaginaire, mais ressemble aux problèmes de performances que vous pouvez rencontrer tous les jours dans une entreprise). De façon à éviter ces recopies de tableaux, nous mettons en œuvre l'armée de monstres avec des listes chaînées. Une liste chaînée est une structure de données classique évitant cette recopie au prix d'un temps de parcours des éléments plus long. Le principe est de construire une chaîne d'éléments homogènes, chacun référençant le suivant de la liste. Pour cela, nous introduisons une nouvelle classe nommée Node permettant de référencer (i) une instance de Monster et (ii) l'instance de Node suivante dans la liste. La figure ci-après présente la structure sous une forme graphique. Chaque boite représente une instance d'une classe. Le nom en haut de la boite donne le nom de la classe instanciée et les noms en dessous sont les champs les plus importants de l'instance. Les flèches quant à elles représentent les références. Dans cette illustration, l'armée (l'instance de Army) référence le premier nœud de la liste chaînée. Le premier nœud référence un premier monstre (Pikachu) et le deuxième nœud. Le deuxième nœud référence le deuxième monstre (Tortank) et le nœud suivant de la liste, jusqu'à la fin de la liste qui est indiquée par la référence null.
Si vous utilisez IntelliJ, vous pouvez maintenant ouvrir le projet copié en allant dans File, Open et en sélectionnant votre nouveau dossier de projet. Une fois le projet ouvert, cliquez sur le bouton de droite sur le dossier du projet dans l'interface d'IntelliJ, puis Refractor et Rename. Mettez le nouveau nom (monster-array par exemple). Suite à l'extraordinaire succès de votre jeu, vous vous mettez à recevoir des centaines de milliers de mails d'utilisateurs mécontents, car les performances de votre jeu sont désastreuses. Après une analyse de performance poussée, vous vous apercevez que des joueurs monomaniaques collectionnent des centaines de milliers de monstres. Lorsque le tableau extensible est étendu pour accueillir les nouveaux monstres de ces joueurs, des centaines de milliers de cases sont copiées de l'ancien tableau vers le nouveau, ce qui écroule les performances de vos serveurs et impacte l'ensemble des joueurs connectés au même serveur (cette anecdote est bien sûr imaginaire, mais ressemble aux problèmes de performances que vous pouvez rencontrer tous les jours dans une entreprise). De façon à éviter ces recopies de tableaux, nous mettons en œuvre l'armée de monstres avec des listes chaînées. Une liste chaînée est une structure de données classique évitant cette recopie au prix d'un temps de parcours des éléments plus long. Le principe est de construire une chaîne d'éléments homogènes, chacun référençant le suivant de la liste. Pour cela, nous introduisons une nouvelle classe nommée Node permettant de référencer (i) une instance de Monster et (ii) l'instance de Node suivante dans la liste. La figure ci-après présente la structure sous une forme graphique. Chaque boite représente une instance d'une classe. Le nom en haut de la boite donne le nom de la classe instanciée et les noms en dessous sont les champs les plus importants de l'instance. Les flèches quant à elles représentent les références. Dans cette illustration, l'armée (l'instance de Army) référence le premier nœud de la liste chaînée. Le premier nœud référence un premier monstre (Pikachu) et le deuxième nœud. Le deuxième nœud référence le deuxième monstre (Tortank) et le nœud suivant de la liste, jusqu'à la fin de la liste qui est indiquée par la référence null.
Commencez par écrire une classe nommée Node contenant deux champs :
un champ monster référençant le monstre associé au nœud et
un champ next référençant le nœud suivant de la liste.
Ajoutez à cette classe une méthode nommée create prenant en argument
un monstre et un nœud suivant et renvoyant un nouveau nœud initialisé de façon adéquate.
Dans la classe Army, ajoutez un champ first de type Node.
Dans la méthode create de Army, initialisez first
avec la valeur null, ce qui indique à Java que cette référence ne pointe nulle part.
Ne supprimez pas encore les anciens champs qui stockent les monstres sous
la forme d'un tableau extensible de façon à conserver un code correct tout au long de
l'exercice.
Dans la méthode addMonster de la classe Army,
sans supprimer le code qui s'y trouve déjà, modifiez la liste de façon à ajouter
le monstre passé en paramètre au début de la liste (à gauche sur la figure ci-dessus).
Techniquement, il vous suffit d'appeler la méthode create de Node de façon adéquate et d'affecter le résultat de cet appel au champ first de l'armée.
Il faut initialiser le nouveau nœud avec comme argument (i) l'ancienne valeur de first et (ii) le nouveau monstre.
Techniquement, il vous suffit d'appeler la méthode create de Node de façon adéquate et d'affecter le résultat de cet appel au champ first de l'armée.
Il faut initialiser le nouveau nœud avec comme argument (i) l'ancienne valeur de first et (ii) le nouveau monstre.
Quelle est la complexité de addMonster ?
La complexité est constante.
Dans la méthode display de la classe Army, en plus d'afficher
les monstres se trouvant dans le tableau extensible, affichez le contenu de la liste chaînée.
Vérifiez que votre programme affiche maintenant bien deux fois votre armée.
Pour afficher votre liste, il vous suffit d'utiliser une variable locale de type Node nommée cur. Ensuite, vous pouvez utiliser une boucle qui s'arrête lorsque cur vaut null et qui, à chaque pas de la boucle, avance d'un cran dans la liste.
Techniquement, à chaque pas de la boucle, il faut exécuter cur = cur.next.
Vous devriez remarquer que, lors du parcours de la liste chaînée,
les monstres sont affichés dans l'ordre inverse de celui de leur insertion.
Ce phénomène est tout à fait normal puisque vous ajoutez les nouveaux nœuds
au début de la liste et que vous affichez votre liste en commençant par
le début.
Pour afficher votre liste, il vous suffit d'utiliser une variable locale de type Node nommée cur. Ensuite, vous pouvez utiliser une boucle qui s'arrête lorsque cur vaut null et qui, à chaque pas de la boucle, avance d'un cran dans la liste.
Techniquement, à chaque pas de la boucle, il faut exécuter cur = cur.next.
Vous pouvez maintenant nettoyer le code et supprimer le tableau extensible qui est devenu inutile.
Pour cela, commencez par supprimer les champs monsters et top de
la classe Army, et corrigez toutes les erreurs que vous indique
votre environnement de développement.
bonus
Pour les étudiants aventuriers, nous vous proposons d'écrire une méthode delMonster
dans la classe Army permettant de supprimer un monstre de l'armée.
Cette méthode doit prendre en paramètre une référence vers une armée et une référence
vers un monstre.
Votre méthode doit traiter trois cas distincts :
- Si le premier nœud de la liste (first) vaut null, il n'y a rien à faire.
- Si le premier nœud de la liste référence un nœud qui référence le monstre passé en paramètre (l'opérateur == permet de savoir si deux références sont identiques), alors il faut affecter first à first.next.
- Sinon, votre méthode doit parcourir la liste de façon à identifier le prédécesseur du nœud qui référence le monstre passé en paramètre. Une fois identifié, si le prédécesseur est stocké dans une variable locale nommée pred, votre méthode doit affecter pred.next.next à pred.next de façon à sauter le nœud que vous souhaitez supprimer.
bonus
Quelle est la complexité de delMonster dans le pire des cas ?
Dans le pire des cas, nous devons parcourir toute la liste pour supprimer l'élément.
La complexité est donc linéaire en la taille de la liste.
bonus
Nous proposons maintenant d'écrire une fonction getMonster qui prend en entrée une armée et un
index i et retourne le monstre à l'index i, s'il existe. Sinon, nous retournons null.
bonus
Quelle est la complexité de la fonction getMonster qui permet d'accéder à l'élément i d'une liste chaînée ?
Comment se compare-t-elle à la complexité dans le cas d'un tableau extensible ?
La complexité est linéaire en i : il faut parcourir tous les éléments jusqu'à i.
Pour un tableau extensible, la complexité est constante.
Pour un tableau extensible, la complexité est constante.
bonus
Comme nous l'avons fait avec le tableau extensible plus haut, nous voulons rendre notre conception plus
modulaire en poussant la logique de la liste chaînée directement dans la classe Node. Écrivez
directement dans Node les fonctions :
La liste chaînée est naturellement compatible avec les fonctions récursives.
- add qui prend en entrée un Node et un Monster et retourne une liste commençant par le monstre et continuant vers l'ancienne liste.
- del qui prend en entrée un Node et un Monster et retourne une liste sans le monstre.
- get qui prend en entrée un Node et un index et retourne le monstre à l'index ou null si ce n'est pas possible.
- display qui doit afficher tous les éléments de la liste.
La liste chaînée est naturellement compatible avec les fonctions récursives.
Pour aller plus loin (Entraînement)
Comme dans le CI précédent, nous proposons ici une série d'exercices libres. À vous de gérer vos projets et classes
pour répondre au problème !
Dans cet exercice, nous allons utiliser la classe Node de la dernière question de l'exercice
précédent. Cependant, nous voulons maintenant manipuler des entiers et non des monstres. Modifiez
Node en conséquence dans un nouveau projet. On réutilisera cette nouvelle classe par la suite.
Pour rendre la lecture des listes plus claire, on affichera les listes chaînées sous la forme : 20 -> 12 -> 10 -> 7 -> 5. Pour cela, on pourra utiliser la fonction System.out.print qui ne rajoute pas de retour à la ligne à la fin de chaque ligne.
Pour rendre la lecture des listes plus claire, on affichera les listes chaînées sous la forme : 20 -> 12 -> 10 -> 7 -> 5. Pour cela, on pourra utiliser la fonction System.out.print qui ne rajoute pas de retour à la ligne à la fin de chaque ligne.
Pour faciliter la création des listes, implémentez une fonction toNode prenant en entrée un
tableau et retournant une liste des éléments du tableau.
Exemple: {5, 7, 10, 12, 20} devient 5 -> 7 -> 10 -> 12 -> 20.
Exemple: {5, 7, 10, 12, 20} devient 5 -> 7 -> 10 -> 12 -> 20.
Écrivez une fonction reverse qui prend en entrée une liste chaînée et retourne la liste inversée.
Exemple: 20 -> 12 -> 10 -> 7 -> 5 devient 5 -> 7 -> 10 -> 12 -> 20.
Exemple: 20 -> 12 -> 10 -> 7 -> 5 devient 5 -> 7 -> 10 -> 12 -> 20.
Écrivez une fonction qui retire les doublons d'une liste chaînée triée.
Exemple: 0 -> 0 -> 1 -> 2 -> 2 -> 3 -> 4 -> 4 devient 0 -> 1 -> 2 -> 3 -> 4.
Exemple: 0 -> 0 -> 1 -> 2 -> 2 -> 3 -> 4 -> 4 devient 0 -> 1 -> 2 -> 3 -> 4.
Pour cette question, nous supposons que nous représentons les nombres par la liste chaînée de leurs chiffres
en ordre inversé. Par exemple, 123 devient 3 -> 2 -> 1. Écrivez une fonction capable
d'additionner deux nombres représentés par une liste.
Exemple: 3 -> 2 -> 1 + 2 -> 1 = 5 -> 3 -> 1
Exemple: 3 -> 2 -> 1 + 2 -> 1 = 5 -> 3 -> 1
Écrivez une fonction Node getMiddleNode(Node nodeFrom, Node nodeTo) qui retourne le nœud situé à
mi-distance entre deux nœuds
donnés en entrée. Essayez d'écrire cette fonction sans calculer la taille totale de la liste.
Il faut utiliser deux curseurs qui parcourent la liste, dont un qui se déplace deux fois plus vite.
Il faut utiliser deux curseurs qui parcourent la liste, dont un qui se déplace deux fois plus vite.
Implémentez le tri fusion pour les listes. Attention, il ne faut pas tout faire dans une seule fonction ! À
vous de vous organiser pour créer des fonctions auxiliaires et faire le code le plus lisible possible.
Voici quelques fonctions auxiliaires qui pourraient vous être utiles:
- Node getLastNode(Node node) qui retourne le dernier nœud d'une liste.
- Node mergeSorted(Node first, Node second) qui fusionne deux listes triées en une nouvelle liste triée elle aussi.
- Node mergeSortAux(Node nodeFrom, Node nodeTo) qui prend le nœud au milieu entre nodeFrom et nodeTo, trie chaque demie-liste et fusionne le résultat.
