00001 #include <stddef.h>
00002 #include <stdio.h>
00003 #include <stdlib.h>
00004 
00005     /* Définition de la structure cell */
00006 struct cell {
00007     int           data;
00008     struct cell * next;
00009 };
00010 typedef struct cell * list_t; // le type list_t permet de représenter une liste
00011 typedef struct cell   cell_t; // le type cell_t permet de représenter une cellule
00012 
00013     /* Insère un élément en tête de liste - renvoie la liste complétée */
00014 list_t insert_in_head(int element, list_t L) {
00015     // Création de la nouvelle cellule
00016     cell_t * new_cell = (cell_t *) malloc(sizeof(cell_t));
00017     if (new_cell == NULL) return NULL;
00018     new_cell->data = element;
00019     new_cell->next = L; // insertion en tête
00020     // La liste résultat est en fait la première cellule
00021     return (list_t) new_cell; // le cast est facultatif
00022 }
00023 
00024     /* insertion en tête - version procédurale */
00025 void proc_insert_in_head(int element, list_t * L) {
00026     list_t* old = L;
00027     *L = insert_in_head(element, *L);
00028     if (L == NULL) *L = *old; // au cas ou l'insertion a échoué
00029 }
00030 
00031     /* Insère un élément en queue de liste - renvoie la liste complétée */
00032 list_t insert_in_tail(int element, list_t L) {
00033     // Création de la nouvelle cellule
00034     cell_t * new_cell = (cell_t *) malloc(sizeof(cell_t));
00035     if (new_cell == NULL) return NULL;
00036     new_cell->data = element;
00037     new_cell->next = NULL; // insertion en queue
00038     // recherche de l'endroit où effectuer l'insertion
00039     if (L == NULL) return (list_t) new_cell;
00040         // à partir de là, L!=NULL et L->next a un sens
00041     list_t tmp = L; 
00042     while (tmp->next != NULL) tmp = tmp->next; // on va à la dernière cellule
00043     // on effectue l'insertion et on renvoie la liste complétée
00044     tmp->next = (list_t) new_cell; // le cast est facultatif
00045     return L;
00046 }
00047 
00048     /* insertion en queue - version procédurale */
00049 void proc_insert_in_tail(int element, list_t * L) {
00050     list_t* old = L;
00051     *L = insert_in_tail(element, *L);
00052     if (L == NULL) *L = *old;
00053 }
00054 
00055     /* suppression de l'élément en tête de liste */
00056 list_t delete_in_head(list_t L) {
00057     if (L == NULL) return L;
00058     list_t res = L->next;
00059     free(L); // libération de la première cellule   
00060     return res;  
00061 } 
00062 
00063     /* suppression de l'élément en tête de liste - version procédurale */
00064 void proc_delete_in_head(list_t * L) {
00065     *L = delete_in_head(*L);
00066 } 
00067 
00068     /* suppression de l'élément en queue de liste */
00069 list_t delete_in_tail(list_t L) {
00070     if (L == NULL) return L;
00071     if (L->next == NULL) { // liste à un seul élément
00072         free(L);
00073         return NULL;
00074     }
00075     list_t tmp    = L->next;
00076     cell_t * prec = L; // pointeur sur la cellule précédant tmp
00077     while(tmp->next != NULL) {
00078         prec = tmp;
00079         tmp  = tmp->next;
00080     }  
00081     // ici, tmp est la dernière cellule (en particulier, prec->next est tmp)
00082     prec->next = NULL; // mise à jour de la cellule voisine
00083     free(tmp);         // libération de la dernière cellule   
00084     return L;  
00085 } 
00086 
00087     /* suppression de l'élément en queue de liste - version procédurale */
00088 void proc_delete_in_tail(list_t * L) {
00089     *L = delete_in_tail(*L); // pour changer :-)
00090 }
00091 
00092     /* suppression de la liste complete */
00093 void delete_list(list_t *L) {
00094     while(*L != NULL) proc_delete_in_head(L);
00095 }
00096 
00097     /* affiche le contenu de la liste L */
00098 void print_list(list_t L) {
00099     while(L != NULL) { // on aurait pu écrire 'while (L)'
00100         printf("%d -> ", L->data);
00101         L = L->next;
00102     }
00103     printf("NULL\n");
00104 }
00105 
00106 list_t insert_in_head     (int element, list_t L);
00107 list_t insert_in_tail     (int element, list_t L);
00108 void   proc_insert_in_head(int element, list_t * L);
00109 void   proc_insert_in_tail(int element, list_t * L);
00110 
00111 list_t delete_in_head     (list_t L);
00112 list_t delete_in_tail     (list_t L);
00113 void   proc_delete_in_head(list_t * L);
00114 void   proc_delete_in_tail(list_t * L);
00115 
00116 void delete_list(list_t *L);
00117 
00118 int main()
00119 {
00120     /* Création de la liste L = (10, 11, 12, 13, 14, 15) */
00121     list_t L = insert_in_head(11, insert_in_head(12, NULL)); // avec insert_in_head
00122     proc_insert_in_head(10, &L);                             // version procédurale
00123     L = insert_in_tail(14,  insert_in_tail(13, L)); // ajout en queue de liste
00124     proc_insert_in_tail(15, &L);                    // version procédurale
00125     printf("L = "); print_list(L);
00126     
00127     /* Suppression d'élément en tête */
00128     L = delete_in_head(L);   
00129     proc_delete_in_head(&L);                        // version procédurale
00130     printf("Suppression de deux éléments en tête  : L = ");
00131     print_list(L);
00132 
00133     /* Suppression d'élément en queue */
00134     L = delete_in_tail(L);   
00135     proc_delete_in_tail(&L);                        // version procédurale
00136     printf("Suppression de deux éléments en queue : L = ");
00137     print_list(L);
00138     
00139     /* Supression de la liste */
00140     delete_list(&L);
00141     printf("Suppression de la liste : L = ");
00142     print_list(L);
00143     return 0;
00144 }
00145 
00146 
00147 
00148