Discussion :

[Ganondorf]

bonsoir à tous,

j'ai un soucis pour la suppression dans ma liste, je vais commencer par vous exposer le code

structure client

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
typedef struct clientinfo
{
	char uid[UIDLEN+1];
	char nick[NICKLEN+1];
	char user[USERLEN+1];
	char host[HOSTLEN+1];
	char name[REALLEN+1];
	char modes[MODELEN+1];
	char server[SIDLEN+1];
 
    struct clientinfo *next;
	time_t uptime;
} aClient;

code pour ajouter un nouveau client

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
 
aClient *client_head = NULL; /* contient le pointeur de tête */
 
int add_client(const char *uid, const char *nick, const char *user, const char *host,
               const char *server, const char *modes, const char *name)
{
	aClient *c;
 
	c = calloc(1, sizeof(*c));
 
	if (!c)
	{
		printf("add_client(): out of memory\n");
		return 0;
	}
 
    strncpy(c->nick, nick, NICKLEN);
    strncpy(c->user, user, USERLEN);
    strncpy(c->host, host, HOSTLEN);
    strncpy(c->uid, uid, UIDLEN);
    strncpy(c->server, server, SIDLEN);
    strncpy(c->modes, modes, MODELEN);
    strncpy(c->name, name, REALLEN);
 
    c->next = NULL;
	c->uptime = time(NULL);
 
	if (client_head == NULL) client_head = c;
	else
	{
		while (client_head->next != NULL)
		{
			client_head = client_head->next;
		}
		client_head->next = c;
	}
	return 1;
}

et le code pour la suppression

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
 
void del_client(const char *uid)
{
	aClient *c = client_head;
	aClient *d;
 
	while (c != NULL)
	{
		if (!strcasecmp(uid, c->uid))
		{
			d = c;
			break;
		}
		c = c->next;
	}
	free(d);
 
    /* affichage de la nouvelle liste */
 
	while (client_head != NULL)
	{
		printf("CLIENT RESTANT: %s\n", client_head->nick);
		client_head = client_head->next;
	}
}

je n'ai aucun bug (pour le moment) mais le code ne fait pas son boulot, lorsqu'un client se deconnecte la fonction del_client est invoquée, pour vérifier a la fin j'affiche la liste des clients restant et le probleme est que le client censé être déconnecté apparait toujours, j'ai lu plusieurs tuto sur les listes chainées et notament sur la suppression dans une liste mais je n'arrive pas a reproduire, je vous remerci par avance pour votre aide

[diogene]

Tu détruis bien le maillon que tu veux, mais tu ne le retires pas de la liste puisque tu ne changes pas le chainage des maillons :

Si A est le maillon à détruire (si il existe), P celui qui le précède (si il existe) et S celui qui le suit (si il existe), alors P.next doit pointer sur S après destruction de A. Cela signifie qu'il faut rechercher le maillon P qui précède celui qu'on veut enlever (si il existe).

Le maillon est détruit mais continue à apparaitre dans la liste parce que le système n'a pas encore récupéré la mémoire pour l'utiliser à autre chose. Sinon, il y aurait plantage parce que la liste est, elle, détruite.

[Ganondorf]

je séche, j'aurai besoin d'un petit exemple, j'ai fais ceci la methode ma paraissait pourtant bonne

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
 
/*
* suppression d'une structure client
*/
void del_client(const char *uid)
{
	aClient *c = client_head;
	aClient *prev = NULL;
 
	while (c != NULL)
	{
		if (!strcasecmp(uid, c->uid))
			break;
 
		prev = c;
		c = c->next;
	}
 
	if (prev)
		prev->next = c->next;
 
	free(c);
	c = NULL;
 
	if (client_head == NULL) printf("aucun client restant\n");
	while (client_head != NULL)
	{
		printf("client restant: %s\n", client_head->nick);
		client_head = client_head->next;
	}
}

[diogene]

Supposons qu'on veuille supprimer le maillon Element2 de cette liste :

Code :

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

1
2
Départ :                        next            next          next
   client_head >----> Element1 >----> Element2 >---->Element3---->.....>----> NULL

On veut donc obtenir la liste suivante :

Code :

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

1
2
Arrivée :                              next                  next
   client_head >----> Element1 >-------------------->Element3---->.....>----> NULL

On voit que le champ next du maillon Element1 qui précédait Element2 doit être modifié pour pointer maintenant sur celui qui suivait Element2.
Il faut donc pouvoir obtenir l'adresse du maillon qui précède celui que l'on veut supprimer.
Si la liste est doublement chainée, pas de problème : Connaissant l'adresse du maillon à supprimer, on obtient celle de celui qui précède, puisque le maillon possède deux pointeurs de chainage : un pointeur vers le suivant et un pointeur vers le précédent.
Si la liste est simplement chainée comme dans ton cas, on ne peut revenir en arrière et donc il faut chercher l'adresse du maillon qui précède celui à supprimer.
On a plusieurs cas :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1- la liste est vide (client_head est NULL). Rien à faire

