TP5/exo_c4/liste_correction.c

   1 /********************************************************************/
   2 /*   Implantation d'une liste triee d'entiers                       */
   3 /********************************************************************/
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6
   7 typedef int element;
   8
   9 typedef struct cellule {
  10  element valeur;
  11  struct cellule *suivant;
  12 } Cellule, *Liste;
  13
  14
  15
  16 Liste ajouter_iter(element e, Liste L)
  17 {
  18  Cellule *pc, *p1=L, *p2=NULL;
  19
  20  pc = (Cellule *)malloc(sizeof(Cellule));
  21  pc->valeur=e;pc->suivant=NULL;
  22
  23  if (!L) /* liste vide */ return pc;
  24  while (p1 && (e >= p1->valeur))
  25  {
  26   p2 = p1;
  27   p1 = p1->suivant;
  28  }
  29
  30  if (!p2) /* insertion en tete */ {pc->suivant = L; L=pc; }
  31  else {/* insertion entre p2 et p1 */
  32        p2->suivant = pc;
  33        pc->suivant = p1;
  34       }
  35
  36  return L;
  37 }
  38
  39
  40 int longueur_iter(Liste L)
  41 {
  42  int res = 0;
  43  while(L)
  44  {
  45   res = res + 1;
  46   L=L->suivant;
  47  }
  48  return res;
  49 }
  50
  51
  52 int longueur_rec(Liste L)
  53 {
  54  if(!L) return 0;
  55  return 1+longueur_rec(L->suivant);
  56 }
  57
  58
  59 void visualiser_iter(Liste L)
  60 {
  61  while (L)
  62  {
  63   printf("%d ",L->valeur);
  64   L = L->suivant;
  65  }
  66  printf("\n");
  67 }
  68
  69
  70 void visualiser_aux(Liste L)
  71 {
  72  if(L)
  73  {
  74   printf("%d ",L->valeur);
  75   visualiser_aux(L->suivant);
  76  }
  77 }
  78
  79
  80 void visualiser_rec(Liste L)
  81 {
  82  visualiser_aux(L);
  83  printf("\n");
  84 }
  85
  86
  87 int rechercher_iter(element e, Liste L)
  88 {
  89  while(L)
  90  {
  91   if(e == L->valeur) return 1;
  92   L = L->suivant;
  93  }
  94  return 0;
  95 }
  96
  97
  98 int rechercher_rec(element e, Liste L)
  99 {
 100  if(L == NULL) return 0;
 101  if(e==L->valeur) return 1;
 102  return rechercher_rec(e,L->suivant);
 103 }
 104
 105
 106 Liste rechercher_rec2(element e, Liste L)
 107 {
 108  if(!L || e==L->valeur) return L;
 109  else return rechercher_rec2(e,L->suivant);
 110 }
 111
 112
 113 Liste ajouter_rec(element e, Liste L)
 114 {
 115  if(!L)
 116  {
 117   L=(Cellule *)malloc(sizeof(Cellule)); /* liste vide */
 118   L->valeur=e;L->suivant=NULL;
 119  }
 120  else if(e < L->valeur) /* ajouter DEVANT la tete */
 121       {
 122        Cellule *p=(Cellule *)malloc(sizeof(Cellule));
 123        p->valeur=e; p->suivant=L;
 124        L=p; /* nouvelle tete de liste */
 125       }
 126       else L->suivant=ajouter_rec(e,L->suivant); /* ajouter DERRIERE la tete */
 127  return L;
 128 }
 129
 130
 131 Liste supprimer_iter(element e, Liste L)
 132 {
 133  Liste prec = NULL;
 134  while(L)
 135  {
 136   if(e == L->valeur) {
 137    prec->suivant = L->suivant; /* le suivant de prec devient le suivant de L */
 138    free(L); /* liberation memoire pour L */
 139    return prec;
 140   }
 141   prec = L;
 142   L = L->suivant;
 143  }
 144  return L;
 145 }
 146
 147
 148 Liste supprimer_rec(element e, Liste L)
 149 {
 150  if(!L) ; /* element absent - on ne fait rien */
 151  else if(L->valeur==e)
 152       {
 153        Cellule *p=L;
 154        L=L->suivant;
 155        free(p);
 156       }
 157       else L->suivant=supprimer_rec(e,L->suivant);
 158  return L;
 159 }
 160
 161
 162 Liste inverser_iter(Liste L)
 163 {
 164  Liste cell=NULL; /* une cellule temporaire */
 165  Liste inv=NULL; /* la liste inversee */
 166
 167  while(L!=NULL)
 168  {
 169   cell=L; /* on prend la premiere cellule de la liste */
 170   L=L->suivant; /* le debut de la liste devient l'element suivant */
 171   cell->suivant=inv; /* on libere l'element de la liste  et on le place en debut de la liste a renvoyer*/
 172   inv=cell; /* l'element qu'on vient de mettre en debut de liste devient le debut de la liste de a renvoyer */
 173  }
 174  return inv;
 175 }
 176
 177
 178
 179 Liste inserer_fin(element e, Liste L)
 180 {
 181  Cellule *pc, *p1=L, *p2=NULL;
 182  pc = (Cellule *)malloc(sizeof(Cellule));
 183  pc->valeur=e;pc->suivant=NULL;
 184  if (!L) return pc;
 185  while (p1)
 186  {
 187   p2 = p1;
 188   p1 = p1->suivant;
 189  }
 190  p2->suivant = pc;
 191  pc->suivant = p1;
 192  return L;
 193 }
 194
 195
 196 Liste inverser_rec(Liste L)
 197 {
 198  if(L != NULL) {
 199   return inserer_fin(L->valeur, inverser_rec(L->suivant));
 200  }
 201  else return L;
 202 }
 203
 204
 205 /****************************************************************************/
 206
 207 int main()
 208 {
 209  Liste L=NULL;
 210  printf("liste vide\n");
 211  visualiser_iter(L);
 212  visualiser_rec(L);
 213
 214  printf("longueur=%d\n",longueur_iter(L));
 215  printf("longueur=%d\n",longueur_rec(L));
 216
 217  printf("ajout de 3\n");
 218  L=ajouter_iter(3,L);
 219  printf("ajout de 6\n");
 220  L=ajouter_iter(6,L);
 221  printf("ajout de 1\n");
 222  L=ajouter_iter(1,L);
 223  printf("ajout de 10\n");
 224  L=ajouter_iter(10,L);
 225  printf("ajout de 6\n");
 226  L=ajouter_iter(6,L);
 227  visualiser_iter(L);
 228  visualiser_rec(L);
 229
 230  printf("longueur=%d\n",longueur_iter(L));
 231  printf("longueur=%d\n",longueur_rec(L));
 232
 233  printf("recherche de %d = %d\n",3,rechercher_iter(3,L));
 234  printf("recherche de %d = %d\n",3,rechercher_rec(3,L));
 235  printf("recherche de %d = %d\n",4,rechercher_iter(4,L));
 236  printf("recherche de %d = %d\n",4,rechercher_rec(4,L));
 237
 238  printf("ajout (rec) de 4\n");
 239  L=ajouter_rec(4,L);
 240  visualiser_iter(L);
 241  printf("ajout (rec) de 8\n");
 242  L=ajouter_rec(8,L);
 243  visualiser_iter(L);
 244
 245  printf("suppression (iter) de 4\n");
 246  supprimer_iter(4,L);
 247  visualiser_iter(L);
 248  printf("suppression (rec) de 6\n");
 249  supprimer_rec(6,L);
 250  visualiser_iter(L);
 251
 252  printf("liste inversee (iter)\n");
 253  Liste inv = inverser_iter(L);
 254  visualiser_iter(inv);
 255
 256  printf("Liste inversee (rec)\n");
 257  Liste inv2 = inverser_rec(inv);
 258  visualiser_iter(inv2);
 259
 260  /* il faut aussi tester chaque fonction (visualiser, supprimer, rechercher, inverser, ...) sur tous les cas : liste vide, liste avec un seul element, operation sur le premier element, operation sur le dernier element, ... */
 261 }
 262
 263
 264 /****************************************************************************/
 265
 266 /* trace d'execution :
 267 liste vide
 268
 269
 270 longueur=0
 271 longueur=0
 272 ajout de 3
 273 ajout de 6
 274 ajout de 1
 275 ajout de 10
 276 ajout de 6
 277 1 3 6 6 10
 278 1 3 6 6 10
 279 longueur=5
 280 longueur=5
 281 recherche de 3 = 1
 282 recherche de 3 = 1
 283 recherche de 4 = 0
 284 recherche de 4 = 0
 285 ajout (rec) de 4
 286 1 3 4 6 6 10
 287 ajout (rec) de 8
 288 1 3 4 6 6 8 10
 289 suppression (iter) de 4
 290 1 3 6 6 8 10
 291 suppression (rec) de 6
 292 1 3 6 8 10
 293 liste inversee (iter)
 294 10 8 6 3 1
 295 Liste inversee (rec)
 296 1 3 6 8 10
 297 */
 298