Gérer une liste dynamique de clients

Bonjour,

Je cherche à gérer une liste de clients dans un tableau dynamique.
La liste des clients se trouve dans un fichier texte, j’ai donc pensé à quelque chose comme :

typedef struct Client
{
    unsigned int id;
    unsigned int points;    // Nombre de points sur sa carte client

} client;

// On initialise un tableau vide (compilation échoue ici)
client clients[0];

// Fonction qui remplit ce tableau avec les données provenant du fichier "clients.txt"
fillClients(&clients);

C’est un premier jet mais j’ai l’impression de partir du mauvais pied… Comment gérer ce problème ?
Une librairie standard permettrait-elle de facilement gérer des tableaux dynamiques ?

Salut,

Si le tableau n’est pas une structure obligatoire, je t’invite plutôt à te tourner vers une liste chaînée (j’en parle un peu dans le tuto C là-bas), cela traduirait à mon sens mieux ce que tu cherches à obtenir (à savoir une liste). Si tu restes sur l’idée du tableau dynamique, c’est expliqué dans le tuto C également.

@Taurre je ne suis pas convaincu par la pertinence de la liste chainée : ça donne une complexité en O(n) pour récupérer un élément…

@OP: Pour le tableau, si tu veux le faire à la main, tu peux partir sur un tableau de taille fixe, et réallouer (doubler la taille par exemple) si tu as besoin de plus d’éléments.

@Taurre je ne suis pas convaincu par la pertinence de la liste chainée : ça donne une complexité en O(n) pour récupérer un élément…

En toute franchise, si l’ID n’est pas corrélé à l’indice alors on va faire une recherche d’une utilisateur plutôt qu’un accès. Donc même dans un tableau ce sera du $O(n)$.

Sinon, il faut absolument que tu étudies l’allocation dynamique pour pouvoir en faire
Le cours de C est très bien pour ça.

Note, les tableaux de taille 0 n’ont pas d’intéret généralement et rien de portable.

Intéressant comme approche la liste chaînée, mais j’ai l’impression que c’est très lourd et compliqué à mettre en place pour arriver au comportement attendu. Existe-t-il un équivalent de ArrayList<> (de Java) en C grâce à la bibliothèque standard ?

Pour le tableau dynamique, je ne connais pas la taille du tableau ni à la compilation NI à l’exécution, puisque je parcours un fichier jusqu’à EOF et le tableau se remplit au fur et à mesure.

Alors là ça me semble impossible en C de faire un tableau de taille fixe, puis de le prolonger, aurais-tu un exemple ?

L’allocation dynamique avec malloc je comprends, mais on retombe alors sur les listes chaînées.
Ce qui serait bien, c’est de partir d’un tableau vide et de le remplir au fur et à mesure. Mais si c’est pas possible, alors je partirai sur une liste chaînée.

En simplifiant, le C te donne le minimum :

• ce dont tu connais la taille à la compilation (nombres sur X bits, tableaux de longueur fixe) qui seront mis dans la pile (stack).
• de quoi demander de mettre des trucs sur le tas (heap) pendant l’exécution parce qu’on ne pouvait pas connaître la taille exacte à l’avance.

Et puis voilà.
Tu veux un truc qui grossit ? Tu connais des structures de données pour tricher (la liste chaînée par exemple) ou tu redemande un peu de mémoire à chaque fois.

Je pense que ce que voulais dire FantasMath c’est de faire une allocation dynamique d’une certaine taille N et plutôt que de demander une case de mémoire supplémentaire à chaque fois tu en demandes N de plus. Ça évite de faire trop d’aller-retour avec ton OS pour lui demander de la mémoire.

Si le tableau n’est pas une structure obligatoire, je t’invite plutôt à te tourner vers une liste chaînée (j’en parle un peu dans le tuto C là-bas), cela traduirait à mon sens mieux ce que tu cherches à obtenir (à savoir une liste). Si tu restes sur l’idée du tableau dynamique, c’est expliqué dans le tuto C également.

