Clasificación de las estructuras de datos.pptx

En esta presentación se aborde la clasificación de la estructura de datos

1. Clasificación de las estructuras de datos

2. Fuente: Facomsys

3. ¿Qué son las estructuras de datos? S on colecciones de elementos de datos relacionados. Los objetos arreglo son estructuras de datos que consisten en elementos de datos relacionados, del mismo tipo. Los arreglos facilitan el procesamiento de grupos de valores relacionados. Los arreglos conservan la misma longitud una vez creados

4. Estáticas: Arreglos ¿Qué es un arreglo? Un arreglo es una estructura de datos utilizada para almacenar datos del mismo tipo. Los arreglos almacenan sus elementos en ubicaciones de memoria contiguas. En Java, los arreglos son objetos.

5. Un arreglo es un grupo de variables (llamadas elementos o componentes) que contienen valores del mismo tipo. Los arreglos son objetos , por lo que se consideran como tipos de referencia. Como veremos pronto, lo que consideramos por lo general como un arreglo es en realidad una referencia a un objeto arreglo en memoria. Los elementos de un arreglo pueden ser tipos primitivos o de referencia . Para hacer referencia a un elemento específico en un arreglo, debemos especificar el nombre de la referencia al arreglo y el número de la posición del elemento dentro del mismo. El número de la posición del elemento se conoce formalmente como el índice o subíndice del elemento

6. S implifiquemos Un arreglo es un conjunto de elementos asociados a un identificador con un tipo de dato, donde cada uno de los elementos puede ser direccionado a través de un elemento llamado índice

7. Representación de arreglos logicos En la figura a continuacion se muestra una representación lógica de un arreglo de enteros, llamado c. Este arreglo contiene 12 elementos . Un programa puede hacer referencia a cualquiera de estos elementos mediante una expresión de acceso a un arreglo que contiene el nombre del arreglo, seguido por el índice del elemento específico encerrado entre corchetes ([]) . El primer elemento en cualquier arreglo tiene el índice cero , y algunas veces se le denomina elemento cero. Por lo tanto, los elementos del arreglo c son c[0], c[1], c[2], y así en lo sucesivo. El mayor índice en el arreglo c es 11: 1 menos que 12 , el número de elementos en el arreglo.

8. Índices y elementos Un índice debe ser un entero no negativo . Un programa puede utilizar una expresión como índice . Por ejemplo, si suponemos que la variable a es 5 y que b es 6, entonces la instrucción: c[a + b] += 2; suma 2 al elemento c[11] del arreglo. El nombre de un arreglo con subíndice es una expresión de acceso al arreglo , la cual puede utilizarse en el lado izquierdo de una asignación, para colocar un nuevo valor en un elemento del arreglo. C[8]=34; Psst , por aquí: Un índice debe ser un valor int , o un valor de un tipo que pueda convertirse a int ; por ejemplo, byte, short o char , pero no long . De lo contrario, ocurre un error de compilación

9. ¿Y que podemos hacer con el contenido de los arreglos? Vamos a examinar con más detalle el arreglo c de la figura vista antes. El nombre del arreglo es c . Cada objeto arreglo conoce su propia longitud y mantiene esta información en una variable de instancia length . La expresión c.length devuelve la longitud del arreglo c . Aun cuando la variable de instancia length de un arreglo es public , no puede cambiarse, ya que es una variable final. La manera en que se hace referencia a los 12 elementos de este arreglo es: c[0], c[1], c[2], …, c[11].

10. El valor de c[0] es -45, el valor de c[1] es 6, el de c[2] es 0, el de c[7] es 62 y el de c[11] es 78. Para calcular la suma de los valores contenidos en los primeros tres elementos del arreglo c y almacenar el resultado en la variable suma, escribiríamos lo siguiente: suma = c[0] + c[1] + c[2]; Para dividir el valor de c[6] entre 2 y asignar el resultado a la variable x, escribiríamos lo siguiente: x = c[6] / 2; Y así con otras operaciones matemáticas

11. ¿Cómo se declara un arreglo? Los objetos arreglo ocupan espacio en memoria. Al igual que los demás objetos, los arreglos se crean con la palabra clave new . Para crear un objeto arreglo, debemos especificar el tipo de cada elemento y el número de elementos que se requieren para el arreglo , como parte de una expresión para crear un arreglo que utiliza la palabra clave new. Dicha expresión devuelve una referencia que puede almacenarse en una variable tipo arreglo. La siguiente declaración y expresión de creación de arreglos crea un objeto arreglo, que contiene 12 elementos int y almacena la referencia del arreglo en la variable c : int [] c = new int [12]; Psst por aquí: Esta expresión puede usarse para crear el arreglo que se mostro con anterioridad en la figura

12. Existe otra forma de declarar una arreglo int [] c; c = new int [12]; Al crear un arreglo, cada uno de sus elementos recibe un valor predeterminado (cero para los elementos numéricos de tipos primitivos , false para los elementos boolean y null para las referencias) .

13. En la declaración, los corchetes que van después del tipo indican que c es una variable que hará referencia a un arreglo (es decir, la variable almacenará una referencia a un arreglo). En la instrucción de asignación, la variable arreglo c recibe la referencia a un nuevo objeto arreglo de 12 elementos int . Un programa puede crear varios arreglos en una sola declaración. La siguiente declaración reserva 100 elementos para b y 27 para x: String[] b = new String[100], x = new String[27]; Psst , por aquí; En la declaración de un arreglo, si se especifica el número de elementos en los corchetes de la declaración (por ejemplo, int [12] c;), se produce un error de sintaxis.

14. Cuando el tipo del arreglo y los corchetes se combinan al principio de la declaración, todos los identificadores en ésta son variables tipo arreglo. En este caso, las variables b y x hacen referencia a arreglos String . Por cuestión de legibilidad, es preferible declarar sólo una variable en cada declaración. La declaración anterior es equivalente a: String [] b = new String [100]; String [] x = new String [27]; Cuando sólo se declara una variable en cada declaración, los corchetes se pueden colocar después del tipo o del nombre de la variable del arreglo, como en: String b[] = new String [100]; String x[] = new String [27]; Psst , por aquí: Un programa puede declarar arreglos de cualquier tipo cada elemento de un arreglo int es un valor int , y cada elemento de un arreglo String es una referencia a un objeto String .

15. Clasificación de los arreglos: Arreglo Unidimensional: Nos referimos a un vector de datos Arreglo Bidimensional: Nos referimos a una estructura de doble entrada, es decir que tiene filas y columnas Arreglo Tridimensional: Extendemos una dimensión mas, lo que se traduce en tener filas, columnas y profundad Arreglo Multidimensional: Nos referimos a que cada dimensión, puede tener un tamaño diferente a las demás dimensiones

16. Arreglo como estructura estática La particularidad que un arreglo como una estructura estática, viene desde el momento en que el arreglo se define en tiempo de diseño, nosotros podemos establecer e tamaño del arreglo, de una manera inicial, cuando nosotros usamos esta estructura, el tamaño de la estructura esta definido por el tamaño inicial de la estructura, lo que implica que la estructura no puede crecer, ni disminuir en tiempo de ejecución, por eso se les llama estáticas, esto tiene algunas complicaciones y efectos durante la ejecución lo que significa que cuando la estructura llega a su limite de capacidad, nos tenemos que conformar con ese limite definido, no podemos ajustar el tamaño de la estructura durante la ejecución de la operación, para ello debemos detener la aplicación y modificar el tamaño de la ejecución y posteriormente volver a cargar los datos.

17. Dinamicas Lineales Pilas Colas Listas No Lineales Arboles Grafos

18. Pilas Una pila es una estructura de datos que principalmente tiene dos operaciones: Apilar y desapilar Es un tipo de estructura que sigue un patrón LIFO ( Last in, First Out ), es decir el ultimo en entrar es el primero en salir

19. Colas Una cola es una estructura de datos que almacena elementos en una lista y permite acceder a los datos por uno de los dos extremos de la lista. Un elemento se inserta en la cola (parte final) de la lista y se suprime o elimina por la frente (parte inicial, cabeza) de la lista. Los elementos se eliminan (se quitan) de la cola en el mismo orden en que se almacenan y, por consiguiente, una cola es una estructura de tipo FIFO ( first -in- first - out , primero en entrar, Primero en salir o bien primero en llegar/primero en ser servido). o El servicio de atención a clientes es un ejemplo típico de cola o el cajero de un banco

20. Listas Una  lista  es una secuencia de elementos dispuesto en un cierto orden, en la que cada elemento tiene como mucho un predecesor y un sucesor. El número de elementos de la lista no suele estar fijado, ni suele estar limitado por anticipado . Representaremos la estructura de datos de forma gráfica con cajas y flechas. Las cajas son los elementos y las flechas simbolizan el orden de los elementos . La estructura de datos deberá permitirnos determinar cuál es el primer elemento y el último de la estructura, cuál es su predecesor y su sucesor (si existen de cualquier elemento dado). Cada uno de los elementos de información suele denominarse  nodo . La lista también puede representarse de forma simbólica escribiendo sus elementos separados por comas y encerrados entre corchetes. Por ejemplo: [" rojo","verde","azul","amarillo "]

