• Author / Uploaded
• Frank Leny Ccapa Usca

Citation preview

Estructura de Datos y Algoritmos

Pág. 1

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN ESCUELA PROFESIONAL DE INGENIERÍA DE SISTEMAS

LABORATORIO 02:

TIPOS DE DATOS ABSTRACTOS Y GENERICIDAD I OBJETIVOS  

Conocer y utilizar la Genericidad en diferentes lenguajes de programación. Implementar TADs aplicando el concepto de Generecidad.

II TEMAS A TRATAR  

Genericidad Técnicas para la genericidad o Clases de tipos genéricos o Métodos genéricos

III MARCO TEÓRICO Genericidad El término Genericidad se refiere a una serie de técnicas que permitan escribir algoritmos o definir contenedores de forma que puedan aplicarse a un amplio rango de tipos de datos, a través de la abstracción del tipo de dato y/o la parametrización de estos tipos.

Técnicas para Genericidad Trataremos algunas técnicas utilizadas en Java y en C++, respecto a la definición y uso de contenedores y métodos que utilizan tipos de datos genéricos. a) Clases de tipos genéricos 

En Java: o

Clase universal Object public class Caja { private Object dato;

Karim Guevara Puente de la Vega

Lab. 02

Estructura de Datos y Algoritmos

Pág. 2

public Caja(){ super(); } public Object dame(){ return dato; } public void pon( Object x ){ dato = x; } }

Primer test: public class TestCaja { public static void main( String args[] ){ Caja c = new Caja(); c.pon( new Integer(46)); Integer n = (Integer) c.dame(); System.out.println(“Dato = ”+n); } }

Segundo test: ¿Hay errores de compilación? ¿y errores en tiempo de ejecución? public class TestCaja { public static void main( String args[] ){ Caja c = new Caja(); c.pon( “Hola”); Integer n = (Integer) c.dame(); System.out.println(“Dato = ”+n); } }

o

Clases Genéricas public class Caja { private T dato; public Caja(){ super(); } public T dame(){ return dato; } public void pon( T x ){ dato = x; } }

Primer test: Un contenedor de Integer public class TestCaja { public static void main( String args[] ){ Caja c = new Caja (); c.pon( new Integer(46)); Integer n = c.dame(); System.out.println(“Dato = ”+n); } }

Karim Guevara Puente de la Vega

Lab. 02

Estructura de Datos y Algoritmos

Pág. 3

Segundo test: Un contener de Strings. ¿Hay errores de compilación? ¿y errores en tiempo de ejecución? public class TestCaja { public static void main( String args[] ){ Caja c = new Caja (); c.pon( “Hola”); Integer n = c.dame(); System.out.println(“Dato = ”+n); } }

b) Métodos genéricos 

En Java public class Test { public static void main( String args[] ){ String[] v = {”Perez”,”Sanchez”,”Rodriguez”}; Integer[] w = {12,34,56}; System.out.println(existe(v,”Sanchez”)); System.out.println(existe(w,34)); System.out.println(existe(w,”Sanchez”)); // No da error } static boolean existe(T[] vec, T x) { for(T e : vec) { if( e.equals(x) ) { return(true); } } return(false); }

IV ACTIVIDADES Frecuenciador Dado un fichero de texto, se desea obtener la lista de pares (carácter, frecuencia) ordenada de mayor a menor por frecuencia, donde ésta indica el número de veces que aparece cada carácter en el texto. Se sabe que se va a pedir aplicar este problema a ficheros de texto que contengan otro tipo de datos (palabras, enteros, etc.) por lo que es esencial resolver el problema de la forma más genérica posible. El conjunto de pasos a seguir en la construcción del frecuenciador se muestra en la figura siguiente:

Karim Guevara Puente de la Vega

Lab. 02

Estructura de Datos y Algoritmos

Pág. 4

Solución: 

La clase parametrizada Cuenta representa a un par (elem, numero_frecuencia), donde T es el tipo de elem: public class Cuenta { private T elem; private int num; public Cuenta(T elem) { this.elem = elem; num = 1; } public T getElem() { return elem; } public int getNum() { return num; } public void incr() { num++; } }



El método genérico búsqueda recibe dos parámetros; una lista de objetos Cuenta (contenedor) y un elemento que será buscado en la lista. public static Cuenta busqueda(List l, T e) { for( Cuenta c : l ) { if( c.getElem().equals(e) ) { return c; } } return null; }



El método genérico recuento recibe una lista de elementos. Y devuelve otra lista de Cuentas, donde almacena para cada elemento su frecuencia. public static List recuento(List lis) { List res = new ArrayList(); for( T elem : lis ) { Cuenta c = busqueda( res, elem ); if( c == null ) { res.add( new Cuenta(elem) ); } else { c.incr(); } } return res; }



Lo siguiente es la implementación del algoritmo para contabilizar los caracteres de un texto System.out.print("Introduzca texto: "); // Usamos Scanner (expresiones regulares) para leer una linea Scanner sc = new Scanner(System.in); List lis = new ArrayList(); String lin = sc.nextLine(); for( i = 0; i < lin.lenght(); i++ ) { lis.add( lin.charAt(i) ); }

Karim Guevara Puente de la Vega

Lab. 02

Estructura de Datos y Algoritmos

Pág. 5

List lisc = recuento(lis); // Para usar sort debemos hacer que Cuenta implemente // la interfaz Comparable for( Cuenta c : lisc ) { System.out.println( c.getNum()+": "+c.getElem() ); } 

Luego de probar, si se requiere ordenar la lista de elementos, la clase Cuenta debe de implementar la interfaz Comparable de tal forma que se pueda establecer un criterio de ordenamiento entre las cuentas. Entonces, la clase Cuenta se deberá modificar como sigue: public class Cuenta implements Comparable { private T elem; private int num; public Cuenta(T elem) { this.elem = elem; num = 1; } public T getElem() { return elem; } public int getNum() { return num; } public void incr() { num++; } public int compareTo(Cuenta o) { if( o.getNum() == num ) { return 0;} else if( o.getNum() > num ) { return 1; } else { return -1; } } }



Además, debemos de incluir la siguiente línea de código para que se pueda ordenar la lista de cuentas. Collections.sort(lisc);

V EJERCICIOS 1. Implemente el algoritmo para probar el frecuenciador para contabilidad palabras de un texto, y numeros enteros de un texto. 2. Escribir un método genérico para intercambiar las posiciones de 2 diferentes elementos en un arreglo. 3. Escribir un método genérico para hallar el elemento máximo en el rango [inicio, fin) de una lista.

Karim Guevara Puente de la Vega

Lab. 02