Entrega Numero 3. semana 7 estructura de datos PDF

Preview

Summary

MODELO ESTRUCTURAS DE DATOSGRUPO N°1.Ejercicios de implementación JAVA.Presentado por:DIAZ CARVAJAL ANA MILENA COD: 812011645PULIDO ACHAGUA JHON ALEXANDER COD: 1911023440VÉLEZ CARLOS ANDRÉS COD: 1911020943ESTRUCTURAS DE DATOSPOLITÉCNICO GRANCOLOMBIANO.BOGOTÁ D2020GRUPO N°Trabajo colaborativo semana ...

Description

MODELO ESTRUCTURAS DE DATOS GRUPO N°1.

Ejercicios de implementación JAVA.

Presentado por: DIAZ CARVAJAL ANA MILENA

COD: 812011645

PULIDO ACHAGUA JHON ALEXANDER

COD: 1911023440

VÉLEZ CARLOS ANDRÉS

COD: 1911020943

ESTRUCTURAS DE DATOS POLITÉCNICO GRANCOLOMBIANO. BOGOTÁ D.C 2020

GRUPO N°1

Trabajo colaborativo semana 7.

Docente a cargo: RICARDO GOMEZ

POLITÉCNICO GRANCOLOMBIANO. Ingeniería Diseño e Innovación. 2020.

Entrega previa N°3. Semana N°7.

1. Implemente un método que, dado un valor, retorne cuántos elementos son mayores que dicho valor dentro de un árbol binario ordenado. Calcule la complejidad temporal del método. Desarrollo public class ArbolBinarioOrdenado { class Nodo{ int info; Nodo izq,der; } private Nodo raiz; public boolean existe(int x) { Nodo reco=raiz; while (reco!=null) { if (x==reco.info) { return true; } else { if (x>reco.info) { reco=reco.der; } else { reco=reco.izq; } } } return false; } public void insertar(int x) { if(!existe(x)) { Nodo nuevo = new Nodo(); nuevo.info=x; if (raiz==null) { raiz=nuevo; } else { Nodo anterior=null; Nodo reco=raiz; while (reco!=null) {

anterior=reco; if (x>reco.info) { reco=reco.der; } else { reco=reco.izq; } } if (x>anterior.info) { anterior.der=nuevo; } else { anterior.izq=nuevo; } } } } private void recorrer(Nodo reco) { if (reco!=null) { recorrer(reco.izq); System.out.print(reco.info+"-"); recorrer(reco.der); } } public void recorrer() { recorrer(raiz); System.out.println(); } public void mayor() { if (raiz!=null) { Nodo reco=raiz; while (reco.der!=null) { reco=reco.der; } System.out.println("Numero mayor:"+reco.info); } }

public static void main(String[] args) { ArbolBinarioOrdenado arbol = new ArbolBinarioOrdenado();

arbol.insertar(10); arbol.insertar(20); arbol.insertar(30); arbol.insertar(40); arbol.insertar(50); arbol.insertar(60); arbol.insertar(70); arbol.insertar(80); arbol.insertar(90); arbol.insertar(100); arbol.insertar(200); arbol.insertar(300); arbol.insertar(400); arbol.insertar(500); arbol.recorrer(); arbol.mayor(); } }

2. Investigue en qué consiste cada una de las siguientes dos estrategias de resolución de colisiones y para cada una de ellas proponga un ejemplo:

Desarrollo. Una colisión es la presencia de dos objetos diferentes o más reciben el mismo índice Hash para el ingreso en la tabla. Es decir, la función hash obtiene una misma dirección para dos claves diferentes. Cabe anotar que para el programador se sugiere tener presente que la elección de un método adecuado para resolver colisiones es tan importante como la elección de una buena función Hash. Existen métodos para la resolución de colisiones: A. Encadenamiento. Este método consiste en que cada elemento contenga un enlace a una lista para que de esta manera sea más fácil almacenar los valores colisionados este método; es un método eficiente debido al dinamismo. Consiste en que cada elemento del arreglo tenga un apuntador a una lista ligada, la cual se ira generando e ira almacenando los valores colisionados a medida que se requiera. Objetos

A

B X

Y

Z

Tabla Hash con enlace por vectores.

