C++

[C] Circular queue... Lol c quoi l'interet :D

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [C] Circular queue... Lol c quoi l'interet :D

Tetedeiench

Head Of God

je veux juste qu'on me dise l'interet de cette structure, dans le cas ou l'implementation est avec une liste chainee...

Je veux dire, a la base, une circular queue, c'est juste une liste chainee, ou on sauvegarde la tete et la queue, ou on insere en queue et on prends en tete (FIFO somme toute).

Mais alors a quoi sert le lien qui fait que le suivant de la queue c'est la tete ?

Meme dans le cas ou la liste est vide ca sert a rien...

a un element ca sert a rien...

a plein d'element ca sert a rien...

Pour un tableau ou le nb d'element est limite, a la rigueur ( et encore).

Mais la...

Je veux juste qu'on m'explique l'interet (l'implementation moi y en a savoir faire).

Merci

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

Publicité

joce

Architecte / Développeur principal
"BugHunter"

si tu te trouves sur un élément particulier et qu'à partir de lui tu veux scanner toute ta liste, tu fais comment si ca reboucle pas :heink:

Message édité par joce le 23-10-2002 à 04:21:17

---------------
Protèges carnets personnalisés & accessoires pour bébé

Tetedeiench

Head Of God

joce a écrit a écrit :

si tu te trouves sur un élément particulier et qu'à partir de lui tu veux scanner toute ta liste, tu fais comment si ca reboucle pas :heink:

ben si tu arrives sur la queue tu repars sur la tete

Mais ouai t'as raison j'avais pas DU TOUT pense au scan... car dans mon probleme ( gerer une queue de paquets a envoyer, FIFO, donc ajout en queue et envoi en tete) on fera pas du tout ca... juste prendre et mettre des elements.

Et ils nous demande une circular queue... alors qu'une linked list aurait marche pareil.

M'enfin [:spamafote]

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

joce

Architecte / Développeur principal
"BugHunter"

Ba ca dépent du sens de tes links dans la liste chainée, ca peut être super rapide :

tu te choppes ce qu'il faut sur la tête, tu effaces le block en refaisant les links, et tu fais un prev pour te retrouver sur la queue directos et faire ton insertion.

Donc faut faire le link de la tête vers la queue et non l'inverse (si tu choppes et qu'en suite t'inséres).
Mais le mieux c'est de faire une double liste chainée, comme ca tu te balades entre la tête et la queue dans les deux sens sans problème

---------------
Protèges carnets personnalisés & accessoires pour bébé

Tetedeiench

Head Of God

joce a écrit a écrit :

Ba ca dépent du sens de tes links dans la liste chainée, ca peut être super rapide :

tu te choppes ce qu'il faut sur la tête, tu effaces le block en refaisant les links, et tu fais un prev pour te retrouver sur la queue directos et faire ton insertion.

Donc faut faire le link de la tête vers la queue et non l'inverse (si tu choppes et qu'en suite t'inséres).
Mais le mieux c'est de faire une double liste chainée, comme ca tu te balades entre la tête et la queue dans les deux sens sans problème

Ouaip, je vois ce que tu veux faire, mais la je n'en aurai pas besoin : J'insere et je prends a une frequence differente.

Donc un seul sens suffit pour ma liste.