Intéressant comme approche la liste chaînée, mais j’ai l’impression que c’est très lourd et compliqué à mettre en place pour arriver au comportement attendu. Existe-t-il un équivalent de ArrayList<> (de Java) en C grâce à la bibliothèque standard ?

Ben tout dépend du comportement attendu x)
Dans la lib standard du C, non il n’y a pas de structure de donné type ArrayList. Mais tu peux très bien la codé toi même !

Pour le tableau dynamique, je ne connais pas la taille du tableau ni à la compilation NI à l’exécution, puisque je parcours un fichier jusqu’à EOF et le tableau se remplit au fur et à mesure.

Alors, tu connais forcément la taille au run-time. Pour les tableaux dynamique, on différencie la contenance et la taille.
La contenance tu la gères comme tu veux (généralement au double la contenance à chaque fois).

Tu veux un truc qui grossit ?

😏😏

L’allocation dynamique avec malloc je comprends, mais on retombe alors sur les listes chaînées.
Ce qui serait bien, c’est de partir d’un tableau vide et de le remplir au fur et à mesure. Mais si c’est pas possible, alors je partirai sur une liste chaînée.

Pas vraiment, la liste chaînées, c’est vraiment une structure de donée différente du tableau. Pareil, tu gères la contenance comme la taille. D’ailleurs tu peux utilisé un tableau dynamique pour implémenter une liste chaînée (même si c’est certainement pas optimal).

Que trouves-tu lourd et/ou compliqué dans l’emploie d’une liste chaînée ? Pour te donner un exemple qui lirait le contenu d’un fichier CSV (id,points), cela se limiterait à ça.

#include <stdio.h>
#include <stdlib.h>

struct client {
    unsigned id;
    unsigned points;
    struct client *next;
};

static struct client *client_create(unsigned, unsigned);
static struct client *read_clients_from_file(FILE *fp);


static struct client *
client_create(unsigned id, unsigned points)
{
    struct client *self = malloc(sizeof *self);

    if (self == NULL) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }

    self->id =id;
    self->points = points;
    self->next = NULL;
    return self;
}


static struct client *
read_clients_from_file(FILE *fp)
{
    struct client head = { 0, 0, NULL };
    struct client *clients = &head;
    unsigned id, points;

    while (fscanf(fp, "%u,%u", &id, &points) == 2) {
        struct client *new = client_create(id, points);
        clients->next = new;
        clients = clients->next;
    }

    if (ferror(fp)) {
        perror("fscanf");
        exit(EXIT_FAILURE);
    }

    return head.next;
}


int
main(void)
{
    FILE *fp = fopen("clients.csv", "r");

    if (fp == NULL) {
        perror("fopen");
        exit(EXIT_FAILURE);
    }

    struct client *client = read_clients_from_file(fp);
    fclose(fp);

    while (client != NULL) {
        printf("id = %u, points = %u\n", client->id, client->points);
        client = client->next;
    }

    return EXIT_SUCCESS;
}

Une solution équivalente avec un tableau dont on augmente la taille progressivement (à l’aide de la fonction realloc) ne serait pas spécialement plus simple, au contraire.

Je suis tout à fait d’accord sur le fait que ce n’est pas la solution la plus optimale en termes de complexité algorithmique, mais je pense que ce n’est pas le propos. Il s’agit d’un exercice pour un débutant en C, le nombre d’éléments à traiter est sans aucun doute insuffisant pour voir une différence quel que soit l’algorithme employé (y compris ceux avec une complexité quadratique, ce qui n’est pas le cas ici).

Alors là ça me semble impossible en C de faire un tableau de taille fixe, puis de le prolonger, aurais-tu un exemple ?

L’idée est de malloc un tableau, et s’il est trop petit à un moment donné, tu peux le realloc pour qu’il devienne plus grand !

Dans tous les cas, tu peux tester différentes implémentations, c’est un bon exercice pour se faire la main avec la gestion de la mémoire en C ;).

Puisqu’on est sur les structures de données, pourquoi ne pas utiliser une table de hachage plutôt ? Accès en O(1)

Ce qui serait bien, c’est de partir d’un tableau vide et de le remplir au fur et à mesure.

C’est justement un ArrayList. Tu peux le recoder comme le dit ache, c’est pas très compliqué.

Puisqu’on est sur les structures de données, pourquoi ne pas utiliser une table de hachage plutôt ? Accès en O(1)

Bonne idée (d’autant plus que si tu débute avec le tuto de zds, ça te permettra d’aller voir plus loin)

En revanche, ça veut dire allouer toute la mémoire pour contenir toutes les images possibles de la fonction de hachage, non?

Existe-t-il un équivalent de ArrayList<> (de Java) en C grâce à la bibliothèque standard ?

Ca existe en C++ (voir std::vector<T>). Mais en C, non, ça n’existe pas. Le C, c’est primitif.

Puisqu’on est sur les structures de données, pourquoi ne pas utiliser une table de hachage plutôt ? Accès en O(1)

Mauvaise idée. AVant de pouvoir faire une table de hachage, il faut déjà maîtriser les tableaux dynamiques. Tu en as forcément besoin pour faire la construction de base. Donc c’est un niveau au-dessus en terme de difficulté.

En revanche, ça veut dire allouer toute la mémoire pour contenir toutes les images possibles de la fonction de hachage, non?

Bien sûr que non. Le principe de base est que l’index du tableau où un élément donné est stocké est donné par le hash de cet élément modulo la taille du tableau.

Par contre, je ne comprends pas pourquoi on s’évertue à recommander les listes chaînées plutôt que les tableaux dynamiques en C. C’est un excellent exercice, certes; mais mis à part ça, c’est pourri en performances, pourri en occupation mémoire, et c’est plus compliqué à gérer. En C++ des gens on benchmarké std::vector<T> vs std::list<T> et à moins d’avoir un grand nombre d’éléments et d’effectivement faire presque exclusivement des opérations coûteuses sur les vector, c’est à peu près toujours vector qui gagne. En C vu qu’il n’y a pas de structures standard nos versions home-made promettent d’être encore pire.

De mon point de vue, la liste chaînée est une structure plus « naturelle » pour gérer une liste de clients, c’est pour cette raison que je la suggère. C’est de mon point de vue plus intuitif et plus simple d’ajouter une entrée à une liste au fur et à mesure que de gérer les allocations successives d’un tableau.

D’ailleurs, tant qu’on y est, voici le même programme, mais avec un tableau dynamique.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

struct client {
    unsigned id;
    unsigned points;
};


struct clients {
    struct client *client;
    size_t lim;
    size_t size;
};

static struct clients *array_create(size_t);
static void array_resize(struct clients *);
static void read_clients_from_file(struct clients *, FILE *fp);


static struct clients *
array_create(size_t lim)
{
    assert(lim > 0);
    assert(SIZE_MAX / sizeof(struct client) > lim);

    struct clients *self = malloc(sizeof *self);

    if (self == NULL) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }

    self->client = malloc(sizeof *self->client * lim);

    if (self->client == NULL) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }

    self->lim = lim;
    self->size = 0;
    return self;
}


static void
array_resize(struct clients *self)
{
    assert(SIZE_MAX / 2 > self->lim);
    assert(SIZE_MAX / sizeof *self->client > (self->lim << 1));

    void *tmp = realloc(self->client, sizeof *self->client * (self->lim << 1));

    if (tmp == NULL) {
        perror("realloc");
        exit(EXIT_FAILURE);
    }

    self->client = tmp;
    self->lim <<= 1;
}


static void
read_clients_from_file(struct clients *clients, FILE *fp)
{
    unsigned id, points;

    for (size_t i = 0; fscanf(fp, "%u,%u", &id, &points) == 2; ++i) {
        if (clients->lim == clients->size)
            array_resize(clients);

        clients->client[i].id = id;
        clients->client[i].points = points;
        clients->size++;
    }

    if (ferror(fp)) {
        perror("fscanf");
        exit(EXIT_FAILURE);
    }
}


