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