Repblica Bolivariana de Venezuela Ministerio del Poder Popular Para la Defensa Universidad Nacional Experimental de la Fuerza Armada Tucupita, Estado delta Amacuro Asignatura: Programacin

FUNCIONES Y PROCEDIMIENTOS DEFINIDOS POR EL USUARIO EN TURBO PASCAL.Profesor: Ing.: Juan Carlos Rubio. Bachiller: Marielys Palacios. CI: 21384616. Tucupita, Junio-2011.

1

ndice Introduccin 1.- Funciones y procedimientos definidos por el usuario en turbo pascal ... 4 2.- Recursividad 3.- Datos Complejos 4.- Definicin de tipos de datos complejos 5.- Pilas 6.- Colas 7.- Listas 8.- Arboles 9.- Grafos 10.- Sistema de archivos 11.- Archivo secuencial 12.- Archivos indexados 13.- Archivos directos o de dispersin 14.- Archivos aleatorios Conclusin Bibliografa . .. . . .. . . .. .. .......10 .. .....15 ... 17 ....19 .. .23 .. 25 .....33 ......35 . .. 38 . . ..42 . .46 ..47 . .49 . ...52 ...54

2

Introduccin. Pascal es un lenguaje de Alto Nivel y propsito general desarrollado por el Prof. suizo Niklaus WIRTH en 1968. Turbo Pascal Lanzado en 1983 por BORLAND International. Un procedimiento es un programa que realiza una tarea especfica. Este est compuesto de un grupo de sentencias a las que se asigna un nombre (identificador) y constituye una unidad de programa y es obligatorio declararlos, se deben declarar antes de que puedan ser referenciados en el cuerpo del programa, se declaran igual que los identificadores dentro del cuerpo del programa. Existen dos tipos de variables las locales y las globales las locales se encuentran dentro del procedimiento mientras que las globales deben de estar fuera del procedimiento y se ubican en el cuerpo principal. El procedimiento consta de tres partes que son cabecera, seccin de declaracin y seccin ejecutable; la cabecera nos proporciona el nombre y la lista de los parmetros formales(los parmetros son mtodos para pasar informacin (valores a variables) del programa principal a un procedimiento y viceversa), si existen, la seccin de declaracin contiene las constantes, variables e incluso otros procedimientos y la ejecutable contiene el cuerpo del procedimiento. Una de las ventajas de utilizar procedimiento es que nos facilita el diseo descendiente y tambin nos facilita la divisin de las tareas entre un equipo de programadores y se pueden comprobar individualmente. Una funcin es un subprograma que recibe como argumento o parmetros datos de un tipo numrico o no numrico y devuelven un resultado. Los argumentos es lo que se conoce en pascal como parmetros. recursividad est ligado, en los lenguajes de programacin, al concepto de procedimiento o funcin. Un procedimiento o funcin es recursivo cuando durante una invocacin a l puede ser invocado a su vez l mismo.El concepto de

3

1. Funciones y procedimientos definidos por el usuario en turbo pascal. Pascal es un lenguaje de alto nivel y de propsito general (es aplicable a un gran nmero de aplicaciones diversas) desarrollado por el profesor suizo Niklaus Wirth como un lenguaje para ensear la programacin con un mtodo disciplinado y sistemtico. Wirth trat de eliminar las inconsistencias de otros lenguajes de programacin de su poca y adems que sirviera para ensear las tcnicas de programacin a sus alumnos. Una versin preliminar del lenguaje apareci en 1968 y a finales de 1970 apareci el primero compilador totalmente completo. Las diferentes versiones ofrecan interpretaciones ligeramente diferentes que impedan la compatibilidad entre ellas. Por estas razones, mediante diferentes proyectos, se logr la estandarizacin bajo las normas ISO (International Standards Organization), ANSI (American National Standards Institute) y IEEE (Institute of Electrical and Electronics Engineers). Sin embargo, las versiones ms populares conocidas como UCSD (Construida por Regents) y Turbo Pascal (de Borland) no estn estandarizadas. Esta ltima es la ms conocida y la ms utilizada. Caractersticas principales y Excelente para el aprendizaje de la informacin. y Lenguaje de propsito general. {PalabraClave: Carteras} Mster En Gestin de Carteras Estudia Con Expertos! www.ieb.esEnlaces patrocinados y Lenguaje procedimental (orientado a rdenes).4

y Lenguaje estructurado (Permite while, for y repeat y no necesita el goto). y Lenguaje recursivo (Puede llamarse a s mismo una funcin o procedimiento). y Riqueza en los tipos de datos. Turbo Pascal Turbo Pascal es un completo sistema de desarrollo de software que incluye un compilador y un entorno de desarrollo integrado (IDE) para el lenguaje de programacin Pascal, desarrollado por borland y liderado por Phillipe kanhh. Fue lanzado por la firma Borland International en 1983 a modo experimental. Fue todo un xito, pues adems de funcionar, compilaba y corra los programas ms rpido. Las versiones han evolucionado de la 1.0 hasta la 7.0 que cuenta con una biblioteca de objetos denominada Turbo Visin. Turbo pascal debe su nombre, por que compila en un minuto. Concepto de Funciones: Una funcin es un modulo de un programa separado del cuerpo principal, que realiza una tarea especifica y que puede regresar un valor a la parte principal del programa u otra funcin o procedimiento que la invoque. Concepto de procedimiento: Un procedimiento es un programa que realiza una tarea especfica. Puede recibir cero o ms valores del programa que llama y devolver cero o ms valores al programa que realiz la llamada. Un procedimiento est5

compuesto de un grupo de sentencias a las que se asigna un nombre (identificador) y constituye una unidad de programa. La tarea asignada al procedimiento se ejecuta siempre que Pascal encuentra el nombre del procedimiento. Un procedimiento es un grupo de sentencias que realizan una tarea concreta. En lugar de reescribir el cdigo completo de esa tarea cada vez que se necesite, nicamente se hace una referencia al procedimiento. Un procedimiento es un programa que realiza una tarea especfica y esta compuesto de un grupo de sentencias a las que se les asigna un nombre (identificador) y constituye una unidad de programa.

Los procedimientos deben declararse dentro del programa, estn las variables locales y las globales.

Las locales: Son las que se encuentran dentro de un procedimiento.

Las globales: Son aquellas que ubican en el cuerpo principal, fuera de los procedimientos.

Parmetros: son los mtodos para transferir informacin desde el cuerpo principal del programa a un procedimiento. Estos pueden ser de entrada y salida.

Partes de un procedimiento: Las partes de un procedimiento son: Cabecera del procedimiento, la seccin de declaracin y la seccin ejecutable.

6

Sus ventajas son: y Facilita el diseo. y Se pueden ejecutar ms de una vez. y Se ahorra tiempo. y Facilita la divisin de las tareas entre un equipo Finalmente cabe destacar que los procedimientos slo realizan operaciones especficas, mientras que las funciones slo realizan clculos. Las funciones en turbo pascal son sub-programa que reciben como argumentos o parmetros datos de un tipo numrico o no numrico, y devuelve un resultado. Esta caracterstica le diferencia de un procedimiento. El pseudocdigo es el siguiente: Los argumentos es lo que se conoce en Pascal como parmetros. Para poder calcular el valor o resultado de la funcin, todo lo que se necesita conocer es el valor o valores de los parmetros respectivos.

7

