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         if (!L)
 171                 return pc;
 172         while (p1) {
 173                 p2 = p1;
 174                 p1 = p1->suivant;
 175         }
 176         p2->suivant = pc;
 177         pc->suivant = p1;
 178         return L;
 179 }
 180
 181 Liste inverser_rec(Liste L)
 182 {
 183         if (L != NULL) {
 184                 return inserer_fin(L->valeur, inverser_rec(L->suivant));
 185         } else
 186                 return L;
 187 }
 188
 189 /****************************************************************************/
 190
 191 int main()
 192 {
 193         Liste L = NULL;
 194         printf("liste vide\n");
 195         visualiser_iter(L);
 196         visualiser_rec(L);
 197
 198         printf("longueur=%d\n", longueur_iter(L));
 199         printf("longueur=%d\n", longueur_rec(L));
 200
 201         printf("ajout de 3\n");
 202         L = ajouter_iter(3, L);
 203         printf("ajout de 6\n");
 204         L = ajouter_iter(6, L);
 205         printf("ajout de 1\n");
 206         L = ajouter_iter(1, L);
 207         printf("ajout de 10\n");
 208         L = ajouter_iter(10, L);
 209         printf("ajout de 6\n");
 210         L = ajouter_iter(6, L);
 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("recherche de %d = %d\n", 3, rechercher_iter(3, L));
 218         printf("recherche de %d = %d\n", 3, rechercher_rec(3, L));
 219         printf("recherche de %d = %d\n", 4, rechercher_iter(4, L));
 220         printf("recherche de %d = %d\n", 4, rechercher_rec(4, L));
 221
 222         printf("ajout (rec) de 4\n");
 223         L = ajouter_rec(4, L);
 224         visualiser_iter(L);
 225         printf("ajout (rec) de 8\n");
 226         L = ajouter_rec(8, L);
 227         visualiser_iter(L);
 228
 229         printf("suppression (iter) de 4\n");
 230         supprimer_iter(4, L);
 231         visualiser_iter(L);
 232         printf("suppression (rec) de 6\n");
 233         supprimer_rec(6, L);
 234         visualiser_iter(L);
 235
 236         printf("liste inversee (iter)\n");
 237         Liste inv = inverser_iter(L);
 238         visualiser_iter(inv);
 239
 240         printf("Liste inversee (rec)\n");
 241         Liste inv2 = inverser_rec(inv);
 242         visualiser_iter(inv2);
 243
 244         /* 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, ... */
 245 }
 246
 247 /****************************************************************************/
 248
 249 /* trace d'execution :
 250 liste vide
 251
 252 longueur=0
 253 longueur=0
 254 ajout de 3
 255 ajout de 6
 256 ajout de 1
 257 ajout de 10
 258 ajout de 6
 259 1 3 6 6 10
 260 1 3 6 6 10
 261 longueur=5
 262 longueur=5
 263 recherche de 3 = 1
 264 recherche de 3 = 1
 265 recherche de 4 = 0
 266 recherche de 4 = 0
 267 ajout (rec) de 4
 268 1 3 4 6 6 10
 269 ajout (rec) de 8
 270 1 3 4 6 6 8 10
 271 suppression (iter) de 4
 272 1 3 6 6 8 10
 273 suppression (rec) de 6
 274 1 3 6 8 10
 275 liste inversee (iter)
 276 10 8 6 3 1
 277 Liste inversee (rec)
 278 1 3 6 8 10
 279 */