InsertSort

Universidad de Talca
Facultad de Ingenier´
ıa
´
ıa
utalca.eps Escuela de Ingenier´ Civil en Computacion

´
´
Asociacion Hipotetica de
Criadores de Caballos

Fecha: Domingo, 25 de Septiembre 2011
Autores: Patricio Valderrama Aliaga
Francisco Herrera Ormazabal

´
1 INTRODUCCION

1.

Introducci´n
o

Los Diccionarios son tipos de estructuras con las cuales se pueden almacenardatos y acceder de forma eficiente a sus datos. Hay diferentes tipos de
´
´
Diccionario, como SkiptList, Arboles Binarios, Arboles AVL, HashTable, etc.
El tema principal de esta tarea tiene relaci´n con el almacenamiento y
o
r´pido acceso a datos de una Asociaci´n Hipot´tica de Criadores de Caballos,
a
o
e
para tener informaci´n de las entidades que existen en dicho lugar.
o
Nuestroprograma debe cumplir las siguientes consultas:
1. Almacenar los datos correspondientes del animal.
2. Determinar la genealog´ ascendente de un individuo espec´
ıa
ıfico.
3. Determinar la genealog´ descendente de un individuo espec´
ıa
ıfico.
4. Determinar la genealog´ descendente de un sexo espec´
ıa
ıfico para un
individuo dado.
5. Dado un par potro/yegua determinar si se les puedencruzar.
6. Registrar nacimientos de nuevos potrillos.
7. Registrar la muerte de ejemplares.
8. Registrar la venta de ejemplares a un destino fuera de la Asociaci´n.
o
9. Mostrar el stock actual de caballos de un haras espec´
ıfico.
10. Mostrar todos los ejemplares que tengan el mismo nombre.
11. Dado un potro o yegua de un tipo espec´
ıfico, determinar cu´les son los
a
posibles animales deltipo respectivo para la cruza.
12. Dado un caballo, indicar cuales de sus descendientes se pueden cruzar
con cu´les.
a

1

´
2 ANALISIS DEL PROBLEMA

2.

An´lisis del Problema
a

El problema principal se enfoca en realizar el almacenamiento de los datos
de una manera tal que las respuestas a las consultas dadas sean en tiempo
optimo. La primera indicaci´n que debemos tomar encuenta es que las estruc´
o
turas de los diccionarios que implementemos deben satisfacer el problema, y
entregar resultados correctos, ordenando y almacenando de manera que esto
se pueda realizar seg´n lo pedido.
u
Para la implementaci´n del ´rbol, no se desarroll´ un est´ndar completo
o
a
o
a
de arbol, sino que se incluy´ el seguimiento inmediato del racional a buscar,
´
o
lo quepermiti´ no adentrarse en la realizaci´n de nodos del ´rbol innecesarios
o
o
a
para nuestro recorrdio por este.
El programa ser´ probado en un men´ interactivo donde se mostrar´n
a
u
a
todas las opciones de consulta o almacenaje de informaci´n acerca de los
o
caballos que se encuentren en la base de datos del programa.
Para nuestra conveniencia y razonamiento de uso, hemos de utilizar comoestructura diccionario base HashTable, dicha estructura nos proporciona un
optimo acceso en relaci´n a las b´squedas e inserci´n de elementos. Debido
´
o
u
o
a la utilizaci´n de HashTable, fue necesaria la implementaci´n de listas que
o
o
en realidad son simplemente Caballos entrelazados por diferente orden. La
raz´n de esto radica en que utilizamos una HashTable para cada forma de
oordenamiento, de modo que para cada opci´n de los requerimientos, acceder
o
en tiempo optimo.
´
La principal raz´n de nuestro programa es el almacenamiento de Caballos,
o
por lo cual es necesario decir qu´ es y qu´ contiene un Caballo. Un Caballo
e
e
es una entidad que pertenece a la Asociaci´n, sus atributos son:
o
Nombre: Atributo de tipo String que representa el Nombre de un
Caballo.Hara: Atributo de tipo String que representa el Hara a la que pertenece
un Caballo.
Cie: Atributo de tipo Integer que representa la C´dula de Identidad
e
Equina de un Caballo.
Tipo: Atributo de tipo String que representa el tipo o labor que representa el Caballo, por ejemplo ’carrera’, ’exhibici´n’, ¸orralero”, etc.
o c
2

´
2 ANALISIS DEL PROBLEMA

Sexo: Atributo de tipo String...