Tipos de de funciones: y Las primeras son de tipo computacional. y Las segundas son aquellas que manipulan informacin y regresan un valor que indica la terminacin o la falla de esa manipulacin. y Las terceras son aquellas que no regresan ningn valor. Comparacin entre funciones y procedimientos. y En vez de la palabra procedure se debe utilizar la palabra function y La lista de los parmetros formales son los identificadores utilizados para recibir valores del programa. y La funcin solo devuelve un valor, el procedimiento devuelve cero, uno, o varios valores.8

Comparacin entre funciones y procedimientos En vez de la palabra procedure se debe utilizar la palabra function Al igual que en los procedimientos, el nombre de una funcin es un identificador. Sin embargo, el nombre de la funcin se refiere a la posicin de memoria que contiene el valor devuelto por la funcin. La lista de los parmetros formales son los identificadores utilizados para recibir valores del programa. El tipo de datos del resultado coincide con el tipo expresado en la cabecera de la funcin. En el cuerpo de la funcin tiene que existir una sentencia de asignacin como la siguiente: Nombre funcin:= valor funcin La funcin slo devuelve un valor, el procedimiento puede devolver cero, uno o varios valores. El tipo de dato del resultado de la funcin debe estar indicado en la cabecera y puede ser tipo char, integer, real o bolean. Ejemplo: Program Cubo; Uses

9

Wincrt; Var Num, valor: integer; Function El_cubo (Numero: integer):integer; Begin valor := Num*Num*Num; End; Begin Write ('Digite un nmero entero: '); Readln (Num); El_cubo(Num); Write ('El cubo de ',Num,' es ',valor); End. Recursividad. Definicin de Recursividad: Tcnica de programacin muy potente que puede ser usada en lugar de la iteracin.

10

El concepto de recursividad est ligado, en los lenguajes de programacin, al concepto de procedimiento o funcin. Un procedimiento o funcin es recursivo cuando durante una invocacin a l puede ser invocado a su vez l mismo. La recursividad es una de las formas de control ms importantes en la programacin. Los procedimientos recursivos son la forma ms natural de representacin de muchos algoritmos. mbito de Aplicacin:

y General y Problemas cuya solucin se puede hallar solucionando el mismo problema pero con un caso de menor tamao. Razones de uso:

y Problemas casi irresolubles con las estructuras iterativas. y Soluciones elegantes. y Soluciones ms simples. Condicin necesaria: Asignacin dinmica de memoria.

Ventajas de la Recursin ya conocidas y Soluciones simples, claras. y Soluciones elegantes. y Soluciones a problemas complejos.

11

Desventajas de la Recursin: y Sobrecarga asociada con las llamadas a subalgoritmos y Una simple llamada puede generar un gran nmero de llamadas recursivas. (Fact(n) genera n llamadas recursivas) y La claridad compensa la sobrecarga? y El valor de la recursividad reside en el hecho de que se puede usar para resolver problemas sin fcil solucin iterativa. y La ineficiencia inherente de algunos algoritmos recursivos. La recursividad se debe usar cuando sea realmente necesario, es decir, cuando no exista una solucin iterativa simple

Como ejemplo, elaboremos una funcin que nos permita calcular el factorial de un nmero: Matemticamente se define como factorial de un nmero n al producto de los enteros positivos desde 1 hasta n y se denota por n! N! = 1. 2. 3. 4. 5. . . (n 2) (n 1) n Tambin se define 0! = 1, de forma que la funcin est definida para todos los enteros no negativos. As tenemos que: 0! = 1 1! = 1 2! = 1. 2 = 2 3! = 1. 2. 3 = 6 4! = 1. 2. 3. 4 = 24 5! = 1. 2. 4. 5 = 120 Y as sucesivamente. Observe que: 5! = 5. 4! = 5. 24 = 120 6! = 6. 5! = 6. 120 = 720 Esto se cumple para cualquier entero n positivo; o sea, n! = n (n 1)!12

De acuerdo con esto, la funcin factorial se puede definir tambin como: Si n < 2 entonces n! = 1 2 entonces n! = n (n 1)!uSi n Esta definicin de n! es recursiva ya que se refiere a s misma cuando invoca (n 1) ! Luego nuestra funcin podra ser: Function Factorial (n: Integer) : Integer; begin If n < 2 Then Factorial: = 1 El se Factorial:= n * Factorial ( n 1); end; Cuando esta funcin es invocada, por ejemplo, para hallar el factorial del nmero 3, se crean en la memoria de la computadora las siguientes instancias:

13

Y al finalizar comienza el retorno a la invocacin anterior efectundose las acciones que haban quedado pendientes.

Observe cmo una nueva invocacin a la funcin Factorial, cuando an no se ha terminado la invocacin anterior, no afecta el valor de la variable local n que se cre en la invocacin anterior. Esto es esencialmente el principio fundamental de las funciones o procedimientos recursivos, y que hace de estos un mecanismo cualitativamente superior; cada instancia interrumpida de la funcin o del procedimiento, por una llamada a otro procedimiento o funcin, conserva sus datos locales, an cuando el procedimiento o funcin pueda ser nuevamente invocado. Al escribir un procedimiento o una funcin recursiva es esencial que se incluya, en el procedimiento o funcin, una condicin de terminacin para evitar que la recursin continu indefinidamente. Mientras la condicin de terminacin permanezca insatisfecha, el procedimiento o funcin se invocar a s mismo, del igual modo que invocara a cualquier otro procedimiento o funcin.

14

Tipos de recursividad: Recursividad directa (simple): Es cuando un subprograma A se llama a s mismo una o ms veces directamente.

Recursividad indirecta (mutua). Es cuando un subprograma A, llama al subprograma B, y ste a su vez, llama al subprograma A

Datos complejos Concepto de dato: Los diferentes objetos de informacin con los que trabaja un programa en Pascal se conocen como datos. Todos los datos tienen un tipo asociado con ellos. Pueden ser de tipo carcter, entero, un nmero real, entre otros. La asignacin de tipos a los datos persigue dos objetivos: y Detectar errores de operaciones en programas. y Determinar cmo ejecutar las operaciones.

15

Clasificacin de los tipos de datos Tipos de datos enteros: Turbo Pascal dispone de cinco tipos predefinidos (no necesitan una nueva definicin de parte del programador pues cada tipo tiene un lmite) que permiten representar valores enteros.

Si se asigna un valor fuera del lmite de cada tipo, producir un mensaje de error:

16

Error 76: Constant out of range Byte: Son los datos comprendidos entre 0 y 255. Integer: Enteros que estn entre -32.768 y 32.767. Longint: A partir de la versin 4.0 se ampla el rango de los enteros. Van desde -2.147,483.647 hasta 2.147,483.647. Shortint: Son datos enteros comprendidos entre -128 y 127. Son utilizados cuando se debe trabajar con valores pequeos y se desea economizar memoria. Ocupan 1 byte de memoria. Word: Se utiliza cuando se desea representar nicamente valores positivos. Ocupan dos bytes de memoria y van de 0 a 65.535.

Definicin de tipos de datos complejos. En los lenguajes de programacin y en otros programas utilitarios tales como una planilla de clculos, un tipo de dato es un atributo de una parte de los datos que indica al ordenador (y/o al programador) algo sobre la clase de datos sobre los que se va a procesar. Esto incluye imponer restricciones en los datos, como qu valores pueden tomar y qu operaciones se pueden realizar. Tipos de datos comunes son: enteros, nmeros de coma flotante (decimales), cadenas alfanumricas, fechas, horas, colores, coches o cualquier cosa que se nos ocurra. Por ejemplo, en Java, el tipo "int" representa un conjunto de enteros de 32 bits cuyo rango va desde el 2.147.483.648 al 2.147.483.647, as como las operaciones que se pueden realizar con los enteros, como la suma, resta y multiplicacin.

