Salut à tous !
Je souhaite implémenter le type file par un tableau dynamique, mais je ne vois pas comment m'y prendre.
A mon humble avis, dans ce cas, le type file ne doit dépendre que du nombre d'élément(s), en effet alors la file sera un tableau de capacité ce nombre d'élément(s). Et je pourrais faire ça dans le main, mais j'aimerais le faire sous forme de structure.
Qu'en dite vous ?
Pourquoi aurais tu besoin d'un tableau ?
Pourquoi ne pas faire une liste chainée, c'est à dire une structure qui contient les données et un pointeur sur le même type, l'élément suivant ?
Ceci en supposant que j'ai bien compris ce que tu entends par file.
Je suppose qu'il veut parler d'une "queue".Envoyé par pm42
Je voulais dire le type pile.
Oui je vais le faire avec une liste chaînée cet après midi, mais tout de même j'ai lu que c'était possible de le faire avec un tableau dynamique donc je suis curieux de savoir ce que ça donne ! Et personnellement je ne vois pas comment faire.
Comme le dit PM42, un tableau dynamique est ici de peu d’intérêt.
Il te faut a priori, une liste chaînée et deux fonctions d"enqueue" et "dequeue".
Je ne sais pas ce qu'on appelle un tableau dynamique en C. Un Vecteur ? Le langage se prête moins à la définition de ce genre de structure de données que le C++ ou équivalent.
C'est à dire l'inverse de la file (queue).
La pile est en LIFO
La file (queue) est en FIFO.
Vecteur n'existe pas en C, à ma connaissance.
Oui mais je me demandais si c'était le même concept ou si Cech avait lu cela dans un truc général indépendant du langage.
Parce que j'ai du mal à voir d'où vient le tableau dynamique dans cette histoire.
Je suppose que ça doit être un pattern particulier de programmation.
Tiens, je n'avais pas regardé de C depuis une vingtaine d'année et j'avais 10mn à perdre.
Voici un exemple de liste chaînée utilisable ou en "stack" ou en "queue" (à améliorer) :
Code:struct tListEntry { void * item; tListEntry * closestEntry; }; struct tVersatileList { int listType; tListEntry * root; tListEntry * current; }; // 0 => Queue; 1 ==> Stack. tVersatileList * createList(int type) { if (type != 0 && type != 1) return NULL; tVersatileList * newList = (tVersatileList *)malloc(sizeof(tVersatileList)); newList->listType = type; newList->current = NULL; newList->root = NULL; return newList; } void insert(tVersatileList * list, void * item) { tListEntry * newEntry = (tListEntry *)malloc(sizeof(tListEntry)); newEntry->item = item; newEntry->closestEntry = 0; if (list->current == NULL) { list->root = newEntry; list->current = newEntry; } else { if (list->listType == 0) { list->root->closestEntry = newEntry; list->root = newEntry; } else { newEntry->closestEntry = list->current; list->current = newEntry; } } } void * get(tVersatileList * list) { if (list->current == NULL) return NULL; // list Empty; void * item = list->current->item; tListEntry * entryToRemove = list->current; list->current = list->current->closestEntry; free(entryToRemove); return item; }
Oui une pile "stack" c'est possible en C mais un Tableau dynamique n'a pas d'intérêt.
Car quand ta pile est pleine et que tu veux l'agrandir alors tu doit refaire un malloc ( fonction qui prend beaucoup de temps au système car il doit trouver de la placer contiguë en mémoire)
Alors qu'avec une liste chaîné tu ne fait que des malloc pour chaque maillon de la chaîne et donc rapide à effectuer.
Si jamais tu veux le faire avec un Tableau dans tout les cas, un bon algo est de construire un Tableau de taille N au départ. Si ce tableau n'est plus assez grand alors tu en fait un nouveau 2x plus grand.
Non, ce n'est pas comme ça que fonctionne un malloc sur un système moderne à mémoire virtuelle. Au contraire même, malloc est conçu pour être très rapide.
Voir par exemple : http://voices.canonical.com/jussi.pa...s-malloc-slow/
Donc tu penses que faire des mallocs souvent pour des petites donnée est plus efficace que d'en faire moins souvent pour des données plus grandes alors que la fonction est supposée lente d'après toi.
Le fait de ne pas faire plein de petits mallocs a aussi pour avantage d'augmenter la localité des données et donc de diminuer le temps d'accès.
La croissance avec un facteur 2 risque de te faire atteindre des limites du système rapidement. Et te force à recopier ton tableau (sauf à utiliser realloc qui peut marcher parfois suivant les implémentations de malloc).
Déterminer le bon N initial est aussi un sujet en soi.
