miércoles, 7 de octubre de 2015

Unidad III: Registros


REGISTROS
Estructura de datos formada por una colección finita de elementos llamados campos, no necesariamente homogéneos (del mismo tipo) y que permiten almacenar una serie de datos relacionados entre si, bajo un nombre y una estructura común.

Características Básicas de los Registros
·           Permiten almacenar un grupo de elementos bajo un nombre y una estructura común.
·           Los elementos (campos) de un registro no tienen que ser homogéneos, de hecho, generalmente son de diferentes tipos.
·           No están disponibles en todos los lenguajes de programación, razón por la cual muchas veces es necesario simularlo o definirlo.
·           Cada campo del registro se comporta como una variable simple, de manera que puede ser usado en una expresión de asignación, como parte de otra expresión, en operaciones o como parámetro al invocar una acción o función.

Declaración de Registros
Declaración por variable: se declara la variable de tipo registro identificándola a través de su nombre, se indica la estructura del registro suministrando la definición de sus campos mediante sus tipos de dato y sus nombres.
La sintaxis a utilizar para declarar un registro será:
Registro=
// se indica el nombre del registro
// tipo de dato y nombre del campo
// tipo de dato y nombre del campo 2…  N N
// tipo de dato y nombre del campo N
Fregistro,
Declaración por tipo: al igual que con los arreglos, para declarar un tipo de registro definido por el usuario, se antecede a la especificación, la palabra clave Tipo y luego se definen las variables del tipo. El uso de la declaración por tipo facilita la declaración de variables con una estructura común, así como el pase de parámetros.

Tipos de Registros
Registros de Segmento: un registro de segmento tiene 16 bits de longitud y facilita un área de memoria para direccionamiento conocida como el segmento actual.
Registros de Apuntador de Instrucciones: Este registro esta compuesto por 16 bits y contiene el desplazamiento de la siguiente instrucción que se va a ejecutar. Los procesadores 80386 y posteriores tienen un IP ampliado de 32 bits llamado EIP.
Registros Apuntadores: permiten al sistema accesar datos al segmento de la pila. Los procesadores 80386 tienen un apuntador de pila de 32 bits llamado ESP. El sistema maneja de manera automática estos registros.
 Registros de Propósito General: son los caballos de batalla del sistema y pueden ser direccionados como una palabra o como una parte de un bytes. Los procesadores 80386 y posteriores permiten el uso de todos los registros de propósitos general más sus versiones ampliadas de 32 bits llamados EAX, EBX, ECX y EDX.
Registros Índices: sirven para el direccionamiento de indexado y para las operaciones de sumas y restas.
Registros de Banderas: sirven para indicar el estado actual de la maquina y el resultado del procesamiento. De los 16 bits de registro de bandera 9 son comunes a toda la familia de los procesadores 8086.

Longitud Fija: son los registros que tienen el mismo tamaño, es decir el mismo número de bytes, además de tener un número fijo de campos.
Longitud Variable: son los registros que se adaptan al tamaño de la información incluida en ellos, en estos se utilizan delimitadores tanto para el fin campo como para el fin de registro, uno de los delimitadores usados es * para el campo y # para el registro. Cabe mencionar que este tipo de longitud en registros se puede dar de dos formas que son:
·           Registros de longitud variable con campo fijo.
·           Registros de longitud variable con campo variable.

ARCHIVOS
Los archivos también denominados ficheros (file); es una colección de información (datos relacionados entre sí), localizada o almacenada como una unidad en alguna parte de la computadora.
Los archivos son conjunto organizado de informaciones del mismo tipo, que pueden utilizarse en un mismo tratamiento; como soporte material de estas informaciones. Los archivos como colección de datos sirven para la entrada y salida a la computadora y son manejados con programas.
Los archivos pueden ser contrastados con Arrays y registros; lo que resulta dinámico y por esto en un registro se deben especificar los campos, el número de elementos de un arrays (o arreglo), el número de caracteres en una cadena; por esto se denotan como “Estructuras Estáticas”.
En los archivos no se requiere de un tamaño predeterminado, esto significa que se pueden hacer archivos de datos más grandes o pequeños, según se necesiten.
Cada archivo es referenciado por su identificador (su nombre).