17

Los colores, por otra parte, se representan como tres bytes denotando la cantidad de rojo, verde y azul, y una cadena de caracteres representando el nombre del color; las operaciones permitidas incluyen la adicin y sustraccin, pero no la multiplicacin. ste es un concepto propio de la informtica, ms especficamente de los lenguajes de programacin, aunque tambin se encuentra relacionado con nociones similares de las matemticas y la lgica. Los tipos de datos definen un conjunto de valores y las operaciones sobre estos valores. Casi todos los lenguajes de programacin explcitamente incluyen la notacin del tipo de datos, aunque lenguajes diferentes pueden usar terminologa diferente. La mayor parte de los lenguajes de programacin permiten al programador definir tipos de datos adicionales, normalmente combinando mltiples elementos de otros tipos y definiendo las operaciones del nuevo tipo de dato. Por ejemplo, un programador puede crear un nuevo tipo de dato llamado "Persona" que especifica que el dato interpretado como Persona incluir un nombre y una fecha de nacimiento. Un tipo de dato puede ser tambin visto como una limitacin impuesta en la interpretacin de los datos en un sistema de tipificacin, describiendo la representacin, interpretacin y la estructura de los valores u objetos almacenados en la memoria del ordenador. El sistema de tipificacin usa informacin de los tipos de datos para comprobar la verificacin de los programas que acceden o manipulan los datos.

18

Pilas. Son elementos que pueden insertar o eliminar solo por sus extremos, conocidos como la estructura de LIFO(Last In, Firt Out) que significa que el ultimo en entrar es el primero en salir, estas son representados en memorias de arreglos y listas enlazadas. Son usados en el software del sistema, compiladores e intrpretes.

Una pila (stack en ingls) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del ingls 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 informtica debido a su simplicidad y ordenacin implcita de la propia estructura.

Para el manejo de los datos se cuenta con dos operaciones bsicas: apilar (push), que coloca un objeto en la pila, y su operacin inversa, retirar (o desapilar, pop), que retira el ltimo elemento apilado. En cada momento slo se tiene acceso a la parte superior de la pila, es decir, al ltimo objeto apilado (denominado TOS, Top of Stack en ingls). La operacin retirar permite la obtencin de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.

19

Por analoga con objetos cotidianos, una operacin apilar equivaldra a colocar un plato sobre una pila de platos, y una operacin retirar a retirarlo. Las pilas suelen emplearse en los siguientes contextos:

Evaluacin de expresiones en notacin postfija (notacin polaca inversa). Reconocedores sintcticos de lenguajes independientes del contexto Implementacin de recursividad.

Historia: El mtodo de pila para la evaluacin de expresiones fue propuesto en 1955 y dos aos despus patentado por Fiedrich L.Bauer, quin recibi en 1988 el premio "IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos. Pila como tipo abstracto de datos: La pila es un contenedor de nodos y tiene dos operaciones bsicas: push (o apilar) y pop (o desapilar). 'Push' aade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el actual nodo superior 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 aadir ms de uso habitual.

Crear: se crea la pila vaca. Apilar: se aade un elemento a la pila.(push) Desapilar: se elimina el elemento frontal de la pila.(pop) Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)20

Vaca: devuelve cierto si la pila est vaca o falso en caso contrario.

Implementacin Un requisito tpico de almacenamiento de una pila de n elementos es O(n). El requisito tpico de tiempo de O (1) las operaciones tambin son fciles de satisfacer con un array o con listas enlazadas simples. La biblioteca de plantillas de C++ estndar proporciona una "pila" clase templated que se limita a slo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especializacin de Vector. Esto podra ser considerado como un defecto, porque el diseo heredado get () de Vector mtodo LIFO ignora la limitacin de la Pila. Arquitectura bsica de la pila. Una pila tpica es un rea de la memoria de los computadores con un origen fijo y un tamao variable. Al principio, el tamao de la pila es cero. Un puntero de pila, por lo general en forma de un registro de hardware, apunta a la ms reciente localizacin en la pila; cuando la pila tiene un tamao de cero, el puntero de pila de puntos en el origen de la pila. Las dos operaciones aplicables a todas las pilas son:

Una operacin apilar, en el que un elemento de datos se coloca en el lugar apuntado por el puntero de pila, y la direccin en el puntero de pila se ajusta por el tamao de los datos de partida.

Una operacin desapilar: un elemento de datos en la ubicacin actual apuntada por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamao de los datos de partida.

21

Hay muchas variaciones en el principio bsico de las operaciones de pila. Cada pila tiene un lugar fijo en la memoria en la que comienza. Como los datos se aadirn a la pila, el puntero de pila es desplazado para indicar el estado actual de la pila, que se expande lejos del origen (ya sea hacia arriba o hacia abajo, dependiendo de la aplicacin concreta). Por ejemplo, una pila puede comenzar en una posicin de la memoria de mil, y ampliar por debajo de las direcciones, en cuyo caso, los nuevos datos se almacenan en lugares que van por debajo de 1000, y el puntero de pila se decrementa cada vez que un nuevo elemento se agrega. Cuando un tema es eliminado de la pila, el puntero de pila se incrementa. Los punteros de pila pueden apuntar al origen de una pila o de un nmero limitado de direcciones, ya sea por encima o por debajo del origen (dependiendo de la direccin en que crece la pila), sin embargo el puntero de pila no puede cruzar el origen de la pila. En otras palabras, si el origen de la pila est en la direccin 1000 y la pila crece hacia abajo (hacia las direcciones 999, 998, y as sucesivamente), el puntero de pila nunca debe ser incrementado ms all de 1000 (para 1001, 1002, etc.) Si un desapilar operacin en la pila hace que el puntero de pila se deje atrs el origen de la pila, una pila se produce desbordamiento. Si una operacin de apilar hace que el puntero de pila incremente o decremente ms all del mximo de la pila, en una pila se produce desbordamiento. La pila es visualizada ya sea creciente de abajo hacia arriba (como pilas del mundo real), o, con el mximo elemento de la pila en una posicin fija, o creciente, de izquierda a derecha, por lo que el mximo elemento se convierte en el mximo a "la derecha". Esta visualizacin puede ser independiente de la estructura real de la pila en la memoria. Esto significa que rotar a la derecha es mover el primer elemento a la tercera posicin, la segunda a la primera y la tercera a la segunda.

22

Colas Estas no permiten un acceso concreto son lneas de informacin en la que accede de un modo determinado, que viene estructurado como FIFO (First In, First Out) que significa que el primero dato que entrar es el primero dato en salir, estas son representados en memorias que como arreglos y como listas ordenadas. Tambin son usados por las simulaciones, planificaciones y los procesos de entrada y salida con buffer. Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operacin de insercin push se realiza por un extremo y la operacin de extraccin pop por el otro. Tambin se le llama estructura FIFO (del ingls First In First Out), debido a que el primer elemento en entrar ser tambin el primero en salir. Las colas se utilizan en sistemas informticos, transportes y operaciones de investigacin (entre otros), dnde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas. Usos concretos de la cola La particularidad de una estructura de datos de cola es el hecho de que slo podemos acceder al primer y al ltimo elemento de la estructura. As mismo, los elementos slo se pueden eliminar por el principio y slo se pueden aadir por el final de la cola.

23

Ejemplos de colas en la vida real seran: personas comprando en un supermercado, esperando para entrar a ver un partido de bisbol, esperando en el cine para ver una pelcula, una pequea peluquera, etc. La idea esencial es que son todas lneas de espera. Operaciones bsicas:

