De plus, si j'arrive a régler pour un cas particulier, je pourrai ensuite dans mon temps libre, me pencher sur le cas général dans un but d'utilisation ultérieure.
Ok
Ensuite, pour ce qui est du nieme maillon, ce maillon end, est intéressant puisqu'il réduit le nombre de paramètres à passer à la fonction (pas besoin de passer la taille puisqu'on peut simplement vérifier qu'on est pas au dernier maillon).
Tu y accèdes surtout en O(1) et non en O(n). Par ailleurs si tu décide de passer en liste doublement chainer et que tu veux pouvoir parcourir ta liste en sens inverse (comme avec les reverse iterator du C++) ce champ est bien pratique. Mais tu pourrais éventuellement te contenter de dire que le dernier maillon à son champ *next qui vaut NULL. Pour moi c'est un détail d'implémentation, il faut que tu codes ta structure de sorte à être le plus à l'aise possible.
Je ne demande pas que tu réécrive toute ma fonction (vais pas être ch... à ce point là), mais pourrais tu me montrer d'une part mes erreurs - différence entre les deux types de structure mentionnés - dans les fonctions et d'autre part m'expliquer en code l'atteinte, estraction, suppression d'un maillon.
Ben j'ai pas le temps de tout recoder de toute façon. Mais c'est à peu près le même raisonnement que pour les piles, il faut juste garantir que ton maillage de liste est toujours cohérent :
- d'une part au niveau des champs begin et end (en particulier si tu supprimes ou ajoute un maillon en début/fin de liste)
- d'autre part au niveau des champs next de chaque maillon (en particulier au niveau des maillons entourant le maillon ajouté ou supprimé).
Si tu écris les opérations à apporter au maillage tu vas voir ça coule de source. Je n'ai pas trop envie de détailler trop comment tu dois faire car pour moi c'est l'exercice idéal pour apprendre les pointeurs, donc je préférerais que tu trouves par toi-même. En cas de blocage bien entendu je t'aiderai, mais j'aimerais au moins que tu me fournisses une souche de code sur laquelle repartir.
Je vois bien un truc du genre (pseudo code, donc inutile de me dire que ca marchera jamais comme ça, c'est une idée générale)
Merci de la précision mais je pense que je m'en serai doutée :)
Le problème c'est que si nb est supérieur à la taille de la liste ça va planter (segmentation fault au moment de faire p = p->next). Par ailleurs tu n'as pas à faire de free(p) (chaque free est associé à un malloc et là tu n'as pas fait de malloc, et une fonction de recherche ).
Ici je suppose que tu stockes dans ta structure de liste le premier maillon (begin), le dernier (end), et le nombre de maillon (size). On cherche le maillon i avec i dans {0...l.size}. On retourne NULL s'il n'existe pas. On garantit que i est positif en utilisant un unsigned plutôt qu'un int.
maillon *recherche(liste l,unsigned n){
unsigned i=0;
maillon *p;
if(n == l.size - 1) return l.end; // dernier élément de la liste, accès en O(1)
if(n >= l.size) return NULL; // en dehors de la liste, réponse en O(1)
for(p = l.begin; p != l.end ; p = p->next, ++i){
if(i == n) return p; // nieme élément de la liste, accès en O(n)
}
return NULL; // n'arrive jamais
}
Sinon tu peux jeter un oeil à cette implémentation :
liste simplement chainee
Bonne chance
Algorithme de liste chainee en langage c
