Bonjour, j'ai créé une fonction qui permet de supprimer les occurrences d'un nombre passé en paramètre de la fonction. Lorsque j'exécute, le nombre et ses occurrences que j'ai demandé à supprimer sont bien supprimés mais à la place il y a des 0 qui d'affichent. Par exemple :
Voici le contenu de ma liste : 10.00 -> 20.00 -> 0.00 -> 10.00 -> 50.00 -> NULL
Je demande à supprimer 10.00. A l'affichage la liste est : 0.00 -> 20.00 -> 0.00 -> 0.00 -> 50.00 -> NULL et des fois, j'ai comme affichage : 0.00 -> 20.00 -> 0.00 -> -980779898.75-> 50.00 -> NULL. La deuxième valeur censé être supprimée est remplacée par une valeur aléatoire et je ne comprends pas trop pourquoi.
Si j'écris aujourd'hui, c'est parce que ça fait bientôt 3 jours que je suis dessus et j'ai vraiment du mal à trouver l'erreur. J'espère vraiment trouvé une solution à ce problème. Merci d'avance à tout ceux qui m'aideront 😊
Le pointeur est d'ailleurs déréférencé dès la ligne 18 car courant et ListeT sont égaux. Tu dois: - ôter l'élément du chaînage (par precedent->suivant = courant->suivant) - libérer l'élément - et ensuite ne plus jamais tenter d'utiliser cet élément (c-à-d ne plus déréférencer ce qui pointe sur lui.)
Et attention a bien tester que tu peux bien supprimer en particulier le 1er et le dernier élément de ta liste. Là tu oublies le dernier.
Pas évident si on peut en supprimer plusieurs au début ou consécutifs au milieu. Voici mon petit essai: - Liste *premier = liste; Liste *courant = liste; Liste *precedent = NULL; while(courant) { if(courant->nombre == nombre) { // Attention aux float! if(precedent == NULL) premier = courant->suivant; else precedent->suivant = courant->suivant; Liste *mauvais = courant; courant = courant->suivant; free(mauvais); } else { precedent =courant; courant = courant->suivant; } } return premier;
Le Tout est souvent plus grand que la somme de ses parties.
c'est peut-être aussi l'occasion de penser un peu récursivement. Si l'on y pense deux secondes, on peut se dire que supprimer les occurrences d'une valeur dans une liste :
vide renvoie la liste vide ;
qui commence par la valeur renvoie la queue privée des éléments recherchés ;
qui ne commence pas par la valeur renvoie la liste dans laquelle la queue a été privée des éléments recherché.
Cela donne un algo élégant dont l'implémentation n'est pas très compliquée en C :
Il faudrait toujours commencer par écrire les primitives d'accès à tes structures avant de commencer à implémenter des algos plus complexe. Cela t'évitera quelques heures de debug ou d'attente de réponse d'un forum.
Idée : on parcourt la liste cellule par cellule. Si elle contient la valeur, on la jette, sinon on la met dans une liste des trucs à conserver, en tête parce que c'est plus simple.
A la fin, on renverse la liste des trucs à conserver, et bingo.
Avant : ( 10 20 10 30 )
après avoir enlevé 10 : ( 20 30 )
PS: changement des noms, pour éviter confusion entre cellule (avec une valeur et un pointeur sur la suivante) et liste (composée de cellules). Maniaque, je sais.
- Edité par michelbillaud 21 novembre 2021 à 21:28:20
Merci à tous pour vos réponses. Sans vouloir offensé qui que ce soit, je comprends beaucoup plus les codes de rouloude et White Crow. Pour la version récursive, je n'aurais pas pensé à la structuration que tu as utilisé White Crow. Je voudrais savoir comment tu as trouvé les les primitives d'accès. J'aurais pu les trouver mais en me creusant vraiment la tête. Est ce que tu (vous tous, merci infiniment ) aurais(iez) des conseils à me donner pour décortiquer les problèmes posés étape par étape svp ?
Et aussi...
" @rouIoude: Dans ton code comme le mien, on n'a pas besoin de tester si liste == NULL au début. Ça se fait tout seul si je peux dire ..."
Hum, j'ai du mal à comprendre comment ça se fait tout seul
C'est simple : les listes, ça a une structure de monoïde. Et c'est défini inductivement comme le plus petit ensemble tel que
Liste<E> = E x Liste<E> u { NULL }
Blague à part, ça fait tellement partie de ce qu'on apprend dans des études un peu sérieuses d'informatique, qu'on ne peut pas vraiment dire qu'on l'a trouvé soi-même.
- Edité par michelbillaud 21 novembre 2021 à 21:36:30
Merci à tous pour vos réponses. Sans vouloir offensé qui que ce soit, je comprends beaucoup plus les codes de rouloude et White Crow. Pour la version récursive, je n'aurais pas pensé à la structuration que tu as utilisé White Crow. Je voudrais savoir comment tu as trouvé les les primitives d'accès. J'aurais pu les trouver mais en me creusant vraiment la tête.[...]
C'est pas compliqué du tout : tu le dis en français, et tant que tu as des termes qui ne sont pas simples tu les redécortiques …
Ensuite, tu te rendras compte rapidement que les primitives d'accès sont ou les morceaux de code simples qui se répète souvent (création, destruction, accès à des membres …) dans ton code, ou encore les blocs dont les commentaires commencent par un verbe → il faut en faire une fonction à part.
Il faut essayer de penser récursivement quand tu te trouves face à une structure elle-même récursive. Dans ces cas tu auras souvent un algo récursif élégant et simple. C'est encore plus criant quand tu vas tu retrouver face à des structures comme des arbres ou des graphes (même si techniquement une liste est un arbre et un arbre est un graphe … mais bon).
Merci à tous pour vos réponses. Sans vouloir offensé qui que ce soit, je comprends beaucoup plus les codes de rouloude et White Crow. Pour la version récursive, je n'aurais pas pensé à la structuration que tu as utilisé White Crow. Je voudrais savoir comment tu as trouvé les les primitives d'accès. J'aurais pu les trouver mais en me creusant vraiment la tête.[...]
C'est pas compliqué du tout : tu le dis en français, et tant que tu as des termes qui ne sont pas simples tu les redécortiques …
Ensuite, tu te rendras compte rapidement que les primitives d'accès sont ou les morceaux de code simples qui se répète souvent (création, destruction, accès à des membres …) dans ton code, ou encore les blocs dont les commentaires commencent par un verbe → il faut en faire une fonction à part.
Il faut essayer de penser récursivement quand tu te trouves face à une structure elle-même récursive. Dans ces cas tu auras souvent un algo récursif élégant et simple. C'est encore plus criant quand tu vas tu retrouver face à des structures comme des arbres ou des graphes (même si techniquement une liste est un arbre et un arbre est un graphe … mais bon).
Je vois mieux mais vraiment merci. Les structures, je les faite en cours la semaine dernière en cours d'algorithmique. En algo, ça paraît simple et ça l'ait. Néanmoins la pratique en langage C a été faite en autonomie, ce pourquoi je galère un peu mais je pense qu'avec le temps, je m'améliorerai. Merci
White Crow a écrit:
Zekeee a écrit:
PierrotLeFou a écrit:
@rouIoude: Dans ton code comme le mien, on n'a pas besoin de tester si liste == NULL au début. Ça se fait tout seul si je peux dire ...
Hum, j'ai du mal à comprendre comment ça se fait tout seul
déroule l'algo à la main … tu t'en rendras vite compte tout seul … la ligne 3 du code de rouloude n'est pas nécessaire au bon déroulement.
T'as raison, je devais le dérouler à la main pour mieux comprendre
Les débutants ont souvent une difficulté avec l'approche récursive, parce qu'ils ont commencé par une approche itérative, qu'ils ont eu du mal a s'y mettre et qu'une fois dedans, ils ont beaucoup de mal à changer de point de vue. (*)
Au lieu de se demander quelle action on doit faire, il faut raisonner par cas, et par induction (une forme de récurrence).
Une liste est
soit vide
soit composée d'un premier élément, suivi par d'autres (qui forment une liste).
A partir de là on se demander quel est le rapport entre les données et le résultat à obtenir. Par exemple, pour enlever les occurrences d'une valeur
si la liste est vide => le résultat est vide
si est composée d'un premier élément => le résultat s'obtient en combinant (peut être) cet élément et le reste dont on a enlevé les occurrences
Plus précisément dans le second cas
si l'élément est celui qu'on veut enlever, le résultat c'est le reste dont on a enlevé etc.
si c'est une autre valeur : le résultat c'est cet élément suivi du reste etc.
On n'est pas dans "il faut d'abord faire ceci, et après faire cela".
Et ça peut donner quelque chose de si simple, qu'on se demande par quel miracle ça fonctionne (**)
Cell * remove_occurrences(Cell *start, int value)
{
if (start != NULL) {
Cell * rest = remove_occurrences(start -> next, value);
if (start -> value == value) {
free(start); // suppression
start = rest;
} else {
start -> next = rest; // raccrochage
}
}
return start;
}
(*) aussi parce que c'est très mal enseigné
en commençant par l'exemple de la factorielle, qui est mauvais parce que les étudiants savent déjà calculer la factorielle en faisant une boucle, et ne voient pas pourquoi ils devraient s'emmerder à apprendre une nouvelle façon de faire ce qu'ils savent déjà. (INUTILITE)
qu'on s'ingénie à leur présenter ensuite l'implémentation naïve de fibonacci dont ils retiennent que la récursivité, c'est complètement inutilisable (INEFFICACITE)
si ça se trouve on va même leur parler de la fonction d'Ackermann (qui n'est pas d'Ackermann mais de Rosza Peter), dont ils ne feront rien de leur vie, mais qui les convaincra que ça explose la pile. (INUTILISABLE).
Il ne reste plus qu'à leur apprendre Fortran IV pour démontrer que la récursivité, ça n'est pas possible.
(**) attention, ça a l'air simple (parce que très court) quand on le voit et qu'on a fini par se convaincre que ça marche. Ca ne veut pas dire que c'est facile d'arriver à une solution aussi simple, et qu'on est nul si on n'arrive pas à trouver ça du premier coup. Ca se travaille.
- Edité par michelbillaud 21 novembre 2021 à 23:28:31
@michelbillaud: « Une autre solution, itérative. Idée : on parcourt la liste cellule par cellule. Si elle contient la valeur, on la jette, sinon on la met dans une liste des trucs à conserver, en tête parce que c'est plus simple. A la fin, on renverse la liste des trucs à conserver, et bingo.» Je n'y aurais pas pensé ... Il faut aimer faire du chaînage. Et comment convaincre un débutant que ça redonne la liste dans l'ordre original? Si on est un peu astucieux, on garde la position du dernier de la nouvelle liste et on peut ajouter directement à la fin. On renvoie directement cette nouvelle liste.
- Edité par PierrotLeFou 22 novembre 2021 à 1:17:35
Le Tout est souvent plus grand que la somme de ses parties.
Tu as raison. À la fin du if intérieur, je pourrais faire: return liste_suppression_occurence(liste, nombre); Je n'exécuterais pas ce qui est après ce if.
Le Tout est souvent plus grand que la somme de ses parties.
A la fin, on renverse la liste des trucs à conserver, et bingo.» Je n'y aurais pas pensé ... Il faut aimer faire du chaînage. Et comment convaincre un débutant que ça redonne la liste dans l'ordre original? Si on est un peu astucieux, on garde la position du dernier de la nouvelle liste et on peut ajouter directement à la fin. On renvoie directement cette nouvelle liste.
- Edité par PierrotLeFou il y a environ 5 heures
1. C'etait une approche alternative, histoire de varier, basee sur l'idée qu'on met de côté les trucs à garder
2. Et que si on met des trucs en tête, ca le fait à l'envers (Le débutant le remarque lors de la construction d'une liste)
3. Et que 2 fois à l'envers, ca remet à l'endroit. Comme quand on retourne les crêpes.
Pour ce qui est de garder un pointeur sur le dernier, excellente idee, mais comme est possible que la liste soit vide, il faut tester si on est dans le cas du premier ajout.
Ça remet en cause - est ce un mal- la présentation qui est donnée de la notion de Liste chainee : une liste n'est pas un pointeur sur une première cellule (ni une cellule). Liste et Cellule, c'est tres different.
Si on a des ajouts à faire à la fin, une liste est mieux représentée par une structure avec 2 pointeurs, premier et dernier. C'est ce qui devrait être comme paramètre de la fonction "enlever les occurrences".
Mais bon, visiblement, y en a encore pour traiter les listes chaînées comme dans les années 60, avant qu'on se rende compte que pour bien programmer, il fallait définir proprement des "types définis par l'utilisateur" qui correspondent à ce qu'on veut faire.
- Edité par michelbillaud 22 novembre 2021 à 7:25:11
Très personnellement, je pense que les détails d'implémentation sont … des détails d'implémentation.
Une liste c'est autre chose que des pointeurs en C. C'est une structure de donnée abstraite bien définie avec des primitives d'accès tout autant bien définies.
Par exemple, la version que tu proposes Michel, est une version utilisant la sda pile et un algo du type :
Supprimer(pile , valeur)
resultat = pile_vide
tant que non est_vide(pile) faire
courant = depiler(pile)
si courant =/= valeur alors
empiler(resultat, valeur)
renvoyer resultat
Et est-ce grave d'avoir une pile inversée comme résultat ?
Si il y avait une approche algorithmique avant de pisser du code tout irait bien mieux dans la tête des apprenants. Tout comme cela se passerait mieux si il n'y avait pas ce réflexe pavlovien de mettre des pointeurs en C dès qu'on entend un des mots «chaîne», «lien», «nœud», «arbre», … Il faut prendre du recul sur tout ça.
Après qu'on implémente une liste chaînée avec des «pointeurs à la C», des index dans un tableau … osef un peu car ce sont des détails d'implémentations.
De mémoire, l'assimilation de la chaîne à un pointeur, on la retrouve dans le k+r.
Mais il y a une probablement une explication historique, la transposition d'exemples écrits precedemment en B, qui ne connaît qu'un seul type de données entier=pointeur, et pas les structures.
Mais bon, comme c'était dans les Saintes Écritures de K&R, ca s'est propagé de génération en génération dans les exemples et exercices.
Pour la notion de pile dans ma variante, oui et non. On s'agit d'y tripatouiller des chaînes de cellules, choses qui sont justement cachées par l'abstraction qui figure dans ADT.
Si on se basait sur des piles, les opérations ça serait empiler et dépiler des _nombres_, et on ne saurait pas si c'est représenté physiquement des chaînes de cellules ou des tableaux extensibles. Alors que la on est en prise avec chainage, allocation et libération de cellules. On est du coté implementation, avec les mains dans le cambouis. On recycle en partie des cellules de la liste d'origine pour construire la liste modifiee. Mais être dans le cambouis ne dispense pas de travailler proprement.
Si on avait une approche plus fonctionnelle, enlever les occurrences etc ça fournirait une AUTRE liste sans modifier la première. Et l'algorithme serait simplement
Résultat = liste vide
Pour toute valeur dans la liste, si elle est différente de celle à éliminer, l'ajouter au Résultat (à la fin)
Retourner Résultat.
Donc il suffirait d'avoir un type liste avec ajout à la fin, et une manière de parcourir, et basta.
Mais le but de l'exercice est de s'embrouiller dans les chaînages. La programmation en C est souvent enseignée par des gorets.
- Edité par michelbillaud 22 novembre 2021 à 9:00:23
Pour la notion de pile dans ma variante, oui et non. On s'agit d'y tripatouiller des chaînes de cellules, choses qui sont justement cachées par l'abstraction qui figure dans ADT.
Si on se basait sur des piles, les opérations ça serait empiler et dépiler des nombres. Alors que la on est en prise avec chainage, allocation et liberation. On est du coté implementation, avec les mains dans le cambouis.
- Edité par michelbillaud il y a moins de 30s
Bah si clairement. Si tu prends du recul tu as considéré les listes comme des piles, et appliqué un algo de pile pour résoudre le problème. Ensuite les détails d'implémentations …
michelbillaud a écrit:
[...] Idée : on parcourt la liste cellule par cellule. Si elle contient la valeur, on la jette, sinon on la met dans une liste des trucs à conserver, en tête parce que c'est plus simple.
[...] -
Edité par michelbillaud il y a environ 11 heures
Cette idée est effectivement plus simple à implémenter avec une sda pile … et si on garde «un pointeur vers le dernier élément» alors c'est plus simple avec une file ou un deque …
Tout prend du sens quand on prend un tout petit peu de recul et qu'on pense un tout petit peu algo …
Il ne faut pas mettre la charrue avant les bœufs, ce n'est pas «comme une pile» parce que le code ressemble à du code utilisant une pile mais bien l'inverse … ton code ressemble à du code utilisant une pile car c'est effectivement un code implémentant un algo qui utilise une pile.
#include <stdio.h>
#include <stdlib.h>
typedef struct Cell {
int value;
struct Cell *next;
} Cell;
typedef struct {
Cell * first, *last;
} List;
#define EMPTY_LIST { .first = NULL, .last = NULL}
void list_add(List *list, int value)
{
Cell *c = malloc(sizeof(Cell));
*c = (Cell) {
.value = value, .next = NULL
};
if (list->first == NULL) {
list->first = c;
} else {
list->last->next = c;
}
list->last = c;
}
void list_print(List *list)
{
printf("( ");
for (Cell *c = list->first; c != NULL; c = c->next) {
printf("%d ",c ->value);
}
printf(")");
}
List list_without(List *list, int value)
{
List result = EMPTY_LIST;
for (Cell *c = list->first; c != NULL; c = c->next) {
if (c->value != value) {
list_add(&result, c->value);
}
}
return result;
}
void list_clear(List *list)
{
Cell *c = list->first;
while (c != NULL) {
Cell *tmp = c;
c = c->next;
free(tmp);
}
list ->first = NULL;
list ->last = NULL;
}
void test_ajout()
{
printf("# test ajout\n");
List list = EMPTY_LIST;
for (int i = 1; i <= 5; i++) {
list_add(&list, 10 * i);
}
list_print(&list);
printf("\n");
list_clear(&list);
}
void test_suppression() {
printf("# test suppression ajout\n");
List list = EMPTY_LIST;
for (int i = 1; i <= 5; i++) {
list_add(&list, 100);
list_add(&list, 10 * i);
}
printf("avant ") ;
list_print(&list);
List resultat = list_without(& list, 100);
printf("\naprès suppression de 100 ");
list_print(&resultat);
printf("\n");
list_clear(&list);
list_clear(&resultat);
}
int main()
{
test_ajout();
test_suppression();
}
Résultat
$ ./main
# test ajout
( 10 20 30 40 50 )
# test suppression ajout
avant ( 100 10 100 20 100 30 100 40 100 50 )
après suppression de 100 ( 10 20 30 40 50 )
$ valgrind ./main
==3436== Memcheck, a memory error detector
...
==3436== in use at exit: 0 bytes in 0 blocks
==3436== total heap usage: 21 allocs, 21 frees, 1,344 bytes allocated
==3436==
==3436== All heap blocks were freed -- no leaks are possible
==3436==
Si on est chagriné par l'idée de faire, dans le "code client" une boucle
for (Cell *c = list->first; c != NULL; c = c->next) {
qui repose - il faut bien le reconnaitre - sur la connaissance de la représentation interne des listes, on peut introduire un type abstrait "Iterateur de Liste" qui fournit les valeurs une par une.
C'est pas que ça soit compliqué, mais je vais pas faire ça en pyjama maintenant.
EDIT Bon, si
// un itérateur, ça planque juste un pointeur sur la
// prochaine cellule à regarder. Mais ne le répétez pas.
typedef struct {
Cell *next_cell;
} ListIterator;
// Pour créer un itérateur
ListIterator list_iterator(List *list) {
return (ListIterator) { .next_cell = list ->first};
}
// pour obtenir une valeur
bool iterator_get_next(ListIterator *iterator, int *next_value) {
if (iterator->next_cell == NULL) {
return false;
} else {
*next_value = iterator->next_cell->value;
iterator->next_cell = iterator->next_cell->next;
return true;
}
}
// exemple d'utilisation : on ne voit plus de chainages, etc.
void list_print_with_iterator(List *list)
{
printf("( ");
ListIterator iterator = list_iterator(list);
for (int value; iterator_get_next(&iterator, &value) ; ) {
printf("%d ",value);
}
printf(")");
}
Abstraction, qu'ils disaient.
- Edité par michelbillaud 22 novembre 2021 à 10:02:37
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
En recherche d'emploi.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.