La implementación de la estructura de datos Tabla de Hash que usa el método de encadenamiento para la resolución de colisiones donde las claves son de tipo entero, y el dato a almacenar que está asociada a cada clave, es un elemento de tipo Sting. El encadenamiento debe ser llevado a cabo mediante una lista doblemente enlazada. Las ventajas de esta tabla son muy sencillas de realizar, la tabla nunca se llena, se puede usar cuando no sabemos cuántos elementos se tienen. Las desventajas se relacionan con el desempeño, dado que se encuentra que no está bueno por sus listas ligadas, se desperdicia memoria si hay celdas que no se usan, si la cadena se hace muy larga el tiempo de acceso se vuelve O(n). Ejemplo: Realizamos la función hash que mapea una llave a un entero que puede ser usado como índice para acceder a la tabla h(x)= x % n Vamos a insertar los siguientes elementos llave

índice 0 1 2 3 4 5 6 7 8 9

valor

llave

modulo h(x) x % 10

tamaño

233 h(57) = 7 56 57,277

h(233) = 3 h(56) = 6 h(277)= 7

aquí hay una colisión y se lleva la parte del encadenamiento

Tamaño

B. Sondeo lineal. Sondeo lineal es un componente de direccionamiento abierto con esquemas para el uso de una tabla Hash con el fin de dar solución a un problema. Todos los elementos se guardan en la misma tabla, se recomienda que la tabla sea mayor a la cantidad de elementos a insertar, por medio de la función Hash obtenemos varios índices donde colocar el elemento en caso de tener colisión, cuando tenemos un índice que ya esta ocupado en la tabla se procede a la siguiente posición y si este vacío entonces se usa, pero si está ocupado el apuntador se dirige al siguiente hasta que encuentra una celda de nuestra tabla vacía y colocar el elemento. Realizamos la función Hash con intentos hi(x) = (h(x)+i) % n. Donde X es la llave que ubica el índice que queremos obtener y esto es igual a nuestra función más i, que hace referencia al número de intentos y luego módulo de n que es la cantidad de celdas. Es necesario tener en cuenta que las celdas van a tener estados vacío, ocupado y borrado y esto permitir de manera correcta las búsquedas dentro de las tablas haciendo uso del direccionamiento abierto.

Ejemplo Vamos a insertar los siguientes elementos llave

h(x)

índice 0 1 2 3 4 5 6 7 8 9 10

valor 23

=x

#intentos

modulo

tamaño

hi(23) = (23+0) % 11 = 1 hi(51) = (51+0) % 11 = 7 hi(40) = (40+0) % 11 = 7 hi(40) = (40+1) % 11 = 8

51 40 62

hi(62) = (62+0) % 11 = 7 hi(62) = (62+1) % 11 = 8 hi(62) = (62+2) % 11 = 9

Tamaño

3. Una compañía logística tiene actualmente 5040 clientes, y espera crecer hasta los 100000 clientes en los próximos cinco años. Si se desea guardar el nombre de cada cliente dentro de una tabla hash, A. ¿Cuál sería un tamaño adecuado para la tabla? B. Proponga una función hash para la tabla.

Desarrollo: La Tabla Hash es una estructura de datos que pretende la inserción, búsqueda y borrado de elementos en tiempo contante 0(1). Por tanto, La función Hash(x) calcula el tiempo contante y la distribución uniforme de los objetos a lo largo de la tabla.

Objetos.

Tabla Hash.

A

B X Y

Z

Una Tabla Hash debe ser considerada con tamaño suficiente para evitar el numero de colisiones. A. ¿Cuál sería un tamaño adecuado para la tabla? Desarrollo: Tamaño n: 100000.

(n-1)

Por lo tanto, n es el valor designado o tamaño, es la cantidad de elementos con capacidad para ser almacenados en la tabla hash, por tanto, es el valor máximo. B. Proponga una función hash para la tabla. Desarrollo. F(x) = |x| % t x = 100000 t = 32 (letras del alfabeto) F (100000) = |100000|%32 F(x) = 3125 3125 corresponde a la dirección.

Referencias. -

La tabla de Hash. Moltó Martínez Germán. Introducción a la Estructura de Datos Tabla Hash. Principales características y operaciones más significativas. Universidad Politécnica de Valencia. 21 nov. 2011. Disponible en: https://www.youtube.com/watch?v=WnLdu8OHA3Q

-

Hashing: Técnicas y Hash para la protección de datos. Sánchez Samuel. Universidad

Tecnológica

de

Panamá.

http://www.laccei.org/LACCEI2018-Lima/student_Papers/SP96.pdf

-

Material académico de la universidad Politécnico Grancolombiano.

Disponible

en:...