“AÑO DE LA DIVERSIFICACIÓN PRODUCTIVA Y DELFORTALECIMIENTO DE LA EDUCACIÓN” UNIVERSIDAD NACIONAL DE PIURA FACULTAD DE INGENIERIA INDUSTRIAL ESCUELA DE INGENIERIA INFORMATICA TEMA: FICHEROS Y NODOS CURSO: ALGORITMIA Y METODO DE ACCESO PROFESOR: ING.MOISES SAAVEDRA SARANGO ALUMNO: ODAR BENITES JOSUE. CICLO: V FECHA: 22-07-2015 FLUJOS Y ARCHIVOS o bien de acceso directo. El acceso directo implica el acceso a un registro determinado. por el canal que comunica el archivo con el . un archivo es. actualizados o borrados y almacenados de nuevo en el archivo con todos los cambios realizados. Otros ejemplos. Java dispone de clases para trabajar las secuencias de bytes como datos de tipos básicos (int. El acceso secuencial implica el acceso a un archivo según el orden de almacenamiento de sus registros. el fichero de inventario..Un fichero (archivo) de datos o. sencillamente. El diseño del archivo es el que establece la forma de manejar las secuencias de bytes. que son la representación de los datos almacenados.).. simplemente. sin que ello implique la consulta de los registros precedentes. una secuencia de bytes. Este tipo de acceso sólo es posible con soportes direccionales. • Acceso directo. String. Los datos están organizados de tal modo que puedan ser recuperados fácilmente. se consideran dos tipos de acceso a los registros de un archivo: • Acceso secuencial. con una organización secuencial. para escribir o leer del archivo objetos. uno tras otro. En Java. Un archivo en una computadora es una estructura diseñada para contener datos. stocks. incluso. un archivo es una colección de registros relacionados entre sí. double. La apertura de un archivo supone establecer la conexión del programa con el dispositivo que contiene al archivo. con aspectos en común y organizados para un propósito específico. un fichero de una clase escolar contiene un conjunto de registros de los estudiantes de esa clase. Según las características del soporte empleado y el modo en que se han organizado los registros. Por ejemplo. Entre el origen y el destino debe existir una conexión o canal (pipe) por la que circulen los datos. Un flujo (stream) es una abstracción que se refiere a un flujo corriente de datos que fluyen entre un origen o fuente (productor) y un destino o sumidero (consumidor). etc. el fichero de nóminas de una empresa. err. Abrir un archivo supone crear un objeto que queda asociado a un flujo. en Java se crean automáticamente tres objetos flujo. una secuencia de bytes almacenados en un dispositivo externo (normalmente en disco). son tres canales por los que pueden fluir datos . System. Si el archivo se abre para entrada. FILE . permite al programa la salida de errores por pantalla. System. por tanto. En Java. que puede estar conectado a un dispositivo o a otro.programa van a fluir las secuencias de datos.in. un archivo es simplemente un flujo externo. Estos son objetos definidos en la clase System: System. Objeto para salida estándar de errores. una abstracción. Al comenzar la ejecución de un programa. Objeto entrada estándar. Objeto salida estándar. El flujo es. es un flujo de archivo de salida. permite al programa la salida de datos por pantalla.out. Los programas leen o escriben en el flujo. de entrada o de salida. Si el archivo se abre para salida. es un flujo de archivo de entrada. de tal forma que las operaciones que realizan los programas son sobre el flujo independientemente del dispositivo al que esté asociado. permite la entrada al programa de flujos de bytes desde el teclado. La clase proporciona métodos para leer el archivo byte por byte o un método para leer grupos de bytes. long.list (). comprueba las propiedades del archivo (data. et c) y otras características. obtener la ruta completa del directorio/ fichero. se lanzará una excepción de tipo java.FileNotFoundException. etc. readonly.IOException o java. Si no existe el archivo. desde la posición inicial. escribe o lee los datos del archivo. Java utiliza dos representaciones de textos: Unicode internamente y UTF para I / O. Hay un segundo constructor que en lugar de File. double. / / lista de los archivos } La clase File proporciona métodos comunes para verificar que existe la ruta de acceso en la máquina local. pasar la posición actual en el archivo y posicionar en una nueva posición.io. que puede ser "r" para lectura y "rw" para la lectura y la escritura. En caso de errores. de la clase RandomAccessFile .io.Esta clase es una representación abstracta de un archivo o directorio de los sistemas de archivos.txt File dir = new File(“C: \ \ tmp”).isDirectory () ) { String[ ] arqs = dir. Para ello vamos a utilizar los streams (flujos) de entrada y salida de datos . File arch = new File(“C: \ \ texto. No accederemos a los datos de estos archivos directamente. recibe una cadena con la ruta del archivo y una cadena con el modo de acceso. crear o eliminar el directorio/ fichero con el nombre especificado. El constructor de la clase coge dos argumentos: una instancia File y otra String con el modo de acceso.txt ”). / / dir representa el directorio c: \ tmp if ( dir. hace una lista de todos los archivos en la ruta del directorio. se crea un nuevo archivo vacío. accede a una posición del archivo. / / arq representa al archivo texto. Esta clase proporciona métodos para comprobar el tamaño del archivo (en bytes).exist s() && dir. en un nivel más elevado de tipos de datos como int. RANDOM ACCESSFILE La clase RandomAccessFile ofrece la posibilidad de acceder a los archivos de forma no secuencial. . char. // escribiendo datos en el archivo raf.readUTF(). raf.writeDouble( 100. String txt = raf.txt”).File arch = new File(“C:\\texto. // leyendo a partir de la posición inicial raf. double saldo = raf. raf. RandomAccessFile raf = new RandomAccessFile( arq.readDouble().seek( 0 ).close(). // siempre cierre el recurso STREAMS . “rw” ).0 ).writeUTF( “Saldo=“ ). En Java. Hay dos clases abstractas. txt”). fos. byte[] bytes = new byte[10]. read( bytes ). lo que hace que sea un acceso fácil y estandarizado para los datos leí dos y escritos. tienen los métodos read () y write (). respectivamente. un constructor recibe un archivo y el otro recibe una cadena con el nombre de la ruta del archivo.out. leen y escriben bytes. fi s. Ambas clases tienen el método close(). . es decir . STREAMS DE BAJO NIVEL Las clases FileInputStream y FileOutputStream son dos clases de bajo nivel de lectura y escritura de datos de un archivo en disco. Estas dos clases tienen dos constructores. haciendo uso de los streams de bajo nivel. La clase FileInputStream tiene otros métodos como: avaliable () y skip (). Estas corrientes de trabajo con bytes de datos pueden ser . Para ello contamos con corrientes de bajo y de alto nivel. File arch = new Fi l e(“C:\ \ texto. Estos datos pueden proceder de un archivo. fos. Fi l eOutputStr eam fos = new Fi l eOutputStr eam( arch ). de leen y escriben datos en un formato general (datos primitivos y Strings). read(). se generaliza esta corriente de flujo como entrada y salida. FileInputStream fis = new FileInputStream( arch ). que son: InputStream(para la entrada de datos) y OutputStream (para la salida). write( “String que va ser guardada”.println( bytes ). Estas clases sólo funcionan con la lectura y escritura de bytes de datos. close(). byte byteLido = (byte) fis. que son la base de los f lujos en Java. getBytes() ). para ello.Los streams es un medio de flujo de datos. a menudo. Los streams de alto nivel. System. Los streams de bajo nivel trabajan con bytes. bastantes difíciles de manejar . txt”). Fi l e arch = new Fi l e(“C:\ \ texto. como de la red o de un dispositivo conectado a la computadora. double d = di s. como InputStream y OutputStream. dis. ByteArray OutputStream. readDoubl e(). / / cierre todos l os streams .close(). Fi leOutputStream fos = new Fi leOutputStream( arch ). las clases no leen directamente desde un archivo. además de los bytes de datos. writeUTF(“String con texto UTF”). cl ose(). Además. txt”). Existen también otras clases de bajo nivel.fi s. DataOutputStream dos = new DataOutputStream( fos ). txt”). En realidad. STREAMS DE ALTO NIVEL Los streams de alto nivel permiten la lectura y escritura de datos sobre otros tipos. String s = di s. Fi leInputStream fi s = new Fi leInputStr eam( arch ). dos. File arch = new Fi l e(“C:\ \ texto. también tenemos las clases: ByteArray InputStream. 99 ). y PipedInputStream PipedOutputStream. close(). readUTF(). sino que leen de otro stream. fos. que son las clases padres de las clases de stream de bajo nivel. cl ose(). Estas clases extienden las clases FilterInputStream y FilterOutputStream y para la entrada y salida. dos. DataInputStream di s = new DataInputStream( fi s ). fis. / / cierre todos l os streams Fi le arch = new Fi l e(“C:\ \ texto. writeDouble( 100. dos. cl ose(). SERIALIZACIÓN DE OBJETOS . txt”). Fi leWriter fw = new FileWr i ter ( arch ). fw. out. etc. printl n(lnr . También tenemos las clases: PrintStream para escribir tipos primitivos como representaciones de carácter y la clase PushbackInputStream. fr . Un buen ejemplo de Readers y Writers de bajo nivel son las clases FileReader y FileWriter . cl ose(). Fi l e arch = new Fi l e(“C:\ \ texto2. Las clases de alto nivel soportes los métodos de bajo nivel. } lnr .Hay otras clases de alto nivel como BufferedInputStream y BufferedOutputStream. FileReader fr = new Fi leReader ( arch ). String s. READER Y WRITER El reader y el writer se basan en los datos de lectura y escritura en formato Unicode. readLi ne()) != nul l ) { System. getLineNumber () + “:” + s). cl ose(). y métodos para manipular la lectura en buffer . Los reader y writer pueden ser de bajo nivel y de alto nivel. Todas estas clases se extienden de las clases Reader y Writer. LineNumber Reader lnr = new LineNumber Reader ( fr ). cl ose(). que son las clases que utilizan el buffer de memoria. El archivo debe contener sólo datos en formato UTF. while( (s = lnr . wr i te(“Li nea 1\ nLi nea 2\ nLi nea 3\ nLi nea 4”). fw. la lectura de línea . ObjectOutputStream oos = new ObjectOutputStream( fos ). fos. Los objetos que van a ser serializados deben implementar la interfaz java. Fi l e ar ch = new Fi l e(“C:\ \ Persona. cl ose(). ser ”). utilizando los streams también pueden viajar en la red. fis. cl ose(). es decir . ObjectInputStream ois = new ObjectInputStream( fi s ).io. Persona per s = new Persona(). Persona p = (Persona) ois. setEdad(35). así como los objetos relacionados con este. oos.readObject(). ser ”).Serializable. oos. Los atributos marcados con el modificador transient no será Serializado. setNombr e(“Miguel ”). cl ose(). se registra el objeto con los datos de su estado actual. writeObject( per s ). Fi le ar ch = new Fi l e(“C:\ \ Persona. per s. ois. Estos objetos. FileInputStream fi s = new FileInputStream( ar ch ). per s. ORDENACIÓN DE UN ARCHIVO. cl ose(). MÉTODOS DE ORDENACIÓN EXTERNA .La serialización es el proceso de desentrañar el objeto y persistirlo en cualquier lugar . Fi leOutputStream fos = new Fi leOutputStream( arch ). Los distintos algoritmos de ordenación externa utilizan el esquema general de separación en tramos y fusión o mezcla.pueden ser comparables si disponen de una clave. Los objetos. Por separación se entiende la distribución de secuencias de registros ordenados en varios archivos. F1 y F2. Un archivo está formado por una secuencia de n elementos. . que posiblemente no pueden almacenarse en memoria. 2. La ordenación externa está ligada con los archivos y los dispositivos en que se encuentra. Variaciones de este esquema general dan lugar a diferentes algoritmos de ordenación externa. al leer el archivo para realizar la ordenación el tiempo de lectura de los registros es notablemente mayor que el tiempo que se tarda en realizar las operaciones de ordenación. El archivo está ordenado respecto a la clave si: ∀i < j ⇒K(i) < K(j) La ordenación de los objetos (registros) de una archivo mediante archivos auxiliares se denomina ordenación externa. utilizan arrays para guardar los elementos a ordenar. la mezcla de dos o más secuencias ordenadas en una única secuencia ordenada. cada elemento es un objeto (registro). El proceso consiste en: 1. Separar los registros individuales del archivo original Oen dos archivos. utiliza el esquema iterativo de separar secuencias de registros y su mezcla. se aplican los algoritmos de ordenación externa. R(i).Los algoritmos de ordenación interna. K(i).mediante la cual se pueden hacer comparaciones. es necesario que la memoria interna tenga capacidad suficiente. Mezclar los archivos F1y F2combinando registros aislados (según sus claves) y formando pares ordenados que son escritos en el archivo O. MEZCLA DIRECTA Es el método más simple de ordenación externa. en memoria principal. Para ordenar secuencias grandes de elementos. por fusión. Se opera con el archivo original y dos archivos auxiliares. Separar pares de registros del archivo original O en los dos archivos auxiliares F1 y F2. Se repiten los pasos de separación y mezcla. 2. de manera natural . las secuencias de registros tienen longitudes que son múltiplos de dos: 1. secuencias más largas ya ordenadas que también puedan mezclarse y dar lugar a otra secuencia ordenada. dependiente del número de registros. FUSIÓN NATURAL El método de fusión natural mejora el tiempo de ejecución de la mezcla directa al introducir una pequeña variación respecto a la longitud de las secuencias de registros. y en ese momento el archivo original O está ordenado. así hasta que la longitud de la subsecuencia sea la que tiene el archivo.de tal forma que el número de pasadas a realizar es fijo. En el método de mezcla directa. 4. 5. 4. Mezclar F1y F2combinando pares de registros y formando cuádruplos ordenados que son escritos en el archivo O. 16. 8. En cada paso de separación y mezcla se duplica el tamaño de las subsecuencias mezcladas..3. La mezcla directa no tiene en cuenta la circunstancia de que pueda haber. ÁRBOLES BINARIOS . combinando cuádruplos para formar óctuplos ordenados.. .Dn} Subárbol derecho de R. Un árbol binario es una estructura recursiva. El número de nodos por nivel contribuye a la densidad del árbol .Un árbol binario es un árbol cuyos nodos no pueden tener más de dos subárboles. . Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho. uno o dos hijos (subárboles). Cada nodo es la raíz de su propio subárbol y tiene hijos. {D1. En cualquier nivel n . que son raíces de árboles.. Un árbol binario no puede tener más de dos subárboles. un árbol binario puede contener de 1a 2n nodos. llamados subárboles derecho e izquierdo del nodo. cada nodo puede tener cero. {I1. . I2. Un árbol binario se divide en tres subconjuntos disjuntos: {R} Nodo raíz. D2. En un árbol binario.In} Subárbol izquierdo de R... respectivamente. El primero es un árbol degenerado a la izquierda. REPRESENTACIÓN DE UN NODO . dcho). izdo)y otro al subárbol derecho (derecho. el segundo es un árbol binario completo de profundidad 4. El valor null indica un árbol o un subárbol vacío.16 muestra la representación enlazada de dos árboles binarios de raíz A. Cada nodo debe contener el campo dato (datos a almacenar) y dos campos de enlace (apuntador).uno al subárbol izquierdo (izquierdo. La Figura 13.ESTRUCTURA DE UN ÁRBOL BINARIO Un árbol binario se construye con nodos. } } . izdo = ramaIzdo. Nodo ramaDcho) { this(dato). } public Nodo subarbolDcho(){ return dcho. dispone de dos constructores. en definitiva. izdo(rama izquierda) y dcho (rama derecha). izdo = dcho = null. } // operaciones de acceso public Object valorNodo(){ return valor. protected Nodo izdo. dcho = ramaDcho. } public void ramaIzdo(Nodo n){ izdo = n. Object valor. protected Nodo dcho. } public Nodo subarbolIzdo(){ return izdo.La clase Nodo agrupa a todos los campos de que consta: dato. se inicializa como hoja y el segundo inicializa dato a un valor y las ramas a dos subárboles. Además. package arbolBinario. } public void nuevoValor(Object d){ dato = d. } public Nodo(Nodo ramaIzdo. el primero inicializa el campo dato a un valor y los enlaces a null. public class Nodo { protected Object dato. } public void ramaDcho(Nodo n){ dcho = n. public Nodo(Object valor) { dato = valor. por ello se mantiene la referencia a la raíz del árbol. } public Nodo raizArbol() { return raiz.. public ArbolBinario() { raiz = null. Las ramas izquierda y derecha son.. a su vez.CREACIÓN DE UN ÁRBOL BINARIO A partir del nodo raíz de un árbol se puede acceder a los demás nodos del árbol. } // . public class ArbolBinario { protected Nodo raiz.raiz = raiz. } // Comprueba el estatus del árbol boolean esVacio() { return raiz == null. y así recursivamente hasta llegar a las hojas del árbol. un constructor que inicializa raíz y métodos para implementar las operaciones. . árboles binarios que tienen su raíz. } public ArbolBinario(Nodo raiz) { this. package arbolBinario. La clase Arbol Binario tiene el campo raiz. nuevoArbol(a1. ArbolBinario arbol. ramaDrcha)."Rodrigo".null). a.null). Nodo ramaDrcha) { return new Nodo(ramaIzqda."Abel".nuevoArbol(null.quitar().insertar(a). dato.null). .nuevoArbol(a1. a = ArbolBinario.null)."Maria".nuevoArbol(null. se utiliza un esquema secuencial y con una Pila (véase el Capítulo 9) que guarda. } Así."M Jesus".18."Anyora"."Esperanza". Nodo a1. a = ArbolBinario."Esperanza".nuevoArbol(null. public static Nodo nuevoArbol( Nodo ramaIzqda.quitar().nuevoArbol(a1. a1 = ArbolBinario. rama izquierda y derecha pasadas en los argumentos.a2). para crear el árbol binario de la Figura 13.El método nuevoArbol()crea un árbol de raíz un nodo con el campo dato. PilaVector pila = new PilaVector().insertar(a). a2 = ArbolBinario. arbol = new ArbolBinario(a). a1 = ArbolBinario. a1 = (Nodo) pila. Object dato. en cada paso. pila. los subárboles: import TipoPila.a2). a2.a2).nuevoArbol(null. pila. a = ArbolBinario.PilaVector. a2 = (Nodo) pila. a2 = ArbolBinario.