21. El uso de listas en Java es una forma útil de almacenar y manipular grandes volúmenes de datos, tal como haríamos en una matriz o arreglo, pero con una serie de ventajas que hacen de este tipo de variables las preferidas para el procesamiento de grandes cantidades de información. Las listas en Java son variables que permiten almacenar grandes cantidades de datos. Son similares a los Array o a las Matrices .

22. Arboles Un árbol es una estructura jerárquica de datos que imita la forma de un árbol, un conjunto de nodos conectados. Un nodo es la unidad sobre la que se construye el árbol y puede tener ceros o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b. Solo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja y a los demás nodos se les conoce como ramas.

23. Formalmente, un árbol se puede definir de manera recursiva, se utiliza la recursión para definir un árbol porque es una característica inherente a los mismos, como: 1. Un solo nodo es, por si mismo, un árbol. Ese nodo es también la raíz de dicho árbol. 2. Se supone que n es un nodo y que A1 , A2 ,..., Ak son arboles con raíces n1 , n2 ,…, nk respectivamente. Se puede construir un nuevo árbol haciendo que n se constituya en el padre de los nodos n1 , n2 ,…, nk . En dicho árbol, n es la raíz y A1 , A2 ,..., Ak son los subarboles (o arboles hijos) de la raíz. Los nodos n1 , n2 ,… , nk reciben el nombre de hijos del nodo n y el nodo n recibe el nombre de padre de dichos nodo

24. Como ejemplo se puede considerar el índice de un libro. T1 (Tema 1) 1.1.-(Pregunta 1 del Tema 1) 1.2.-(Pregunta 2 del Tema 1) T2 (Tema 2) 2.1.-(Pregunta 1 del Tema 2) 2.1.1.-(Pregunta 1 de la pregunta 1 del Tema 2) 2.1.2.-( Pregunta 2 de la pregunta 1 del Tema 2) 2.2.-(Pregunta 2 del Tema 2) 2.3.-(Pregunta 3 del Tema 2) T3 (Tema 3)

25. Árbol del índice:

26. Grafos Desde un punto de vista intuitivo un grafo es un conjunto de nodos unidos por un conjunto de arcos. Un ejemplo de grafo que podemos encontrar en la vida real es el de un plano de trenes. El plano de trenes está compuesto por varias estaciones (nodos) y los recorridos entre las estaciones (arcos) constituyen las líneas del trazado.

27. Un  grafo  G=(V,E) consiste en un conjunto V de  nodos  (vértices) y un conjunto E de  aristas  (arcos). Cada arista es un par ( v,w ), siendo v y w un par de nodos pertenecientes al conjunto V de nodos. Podemos distinguir entre grafos dirigidos y no dirigidos. En un  grafo dirigido  los pares ( v,w ) están ordenados, traduciéndose la arista en una flecha que va desde el nodo  v  al nodo  w . En el caso de un grafo no dirigido, los nodos están unidos mediante líneas sin indicación de dirección . Por último se puede definir una función que asocie a cada arco un coste:  coste(arco)

28. Terminología de grafos Hablaremos de dos vértices  adyacentes  cuando estén unidos por un arco. El número de vértices adyacentes de un nodo constituye el  grado  del mismo. En el ejemplo los vértices adyacentes al nodo C son el a, d y e , siendo éste por tanto un nodo de grado tres por tener tres vértices adyacentes.

29. Un  camino  entre dos vértices, es una secuencia de vértices tal que dos vértices consecutivos son adyacentes. En el siguiente ejemplo el camino entre el vértice  a  y el vértice  e  será la secuencia de vértices  abecde . Cuando este camino no tiene vértices repetidos se dice que es  simple . Salvo en el caso de que el primer y último vértice del camino sean el mismo, en cuyo caso hablaremos de un  ciclo

30. Cuando este camino no tiene vértices repetidos se dice que es  simple . Salvo en el caso de que el primer y último vértice del camino sean el mismo, en cuyo caso hablaremos de un  ciclo

31. La siguiente clasificación, aunque no es completa, presenta las principales características que nos podemos encontrar en los grafos: Grafo conexo : Cuando entre cada dos nodos del grafo hay un camino. Bosque : Es un grafo sin ciclos. Arbol libre : es un bosque conexo. La representación más extendida de los grafos es mediante lo que se llaman  Matrices de adyacencia .

32. Como medida ante la estática los arreglos, tenemos estructuras dinámicas, esto significa que el tamaño de estructura puede ir creciendo o disminuyendo en tiempo de ejecución, lo que significa que el tamaño de la estructura es variante, y por lo tanto siempre ataremos utilizando la cantidad de memoria necesario para manejar o manipular los datos que la aplicación requiere, dentro de esta calificación tenemos las lineales y no lineales, cada una de estas estructuras tiene una lógica o algoritmo de funcionamiento partículas