UNIDADES 11,12,13 Y 14 ALGORÍTMICA Y PROGRAMACIÓN

A CONTINUACIÓN EN ESTE BLOG SE VERÁN LAS UNIDADES IMPARTIDAS EN LA MATERIA ALGORÍTMICA Y PROGRAMACIÓN DESDE LA NUMERO 11 A LA NUMERO 14 LAS CUALES POSEEN INFORMACIÓN ÚTIL PARA LOS FUTUROS INGENIEROS INFORMÁTICOS DE ESTA SOCIEDAD, QUIENES SE ENCARGARAN DE SEGUIR CRECIENDO COMO PROFESIONALES EN SU ÁREA Y DESCUBRIENDO NUEVAS FORMAS DE IMPLEMENTAR LA PROGRAMACIÓN.

UNIDAD 11: PUNTEROS.

En el campo de la informática los punteros son aquellos objetos a los cuales cuyo valor es referido a otro valor almacenado otro valor almacenado en otra parte de la memoria del ordenador utilizando su dirección. Estos pueden hacer referencia a algún tipo de dato almacenado en la memoria del computador que luego será encontrada al usar el valor de esta como referencia. Los punteros funcionan como acceso rápido de un punto a otro, algo parecido al índice de un libro dando la ubicación de dicho contenido nombrado en él.

En la programación el la que se orienta a un objeto los punteros son utilizados como método de unión.Los punteros también permiten proteger así como como permitir el acceso a direcciones de memoria, pero estos también pueden ser muy riesgosos, por ende se les tiene que asignar un límite de búsqueda específico.

1. DECLARACIÓN DE PUNTEROS.

Una declaración de puntero identifica una variable de puntero y especifica el tipo del objeto al que señala la variable.Por tanto, una declaración de puntero puede ser escrita en términos generales como: <tipo>(cualquier tipo de variable en C) y <identificador> o<nombre> ( es el nombre del puntero. El tipo o tipo base, indica el tipo de variables que se podrán manipular a través del puntero).Existen tres formas seguras de iniciar un puntero:

1. Iniciando con el valor de NULL, de este modo se estará especificando que el puntero no apunta a ninguna memoria concreta. El valor NULL también se define en un fichero de header.

2. Inicializarlo haciendo que tome como valor la dirección de una variable.

3. Asignarle memoria dinámica a través de una función de asignación de memoria. Las funciones más habituales son calloc y malloc, definidas en el fichero alloc.h o bien en stdlib.h.

1.1. OPERADORES DE PUNTEROS.

un operador es justamente la dirección en memoria de un objeto, en este caso del puntero, existen dos operadores para manipular los punteros, estos son el * y el &. El operador * es aplicado a un puntero y nos da el valor de la variable referencia. El operador & se aplica a variables comunes, nos da la dirección de memoria de variable a la que se aplica. a continuación se veran las formas en las que se utilizan estos operadores:

1.int *pt; ¬ Aquí el puntero se define pero no la variable referenciada, se debe inicializar el puntero.

2.pt = &a; ¬ Se inicializa el puntero "pt" con una direcció válida, la direccíón de la variable "a". Se dice a partir de aquí que "pt" apunta a "a" o que la variable referenciada por "pt" coincide con "a". El valor de la variable refernciada por "pt" (*pt) es 1 (el mismo valor que tiene la variable "a").

3.*pt = 73; ¬ Se modifica el valor de la variable referenciada, ahora *pt tiene el valor de 73. La variable "a" también cambia a 73.

4.b = *pt; ¬ La variable "b" ahora tiene el valor de 73.

6.pt = NULL; ¬ El puntero "pt" apunta ahora a NULL, ya no existe a partir de aquí la variable referenciada.

*pt = 25; ¬ ERROR: No existe la variable referenciada en este punto.

7.pt = c; ¬ "c" es un arreglo, por lo tanto el identificador "c" está relacionado con la dirección del primer elemento del arreglo. Esta instrucción hace que "pt" apunte a esa misma dirección de memoria.

