Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

INFO088_2018_08

No description
by

Erick Araya

on 28 July 2018

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of INFO088_2018_08

LISTAS DOBLEMENTE ENLAZADAS
Inserción en un ABB
Estructuras en C++
Inserción en un ABB
LISTAS DOBLEMENTE ENLAZADAS
Ejercicio

ESTRUCTURAS DINÁMICAS PARTE 5
Apunte 08
Taller de Ingeniería: Estructura de Datos y Algoritmos
Se desea comprar en la feria duraznos y plátanos. Para ello debe hacer uso de la estructura Fruta, cuya definición es:
Escriba un programa que, haciendo uso de la estructura anterior, solicite al usuario el número de kilos y el precio por kilo de las frutas duraznos y plátanos. El programa debe indicar cuál es el total a pagar por la compra. Un ejemplo de E/S se muestra a continuación:
Se propone el siguiente main():
LISTAS DOBLEMENTE ENLAZADAS
Solución:
El código para la inserción del primer elemento de la lista:
Solución (cont.)
Ejemplo:
Los pasos a seguir para agregar un nuevo nodo a un árbol binario de búsqueda son los siguientes:
Cuando la lista tiene al menos un nodo, y se desea insertar uno nuevo a la derecha:
LISTAS DOBLEMENTE ENLAZADAS
Para conectar el nuevo nodo a la derecha (cola) de la lista:
Se usa el mismo puntero p para conectar el último nodo de la lista con el nuevo nodo:
El campo next del nuevo nodo debe quedar apuntando a
nullptr
:
Ejercicio 2 : Desarrollar un programa completo para la inserción de nodos por la derecha de una lista doblemente enlazada. El programa debe imprimir la lista de la cabeza a la cola y viceversa. Un ejemplo de E/S se muestra a continuación:
Para lo anterior, se propone el siguiente main():
LISTAS DOBLEMENTE ENLAZADAS
Ejercicios
1. Asuma que se tiene una lista doblemente enlazada ORDENADA DE MENOR A MAYOR DE IZQUIERDA A DERECHA, con los siguientes valores iniciales:
10 - 20 - 30 - 40 - 50.
Escriba una función que solicite un entero cualquiera y, dependiendo de su magnitud, ha de ser insertada en la lista doblemente enlazada. El programa principal ha de inicializar la lista con los valores anteriores, imprimir la lista en ambos sentidos (de cabeza a cola y viceversa), antes de solicitar el nuevo valor, el cual ha de ser agregado a la lista SOLO SI NO SE ENCUENTRA. Finalmente se imprimirá la lista en ambos sentidos.
Solución
Solución
LISTAS DOBLEMENTE ENLAZADAS
2. Para la misma lista doblemente enlazada anterior, escriba una función que elimine un elemento (si existe) ingresado por el usuario.
El código:
Ejercicio 1 : Desarrollar un programa completo para la inserción de nodos por la izquierda de una lista doblemente enlazada. El programa debe imprimir la lista de la cabeza a la cola y viceversa. Un ejemplo de E/S se muestra a continuación:
El main:
Inserción en un ABB
El nuevo main():
Eliminación de un nodo en un ABB
Para enfrentar el problema:
Eliminación de la raíz en un ABB
Si asumimos que la raíz tiene al menos un descendiente por lado, al eliminarla debe permanecer la coherencia de los enlaces
TAREA
Escriba un programa completo que, dado un árbol binario de búsqueda, ingresado y almacenado en un arreglo de 20 elementos (usted puede definir el método de ingreso de los 20 elementos enteros), ha de hacer lo siguiente:
* Verificar que los elementos ingresados forman realmente un árbol binario equilibrado. Si no es así, solicita el reingreso de los datos nuevamente, hasta que se cumpla ña condición de equilibrio
LISTAS DOBLEMENTE ENLAZADAS
Sobrecarga de Funciones:
Proceso mediante el cual varias funciones pueden compartir el MISMO NOMBRE, siempre y cuando sus declaraciones de parámetros sean DIFERENTES
Para el caso cuando no existen nodos en la lista:
LISTAS DOBLEMENTE ENLAZADAS
Solución (cont):
LISTAS DOBLEMENTE ENLAZADAS
Sobrecarga de Funciones:
Cuando la lista contiene, al menos un nodo:
Para recorrerla, deben haber dos funciones:
Desde la cabeza a la cola,
Desde la cola a la cabeza,
LISTAS DOBLEMENTE ENLAZADAS
Cuando se crea un nuevo nodo,
se asigna el dato al campo valor...
Como es el primer nodo asignado a la lista, ambos campos puntero del nodo señalarán a nullptr. Además, los punteros cabeza y cola señalarán al nuevo nodo
Se asumirá ahora que la lista va insertando nodos por la derecha
Al iniciar la lista, el puntero cabeza señala a
nullptr,
al igual que el puntero cola
Lista
Nuevo nodo
Primero se asigna el dato al campo val:
Finalmente, la cola debe cambiar, porque se ha agregado un nuevo nodo:
LISTAS DOBLEMENTE ENLAZADAS
El código para la inserción del nuevo nodo al extremo derecho de la lista:
Note que se ha usado la característica de sobrecarga para la función creaNodo()
Y se necesitará la función:
Esta función decidirá si el nuevo nodo se agrega a una lista vacía o a una no vacía
2. Para la misma lista doblemente enlazada anterior, escriba una función que elimine un elemento (si existe) ingresado por el usuario.
1. Comparar la clave a insertar con la raíz del árbol. Si es mayor, se sigue con el subárbol derecho. Si es menor, se continúa con el subárbol izquierdo.
No es tan simple como la inserción
Puede darse el caso de la recolocación de nodos en el árbol
Inserción en un ABB
El código:
Verifique el algoritmo insertando otros nodos
Busque el nodo que se desea borrar, manteniendo un puntero a su padre
La solución consiste en sustituir la información de la raíz (o de un nodo con más descendencia) por el de una de las hojas. No puede ser cualquier hoja:
* Utilizar el algoritmo dado en clases para imprimir el árbol
* Desarrollar un algoritmo COMPLETO que permita la eliminación de uno de los nodos, independiente de su ubicación. Esto es, el nodo a eliminar podría ser, incluso, la raíz. Para ese caso, es importante que el árbol resultante no pierda sus propiedades origunales. Para ello, ha de solicitar al usuario ingrese el valor a eliminar, o finalizar. Cada vez que elimine un nodo ha de mostrarse el árbol resultante. Si el elemento a eliminar no existe debe indicarlo y solicitar el ingreso de un nuevo nodo a eliminar (o finalizar). Cuando ya no hayan nodos a eliminar, debe indicarlo.
* Debe formar grupos de a tres estudiantes como máximo.
* NO SE ACEPTAN TAREAS INDIVIDUALES
* Plazo de entrega:
7 de Agosto
. Enviar tareas al correo del profesor. Indicar en un documento los integrantes y la labor realizada por cada uno.
Si el nodo existe, puede darse 3 casos posibles:
Eliminación de un nodo en un ABB
2.Repetir sucesivamente el paso 1 hasta que se cumpla que el subárbol derecho, o el subárbol izquierdo, es igual a vacío, en cuyo caso se procederá a insertar el elemento en el lugar que le corresponde.
EJEMPLO
Suponga que tiene un árbol creado por los siguientes datos:
{50,40,30,80,75,60,90,20,35,25,70,15,45,85,5}
Recuerda cómo crearlo?
Este código lo arreglaremos para que se inserte un nuevo nodo
Por simplicidad, se asumirá que el nodo a insertar es el 55 (sin interacción)
La nueva función, insertaNodo(raiz,55) insertará sólo si el nodo NO EXISTE en el árbol.
Primero pregunta si el dato a insertar es menor que el nodo apuntado por el puntero.
Si se cumple, primero pregunta si el puntero a la izquierda es vacío (nullptr). Si lo es, crea un nuevo nodo. Si no, llama a la función insertaNodo() (recursivamente!!), donde el puntero es reemplazado por el puntero left del nodo.
Si el dato a insertar no es menor que el nodo apuntado por el puntero, pregunta si el dato a insertar es mayor que el nodo apuntado por el puntero
Si se cumple, primero pregunta si el puntero a la derecha es vacío (nullptr). Si lo es, crea un nuevo nodo. Si no, llama a la función insertaNodo() (recursivamente!!), donde el puntero es reemplazado por el puntero right del nodo.
Finalmente, si el dato a ingresar ya existe, rechaza el ingreso (no es el caso para el 55).
a) Si el nodo a borrar no tiene hijos, se elimina sin problemas
b) Si el nodo a borrar tiene un único hijo, el hijo sustituye a su padre en la posición
c) Si el nodo a borrar tiene dos hijos, se busca el máximo de la rama izquierda, o el mínimo de la rama derecha. Se sustituye el nodo a borrar por el nodo encontrado
Además, debe mantenerse la estructura de un ABB
La mayor de las claves menores al nodo que se borra
La menor de las claves mayores al nodo que se borra
Inserción en un ABB
Ejercicio
Basado en la descripción anterior, implementar en c++ la función insertaNodo(raiz,55) . Pruébela también para otros valores.
Eliminación de un nodo en un ABB
Desarrolle la función eliminaNodoBasico(nodo* raiz, int valor) que, dado un árbol almacenado en el arreglo
Ejercicio
ha de eliminar un nodo hoja, por ejemplo, el nodo 70
Esto es, el main() será:
Full transcript