Punteros y referencias

1. Recordatorio sobre la memoria y los datos

a. Estructura de la memoria

Los capítulos anteriores ya le han enseñado mucho sobre la memoria y la organización de su contenido:

La memoria se divide en bytes.
Cada byte de la memoria tiene una dirección.
Los datos se pueden repartir en varios bytes, ocupando un rango de direcciones (por ejemplo, 4 u 8 bytes para un número real, incluso más para una cadena).

Representación de una variable en memoria

Una variable es un nombre que se da a una o varias celdas. Nombra la zona de memoria que contiene los datos. La zona de memoria que contiene los datos está definida por dos elementos:

La dirección de inicio de los datos, es decir, la dirección del primer byte que contiene los datos.
El tamaño de esta zona, es decir, el número de bytes que componen los datos.

El tamaño de la zona depende del tipo de datos. Un carácter ASCII ocupa un solo byte, un entero cuatro, un entero largo ocho, etc.

Cuando se accede al contenido de la variable, se accede al contenido de la zona de memoria asociada a ella. Por tanto, la propia variable contiene otra información, la dirección de la zona de memoria a la que está asignada.

Por convención, dado que un ordenador puede gestionar mucha memoria, las direcciones se escriben en hexadecimal. Es más fácil hablar de la dirección 0x2dcf0239 que de la dirección 768541241. Algunos lenguajes permiten acceder y por tanto ver la dirección de la zona de memoria de una variable, simplemente la dirección de la variable.

b. PHP: límites que no lo son

El lenguaje PHP utilizado desde el principio de este libro no permite averiguar la dirección de la variable. De hecho, la mayoría de las cosas descritas en las próximas páginas serán parcialmente inaccesibles para este lenguaje. Una de ellas es la posibilidad de acceder a la dirección de memoria de diversas variables. La razón es simple: PHP es un lenguaje avanzado de alto nivel que no tiene que interferir directamente con la memoria de la computadora. El programa PHP no sabe dónde están almacenados realmente sus datos en la memoria principal; es el intérprete el que se encarga de todo. Si hubiera sido posible ver una dirección, habría sido dentro de la memoria reservada...

Las listas enlazadas

1. Listas enlazadas simples

a. Aspectos principales

En la vida cotidiana, una lista adopta muchas formas: una lista de la compra, una lista de tareas pendientes, un índice, un glosario, una colección de DVD, una colección de música, etcétera. Estas listas se componen de elementos individuales, vinculados entre sí por su tipo o por el orden que quiera darles. Para pasar de un elemento a otro, desplázate por la lista en el orden que especifique.

¿Cómo se representa en programación una lista, que por definición es lineal? Conoce al menos una forma: las tablas. En una tabla se pueden almacenar n elementos y el orden se puede representar mediante el índice de la tabla.

¿Conoce otra forma de almacenar elementos? Los registros de tipo estructurado le permiten hacer precisamente eso y puede almacenar en ellos muchos más detalles. También puede crear tablas de registros, para darles un cierto orden.

Sin embargo, el uso de tablas a veces puede plantear problemas un poco complejos. Ya lo ha notado con los métodos de ordenación.

¿Cómo se inserta un nuevo registro al principio de una tabla? No hay índices negativos...
¿Cómo se inserta un nuevo registro al final de una tabla? MientrasQue los algoritmos sugieren el redimensionamiento dinámico, los lenguajes PHP lo permiten.
¿Cómo se inserta un elemento en el centro de la tabla? ¿Hay que desplazar todos los elementos para colocar el nuevo en la posición dada? Si es así, la tabla puede desbordarse.
Y si borra un registro, ¿desplazará de nuevo la tabla para tapar el hueco? ¿O encontrará una forma de superarlo?

Puede programarlo todo para que funcione con las tablas. Es perfectamente posible. Pero, ¿es realmente sensato? ¿Es una programación eficiente? Recuerde que en el capítulo de Introducción a los algoritmos, aprendió que hay que ser ahorrador con los recursos. Este método es avaro y complicado. Necesita encontrar otro método que sea más simple y económico.

De hecho, una vez más, conoce todos los principios básicos de este nuevo método. He aquí algunos puntos:

Un registro puede contener otro registro.
Este otro registro puede ser del mismo tipo estructurado.
El registro también...

Los árboles

1. Aspectos principales

La implementación de árboles en PHP se basa en los mismos principios que las listas que hemos visto anteriormente. Esta vez, no se le proporcionará el código PHP. Depende de usted implementar estos algoritmos - no es tan difícil.

En la naturaleza, las plantas describen a menudo las llamadas estructuras arborescentes. El ejemplo más evocador es el árbol: el tronco se descompone en varias ramas, que, a su vez, se descomponen en ramas más pequeñas y así sucesivamente, hasta llegar a los extremos donde crecen las hojas.

En su caso, después de las tablas y las listas, también puede optar por representar la organización de sus datos en forma de estructura de árbol en programación. La noción de estructura arborescente es muy común en el ordenador personal y una gran cantidad de información se representa, directa o indirectamente, en forma de estructura arborescente: carpetas del disco duro, la estructura de una página web, la estructura de un sitio web, el desglose de la ejecución de un programa y sus llamadas a subprogramas... en resumen, cualquier cosa que pueda incorporar una noción de jerarquía se puede representar en forma de una estructura de árbol.

El ejemplo más sencillo de entender es la genealogía. Se llama árbol genealógico. Empezando por usted (1), primero coloca a sus padres (2), luego a los padres de sus padres (4), luego a los padres de estos (8) y así sucesivamente. Todos están vinculados por sus lazos familiares: usted con tus padres, los padres con los abuelos y así sucesivamente. El diagrama empieza con usted, pero podría empezar con tus bisabuelos, que tienen x hijos, y nietos, z bisnietos (incluido usted), siendo cada individuo el sucesor de su progenitor y predecesor de sus hijos.

Un árbol genealógico es un árbol binario

¿Cómo se representa un árbol genealógico de este tipo en programación? Como suele ocurrir con las bases de datos, hay varias formas de hacerlo, pero si está familiarizado con las listas enlazadas, pensará que hay una forma u otra de arreglárselas con unos pocos registros y punteros. Y estaría en lo cierto.

En un árbol, cada elemento (miembro de su familia) tiene un padre y una madre...

Ejercicios

Ejercicio 1

Escriba en PHP el algoritmo de ordenación por fusión explicado en la sección de ejemplos de ordenación.

Ejercicio 2

Busque en la documentación de PHP el nombre SplDoublyLinkedList. Implemente un ejemplo añadiendo las cuatro primeras letras del alfabeto a la lista. A continuación, muestre todo el contenido en modo FIFO (First In First Out).

A continuación, muestre el primer valor, el último valor y el número de elementos de la lista.

Ejercicio 3

Considere el siguiente árbol:

Representar el árbol de ejemplo en PHP. Este árbol es un tabla multidimensional con el valor (A, B, D, etc.) como clave y el hijo como valor. Muestre el árbol completo utilizando la función var_dump().

Ejercicio 4