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 Liste ajouter_iter(element e, Liste L)
  16 {
  17         Cellule *pc, *p1 = L, *p2 = NULL;
  18
  19         pc = (Cellule *) malloc(sizeof(Cellule));
  20         pc->valeur = e;
  21         pc->suivant = NULL;
  22
  23         if (!L)                 /* liste vide */
  24                 return pc;
  25
  26         while (p1 && (e >= p1->valeur)) {
  27                 p2 = p1;
  28                 p1 = p1->suivant;
  29         }
  30
  31         if (!p2) {              /* insertion en tete */
  32                 pc->suivant = L;
  33                 L = pc;
  34         } else {                /* insertion entre p2 et p1 */
  35                 p2->suivant = pc;
  36                 pc->suivant = p1;
  37         }
  38
  39         return L;
  40 }
  41
  42 int longueur_iter(Liste L)
  43 {
  44         int longueur = 0;
  45
  46         while (L != NULL) {
  47                 L = L->suivant;
  48                 longueur++;
  49         }
  50         return longueur;
  51 }
  52
  53 int longueur_rec(Liste L)
  54 {
  55         if (L != NULL) {
  56                 return 1 + longueur_rec(L->suivant);
  57         } else {
  58                 return 0;
  59         }
  60 }
  61
  62 void visualiser_iter(Liste L)
  63 {
  64         int compteur = 0;
  65
  66         printf("--Debut--\n");
  67         while (L != NULL) {
  68                 printf("L[%d]->value=%d\n", compteur, L->valeur);
  69                 L = L->suivant;
  70                 compteur++;
  71         }
  72         printf("--Fin--\n");
  73 }
  74
  75 void _visualiser_rec(Liste L, int compteur)
  76 {
  77         if (L != NULL) {
  78                 if (compteur == 0)
  79                         printf("--Debut--\n");
  80                 printf("L[%d]->value=%d\n", compteur, L->valeur);
  81                 compteur++;
  82                 _visualiser_rec(L->suivant, compteur);
  83                 if (compteur == (longueur_rec(L) - 1))
  84                         printf("--Fin--\n");
  85         }
  86
  87 }
  88
  89 void visualiser_rec(Liste L)
  90 {
  91         int compteur = 0;
  92
  93         _visualiser_rec(L, compteur);
  94 }
  95
  96 bool rechercher_iter(element e, Liste L)
  97 {
  98         bool rt_val = false;
  99
 100         while (L != NULL && L->valeur != e) {
 101                 L = L->suivant;
 102         }
 103         if (L->valeur == e)
 104                 rt_val = true;
 105         return rt_val;
 106 }
 107
 108 Liste rechercher_rec(element e, Liste L)
 109 {
 110 }
 111
 112 Liste ajouter_rec(element e, Liste L)
 113 {
 114         /* ... */
 115 }
 116
 117 Liste supprimer_iter(element e, Liste L)
 118 {
 119         /* ... */
 120 }
 121
 122 Liste supprimer_rec(element e, Liste L)
 123 {
 124         /* ... */
 125 }
 126
 127 Liste inverser_iter(Liste L)
 128 {
 129         /* ... */
 130 }
 131
 132 Liste inverser_rec(Liste L)
 133 {
 134         /* ... */
 135 }
 136
 137 /****************************************************************************/
 138 int main()
 139 {
 140         int x;
 141         Liste L = NULL;
 142         L = ajouter_iter(2, L);
 143         L = ajouter_iter(1, L);
 144         L = ajouter_iter(3, L);
 145         printf("Saisir un entier a ajouter a la liste L\n");
 146         scanf("%d", &x);
 147         L = ajouter_iter(x, L);
 148         printf("L a pour longueur %d\n", longueur_rec(L));
 149         visualiser_iter(L);
 150         visualiser_rec(L);
 151         if (rechercher_iter(3, L))
 152                 printf("Element 3 est present dans L\n");
 153         /* ... */
 154 }
 155
 156 /****************************************************************************/