trier une pile en C

Version imprimable

trier une pile en C

bonjour tout le monde !
svp je me suis bloqué sur la fonction de trier une pile pourriez-vous m'aider ????
voici l'implémentation de la fonction :

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
 
typedef struct ElementListe{
  char *donnee;
  struct ElementListe *suivant;
} Element;
 
typedef struct ListeRepere{
  Element *debut;
  int taille;
} Pile;
 
//voilà la fonction qui ne marche pas 
void trie_pile(Pile *tas)
{
    Element *courant;
    courant=tas->debut;
    int i,s; char *data;
    data= (char *) malloc (50 * sizeof (char));
    for(i=0;i<tas->taille;i++)
    {
        s=strcmp(courant->donnee,courant->suivant->donnee);
        if(s>0)
        {
            *data=*courant->donnee;
            *courant->donnee=*courant->suivant->donnee;
            *courant->suivant->donnee=*data;
               courant=tas->debut++;
        }
 
    }
 
}

17/10/2013, 12h59
Metalman

Eh bein il suffit que tu regardes les algos de tri :
tri à bulle (conseillé pour démarrer), quicksort, ...

Mais dans ce cas, est-ce vraiment encore une pile si on la trie ?
17/10/2013, 16h37
diogene

Vu la définition de 'data', qui est un char *, *data va être un char. *data=*courant->donnee; va donc copier le premier char de la chaine 'donnee' dans le premier char de la chaine 'data'. Le reste de la chaine 'data' est inchangé. Même remarque pour les lignes suivantes.

Pour copier une chaine dans un autre tableau, se tourner vers la fonction strcpy().
17/10/2013, 19h48
Snack3r
Bonsoir

Element représente "une pile" en utilisant une liste simplement chainée. Donc lors du parcours du tri il faut quand même utiliser une boucle du genre :

Code:

while(top != NULL)

pour savoir est-ce qu'on a atteint la fin de la pile.

En plus, souvent si on manipule une pile, il est recommandé d'utiliser les opérations standard comme pop et push au lieu de faire un échange entre la chaine courante et la chaine qui suit d'une façon qui ne respecte pas le LIFO.
Par exemple, votre algorithme doit s’annoncer ainsi :
Code:

1 2 3 4 5 6 7 8 9 void sort(stack) { type x; if (!isEmpty(stack)) { x = pop(stack); sort(stack); insert(x, stack); } }

je suis d'accord pour le principe ahmed mohammed mais je saisi pas bien les listes chainée , je vais te montre ma nouvelle fonction c'est presque le même principe mais ça fonction pas bien , j'aime bien si tu peux me donner une solution en donnant le code exacte à exécuter svp !

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
 
 
//********************* trier *****************************************
Pile* trie_pile(Pile *tas)
{
Pile *p1,*p2;
int x,v;
 
p1=(Pile *) malloc (la_taille(tas)*sizeof (Pile));
//p2=(Pile *) malloc (sizeof (Pile));
 
//Element *p1_e,*p2_e;
 
x=depiler(tas);
p1=empiler(p1,x);
 
while(tas != NULL){
    if(tas->debut->donnee <= p1->debut->donnee)
    {
printf("la donnee ==> %d \n",tas->debut->donnee);
printf("la donnee de tri ==> %d \n",p1->debut->donnee);
        x=depiler(tas);
        p1=empiler(p1,x);
    }
 
 
    else
    {
        if(p1!=NULL && tas->debut->donnee > p1->debut->donnee)
        {
 
            v=depiler(p1);
            p2=empiler(p2,v);
 
            x=depiler(tas);
            p1=empiler(p1,x);
 
        }
    }
 
 
}
return p1;
}

Mr. Tarik, comme vous savez, les règles du forum interdisent de donner le code exacte car le grand but du forum est d'aider les gens et non pas de faire les exercices à leurs places.

En ce qui concerne votre code :

pourquoi vous avez déclaré p1 et p2 à la fois ?
La variable donnee est de type char* donc on ne peut pas comparer deux chaines en utilisant le symbole < mais plutôt la fonction strcmp.

pour l’algorithme précédent on peut écrire la fonction insert comme ceci :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 void insert(x, stack) { type y; if (!isEmpty(stack) && top(stack) < x) { y = pop(stack); insert(x, stack); push(y, stack); } else { push(x, stack); } }
A vous d’écrire le code de la fonction top.

Sinon, Pour le tri vous pouvez utiliser la récurrence ou bien une boucle.

17/10/2013, 21h30
Médinoc

Trier une liste simplement chaînée avec les algorithmes traditionnels qu'on applique aux tableaux (en gros, ceux avec permutations) n'est pas une mince affaire si l'on veut trier les chaînons eux-mêmes.
Sauf si l'on trie leurs contenus à la place, sans bousculer le chaînage.

