Adloun

algorithmique (école d'ingénieur) · Chapitre 8 · Exercice de TD

Un petit diff

Séquences et chaînes de caractères · niveau 2

Énoncé

La commande Unix diff compare deux fichiers ligne à ligne : chaque ligne est un symbole, le fichier est une séquence de lignes.

  • Adapter calculerL à deux tableaux de lignes String[] T, U (attention : on compare des chaînes avec equals, pas avec ==).
  • Écrire une fonction récursive qui affiche les lignes communes (précédées de deux espaces), supprimées (précédées de -) et ajoutées (précédées de +), dans l'ordre des fichiers.
  • Tester sur les deux versions d'une fonction ci-dessous.

version 1             version 2
int s = 0;            long s = 0;
for (int x : T)       for (int x : T)
  s = s + x;            s = s + x;
return s;             System.out.println(s);
                      return s;

Corrigé

  • Seule la comparaison change : T[p - 1].equals(U[q - 1]). Avec ==, Java comparerait les adresses des chaînes, et deux lignes identiques lues dans deux fichiers seraient jugées différentes.
  • On suit la reconstruction d'une plsc ; une ligne de la plsc est commune, une ligne de hors plsc est supprimée, une ligne de hors plsc est ajoutée.

static void diff(String[] T, String[] U, int[][] L, int p, int q) {
    if (p > 0 && q > 0 && T[p - 1].equals(U[q - 1])) {
        diff(T, U, L, p - 1, q - 1);
        System.out.println("  " + T[p - 1]);              // ligne commune
    } else if (q > 0 && (p == 0 || L[p][q - 1] >= L[p - 1][q])) {
        diff(T, U, L, p, q - 1);
        System.out.println("+ " + U[q - 1]);              // ligne ajoutée
    } else if (p > 0) {
        diff(T, U, L, p - 1, q);
        System.out.println("- " + T[p - 1]);              // ligne supprimée
    }
}

Pour lire un fichier : String[] T = Files.readAllLines(Path.of(nom)).toArray(new String[0]);

  • Exécution :

- int s = 0;
+ long s = 0;
  for (int x : T)
    s = s + x;
+ System.out.println(s);
  return s;

100 % gratuit

La suite du chapitre est sur Adloun

Exercice suivant et tuteur

Sans compte : le cours, le premier QCM et 2 minutes de podcast et de vidéo. Exercices et tuteur : inscription gratuite en 30 secondes, sans carte bancaire.

Le cours du chapitre · Tous les exercices du chapitre

Exercice suivant et tuteur →