IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

 C Discussion :

trier une pile en C


Sujet :

C

  1. #1
    Nouveau membre du Club
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2012
    Messages
    36
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Novembre 2012
    Messages : 36
    Points : 26
    Points
    26
    Par défaut 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 : 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
     
    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++;
            }
     
        }
     
    }

  2. #2
    Membre expert
    Avatar de Metalman
    Homme Profil pro
    Enseignant-Chercheur
    Inscrit en
    Juin 2005
    Messages
    1 049
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Enseignant-Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2005
    Messages : 1 049
    Points : 3 532
    Points
    3 532
    Par défaut
    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 ?
    --
    Metalman !

    Attendez 5 mins après mes posts... les EDIT vont vite avec moi...
    Les flags de la vie : gcc -W -Wall -Werror -ansi -pedantic mes_sources.c
    gcc -Wall -Wextra -Werror -std=c99 -pedantic mes_sources.c
    (ANSI retire quelques fonctions comme strdup...)
    L'outil de la vie : valgrind --show-reachable=yes --leak-check=full ./mon_programme
    Et s'assurer que la logique est bonne "aussi" !

    Ma page Developpez.net

  3. #3
    Expert éminent sénior
    Avatar de diogene
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    Juin 2005
    Messages
    5 761
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2005
    Messages : 5 761
    Points : 13 926
    Points
    13 926
    Par défaut
    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().
    Publication : Concepts en C

    Mon avatar : Glenn Gould

    --------------------------------------------------------------------------
    Une réponse vous a été utile ? Remerciez son auteur en cliquant le pouce vert !

  4. #4
    Membre averti
    Avatar de Snack3r
    Homme Profil pro
    Doctorant à l'Université Cheikh Anta Diop de Dakar
    Inscrit en
    Octobre 2013
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Mauritanie

    Informations professionnelles :
    Activité : Doctorant à l'Université Cheikh Anta Diop de Dakar
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Octobre 2013
    Messages : 118
    Points : 444
    Points
    444
    Par défaut
    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 :
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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);
        }           
    }
    C++ and Java, say, are presumably growing faster than plain C, but I bet C will still be around. ― Dennis Ritchie.

  5. #5
    Nouveau membre du Club
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2012
    Messages
    36
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : Novembre 2012
    Messages : 36
    Points : 26
    Points
    26
    Par défaut
    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 : 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
     
     
    //********************* 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;
    }

  6. #6
    Membre averti
    Avatar de Snack3r
    Homme Profil pro
    Doctorant à l'Université Cheikh Anta Diop de Dakar
    Inscrit en
    Octobre 2013
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Mauritanie

    Informations professionnelles :
    Activité : Doctorant à l'Université Cheikh Anta Diop de Dakar
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Octobre 2013
    Messages : 118
    Points : 444
    Points
    444
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.
    C++ and Java, say, are presumably growing faster than plain C, but I bet C will still be around. ― Dennis Ritchie.

  7. #7
    Expert éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    Par défaut
    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.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  8. #8
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par dimateo_2012 Voir le message
    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...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  9. #9
    Expert éminent sénior
    Avatar de Mat.M
    Profil pro
    Développeur informatique
    Inscrit en
    Novembre 2006
    Messages
    8 352
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Novembre 2006
    Messages : 8 352
    Points : 20 359
    Points
    20 359
    Par défaut
    Citation Envoyé par Metalman Voir le message
    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...)

  10. #10
    Expert éminent sénior
    Avatar de Mat.M
    Profil pro
    Développeur informatique
    Inscrit en
    Novembre 2006
    Messages
    8 352
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Novembre 2006
    Messages : 8 352
    Points : 20 359
    Points
    20 359
    Par défaut
    Citation Envoyé par dimateo_2012 Voir le message
    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 Voir le message
    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,
    pour accéder au dernier élément empilé tu parcours la liste jusqu'à que l'élément suivant soit égal à nul
    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

Discussions similaires

  1. Réponses: 8
    Dernier message: 30/03/2014, 00h27
  2. Comment trier une DBGRID en cliquant sur une colonne
    Par sessime dans le forum Bases de données
    Réponses: 8
    Dernier message: 09/10/2004, 17h18
  3. [Debutant(e)]Trier une liste
    Par LeDébutantJava dans le forum Collection et Stream
    Réponses: 8
    Dernier message: 19/08/2004, 13h44
  4. [langage] Trier une hastable
    Par Gogoye dans le forum Langage
    Réponses: 11
    Dernier message: 03/08/2004, 17h43
  5. Créer une vue pour trier une requete UNION ?
    Par Etienne Bar dans le forum SQL
    Réponses: 3
    Dernier message: 03/01/2003, 21h22

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo