Votre question

Besoin d'aide pour la résolution d'un problème en algorithmique

Tags :
  • element
  • Programmation
Dernière réponse : dans Programmation
2 Mars 2009 10:56:06

Voici le Sujet:
On se propose d'écrire une fonction appelée Supprimer qui prend en argument une Liste L et retourne la liste L privée de son premier élément de tête.

Et moi ma solution :

Fonction SUPPRIMER_X(X:entier;L:liste):liste
Variable
A,B : liste
Début
Si L= NULL alors
Début
A <= NULL
Fin
Sinon
Début
Si L^.Val=X alors
Début
A <= SUPPRIMER_X(X ;L^.lien)
Fin
Sinon
Début
NOUVEAU (B)
B^.Val <= L^.Val
B^.Lien <= SUPPRIMER_X(X ;L^.lien)
A <= B
Fin
Fin
Retourner (A)
Fin

Autres pages sur : besoin aide resolution probleme algorithmique

9 Mars 2009 17:52:17

Oulala...Ce qui est bien c'est que tu sembles faire les questions et les réponses, ce qui est moins bien c'est ta réponse. Pourquoi préciser dans le prototype X:entier, si tu veux seulement enlevé le premier élément de la liste ? Pourquoi faire un traitement récursif, qui va exploser ta mémoire si la liste est longue ? Enfin pourquoi recopier ta liste dans une aurte pour ne jamais la retourner ? Peut être que ta question c'est de supprimer le 1er élément X rencontré dans la liste ? Ma réponse dépendrait du fait que la liste soit simplement chaînée ou doublement chaînée...
Si tu précises ta question je reviendrai t'apporter une réponse plus "algorithmique".
10 Mars 2009 09:07:45


Attention !!! Il ya une erreur dans le sujet. Voici le bon:
On se propose d'écrire une fonction appelée Supprimer_x qui prend en argument un élément X et L une Liste et retourne la liste L privée de toutes les occurrences de X.

C’est une liste simplement liée.
10 Mars 2009 15:21:55

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct Element {
  5. int value;
  6. struct Element *suivant;
  7. }Element;
  8.  
  9. typedef struct Liste {
  10. Element *debut;
  11. Element *fin;
  12. }Liste;
  13.  
  14. void addToList(Liste * liste, int num) {
  15. Element *e = (Element*)malloc(sizeof(Element));
  16. e->value = num;
  17. if (liste->debut == NULL) { //La liste est vide, ajout premier element
  18. liste->debut = e;
  19. liste->fin = e;
  20. } else { //La liste est non vide, insertion en fin
  21. liste->fin->suivant = e;
  22. liste->fin = e;
  23. }
  24. }
  25.  
  26. void printList(Liste * liste) {
  27. if (liste == NULL || liste->debut == NULL) return;
  28. Element * c = liste->debut;
  29. while (c != NULL) {
  30. printf("'%d'", c->value);
  31. c = c->suivant;
  32. if (c != NULL) {
  33. printf(", ");
  34. } else {
  35. printf("\n");
  36. }
  37. }
  38. if (liste->debut != NULL)
  39. printf("Debut = %d",liste->debut->value);
  40. if (liste->fin != NULL)
  41. printf(" Fin = %d",liste->fin->value);
  42. printf("\n");
  43. }
  44.  
  45. void freeList(Liste * liste) {
  46. if (liste == NULL) return;
  47. Element * c = liste->debut;
  48. while (c != NULL) {
  49. c = c->suivant;
  50. if (c != NULL) {
  51. free(c);
  52. }
  53. }
  54. free(liste);
  55. }
  56.  
  57. void supprimerX(Liste * liste, int num) {
  58. if (liste == NULL) return;
  59. Element * temp = NULL;
  60. Element * current = liste->debut;
  61.  
  62. while (liste->debut != NULL && liste->debut->value == num) {
  63. temp = liste->debut->suivant;
  64. free(liste->debut);
  65. liste->debut = temp;
  66. }
  67.  
  68. if (liste->debut == NULL || liste->debut->suivant == NULL) {
  69. liste->fin = liste->debut;
  70. }
  71.  
  72. while (current != NULL && current->suivant != NULL) {
  73. if (current->suivant->value == num) {
  74. free(current->suivant);
  75. current->suivant = current->suivant->suivant;
  76. }
  77. if (current->suivant == NULL) { //Je redresse la fin au cas ou on l'ait supprimée
  78. liste->fin = current;
  79. }
  80. current = current->suivant;
  81. }
  82. }
  83.  
  84. int main () {
  85. Liste *list = (Liste*)malloc(sizeof(Liste));
  86.  
  87. addToList(list, 2);
  88. addToList(list, 3);
  89. addToList(list, 5);
  90. addToList(list, 6);
  91. addToList(list, 2);
  92. addToList(list, 3);
  93. addToList(list, 8);
  94. addToList(list, 3);
  95. addToList(list, 2);
  96.  
  97. printList(list);
  98. supprimerX(list, 2);
  99. printList(list);
  100. freeList(list);
  101. return 0;
  102. }


Bon voilà une implémentation possible, je ne dis pas que c'est la plus clean, cependant elle a le mérite de fonctionner correctement.
Pour construire le programme je compile avec gcc : gcc -Wall list.c -o list
et je lance avec ./list sous linux.

La fonction qui t'interresse est :
  1. void supprimerX(Liste * liste, int num)

Il y a un cas particulier si le premier élément de la liste contient le nombre a supprimer. Ensuite dans le cas général on garde le pointeur sur l'élément précédent celui testé afin d'affecter l'élément suivant comme successeur au prédésseur de celui qui contient le nombre (relit lentement la phrase précédente tu verras c'est pas si compliqué que ca :) ).

Bon courage.
Tom's guide dans le monde
  • Allemagne
  • Italie
  • Irlande
  • Royaume Uni
  • Etats Unis
Suivre Tom's Guide
Inscrivez-vous à la Newsletter
  • ajouter à twitter
  • ajouter à facebook
  • ajouter un flux RSS