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

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

Marsh Posté le 23-10-2002 à 04:11:56    

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 :D (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 !
Reply

Marsh Posté le 23-10-2002 à 04:11:56   

Reply

Marsh Posté le 23-10-2002 à 04:21:04    

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é
Reply

Marsh Posté le 23-10-2002 à 04:30:39    

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 :D
 
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 !
Reply

Marsh Posté le 23-10-2002 à 04:39:25    

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é
Reply

Marsh Posté le 23-10-2002 à 04:45:22    

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 :
  1. typedef struct element
  2. {
  3.   tpacket t;
  4.   struct element *next;
  5. }element;
  7. typedef struct
  8. {
  9.   element* head;
  10.   element* tail;
  11.   int nbelem;
  12. }c_list;
  14. void add(element *el, c_list *c)
  15. {
  16.   if(c->nbelem == 0)
  17.     {
  18.       c->head=(c->tail=el);
  19.     }
  20.   else
  21.     {
  22.       (c->tail)->next = el;
  23.       c->tail=el;
  24.     }
  25.   el->next = c->head;
  26.   (c->nbelem)++;
  27. }
  29. element *take(element *el, c_list *c)
  30. {
  31.   element *former_head;
  32.   if(c->nbelem == 0)
  33.     return NULL;
  34.   former_head = c->head;
  35.   c->head = (c->head)->next;
  36.   (c->tail)->next = c->head;
  37.   (c->nbelem)--;
  38.   return former_head;
  39. }


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


---------------
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 !
Reply

Marsh Posté le 23-10-2002 à 04:56:29    

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é
Reply

Marsh Posté le 23-10-2002 à 05:00:29    

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é
Reply

Marsh Posté le 23-10-2002 à 05:00:29    

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 !
Reply

Marsh Posté le 23-10-2002 à 05:53:43    

et j'ai oublie le malloc :D
 
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 :
  1. typedef struct element
  2. {
  3.   int t; // <== vous mettez ce que vous voulez ici
  4.   struct element *prev;
  5. }element;
  7. typedef struct
  8. {
  9.   element* head;
  10.   pthread_mutex_t mutex;
  11. }c_list;
  13. void add(int i, c_list* c)
  14. {
  15.   element* el;
  16.   el = (element*)malloc(sizeof(element));
  17.   el->t = i;
  18.   pthread_mutex_lock(&(c->mutex));
  19.   if(c->head == NULL)
  20.     {
  21.       c->head = el;
  22.       (c->head)->prev = c->head;
  23.     }
  24.   else
  25.     {
  26.       el->prev = (c->head)->prev;
  27.       (c->head)->prev = el;
  28.       c->head = el;
  29.     }
  30.   pthread_mutex_unlock(&(c->mutex));
  31. }
  33. int* take(c_list *c)
  34. {
  35.   element *former_tail;
  36.   pthread_mutex_lock(&(c->mutex));
  37.   if(c->head == NULL)
  38.     return NULL;
  39.   former_tail = (c->head)->prev;
  40.   (c->head)->prev = former_tail->prev;
  41.   pthread_mutex_unlock(&(c->mutex));
  42.   return &(former_tail->t);
  43. }


 
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 !
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed