• Author / Uploaded
• maria isabel zuñiga castañeda

Citation preview

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

TECNOLOGICO DE ESTUDIOS SUPERIORES DE ECATEPEC

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

María Isabel Zúñiga Castañeda Grupo:15301 ESTRUCTURA DE DATOS

Fecha de Trabajo: 05/03/2018

0

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

INTRODUCCION: Este trabajo está basado en dejar una explicación de lo que son los tipos de datos abstractos y unos ejemplos que se implementan con arreglos la verdad es que este tema espero y al leerlo les deje una enseñanza y les sirva de mucho ya que está muy completo y muy eficaz a mi parecer espero y les sea de su agrado y les sirva de mucho.

1

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

OBJETIVO: Mi objetivo es aprender un poco más de este tema de los tipos abstractos ya que no estaba muy entendible y así mismo ir practicando sobre los temitas que me hacían falta y dejarles este archivo a personas que como yo necesita un poco de ayuda para comprender el tema.

2

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

TIPOS DE DATOS ABSTRACTOS

Abstracción: consiste en ignorar los detalles de la manera particular en que está hecha una cosa, quedándonos solamente con su visión general. Tipo de Dato Abstracto (TDA) se define como un conjunto de valores que pueden tomar los datos de ese tipo, junto a las operaciones que los manipulan. Un TDA es un modelo matemático de estructuras de datos que especifican los tipos de datos almacenados, las operaciones definidas sobre esos datos y los tipos de parámetros de esas operaciones. TAD = Valores (tipo de dato) + operaciones Un TDA define lo que cada operación debe hacer, más no como la debe hacer. En un lenguaje de programación como Java un TDA puede ser expresado como una interface, que es una simple lista de declaraciones de métodos. Un TDA es materializado por una estructura de datos concreta, en Java, es modelada por una clase. Una clase define los datos que serán almacenados y las operaciones soportadas por los objetos que son instancia de la clase. Al contrario de las interfaces, las clases especifican como las operaciones son ejecutadas (implementación). Ejemplos de tipos de datos abstractos son las Listas, Pilas, Colas, etc.

ARREGLOS LINEALES Un arreglo se usa para agrupar, almacenar y organizar datos de un mismo tipo. En un arreglo cada valor se almacena en una posición numerada específica dentro del arreglo. El número correspondiente a cada posición se conoce como índice.

3

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

La estructura de un arreglo es:

Normalmente el primer objeto del arreglo tiene el índice 0, aunque esto varía de lenguaje en lenguaje. Declaración: Como se sabe, hay 2 tipos de datos en Java: primitivos (como int y double) y objetos. En muchos lenguajes de programación (aún en Orientados a Objetos como C++) los arreglos son tipos primitivos, pero en Java son tratados como objetos. Por consiguiente, se debe utilizar el operador new para crear un arreglo:

int miArreglo[]; miArreglo = new int[100];

// define la referencia a un arreglo // crea el arreglo y establece miArreglo // como referencia a él

O el equivalente a hacerlo dentro de una misma sentencia int miArreglo[] = new int[100];

El operador [] es la señal para el compilador que estamos declarando un arreglo (objeto) y no una variable ordinaria. Dado que un arreglo es un objeto, el nombre – miArreglo-, en el ejemplo anterior- es una referencia a un arreglo y no el nombre

4

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

del arreglo como tal. El arreglo es almacenado en una dirección de memoria x, y miArreglo almacena solo esa dirección de memoria. Los arreglos tienen el método length, el cual se utiliza para encontrar el tamaño de un arreglo: int tamaño = miArreglo.length; // arroja el tamaño del arreglo Para acceder a los elementos de un arreglo se debe utilizar los corchetes, muy similar a otros lenguajes de programación: temp = miArreglo[4]; // guarda en temp el valor del cajón 4 del arreglo miArreglo[8] = 50; // almacena en el cajon 8 del arreglo el valor 50 Es preciso recordar que en Java, como en C y C++, el primer elemento del arreglo es el 0. Luego entonces, los índices de un arreglo de 10 elementos van del 0 al 9. (S/A)

ESTOS SON UNOS EJEMPLOS :

TDA lista

Una lista se define como una serie de N elementos E1, E2, ..., EN, ordenados de manera consecutiva, es decir, el elemento Ek (que se denomina elemento k-ésimo) es previo al elemento Ek+1. Si la lista contiene 0 elementos se denomina como lista vacía. Las operaciones que se pueden realizar en la lista son: insertar un elemento en la posición k, borrar el k-ésimo elemento, buscar un elemento dentro de la lista y preguntar si la lista esta vacía. Una manera simple de implementar una lista es utilizando un arreglo. Sin embargo, las operaciones de inserción y borrado de elementos en arreglos son ineficientes, puesto que para insertar un elemento en la parte media del arreglo es necesario mover todos los elementos que se encuentren delante de él, para hacer espacio, y

5

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

al borrar un elemento es necesario mover todos los elementos para ocupar el espacio desocupado. Una implementación más eficiente del TDA se logra utilizando listas enlazadas. A continuación se presenta una implementación en Java del TDA utilizando listas enlazadas y sus operaciones asociadas:     

estaVacia(): devuelve verdadero si la lista esta vacía, falso en caso contrario. insertar(x, k): inserta el elemento x en la k-ésima posición de la lista. buscar(x): devuelve la posición en la lista del elemento x. buscarK(k): devuelve el k-ésimo elemento de la lista. eliminar(x): elimina de la lista el elemento x.

En la implementación con listas enlazadas es necesario tener en cuenta algunos detalles importantes: si solamente se dispone de la referencia al primer elemento, el añadir o remover en la primera posición es un caso especial, puesto que la referencia a la lista enlazada debe modificarse según la operación realizada. Además, para eliminar un elemento en particular es necesario conocer el elemento que lo antecede, y en este caso, ¿qué pasa con el primer elemento, que no tiene un predecesor? Para solucionar estos inconvenientes se utiliza la implementación de lista enlazada con nodo cabecera. Con esto, todos los elementos de la lista tendrán un elemento previo, puesto que el previo del primer elemento es la cabecera. Una lista vacía corresponde, en este caso, a una cabecera cuya referencia siguiente es null.

Los archivos NodoLista.java, IteradorLista.java y Lista.java contienen una implementación completa del TDA lista. La clase NodoLista implementa los nodos de la lista enlazada, la clase Lista implementa las operaciones de la lista propiamente tal, y la clase IteradorLista implementa objetos que permiten recorrer la lista y posee la siguiente interfaz:

6

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

 

avanzar(): avanza el iterador al siguiente nodo de la lista. obtener(): retorna el elemento del nodo en donde se encuentra el iterador.

Costo de las operaciones en tiempo:  

Insertar/eliminar elemento en k-ésima posición: O(k) (¿Se puede hacer en O(1)?). Buscar elemento x: O(N) (promedio).

Arreglos Unidimensionales En este tipo de arreglo se hace uso de un índice solamente para hacer referencia a una posición particular del arreglo. Ejemplos de declaraciones de arreglos unidimensionales: 1. double [ ] vector; 2. double vector [ ]; Ambas formas anteriores son equivalentes. 3. String [ ] nombres; 4. boolean [ ] valores_booleanos; 5. int[ ] enteros; Para asignarle posiciones de memoria principal a un arreglo se usa el operador new. Se puede usar un sola oración para declarar y asignarle memoria a un arreglo. Ejemplos: 1. vector = new double [12]; (Se crea un arreglo de tamaño 12 y cada posición se inicializa a 0.) 2. double [ ] vector = new double [12]; (Equivalente al ejemplo 1.) 3. String[ ] nombre = new String[100]; (El identificador de la primera posición de un arreglo unidimensional tiene índice 0.) 4. boolean[ ] valor_booleano = new boolean[4]; (Cada variable booleana se inicializa con el valor false.) Copyright © 2008 CARIMOBITS 1 5. int[ ] entero = new int[10]; (Los identificadores de las posiciones son entero[0],

7

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

entero[1], ..., entero[9].) En los ejemplols 1 y 2, ambas formas son equivalentes y se crea un arreglo con 12 posiciones cuyos identificadores respectivos tienen subíndices del 0 al 11. Notas: 1. Cuando se crea un arreglo, cada una de sus posiciones será inicializada con el valor por defecto (default) del tipo de dato u objeto. Por ejemplo, si el arreglo es de tipo boolean, todas las posiciones del arreglo serán inicializadas con el valor false (ya que este es valor por defecto del tipo de datos boolean ). Por otro lado, si el arreglo fuese de un tipo no primitivo o elemental, el valor que contendrá cada posición será null. 2. Se le puede asignar valores a un arreglo al momento de declararlo o luego, cuando sea necesario. Ejemplos:

