C++

Tri d'une liste doublement chainée

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Tri d'une liste doublement chainée

assil

J'ai programmé une fonction de tri pour ma liste, mais il n'affiche pas la dernière valeur.
Par exemple j'ai 4 valeurs a trier:
2
7
4
3

et la fonction tri comme ça:
2
3
4

Voila le code si quelqu'un peut me dire ce ça marche pas:

Message édité par assil le 30-12-2012 à 23:50:48

Publicité

Profil supprimé

Moi j'aime bien l'indentation.

Code :

void Tri_liste(Element** Entete)
{
  Element *courant;
  courant=*Entete;
 
  if (courant->suivant==NULL)
    return;
 
  Element *ptr,*tmp;
 
  courant=courant->suivant;
  while(courant!=NULL)
    {
      ptr=courant;
      tmp=courant->precedent;
      courant=courant->suivant;
      while (tmp!=NULL && tmp->prix>ptr->prix)
        {
          tmp=tmp->precedent;
        }
      ptr->precedent->suivant=ptr->suivant;
      if (ptr->suivant!=NULL)
        {
          ptr->suivant->precedent=ptr->precedent;
          if (tmp==NULL)
            {
              tmp=*Entete;
              ptr->precedent=NULL;
              ptr->suivant=tmp;
              ptr->suivant->precedent=ptr;
              *Entete=ptr->precedent;
            }
          else
            {
              tmp=tmp->suivant;
              tmp->precedent->suivant=ptr;
              ptr->precedent=tmp->precedent;
              tmp->precedent=ptr;
              ptr->suivant=tmp;
            }
        }
    }
}

Ceci dit, le code est un poil tordu pour moi, je ne peux que te conseiller d'ajouter quelque print pour bien saisir le déroulement de ton programme.

assil

Merci pour ta réponse, mais j'ai essayé tout ce que je peux sans rien trouver.

Trap D

J'ai corrigé le code

Code :

void Tri_liste(Element** Entete)
{
Element *courant;
Element *ptr,*tmp, *tmp1;
courant=*Entete;
if (courant->suivant==NULL)
return;
courant=courant->suivant;
while(courant!=NULL)
{
ptr=courant;
tmp=courant->precedent;
courant=courant->suivant;
while (tmp !=NULL && tmp->prix>ptr->prix)
{
tmp=tmp->precedent;
}
// on raccorde les elemnts qui entourent ptr
ptr->precedent->suivant=ptr->suivant;
if (ptr->suivant != NULL)
ptr->suivant->precedent = ptr->precedent;
if (tmp == NULL)
{ // on ajoute en tete
ptr->precedent = NULL ;
(*Entete)->precedent = ptr;
ptr->suivant = *Entete;
*Entete = ptr;
}
else
{
ptr->suivant = tmp->suivant;
if (tmp->suivant != NULL)
tmp->suivant->precedent = ptr;
tmp->suivant = ptr;
ptr->precedent = tmp;
}
}
}

assil

Merci pour votre aide mais même avec ça, le tri marche pas et pour les valeurs 7,2,4 et 3 j'ai eu comme résultat 0,2,3 et 4.

Message cité 1 fois

Trap D

assil a écrit :

Merci pour votre aide mais même avec ça, le tri marche pas et pour les valeurs 7,2,4 et 3 j'ai eu comme résultat 0,2,3 et 4.

Mon code fonctionne très bien chez moi, le voici en intégralite :

