Apuntadores, Estructuras Lineales Y No Lineales, Grafos

APUNTADORES

Un dispositivo apuntador es un componente hardware (más concretamente un dispositivo de interfaz humana) que permite al usuario introducir datos de espacio a una computadora. Los sistemas CAD y los equipos dotados de Interfaz gráfica de usuario (GUI) permiten al usuario controlar y proporcionar datos al ordenador usando movimientos físicos del dispositivo (apuntar, clic, arrastrar), principalmente moviendo un ratón de mano sobre la superficie real de una mesa y activando los interruptores en éste. Los movimientos del periférico son reflejados en la pantalla como movimientos del puntero o cursor, y otros cambios visuales.

La conexión del dispositivo puede ser por cable, inalámbrica (radio, Bluetooth, infrarrojos...), de contacto (pantallas táctiles), entre otros.

El dispositivo apuntador más habitual es el ratón, pero se utilizan también TrackBall, touchpad, TrackPoint, lápiz óptico, joystick, varios tipos de tableta digitalizadora, punteros de cabeza, dispositivos de seguimiento ocular, guante de datos (data glove), traje de datos (un mono dotado de sensores), videocámaras (quizá la más conocida sea la Eye Toy de Sony), varios tipos de punteros bucales (usados principalmente por personas afectadas por tetraplejía) que convierten acciones del usuario en acciones del sistema informático.

Un puntero puede referirse también a un tipo especial de lápiz que se utiliza para señalar cosas en una superficie amplia, como mapas o pantallas de proyección personal. Inicialmente solían ser lápices telescópicos que se recogían y ampliaban cuando no se usaban (quedando y pareciendo un bolígrafo normal que incluso escribe), pero están siendo sustituidos por punteros lumínicos, particularmente láser. Varios tipos de TrackBall especialmente diseñados para presentaciones suelen incorporar uno de estos en uno de sus extremos.

STACKS

Una pila (stacks en inglés) es una lista ordenada o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.

En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stacks en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.

Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

Las pilas suelen emplearse en los siguientes contextos:

• Evaluación de expresiones en notación postfija (notación polaca inversa).

• Reconocedores sintácticos de lenguajes independientes del contexto.

OPERACIONES EN COLAS

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todas líneas de espera. En caso de estar vacía, borrar un elemento sería imposible hasta que no se añade un nuevo elemento. A la hora de añadir un elemento podríamos darle una mayor importancia a unos elementos que a otros (un cargo VIP) y para ello se crea un tipo de cola especial que es la cola de prioridad.

OPERACIONES BASICAS

• Crear: se crea la cola vacía.

• Encolar: (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.

• Desencolar: (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.

• Frente: (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

COLAS CIRCULARES

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual. Las colas lineales tienen un grave problema, como las extracciones sólo pueden realizarse por un extremo, puede llegar un momento en que el apuntador A sea igual al máximo número de elementos en la cola, siendo que al frente de la misma existan lugares vacíos, y al insertar un nuevo elemento nos mandará un error de overflow (cola llena).Para solucionar el problema de desperdicio de memoria se implementaron las colas circulares, en las cuales existe un apuntador desde el último elemento al primero de la cola. La representación gráfica de esta estructura es la siguiente: Ejemplos:

COLAS DE PRIORIDAD

Una cola de prioridad es una estructura de datos que permite al menos las siguientes dos operaciones: insertar, que añade elementos a la cola, y eliminar mínimo, que busca, devuelve y elimina el elemento mínimo de la cola.

LISTAS ENCADENADAS

Listas simples encadenadas

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo (o indica que tiene la dirección en memoria del siguiente nodo) en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Listas doblemente encadenadas

Un tipo de lista enlazada más sofisticado es la lista doblemente encadenada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el

...