Crear: se crea la cola vaca. Encolar: (aadir, entrar, push): se aade un elemento a la cola. Se aade al final de esta. Desencolar:(sacar, salir, pop): se elimina el elemento frontal de la cola, es decir, el primer elemento que entr. Frente: (consultar, front): se devuelve el eleme Tipos de colas:

Colas circulares (anillos): en las que el ltimo elemento y el primero estn unidos.

24

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 atendern de modo convencional segn la posicin que ocupen. Hay 2 formas de implementacin: 1. Aadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad. 2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

Bicolas: son colas en donde los nodos se pueden aadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes: Bicolas de entrada restringida: Son aquellas donde la insercin slo se hace por el final, aunque podemos eliminar al inicio al final. Bicolas de salida restringida: Son aquellas donde slo Listas.

Son elementos de coleccin que almacenar informacin, en lista de una estructura de datos lineales. Estas listas vienen enlazada o encadenada en una coleccin de nodos o elementos; un nodo siempre contiene la direccin de memoria del siguiente nodo de informacin y un apuntador es la direccin de memoria de un nodo. Es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias(punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.25

Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminacin de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto est previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas. Historia: Las listas enlazadas fueron desarrolladas en 1955-56 por Cliff Shaw y Herbert Simn en RAND Corporation como la principal estructura de datos para su Lenguaje de Procesamiento de la Informacin (IPL). IPL fue usado por los autores para desarrollar varios programas relacionados con la inteligencia artificial, incluida la Mquina de la Teora General, el Solucionador de Problemas Generales, y un programa informtico de ajedrez. Se public en IRE Transactions on Information Theory en 1956, y en distintas conferencias entre 1957-1959, incluida Proceedings of the Western Joint Computer en 1957 y 1958, y en Information Processing (Procendents de la primera conferencia internacional del procesamiento de la informacin de la Unesco) en 1959. El diagrama clsico actual, que consiste en bloques que representan nodos de la lista con flechas apuntando a los sucesivos nodos de la lista, apareci en Programming the Logic Theory Machine, de Newell y Shaw. Newell y Simon fueron reconocidos por el ACM Turing Award en 1975 por hacer contribuciones bsicas a la inteligencia artificial, a la psicologa del conocimiento humano y al procesamiento de las listas .26

El problema de los traductores del procesamiento natural del lenguaje condujo a Vctor Yngve del Instituto Tecnolgico de Massachusetts(MIT) a usar listas enlazadas como estructura de datos en su COMIT, lenguaje de programacin para computadoras, que investig en el campo de la Lingstica computacional. Un informe de este lenguaje, titulado A programming language for mechanical translation apareci en Mechanical Translation en 1958. LISP, el principal procesador de listas, fue creado en 1958. Una de las mayores estructuras de datos de LISP es la lista enlazada. En torno a los 60, la utilidad de las listas enlazadas y los lenguajes que utilizaban estas estructuras como su principal representacin de datos estaba bien establecida. Bert Green del MIT Lincoln Laboratory, public un estudio titulado Computer languages for symbol manipulation en IRE Transaction on Human Factors in Electronics en marzo de 1961 que resuma las ventajas de las listas enlazadas. Un posterior artculo, A Comparison of list-processing computer languages by Bobrow and Raphael, apareca en Communications of the ACM en abril de 1964. Muchos sistemas operativos desarrollados por Technical Systems Consultants (originalmente de West Lafayette Indiana y despus de Raleigh, Carolina del Norte) usaron listas enlazadas simples como estructuras de ficheros. Un directorio de entrada apuntaba al primer sector de un fichero y daba como resultado porciones de la localizacin del fichero mediante punteros. Los sistemas que utilizaban esta tcnica incluan Flex (para el Motorola 6800 CPU), mini-Flex (la misma CPU) y Flex9 (para el Motorola 6809 CPU). Una variante desarrollada por TSC se comercializ a Smoke Signal Broadcasting en California, usando listas doblemente enlazadas del mismo modo. El sistema operativo TSS, desarrollado por IBM para las mquinas System 360/370, usaba una lista doblemente enlazada para su catlogo de ficheros de sistema. La estructura del directorio era similar a Unix,27

donde un directorio poda contener ficheros u otros directorios que se podan extender a cualquier profundidad. Una utilidad fue creada para arreglar problemas del sistema despus de un fallo desde las porciones modificadas del catlogo de ficheros que estaban a veces en memoria cuando ocurra el fallo. Los problemas eran detectados por comparacin de los links posterior y anterior por consistencia. Si el siguiente link era corrupto y el anterior enlace del nodo infectado era encontrado, el posterior link era asignado al nodo con el link del anterior. Tipos de Listas Enlazadas y Listas enlazadas lineales y Listas simples enlazadas La lista enlazada bsica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vaca, si es el ltimo nodo.

Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo y Lista Doblemente Enlazada Un tipo de lista enlazada ms sofisticado es la lista doblemente enlazada o lista enlazadas de dos vas. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el ltimo nodo.

28

Una lista doblemente enlazada contiene tres valores: el valor, el link al nodo siguiente, y el link al anterior En algn lenguaje de muy bajo nivel, XOR-Linking ofrece una va para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque el uso de esta tcnica no se suele utilizar. y Listas enlazadas circulares En una lista enlazada circular, el primer y el ltimo nodo estn unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier direccin hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el ms usado para dirigir buffers para ingerir datos, y para visitar todos los nodos de una lista a partir de uno dado.

Una lista enlazada circular que contiene tres valores enteros y Listas enlazadas circulares simples Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del ltimo apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados despus de uno que ya tengamos referenciado. Por esta razn, es usual quedarse con una referencia solamente al ltimo elemento en una lista enlazada circular simple, esto nos permite rpidas inserciones al principio, y tambin permite accesos al primer nodo desde el puntero del ltimo nodo.29

y Lista Enlazada Doblemente Circular En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al ltimo y el enlace siguiente del ltimo nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algn nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que est en la cabeza o al nodo cola, y as mantener el orden tan bien como en una lista doblemente enlazada. y Nodos Centinelas A veces las listas enlazadas tienen un nodo centinela (tambin llamado falso nodo o nodo ficticio) al principio o al final de la lista, el cual no es usado para guardar datos. Su propsito es simplificar o agilizar algunas operaciones, asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la lista (incluso alguna que no contenga datos) siempre tenga un primer y ltimo nodo. Ventajas: Como muchas opciones en programacin y desarrollo, no existe un nico mtodo correcto para resolver un problema. Una estructura de lista enlazada puede trabajar bien en un caso pero causar problemas en otros. He aqu una lista con algunas de las ventajas ms comunes que implican las estructuras de tipo lista. En general, teniendo una coleccin dinmica donde los elementos estn siendo aadidos y eliminados frecuentemente e importa la localizacin de los nuevos elementos introducidos se incrementa el beneficio de las listas enlazadas.

30

Listas Enlazadas vs. Vectores o Matrices Array Lista Enlazada Indexado Insercin / Eliminacin al final O(1) O(1) O(n) O(1) or O(n)2 O(1) Simples s

Insercin / Eliminacin en la mitad O(n) No

Persistencia

Localizacin

Buena Mala

Las listas enlazadas poseen muchas ventajas sobre los arrays. Los elementos se pueden insertar en una lista indefinidamente mientras que un array tarde o temprano se llenar necesitar ser redimensionado, una costosa operacin que incluso puede no ser posible si la memoria se encuentra fragmentada. En algunos casos se pueden lograr ahorros de memoria almacenando la misma cola de elementos entre dos o ms listas es decir, la lista acaba en la misma secuencia de elementos. De este modo, uno puede aadir nuevos elementos al frente de la lista manteniendo una referencia tanto al nuevo como a los viejos elementos - un ejemplo simple de una estructura de datos persistente.

31

Desventajas: Por otra parte, los arrays permiten acceso aleatorio mientras que las listas enlazadas slo permiten acceso secuencial a los elementos. Las listas enlazadas simples, de hecho, solo pueden ser recorridas en una direccin. Esto hace que las listas sean inadecuadas para aquellos casos en los que es til buscar un elemento por su ndice rpidamente, como el heapsort. El acceso secuencial en los arrays tambin es ms rpido que en las listas enlazadas. Otra desventaja de las listas enlazadas es el almacenamiento extra necesario para las referencias, que a menudos las hacen poco prcticas para listas de pequeos datos como caracteres o valores booleanos. Tambin puede resultar lento y abusivo el asignar memoria para cada nuevo elemento. Existe una variedad de listas enlazadas que contemplan los problemas anteriores para resolver los mismos. Un buen ejemplo que muestra los pros y contras del uso de arrays sobre listas enlazadas es la implementacin de un programa que resuelva el problema de Josephus. Este problema consiste en un grupo de personas dispuestas en forma de crculo. Se empieza a partir de una persona predeterminada y se cuenta n veces, la persona n-sima se saca del crculo y se vuelve a cerrar el grupo. Este proceso se repite hasta que queda una sola persona, que es la que gana. Este ejemplo muestra las fuerzas y debilidades de las listas enlazadas frente a los arrays, ya que viendo a la gente como nodos conectados entre s en una lista circular se observa como es ms fcil suprimir estos nodos. Sin embargo, se ve como la lista perder utilidad cuando haya que encontrar a la siguiente persona a borrar. Por otro lado, en un array el suprimir los nodos ser costoso ya que no se puede quitar un elemento sin reorganizar el resto. Pero en la bsqueda de la n-sima persona tan slo basta con indicar el ndice n para acceder a l resultando mucho ms eficiente.

32

Arboles. Un rbol es una estructura de datos ampliamente usada que imita la forma de un rbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el rbol y puede tener cero o ms nodos hijos conectados a l. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, tambin decimos que b es hijo de a). Slo puede haber un nico nodo sin padres, que llamaremos raz. Un nodo que no tiene hijos se conoce como hoja. Los dems nodos (tienen padre y uno o varios hijos) se les conoce como rama. Es un conjunto de grafos formados por nodos y conectados por las aristas. Contienen la raz, caminos, padre, hijos, hojas y subrbol. Definicin: Formalmente, podemos definir un rbol de la siguiente forma:

