La mémoire de chaques structures a été alloué avec un malloc, je ne suis
donc pas dans le cas d'une liste de structure stocké dans un tableau. (
genre struct toto[xx];), de ce fait, je ne peux utiliser qsort().
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
La mémoire de chaques structures a été alloué avec un malloc, je ne suis donc pas dans le cas d'une liste de structure stocké dans un tableau. ( genre struct toto[xx];), de ce fait, je ne peux utiliser qsort().
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
http://fr.wikipedia.org/wiki/Algorithme_de_tri
Pour les listes chainées, le tri par insertion (pour les petites listes) et le tri par fusion (pour les grosses) sont généralement assez efficaces et faciles à implémenter.
-- Richard
Bonjour,
Je voudrais trier par ordre alphabethique( toto->name) une liste de
structure se présentant sous cette forme:
La mémoire de chaques structures a été alloué avec un malloc, je ne suis
donc pas dans le cas d'une liste de structure stocké dans un tableau. (
genre struct toto[xx];), de ce fait, je ne peux utiliser qsort().
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
http://fr.wikipedia.org/wiki/Algorithme_de_tri
Pour les listes chainées, le tri par insertion (pour les petites listes)
et le tri par fusion (pour les grosses) sont généralement assez
efficaces et faciles à implémenter.
La mémoire de chaques structures a été alloué avec un malloc, je ne suis donc pas dans le cas d'une liste de structure stocké dans un tableau. ( genre struct toto[xx];), de ce fait, je ne peux utiliser qsort().
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
http://fr.wikipedia.org/wiki/Algorithme_de_tri
Pour les listes chainées, le tri par insertion (pour les petites listes) et le tri par fusion (pour les grosses) sont généralement assez efficaces et faciles à implémenter.
-- Richard
Emmanuel Delahaye
Zorro wrote on 10/09/05 :
Je voudrais trier par ordre alphabethique( toto->name) une liste de structure se présentant sous cette forme:
La mémoire de chaques structures a été alloué avec un malloc, je ne suis donc pas dans le cas d'une liste de structure stocké dans un tableau. ( genre struct toto[xx];), de ce fait, je ne peux utiliser qsort().
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
Rien à voir avec le langage C (algo).
<HS> Il suffit de relire la liste en faisant du tri/insersion. Pour ça il faut une deuxième 'tête' et une fonction d'insertion triée selon le critère choisi
- Parcourir la liste A, - Déplacer chaque élément dans la liste B en faisant l'insertion triée. -- Parcourir la liste B -- Chercher l'endroit où ranger l'élément (selon le critère de tri) -- Le ranger en faisant les raccordements nécessaires.
C'est pas bien compliqué.
Par contre, c'est pas rapide. Si tu veux du rapide, parcours la liste, deplace chaque élément dans un tableau, trie le tableau (qsort() etc.), recrée la liste à partir des éléments triés. </HS>
-- Emmanuel The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html The C-library: http://www.dinkumware.com/refxc.html
"It's specified. But anyone who writes code like that should be transmogrified into earthworms and fed to ducks." -- Chris Dollin CLC
Zorro wrote on 10/09/05 :
Je voudrais trier par ordre alphabethique( toto->name) une liste de structure
se présentant sous cette forme:
La mémoire de chaques structures a été alloué avec un malloc, je ne suis donc
pas dans le cas d'une liste de structure stocké dans un tableau. ( genre
struct toto[xx];), de ce fait, je ne peux utiliser qsort().
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
Rien à voir avec le langage C (algo).
<HS>
Il suffit de relire la liste en faisant du tri/insersion. Pour ça il
faut une deuxième 'tête' et une fonction d'insertion triée selon le
critère choisi
- Parcourir la liste A,
- Déplacer chaque élément dans la liste B en faisant l'insertion triée.
-- Parcourir la liste B
-- Chercher l'endroit où ranger l'élément (selon le critère de tri)
-- Le ranger en faisant les raccordements nécessaires.
C'est pas bien compliqué.
Par contre, c'est pas rapide. Si tu veux du rapide, parcours la liste,
deplace chaque élément dans un tableau, trie le tableau (qsort() etc.),
recrée la liste à partir des éléments triés.
</HS>
--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
The C-library: http://www.dinkumware.com/refxc.html
"It's specified. But anyone who writes code like that should be
transmogrified into earthworms and fed to ducks." -- Chris Dollin CLC
La mémoire de chaques structures a été alloué avec un malloc, je ne suis donc pas dans le cas d'une liste de structure stocké dans un tableau. ( genre struct toto[xx];), de ce fait, je ne peux utiliser qsort().
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
Rien à voir avec le langage C (algo).
<HS> Il suffit de relire la liste en faisant du tri/insersion. Pour ça il faut une deuxième 'tête' et une fonction d'insertion triée selon le critère choisi
- Parcourir la liste A, - Déplacer chaque élément dans la liste B en faisant l'insertion triée. -- Parcourir la liste B -- Chercher l'endroit où ranger l'élément (selon le critère de tri) -- Le ranger en faisant les raccordements nécessaires.
C'est pas bien compliqué.
Par contre, c'est pas rapide. Si tu veux du rapide, parcours la liste, deplace chaque élément dans un tableau, trie le tableau (qsort() etc.), recrée la liste à partir des éléments triés. </HS>
-- Emmanuel The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html The C-library: http://www.dinkumware.com/refxc.html
"It's specified. But anyone who writes code like that should be transmogrified into earthworms and fed to ducks." -- Chris Dollin CLC
Harpo
Zorro wrote:
Bonjour,
Je voudrais trier par ordre alphabethique( toto->name)
Pourquoi ?
Votre pseudo vous ferait arriver dns les derniers.
Zorro wrote:
Bonjour,
Je voudrais trier par ordre alphabethique( toto->name)
Pourquoi ?
Votre pseudo vous ferait arriver dns les derniers.
Sur une liste chainée, c'est moyen... En tout cas, ce n'est pas direct...
-- Emmanuel The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html The C-library: http://www.dinkumware.com/refxc.html
I once asked an expert COBOL programmer, how to declare local variables in COBOL, the reply was: "what is a local variable?"
Zorro
Rien à voir avec le langage C (algo).
Oui, en fait, je désirai également qu'on me dirige vers un source code générique.. je ne dois pas être le premier à vouloir trier un liste chainé :P
<HS> Il suffit de relire la liste en faisant du tri/insersion. Pour ça il faut une deuxième 'tête' et une fonction d'insertion triée selon le critère choisi
- Parcourir la liste A, - Déplacer chaque élément dans la liste B en faisant l'insertion triée. -- Parcourir la liste B -- Chercher l'endroit où ranger l'élément (selon le critère de tri) -- Le ranger en faisant les raccordements nécessaires.
C'est pas bien compliqué.
Non, mais c'est un peu lent :/
Par contre, c'est pas rapide. Si tu veux du rapide, parcours la liste, deplace chaque élément dans un tableau, trie le tableau (qsort() etc.), recrée la liste à partir des éléments triés.
C'est ce que je fais actuellement, c'est juste que je ne trouve pas ça élégant.
Oui, en fait, je désirai également qu'on me dirige vers un source code
générique.. je ne dois pas être le premier à vouloir trier un liste
chainé :P
<HS>
Il suffit de relire la liste en faisant du tri/insersion. Pour ça il
faut une deuxième 'tête' et une fonction d'insertion triée selon le
critère choisi
- Parcourir la liste A,
- Déplacer chaque élément dans la liste B en faisant l'insertion triée.
-- Parcourir la liste B
-- Chercher l'endroit où ranger l'élément (selon le critère de tri)
-- Le ranger en faisant les raccordements nécessaires.
C'est pas bien compliqué.
Non, mais c'est un peu lent :/
Par contre, c'est pas rapide. Si tu veux du rapide, parcours la liste,
deplace chaque élément dans un tableau, trie le tableau (qsort() etc.),
recrée la liste à partir des éléments triés.
C'est ce que je fais actuellement, c'est juste que je ne trouve pas ça
élégant.
Oui, en fait, je désirai également qu'on me dirige vers un source code générique.. je ne dois pas être le premier à vouloir trier un liste chainé :P
<HS> Il suffit de relire la liste en faisant du tri/insersion. Pour ça il faut une deuxième 'tête' et une fonction d'insertion triée selon le critère choisi
- Parcourir la liste A, - Déplacer chaque élément dans la liste B en faisant l'insertion triée. -- Parcourir la liste B -- Chercher l'endroit où ranger l'élément (selon le critère de tri) -- Le ranger en faisant les raccordements nécessaires.
C'est pas bien compliqué.
Non, mais c'est un peu lent :/
Par contre, c'est pas rapide. Si tu veux du rapide, parcours la liste, deplace chaque élément dans un tableau, trie le tableau (qsort() etc.), recrée la liste à partir des éléments triés.
C'est ce que je fais actuellement, c'est juste que je ne trouve pas ça élégant.
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
http://fr.wikipedia.org/wiki/Algorithme_de_tri
Pour les listes chainées, le tri par insertion (pour les petites listes) et le tri par fusion (pour les grosses) sont généralement assez efficaces et faciles à implémenter.
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
http://fr.wikipedia.org/wiki/Algorithme_de_tri
Pour les listes chainées, le tri par insertion (pour les petites listes)
et le tri par fusion (pour les grosses) sont généralement assez
efficaces et faciles à implémenter.
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
http://fr.wikipedia.org/wiki/Algorithme_de_tri
Pour les listes chainées, le tri par insertion (pour les petites listes) et le tri par fusion (pour les grosses) sont généralement assez efficaces et faciles à implémenter.
qsort() directement avec une liste chainé? on sent le professionel..
Casssé...
-- Emmanuel The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html The C-library: http://www.dinkumware.com/refxc.html
"There are 10 types of people in the world today; those that understand binary, and those that dont."
Harpo
Zorro wrote:
Zorro wrote:
Bonjour,
Je voudrais trier
man qsort
qsort() directement avec une liste chainé? on sent le professionel..
Je me suis fait repérer...
Si tu connais le nombre d'éléments de la liste, tu alloues un tableau dans lequel tu charges les pointeurs vers les éléments de la liste , tu tries ce tableau de pointeurs avec qsort, tu reprends le tableau sequentiellement pour refaire les chaînages dans la liste. Si tu ne connais pas le nombre d'éléments, il faut d'abord les compter pour allouer le tableau avant de faire la même chose.
Il y a certainement mieux, mais ce n'est pas compliqué à programmer et d'une performance acceptable. La solution d'Emdel est correcte pour des listes pas très grandes. Sinon, beaucoup d'algorithmes de tri sont sans doute applicables. Il faut dans la mesure du possible éviter de changer les données de place et ne bouger que les adresses.
Zorro wrote:
Zorro wrote:
Bonjour,
Je voudrais trier
man qsort
qsort() directement avec une liste chainé? on sent le professionel..
Je me suis fait repérer...
Si tu connais le nombre d'éléments de la liste, tu alloues un tableau
dans lequel tu charges les pointeurs vers les éléments de la liste , tu
tries ce tableau de pointeurs avec qsort, tu reprends le tableau
sequentiellement pour refaire les chaînages dans la liste.
Si tu ne connais pas le nombre d'éléments, il faut d'abord les compter
pour allouer le tableau avant de faire la même chose.
Il y a certainement mieux, mais ce n'est pas compliqué à programmer et
d'une performance acceptable. La solution d'Emdel est correcte pour des
listes pas très grandes. Sinon, beaucoup d'algorithmes de tri sont sans
doute applicables. Il faut dans la mesure du possible éviter de changer
les données de place et ne bouger que les adresses.
qsort() directement avec une liste chainé? on sent le professionel..
Je me suis fait repérer...
Si tu connais le nombre d'éléments de la liste, tu alloues un tableau dans lequel tu charges les pointeurs vers les éléments de la liste , tu tries ce tableau de pointeurs avec qsort, tu reprends le tableau sequentiellement pour refaire les chaînages dans la liste. Si tu ne connais pas le nombre d'éléments, il faut d'abord les compter pour allouer le tableau avant de faire la même chose.
Il y a certainement mieux, mais ce n'est pas compliqué à programmer et d'une performance acceptable. La solution d'Emdel est correcte pour des listes pas très grandes. Sinon, beaucoup d'algorithmes de tri sont sans doute applicables. Il faut dans la mesure du possible éviter de changer les données de place et ne bouger que les adresses.
