Listas y punteros como los ordeno?

[delphi]

Buenos días a todos, en esta ocasión, vengo a pedirles su ayuda, ya que no logro comprender la lógica de reparar u ordenar esta lista que esta con 2 punteros, asi mismo también si es posible necesito que me expliquen como se lograría reparar u ordenar con un sólo puntero, adjunto unas imágenes para que me entiendan que es lo que necesito, comienzo:
En laIMAGEN 1 aparecen un monton de lineas que necesito eliminar para lograr llegar a la forma correcta o sea a la IMAGEN 2, lo que no entiendo como es que voy a ir quitando las lineas que estan enrredadas y dejarlas como la IMAGEN 2 y al final he agregado la salida que representaría en código como estaría correcta la lista. muchas gracias por sus aportes y ayuda

[delphi]

Empezado por delphi

Buenos días a todos, en esta ocasión, vengo a pedirles su ayuda, ya que no logro comprender la lógica de reparar u ordenar esta lista que esta con 2 punteros, asi mismo también si es posible necesito que me expliquen como se lograría reparar u ordenar con un sólo puntero, adjunto unas imágenes para que me entiendan que es lo que necesito, comienzo:
En laIMAGEN 1 aparecen un monton de lineas que necesito eliminar para lograr llegar a la forma correcta o sea a la IMAGEN 2, lo que no entiendo como es que voy a ir quitando las lineas que estan enrredadas y dejarlas como la IMAGEN 2 y al final he agregado la salida que representaría en código como estaría correcta la lista. muchas gracias por sus aportes y ayuda

IMAGEN 1


IMAGEN 2


IMAGEN 3

[Neftali [Germán.Estévez]]

Yo personalmente no he entendido bien lo que necesitas, ni las imágenes tampoco (debo estar un poco espeso).
No se si los demás estarán igual.

[Ñuño Martínez]

Yo tampoco lo entiendo bien, pero por el dibujo coligo que está hablando de listas doblemente enlazadas, ¿no? Y aunque fuera así, tampoco sé qué es lo que quiere hacer, exactamente...

[delphi]

ok, explicaré de otra forma:
La imagen 1, cuando la información está mal relacionada, un usuario puede optar a desfragmentar, entonces cae en la imagen 2, y de la imagen 2 el resultado en código de la desfragmentación que se ejecutó es la imagen 3, donde ya se enlazan correctamente, lo que necesito es saber como relacionar la información y para ello se hace dibujando las flechas paralelas en sentido contrario asi como la imagen 2, luego el código representa el orden luego de eliminar las líneas de la imagen 1, pero en sí lo que quiero saber es que me exliquen la lógica de llegar la la imagen 2, eso significaría llegar a quitar todo el desorden de la imagen 1...

[Neftali [Germán.Estévez]]

Empezado por delphi

pero en sí lo que quiero saber es que me exliquen la lógica de llegar la la imagen 2, eso significaría llegar a quitar todo el desorden de la imagen 1...

Eso es lo que no entiendo. Bueno entiendo lo que quieres, pero es que no veo relación entre las dos imágenes.

Es decir, en la imagen1, por ejemplo, (3) parece que tiene un puntero a (1), mientra que en la imagen2, (3) está relacionado con (2) y con (4).

El problema es que no entiendo cómo pasar de una imagen a la otra, Ahí no hay una simple ordenación, ahí se han cambiado más cosas. Los punteroos no apuntan a los mismos lugares, por lo tanto no entiendo la relación entre ambas imágenes. No parece que sea una simple ordenación, o yo al menos no la veo...

[delphi]

Empezado por Neftali

Eso es lo que no entiendo. Bueno entiendo lo que quieres, pero es que no veo relación entre las dos imágenes.

Es decir, en la imagen1, por ejemplo, (3) parece que tiene un puntero a (1), mientra que en la imagen2, (3) está relacionado con (2) y con (4).

El problema es que no entiendo cómo pasar de una imagen a la otra, Ahí no hay una simple ordenación, ahí se han cambiado más cosas. Los punteroos no apuntan a los mismos lugares, por lo tanto no entiendo la relación entre ambas imágenes. No parece que sea una simple ordenación, o yo al menos no la veo...