Caso base: un rbol con slo un nodo (es a la vez raz del rbol y hoja). Un nuevo rbol a partir de un nodo nr y k rboles de races con elementos cada uno, puede construirse estableciendo una relacin padre-hijo entre nr y cada una de las races de los k rboles. El rbol resultante de nodos tiene como raz el nodo nr, los nodos son los hijos de nr y el conjunto de nodos hoja est formado por la unin de los k conjuntos hojas iniciales. A cada uno de los rboles Ai se les denota ahora subrbolesde la raz.

Una sucesin de nodos del rbol, de forma que entre cada dos nodos consecutivos de la sucesin haya una relacin de parentesco, decimos que es un recorrido rbol. Existen dos recorridos tpicos para listar los nodos de un rbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y as sucesivamente. En el segundo, por su parte, antes de33

listar los nodos de nivel n + 1 (a distancia n+ 1 aristas de la raz), se deben haber listado todos los de nivel n. Otros recorridos tpicos del rbol son preorden, postorden e inorden:

El recorrido en preorden, tambin llamado orden previo consiste en recorrer en primer lugar la raz y luego cada uno de los hijos en orden previo. El recorrido en inorden, tambin llamado orden simtrico (aunque este nombre slo cobra significado en los rboles binarios) consiste en recorrer en primer lugar A1, luego la raz y luego cada uno de los hijos en orden simtrico. El recorrido en postorden, tambin llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por ltimo la raz.

Finalmente, puede decirse que esta estructura es una representacin del concepto de rbol en teora de grafos. Un rbol es un grafo conexo y acclico (ver tambin teora de grafos y Glosario en teora de grafos). Tipos de arboles

34

y rboles Binarios y rbol de bsqueda binario auto-balanceable y rboles AVL y rboles Rojo-Negro y rbol AA y rboles Multicamino y rboles B (Arboles de bsqueda multicamino autobalanceados) y rbol-B+ y rbol-B* Usos de los rboles y Representacin de datos jerrquicos. y Como ayuda para realizar bsquedas en conjuntos de datos (ver tambin: algoritmos de bsqueda en rboles). Grafos. Los grafos son conjunto de puntos en el espacio en donde se hacen llamar vertices, el cual estn conectados por un conjuntos de lneas denominadas aristas en donde tales aristas pueden ser adyacentes, paralelas, cclicas y cruce, en cuanto a los vertices estas pueden ser adyacentes, terminal y aislados. Representacin de un grafo: Existen dos formas de mantener un grafo "G" en la memoria de una computadora, una se llama Representacin secuencial de G, la cual se basa en la matriz de adyacencia A; la otra forma, es la llamada Representacin enlazada de G y se basa en listas enlazadas de vecinos. Independientemente de la forma en que se mantenga un grafo G en la memoria de una computadora, el grafo G normalmente se35

introduce en la computadora por su definicin formal: Un conjunto de nodos y un conjunto de aristasy

Representacin secuencial de un grafo:

Considere el grafo siguiente "G": Conceptos y definiciones: Grafo: Es el conjunto de elementos entre los que existen ligaduras orientadas. Suponemos un conjunto x = {A, B, C, D, E, F} y una relacin G = (x, T) de manera que: TA = {B, C, D} TB = {A} TC = {B, D, F} TD = {D, E} TE = {0} TF = {0} Lo representamos mediante un diagrama sagital. Para ver el grfico seleccione la opcin "Descargar" del men superior Cuadro de doble entrada. A B C DE F36

A B 1 C D E F

1 1 1

1

1 1 1

1

Definiciones: Vrtice: Elemento de un conjunto que constituye un grafo. Arco: Par de elementos entre los que existe relacin teniendo en cuenta la orientacin, es decir que exista relacin orientada: (A, B); (A, C); (B, A); Camino: Es una sucesin de arcos adyacentes que nos permiten pasar de un vrtice a otro: (A, C, D, E). Circuito: Es un camino en el que el vrtice inicial y final coinciden: (A, C, B, A); (A, B, A). Bucle: Es un arco en el que el vrtice origen y final coinciden: (D) Arista: Relacin entre dos vrtices sin atender a la orientacin: (C, A); (A, C). Cadena: Sucesin de aristas adyacentes: (F, C, B, A). Longitud de un camino o circuito: Se mide por el nmero de arcos que constituyen el camino o circuito. Grafo conexo: Entre todo par de vrtices podemos establecer al menos una cadena.

37

A Grafo no conexo ya que E no se relaciona con nadie y nadie se relaciona con l. Para ver el grfico seleccione la opcin "Descargar" del men superior Grafo fuertemente conexo: Es aquel que entre cualquier par de vrtices podemos establecer al menos un camino. Grafo sin circuitos: Es aquel que no tiene circuitos. A nosotros nos interesan los grafos sin circuitos y conexos.

