Ediciones ENI Editorial | líder en informática
Nociones avanzadas
Los punteros y referencias
1. Recordatorio sobre la memoria y los datos
a. Estructura de la memoria
Los capítulos anteriores le han permitido aprender muchas cosas sobre la memoria y la organización de su contenido:
-
La memoria se descompone en bytes.
-
Cada byte de memoria dispone de una dirección.
-
Un dato se puede extender entre varios bytes, por lo tanto puede ocupar una franja de direcciones (por ejemplo 4 o 8 bytes para un real, un entero en 64 bits y todavía más para una cadena).
Representación de una variable en memoria
Una variable es un nombre dado a una o varias casillas. Nombra la zona de memoria que contiene el dato. La zona de memoria que contiene el dato se define por dos cosas:
-
La dirección de inicio del dato, es decir, la dirección del primer byte que contiene el dato.
-
El tamaño de esta zona, es decir, el número de bytes sobre el que se extienden los datos.
El tamaño de la zona depende del tipo del dato. Un carácter ASCII solo ocupa un único byte, un entero cuatro, un entero largo ocho, etc.
Cuando accede al contenido de la variable, accede al contenido de la zona de memoria que se le asocia. Por lo tanto, la variable contiene otra información, la dirección de la zona de memoria a la que se asigna.
Por convención, un ordenador que sabe gestionar mucha memoria, las direcciones se anotan en hexadecimal. Es más sencillo hablar de dirección 0x2dcf0239 que la dirección 768541241. Algunos lenguajes permiten acceder y por lo tanto ver la dirección de la zona de memoria de una variable, simplemente la dirección de la variable.
b. Python: los límites que no lo son
Puede que esté un poco decepcionado. El lenguaje Python utilizado desde el inicio de este libro, no permite conocer la dirección de la variable. De hecho, la mayor parte de las cosas descritas en las próximas páginas serán en parte inaccesibles para este lenguaje. Y entre estas cosas, la posibilidad de acceder en la dirección de memoria de las diversas variables. La razón es simple: Python es un lenguaje evolucionado de alto nivel que no (y usted con él) interactúa directamente con la memoria del ordenador.
Por el contrario, existen librerías un poco más complejas de utilizar que lo permiten, como pydbg. Cuando haya terminado el estudio de este libro, podrá...
Las listas encadenadas
1. Listas encadenadas simples
a. Principio
En la vida diaria, una lista toma varias formas: una lista de viajes, de tareas a realizar, un índice, un glosario, una colección de películas, de músicas, etc. Estas listas están compuestas por elementos individuales, relacionados unos con otros por su tipo o el orden que se le quiera dar. Para pasar de un elemento a otro, desciende por la lista en el orden que se le ha dado.
¿Cómo se representa una lista, por definición lineal, en programación? Al menos conoce un sistema: las tablas. En una tabla, puede almacenar n elementos y el orden se puede representar por el índice de la tabla.
¿Conoce otra forma de almacenar elementos? Los registros de tipos estructurados lo permiten y además, puede almacenar más detalles. También puede crear tablas de registros, por lo tanto darle un cierto orden.
Sin embargo, la utilización de las tablas plantea algunas veces problemas un poco complejos. Ya lo ha podido observar con los métodos de ordenación.
-
¿Cómo insertar un nuevo registro al inicio de tabla? No hay índices negativos…
-
¿Cómo insertar un nuevo registro al final de la tabla? Si la algoritmia ofrece un redimensionamiento dinámico, los lenguajes como Java no le permiten.
-
¿Cómo insertar un elemento en medio de la tabla? ¿Hay que mover todos los elementos para situar el nuevo en un lugar dado? Si la respuesta es afirmativa, la tabla tiene el riesgo de desbordarse.
-
¿Y si elimina un registro, de nuevo tiene que mover la tabla para tapar el agujero? ¿O encontrar un lugar para pasar?
Se puede organizar para programar de tal manera que todo funcione con las tablas. Es perfectamente posible. Pero, ¿es realmente razonable? ¿Es una programación eficaz? Recuerde que en el capítulo Introducción a la algoritmia ha aprendido que hay que ahorrar recursos. Este método es muy costoso y complicado. Es necesario encontrar otro más sencillo y atractivo.
De hecho, de nuevo una vez más, conoce todos los principios básicos de este nuevo método. A continuación se muestran algunos elementos:
-
Un registro puede contener otro registro.
-
Este otro registro puede ser del mismo tipo estructurado.
-
El registro también puede contener un puntero...
Los árboles
1. Principio
La implementación de los árboles en Python retoma los principios casi idénticos a las listas vistas anteriormente. No se le proporcionará esta vez el código Python. Es su responsabilidad en este caso implementar estos algoritmos, aunque no se preocupe porque no es muy difícil.
En la naturaleza, las plantas describen normalmente estructuras llamadas arborescentes. El ejemplo más evocador es el árbol: el tronco se descompone en varias ramas, las que se descomponen en ramas más pequeñas y así sucesivamente, hasta las extremidades donde podemos encontrar las hojas.
Según el caso, además de utilizar tablas y listas, en programación también puede elegir representar la organización de sus datos en forma arborescente. La noción de arborescencia es muy habitual en su ordenador personal. Hay mucha información representada, directa o indirectamente, en forma arborescente: los directorios de los discos duros, la estructura de una página web, la estructura de un sitio web, la descomposición de la ejecución de un programa y de sus llamadas a los subprogramas. En resumen, todo lo que utiliza una noción de jerarquía se puede representar en forma arborescente.
El ejemplo más sencillo de entender es el árbol genealógico. Partiendo de usted (1), en primer lugar ubica a sus padres (2) y después los padres de sus padres (4). Continúa con los padres de estos últimos (8) y así sucesivamente. Todos están relacionados por sus relaciones de parentesco: usted con sus padres, padres con abuelos y así sucesivamente. El esquema parte de usted, pero podría partir de sus bisabuelos, que tuvieron x hijos, y nietos, z biznietos (uno de ellos es usted). Cada individuo es el sucesor de su padre y el predecesor de sus hijos.
Un árbol genealógico es un árbol binario
¿Cómo representar un árbol genealógico en programación? Como sucede habitualmente dispone de varios medios, principalmente las bases de datos, pero conociendo las listas encadenadas debe pensar que existe un medio u otro de conseguirlo directamente con algunos registros y punteros. Tiene razón.
En un árbol, cada elemento (miembro de su familia), dispone de un padre y de una madre...
Ejercicios
Ejercicio 1
Escriba el algoritmo que permite recorrer y mostrar los n elementos de una tabla de enteros, partiendo de su primer elemento, con un puntero.
Ejercicio 2
Crear una estructura de lista encadenada circular y situar en ella tres elementos. Crear la función que permite devolver el primer elemento y después, el que permite recorrer todos los elementos.
Ejercicio 3
Sea la siguiente estructura:
Estructura nodo
valor:entero
pIzquierdo:puntero a nodo
pDerecho:puntero a nodo
FinEstruct y la siguiente función infija:
Funcion infija (pNodo:puntero a nodo)
Inicio
Si pNodo<>NIL Entonces
infija(pNodo→pIzquierdo) // subárbol izquierdo
Mostrar pNodo→valor // raíz
infija(pNodo→pDerecho) // subárbol derecho
FinSi
Fin Implementar en Python esta estructura y la función infija.
