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