Sistemas de archivos. Un sistema de archivos son los mtodos y estructuras de datos que un sistema operativo utiliza para seguir la pista de los archivos de un disco o particin; es decir, es la manera en la que se organizan los archivos en el disco. El trmino tambin es utilizado para referirse a una particin o disco que se est utilizando para almacenamiento, o el tipo del sistema de archivos que utiliza. As uno puede decir tengo dos sistemas de archivo refirindose a que tiene dos particiones en las que almacenar archivos, o que uno utiliza el sistema de archivos extendido , refirindose al tipo del sistema de archivos. Los archivos tambin denominados ficheros son una coleccin de informacin (datos relacionados entre s), localizada o almacenada como una unidad en alguna parte de la computadora. Los archivos son el conjunto organizado de informaciones del mismo tipo, que pueden utilizarse en un mismo tratamiento; como soporte material de estas informaciones.

38

Un sistema de archivos es un mtodo para el almacenamiento y organizacin de archivos de computadora y los datos que estos contienen, para hacer ms fcil la tarea encontrarlos y accederlos. Los sistemas de archivos son usados en dispositivos de almacenamiento como discos duros y CD-ROM e involucran el mantenimiento de la localizacin fsica de los archivos. Ms formalmente, un sistema de archivos es un conjunto de tipo de datos abstractos que son implementados para el almacenamiento, la organizacin jerrquica, la manipulacin, el acceso, el direccionamiento y la recuperacin de datos. Los sistemas de archivos comparten mucho en comn con la tecnologa de las bases de datos. En general, los sistemas operativos tienen su propio sistema de archivos. En ellos, los sistemas de archivos pueden ser representados de forma textual (ej.: el shell de DOS) o grficamente (ej.:Explorador de archivos en Windows) utilizando un gestor de archivos. El software del sistema de archivos se encarga de organizar los archivos (que suelen estar segmentados fsicamente en pequeos bloques de pocos bytes) y directorios, manteniendo un registro de qu bloques pertenecen a qu archivos, qu bloques no se han utilizado y las direcciones fsicas de cada bloque. Los sistemas de archivos pueden ser clasificados en tres categoras: disco, sistemas y sistemas de archivos de propsito especial. Los sistemas de archivos o ficheros (en ingls:filesystem), estructuran la informacin guardada en una unidad de almacenamiento(normalmente un disco duro de una computadora), que luego ser representada ya sea textual o grficamente utilizando un gestor de archivos. La mayora de los sistemas operativos manejan su propio sistema de archivos.139

Lo habitual es utilizar dispositivos de almacenamiento de datos que permiten el acceso a los datos como una cadena de bloques de un mismo tamao, a veces llamados sectores, usualmente de 512 bytes de longitud. El software del sistema de archivos es responsable de la organizacin de estos sectores en archivos y directorios y mantiene un registro de qu sectores pertenecen a qu archivos y cules no han sido utilizados. En la prctica, un sistema de archivos tambin puede ser utilizado para acceder a datos generados dinmicamente, como los recibidos a travs de una conexin de red (sin la intervencin de un dispositivo de almacenamiento). Los sistemas de archivos tradicionales proveen mtodos para crear, mover, renombrar y eliminar tanto archivos como directorios, pero carecen de mtodos para crear, por ejemplo, enlaces adicionales a un directorio o archivo (enlace duro en Unix) o renombrar enlaces padres (".." en Unix). El acceso seguro a sistemas de archivos bsicos puede estar basado en los esquemas de lista de control de acceso o capacidades. Las listas de control de acceso hace dcadas que demostraron ser inseguras, por lo que los sistemas operativos experimentales utilizan el acceso por capacidades. Los sistemas operativos comerciales an funcionan con listas de control de acceso. Caractersticas de los sistemas de Archivos y Seguridad o permisos y Listas de control de acceso (ACLs) y UGO (Usuario, Grupo, Otros, en ingls, User, Group, Others) o por sus siglas

40

y Capacidades granuladas y Atributos extendidos (ej.: slo aadir al archivo pero no modificar, no modificar nunca, etc.) y Mecanismo para evitar la fragmentacin y Capacidad de enlaces simblicos o duros y Integridad del sistema de archivos (Journaling) y Soporte para archivos dispersos y Soporte para cuotas de discos y Soporte de crecimiento del sistema de archivos nativo Tipos de sistemas de archivos: Sistemas de archivos de disco: Un sistema de archivo de disco est diseado para el almacenamiento de archivos en una unidad de disco, que puede estar conectada directa o indirectamente a la computadora. Sistemas de archivos de red: Un sistema de archivos de red es el que accede a sus archivos a travs de una red. Dentro de esta clasificacin encontramos dos tipos de sistemas de archivos: los sistemas de archivos distribuidos (no proporcionan E/S en paralelo) y los sistemas de archivos paralelos (proporcionan una E/S de datos en paralelo).

41

Sistemas de archivos de propsito especial: son aquellos tipos de sistemas de archivos que no son ni sistemas de archivos de disco, ni sistemas de archivos de red. Ejemplos: acme (Plan 9), archfs, cdfs, cfs, devfs, udev, ftpfs, lnfs, nntpfs, plumber (Plan 9), procfs, ROMFS, swap, sysfs, TMPFS, wikifs, LUFS, etc. . Archivo secuencial. Es la forma bsica de organizar un conjunto de registros, que forman un archivo, utilizando una organizacin secuencial. En un archivo organizado secuencialmente, lo registros quedan grabados consecutivamente cuando el archivo se utiliza como entrada. En la mayora de los casos, los registros de un archivo secuencial quedan ordenados de acuerdo con el valor de algn campo de cada registro. Semejante archivo se dice que es un archivo ordenado; el campo, o los campos, cuyo valor se utiliza para determinar el ordenamiento es conocido como la llave del ordenamiento. Un archivo puede ordenarse ascendente o descendentemente con base en su llave de ordenamiento. La forma ms comn de estructura de archivo es el archivo secuencial. En este tipo de archivo, un formato fijo es usado para los registros. Todos los registros tienen el mismo tamao, constan del mismo nmero de campos de tamao fijo en un orden particular. Como se conocen la longitud y la posicin de cada campo, solamente los valores de los campos se necesitan almacenarse; el nombre del campo y longitud de cada campo son atributos de la estructura de archivos. Estructura de organizacin: Archivo secuencial es la forma ms simple de almacenar y recuperar registros de un archivo. En un archivo secuencial, se almacenan los registros uno tras otro. El primer registro almacenado se coloca al principio del archivo. El segundo se almacena inmediatamente despus

42

(no existen posiciones sin uso), el tercero despus del segundo. Este orden nunca cambia en la organizacin secuencial. Una caracterstica de los archivos secuenciales es que todos los registros se almacenan por posicin: de primer registro, segundo registro entre otros. Ventajas: Los archivos secuenciales proveen la mejor utilizacin de espacio y son rpidos cuando los registros son accesados secuencialmente. Los archivos con poca volatilidad, gran actividad y tamao variable son altamente susceptibles de ser organizados secuencialmente. La ventaja ms importante de la tcnica de organizacin secuencial de archivos es la capacidad de acceso al "siguiente" registro rpidamente: Mientras que el patrn de acceso a un archivo secuencial se conforme al ordenamiento de registros en el archivo, los tiempos de acceso sern muy buenos. Sin embargo, si el patrn de acceso al programa no se conforma al patrn de ordenamiento de los registros, entonces la eficiencia del programa puede ser terrible. Otra ventaja de los archivos de organizacin secuencial es que son muy sencillos de usar y aplicar. Desventajas: El acceso a un registro es pobre, la localizacin de un determinado registro no se puede hacer individualmente no de manera rpida, y el acceso aleatorio es imprctico.

Adems, en los archivos secuenciales la direccin de registro est implcita y estn vulnerables a fallas del sistema.

