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