1. int[ ] arreglo = new int[4]; 2. int[ ] arreglo = {100,200,302,400}; Nota: La constante length está asociada con un arreglo y su valor es el tamaño del arreglo. Ejemplo: for (int i = 0; i < vector.length; i = i + 1;) { ...//cuerpo del ciclo. } (S/A)

8

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

ARRAYS (ARREGLOS) MULTIDIMENSIONALES

Vamos a realizar un repaso sobre conocimientos que debemos tener relativos a arrays multidimensionales. En Java es posible crear arrays con más de una dimensión, pasando de la idea de lista, vector o matriz de una sola fila a la idea de matriz de m x n elementos, estructuras tridimensionales, tetradimensionales, etc. La sintaxis será:

Tipo_de_variable[ ][ ]… [ ] Nombre_del_array = new Tipo_de_variable[dimensión1][dimensión2]…[dimensiónN];

También podemos alternativamente usar esta declaración:

Tipo_de_variable[ ][ ] … [ ] Nombre_del_array; Nombre_del_array = new Tipo_de_variable[dimensión1][dimensión2]…[dimensiónN];

El tipo de variable puede ser cualquiera de los admitidos por Java y que ya ha sido explicado. Ejemplos de declaración e inicialización con valores por defecto de arrays, usando los distintos tipos de variables Java, serían:

9

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

o byte[][] edad = new byte[4][3]; o short ][] edad = new short[4][3]; o int[][] edad = new int[4][3]; o long[][] edad = new long[4][3]; o float[][] estatura = new float[3][2]; o double[][] estatura = new double[3][2]; o boolean[][] estado = new boolean[5][4]; o char[][] sexo = new char[2][1]; o String[][] nombre = new String[2][1];

a declaración de una matriz tradicional de m x n elementos podría ser: /* Ejemplo declaración - aprenderaprogramar.com */ int[][] matriz = new int[3][2]; O alternativamente int[][] matriz; matriz = new int[3][2]; MATRICES Una matriz es un array bidimensional (2 dimensiones, filas y columnas) Cómo algunos ejemplos de matrices podríamos tener:

10

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

Una matriz debe tener un nombre (sin espacios) Por ejemplo

Cada elemento de una matriz tiene una posición dado por la fila y columna, las mismas que empieza en cero

11

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

Entonces podemos ver que cada elemento de una matriz tiene una posición (dado por la fila y columna) y un dato Por ejemplo: M[0][1] tiene el dato 7 M[3][2] error porque no existe la fila 3 M[2][0] tiene el dato 2 M[2][3] tiene el dato 8 Cada elemento del vector puede ser manejado como cualquier variable. Por ejemplo: int A = M[0][1] + M[1][1]; // A = 7 + 6 = 13 int B = 2 + M[1][2]; // B = 2 + 4 = 6 M[0][0] = A + B; // M[0][0] = 13 + 6 = 19 (htt) EJEMPLO: TDA pila Una pila (stack o pushdown en inglés) es una lista de elementos de la cual sólo se puede extraer el último elemento insertado. La posición en donde se encuentra dicho elemento se denomina tope de la pila. También se conoce a las pilas como listas LIFO (LAST IN - FIRST OUT: el último que entra es el primero que sale).

12

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

La interfaz de este TDA provee las siguientes operaciones:    

apilar(x): inserta el elemento x en el tope de la pila (push en inglés). desapilar(): retorna el elemento que se encuentre en el tope de la pila y lo elimina de ésta (pop en inglés). tope(): retorna el elemento que se encuentre en el tope de la pila, pero sin eliminarlo de ésta (top en inglés). estaVacia(): retorna verdadero si la pila no contiene elementos, falso en caso contrario (isEmpty en inglés).

Nota: algunos autores definen desapilar como sacar el elemento del tope de la pila sin retornarlo. Implementación del TDA pila

A continuación se muestran dos maneras de implementar una pila: utilizando un arreglo y utilizando una lista enlazada. En ambos casos el costo de las operaciones es de O(1). Implementación utilizando arreglos

Para implementar una pila utilizando un arreglo, basta con definir el arreglo del tipo de dato que se almacenará en la pila. Una variable de instancia indicará la posición del tope de la pila, lo cual permitirá realizar las operaciones de inserción y borrado, y también permitirá saber si la pila esta vacía, definiendo que dicha variable vale 1 cuando no hay elementos en el arreglo. class PilaArreglo { private Object[] arreglo; private int tope; private int MAX_ELEM=100; // maximo numero de elementos en la pila public PilaArreglo() { arreglo=new Object[MAX_ELEM]; tope=-1; // inicialmente la pila esta vacía }

13

EL USO DE TIPOS DE DATOS ABSTRACTOS CON ARREGLOS

public void apilar(Object x) { if (tope+1