Vla mon code fait rapidos, compile mais je sais pas si il tourne ( pas encore teste... faut que je progge les sockets avant, etj'ai pas envie de le faire today )

Code :

typedef struct element
{
tpacket t;
struct element *next;
}element;
typedef struct
{
element* head;
element* tail;
int nbelem;
}c_list;
void add(element *el, c_list *c)
{
if(c->nbelem == 0)
{
c->head=(c->tail=el);
}
else
{
(c->tail)->next = el;
c->tail=el;
}
el->next = c->head;
(c->nbelem)++;
}
element *take(element *el, c_list *c)
{
element *former_head;
if(c->nbelem == 0)
return NULL;
former_head = c->head;
c->head = (c->head)->next;
(c->tail)->next = c->head;
(c->nbelem)--;
return former_head;
}

C'est aussi efficace comme ca, et ca prends moins de place que toi, non ?

(j'avais pas envie de me faire chier a gerer les erreurs )

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

joce

Architecte / Développeur principal
"BugHunter"

en tout cas dans take, el sert à rien.
ca sert à quelque chose de stocker le nombre d'element ?

---------------
Protèges carnets personnalisés & accessoires pour bébé

joce

Architecte / Développeur principal
"BugHunter"

sinon pour faire plus simple t'as :

typedef struct element
{
tpacket t;
struct element *prev;
}element;

element* head;

comme ca à partir de la tête t'accède directement à la tail en faisant head->prev, donc simplification de ta structure.
Faut juste changement le sens dans lequel tu fais l'insertion et c'est bon.

Message édité par joce le 23-10-2002 à 05:01:12

---------------
Protèges carnets personnalisés & accessoires pour bébé

Tetedeiench

Head Of God

joce a écrit a écrit :

en tout cas dans take, el sert à rien.
ca sert à quelque chose de stocker le nombre d'element ?

Ouai, car on doit l'afficher (sinon c clair que j'aurai foutu la tete et la queue a null et basta).

Et j'ai pas envie de reparcourir la liste a chaque fois ( mon PC non plus).

Et la t'es d'accord que le fait qu'elle soit circulaire change *rien* a la liste...

Car la, j'aurai pas besoin de faire d'autres operations dessus.

D'ailleurs, j'ai oublie le mutex, oh con.

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

Tetedeiench

Head Of God

et j'ai oublie le malloc

La, pour ceux que ca interesse, vla une implementation d'une liste circulaire sans gestion de la queue, avec uniquement la tete, sans gestion du nb d'element, et qui marche ( j'viens d'taistai), meme avec des threads bossant dessus (mutex power).

Code :

typedef struct element
{
int t; // <== vous mettez ce que vous voulez ici
struct element *prev;
}element;
typedef struct
{
element* head;
pthread_mutex_t mutex;
}c_list;
void add(int i, c_list* c)
{
element* el;
el = (element*)malloc(sizeof(element));
el->t = i;
pthread_mutex_lock(&(c->mutex));
if(c->head == NULL)
{
c->head = el;
(c->head)->prev = c->head;
}
else
{
el->prev = (c->head)->prev;
(c->head)->prev = el;
c->head = el;
}
pthread_mutex_unlock(&(c->mutex));
}
int* take(c_list *c)
{
element *former_tail;
pthread_mutex_lock(&(c->mutex));
if(c->head == NULL)
return NULL;
former_tail = (c->head)->prev;
(c->head)->prev = former_tail->prev;
pthread_mutex_unlock(&(c->mutex));
return &(former_tail->t);
}

OK, y a beaucoup de parentheses, mais c'est pour mieux me relire par la suite ( ca m'aide bcp et ca coute STRICTEMENT rien ).

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

FORUM HardWare.fr

Programmation

C++

[C] Circular queue... Lol c quoi l'interet :D

Sujets relatifs
webdev, sans interet ?	[JAVA] Quel est l'intérêt d'un bean ?? (en association avec les JSP)
PHP + SQL = GALERE LoL	Help me help me une chtite conclusion pour l interet de SQL server
MySQL - PostgreSQL : l'intérêt du relationnel ?	[PHP & MySQL] Intêret du mysql_free_result() ?
[ SCRIPT cote SERVEUR ] C'est quoi l'intérêt du .cgi par rapport au...	[JAVA] interet de faire des package ?
Intérêt du header des navigateurs ?	Quel est l'intéret d'apprendre le C avant le C++ ?
Plus de sujets relatifs à : [C] Circular queue... Lol c quoi l'interet :D

Page générée en 0.050 secondes