TP5/exo4/liste_chainee.c

   1 /********************************************************************/
   2 /*   Implantation d'une liste triee d'entiers                       */
   3 /********************************************************************/
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <stdbool.h>
   7
   8 typedef int element;
   9
  10 typedef struct cellule {
  11         element valeur;
  12         struct cellule *suivant;
  13 } Cellule, *Liste;
  14
  15 Cellule *creer_maillon(element e, Cellule * suivant)
  16 {
  17         Cellule *pnouveau = malloc(sizeof(Cellule));
  18         pnouveau->valeur = e;
  19         pnouveau->suivant = suivant;
  20         return pnouveau;
  21 }
  22
  23 Liste ajouter_iter(element e, Liste L)
  24 {
  25         Cellule *pc, *p1 = L, *p2 = NULL;
  26         pc = creer_maillon(e, NULL);
  27
  28         if (!L)                 /* liste vide */
  29                 return pc;
  30
  31         while (p1 && (e >= p1->valeur)) {
  32                 p2 = p1;
  33                 p1 = p1->suivant;
  34         }
  35
  36         if (!p2) {              /* insertion en tete */
  37                 pc->suivant = L;
  38                 L = pc;
  39         } else {                /* insertion entre p2 et p1 */
  40                 p2->suivant = pc;
  41                 pc->suivant = p1;
  42         }
  43
  44         return L;
  45 }
  46
  47 int longueur_iter(Liste L)
  48 {
  49         int longueur = 0;
  50
  51         while (L != NULL) {
  52                 L = L->suivant;
  53                 longueur++;
  54         }
  55         return longueur;
  56 }
  57
  58 int longueur_rec(Liste L)
  59 {
  60         if (L != NULL) {
  61                 return 1 + longueur_rec(L->suivant);
  62         } else {
  63                 return 0;
  64         }
  65 }
  66
  67 void visualiser_iter(Liste L)
  68 {
  69         int compteur = 0;
  70
  71         printf("--Debut--\n");
  72         while (L != NULL) {
  73                 printf("L[%d]->value=%d\n", compteur, L->valeur);
  74                 L = L->suivant;
  75                 compteur++;
  76         }
  77         printf("--Fin--\n");
  78 }
  79
  80 void _visualiser_rec(Liste L, int compteur)
  81 {
  82         if (L != NULL) {
  83                 /* FIXME: suboptimal printing to stdout, put this code path outside the recursion */
  84                 if (compteur == 0)
  85                         printf("--Debut--\n");
  86                 printf("L[%d]->value=%d\n", compteur, L->valeur);
  87                 compteur++;
  88                 _visualiser_rec(L->suivant, compteur);
  89                 if (compteur == (longueur_rec(L) - 1))
  90                         printf("--Fin--\n");
  91         }
  92
  93 }
  94
  95 void visualiser_rec(Liste L)
  96 {
  97         int compteur = 0;
  98
  99         _visualiser_rec(L, compteur);
 100 }
 101
 102 bool rechercher_iter(element e, Liste L)
 103 {
 104         bool rt_val = false;
 105
 106         while (L != NULL) {
 107                 if (L->valeur == e) {
 108                         rt_val = true;
 109                         break;
 110                 }
 111                 L = L->suivant;
 112         }
 113         return rt_val;
 114 }
 115
 116 Liste rechercher_rec(element e, Liste L)
 117 {
 118         if (L->valeur != e && L->suivant != NULL) {
 119                 return L = rechercher_rec(e, L->suivant);
 120         }
 121 }
 122
 123 Liste ajouter_rec(element e, Liste L)
 124 {
 125         if (!L || !(L->valeur < e)) {
 126                 return creer_maillon(e, L);
 127         }
 128
 129         L->suivant = ajouter_rec(e, L->suivant);
 130
 131         return L;
 132 }
 133
 134 Liste supprimer_iter(element e, Liste L)
 135 {
 136         Cellule *pavant = NULL;
 137         Cellule *pdebut = L;
 138
 139         while (L != NULL) {
 140                 /* supprimer en fin de liste */
 141                 if (L->valeur == e && L->suivant == NULL) {
 142                         free(L);
 143                         pavant->suivant = NULL;
 144                         return pdebut;
 145                         /* supprimer au début de la liste */
 146                 } else if (L->valeur == e && pavant == NULL) {
 147                         Cellule *pcourant = L;
 148                         free(L);
 149                         return pcourant->suivant;
 150                         /* supprimer au mileu de la liste */
 151                 } else if (L->valeur == e) {
 152                         Cellule *pcourant = L;
 153                         free(L);
 154                         L = pavant;
 155                         L->suivant = pcourant->suivant->suivant;
 156                         return pdebut;
 157                 }
 158                 pavant = L;
 159                 L = L->suivant;
 160         }
 161 }
 162
 163 Liste supprimer_rec(element e, Liste L)
 164 {
 165         if (L == NULL) {
 166                 return L;
 167         }
 168         if (L->valeur == e) {
 169                 Cellule *p = L;
 170                 L = L->suivant;
 171                 free(p);
 172         } else {
 173                 L->suivant = supprimer_rec(e, L->suivant);
 174         }
 175         return L;
 176 }
 177
 178 Liste inverser_iter(Liste L)
 179 {
 180         /* ... */
 181 }
 182
 183 Liste inverser_rec(Liste L)
 184 {
 185         /* ... */
 186 }
 187
 188 void liberer_iter(Liste L)
 189 {
 190         while (!L) {
 191                 Cellule *pcourant = L;
 192                 free(L);
 193                 L = pcourant->suivant;
 194         }
 195 }
 196
 197 void liberer_rec(Liste L)
 198 {
 199         if (!L) {
 200                 liberer_rec(L->suivant);
 201                 free(L);
 202         }
 203 }
 204
 205 /****************************************************************************/
 206 int main()
 207 {
 208         int x;
 209         Liste L = NULL;
 210         L = ajouter_iter(2, L);
 211         L = ajouter_iter(1, L);
 212         L = ajouter_iter(3, L);
 213         L = ajouter_iter(4, L);
 214         printf("Saisir un entier a chercher dans la liste L\n");
 215         scanf("%d", &x);
 216         printf("L a pour longueur %d\n", longueur_rec(L));
 217         visualiser_iter(L);
 218         visualiser_rec(L);
 219         if (rechercher_iter(x, L))
 220                 printf("L'element %d est present dans L\n", x);
 221         else
 222                 printf("L'element %d n'est pas present dans L\n", x);
 223         if (rechercher_rec(x, L) != NULL)
 224                 printf("L'element %d est present dans L\n", x);
 225         else
 226                 printf("L'element %d n'est pas present dans L\n", x);
 227         L = ajouter_rec(6, L);
 228         L = ajouter_rec(5, L);
 229         L = ajouter_rec(7, L);
 230         visualiser_iter(L);
 231         /* L = supprimer_iter(1, L);
 232            L = supprimer_iter(4, L);
 233            L = supprimer_iter(2, L); */
 234         L = supprimer_rec(1, L);
 235         L = supprimer_rec(4, L);
 236         L = supprimer_rec(2, L);
 237         visualiser_rec(L);
 238         visualiser_iter(L);
 239         liberer_rec(L);
 240         //liberer_iter(L);
 241         /* ... */
 242 }
 243
 244 /****************************************************************************/
 245 /* vim:noet:ts=8:sw=8:textwidth=80 */