Discussion :

[Endori]

Bonjour,

Je suis en DUT Info et on a commencé les listes chaînées, les files et les piles. Il y a peu.

Tout ceci reste très obscur pour moi mais pour l'instant, mon incompréhension reste sur l'utilité du malloc dans une structure files.

Je sais que le malloc, c'est de l'allocation de mémoire dynamique. Dans nos précédents TP, on savait allouer une taille à partir d'une variable et de son type. Pourtant, dans notre TP sur les files. Nos professeurs veulent que l'on simule une liste d'attente dans un bureau de poste pendant un temps déterminé. Je sais pas trop qu'est-ce que j'alloue dans ma structure files, sachant que notre élément sera une structure client.
De plus, je ne sais pas quelle sera la taille de mon file puisqu'une fois un client sera servi, il sortira de la file d'attente et qu'on ne sait pas combien de client sera présent dans la file d'attente puisqu'ils apparaissent selon une probabilité.

J'espère m'être bien fait comprendre et que vous pourriez me fournir une explication. Merci d'avance !

[quetzacoatl]

L'utilité d'une file avec l'utilisation de malloc est justement de pouvoir traité un nombre de données indéterminé.
En général, l'élément d'une file est défini de la manière suivante:
struct element

Code :

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

1
2
3
4
5
{
     data donnee;
     struct element* suivant;/*l'utilité de ce champ est de pouvoir accéder
 l'élément suivant dans la file(d'où l'utilisation du pointeur)*/
}

avec data qui peut être un type ou une structure
On défini alors la structure file:

Code :

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

1
2
3
4
5
struct file
{
     struct element premier;/*premier élément de la file*/
     struct element dernier;/*dernier élément de la file*/ 
}

j'espère que t'y vois plus clair

[Endori]

Merci d'avoir répondu si rapidement.

Tu m'éclairci sur les files en général, mais j'ai l'impression que le cours du professeur est différent de ton explication. A moins que je ne m'emmêle.

Si, j'ai bien compris avec le cours du prof (qui n'est par ailleurs que du code. )
Ce doit me donner ça :

Pour mon élément...

Code :

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

1
2
3
4
5
6
struct client
{
double TempsArrive; //Temps d'arrivée du client par rapport à l'ouverture du bureau de poste
double TempsExas; //Combien de temps avant que le client ne reparte exaspéré
struct client* next;
}

Ici, la structure de mon file...

Code :

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

1
2
3
4
5
6
7
8
typedef struct client
{
     struct client premier;
     struct client dernier;
     int taillemax;
     int nb_client;
     client donnee; //Dans mon fichier.c, j'allouerai ici le malloc avec un type CLIENT
} file;

Dis moi, si c'est à peu près ça, s'il te plait. A moins que je n'ai rien compris et ça commence à m'énerver de bloquer, sachant que les profs de TP doivent nous laisser réfléchir tout seul sans se préoccuper de nous... :/

[quetzacoatl]

attends, tu es sûr que tu n'as pas fait une erreur de recopie?
Tu définis deux fois la structure "struct client"?

[quetzacoatl]

En fait il y a deux façons d'implémenter une file:
-la première est la méthode par liste, c'est celle que je t'ai présenté précédemment(elle correspond à ta première "struct client")
-la deuxième manière est l'implémentation par tableau (on limite alors la longueur de la file),par ex:

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
 
struct client
{
double TempsArrive;
double TempsExas;
}
 
struct file
{
    struct client premier;/*le premier dans la file d'attente*/
    int nb_clients;
    struct client tableau[TAILLE]/*les structures clients y sont stockées: le
dernier dans la file d'attente est à la position 0, le premier à la position
nb_clients-1*/
}

ceci est dans le cas où la taille maximale de la file est connue d'avance
Si on ne l'apprend que lors de l'exécution, il faut faire:

Code :

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

1
2
3
4
5
6
7
struct file
{
    struct client premier;
    int taille_max;/*taille maximale autorisée*/
    int nb_clients;
    struct client* tableau;
}

[matafan]

Pour les listes chainées il y a deux solutions. Imaginons que tu ais à gérer une liste de clients, avec pour chaque clients par exemple deux champs de type T1 et T2.

Solution 1 : ajouter un champs dans la structure client elle même, qui permet de chainer des clients. Ca donne :

Code :

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

1
2
3
4
5
6
typedef struct client client_t;
struct client {
    T1 field_1;
    T2 field_2;
    client_t *next;
};

Pour chaque client dans la file, tu as une structure client_t allouée par un malloc.

Solution 2 : utiliser une structure additionnelle pour chainer les structures client. Ca donne :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
typedef struct client client_t;
struct client {
    T1 field_1;
    T2 field_2;
};
 
typedef struct link link_t;
struct link {
    client_t *client;
    client_t *next;
};

Dans ce cas pour chaque client dans la file, tu as un objet client_t alloué par malloc, et un objet link_t alloué lui aussi par malloc.



Ca c'est la base. Après suivant ce que tu as besoin de faire tu peux évidemment ajouter une structure pour représenter ta file, avec un pointeur vers le premier élément, vers le dernier élément, un compte du nombre d'élément... Tout ce que tu peux imaginer suivant ce que tu as besoin de faire.

L'important c'est de comprendre que ta file sera constituée d'un ensemble de structures liées entre elles d'une manière ou d'une autre, et chacune de ses structures sera allouée dynamiquement par un malloc() au moment où un nouveau client arrive.

[Endori]

Ok !!

Je crois avoir enfin compris comment les files marchent grâce à vous. Je vais quand même vous expliquez mon point de vue pour ça, si j'ai bien assimilé la notion.

Je dois donc faire une file d'attente de client qui doit comptabiliser le nombre de clients exaspéré (sur le nombre de client servis).

Donc pour cela, je crée mes deux structures

dans un fichier client.h, je mets

Code :

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

1
2
3
4
5
6
7
typedef struct client element;
 
struct client{
double tmpexas; //Temps que mettras le client a en avoir marre dans la file d'attente. Calculer aléatoirement par une fonction donnée par les profs.
double tmparrive //Je compare ici l'heure d'ouverture avec l'heure à laquelle le client est arrivée dans la fille.
element* next;
}

dans un fichier client.c

je crée la fonction uniform() //qui calcule le temps au bout duquel le client partira exaspéré

je crée une fonction qui initialise un client.

Code :

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

1
2
3
4
5
6
7
8
9
client init_client (){
client c;
c = malloc(sizeof(element));
double tmpexas = uniform();
double tmparrive = fonction(); // Je créerai une fonction qui fera la différence entre le temps actuel et l'heure d'ouverture du bureau de poste (en seconde)
element* next = ??; //Ici, je comprends que ça permet d'accéder au prochain élément mais, je ne sais pas quoi mettre lors de l'initialisation du client à part NULL :S
element* previous = ??; //idem
return c;
}

Ensuite, je crée une structure file dans mon file.h

Code :

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

1
2
3
4
5
6
7
8
 
struct file{
element first; //premier élément
int free; //indice de la première case (pour revenir au début)
int taillemax; //nombre d'élément maximum (mais j'aimerai bien avoir un nombre indéterminée...
int nbclient; //nombre de client présent dans la file
element donnee; //Quand on initialise la file, il faut faire malloc(sizeof(element)*nbclient);
}

Enfin avec ce que, je pense que vous pouvez voir où j'en suis au niveau de mon interprétation. Je crois que j'ai encore bien du mal à comprendre.