tri par insertion, list simplement chainee

Version imprimable

Voir 40 message(s) de cette discussion en une page

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 ;)

Voir 40 message(s) de cette discussion en une page