Résolution d'un problème sur les Files

Bonjour à tous. Vraiment chapeau à l'initiateur ou aux initiateurx de ce site.Je suis nouveau dans le forum , je passe directement à ma préoccupation sans être long:
J'ai beaucoup de problème à résoudre cet exercice vu mon très faible niveau en programmation; début du problème:

L'objectif de cet exercice est de manipuler une file à base d'un vecteur circulaire.
La file est composée d'un vecteur de N élément de type "Objet" et de deux variables entières:
f: l'index de l'élément de début; r: l'index suivant celui du dernier élément.
a) Illustrer à l'aide d'un schéma, la configuration normale et la configuration circulaire d'une telle file.
b) Proposer en C, une structure de données pour cette file.

Merci d'avance pour vos réponses. :roll:

Bonsoir et bienvenue sur developpez.com.

Nous t'aiderons mais ne ferons pas l'exercice à ta place.

Qu'as-tu déjà fait ?

Pour du C, petit indice : les listes chainées.

Pour implémenter un buffer circulaire, un tableau suffit. (redimensionnable s'il le faut).

Je ne sais pas pourquoi (*), à la fin de la seconde décennie du XXIe siècle, on s'obstine à utiliser les indices de début et fin (ou + 1) pour les files représentées par des tableaux circulaires.

Ca fait une embrouille pour tester si c'est complétement plein ou complétement vide, et ça implique de conserver une place vide dans le buffer, ce qui choque profondément mon sens de l'économie.


En effet, un indice dans un tableau circulaire de taille N ne peut prendre que N valeurs, donc le nombre d'éléments présents, qui commence à 0, ne peut aller que jusqu'à N-1. Donc il reste une case vide. C'est con, hein ?

Autant avoir indice de début + nb d'éléments, l'autre bout de la file étant à l'indice (début + nb - 1) % N.

(*) parce que c'était écrit comme ça dans les vieux bouquins, quand on programmait en assembleur des tampons circulaires de caractères de taille 256 avec les indices dans des octets ?

Merci vraiment à tous pour la considération que vous accorder à ma préoccupation.je vous montrerai ce que j'ai moi-meme fait.

Je sais pourquoi à la fin de la seconde décennie du XXIe siècle, on s'obstine à utiliser les indices de début et fin pour les files représentées par des tableaux circulaires.
Les buffers circulaires sont souvent utilisés pour transmettre des données en FIFO entre 2 threads ou entre une interruption et un thread. Il est alors primordial d'utiliser des accès atomiques et qu'aucun élément de synchro ne soit écrit par plusieurs entités.
En utilisant Indice début et taille utilisée, cela n'est pas possible (pour ajouter on change la taille, pour extraire on change aussi la taille en plus de l'indice de début.)
En utilisant un indice de début et un indice de fin, cela fonctionne. L'écrivain effectue une incrémentation atomique de l'indice de fin, alors que le lecteur effectue une incrémentation atomique de l'indice de début. Il y a par contre une contrainte supplémentaire : on met au maximum N-1 éléments dans le tableaux, on évite ainsi d'avoir à distinguer le cas vide du cas plein avec N valeurs.

Oui mais il n'y a pas que l'incrémentation/décrémentation à faire, il y a aussi la copie de l'élément désigné par l'indice. L'atomicité, ça ne marchera tout seul que si écrire+incrémenter l'indice se fait en une opération atomique.

Bonjour

Citation:

---

Envoyé par Pladel

J'ai beaucoup de problème à résoudre cet exercice vu mon très faible niveau en programmation

---

Désolé, ce genre de phrase vue 10000 fois ça ne prend pas. Si tu as un exercice, c'est que tu as eu l'enseignement pour le résoudre donc tu as le niveau. Et si tu n'as pas le niveau, c'est que tu n'as pas travaillé quand tu aurais dû...

Citation:

---

Envoyé par Pladel

L'objectif de cet exercice est de manipuler une file à base d'un vecteur circulaire.
La file est composée d'un vecteur de N élément de type "Objet" et de deux variables entières:
f: l'index de l'élément de début; r: l'index suivant celui du dernier élément.
b) Proposer en C, une structure de données pour cette file.

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11

typedef struct { ... ... ... } t_objet;   typedef struct { t_objet tab[SIZE_FILE + 1]; unsigned short f; unsigned short r; } t_file;

---

Voilà comment je ferais. Mais ne te méprends pas. Ce n'est pas parce que j'écris la structure (somme toute très banale qui aurait pu être donnée par le prof) que ça signifie qu'on fera la suite de l'exo...

Citation:

---

Envoyé par Pladel

Merci d'avance pour vos réponses. :roll:

---

Donc déjà on ne remercie jamais d'avance. Cette fausse politesse met le lecteur en porte à faux se sentant en quelque sorte "obligé" de faire ce pour quoi il a été remercié. Et le smiley "roll" est un smiley sarcastique signifiant "c'est vraiment n'importe quoi". Pour une première sur ce forum, tu fais assez fort...

Citation:

---

Envoyé par ekieki

Je ne sais pas pourquoi, à la fin de la seconde décennie du XXIe siècle, on s'obstine à utiliser les indices de début et fin (ou + 1) pour les files représentées par des tableaux circulaires.

---

Peut-être parce que le changement de siècle n'a pas rendu périmé une technologie qui était valable auparavant...

Citation:

---

Envoyé par ekieki

Ca fait une embrouille pour tester si c'est complétement plein ou complétement vide, et ça implique de conserver une place vide dans le buffer, ce qui choque profondément mon sens de l'économie.

---

Pour une place ? C'est quand-même pas la mort quoi. Es-tu choqué par la place prise par le '\0' dans les chaines ?
Ok, le '\0' c'est un caractère alors que si on gère un buffer de super gros trucs, on perd une super grosse place. Mais on peut alors remplacer ça par un flag vide/non vide ce qui ne prend alors qu'un char/int...

Citation:

---

Envoyé par ekieki

Autant avoir indice de début + nb d'éléments, l'autre bout de la file étant à l'indice (début + nb - 1) % N.

---

En effet, ça aurait pu (et même au siècle précédent). Mais (cf dalfab)...

Citation:

---

Envoyé par ekieki

L'atomicité, ça ne marchera tout seul que si écrire+incrémenter l'indice se fait en une opération atomique.

---

C'est tout à fait possible de grouper plusieurs actions dans une opération atomique...

Citation:

---

Envoyé par Sve@r

C'est tout à fait possible de grouper plusieurs actions dans une opération atomique...

---

Comme quoi, ce n'est pas plus difficile de faire

Code:

---

1 2	longueur = longueur + 1; data[(debut + longueur) mod taille] = element;

---

quer

Code:

---

1 2	dernier = (dernier + 1) mod taille; data[dernier] = element

---

et que l'objection sur l'atomicité ne tient pas, l'une n'étant pas d'une nature intrinsèquement plus atomique que l'autre.