Qu'est ce qu'un Curseur Lié Liste? [C++]
Mon professeur m'a fourni avec un fichier appelé CursorList.cpp qui met en œuvre un "Curseur de la Liste Liée". Le problème est que je n'ai aucune idée de ce que c'est!
Quelqu'un pourrait-il me donner l'essentiel, c'?
Merci!
yuval, vous devriez probablement commencer par voir ce que l'interface le fichier a exposés. C'est, de lire, de regarder ce que les méthodes y sont, comment les utiliser, etc. À partir du nom, il semble assez certain qu'il met en œuvre une liste liée structure de données, c'est à dire celui qui vous permet d'effectuer des insertions, suppressions, transversal, ce genre de chose. De la tester.
OriginalL'auteur Yuval Karmi | 2010-04-07
Vous devez vous connecter pour publier un commentaire.
Selon cette, voici quelques informations générales sur un curseur linkedlist:
Donc, fondamentalement, une liste, qui est mise en œuvre sans l'aide de pointeurs. Peut-être que cette mise en œuvre est censé être "plus facile" à comprendre?
en.wikipedia.org/wiki/Linked_list
OriginalL'auteur Justin Ethier
J'imagine que c'est un liste liée qui, en outre, conserve un pointeur vers un "courant" de l'élément, par exemple pour itérer sur la liste.
Si vous voulez être sûr de ce que exactement à votre professeur dire, regardez-le .fichier cpp et de trouver ce qui est mis en œuvre.
OriginalL'auteur sth
Un CursorList est un tableau version d'une Liste chaînée. Essentiellement, vous avez un tableau de la liste des nœuds, mais au lieu de chaque nœud contient un pointeur vers l'élément suivant de la liste liée, chaque nœud de l'élément dans le tableau contient l'indice pour le prochain élément de nœud. Ainsi par exemple, si nous voulions stocker
5, 3, 2, 11, 9
dans une liste, nous aurions5 -> 3 -> 2 -> 11 -> 9 -> NULL
. L'insertion n'est pas un problème que nous venons de changer le dernier pointeur sur le nœud inséré et ont inséré le point de nœud àNULL
. La suppression est la même, nous venons de réajuster les pointeurs. Cependant, ayant toujours allouer dynamiquement (à l'aide de malloc ou nouveaux) de mémoire pour un nouveau nœud pourrait être problématique.Si nous stocker dans un CursorList, nous avons d'abord déclarer la taille maximale de la matrice, puis de le remplir. Donc, nous disons
listNode cursorList[10]
où nous déclarons une listNode objet comme suit:donc, après avoir rempli le tableau avec listNode objets que nous aurons quelque chose qui ressemble à ceci:
maintenant, si nous voulons supprimer 5 tout ce que nous avons à faire est de mettre à jour le
next
index. Donc on se retrouve avec ceci:Une question se pose, comment savons-nous ce que pour définir 5
next
index? Eh bien, c'est où la Freelist (mentionné dans @Justin Ethier du repsonse). La Freelist contient les indices qui sont toujours libres dans le tableau. Donc, lors de la création de la CursorList, la Freelist a 0-9. Comme listNode les objets sont assignés aux éléments de la matrice, la Freelist supprime ces indices. Lorsqu'un numéro est supprimé (comme l'exemple 5 ci-dessus), l'index est ajouté à la Freelist. Si nous voulons ajouter un numéro à la CursorList nous venons de mettre à jour lenext
indices pour les éléments appropriés.OriginalL'auteur sbru
Dans le curseur de mise en œuvre, nous construisons le stockage
la piscine nous-mêmes, le stockage de nos nœuds inutilisés dans un
liste liée stockées dans un tableau.
En C et C++, le pool de stockage est géré par un ensemble de
bibliothèque de fonctions fournies par la langue.
Au début de l'exécution, une assez grande piscine de stockage est
obtenu à partir du système d'exploitation.
Lorsqu'un programme demande un nouveau nœud de stockage est obtenu à partir de la
piscine par un langage de fonction de bibliothèque.
En cas d'insuffisance de stockage est disponible dans la piscine, la bibliothèque demandes
supplémentaire de la piscine de l'espace sur le système d'exploitation.
Lorsque le stockage est libéré par un programme, une langue ou une fonction de la bibliothèque
il retourne dans le pool de stockage.
Le curseur de la mise en œuvre sera normalement obtenir un fixe
quantité de stockage de l'ordinateur comme un tableau, et
offrent des fonctions similaires à new et delete pour un
programme d'application pour l'utilisation
OriginalL'auteur Kokul Jose