/*************************************************************************** Langage C TD nø2 Exercice 2 Olivier SANNIER Denis VANPEPERSTRAETE Groupe C ****************************************************************************/ #include #include #include /* ------------------------------------------------------------------------ D‚finition de la structure elem qui contient un entier et deux pointeurs sur une structure de mˆme type. On pourra ainsi cr‚er une liste doublement chain‚e d'entiers. -------------------------------------------------------------------------- */ typedef struct Elem { int val; struct Elem *avant, *apres; }elem; /* ------------------------------------------------------------------------ void liberetout(elem **debut) cette proc‚dure libŠre toute la m‚moire allou‚e … une liste doublement chain‚e tri‚e. Le premier ‚l‚ment de cette liste est point‚e par le pointeur debut pass‚ en paramŠtre. entr‚e --> debut : pointeur sur le d‚but de la liste chain‚e, pass‚ par adresse. sortie --> rien -------------------------------------------------------------------------- */ void liberetout(elem **debut) { elem *temp; while (*debut!=NULL) { // recr‚ation des liens temp = *debut; *debut=(*debut)->apres; (*debut)->avant = NULL; // lib‚ration de la m‚moire free(temp); } } /* ------------------------------------------------------------------------ void insertion(elem **debut, int nb) Cette proc‚dure ajoute un nouvel ‚l‚ment ayant pour valeur nb dans la liste doublement chain‚e tri‚e point‚e par debut. Pour cela, on recherche d'abord l'emplacement o— ins‚rer et on effectue une insertion classique, c'est … dire qu'on alloue, qu'on met en place la valeur puis qu'on refait les liens. Cependant, il convient de noter que le pointeur debut n'est modifi‚ que si on se trouve au d‚but de la liste chain‚e. entr‚e --> debut : pointeur sur le d‚but de la liste chain‚e, pass‚ par adresse. nb : valeur … ins‚rer. sortie --> rien -------------------------------------------------------------------------- */ void insertion(elem **debut, int nb) { elem *rech, *temp; rech = *debut; while ((rech!=NULL)&&(rech->val<=nb)) rech = rech->apres; // allocation de la m‚moire et mise en place de la valeur temp = (elem *)malloc(sizeof(elem)); temp-> val = nb; // cr‚ation des nouveaux liens. if (rech==*debut){ temp->apres = *debut; (*debut)->avant = temp; temp->avant=NULL; *debut=temp; } else { temp->apres = rech; temp->avant = rech->avant; (rech->avant)->apres = temp; rech->avant = temp; } } /* ------------------------------------------------------------------------ void affiche(elem **debut) Cette proc‚dure affiche une liste doublement chain‚e tri‚e sur la sortie standard dans le sens croissant ou d‚croissant selon la valeur du paramŠtre sens : 1 sens croissant, 0 sens d‚croissant Dans le cas du sens d‚croissant, le pointeur actuel est d'abord positionn‚ en fin de chaine puis celle-ci est parcourue … l'envers. entr‚e --> debut : pointeur sur le d‚but de la liste chain‚e. sens : indique le sens d'affichage (1 = croissant, 0 = d‚croisssant) sortie --> rien -------------------------------------------------------------------------- */ void affiche(elem *debut, int sens) { elem *actuel; if (sens) { actuel=debut; while (actuel!=NULL) { printf("%3d", actuel->val); actuel=actuel->apres; } } else { actuel=debut; while (actuel->apres!=NULL) actuel=actuel->apres; while (actuel!=NULL) { printf("%3d", actuel->val); actuel=actuel->avant; } } } /*------------------------------------------------------------------------- elem *supprime(elem **debut, elem *suppr) Cette fonction supprime l'‚l‚ment point‚ par suppr de la liste chain‚e dont le premier ‚l‚ment est point‚ par debut. si suppr est ‚gal … *debut, il faut le pointeur de d‚but de chaine. Sinon, il suffit de modifier le lien de l'‚l‚ment pr‚c‚dent celui … supprimer. Dans tous les cas, on libŠre la m‚moire occup‚e par suppr et on renvoie un pointeur sur l'‚l‚ment qui ‚tait situ‚ juste aprŠs lui avant la suppression. entr‚e --> debut : pointeur sur le d‚but de la liste chain‚e, pass‚ par adresse. suppr : pointeur sur l'‚l‚ment … supprimer sortie --> un pointeur sur l'‚l‚ment qui ‚tait situ‚ aprŠs celui point‚ par suppr avant qu'il ne soit supprim‚. -------------------------------------------------------------------------*/ elem *supprime(elem **debut, elem *suppr) { elem *retour; // sommes-nous en d‚but de chaine ? if (suppr==*debut) { // oui, alors on modifie debut *debut=suppr->apres; retour=*debut; } else { // sinon, on ne modifie que le lien de l'‚l‚ment pr‚c‚dent (suppr->avant)->apres=suppr->apres; retour=suppr->apres; } // dans tous les cas, le lien de l'‚l‚ment suivant doit ˆtre modifi‚ (suppr->apres)->avant=suppr->avant; // on libŠre la m‚moire et on retourne le pointeur sur l'‚l‚ment qui // suivait l'‚l‚ment que l'on vient de supprimer free(suppr); return retour; } /* ------------------------------------------------------------------------ void supprime_nb(elem **debut, int nb) Cette proc‚dure supprime dans une liste chain‚e tous les ‚l‚ments dont le champ val est ‚gal … nb. Pour cela, on utilise un pointeurs : actuel qui pointe sur l'‚l‚ment en cours de comparaison. Lorsque actuel->val est ‚gal … nb, on fait appel … la fonction supprime qui va supprimer cet ‚l‚ment de la chaine et lib‚rer la m‚moire qu'il occupait. D'autre part, on ne change la valeur de actuel pour passer … l'‚l‚ment suivant que dans le cas o— on n'a pas supprim‚ d'‚l‚ment. En effet, si on passait … l'‚l‚ment suivant dans tous les cas, on sauterait un ‚l‚ment lors d'une suppression. la boucle est r‚alis‚e tant que actuel est diff‚rent de NULL, c'est … dire tant que l'on a pas atteint le dernier ‚l‚ment. entr‚e --> debut : pointeur sur le d‚but de la liste chain‚e, pass‚ par adresse. nb : nombre … supprimer de la liste chain‚e sortie --> rien -------------------------------------------------------------------------- */ void supprime_nb(elem **debut, int nb){ elem *actuel; // initialisation de actuel et prec actuel = *debut; // test en d‚but de boucle ce qui ‚vite de traiter une liste chain‚e // qui ne contient aucun ‚l‚ment while(actuel!=NULL) { // l'‚l‚ment actuel doit-il ˆtre supprim‚ ? if (actuel->val==nb) // oui, alors on supprime actuel=supprime(debut, actuel); else { // l'‚l‚ment ne devant pas ˆtre supprim‚, on passe au suivant actuel=actuel->apres; } } } /*------------------------------------------------------------------------- void main(void) C'est la proc‚dure principale. Elle gŠre un menu qui propose d'essayer toutes les fonctions de gestion de liste doublement chain‚e tri‚e. entr‚e --> rien sortie --> rien ---------------------------------------------------------------------------*/ void main(void) { char cara; elem *debut; int valeur; debut = NULL; do { clrscr(); printf("--- Langage C : TD2, exercice 2---"); printf("\n1 : Ajouter un nombre dans la liste doublement chain‚e tri‚e"); printf("\n2 : Afficher la liste doublement chain‚e tri‚e"); printf("\n3 : Supprimer un nombre de la liste doublement chain‚e tri‚e"); printf("\nq : Quitter"); printf("\n\nVotre choix ? "); cara = getche(); switch (cara) { case '1' : printf("\nNombre … ajouter ? "); scanf("%d", &valeur); insertion(&debut, valeur); break; case '2' : printf("\n"); affiche(debut, 1); getch(); break; case '3' : printf("\nNombre … supprimer ? "); scanf("%d", &valeur); supprime_nb(&debut, valeur); break; case 'q' : case 'Q' : break; default : printf("\nMauvais choix"); getch(); break; } }while((cara!='Q')&&(cara!='q')); liberetout(&debut); }