ahhhh es que o sea las imagenes que yo he puesto es de un ejemplo que tengo, pero en si el detalle es ¿cómo se resuelve ese tipo de problemas?, de tal forma que queden como la imagen 2, ya que la imagen 1 esta desordenado (es el problema a resolver), y el resultado es la imagen 2 junto con el código que hace referencia a la imagen 2, pero ¿cómo o cuales son los pasos para resolver este tipo de problemas con listas, punteros...etc

los punteros se pueden mover, porque algunas veces sólo existe un puntero, pero eso depende del problema, lo que necesito es eliminar las lineas desordenadas y dejarlas como la imagen 2

[rgstuamigo]

Yo más o menos entiendo lo que pretetendes hacer, pero la duda que tengo es, si se puede ordenarlos cambiando de posicion a los nodos?
Es decir hacer por ejemplo que el nodo de la posicion 3 (Que es P1) pueda llegar a tener la posision 1.
Dinos si vale mover la posicion de los nodos...

[[Delphius]]

Hola,

Intuyo que se trata de un práctico o trabajo para entregar en alguna cátedra o materia. Tus imágenes me hizo acordar a un TP de Lenguajes cuando vi el tema de punteros y TADs.

El ejercicio consistía en escribir las instrucciones necesarias para ir de un estado inicial (tu imagen 1) hacia un estado final (imagen 2). No necesariamente debíamos apegarnos a un lenguaje, aunque usamos la sintaxis de Pascal.
En ese entonces los ejercicios los hacíamos a mano y nos tomábamos toda la tarde, la noche e incluso en ocasiones la mañana para resolverlos... Nos daban de 20 a 50.

Vaya que han cambiado las cosas, ahora uno "consulta" pidiendo que les resuelvan el ejercicio y todo hace a computadora.

Respondiendo a tu duda: ¿Cómo se hace? Y... "jugando" con los punteros, intercambiandolos, empleando alguna variable auxiliar en caso de considerarse necesario. No hay un proceso único o manera de encarar el problema. Las instrucciones dependerán del problema, no hay método genérico... allí es donde radica lo lindo de esto

Debes guiarte por la forma en como están relacionados, y corregir los punteros. Lamentablemente deberás exprimir el cerebro.

Además, si te damos los pasos lo resolvemos nosotros... se supone que lo debes resolver vos.

Aquí algo que puedes tener como guía, desde un vistazo rápido a la imagen 1:

P2^A = P1
P2^S = P2
P1^S = P2

Ahorita está un poco más complicado:
Anterior^S^A = P1

La explicación es fácil de apreciar: Anterior^S (que se lee el puntero siguiente del nodo Anterior) apunta hacia el nodo 4º. Ahora el puntero anterior de éste va hacia el nodo 3º que corresponde a la variable P1.

De la imagen 2 vemos que P2 debe apuntar hacia P1, por lo que prematuramente podría resolverse esta parte con algo como:
P2^S = P1

Espero haber dado una idea. El resto es cerebral y lógica.

Saludos,

[delphi]

Empezado por Delphius

Hola,

Intuyo que se trata de un práctico o trabajo para entregar en alguna cátedra o materia. Tus imágenes me hizo acordar a un TP de Lenguajes cuando vi el tema de punteros y TADs.

El ejercicio consistía en escribir las instrucciones necesarias para ir de un estado inicial (tu imagen 1) hacia un estado final (imagen 2). No necesariamente debíamos apegarnos a un lenguaje, aunque usamos la sintaxis de Pascal.
En ese entonces los ejercicios los hacíamos a mano y nos tomábamos toda la tarde, la noche e incluso en ocasiones la mañana para resolverlos... Nos daban de 20 a 50.

Vaya que han cambiado las cosas, ahora uno "consulta" pidiendo que les resuelvan el ejercicio y todo hace a computadora.