43

Escritura de los archivos secuenciales. En estos archivos, la informacin slo puede leerse y escribirse empezando desde el principio del archivo. Los archivos secuenciales tienen algunas caractersticas que hay que tener en cuenta:

1. La escritura de nuevos datos siempre se hace al final del archivo. 2. Para leer un dato concreto del archivo hay que avanzar siempre hasta donde se encuentre dicho dato. Si el dato requerido se encuentra antes del dato en que est se est posicionado el archivo en un momento dado, ser necesario regresar al comienzo del archivo y avanzar hasta el dato necesario. Almacenamiento de archivos Secuenciales Los archivos secuenciales pueden almacenarse en dispositivos de acceso serial o directo. Con frecuencia los dispositivos de acceso serial son considerablemente menos caros que los dispositivos de acceso directo en un sistema de cmputo, pero de hecho, los dispositivos de almacenamiento de acceso directo en una computadora siempre proporcionan mayor capacidad de almacenamiento y acceso ms rpido que los dispositivos de acceso serial. Actualizacin en archivos secuenciales Un archivo maestro representa el punto esttico de algn aspecto de alguna organizacin en un tiempo dado. Los cambios en la organizacin se reflejan en el archivo maestro, y para llevar a cabo la actualizacin del archivo maestro se tendrn que realizar los tipos de actualizacin: Insertar un nuevo registro.44

Borrar un registro. Modificar un registro. Al estar usando un archivo secuencial como archivo maestro, el realizar las operaciones de actualizacin se llevara con el auxilio de un archivo de transacciones, debido a que se realizar el proceso en lote para que sea ms eficiente. Creacin de archivos secuenciales: La creacin de un archivo secuencial se realiza agregando registros al final del archivo, no importa el medio de entrada de datos. El archivo secuencial puede ser almacenado en cintas o en discos magnticos. Un archivo secuencial puede tener registros fijos o variables, la declaracin del archivo y la definicin del registro depender del lenguaje de programacin que se vaya a usar. Clasificacin de los archivos secuenciales: Normalmente el uso de los archivos secuenciales se da en procesos en lote, donde se ha hecho notar que son eficientes cuando se llevan a cabo diversas operaciones sobre una gran cantidad de registros o de todo el archivo. Esta eficiencia se logra con una accin: la clasificacin, proceso que no es exclusivo de los archivos secuenciales, pero si necesaria para diversa operaciones. La clasificacin es el proceso de examinar los registros en un archivo y ponerlos en una secuencia ascendente o descendente basada en el valor de uno o ms campos del registro.

45

8. Archivos indexados: Los archivos secuenciales indexados retienen la limitacin del archivo secuencial: la eficacia en el procesamiento se limita al basado en un nico campo del archivo. Cuando es necesario buscar un registro basndose en algn otro atributo distinto del campo clave ambas formas de archivo secuencial no son adecuadas. En algunas aplicaciones esta flexibilidad es deseable. Para alcanzar esta flexibilidad, se necesita una estructura que utilice mltiples ndices, uno para cada tipo de campo que pueda ser objeto de la bsqueda. Se suelen utilizar dos tipos de ndices. Uno ndice exhaustivo contiene una entrada par cada registro del archivo principal. Otro ndice parcial contendr entradas a los registros donde este el campo de inters. Con registros de longitud variable, algunos registros no contendrn todos los campos. Los archivos indexados son muy utilizados en aplicaciones donde es crtica la oportunidad de la informacin y donde los datos son rara vez procesados de forma exhaustiva. Los archivos secuenciales indexados retienen la limitacin del archivo secuencial: la eficacia en el procesamiento se limita al basado en un nico campo del archivo. Cuando es necesario buscar un registro basndose en algn otro atributo distinto del campo clave ambas formas de archivo secuencial no son adecuadas. En algunas aplicaciones esta flexibilidad es deseable. Para alcanzar esta flexibilidad, se necesita una estructura que utilice mltiples ndices, uno para cada tipo de campo que pueda ser objeto de la bsqueda.

46

Se suelen utilizar dos tipos de ndices. Uno ndice exhaustivo contiene una entrada par cada registro del archivo principal. Otro ndice parcial contendr entradas a los registros donde este el campo de inters. Con registros de longitud variable, algunos registros no contendrn todos los campos. Los archivos indexados son muy utilizados en aplicaciones donde es crtica la oportunidad de la informacin y donde los datos son rara vez procesados de forma exhaustiva. 9. Archivos directos o de dispersin: Los archivos directos explotan la capacidad de los discos para acceder directamente a cualquier bloque de direccin conocida. Como en los archivos secuenciales y secuenciales indexados, se requiere un campo clave en cada registro. Sin embargo, aqu no hay concepto de ordenamiento secuencial. Los archivos directos explotan la CAPACIDAD de los discos para acceder DIRECTAMENTE a cualquier bloque de direccin conocida. Como en los archivos secuenciales y secuenciales indexados, se requiere un CAMPO CLAVE en cada registro. Sin embargo, aqu NO hay concepto de ORDENAMIENTO SECUENCIAL. Los archivos directos son muy usados donde se necesita un ACCESO muy RPIDO, donde se usan registros de LONGITUD FIJA y donde siempre se ACCEDE a los registrosg DE UNA VEZ. La organizacin directa es aquella que permite un POSICIONAMIENTO sobre registros especficos al LOCALIZAR una LLAVE. Lo anterior permite AGILIZAR la localizacin de un dato en un archivo determinado al no requerirse el procesamiento de los registros contiguos previos.47

Un archivo se accesa directamente cuando el programa que lo utiliza especifica directamente la posicin dentro del archivo que se accesar. Por ejemplo el programa puede leer la lnea nmero 200, luego la lnea 50000 y ms tarde la lnea 1. Es importante notar que para el sistema operativo todos los archivos pueden ser accesados directamente. Para que un archivo se pueda accesar cmodamente en forma directa, es necesario que sus lneas tengan un nmero fijo de caracteres. Por esta razn, los archivos de acceso directo que usaremos en los ejemplos, tendrn la extensin ".raf". Operaciones:

Creacin de archivo:.- En este proceso se pretende solamente crear un archivo nuevo en disco con su nombre tipo y especialidad de almacenamiento de datos apropiado. Apertura de archivos: En este caso se pretende abrir un archivo ya existente en disco para procesarlo ya sea para cargar o grabar estructuras en sus registros o leer algn registro en especial para mandarlo a una variable de cualquier tipo. Cierre de archivos: Es la operacin mas importante en cualquier programa que maneje archivos, o se cierra el archivo como ultima instruccin del programa o se vera el anuncio ABORT, RETRY, FAIL, 98, scandisk. Altas en archivos: En este proceso se captura una estructura en memoria con sus datos pertinentes y despus se graba la estructura al archivo en disco.

48

Lectura de archivos: En este proceso se abre el archivo, se manda el registro de disco a una estructura en memoria para su procesamiento. Consulta de archivos: En este proceso se pretende desplegar todos los registros del archivo en disco a la pantalla ya sea consola o mejor an, a una pgina html. Bsqueda de archivos: Una de las operaciones mas comunes consiste en que el usuario pide toda la informacin de algn rengln en disco proporcionando la informacin de algn campo generalmente el campo clave de la estructura. Filtros: En este proceso el usuario esta interesado en algn conjunto de renglones con caractersticas comunes (condicin), por ejemplo todos los alumnos de "sistemas" o todos los empleados que ganen mas de $500.00 pesos, o todos los clientes que sean de "Tijuana", etc Modificaciones de registros: Problema muy comn, donde los datos originales ya grabados se tienen que cambiar o actualizar, por ejemplo el nombre no era "Juan" es "Juana", o la calificacin no es 100 es 20. Bajas de registros: tambin muy comn este proceso, por ejemplo el alumno ya egreso, el cliente huyo, entre otros. 10.Archivos aleatorios: Los archivos aleatorios son tambin llamados archivos directos, a diferencia de los archivos secuenciales, almacenan los datos con una estructura diferente. Los datos se guardan en registros mediante una estructura definida de tipo. Para declarar un archivo de acceso directo se realiza con las palabras reservadas file of.

