Exercices (pc4)

Exercice 1 Ecrire une fonction qui calcule la liste (a_{n}, a_{n−1}, …, a_{0}) renversée de la liste (a_{0}, a_{1}, …, a_{n}).

static Liste retourner(Liste p) {
  Liste q;
  while (p != null) {
    q= ajouter(p.contenu,q);
    p=p.suivant;
  }
  return q;
}

Exercice 2 On utilise une classe BiListe de la forme

class BiListe {
  Liste
    debut,
    fin;
}

donnant à la fois une référence sur le début, et une sur la fin de la liste.

1. Ecrire un constructeur pour la classe BiListe.

2. Ecrire une fonction qui concatène deux listes non vides sous cette forme.

Biliste(Liste p, Liste q) {
  debut= p;
  fin= q;
}
static Biliste cat(Biliste p, Biliste q) {
  Biliste b=new Biliste(p.debut,q.fin);
  p.fin.suivant= q.debut;
  return b;
}

Exercice 3 Ecrire sous forme itérative la suppression d’un élément dans une liste.

static Liste supprimer(int x, Liste p) {
   Liste q;
  if (p != null)
    if (p.contenu == x)
      return p.suivant;
    else {
      q = p;
      while (q.suivant != null && q.suivant.contenu !=x)
        q= q.suivant;
      if (q.suivant != null)
        q.suivant= q.suivant.suivant;
    }
    return p;
}