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 :

probleme avec le tri des listes chainee


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Inscrit en
    Avril 2008
    Messages
    42
    Détails du profil
    Informations forums :
    Inscription : Avril 2008
    Messages : 42
    Par défaut probleme avec le tri des listes chainee

    j'explique mon problème avec un exemple :
    supposons que j'ai 3 processus avec chacun son temps d'exécution et son temps d'arrivé insérer dans une liste chaînée dans l'ordre qui suit:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
       processus A :                      processus B :                  processus C:
    temps d'exécution: 5                  temps d'exécution: 4          temps d'exécution: 10
    temps d'arrivé: 4                     temps d'arrivé: 4             temps d'arrivé: 2
    j'aimerai les trier dabord par leur temps d'arrivé, et après par leur temps d'exécution pour avoir comme suis :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
       processus A :                      processus B :                  processus C:
    temps d'exécution: 10          temps d'exécution: 4            temps d'exécution: 5
    temps d'arrivé: 2              temps d'arrivé: 4                temps d'arrivé: 4
    je cherche l'algorithme ou la boucle qui me permettra de faire ça.
    j'ai déjà essayer mais j'arrive a faire le truc que sur le temps d'exécution ou le temps d'arrivé mais pas les deux a la fois.
    merci d'avance

  2. #2
    Membre Expert
    Avatar de Gruik
    Profil pro
    Développeur Web
    Inscrit en
    Juillet 2003
    Messages
    1 566
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : Juillet 2003
    Messages : 1 566
    Par défaut
    Salut,

    Si tu avais un tableau plutot qu'une liste, tu aurais pu utiliser qsort(). Enfin rien t'empeche de créer un tableau à partir de cette liste.

  3. #3
    Membre averti
    Inscrit en
    Avril 2008
    Messages
    42
    Détails du profil
    Informations forums :
    Inscription : Avril 2008
    Messages : 42
    Par défaut
    le projet qu'on ma demande doit etre fait avec une liste chaînée, si je trouve pas de solution j'utiliserai la tienne merci

  4. #4
    Membre chevronné
    Profil pro
    Inscrit en
    Mai 2007
    Messages
    417
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations forums :
    Inscription : Mai 2007
    Messages : 417
    Par défaut
    tu peux donner la structure que tu utilises pour stocker tes processus

    c est du genre :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     typedef struct processus {
    	char *nom;
    	int tps_exec;
    	int tps_arrivee;
    	struct processus *suivant
    } Processus;
     
    typedef Processus *ta_liste;
    je suppose que l'algo doit fonctionner qu importe le nombre de processus ?

  5. #5
    Membre averti
    Inscrit en
    Avril 2008
    Messages
    42
    Détails du profil
    Informations forums :
    Inscription : Avril 2008
    Messages : 42
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    struct process
     {
      int numero;
      int datearrive;
      int tempsexecution;
      int priorite;
      struct process *suivant;
     };
    typedef struct process proc;
    le projet parle de 5 processus , mais normalement il doit pouvoir gerer n'importe quelle nombre de processus

  6. #6
    Expert confirmé
    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
    Par défaut
    Prends un algo de tri à ta convenance (par exemple le tri par sélection qui repose sur :

    1 - savoir où commence l'ensemble des données (pour un tableau à l'indice 0, pour une liste au début de la liste)
    2 - savoir où se termine l'ensemble des données (pour un tableau à l'indice <taille du tableau> -1, pour une liste lorsque le pointeur de chaînage sur le suivant est NULL)
    3 - parcourir les éléments dans l'ordre(pour un tableau en incrémentant l'indice, pour une liste en utilisant le pointeur de chaînage)
    4 - comparer les éléments
    5 - échanger les éléments. Pour une liste, ceci revient à modifier les pointeurs de chaînage (ce qui est préférable (en général) à déplacer le contenu des structures).

    Tu l'adaptes facilement à une liste, la seule "difficulté" est le code qui échange les éléments. C'est plus simple à faire si la liste est doublement chaînée.


    Autre possibilité à base de qsort() ( c'est assez facile) :
    1 - Tu crées un tableau de pointeurs sur les structures de ta liste, ce qui se fait en parcourant la liste à partir des pointeurs de chaînage. (mais ça demande de parcourir la liste deux fois : la première pour obtenir le nombre d'éléments pour créer le tableau par allocation dynamique, la seconde pour remplir le tableau avec les pointeurs)
    2 - tu tries le tableau de pointeur avec qsort() et pour critère de tri le contenu des structures pointées
    3 - Tu reconstitues le chaînage à partir des informations du tableau "trié"
    4 - Tu détruits le tableau

Discussions similaires

  1. Réponses: 2
    Dernier message: 04/01/2016, 21h01
  2. Liste avec dictionnaire, tri des clés et sélection des variables
    Par CandyCH dans le forum Général Python
    Réponses: 8
    Dernier message: 07/12/2012, 21h56
  3. [LG]probleme d'ajout dans une liste chainée...
    Par misteryann dans le forum Langage
    Réponses: 5
    Dernier message: 08/03/2004, 20h28
  4. Probleme avec la copie des surfaces
    Par Black_Daimond dans le forum DirectX
    Réponses: 3
    Dernier message: 09/01/2003, 10h33
  5. Problèmes avec le filtrage des ip
    Par berry dans le forum Réseau
    Réponses: 9
    Dernier message: 30/12/2002, 07h51

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