Respondiendo a tu duda: ¿Cómo se hace? Y... "jugando" con los punteros, intercambiandolos, empleando alguna variable auxiliar en caso de considerarse necesario. No hay un proceso único o manera de encarar el problema. Las instrucciones dependerán del problema, no hay método genérico... allí es donde radica lo lindo de esto

Debes guiarte por la forma en como están relacionados, y corregir los punteros. Lamentablemente deberás exprimir el cerebro.

Además, si te damos los pasos lo resolvemos nosotros... se supone que lo debes resolver vos.

Aquí algo que puedes tener como guía, desde un vistazo rápido a la imagen 1:

P2^A = P1
P2^S = P2
P1^S = P2

Ahorita está un poco más complicado:
Anterior^S^A = P1

La explicación es fácil de apreciar: Anterior^S (que se lee el puntero siguiente del nodo Anterior) apunta hacia el nodo 4º. Ahora el puntero anterior de éste va hacia el nodo 3º que corresponde a la variable P1.

De la imagen 2 vemos que P2 debe apuntar hacia P1, por lo que prematuramente podría resolverse esta parte con algo como:
P2^S = P1

Espero haber dado una idea. El resto es cerebral y lógica.

Saludos,

en realidad el ejercicio que esta arriba como dije esta resuelto, lo que me interesa saber es como? dónde se comienza?, que debe de analizar primero para eliminar las líneas que estan desordenadas? para luego poder resolver el problema que sea siempre referente a esto...

[rgstuamigo]

Bueno analizandolo un poco más a fondo el problema veo que la cuestion no puede ser resuelta, ya que para poder resolverla por lo menos deberiamos tener un puntero o referencia que vaya de P1 o P2 hacia el nodo nro. 4 o tambien un tercer puntero(P3) que apunte al nodo 4.
El caso actual es que con P1 y P2 solo podemos movernos entre ellos mismo y no podemos salir de cualquiera de ellos ya sea al nodo nro 1 o nodo nro 4., por lo tanto estamos encerrados..
Saludos...

[ecfisa]

Hola delphi.

Según tu gráfico la lista erronea (a reparar) esta así:

p1.ant = nil (o indeterminado)
p1.sig = 2
p1.Dato = Img1

p2.ant = 3
p2.sig = 2
p2.Dato = Img2

p3.ant = nil (o indeterminado)
p3.sig = 2
p3.Dato = Img3

p4.ant = 3
p4.sig = 1
p4.Dato = Img4

Realmente no veo manera de organizar esos nodos partiendo de sus enlaces, ya que la lista no es continua. Si quisieras recorrerla de forma ascendente no irias más allá del nodo 2 y en forma descendente, mas allá del nodo 3.
Lo que yo haría es reconstruir la lista con el mismo criterio de ordenamiento que utilizaste, supuestamente basado en los datos de los nodos.

Saludos.

[[Delphius]]

Empezado por rgstuamigo

Bueno analizandolo un poco más a fondo el problema veo que la cuestion no puede ser resuelta, ya que para poder resolverla por lo menos deberiamos tener un puntero o referencia que vaya de P1 o P2 hacia el nodo nro. 4.
El caso actual es que con P1 y P2 solo podemos movernos entre ellos mismo y no podemos salir de cualquiera de ellos ya sea al nodo nro 1 o nodo nro 4., por lo tanto estamos encerrados..
Saludos...

Si nos limitamos a los nodos P1 y P2 evidentemente no se puede resolver el problema. Pero observa que también existen los nodos flags denominados Anterior y Proximo que apuntan al nodo 4º y de éste resulta posible llegar al nodo 1º. Luego de 1º es posible llegar a P2.

Saludos,

[rgstuamigo]

Empezado por Delphius

Si nos limitamos a los nodos P1 y P2 evidentemente no se puede resolver el problema. Pero observa que también existen los nodos flags denominados Anterior y Proximo que apuntan al nodo 4º y de éste resulta posible llegar al nodo 1º. Luego de 1º es posible llegar a P2.

Saludos,