int
main(void)
{
    FILE *fp = fopen("clients.csv", "r");

    if (fp == NULL) {
        perror("fopen");
        exit(EXIT_FAILURE);
    }

    struct clients *clients = array_create(256U);
    read_clients_from_file(clients, fp);
    fclose(fp);

    for (size_t i = 0; i < clients->size; ++i)
        printf("id = %u, points = %u\n", clients->client[i].id, clients->client[i].points);

    return EXIT_SUCCESS;
}

Franchement, des deux exemples, je préfère largement suggérer une liste chaînée à un débutant par rapport à un tableau dynamique. Un tableau dynamique nécessite une gestion plus complexe de la mémoire (le mauvais usage de realloc()et fréquent et pas que pour les débutants) et nécessite de vérifier les dépassements de capacités (du tableau lui-même et des opérations mathématiques lors du changement de taille).

Ensuite, « pourri en occupation mémoire », je suppose que tu fais référence au fait que la liste chaînée peut induire une fragmentation de la mémoire à l’inverse du tableau qui utilise un bloc contigu ? Si oui, c’est pas un problème pour le programmeur, mais pour l’OS. Par ailleurs, cela a ses avantages aussi, parce que trouver un gros bloc contigu libre peut s’avérer difficile à l’inverse d’un petit bloc pour un nœud.

Enfin, honnêtement, je trouve l’argument des performances dans le cadre d’un exercice de débutant totalement non pertinent. Quand bien même il s’amuserait à trier sa liste avec un tri à bulle coder avec des moufles, s’il y a 256 entrées, on ne verra aucune différence à l’exécution par rapport à un tri fusion par exemple. Je veux dire, c’est sympa de se soucier des performances, mais à un moment donner il faut également garder le but et l’usage du programme à l’esprit.

Allez, on met tout le monde d’accord ? On lit le fichier pour compter le nombre de lignes, un seul malloc et on relit le fichier ?

Bof.

Merci pour vos conseils !

Pour un peu contextualiser, le projet est dans un cadre purement académique pour l’apprentissage des notions en C, par ailleurs les questions de performances et de mémoire ne sont pas à envisager pour l’instant.

Pour résumer le sujet, j’en retiens qu’il n’existe pas d’équivalent dans la librairie standard C d’un ArrayList. Par conséquent, il me reste deux choix :

1. Soit implémenter une liste chaînée. C’est peut-être ce qu’il y a de plus simple à mon niveau, en espérant que cela ne donne pas un code trop moche.
2. Soit un tableau dynamique, en utilisant realloc(). Sauf que rien ne me garantit que realloc fonctionnera pour toutes les lignes du fichier (~2000 lignes, une ligne par client, donc la fonctionne realloc va faire beaucoup d’aller-retour sur la mémoire).

Je choisis la première option qui me semble la plus adaptée et la plus logique pour ce cas-ci.

Je n’ai pas d’argument contre cette solution, pourtant elle me semble être contraire aux bonnes pratiques. J’y avait pensé. Je pense que cette solution gaspille les ressources, car elle doit lire deux fois le fichier.

PS : les tables de hashage, ça ne me parle absolument pas.

Je n’ai pas d’argument contre cette solution, pourtant elle me semble être contraire aux bonnes pratiques. J’y avait pensé. Je pense que cette solution gaspille les ressources, car elle doit lire deux fois le fichier.

En vrai pas vraiment car les systèmes d’exploitation gardent un cache des fichiers récemment ouverts (ou liés à ceux actuellement ouverts) pour améliorer les perfs. Donc deux lectures consécutives d’un même fichier n’est pas vraiment un gaspillage en ressource et est très indolore dans ton cas de figure.

Et en l’occurrence, les perfs dans ton exercice tu t’en fiches. Il n’y a pas de mauvaises solutions, trouve juste ce qui est le plus simple pour toi.

PS : les tables de hashage, ça ne me parle absolument pas.

info-matique

En gros le principe, c’est de retrouver facilement une série de données grâce au hache de celles-ci:

Dans le cas des tableaux en c, il va s’agir de stocker une donnée dans le tableau à l’indice donné par son hash. Je te conseil ce tuto qui explique ça mieux que moi.

Chouette tuto, merci j’ai appris un petit truc en plus en C !