tri par insertion, list simplement chainee

**Buyakhaska** · 11/11/2008, 17h18

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

**Emmanuel Delahaye** · 11/11/2008, 18h13

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 :

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
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...

**orfix** · 11/11/2008, 22h36

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 :

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
 
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.

**Emmanuel Delahaye** · 11/11/2008, 22h50

Envoyé par ssmario2

insert_sorted peut se réduire à :

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
 
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 :

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
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 :

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
 
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...

**orfix** · 12/11/2008, 20h30

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 :

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
 
<...>
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

tri par insertion, list simplement chainee

C

Discussions similaires

Partager

Partager