8.*pt = 88; ¬ Modifica el elemento "c[0]" en 88.

pt[0] = 88; ¬ Equivale a la enterior sentencia, modifica el elemento "c[0]" en 88.

9.pt[2] = 51; ¬ Modifica el elemento "c[2]" en 51. Un puntero puede manejarse como un arreglo.

10.pt = &c[3]; ¬ El puntero "pt" apunta al cuarto elemento de c.

11.*pt = 102; ¬ Modifica el elemento "c[3]" en 102.

pt[0] = 102; ¬ Equivale a la enterior sentencia, modifica el elemento "c[3]" en 102.

1.2. OPERACIONES CON PUNTEROS.

La suma o resta de un entero produce una nueva localización de memoria. también Se pueden comparar punteros, utilizando expresiones lógicas, para ver si están apuntando o no a la misma dirección de memoria. así como se aplica La resta de dos punteros da como resultado el número de variables entre las dos direcciones.

a continuación veremos un ejemplo acerca de una operación en la que se utilizan los punteros:

#include <iostream.h>

main()

{

int vector[3];

int* princPunt = vector;

int* finPunt = &vector[2];

vector[2] = 15;

cout << *(princPunt+2) << '\t' << *finPunt <<'\n';

if (princPunt == finPunt)

cout << " Esto no puede suceder " << '\n';

cout << "Numero de elementos \t" <<finPunt-princPunt << '\n';

}

el resultado como puede apreciarse en el ejemplo es de 15 y el numero de elementos utilizados fueron 2.

Las operaciones permitidas con punteros son diversas y se ver a continuación:

Operación	Resultado	Comentario
pt1++	puntero	Desplazamiento ascendente de 1 elemento
pt1--	puntero	Desplazamiento descendente de 1 elemento
pt1 + n	puntero	Desplazamiento ascendente n elementos
pt1 - n	puntero	Desplazamiento descendente n elementos
pt1 - pt2	entero	Distancia entre elementos
pt1 == NULL	booleano	Siempre se puede comprobar la igualdad o desigualdad con NULL
pt1 != NULL	booleano	Cierto o falso
pt1 <R> pt2	booleano	<R> es una expresión relacional
pt1 = pt2	puntero	Asignación
pt1 = void	puntero genérico	Asignación

2.PUNTEROS Y FUNCIONES.

En los distintos lenguajes de programación, un puntero puede hacer referencia a código ejecutable, es decir, puede apuntar a una función, método o procedimiento. Un puntero a función almacenará la dirección de una función que sea invoca. Este tipo de construcción es útil pues encapsula comportamiento, que puede ser llamado a través de un puntero. a continuación veremos un ejemplo:

#include <stdio.h>

//Funcion de ejemplo

void funcion()

{

printf("Se ha entrado en la funcion\n");

}

int main()

{

//Creamos el puntero a la funcion

void (*puntero_funcion)() = &funcion;

//Llamamos la funcion a traves del puntero

puntero_funcion();

return 0;

}

Si bien este mecanismo se puede utilizar para llamar a funciones de forma dinámica, muchas veces es una técnica favorita de virus y otros autores de software malicioso. Cabe destacar que en ocasiones se verán otros tipos de funciones que albergaran diferentes parámetros dependiendo de la situación requerida.

3.PUNTEROS Y ESTRUCTURAS.

Un puntero puede apuntar a una estructura y acceder a sus campos, las estructuras tienen una dirección, asumiendo que esta es el comienzo de su almacenamiento. Esto es especialmente cierto en C, donde las estructuras representan exclusivamente conjuntos de datos. En C++ las estructuras son cierto tipo de clases que pueden contener código (funciones), pero incluso entonces, lo que realmente se almacena en el cuerpo de la estructura son punteros (datos) a las funciones correspondientes. La utilización de dichas variables se emplea frecuentemente cuando es necesario pasar la estructura por referencia a una función o cuando se quiere hacer una reserva dinámica de memoria para una estructura en un determinado momento de la ejecución del programa.Veremos que los punteros a estructuras son de uso muy frecuente para el manejo de estas; en especial cuando se pasan como argumentos a funciones, o son devueltas por estas. Por ejemplo, la sentencia:

struct punto {int x; int y;} pto = {3,4}, *ptr = &pto, arsp[10];

La sintaxis de declaración de punteros a estructuras se puede hacer de esta manera:

<tipo_objeto> * <etiqueta_puntero> [ = <iniciador> ]

También se puede apreciar diversos ejemplos de expresiones para estructuras:

++ptr->x	Debido a la precedencia de operadores, equivale a ++(ptr->x). Así pues, incrementa el miembro x, no el valor del puntero ptr.
*ptr->x	*Del mismo modo, esta indirección equivale a (ptr->x).**
*ptr->str	En este caso, si es correcta la aplicación del operador ; la expresión equivale a (ptr->str), y ptr->str sí es un puntero (a carácter); concretamente señala a la primera posición de la cadena.
*++ptr->str**	Este debe ser utilizado en caso de que Se halla señalado que *ptr->str equivale a algún valor requerido ahora el compilador se enfrenta a la expresión: ++'valor' == 'valor'+1;. El resultado depende del contexto, por ejemplo, 'B' = 'B'+1; es un error ('H' no es un Lvalue).
*ptr++->str	*La expresión se traduce en: ((ptr++)->str). Si se utiliza la expresión que sigue, el resultado es el que se indica, pero cualquier posterior intento de utilizar ptr conduce a un error**
*++ptr->str	*La expresión equivale a (++ (ptr->str)). Nuevamente el resultado es correcto: ptr->str es un puntero p que señala al carácter 'B'; su incremento en 1 lo hace apuntar al segundo.**
*ptr->str++	*Esta expresión equivale a ((ptr->str))++. Es decir, 'B'++; nuevamente el resultado depende del contexto.**

las estructuras pueden asociarse con los siguientes operadores:

• ( ): Llamada de función.

• [ ]: Subíndices.

• ->: Acceso a miembro de estructura (mediante puntero).

• . : Acceso a miembro de estructura.

• :: : Acceso a miembro de clase.

UNIDAD 12: LISTAS ENLAZADAS

Las listas enlazadas es una secuencia de varios elementos almacenados en la memoria, son posiblemente las estructuras de datos más fáciles, rápidas y sencillas de estudiar, aprender y entender La resolución de una función relacionada con listas simplemente enlazadas, es fácil y rápida, en especial porque no se requieren demasiadas líneas de código, por ende la solución es inmediata. La implementación de una aplicación basada en listas simplemente enlazadas, también supone un fácil desarrollo.

1.CONCEPTO Y CLASIFICACIÓN.

Una lista es una secuencia de 0 o más elementos de un tipo dado almacenados en memoria.Son estructuras lineales formadas por una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior. Si una lista tiene 0 elementos se dice que la lista está vacía. Se representa con una caja rectangular dividida en dos secciones: Dato o información y enlace o puntero.

Dato: Representa el dato o los datos a almacenar. Puede ser de cualquier tipo.

Enlace: es un puntero al siguiente elemento de la lista y se representa con una flecha para facilitar la comprensión de la conexión de los nodos. Este puntero contiene la dirección del nodo sucesor, de esta forma se enlazan y podemos construir la lista. El último nodo no enlaza con ningún otro, por lo tanto, el puntero contiene un valor nulo que en el caso de C++ se denomina nil.

A CONTINUACIÓN SE VERA UN EJEMPLO GRÁFICO DE UN ENLACE APUNTANDO A UN NIL:

LAS LISTAS ENLAZADAS SE CLASIFICAN DE LA SIGUIENTE MANERA:

• Listas simples o enlazadas: cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es nil. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento.

• Listas circulares: Es una modificación de la lista enlazada, en las que el puntero del último elemento apunta al primero de la lista.

• Listas doblemente enlazadas :cada nodo consta de un campo con información y dos punteros: un puntero que apunta al nodo anterior y otro que apunta al nodo siguiente. En el caso del primer nodo, como no tiene nodo anterior, el puntero que apunta a anterior apuntará a nil.