No sé tú pero a mi parecer esa parte de la imagen más bien yo lo interpreté como una descripcion(solo una informacion) de que cada nodo tiene su nodo Siguiente y Anterior, es decir que solo nos están informando que es así en todo caso si en realidad son dos variables(punteros) que tambien se los puede utilizar, en ese caso la solucion es muy fácil.
Bueno, eso tendría que comentarnos nuestro amigo delphi.
Saludos...

[[Delphius]]

Empezado por rgstuamigo

No sé tú pero a mi parecer esa parte de la imagen más bien yo lo interpreté como una descripcion(solo una informacion) de que cada nodo tiene su nodo Siguiente y Anterior, es decir que solo nos están informando que es así en todo caso si en realidad son dos variables(punteros) que tambien se los puede utilizar, en ese caso la solucion es muy fácil.
Bueno, eso tendría que comentarnos nuestro amigo delphi.
Saludos...

Entiendo tu punto de vista, y lo había entendido así antes, pero me dije que si eso sólo es a modo de información para guiar al estudiante de que el nodo tiene un campo anterior y un campo próximo entonces sólo nos queda P1 y P2 como referencias para trabajar.

Y la verdad es que no veo manera de como únicamente se pueda llegar a la imagen 2 empleando P1 y P2. En este caso caben dos posibilidades:
1. El ejercicio está mal planteado, ó bien
2. Anterior y Próximo son dos nodos flags. Con ellos ya podría llegarse a una solución.

Antes de pensar que el profesor ha metido el dedo prefiero inclinarme por lo segundo.

Como dices, habrá que esperar a ver que comenta Delphi al respecto.

Saludos,

[ecfisa]

Empezado por rgstuamigo

yo lo interpreté como una descripcion(solo una informacion) de que cada nodo tiene su nodo Siguiente y Anterior

Al igual que vos, interpreté que la imágen puesta por delphi, era sólo a modo de ejemplo.
Supongo que no implementaría una lista doblemente enlazada si supiera con certeza que son 4 nodos ya que las listas, normalmente, se implementan cuando el número de nodos a agregar no está definido.

De ahí mi anterior conclusión. Ya que si la lista tuviese más nodos y los enlaces pueden 'romperse' en cualquier punto de forma aleatoria, lo más probable es que sea imposible recostruir la lista sólamente a partir sus enlaces. Incluso usando más de un apuntador.

Ahora, si se trata de ese caso en concreto tendría solución...


Saludos.

[delphi]

Empezado por ecfisa

Hola delphi.

Según tu gráfico la lista erronea (a reparar) esta así:

p1.ant = nil (o indeterminado)
p1.sig = 2
p1.Dato = Img1

p2.ant = 3
p2.sig = 2
p2.Dato = Img2

p3.ant = nil (o indeterminado)
p3.sig = 2
p3.Dato = Img3

p4.ant = 3
p4.sig = 1
p4.Dato = Img4

Realmente no veo manera de organizar esos nodos partiendo de sus enlaces, ya que la lista no es continua. Si quisieras recorrerla de forma ascendente no irias más allá del nodo 2 y en forma descendente, mas allá del nodo 3.
Lo que yo haría es reconstruir la lista con el mismo criterio de ordenamiento que utilizaste, supuestamente basado en los datos de los nodos.

Saludos.

es correcto ocupa nil, y en la imagen 2 pues ya todo esta correcto, mi interés es llegar a la imagen 2, y la imagen 2 es igual al código de la iamgen 3, pero no sé dónde iniciar o que debo tomar en cuenta para poder seguir la lógica de quitar el desorden de las flechas de la imagen 1, y asi sucesivamente hasta tener ordenado todo...pero tienes la idea

[ecfisa]

Hola delphi.

Espero interpretarte bien...

Si tenés el puntero al primer elemento de la lista (llamémosla Lista), para acceder al segundo nodo (imágen), solamente tenés que hacer:

Código Delphi [-]
Lista:= Lista.Sig;

Si no es una lista circular, el nodo 'p1' pareciera ser coherente, por que:
p1.ant:= nil;
p1.sig:= p2

Así que no deberías tener dificultad de acceder a P2 con la instrucción anterior.

Saludos.