Elaborar un algoritmo o programa que realice al menos 3 operaciones con arreglos:
a) Ordenar los datos de mayor a menor o menor a mayor.
clic aqui
a) Ordenar los datos de mayor a menor o menor a mayor.
clic aqui
viernes, 31 de octubre de 2014
miércoles, 29 de octubre de 2014
Práctica 5
Realizar un programa con arreglos que lleve a cabo las siguientes operaciones:
a) Lectura de los datos.
b) Cálculo de la suma de sus elementos.
c) Cálculo del promedio de sus elementos.
d) Cálculo de la suma del valor n a sus elementos.
e) Cálculo de la multiplicación del valor n a sus elementos.
clic aqui
a) Lectura de los datos.
b) Cálculo de la suma de sus elementos.
c) Cálculo del promedio de sus elementos.
d) Cálculo de la suma del valor n a sus elementos.
e) Cálculo de la multiplicación del valor n a sus elementos.
clic aqui
martes, 28 de octubre de 2014
Práctica 6
Realice las siguientes actividades:
a) Programe el código de ejemplo que aparece en la página 71 del libro “Estructuras de datos en java” de Joyanes Aguilar.
b) Documente la implementación y el funcionamiento del arreglo multidimensional que aparece en el ejemplo.
clic aqui
a) Programe el código de ejemplo que aparece en la página 71 del libro “Estructuras de datos en java” de Joyanes Aguilar.
b) Documente la implementación y el funcionamiento del arreglo multidimensional que aparece en el ejemplo.
clic aqui
domingo, 26 de octubre de 2014
II UNIDAD. ESTRUCTURAS LINEALES
Objetivo:
Aplicar las principales estructuras de datos lineales.
Subtemas:
2.1. Listas.
2.2. Pilas estáticas y dinámicas.
2.3. Colas estáticas y dinámicas.
2.4. Aplicaciones.
Aplicar las principales estructuras de datos lineales.
Subtemas:
2.1. Listas.
2.2. Pilas estáticas y dinámicas.
2.3. Colas estáticas y dinámicas.
2.4. Aplicaciones.
sábado, 25 de octubre de 2014
Introducción
En
algunas ocasiones no se conoce por adelantado cuánta memoria se requerirá para
un programa. En esos casos es conveniente disponer de un método para adquirir
posiciones adicionales de memoria a medida que se necesiten durante la
ejecución del programa y liberarlas cuando no se necesitan. Las variables que
se crean y están disponibles durante la ejecución de un programa se llaman
variables dinámicas. Estas variables se representan con un tipo de datos
conocido como puntero. Las variables dinámicas se utilizan para crear
estructuras dinámicas de datos que se puede ampliar y comprimir a medida que se
requieran durante la ejecución del programa. Una estructura de datos dinámica
es una colección de elementos denominados nodos de la estructura (normalmente
de tipo registro) que son enlazados juntos. Las estructuras dinámicas de datos
se clasifican en lineales y no lineales.
Terminología
LISTA LINEAL
Una lista lineal es un conjunto
de elementos de un tipo dado que pueden variar en número y donde cada elemento
tiene un único predecesor y un único
sucesor o siguiente, excepto el primero y el último de la lista.
Los elementos de una lista lineal se almacenan normalmente
contiguos (un elemento detrás de otro) en posiciones consecutivas de la
memoria.
Las operaciones que se pueden realizar con listas
lineales contiguas son:
1. insertar,
eliminar o localizar un elemento
2.
Determinar el tamaño (número de elementos) de la lista
3. Recorrer
la lista para localizar un determinado elemento
4.
Clasificar los elementos de la lista en orden ascendente o descendente
5. Unir dos
o más listas en una sola
6. Dividir
una lista en varias sublistas
7. Copiar la
lista
8. Borrar la
lista
Las operaciones directas de
añadir y eliminar se efectúan únicamente en los extremos de la lista. Esta
limitación es una de las razones por las
que esta estructura es poco utilizada.
LISTAS ENLAZADAS
Los inconvenientes de las listas
contiguas se eliminan con las listas enlazadas.
Una lista enlazada o encadenada
es un conjunto de elementos en los que cada uno de ellos contiene la posición
(o dirección) del siguiente elemento de
la lista. Cada elemento de la lista enlazada debe tener al menos dos campos: un
campo que tiene el valor del elemento y un campo enlace (link) que contiene la posición del
siguiente elemento, es decir, su conexión, enlace o encadenamiento. Los
elementos de una lista son enlazados por
medio de los campos enlaces.
PILAS
Una pila (stack) es una colección ordenada de
elementos a los cuales sólo se puede acceder por un único lugar o extremo de la
pila. Los elementos se añaden o se quitan (borran) de la pila sólo por su parte
superior (cima). Este es el caso de una pila de platos, una pila de
libros, etc.
Cuando se dice que la pila está ordenada, lo que se quiere
decir es que hay un elemento al que se puede acceder primero (el que está
encima de la pila), otro elemento al que se puede acceder en segundo lugar
(justo el elemento que está debajo de la cima), un tercero, etc. No se requiere
que las entradas se puedan comparar utilizando el operador “menor que” (<) y
pueden ser de cualquier tipo.
Las entradas de la pila deben ser eliminadas en el orden
inverso al que se situaron en la misma. Por ejemplo, se puede crear una pila de
libros, situando primero un diccionario, encima de él una enciclopedia y encima
de ambos una novela, de modo que la pila tendrá la novela en la parte superior.
Debido a su propiedad específica último en entrar, primero
en salir se conoce a las pilas como estructuras de datos LIFO (last-in,
first-out)
Las operaciones usuales en la pila son Insertar y Quitar.
La operación Insertar (push) añade un elemento en la cima de la pila, y
la operación Quitar (pop) elimina o saca un elemento de la pila.
Tipo de dato: Dato
que se almacena en la pila.
Operaciones:
Crear. Pila Inicia.
Insertar (push). Pone
un dato en la pila.
Quitar (pop). Retira
(saca) un dato de la pila.
Pila vacía. Comprueba
si la pila no tiene elementos.
Pila llena. Comprueba
si la pila está llena de elementos.
Limpiar pila. Quita
todos sus elementos y deja la pila vacía.
Cima Pila. Obtiene
el elemento cima de la pila.
Tamaño de la pila. Número
de elementos máximo que puede contener la pila.
Aplicaciones: Las pilas se
utilizan en compiladores, sistemas operativos y programas de aplicaciones. Una
aplicación interesante es la evaluación de expresiones aritméticas, también la
organización de la memoria.
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 el frente (parte inicial, frente) de la lista. Las
aplicaciones utilizan una cola para almacenar elementos en su orden de
aparición o concurrencia.
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, firs-out,
primero en entrar-primero en salir o bien primero en llegar-primero en ser
servido). El servicio de atención a clientes en un almacén es un ejemplo típico
de cola. La acción de gestión de memoria intermedia (buffering) de trabajos
o tareas de impresora en un distribuidor de impresoras (spooler) es otro
ejemplo típico de cola.
Las operaciones que sirven
para definir una cola y poder manipular su contenido son las siguientes:
Tipo de dato: Elemento
que se almacena en la cola.
Operaciones:
CrearCola.
Inicia
la cola como vacía.
Insertar.
Añade
un elemento por el final de la cola.
Quitar.
Retira
(extrae) el elemento frente de la cola.
Cola
vacía. Comprueba si la cola no tiene elementos.
Cola
llena. Comprueba si la cola está llena de elementos.
Frente.
Obtiene
el elemento frente o primero de la cola.
Tamaño
de la cola. Número de elementos máximo que puede contener
la cola.
En una cola, al igual que en
una pila, los datos se almacenan de un modo lineal y el acceso a los datos sólo
está permitido en los extremos de la cola.
Aplicaciones: Las
colas tienen numerosas aplicaciones en el mundo de la computación: colas de
mensajes, colas de tareas a realizar por una impresora, colas de prioridades,
etc.
COLA
DE PRIORIDAD
El término cola sugiere la
forma en que ciertos objetos esperan la utilización de un determinado servicio.
Por otro lado, el término prioridad sugiere que el servicio no se
proporciona únicamente aplicando el concepto primero en llegar primero en
ser atendido, sino que cada objeto tiene asociada una prioridad basada en
un criterio objetivo. Las colas de prioridades son una estructura ordenada que
se utiliza para guardar elementos en un orden establecido. El orden para
extraer un elemento de la estructura sigue estas reglas:
• Se
elige la cola no vacía que se corresponde con la mayor prioridad.
• En
la cola de mayor prioridad, los elementos se procesan según el orden de
llegada: primero en entrar-primero en salir.
Una organización formada por
colas de prioridades es el sistema de tiempo compartido, necesario para
mantener una serie de procesos que esperan ser ejecutados por el procesador; cada
proceso lleva asociado una prioridad. También las simulaciones de sucesos que
ocurren en un tiempo discreto, como la atención de una fila de clientes en un
sistema de n ventanillas de despacho de billetes de transporte, se
realizan con una estructura de colas de prioridades.
Implementación:
Una forma simple de
implementar una cola de prioridades es con una lista enlazada y ordenada
según la prioridad. Otra alternativa consiste en un array o tabla de
tantos elementos como prioridades estén previstas; cada elemento de la tabla
guarda los objetos con la misma prioridad. Por último, se puede utilizar la
estructura del montículo para guardar los componentes. La característica del
montículo permite recuperar el elemento de máxima prioridad con una simple
operación.
Los elementos de una cola
de prioridades son objetos con la propiedad de ordenación, de tal forma
que se puedan realizar comparaciones. Esto equivale a que dispongan de un
atributo, de tipo ordinal, representando la prioridad del objeto.
viernes, 24 de octubre de 2014
Presentación: Listas
La siguiente presentación corresponde al tema de listas. Comenzamos con la definición, características y operaciones que se pueden realizar en estas estructuras, y después mostramos la clasificación de las mismas.
clic aqui
clic aqui
jueves, 23 de octubre de 2014
Mapa conceptual de listas
El siguiente mapa conceptual contiene la definición, los componentes y la clasificación de la estructura lista, y señala las operaciones que se pueden realizar en ella.
miércoles, 22 de octubre de 2014
Tabla comparativa
En el siguiente enlace podrán encontrar una tabla comparativa de las estructuras de datos lineales y las no lineales.
clic aqui
clic aqui
Práctica 1
Realizar un programa que cree una lista de 10 elementos:
a) Declarar la lista como vacía.
b) Agregar nodo por nodo.
c) Visualizar la lista.
clic aqui
a) Declarar la lista como vacía.
b) Agregar nodo por nodo.
c) Visualizar la lista.
clic aqui
martes, 21 de octubre de 2014
Práctica 2
Realizar el programa explicado en el primer video (Listas Simplemente Enlazadas en Java).
a) Cambiar el tipo de dato
clic aqui
a) Cambiar el tipo de dato
clic aqui
lunes, 20 de octubre de 2014
Práctica 3
Realizar el programa explicado en el segundo video (Lista simple inserción al inicio y final, impresión, NetBeans (java)).
a) Cambiar el tipo de dato
clic aqui
a) Cambiar el tipo de dato
clic aqui
domingo, 19 de octubre de 2014
Práctica 4
Realizar lo siguiente:
a) Elaborar un programa que agregue y quite nodos, y que cada vez se añada o elimine un nodo, se muestre el número de elementos que contiene la lista.
b) Elaborar un programa con una lista lineal que agregue y elimine nodos, y que el
valor del último de ellos sea 10.
clic aqui
a) Elaborar un programa que agregue y quite nodos, y que cada vez se añada o elimine un nodo, se muestre el número de elementos que contiene la lista.
b) Elaborar un programa con una lista lineal que agregue y elimine nodos, y que el
valor del último de ellos sea 10.
clic aqui
viernes, 17 de octubre de 2014
Mapa mental de pilas
El siguiente mapa mental corresponde al tema de pilas, esta actividad fue realizada en el salón de clases.
jueves, 16 de octubre de 2014
Práctica 5
Implementar una pila con arreglos:
a) Agregar elementos
b) Eliminar elementos
c) Borrar elementos
d) Mostrar si es vacía o no
clic aqui
a) Agregar elementos
b) Eliminar elementos
c) Borrar elementos
d) Mostrar si es vacía o no
clic aqui
miércoles, 15 de octubre de 2014
Práctica 6
A partir de una frase dada, formar varias pilas:
a) Pila de consonantes
b) Pila de vocales
c) Pila de caracteres especiales
clic aqui
a) Pila de consonantes
b) Pila de vocales
c) Pila de caracteres especiales
clic aqui
lunes, 13 de octubre de 2014
Práctica 7
Implementar un menú con las diferentes formas de implementar una cola.
a) Estática
b) Dinámica
clic aqui
a) Estática
b) Dinámica
clic aqui
domingo, 12 de octubre de 2014
Práctica 8
Crear un menú que implemente las cuatro estructuras lineales vistas:
a) Arreglos
b) Listas
c) Pilas
d) Colas
clic aqui
a) Arreglos
b) Listas
c) Pilas
d) Colas
clic aqui
sábado, 11 de octubre de 2014
III UNIDAD. ESTRUCTURAS NO LINEALES
Objetivo: Aplicar las principales estructuras de datos no lineales.
Subtemas:
3.1. Recursividad.
3.2. Árboles.
3.3. Grafos.
Subtemas:
3.1. Recursividad.
3.2. Árboles.
3.3. Grafos.
viernes, 10 de octubre de 2014
Introducción
Las estructuras dinámicas
lineales de datos tienen grandes ventajas de flexibilidad sobre las
representaciones contiguas; sin embargo, tienen un punto débil: son listas
secuenciales, es decir, están dispuestas de modo que es necesario moverse a
través de ellas una posición a la vez (cada elemento tiene un siguiente elemento).
Esta linealidad es típica de cadenas, de elementos que pertenecen a una sola
dimensión: campos en un registro, entradas en una pila, entradas en una cola y
de nodos en una lista enlazada simple. Las estructuras de datos no lineales
resuelven los problemas que plantean las listas lineales y en las que cada elemento
puede tener diferentes siguientes elementos.
Terminología
RECURSIVIDAD
La
recursividad (recursión) es aquella propiedad que posee un método por la
cual puede llamarse a sí mismo. Aunque se puede utilizar la recursividad como
una alternativa a la iteración, una solución recursiva es, normalmente, menos
eficiente en términos de tiempo de computadora que una solución iterativa,
debido a las operaciones auxiliares que llevan consigo las invocaciones
suplementarias a los métodos; sin embargo, en muchas circunstancias, el uso de
la recursión permite a los programadores especificar soluciones naturales,
sencillas, que serían, en caso contrario, difíciles de resolver. Por esta
causa, la recursión es una herramienta poderosa e importante en la resolución
de problemas y en la programación. Diversas técnicas algorítmicas utilizan la
recursión, como los algoritmos divide y vence y los algoritmos de vuelta
atrás.
ÁRBOLES
Intuitivamente, el concepto
de árbol implica una estructura en la que los datos se organizan de modo que
los elementos de información están relacionados entre sí a través de ramas. El
árbol genealógico es el ejemplo típico más representativo del concepto de árbol
general.
Un árbol consta de un
conjunto finito de elementos, denominados nodos y de un conjunto finito
de líneas dirigidas, denominadas ramas, que conectan los nodos. El
número de ramas asociado con un nodo es el grado del nodo.
Un árbol es un conjunto de
uno o más nodos tales que:
1.
Hay un nodo diseñado especialmente llamado raíz.
2.
Los nodos restantes se dividen en n ≥ 0 conjuntos disjuntos, T1 ... Tn, tal que
cada uno de estos conjuntos es un árbol. A T1 ... Tn se les denomina subárboles
del raíz.
Si
un árbol no está vacío, entonces el primer nodo se llama raíz.
Además
del nodo raíz, existen muchos términos utilizados en la descripción de los
atributos de un árbol. En la Figura 13.3, el nodo A es el raíz. Utilizando el
concepto de árboles genealógicos, un nodo puede ser considerado como padre si
tiene nodos sucesores.
Estos
nodos sucesores se llaman hijos. Por ejemplo, el nodo B es el padre de
los hijos E y F. El padre de H es el nodo D. Un árbol puede representar
diversas generaciones en la familia. Los hijos de un nodo y los hijos de estos
hijos se llaman descendientes, y el padre y los abuelos de un nodo son
sus ascendientes. Por ejemplo, los nodos E, F, I y J son descendientes
de B. Cada nodo no raíz tiene un único padre y cada padre tiene cero o más
nodos hijos. Dos o más nodos con el mismo padre se llaman hermanos. Un
nodo sin hijos, tal como E, I, J, G y H se llama nodo hoja.
El
nivel de un nodo es su distancia al nodo raíz. La raíz tiene una distancia
cero de sí misma, por ello se dice que está en el nivel 0. Los hijos del nodo
raíz están en el nivel 1, sus hijos están en el nivel 2, y así sucesivamente.
Una cosa importante que se aprecia entre los niveles de nodos es la relación
entre niveles y hermanos. Los hermanos están siempre al mismo nivel,
pero no todos los nodos de un mismo nivel son necesariamente hermanos.
Los
árboles se utilizan para representar fórmulas algebraicas, para organizar
objetos en orden de tal forma que las búsquedas sean muy eficientes y en
aplicaciones diversas tales como inteligencia artificial o algoritmos de
cifrado. Casi todos los sistemas operativos almacenan sus archivos en árboles o
estructuras similares a árboles. Además de las aplicaciones citadas, los
árboles se utilizan en diseño de compiladores, procesado de texto y algoritmos
de búsqueda.
GRAFOS
Un
grafo es un conjunto de puntos (una estructura de datos) y un conjunto de
líneas, cada una de las cuales une un punto a otro. Los puntos se llaman nodos
o vértices y las líneas se llaman aristas o arcos. Se representa con el par G = (V, A).
Un
arco o arista representa una relación entre dos nodos, se representa por (u, v)
siendo u, v el par de nodos.
§ Lazo:
arista que une a un nodo(vértice) consigo mismo.
§ camino:
secuencia de uno o mas aristas que conectan dos nodos.
§ La
longitud de un camino es el número de aristas que comprende.
§ Se
dice que dos vértices son adyacentes si hay una arista que los une.
Un
grafo permite modelar relaciones arbitrarias entre objetos. Un grafo G = (V,A)
es un par formado por un conjunto de vértices o nodos, V, y un conjunto de
arcos o aristas, A.
Cada
arco es el par (u,w), siendo u, w dos vértices relacionados.
jueves, 9 de octubre de 2014
Mapa conceptual de recursividad
El siguiente mapa conceptual corresponde al tema de recursividad, esta actividad fue realizada en equipo y en el salón de clases.
miércoles, 8 de octubre de 2014
Reporte de investigación de recursividad
El siguiente enlace corresponde a la investigación del tema "Recursividad". Contiene la definición, los tipos, las características y ejemplos del tema.
clic aqui
clic aqui
martes, 7 de octubre de 2014
Práctica 1
Crear un programa que calcule el factorial de un número:
a) De forma recursiva
b) De forma iterativa
clic aqui
a) De forma recursiva
b) De forma iterativa
clic aqui
lunes, 6 de octubre de 2014
Práctica 2
Crear un programa que determine el producto de dos números naturales:
a) De forma recursiva
b) De forma iterativa
a) De forma recursiva
b) De forma iterativa
domingo, 5 de octubre de 2014
Práctica 3
Crear un programa que implemente la serie de Fibonacci:
a) De forma recursiva
b) De forma iterativa
clic aqui
a) De forma recursiva
b) De forma iterativa
clic aqui
sábado, 4 de octubre de 2014
Práctica 4
Esta práctica fue realizada en el salón de clases, y consistió en crear un método recursivo para determinar el mínimo común divisor de dos números.
viernes, 3 de octubre de 2014
Práctica 5
Crear un programa que implemente las Torres de Hanoi.
Nota: Las Torres de Hanoi es un juego oriental que consta de tres columnas o varillas llamadas origen, destino y auxiliar y una serie de discos de distintos tamaños.
Los discos están colocados de mayor a menor tamaño en la columna origen. El juego consiste en pasar todos los discos a la columna destino y dejarlos como estaban de mayor a menor. (el más grande en la base, el más pequeño arriba)
Las reglas del juego son las siguientes:
Sólo se puede mover un disco cada vez.
Para cambiar los discos de lugar se pueden usar las tres columnas.
Nunca deberá quedar un disco grande sobre un disco pequeño.
clic aqui
Nota: Las Torres de Hanoi es un juego oriental que consta de tres columnas o varillas llamadas origen, destino y auxiliar y una serie de discos de distintos tamaños.
Los discos están colocados de mayor a menor tamaño en la columna origen. El juego consiste en pasar todos los discos a la columna destino y dejarlos como estaban de mayor a menor. (el más grande en la base, el más pequeño arriba)
Las reglas del juego son las siguientes:
Sólo se puede mover un disco cada vez.
Para cambiar los discos de lugar se pueden usar las tres columnas.
Nunca deberá quedar un disco grande sobre un disco pequeño.
clic aqui
jueves, 2 de octubre de 2014
Práctica 6
Crear un programa que implemente las operaciones aritméticas básicas (haciendo uso de la recursividad):
a) Suma
b) Resta
c) Multiplicación
d) División
clic aqui
a) Suma
b) Resta
c) Multiplicación
d) División
clic aqui
miércoles, 1 de octubre de 2014
Práctica 7
Crear un programa que implemente un menú con las siguientes opciones:
a) Potencia n de un número x.
b) Factorial de un número.
c) Serie de Fibonacci.
d) Producto de dos números naturales.
clic aqui
a) Potencia n de un número x.
b) Factorial de un número.
c) Serie de Fibonacci.
d) Producto de dos números naturales.
clic aqui
Suscribirse a:
Entradas (Atom)
