Mon professeur m'a fourni un fichier appelé CursorList.cpp qui implémente une "Liste Liée au Curseur". Le problème est - je n'ai aucune idée de ce que c'est!Qu'est-ce qu'une liste liée au curseur? [C++]
Quelqu'un pourrait-il me donner l'essentiel?
Merci!
Selon this, voici quelques informations sur un curseur chaînée:
Donc, fondamentalement, une liste chaînée qui est implémentée sans utiliser de pointeurs. Peut-être que cette implémentation est censée être "plus facile" à comprendre?
Toujours pas très clair sur ce qu'ils sont. Pourrais-je alors étendre ma question et demander quelle est la liste utilisée dans ce contexte? Merci! –
http://en.wikipedia.org/wiki/Linked_list – stefanB
Je suppose que c'est un linked list qui garde en plus un pointeur sur un élément "en cours", par exemple pour l'itérer sur la liste.
Si vous voulez être sûr de ce que votre professeur entend par là, regardez le fichier .cpp et découvrez ce qui y est implémenté.
Cela correspond à mon souvenir de ce type d'objet ADT^H^H^H - liste + une position actuelle - retour dans ma classe de structures de données (années 80, hélas), avant que le mot ait été «volé» pour signifier (uniquement) et le tampon de jeu de résultats SQL – Roboprog
Une CursorList est une version matricielle d'une liste liée. Essentiellement, vous avez un tableau de noeuds de liste mais au lieu de chaque noeud contenant un pointeur vers l'élément suivant dans la liste chaînée, chaque élément de noeud dans le tableau contient l'index pour l'élément de noeud suivant. Donc, par exemple, si nous voulions stocker 5, 3, 2, 11, 9 dans une liste liée, nous aurions 5 -> 3 -> 2 -> 11 -> 9 -> NULL. L'insertion n'est pas un problème car il suffit de changer le dernier pointeur pour pointer sur le nœud inséré et faire pointer le nœud inséré sur NULL. La suppression est la même, nous réajustons simplement les pointeurs. Cependant, devoir toujours allouer dynamiquement (en utilisant malloc ou new) de la mémoire pour un nouveau nœud pourrait être problématique.
Si nous devions stocker dans un CursorList, nous déclarons d'abord la taille maximale du tableau, puis le remplissons. Nous disons donc listNode cursorList[10] où nous déclarons un objet ListNode comme suit:
class listNode {
public:
listNode() {
data = -1;
next = NULL;
}
listNode(int inputData, &listNode inputNext) {
data = inputData;
next = inputNext;
}
private:
int data;
listNode* next;
};
donc après avoir rempli le tableau avec des objets ListNode nous aurons quelque chose qui ressemble à ceci: 
maintenant si nous voulons éliminer 5 tous nous devons faire est de mettre à jour l'index next. Donc, nous sommes partis avec ceci: 
Une question se pose, comment savons-nous quoi mettre next index de 5? Eh bien, c'est là qu'intervient le Freelist (mentionné dans la réponse de @Justin Ethier). Le Freelist contient les index qui sont encore libres dans le tableau. Donc, lors de la création du CursorList, le Freelist a 0-9. Comme les objets listNode sont assignés aux éléments du tableau, le Freelist supprime ces index. Lorsqu'un nombre est supprimé (comme l'exemple avec 5 ci-dessus), l'index est ajouté à la liste de diffusion. Si nous voulons ajouter un nombre à la CursorList nous mettons juste à jour les indices next pour les éléments appropriés.
Dans la mise en œuvre du curseur, nous construisons nous-mêmes le stockage en stockant nos nœuds inutilisés dans une liste chaînée stockée dans un tableau.
En C et C++, le pool de stockage est géré par un ensemble de fonctions de bibliothèque fournies par le langage. Au début de l'exécution, un pool de stockage suffisamment grand est obtenu à partir du système d'exploitation. Lorsqu'un programme demande un nouveau nœud, le stockage est obtenu à partir du pool par une fonction de bibliothèque de langues. Si un espace de stockage insuffisant est disponible dans le pool, la bibliothèque demande espace de pool supplémentaire à partir du système d'exploitation. Lorsque le stockage est libéré par un programme, une fonction de bibliothèque de langue le renvoie dans le pool de stockage. La mise en œuvre du curseur normalement obtenir une quantité fixe de stockage du système comme un tableau, et fournir des fonctions similaires à nouveau et supprimer pour un programme d'application utiliser
Yuval, vous devriez probablement commencer par voir de quelle interface la fichier a exposé. C'est-à-dire, lisez-le, regardez quelles sont les méthodes publiques, comment les utiliser, etc. Du nom, il semble assez certain qu'il implémente une structure de données en liste chaînée, c'est-à-dire qui permet de faire des insertions, des suppressions, des traversées , ce genre de chose. Testez-le. –