Pour une liste chaînée, il sera plus simple de trier par sélection du "plus petit" chaînon et insertion en queue de la liste triée, mais là encore il faut faire attention en supprimant le chaînon de la liste non-triée. Je temps à recommander l'usage de pointeur de pointeur de chaînon (Element **) pour cela, ça permet de détacher un chaînon de celui qui le précède ou de la tête de liste, indifféremment.
18/10/2013, 09h08
Sve@r

Citation:

Envoyé par dimateo_2012

je suis d'accord pour le principe ahmed mohammed mais je saisi pas bien les listes chainée

Bonjour
Une liste chainée est une liste où chaque élément contient l'adresse de l'élément suivant. La notion de "suivant" ne dépendant que du sens qu'on veut bien lui donner (par ordre alphabétique, par ordre d'éloignement, par poids, par tailles, etc etc etc).
Le but d'une liste chainée étant de pouvoir facilement insérer un ou un autre élément tout en conservant l'ordre logique de l'ensemble. Pour cela il suffit de créer l'élément en mémoire puis repérer celui venant juste avant et celui venant juste après puis modifier les adresses pour que tout se suive.
Toutefois une liste chainée demandant un certain travail, ne se justifie que si on a besoin de son principal avantage, à savoir insérer et enlever faclement divers éléments intermédiaires. Si on a juste besoin d'empiler les éléments sans se soucier de leur ordre, un simple tableau alloué puis réalloué suffira.

Ceci dit, la question de Metalman a une certaine importance. Une pile triée perd son utilité de "pile" ; à savoir "empilement" d'éléments dans un ordre, là bien précis et inchangé, pour pouvoir ensuite les retrouver soit dans l'ordre dans lequel ils ont été empilés (pile FIFO), soit dans l'ordre inverse (pile LIFO).
Ce qui amène donc une autre question à savoir "pourquoi as-tu besoin de trier une pile" ? Si c'est pour avoir un ensemble d'éléments triés alors autant les trier dès leur création et non à la fin et remplacer alors la pile par une liste chainée. Déjà tu gagneras du temps (créer un ensemble trié est moins long que le trier à la fin) et tu éviteras le travail de création du mécanisme de pile devenu ensuite inutile.
Si maintenant ton but est de te familiariser avec les tris, alors autant partir d'un simple tableau puis ensuite de lui appliquer un algorithme de permutation de ses éléments pour avoir en final un tableau trié.
Bref dans tous les cas tu n'as jamais besoin de pile...
18/10/2013, 22h54
Mat.M

Citation:

Envoyé par Metalman

Eh bein il suffit que tu regardes les algos de tri :
tri à bulle (conseillé pour démarrer), quicksort, ...

Mais dans ce cas, est-ce vraiment encore une pile si on la trie ?

c'est tout à fait exact ; une pile n'a pas vocation à être triée.
L'intérêt c'est de restituer soit le premier soit le dernier élément placé soit sur le dessus soit à la fin ( queue, stack...)
18/10/2013, 22h56
Mat.M

Citation:

Envoyé par dimateo_2012

bonjour tout le monde !
svp je me suis bloqué sur la fonction de trier une pile pourriez-vous m'aider

si tu veux faire une "pile" classique LIFO,FIFO...alors une liste chainée n'est peut-être pas toujours utile..
un simple tableau que tu redimensionnes avec calloc et malloc peut suffire
Regarde l'algorithme de Shuntyard dans Wikipedia cela montre comment gérer une pile dans le cadre d'un exemple d'analyse d'expression numérique

Citation:

Envoyé par dimateo_2012

je suis d'accord pour le principe ahmed mohammed mais je saisi pas bien les listes chainée ,

Le principe d'une liste chaînée c'est
1 de se comporter comme un tableau statique mais que l'on ré alloue en fonction de l'élément que l'on veut rajouter
2 donc de s'agrandir ou diminuer selon les ajouts ou les suppressions d'éléments
3 de rechercher un élément dans la liste.Comme ce sont des pointeurs qui pointent soit vers l'élément suivant soit le précédent ( ou les 2 selon ce que l'on veux faire ->liste doublement chainée ) ça va très vite à l’exécution puisque en C on manipule des adresses mémoire directement

Maintenant si tu veux utiliser une liste chainée pour faire une pile,
:fleche: pour accéder au dernier élément empilé tu parcours la liste jusqu'à que l'élément suivant soit égal à nul
:fleche: pour le premier élément c'est là où l'élément précédent est égal à nul

Une fois que tu as le premier ou le dernier selon ce que tu veux faire, il faut supprimer soit le premier ou soit le dernier et traiter soit le deuxième ou avant-dernier respectivement