• Listas circulares doblemente enlazadas: cada nodo consta de un campo con información y dos punteros: un puntero que apunta al nodo anterior y otro que apunta al nodo siguiente. En el caso del primer nodo, como no tiene nodo anterior, el puntero que apunta a anterior apuntará a último nodo.

2.LISTAS SIMPLEMENTE ENLAZADAS: FUNDAMENTOS TEÓRICOS, CLASIFICACIÓN, OPERACIONES BÁSICAS.

La Lista Enlazada Simple es la más fundamental estructura de datos basada en punteros, y del concepto fundamental de ésta derivan las otras estructuras de datos. A continuación se verán sus fundamentos teóricos, clasificación y las operaciones básicas que pueden ejecutarse en estas:

los fundamentos teóricos de una lista simplemente enlazada se basan en una colección o secuencia de elementos dispuestos uno detrás de otro, en la que cada elemento se conecta al siguiente elemento por un «enlace» o «puntero». La idea básica consiste en construir una lista cuyos elementos llamados nodos se componen de dos partes o campos: la primera parte o campo contiene la información y es, por consiguiente, un valor de un tipo genérico. y estas se pueden dividir en cuatro clasificaciones las cuales son:

• Listas simplemente enlazadas: Cada nodo (elemento) contiene un único enlace que conecta ese nodo al nodo siguiente o nodo sucesor. La lista es eficiente en recorridos directos ((<adelante»).

• Listas doblemente enlazadas simples: Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor. La lista es eficiente tanto en recorrido directo («adelante») como en recorrido inverso («atrás»).

• Lista circular simplemente enlazada: Una lista enlazada simplemente en la que el último elemento (cola) se enlaza al primer elemento (cabeza) de tal modo que la lista puede ser recorrida de modo circular («en anillo»).

• Lista circular doblemente enlazada simple: Una lista doblemente enlazada en la que el último elemento se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modo circular (en anillo) tanto en dirección directa («adelante») como inversa («atrás»).

Las operaciones básicas que pueden ejecutarse con las listas simplemente enlazadas son las siguientes.

• Declaración: El proceso de declaración consiste en el inicializar la lista con cada nodo de manera sucesiva dando a entender el tipo de lista a ejecutar.

• Punteros de cabecera y cola: Estos procesos son utilizados para insertar Y guardar los datos a procesar. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

• Operador de selección: Esta operación sirve para la resolución de solicitudes e incidencias de los usuarios, así como la mejora y el mantenimiento de las infraestructuras existentes.

• Inserción: Esta operación consiste en agregar un nuevo nodo a la lista, sin embargo, dependiendo de la posición en la que se deba insertar el nodo, se puede presentar diferentes casos, los cuales serian al inicio de la lista, al final de la lista, antes de un punto X y después de un punto X.

• Búsqueda: La operación de búsqueda de un elemento en una lista simplemente ligada es muy fácil de realizar, aunque ineficiente ya que se lleva a cabo de forma secuencial. Se debe haber recorrido los nodos hasta encontrar el que estamos buscando o hasta que se llega al final de la lista.

• Eliminación de elementos: Consiste en eliminar un número de la lista y liberar el espacio de memoria correspondiente.

3.LISTAS DOBLEMENTE ENLAZADAS Y CIRCULARES:

A continuación se verán las definiciones de las listas doblemente enlazadas y circulares:

• Listas doblemente enlazadas: es una colección de nodos, en la cual cada uno de ellos tiene dos apuntadores, uno apuntando a su predecesor y otro a su sucesor. Por medio de estos punteros se podrá entonces avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro apuntador.

• Las listas circulares: son similares a las listas simplemente enlazadas. Sin embargo, tiene las características de que el último elemento de la lista apunta al primero, en lugar a apuntar al vacío NL. Las operaciones básicas de este tipo de listas son iguales a las de las simplemente enlazadas.

3.1.DECLARACIÓN, RECORRIDO, INSERCIÓN Y ELIMINACIÓN DE ELEMENTOS DE LAS LISTAS DOBLEMENTE ENLAZADAS.

• Declaración: Para declarar una lista doblemente enlazada y circular se necesita el comienzo del algoritmo. En el caso de las doblemente enlazadas es cuando se encuentra apuntando a su inicio y fin. En el caso de las circulares es cuando el último elemento apunta de manera directa al primer punto vacío.

• Recorrido: Al tener cada nodo una doble liga, la lista se puede recorrer tanto del inicio al final, mediante las ligas derechas, como en sentido inverso; es decir, del final al principio, con las ligas izquierdas. Cualquiera que sea la dirección del recorrido, el algoritmo es similar al que se presenta para listas simplemente enlazadas.

• Inserción: La inserción de un elemento consiste en agregar un nuevo nodo a la lista y establecer los apuntadores correspondientes. No se considerará el caso de lista vacía.

• Eliminación de elementos: La operación de eliminación de un nodo en una lista doblemente ligada al igual que en el caso de las listas simplemente ligadas, consiste en eliminar un elemento de la lista, predefiniendo los apuntadores correspondientes y liberando el espacio de la memoria ocupado por el nodo.

UNIDAD 13: RECURSIVIDAD.

Los programadores necesitan ser capaces de resolver todos los problemas que se les presente a través del computador aun cuando en el lenguaje que utilizan no haya una manera directa de resolver los problemas. En el lenguaje de programación, así como en otros lenguajes de programación, se puede aplicar una técnica que se le dio el nombre de recursividad por su funcionalidad. Esta técnica es utilizada en la programación estructurada para resolver problemas que tengan que ver con el factorial de un número, o juegos de lógica. Las asignaciones de memoria pueden ser dinámicas o estáticas y hay diferencias entre estas dos y se pueden aplicar las dos en un programa cualquiera.

1.FUNDAMENTOS TEÓRICOS: DEFINICIÓN, ÁMBITO DE APLICACIÓN Y UTILIDAD DE LA RECURSIVIDAD.

En términos de informática La recursividad es una técnica muy empleada en la programación informática y consiste en que una función se llame a sí misma. El ejemplo clásico es la función que calcula la factorial de un número. Una factorial consiste en multiplicar un número natural por el número anterior, y este a su vez por el anterior, y así sucesivamente hasta llegar al número 1.

Su utilidad viene de la de ser en aplicaciones de cálculo y en problemas complejos de naturaleza recursiva. Puede ser utilizada como una alternativa a la estructura repetitiva. Para así poder seguir llamándose a sí misma.

También es útil porque La mayoría de los lenguajes de programación dan soporte a la recursión permitiendo a una función llamarse a sí misma desde el texto del programa.

2.VENTAJAS Y DESVENTAJAS DE LA RECURSIVIDAD.

A continuación en este cuadro comparativo se verán las ventajas y desventajas de la recursividad en el campo de la informática:

VENTAJAS

DESVENTAJAS

• Puede resolver los problemas más complejos en la informática de manera muy eficiente.

• Es muy útil debido a que los lenguajes de programación dan soporte a la acción de recursión haciendo que esta se llame así misma.

• Puede ser utilizada como una alternativa a una estructura informática repetitiva.

• Depura e incrementa los algoritmos recursivos.

• Es muy útil para resolver problemas de cálculos.

• Ayuda a resolver algorítmicos matemáticos.

• Este método puede requerir bastante tiempo que puede ser utilizado para otras cosas.

• La incrementación de los algoritmos repetitivos pueden ser más efectivos que los recursivos.

• Abarca mucho espacio en memoria del sistema.

• Sino se mantiene controlada la función de llamada esta podría generar muchas copias perjudicando la capacidad de almacenamiento del computador.

• Requiere mucho procedimiento en el caso de crear algoritmos matemáticos.

• Requiere que los algoritmos matemáticos estén bien escritos debido a que con un error no se dará el resultado deseado.

3.DISEÑO Y ESCRITURA DE PROGRAMAS RECURSIVOS.

Cuando se diseña una función recursiva es preciso considerar una condición de terminación, porque de lo contrario la función continuaría indefinidamente invocándose a sí misma hasta que se agote la memoria. Los casos triviales definen la solución directamente y los casos "más complicados" se definen utilizando una (o más) llamadas al subprograma que se define. a continuación veremos las diversas etapas de diseño y escritura de programas recursivos:

ESPECIFICACIÓN/PARAMETRIZACIÓN:

Esta etapa especifica los parámetros fundamentales para el diseño del programa recursivo que va a hacerse y define lo que valla a ejecutar según los parámetros escogidos para su construcción estableciendo con que iniciara, las opciones de inicio son: IN, IN OUT y OUT.

ANÁLISIS DE LOS CASOS:

Son distintos los tipos de caso a analizar para crear un programa recursivo y son los siguientes:

• TRIVIALES: que consiste en Determinar para qué valores de los parámetros (bajo qué condiciones), existe una solución directa y cuál es esa solución. Debe existir como mínimo 1 caso trivial, si no el algoritmo no parará de generar subproblemas.

• GENERALES: que consiste en Determinar para qué valores de los parámetros la solución se obtiene por descomposición en subproblemas del mismo tipo. Establecer cómo se calculan las soluciones resueltas las llamadas recursivas correspondientes.

Es importante Comprobar que las llamadas recursivas usan exactamente los parámetros definidos y que el tamaño del problema se reduce o tiende hacia los casos triviales.

DISEÑO DEL ALGORITMO:

En esta etapa ya se agrupa lo diseñado en pasos previos, procurando simplificar el algoritmo cuando sea posible, también se eliminan redundancias y se agrupan casos triviales cuando sea interesante y por último se procura la eliminación de cálculos repetidos originada por el estudio separado de casos.

IMPLEMENTACIÓN:

En esta etapa se implementan las estructuras de datos, adecuadas a la representación de los mismos así como también se construyen los subprogramas para ayudar en funciones secundarias al programa principal. a continuación se vera un ejemplo de programa recursivo completamente implementado:

UNIDAD 14: INTRODUCCIÓN A LAS ESTRUCTURAS DE DATOS DINÁMICAS AVANZADAS: PILAS, COLAS Y ÁRBOLES.

La información que se procesa en la computadora es un conjunto de datos, que pueden ser simples o estructurados. Los datos simples son aquellos que ocupan sólo una localidad de memoria, mientras que los estructurados son un conjunto de casillas de memoria a las cuales hacemos referencia mediante un identificador único.

Debido a que por lo general tenemos que tratar con conjuntos de datos y no con datos simples que por sí solos no nos dicen nada, ni nos sirven de mucho, es necesario tratar con estructuras de datos adecuadas a cada necesidad.

Las estructuras de datos son una colección de datos cuya organización se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos.Una estructura de datos bien organizada debe permitir realizar un conjunto de acciones sobre los datos de tal forma de minimizar el uso de los recursos y el tiempo empleado para efectuar la operación. Y estas pueden ser:

1.PILAS: DEFINICIÓN, ESPECIFICACIONES Y TIPOS.

en el campo de la informática, una pila es una estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos, es decir, la inserción y extracción de elementos de la pila siguen el principio LIFO ya que el último elemento que se agrega a la pila es el primero en salir de la misma.

las especificaciones que deben seguirse para las pilas se reflejan en sus tipos de operaciones disponibles que son las siguientes:

• Apilar: colocar un nuevo dato en la pila. Se lee el puntero para localizar el último elemento, se incorpora a continuación de este y se redirecciona el puntero para que apunte al nuevo dato incorporado.

• Desapilar: extraer un dato de la pila. Se localiza el último dato mediante el puntero, se lee el dato y se redirecciona el puntero al elemento inmediato anterior para que vuelva a apuntar al último dato de la pila

A continuación una representación gráfica de como se ve el proceso de apilar y desapilar(push y pop)

2.COLAS: DEFINICIÓN, ESPECIFICACIONES Y TIPOS.

Una cola (también llamada fila) es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pull por el otro Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), donde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento.Las especificaciones que se ven en las colas son las que van en sus operaciones básicas las cuales son:

• Crear: se crea la cola vacía.

• Encolar: se añade un elemento a la cola. Se añade al final de esta.

• Desencolar: (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.

• Frente: (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

a continuación se ve un ejemplo gráfico en el cual se pueden apreciar las funciones Básicas que se ejecutan en las colas:

También existen diversos tipos de colas que pueden ser llamadas:

• Colas circulares: Es aquella en la cual el sucesor del último elemento es el primero. Por lo tanto, el manejo de las colas como estructuras circulares permite un mejor uso del espacio de memoria reservando para la implementación de las pilas.

• Colas dobles: Permiten realizar las operaciones de inserción y eliminación por cualquiera de sus extremos.

Entre otros tipos secundarios de colas se encuentran:

• Colas de Prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen

• Bicolas de entrada registrada: Son aquellas donde la inserción solo se hace por el final, aunque podemos eliminar al inicio o al final.

• Bicolas de salida restringida: Son aquellas donde solo se elimina por el final, aunque se puede insertar al inicio y al final.

3.ARBOLES: DEFINICIÓN, ESPECIFICACIONES Y TIPOS.

Un árbol es un tipo abstracto de datos (TAD) ampliamente usado que imita la estructura jerárquica de un árbol, con un valor en la raíz y sub-árboles con un nodo padre, representado como un conjunto de nodos enlazados.Una estructura de datos de árbol se puede definir de forma recursiva (localmente) como una colección de nodos (a partir de un nodo raíz), donde cada nodo es una estructura de datos con un valor, junto con una lista de referencias a los nodos (los hijos).Las especificaciones de los árboles son diversas entre las cuales se pueden encontrar:

• Su estructura que está compuesta por:

Raíz: El nodo superior de un árbol.

Hijo: Un nodo conectado directamente con otro cuando se aleja de la raíz.

Padre: La noción inversa de hijo.

Hermanos: Un conjunto de nodos con el mismo padre.

Descendiente: Un nodo accesible por descenso repetido de padre a hijo.

Ancestro: Un nodo accesible por ascenso repetido de hijo a padre.

Hoja: Un nodo sin hijos.

Nodo interno: Un nodo con al menos un hijo.

Grado: Número de subárboles de un nodo.

Brazo: La conexión entre un nodo y otro.

Camino: Una secuencia de nodos y brazos conectados con un nodo descendiente.

Nivel: El nivel de un nodo se define por 1 + (el número de brazos entre el nodo y la raíz).

Altura de un nodo: La altura de un nodo es el número de brazos en el camino más largo entre ese nodo y una hoja.

Altura de un árbol: La altura de un árbol es la altura de su nodo raíz.

Profundidad: La profundidad de un nodo es el número de brazos desde la raíz del árbol hasta un nodo.

Bosque: Un bosque es un conjunto de árboles n ≥ 0 disjuntos.

Rama: Una ruta del nodo raíz a cualquier otro nodo.

• El recorrido de un árbol también es importante a la hora de hacerle especificaciones, las formas de recorrer un árbol son:

Recorrido preorden: consiste en recorrer el árbol en el siguiente orden: raíz, subárbol izquierdo, subárbol derecho.

Recorrido en orden (inorden): consiste en visitar el árbol en el siguiente orden: subárbol izquierdo, raíz, subárbol derecho.

Recorrido postorden: consiste en procesar el árbol en el siguiente orden: subárbol izquierdo, subárbol derecho, raíz.

entre los tipos de arboles se encuentran una gran variedad de estos los cuales son:

• Árbol binario: Un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo.

• Árbol binario de búsqueda: Es aquel que dado un nodo, todos los elementos del lado izquierdo del nodo son menores que los datos de dicho nodo, y todos los elementos del lado derecho del nodo son mayores que los datos de dicho nodo.

• Árbol de Fibonacci: Se llama árbol de Fibonacci a una variante de árbol binario con la propiedad que el orden de un nodo se calcula como la sucesión de Fibonacci.

• Árbol AVL: Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O (log n

• Árbol rojo-negro: Concretamente, es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación.Es complejo, pero tiene un buen peor caso de tiempo de ejecución para sus operaciones y es eficiente en la práctica. Puede buscar, insertar y borrar en un tiempo O(log n), donde n es el número de elementos del árbol.

• Árbol AA: Un árbol AA es un tipo de árbol binario de búsqueda auto-balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente.

4.FUNCIONALIDADES E IMPLEMENTACIÓN BÁSICA DE LAS PILAS ,COLAS Y ARBOLES.

Empezando por la primera veremos de qué forma funcionan y se implementan las ya anteriormente mencionadas pilas, las funciones de estas son para ayudar a recopilar información en la memoria interna de manera temporal hasta que se valla a Desapilar mas adelante. Aquí u ejemplo de implementación de un algoritmo de una pila estática en la base de un arreglo:

private int pila[];

private int top;//indica la posición del último elemento insertado

private int capacidad;

public PilaEstatica(int cap){

capacidad=cap;

pila=new int[capacidad];

top=-1;

}

public boolean estaVacia(){

return(top==-1);

}

public boolean estaLlena(){

return((top+1)==capacidad);

}

public void apilar(int elemento){

if(estaLlena()==false)

pila[++top]=elemento;

else

System.out.println("Desbordamiento superior, no se puede apilar");

}

public int desapilar(){

if(estaVacia()==false){

return pila[top--];

}

else{

System.out.println("Desbordamiento inferior, no se puede desapilar");

}

return -1;

}

public static void main (String args[]){

PilaEstatica pilita=new PilaEstatica(5);

pilita.apilar(1);

pilita.apilar(12);

pilita.apilar(3);

int r=pilita.desapilar();

System.out.println("El dato eliminado es "+r);

boolean b=pilita.estaVacia();

boolean c=pilita.estaLlena();

System.out.println("¿Está vacia la pla? "+b);

System.out.println("¿Está llena la pla? "+c);

}

A continuación veremos el proceso de cambio de agregar y eliminar elementos de una cola, en este caso se planea agregar el elemento 15 al final y se planea quitar el elemento 26 del frente para darle espacio al elemento 20

Para finalizar se verá por ultimo la funcionalidad y la implementación de un árbol, la funcionalidad de un árbol es la de En Las Operaciones funcionales sobre árboles, veremos como los algoritmos de árboles pueden diseñarse en términos de estas operaciones, existen varias formas de implementar un árbol pero en este caso vamos por el ejemplo de implementación matricial:

La implementación matricial Sea A un árbol en el cual los nodos se etiquetan 0, 1,2,..., n-1, es decir, cada nodo contiene un campo de información que contendrá estos valores. La representación más simple de A que soporta la operación PADRE es una matriz lineal P en la cual el valor de P[i] es un valor o un cursor al padre del nodo .La raíz de A puede distinguirse dándole un valor nulo o un valor a él mismo como padre como se ve a continuación:Por ejemplo., podemos usar un esquema de cursores donde P[i]=j si el nodo j es el padre del nodo y P[i]=-1 (suponemos que NODO_NULO=-1) si el nodo i es la raíz. entonces se leería:

#define MAXNODOS 100 /*Por ejemplo*/

#define NODO_NULO -1

typedef int nodo; /*Indica una casilla de la matriz*/

typedef int *ARBOL;

Con esto hemos llegado al final del blog, antes de terminar es importante destacar que si se puede llegar a pensar en algo esa cosa también puede llegar a ser programada por una persona, cualquiera en estos días puede ser programador si se hace el esfuerzo no importa la edad o el género, si te encanta la informática nada te será difícil y como dijo una vez un sabio “nada es imposible para el que lucha”.

Buscar este blog

unidades 11, 12, 13 y 14 algorítmica y programación