Tom's Guide > Forum > Programmation > Besoin d'aide pour la résolution d'un problème en algorithmique

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

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

TomsGuide.com : 800 000 inscrits répondent à toutes vos questions high-tech et informatique. Pour obtenir de l'aide, inscrivez-vous gratuitement !
Créer un nouveau sujet Répondre
Mot :    Pseudo :           
 
shaici   02-03-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

Répondre
Liens sponsorisés
Inscrivez-vous ou connectez-vous pour masquer ceci.
icecat   09-03-2009 à 17:52:17
- 0 +

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".

------------------------------ A commune is where people join together to share their lack of wealth.
-- R. Stallman

 

Répondre à icecat

shaici   10-03-2009 à 09:07:45
- 0 +


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.

Répondre à shaici
icecat   10-03-2009 à 15:21:55
- 0 +

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. typedef struct Element {
  5.   int value;
  6.   struct Element *suivant;
  7. }Element;
  9. typedef struct Liste {
  10.         Element *debut;
  11.         Element *fin;
  12. }Liste;
  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. }
  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. }
  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. }
  57. void supprimerX(Liste * liste, int num) {
  58.   if (liste == NULL) return;
  59.   Element * temp = NULL;
  60.   Element * current = liste->debut;
  62.   while (liste->debut != NULL && liste->debut->value == num) {
  63.     temp = liste->debut->suivant;
  64.     free(liste->debut);
  65.     liste->debut = temp;
  66.   }
  68.   if (liste->debut == NULL || liste->debut->suivant == NULL) {
  69.     liste->fin = liste->debut;
  70.   }
  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. }
  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);
  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 :

Code :
  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.


Message édité par icecat le 10-03-2009 à 15:25:23
------------------------------ A commune is where people join together to share their lack of wealth.
-- R. Stallman

 

Répondre à icecat

Créer un nouveau sujet Répondre
Tom's Guide > Forum > Programmation > Besoin d'aide pour la résolution d'un problème en algorithmique
Aller à :

Il y a 1540 utilisateurs connus et inconnus. Pour voir la liste des connectés connus, cliquez ici.

Plan du forum
Forum Bestofmedia ©
2000-2009 Bestofmedia Group
Page générée en 0,421 secondes
Attention

Vous allez répondre sur un sujet resté inactif pendant plus de 6 mois.
Assurez-vous d'apporter des éléments nouveaux à la discussion avant de poursuivre.

Répondre Annuler
Liens