00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 
00004 struct cell {
00005     int           data;
00006     struct cell * next;
00007     struct cell * prev; 
00008 };
00009 typedef struct cell cell_t;
00010 typedef struct {
00011     cell_t * start; // pointeur sur le premier élément 
00012     cell_t * end;   // pointeur sur le dernier élément 
00013 } list_t;
00014 
00015     /* Création d'une liste vide. */
00016 list_t * create_list() {
00017     list_t * L = (list_t *) malloc(sizeof(list_t));
00018     if (L != NULL) {
00019         L->start = NULL;
00020         L->end   = NULL;
00021     }
00022     return L;
00023 }
00024     /* Affiche le contenu de la liste L. */
00025 void print_list(list_t * L) {
00026     if (L == NULL) return;
00027     cell_t * tmp = L->start;
00028     while(tmp != NULL) { 
00029         printf("%2d -> ", tmp->data);
00030         tmp = tmp->next;
00031     }
00032     printf("NULL\n");
00033 }
00034     /* Renvoie le nombre d'éléments de la liste. */
00035 long get_size(list_t * L) {
00036     if (L == NULL) return -1;
00037     cell_t * tmp = L->start;
00038     long res = 0; 
00039     for(; tmp != NULL; tmp=tmp->next,res++);
00040     return res;
00041 }
00042     /* Insère un élément en tete de liste. */
00043 int insert_in_head(int element, list_t * L) {
00044     if (L == NULL) return -2;
00045     // Création de la nouvelle cellule.
00046     cell_t * new_cell = (cell_t *) malloc(sizeof(cell_t));
00047     if (new_cell == NULL) return -1;
00048     new_cell->data = element;
00049     new_cell->next = L->start; // Insertion en tête.
00050     new_cell->prev = NULL;
00051     // Deuxième étape: mise-à-jour de la liste et des cellules voisines.
00052     if (L->start != NULL) (L->start)->prev = new_cell;
00053     if (L->end == NULL) L->end = new_cell;  
00054     L->start = new_cell;
00055     return 0;
00056 }
00057     /* Insère un élément en queue de liste. */
00058 int insert_in_tail(int element, list_t * L) {
00059     if (L == NULL) return -2;
00060     // Création de la nouvelle cellule.
00061     cell_t * new_cell = (cell_t *) malloc(sizeof(cell_t));
00062     if (new_cell == NULL) return -1;
00063     new_cell->data = element;
00064     new_cell->next = NULL; // Insertion en tête.
00065     new_cell->prev = L->end;
00066     // Deuxième étape: mise-à-jour de la liste et des cellules voisines.
00067     if (L->end   != NULL) (L->end)->next = new_cell;
00068     if (L->start == NULL) L->start = new_cell;  
00069     L->end = new_cell;
00070     return 0;
00071 }
00072     /* Suppression du contenu de la liste L. */
00073 void free_content_of(list_t * L) {
00074     if (L == NULL) return; 
00075     cell_t * tmp = L->start, *cur = NULL;
00076     while ((cur = tmp) != NULL) { // cur: pointeur sur la cellule courante.
00077         tmp = tmp->next;
00078         free(cur);  // Libération des éléments.
00079     }
00080     L->start = NULL;
00081     L->end   = NULL;
00082 }
00083     /* Suppression de la liste L et de son contenu. */
00084 void destroy(list_t * L) {
00085     free_content_of(L);
00086     free(L);
00087 }
00088     /* Ajout au bon endroit de e dans la liste ordonnée;
00089        renvoie 0 en cas de succès, 1 en cas d'erreur (e déjà présent). */
00090 int insert(int e, list_t * L) {
00091     if (L == NULL) return -2;
00092     if ((L->start == NULL) || ((L->start)->data > e)) {
00093         // Cas liste vide ou premier élément plus grand que e.
00094         if (! insert_in_head(e, L)) return 0;
00095         else return -1;
00096     }
00097     if ((L->end)->data < e) {
00098         if (! insert_in_tail(e, L)) return 0;
00099         else return -1;
00100     }
00101     // Ici, e est dans l'intervalle des valeurs de la liste.
00102     cell_t * tmp = L->start;
00103     while(tmp->data < e) tmp = tmp->next; // Déplacement jusqu'au bon endroit.
00104     if (tmp->data == e) return -1;
00105     // Création de la nouvelle cellule
00106     cell_t * new_cell = (cell_t *) malloc(sizeof(cell_t));
00107     if (new_cell == NULL) return -1;
00108     new_cell->data = e;
00109     new_cell->next = tmp; 
00110     new_cell->prev = tmp->prev;
00111     // Deuxième étape: mise-à-jour des cellules voisines.
00112     (tmp->prev)->next = new_cell;
00113     tmp->prev = new_cell;
00114     return 0;
00115 }
00116     /* Suppression de l'entier e de la liste ordonnée;
00117        renvoie 0 en cas de succès, 1 en cas d'erreur (e absent de la liste). */
00118 int delete(int e, list_t * L) {
00119     if (L == NULL) return -2;
00120     if ((L->start == NULL) || (L->start->data > e) || (L->end->data < e))
00121         return -1;
00122     cell_t * tmp = L->start;
00123     //Cas "suppression du premier élément": il faut au moins mettre à jour L->start.
00124     if (tmp->data == e) {
00125             L->start = tmp->next;
00126             if (L->start != NULL) L->start->prev = NULL; 
00127             else L->end = NULL; // On avait une liste à un élément.
00128             free(tmp);
00129             return 0;
00130     }
00131     // Cas "suppression du dernier élément": il faut au moins mettre à jour L->end.
00132     tmp = L->end;
00133     if (tmp->data == e) {
00134             L->end = tmp->prev;
00135             if (L->end != NULL) L->end->next = NULL;
00136             else L->start = NULL; // On avait une liste à un élément
00137             free(tmp);
00138             return 0;
00139     }
00140     // Cas "suppression d'un élément intermédiaire".
00141     tmp = L->start->next;
00142     while(tmp->data < e) tmp = tmp->next;     // On va au bon endroit.
00143     if (tmp->data != e) return -1;  // e n'est pas dans la liste.
00144     cell_t * tmp_prev = tmp->prev;
00145     cell_t * tmp_next = tmp->next;
00146     tmp_prev->next = tmp_next;
00147     tmp_next->prev = tmp_prev;
00148     free(tmp);
00149     return 0;
00150 }
00151      /* Fonction qui facilite les tests d'insertion. */
00152 void test_add(int tab[], size_t n, list_t * L) {
00153     size_t i;
00154     for (i=0; i<n; i++) {
00155         printf("Ajout de %2d : [%d]",tab[i],insert(tab[i],L));
00156         printf(" --> |L|=%lu et L = ", get_size(L));  
00157         print_list(L);
00158     }
00159 }
00160      /* Fontion qui facilite les tests de suppression. */
00161 void test_delete(int tab[], size_t n, list_t * L) {
00162     size_t i;
00163     for (i=0; i<n; i++) {
00164         printf("Suppression de %2d : [%d]",tab[i],delete(tab[i],L));
00165         printf(" --> |L|=%lu et L = ", get_size(L));  
00166         print_list(L);
00167     }
00168 }
00169 
00170 int main() 
00171 {
00172     list_t * L = create_list();
00173     int to_add[] = { 13, 10, 14, 11, 9, 12,     
00174                    13, 12, 11 }; // testent l'ajout de valeurs déjà présentes
00175     int to_del[] = { 9, 14, 11, 5, 15, 11};
00176     printf("*** tests d'insertion (listes non ordonnées) ***\n");
00177     insert_in_head(10, L);
00178     insert_in_head(9,  L);
00179     insert_in_tail(10, L);
00180     insert_in_tail(9,  L);
00181     printf(" -> L = "); print_list(L);
00182     free_content_of(L);
00183     printf("\n***   tests d'insertion (listes ordonnées)  ***\n");    
00184     test_add(to_add, sizeof(to_add)/sizeof(int), L);
00185     printf("\n*** tests de suppression (listes ordonnées) ***\n");    
00186     test_delete(to_del, sizeof(to_del)/sizeof(int), L);
00187     destroy(L);
00188     return 0;
00189 }