LENGUAJES DE PROGRAMACIÓN
ANTECEDENTES DE LA MATERIA
AGUILAR LOZANO CÉSAR IVÁN
SERVIN PICHARDO LUZ TAVATA
TOLEDO FLORES MIGUEL ANGEL
miércoles, 28 de noviembre de 2007
sábado, 3 de noviembre de 2007
Antecedentes de la materia
ARCHIVOS
¿Qué son los archivos?
Los archivos también denominados ficheros (file); es una colección de información (los datos relacionados entre sí), localizada o almacenada como una unidad en alguna parte de la misma computadora.
A modo de otra definición, los archivos son el conjunto organizado de informaciones del mismo tipo, que pueden utilizarse en un mismo tratamiento; como soporte material de estas informaciones.
Breve introducción a los archivos
Los archivos como colección de datos sirve para la entrada y salida a la computadora y son manejados con diferentes 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, él 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).
Principales características de los archivos DE LOS ARCHIVOS
Las principales características de este tipo de estructuras son:
Independencia de las informaciones respecto de los programas
La información almacenada es permanente
Un archivo puede ser accedido por distintos programas en distintos momentos
Gran capacidad de almacenamiento
Clasificación de los archivos
Los archivos se clasifican según su uso en tres grandes grupos:
Permanentes o Maestros:
Estos contienen información que varia poco. En algunos casos es preciso actualizarlos periódicamente.
De Movimientos
Se cercan para actualizar los archivos maestros. Sus registros son de tres tipos: alta, bajas y modificaciones.
De Maniobra o Trabajo.
Tienen una vida limitada, normalmente menor que la duración de la ejecución de un programa. Su utilizan como auxiliares de los anteriores.
Distintos 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 cuyo registros sufren pocas o ninguna variación a lo largo del tiempo, se dividen en:
Constantes: Están formados por registros que contienen campos fijos y campos de baja frecuencia de variación en el tiempo.
De Situación: Son los que en cada momento contienen información actualizada.
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 Movimiento
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 experimentados por los mismos.
c.- Archivo de Maniobra o Transitorio
Son los archivos creados auxiliares creados durante la ejecución del programa y borrados habitualmente al terminar el mismo.
Según sus elementos
Los principales archivos de este tipo son:
Archivo de Entrada: Una colección de datos localizados en un dispositivo de entrada.
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.
De Situación: son los que en cada momento contienen información actualizada.
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.
Archivos de movimiento 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 experimentados por los mismos.
Archivos de Maniobra o Transitorios: Son los archivos auxiliares creados durante la ejecución del programa y borrados habitualmente al terminar el mismo.
Según sus elementos
Los principales archivos de este tipo son:
Archivo de Entrada, una colección de datos localizada en un dispositivo de entrada.
Archivo de Salida, una colección de información visualizada por la computadora
Archivo de Programa, un programa codificado en un lenguaje especifico y localizado o almacenado en un dispositivo de almacenamiento
Archivo de Texto, una colección de caracteres almacenados como una unidad en un dispositivo de almacenamiento.
El acceso a los archivos
Se refiere al método utilizado para acceder a los registros de un archivo prescindiendo de su organización. Existen distintas formas de acceder a los datos:
Secuenciales; los registros se leen desde el principio hasta el final del archivo, de tal forma que para leer un registro se leen todos los que preceden.
Directo; cada registro puede leerse / escribirse de forma directa solo con expresar su dirección en el fichero por él numero relativo del registro o por transformaciones de la clave de registro en él numero relativo del registro a acceder.
Por Índice; se accede indirectamente a los registros por su clave, mediante consulta secuenciales a una tabla que contiene la clave y la dirección relativa de cada registro, y posterior acceso directo al registro.
Dinámico; es cuando se accede a los archivos en cualquier de los modos anteriormente citados.
La elección del método esta directamente relacionada con la estructura de los registros del archivo y del soporte utilizado.
Los tipos de accesos
Acceso Secuencial. Exige el tratamiento de elemento, para esto es necesario una exploración secuencial comenzando desde el primer momento
Secuenciales: archivo de texto que debe ser leído del principio hasta el final.
Acceso Directo. Permite procesar o acceder a un elemento determinado y referencia directamente por su posición en el soporte de almacenamiento
Aleatorios: es un archivo con registros de un mismo largo. Un programa puede accesar directamente cualquier registro sin tener que leer los registros previos.
Binarios: es un archivo que lee byte por byte sin asumir ninguna estructura. Los archivos Binarios no son un nuevo tipo de archivo, pero si una nueva forma de manipular cualquier tipo de archivo. Las técnicas de archivo binarios permiten leer o cambiar cualquier byte de un archivo. Son herramientas extremadamente potentes, pero como toda herramienta potente debe manejarse con cuidado
Instrucciones para manejar archivos
OPEN: reserva un espacio del buffer para la data que moverá entre el programa y los archivos.
La estructura es:
OPEN filespec FOR {AppendBinaryInputOutuputRandom} As #filenumber
Por ejemplo:
OPEN "C:\Windows\AddrBook.ini" FOR Input As #1
Filespec: Es la localización de archivo en el que se trabajará, incluyendo usualmente el drive y path.
"C:\Windows\AddrBook.ini"
{Append Binary Input Outuput Random} El programador tiene que seleccionar uno. Binary y Random se utiliza para archivos binarios y aleatorios. Append, Input y Output son usados con archivos secuenciales. Un archivo secuencial no puede ser abierto para leer y escribir simultaneamente. Output es usado para escribir en el archivo. Input es usado para leer del archivo. Append es usado para colocar data al final de un archivo exitente.
#filenumber: es necesario asignar un número al archivo. El número puede estar en el rango de #1 a #511 y es usado por Visual Basic para identificar el archivo.
CLOSE: para cerrar un archivo.
La estructura es:
CLOSE #filenumber
Por ejemplo:
CLOSE #1
WRITE: envia data del programa al archivo secuencial.
La estructura es: WRITE #filenumber, [OutputList]
Por ejemplo:
WRITE #1, UserName, UserCompany, SerialNumber
WRITE es la operación opuesta al INPUT. Las expresiones en el OutputList son separadas por comas. WRITE inserta comillas y comas a la data que envia al archivo.
INPUT: lee data del archivo. La estructura es:
INPUT #filenumber, InputList
Por ejemplo:
INPUT #1, UserName, UserCompany, SerialNumber
Declaración y asignación de archivos
La declaración de un archivo con tipo se efectúa con la ayuda de las palabras reservadas file of.
El procedimiento de asignación es idéntico al utilizado anteriormente.
Ejemplo:
Type
datos = record
clave : integer;
nombre : string[30];
puesto : string[20];
sueldo : real;
estado : boolean;
{true activo,false baja lógica}
end;
Var
archivo:file of datos;
begin
Assign(archivo,'empleado.dat');
El sistema de manejo de archivos
Tiene las siguientes funciones:
Controla los datos en almacenamiento secundario
Proporciona al usuario una abstracción de cómo se manipulan los datos internamente.
Proporciona independencia de E/S con los dispositivos
Soporte de compartición, protección, recuperación de archivos y posibles caídas del sistema.
Transmisión de datos de memoria principal a secundaria.
Por ejemplo, los archivos de una empresa pueden almacenarse en diferentes dispositivos. Todos los archivos se pueden almacenar por medio de directorios, que no son otra cosa más que tablas de símbolos de archivo, los directorios se pueden utilizar de dos formas:
DIRECTORIO DE NIVEL ÚNICO O DIRECTORIO PLANO
Con este método, se almacenan todos los archivos en un solo nivel, este método en sistemas donde el volumen de archivos no es grande.
DIRECTORIO JERARQUICO
Los archivos son almacenados por medio de directorios, esta clasificación se de acuerdo a la conveniencia del usuario o de la empresa.
La estructura tiene una forma de árbol con raíz, este método es el más utilizado debido a que la revisión o búsqueda se realiza de forma sencilla.
Para accesar a los archivos que se almacenan en un sistema jerárquico, el usuario debe indicar el o los directorios que se deben recorrer para localizar el archivo deseado, a esto se le denomina ruta de acceso del archivo.
La ruta de acceso puede ser de dos formas:
Ruta absoluta.- Este tipo de ruta de acceso inicia siempre con una diagonal invertida
C:\Edit c:\SOS\sistemas\report.txt
Ruta relativa.- Este tipo de ruta de acceso realiza la búsqueda del archivo en el directorio de trabajo actual, si el archivo no se localiza aquí, el S.O. lo buscará en los directorios especificados en el PATH de un archivo con extensión .BAT.
C:\Edit report.txt
Operaciones generales que se realizan sobre un archivo
Las operaciones generales que se realizan son:
Creación.
Escritura de todos sus registros.
Consulta.
Lectura de todos sus registros.
Actualización.
Inserción supresión o modificación de algunos de sus registros
Clasificación.
Reubicación de los registros de tal forma que queden ordenados según determinados criterios.
Borrado.
Eliminando total del archivo, dejando libre el espacio del soporte que ocupaba.
Organización de los archivos
Los archivos se encuentran organizados lógicamente como una secuencia de registros de varias longitudes diferentes.
Los archivos de registros de longitud fija: son los que almacenan la información en los archivos mediante un encabezado y luego se introducen uno a uno los registros ubicados en posiciones consecutivas.
Los registros de longitud variable: es el almacenamiento de registros de varios tipos en un archivo y permite uno o más campos de longitudes variables y dichos campos pueden ser repetidos. La longitud de los registros debe estar definida correctamente para poder leer y escribir de forma efectiva.
Enfoques generales para la organización de archivos
Los enfoques son:
1. - Enfoque de acceso secuencial: Se refiere al procesamiento de los archivos de acuerdo con el orden especifico. Ejemplo archivo secuenciales y de texto
2. - Enfoque de acceso Directo Permite recuperar registros individuales sin leer otros registros del archivo, ejemplos archivos indizados.
Archivos secuenciales
Se refiere al procesamiento de los registros, no importa el orden en que se haga, para eso los registros están organizados en forma de una lista y recuperarlos y procesarlos uno por uno de principio a fin.
Rudimentos de los archivos Secuenciales; dependiendo del dispositivo de almacenamiento utilizado el archivo se puede mostrar el usuario como si fuera un sistema secuencial.
Al finalizar un archivo secuencial se denota con una marca de fin de archivo. (End end-of-file)
El usuario de un archivo secuancial puede ver los registros en un orden secuancial simple.
La única forma de recuperar registros es comenzar al principio y extraerlos en el orden contemplado.
Cuestiones de programación; la manipulación de los archivos se hace en el contexto de la programación en un lenguaje por procedimientos de alto nivel. Estos lenguajes tienden a expresar la manipulación de archivos mediante subrutinas que se definen como parte del lenguaje formal o se incluyen como extensiones del lenguaje en una biblioteca estándar.
La mayor parte de los lenguajes por procedimiento de alto nivel cuenta con características que ayudan a detectar la marca de fin de archivo.
Archivos de texto
También conocidos como (Slream File) son utilizados para almacenar documentos que consisten en texto; En ellos, cada registro es un solo símbolo o código de control.
El leer estos archivos recibimos la información en orden secuencial en el que aparece cuando lo vemos en un monitor
Los archivos de texto son una secuencia de líneas separadas por marcas de fin de línea.
Rudimentos de los archivos de textos; El usuario escribe los archivos de textos mediante un procesador de palabras que le permitirá almacenar la información pero no estrictamente en forma secuencial.
El procesador también nos permite desplazarnos por todo el bloque de información y permitirnos realizar modificaciones.
Mientras el usuario avance rápidamente en la lectura de registro lograra ver mas archivos.
Cuestiones de programación; Casi todos los entornos de programación por procedimientos de alto nivel cuentan con subrutinas para manipular los archivos de texto.
Estas subrutinas pueden formar parte de la definición formal del lenguaje o que se ofrezca en biblioteca como extensiones del mismo.
Archivos indizados o indexados
Es la aplicación de incluir índices en el almacenamiento de los archivos; de esta forma nos será más fácil buscar algún registro sin necesidad de ver todo el archivo.
Un índice en un archivo consiste en un listado de los valores del campo clave que ocurren en el archivo, junto con la posición de registro correspondiente en el almacenamiento masivo.
Fundamento de los Índices
a.- La colocación de un listado al inicio del archivo: para la identificación del contenido.
b.- La presentación de un segundo índice: para reflejar la información de cada punto principal del índice anterior.
c.- La actualización de los índices: Cuando se insertan y eliminan archivos, es preciso actualizar los índices para evitar contratiempos actualizando un archivo.
d.- La organización de un índice: Nos evita examinar archivo por archivo para recuperar algún registro buscado; por lo tanto ahorraríamos tiempo si tenemos una adecuado organización de los índices.
Cuestiones de Programación
Algunos lenguajes de alto nivel cuentan con subtítulos para manipular los archivos de un registro indizado.
Valiéndose de las subrutinas es posible escribir programas sin tener que preocuparse por la estructura real del sistema de índices que se aplique.
Archivos dispersos
También llamados (Hashed Files) representan un sistema de almacenamiento de archivos que solo ofrece acceso directo, y permiten calcular la posición de un registro en el almacenamiento masivo.
Rudimentos de los archivos dispersos.
El usuario debe dividir el área de almacenamiento asignando al archivo en varias secciones llamadas cubetas para poder ingresar los datos.
La distribución de la información en las cubetas es problemática debido a que la estructura de los archivos es dispersa.
Dentro de los archivos se presentan colisiones de información debido al agrupamiento de los registros ingresados.
Cuestiones de programación.
Casi ninguno de los lenguajes de programación por procedimientos en la actualidad ofrece implantaciones directas de archivos dispersos; esto es debido a las cuestiones dependientes de la aplicación implicadas en el diseño de estos archivos.
Medidas para la utilización de los archivos
Para utilizar un archivo debemos tener en cuenta:
1. - Índice de Volatilidad; Un archivo es volátil cuando tiene un alto porcentaje de adiciones y supresiones debido al ingreso o eliminación de registros respecto al numero promedio de registros que haya en el archivo.
2. - Índice de Actividad; Un archivo es activo cuando tiene un alto porcentaje de utilidad sea de actualización o consulta en un periodo de tiempo fijo respecto al numero promedio de registro que se encuentran en el archivo.
El índice de actividad suele emplearse para saber si un archivo puede explotarse como una organización secuencial o relativa.
Archivos de acceso directo (con tipo)
Los archivos tipeados (con tipo), también llamados archivos binarios, contienen datos de tipo simple o estructurado, tales como integer, real , record, etc., excepto otro tipo de archivos.
Los archivos con tipos están estructurados en elementos o registros (record) cuyo tipo puede ser cualquiera. A los elementos de estos archivos se accede directamente, al no situarse éstos en posiciones físicamente consecutivas, sino en posiciones lógicas. Esta es la razón por la cual se les denomina archivos de acceso aleatorio o directo. Los elementos de los archivos aleatorios son de igual tamaño y el término acceso directo significa que es posible acceder directamente a un elemento con solo especificar su posición
A manera de resumen, presentamos las definiciones más utilizadas dentro del desarrollo de este tema:
Archivo (Fichero):
Conjunto de información estructurada en unidades de acceso denominada registro.
Registros.
Estructura de datos formada por uno o más elementos denominados "Campos" y estos pueden estar compuestos a su vez por "subcampos".
Claves:
Se denomina a un campo especial del registro que sirve para identificarlo
Bloque:
Es la cantidad de información que se transfiere en cada operación de lectura o escritura sobre un archivo.
Campo:
Es cada uno de los diferentes datos que constituyen un registro lógico.
LISTAS.
Objetivos:
Se busca distinguir una estructura secuencial y una estructura enlazada.
Definir el tipo abstracto de datos: ListaEnlazada
Aplicar la asignación dinámica de memoria para crear estructuras de información
Conocer las operaciones básicas de las listas enlazadas
Implementar una lista enlazada para un tipo de elemento
Realizar aplicaciones donde los datos se representan con una estructura lista
Definir una lista doblemente enlazada
Definir una lista circular
Implementar listas enlazadas ordenadas
Introducción
Al contrario que las estructuras de datos estáticos (arrays- listas, vectores, tablas- y estructuras) en las que su tamaño de memoria se establece durante la compilación y permanece inalterable durante la ejecución del programa, las estructuras de datos dinámicas crecen y se contraen a medida que se ejecuta el programa.
Fundamentos teóricos de las listas enlazadas
Los arrays han sido utilizados para implementar estructuras lineales de elementos homogéneos (listas, tablas, vectores) Esta técnica obliga a fijar por adelantado el espacio a ocupar en memoria, de modo que cuando se desea añadir un nuevo elemento que rebase el tamaño prefijado del array, no es posible realizar la operación sin que se produzca un error en tiempo de ejecución. Ello se debe a que los arrays hacen un uso ineficiente de la memoria. Gracias a la asignación dinámica de variables, se pueden implementar listas de modo que la memoria física utilizada se corresponda con el número de elementos de la tabla. Para ello se recurre a los punteros (apuntadores) que hacen un uso más eficiente de la memoria.
Una lista enlazada es una colección o secuencia de elementos dispuestos uno detrás de otro, en la que cada elemento se conecta al siguiente elemento por uno . La idea básica consiste en construir una lista cuyos elementos llamados nodos se componen de dos partes o campos: la primera parte o campo contiene la información y es, por consiguiente, un valor de un tipo genérico (denominado TpoElemento, Info, etc.) y la segunda parte o campo es un puntero denominado (enlace o sgte) que apunta al siguiente elemento de la lista.
La representación gráfica más extendida es aquella que utiliza una caja (un rectángulo) con dos secciones en su interior. En la primera sección se escribe el elemento o valor del dato, y en la segunda sección el enlace o puntero mediante una flecha que sale de la caja y apunta al nodo siguiente.
Una lista enlazada consta de un número de elementos y cada elemento tiene dos componentes (campos), un puntero al siguiente elemento de la lista y un valor, que puede ser de cualquier tipo.
Los enlaces se representan por flechas para facilitar la comprensión de la conexión entre dos nodos; ellos indica que el enlace tiene la dirección en memoria del siguiente nodo. Los enlaces también sitúan los nodos en una secuencia.
Clasificación de las listas enlazadas
Las litas se pueden dividir en cuatro categorías:
listas simplemente enlazadas. Cada nodo (Elemento) contiene un único enlace que conecta ese nodo al nodo siguiente o nodo sucesor. La lista es eficiente en recorridos directos
Listas doblemente enlazadas. Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor. La lista es eficiente tanto en recorrido directocomo en recorrido inverso
Lista circular simplemente enlazada. Una lista enlazada simplemente en la que el último elemento (cola) se enlaza al primer elemento (cabeza) de tal modo que la lista puede ser recorrida de modo circular
Lista circular doblemente enlazada. Una lista doblemente enlazada en la que el último elemento se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modo circular (en anillo) tanto en dirección directacomo inversa
Por cada uno de estos cuatro tipos de estructuras de listas se puede elegir una implementación basada en arrays o una implementación basada en punteros. De forma más específica según la forma de reservar memoria las implementaciones pueden hacerse con:
Asignación fija o estática, de memoria mediante arrays
Asignación dinámica de memoria mediante punteros o apuntadores
Una lista enlazada consta de un conjunto de nodos. Un nodo consta de un campo dato y un puntero alelemento de la lista.
Tipo abstracto de datos (TAD) lista
Una lista se utiliza para almacenar información del mismo tipo, con la característica de que puede contener un número indeterminado de elementos y que estos elementos mantienen un orden explícito. Este ordenamiento explícito se manifiesta en que cada elemento contiene en sí mismo la dirección del siguiente elemento.
Cada elemento de una lista se denomina nodo. En un nodo podemos considerar que hay dos campos, campo de información y campo de enlace o dirección del elemento siguiente.
A una lista enlazada se accede desde un puntero externo que contiene la dirección (referencia) del primer nodo de la lista. E campo de dirección o enlace del último elemento de la lista no debe apuntar a ningún elemento, no debe tener ninguna dirección, por lo que contiene un valor especial denominado puntero nulo (null).
La lista vacía, es aquella que no tiene nodos, tiene el puntero externo de acceso a la lista a nulo. Una lista es una estructura de daos dinámica. El número de nodos puede variar rápidamente en un proceso. Aumentando los nodos por inserciones, o bien disminuyendo por borrado de nodos.
Las inserciones se pueden realizar por cualquier punto de la lista. Así, pueden realizarse por el comienzo de la lista, por el final de la lista, a partir o antes de un nodo determinado. Las eliminaciones también se pueden realizar en cualquier punto de la lista, aunque generalmente se hacen dando el campo de información o dato que se desea eliminar.
Especificación formal del TADA lista
Matemáticamente, una lista es una secuencia de ceros o más elementos de un determinado tipo.
(a1, a2, a3 , … , an) siendo n>= 0, si n= 0 la lista es vacía
Los elementos de la lista tienen la propiedad de que sus elementos están ordenados de forma lineal, según las posiciones que ocupan en la misma. Se dice que ai, precede a ai+1 para i=1 …, n-1; y que ai sucede a ai+1 para i=2, …, n.
Para formalizar el tipo de datos abstracto lista a partir de la noción matemática, se define un conjunto de operaciones básicas con objetos de tipo lista. Las operaciones:
Listavacia (L) Inicializa la lista L como lista vacía.
Espacia(L) Operación que determina si la lista L está vacía.
Insertar (L,x,p) Inserta en la lista L un nodo con el campo dato x, delante del nodo de dirección p.
Localizar(L,x) Operación que devuelve la posición/dirección donde está el campo de información x.
Suprimir(L,x) Elimina de la lista el nodo que contiene el dato x.
Anterior(L,p) operación que devuelve la posición/dirección del nodo anterior a p.
Primero(L) Operación que devuelve la posición/dirección del primer nodo de la lista L.
Anula(L) Esta operación vacía la lista L.
Estas operaciones son las que pueden considerarse básica para manejar listas. En realidad, la decisión de qué operaciones son las básicas depende de las características del problema que se va a resolver También dependerá del tipo de representación elegido para las listas. Así, para añadir nuevos nodos a una lista se implementan, además de insertar(), versiones como:
insertarPrimero(L,x) Inserta un nodo con el dato x como primer nodo de la lista L.
inserFinal(L,x) Inserta un nodo con el dato x como ultimo nodo de la lista L.
Una operación típica de toda estructura enlazada es recorrer, consistente en visitar cada uno de los datos o nodos de que consta, en las listas enlazadas, normalmente se realiza desde el nodo cabeza al último nodo o cola de la lista.
Operaciones en listas enlazadas
Una lista enlazada requiere realizar la gestión de los elementos contenidos en ellas. Estos controles se manifiestan en forma de las operaciones básicas, especificadas al definir el tipo abstracto lista, que tendrán las siguientes funciones:
Declaración de los tipos nodos y puntero a nodo.
Inicialización o creación.
Insertar elementos en una lista.
Eliminar elementos de una lista.
Buscar elementos de una lista (Comprobar la existencia de elementos en una lista).
Recorrer una lista enlazada (visitar cada nodo de la lista).
Comprobar si la lista está vacía.
Declaración de un nodo
Una lista enlazada se compone de una serie de nodos enlazados mediante punteros. Cada nodo es una combinación de dos partes: un tipo de dato (entero, real, doble, carácter, o tipo predefinido) y un enlace (puntero) al siguiente nodo.
Puntero de cabecera y cola
Normalmente, los programas no declaran variables de nodos. En su lugar, cuando se construye y manipula una lista enlazada, a la lista se accede a través de uno o más punteros a los nodos. El acceso más frecuente a una lista enlazada es a través del primer nodo de la lista que se llama cabeza o cabecera de la lista. Un puntero al primer nodo se llama puntero cabeza, o simplemente L. En ocasiones, se mantiene también un puntero al último nodo de una lista enlazada. El último nodo es la cola de la lista, y un puntero al nodo es el puntero cola. También se pueden mantener punteros otros nodos de una lista enlazada. Cada puntero a un nodo debe ser declarado como una variable de puntero.
Acceso a una lista. La construcción y manipulación de una lista enlazada requiere el acceso a los nodos de la lista través de uno o más punteros a nodos. Normalmente, un programa incluye un puntero al primer nodo (cabeza) y un puntero al último nodo (cola)
En cualquier forma, el último elemento de la lista contiene un campo de enlace con valor 0, esto es, un puntero nulo (NULL) que señala el final de la lista.
El puntero nulo
La palabra NULL representa el puntero nulo, que es una constante especial. Se puede utilizar el puntero nulo para cualquier valor de puntero que no apunte a ningún sitio. El puntero nulo se utiliza, normalmente, en dos situaciones:
Usar el puntero nulo en el campo enlace o siguiente del nodo final de una lista enlazada.
Cuando analista enlazada no tiene ningún nodo, se utiliza el puntero NULL como puntero de cabeza y de cola. Tal lista se denomina lista vacía
El puntero de cabeza y de cola en una lista enlazada puede ser NULL, lo que indicará que la lista es vacía (no tiene nodos). Éste suele ser un método usual para construir una lista. Cualquier función que se escribe para manipular listas enlazadas debe poder manejar un puntero de cabeza y un puntero de cola nulos.
El operador -> de selección de un miembro
Si p es un puntero a una estructura y m es un miembro de la estructura, entonces p-> m accede al miembro m de la estructura apuntada por p.
El símbolo -> se considera como un operador simple (en vez de compuesto, al constar de dos símbolos independientes, -y>. Se denomina operador de selección de miembro o también operador de selección de componente. De modo visual el operador p-> m recuerda a una flecha que apunta del puntero p al objeto que contiene al miembro m.
Suponiendo que un programa ha de construir una lista enlazada y crear un puntero de cabecera ptr_cabeza a un nodo Nodo, el operador * de indirección aplicado a una variable puntero representa el contenido del nodo apuntado por ptr_cabeza. Es decir, *ptr_cabeza es un tipo de dato Nodo.
Precaución. Los paréntesis son necesarios alrededor de la primera parte de la expresión (*ptr_cabeza) ya que los operadores unitarios que aparecen a la derecha tienen prioridad más alta que los operadores unitarios que aparecen en el lado izquierdo (El asterisco de indirección).
Sin paréntesis, el significado de ptr_cabeza producirá un error de sintaxis, al intentar evaluar ptr_cabeza. Dato antes de la indirección o desreferencia.
P -> m significa lo mismo que (*p).m
Error. Uno de los errores típicos en el tratamiento de punteros es escribir la expresión *p o bien p-> cuando el valor del puntero p es el puntero nulo, ya que como se sabe el puntero nulo no apunta a nada.
Construcción de una lista
Una primera operación que se realiza con analista es asignar un valor inicial; éste es el de Lista vacía. Sencillamente consiste en asignar nulo al puntero de acceso a la lista.
Para añadir elementos a la lista se utiliza la operación insertar(), con sus diferentes versiones. También, para la creación de analista enlazada, se utiliza el siguiente algoritmo que entraña los siguientes pasos:
Paso 1. Declarar el tipo de dato y el puntero de cabeza o primero.
Paso 2. Asignar memoria para un elemento del tipo definido anteriormente utilizando alguna de las funciones de asignación de memoria(malloc(), calloc(), realloc()) y un cast para la conversión de void* al tipo puntero a nodo; la dirección del nuevo elemento es ptr_nuevo.
Paso 3. Crear iterativamente el primer elemento (Cabeza) y los elementos sucesivos de una lista enlazada simplemente.
Paso 4. Repetir hasta que no haya mas entradas para el elemento.
Inserción de un elemento en una lista
El algoritmo empleado para añadir o insertar un elemento en una lista enlazada varía dependiendo de la posición en que se desea insertar el elemento. La posición de inserción puede ser:
En la cabeza (elemento primero) de la lista.
En el final de la lista (elemento último).
Antes de un elemento especificado.
Después de un elemento especificado.
Inserta un nuevo elemento en la cabeza de una lista
Aunque normalmente se insertan nuevos datos al final de una estructura de datos, es más fácil y más eficiente insertar un elemento nuevo en la cabeza de analista. El proceso de inserción se puede resumir en este algoritmo:
Asignar un nuevo nodo apuntado por nuevo, que es una variable puntero local que apunta al nuevo nodo que se va a insertar en la lista.
Simular el nuevo elemento en el campo dato del nuevo nodo.
Hacer que el campo enlace siguiente del nuevo nodo apunte a la cabeza (primer nodo) de la lista original.
Hacer que cabeza (puntero cabeza) apunte al nuevo nodo que se ha creado.
Inserción de un nodo al final de la lista
La inserción al final de la lista es menos eficiente debido a que, normalmente, no e tiene un puntero al último elemento de la lista y entonces se ha de seguir la traza desde la cabeza de la lista hasta el último nodo de la lista ya continuación realizar la inserción. Cuando ultimo es una variable puntero que apunta a último nodo de la lista, las sentencias siguientes insertan un nodo al final de la lista.
Ultimo -> siguiente = crearNodo(x);
Ultimo -> siguiente -> siguiente = NULL;
Ultimo = ultimo -> siguiente;
La primera sentencia crea un nuevo nodo, llamada a crearNodo(), y se asigna al campo siguiente del último nodo de la lista (antes de la inserción) de modo que el nuevo nodo ahora es el último. La segunda sentencia establece el campo siguiente del nuevo último nodo a NULL. Y la última sentencia pone la variable ultimo al nuevo último nodo de la lista.
La función inserFinal() tiene como entrada el puntero cabeza, recorre la lista hasta situarse al final y realiza la inserción. Se tiene en cuenta la circunstancia de que la lista este vacía, en cuyo caso inserta el nuevo nodo como nodo primero y único.
Inserción de un nodo entre dos nodos de la lista
La inserción de un nuevo nodo no siempre se realiza al principio (en cabeza) de la lista o al final se puede insertar entre dons nodo cualesquiera de la lista.
El algoritmo de la nueva operación insertar requiere las siguientes etapas:
1. Asignar el nuevo nodo, con el campo dato, apuntado por el puntero nevo.
2. Hacer que el campo en lace siguiente del nuevo nodo apunte al nodo que va después de la posición que se desea para el nuevo nodo (o bien a NULL, si no hay ningún nodo después de la nueva posición).
3. En la variable puntero anterior tener la dirección del nodo que está antes de la posición deseada para el nuevo nodo. Hacer que anterior-> siguiente apunte al nuevo nodo que se acaba de crear.
Para llamar a la función insertar(), previamente se ha de buscar la dirección del nodo anterior y asegurarse de que la lista no está vacía, ni que se quiere insertar como primer nodo.
Una versión de la función tiene como argumentos la dirección de inicio de la lista, cabeza, el campo dato a partir del cual se inserta y el dato del nuevo nodo.
El algoritmo de esta versión de la operación insertar requiere las siguientes etapas:
1. Asignar el nuevo nodo, con el campo dato, apuntado por el puntero nuevo.
2. Buscar la dirección del nodo, después, que contiene el campo dato a partir del cual se ha de insertar.
3. Hacer que el campo enlace siguiente del nuevo nodo apunte al nodo que va a continuación de la posición que se desea para el nuevo nodo (o bien NULL si no hay ningún nodo).
4. Hacer que después -> siguiente apunte al nuevo nodo que se acaba de crear.
La primera comprobación, previa a las etapas a seguir, es que la lista esté vacía. Si es así se inserta como primer nodo. También se tiene que tener precaución en la búsqueda que se realiza en la etapa 2, ésta puede ser negativa, no se encuentra el dato; entonces no se inserta el nuevo nodo.
Búsqueda den listas enlazadas
La función localizar() utiliza una variable puntero denominada indice que va recorriendo la lista nodo a nodo .Mediante un bucle, indice apunta a los nodos de la lista de modo que si se encuentra el nodo buscado, se devuelve un puntero al nodo con la sentencia de retorno (Return); en elcaso de no encontrarse el nodo buscado la función debe devolver NULLL (return NULL). El nodo que se busca es el que tiene un campo dato que coincide con una clave.
A tener en cuenta. La operación de búsqueda puede tener diferentes enfoques: búsqueda de la posición del primer nodo que contiene un dato, búsqueda de la posición de un nodo según el número de orden, determinación si existe o no un nodo con un campo dato determinado.
Eliminación de un nodo en una lista
La operación de eliminar (borrar) un nodo de una lista enlazada supone enlazar el nodo anterior con el nodo siguiente al que se desea eliminar y liberar la memoria que ocupa.
El algoritmo para eliminar un nodo que contiene un dato se puede expresar en estos pasos o etapas:
1. Búsqueda del nodo que contiene el dato (se ha de tener la dirección del nodo a eliminar y la dirección del anterior).
2. El puntero siguiente del nodo anterior ha de apuntar al siguiente del nodo a eliminar.
3. En caso de que el nodo a eliminar sea el primero, cabeza, se modifica cabeza para que tenga la dirección del nodo siguiente.
4. Por ultimo, se libera la memoria ocupada por el nodo.
Lista doblemente enlazada
Hasta ahora el recorrido de una lista se realizaba en sentido directo (adelante) o, en algunos casos en sentido inverso (hacia atrás). Sin embargo, existen numerosas aplicaciones en las que es conveniente poder acceder a los elementos o nodos de analista en cualquier orden. En este caso se recomienda el uso de una lista doblemente enlazada. En al lista, cada elemento contiene dos punteros, aparte del valor almacenado en el elemento. Un puntero apunta al siguiente elemento de la lista y el otro apunta al elemento anterior.
Las operaciones básicas que se definen en el tipo abstracto Lista doble son básicamente las mismas que las definidas en una lista simple y tendrán las siguientes funciones:
Declaración de los tipos nodo y puntero a nodo.
Inicialización o creación.
Insertar elementos en una lista.
Eliminar elementos de una lista.
Buscar elementos de una lista (comprobar la existencia de elementos en una lista).
Recorrer una lista enlazada (visitar cada nodo de la lista).
Comprobar si la lista está vacía.
Cabeza
Existe una operación de insertar y eliminar (borrar) en cada dirección.
Insertar un elemento en una lista doblemente enlazada
El algoritmo empleado para añadir o insertar un elemento en una lista doble varía dependiendo de la posición en que se desea insertar el elemento. La posición de inserción puede ser:
En la cabeza (elemento primero) de la lista.
En el final de la lista (elemento último).
Antes de un elemento especificado.
Después de un elemento especificado.
Insertar un nuevo elemento en la cabeza de una lista doble
El proceso de inserción se puede resumir en este algoritmo:
Asignar un nuevo nodo el campo dato (Info) apuntado por nuevo que es una variable puntero local que a su vez apunta al nuevo nodo que se va a insertar en la lista doble.
Hacer que el campo enlace adelante del nuevo nodo apunte a la cabeza (primer nodo) de la lista original, y que el campo enlace atrás del nodo cabeza apunte al nuevo nodo.
Hacer que cabeza (puntero cabeza) apunte al nuevo nodo que se ha creado.
En este momento, la función de insertar un elemento en la lista termina su ejecución, la variable local nuevo desaparece y sólo permanece el puntero de cabeza, cabeza, que apunta a la nueva lista doblemente enlazada.
Inserción de un nuevo nodo que no está en la cabeza de la lista
La inserción de un nuevo nodo en una lista doblemente enlazada se puede realizar en un nodo intermedio de ella. El algoritmo de la nueva operación insertar requiere las siguientes etapas:
1. Asignar el nuevo nodo el campo dato(Info) apuntado por el puntero nuevo.
2. Hacer que el campo enlace adelante del nuevo nodo apunte al nodo que va después de la posición del nuevo nodo (o bien a NULL si no hay ningún nodo después de la nueva posición). El campo atrás del nodo siguiente al nuevo tiene que apuntar a nuevo.
3. La dirección del nodo que está antes de la posición deseada para el nuevo nodo está en la variable puntero anterior. Hacer que anterior-> adelante apunte al nuevo nodo. El enlace atrás del nuevo nodo debe de apuntar a anterior.
En la función que se escribe a continuación, se tiene en cuenta que la inserción sea en una lista vacía en cuyo caso cabeza es NULL, o que sea como primer nodo. De igual forma se contempla que la inserción sea como último nodo.
Eliminación de un elemento en una lista doblemente enlazada
La operación de eliminar un nodo de una lista doble supone realizar el enlace de dos punteros: el nodo anterior con el nodo siguiente al que se desea eliminar, con el putero adelante; y el nodo siguiente con el anterior, con el puntero atrás, y liberar la memoria que ocupa.
El algoritmo para eliminar un nodo que contiene un dato es similar al algoritmo de eliminación en una lista simple. Ahora la dirección del nodo anterior se encuentra en el puntero atrás del nodo a eliminar o borrar. Los pasos a seguir:
1. Búsqueda del nodo que contiene el dato. Se ha de tener la dirección del nodo a eliminar y la dirección del anterior.
2. El punto adelante del nodo anterior tiene que apuntar al puntero adelante del nodo a eliminar (en el caso de no ser el nodo cabecera).
3. El puntero atrás del nodo siguiente a eliminar debe apuntar al puntero atrás del nodo a eliminar (en el caso de no ser el nodo último).
4. En caso de que el nodo a eliminar sea el primero, cabeza; se modifica cabeza para que tenga la dirección del nodo siguiente.
5. Por último, se libera la memoria ocupada por el nodo.
Listas circulares
En las listas lineales simples o en las dobles siempre hay un primer nodo y un último nodo que tiene el campo de enlace a nulo. Una lista circular, por propia naturaleza no tiene ni principio ni fin. Sin embargo, resulta útil establecer un nodo a partir del cual se acceda a la lista y así poder acceder a sus nodos.
Las operaciones que se realizan sobre una lista circular son similares a las operaciones sobre listas lineales, teniendo en cuenta que el último nodo no apunta anulo sino al primero. Estas operaciones permiten construir el TAD Lista circular y su funcionalidad:
Declaración de los tipos nodo y puntero a nodo.
Inicialización o creación.
Insertar elementos en una lista circular.
Eliminar elementos de una lista circular.
Buscar elementos de una lista circular.
Recorrer o visitar cada nodo de la lista circular.
Comprobar si la lista está vacía.
La creación de una lista circular se puede hacer con un enlace simple o enlace. Considerando que la lista circular se enlaza con un solo enlace, la realización con enlace adelante y atrás es similar.
A tener en cuenta. El puntero de acceso a una lista circular, normalmente apunta al último nodo añadido a la estructura. Esta convención puede cambiar ya que en una estructura circular no hay primero ni último.
Insertar un elemento en una lista circular
El algoritmo empleado para añadir o insertar un elemento en una lista circular vacía dependiendo de la posición en que se desea insertar el elemento. La posición de inserción puede variar, consideramos que se hace como nodo anterior al nodo de acceso a la lista y tiene la dirección del último nodo insertado.
Eliminar un elemento en una lista circular
La operación de eliminar un nodo de una lista circular sigue los mismos pasos que los dados para eliminar un nodo en una lista lineal. Hay que enlazar el nodo anterior con el nodo siguiente al que se desea eliminar y liberar la memoria que ocupa.
El algoritmo para eliminar un nodo de una lista circular es:
Búsqueda del nodo que contiene el dato.
Se enlaza el nodo anterior con el siguiente.
En caso de que el nodo a eliminar sea el referenciado por el puntero de acceso a la lista, se modifica para que tenga la dirección del nodo anterior.
Por último, se libera la memoria ocupada por el nodo.
En la función eliminar hay que tener en cuenta la característica de lista circular; así, para detectar si la lista es de un solo nodo se pregunta si se apunta al mismo.
RESUMEN
La estructura de daos lista se puede implementar, bien como un array, bien como una lista enlazada. Una lista enlazada es una estructura de datos dinámica en la que sus componentes están ordenados lógicamente por sus campos punteros en vez de ordenados físicamente como están en un arrary. El final de la lista se señala mediante una constante o puntero especial llamado NULL.
La gran ventaja de analista enlazada sobre un array es que la lista enlazada puede crecer y decrecer en tamaño, ajustándose al número de elementos.
Una lista simplemente enlazada contiene sólo un enlace a un sucesor único, a menos que sea el último, en cuyo caso no se enlaza con ningún otro nodo.
Cuando se inserta un elemento en una lista enlazada, se deben considerar cuatro casos: añadir a una lista vacía, añadir al principio de la lista, añadir en el interior y añadir al final de la lista.
Para borrar (eliminar) un elemento, primero hay que buscar el nodo que los contiene y considerar dos casos: borrar el primer nodo y borrar cualquier otro de la lista.
El recorrido de una lista enlazada significa pasar por cada nodo (visitar) y procesarlo. El proceso puede ser: escribir su contenido o modificar el campo de datos.
Una lista doblemente enlazada es aquella en la que cada nodo tiene un puntero a su sucesor y otro a su predecesor. Las listas doblemente enlazadas se pueden recorrer en ambos sentidos. Las operaciones básicas son inserción, eliminación y recorrido de la lista: similares a las listas simples.
Una lista enlazada circularmente por propia naturaleza no tiene primero ni último nodo. Las listas circulares puedes ser de enlace simple o doble.
4.- Guía de Estructura y Procesamiento de Datos, Autor Profesor David López, Segundo semestre U.N.I.R. (Maracaibo).
¿Qué son los archivos?
Los archivos también denominados ficheros (file); es una colección de información (los datos relacionados entre sí), localizada o almacenada como una unidad en alguna parte de la misma computadora.
A modo de otra definición, los archivos son el conjunto organizado de informaciones del mismo tipo, que pueden utilizarse en un mismo tratamiento; como soporte material de estas informaciones.
Breve introducción a los archivos
Los archivos como colección de datos sirve para la entrada y salida a la computadora y son manejados con diferentes 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, él 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).
Principales características de los archivos DE LOS ARCHIVOS
Las principales características de este tipo de estructuras son:
Independencia de las informaciones respecto de los programas
La información almacenada es permanente
Un archivo puede ser accedido por distintos programas en distintos momentos
Gran capacidad de almacenamiento
Clasificación de los archivos
Los archivos se clasifican según su uso en tres grandes grupos:
Permanentes o Maestros:
Estos contienen información que varia poco. En algunos casos es preciso actualizarlos periódicamente.
De Movimientos
Se cercan para actualizar los archivos maestros. Sus registros son de tres tipos: alta, bajas y modificaciones.
De Maniobra o Trabajo.
Tienen una vida limitada, normalmente menor que la duración de la ejecución de un programa. Su utilizan como auxiliares de los anteriores.
Distintos 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 cuyo registros sufren pocas o ninguna variación a lo largo del tiempo, se dividen en:
Constantes: Están formados por registros que contienen campos fijos y campos de baja frecuencia de variación en el tiempo.
De Situación: Son los que en cada momento contienen información actualizada.
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 Movimiento
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 experimentados por los mismos.
c.- Archivo de Maniobra o Transitorio
Son los archivos creados auxiliares creados durante la ejecución del programa y borrados habitualmente al terminar el mismo.
Según sus elementos
Los principales archivos de este tipo son:
Archivo de Entrada: Una colección de datos localizados en un dispositivo de entrada.
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.
De Situación: son los que en cada momento contienen información actualizada.
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.
Archivos de movimiento 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 experimentados por los mismos.
Archivos de Maniobra o Transitorios: Son los archivos auxiliares creados durante la ejecución del programa y borrados habitualmente al terminar el mismo.
Según sus elementos
Los principales archivos de este tipo son:
Archivo de Entrada, una colección de datos localizada en un dispositivo de entrada.
Archivo de Salida, una colección de información visualizada por la computadora
Archivo de Programa, un programa codificado en un lenguaje especifico y localizado o almacenado en un dispositivo de almacenamiento
Archivo de Texto, una colección de caracteres almacenados como una unidad en un dispositivo de almacenamiento.
El acceso a los archivos
Se refiere al método utilizado para acceder a los registros de un archivo prescindiendo de su organización. Existen distintas formas de acceder a los datos:
Secuenciales; los registros se leen desde el principio hasta el final del archivo, de tal forma que para leer un registro se leen todos los que preceden.
Directo; cada registro puede leerse / escribirse de forma directa solo con expresar su dirección en el fichero por él numero relativo del registro o por transformaciones de la clave de registro en él numero relativo del registro a acceder.
Por Índice; se accede indirectamente a los registros por su clave, mediante consulta secuenciales a una tabla que contiene la clave y la dirección relativa de cada registro, y posterior acceso directo al registro.
Dinámico; es cuando se accede a los archivos en cualquier de los modos anteriormente citados.
La elección del método esta directamente relacionada con la estructura de los registros del archivo y del soporte utilizado.
Los tipos de accesos
Acceso Secuencial. Exige el tratamiento de elemento, para esto es necesario una exploración secuencial comenzando desde el primer momento
Secuenciales: archivo de texto que debe ser leído del principio hasta el final.
Acceso Directo. Permite procesar o acceder a un elemento determinado y referencia directamente por su posición en el soporte de almacenamiento
Aleatorios: es un archivo con registros de un mismo largo. Un programa puede accesar directamente cualquier registro sin tener que leer los registros previos.
Binarios: es un archivo que lee byte por byte sin asumir ninguna estructura. Los archivos Binarios no son un nuevo tipo de archivo, pero si una nueva forma de manipular cualquier tipo de archivo. Las técnicas de archivo binarios permiten leer o cambiar cualquier byte de un archivo. Son herramientas extremadamente potentes, pero como toda herramienta potente debe manejarse con cuidado
Instrucciones para manejar archivos
OPEN: reserva un espacio del buffer para la data que moverá entre el programa y los archivos.
La estructura es:
OPEN filespec FOR {AppendBinaryInputOutuputRandom} As #filenumber
Por ejemplo:
OPEN "C:\Windows\AddrBook.ini" FOR Input As #1
Filespec: Es la localización de archivo en el que se trabajará, incluyendo usualmente el drive y path.
"C:\Windows\AddrBook.ini"
{Append Binary Input Outuput Random} El programador tiene que seleccionar uno. Binary y Random se utiliza para archivos binarios y aleatorios. Append, Input y Output son usados con archivos secuenciales. Un archivo secuencial no puede ser abierto para leer y escribir simultaneamente. Output es usado para escribir en el archivo. Input es usado para leer del archivo. Append es usado para colocar data al final de un archivo exitente.
#filenumber: es necesario asignar un número al archivo. El número puede estar en el rango de #1 a #511 y es usado por Visual Basic para identificar el archivo.
CLOSE: para cerrar un archivo.
La estructura es:
CLOSE #filenumber
Por ejemplo:
CLOSE #1
WRITE: envia data del programa al archivo secuencial.
La estructura es: WRITE #filenumber, [OutputList]
Por ejemplo:
WRITE #1, UserName, UserCompany, SerialNumber
WRITE es la operación opuesta al INPUT. Las expresiones en el OutputList son separadas por comas. WRITE inserta comillas y comas a la data que envia al archivo.
INPUT: lee data del archivo. La estructura es:
INPUT #filenumber, InputList
Por ejemplo:
INPUT #1, UserName, UserCompany, SerialNumber
Declaración y asignación de archivos
La declaración de un archivo con tipo se efectúa con la ayuda de las palabras reservadas file of.
El procedimiento de asignación es idéntico al utilizado anteriormente.
Ejemplo:
Type
datos = record
clave : integer;
nombre : string[30];
puesto : string[20];
sueldo : real;
estado : boolean;
{true activo,false baja lógica}
end;
Var
archivo:file of datos;
begin
Assign(archivo,'empleado.dat');
El sistema de manejo de archivos
Tiene las siguientes funciones:
Controla los datos en almacenamiento secundario
Proporciona al usuario una abstracción de cómo se manipulan los datos internamente.
Proporciona independencia de E/S con los dispositivos
Soporte de compartición, protección, recuperación de archivos y posibles caídas del sistema.
Transmisión de datos de memoria principal a secundaria.
Por ejemplo, los archivos de una empresa pueden almacenarse en diferentes dispositivos. Todos los archivos se pueden almacenar por medio de directorios, que no son otra cosa más que tablas de símbolos de archivo, los directorios se pueden utilizar de dos formas:
DIRECTORIO DE NIVEL ÚNICO O DIRECTORIO PLANO
Con este método, se almacenan todos los archivos en un solo nivel, este método en sistemas donde el volumen de archivos no es grande.
DIRECTORIO JERARQUICO
Los archivos son almacenados por medio de directorios, esta clasificación se de acuerdo a la conveniencia del usuario o de la empresa.
La estructura tiene una forma de árbol con raíz, este método es el más utilizado debido a que la revisión o búsqueda se realiza de forma sencilla.
Para accesar a los archivos que se almacenan en un sistema jerárquico, el usuario debe indicar el o los directorios que se deben recorrer para localizar el archivo deseado, a esto se le denomina ruta de acceso del archivo.
La ruta de acceso puede ser de dos formas:
Ruta absoluta.- Este tipo de ruta de acceso inicia siempre con una diagonal invertida
C:\Edit c:\SOS\sistemas\report.txt
Ruta relativa.- Este tipo de ruta de acceso realiza la búsqueda del archivo en el directorio de trabajo actual, si el archivo no se localiza aquí, el S.O. lo buscará en los directorios especificados en el PATH de un archivo con extensión .BAT.
C:\Edit report.txt
Operaciones generales que se realizan sobre un archivo
Las operaciones generales que se realizan son:
Creación.
Escritura de todos sus registros.
Consulta.
Lectura de todos sus registros.
Actualización.
Inserción supresión o modificación de algunos de sus registros
Clasificación.
Reubicación de los registros de tal forma que queden ordenados según determinados criterios.
Borrado.
Eliminando total del archivo, dejando libre el espacio del soporte que ocupaba.
Organización de los archivos
Los archivos se encuentran organizados lógicamente como una secuencia de registros de varias longitudes diferentes.
Los archivos de registros de longitud fija: son los que almacenan la información en los archivos mediante un encabezado y luego se introducen uno a uno los registros ubicados en posiciones consecutivas.
Los registros de longitud variable: es el almacenamiento de registros de varios tipos en un archivo y permite uno o más campos de longitudes variables y dichos campos pueden ser repetidos. La longitud de los registros debe estar definida correctamente para poder leer y escribir de forma efectiva.
Enfoques generales para la organización de archivos
Los enfoques son:
1. - Enfoque de acceso secuencial: Se refiere al procesamiento de los archivos de acuerdo con el orden especifico. Ejemplo archivo secuenciales y de texto
2. - Enfoque de acceso Directo Permite recuperar registros individuales sin leer otros registros del archivo, ejemplos archivos indizados.
Archivos secuenciales
Se refiere al procesamiento de los registros, no importa el orden en que se haga, para eso los registros están organizados en forma de una lista y recuperarlos y procesarlos uno por uno de principio a fin.
Rudimentos de los archivos Secuenciales; dependiendo del dispositivo de almacenamiento utilizado el archivo se puede mostrar el usuario como si fuera un sistema secuencial.
Al finalizar un archivo secuencial se denota con una marca de fin de archivo. (End end-of-file)
El usuario de un archivo secuancial puede ver los registros en un orden secuancial simple.
La única forma de recuperar registros es comenzar al principio y extraerlos en el orden contemplado.
Cuestiones de programación; la manipulación de los archivos se hace en el contexto de la programación en un lenguaje por procedimientos de alto nivel. Estos lenguajes tienden a expresar la manipulación de archivos mediante subrutinas que se definen como parte del lenguaje formal o se incluyen como extensiones del lenguaje en una biblioteca estándar.
La mayor parte de los lenguajes por procedimiento de alto nivel cuenta con características que ayudan a detectar la marca de fin de archivo.
Archivos de texto
También conocidos como (Slream File) son utilizados para almacenar documentos que consisten en texto; En ellos, cada registro es un solo símbolo o código de control.
El leer estos archivos recibimos la información en orden secuencial en el que aparece cuando lo vemos en un monitor
Los archivos de texto son una secuencia de líneas separadas por marcas de fin de línea.
Rudimentos de los archivos de textos; El usuario escribe los archivos de textos mediante un procesador de palabras que le permitirá almacenar la información pero no estrictamente en forma secuencial.
El procesador también nos permite desplazarnos por todo el bloque de información y permitirnos realizar modificaciones.
Mientras el usuario avance rápidamente en la lectura de registro lograra ver mas archivos.
Cuestiones de programación; Casi todos los entornos de programación por procedimientos de alto nivel cuentan con subrutinas para manipular los archivos de texto.
Estas subrutinas pueden formar parte de la definición formal del lenguaje o que se ofrezca en biblioteca como extensiones del mismo.
Archivos indizados o indexados
Es la aplicación de incluir índices en el almacenamiento de los archivos; de esta forma nos será más fácil buscar algún registro sin necesidad de ver todo el archivo.
Un índice en un archivo consiste en un listado de los valores del campo clave que ocurren en el archivo, junto con la posición de registro correspondiente en el almacenamiento masivo.
Fundamento de los Índices
a.- La colocación de un listado al inicio del archivo: para la identificación del contenido.
b.- La presentación de un segundo índice: para reflejar la información de cada punto principal del índice anterior.
c.- La actualización de los índices: Cuando se insertan y eliminan archivos, es preciso actualizar los índices para evitar contratiempos actualizando un archivo.
d.- La organización de un índice: Nos evita examinar archivo por archivo para recuperar algún registro buscado; por lo tanto ahorraríamos tiempo si tenemos una adecuado organización de los índices.
Cuestiones de Programación
Algunos lenguajes de alto nivel cuentan con subtítulos para manipular los archivos de un registro indizado.
Valiéndose de las subrutinas es posible escribir programas sin tener que preocuparse por la estructura real del sistema de índices que se aplique.
Archivos dispersos
También llamados (Hashed Files) representan un sistema de almacenamiento de archivos que solo ofrece acceso directo, y permiten calcular la posición de un registro en el almacenamiento masivo.
Rudimentos de los archivos dispersos.
El usuario debe dividir el área de almacenamiento asignando al archivo en varias secciones llamadas cubetas para poder ingresar los datos.
La distribución de la información en las cubetas es problemática debido a que la estructura de los archivos es dispersa.
Dentro de los archivos se presentan colisiones de información debido al agrupamiento de los registros ingresados.
Cuestiones de programación.
Casi ninguno de los lenguajes de programación por procedimientos en la actualidad ofrece implantaciones directas de archivos dispersos; esto es debido a las cuestiones dependientes de la aplicación implicadas en el diseño de estos archivos.
Medidas para la utilización de los archivos
Para utilizar un archivo debemos tener en cuenta:
1. - Índice de Volatilidad; Un archivo es volátil cuando tiene un alto porcentaje de adiciones y supresiones debido al ingreso o eliminación de registros respecto al numero promedio de registros que haya en el archivo.
2. - Índice de Actividad; Un archivo es activo cuando tiene un alto porcentaje de utilidad sea de actualización o consulta en un periodo de tiempo fijo respecto al numero promedio de registro que se encuentran en el archivo.
El índice de actividad suele emplearse para saber si un archivo puede explotarse como una organización secuencial o relativa.
Archivos de acceso directo (con tipo)
Los archivos tipeados (con tipo), también llamados archivos binarios, contienen datos de tipo simple o estructurado, tales como integer, real , record, etc., excepto otro tipo de archivos.
Los archivos con tipos están estructurados en elementos o registros (record) cuyo tipo puede ser cualquiera. A los elementos de estos archivos se accede directamente, al no situarse éstos en posiciones físicamente consecutivas, sino en posiciones lógicas. Esta es la razón por la cual se les denomina archivos de acceso aleatorio o directo. Los elementos de los archivos aleatorios son de igual tamaño y el término acceso directo significa que es posible acceder directamente a un elemento con solo especificar su posición
A manera de resumen, presentamos las definiciones más utilizadas dentro del desarrollo de este tema:
Archivo (Fichero):
Conjunto de información estructurada en unidades de acceso denominada registro.
Registros.
Estructura de datos formada por uno o más elementos denominados "Campos" y estos pueden estar compuestos a su vez por "subcampos".
Claves:
Se denomina a un campo especial del registro que sirve para identificarlo
Bloque:
Es la cantidad de información que se transfiere en cada operación de lectura o escritura sobre un archivo.
Campo:
Es cada uno de los diferentes datos que constituyen un registro lógico.
LISTAS.
Objetivos:
Se busca distinguir una estructura secuencial y una estructura enlazada.
Definir el tipo abstracto de datos: ListaEnlazada
Aplicar la asignación dinámica de memoria para crear estructuras de información
Conocer las operaciones básicas de las listas enlazadas
Implementar una lista enlazada para un tipo de elemento
Realizar aplicaciones donde los datos se representan con una estructura lista
Definir una lista doblemente enlazada
Definir una lista circular
Implementar listas enlazadas ordenadas
Introducción
Al contrario que las estructuras de datos estáticos (arrays- listas, vectores, tablas- y estructuras) en las que su tamaño de memoria se establece durante la compilación y permanece inalterable durante la ejecución del programa, las estructuras de datos dinámicas crecen y se contraen a medida que se ejecuta el programa.
Fundamentos teóricos de las listas enlazadas
Los arrays han sido utilizados para implementar estructuras lineales de elementos homogéneos (listas, tablas, vectores) Esta técnica obliga a fijar por adelantado el espacio a ocupar en memoria, de modo que cuando se desea añadir un nuevo elemento que rebase el tamaño prefijado del array, no es posible realizar la operación sin que se produzca un error en tiempo de ejecución. Ello se debe a que los arrays hacen un uso ineficiente de la memoria. Gracias a la asignación dinámica de variables, se pueden implementar listas de modo que la memoria física utilizada se corresponda con el número de elementos de la tabla. Para ello se recurre a los punteros (apuntadores) que hacen un uso más eficiente de la memoria.
Una lista enlazada es una colección o secuencia de elementos dispuestos uno detrás de otro, en la que cada elemento se conecta al siguiente elemento por un
La representación gráfica más extendida es aquella que utiliza una caja (un rectángulo) con dos secciones en su interior. En la primera sección se escribe el elemento o valor del dato, y en la segunda sección el enlace o puntero mediante una flecha que sale de la caja y apunta al nodo siguiente.
Una lista enlazada consta de un número de elementos y cada elemento tiene dos componentes (campos), un puntero al siguiente elemento de la lista y un valor, que puede ser de cualquier tipo.
Los enlaces se representan por flechas para facilitar la comprensión de la conexión entre dos nodos; ellos indica que el enlace tiene la dirección en memoria del siguiente nodo. Los enlaces también sitúan los nodos en una secuencia.
Clasificación de las listas enlazadas
Las litas se pueden dividir en cuatro categorías:
listas simplemente enlazadas. Cada nodo (Elemento) contiene un único enlace que conecta ese nodo al nodo siguiente o nodo sucesor. La lista es eficiente en recorridos directos
Listas doblemente enlazadas. Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor. La lista es eficiente tanto en recorrido directo
Lista circular simplemente enlazada. Una lista enlazada simplemente en la que el último elemento (cola) se enlaza al primer elemento (cabeza) de tal modo que la lista puede ser recorrida de modo circular
Lista circular doblemente enlazada. Una lista doblemente enlazada en la que el último elemento se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modo circular (en anillo) tanto en dirección directa
Por cada uno de estos cuatro tipos de estructuras de listas se puede elegir una implementación basada en arrays o una implementación basada en punteros. De forma más específica según la forma de reservar memoria las implementaciones pueden hacerse con:
Asignación fija o estática, de memoria mediante arrays
Asignación dinámica de memoria mediante punteros o apuntadores
Una lista enlazada consta de un conjunto de nodos. Un nodo consta de un campo dato y un puntero al
Tipo abstracto de datos (TAD) lista
Una lista se utiliza para almacenar información del mismo tipo, con la característica de que puede contener un número indeterminado de elementos y que estos elementos mantienen un orden explícito. Este ordenamiento explícito se manifiesta en que cada elemento contiene en sí mismo la dirección del siguiente elemento.
Cada elemento de una lista se denomina nodo. En un nodo podemos considerar que hay dos campos, campo de información y campo de enlace o dirección del elemento siguiente.
A una lista enlazada se accede desde un puntero externo que contiene la dirección (referencia) del primer nodo de la lista. E campo de dirección o enlace del último elemento de la lista no debe apuntar a ningún elemento, no debe tener ninguna dirección, por lo que contiene un valor especial denominado puntero nulo (null).
La lista vacía, es aquella que no tiene nodos, tiene el puntero externo de acceso a la lista a nulo. Una lista es una estructura de daos dinámica. El número de nodos puede variar rápidamente en un proceso. Aumentando los nodos por inserciones, o bien disminuyendo por borrado de nodos.
Las inserciones se pueden realizar por cualquier punto de la lista. Así, pueden realizarse por el comienzo de la lista, por el final de la lista, a partir o antes de un nodo determinado. Las eliminaciones también se pueden realizar en cualquier punto de la lista, aunque generalmente se hacen dando el campo de información o dato que se desea eliminar.
Especificación formal del TADA lista
Matemáticamente, una lista es una secuencia de ceros o más elementos de un determinado tipo.
(a1, a2, a3 , … , an) siendo n>= 0, si n= 0 la lista es vacía
Los elementos de la lista tienen la propiedad de que sus elementos están ordenados de forma lineal, según las posiciones que ocupan en la misma. Se dice que ai, precede a ai+1 para i=1 …, n-1; y que ai sucede a ai+1 para i=2, …, n.
Para formalizar el tipo de datos abstracto lista a partir de la noción matemática, se define un conjunto de operaciones básicas con objetos de tipo lista. Las operaciones:
Listavacia (L) Inicializa la lista L como lista vacía.
Espacia(L) Operación que determina si la lista L está vacía.
Insertar (L,x,p) Inserta en la lista L un nodo con el campo dato x, delante del nodo de dirección p.
Localizar(L,x) Operación que devuelve la posición/dirección donde está el campo de información x.
Suprimir(L,x) Elimina de la lista el nodo que contiene el dato x.
Anterior(L,p) operación que devuelve la posición/dirección del nodo anterior a p.
Primero(L) Operación que devuelve la posición/dirección del primer nodo de la lista L.
Anula(L) Esta operación vacía la lista L.
Estas operaciones son las que pueden considerarse básica para manejar listas. En realidad, la decisión de qué operaciones son las básicas depende de las características del problema que se va a resolver También dependerá del tipo de representación elegido para las listas. Así, para añadir nuevos nodos a una lista se implementan, además de insertar(), versiones como:
insertarPrimero(L,x) Inserta un nodo con el dato x como primer nodo de la lista L.
inserFinal(L,x) Inserta un nodo con el dato x como ultimo nodo de la lista L.
Una operación típica de toda estructura enlazada es recorrer, consistente en visitar cada uno de los datos o nodos de que consta, en las listas enlazadas, normalmente se realiza desde el nodo cabeza al último nodo o cola de la lista.
Operaciones en listas enlazadas
Una lista enlazada requiere realizar la gestión de los elementos contenidos en ellas. Estos controles se manifiestan en forma de las operaciones básicas, especificadas al definir el tipo abstracto lista, que tendrán las siguientes funciones:
Declaración de los tipos nodos y puntero a nodo.
Inicialización o creación.
Insertar elementos en una lista.
Eliminar elementos de una lista.
Buscar elementos de una lista (Comprobar la existencia de elementos en una lista).
Recorrer una lista enlazada (visitar cada nodo de la lista).
Comprobar si la lista está vacía.
Declaración de un nodo
Una lista enlazada se compone de una serie de nodos enlazados mediante punteros. Cada nodo es una combinación de dos partes: un tipo de dato (entero, real, doble, carácter, o tipo predefinido) y un enlace (puntero) al siguiente nodo.
Puntero de cabecera y cola
Normalmente, los programas no declaran variables de nodos. En su lugar, cuando se construye y manipula una lista enlazada, a la lista se accede a través de uno o más punteros a los nodos. El acceso más frecuente a una lista enlazada es a través del primer nodo de la lista que se llama cabeza o cabecera de la lista. Un puntero al primer nodo se llama puntero cabeza, o simplemente L. En ocasiones, se mantiene también un puntero al último nodo de una lista enlazada. El último nodo es la cola de la lista, y un puntero al nodo es el puntero cola. También se pueden mantener punteros otros nodos de una lista enlazada. Cada puntero a un nodo debe ser declarado como una variable de puntero.
Acceso a una lista. La construcción y manipulación de una lista enlazada requiere el acceso a los nodos de la lista través de uno o más punteros a nodos. Normalmente, un programa incluye un puntero al primer nodo (cabeza) y un puntero al último nodo (cola)
En cualquier forma, el último elemento de la lista contiene un campo de enlace con valor 0, esto es, un puntero nulo (NULL) que señala el final de la lista.
El puntero nulo
La palabra NULL representa el puntero nulo, que es una constante especial. Se puede utilizar el puntero nulo para cualquier valor de puntero que no apunte a ningún sitio. El puntero nulo se utiliza, normalmente, en dos situaciones:
Usar el puntero nulo en el campo enlace o siguiente del nodo final de una lista enlazada.
Cuando analista enlazada no tiene ningún nodo, se utiliza el puntero NULL como puntero de cabeza y de cola. Tal lista se denomina lista vacía
El puntero de cabeza y de cola en una lista enlazada puede ser NULL, lo que indicará que la lista es vacía (no tiene nodos). Éste suele ser un método usual para construir una lista. Cualquier función que se escribe para manipular listas enlazadas debe poder manejar un puntero de cabeza y un puntero de cola nulos.
El operador -> de selección de un miembro
Si p es un puntero a una estructura y m es un miembro de la estructura, entonces p-> m accede al miembro m de la estructura apuntada por p.
El símbolo -> se considera como un operador simple (en vez de compuesto, al constar de dos símbolos independientes, -y>. Se denomina operador de selección de miembro o también operador de selección de componente. De modo visual el operador p-> m recuerda a una flecha que apunta del puntero p al objeto que contiene al miembro m.
Suponiendo que un programa ha de construir una lista enlazada y crear un puntero de cabecera ptr_cabeza a un nodo Nodo, el operador * de indirección aplicado a una variable puntero representa el contenido del nodo apuntado por ptr_cabeza. Es decir, *ptr_cabeza es un tipo de dato Nodo.
Precaución. Los paréntesis son necesarios alrededor de la primera parte de la expresión (*ptr_cabeza) ya que los operadores unitarios que aparecen a la derecha tienen prioridad más alta que los operadores unitarios que aparecen en el lado izquierdo (El asterisco de indirección).
Sin paréntesis, el significado de ptr_cabeza producirá un error de sintaxis, al intentar evaluar ptr_cabeza. Dato antes de la indirección o desreferencia.
P -> m significa lo mismo que (*p).m
Error. Uno de los errores típicos en el tratamiento de punteros es escribir la expresión *p o bien p-> cuando el valor del puntero p es el puntero nulo, ya que como se sabe el puntero nulo no apunta a nada.
Construcción de una lista
Una primera operación que se realiza con analista es asignar un valor inicial; éste es el de Lista vacía. Sencillamente consiste en asignar nulo al puntero de acceso a la lista.
Para añadir elementos a la lista se utiliza la operación insertar(), con sus diferentes versiones. También, para la creación de analista enlazada, se utiliza el siguiente algoritmo que entraña los siguientes pasos:
Paso 1. Declarar el tipo de dato y el puntero de cabeza o primero.
Paso 2. Asignar memoria para un elemento del tipo definido anteriormente utilizando alguna de las funciones de asignación de memoria(malloc(), calloc(), realloc()) y un cast para la conversión de void* al tipo puntero a nodo; la dirección del nuevo elemento es ptr_nuevo.
Paso 3. Crear iterativamente el primer elemento (Cabeza) y los elementos sucesivos de una lista enlazada simplemente.
Paso 4. Repetir hasta que no haya mas entradas para el elemento.
Inserción de un elemento en una lista
El algoritmo empleado para añadir o insertar un elemento en una lista enlazada varía dependiendo de la posición en que se desea insertar el elemento. La posición de inserción puede ser:
En la cabeza (elemento primero) de la lista.
En el final de la lista (elemento último).
Antes de un elemento especificado.
Después de un elemento especificado.
Inserta un nuevo elemento en la cabeza de una lista
Aunque normalmente se insertan nuevos datos al final de una estructura de datos, es más fácil y más eficiente insertar un elemento nuevo en la cabeza de analista. El proceso de inserción se puede resumir en este algoritmo:
Asignar un nuevo nodo apuntado por nuevo, que es una variable puntero local que apunta al nuevo nodo que se va a insertar en la lista.
Simular el nuevo elemento en el campo dato del nuevo nodo.
Hacer que el campo enlace siguiente del nuevo nodo apunte a la cabeza (primer nodo) de la lista original.
Hacer que cabeza (puntero cabeza) apunte al nuevo nodo que se ha creado.
Inserción de un nodo al final de la lista
La inserción al final de la lista es menos eficiente debido a que, normalmente, no e tiene un puntero al último elemento de la lista y entonces se ha de seguir la traza desde la cabeza de la lista hasta el último nodo de la lista ya continuación realizar la inserción. Cuando ultimo es una variable puntero que apunta a último nodo de la lista, las sentencias siguientes insertan un nodo al final de la lista.
Ultimo -> siguiente = crearNodo(x);
Ultimo -> siguiente -> siguiente = NULL;
Ultimo = ultimo -> siguiente;
La primera sentencia crea un nuevo nodo, llamada a crearNodo(), y se asigna al campo siguiente del último nodo de la lista (antes de la inserción) de modo que el nuevo nodo ahora es el último. La segunda sentencia establece el campo siguiente del nuevo último nodo a NULL. Y la última sentencia pone la variable ultimo al nuevo último nodo de la lista.
La función inserFinal() tiene como entrada el puntero cabeza, recorre la lista hasta situarse al final y realiza la inserción. Se tiene en cuenta la circunstancia de que la lista este vacía, en cuyo caso inserta el nuevo nodo como nodo primero y único.
Inserción de un nodo entre dos nodos de la lista
La inserción de un nuevo nodo no siempre se realiza al principio (en cabeza) de la lista o al final se puede insertar entre dons nodo cualesquiera de la lista.
El algoritmo de la nueva operación insertar requiere las siguientes etapas:
1. Asignar el nuevo nodo, con el campo dato, apuntado por el puntero nevo.
2. Hacer que el campo en lace siguiente del nuevo nodo apunte al nodo que va después de la posición que se desea para el nuevo nodo (o bien a NULL, si no hay ningún nodo después de la nueva posición).
3. En la variable puntero anterior tener la dirección del nodo que está antes de la posición deseada para el nuevo nodo. Hacer que anterior-> siguiente apunte al nuevo nodo que se acaba de crear.
Para llamar a la función insertar(), previamente se ha de buscar la dirección del nodo anterior y asegurarse de que la lista no está vacía, ni que se quiere insertar como primer nodo.
Una versión de la función tiene como argumentos la dirección de inicio de la lista, cabeza, el campo dato a partir del cual se inserta y el dato del nuevo nodo.
El algoritmo de esta versión de la operación insertar requiere las siguientes etapas:
1. Asignar el nuevo nodo, con el campo dato, apuntado por el puntero nuevo.
2. Buscar la dirección del nodo, después, que contiene el campo dato a partir del cual se ha de insertar.
3. Hacer que el campo enlace siguiente del nuevo nodo apunte al nodo que va a continuación de la posición que se desea para el nuevo nodo (o bien NULL si no hay ningún nodo).
4. Hacer que después -> siguiente apunte al nuevo nodo que se acaba de crear.
La primera comprobación, previa a las etapas a seguir, es que la lista esté vacía. Si es así se inserta como primer nodo. También se tiene que tener precaución en la búsqueda que se realiza en la etapa 2, ésta puede ser negativa, no se encuentra el dato; entonces no se inserta el nuevo nodo.
Búsqueda den listas enlazadas
La función localizar() utiliza una variable puntero denominada indice que va recorriendo la lista nodo a nodo .Mediante un bucle, indice apunta a los nodos de la lista de modo que si se encuentra el nodo buscado, se devuelve un puntero al nodo con la sentencia de retorno (Return); en elcaso de no encontrarse el nodo buscado la función debe devolver NULLL (return NULL). El nodo que se busca es el que tiene un campo dato que coincide con una clave.
A tener en cuenta. La operación de búsqueda puede tener diferentes enfoques: búsqueda de la posición del primer nodo que contiene un dato, búsqueda de la posición de un nodo según el número de orden, determinación si existe o no un nodo con un campo dato determinado.
Eliminación de un nodo en una lista
La operación de eliminar (borrar) un nodo de una lista enlazada supone enlazar el nodo anterior con el nodo siguiente al que se desea eliminar y liberar la memoria que ocupa.
El algoritmo para eliminar un nodo que contiene un dato se puede expresar en estos pasos o etapas:
1. Búsqueda del nodo que contiene el dato (se ha de tener la dirección del nodo a eliminar y la dirección del anterior).
2. El puntero siguiente del nodo anterior ha de apuntar al siguiente del nodo a eliminar.
3. En caso de que el nodo a eliminar sea el primero, cabeza, se modifica cabeza para que tenga la dirección del nodo siguiente.
4. Por ultimo, se libera la memoria ocupada por el nodo.
Lista doblemente enlazada
Hasta ahora el recorrido de una lista se realizaba en sentido directo (adelante) o, en algunos casos en sentido inverso (hacia atrás). Sin embargo, existen numerosas aplicaciones en las que es conveniente poder acceder a los elementos o nodos de analista en cualquier orden. En este caso se recomienda el uso de una lista doblemente enlazada. En al lista, cada elemento contiene dos punteros, aparte del valor almacenado en el elemento. Un puntero apunta al siguiente elemento de la lista y el otro apunta al elemento anterior.
Las operaciones básicas que se definen en el tipo abstracto Lista doble son básicamente las mismas que las definidas en una lista simple y tendrán las siguientes funciones:
Declaración de los tipos nodo y puntero a nodo.
Inicialización o creación.
Insertar elementos en una lista.
Eliminar elementos de una lista.
Buscar elementos de una lista (comprobar la existencia de elementos en una lista).
Recorrer una lista enlazada (visitar cada nodo de la lista).
Comprobar si la lista está vacía.
Cabeza
Existe una operación de insertar y eliminar (borrar) en cada dirección.
Insertar un elemento en una lista doblemente enlazada
El algoritmo empleado para añadir o insertar un elemento en una lista doble varía dependiendo de la posición en que se desea insertar el elemento. La posición de inserción puede ser:
En la cabeza (elemento primero) de la lista.
En el final de la lista (elemento último).
Antes de un elemento especificado.
Después de un elemento especificado.
Insertar un nuevo elemento en la cabeza de una lista doble
El proceso de inserción se puede resumir en este algoritmo:
Asignar un nuevo nodo el campo dato (Info) apuntado por nuevo que es una variable puntero local que a su vez apunta al nuevo nodo que se va a insertar en la lista doble.
Hacer que el campo enlace adelante del nuevo nodo apunte a la cabeza (primer nodo) de la lista original, y que el campo enlace atrás del nodo cabeza apunte al nuevo nodo.
Hacer que cabeza (puntero cabeza) apunte al nuevo nodo que se ha creado.
En este momento, la función de insertar un elemento en la lista termina su ejecución, la variable local nuevo desaparece y sólo permanece el puntero de cabeza, cabeza, que apunta a la nueva lista doblemente enlazada.
Inserción de un nuevo nodo que no está en la cabeza de la lista
La inserción de un nuevo nodo en una lista doblemente enlazada se puede realizar en un nodo intermedio de ella. El algoritmo de la nueva operación insertar requiere las siguientes etapas:
1. Asignar el nuevo nodo el campo dato(Info) apuntado por el puntero nuevo.
2. Hacer que el campo enlace adelante del nuevo nodo apunte al nodo que va después de la posición del nuevo nodo (o bien a NULL si no hay ningún nodo después de la nueva posición). El campo atrás del nodo siguiente al nuevo tiene que apuntar a nuevo.
3. La dirección del nodo que está antes de la posición deseada para el nuevo nodo está en la variable puntero anterior. Hacer que anterior-> adelante apunte al nuevo nodo. El enlace atrás del nuevo nodo debe de apuntar a anterior.
En la función que se escribe a continuación, se tiene en cuenta que la inserción sea en una lista vacía en cuyo caso cabeza es NULL, o que sea como primer nodo. De igual forma se contempla que la inserción sea como último nodo.
Eliminación de un elemento en una lista doblemente enlazada
La operación de eliminar un nodo de una lista doble supone realizar el enlace de dos punteros: el nodo anterior con el nodo siguiente al que se desea eliminar, con el putero adelante; y el nodo siguiente con el anterior, con el puntero atrás, y liberar la memoria que ocupa.
El algoritmo para eliminar un nodo que contiene un dato es similar al algoritmo de eliminación en una lista simple. Ahora la dirección del nodo anterior se encuentra en el puntero atrás del nodo a eliminar o borrar. Los pasos a seguir:
1. Búsqueda del nodo que contiene el dato. Se ha de tener la dirección del nodo a eliminar y la dirección del anterior.
2. El punto adelante del nodo anterior tiene que apuntar al puntero adelante del nodo a eliminar (en el caso de no ser el nodo cabecera).
3. El puntero atrás del nodo siguiente a eliminar debe apuntar al puntero atrás del nodo a eliminar (en el caso de no ser el nodo último).
4. En caso de que el nodo a eliminar sea el primero, cabeza; se modifica cabeza para que tenga la dirección del nodo siguiente.
5. Por último, se libera la memoria ocupada por el nodo.
Listas circulares
En las listas lineales simples o en las dobles siempre hay un primer nodo y un último nodo que tiene el campo de enlace a nulo. Una lista circular, por propia naturaleza no tiene ni principio ni fin. Sin embargo, resulta útil establecer un nodo a partir del cual se acceda a la lista y así poder acceder a sus nodos.
Las operaciones que se realizan sobre una lista circular son similares a las operaciones sobre listas lineales, teniendo en cuenta que el último nodo no apunta anulo sino al primero. Estas operaciones permiten construir el TAD Lista circular y su funcionalidad:
Declaración de los tipos nodo y puntero a nodo.
Inicialización o creación.
Insertar elementos en una lista circular.
Eliminar elementos de una lista circular.
Buscar elementos de una lista circular.
Recorrer o visitar cada nodo de la lista circular.
Comprobar si la lista está vacía.
La creación de una lista circular se puede hacer con un enlace simple o enlace. Considerando que la lista circular se enlaza con un solo enlace, la realización con enlace adelante y atrás es similar.
A tener en cuenta. El puntero de acceso a una lista circular, normalmente apunta al último nodo añadido a la estructura. Esta convención puede cambiar ya que en una estructura circular no hay primero ni último.
Insertar un elemento en una lista circular
El algoritmo empleado para añadir o insertar un elemento en una lista circular vacía dependiendo de la posición en que se desea insertar el elemento. La posición de inserción puede variar, consideramos que se hace como nodo anterior al nodo de acceso a la lista y tiene la dirección del último nodo insertado.
Eliminar un elemento en una lista circular
La operación de eliminar un nodo de una lista circular sigue los mismos pasos que los dados para eliminar un nodo en una lista lineal. Hay que enlazar el nodo anterior con el nodo siguiente al que se desea eliminar y liberar la memoria que ocupa.
El algoritmo para eliminar un nodo de una lista circular es:
Búsqueda del nodo que contiene el dato.
Se enlaza el nodo anterior con el siguiente.
En caso de que el nodo a eliminar sea el referenciado por el puntero de acceso a la lista, se modifica para que tenga la dirección del nodo anterior.
Por último, se libera la memoria ocupada por el nodo.
En la función eliminar hay que tener en cuenta la característica de lista circular; así, para detectar si la lista es de un solo nodo se pregunta si se apunta al mismo.
RESUMEN
La estructura de daos lista se puede implementar, bien como un array, bien como una lista enlazada. Una lista enlazada es una estructura de datos dinámica en la que sus componentes están ordenados lógicamente por sus campos punteros en vez de ordenados físicamente como están en un arrary. El final de la lista se señala mediante una constante o puntero especial llamado NULL.
La gran ventaja de analista enlazada sobre un array es que la lista enlazada puede crecer y decrecer en tamaño, ajustándose al número de elementos.
Una lista simplemente enlazada contiene sólo un enlace a un sucesor único, a menos que sea el último, en cuyo caso no se enlaza con ningún otro nodo.
Cuando se inserta un elemento en una lista enlazada, se deben considerar cuatro casos: añadir a una lista vacía, añadir al principio de la lista, añadir en el interior y añadir al final de la lista.
Para borrar (eliminar) un elemento, primero hay que buscar el nodo que los contiene y considerar dos casos: borrar el primer nodo y borrar cualquier otro de la lista.
El recorrido de una lista enlazada significa pasar por cada nodo (visitar) y procesarlo. El proceso puede ser: escribir su contenido o modificar el campo de datos.
Una lista doblemente enlazada es aquella en la que cada nodo tiene un puntero a su sucesor y otro a su predecesor. Las listas doblemente enlazadas se pueden recorrer en ambos sentidos. Las operaciones básicas son inserción, eliminación y recorrido de la lista: similares a las listas simples.
Una lista enlazada circularmente por propia naturaleza no tiene primero ni último nodo. Las listas circulares puedes ser de enlace simple o doble.
1.- Algoritmos y estructuras de datos. Una perspectiva en C, Autor Luis Joyanes Aguilar, Ignacio Zahonero Martínez. Ed. McGraw Hill
2.- Estructuras de Datos , Autor Aarón M. Tenenbaum, Moshe J. Augentein. Primera edición.
3.- Diseño y Administración de Base de Datos, Autor Gary W. Hansen, James V. Hansen, Segunda Edición.
4.- Guía de Estructura y Procesamiento de Datos, Autor Profesor David López, Segundo semestre U.N.I.R. (Maracaibo).
Suscribirse a:
Entradas (Atom)
