Fonctions listes chaînées

**deubelte** · 16/10/2007, 09h48

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

**nikko34** · 16/10/2007, 10h56

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

**deubelte** · 16/10/2007, 11h12

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.

**Thierry Chappuis** · 16/10/2007, 11h53

Voilà comment je ferais (non testé):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**deubelte** · 16/10/2007, 12h32

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

**Thierry Chappuis** · 16/10/2007, 13h24

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

**Trap D** · 16/10/2007, 13h30

Mon avis sur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !

**deubelte** · 16/10/2007, 13h55

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.

**deubelte** · 16/10/2007, 14h06

Le plus rapide cest le heapsort:

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

**deubelte** · 16/10/2007, 19h39

a quoi ca sert "assert"?

**Gruik** · 16/10/2007, 20h13

A quoi ç'assert?

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.

**deubelte** · 16/10/2007, 20h14

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

**Gruik** · 16/10/2007, 20h17

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.

**deubelte** · 16/10/2007, 21h17

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

**Emmanuel Delahaye** · 16/10/2007, 23h12

Envoyé par deubelte

a quoi ca sert "assert"?

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

**deubelte** · 17/10/2007, 11h16

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
        typedef struct pile
        {
                int valeur;
                struct pile *prec;
        } pile ;

Ici:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
        pile *MaPile = NULL;

Pourquoi ne peut -on pas faire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
int a;

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
int a=0;

**Médinoc** · 17/10/2007, 11h19

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

**deubelte** · 17/10/2007, 11h49

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

**Thierry Chappuis** · 17/10/2007, 11h58

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