Exercices (pc 4) Corrigé

1. On pourra écrire :

Liste Lire() {
  Liste p=NULL;
  int x;
  scanf("%d",&x);
  while (x != -1) {
    p=Inserer(x,p);
    scanf("%d",&x);
  }
  return p;
}

2. Il faut distinguer la suppression en tête de la suppression aux autres positions.

Liste Supprimer(Element 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;
}

3. Il suffit d’inserer en tete :

Liste Retourner(Liste p) {
  Liste q,r;

q= p;
r= NULL;
while (q != NULL) {
  r= Inserer(q->contenu,r);
  q= q->suivant;
}
return r;
}

4.

Liste Concat(Liste p, Liste q) {
return (p== nil)?  q : Inserer( p->contenu, Concat(p->suivant,q));
}

On a aussi la version très astucieuse :

void Concat (Liste * pp, Liste q) {
if (*pp == NULL)
 *pp= q;
else
  Concat(&((*pp)->suivant), q);
}

Pour une execution en temps constant, il faut utiliser des listes gardées en tête et en queue.

5.

int Longueur(Liste p) {
int i=0;
while (p != NULL) {
  ++i;
  p= p->suivant;
}
return p;
}

ou encore

int Longueur(Liste p) {
  int i=0;
  for( ; p; p=p->suivant)
    ++i;
}