Tipos de Archivos
Los elementos de un archivo pueden ser de cualquier tipo, simples o estructurados o según su función.
Según su función. Se define por:
a)    Archivos permanentes: son aquellos cuyos registros sufren pocas o ninguna variación a lo largo del tiempo, se dividen en:
a.    Constantes: están formados por registros que contienen campos fijos y campos de baja frecuencia de variación en el tiempo.
b.    De situación: son los que en cada momento contienen información actualizada.
c.    Históricos: contienen información acumulada a lo largo del tiempo de archivos que han sufridos procesos de actualización o bien acumulan datos de variación periódica en el tiempo.
b)   Archivos de movimientos: son aquellos que se utilizan conjuntamente con los maestros (constantes), y contienen algún campo común en sus registros con aquellos, para el procesamiento de las modificaciones experimentado por los mismos.
c)    Archivo de maniobra o transitorio: son los archivos creados auxiliares durante la ejecución del programa y borrados habitualmente al terminar el mismo.

Según sus elementos. Los principales archivos de este tipo son:
a)    Archivo de Entrada: una colección de datos localizados en un dispositivo de entrada.
b)   Archivo de Salida: una colección de información visualizada por la computadora. Constantes: están formados por registros que contienen campos fijos y campos de baja frecuencia de variación en el tiempo.
c)    De Situación: son los que en cada momento contienen información actualizada.
d)   Históricos: contienen información acumulada a lo largo del tiempo de archivos que han sufrido procesos de actualización, o bien, acumulan datos de variación periódica en el tiempo.
e)    Archivos de Movimientos o Transacciones: son aquellos que se utilizan conjuntamente con los maestros (constantes), y contienen algún campo común en sus registros con aquellos, para el procesamiento de las modificaciones experimentado por los mismos.
f)     Archivo de Maniobra o Transitorios: son los archivos creados auxiliares durante la ejecución del programa y borrados habitualmente al terminar el mismo.

Según sus elementos. Los principales archivos de este tipo son:
a)    Archivo de Entrada: una colección de datos localizada en un dispositivo de entrada.
b)   Archivo de Salida: una colección de información visualizada por la computadora. Archivo de Programa, un programa codificado en un lenguaje específico y localizado o almacenado en un dispositivo de almacenamiento.
c)    Archivo de Texto: una colección de caracteres almacenados como una unidad en un dispositivo de almacenamiento.

ACCESO SECUENCIAL
El acceso secuencial (sequential access) es la lectura o escritura de datos en forma secuencial, o sea, uno tras otro. Contrario al acceso aleatorio, donde es posible leer cualquier posición sin tener que pasar por las que están detrás.
El método de acceso secuencial requiere interactuar con el resto de los datos o espacio físico del medio de almacenamiento para acceder a un dato especifico. En informática, la lista enlazada es un claro ejemplo de una estructura de almacenamiento de datos que requiere el acceso secuencial para poder leer o guardar un dato específico.
Otros ejemplos de acceso secuencial: el tocadiscos, lectora de cinta de respaldo, grabador de discos ópticos (cuando se graba un disco óptico, como un CD o un DVD, el láser va guardando la información en forma de espiral sobre la superficie de disco duro, escribiendo un dato a continuación del otro), los casetes (para acceder a una porción de lo almacenado es necesario recorrer una parte de cinta antes).

ACCESO DIRECTO
El acceso directo es un concepto usado en los sistemas operativos Microsoft Windows para referirse a un fichero u objeto cuyo contenido contiene instrucciones que redirigen a otro fichero del sistema de ficheros o a un lugar de la red. Está representado por un icono con una flecha en la parte inferior del lado izquierdo del icono.
Este tipo de archivos contienen información sobre una ubicación (programa o documento), generalmente representada mediante un icono personalizado. No son editables mediante un editor de texto; sólo se pueden editar desde el explorador de Windows. 


