[SOLUCIONADO]de aplicación Lista Saltar en C++
así que decidí tratar de crear una lista doblemente enlazada salto ordenados ...
Estoy bastante seguro de que tengo una buena comprensión de cómo funciona. Cuando inserta x el programa busca en la lista base el lugar apropiado para poner x (ya que está ordenado), (conceptualmente) arroja una moneda, y si la "moneda" cae en a, entonces ese elemento se agrega a la lista que está arriba (o una nueva lista se crea con un elemento en ella), vinculada al elemento debajo de ella, y la moneda se voltea de nuevo, etc. Si la "moneda" cae sobre b en cualquier momento, entonces la inserción ha terminado. También debe tener un -infinite almacenado en cada lista como punto de partida para que no sea posible insertar un valor que sea inferior al punto de inicio (lo que significa que nunca podría encontrarse).
Para buscar x, comienza en "arriba a la izquierda" (el valor más bajo en la lista más alta) y "mueve a la derecha" en el siguiente elemento. Si el valor es menor que x, continúe con el siguiente elemento, etc. hasta que haya "ido demasiado lejos" y el valor sea mayor que x. En este caso, vuelve al último elemento y baja un nivel, continuando con esta cadena hasta que encuentres x o x nunca se encuentre.
Para eliminar x simplemente busque x y elimínelo cada vez que aparece en las listas.
Por ahora, simplemente voy a hacer una lista de saltos que almacena números. No creo que haya nada en el STL que pueda ayudarme, así que tendré que crear una lista de clase que contenga un valor entero y tenga funciones de miembro, busque, elimine e inserte.
El problema que tengo es el manejo de enlaces. Estoy bastante seguro de poder crear una clase para manejar los enlaces "horizontales" con un puntero al elemento anterior y el elemento de frente, pero no estoy seguro de cómo tratar con los enlaces "verticales" (señalar el elemento correspondiente) ? en otra lista)
Si cualquiera de mi lógica es defectuosa por favor dígame, pero mis principales preguntas son:
- ¿Cómo lidiar con enlaces verticales y si mi idea enlace es correcto
- Ahora que Leí mi idea de lista de clase. Estoy pensando que una lista debe contener un vector de números enteros en lugar de un solo entero. De hecho, soy bastante positivo, pero me gustaría algo de validación.
- Supongo que la moneda bastará con llamar a la función int donde rand()% 2 devuelve un valor de 0 o 1 y si es 0, entonces el valor "sube de nivel" y si es 0, la inserción finaliza. ¿Es esto incorrecto?
- ¿Cómo almacenar un valor similar a -infinito?
Editar: He comenzado a escribir algunos códigos y estoy considerando cómo manejar el constructor List ... Supongo que en su construcción, el valor "-infinite" debe almacenarse en el nombre del vector [ 0] elemento y puedo simplemente llamar a insertar después de su creación para poner la x en el lugar apropiado.
Para 2 me refiero a cómo lidiar con el almacenamiento de datos real. Supongo que List debe tener un miembro privado: vector números que contiene los números insertados. Para 4, supongo que debería ser el valor entero más bajo posible. –
trikker
Para 2, necesita almacenar un puntero a lo que quiere almacenar como * char o * int o * MyClass, etc ... Para 4, no hay manera de hacer eso con enteros regulares, debe implementar el suyo o usar puntos flotantes – Unknown
¿Por qué debería contener un vector? Cada nodo en la lista debe almacenar un número entero. Puede usar std :: numeric_limits :: min() para -infinity, pero le recomiendo hacer del nodo principal un caso especial. –
Geerad