PDF de programación - Introducción a las Estructuras de Datos y Archivos

UUNNIIVVEERRSSIIDDAADD TTEECCNNOOLLÓÓGGIICCAA NNAACCIIOONNAALL

FFAACCUULLTTAADD RREEGGIIOONNAALL MMEENNDDOOZZAA



I

Ing. Santiago C. PÉREZ





INDICE


TEMA 2: Estructuras lineales de Datos

INTRODUCCIÓN ......................................................................................................

TEMA 1: Modelos matemáticos y representaciones de computadora.

1


2
Estructuras de Datos y Archivos.......................................................................
Modelos Matemáticos.......................................................................................
3
Representaciones.............................................................................................. 4
5
Conceptos de teoría de grafos .........................................................................
Ejercicios ..........................................................................................................
8


9
Propiedades formales. Relaciones lineales. Listas. .........................................
Tipos de listas ................................................................................................... 9
Representaciones secuencial y linkeada ......................................................... 10
Pila ................................................................................................................... 10
Cola .................................................................................................................. 12
Asignación dinámica de memoria ..................................................................... 14
Doble cola ......................................................................................................... 15
Lista irrestricta ................................................................................................. 16
Ejercicios .......................................................................................................... 18


Propiedades formales ....................................................................................... 20
Árboles binarios. Representaciones secuencial y linkeada .............................
21
Barridos de árboles binarios ............................................................................. 23
Tipos de árboles binarios ................................................................................. 25
Árboles N-arios. Transformada de Knuth ......................................................... 26
Ejercicios .......................................................................................................... 28


Tablas de símbolos. Costos de acceso............................................................. 29
Árboles de búsqueda. Árboles balanceados. Árboles AVL .............................. 30
Árboles de búsqueda óptimos .......................................................................... 37
Hashing. Funciones de Transformación. Colisiones ........................................ 38


TEMA 3: Árboles


TEMA 4: Acceso de Datos

I

INDICE



Árboles de búsqueda n-arios. Árbol B .............................................................. 44
Ejercicios .......................................................................................................... 47


Listado de programas fuentes disponibles ................................................................ 49


Bibliografía ................................................................................................................ 50



II

INTRODUCCIÓN



La recapitulación de bibliografía sobre el tema, ha permitido la generación del
presente apunte, cuyo objeto fundamental es poner a disposición de cátedras con
contenidos afines, docentes, estudiantes e interesados en general este material,
como una referencia adicional, aunque breve, conceptual e informativa sobre el
particular.


La lectura del texto requiere conocimientos de computación y programación, a

fin de adquirir nociones fundamentales de Estructuras de Datos y Archivos.


Se proponen ejercicios a resolver, sencillos, aunque útiles para consolidar los
conceptos adquiridos. Además, se deja a disposición de los lectores programas
fuente directamente relacionados con los contenidos. Los mismos estarán a
disposición como material complementario del presente texto.


El que suscribe estaría muy agradecido de aquellos lectores, a quienes el
mismo haya resultado de utilidad, y que puedan aportar una critica o información
para su mejora.


Finalmente, agradezco la colaboración de los Ayudantes de Segunda, Carlos
Campos y Laura Noussan Lettry, en la revisión de los contenidos y el pasaje a
formato electrónico.



Mendoza, Junio de 2004.



Ing. Santiago Pérez
Docente Cátedra Gestión de Datos
Email: [email protected]



1

TEMA 1: Modelos matemáticos y representaciones de computadora.

Estructuras de Datos y Archivos.


Comúnmente se define a los datos como un conjunto de hechos, de números,
o de símbolos que usan y manipulan los programas de computadora. Una estructura
de datos o archivos puede definirse como aquellos datos que denotan un conjunto
de hechos, que pueden servir como operandos a un programa de computadora y
cuya estructura es la manifestación de las relaciones (si las hay) entre elementos
individuales de aquel conjunto. Por ejemplo, un conjunto de datos acerca de una
empresa puede contener los nombres de todos los empleados, y los cargos de todos
los niveles jerárquicos.


Así, podemos considerar la relación entre los niveles jerárquicos, es decir,
que niveles jerárquicos son superiores a otros. Al resultado, frecuentemente se le
llama estructura de organización de la empresa (Figura 1).



El estudio de estructuras de datos y archivos aproxima al interesado a
encontrar resultados que son también aplicables a la teoría de sistemas operativos,
de computación, y de lenguajes de programación, además de a las estructuras de
datos y archivos en sí mismas.


Este estudio comprende dos objetivos complementarios. El primero es
identificar y desarrollar modelos abstractos y operaciones útiles sobre las estructuras
de datos, y determinar que clases de problemas pueden resolverse con ellos. El
segundo objetivo es el de determinar las representaciones para aquellos modelos
abstractos e implementar las operaciones sobre ellos con tipos de datos concretos y
conocidos.


El primero de estos dos objetivos considera un tipo de datos superior, como
una herramienta que puede ser utilizada para resolver nuevos problemas o mejorar
otros; mientras que el segundo considera la implementación de dichos tipos de datos
como un problema para ser resuelto utilizando tipos de datos ya existentes.


2

Por otro lado, deberemos distinguir que la teoría y las técnicas de las

estructuras de datos y de archivos difieren entre sí. El estudio de las estructuras de
archivos es, en esencia, la aplicación de las técnicas de estructuras de datos a
problemas especiales asociados con el almacenamiento y la recuperación de datos
en dispositivos de almacenamiento secundario.


Normalmente el estudio de las estructura de datos supone que éstos se
encuentran almacenados en memoria RAM. Un archivo constituido por decenas o
más de millones de registros es demasiado grande para cargarlo en memoria RAM a
fin de efectuar operaciones sobre él. Dichas operaciones implican el uso de
almacenamiento secundario, y por lo tanto, ya no se está en un ambiente de acceso
aleatorio. Ahora, el costo de recuperar algunas partes de la información es
desproporcionadamente mayor que el costo de recuperar otras. Un enfoque para las
operaciones que se oriente al diseño de estructuras de archivos reconocería esto.
Así minimizaría el número de acceso al disco y además intentaría adecuar el patrón
de accedo de modo tal que, cuando se necesite otra parte de la información, ésta se
localice donde el acceso resulte relativamente barato.

Por lo expuesto, salvando las dimensiones de los datos involucrados, que nos

forzaría a reconocer las técnicas de estructuras de datos o de archivos, para su
operación, usaremos el término estructura de datos para ambos casos.


Una consideración importante a la hora de la imp