12_Programacion_Dinamica
-
Upload
alexis-sovero-camacuari -
Category
Documents
-
view
221 -
download
0
description
Transcript of 12_Programacion_Dinamica
![Page 1: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/1.jpg)
Company
LOGO
Programación Dinámica
Algoritmos y Estructuras de Datos
![Page 2: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/2.jpg)
Agenda
1. Punteros
2. Estructuras autoreferenciadas
3. Asignación dinámica de memoria
4. Listas enlazadas
![Page 3: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/3.jpg)
Punteros
Su valor es una dirección de
memoria.
Las variables normales contienen un valor específico.
Los punteros almacenan la
dirección de una variable que tiene
un valor específico.
Sirven para simular parámetros por
referencia.
![Page 4: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/4.jpg)
Punteros
![Page 5: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/5.jpg)
Declarar punteros
Sintaxis Definir *mi_puntero como Entero;
Definición Declara un puntero hacia un Entero.
Se pueden definir punteros hacia cualquier tipo de dato.
![Page 6: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/6.jpg)
Punteros y operadores
Operador de dirección (&)
Devuelve la dirección de memoria del operando
Ejemplo Declarar un_numero como Entero;
Declarar *un_puntero como Entero;
un_numero <- 5;
un_puntero <- &un_numero;
//un_puntero obtiene la dirección de un_numero
![Page 7: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/7.jpg)
Punteros y operadores
![Page 8: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/8.jpg)
Punteros y operadores
Operador de indirección(*)
Nos permite obtener el valor almacenado en la dirección que tiene asignada.
*un_puntero nos devolvería un_numero, dado que un_puntero apunta hacia un_numero.
Ejemplo Para asignar:
*un_puntero <- 7;
//Ahora el valor de un_numero es 7
![Page 9: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/9.jpg)
El ejemplo
![Page 10: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/10.jpg)
Punteros y Estructuras
Operador punto (.)
Definir una_carta como carta;
Escribir una_carta.signo;
Operador flecha (<-)
Definir *puntero_carta como carta;
puntero_carta <- &una_carta;
Escribir puntero_carta->signo;
Equivalente a:
Escribir (*puntero_carta).signo;
![Page 11: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/11.jpg)
Parámetros por referencia
Estructuras de Datos Dinámicas: Crecen o se contraen durante la ejecución
Listas enlazadas
• Inserciones y eliminaciones sin restricciones.
Pilas
• Inserciones y eliminaciones sólo en la parte superior.
Colas
• Inserciones en la parte posterior y eliminaciones en la parte superior.
Árboles binarios
• Búsqueda y ordenamiento de alta velocidad y eliminación de duplicados eficiente
![Page 12: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/12.jpg)
Estructura auto-referenciada
Contienen un puntero a otra
estructura
Esta otra estructura es del
mismo tipo.
Pueden enlazarse
mutuamente.
Lo que permite formas
estructuras de datos.
Estas estructuras
terminan con un puntero NULO.
![Page 13: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/13.jpg)
Estructura auto-referenciada
![Page 14: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/14.jpg)
Estructura auto-referenciada
Sintaxis Estructura nodo
Definir dato como Entero;
Definir *puntero_siguiente como nodo;
FinEstructura
Enlace Es el vínculo entre un nodo y otro.
puntero_siguiente apunta hacia un dato del tipo nodo.
![Page 15: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/15.jpg)
Asignación dinámica de
memoria
Definición Obtiene y libera memoria durante la ejecución del programa.
Función reservar()
Reserva memoria para un puntero.
Definir *puntero_nodo como nodo;
reservar(puntero_nodo);
Función liberar()
Libera la memoria reservada por la función reservar.
liberar(puntero_nodo);
![Page 16: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/16.jpg)
Listas enlazadas
Colección lineal de estructuras auto-referenciadas, llamadas nodos, conectadas
por enlaces mediante punteros.
Se acceden mediante
un puntero al primer elemento de la lista.
Los siguientes nodos se
acceden a través de
los enlaces.
El último elemento
tiene como enlace un puntero NULO.
![Page 17: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/17.jpg)
Listas enlazadas
A diferencia de un vector, soporta un
número indeterminado de elementos.
A diferencia de un vector, es fácil
mantenerla ordenada.
Existen varios tipos: Simples, dobles, circulares, etc.
Nosotros trabajaremos con LISTAS
ENLAZADAS SIMPLES
Comienzan con un puntero al primer nodo,
terminan en puntero nulo y se recorren en
una dirección
![Page 18: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/18.jpg)
Un problema
Diseñe un algoritmo que permita
manipular una lista de caracteres.
Debe permitir ingresar caracteres en la lista
en orden alfabético.
Debe permitir eliminar cualquier carácter de la
lista.
![Page 19: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/19.jpg)
Plan de acción
El usuario ingresa una opción
En caso la opción sea 1, se ejecuta el procedimiento de inserción
En caso la opción sea 2, se ejecuta el procedimiento de eliminación
• Sólo si la lista no está vacía
En caso la opción sea 3, se termina la ejecución del programa
![Page 20: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/20.jpg)
Estructura jerárquica
Módulo Principal
Insertar carácter en
orden
Eliminar carácter
Verificar que lista esté
vacía
Mostrar contenido de
la lista
![Page 21: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/21.jpg)
Definir Estructuras
Nodo en Lista Enlazada
Estructura nodo_lista
Definir caracter como
Caracter;
Definir *puntero_siguiente
como nodo_lista;
FinEstructura
![Page 22: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/22.jpg)
Módulo Principal
Proceso principal
Definir *puntero_inicio como nodo_lista;
//Variables para opción y caracteres ingresados
Leer opcion;
Mientras opcion <> 3 Hacer
Segun opcion Hacer
1:
Leer caracter_ingresado;
insertar(puntero_inicio, caracter_ingresado);
2:
es_una_lista_vacia <- esta_vacia(puntero_inicio);
Si ~es_una_lista_vacia Entonces
Leer caracter_ingresado;
caracter_eliminado <- suprimir(puntero_inicio, caracter_ingresado);
FinSi
FinSegun
Leer opcion;
FinMientras
FinProceso
![Page 23: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/23.jpg)
Insertar elemento
Reservar memoria para el nuevo nodo
Ubicar entre que nodos hay que colocar el nuevo elemento recién creado
En caso haya colocarlo en primera posición, hay que cambiar el valor del puntero al primer nodo.
En caso esté al medio, la inserción se realiza modificando las direcciones de los punteros.
![Page 24: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/24.jpg)
Insertar elemento
![Page 25: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/25.jpg)
Insertar elemento
SubProceso insertar (puntero_inicio por Referencia, caracter por Valor)
Definir *puntero_nuevo como nodo_lista;
Definir *puntero_previo como nodo_lista;
Definir *puntero_actual como nodo_lista;
reservar(puntero_nuevo);
puntero_nuevo->caracter <- caracter;
puntero_nuevo->puntero_siguiente <- NULO;
puntero_previo <- NULO;
puntero_actual <- puntero_inicio;
Mientras (puntero_actual <> NULO & caracter > puntero_actual->caracter) Hacer
puntero_previo <- puntero_actual;
puntero_actual <- puntero_actual->puntero_siguiente;
FinMientras
Si puntero_previo = NULO Entonces
puntero_nuevo->puntero_siguiente <- puntero_inicio;
puntero_inicio <- puntero_nuevo;
Sino
puntero_previo->puntero_siguiente <- puntero_nuevo;
puntero_nuevo->puntero_siguiente <- puntero_actual;
FinSi
FinSubProceso
![Page 26: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/26.jpg)
Eliminar elemento
La eliminación implica remover los enlaces al nodo a eliminar
Al eliminar, necesitamos liberar la memoria reservada para el nodo eliminado.
Si el carácter a eliminar está en la primera posición, es necesario cambiar el puntero al primer nodo.
Debemos informar al programa si el nodo a eliminar fue encontrado en la lista.
![Page 27: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/27.jpg)
Eliminar elemento
![Page 28: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/28.jpg)
Eliminar elemento
Funcion caracter_eliminado <- suprimir (puntero_inicio por Referencia, caracter por Valor)
Definir *puntero_previo, *puntero_actual, *auxiliar como nodo_lista;
Si caracter = puntero_inicio->caracter Entonces
auxiliar <- puntero_inicio;
puntero_inicio <- puntero_inicio<-puntero_siguiente;
liberar(auxiliar);
caracter_eliminado <- caracter;
Sino
puntero_previo <- puntero_inicio;
puntero_actual <- puntero_inicio->siguiente;
Mientras puntero_actual <> NULO & puntero_actual->caracter <> caracter Hacer
puntero_previo <- puntero_actual;
puntero_actual <- puntero_actual->siguiente;
FinMientras
Si puntero_actual <> NULO Entonces
auxiliar <- puntero_actual;
puntero_previo->puntero_siguiente <- puntero_actual->puntero_siguiente;
liberar(auxiliar);
caracter_eliminado <- caracter;
FinSi
FinSi
FinFuncion
![Page 29: 12_Programacion_Dinamica](https://reader034.fdocumento.com/reader034/viewer/2022052603/563db895550346aa9a95046d/html5/thumbnails/29.jpg)
Mostrar contenido
SubProceso mostrar_lista(puntero_actual)
Si puntero_actual = NULO Entonces
Escribir "La lista está vacía";
Sino
Mientras puntero_actual <> NULO Hacer
Escribir puntero_actual->caracter, "-->", Sin Saltar;
puntero_actual <- puntero_actual->puntero_siguiente;
FinMientras
Escribir "NULO";
FinSi
FinSubProceso