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         if (!L)
  46                 return longueur;
  47
  48         while ( L->suivant != NULL)
  49         {
  50                 L = L->suivant;
  51                 longueur++;
  52         }
  53         return longueur;
  54 }
  55
  56 int longueur_rec(Liste L)
  57 {
  58         /* ... */
  59 }
  60
  61 void visualiser_iter(Liste L)
  62 {
  63         /* ... */
  64 }
  65
  66 void visualiser_rec(Liste L)
  67 {
  68         /* ... */
  69 }
  70
  71 int rechercher_iter(element e, Liste L)
  72 {
  73         /* ... */
  74 }
  75
  76 Liste rechercher_rec(element e, Liste L)
  77 {
  78         /* ... */
  79 }
  80
  81 Liste ajouter_rec(element e, Liste L)
  82 {
  83         /* ... */
  84 }
  85
  86 Liste supprimer_iter(element e, Liste L)
  87 {
  88         /* ... */
  89 }
  90
  91 Liste supprimer_rec(element e, Liste L)
  92 {
  93         /* ... */
  94 }
  95
  96 Liste inverser_iter(Liste L)
  97 {
  98         /* ... */
  99 }
 100
 101 Liste inverser_rec(Liste L)
 102 {
 103         /* ... */
 104 }
 105
 106 /****************************************************************************/
 107 int main()
 108 {
 109         int x;
 110         Liste L = NULL;
 111         scanf("%d", &x);
 112         L = ajouter_iter(x, L);
 113         printf("longueur=%d\n", longueur_iter(L));
 114         visualiser_iter(L);
 115         /* ... */
 116 }
 117
 118 /****************************************************************************/