Unidad IV: Pilas y Colas


PILA
Una pila (stack 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 solo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack 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.
·         Implementación de recursividad.



Declaraciones de tipos para manejar pilas en C
Los tipos que definiremos normalmente para manejar pilas serán casi los mismos que para manejar listas, tan solo cambiaremos algunos nombres:
typedef struct_nodo {
int dato;
struct_nodo *siguiente;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;

tipoNodo es el tipo para declarar nodos, evidentemente.
pNodo es el tipo para declarar punteros a un nodo.
Pila es el tipo para declarar pilas.
           
            Es evidente, a la vista del gráfico, que una pila es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas.        Teniendo en cuenta que las inserciones y borradores en una pila se hacen siempre en un extremo, lo que consideramos como el primer elemento de la lista es en realidad el último elemento de la pila.

OPERACIONES
            Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.
·         Crear: se crea la pila vacia (constructor).
·         Tamaño: regresa el número de elementos de la pila (size).
·         Apilar: se añade un elemento a la pila (push).
·         Desapilar: se elimina el elemento frontal de la pila (pop).
·         Cima: devuelve el elemento que está en la cima de la pila (top o peek).
·         Vacía: devuelve cierto si la pila está sin elementos o falso en caso de que contenga uno (empty).

Tipos de Pilas
El tipo base de la estructura FIFO (el primero en entrar es el primero en salir) es la cola y la combinación de las operaciones de la pila y la cola es proporcionado por el de que. Por ejemplo: el cambio de una pila en una cola en un algoritmo de búsqueda puede cambiar el algoritmo de búsqueda en primera profundidad (en inglés, DFS) por una búsqueda en amplitud (en inglés, BFS). Una pila acotada es una pila limitada a un tamaño máximo impuesto en su especificación.

Pilas alojadas en arreglos
Implementación de pilas con arreglos: resulta conveniente el almacenamiento secuencial para el tratamiento de pilas. Podemos tener una variable llamada TOPE que contenga el índice donde está ubicado el tope de la pila. Cuando la pila está vacía, se hace TOPE=0.
Por ejemplo: se puede definir una constante llamada CANTELEMENTOS que tenga el valor máximo de elementos que podrá contener la pila, un tope con la última posición, un valor a ser ingresado y el arreglo mismo:
#define CANTELEMENTOS 10;
int tope= -1; /*inicializamos a la variable tope con el valor -1 para que represente a la pila vacía porque el 1º elemento tiene índice 0.*/
 int pila[CANTELEMENTOS];
int valor;
            Para darte un ejemplo sencillo: supone que tienes una pila de 10 platos. El primer plato de la pila será el último en quitarse y el último plato de la pila será el primero en quitarse.
            Un arreglo constituye el depósito de los elementos de la pila. El rango del arreglo debe ser lo suficientemente amplio para poder contener el máximo previsto de elementos de la pila. Un extremo del arreglo se considera el fondo de la pila, que permanecerá fijo. La parte superior de la pila, tope o cima, estará cambiando dinámicamente durante la ejecución del programa. Además del arreglo, una variable entera nos sirve para tener en todo momento el índice del arreglo que contiene el elemento tope. Las declaraciones, procedimientos y funciones para representar el TAD pila, forman parte de la unidad pila.
·         Max_elem=…(Dependerá de cada realización).
·         Tipo_elem=…(Tipo de los elementos de la pila).
·         Pila= Registro.
·         Elem= arreglo [1…Max_elem] de Tipo_elem;
·         Tope= entero; FinRegistro.

Implementación de Procedimientos Recursivos mediante pilas
Un procedimiento o función contiene tanto variables locales como argumentos ficticios o parámetros. A través de los argumentos se transmiten datos en las llamadas a los subprogramas, o bien, se devuelven valores al programa o subprograma invocante. Además, el subprograma debe guardar la dirección de retorno al programa que realiza la llamada. En el momento en que termina la ejecución de un subprograma el control pasa a la dirección guardada.
Ahora, el subprograma es recursivo, entonces además de la dirección de retorno, los valores actuales de las variables locales y argumentos deben de guardarse ya que se usarán de nuevo cuando el subprograma se reactive. Supongamos que se ha llamado al subprograma P, que tiene llamadas a si mismo, es decir, es recursivo. El funcionamiento del programa recursivo P será: ü se crea una pila para cada argumento. ü se crea una pila para cada variable local. ü se crea una pila para almacenar la dirección de retorno. Cada vez que se hace una llamada recursiva a P, los valores actuales de los argumentos y de las variables locales se meten en sus pilas para ser procesadas posteriormente. Asimismo, cada vez que hay un retorno a P procedente de una llamada recursiva anterior, se restauran los valores de variables locales y argumentos de la simas de la pilas. Para la obtención de la dirección de retorno es de suponer que el procedimiento P contiene una llamada recursiva en la sentencia N. Entonces guarda en optra pila la dirección de retorno, que será la sentencia siguiente, la N+1. De tal forma que cuando el nivel de ejecución del procedimiento P actual termine, o sea, alcance la sentencia end final, usará dicha pila de direcciones para volver al nuevo nivel de ejecución.

COLAS
Una cola (también llamada fila) es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Representación de las Colas
Se las puede representar por listas enlazadas o por arrays
C= Q (1), Q (2),…, Q (n).
En cualquier caso se necesitan dos punteros
frente (f)
final(r)
y la lista o array de n elementos (LONGMAX)

Las operaciones que pueden realizar con una cola son:
·         Acceder al primer elemento de la cola.
·         Añadir un elemento al final de la cola.
·         Eliminar el primer elemento de la cola.
·         Vaciar una cola.
·         Verificar el estado de la cola: vacía o llena.

Operaciones
·         Crear: se crea 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ó.

Cola 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 cosultarse, 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.

Colas Doblemente Enlazadas
Como ocurre con toda representación estática, una de las principales desventajas es que hay que prever un máximo de elementos, y de ese máximo no se puede pasar. La realización de una cola mediante una lista enlazada permite ajustarse exactamente al número de elementos de la cola. Esta implementación con las listas enlazadas utiliza dos punteros que acceden a la lista, el puntero frente y el puntero final. Cola implementada con listas enlazadas, el puntero final referencia al último nodo que fue añadido. En esta representación no tiene sentido la operación que indica si la cola está llena. Al ser una estructura dinámica crece y decrece según las necesidades. La definición de cola usando listas enlazadas serían:
·         Tipo_elto: (Tipo del campo información de cada nodo).
·         Nodo: Registro.
·         Elto: Tipo_elto;
·         Sig: hNodo;
·         Fregistro; Cola:
·         Registro frente: hNoho;
·         final: hNodo; Fregistro;

Tipos de Colas
a)     Colas Circulares (anillos): en las que el último elemento y el primero están unidos.
b)     Colas de Prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:
a.    Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
b.    Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.
c)     Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las Bicolas se puede hacer con un array ciruclar con inicio y fin que apunten a cada uno de los extremos. Hay variantes:
a.    Bicolas de entrada restringida: son aquellas donde la inserción sólo se hace por el final, aunque se puede eliminar al inicio ó al final.
b.    Bicolas de salida restringida: son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

Aplicaciones de Colas
Las colas también se utilizan en muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento).
Si esta trabajando en un sistema multiusuario, cuando le dice a la computadora que ejecute un programa concreto, el sistema operativo añade su petición a su “cola de trabajo”. Cuando su petición llega al frente de la cola, el programa solicitado pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de entrada / salida (E/S), impresoras, discos, cintas y demás. El sistema operativo mantiene colas para peticiones de imprimir, leer o escribir en cada uno de estos dispositivos.