NC a Bona ee ESSTABLA DE MATERIAS PRESENTACION INFRODUCCION DE LOS TRADUCTORES PROLOG |. ESTRUCTURAS FUNDAMENTALES DE DATOS. Itroduccion Conceptos tipo de datos TiposCementaes de datos Tipos elementales ormalizados ‘Tpos subearpo Uterus say estructura resto Wariantes de ta estructura registro Ta estructura conjunto (oct) [Representacion de las estructures array, reiseoy conjunto 110. Represemaciin de fas erays 10:2. Representacton dels extructras registro 1103, Representactin dels confunos struct fichero secaenciat 1 Operadares clementales de fcheres 3: Ribtron con swetnutura 5. Textos L114 Un programa para edicin de ficheros Ejerion Referencias Bi 2 ORDENACION 21, Tatroduesion 22) Ordenacioa de arrays ‘Ordenacion por inserciin directa Ordenacion por seleceiin directa Ordenacion por inercambio directo ‘Ondenacion por insercin com ierementasdecrecentes rdenacion Sein wr airbol Ordenacion por partcion btenchin dela mediana 228. Comparacidn de fs metodos de ordenacin de arrays 23, Ordenaciom de icherosseovencales 2. Método de mezela directa, 232) Mescla natural 233. Mezea equilbrada mitiple 334. Ondenasian poston 233. Disraeid de fos tramos iniciles Bjercicios Referenciasvu TABLA DE MATERIAS 4. ALGORITMOS RECURSIVOS a1 Introduccion Yh Cine no utiliza ls recursion \ Wor'jomplos de programas recursivos Algoritmo de wrtta tri 15. Tfprobloma de as ocho reins {1 problema de los atrimonios stables 11 11 problema de a seleceton Optima Tereieios 4. USTRIUCTURAS DINAMICAS DE INFORMACION 1. ‘tipos recursos de datos 1 Punioroso referencias 4A Ustas ncales, 5.1. Operacones basics 412) Utes ordenadae'y lista reorgantzables G5, Cra aplcacién: dndenaciontopoliica ag 44, TSiructurasdPbot A Defiicones» concepos Bésicos 1°02. Operactone basens con drbotes Binaries JA lsgueda e inserclon en arboles S49. ora on arbotes S43. Anois dela buoqueda e msercion en airtotes 148. Arboles equitbrados 442 invercin en aboles equilbrades SUS. Bora en irbote eguibrados 449. Arboles de bisqucda optimos 4410, “Presentacin deextructurasdnbol 45, ‘Aiboes multeamting 131 aboles 8 432. Arboles B binarias +46, Transtormaciones de claves (shashing») 46.) Blecclon dela fncin de iransformacion 452 Manejo decoliiones 43. Anil de Método de transformactén de claves Bacieios erencias S._ESTRUCTURAS ¥ COMPILADORES DE LENGUAJES 5.1. efinicon y estructura de los Iengusies Smits de eases 3.) Construceion de un grafo sintético 34. Consteuceton de un Snalizador para una sintaie dada 55. Construcctoa de un programa analizador drgido por tabla Su Unteaductor de BNF en estructuras de datos para digit tnabzadores 57. ELlenguaje de programacion PLO SK Unlanatizdar sintitieo para PLO 39. Tratamiento de errressintaeticos vil Un procesador PLO VI Generacon de obdigo ersiciow Referencias APENDICES, A EL CONJUNTO DE CARACTERES ASCH DIAGHAMAS SINFACTICOS DE PASCAL INDICE DE MA INDICE DE Pred RIAs HAMAS PRESENTACION Debido a la complejidad de los temas » al proceso de cambio constante en el campo de ta informética, las publicaciones en este sirea oscilan habitualmente entre Jos simples manuales de programaciin v la monografia excesivamente especializada, tn siendo, en cambio, jicil encontrar textos adecuados para la enseftanza de pro- sramaciin que aionen modernidad, generalidad profundidad en el tratamiento, cn fuarcionalidad didictica Un texto que cumple las condiciones anteriores, como lo demuestran tas siete ‘ediciones en menos de tres ais que se han Hlevado a efecto de su versién inglesa, «el presente libro del profesor Wirth, que incorpora los desarroltostiltimos, tanto 1 to referente a la gama de algoritmos que describe, como a su metodologia de construcin. Ta Facultad de Informética, que sigue una linea de apoyo a la creaciém de una ‘ruse auténticamente cientifiea de la informitica en nuestro pais, es consciente de a inportancia que tiene este libro tanto para la consulta de los profesionales como nara texto de ensefianza de programacién en los centros universtarias y, por ello, ww hat dudado en impulsar la iniciativa de los profesores Angel Alvarez Rodriguez v José Cuena Bartolomé de esta Facultad de realizar su version castellana, conside- ‘urudo la indudable calidad de esta publicacién, RAVAEL PORTAENCASA DECANO DE LA EACULTAD DE INFORMATICA DE MADRID1 ESTRUCTURAS FUNDAMENTALES DE DATOS 1.1. INTRODUCCION Los modernos computedores digitales fueron inventados con Ia idea de facilitar y acelerar célculos complicados y onerosos de tiempo. En la mayoria de las aplicaciones, su capacidad de almacenamiento y acceso a grandes masas de informacién juega un papel dominante y, por ello, se considera esta su carac- teristica primordial, es decir, su capacidad para realizar calculos aritméticos ha Megado a tener escaso relieve en muchos casos. En todos estos casos, Ia gran masa de informacién que es necesario procesar representa, en cierta forma, una abstraccién de una parte del mundo real. La informacién utilizable por el computador consiste en una seleccién de daros dela realidad, precisamente el conjunto de datos que se considera relevante para el problema en estudio, y a partir del cual se cree que pueden obtenerse los resulta- dos deseados. Los datos representan una abstraccién de la realidad en el sentido tic que ciertas propiedades y caracteristicas de los objetos reales se ignoran por- «que no interesan para el problema concreto que se estudia. Por ello, una abstrac- cin es, también, una simplificacién de la realidad. Puede tomarse como ejemplo el fichero de personal de una empresa. Cada cmpleado se representa (en forma abstracta) en este fichero por un conjunto de slatos de interés bien para la empresa o para sus procesos contables. Esta infor- tmacién puede incluir datos de identificacién del empleado, por ejemplo, su nom- Ihre y sueldo, Pero, seguramente, no contendra datos sin interés tales como el color del pelo, peso y estatura. Al resolver un problema, s¢ utilice o no el computador, es necesario elegir una mn de la realidad, es decir, definir un conjunto de datos para representar li situacién real, Esta eleccién debe estar guiada por el problema a resolver. A con- tinuacién, debe seleccionarse la forma de representar esta informacion, Esta» ESTRUCTURAS FUNDAMENTALES DE DATOS segunda eleccién debe hacerse en base al instrumento con que va a resolverse el problema, por ejemplo en base a las posibilidades concretas que oftece el com- initador. En muchos casos, estas dos etapas de dis endienies una de otra La eleccién de ta representaciOn de los datos es a menudo bastante dificil y hno esté determinada exclusivamente por los instrumentos disponibles. Deben tenerse siempre en cuenta las operaciones a realizar con los datos. Un buen ejem- bio ilustrativo de esto es la representacién de los ntimeros que son, a su Vez, abs- twacciones de propiedades de objetos a caracterizar. Sila adicién es la tnica (0 al ‘ncnos predominante) operacién a realizar, una buena forma de representar el wvinero n es escribir n barras. La regla de adieién, con esta representacidn, es real- swente obvia y muy sencilla, La numeracién romana se basa en el mismo principio sencillo y Tas reglas para sumar son igualmente simples para nimeros pequeiios, tin cambio, Ia numeracién arabe requiere reglas que estén lejos de ser obvias (para niimeros pequetios) y por tanto deben ser aprendidas de memoria, Sin «mbargo, la situacin se invierte cuando se considera la suma de grandes niimeros «la multiplicacion y division. La descomposiciéa de estas operaciones en otras ‘nas simples es mucho mas fécil en el caso de la numeracién arabe, debido a su principio sistemitico basado en el distinto peso posicional de los digitos. Es bien sabido que fos computadores usan una representacién interta basada cn digitos binarios (bits). Esta representacién no es viable para las personas de- bdo al niimero, frecuentemente clevado, de digitos que son necesatios pero, «n cambio, es muy adecuada para lo circuitos electrénicos porque los dos valores ‘Vy | pueden representarse en forma conveniente y fiable por la presencia o ausen- wit de corrientes eléctrieas, carga eléctrica y campos magnéticos, A partir de este ejemplo, puede verse también que el problema de representa- «in, a menudo, abarca varios niveles de detalle. Dado el problema de representar, ior ejemplo, la posicién de un objeto, ln primera decisién puede conducir a la vleccin de una pareja de niimeros reales que sean, por ejemplo, sus coordenadas varlesianas o polates. La segunda decision puede llevar a una representacién wn coma flotante, donde cada nimero real se describe por un par de niémeros sateros que representan una fraction fy un exponente ¢ al que se eleva dcter- sinasdt base (por ejemplo, x ~ f- 2"). La tercera decisién, basada en el conoci= snicito de que los datos se almacenarin en un computador, puede conducit a una ‘presentacién binaria posicional de los niimeros enteros y la decisi6n final podria ot representar los digitos binarios por la direecién del flujo en un dispositive snapmetico de almacenamiento. Evidentemente, Ia primera decisién en esta ca- «lena est prineipalmente influida por el planteamiento del problema y las si wirales son cada vez més dependienies de la herramienta a utilizar y su teeno- tipua. Asi pues, dificiimente podra pedirse a un programador que decida sobre ls forma de representar los nimeros que deben emplearse o, incluso, sobre las “snteristicas del dispositive magnético de almacenamiento, Estas «decisiones «lc hajo nivel» pueden encomendarse a Tos disefiadores de equipos que tienen a st “Inpwsicidn ti ms completa informacién sobre la tecnologi © no son totalmente inde- ‘actual, con fa que INTRODUCCION 3 pueden adoptar una decisiOn sensata que, en general, seré aceptable para todas (0 casi todas) las aplicaciones en que intervengan numeros. En este contexto adquiere significado el concepto de lenguajes de programa- cién, Un lenguaje de programacién representa un computador abstracto capaz de entender los términos'utilizados en este lenguaje, que pueden ser mas abstrac- tos que los de los objetos utilizados por la maquina real. De esta manera, el programador que utiliza este tipo de lenguaje de «alto nivel» estara liberado (e impedido) de tener que considerar cuestiones relativas a la representacion de los nimeros, caso-de-que el niimero sea un objeto clemental de este fenguaje. La importancia de utilizar un lenguaje que ofrezca un conjunto conveniente de abstracciones biisicas, comunes a la mayoria de los problemas de proceso de datos, reside principalmente en Ia fiabilidad de los programas resultantes. Es mds ficil diseilar un programa razonando sobre los conceptos familiares de nnlimeros, conjuntos, sucesiones y repeticiones que razonando con bits, «pala- bras», y saltos de secuencia. Desde luego, un computador real representara todos los datos, ya sean miimeros, conjuntos 0 sucesiones como grandes masas de bits. Pero esto carece de importancia para el programador, mientras no tenga que pre- ‘ocuparse de los detalles de representacién de las abstracciones que ha elegido pueda estar seguro de que la representacién elegida por el computador (o el com- pilador) es adecuada para sus fines. Cuanto més préximas son las abstracciones a un computador dado, mas Ficil Ie resutta al ingeniero o técnico de implantacién del lenguaje la eleccibn de fa forma de representacién, y mas alta es la probabilidad de que una eleccién iiica sea adecuada para todas (0 casi todas) las aplicaciones posibles. Este hecho de- termina limites definidos al grado de abstraccién a realizar a partir de un com- putador real dado, Por ejemplo, no tendria sentido incluir objetos geométricos, ‘como clementos bisicos de datos, en un lenguaje de uso general, ya que su ade ‘cuada representacion dependerd, en forma importante, debido. su inherente com- tilejidad, de las operaciones. realizar con tales objetos, La naturaleza y frecuencia ile estas operaciones, sin embargo, sern desconocidas para el disefiador de un lenguaje de uso general y de su compilador y, por tanto, cualquier eleccién que uulopte puede no ser apropiada para alguna de las posibles aplicaciones. Las consideraciones anteriores han determinado en este libro la eleccién de la notacion a utilizar en la descripcién de los algoritmos y sus datos. Por un lado, .© quiere utilizar nociones familiares en matemiticas, (ales como niimeros, con- iuntos, sucesiones y similares, miis que entidades dependientes del computador tales como secuencias de bits. Igualmente interesa utilizar una notacién para la nyse se conozea la existencia de compiladores eficientes. Tan inadecvado es utili- sar lenguajes fuertemente orientados a la maquina y, por tanto, fuertemente de- pendientes de ella, como describir los programas en una notacién abstracta sine deje penilientes de resolver los problemas de representacién. EL lenguaje de programacion PASCAL ha sido disetado con la intencién de rieontrar un compromise entre ambos extremos y se utiliza a lo largo de todo este libro [Ly LS]. Hste lenusje se ha implintado satisfactoriamente en varios4 ESTRUCTURAS FUNDAMENTALES DF DATOS computadores y se ha comprobado que su notacidn es lo suficientemente pré- xima a las miquinas existentes como para que las caracteristicas elegidas y su tepresentacién, puedan explicarse en forma clara, El lenguaje es también sufi- cientemente proximo a otros lenguajes, en particular a ALGOL 60 como para ‘que las Tecciones explicadas aqui puedan aplicarse, igualmente bien, para uso de estos lenguajes. . 1.2. CONCEPTO DE TIPO DE DATOS En mateméticas se acostumbra clasificar las variables de acuerdo con ciertas caracteristicas importantes. Se hacen distinciones claras entre variables ldgicas, reales y complejas, 0 entre variables que representan valores individuales, con- juntos de valores, conjuntos de conjuntos, o entre funciones, funcionales, con: juntos de funciones, y asi sucesivamente, Esta nocién de clasificacién es impor- tante en igual medida, si no mas, en proceso de datos. Se adoptard de aqui en adelante el principio basico de que cada constant, variable, expresién o funcién es de wn tipo determinado, Este tipo caracteriza csencialmente el conjuto de valores al que pertenece una constante o sobre el que puede tomar valores una variable 0 expresion, o cuyos elementos pueden ser generados por una funcién, En los textos matemiticos el tipo de una variable se deduce, generalmente de fa forma de escritura, sin tener en cuenta el contexto; esto no es factible en los Programas, ya que, normalmente, s6lo hay un tipo de escritura utilizable en los ‘cquipos de proceso de datos (alfabeto latino). Debido a esto, la norma comén- mente aceptada es que el tipo asociado se manifieste explicitamente en una deela- racién de la constante, variable o funcién y esta declaracién preceda en el texto ‘ala utilizacién de cada constante, variable 6 funcién. Esta norma es especialmente ‘oportuna sise tiene en cuenta que un compilador tiene que elegir la representacién del objeto en la memoria del computador. Evidentemente, la capacidad de me- ‘moria asignada a una variable debe decidirse de acuerdo con el tamafio del campo dle valores que la variable puede adoptar. Si esta informacién es conocida por el compilador, puede evitarse la Hamada asignacién dinamica de memoria, Esta «8 muy frecuentemente la clave de una ejecucién eficiente de un algoritmo. Loa tant, les caactersticas principales del conepto de tio que ee utiliza «to largo de este texto, y que estén incorporadas en el lenguaje de programacién PASCAL, son ls siguientes [12]. iste ce oe |. Un tipo de datos determina el conjunto de valores al que pertenece una constante, 0 que puede tomar una variable o expresién, o que pueden ser nenerados por un operador funcién. 2. 111 tipo del vator identificado por una constante, variable, o expresién puede deduciese de su forma o de su declaracién sin necesidad de sjecutar cl proceso. CONGEPTO DE TIPO DE DATOS 5 3. Cada operador o funcién presupone argumentos de un determinado tipo y produce un resultado también de un tipo determinado. Si un operador ‘admite argumentos de varios tipos (por ejemplo, se utiliza + igualmente para tniimeros enteros y reales), el tipo del resultado puede determinarse a partir de reglas especificas’ de! lenguaje. Por tanto, un compilador puede utilizar esta informacién sobre tipos para comprobar la compatibilidad y observancia de normas de las distintas cons- trucciones de un programa, Por ejemplo, puede detectarse, sin ejecutar el progra- ima, la asignacién de un valor de tipo boolean (Jégico) a una variable de tipo aaritmético (real), Este tipo de redundancias en el texto de un programa es muy Util en el desarrollo de los mismos y debe considerarse la principal ventaja de los hhuenos lenguajes de alto nivel sobre los lenguajes en cédigo de maquina (0 en- sambladores). Evidentemente, los datos acaban representandose pot un gran imimero de digitos binarios, independientemente de que el programa haya sido concebido inicialmente en un lenguaje de alto nivel, utilizando el concepto de tipo, «en un lenguaje ensamblador que no lo tenga en cuenta. Para el computador, la memoria es una masa homogénea de bits sin estructura aparente, Pero ¢s, precisamente, esta estructura abstracta, la tnica que permite a los programadores reconocer significado en el mondtono paisaje de la memoria de un computador, La teoria presentada en este libro y el lenguaje de programacién PASCAL cspecifican ciertos métodos de definicién de tipos de datos. En la mayoria de los casos se definen nuevos tipos de datos en funcién de otros definidos previa- mente. Los valores de tal tipo son usualmente agrupaciones de valores compo- nentes de los tipos constituyentes definidos previamente y se dice que estin estruc- turados. Si solamente hay un tipo constituyente, esto es, si todos los componentes son del mismo tipo, entonces éste se denomina tipo base. El mimero de valores distintos que pertenecen a un tipo 7 se llama cardina- lidad (0 cardinal) de T. La cardinalidad proporciona una medida de la cantidad de memoria que se necesita para representar una variable x de tipo 7 y esto iiltimo se expresa de la forma x: T. ‘Como los tipos constituyentes, a su vez, pueden también estar estructurados, pueden construirse verdaderas jerarquias de estructuras pero, obviamente, los ‘componentes iiltimos de una estructura deben ser atémicos. Por esto, también ces necesaria una notacién para introducir tales tipos elementales, no estructura- dos. Un método directo es el de emumeracién de los valores que van a constituir cl tipo. Por ejemplo, en un programa que trate figuras geométricas planas puede introducirse un tipo elemental llamado forma cuyos valores pueden designarse con los identificadores: rectdngulo, cuadrado, elipse, circulo. Pero ademas de tsstos tipos definidos por el programador debe haber algunos tipas normalizados (o estindar) que se Taman tipos predefinidos: incluirén frecuentemente los vulares numéricas y Higicas. Si existe un orden entte los valores individuales el Lipo se dive que est ordenado o que es un escalar, En PASCAL se supone que foxlos los tipos no esiructurados estin ordenados: en el caso de enumeracién6 ISIRUCTURAS FUNDAMENTALES DE DATOS “xplivita, los valores se suponen ordenados segiin la secuencia de enumeracién. Con este instrumento es posible definirtjpos elementales y consttuir agru- twcinnes, tipos estructurados, hasta el grado de complejidad que se desee, En li pyfictics-no es suficiemte tener s6lo un método general de combinar los tipos onstituyentes en una estructura. Teniendo en cuenta os problemas practicos «le tepresentacién y utilizacién, un lenguaje de programacién, de uso general, sIche ofrecer varios métodos de estructuracién de datos. Matemiticamente pueden «1 tos equivalentes; se diferenciarén en los operadores utilizados para cons- tinue sus valores y para seleceionar componentes de estos valores. Los métodos Inisivos de estructuracién presentados agul son el array'*, el registro, el conjunto ¥ el fickero secuencial. No se definen habitualmente estructuras mas compli« caus como tipos «estiticos»; éstas son, més bien, generadas «dindmicamenten sIurante la ejecueién del programa en la cual pueden variar de tamaio y de forma Hales estructuras son el tema del capitulo 4 e ineluyen listas, anillos,arboles y yrtos Finitos genéricos. {Las variables y ls tipos de datos se introducen en un programa para ser uti ‘aulos eH proceso, A este fin debe disponerse de un conjunto de operadores. Tal ‘amo sueéde con los tipos de datos, los lenguajes de programacion ofrecen un cierto nGimero de operadores clementales normalizados (at6micos) y un mimero «le metodos de estructuracién, de forma que pueden definirse operaciones com blejas en funcién de los operadores elementales. La composicién de operaciones w considera, a menudo, la tarea fundamental del arte de programar. Sin embar- 10, lo sucesivo, se pondré en evidencia que una apropiada composicién de los datos es igualmente fundamental y esencial. {ns operadores bisicos mas importantes son la comparacién y la asignacién, «ss decir, fa comprobacién de igualdad (y de orden en el caso de tipos ordenados) ¥ lu instruceién que obliga a la igualdad. La diferencia fundamental entre estas «los operaciones se pone de relieve mediante la distincién clara en su notacion a lo Lingo de este texto, aunque, desgraciadamente, esta distincién aparece osci~ ‘evida en lenguajes tan amptiamente usados como el FORTRAN y PL/I que uti- isan ef signo de igualdad como operador de asignacidn. Comprobacién (test) de igualdad: x = y Asignacién a x ximy Fstos operadores fundamentales se definen para la mayotia de los tipos de status, pero hay que advertir que su ejecucién puede involucrar una cantidad tmporiante de esfuerze de proceso si 10s datos son extensos y altamente estruc- tos, Adtemivs del test de igualdad (u orden) y el operador de asignacién, existe * nada tcc de eta palabra yt diticua de encontrar un teeing eastellan adc ua 4 ati esl Fa is pa ingles qe, pow al ex icenteene fy 1h goes de inst Ne doy P TIPOS ELEMENTALES DE DATOS 7 tuna clase de operadores fundamentales, definidos implicitamente, lamados ‘operadores de transferencia, Estos aplican unos tipos de datos en otros. Son particularmente importantes en relacién con los tipos estructurados. Los valores estructurados se generan a pagtir de sus valores correspondientes por los Ilamados constructores y los valores componentes son extraidos de los valores estructurados ‘mediante los llamados selectores. Constructores y selectores son, asi, operadores de transferencia que aplican los tipos constituyentes en los extructurados y rec procamente. Cada método de estructuracién tiene su pareja particular de cons- tructores y [Link] se diferencian claramente por su notacién. Los tipos de datos clementales estandarizados también requieren un con- junto de operadores primitivos normalizados. Asi, junto con los tipos de datos normalizados de ntimeros y valores ldgicos también se introducen las operaciones convencionales de aritmética y légica proposicional. 1.3. TIPOS ELEMENTALES DE DATOS En muchos programas los niimeros enteos se utlizan cuando no estin invo~ lucradas propiedades numéricas y cuando cada entero representa una eleccién centre un pequefio nimero de alternativas. Para estos casos, e introduce un nuevo {ipo elemental, no estructurado, definido por enumeracién del conjunto de todos los posibles valores ¢,, Ca, «--+ Ex type T= (even 2) | ap La cardinalidad de T es card(T) ~ n. Tse MPLos type forma = (rectangulo, cuadrado, elipse, circulo) type color = (rojo, amarillo, verde) type sexo ~ (masculino, femenino) type boolean ~ (false, true) - type diasemana = (lunes, martes, miercoles, jueves, viernes, sabado, domingo) type moneda = (peseta, franco, marco, libra, dolar, lira, rublo, eruzeiro, yen) type destino ~ (infierno, purgatorio, cielo) type vehiculo = (ren, autobus, automovit, barco, avion) type graduacion = (soldado, cabo, sargento, teniente, capitan, comandante, coronel, general) type objeto ~ (constante, tipo, variable, procedimiento, funcion) type estructura ~ (fichero, array, registro, conjunto) type concn (manual, descargads, prided, dsalineada) La definicidn de tales tipos introduce no s6lo un nuevo identificador de tipo1 ESTRUCTURAS FUNDAMENTALES DE DATOS sino también el conjunto de identificadores que designan los valores de este nuevo ‘ipo, Estos identificadores pueden ser usados como constantes a Io largo del programa con Io que aumenta de una manera considerable su inteligibilidad, por cjemplo, se introducen las variables s, d, g y b. var s: sexo var d: diasemana var g: graduacion var b: boolean cs posible escribir las siguientes asignaciones = masculine - domingo = comandante := true wae videntemente estas instrucciones son mucho mas informativas que sus corres pondientes en cédigo numérico: si=l d:=7 g 6 2 resultantes de suponer que las variables s, d, gy b estuvieran definidas como de lipo integer y que, a las constantes de los tipos anteriores, se hubiera hecho co- responder el ntimero natural indicativo de su situacién en el orden de enuimera: cin, Ademas, un compilador puede controlar el uso indebido de operadores arit- Inigo con tales variables, definidas como no numérias, asi como sucede en instruecién Sin embargo, si se considera un tipo como ordenado, es razonable introducir Iunciones que generen el predecesor y el sucesor de su argumento. Estas se deno- ‘minan pred(x) y succ(x). El orden de los valores de T se define por la regla 10, p= false y q= true. El tipo normalizado char comprende el conjunto de caracteres imprimibles. Vesgraciadamente, no existe ningin conjunto normatizado de caracteres gene- ralmente aceptado para todos los equipos de proceso de datos. Por ello el adjetivo «normalizadon puede ser equivoco en este caso; debe entenderse camo norma- lizado en el equipo de proceso de datos en el que se va a ejecutar determinado programa. E1 conjunto de caracteres definido por la International Standards Organi- vation (J.S.0.) y, en particular, su version americana ASCII (American Standard Code for Information Interchange), es probablemente el cédigo mas amplia- mente admitido. Por ello este cédigo se presenta en el Apéndice A, Consta de 95 caracteres de impresién (grificos) y 33 caracteres de control; estos tltimos se ntilizan principalmente en transmisién de datos y control del equipo de im- presion, Un subconjunto de 64 caracteres grificos (solo las letras maytisculas) se utiliza de forma generalizada y se denomina el cddigo restringido ASCI. Para disefar algoritmos que trabajen con caracteres (es decir, valores de tipo char) que sean independientes del equipo de proceso de datos especifico, es con- veniente hacer la hipétesis de que todos los conjuntos de caracteres tienen ciestas propiedades obligatorias 1. 1 tipo char contiene las 26 letras del alfabeto latino, los diez digitos de la numeracién arabe y cierto némero de otros caracteres graficos, como, por iemplo, tos signos de puntuacién Fox subconjuntos de letras y niimeros estin ordenadas y son coherentes, wos decies CA 0} i: =0y 4? (15) i+ 1 until (@{i] = 2) V (= N): if ali] # xthen eno estd este elemento en a» Puede realizarse wha’ variante de este programa utilizando la técnica del vvntinela apostado al final del array. El objetivo de este centinela es permitir ‘una simplificacién de Ia condicién que seftala el final de la iteracién. vara: array(1...V + 1of 7; [Nb AJ: = xy (1.16) repeat i: = 1 + Lunt {i} = x; if] > N then «no estd este elemento en a» 1a asignacion a[W + 1]: —.x es un ejemplo de actualizacién selectiva, es de- ‘su. de alteracién de un componente particular de una variable estructurada, {hn condicién esencial que se verifca, cualquiera que sea el nimero de veces que w repita la instruccion i: =i + 1, es Ulex, para j= 4y...5i-1 y esto en ambas versiones (1.15) y (1.16). Esta condicién se denomina por ello ww invariante del cielo. Ia bisqueda puede, desde luego, acelerarse considerablemente silos elementos satin ya ordenados, En este caso el método de trabajo mas usual es el de division tepetida en partes iguales del intervalo en que debe buscarse el elemento. Este {uct se conoce con el nombre de hiisqueda binaria 0 de biseccién y se muestra vw (1.17), Bn cada iteracién se divide en partes iguales el intervalo entre los in- wes Zy J. EI nimero necesario de comparaciones es, por ello, como mucho Hon (ND) d= ij jr Ny repeat k= (i +f) div2; an ix > alk] then i: = k + 1 else j: wntil (afk] = 3) VG> A) {hn este caso la condicién invariante a la entrada de la instruccién repetitiva es ath] =, + Los blancos y finales de linea se saltan. ‘cuenta con el procedimiento bisico read{x) que extrae el caracter siguiente sle la secuencia de entrada y lo asigna a la variable x. El simbolo de salida resul- tute se asigna a una variable global llamada sym. Ademés, estan las variables lobules id y num cuyo objetivo resulta evidente en el programa 1.2 y ch que re- presenta ef cardcter de la secuencia de entrada en fase de andlisis. S designa una splicacién del conjunto de caracteres sobre el de simbolos, es decir, un array ‘ie simbolos con un dominio de indices formado por caracteres que no son ni ‘lepitos ni letras. El uso de conjuntos de caracteres demuestra e6mo un analizador Iv sicgraficn puede programarse independientemente del orden que exista entre tis earacteres que Forman los textos. UL segundo ciemplo consiste en la construccién de un horaria escolar. Se upone que M estudiantes han elegido entre N asignaturas. Debe construirse2 SIRUCTURAS FUNDAMENTALES DE DATOS worario de forma que se programen determinadas asignaturas para ser expli- clay a1 lt misma hora sin que haya conflictos [1.1]. hn Programa 1.2. Analizador lxicogrtico («Scanner»), vm: simbolos ‘nun: integer: id: record k: 0, maxk: «array (1... maxk] of char end ; racedure analizador var eh: chars bein {saltar blancos} while ch" * do read( eh): Wehr [AY .°2°) then with il do Degin sym : = tdentficador; k : = 0 repeat if k < maxk then begin k: = k + 1 alk] end ; read{ch) wuatil—(ch in [(A* ch a) 9°] thea ‘numero; mum : = 0; repeat num : = 10°» num + ord{eh) — ord\‘0'); readch) wo il (chin [O° .°9" ul else ' » it chin [<,,°>7] then begin ch: = ch; read(eh); if ch = "= th begin cht ~*<" then sym : = menoroigual else if cht —*>" then sym : — mayoroigual else sym : = tomaetvalorde; read(ch) end clse sym: Sfehl] wl else begin {otros simbotos} wm: Sleh |; rewdoh) lanatizador| LA ESTRUCTURA CONJUNTO (SET) 29 type asignatura = 1. Ns estudiante = 1... M; seleccion = set of asignatura; var s: asignatura; i: estudiante; © ¥ ‘matricula: akray [estudiante) of seleccion; conflicto: array [asignatura] of seleccion; 28 {Determinacion de los conjuntos de asignaturas conflictivas ‘a partir de las-asignaturas en que se matricula cada estudiante} for s: = 1 to N do conflicio[s}: ~ []5 fori: = 1 toM do fors: = 1toNdo if's in matricula{i) then conflicto|s] :~ conflicto{s] + matricula{i] (Obsérvese que s in conflicto[s] es una consecuencia de este algoritmo.) En general, Ja construceién de un horario es un problema combinatorio muy ulifieil, donde debe tomarse una decisién teniendo en cuenta muchos factores y con abundantes restricciones. En este ejemplo se simplificard el problema de forma drastica sin plantearse Ia basqueda de una solucién de horario realista, En primer lugar se constata que para obtener clases simulténeas aceptables x preciso basar las decisiortes en el conjunto de datos obtenidos de las matriculas individuales de los alumnos, es decir, en Ia enumeracién de asignaturas que no puedan explicarse simultineamente, Por ello, se programa en primer Ilugar un moceso de reduccién de datos basado en las siguientes declaraciones y en el convenio de que los estudiantes se numeran de | a My las asignaturas de 1a N. La tarea principal ahora consiste en construir un horario, es decir, una lista sle sesiones, cada sesién formada por una seleccién de asignaturas que no estén en conflicto, Del conjunto de todas las asignaturas se eligen subconjuntos de vsignaturas aceptables, no conflictivas, suprimiéndolas de una variable con- junto denominada remanente, hasta que este conjunto de asignaturas remanentes yuede vacio. var k: integer: remanent, sesion: seleccion: horario: array 1 ...N] of seleecion; ke: =0; remanente: = (1..N}s a while remanente + { ]do 0.29) begin sesion : — siguiente seleccion aceptable; remanente | = remanente — sesion: ki kt Ishorario[k]: = sesionWw) ESTRUCTURAS FUNDAMENTALES DE DATOS REPRESENTACION DE LAS ESTRUCTURAS ARRAY, REGISTRO Y CONJUNTO 31 {.Cémo se realiza una «siguiente seleccién aceptable»? Al iniciar el proceso puede clegirse cualquier asignatura del conjunto de las remanentes, Subsiguien- alg A fentente,la eleceién de nuevos candidatos puede estar restringida al conjunto ah g ck ssignaturas remanentes que no entran en conflicto con las inicialmente selec- pals 5 cionadas. Este conjunto se lamara de prueba. Cuando se investiga un candidato wl 8 =i «let eonjunto de prueba, se constata que su eleccién depende de que la interseccién ‘ lel conjunto de asignaturas seleccionado y el conjunto de las que entran en con- = het con el candidato esté 0 no vacia. Esto conduce a la siguiente elaboracién dks ln siruceién «sesion: = siguiente selecion acptabley w- | od 5 | Be | Sq | var s, 1 asignatura; Fela He prucha:seleccon; ble |ia begins: = 1; a vhile(s in remanent) dos: = s+ 1; | sesion : = [3]; prueba : = remanente — conflictols]; . g ee for 1: — 1 to Ndo (1.30) Wee | 2 fea lea if in prucha then |e By, | aE. begin if conflicto[t] * sesion ~ [ ] then 33 | bg gba | 3 sesion : = sesion + [t] ge BEE sag) 2 7 age [bee | 8 Evidentemente esta solucién para seleccionar sesiones «aceptables» generar’ homurios no necesariamente 6ptimos en algin aspecto especifico. Puede darse cit algin caso no afortunado la circunstancia de que el niimero de sesiones resul- ‘antes sea tan amplio como el de asignaturas, incluso aunque fuera posible pro- Selector wed pramor eet clases simliéneament. i 2 2 | 1.10. REPRESENTACION DE LAS ESTRUCTURAS ARRAY, 7 REGISTRO Y CONJUNTO Sete 4 ee'g le # % ppucale concebirse, comprenderse y verificarse en base a las leyes que tigen aqueéllas | 4|* ‘y qu no es necesario preocuparse de la forma en que se implantan y representan | eo fe s cu sn determinado computador. De todas formas es una ayuda para el éxito «lel programador la comprensi6n de las técnieas de uso mis generalizado para t—— tepresentar los [Link] de las abstracciones de programacién, tales : e ‘ono tas estructaras Fondamentales de datos. Es una ayuda en cf sentido de els g 3 {une capacita al programador para tomar decisiones sensatas sobre ef diseiio z)@ |$ 3 sel programa y tos datos teniendo en cuenta no slo las propieddes ibstractas a * ° de lay estructura sino tambien fas de st realizacién conereta en los compututo:\y_ |SIMUCTURAS FUNDAMENTALES DE DATOS re, (eu Jo en cuenta las capacidades y limitaciones de un determinado compu- tudor 1 problema de la representacién de datos es el de definir una aplicucion de la cesiruetura abstracta sobre la memoria del computador. Las memorias de los com- piitudores son, en primera aproximacién, arrays de celdas de almacenamiento individu! denominadas palabras. Los indices de las palabras se laman direc- var memoria: array direccion] of palabra a3 Los cardinales de los tipos direccion y palabra varian de unos computadotes @ ‘otros. Lat gran variabilidad del cardinal de la palabra es un problema. Su loga- rine se Hama tama de la palabra, porque es el nimero de bits que contiene una welds de: memoria, 1.4041. Ropresontacién de los arrays Una representacion de una estructura array es una aplicacién del array (abstraeto), con eomponentes de tipo T, sobre la memoria, que a su vez es un array von componentes de tipo palabra. Hl asray debe aplicarse de tal forma que el céleulo de diecciones de sus com- ponentes sea lo mas simple (y, por tanto, eficiente) posible. La direccién o indice le memoria i del componente j del array se calcula por la funcién de aplicacién i=i, ties (1.32) cn donde j, ¢s la direccién del primer componente y s ¢s el nimero de palabras tune «excupa cada componente. Dado que la palabra es por definicién la unidad le memoria mas pequefia a la que puede accederse individualmente, es muy dloseable, evidentemente, que s sea un niimero entero, en el caso mas sencillo +L Sino es entero (que es el caso normal) se redondea, habitualmente, hasta cl emer mayor mis préximo [s]. En este caso, cada componente del array ticupsa fs] palabras y, por tanto, [s] — s palabras no se usan (ver Figs. 1.5 y 1.6). ute redondeo del nlimero de palabras necesarias hasta el entero més préximo, we llama ajusfe, El factor de «utilizacion de memoria», u, es el cociente de la can- Lida minima de memoria necesaria para representar una estructura y la cantidad eslmente utilizada vated 139 oo Tal ae ong ls hora de implantar x iendea queel factor de uilizacién de memoria sea lv nix prOuino posed I-y dado queel eceso aromas parciles despa AEPRESENTAGION DE LAS ESTRUCTURAS AARAY, REGISTRO Y CONJUNTO 33. WT TT RRRK Baca } . | | Fig. 146 Representacidn del ajuste dean no utlizado rapist, bras es un proceso farragoso y relativamente ineficiente, hay que llegar a un compromiso. Para ello, deben hacerse las siguientes consideraciones: | Bl ajuste disminuye la utilizacién de memoria, ), La omisién del ajuste puede necesitar el acceso ineficiente a zonas parciales de Ja palabra. 1. Blacceso a las zonas parciales de Ia palabra, puede dar lugar a que aumente el programa compilado y, por ello, contrarrestar el beneficio obtenido por Ia omisi6n del ajuste. De hecho, las consideraciones 2 y 3 son frecuentemente tan dominantes que los compiladores ajustaran siempre automaticamente. Se observa que el factor lc utilizacién sera siempre u > 0,5, sis > 0,5. Sin embargo, sis < 0,5, el factor ute utilizacién puede incrementarse de manera significativa almacenando mas ie un componente del array en cada palabra. Esta técnica se denomina empaque- undo, Si se empaquetan n componentes en una palabra, el factor de utilizacién es (ver Fig. 17), a3 T 2 a ig 17 Foard de ses esmpnentes em unt pars,1 ISTRUCTURAS FUNDAMENTALES DE DATOS Para ncceder al componente i de un array empaquctado es preciso caleular la sneveidn je la palabra en que esté localizado y su posicién & dentro de la palabra, j= idive k= imodn=1—jen (1.39) Hn kx mayoria de los lenguajes de programacién el programador no tiene con- ol sobre la representacién de las estructuras abstractas de datos. Sin embargo, tleheria ser posible indicar el deseo de empaquetar, al menos en los casos en que squepa mids de un componente por palabra, es decir, cuando pueda conseguitse ‘unit gamnaneia en economia de memoria de factor 2 0 superior. Se adopta el con venio de indicar este deseo de empaquetar, precediendo el simbolo array (0 record), en a declaracién, por el simbolo packed. type alfa — packed array [1 . .n] of char Lista posibilidad es particularmente valiosa en computadores con palabras snules y con accesibilidad a campos parciales de la palabra relativamente ade- cuada. La propiedad esencial de este prefijo es que de ninguna forma cambia cl significado (0 validez) de un programa. Esto significa que la eleccién de una representacién alternativa puede indicarse ficilmente con la garantia implicita que el significado del programa permanece invariable. HI eoste de acceso a los componentes de un array empaquetado puede tedu- cirse dristicamente si todo el array se empaqueta (0 desempaqueta) al mismo tiempo. La razén es que puede hacerse un barrido secuencial eficiente sobre todo cl array, sin que sea necesario evaluar una complicada funcién para cada com- ponente individual. Por ello se postula la existencia de dos procedimientos norma- lizudos pack y unpack, definidos de Ja forma que se indica a continuacién. Se suponen las variables u: array [a..d] of T p: packed array [b.. c)of T Houde a « Gin y) LA ESTRUCTURA FICHERO SECUENCIAL 37 Estas operaciones légicas existen en todos los computadores digitales y ademas operan simulidneamente con todos los elementos correspondientes (bts) de una palabra. De acuerdo con ello, parece que para poder implantar las operaciones bisicas entre conjuntos de fotma eficiente, éstos deben representarse por un mime- ro fijo. pequeno, de palubras sobre las que sea posible utilizar no s6lo las operacio~ nes légicas bisicas, sino, ambign las de desplazamiento (shi). [Link]én de pertenencia a un conjunto se implanta fisicamente, entonces, mediante despla~ vamiento tinico y subsiguiente operacién de test del bit de signo, Por tanto, un test de la forma: * xin [ey Cy ---5 Gn) puede implementarse de una forma mucho mis eficiente que Ja expresién booleana convencional =a) V & Sa) VV OHO) Por tanto, la estructura conjunto debe emplearse solamente con tipos base pequefios. El limite de cardinalidad del tipo base, para el que puede garantizarse ula implantacién fisica razonablemente eficiente, viene determinado por la Iongitud de palabra del computador de que se trate y es evidente que los compu tadores de palabra larga son preferibles a este respecto. Si el tamaiio de palabra cs relativamente pequeiio puede adoptarse una representaci6n que utilice varias palabras 1.11, LA ESTRUCTURA FICHERO SECUENCIAL La caracteristica comiin de las estructuras de datos presentadas hasta aqui, es lect, el array, el registro y el conjunto, es que su cardinalidad es finita (siempre ‘gue el cardinal de los tipos de sus componentes sea finito). Por ello, presentan pocas dificultades de implantacién; pueden encontrarse representaciones vilidas pura las mismas, en cualquier computador digital La mayoria de las lamadas estructuras avanzadas —secuencias, Arboles, rrafos, etc..—se caracterizan porque su cardinalidad es infnita. Esta diferencia ‘on las estructuras Fundamentales de cardinalidad finita es de gran importancia y tiene consecuencias pricticas significativas. Como ejemplo, se define a estructura secuencia como sigue: ‘Una secuencia con tipo base 7, es, bien la secuencia vacia, o la concatenacién «le una secuencia (con tipo base T,) con un valor de tipo T, Ta secuencia tipo T asi definida comprende infinitos valores. Cada valor en \isnismo contiene un nimero finito de componentes de tipo T,, pero este nimero ho esti acotado, es decit, para cualquier secuencia dada es posible construir otra jones andlogas pueden hacerse sobre otras estructuras «avanzadasy\W[SiIUCTURAS FUNDAMENTALES DE DATOS dio hatos. La mas importante es que la cantidad de memoria necesaria para repre- seutit_un dato de un tipo estructural avanzado no se conoce en ef momento de ‘vompilacidn: de hecho, puede variar durante la ejecucién del programa. Esto re- quiere algiin esquema de asignacin dinémica de memoria en el que la memoria vw vaya octipando a medida que los valores «crecen» y, posiblemente, se vaya libe- tunuko para otros us0s a medida que los valores «encogen». Por ello, estd claro siue li repreventacién de las estructuras avanzadas es un problema sutil y dificil ‘aya sulucidn influye de forma crucial en la eficiencia de un proceso y en la eco- nama conseguida en ef uso de la memoria. Una eleccién adecuada s6lo puede Ilevurse a eabo sobre la base de un conocimiento de las operaciones elementales «que se vayan a realizar sobre ta estructura y de su frecuencia de ejecucién. Como «ta informacién es desconocida por el disefiador del lenguaje y de su compilador cs taonable que las estructuras avanzadas se encuentren excluidas de los lenguajes sle-uso general, Por la misma razén, los programadores deberian evitar su utiliza «46 siempre que su problema pueda tratarse mediante el empleo tinico de estruc- {uray fundamentales. thu la mayor parte de los lenguajes y compiladores, se resuelve el dilema de tener que proporcionar dispositives de estructuracién avanzada de datos, sin ‘obre su uso potencial, teniendo en cuenta que todas las estructuras, wauzudlas «le datos se componen, bien de elementos no estructurados, 0 de es- tvucturas fundamentales de datos. Cualquier estructura puede ser generada me- thante operaciones explicitas especificadas por el programador, siempre que éste ‘ueute von posibilidades de asignacién dindmica de sus componentes, y de enca- dlenamiento y referenciacién dindmicos de estos componentes. En el Capitulo 4 senicas de generacién y manipulaci6n de estas estructuras avanzadi Vsiste, sin embargo, una estructura que puede considerarse avanzada, ya que su catdinalidad es infinita, pero cuyo uso es tan general y frecuente, que resulta da su inchusién entre las estructuras basicas: la secuencia. Para definir ‘le forma abstracta el concepto de secuencia, se introduce la siguiente notacién: 1. ©) designa la secuencia vacta. +g) designa la secuencia de un tinieo componente, x4; se denomina secuencia unitaia. SEN Gey eeey tp) ©Y = Oye os Je) som secuencias XB = ey Ss Day Te aan ces ht eoncatenacién de xe y Siw Gxyeessa) €8 tina Secuencia no vacia, primerolx) x, (1.42 slesipna ef primer elemento dev SEA Opec ta? OF MMT SeetENEEA MO Vacia LA ESTRUCTURA FICHERO SECUENCIAL 39 restofx) = CX yy +s ¥e? (1.43) es la secuencia x sin su primer componente. Por tanto, se verifica la relacién invariante €primero( x) & «aay La introduccién de’estas notaciones no significa que se vayan a utilizar en pro~ agramas reales para ser ejecutados en computadores reales. De hecho, es esencial ‘que la operacién de concatenacién no se use en forma generalizada, y que la mani- pulacién de secuencias se limite a la aplicacién de un conjunto de operadores ‘cuidadosamente seleccionados, que aseguran una cierta disciplina de utilizacién, pero que, a su vez, se definen a partir de las nociones abstractas de secuencia y concatenacién, La eleccién cuidadosa del conjunto de operadores de secuencias capacita a los implementadores para encontrat representaciones adecuadas y cficientes de las secuencias en cualquier tipo de memoria; esto garantiza que el ‘mecanismo asociado de asignacién dindmica de memoria sea lo suficientemente simple como para que cl programador pueda trabajar sin preocuparse de los de- talles. Para poner en claro que la secuencia que se va a introducir como estructura bisica, esti asociada con un conjunto restringido de operadores, que fundamental- mente permiten s6lo el acceso estrictamente secuencial a componentes, esta es- iructura se denomina fichero secuencial 0, para abreviar, simplemente fichero. En forma totalmente aniloga a la empleada para definicién de los tipos array y conjunto, un tipo fichero se define por la formula [ope 7 = feof 7. (145) ‘que expresa que cualquier fichero de tipo T' consta de cero © mas componentes de tipo T,. Exeapos type texto = file of char type mazo ~ file of tarjeta Lo principal del acceso secuencial es que en un momento dado sélo puede acce- lerse de forma inmediata a un tinico, y especificado, componente de la secuencia. Kste componente corresponde a la posicién en ese momento del mecanismo de ceeso. Esta posicién puede cambiarse, por los operadores de fichero, normal- mente all componente siguiente o al primero de toda la secuencia, Para expresar, de una manera formal, {a posicidn de un fichero, se considerara un fichero xfu LSIHUCTURAS FUNDAMENTALES DE DATOS como si estuviera dividido en dos partes, una, x), a su izquierda y otra, x, @ su detecla, videntemente la 6 (1.46) express un relaci6n invariant. Un segunda, y muy importante, consecuencia del acceso secuencial es que los provenos de construcein e inspeccién de una secuencia son distintos y no pueden tnerclurse en cualquier orden. Asi, un fichero se construye afiadiendo repetida- mncnte componentes (a su extrem final) y puede, subsiguientemente, inspeccio- tuntse secuencialmente, Por ello, es habitual considerar que un fichero puede en- Canttarne bien en estado de ser construido (escrito) 0 bien en estado de ser inspec- nut (leido. Ti ventaja del acceso estrictamente secuencial es particularmente notoria, silos licheros van a estar situados en dispositivos de almacenamiento intermedio, to decir, si se presentan transferencias entre distintos dispositivos. El método de xvew secuencial eal nico et el que las complejidades de los mecanismos nece- snrios para tales transfereneias pueden ser ocultadas con éxito al programador. Ti particutar, es posible la aplicaciOn de simples réenicas «buffering» (memorias ampon) que garantizan por si solas el uso Sptimo de los distintos recursos dis- pwonibles en equipes complejos de proceso de datos, Iixisten algunos dispositivos de almacenamiento en los que el aceeso secuencial ¢s realmente el tinico posible, Entre ellos estin evidentemente todas las clases dlecintas Pero, incluso en los tambores magnéticos y discos, cada pista constituye tw dispositive de almacenamiento que permite tinicamente el acceso secuencial 11 acceso estrctamente seeuencial es la caracteristica primordial de todo dispo- sutivo movil, y también de algunos otros no mévites, 1.11.1. Oporadores elomentales de ficheros ‘A continuacién se formula la nocién abstracta de acceso secuencial mediante tun conjunto de operadores elementales de fichero, wtilizables por el programador. ‘Sc dlinen a partir de los conceptos de secuencia y concatenacién. Hay un opera- lo patra iniciar el proceso de generacién del fichero, otro para iniciar ta inspec- ‘in, otro para afiadit un componente al final de la secuencia y otro para avanzar {a inspeccién al componente siguiente. Los dos diltimos se definen de forma que incluyen un variable implicita auxiliar que representa un «buffer», Se supone que este timo se asocia automaticamente a cada variable fichero x, y se le de- “innit por xf. Evidentemente, si x es del tipo 7, x} es del tipo base de T, Ty 1. Construccién de ka secuencia vacia, La operacion rewrite(x) a7) LA ESTRUCTURA FICHERO SECUENCIAL 41 equivale a la asignaci6n =O Esta operacion se realida para escribir sobre la secuencia en curso, x, ¢ iniciar 1 proceso de constryecién de una nueva secuencia, y corresponde al rebobi- nado de una cinta, 2, Extensi6n de una’secuencia, La operacién ar) (1.48) corresponde a Ia asignacién xis x& (x1) {que afiade el valor xf al final de la secuencia x. 3. Iniciacién de una inspeccién. La operacién reset(x) (1.49) equivale a las asignaciones simultaneas Q coy primero(x) Esta operacién se utiliza para iniciar el proceso de lectura de una secuencia. 4, Paso al componente siguiente. La operacién, get(x) (1.50) ‘equivale a las asignaciones simultaneas x12 = xy & Cprimerolxp)> Xp! = restolxp) xt! = primero(restoxp)) Obsérvese que primero(s) slo esti definida si s + <>. Lox operadores rewrite y reset no dependen de la posicién del fichero previa a su ejecucién; yuelven a situar el fichero, en cualquier caso, en su posicién origen,42 |STRUCTURAS FUNDAMENTALES DE DATOS ‘Cuando se inspeceiona una secuencia es necesario estar en condiciones de re- crmocer el final de la misma, porque, de otra forma la asignacion xf: = primerolxp) epresentarii una operaci6n no definida, Alcanzar el final del fichero es evidente- tc sinbnimo de que la parte a la derecha, xp, esta vacia. Por ello se introduce of predicado eoftx) = x1 <>. (st) ita significar que se aleanza el fin del fichero (end of file). La operacién get(x), ur tanto, solo puede ejecutarse si el predicado eof(x) es falso. {En principio, es posible expresar todas las operaciones sobre ficheros en fun- cin de cuatro operadores bisicos, En Ia prictica, sin embargo, es frecuente combinar kt operacién de avanzar la posicién del fichero (ger 0 put) con el acceso tt la variable buffer, Por ello, se proponen dos nuevos procedimientos; ambos pueden expresarse en funcidn de los operadores basicos. Sea v una variable ye tuna expresién de tipo T,, componente del fichero. De acuerdo con esto reail(x, ») es sindnimo dev: = xt; get(x) write(x, €) es sinonimo de xt: = e; put(x) 11 ventaja de utilizar read y write en lugar de get y put reside no sélo en su breve- dnd, sino también en su simplicidad conceptual. Ya que, de esta forma, es po- sible ignorar la existencia de la variable buffer x1, cuyo valor algunas veces esté invlfinido, La variable buffer puede, sin embargo, ser util para cuando se quiere inspeccionar el componente siguiente sin ener que avanzar la posicin del fichero. Las condiciones previas para la ejecucién de los dos procedimientos son —reoftx) para —_read{x, ») eofx) para write(x, e) A leer el predicado eof(x) toma el valor verdadero tan pronto como se ha leido cliltimo elemento del fichero. Estas consideracjones estan elegantemente incor- poradas en Ios dos esquemas de programas que se indican a continuacion para la consiruceidn y proceso secnencial de un fichero x. Las instrucciones R y Sy el Hredicado.p son parmetros adicionales de tos esquemas. LA ESTRUCTURA FICHERO SECUENCIAL 43 rewrt(o): | ile p do Ae co beain 00; wrt) [st Escribir el fichero Iver el fichero x ==. | while —eof(x) do | begin read(x0); S(e) al (1.53) 1.11.2. Ficheros con subestructura En la mayoria de las aplicaciones, los grandes ficheros requieren cierta clase de subestructura, Por ejemplo, un libro, aunque puede considerarse como una secuencia tinica de caracteres,se subdivide en capitulos y parrafos. El objeto de festa subestructura es proporcionar algunos puntos explicitos de referencia, ‘algunas coordenadas para facilitar la orientacién en la larga secuencia de infor- tnacién, Algunos de los dispositivos fisicos de almacenamiento facilitan la repre- sentacién de estos puntos de referencia (por ejemplo, las marcas de cinta) y son ccapaces de situarse en ellos con mayor velocidad que cuando se inspecciona toda la informacién situada entre estos puntos de referencia. De acuerdo con la notacién seguida hasta ahora, la forma natural de introducir un primer nivel de subestructura es considerar el fichero como una secuencia de componentes que a su vez son secuencias, es decir, como un fichero de ficheros. Suponiendo que los componentes iiltimos (0 unidades) son de tipo U, las subes- ructuras son, por tanto, de tipo T = file of U el fichero completo es del tipo T = file of T 1's evidente que de esta forma los ficheros pueden construirse con particiones Bats aeees que se desee. En general, un tipo T, puede definirse 1 fileof TG» i= Le. v Ty U. Tales fi eros se denominan frecuentemente ficheros multinivel, yI LSTHUGTURAS FUNDAMENTALES DE DATOS tin componente de tipo ; se denomina segmento de nivel i, Un ejemplo de fichero thnultinivel es un fibeo, en el que los niveles de segmentacién corresponden a capi- Tile, apuartados, parrafos y lineas. Sin embargo, el caso ms general es el fichero ‘an un diivo nivel de segmentacion 1H ichero segmentado de un tnico nivel no es idéntico en absoluto a un array dle tihieros. ya que el ndimero de segmentos es variable y el fichero sélo puede vratemerse por su extremo final, Continuando dentro de la convencién de no- facxin wtilizada hasta ahora, y suponiendo un fichero definido por x: file of file of U {| desigua ef segmento accesible en el momento de proceso, xT el componente Initnrio accesible en dicho momento. De acuerdo con esto put(xt) y get(x1) se ‘lefieren a un componente unitario y pur(x) y ger(x) designan las operaciones de audir y avanzar al segmento siguiente. Lon fichcros segmentados estén implantados pricticamente en todos los dis- Jwositives de almacenamiento incluso en cintas magnéticas. Su segmentacién no In cambiudo su caracteristica basica de permitir solamente acceso secuencial bien i eomponentes unitarios 0 bien —por mecanismos de salto més rpido— a seg- nentos, Olcos dispositives de almacenamiento —notablemente los discos y Jambores- contienen habitualmente un niimero de pistas cada una de las cuales representa propiamente un dispositive secuencial que normalmente es demasiado Conte pant almacenar un fichero completo. Por ello, los ficheros en disco se ex- tienen sobre varias pistas y tienen la informacién de control apropiada para ase~ jury la conexion ente pistas, Obviamente el punto origen decada pista constituye tina marca natural de segmento, a la que puede accederse atin mas directamente {ea fis marcas en cualquier soporte estrictamente secuencial. Una tabla de in- ‘{ices almavenada en memoria principal podria utilizarse, por ejemplo, para diree- ‘omar las pistas donde comienzan Jos segmentos ¢ indicar su longitud (ver Figu- ra 1.10) =e Weed oo coo coe ooo ig 1.10 ehero indexado eon einen smenton tas considernciones anteriores conducen a los amados fieheros indexados amidios tnmbién alyunas voces fieheras de acceso directo), Realmente los tam- LA ESTRUCTURA FICHERO SECUENCIAL 45 bores y los discos estin organizados de forma que cada pista contiene muchas marcas fisicas en las que puede empezar la lectura o escritura. Por ello, no es preciso que cada segmento ocupe una pista completa, ya que de esta forma resul- taria una utilizacién muy pobre del almacenamiento disponible, si los segmentos son cortos para la longitud, de'pista. El tramo de almacenamiento entre marcas cconsecutivas se denominia segmento fisico (0 sector) en contraste con el segmento légico que es una entidad ‘significativa en la estructura de datos del programa. Evidentemente cada segmento fisico alberga como méximo un segmento l6gico, y cada segmento lé[Link] como minimo un segmento fisico (incluso si esta vacio), Debe tenerse en cuenta que aunque se denominan ficheros de «acceso \Jirecto», el tiempo medio para localizar un segmento, llamado tiempo de laten cia, es ka mitad del tiempo de una vuelta del disco. Los ficheros indexados conservan la caracteristica esencial de que la eseritura se realiza secuencialmente a partir del dtimo elemento, Por ello, son particular- ‘mente ities en aplicaciones en las que se producen pocos cambios. Estos cambios se realizan, bien ampliando el fichero, o actualizandolo y volviéndolo a copiar completo. La inspeccién de los datos puede realizarse de forma mucho més rapida y selectiva mediante el uso de las tablas de indices, Esta situacton es tipica en los llamados bancas de datos. Los sistemas que permiten la actualizacién selectiva de partes interiores del fichero son generalmente de utilizacién dificil y poco fiable, ya que los nuevos clomentos de informacion deben tener ef mismo tamaiio que los antiguos que roemplazan, Ademis, en aplicaciones que afectan a grandes masas de datos, la vciualizacién selectiva no es recomendable, habida cuenta de la regla basica tle que ante cualquier fallo, ya sea debido a un programa erréneo, o al mal fun- cionamiento del equipo, debe existir un estado de los datos al cual pueda volverse para poder repetit el proceso que fall6. Por ello, la actualizacién se lleva a cabo hormalmente de manera completa, de forma que el fichero antiguo se sustituye por la nueva copia actualizada, s6lo después de que se ha Hlevado a efecto una verificacién que establezca que el nuevo fichero es vilido. A efectos de actualiza- +i6n la organizaci6n secuencial es con mucho la mejor desde el punto de vista de tabilidad. Debe preferirse a otras organizaciones més sofisticadas de grandes nurses de datos, que pueden ser mas eficientes, pero que, a menudo, producen i pérdida total de Ios datos cuando falla el equipo de proceso. 111.8, Textos 1Los ficheros cuyos componentes son de tipo char juegan un papel especial- cute importante en el céleulo y proceso de datos: constituyen el elemento de ‘antaicto entre los computadores y los usuarios humanos. Tanto la entrada legible proporcionada por los programadores, como la salida legible que representa los treailtados calculidos, estin constituidos por secuencias de caracteres. Por ello, 1 este Lipo de datos debe dirsele un nombre normaAu USTRUCTURAS FUNDAMENTALES DE DATOS type text = file of char 1.1 comunicaci6n entre un proceso en el computador y su autor humano se es- {ubleve,finalmente, mediante un elemento puente (interface) que puede represen tise por dos ficheros de textos. Uno de ellos contiene la entrada (input) al proceso, y el olro los resultados procesados llamados salida (ouput). Por ello, se supondra In existencia de estos dos ficheros en todos los programas, siendo su declaracion var input, output: text eniendo en cuenta la hipétesis de que estos ficheros representan los dispositivos normalizados de un equipo de proceso (tales como la Iectora de fichas y la impre- sora) se supondra que el fichero input es s6lo para lectura y el fichero output s6lo para eseritura, nado que ambos ficheros se utilizan predominantemente, se considerard que Si el primer pardmetro de los procedimientos read y write no es una variable ichera, tom el valor input 0 outpur por defecto. Avanzando en esta linea, se presentan dos procedimientos normalizados con un niimero arbitrario de argu- mientos. Los convenios de notacién de estos procedimientos se resumen de la forma siguiente: read(x1,...,n) equivalente a reaatinput, x1, xn) write(xl, ...sn) equivalente a write(output, x1, .-. xm) read(f, x1, ..., xn) equivalente a begin read(f, x1); ... ; read(f, xn) end write(f, x1, . xn) equivalente a Dewln write(f, x1); .. .; write(f, xn) end 1Los textos son ejemplos tipicos de secuencias con subestructura. Las unidades usuales de subestructura son eapitulos, parrafos y lineas. Una forma corriente de representar estas estructuras elementales en los ficheros de texto es utilizar ca- racteres especiales de separacién. El carécter blanco es el ejemplo mas conocido, pero pueden utilizarse separadores similares para marcar los finales de linea, inirrafo y capitulo, Por ejemplo, el cédigo ISO de amplia difusién (incluyendo su versién americana ASCID) contiene varios elementos de esta clase lamados earacteres de control (véase Apéndice A). este libro se ha rehusado la utilizacién de caracteres especificos de separa- iin, y lt definicién de un método de representacién de las subestructuras, En su Ingsr se considera un texto como fichero formado por secuencias de secuencias dle earacteres, que representan las lineas. También, se limita el analisis a un nivel ‘imivo de subestructura, es decir, la linea. Sin embargo, en vez de considerar lox textos como ficheros constituidos por ficheros de caracteres. imprimibles, se consideran como ficheras de caracteres, introduciendo operadores y predica- los adicionales para su manipulacién, es decir, para marcar y reconover las La ESTRUCTURA FICHERO SECUENCIAL 47 lincas. El efecto de ellos se comprenderé mejor si se supone que las lineas estan weparadas por caracteres (hipotéticos) de separacién (no pertenecientes al tipo char) y su misién se considera que es la insercién y reconocimiento de tales sepa- autores. Los operadores adigionales son los siguientes: writeln(f)Atiadir-una marca de linea al final del fichero readin(f) Saltar caracteres en el fichero f hasta el siguiente inmediato a la proxima marca de linea. cof) Funcién booleana. Verdadera, si la posicién del fichero ha avanzado hasta una marca de linea; falsa, en otro ¢as0 (se st pondré que si eoln(f) es verdad 1/= blanco). Con esta base, es posible formular dos esquemas de programa para escribir ¥ leer textos, semejantes a los de «escritura» y «lectura» de otros ficheros [véase (1.52) y (1.53)}. Estos esquemas se basan en un fichero de texto fy prestan la lebida atencién a la generacién y reconocimiento de la estructura de linea. Sea R(\) una instrucei6n que asigna un valor a x (de tipo char) y define las condiciones vy qcon significadas «éste era el ltimo cardcter de fa linea» y «éste era el Glin ‘uvficter del fichero», Sea U una instruccién a ejecutar al principio de cada linea leisa, S(x) una instruccién a ejecutar para cada caricter x del fichero, y V una uuccién a ejecutar al final de cada linea. Uscritura de un texto f. rewrite(f); white 9 do begin hile ap do in R(x)s write x) ae end ; writeln(f) Fevtura de un texto f. reset(); while —eof(J) do j begin U; | while eoln(/) do begin real(f.x); S() | end ; | V5 read) | (1.53) endAN, USTRUCTURAS FUNDAMENTALES DE DATOS Hay casos en que la estructura de lineas en un texto no representa informacién elevate alguna, La hipétesis realizada sobre el valor de la variable «buffer» al ceontrar una marca de linea [ver definicién de eoln(/)] permite utilizar, en fests casos, un esquema de programa més simple, Obsérvese que de acuerdo ‘can la definicién de eoln cada final de linea se presenta como un carécter blanco aicion: while “eo/(f) do. begin read(f, x); S(x) (1.56) end Lin ka mayoria de Jos lenguajes de programacion se acostumbra admitit ungumentos de tipo integer 0 real para los procedimientos de leer y escribir. sti peneralizacién seria inmediata si los tipos integer y real se definieran como inniays de caracteres cuyos elementos designaran los digitos individuales de los iniunscros, Los kenguajes fuertemente orientados hacia las aplicaciones comerciales se aclaptan realmente a tales definiciones, y requicren una representacion de los hhimeros a partir de los digitos decimales de acuerdo con el sistema numérico de- imal, La ventaja importante de presentar los tipos de datos integer y real como fundamentales es que estas especificaciones detalladas pueden omitirse y que un ‘xuipo de proveso puede usar diferentes representaciones de los niimeros que scan hnncho mis adecuadas para sus propésitos. De hecho, los sistemas orientados ha- cist cileulo cientifico invariablemente eligen Ia representacién binaria que en mu- ‘hos aspectos es superior a la representacién decimal, Histo implica, sin embargo, que un programador no puede suponer que los inimieros se len © escriben en Ficheros de texto sin que medien operaciones de conversion. Es costumbre esconder estas operaciones de conversi6n en las instruc- ciones de keetura y escritura con argumentos de tipo numérico. El programador profesional, sin embargo, es consciente de que tales instrucciones (llamadas instrucciones EJS 0 1/0) ‘ncorporan dos funciones distintas: transferencia de dios entre diferentes dispositivos de almacenamiento y transformaciones de la tepresentacién de los datos. Estas iltimas pueden ser muy complejas y costosas en tiempo. Tin Jos capitulos siguientes de este libro, las instrucciones de lectura y escritura de argumentos numéricos se utilizarin de acuerdo con las reglas del lenguaje dle programacion PASCAL. Estas reglas permiten controlar el proceso de trans- Formacidn, mediante un determinado tipo de especificacién del formato. La espe: cifieaciin de formato indica el niimero de digitos que se desea para el caso de ins- ruceiones de escritura, Este niimero de earacteres, también llamado «amplitud de tcamipoo, se escribe inmediatamente después del argumento de la forma siguiente: write fm) Hi arpumente x vn a eseribinse en el ficinero /: su valor se convierte en unt sectien- LA ESTRUCTURA FICHERO SECUENCIAL 49 cia (como minimo) de n caracteres; si es necesario, los digitos iran precedidos por tun signo y un niimero adecuado de blancos. No es preciso dar més detalles para comprender los iiltimos ejemplos de programas de este libro, A continuacién se incluyen dos ejemplos de conversion dle la representacién de,unrniimero (Programas 1.3 y 1.4), con el propésito de poner de relieve ka costosa complejidad de tales operaciones, que normalmente cstin implicitas en las’ instrucciones de escritura, Estos dos. procedimientos opresentan la conversién de nimeros reales desde la representacién decimal a ‘una representacion «interna» arbitraria, y viceversa. (Las constantes en las cabe~ ‘voras se determinan por las propiedades del formato de nlimeros en coma flotante del computador CDC 6000: exponente binario de 11 bits y mantisa de 48 bits. La funcién expo(x) designa el exponente de x.) Programa 1.3. Lectura de un nimero rel procedure leerreal (sar f+ texto; var x: real); ‘lee un maero real x del fichero {las constantes siguientes dependen del sistema const 148 — 281474976710656; {= 2448} Timi = 6294995342131; {= 148 div 5} 2=2%; {=ord'0)} lim = 322; { maximo exponente } lim 2 = 292; _{ minimo exponente } type posint = 0.323 vue ch: char; y: real; a i €: integers s.8: boolean; ”{signos } sion ten(e: posint): real; { = Wese, 0 « end “4 then Programa {21 (Continucion) LA ESTRUCTURA FICHERO SECUENCIAL 51 ite < fim? thea begin a: =0;e: = 0 end else ife> limi then 3 begin message ("NUMERO DEMASIADO GRANDE’); halt end; {0 148 then y ; = ((a + 1) div 2) + 2.0 ese y : = a; its then y : = ite <0 then x2 y/ten(—) else ife + O then x: = y « ten(o) else T=) \ Creofif)) do gen: cond {lerreal} Programa 1.3. (Continuacién) Programa 1.4 “Eserbir un nimero real procedure escribireal (var f: text: x: real; n: integer): \eseribir un numero real x con n caracteres en coma flotante decimal} Mas siguientes constantes dependen de as condiciones de la representacion tle numeros reales en coma flotante} const 148 ~ 281474976710656; {= 2 «= 48; 48 ~ tamatio de la mantisa} z ford? 0") type posint = 0, .323; {rango del exponente decimal} vat ¢, de, , el, €2, i: integer; function ten(e: posint): real; { 10 ++ e,0 < e < 322} var i: integer; t: real; begin i: = 050: = 1.0; repeat if odd{e) then case iof Ort: = 1+ LOL; Litt= t+ LOB2; iste te LOEA Bite 1s LOES; [Link] = 1+ LOEI6; Sit: = t+ 1.0B32; [Link] = te LOE6S: Titi = te LOEI28; Bir: = 14 10E256 end: ce: ediv2;i:=i+1 until e 0; ten: 4 cod [ ten}ESTRUCTURA FUNDAMENTALES DE DATOS begin { al menos se necesitan 10 caracteres: b + 9.9. + 999} ix = O then begin repeat write(f,"):n: =n — 1 until n <1; write(f, 0?) ud else beggin < 10 then n : = 3 else n repeat write f,*");n: =n —1 until < 15 {1 Othen begin e : = ¢ © 77 div 256 + 1; x: = x/ten(e); ifx > 1.0 then begin x: = x/10.0;e: =e +1 end end else begin e : = (e + 1) #77 div 256; x: = ten(—e) + x; if x <0.1 then begin x: = 10.0*x;e:-e—1 end end; fos x<109} ease nof —{ redondeo } Qixr=x+05E~ 2; 3ixi=x+05E—3; 4ix:=x405E— 4; Six:=x+05E~5; 6:x:= x +05E—6; Tix:= x +05B—7; Bix:= x +05E 9ix:= x +05E— 10:x:= x +05E— 10; Mix: =x +05B—11; I2:x:=x +05E— 12; ixi=x+05E—13 Mix:= x +05E— 14; IS:x:=x +05E~15 end; Programa 14 (Continuen) UA ESTRUCTURA FICHERO SECUENCIAL 59 ifx> 10 then begin: =[Link]:=e +15 end; 2 = rume(x, 48); [3 trunclx +(2 +948))} 2 = 10 werd == div 148; write(f, chr(d $2), fori: 2t0n do, begin c : = (c — d# 148)» 10; d: = ediv 48; writef, chr{d + 2) end: write f,"E); €: = ife <0 then begin write(f, ‘—);e: = —e end else write(f,* +”): el: = e+ 205 div 2048; 2: = e — 10 sel; 0: = el + 205 div 2048; el : = el — 10 0; writelf, chr(el) + 2), chr(el + 2), chrle2 + 2)) end end lexeribirreal} Progeama 14. (Continuscién) 111.4. Un programa para edicién de ficheros Como ejemplo de aplicacion de estructuras secuenciales se plantea el siguiente tublemea que, ademis, sirve para mostrar un método de desarrollo y explieaci6n vlc juogramas. Este método se Hama de refinamiento gradual [1.4, 1.6] y se uti- Avani para explicar muchos algoritmos a lo largo de este libro. 11 problema es desarrollar un programa que edite un texto x en la forma de ‘wi texto» Editar se utiliza agui en el sentido de borrar o reemplazar determinadas lines © insertar otras nuevas. La edicién esti dirigida por una secuencia de ‘mimueciones de edicién representadas por un texto normalizado llamado input vi ly forma siguiente: 1m lnsercién de un texto después de la linea m. B, mn. Borrado de las lineas m hasta n. Ry mn. Reemplazamiento de las lineas m a n. F Fin del proceso de edicién, ‘Cada insteuceiin se eseribe como una lines en el fichero normalizado input, al ‘ques deuromina fichero de instrueciones, nr yn son niimeros de linea, decimales,M ESTRUCTURAS FUNDAMENTALES DE DATOS y los textos a insertar deben seguir inmediatamente a las instrucciones J, R. La listu de insteucciones se termina por una linea en blanco. Se supone que las instrucciones de edicién se producen para mimeros de linea estrictamente crecientes. Esta regla sugiere, de forma inmediata, un proceso wwenncial del texto de entrada x. Bsti claro que el estado del proceso debe carac- {ctizarse por la posicién en cada momento del texto x, definida por el mimero ule la Tinea que se esti considerando en cada instante Supéngase ahora que el programa de edicién se va a utilizar de manera inter- tiva y que, por ello, el fichero de instrucciones representa, por ejemplo, los datos ‘que se originan en la consola de un terminal. Con esta forma de operacién es muy interesante que el operndor reciba alguna clase de informacién de comprobacién. Una informacién atil y apropiada es el texto de la linea en la que el proceso se situs como consecuencia de la altima instruccién. Esta linea se denominara ine en curso. Una consecuencia importante de esto ultimo es que esta linea ulche representarse explicitamente por una variable, en la que se almacena transi oriamente después de leerla de x, y antes de escribirla en y. Esta técnica se de- homina de «mirada adelante». El programa de edicién puede formularse de la forma siguiente: rogram editor (x, y, input, output): var Ino: integer; {numero de la linea en curso} Ie : linea: {linea en curso} x viet begin leer instruccion; repeat interpretar instruccion; (57) escribir linea; leer instruccion until nstruceion = *F* end ‘A continuacién se procede a especificar con més detalles varias de las instruc ciones, Al refinar leer instruccion ¢ interpretar instruecion se observa que las ins- trucciones de edicién planteadas constan de tres partes: el cédigo de instruccién y dos pardmetros. Por ello, se introducen las tres variables codigo, m y n para vomunicacién entre ambas rutinas. var codigo, ch: char; im, m: integer Leer instruecién reait{codigo, ch); itch ~*) then read(m, ch) else m : = Ino; (1.58) Woh *} then readin) else m: = m; LA ESTRUCTURA FICHERO SECUENCIAL 55 \'sta formulacién capacita para aceptar instruceiones con 0, 1 6 2 parémetros sustituyendo apropiadamente por valores por defecto los no especificados. Iuterpretar instruceién copiar; if codigo ~ ‘I" then begin ponerlinea: insertar; end else if codigo = *B* then salvar else (1.59) if codigo = ‘R’ then begin insertar; saltar; end else if codigo = *F* then copiarresto else Error in una segunda etapa de refinamiento se expresan las instrucciones, copiar, unertar y saltar utilizadas en (1.59), en funcion de operaciones que afecten exclu avamente a Tineas, es decir, en funcidn de traerlinea y ponerlinea. Su caracteristica + onmin es la estructura repetitiva. Copiar sirve para copiar lineas de x a y, empe- ‘undo por la linea en curso y terminando en la linea m. Saltar lee lineas de x, ou copiarlas, hasta la linea m, Copiar: while Ino < m do begin ponerlinea; traerlinea; end Saltar: while Ino < do traerlinea Insertar: leerlinea: hile nofin do (1.60) begin ponerlinea:; traertinea end ‘raerlinea; Copiarresto: wile eoftx) do begin ponerlinea; traerlinea end: ponerlinea Fu ke tercera y titima etapa de refinamiento se expresan las operaciones ‘uctlinea, ponerlinea, leerlinea y escribirlinea en funcién de operaciones con carac- rics aistidos, Obsérvese ute, last ahora, (odas las operaciones trabajan exclusi- wuente eon lineas enters y no se ha realizado ninguna hipdtesis espe: Hole: fos detalles de estructura interna de kr lines, Se sube que fas Hineas a su ver,Mi ESTRUCTURAS FUNDAMENTALES DE DATOS son secuencias de caracteres, Serfa tentador declarar la variable /e (linea en curso) ‘vom una secuencia var le: file of char Sin embargo, teniendo en cuenta la recomendacién de que no debe usarse una entruclurt con cardinalidad infinita sies adecuada a los mismos fines una estruc- {uu fundamental (como el array) seria aconsejable utilizar una estructura de tray ct este caso, Esto es factible si se limita la longitud de linea, por ejemplo, 1 M0 caracteres. De acuerdo con esto se especifica var Je: array [1 . . 80] of char [as cuatro rutinas utilizan una variable indice i para este array que, en realidad, se miliza localmente y podria muy bien declararse de esta forma en cada rutina; adem, ahora es necesario introducir una variable global L para designar Ia longitud de la linea en curso. Traerlinea: i: = 0; ho: = Ino +1; eoln(x) do Ls read (x, lef) L: = 1; readin(x) Ponerlinea: i: = 03 while i < L do Degin i end; vwriteln(y) ast Leerlinea: i: = 0; while“ eoln(input) do begin: i ~ 1; readllefil) end; readin i: = 0; write (Ino} while i < L do begin i: = i end: vriteln rite (y, lel) Escribirtinea 1; write(le(@) 11a condicion nofin en la rutina insertar se expresa ahora en forma adecuada Lio ste programa de edicién de Ficheros. Con esto coneluye ef desarrollo de 1. tx EJERCICIOS 67 EJERCICIOS Supéngase que ls cardinals de los tiasestindaes integer, realy char se denominan por js de. £Cu 50, os cardinals de los siguientes tpox de datos dfinidos Como ejemplos en este caput: Sexo, boolean, diasemana, era, digo, oii, fl, if. complejo, persona. coordenada, charset, fecha, estadoina? Como se repesentiran ls variables de Ios tipos lists en e Eercicio 1.1 5) en la memoria det computador? 3) jen FORTRAN? ©) Jen otro lengtiajé de programacién a clegir por el lector? Cues son ls secuencias de instruciones (en el computador que decid el lst) Para las siguientes operaciones 2) aces lmacenamiento os elementos de araysy estos erapaquetados? b) operaciones con conjantos, inclido el test de prtenenia? {Puede comprobarse el wio corresto de los registos variants al ejcatar? Puede inoso comprobarse al compitr? 2Cailes son las razones para define determinados conjuntos de datos como ficheros Secuenciles en vez de como arrays? Se quiere implementa los fcherossecuenciles de la forma definida en 1.1. en un omutador con memoria muy ampli, Se permite mpone la estieién de ue Tos fisheros no exsedan una longitd determinada L, Po tanto 1s ficheos pueden repre sentase como arrays ‘Desrbir una posible mplementacin, que inciuya la forma elegida de eprsenta- cin de fos datos los procedimientos para los operadores elementals de fchero fet, pu, reset rerie, que definen por un conjunto de wxiomas et 1.11 Aplicar el ej cio 1.6 para ficheros segmentados, ‘Dado un horario de ferrocarril que lista Ios servicios diarios en varias lineas de una ‘compasia, se pide encontrar una representacion de estos datos en términos de arrays, jstros 0 icheros, que sea adecuada para consulta las horas de Hegads y sada para tuna estacién dada y en la direccién deseads del tren Se supone dado un texto T'en forma de fichero, y dos lstas de un pequetio nimero de Plabras en Forma de dos arrays y B. Se supone que las palabras son pequeliosatrays de caracteres de una Iongitud pequeda y fijada, Escribir un programa que transforme el texto T'en el texto 8 reemplazando cada ‘currencia de una palabra 4, por su correspondiente B, Qué ajustes —redefinicién de constantes, ete.— son necesarios para adaptar los Programas 1.3 y 14 al ordenador utilizable por el lector? Uscribir un procedimiento semejante al programa 14 cuya cabecera sea procedure inpriminreal (var f: texts x: real: nm: integer) Se supone que transforms el valor x en una secuencia de n earacteres como minimo {ys soe afaieos af extreme final del fichero f)-x se representa en forma decimal ‘neon fit eo a diilos a eontinnacibn eel panto decimal. Sies preciso, et nimero Thi prevedihs pon ner avdecna ale Blancos y/o un signe,li) ESTRUCTURAS FUNDAMENTALES DE DATOS 112. Volver a escribir el editor de texto de 1.11.4 en forma de un programa completo, 1.13. Comparar fas siguientes tres versiones de la biisqueda binaria con (1.17). ;Cudles de los tres programas son correctos? ; ules son mas eficientes? Se suponen las siguientes variables y una constante V > 0. var i,j,k: integers a array[l ..N] of 7: xT Programa A: hel ji=M repeat k= (0+ j) div 2; alk] < x then: = k else j: =k until (alk = 3) V =) Programa B: beh h=M; repeat k= (+ j)aiv2 ix < alk] then j:= k — 1; ial] < xtheni: =k +1 until i> 7 Programa C: -4f) a ffx < aff] then j : until > 7 ‘Nota: Todos los programas deben terminar con a[k] = x si tal elemento existe y ‘con alk] + sino existe ningin elemento con valor x, 1.14, Una compatia organiza una encuesta para determinar el éxito de sus productos: Sus productos son discos y cintas con éxitos musicales: los éxitos mis populares deben. ‘star ineluidos en una lista de éxitos (it parade), La poblacin encuestada se va a di- Vidir en cuatro eategorias sep sexo y edad (por jem, menores o iguales a veinte aosy mayoresde veintesanos) A cada persona se epde que dé el nombre dence oxi tos, Los Exitos se identitican por los ndimeros 1 N (por ejemplo N~ 30), Los resul tude de tn encuexta se representan por el fichero siguiente: REFERENCIAS 59 type exito = 1..N; sexo = (masculino, femenino): respuesta record apelido, nombre: alfa ‘edad: integer ‘eleccion: aray {1 .. S]ofexito end; var encuesta fie of respuesta Por tanto, cada elemento del fchero represents un encuestado ¢ incluye Su apelido, nombre, sexo, edad y sus cinco éritos elegidos en orden de preferencia. Este fichero cs la entrada a un programa que, se supone, calcula los siguientes resultados: 1. Lista de éxitos en orden de popularidad. Para cada uno se lista ef mimero del {xito y el nimero de veces que ha sido mencionado en la encuesta. Los éxito que ho han sido mencionados en br eucuesta se omiter de Ia ist 2. Cuatro listas distintas con los nombres y apellidos de todos los encuestados que ‘habian mencionado en primer lugar. uno de los tres éxitos mas populares en su categoria, Las cinco listas deben ir procedidas por titulos adecuados. REFERENCIAS Dau, 0. J,, Duxsrea, E. W. y Hoare, CA. R., Structured Programming (Nueva York! Academic Press, 1972), pg. 155-65, Hoare, C. A. R., «Notes on Data Structuring», en Structured Programming. Dahl, Dijkstra, and Hoare, pig. 83-174, junson, K. y Warrit, N., «PASCAL, User Manual and Report», Lecture Notes in Computer Science, Vol. 18 (Berlin: Springer-Verlag, 1974) ‘Want, N., «Program Development by Stepwise Refinement», Comm, ACM, 14, n.°4 (97th 7.ho LSIRUCTURAS FUNDAMENTALES DE DATOS ts « «The Programming Language PASCAL», Acta Informatie, 1, n° 1 (1971), nin, 15-68 bo «On the Composition of Well Structured Programs», Compuring Surveys 6, ne 4 (1974), pig. 247-59, 2 ORDENACION 2.4. INTRODUCCION El objetivo principal de este capitulo es aportar un conjunto extenso de ejem- pos que ilustren el uso de las estructuras de datos presentadas en el capitulo vaterior y mostrar como la estructura de los datos de base influye profundamente «1 los algoritmos que evan a efecto una tarea dada, Los procesos de ordenacién constituyen también un buen ejemplo de cémo una tarea puede desarrollarse ‘mediante algoritmos muy distintos, cada uno con ciertas ventajas ¢ inconvenien- tes, que deben ser valorados unos respecto de otros, segin la aplicacién particu lar de que se trate. Generalmente, se considera ordenar como el proceso de reorganizar un con- junto dado de objetos en una secuencia especificada. Fl objetivo de este proceso ‘> facilitar la bisqueda subsiguiente de los elementos del conjunto ordenado, Como tal, ¢s una actividad fundamental que se reatiza universalmente. Los ob- ivlos ordenados aparecen en las guias de teléfonos, en los ficheros del impuesto wre la renta, 10s indices de libros, bibliotecas, diccionarios, almacenes y casi en lowkas partes en que hay objetos que deben buscarse y recuperarse, Incluso a los hos pequefios se les ensefia a poner sus cosas «en orden», y se les enfrenta con sertas formas de ordenacién mucho antes de que aprendan nada de aritmética De aqui que la ordenacién sea una actividad fundamental y relevante, par- hicularmente en proceso de datos. {Qué otra cost va a ser mas fécil de ordenar «jue los datos! A pesar de todo, el interés de tratar los procesos de ordenacién 1 este libro se centra en las, atin més fundamentales, téenicas utilizadas en la vonstruceién de algoritmos. Existen pocas técnicas que no se relacionen en ‘nana forma con los algoritmos de ordenacién. En particular, este tema es idéneo yori mostrar una gran diversidad de algoritmos, todos con el mismo objetivo, muchos siendo Sptimos en algtn aspecto, y Ja mayoria de ellos presentando62 ORDENACION ciertas ventajas sobre los otros. Es por ello un tema ideal para hacer patente la wwecesidad del andlisis del funcionamiento de algoritmos. Ademas el caso de orde- nacion es muy adecuado para mostrar como pueden obtenerse ganancias muy sinnificativas del rendimiento mediante el desarrollo de algoritmos sofisticados, we se disponga de otros métodos mas sencillos, 1 influencia de la estructura de datos en Ia eleccion de un algoritmo —fené- ‘neu omnipresente— es tan profunda para los problemas de ordenacién que los inetods se dividen en dos categorias: ordenacién de arrays y ordenacién de ficke- ‘as (seouenciales). Ambas clases se denominan a menudo ordenacién interna y ‘ever, ya que Tos arrays se almacenan en la memoria interna répida, de acceso ‘leatorio, del computador y los ficheros se colocan convenientemente en alma cenamientos dexternos> mas lentos basados en dispositivos mecdnicos (discos y cintas), La importancia de esta distincién se hace evidente en el ejemplo de ‘ordenacin de tarjetas numeradas. Estructurar las tarjetas segin un array se corresponde con extenderlas todas delante del encargado de ordenarlas de forma ‘gue cada tarjeta sea visible y accesible individualmente (ver Fig, 2.1). Fig. 2.1, Ordenacion de arrays En cambio, estructurar las tarjetas segiin un fichero implica que de cada mon- {60 solamente es visible la tarjeta superior (ver Fig. 2.2). Esta restriccién tiene una influencia evidente en el método de ordenacién a utilizar, pero es inevitable si el nifimero de tarjetas a extender supera el que cabe en la mesa disponible, ‘Antes de comenzar, se introduce la notacién y terminologia que se va a utilizar 1 lo kargo del capitulo. Se suponen dados los items 0 articulos, a ayy INTRODUCCION 63 ay ays Or de forma que dada una funcién de ordenacién f se verifique: flan) < He) S++ < flay ep Fig. 2.2. Ordenacién de fcheros Normalmente, la funcién de ordenacién no se evaliia segin una regia determinada dle cAleulo, sino que se almacena como componente explicito (campo) de cada item. Su valor se denomina clave del item. Por tanto, la estructura registro es purticularmente idénea para representar los elementos a. A tal fin, se define un tipo item, que va a ser utilizado en todos los algoritmos de ordenacién que iuen: —— ~ type item — record clave: integer: lel rade decararse os vos components} | (22 | | t Los otros componenies, representan los datos de interés acerca de los items ne forman parte de la coleccién; la clave sirve exclusivamente para identificar det articulo. En lo que se refiere a los algoritmos de ordenacién que se van a Hvatar, sin embargo, la clave es el irico componente de interés y no es preciso sletinit ninguno de los dems. La eleccién de tipo uteger para la clave es, en cierta Jun, arbitraria. Evidentemente, puede utilizarse también cualquier tipo en el syne pueda definirse una relacién de orden total. Un método de ordenacién se denomina estable si el orden relativo de los ar- ficalos con la misma clave no se altera por ef proceso de ordenacidn. La estabi-4 ORDENACION tidad es deseable, 2 veces silos items estin ya ordenados de acuerdo con otras claves secundarias, es decir, con propiedades no rellejadas por la propia clave prinvari. Histe capitulo no debe contemplarse como un tratado exhaustivo de las tée- nia de ordenacién, Mas bien, se presentan en & ejemplos muy detallados de ilnunas (Genieas seleccionadas. Para un tratamiento més profundo del tema de tdennacién, el lector interesado puede acudir al excelente compendia de D. E. Kaw [2-7] (ver tambien Lorin 2-10), 22, ORDENACION DE ARRAYS La principal condici6n a imponer a los métodos de ordenacién de arrays es | utilizacion econémica de la memoria disponible. Esto implica que las permu- {aviones de items, con vistas a su ordenacidn,deben realizarse utilizando el espacio ‘ocupado por el array (ordenacién in situ) y que los métodos que transportan articulos de un array a hacia un array resultado b son intrinsecamente de menor interés, Teniendo restringida la eleccién de métadas entre las muchas soluciones. posibles por el criterio de economia de memoria, se clasifican a continuacién Estos, segiin su eficiencia, es decir, su economia de tiempo. Una buena medida de eficiencia se obtiene en base al niimero C de comparaciones de claves y M de movimientos (transferencias) de items. Estos nimeros son funcién del nimero nde articulos a ordenar, Aunque los buenos algoritmos de ordenacién necesitan del orden de n-log n comparaciones, se estudian inicialmente varias técnicas seneillas de ordenacién denominadas métodos directos, que requicren del orden de n® comparaciones de claves. Hay tres buenas razones para presentar los mé- todos directos antes que otros algoritmos mas répidos, 1. Los métodos directos son especialmente adecuados para poner de relieve las caracteristicas de los principios de ordenacion mas usuales. >. Sus programas son cortos y faciles de entender. Hay que recordar que tam- bbién los programas ocupan memori 8. Aunque los métodos sofisticados requieren menos operaciones, éstas nor- malmente son mas complejas en detalle; consecuentemente 10s métodos directos son mas rapidos para m suficientemente pequefio, aunque no deben usarse para valores grandes de 1. Los métodos de ordenacién in situ, pueden clasificarse en tres categorias prin- ciples de acuerdo con el método de base que utilizan 1. Ordenacién por insercion, 2. Ordenacién por seleccion. \. Ordenaei6n por intercambie. sto tres prineipioy bisicas vein objet ele examen y coniparacion en lo que sigue. ORDENACION DE ARRAYS 65 Los programas operan sobre la variable a, cuyos componentes se ordenarin in situ, y se referirin a los tipos de datos item (2.2) indice, definidos de la forma “5 = . * type indice ~ 0 var a: array [1 .. of item 23) 2.24. Ordenacion por insercién directa Este método se usa generalmente por los jugadores de cartas. Los items (cartas) estén dividides conceptualmente en una secuencia destino ai, -.-.ai-1 y tna secuencia origen a, ... , d,. En cada paso, empezando con i = 2, ¢ incre- mentando / de uno en uno, se tom el elemento i de la secuencia origen y se trans- Tiere a la secuencia destino insertindolo en el sitio apropiado. Cle iniinles 44 5p 1288? i 4% po 2 4 18 oO oF ie3 fas ss oss i=4 2 ba 5s 18 05 7 fas 2 246 55 S406 i=6 rae Ta ea oa ess tod] eT fet 6 IRA aS GT i=8 6 2 6b eR 4 ss Om Tabla 2.1. Proceso tpica de ordenacion por insercion directa EI proceso de ordenacién por insercién puede verse en un ejemplo de ocho niimeros elegidos aleatoriamente (tabla 2.1). El algoritmo es fori: = 2tondo begin x: = ali]; cinsertar xen el sitio adecuado en a... ap» end in el proceso de encontrar realmente el sitio adecuado conviene alternar com- Initaciones y movimientos, es decir, «dejar caer x, comparindolo con el item tumediato precedente aj: como consecuencia, se inserta x 0 se mueve aj a st «lvecha, y se continia con el inmediato por la izquierda, sewin el mismo proceso. we observa que hay dos condiciones distintas de terminacién de este proceso de sid Se encuentra un item aj cuya clave es menor que la de x. Se alcanza el extremo izquierdo de la secuencia destino,tORDENACION Este caso tipico de una repeticién con dos condiciones de terminacién permite uuplicar la conocida técnica del centinela. Se aplica facilmente situando como cen- tinicla uy ~ x (obsérvese que esto debe hacerse extendiendo el campo de variacion ddl indice de a de 0a n). El algoritmo completo se formula en el programa 2.1 Programa 2:1. Ordenacibn por inserein direct, procedure inserciondirecta: var i,j: indice; x: item; begin fori: = 2ton do begin x: = ali]; al0}: = xi72 while x .clave < a[j] clave do begin afj +1]: =al/jt=j— 1s end; aj +1) end cod “Anélisis de la insercién directa, El niimero de comparaciones entre claves, C, en el paso de caida ies, como maximo, i -1 y, como minimo, 1, y —suponiendo {que todas las permutaciones de las 7 claves tienen igual probabilidad— como media j/2. El nimero de movimientos M, (asignaciones de items) es C, + 2 (incluido el centinela). Por ello, los nimeros totales de comparaciones y movi- mientos son Com =n 1 Mais = 20 — 1) Coos = f(r +2 — 2) Meg = AGP + 9m — 10) 4) Cou = YO? $0) — 1 Mage = A? + 3 — 4) EI numero de comparaciones y movimientos minimo se presenta cuando los items estén ordenados de origen, el méximo se presenta si estén inicialmente ‘orden inverso. En este aspecto la ordenacién por insercién se comporta de Forma realmente natural. Es evidente que el algoritmo antes descrito es un proceso ‘estable de ordenacién: no modifica el orden de los items con Ia misma clave. EL algoritmo de insercién directa se mejora facilmente si se observa que la secuencia de destino a, ...,a-1 en la que debe insertarse ef nuevo articulo std ya ordenada. A tal fin puede utilizarse un método més répido para determinar Jn, Obviamente, este método es el de biisqueda binaria que cuencia de destino y continaa por biseecion a. El algoritmo modificado de insereién se 2.2. cf lugar de inser tarranca del elemento central de ist encontrar ef punto do in denomina insereidn binarla y aparece en el Progran ORDENACION DE ARRAYS 67 Programa 2.2. Ordenacién por inserién binria, procedure insercionbinaria; var i,j, iz, de, m: indice: x: item; begin , for i: = 2 to ndo begin x: = ali); iz: = Isde: =i 15 while iz < de do begin m de) div 2; ffx .clave < alm) .clave then de: =m —Lelse iz: =m +1 end; for j: =i ~ 1 downto iz do af j + 1) : = als aa | end Aniélisis dela insercién hinaria. Se encuentra la posicién de insercién cuando se verifica ay, “clave < x- clave < a, clave. Por tanto, el intervalo de busqueda final debe valer 1; esto representa dividir el intervalo formado por i elementos [logs i} veces. Por tanto, = $5 ote Eta sumatoria pede aproximarse por la integral [tear = allogx — 0) = nog — 0) +e es) siendo © = log ¢ = I/In 2 = 1.44269... El mimero de comparaciones es in pendiente del orden inicial de los items. Sin embargo, debido a que la divisién ‘uilizada en la etapa de biseccién trunca el resultado, el mimero real de compa- ruciones necesarias con i items puede aumentar en una sobre las esperadas. Esta circunstancia hace que las posiciones inferiores de insercién se localicen ligera- innente més rapido que las superiores. Esto favorece. por tanto, los casos en que los items estin inicialmente muy desordenados. En efecto, se necesita el minimo de comparaciones cuando Ios articulos estén en orden inverso inicialmente y el fiximo cuando ya estén ordenados. De aqui que éste sea un caso de comporta- miento antinarural de un algoritmo de ordenacién. C*nflogn loge + 0.5) Hesgriciadamente, lt mejor obtenida al utilizar ka bésqueda binaria s6lo se