/* * File: main.c * Author: Andréa * * Created on 14 octobre 2010, 10:54 */ #include #include #define DEBUG 0 #define DEBUG_LAST 1 typedef struct CEL { int int_valeur; struct CEL* sCEL_suivant; } cellule; typedef int boolean; cellule* CreeCellule (int val); void AfficheListe(cellule* liste); cellule* InsereSansDoublon (cellule* liste, int val); cellule* CreeListe (int* vals); cellule* CreeCellule (int val) { cellule* cell; if(DEBUG) printf("\n\n 'CreeCellule'\n"); if(DEBUG) printf(" '%d'\n",val); cell = (cellule *)malloc(sizeof(cellule)); cell->int_valeur = val; cell->sCEL_suivant = NULL; if(DEBUG) { printf("\n"); AfficheListe(cell); printf("\n\n"); } return cell; } void AfficheListe(cellule* liste) { if(DEBUG) printf("\n\n 'AfficheListe'\n"); if(DEBUG) printf(" '%d'\n",liste); if(liste == NULL) printf("Liste vide !"); while(liste != NULL) { printf(" : '%d'\n",liste->int_valeur); liste = liste->sCEL_suivant; } } boolean isIn(cellule* liste,int val) { while(liste != NULL) { if(liste->int_valeur == val) return 1; liste = liste->sCEL_suivant; } return 0; } cellule* InsereSansDoublon (cellule* liste, int val) { cellule* cursor = NULL; if(DEBUG) printf("\n\n 'InsererSansDoublons'\n"); if(DEBUG) printf(" '%d'\n",liste); if(DEBUG) printf(" '%d'\n",val); if(liste == NULL) { if(DEBUG) printf("\n"); return CreeCellule(val); } else { if(DEBUG) printf(" '%d'\n",isIn(liste,val)); if( !isIn(liste,val) ) { cursor = liste; while(cursor->sCEL_suivant != NULL) cursor = cursor->sCEL_suivant; cursor->sCEL_suivant = CreeCellule(val); } if(DEBUG) printf(" '%d'\n",liste); if(DEBUG) printf(" '%d'\n",liste->int_valeur); if(DEBUG) printf(" '%d'\n",liste->sCEL_suivant); return liste; } } cellule* CreeListe (int* vals) { cellule* liste = NULL; cellule* head = NULL; if(DEBUG) printf("\n\n 'Creer liste'\n"); if(DEBUG) printf(" '%d'\n",*vals); if(*vals != -1) head = InsereSansDoublon(head,*vals); else return NULL; liste = head; if(DEBUG) printf(" '%d'\n",head); if(DEBUG) printf(" '%d'\n",head->int_valeur); if(DEBUG) printf(" '%d'\n",head->sCEL_suivant); if(DEBUG) printf(" '%d'\n",liste); while(*vals != -1) { if(DEBUG) printf("\t '%d'\n",*vals); liste = InsereSansDoublon(liste,*vals); if(DEBUG) printf(" '%d'\n",head); if(DEBUG) printf(" '%d'\n",head->int_valeur); if(DEBUG) printf(" '%d'\n",head->sCEL_suivant); if(DEBUG) printf(" '%d'\n",liste); if(DEBUG) printf(" '%d'\n",liste->int_valeur); if(DEBUG) printf(" '%d'\n",liste->sCEL_suivant); if(DEBUG) { printf("\n"); AfficheListe(head); printf("\n"); } vals++; } if(DEBUG) { printf("\n"); AfficheListe(head); printf("\n\n"); } return head; } void DetruitListe (cellule** liste) { if(DEBUG) printf("\n\n 'DetruitListe'\n"); if(DEBUG) printf(" '%d'\n",liste); if(*liste != NULL) { DetruitListe(&((*liste)->sCEL_suivant)); (*liste)->sCEL_suivant = NULL; free(*liste); (*liste) = NULL; } } void split (cellule* liste, cellule** un, cellule** deux) { if(DEBUG_LAST) printf("\n\n 'split'\n"); if(DEBUG_LAST) printf(" '%d'\n",liste); if(DEBUG_LAST) printf(" '%d'\n",un); if(DEBUG_LAST) printf(" '%d'\n",*un); if(DEBUG_LAST) printf(" '%d'\n",deux); if(DEBUG_LAST) printf(" '%d'\n",*deux); *un = NULL; *deux = NULL; int moduleur = 0; while(liste != NULL) { if(DEBUG_LAST) printf(" '%d'\n",moduleur); if(DEBUG_LAST) printf(" '%d'\n",(moduleur % 2)); if(DEBUG_LAST) printf(" '%d'\n",liste->int_valeur); if(++moduleur % 2) { *un = InsereSansDoublon(*un,liste->int_valeur); if(DEBUG_LAST) printf(" '%d'\n",un); if(DEBUG_LAST) printf(" '%d'\n",*un); } else { *deux = InsereSansDoublon(*deux,liste->int_valeur); if(DEBUG_LAST) printf(" '%d'\n",deux); if(DEBUG_LAST) printf(" '%d'\n",*deux); } liste = liste->sCEL_suivant; } } cellule* join (cellule* liste1, cellule *liste2) { int moduleur = 0; cellule* liste = NULL; for(moduleur = 0;liste1 && liste2;moduleur ++) { if(moduleur % 2) { liste = InsereSansDoublon(liste,liste1->int_valeur); liste1 = liste1->sCEL_suivant; } else { liste = InsereSansDoublon(liste,liste2->int_valeur); liste2 = liste2->sCEL_suivant; } } if(liste1) { while(liste1) { liste = InsereSansDoublon(liste,liste1->int_valeur); liste1 = liste1->sCEL_suivant; } } else if(liste2) { while(liste2) { liste = InsereSansDoublon(liste,liste2->int_valeur); liste2 = liste2->sCEL_suivant; } } return liste; } int main(int argc, char** argv) { int valeurs[] = {1,2,4,8,16,48,8,2,22,-1}; cellule* liste = NULL; cellule* un = NULL; cellule* deux = NULL; liste = CreeListe(valeurs); printf("\nliste total\n"); AfficheListe(liste); /* DetruitListe(&liste); AfficheListe(liste); */ un = (cellule *)malloc(sizeof(un)); deux = (cellule *)malloc(sizeof(deux)); split(liste,&un,&deux); printf("\nliste 1\n"); AfficheListe(un); printf("\nliste 2\n"); AfficheListe(deux); printf("\nJointure \n"); AfficheListe(join(un,deux)); return (EXIT_SUCCESS); }