tri par insertion, list simplement chainee

Version imprimable

Bonjour a vous :-)
J'ai un soucis de seg fault... Je vous montre:

Code:

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
 
t_rep   *trie_ins(t_rep *ins, t_rep *ls, t_rep *cur, t_rep *prev)
{
  if(my_strcmp(cur->str, ins->str) == -1)
    {
      ins->nxt = cur;
      if (prev != NULL)
        prev->nxt = ins;
      return ((ls != NULL) ? ls : ins); /* debut de la sous liste triee*/
    }
  else if (cur->nxt != NULL)
    {
      return ((ls != NULL) ? trie_ins(ins, ls, cur->nxt, cur) : trie_ins(ins, cur, cur->nxt, cur));
    }
  /*envoie de ls sinon cur si pas de ls*/
  else /*on le met a la fin*/
    {
      cur->nxt = ins;
      ins->nxt = NULL;
      return ((ls != NULL) ? ls : cur); /* debut de la ls*/
    }
}
 
t_rep   *triInsert(t_rep *ls)
{
  if (ls->nxt != NULL)
      return (trie_ins(ls, NULL, triInsert(ls->nxt), NULL));
  else
    return (ls);
  /* Si ls->nxt == NULL c ke fo trier le last elem, cad le first kje ve inserer dans ls*/
  /* Sinan, jinsere l'elem dans la list formee par le tri des elem qui suivent*/
  /* Jstart dc a classer les elements en partant du last de la liste originelle*/
}

La structure t_rep est juste une liste chainee avec une chaine de caractere est un pointeur sur le suivant.

Mon soucis: je n'arrive pas a prendre le 1er element de ma liste.. Juste le dernier.
Dans la fonction trie_ins le compilo ne connais jamais l'element courant alors que je lui envois bien le 1er de ma liste avec: triInser(ls->nxt)

Voila... J'espere avoir un peu d'aide :-)

Bonjour,

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
>gcc -Wall -Wextra 08-11-07-1.c
08-11-07-1.c:9: error: parse error before '*' token
08-11-07-1.c:9: error: parse error before '*' token
08-11-07-1.c:10: warning: return type defaults to `int'
08-11-07-1.c: In function `trie_ins':
08-11-07-1.c:11: warning: implicit declaration of function `my_strcmp'
08-11-07-1.c:11: error: `cur' undeclared (first use in this function)
08-11-07-1.c:11: error: (Each undeclared identifier is reported only once
08-11-07-1.c:11: error: for each function it appears in.)
08-11-07-1.c:11: error: `ins' undeclared (first use in this function)
08-11-07-1.c:14: error: `prev' undeclared (first use in this function)
08-11-07-1.c:14: error: `NULL' undeclared (first use in this function)
08-11-07-1.c:16: error: `ls' undeclared (first use in this function)
08-11-07-1.c: At top level:
08-11-07-1.c:31: error: parse error before '*' token
08-11-07-1.c:31: error: parse error before '*' token
08-11-07-1.c:32: warning: return type defaults to `int'
08-11-07-1.c: In function `triInsert':
08-11-07-1.c:33: error: `ls' undeclared (first use in this function)
08-11-07-1.c:33: error: `NULL' undeclared (first use in this function)

Peut on avoir un exemple minimal qui compile ? (histoire de voir sur quelle ligne ce produit le problème).

Voila mon code qui compile mais seg fault :p

main.c:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "my_ls.h"
 
int	main(int ac, char **av)
{
  int	i;
 
  i = 1;
  while (i < ac)
    {
      my_ls(av[i]);
      my_putchar('\n');
      i++;
    }
  return (0);
}

my_ls.h

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef __MY_LS_H__
# define __MY_LS_H__
 
#include <unistd.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <dirent.h>
#include <grp.h>
#include <errno.h>
#include <string.h>
 
void	my_ls(char *str);
 
typedef struct	s_rep
{
  char		*str;
  struct s_rep	*nxt;
}	t_rep;
 
#endif

my_ls.c:

Code:

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
#include "my_ls.h"
 
void    *my_malloc(int size)
{
  void  *retour;
 
  retour = malloc(size);
  if (retour == NULL)
    {
      my_putstr("Erreur de malloc\n");
      exit(0);
    }
  else
    return (retour);
}
 
void    my_error()
{
  my_putstr(strerror(errno));
  my_putchar('\n');
  exit(0);
}
 
