Enlaces sin punteros

[Ñuño Martínez]

¿Confundidos? Pues agárrense, que vienen curvas.

Estoy leyendo Algoritmos + Estructuras de datos = Programas, del bueno de Kiklaus Wirth, porque encontré una primera edición en inglés (como curiosidad, fue el libro que provocó que Anders Hejlsberg escribiera Turbo Pascal 1.0).

La cosa es que me he atascado con un concepto en la página 19, porque por más vueltas que le doy no entiendo qué dice. Está hablando de registros (record) y listas, y habla de que se puede crear una lista doblemente enlazada añadiendo un campo más y haciendo una suma o una resta. El texto original:

http://www.burdjia.com/personal/img/adp-link.png

No incluye código de ejemplo. He probado varias implementaciones a ver si así lograba entender algo, pero no hay manera: no consigo que recorra toda la lista ni para atrás ni para delante. Pongo la primera que hice, que es la más naïf, para que veáis la estructura básica.

program RegsistrosEnlazados;
(* Intento de implementación del sistema de enlazado explicado en A+D=P. *)

type
(* Para identificar mejor. *)
TSexo = (Masculino, Femenino);
(* Contiene información de personas. *)
TPersona = record
Nombre: String;
Sexo: TSexo;
Link: Integer
end;
var
(* Información (extraído del libro). *)
Personas: array [1..10] of TPersona = (
(Nombre: 'Carolyn'; Sexo: Femenino; Link: 2),
(Nombre: 'Chris'; Sexo: Masculino; Link: 2),
(Nombre: 'Tina'; Sexo: Femenino; Link: 5),
(Nombre: 'Robert'; Sexo: Masculino; Link: 3),
(Nombre: 'Jonathan'; Sexo: Masculino; Link: 3),
(Nombre: 'Jennifer'; Sexo: Femenino; Link: 5),
(Nombre: 'Raytheon'; Sexo: Masculino; Link: 5),
(Nombre: 'Mary'; Sexo: Femenino; Link: 3),
(Nombre: 'Anne'; Sexo: Femenino; Link: 1),
(Nombre: 'Mathias'; Sexo: Masculino; Link: 3)
);

(* Elemento siguiente. *)
function SiguienteIndice (x, y: Integer): Integer;
begin
SiguienteIndice := x + Personas[y].Link
end;



(* Elemento anterior. *)
function AnteriorIndice (x, y: Integer): Integer;
begin
AnteriorIndice := x - Personas[y].Link
end;

var
Ndx: Integer;
begin
Ndx := 1;
repeat
WriteLn ('Nombre: ', Personas[Ndx].Nombre);
Ndx := SiguienteIndice (Ndx - 1, Ndx)
until (1 > Ndx) or (Ndx > High (Personas))
end.


De ahí he intentado varias cosas bastante más complejas, como intentar llevar la cuenta del elemento anterior (I^k-1) y el actual (i^k), pero no lo pillo.

Tampoco me va la vida en ello, pero si alguien me da una pista, o una implementación que funcione, pues se agradecerá. Yo, de momento, me paso al capítulo siguiente, que la neurona no me da para más.

[Casimiro Notevi]

Parece que no tiene lógica, a ver si es un error y en la siguiente edición del libro sacaron una "fe de erratas" de la primera versión :rolleyes:

[Casimiro Notevi]

Aquí está en español, creo que lo que enlaza es masculino/femenino, y no el siguiente registro, no sé :confused:


https://i.imgur.com/bxXA1E1.png

[mamcx]

Aquí está en español, creo que lo que enlaza es masculino/femenino, y no el siguiente registro, no sé :confused:

Si, eso es lo que dice el texto en ingles.


---


La idea general se llama una estructura de "Arena":

https://dev.to/deciduously/no-more-tears-no-more-knots-arena-allocated-trees-in-rust-44k6

basicamente, reemplazar por indices numericos lo que es un puntero. Es muy simple de usar, pero claro todo depende de los datos a enlazar.

P.d: Tengo un ejemplo de usar arenas para un arbol:

https://elmalabarista.com/blog/2022-flat-tree/

[Ñuño Martínez]

Tengo que darle una lectura más profunda a lo que pones, mamcx, porque así de primeras y con una lectura rápida sigo sin enterarme. Gracias por los enlaces.

Y la traducción que pones, Casi, parece confirma que mi traducción es correcta. Yo también he sospechado que podría haber algún error en la edición que estoy leyendo.

[Ñuño Martínez]

Pues como [casi] siempre que leo uno de estos artículos sobre temas esotéricos, me quedo con la sensación de que el autor presupone que sé algo que no sé. No sé si tiene que ver con que no tengo ni idea de Rust o si es otra cosa. De todas formas, he estado buscando y creo que lo que propone Wirth no tiene nada que ver con eso de las Arenas. Puede que esté equivocado, pero no he visto ninguna relación entre Arena Allocation (https://en.wikipedia.org/wiki/Arena_allocation) y lo que se explica en A+D=P.

[mamcx]

pero no he visto ninguna relación entre Arena Allocation (https://en.wikipedia.org/wiki/Arena_allocation) y lo que se explica en A+D=P.

Lo que Wirth explica es el algoritmo y una version simple de la estructura. La "Arena" es una aplicación concreta para que ademas, sirva para manejar memoria.

Ya que estamos hablando de punteros, es de hecho, un "memory manager". En estos días es mas fácil que encuentres recursos usando "Arena" como keyword, porque como se nombra esta idea? En fin.


---


Resumiendo: Todo el truco es como usas un indice numerico en un array para reemplazar un puntero. Como construyes ese mapeo varia de acuerdo a la estructura que deseas emular (vector, árbol, grafo, ...) y que operaciones(ges) deseas optimizar.