Estructura de Datos - Trabajo Final

CENTRO DE ENSEÑANZA TECNICA Y SUPERIOR

[pic 1]

Escuela de Ingeniería

Estructura de Datos

Trabajo Final

Presenta:

Tijuana, B.C., 1 de Diciembre del 2015

Índice

1. Introduccion............................................................ 3

1. Desarrollo..............................................................4

1. Programas Básicos................................................4

1. Números...................................................4
2. Rectángulo...................................................5
3. Salario................................................... 5
4. Frase...................................................5 
5. Fibonacci................................................... 6

1. Métodos de Ordenamiento............................................6

1. Intercambio...................................................6
2. Selección...................................................7
3. Inserción...................................................8
4. Burbuja...................................................8
5. Shell...................................................8
6. Quicksort...................................................9
7. Heapsort...................................................10

1. Listas............................................................11

1. Pilas.............................................................13

1. Pilas simples...................................................13
2. Pilas con expresiones............................................14

1. Colas............................................................14

1. Arboles..........................................................15

1. Grafos..........................................................18

1. Conclusión.............................................................. 20

1. Referencias..............................................................21

Introducción

A lo largo del semestre se ha visto el currículo completo de la materia y se han hecho una gran variedad de programas con la intención de demostrar nuestra dominancia de los varios temas que presentados en el semestre. El punto de este trabajo es presentar un menú detallado con todos los programas que se han hecho y una explicación detallada de cada uno.

Los temas vistos se han ido de métodos de ordenamiento a grafos tanto viendo conceptos como trabajando con todos los métodos que los manipulan y las características que serán manipuladas por dichos métodos. NO falta mencionar  los exámenes que se han dado con tal de establecer niveles de dominancia y retarla al mismo tiempo.

Desarrollo

Se empezara con los programas simples:

El primero es un programa que le pide al usuario tres números enteros y después de analizar si el primero contra de un numero positivo o no, los multiplica si el primero fue comprobado como positivo o los suma si no logra serlo.

[pic 2][pic 3]

El segundo calcula el área de un rectángulo después de pedirle al usuario su base y su altura y compruebe que estos si pueden constituir a un rectángulo y no a un cuadrado.

[pic 4]

[pic 5]

El tercer programa Calcula el salario neto de un trabajador tras pedirle al usuario su salario y horas trabajadas y le informa al usuario el salario del trabajador antes y después de aplicarle un descuento de impuesto equivalente a 20% del salario neto.

[pic 6][pic 7]

El cuarto programa calcula el porcentaje de hombres y mujeres usando cantidades dadas por el usuario informándole del total de personas y porcentaje de hombres y mujeres en el cuarto.

[pic 8][pic 9]

El quinto programa le pide al usuario una frase de por lo menos 10 palabras y después de comprobar que si las contenga usando la cantidad de espacios como referencia, calcula el número de vocales y consonantes en la frase y se las demuestra con la adición de número de espacios al usuario.

[pic 10][pic 11]

El sexto y último programa  es una prueba del método de Fibonacci. Este método consta en sumar dos números a y b empezando con los valores 0 y 1 respectivamente. De ahí los sigue sumando hasta un límite de 12 sumas.

[pic 12][pic 13]

Métodos de Ordenamiento

Los siguientes Programas constan en demostraciones de los 7 métodos de ordenamiento        y uno que compara su efectividad: cada programa pide al usuario su preferencia entre:

• Array Hecho manualmente o Automáticamente
• Array de letras o números
• Orden ascendiente o descendiente

Además de tener las capacidades para medir tiempo de ejecución y muermo de intercambios y comparaciones.

Método de Intercambio:

El método de intercambio, también conocido como método de burbuja, tiene como característica  el intercambio entre elementos de un array. La idea consiste en comparar e intercambiar, en casos definidos, pares de elementos adyacentes hasta que todos estén ordenados en orden adyacente.

[pic 14][pic 15]

Método de Selección:

Este método consta en Buscar el mínimo elemento de la lista el cual intercambia con el primero, buscar el siguiente mínimo en el resto de la lista, intercambiarlo con el segundo y seguir así sucesivamente.

[pic 16][pic 17]

Método de Inserción:

Inicialmente se tiene un solo elemento, que consta de un conjunto de elementos. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores se desplazan una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

[pic 18][pic 19]

Método Burbuja

En este método se toma los elementos de un array empezando con el primero y se comparan de par en par, desplazándose de acuerdo al criterio hasta que lleguen al final del array o el elemento adyacente ya no es mayor o menor dependiendo del orden requerido.

[pic 20][pic 21]

Método Quicksort

Este algoritmo consta de: Elegir un elemento de la lista de elementos a ordenar, ordenar los demás elementos de la lista a cada lado del elemento seleccionado, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al elemento seleccionado pueden ser colocados en cualquiera de los dos lados. En este momento, el elemento seleccionado ocupa exactamente el lugar que le corresponderá en la lista ordenada. La lista queda separada en dos sublista, una formada por los elementos a la izquierda del elemento seleccionado, y otra por los elementos a su derecha. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

[pic 22][pic 23][pic 24]

[pic 25]

Método Heapsort:

Este método consiste en almacenar todos los elementos del vector a ordenar en un conjunto, y luego extraer el nodo que queda como nodo raíz de la cima en sucesivas iteraciones obteniendo el conjunto ordenado. De acuerdo al criterio buscado  la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él. El algoritmo, después de cada extracción, recoloca en la cima, la última hoja por la derecha del último nivel. Lo cual destruye la propiedad del conjunto del árbol. Pero, a continuación realiza un proceso de "descenso" del número insertado de forma que se elige a cada movimiento el mayor de sus dos hijos, con el que se intercambia. Este intercambio, realizado sucesivamente altera  el nodo en el árbol restaurando la propiedad montículo del árbol y dejando paso a la siguiente extracción del nodo raíz.

...