t_rep	*add_list(t_rep *tmp, char *str)
{
  tmp->str = my_malloc(my_strlen(str));
  tmp->str = str;
  tmp->nxt = my_malloc(sizeof(*tmp));
  tmp = tmp->nxt;
  tmp->nxt = NULL;
  return(tmp);
}
 
/*
** ins = element a inserer
** ls = sous liste triee
** cur = element courant
** prev = element precedent
 */
 
t_rep	*trie_ins(t_rep *ins, t_rep *ls, t_rep *cur, t_rep *prev)
{
  if (strcmp(cur->str, ins->str) == -1)
    {
      ins->nxt = cur;
      if (prev != NULL)
	prev->nxt = ins;
      return ((ls != NULL) ? ls : ins); /* debut de la sous liste triee*/
    }
  else if (cur->nxt != NULL)
    {
      return ((ls != NULL) ? trie_ins(ins, ls, cur->nxt, cur) : trie_ins(ins, cur, cur->nxt, cur));
    }  
  /*envoie de ls sinon cur si pas de ls*/
  else /*on le met a la fin*/
    {
      cur->nxt = ins;
      ins->nxt = NULL;
      return ((ls != NULL) ? ls : cur); /* debut de la ls*/
    }
}
 
t_rep	*triInsert(t_rep *ls)
{
  if (ls->nxt != NULL)
      return (trie_ins(ls, NULL, triInsert(ls->nxt), NULL));
  else
    return (ls);
  /*  return ((ls->nxt != NULL) ? trie_ins(ls, NULL, triInsert(ls->nxt), NULL) : ls);*/
  /* Si ls->nxt == NULL c ke fo trier le last elem, cad le first kje ve inserer dans ls*/
  /* Sinan, jinsere l'elem dans la list formee par le tri des elem qui suivent*/
  /* Jstart dc a classer les elements en partant du last de la liste originelle*/
}
 
void	                 my_ls(char *str)
{
  DIR		         *rep;
  struct dirent	    *lect;
  t_rep		        *list;
  t_rep		        *tmp;
 
  rep = opendir(str);
  if (rep == NULL)
    my_error();
  list = my_malloc(sizeof(*list));
  tmp = list;
  while ((lect = readdir(rep)))
      tmp = add_list(tmp, lect->d_name);
  closedir(rep);
  tmp = list;
  tmp = triInsert(tmp);
}

bonjour,

deja ta fonction add_list est etrange:
Code:

1 2 3 4 5 6 7 8 9 10 t_rep *add_list(t_rep *tmp, char *str) { tmp->str = my_malloc(my_strlen(str)); tmp->str = str; tmp->nxt = my_malloc(sizeof(*tmp)); tmp = tmp->nxt; tmp->nxt = NULL; return(tmp); }
1er chose :
Code:

1 2 3 tmp->str = my_malloc(my_strlen(str)); tmp->str = str;
ici tu alloues un espace memoire que tu perds directement. En effet lorsque que tu fais tmp->str= str, tu ne copies pas le contenu de ta chaine, mais le pointeur. Du coup si tu modifies plus loin str (sans changer l'espace memoire) tu modifies aussi ton tmp->str. Pour copier une chaine utilise strcpy par exemple.

2eme chose:
Code:

1 2 3 tmp->nxt = my_malloc(sizeof(*tmp)); tmp = tmp->nxt;
ici tu alloues le next "d'avance" je comprend pas trop pourquoi, mais surtout ensuite tu perd le pointeur de tmp puisque tu re attribues le pointeur tmp vers un nouveau ces 2 lignes peuvent se resumer par :
Code:

1 2 tmp = my_malloc(sizeof(*tmp));
du coup *str n'est plus alloué de nouveau.

Je pense que ton segV vient d'ici.

Voici une petite correction si tu veux ajouter en tete :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 /* ** Prend en parametre la tete de la liste et la chaine de charactere à ajouter. ** Retourne la nouvelle tete de liste */ t_rep *add_list(t_rep *first, char *str) { t_rep *tmp = my_malloc(sizeof(t_rep)); tmp->str = my_malloc(my_strlen(str)); tmp->str = strcpy(tmp->str, str); tmp->nxt = first; return(tmp); }
je n'ai pas regardé le reste, mais deja avec ca, ca devrait mieux marcher.
Si tu developpes sous Unix essaye d'utiliser des debugger comme gdb, tu peux reperer ce genre de probleme assez facilement.

Codeusement,

ps : je n'ai pas de compilateur sous la main, il y a peut etre des erreurs de syntaxes dans ce que j'ai ecris, mais le principe est la.

07/11/2008, 14h50
Invité(e)
Pour commencer:
Code:

1 2 3 4 t_rep* add_list(t_rep *tmp, char *str) { tmp->str = my_malloc(my_strlen(str)); tmp->str = str;
La fonction my_strlen renvoie t elle la même valeur que strlen ou strlen + 1 ?
Dans le premier cas, il manque la place pour la caractère 0 de fin de chaîne.
Une copie de chaîne de caractère ne se fait pas par =, mais par strcpy ou strcat.

EDIT :
L'erreur de segmentation apparait ici :

Code:

if (strcmp(cur->str, ins->str) == -1)

cur->str vaut 0x00 au premier appel chez moi. N'y a-t-il pas une mauvaise initialisation des membres str ?

Citation:

Envoyé par Maf77

Voila mon code qui compile

8O Sur quelle système ?

Code:

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
 
 
-------------- Build: Debug in hello ---------------
 
Compiling: my_ls.c
Compiling: main.c
Linking console executable: bin\Debug\hello.exe
In file included from C:\dev\hello\my_ls.c:2:
In file included from C:\dev\hello\main.c:1:
C:\dev\hello\my_ls.h:7:21: sys/uio.h: No such file or directory
C:\dev\hello\my_ls.h:9:17: grp.h: No such file or directory
C:\dev\hello\main.c: In function `main':
C:\dev\hello\main.c:11: warning: implicit declaration of function `my_putchar'
Process terminated with status 1 (0 minutes, 1 seconds)
2 errors, 1 warnings
 
C:\dev\hello\my_ls.h:7:21: sys/uio.h: No such file or directory
C:\dev\hello\my_ls.h:9:17: grp.h: No such file or directory
C:\dev\hello\my_ls.c: In function `my_malloc':
C:\dev\hello\my_ls.c:11: warning: implicit declaration of function `my_putstr'
C:\dev\hello\my_ls.c: At top level:
C:\dev\hello\my_ls.c:19: warning: function declaration isn't a prototype
C:\dev\hello\my_ls.c: In function `my_error':
C:\dev\hello\my_ls.c:21: warning: implicit declaration of function `my_putchar'
C:\dev\hello\my_ls.c: In function `add_list':
C:\dev\hello\my_ls.c:27: warning: implicit declaration of function `my_strlen'
Process terminated with status 1 (0 minutes, 1 seconds)
4 errors, 5 warnings

Regle #1 quand on manipule une liste chainée, écrire un fonction qui permet d'en voir le contenu :

Code:

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
 
static void show (t_rep * list)
{
   t_rep *tmp = list;
 
   while (tmp != NULL)
   {
      printf ("%s\n", tmp->str);
      tmp = tmp->nxt;
   }
}
 
void my_ls (char *str)
{
   DIR *rep = opendir (str);
   if (rep == NULL)
   {
      my_error ();
   }
   else
   {
      t_rep *list = my_malloc (sizeof *list);
      t_rep *tmp = list;
      {
         struct dirent *lect;
         while ((lect = readdir (rep)))
         {
            tmp = add_list (tmp, lect->d_name);
         }
         closedir (rep);
      }
      show (list);
 
#if 0
      tmp = triInsert (list);
#endif
   }
}

et là, déjà, on se rend compte que la liste est cassée. Donc inutile d'essayer de la trier...

Il faut déjà mettre au point le mécanisme d'écriture de la liste. Il est faux.

Oui oui...
Code:

1 2 3 4 5 6 #include <unistd.h> void my_putchar(char c) { write(1, &c, 1); }
Code:

1 2 3 4 5 6 7 8 9 10 11 12 int my_putstr(char *str) { int i; i = 0; while (str[i] != '\0') { my_putchar(str[i]); i = i + 1; } return (0); }
et pour my_strlen c'est:
Code:

1 2 3 4 5 6 7 8 9 int my_strlen(char *str) { int i; i = 0; while (str[i] != '\0') i = i + 1; return (i); }
Voila... Donc je perds ma place allouer quand j'ajoute.. Pourtant ca marche tres bien :p
Le moment du seg fault c'est qund il demarre trie_ins.

Merci de vos reponses!! J'en veux, j'en veux :p

ps: je compile sous FreeBSD

07/11/2008, 15h35
oniric
Citation:

Envoyé par Maf77

Oui oui...

Voila... Donc je perds ma place allouer quand j'ajoute.. Pourtant ca marche tres bien :p

l'impression que ca marche et marcher reelement à 100% sont 2 choses bien differente, passe un valgrind sur ton projet et tu aura des erreurs de lecture ecriture partout dans ta liste et beaucoup de leak (fuite de memoire)
Code:

1 2 bash>gcc -o *.c -c mybin bash>valgrind mybin
et regarde ;)

de plus mabu a raison, ton mystrlen doit renvoyer i + 1. Imagine la chaine str = "\0". Ton mystrlen renvoie 0 hors il faut bien 1 octet pour stocker le le caractere '\0'.

ps : si tu veux un commentaire sur valgrind post sa sortie, je ne peux le faire d'ici... Windows work ...

d'accord :-)
Ma petite fonction d'ajout toute fraiche:
Code:

1 2 3 4 5 6 7 8 9 t_rep *add_list(t_rep *tmp, char *str) { tmp->str = my_malloc(my_strlen(str) + 1); tmp->str = my_strcpy(tmp->str, str); tmp->nxt = my_malloc(sizeof(*tmp)); tmp = tmp->nxt; tmp->nxt = NULL; return(tmp); }
Comme ca valgrind va moins me taper dessus!
Je garde mon seg fault au moment du trie :'(

07/11/2008, 15h48
Invité(e)

Pour faciliter un peu le débogage, il pourrait être intéressant de créer une fonction qui affiche les éléments de la liste avant de les trier... Car comme écrit plus haut, chez moi, le crash ne vient pas forcément du tri, mais des données triées.

J'en ai une toute prete de fonction pour afficher la liste :-)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
void            printliste(t_rep *liste)
{
  t_rep         *tmp;
 
  tmp = liste;
  my_putstr(liste->str);
  while(tmp->nxt != NULL)
    {
      my_putstr(tmp->str);
      my_putchar(' ');
      tmp = tmp->nxt;
    }
}

J'ai un peu modifié print_liste:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void printliste(t_rep *liste) { int i = 0; t_rep *tmp; tmp = liste; my_putstr(liste->str); while(tmp->nxt != NULL) { printf("%d: str(%p): ", ++i, (void*)tmp->str); my_putstr(tmp->str); my_putchar('\n'); tmp = tmp->nxt; } }
Voici le résultat, avant l'appel de la fonction de tri :
Code:

1 2 3 4 5 6 1: str(0xd90160): 2: str(0xda4258): .. 3: str(0xda4278): cat 4: str(0xda4298): chicken 5: str(0xda42b8): dog 6: str(0xda42d8): duck
La valeur du premier élément est très très louche : l'adresse est loin des autres, il devrait écrire '.', il n'écrit rien...

Citation:

Envoyé par Maf77

d'accord :-)
Ma petite fonction d'ajout toute fraiche:

Code:

1
2
3
4
5
6
7
8
9
t_rep   *add_list(t_rep *tmp, char *str)
{
  tmp->str = my_malloc(my_strlen(str) + 1);
  tmp->str = my_strcpy(tmp->str, str);
  tmp->nxt = my_malloc(sizeof(*tmp));
  tmp = tmp->nxt;
  tmp->nxt = NULL;
  return(tmp);
}

Comme ca valgrind va moins me taper dessus!
Je garde mon seg fault au moment du trie :'(

je me repete ici encore quand tu fais tmp = tmp->next. Le 1er pointeur de t_rep est perdu donc ta chaine tmp->str aussi.

Regarde mieux ce que je t'ai ecris, je t'ai donné 2 points critique dans cette fonction. Tu as corrigé le 1er pas le 2eme.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
main.c
 
void	                 my_ls(char *str)
{
  DIR		         *rep;
  struct dirent	    *lect;
  t_rep		        *list;
  t_rep		        *tmp; //inutil
 
  rep = opendir(str);
  if (rep == NULL)
    my_error();
  list = NULL; //init de la liste à NULL
 
  while ((lect = readdir(rep)))
      list = add_list(list, lect->d_name); //tmp inutil
  closedir(rep);
  tmp = list;
  tmp = triInsert(tmp);
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
t_rep   *add_list(t_rep *first, char *str)
{
  t_rep *tmp = NULL;
 
  if (first == NULL)
  { 
    //initialisation de la liste
    first->str = my_malloc(my_strlen(str) + 1);
    first->str = my_strcpy(tmp->str, str);
    first->nxt = NULL;
    tmp = first; //pour le return
  }
  else
  {
    tmp = my_malloc(sizeof(t_rep*));
    tmp->str = my_malloc(my_strlen(str) + 1);
    tmp->str = my_strcpy(tmp->str, str);
    tmp->nxt = first; // tmp en tete de liste
  }
    return(tmp);
 
}

Pourtant, avec ce code:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
void            printliste(t_rep *liste)
{
  t_rep         *tmp;
  int           i;
 
  tmp = liste;
  i = 0;
  while(tmp->nxt != NULL)
    {
      printf("%d: %p, %s\n", i++, (void *)tmp->str, tmp->str);
      tmp = tmp->nxt;
    }
}

Tout va bien:

Code:

1
2
3
4
5
6
7
8
9
10
0: 0x804d040, .
1: 0x804d060, ..
2: 0x804d080, Makefile
3: 0x804d0a0, main.o
4: 0x804d0c0, my_ls.o
5: 0x804d0e0, my_ls.c
6: 0x804d100, my_ls.h
7: 0x804d120, main.c
8: 0x804d140, my_ls
9: 0x804d160, Makefile~

Pour oniric, je comprends que le pointeur doit ce sauvegarder! comme ca dans le main la liste utiliser ne changera d'element pas.
Cela donne donc:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
t_rep   *add_list(t_rep *first, char *str)
{
  t_rep *tmp;
 
  tmp = first;
  tmp->str = my_malloc(my_strlen(str) + 1);
  tmp->str = my_strcpy(tmp->str, str);
  tmp->nxt = my_malloc(sizeof(*tmp));
  tmp = tmp->nxt;
  tmp->nxt = NULL;
  return(tmp);
}

07/11/2008, 16h45
oniric

oki je viens de saisir, une ligne m'avais echappé dans ton main tmp = list;
tu fais donc un ajout en fin de chaine, oki. bcp de manipulation de variable de mon point de vue. Autant pour moi pour ce malentendu de ma part.
Par contre du coup en bout de chaine tu as toujours un maillon alloués mais dont str n'est pas alloués ni NULL. Ton segV peut venir de la aussi du coup.
07/11/2008, 17h11
Maf77

Citation:

Envoyé par oniric

Par contre du coup en bout de chaine tu as toujours un maillon alloués mais dont str n'est pas alloués ni NULL.

Je comprends un peu... Je suis oblige de malloquer le suivant pour qu'il ne plante pas, et je lui assigne la valeur NULL.
Donc je comprends pas enfaite ^^

Code:

1
2
3
4
5
6
7
8
9
10
11
t_rep   *add_list(t_rep *first, char *str)
{
  t_rep *tmp;
 
  tmp = my_malloc(sizeof(*tmp));
  tmp->str = my_malloc(my_strlen(str) + 1);
  tmp->str = my_strcpy(tmp->str, str);
  tmp->nxt = first;
  first = tmp;
  return(tmp);
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void    my_ls(char *str)
{
  DIR           *rep;
  struct dirent *lect;
  t_rep         *list;
 
  rep = opendir(str);
  if (rep == NULL)
    my_error();
  list = 0;
  while ((lect = readdir(rep)))
      list = add_list(list, lect->d_name);
  closedir(rep);
  printliste(list);
  list = triInsert(list);
  printliste(list);
}

Voila! Ca tourne super :P sauf que un element c'est fait sauter au passage lol :x mais sinon, ca rox tu tonnerre!
Merci d'avoir trouve la faille oniris :-)

Citation:

Envoyé par Maf77

Oui oui...

Code:

1
2
3
4
5
6
7
8
9
10
11
#include <unistd.h>
 
void    my_putchar(char c)
{
 
int     my_putstr(char *str)
{
 
int     my_strlen(char *str)
{
<...>

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#ifndef H_MY_LS
#define H_MY_LS
 
#include <stdio.h>
#include <string.h>
 
#define my_strlen(a) strlen(a)
#define my_strcpy(a, b) strcpy(a, b)
#define my_putstr(a) puts(a)
#define my_putchar(a) putchar(a)
 
void my_ls (char *str);
 
#endif

:):)

Citation:
Envoyé par Maf77
d'accord :-)
Ma petite fonction d'ajout toute fraiche:
Code:

1 2 3 4 5 6 7 8 9 t_rep *add_list(t_rep *tmp, char *str) { tmp->str = my_malloc(my_strlen(str) + 1); tmp->str = my_strcpy(tmp->str, str); tmp->nxt = my_malloc(sizeof(*tmp)); tmp = tmp->nxt; tmp->nxt = NULL; return(tmp); }
Comme ca valgrind va moins me taper dessus!
Je garde mon seg fault au moment du trie :'(
Non. C'est mieux, mais il se fait dès l'affichage vers la fin de la liste.

Tu es têtu et/ou présomptueux. Avant de faire des choses compliquées sur la liste (tri), vérifie qu'elle peut se parcourir sans problèmes. Or, là, il y a encore des problèmes.

Le but n'est pas de faire plaisir à valgrind , mais déjà créer une liste correcte que l'on peut lire sans erreur.

Au fait, tu as vérifié ce que dit valgrind ? Ca pourrait t'aider à trouver le bug...

Citation:

Envoyé par Maf77

Code:

1
2
3
4
5
6
7
8
9
10
11
t_rep   *add_list(t_rep *first, char *str)
{
  t_rep *tmp;
 
  tmp = my_malloc(sizeof(*tmp));
  tmp->str = my_malloc(my_strlen(str) + 1);
  tmp->str = my_strcpy(tmp->str, str);
  tmp->nxt = first;
  first = tmp;
  return(tmp);
}

Avec ça, la lecture de la liste part en boucle infinie...

J'ai modifié le main() :

Code:

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
 
void my_ls (char *str)
{
   DIR *rep = opendir (str);
   if (rep == NULL)
   {
      my_error ();
   }
   else
   {
      t_rep *list = NULL;
      {
         struct dirent *lect;
         while ((lect = readdir (rep)))
         {
            list = add_list (list, lect->d_name);
         }
         closedir (rep);
      }
      show (list);
 
#if 0
      tmp = triInsert (list);
#endif
   }
}

Là, c'est OK :

Code:

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
 
wordlist.txt
system.cfg
server.c~
server.cmt
server.bak
resultats_num_treated.txt
resultats_num.txt
obj
my_ls.h~
my_ls.h
my_ls.c~
my_ls.c
main.c~
main.cmt
main.c
main.bak
main.asm
home
hello.layout
hello.depend
hello.cbp
fable.txt
data.txt
client.c~
client.cmt
client.bak
clean.h
clean.c
bin
analyse_res_num.txt
..
.
 
 
Process returned 0 (0x0)   execution time : 0.049 s
Press any key to continue.

Par contre, la fonction de tri ne fait rien...

Code:

1
2
3
4
5
 
#if 1
      list = triInsert (list);
      show (list);
#endif

L'affichage est identique (ou alors le tri se fait de Z->A)

11/11/2008, 16h18
Buyakhaska

Arf

Et si le tri n'est pas fait du tout ??? :) ca me fait bien l'affichage de tout ca mais le tri n'est pas du tout ordonné dans un quelconque sens :
my_ls.c~
my_ls.c
my_ls.h
a.out
main.c
libmy.a

Citation:

Envoyé par Buyakhaska

Et si le tri n'est pas fait du tout ??? :)

Oui, c'est bien ça le problème... Ton tri ne fonctionne pas du tout.

Heureux hasard, il se trouve que je viens de terminer un tri par insertion dans une liste chainée simple :

Code:

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
#include <stdio.h>
#include <string.h>
 
/* 0=normal 1=debug */
#define DBG 0
 
#undef PRINTF
#if DBG
#define PRINTF(a) printf a
#else
#define PRINTF(a)
#endif
 
typedef struct node
{
   char const *nom;
   struct node *next;
}
node;
 
struct list
{
   struct node *head;
};
 
void aff_list (struct list const *liste)
{
   struct node const *p = liste->head;
   while (p != NULL)
   {
      printf ("%s -> ", p->nom);
      p = p->next;
   }
   printf ("NIL\n");
}
 
void insert_sorted (struct list *liste, struct node *node)
{
   if (liste->head == NULL)
   {
      PRINTF (("first.head\n"));
      liste->head = node;
      node->next = NULL;
   }
   else
   {
      struct node *p = liste->head;
 
      if (p->next == NULL)
      {
         int cmp = strcmp (node->nom, p->nom);
         PRINTF (("second %s %s %d", node->nom, p->nom, cmp));
         if (cmp < 0)
         {
            PRINTF ((".head\n"));
            node->next = liste->head;
            liste->head = node;
         }
         else
         {
            PRINTF ((".tail\n"));
            liste->head->next = node;
            node->next = NULL;
         }
      }
      else
      {
         int cmp = strcmp (node->nom, p->nom);
         PRINTF (("else %s %s %d", node->nom, p->nom, cmp));
         if (cmp < 0)
         {
            PRINTF ((".head\n"));
            node->next = liste->head;
            liste->head = node;
         }
         else
         {
            int done = 0;
            while (!done && p->next != NULL)
            {
               int cmp = strcmp (node->nom, p->next->nom);
               PRINTF ((" %s %s %d", node->nom, p->next->nom, cmp));
               if (cmp < 0)
               {
                  PRINTF ((".mid\n"));
 
                  node->next = p->next;
                  p->next = node;
                  done = 1;
               }
               p = p->next;
            }
            if (!done)
            {
               PRINTF ((".tail\n"));
 
               p->next = node;
               node->next = NULL;
            }
         }
      }
   }
}
 
void tri_list (struct list *liste)
{
   struct list new = { NULL };
 
   {
      /* first location */
      struct node *p = liste->head;
 
      while (p != NULL)
      {
         /* save the next location address */
         struct node *next = p->next;
 
         /* detach the node */
         p->next = NULL;
 
         /* insert the node in the sorted list */
         insert_sorted (&new, p);
         aff_list (&new);
 
         /* point to the next location */
         p = next;
      }
   }
 
   /* quand c'est termine : */
   liste->head = new.head;
}
 
#ifdef TEST
 
int main (void)
{
/* liste chainee */
   static struct node a[] = {
      {"B", a + 1},
      {"A", a + 2},
      {"D", a + 3},
      {"C", NULL},
   };
 
   struct list liste = { a };
 
   aff_list (&liste);
   tri_list (&liste);
   aff_list (&liste);
   return 0;
}
 
#endif

Mon algo d'insertion est assez compliqué, car il y a beaucoup de cas spéciaux à traiter, mais il a l'air de fonctionner...

Citation:

Envoyé par Emmanuel Delahaye

Mon algo d'insertion est assez compliqué, car il y a beaucoup de cas spéciaux à traiter, mais il a l'air de fonctionner...

insert_sorted peut se réduire à :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 void insert_sorted (struct list *liste, struct node *node) { struct node **pp = &(liste->head); int done = 0; while( !done && *pp != NULL ) { if( strcmp(node->nom, (*pp)->nom )<0) { node->next = *pp; *pp = node; done = 1; } else { pp = &((*pp)->next); } } if( !done ) { *pp = node; } }
Il me semble que tous les cas son pris en compte : liste vide, un seul noeud, deux noeuds et plus.

Citation:

Envoyé par ssmario2

insert_sorted peut se réduire à :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
void insert_sorted (struct list *liste, struct node *node)
{
	struct node **pp = &(liste->head);
	int done = 0;
 
	while( !done && *pp != NULL )
	{
		if( strcmp(node->nom, (*pp)->nom )<0)
		{
			node->next = *pp;
			*pp = node;
			done = 1;
		}
		else
		{
			pp = &((*pp)->next);
		}
	}
	if( !done )
	{
		*pp = node;
	}
}

Il me semble que tous les cas son pris en compte : liste vide, un seul noeud, deux noeuds et plus.

Ca a l'air d'aller.

Je vais sortir mon test unitaire de la mort :

Code:

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
 
#ifdef TEST
 
static void test (struct list* liste)
{
   aff_list (liste);
   tri_list (liste);
   aff_list (liste);
   printf ("\n");
}
 
 
static void test_vide (void)
{
 
   struct list liste = { NULL };
 
   test (&liste);
}
 
static void test_un_element (void)
{
/* liste chainee */
   static struct node a[] = {
      {"B", NULL},
   };
 
   struct list liste = { a };
 
   test (&liste);
}
 
static void test_deux_elements_tries (void)
{
/* liste chainee */
   static struct node a[] = {
      {"A", a + 1},
      {"B", NULL},
   };
 
   struct list liste = { a };
 
   test (&liste);
}
 
static void test_deux_elements_inverses (void)
{
/* liste chainee */
   static struct node a[] = {
      {"B", a + 1},
      {"A", NULL},
   };
 
   struct list liste = { a };
 
   test (&liste);
}
 
static void test_trois_elements_abc (void)
{
/* liste chainee */
   static struct node a[] = {
      {"A", a + 1},
      {"B", a + 2},
      {"C", NULL},
   };
 
   struct list liste = { a };
 
   test (&liste);
   printf ("\n");
}
 
static void test_trois_elements_acb (void)
{
/* liste chainee */
   static struct node a[] = {
      {"A", a + 1},
      {"C", a + 2},
      {"B", NULL},
   };
 
   struct list liste = { a };
 
   test (&liste);
   printf ("\n");
}
 
static void test_trois_elements_bac (void)
{
/* liste chainee */
   static struct node a[] = {
      {"B", a + 1},
      {"A", a + 2},
      {"C", NULL},
   };
 
   struct list liste = { a };
 
   test (&liste);
   printf ("\n");
}
 
static void test_trois_elements_bca (void)
{
/* liste chainee */
   static struct node a[] = {
      {"B", a + 1},
      {"C", a + 2},
      {"A", NULL},
   };
 
   struct list liste = { a };
 
   test (&liste);
   printf ("\n");
}
 
static void test_trois_elements_cab (void)
{
/* liste chainee */
   static struct node a[] = {
      {"C", a + 1},
      {"A", a + 2},
      {"B", NULL},
   };
 
   struct list liste = { a };
 
   test (&liste);
   printf ("\n");
}
 
static void test_trois_elements_cba (void)
{
/* liste chainee */
   static struct node a[] = {
      {"C", a + 1},
      {"B", a + 2},
      {"A", NULL},
   };
 
   struct list liste = { a };
 
   test (&liste);
   printf ("\n");
}
 
int main (void)
{
   test_vide ();
   test_un_element ();
   test_deux_elements_tries ();
   test_deux_elements_inverses ();
   test_trois_elements_abc ();
   test_trois_elements_acb ();
   test_trois_elements_bac ();
   test_trois_elements_bca ();
   test_trois_elements_cab ();
   test_trois_elements_cba ();
   return 0;
}
#endif

Moi, je dis OK :

Code:

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
 
NIL
NIL
 
B -> NIL
B -> NIL
B -> NIL
 
A -> B -> NIL
A -> NIL
A -> B -> NIL
A -> B -> NIL
 
B -> A -> NIL
B -> NIL
A -> B -> NIL
A -> B -> NIL
 
A -> B -> C -> NIL
A -> NIL
A -> B -> NIL
A -> B -> C -> NIL
A -> B -> C -> NIL
 
 
A -> C -> B -> NIL
A -> NIL
A -> C -> NIL
A -> B -> C -> NIL
A -> B -> C -> NIL
 
 
B -> A -> C -> NIL
B -> NIL
A -> B -> NIL
A -> B -> C -> NIL
A -> B -> C -> NIL
 
 
B -> C -> A -> NIL
B -> NIL
B -> C -> NIL
A -> B -> C -> NIL
A -> B -> C -> NIL
 
 
C -> A -> B -> NIL
C -> NIL
A -> C -> NIL
A -> B -> C -> NIL
A -> B -> C -> NIL
 
 
C -> B -> A -> NIL
C -> NIL
B -> C -> NIL
A -> B -> C -> NIL
A -> B -> C -> NIL
 
 
 
Process returned 0 (0x0)   execution time : 0.097 s
Press any key to continue.

Le coup du 'pp' est apparemment indispensable... C'est troublant...

Citation:

Envoyé par Emmanuel Delahaye

Le coup du 'pp' est apparemment indispensable... C'est troublant...

mmm.... On peut faire plus simple si vous voulez, en ajoutant un élément en début de liste ( qui ne fera pas partie du trie ) ainsi la liste ne sera jamais vide, donc plus besoin de faire une série de tests pour des cas bien particulier.
l'élément inséré ( une sentinelle ? ) sera biensûr retiré une fois le trie effectué, quelque chose comme :
Code:

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 <...> void insert_sorted (struct list *liste, struct node *node) { /* liste->head ne peut être NULL meme si la liste est vide */ if (liste->head != NULL) { struct node *p = liste->head; int done = 0; while (!done && p->next != NULL) { int cmp = strcmp (node->nom, p->next->nom); if (cmp < 0) { node->next = p->next; p->next = node; done = 1; } p = p->next; } if (!done) { p->next = node; node->next = NULL; } } } <...> void tri_list (struct list *liste) { struct node sentinelle={ "DUMMY", NULL }; struct list new; new.head = &sentinelle; /* first location */ struct node *p = liste->head; while (p != NULL) { /* save the next location address */ struct node *next = p->next; /* detach the node */ p->next = NULL; /* insert the node in the sorted list */ MO_insert_sorted (&new, p); aff_list (&new); /* point to the next location */ p = next; } /* quand c'est termine : */ liste->head = new.head->next; } <...>
et ça passe votre test unitaire de la mort ;)