TD 7

/users/profs/info/Depot/INF_321/deposer *.java TD_7 numéro_du_groupe

Listes de mots

• un constructeur ListeDeMots(String c, ListeDeMots l) qui rajoute le mot c en tête de la liste de mots l.
• une fonction static ListeDeMots creerDepuisTableau(String[] tab) qui renvoie la liste contenant les éléments de tab, en conservant l'ordre : tab[0] doit apparaître en tête. Rappel : si a est un tableau, a.length est le nombre d'éléments de a.
• une fonction static void afficher(ListeDeMots l), qui affiche le contenu de la liste (la tête doit apparaître en premier).
• une fonction static String concatener(ListeDeMots l) qui renvoie la chaîne obtenue en concaténant les entrées de l.
• une fonction static int longueur(ListeDeMots l) qui calcule le nombre d'éléments de l.

Tri fusion

• static ListeDeMots recopierPremiers(ListeDeMots l, int n) qui renvoie la liste des n premiers mots de l (en tronquant avec null si n dépasse la taille de l). Cette fonction doit créer une nouvelle liste.
• static ListeDeMots recopierAPartirDe(ListeDeMots l, int n) qui renvoie la sous-liste de l formée des entrées de l de rang n, n+1, ..., jusqu'à la fin (on renvoie null si n dépasse la taille de l). Cette fonction doit créer une nouvelle liste.
• static ListeDeMots fusion(ListeDeMots s1, ListeDeMots s2) qui fusionne les listes s1 et s2. On supposera que ces listes sont triées en ordre lexicographique (ordre du dictionnaire), et on demande que la liste obtenue le soit également.
  Indication : Si s et t sont des chaînes, s.compareTo(t) renvoie un entier positif (resp. négatif) si s est plus grand que t lexicographiquement.
• static ListeDeMots trier(ListeDeMots l) qui trie la liste l. Pour cela, si l contient au moins 2 éléments, on la coupe en deux parties de taille égale à la moitié de la taille de l (à un près), on trie les deux sous-listes, puis on les fusionne.

• On souhaite écrire une fonction static void decouper qui coupe une liste en deux en son milieu, et qui permet d'obtenir les deux moitiés, sans effectuer de recopie. Vous êtes libre de créer de nouvelles classes, et de donner les arguments que vous souhaitez à cette fonction.

Listes circulaires de caractères

• Créez cette classe, un constructeur ListeCirculaire(char c) qui crée une liste circulaire à un élément, et une fonction static boolean estSingleton(ListeCirculaire l) qui renvoie true si et seulement si l est une liste circulaire à un élément.
• Écrire une fonction static ListeCirculaire inserer(char c, ListeCirculaire l) qui renvoie la liste circulaire obtenue en insérant le caractère c en tête de la liste l. Cette fonction pourra modifier l.
  Exemple. Supposons que l contient le seul caractère 'b', avec donc l.suivant = l. Soit m la liste obtenue par inserer('a',l). On doit alors avoir m.contenu = 'a', m.suivant.contenu = 'b', et, pour boucler la boucle, m.suivant.suivant = m.
• Écrire une fonction static void afficher(ListeCirculaire l) qui affiche le contenu de l (on n'affichera qu'une seule fois chaque entrée).
• Écrire une fonction static ListeCirculaire creerDepuisChaine(String s) qui renvoie la liste circulaire formée des lettres de s en en conservant l'ordre (le contenu du résultat doit être égal à s.charAt(0)).
  Réciproquement, écrire une fonction static String creerChaine(ListeCirculaire l) qui renvoie la chaîne codée par l. Ici, si s est le résultat, on doit avoir s.charAt(0) = l.contenu. On appelle aussi s la chaîne associée à l.
  Indication. La longueur d'une chaîne s s'obtient par s.length(), et son i-ème caractère par s.charAt(i). La concaténation d'une chaîne s et d'un caractère c s'obtient par s+c.
• Écrire une fonction static ListeCirculaire avancer(ListeCirculaire l) qui renvoie la liste obtenue en décalant l d'un élément, de sorte que le contenu de l.suivant soit en tête de la liste obtenue. Cette fonction ne doit pas modifier l.
  Exemple. Reprenons l'exemple de la liste m ci-dessus, et soit n le résultat de avancer(m). Alors on doit avoir n.contenu = 'b', n.suivant.contenu = 'a', et n.suivant.suivant = n. De même, si on applique avancer à la liste dont les contenus successifs sont a b c d, on doit obtenir la liste dont les contenus sont b c d a.
  Les listes obtenues en appliquant une ou plusieurs fois avancer à l s'appellent ses décalées.

• Écrire une fonction static ListeCirculaire renverser(ListeCirculaire l) qui renverse (retourne) une liste circulaire Le contenu de la liste obtenue doit être le même que celui de l.
  Exemple. Si on applique renverser à la liste dont les contenus successifs sont a b c d, on doit obtenir la liste dont les contenus sont a d c b.
• Écrire une fonction static ListeCirculaire supprimerTete(ListeCirculaire l) qui renvoie la liste circulaire obtenue après la suppression de l'élément de tête de l ; vous pouvez modifier l si nécessaire.

Mots de Lyndon

• Une liste circulaire l est cyclique si le mot codé par l peut s'écrire comme la concaténation d'au moins 2 occurences d'un mot t.
• Une liste circulaire l est plus petite qu'une liste circulaire m si le mot associé à l est plus petit que le mot associé à m.

• Écrire une fonction static boolean estLyndon(String s) qui teste si s est de Lyndon.
• Écrire une fonction static String[] tousLesLyndon(char[] alphabet, int taille) qui renvoie le tableau de tous les mots de Lyndon de taille taille, formés des lettres de alphabet.
• Écrire une fonction static String concatenation(char[] alphabet, int taille) qui renvoie le mot obtenu en concaténant, dans l'ordre lexicographique, tous les mots de Lyndon dont la taille divise taille, sur les lettres de alphabet. L'ordre est indifférent.
• Écrire une fonction pour vérifier la propriété suivante : la chaîne obtenue par concatenation est de taille |alphabet|^taille, et, si on la voit cycliquement, contient comme sous-chaîne tous les mots de longueur taille formés sur les lettres de alphabet.