La implementación de la lista Saltar en C ++

Question

[SOLVED]

Así que decidí probar y crear una lista doblemente enlazada salto ordenados ...

Estoy bastante seguro de que tengo una buena comprensión de cómo funciona. Al insertar x el programa busca en la lista de base para el lugar apropiado para poner x (ya que está ordenada), (conceptualmente) lanza una moneda, y si las tierras "monedas" en una continuación de ese elemento se añade a la lista anterior se (o una nueva lista se crea con el elemento en él), vinculada al elemento por debajo de ella, y la moneda se voltea de nuevo, etc. Si las tierras de "moneda" en b en cualquier momento luego de la inserción ha terminado. También debe tener un -infinito almacenada en cada lista como punto de partida por lo que no es posible insertar un valor que es menor que el punto de partida (lo que significa que no se pudo encontrar.)

Para buscar x, se inicia en el "top-izquierda" (lista de más alto valor más bajo) y "mover hacia la derecha" al siguiente elemento. Si el valor es menor que x que de continuar con el siguiente elemento, etc. hasta que haya "ido demasiado lejos" y el valor es mayor que x. En este caso, volver al último elemento y se mueven a un nivel inferior, continuando esta cadena hasta que usted encuentre xo x nunca se encuentra.

Para eliminar x que x, simplemente, buscar y borrar cada vez que aparece en las listas.

Por ahora, simplemente voy a hacer una lista de salto que almacena números. No creo que haya nada en el STL que me puede ayudar, por lo que tendrá que crear una lista de clase que contiene un valor entero y tiene funciones miembro, buscar, eliminar e insertar.

El problema que estoy teniendo es tratar con los enlaces. Estoy bastante seguro de que podría crear una clase para manejar los vínculos "horizontales" con un puntero al elemento anterior y el elemento de delante, pero no estoy seguro de cómo hacer frente a los enlaces "verticales" (punto de elemento correspondiente en otra lista?)

Si cualquiera de mi lógica es defectuosa por favor dígame, pero mis principales preguntas son:

1. ¿Cómo lidiar con enlaces verticales y si mi idea es correcta enlace
2. Ahora que leo mi idea de la clase Lista estoy pensando que una lista debe contener un vector de enteros en lugar de un único entero. De hecho estoy bastante positivo, sino que al igual que algunos de validación.
3. Asumo el tirón de la moneda sería simplemente llamar a la función int donde rand ()% 2 devuelve un valor de 0 ó 1, y si es 0, entonces A El valor "niveles" y si es 0, entonces el inserto ha terminado. Es esta incorrecto?
4. ¿Cómo almacenar un valor similar al -infinito?

Edit: He empezado a escribir algo de código y estoy considerando cómo manejar el constructor Lista .... supongo que en su construcción, el valor "-infinito" se debe almacenar en el vectorname elemento [0] y yo sólo puedo llamar inserto en él después de su creación a poner la X en el lugar apropiado.

Answer 1

1. Sólo almacenar 2 punteros. Una llamada anterior, y uno llamado más adelante en la clase de nodo.
2. No está seguro de lo que quiere decir.
3. Wikipedia también se puede hacer una distribución geométrica. No estoy seguro de si el tipo de cuestiones de distribución para el acceso totalmente al azar, pero es evidente que importa si sabe que su patrón de acceso.
4. No estoy seguro de lo que quiere decir con esto. Puede representar algo así con números de punto flotante.

Answer 2

http://msdn.microsoft. com / es-es / library / ms379573 (VS.80) .aspx # datastructures20_4_topic4

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

Las listas de salto anteriores se implementan en C #, pero puede llegar a un ++ aplicación c usando ese código.

Answer 3

Usted está haciendo "vertical" y "horizontal" demasiado complicado. Todos ellos son sólo los punteros. Las pequeñas cajas que se dibujan en papel con líneas en ellos son sólo para ayudar a visualizar algo cuando pensando en ellos. Se le podría llamar un puntero "elefante" y sería ir al siguiente nodo si quería.

por ejemplo. un "siguiente" y el puntero "prev" son exactamente el mismo como un puntero "arriba" / "abajo".

De todos modos, buena suerte con su tarea. Tengo la misma tarea una vez en mi clase de estructuras de datos.