Fonctions listes chaînées

Suite au tuto dispo ici

http://chgi.developpez.com/pile/

j'ai decidé de continuer et de faire de nouvelles fonctions
Dont une qui supprime un element qui possede une valeur determiée d'une pile alors que la fonction de suppression disponible sur le tuto ne permettait que de supprimer celui sur le debut.

Je voudrais avoir votre avis.

Code:

---

1 2 3 4 5 6 7

pile* renvoie_nieme_element(pile *Mapile,int n){ for(int i=2;i<=n;i++){ Mapile=Mapile->prec; } return Mapile; }

---

Ca permet de renvoie l'element qui se trouve a la nieme place.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

pile* supr_un_element(pile** Mapile,int a){ //supprime lelement qui possede la valeur a. pile* temp=*Mapile; pile* element_avant_le_supprimé; pile* element_apres_le_supprimé; pile* element_a_supprimer; int n=0; //n est le numéro de la place de l'élément qui précède celui qu'on doit supprimer. if(temp!=0){ while(temp->val!=a){ temp=(temp)->prec;   n=n+1; } element_avant_le_supprimé=renvoie_nieme_element(*Mapile,n); element_a_supprimer=renvoie_nieme_element(*Mapile,n+1); element_avant_le_supprimé->prec=element_a_supprimer->prec;     } return temp2; }

---

Il y certainement mieux a faire, mais c'est ce que j'ai fait
J'attends tous vos commentaires.


et voici une fonction qui renvoie le min

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int renvoie_min(pile* mapile){; int a;   a=(*mapile).val; for (int i=1;i<=lentgh(mapile);i++){ mapile=mapile->prec; //cout<<(*mapile).val<<endl; if (a>=(*mapile).val){   a=mapile->val; } } return a; }

---

il faut que t'ailles dans le forum C je pense

Je sais pas, moi a mon niveau je fais pas la diference,
mais si vous le dites.

Pour moi, le programme a ete ecrit en C ou en C++. Je fais pas de diff.

Voilà comment je ferais (non testé):

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#include <stdlib.h> #include <assert.h>   int supr_un_element(pile **Mapile, int valeur) { /* code d'erreur retourne par la fonction. 0 signifie pas d'erreur. */ int err = 0;   if (Mapile != NULL) { if (*Mapile != NULL) /* La pile n'est pas vide */ { pile *p = *Mapile; pile *tmp = p;   while (p != NULL && p->valeur != valeur) { tmp = p; p = p->prec; } if (p != NULL) /* L'element a ete trouve */ { assert(p->valeur == valeur);   if (tmp != p) /* L'element a effacer n'est pas le 1er element */ { tmp->prec = p->prec; free(p), p = NULL; } else /* L'element a effacer est le 1er element */ { *Mapile = p->prec; free(p), p = NULL, tmp = NULL; } } else { /* L'element n'a pas ete trouve */ err = 3; } } else { /* Erreur: on ne fait rien, la pile est vide */ err = 2; } } else { /* Erreur: argument invalide. */ err = 1; }   return err; }

---

Pose des questions si tu ne comprends pas. Par ailleurs, n'oublie pas que ce n'est pas portable d'utiliser des caractères accentués pour tes identificateurs de variables.

Thierry

et comment ferais-tu pour supprimer le tout premier element?

Citation:

---

Envoyé par deubelte

et comment ferais-tu pour supprimer le tout premier element?

---

Oups, j'ai fait les choses un peu vite. Effectivement, je ne traite pas correctement le cas ou valeur correspond au premier élément de la pile. J'ai corrigé mon code dans ce sens et je l'ai validé. Tout semble OK! Toutefois, je verrais plus l'utilité d'une fonction comme supr_un_element() dans un type abstrait de donnée liste chainée. Avec une pile (comme c'est le cas ici), il n'y a pas vraiment de sens d'effacer un élément autre que celui qui se trouve au sommet. Dans ce cas, la fonction Pop() décrite dans le tuto de CGi est tout ce dont tu as besoin.

Thierry

Mon avis sur

Code:

---

1 2 3 4 5 6

pile* renvoie_nieme_element(pile *Mapile,int n){ for(int i=2;i<=n;i++){ Mapile=Mapile->prec; } return Mapile; }

---

Tu ne testes jamais si Mapile->prec est NULL, donc plante potentielle !

En fait, ce que je veux faire,cest une fonction de tri.
je veux trier la pile
je pense a un algo bourrin:
Supposons la pile: 92369472
On prend la pile par le debut
On regarde ou se trouve le min
on prend le min, on creer une nouvelle pile qui commence par cet element
et on supprime l'element de la pile
Ensuite, on recommence avec la pile une fois l'element supprimé.


Bourrin je pense.

Le plus rapide cest le heapsort:

http://en.wikipedia.org/wiki/Heapsort

a quoi ca sert "assert"?

A quoi ç'assert? :mrgreen:

En gros, ça sert à verifier certains trucs en phase de test. Dire "bein là theoriquement cette expression doit valoir ceci". Attention toutefois, le piege c'est de vouloir l'utiliser pour la gestion des erreurs dues à des paramètres incorrects du logiciel, de la fonctionnalité, de la fonction.

Lol.
Cette plaisenterie mise a part,
ca n'est pas fondamental pour le reste du code qui peut fonctionner sans cela?

Sachant que c'est actif qu'en phase de test, oui ce n'est pas fondamental pour le reste du code, ça peut aider ... qu'en phase de test.

cette pile que j'ai faite, c'est bien une FIFO?

Citation:

---

Envoyé par deubelte

a quoi ca sert "assert"?

---

http://emmanuel-delahaye.developpez....tes.htm#assert

http://chgi.developpez.com/pile/

Dans cette page, il est dit que pour initialiser la pile, il faut dire qu'elle pointe sur le pointeur nul.

Code:

---

1 2 3 4 5 6

typedef struct pile { int valeur; struct pile *prec; } pile ;

---

Ici:

Code:

---

1 2	pile *MaPile = NULL;

---

Pourquoi ne peut -on pas faire:

Code:

---

1 2	pile *MaPile;

---

Un pointeur lorsqu'il est déclarer, ne pointe il pas par defaut sur NULL?

C'est un peu la différence entre:

Code:

---

1 2

int a;

---

et

Code:

---

1 2

int a=0;

---

Citation:

---

Un pointeur lorsqu'il est déclarer, ne pointe il pas par defaut sur NULL?

---

Absolument pas en C ou en C++.
C'est un pointeur non-initialisé, il peut pointer n'importe où (le plus souvent dans le décor).

a se moment la, pourquoi le sommet d'une pile doit pointeur sur NULL et pas dans le decors?

Citation:

---

Envoyé par deubelte

cette pile que j'ai faite, c'est bien une FIFO?

---

Non, une pile fonctionne selon un mode LIFO (Last-In/First-Out). Dans ce contexte, je ne fois pas l'intérêt de trier une pile.

Si tu désires implanter une file (FIFO) de priorité, utilise effectivement le tri par tas qui est la méthode la plus efficace.

Thierry

Citation:

---

Si tu désires implanter une file (FIFO) de priorité, utilise effectivement le tri par tas qui est la méthode la plus efficace.

---

OK, c'est pas trop dur a programmer?

Citation:

---

Envoyé par deubelte

OK, c'est pas trop dur a programmer?

y a t il des codes sur developpez.com sur les tris?

---

Tu trouveras tout ce qu'il faut dans ton livre d'algo. Le tutoriel de Nicolas Joseph ne concerne que les files et pas les files de priorités. C'est une idée, et je vais peut-être écrire un didacticiel sur l'implantation d'une file de priorité en C (peut-être qu'un tel tuto aurait plus sa place dans la rubrique algos que dans la rubrique C). Pour le moment, il n'y a rien au sujet des files de priorité sur developpez.com (au vu des recherches que j'ai effectuées).

Thierry