49

En la funcin de este archivo nos facilita acceder a un dato o registro directamente sin necesidad de pasar por algn otro, es decir, si se necesita conocer o editar la informacin contenida en el registro n nos vamos directamente a l, estos archivos tienen diferentes secuencias de almacenar datos como lo es el secuencial que debamos leer todo el archivo, no podamos leer datos que estuviesen en la lnea 35 del mismo sin antes pasar por todos los datos anteriores. Y los archivos aleatorios o directos almacenan los datos con una estructura diferente que se guardan en registros mediante una estructura que es de tipo type (structura definida por nosotros) tambin llamada UDT. Los Archivos aleatorios almacenan datos en forma de registros mediante una estructura definida de tipo Type (estructura definida por nosotros) tambin llamada UDT. Para declarar un archivo de acceso directo se realiza con las palabras reservadas FILE OF. Los registros de tipo RECORD permiten grabar en un solo registro un grupo de datos que pueden ser de diferentes tipos, uno de tipo INTEGER, uno de tipo STRING, deben ser declarados antes de las variables en una seccin llamada TYPE. Aun cuando se tenga declarado el archivo no es posible grabar nada en el si no se le asigna un nombre real para guardarlo en el disco. El proceso de dicha asignacin es el mismo que para los archivos de texto: Assign (archivo, "nombre.ext"), abrir archivos. Cada uno de los registros de un archivo esta referenciado por un numero especifico comenzando desde el registro 0 y aumentando de 1 en 1.La funcin FilePos devuelve el numero de registro actual, su sintaxis es: -FilePos (variableArchivo)-Seek (variableArchivo, NumResgistro) -Seek (variablearchivo, FileSize (variableArchivo).

50

Para la lectura y escritura de un archivo de acceso directo nicamente se utilizan los procedimientos Read y Write. Para cerrar los archivos abiertos se procede ihual que en uno de acceso secuencial, utilizando el procedimiento close. Esta estructura la podemos definir los usuarios y al momento de acceder a un registro lo podemos hacer de forma directa entonces se puede decir que este archivo trabaja de forma mas rpida. Para declarar un archivo se deben utilizar las palabras reservadas file of.Los registros de tipo record permiten la reduccin de creacin de mas archivos debido a que el registro record tiene la ventaja de gravar en un solo registro datos diferentes de tipo integer y string este registro record debe ser declarado antes de la variable. Es aquel en donde los datos se guardan en registros mediante una estructura definida de tipo Type (estructura definida por nosotros) tambin llamada UDT. Estos permiten acceder a cualquier parte del fichero en cualquier momento, como si fueran arrays en memoria. Las operaciones de lectura y/o escritura pueden hacerse en cualquier punto del archivo. En general se suelen establecer ciertas normas para la creacin, aunque no todas son obligatorias: Abrir el archivo en un modo que te permita leer y escribir. Esto no es imprescindible, es posible usar archivos de acceso aleatorio slo de lectura o de escritura. Abrirlo en modo binario, ya que algunos o todos los campos de la estructura pueden no ser caracteres. Usar funciones como fread y fwrite, que permiten leer y escribir registros de longitud constante desde y hacia un fichero. Usar la funcin fseek para situar el puntero de lectura/escritura en el lugar apropiado de tu archivo.

51

Conclusin. Turbo Pascal es un lenguaje de programacin de alto nivel bajo entorno mas-dos, con esta poderosa herramienta, se pueden crear un sin nmero de aplicaciones que van desde simples operaciones aritmticas como sumas, restas, hasta sistemas operativos, lenguajes de programacin, simulaciones, videojuegos, manejadores de base de datos, virus y una amplia gama de programas cuyo nico lmite es solo la imaginacin del programador. A pesar de que Turbo Pascal es un lenguaje orientado a objetos, este tutor esta orientado a programacin estructurada. La recursividad en pascal, a un procedimiento o funcin le es permitido no solo invocar a otro procedimiento o funcin sino tambin invocarse a si mismo. Esta unida es importante como todas las dems pero esta nos ayudara a hacer lo q necesitemos. Un archivo se define como grupo de datos estructurados que son almacenados en algn medio y pueden ser usados por las aplicaciones y el sistema de archivos es la forma en que una computadora organiza, da nombre, almacena y manipula los archivos. La informacin se encuentra organizada por: datos, Campos, registro, archivo y base de Datos. Un sistema de archivo es un conjunto de tipo de datos abstractos que son implementados para el almacenamiento, la organizacin jerrquica, la manipulacin, el acceso, el direccionamiento y la recuperacin de datos. Los archivos aleatorios o archivos directos son los que almacenan datos con estructuras diferentes. Esta estructura la podemos definir los usuarios y al momento de acceder a un registro lo52

podemos hacer de forma directa entonces se puede decir que este archivo trabaja de forma mas rpida. Para declarar un archivo se deben utilizar las palabras reservadas file of. Los registros de tipo record permiten la reduccin de creacin de mas archivos debido a que el registro record tiene la ventaja de gravar en un solo registro datos diferentes de tipo integer y string este registro record debe ser declarado antes de la variable.

Los diferentes objetos de informacin con los que trabaja un programa en Pascal se conocen como datos. Todos los datos tienen un tipo asociado con ellos. Pueden ser de tipo carcter, entero, un nmero real, entre otros. Los tipos de datos definen un conjunto de valores y las operaciones sobre estos valores.1 Casi todos los lenguajes de programacin explcitamente incluyen la notacin del tipo de datos, aunque lenguajes diferentes pueden usar terminologa diferente. Un tipo de dato puede ser tambin visto como una limitacin impuesta en la interpretacin de los datos en un sistema de tipificacin, describiendo la representacin, interpretacin y la estructura de los valores u objetos almacenados en la memoria del ordenador. En los lenguajes de programacin y en otros programas utilitarios tales como una planilla de clculos, un tipo de dato es un atributo de una parte de los datos que indica al ordenador (y/o al programador) algo sobre la clase de datos sobre los que se va a procesar. Esto incluye imponer restricciones en los datos, como qu valores pueden tomar y qu operaciones se pueden realizar.

53

Bibliografa. http://en.wikipedia.org/wiki/Turbo_Pascal http://es.wikipedia.org/wiki/Turbo_Pascal http://www.lacoctelera.com/myfiles/ncastillo_unefai/Objetivo-8.2Recursividad.pdf http://www.lacoctelera.com/myfiles/ncastillo_unefai/Unidad-11.Archivos-aleatorios.pdf http://www.buenastareas.com/temas/procedimientos-en-laprogramaci%C3%B3n-modular/80 http://www.monografias.com/trabajos6/sistar/sistar.shtml http://www.monografias.com/trabajos6/sistar/sistar.shtml#indexados http://catedraprogramacion.foroactivo.net/t275-archivos-secuencialesconcepto http://www.mitecnologico.com/Main/OperacionesSobreArchivosSecuen ciale http://www.buenastareas.com/ensayos/DatosComplejos/483405.html

54