La mise en œuvre Liste Passer en C ++

Question

[RESOLU]

Alors j'ai décidé d'essayer de créer une liste de saut doublement chaînée trié ...

Je suis assez sûr que j'ai une bonne compréhension de la façon dont cela fonctionne. Lorsque vous insérez x le programme recherche la liste de base pour l'endroit approprié pour mettre x (puisqu'il est trié), (conceptuellement) flips une pièce de monnaie, et si les terres de « monnaie » sur un alors cet élément est ajouté à la liste au-dessus (ou une nouvelle liste est créée avec un élément en elle), lié à l'élément ci-dessous, et la pièce est retournée à nouveau, etc. Si les terres de « pièces » sur b à tout moment alors l'insertion est terminée. Vous devez également avoir un -infini stocké dans chaque liste comme point de départ afin qu'il ne soit pas possible d'insérer une valeur qui est inférieure au point de départ (ce qui signifie qu'elle n'a jamais pu être trouvée.)

Pour rechercher x, vous commencez par le « supérieur gauche » (la plus élevée liste de valeur la plus faible) et « passer à droite » à l'élément suivant. Si la valeur est inférieure à x que vous continuez à l'élément suivant, etc. jusqu'à ce que vous « allé trop loin » et la valeur est supérieure à x. Dans ce cas, vous revenez au dernier élément et descendre d'un niveau, en continuant cette chaîne jusqu'à ce que vous trouverez x ou x est jamais trouvé.

Pour supprimer x vous recherchez simplement x et de supprimer chaque fois qu'il apparaît dans les listes.

Pour l'instant, je vais simplement faire une liste de saut que les numéros de magasins. Je ne pense pas qu'il y ait quoi que ce soit dans la STL qui peut me aider, donc je dois créer une liste de classe qui détient une valeur entière et a des fonctions membres, rechercher, supprimer et insérer.

Le problème que je vais avoir fait face à des liens. Je suis sûr que je pourrais créer une classe pour gérer les liens « horizontaux » avec un pointeur vers l'élément précédent et l'élément en avant, mais je ne suis pas sûr de savoir comment traiter les liens « verticaux » (point à l'élément correspondant dans une autre liste?)

Si l'une de ma logique est erronée s'il vous plaît me dire, mais mes questions principales sont:

1. Comment traiter avec des liens verticaux et si mon idée de lien est correct
2. Maintenant que je lis mon idée de liste de classe Je pense qu'une liste devrait tenir un vecteur d'entiers plutôt qu'un seul entier. En fait, je suis assez positif, mais il tout comme certains validation.
3. Je suppose que le coin flip serait tout simplement appeler la fonction int où rand ()% 2 retourne une valeur de 0 ou 1 et si elle est 0 alors la valeur « niveaux » et si elle est 0 alors l'insert est terminée. Est-ce incorrect?
4. Comment stocker une valeur similaire à -infini?

Edit: J'ai commencé à écrire un code et je considérais comment gérer le constructeur de la liste .... Je devine que sur sa construction, la valeur « -infini » doit être stocké dans l'élément NomVecteur [0] et je peux simplement appeler insert sur elle après sa création à mettre x à l'endroit approprié.

Answer 1

1. Il suffit de stocker 2 pointeurs. Un appelé ci-dessus, et un autre appelé ci-dessous dans votre classe de nœud.
2. Je ne sais pas ce que vous voulez dire.
3. Selon wikipedia vous pouvez également faire une distribution géométrique. Je ne sais pas si le type de questions de distribution pour un accès totalement aléatoire, mais il importe évidemment, si vous savez que votre modèle d'accès.
4. Je ne suis pas sûr de ce que vous entendez par là. Vous pouvez représenter quelque chose comme ça avec des nombres à virgule flottante.

Answer 2

http://msdn.microsoft. com / fr-fr / bibliothèque / ms379573 (VS.80) .aspx # datastructures20_4_topic4

http://igoro.com/archive/skip-lists-are- fascinant /

Les listes de saut ci-dessus sont mises en œuvre en C #, mais peut élaborer un c ++ en utilisant la mise en œuvre de ce code.

Answer 3

Vous faites « verticale » et « horizontale » trop compliqué. Ils sont tous seulement des pointeurs. Les petites boîtes vous dessiner sur du papier avec des lignes sur eux sont juste pour aider à visualiser quelque chose en pensant à eux. Vous pouvez appeler un pointeur « éléphant » et il serait aller au noeud suivant si vous le voulais.

par exemple. un pointeur « suivant » et « prev » sont exactement les mêmes en tant que pointeur « au-dessus » / « ci-dessous ».

Quoi qu'il en soit, bonne chance avec vos devoirs. Je suis le même devoirs une fois dans ma classe des structures de données.