Discussion :

[awesomeman]

Bonsoir,
je suis confronté à un problème: trier dans l'ordre alphabétique des chaines de caractères contenu dans des listes chainés.

Ca fonctionne pour la première chaine mais le reste ne passe pas, je boucle inf.
je pense que le problème vient de la manipulation des pointeurs ..
je print au fur et à mesure ma chaine (trié donc) quand j'ai une chaine trié je mets seen à 1 pour dire que je l'ai déjà print.

j'ai pris pour exemple ces noms: -Charvet
-LeeNolin
-Anderson
-Hassel

ducoup j'ai comme output : Anderson
Charvet (x9)


je dois mal m'y prendre avec les pointeurs , je n'ai pas tout précisé , si vous avez des questions n'hésitez pas.
Merci

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int 	check_seen_all(t_employee *emp)
{
  int i;
 
  i = 0;
  while (emp->next != NULL)
    {
      if (emp->seen != 1)
	return (1);
      emp = emp->next;
    }
  return (0);
}
 
char 	*choose(t_employee *emp)
{
  while (emp->next != NULL)
    {
      if (emp->seen == 0)
	return (emp->lname);
      emp = emp->next;
    }
  return (NULL);
}
 
int 	check_order(char *str, t_employee *emp)
{
  while (emp->next != NULL)
    {
      if (strcmp(str, emp->next->lname) > 0 && emp->seen != 1)
	return (-1);
      emp = emp->next;
    }
  return (0);
}
 
void 	sort_all(t_employee *emp) 
{
  t_employee *tmp;
  char *str;
  int i;
 
  i = 0;
  tmp = emp;
  str = my_malloc(sizeof(char) * 20);
  while (/*check_seen_all(tmp) != 0*/i != 10) //le i est provisoire, c'est pour éviter la boucle inf
    {
      str = choose(emp);
      while (emp->next != NULL) 
	{
	  if (strcmp(str, emp->next->lname) > 0 && emp->seen != 1) //si la str est avant l'élément de la liste et si je n'ai pas print cet élément 
	    {
	      str = emp->next->lname; // je change la str avec la nouvelle chaine
	      if (check_order(str, emp) == 0) //  si l'élément est bien le premier dans l'apha je marque l'élément comme vu
		emp->seen = 1; 
	    }
	  emp = emp->next;
	}
      printf("%s\n", str); // print du str (le premier élément dans l'alpha et pas encore vu)
      emp = tmp;
      i++;
    }
}

[edgarjacobs]

Hello,

Une question, en présumant que c'est toi qui a écrit le programme: pourquoi ne pas trier lors de la création de la liste ? Et si les éléments doivent être chaînés dans l'ordre de leur apparition, pourquoi ne pas avoir un second pointeur (dans la même strucure évidement), et trier alphabétiquement lors de la création avec ce second pointeur ? Tu as alors deux pointeurs pour parcourir la liste: un dans l'odre d'apparition, un dans l'ordre alphabétique.

A+

Edgar;

[awesomeman]

ahah malheureusement je ne veux pas juste trier au moment d'entrer les données.
je veux toutes les stocker puis ensuite les trier en fonction du choix entré par l'utilisateur (ex "trier par nom" ou "trier par ville"), sachant que l'utilisateur peut demander plusieurs fois l'affichage selon un tri différent ou non.

Merci pour ta réponse edgar

[skeud]

Il existe plusieurs algorythme pour effectuer le tri. Il faut d'abord que tu définisse quel algo tu veux utiliser. Que tu le pose sur papier, pour ensuite le coder.
Dans ton code, il y a pas mal de choses illogiques qui sont induites du fait d'être parti directement dans le code, c'est une faute très courante et normale, ne t'en fais pas.

L'idéal lors de traitement complexe, est vraiment de posé sur papier (en pseudo-code) un algorythme pour ensuite le traduire en code. De cette manière on est sur que notre code suit bien la logique que l'on avait à la base, et pas besoin de tout retenir dans la tête .

Si tu pose ton pseudo-code, tu te rendras rapidement compte que quelques lignes de code ne font pas ce que tu voudrais faire.

[Médinoc]

Je ne vois pas trop comment trier une liste chaînée en temps linéarithmique, mais en temps quadratique, le plus simple serait de faire un tri par insertion:

Code X :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
liste_sortie = créer liste vide
TANT QUE liste_entree n'est pas vide
    prendre premier élément de liste_entree
    insérer juste avant le premier élément supérieur dans liste_sortie
FIN TANT QUE
retourner liste_sortie

[picodev]

Bonjour,
un mergesort adapté peut faire l'affaire → Mergesort For Linked Lists.

Edit: En y réfléchissant un peu, c'est un cas de figure où il aurait mieux valu implémenter la liste chaînée sous forme de tableau croissant dynamiquement au lieu de suivre le réflexe pavlovien du programmeur C à implémenter toutes les listes sous formes de pointeurs à la C.