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                 printf("L[%d]->value=%d\n", compteur, L->valeur);
  84                 compteur++;
  85                 _visualiser_rec(L->suivant, compteur);
  86         }
  87
  88 }
  89
  90 void visualiser_rec(Liste L)
  91 {
  92         int compteur = 0;
  93
  94         printf("--Debut--\n");
  95         _visualiser_rec(L, compteur);
  96         printf("--Fin--\n");
  97 }
  98
  99 bool rechercher_iter(element e, Liste L)
 100 {
 101         bool rt_val = false;
 102
 103         while (L != NULL) {
 104                 if (L->valeur == e) {
 105                         rt_val = true;
 106                         break;
 107                 }
 108                 L = L->suivant;
 109         }
 110         return rt_val;
 111 }
 112
 113 Liste rechercher_rec(element e, Liste L)
 114 {
 115         if (L->valeur != e && L->suivant != NULL) {
 116                 return L = rechercher_rec(e, L->suivant);
 117         }
 118 }
 119
 120 Liste ajouter_rec(element e, Liste L)
 121 {
 122         if (!L || !(L->valeur < e)) {
 123                 return creer_maillon(e, L);
 124         }
 125
 126         L->suivant = ajouter_rec(e, L->suivant);
 127
 128         return L;
 129 }
 130
 131 Liste supprimer_iter(element e, Liste L)
 132 {
 133         Cellule *pavant = NULL;
 134         Cellule *pdebut = L;
 135
 136         while (L != NULL) {
 137                 /* supprimer en fin de liste */
 138                 if (L->valeur == e && L->suivant == NULL) {
 139                         free(L);
 140                         pavant->suivant = NULL;
 141                         return pdebut;
 142                         /* supprimer au début de la liste */
 143                 } else if (L->valeur == e && pavant == NULL) {
 144                         Cellule *pcourant = L;
 145                         free(L);
 146                         return pcourant->suivant;
 147                         /* supprimer au mileu de la liste */
 148                 } else if (L->valeur == e) {
 149                         Cellule *pcourant = L;
 150                         free(L);
 151                         L = pavant;
 152                         L->suivant = pcourant->suivant->suivant;
 153                         return pdebut;
 154                 }
 155                 pavant = L;
 156                 L = L->suivant;
 157         }
 158 }
 159
 160 Liste supprimer_rec(element e, Liste L)
 161 {
 162         if (L == NULL) {
 163                 return L;
 164         }
 165         if (L->valeur == e) {
 166                 Cellule *p = L;
 167                 L = L->suivant;
 168                 free(p);
 169         } else {
 170                 L->suivant = supprimer_rec(e, L->suivant);
 171         }
 172         return L;
 173 }
 174
 175 Liste inverser_iter(Liste L)
 176 {
 177         /* ... */
 178 }
 179
 180 Liste inverser_rec(Liste L)
 181 {
 182         /* ... */
 183 }
 184
 185 void liberer_iter(Liste L)
 186 {
 187         while (!L) {
 188                 Cellule *pcourant = L;
 189                 free(L);
 190                 L = pcourant->suivant;
 191         }
 192 }
 193
 194 void liberer_rec(Liste L)
 195 {
 196         if (!L) {
 197                 liberer_rec(L->suivant);
 198                 free(L);
 199         }
 200 }
 201
 202 /****************************************************************************/
 203 int main()
 204 {
 205         int x;
 206         Liste L = NULL;
 207         L = ajouter_iter(2, L);
 208         L = ajouter_iter(1, L);
 209         L = ajouter_iter(3, L);
 210         L = ajouter_iter(4, L);
 211         printf("Saisir un entier a chercher dans la liste L\n");
 212         scanf("%d", &x);
 213         printf("L a pour longueur %d\n", longueur_rec(L));
 214         visualiser_iter(L);
 215         visualiser_rec(L);
 216         if (rechercher_iter(x, L))
 217                 printf("L'element %d est present dans L\n", x);
 218         else
 219                 printf("L'element %d n'est pas present dans L\n", x);
 220         if (rechercher_rec(x, L) != NULL)
 221                 printf("L'element %d est present dans L\n", x);
 222         else
 223                 printf("L'element %d n'est pas present dans L\n", x);
 224         L = ajouter_rec(6, L);
 225         L = ajouter_rec(5, L);
 226         L = ajouter_rec(7, L);
 227         visualiser_iter(L);
 228         /* L = supprimer_iter(1, L);
 229            L = supprimer_iter(4, L);
 230            L = supprimer_iter(2, L); */
 231         L = supprimer_rec(1, L);
 232         L = supprimer_rec(4, L);
 233         L = supprimer_rec(2, L);
 234         visualiser_rec(L);
 235         visualiser_iter(L);
 236         liberer_rec(L);
 237         //liberer_iter(L);
 238         /* ... */
 239 }
 240
 241 /****************************************************************************/
 242 /* vim:noet:ts=8:sw=8:textwidth=80 */