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
  27         pc = creer_maillon(e, NULL);
  28
  29         if (!L)                 /* liste vide */
  30                 return pc;
  31
  32         while (p1 && (e >= p1->valeur)) {
  33                 p2 = p1;
  34                 p1 = p1->suivant;
  35         }
  36
  37         if (!p2) {              /* insertion en tete */
  38                 pc->suivant = L;
  39                 L = pc;
  40         } else {                /* insertion entre p2 et p1 */
  41                 p2->suivant = pc;
  42                 pc->suivant = p1;
  43         }
  44
  45         return L;
  46 }
  47
  48 int longueur_iter(Liste L)
  49 {
  50         int longueur = 0;
  51
  52         while (L != NULL) {
  53                 L = L->suivant;
  54                 longueur++;
  55         }
  56         return longueur;
  57 }
  58
  59 int longueur_rec(Liste L)
  60 {
  61         if (L != NULL) {
  62                 return 1 + longueur_rec(L->suivant);
  63         } else {
  64                 return 0;
  65         }
  66 }
  67
  68 void visualiser_iter(Liste L)
  69 {
  70         int compteur = 0;
  71
  72         printf("--Debut--\n");
  73         while (L != NULL) {
  74                 printf("L[%d]->value=%d\n", compteur, L->valeur);
  75                 L = L->suivant;
  76                 compteur++;
  77         }
  78         printf("--Fin--\n");
  79 }
  80
  81 void _visualiser_rec(Liste L, int compteur)
  82 {
  83         if (L != NULL) {
  84                 /* FIXME: suboptimal printing to stdout, put this code path outside the recursion */
  85                 if (compteur == 0)
  86                         printf("--Debut--\n");
  87                 printf("L[%d]->value=%d\n", compteur, L->valeur);
  88                 compteur++;
  89                 _visualiser_rec(L->suivant, compteur);
  90                 if (compteur == (longueur_rec(L) - 1))
  91                         printf("--Fin--\n");
  92         }
  93
  94 }
  95
  96 void visualiser_rec(Liste L)
  97 {
  98         int compteur = 0;
  99
 100         _visualiser_rec(L, compteur);
 101 }
 102
 103 bool rechercher_iter(element e, Liste L)
 104 {
 105         bool rt_val = false;
 106
 107         while (L != NULL) {
 108                 if (L->valeur == e) {
 109                         rt_val = true;
 110                         break;
 111                 }
 112                 L = L->suivant;
 113         }
 114         return rt_val;
 115 }
 116
 117 Liste rechercher_rec(element e, Liste L)
 118 {
 119         if (L->valeur != e && L->suivant != NULL) {
 120                 return L = rechercher_rec(e, L->suivant);
 121         }
 122 }
 123
 124 Liste ajouter_rec(element e, Liste L)
 125 {
 126         if (!L || !(L->valeur < e)) {
 127                 return creer_maillon(e, L);
 128         }
 129
 130         L->suivant = ajouter_rec(e, L->suivant);
 131
 132         return L;
 133 }
 134
 135 Liste supprimer_iter(element e, Liste L)
 136 {
 137         Cellule *pavant = NULL;
 138         Cellule *pdebut = L;
 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         /* ... */
 166 }
 167
 168 Liste inverser_iter(Liste L)
 169 {
 170         /* ... */
 171 }
 172
 173 Liste inverser_rec(Liste L)
 174 {
 175         /* ... */
 176 }
 177
 178 void liberer_iter(Liste L)
 179 {
 180         while (!L) {
 181                 Cellule *pcourant = L;
 182                 free(L);
 183                 L = pcourant->suivant;
 184         }
 185 }
 186
 187 void liberer_rec(Liste L)
 188 {
 189         if (!L) {
 190                 liberer_rec(L->suivant);
 191                 free(L);
 192         }
 193 }
 194
 195 /****************************************************************************/
 196 int main()
 197 {
 198         int x;
 199         Liste L = NULL;
 200         L = ajouter_iter(2, L);
 201         L = ajouter_iter(1, L);
 202         L = ajouter_iter(3, L);
 203         L = ajouter_iter(4, L);
 204         printf("Saisir un entier a chercher dans la liste L\n");
 205         scanf("%d", &x);
 206         printf("L a pour longueur %d\n", longueur_rec(L));
 207         visualiser_iter(L);
 208         visualiser_rec(L);
 209         if (rechercher_iter(x, L))
 210                 printf("L'element %d est present dans L\n", x);
 211         else
 212                 printf("L'element %d n'est pas present dans L\n", x);
 213         if (rechercher_rec(x, L) != NULL)
 214                 printf("L'element %d est present dans L\n", x);
 215         else
 216                 printf("L'element %d n'est pas present dans L\n", x);
 217         L = ajouter_rec(6, L);
 218         L = ajouter_rec(5, L);
 219         L = ajouter_rec(7, L);
 220         visualiser_iter(L);
 221         L = supprimer_iter(1, L);
 222         L = supprimer_iter(4, L);
 223         L = supprimer_iter(2, L);
 224         visualiser_rec(L);
 225         visualiser_iter(L);
 226         //liberer_rec(L);
 227         liberer_iter(L);
 228         /* ... */
 229 }
 230
 231 /****************************************************************************/
 232 /* vim:noet:ts=8:sw=8:textwidth=80 */