2- la liste n'a qu'un maillon (client_head non NULL et client_head->next est NULL). 
  Si ce maillon est celui à supprimer, le détruire et mettre client_head à NULL (la liste est maintenant vide). 
  Sinon, rien à faire.

3- Sinon, rechercher le maillon qui précède le maillon à supprimer. 
    Ce maillon d'adresse p est celui pour lequel on a p->next à supprimer. Donc le test porte sur p->next. 
    Si on trouve un maillon p pour lequel le test est positif
         a- stocker p->next dans un pointeur q (le maillon d'adresse q est celui à supprimer)
         b- remplacer p->next par q->next
         c- supprimer q
    Sinon, rien à faire

Le cas 3 est illustré ci-dessous

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
Départ :                        next              next          next
   client_head >----> Element1 >------> Element2 >---->Element3 >---->.....>----> NULL
a-                       p                 q
                                             

b-                                   -----------------          
                                    /                  \          
   client_head >----> Element1 >----    Element2 >------>Element3 >---->.....>----> NULL
                         p      next       q      next           next

c-                        
   client_head >----> Element1 >------------------------>Element3 >---->.....>----> NULL
                         p      next                             next

[Ganondorf]

merci diogene,

voici ce que j'ai fais, ca ne fonctionne pas encore mais je voudrai savoir si je vais dans le bon sens

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
 
/*
* suppression d'une structure client
*/
void del_client(const char *uid)
{
	aClient *p, *q;
 
	/* la liste est vide, rien à faire */
	if (client_head == NULL);
		return;
 
	if (client_head != NULL && client_head->next == NULL)
	{
		if (!strcasecmp(uid, client_head->uid))
		{
			free(client_head);
			client_head = NULL;
		}
	}
 
	while (client_head != NULL)
	{
		if (!strcasecmp(uid, client_head->uid))
		{
			/* ici je bloque */
		}
		p = client_head; /* pointeur precedent */
		client_head = client_head->next; /* pointeur courant */
	}
 
	if (client_head == NULL) printf("aucun client restant\n");
	while (client_head != NULL)
	{
		printf("client restant: %s\n", client_head->nick);
		client_head = client_head->next;
	}
}

[diogene]

client_head est une variable globale (ce qui n'est pas bien et devra être changé plus tard). Donc quand tu écris

Code :

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

client_head = client_head->next;

tu détruis ta tête de liste.

Code :

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

if (client_head == NULL);

Attention au ';'

[Ganondorf]

je n'ai toujours pas réussi cependant dans le cas ou j'ai beaucoup de client à gérer (au moins 300) es-ce que cette manière de faire et la plus adéquate, ou y 'a t'il une solution plus optimisé

[Ganondorf]

mon problème est corrigé, j'ai utilisé une liste doublement chainée, pour ceux que ca intéresse voici le code

ajout d'un nouveau client:

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
 
/*
* creation d'une nouvelle structure client
*/
aClient *add_client(const char *uid, const char *nick, const char *user, const char *host,
               const char *server, const char *modes, const char *name)
{
	aClient *c;
 
	c = calloc(1, sizeof(*c));
 
	if (!c) return NULL;
 
	strncpy(c->nick, nick, NICKLEN);
	strncpy(c->user, user, USERLEN);
	strncpy(c->host, host, HOSTLEN);
	strncpy(c->uid, uid, UIDLEN);
	strncpy(c->server, server, SIDLEN);
	strncpy(c->name, name, REALLEN);
 
	parse_umodes(c, (char *)modes);
 
	c->next = clientlist;
	c->prev = NULL;
 
	if (c->next)
		c->next->prev = c;
 
	clientlist = c;
 
	return c;
}

recherche d'un client en fonction de son identifiant

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
 
/*
* recherche un client en fonction de son identifiant
* et renvoi un pointeur sur sa structure s'il existe sinon renvoi NULL
*/
aClient *find_client_uid(const char *uid)
{
	aClient *c = clientlist;
 
	while (c != NULL)
	{
		if (!strcasecmp(uid, c->uid))
			return c;
		c = c->next;
	}
	return NULL;
}

et la suppression d'un client

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
 
/*
* suppression d'une structure client
*/
void del_client(const char *uid)
{
	aClient *c = find_client_uid(uid);
	aClient *d;
 
	if (c->prev)
		c->prev->next = c->next;
	else clientlist = c->next;
 
	if (c->next)
		c->next->prev = c->prev;
 
	free(c);
 
	d = clientlist;
 
    /* affichage de la liste pour les tests */
	if (d == NULL) printf("aucun client restant\n");
	while (d != NULL)
	{
		printf("Client restant: %s\n", d->nick);
		d = d->next;
	}
}

ca fonctionne mais es-ce vraiment la méthode la plus rapide ?