C++

[C / Algo] - Tri d'une liste chainée par nom [ résolu... oufff ! ]

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : [C / Algo] - Tri d'une liste chainée par nom [ résolu... oufff ! ]

_maximus_

Goret ptit con ^_^

Bonjour,

ca fait des jours que j'essaie de trouver une solution, mais c'est trop pour moi j'y arrive pas :'( ...

voila j'ai une liste chainees avec des maillons de ce type :

Code :

struct DATA
{
char nom[31];
char prenom[21];
char telephone[16];
char adresse[51];
char cp[5];
char ville[31];
char metier[31];
struct DATA *pSuivant;
struct DATA *pPrecedent;
};

non triée biensur,

Si qqun pouvais m'aider a faire un algo pour trié cette sdfsdffsd de liste chainee par ordre de nom ascendant ca serait super cool, parce qeu la je m'emmele les pinceau et je dois remettre mon projet cette semaine :cry:

Merci d'avance pour votre aide

Message édité par _maximus_ le 12-12-2002 à 02:21:16

---------------
Ptit con de goret je t'emmerde ^_^

Publicité

bjone

Insert booze to continue

bin tu peux faire un tri à bulle (version avec sélection ou je sais plus comment), du style:

pour i du premier à l'avant dernier

m <- rien de mieux

pour j du suivant de i au dernier
si j est "<" à i
m <- j
fin si
fin pour

si m n'est pas "rien de mieux"
injecter m avant i
fin si

fin pour

voilà, démerdes toa avec ça

_maximus_

Goret ptit con ^_^

bjone a écrit :

Salut,

mais dans ma liste chainée, il n'y a pas d'indice, dois-je tout remettre dans un tableau normal avant de proceder au tri a bulle??

aussi j'ai pas compris ce que signifie le "rien de mieux" :??:

merci

---------------
Ptit con de goret je t'emmerde ^_^

antp

Super Administrateur
Champion des excuses bidons

spa plus simple d'utiliser qsort ?

---------------
mes programmes ·· les voitures dans les films ·· apprenez à écrire

_maximus_

Goret ptit con ^_^

antp a écrit :

spa plus simple d'utiliser qsort ?

J'avais trouvé cette fonction qsort, mais je dois avouer que j'ai rien capté a son utilisation :'(
y a moyen de trier DIRECTEMENT une liste chainées du type que je viens de donné avec ca?

Le principe serait d'echanger les adresse de pSuivant et pPrecedent de la structure pour trier la liste chainee...
:pt1cable:

---------------
Ptit con de goret je t'emmerde ^_^

bjone

Insert booze to continue

_Maximus_ a écrit :

i peut être un pointeur

antp

Super Administrateur
Champion des excuses bidons

je sais plus si ça marche avec les listes chaînées en fait... ça date d'y a longtemps pour moi ces trucs-là

---------------
mes programmes ·· les voitures dans les films ·· apprenez à écrire

bjone

Insert booze to continue

qsort ça implique un tableau d'objets (linéaire)

_maximus_

Goret ptit con ^_^

bjone a écrit :

i peut être un pointeur

ok mais je vois vraiment pasdu tout comment faire....

---------------
Ptit con de goret je t'emmerde ^_^

bjone

Insert booze to continue

bin j'ai déjà fait 40% de ton taf....

Publicité

bjone

Insert booze to continue

bon aide:

les "pour" se traduiront certainement en parcours via le "suivant" de chaque élément de la liste chainée.

beaucoup de variables seront des pointeurs.

l'injection aura ptet des cas particulier à prendre en compte.

darkoli

Le Petit Dinosaure Bleu

_Maximus_ a écrit :

Ben déjà tu fais une fonction magique qui gère l'inversion de deux maillons de ta liste. Simplement en lui filant en paramètre les deux adresses. Vu que ta liste est doublement chaînée c'est nickel y'a rien d'autre à faire.

Ensuite tu pourras te concentrer sur le tri de ta liste ...

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html

Carbon_14

Dans la méthode bjone, le i et le j correspondent au rang des "enregistrements" dans la "base de données".
Y a bien un premier, un second objet entré ? puis un troisième, etc..

Faut appliquer son algo en mettant à jour les *pSuivant et *pPrecedent à chaque comparaison.

En faisant le truc avec un exemple sur une feuille de papier, ça permet de voir le principe, ensuite la machine le fera pour le fichier une fois mis au point.

_maximus_

Goret ptit con ^_^

bjone a écrit :

Merci j'avais compris pour les pour, la je suis occupé a essayer de le faire en C, ùmais je n'ai pas compris comment traduire ca "m <- rien de mieux"
ca fait quoi exactement? Merci

---------------
Ptit con de goret je t'emmerde ^_^

_maximus_

Goret ptit con ^_^

carbon_14 a écrit :

Yep je commence a y voir plus clair, mais chui pas encore sur du tout de ce que je fais, quand j'aurai fait l'algo je le posterai ( je suppose kil foirera au premier coup )

---------------
Ptit con de goret je t'emmerde ^_^

bjone

Insert booze to continue

en fait:

faire les échanges d'éléments via les pointeurs
suivant/précédent à chaque fois c'est du pure tri à bulle (ou à plomb )

mais si tu maintiens l'élement qui est plus "petit" (ou plus "grand" ), tu as juste à balayer tous les éléments suivant le courant, et faire un échange d'élements à la fin une fois que tu sais kicékiestmieuxplacé, c'est du tri par sélection/insertion (en principe plus rapide).

en gros ce que j'ai donné c'est:

pour chaque élement sauf le dernier
pour chaque élement à partir du "suivant du courant"
si l'élement il me plait mieux je le "mémorise"
fin pour

si il y a un élément qui me plait mieux
je le DEPLACE devant le courant
fin si
fin pour

Message édité par bjone le 10-12-2002 à 15:11:14

bjone

Insert booze to continue

peux pas faire plus simple.

bjone

Insert booze to continue

a oui en fait y'aura un problème

dans le:

si il y a un élément qui me plait mieux
je le DEPLACE devant le courant
fin si

faut faire attention à repartir du courant (et pas du meilleur élément déplacé ou du suivant du courant ) à la prochaine itération générale.

Message édité par bjone le 10-12-2002 à 15:14:26

_maximus_

Goret ptit con ^_^

bjone a écrit :

peux pas faire plus simple.

Si j'ai bien capté, ton M c'est le courant c ca?

---------------
Ptit con de goret je t'emmerde ^_^

_maximus_

Goret ptit con ^_^

bjone a écrit :

a oui en fait y'aura un problème

cad? :??:

---------------
Ptit con de goret je t'emmerde ^_^

bjone

Insert booze to continue

dans le truc initial:

i -> le courant
j -> permet de balayer du suivant du courant au dernier
m -> élément à insérer devant i

bjone

Insert booze to continue

honte à moi, le vilain bug que je te fait faire:

pour i du premier à l'avant dernier

m <- i

pour j du suivant de i au dernier
si j est "<" à m
m <- j
fin si
fin pour

si m est différent de i
injecter m avant i
fin si

fin pour

_maximus_

Goret ptit con ^_^

bjone a écrit :

lol s'pas grave,

bon je v essayer avec ca... des que c fini je poste mon code
tkx

---------------
Ptit con de goret je t'emmerde ^_^

_maximus_

Goret ptit con ^_^

Bon voila ce que donne le code de ma fonction mais comme prevu ca foire , j'ai du loupé qque chose, en fait quand j'affiche ma liste chainee apres ca, non seulement c pas trié mais en plus il manque plein de maillon ... qu'est ce qeu j'ai encore foutu moi...

Code :

void TriNom(struct DATA *LC_result)
{
struct DATA *pMem, *pTmp, *pI, *pJ;
pI=LC_result;
while(pI->pSuivant->pSuivant!=NULL)
{
pMem=pI;
pJ=pI->pSuivant;
while(pJ->pSuivant!=NULL)
{
if(strcmp(pJ->nom, pMem->nom)<0)
{
pMem=pJ;
}
pJ=pJ->pSuivant;
}
if(strcmp(pMem, pI)!=0)
{
pTmp=pMem->pSuivant;
pMem->pSuivant=pI;
pI->pSuivant=pTmp;
}
pI=pI->pSuivant;
}
}

Message édité par _maximus_ le 10-12-2002 à 15:40:04

---------------
Ptit con de goret je t'emmerde ^_^

_maximus_

Goret ptit con ^_^

bon jai corrigé ce qu'il y avait dans la derniere conditrion c t pas bon, mais ca marche tjrs pas

Code :

void TriNom(struct DATA *LC_result)
{
struct DATA *pMem, *pTmp, *pI, *pJ;
pI=LC_result;
while(pI->pSuivant->pSuivant!=NULL)
{
pMem=pI;
pJ=pI->pSuivant;
while(pJ->pSuivant!=NULL)
{
if(strcmp(pJ->nom, pMem->nom)<0)
{
pMem=pJ;
}
pJ=pJ->pSuivant;
}
if(strcmp(pMem, pI)!=0)
{
pI->pSuivant=pMem->pSuivant;
pMem->pSuivant=pI;
}
pI=pI->pSuivant;
}
}

---------------
Ptit con de goret je t'emmerde ^_^

_maximus_

Goret ptit con ^_^

Mon code vous fait peur? Zetes tous parti? :'(

help plz m'en sort plus je test pas a pas mon code avec des printf partout, je vois pas ce qui cloche si la logique est bonne

:cry:

---------------
Ptit con de goret je t'emmerde ^_^

bjone

Insert booze to continue

alors dans le while, il faut:

while( pI->pSuivant != NULL && pI->pSuivant->pSuivant!=NULL )

qui est équivalent à:

while( pI->pSuivant && pI->pSuivant->pSuivant )

et encore par sécurité:

while( pI && pI->psuivant....

ça protège des bugs plus bas, et ça protège du cas ou il y a q'un seul élément....

pour le if:

if(strcmp(pMem, pI)!=0)
{
pI->pSuivant=pMem->pSuivant;
pMem->pSuivant=pI;

}

vo mieux:

if( pMem != pI )
{

}

ensuite ton insertion est "fausse"

ton insertion doit faire:

// meilleur devant courant
courant->précédent->suivant = meilleur
courant->précédent = meilleur

// on "enlève" meilleur
meilleur->précédent->suivant = meilleur->suivant
meilleur->suivant->précédent = meilleur->précédent

// meilleur devant courant (suite)
meilleur->suivant=courant

et ceci doit gérer les cas spéciaux:

insetion devant le premier élément où le pointeur précédent est à NULL ( modifer le pointeur "racine" )

cas ou le meilleur est le dernier élément où le pointeur suivant est à NULL (sinon crash)

Message édité par bjone le 10-12-2002 à 16:30:04

bjone

Insert booze to continue

et comme tu fais un courant=courant->suivant en fin de while

dans le if en cas d'insertion, il faut à la fin faire courant=meilleur, comme ça le courant pris au prochain coup sera le MEME que celui de ce tour là, et si il y a encore des élements mieux placés il seront insérés devant.

_maximus_

Goret ptit con ^_^

bjone a écrit :

Bon voila j'ai fais ce que tu as dis, enfin je crois :

Code :

void TriNom(struct DATA *LC_result)
{
struct DATA *pMem, *pTmp, *pI, *pJ;
pI=LC_result;
while(pI->pSuivant != NULL && pI->pSuivant->pSuivant!=NULL)
{
pMem=pI;
pJ=pI->pSuivant;
while(pJ->pSuivant!=NULL)
{
if(strcmp(pJ->nom, pMem->nom)<0)
{
pMem=pJ;
}
pJ=pJ->pSuivant;
}
if(strcmp(pMem->nom, pI->nom)!=0)
{
pI->pPrecedent->pSuivant=pMem;
pI->pPrecedent=pMem;
pMem->pPrecedent->pSuivant=pMem->pSuivant;
pMem->pSuivant->pPrecedent=pMem->pPrecedent;
pMem->pSuivant=pI;
}
pI=pI->pSuivant;
}
getch();
}

maintenant a TOUT les coup il manques un enregistrement.... c'est deja mieux, mais ca trie encore n'importe comment.

j'ai essaié de mettre pI=pMem; a la place de pI=pI->pSuivant; mais alrso il boucle a l'infini...

désolé de t'ennuyé encore mais chui un peu largué la... stressé, car c'est la seule fonction de mon prog ki marche pas encore , et je dois remettre le projet demain

gros stress :'(

thkx

---------------
Ptit con de goret je t'emmerde ^_^

BifaceMcLeOD

The HighGlandeur

Algorithme de tri en O(n log n) pour les listes chaînées :

http://www.chiark.greenend.org.uk/ [...] tsort.html

Avec du code en C.

PS: Vive [:google]

_maximus_

Goret ptit con ^_^

BifaceMcLeOD a écrit :

Algorithme de tri en O(n log n) pour les listes chaînées :

http://www.chiark.greenend.org.uk/ [...] tsort.html

Avec du code en C.

PS: Vive [:google]

Je v voir ca merci, puis, j'ai passé des heures sans trouver sur google... avec les criteres "tri de liste chainee" "langage C"
et rien

edit: un rien complexe a comprendre leur exemple

Message édité par _maximus_ le 10-12-2002 à 17:12:06

---------------
Ptit con de goret je t'emmerde ^_^

_maximus_

Goret ptit con ^_^

bjone a écrit :

dans mon dernier code tu vois qque chose qui cloche :??:
chai plus quoi faire pour ke ca marche :'(

---------------
Ptit con de goret je t'emmerde ^_^

BifaceMcLeOD

The HighGlandeur

_Maximus_ a écrit :

Je v voir ca merci, puis, j'ai passé des heures sans trouver sur google... avec les criteres "tri de liste chainee" "langage C"
et rien

Il faut savoir parler anglais parfois. Je l'ai trouvé en tapant "sort linked list".

youdontcare

Si tu veux une solution simple ... une liste chaînée n'est qu'un container de données. Le container le plus simple à trier est le tableau - tu vas donc ranger tous les pointeurs de ta liste chaînée dans un tableau de DATA* temporaire. Ensuite, un qsort() sur ce tableau, puis recréation de la liste chaînée (simple parcours du tableau qui met pointeur suivant = case suivante, etc).

la fonction à passer à qsort va te filer deux pointeurs void* (en fait des pointeurs vers tes DATA*)

void fn(void* d1, void* d2)

tu n'as qu'à les caster puis faire ta comparaison dessus :

return strcmp((DATA*)d1->nom, (DATA*)d2->nom);

_maximus_

Goret ptit con ^_^

youdontcare a écrit :

bon j'ai commencé mais je suis deja bloqué

Code :

void TriNom(struct DATA *LC_result)
{
struct DATA *pMem, *pTmp, *pI, *pJ;
struct *DATA TabDATA[];
int i=0;
while(pI->pSuivant!=NULL)
{
TabDATA[i++]=pI;
}
qsort(*base, i, malloc(sizeof(struct DATA)), fn(/* que mettre ici*/));
}
void fn(void* d1, void* d2)
{
return strcmp((DATA*)d1->nom, (DATA*)d2->nom);
}

j'parie que chui a coté de la plaque completement...

---------------
Ptit con de goret je t'emmerde ^_^

youdontcare

void TriNom(struct DATA *LC_result)
{
struct DATA *pMem, *pTmp, *pI, *pJ;
struct *DATA TabDATA[];
int i=0;
/*
manque l'allocation du tableau ...
*/

while(pI->pSuivant!=NULL)
{
TabDATA[i++]=pI;
}

/*
regarde l'aide de qsort (ou google). il faut un tableau, donc ici TabData, le nombre de ses éléments, la taille d'un élément (ici sizeof(DATA*)), puis la fonction de comparaison (regarde l'aide, compile un exemple et debugge-le pour voir comment la fonction est appelée).
*/
qsort(*base, i, malloc(sizeof(struct DATA)), fn(/* que mettre ici*/));
}

/*
manque la mise à jour des pointeurs. le quicksort a 'trié les pointeurs' vers les éléments de ta liste, suffit de parcourir le tableau et de faire TabData[i].pSuivant = TabData[i+1], etc. et faire gaffe aux valeurs de i.

donc le premier élément de ta liste sera TabData[0].
*/

/*
pareil, regarde l'aide. maîtriser qsort() & ses mécanismes est indispensable.
*/
void fn(void* d1, void* d2)
{
return strcmp((DATA*)d1->nom, (DATA*)d2->nom);
}

bjone

Insert booze to continue

boh j'essayais de le mettre sur la voie

_maximus_

Goret ptit con ^_^

bjone a écrit :

boh j'essayais de le mettre sur la voie

bjone, qu'est ce qui cloche alors dans ce que j'ai fait??

capte pas [:spamafote]

merci

---------------
Ptit con de goret je t'emmerde ^_^

_maximus_

Goret ptit con ^_^

v devenir singléééé :cry:

---------------
Ptit con de goret je t'emmerde ^_^

youdontcare

_Maximus_ a écrit :

v devenir singléééé :cry:

si tu détaillais un peu les endroits où tu es bloqué ... j'ai mis tout ce que tu avais à corriger dans mon post précédent. le code final ne devrait pas prendre plus d'une trentaine de lignes.

et quand je dis de recopier & debugger les exemples qsort() & co, c'est pas pour faire joli, c'est crucial. cf l'exemple dans la msdn : http://msdn.microsoft.com/library/ [...] _qsort.asp

si tu veux comprendre l'algo, http://www.google.com/search?q=quicksort+explained . ce n'est pas indispensable pour son utilisation.

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

C++

[C / Algo] - Tri d'une liste chainée par nom [ résolu... oufff ! ]

Sujets relatifs
Ou puis-je trouver une liste de ts les pays pr mettre dans un combo?	Serveur local impossible de passer des variable par url [résolu]
[ALGO] algo avec restriction de donnée	pbr recherche en LDAP (newbie inside) [Résolu]
[Algo]ou trouver des infos sur le parcours des arbres ?	[HTML]Comment recuperer ts les elt selectionnées d'une boîte liste?
Besoin d'un pro? : Problème de regexp (résolu)	Délai dans la suppression des variables de session (résolu)
probleme avec un applet qui prend un fichier en parametre [resolu]	comment recuperer le path du fichier qu'on execute ? [resolu]
Plus de sujets relatifs à : [C / Algo] - Tri d'une liste chainée par nom [ résolu... oufff ! ]

Page générée en 0.136 secondes