Code :

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct _elem
{
int prix;
struct _elem *precedent;
struct _elem *suivant;
} Element ;
void Tri_liste(Element** Entete)
{
Element *courant;
Element *ptr,*tmp;
puts("Tri de la liste" );
courant=*Entete;
if (courant == NULL || courant->suivant==NULL)
return;
courant=courant->suivant;
while(courant!=NULL)
{
ptr=courant;
tmp=courant->precedent;
courant=courant->suivant;
while (tmp !=NULL && tmp->prix>ptr->prix)
{
tmp=tmp->precedent;
}
// on raccorde les elemnts qui entourent ptr
ptr->precedent->suivant=ptr->suivant;
if (ptr->suivant != NULL)
ptr->suivant->precedent = ptr->precedent;
if (tmp == NULL)
{ // on ajoute en tete
ptr->precedent = NULL ;
(*Entete)->precedent = ptr;
ptr->suivant = *Entete;
*Entete = ptr;
}
else
{
ptr->suivant = tmp->suivant;
if (tmp->suivant != NULL)
tmp->suivant->precedent = ptr;
tmp->suivant = ptr;
ptr->precedent = tmp;
}
}
}
Element *add(Element *Liste, int Val)
{
Element *elem = malloc(sizeof(*elem));
Element *tmp ;
if (elem == NULL)
{
printf("Pb ajout de %d\n", Val);
return Liste;
}
elem->prix = Val;
elem->precedent = NULL;
elem->suivant = NULL;
if (Liste == NULL)
Liste = elem;
else
{
tmp = Liste;
while(tmp->suivant != NULL)
tmp = tmp -> suivant;
tmp->suivant = elem;
elem->precedent = tmp;
}
return Liste ;
}
void my_free(Element *Liste)
{
Element *tmp = Liste;
Element *tmp2 ;
while(tmp != NULL)
{
tmp2 = tmp->suivant;
free(tmp);
tmp = tmp2;
}
}
void printf_liste(Element *Liste)
{
Element *tmp = Liste;
Element *tmp1 = Liste;
puts("Affichage de la liste en sens direct" );
while(tmp != NULL)
{
printf("%d\n", tmp->prix);
tmp = tmp->suivant;
}
puts("Affichage de la liste en sens indirect" );
tmp = Liste;
while (tmp != NULL)
{
tmp1 = tmp;
tmp = tmp->suivant;
}
while(tmp1 != NULL)
{
printf("%d\n", tmp1->prix);
tmp1 = tmp1->precedent;
}
puts("\n" );
}
// Liste a sans element
void t1(void)
{
Element *Liste = NULL;
puts("Liste sans element" );
printf_liste(Liste);
Tri_liste(&Liste);
printf_liste(Liste);
my_free(Liste);
}
// liste avec un seul element
void t2(void)
{
Element *Liste = NULL;
puts("Liste avec un seul element" );
Liste = add(Liste, 2);
printf_liste(Liste);
Tri_liste(&Liste);
printf_liste(Liste);
my_free(Liste);
}
// liste avec un plusieurs elements tries
void t3(void)
{
Element *Liste = NULL;
puts("liste avec un plusieurs elements tries" );
Liste = add(Liste, 2);
Liste = add(Liste, 3);
Liste = add(Liste, 4);
Liste = add(Liste, 5);
Liste = add(Liste, 7);
printf_liste(Liste);
Tri_liste(&Liste);
printf_liste(Liste);
my_free(Liste);
}
// liste avec un plusieurs elements tries en sens inverse
void t4(void)
{
Element *Liste = NULL;
puts("liste avec un plusieurs elements tries en sens inverse " );
Liste = add(Liste, 7);
Liste = add(Liste, 5);
Liste = add(Liste, 4);
Liste = add(Liste, 3);
Liste = add(Liste, 2);
printf_liste(Liste);
Tri_liste(&Liste);
printf_liste(Liste);
my_free(Liste);
}
// liste avec un plusieurs elements
void t5(void)
{
Element *Liste = NULL;
puts("liste avec un plusieurs elements quelconques" );
Liste = add(Liste, 7);
Liste = add(Liste, 10);
Liste = add(Liste, 4);
Liste = add(Liste, 9);
Liste = add(Liste, 4);
printf_liste(Liste);
Tri_liste(&Liste);
printf_liste(Liste);
my_free(Liste);
}
int main(void)
{
t1();
t2();
t3();
t4();
t5();
_getch();
return 0;
}

EDIT C'est quoi ce problème d'indentation ? Les tab ne sont pas transformés en espaces ?

Message édité par Trap D le 30-12-2012 à 10:55:59

assil

J'ai testé ton code mais lorsque j'ai essayé de l'implanté sur mon code sa marche pas:

Voila mon code avec 3 fonctions (chargement de la liste, tri de la liste et affichage):

Message édité par assil le 30-12-2012 à 23:51:29

gilou

Modérateur
Modzilla

Primo, ce sujet devrait se trouver en catégorie C++ (et je viens de le déplacer)
Secondo:

Code :

class Element
{
public:
string titre;
string source;
int numero;
int prix;
string niveaux_de_confidentialite;
string adresse;
int ID;
int date;
int age;
string examen;
Element* suivant;
Element* precedent;
..........
}

Surtout pas!

Code :

class Donnees
{
public:
string titre;
string source;
int numero;
int prix;
string niveaux_de_confidentialite;
string adresse;
int ID;
int date;
int age;
string examen;
...........
}
class Element
{
Donnees* donnees;
Element* suivant;
Element* precedent;
..........
}

Il n'y a aucune raison de mélanger les torchons avec les serviettes, ie ce qui fait partie du chaînage et ce qui fait partie des données.
De plus en procédant ainsi, ta fonction de tri n'a plus besoin de modifier la liste chaînée, elle a juste à échanger la valeur des pointeurs donnees.

A+,

Message édité par gilou le 30-12-2012 à 13:03:03

---------------
There's more than what can be linked! -- Iyashikei Anime Forever! -- AngularJS c'est un framework d'engulé! --

FORUM HardWare.fr

Programmation

C++

Tri d'une liste doublement chainée

Sujets relatifs
Tri dynamique	[Need HELP !] Garder la dernière version dans une liste
Tri tableau 2 dimensions	[VBA] Créer une liste depuis une cellule
Créer une liste numérotée en PHP	Liste et lien de fichiers
Liste en ligne?	imprimer des feuilles excel générées à partir d'une liste de données
access 97 - Liste des formulaires	garder des données en mémoire dans une liste déroulante
Plus de sujets relatifs à : Tri d'une liste doublement chainée

Page générée en 0.108 secondes