Forum Programmation.c Encore moi, je rame...

• # Commentaire supprimé

  Posté par Anonyme le 29 juillet 2004 à 16:21. Évalué à 2.

  

  Ce commentaire a été supprimé par l’équipe de modération.

  • [^] # Re: C'est quoi une "fifo circulaire" ?

    Posté par Pierre Jacquier le 29 juillet 2004 à 16:24. Évalué à 1.

    

    Quand je parle de circulaire, en fait, c'était juste le modulo taille du tableau...
    Ca fait de la circularité...
    Merci beaucoup ...

• # c'est simple

  Posté par vincent LECOQ (site web personnel) le 29 juillet 2004 à 16:39. Évalué à 1.

  

  fait une liste chainee circulaire ...
  ca marche tres bien, voire meme une liste doublement chainee circulaire
  sinon le plus simple avec un tableau est de bien gerer tes indexs de boucles avec i%taille de ton tableau

  • [^] # Re: c'est simple

    Posté par Pierre Jacquier le 29 juillet 2004 à 16:41. Évalué à 1.

    

    je pensais qu'une liste chainee circulaire serait plus jolie, mais comment la rendre circulaire ? Comme on ne connait pas sa taille... Ou alors on définit une taille maximum, comme pour un tableau ?

    • [^] # Re: c'est simple

      Posté par ham le 30 juillet 2004 à 01:18. Évalué à 1.

      

      D->next == A (le "début")
      
      ensuite faire une fifo circulaire c'est surtout avec des tableau et des index bien géré:
      c'est interessant d'avoir une strucutre qui boucle car on a pas a deplacer les éléments
      0 1 2 3 4 X X
      ajout -> 0 1 2 3 4 5 X
      remove -> X 1 2 3 4 5 X
      ajout -> X 1 2 3 4 5 6
      ajout -> 7 1 2 3 4 5 6 -> fifo plein
      remove -> 7 X 2 3 4 5 6 -> ok
      
      
      
      Si tu fait avec des pointeurs du coup tu n'a plus besoin d'avoir de fifo circulaire, puisque tu peut juste mettre un element de debut et un de fin.
      
      pour la form rendre une liste chainé circulaire (qui se mord la queue):
      struct list_item_s {
      struct list_item_s *next;
      void * data
      };
      
      struct list_s {
      struct list_item_s * head;
      struct list_item_s * tail;
      struct list_item_s * pool; // Cf le Offtopic
      int pool_size;
      unsigned int size; // pour la forme
      }
      
      et pour rendre circulaire la liste:
      A->B->C->D->A
      la structure list est la pour marquer un element comme le debut et pas partir dans des boucles infini.
      L'avantage c'est si tu ne considere que le prochain element dans ton traitement, la gestion devient tres simple: tu prend le current->next.
      
      par contre tu as toujours besoin de la structure de liste pour l'insertion des éléments dans l'ordre.
      
      Offtopic, pour m'entrainer:
      
      ensuite les listes chainée sont pénalisantes niveau allocation mémoire, ou alors il faut les allouer en bloc et en ajoutant un struct list_item_s * pool_start dqns la structure de liste;
      alloc_pool() {
      ptr = malloc(constante*sizeof(struct list_s));
      // nettoyage
      memset(ptr,0,constante*sizeof(struct list_s));
      // mettre les pointeurs les un q lq suite des autres
      
      for (i=0; i <constante-1;i++) {
      temp_item =((struct...)ptr)[i];
      temp_item->next=((struct...)ptr)[i+1];
      }
      //comme ca en mémoire si constante==5
      A->B->C->D->E->
      list->pool=((struct...)ptr);
      list->pool_size=constante;
      }
      
      
      
      add_data(void * data) {
      //add data to the end of the list
      if (list->head == NULL) {
      alloc_pool();
      list->head = list->pool;
      list->pool = list->pool->next;
      list->head->next=list->head;
      list->tail=list->head;
      list->size=1;
      return;
      }
      // go to the end
      tail = list->tail;
      if (list->pool == NULL) {
      //pool exhausted
      alloc_pool()
      }
      // list->pool != NULL
      tail->next = list->pool; // on rajoute apres le dernier element
      list->pool = list->pool->next;//on change le pool,
      tail->next->next=list->head;//le nouveau dernier pointe vers la tete
      list->tail=list->tail->next;// on update le tail
      list->size=list->size+1;
      return;
      }
      
      remove_data() {
      //enleve la tete de liste
      if list->head == NULL return NULL;
      return_ptr = list->data;
      element=list->head;.
      if (list->head == list->tail) {
      list->head=NULL;
      list->tail==NULL;
      list->size=0;
      } else {
      // update des pointeurs
      list->head=list->head->next;
      list->tail->next = list->head;
      list->size = list->size -1;
      }
      // on manage le pool
      // des fois il fqut liberer de la memoire
      if (list->pool_size=constante) {
      // dans pool: un pool entier
      free (list->pool);
      list->pool=NULL.
      list->pool_size =0;
      }
      // on remet l'element enlever dqns le pool
      element->next = list->pool;
      list->pool_size= list->pool_size+1;
      list->pool=element;
      return returnn_ptr;
      }
      
      Et pour faire overkill, constante peut varier en fonction des stats, mais il fqut mettre des octets de gqrde avant et aprés le pool, et vérifer ces octets pour la libérqtion

• # Cool, j'ai compris

  Posté par Pierre Jacquier le 29 juillet 2004 à 16:48. Évalué à 1.

  

  Merci à tous les deux, vous venez de me sauver la vie.
  J'ai bien compris comment m'y prendre.
  A plus tard pour de nouvelles aventures !!!
  
  Jacouille la fripouille

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.