Computación ii 324-1-estructuras dinamicas-con enlaces
-
Upload
isbelia-pelayo -
Category
Documents
-
view
1.465 -
download
4
Transcript of Computación ii 324-1-estructuras dinamicas-con enlaces
![Page 1: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/1.jpg)
Computación II - 324
![Page 2: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/2.jpg)
Computación II - 324
C
a
t
e
g
o
r
i
a
s
Bajo Nivel
Lenguaje máquina
Lenguaje Ensamblador
![Page 3: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/3.jpg)
Computación II - 324
C
a
t
e
g
o
r
i
a
s
Alto Nivel
Cuarta Generación y Quinta Generación
![Page 4: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/4.jpg)
Computación II - 324
Programación Estructurada
Para resolver problemas de cierta envergadura se
utiliza normalmente la técnica de diseño que se conoce
con el nombre de diseño modular.
El problema se divide en subproblemas que se puedan
resolver con un conjunto de subprogramas que tengan
una cierta cohesión.
Al conjunto de subprogramas que resuelve un
subproblema se le llama módulo funcional.
Un módulo puede hacer uso de un subprograma de otro
módulo si éste aparece en su interfaz
![Page 5: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/5.jpg)
Computación II - 324
Programación Estructurada
Un interfaz es un conjunto de cabeceras de
subprogramas que pueden ser utilizados por otros
módulos.
Los interfaces aparecieron para minimizar el
acoplamiento entre los módulos. Se dice que es
conveniente un diseño con acoplamiento débil entre
módulos.
La interfaz sólo tienen que aparecer los subprogramas
principales del módulo y no los subprogramas que son
utilizados para implementar los subprogramas principales
![Page 6: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/6.jpg)
Computación II - 324
Programación Estructurada
Esta descomposición se conoce con el nombre de
descomposición funcional.
Posteriormente aparece un nuevo tipo de
descomposición o abstracción que se conoce con el
nombre de abstracción de datos
![Page 7: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/7.jpg)
Computación II - 324
Abstracción
La técnica de la abstracción no permite acceder
directamente a la representación de la estructura.
![Page 8: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/8.jpg)
Computación II - 324
Abstracción
La abstracción: Separa la especificación (qué hace) de
la implementación (cómo lo hace). Los usuarios de un
TAD no necesitan conocer sus detalles de
implementación (Cómo lo hacen). Como consecuencia,
aporta las ventajas de:
Extensibilidad del código: Es posible modificar y
mejorar la implementación del TAD sin afectar a los
demás módulos que lo utilizan.,
b) Aumenta la facilidad de uso.
c) Aumenta la legibilidad del código que usa el TAD.
![Page 9: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/9.jpg)
Manejo de memoria
5 caracteres
Computación II - 324
La asignación estática de memoria reserva la cantidad
necesaria para almacenar los datos de cada estructura en
tiempo de compilación
![Page 10: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/10.jpg)
Tipo de datos en Pascal
5 caracteres
Computación II - 324
Tipo Rango Espacio en memoria
Char Carácter ASCII 1 byte
Byte 0 a 255 1 byte
Integer -32768 a 32767 2 bytes
Real 1 E -38 a 1 E+38 6 bytes
Boolean True – False 1 byte
Shortint -128 a 127 1 byte
Word 0 a 65535 2 byte
Longint -2147483648 a
214748364
4 byte
String Cadena de 255 caracteres Hasta 255 bytes
![Page 11: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/11.jpg)
Manejo de memoria
5 caracteres
Computación II - 324
No se almacenan en memoria estática.
• Los objetos correspondientes a procedimientos o funciones
recursivas, ya que en tiempo de compilación no se sabe el
número de variables que serán necesarias.
• Las estructuras dinámicas de datos tales como listas,
árboles, etc. ya que el número de elementos que la forman no
es conocido hasta que el programa se ejecuta.
![Page 12: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/12.jpg)
Computación II - 324
Uso de Procedimiento y funciones
Parámetros Valor
No devuelve valores…no antecede la palabra VAR
El compilador crea una copia del dato y lo almacena en
la variable parámetro que lo recibe. Dentro de la
función o procedimiento se trabaja con la copia
obtenida, no importando las operaciones que se
realicen con la copia, la variable introducida como
parámetro, no será afectada en su valor inicial al
terminar el proceso. Su sintaxis es la siguiente:
PROCEDURE Identificador (Ide1, Ide2: Tipo; Ide3: Tipo);
![Page 13: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/13.jpg)
Computación II - 324
Ejemplo
program Ejemplo;
uses crt;
var nombre:string;
Procedure pasar(nombre1:string);
begin (* cambiando parametro *)
nombre1:='maria elena';
end;
BEGIN
clrscr; (* cargando variable *)
nombre:='juan fernando';
pasar(nombre);
(* desplegando *)
writeln('nombre : ',nombre);
readln;
END.
Valor de la variable nombre en el Procedimiento Pasar ?
Valor de la variable nombre en el Programa Principal?
![Page 14: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/14.jpg)
Computación II - 324
Parámetro Por Referencia
Se reciben/envían con la palabra clave VAR.
Se trabaja en la misma posición de memoria de la
variable original, es decir, se referencian.
Cualquier cambio que se realice a la variable parámetro,
en el procedimiento o función también se le estará haciendo
a la variable original.
PROCEDURE Identificador (VAR Ide1: Tipo);
![Page 15: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/15.jpg)
Computación II - 324
Ejemplo Ejemplo
program Ejemplo;
uses crt;
var nombre:string; edad:integer;
procedure pasar(nombre1:string;
var edad1:integer);
begin (* cambiando parametro *)
nombre1:='maria elena';
edad1:=50;
end;
BEGIN
clrscr; (* cargando variable *)
nombre:='juan fernando';
Edad:= 30;
(* mandando a procedimiento *)
pasar(nombre,edad);
(* desplegando *)
writeln('nombre : ',nombre);
writeln(‘edad : ',edad);
readln;
END.
Valor de la variables nombre y edad?
http://www.pcg.ull.es/edapplets/DataControlJApplet/pasoparametros.html
![Page 16: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/16.jpg)
Computación II - 324
Punteros en Pascal.
Es una variable cuyo valor es una dirección de memoria donde se
encuentra la variable dinámica apuntada
![Page 17: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/17.jpg)
sComputación II - 324
Punteros en Pascal.
En PASCAL los punteros se declaran con el símbolo ^.
Declarar las variables tipo puntero que sean necesarias
(Dentro de la sección VAR).
![Page 18: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/18.jpg)
Computación II - 324
Se pueden definir tipos punteros o definir variables de tipo
puntero:
Type
ptr = ^integer;
Var
p: ptr;
q: ^real;
Ejemplo
p^:= 5 . Asigno el valor 5 a la variable apuntada por p.
writeln(p^). Imprime el valor de la variable apuntada por p.
![Page 19: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/19.jpg)
sComputación II - 324
Creación y destrucción de variables dinámicas
El Procedimiento NEW(), asigna memoria a la variable puntero, en
caso de que el PC no obtenga memoria para alocar el pedido, al
puntero se le asignara la dirección NIL, cuyo significado es "nada", es
decir el puntero no apunta a ningún sector de la memoria.
El Procedimiento DISPOSE(), Libera memoria reservada por a la
variable puntero mediante el procedimiento DISPOSE()
![Page 20: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/20.jpg)
Computación II - 324
Ejemplo.
New (puntero).
Asigna memoria a la variable apuntada por puntero.
Gráficamente.
![Page 21: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/21.jpg)
Computación II - 324
Ejemplo.
Representación Gráfica.
![Page 22: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/22.jpg)
Computación II - 324
Diagrama sintáctico. Tipo de dato
de dato
predefinido
en pascal
Tipo de dato
puntero.
Contiene una
dirección de
memoria
![Page 23: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/23.jpg)
Computación II - 324
Ejemplo.
Dispose (puntero).
Libera la memoria asociada a la variable referida (la que contiene el dato).
Deja indefinido el puntero.
Gráficamente.
![Page 24: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/24.jpg)
Computación II - 324
Ejemplo.
Type
Puntx=^Real;
Var
P:Puntx; <apunta a direcciones de memoria que contienen valores de tipo real.>
Estas declaraciones aún no crean nada en memoria hasta cuando el programa se ejecute el procedimiento NEW.
NEW(P) , genera lo siguiente en memoria.
P^
P--
![Page 25: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/25.jpg)
Computación II - 324
Puntero.
NEW(P) , genera lo siguiente en memoria. Una celda vacía
apuntada por P y contendrá valor real.
P^
P--
P^:= 355 <asigna el valor 355 en la celda de memoria
apuntada por P^.
P--
355
![Page 26: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/26.jpg)
Computación II - 324
TYPE
TApcar=^char;
VAR
Apcar:TApcar;
BEGIN
New(Apcar);
Readln(Apcar^);
Apcar^:= Pred(Apcar^);
END.
![Page 27: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/27.jpg)
Computación II - 324
Operaciones con Puntero.
Las operaciones permitidas para esta nueva variables son:
Asignación
Lectura
Escritura
Todas las operaciones legales que se puedan realizar con dicho
tipo declarado (entero, string, char, etc).
![Page 28: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/28.jpg)
Computación II - 324
Operaciones con Punteros (^).
Ejemplos.
Asignación:
Los cambios que se efectúen con la variable Apnum1 o la
Variable Apnum2 afectan a ambas, son indistintas.
El espacio en memoria que se reservo con la variable Apnum1
Sigue ocupado en memoria, lo conveniente es liberar este
Espacio antes de realizar la asignación.
![Page 29: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/29.jpg)
Computación II - 324
TYPE
TApnum=^integer;
VAR
Apnum1,Apnum2:TApnum;
BEGIN
New(Apnum1);New(Apnum2); { inst. 1}
Apnum1^:=2;Apnum2^:=4; {inst. 2}
Apnum2^:=Apnum1^ + Apnum2^; {inst. 3}
Apnum1^:=Apnum2^ DIV 2 ; {inst. 4}
END.
![Page 30: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/30.jpg)
Computación II - 324
New(Apnum1);New(Apnum2); { inst. 1}
Apnum1 Apnum2
Apnum1^:=2;Apnum2^:=4; {inst. 2}
Apnum1 Apnum2
2 4
![Page 31: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/31.jpg)
Computación II - 324
6
Apnum2
Apnum1
3
Apnum2^:=Apnum1^ + Apnum2^; {inst. 3}
Apnum1^:=Apnum2^ DIV 2 ; {inst. 4}
![Page 32: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/32.jpg)
Computación II - 324
Operaciones con Punteros (^).
Ejemplos.
Comparación:
Apnum1= Apnum2
La Comparación resulta con un valor TRUE, ya que Apnum1 y
Apnum2 contienen direcciones de memoria diferentes.
![Page 33: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/33.jpg)
Computación II - 324
Operaciones con Punteros (^).
Ejemplos.
Asignación:
Apnum1: = Apnum2
![Page 34: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/34.jpg)
Computación II - 324
Operaciones con Punteros (^).
• Comparación: Se comparan las direcciones, no los Contenidos de los datos apuntados o referenciados.
Apnum1=Apunum2 { Apnum1,Apnum2 son datos tipo ^}.
• Asignación: Se asignan las direcciones entre sí, no
el contenido de los datos apuntados.
Apnum1:= Apnum2 { Apnum1 y Apnum2 tienen la misma
dirección por lo tanto apuntan al mismo
dato.}.
![Page 35: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/35.jpg)
Computación II - 324
Valor Nil .
Palabra reservada en el Lenguaje Pascal.
Es un valor que puede asignarse solo a las variables puntero
e indica que no están apuntando a ningún valor .
Nil puede ser utilizado por cualquier puntero, es decir,
independiente del tipo de dato referenciado (apuntado) por la
variable tipo puntero.
Ejemplo
Apnum1:= nil
![Page 36: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/36.jpg)
Computación II - 324
Otras Estructuras de Datos…
Lineales: Listas enlazadas, Listas Doblemente enlazada, Pilas,
Colas.
No lineales: árboles , grafos.
![Page 37: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/37.jpg)
Computación II - 324
Nodos.
Es una estructura creada por el programador, para poder
crear otras estructuras tales cómo Listas o Colas en memoria dinámica.
Un nodo posee un puntero que permite almacenar una dirección de otro nodo; es decir permite
enlazar múltiples nodos entre sí y hacer nuestras estructuras más complejas y alocarlas en memoria dinámica.
![Page 38: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/38.jpg)
Computación II - 324
Nodo.
Ejemplo. Definición de un nodo.
TYPE TipoLista =^ TipoNodo; TipoNodo = Record Info:TipoInfo; Siguiente:TipoLista END;
Se declara un tipo de puntero llamado TipoLista que apunta a un registro TipoNodo.
Donde TipoNodo esta definido como un registro que almacenará información y un campo siguiente. Siguiente es un puntero a un tipo de dato TipoLista. Esta forma de definición recursiva nos permite construir los nodos.
![Page 39: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/39.jpg)
Computación II - 324
Listas Enlazadas.
Es un conjunto de elementos llamados nodos en los que cada
uno de ellos contiene un dato y también la dirección del siguiente nodo. Cada nodo apunta al siguiente nodo, excepto el último nodo que apunta a NIL. Esto indica que cada nodo ocupa
posiciones no contiguas en memoria.
El orden de los mismos se establece mediante punteros.
![Page 40: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/40.jpg)
Definición de estructura recursiva de nodos
Computación II - 324
Declaración de una estructura de nodos.
![Page 41: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/41.jpg)
Computación II - 324
Una Lista enlazada requiere, como minímo de una
refrencia al primer nodo
Una lista vacía el primer nodo apunta a null
Operaciones básicas con listas
Crear Lista
Recorrer lista
Inserta un elemento (inicio-final-una posición dada)
Borrar un elemento
Búsqueda de un elemento
Característica de las listas
Estructura recursiva de nodos
<<En estas operaciones es fundamental el movimientos de los punteros>>
![Page 42: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/42.jpg)
Computación II - 324
Para acceder al primer nodo de una lista es necesario el
uso de un puntero externo y posteriormente se continua
con siguiendo la cadena de puntero.
Operaciones con Listas enlazadas
(Puntero Externo)
Punteros enlazando al siguiente nodo Puntero del último nodo
apunta a nil
![Page 43: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/43.jpg)
Computación II - 324
Cualquier operación con cualquier tipo de lista implica
redireccionar los punteros de los nodos involucrados o
afectados por la operación.
Operaciones Con listas enlazadas
Cualquier operación con cualquier tipo de lista implica
redireccionar los punteros de los nodos involucrados o
afectados por la operación.
Para la operación de inserción se debe determinar el
lugar dentro de la lista.
![Page 44: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/44.jpg)
Operación Inserción un elemento en una lista
Esta operación consiste en agregar un nuevo nodo
a la lista. Se considerar tres casos:
Insertar un nodo al inicio.
Insertar un nodo antes o después de cierto nodo.
Insertar un nodo al final
Computación II - 324
![Page 45: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/45.jpg)
Computación II - 324
Operación Inserción un elemento en una lista
Para la inserción es la creación de nodo, determinar el lugar dentro de
la lista y realizar el movientos de punteros requerido.
En el ejemplo anterior, observamos un nuevo nodo denominado tmp (al
que se asigna un valor x en el campo icorrespondiente a datos), el cual va
ser insertado en la posición posterior dada (apuntada por el nodo actual).
Observamos que para incluirlo en la lista, el apuntador siguiente de tmp,
lo movemos al la misma dirección que apunta el nodo actual y la posición
siguiente del nodo actual se mueve al nodo tmp.
![Page 46: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/46.jpg)
Computación II - 324
Operación eliminar elemento en una lista
La operación consiste en eliminar un nodo de la
lista, redefiniendo las punteros que correspondan.
Se pueden presentar cuatro casos:
Eliminar el primer nodo.
Eliminar el último nodo
Eliminar un nodo con cierta información.
Eliminar el nodo anterior o posterior al nodo
cierta con información.
![Page 47: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/47.jpg)
Computación II - 324
Operación eliminar elemento en una lista
Esta operación consiste en un simple cambio de una
referencia.
En el dibujo para eliminar el nodo con contenido x, hacemos que la referencia siguiente del nodo actual apunte
apunte al nodo b. Con eso queda alislado el nodo b.
![Page 48: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/48.jpg)
Computación II - 324
Búsqueda de un elemento en una lista
Esta operación consiste en visitar cada uno de los
nodos, tomando al campo siguiente como puntero
al siguiente nodo a visitar.
Una lista enlazada con cabecera es una lista enlazada que
contiene un nodo especial, llamado nodo cabecera, al
principio de la lista.
Listas especiales con nodo cabecera
![Page 49: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/49.jpg)
Computación II - 324
Listas especiales con nodo cabecera La eliminación del primer nodo se convierte en un caso
especial al igual que la inserción en la primera posición de la
lista, en este caso las operaciones se restringen a aquellas
posiciones posteriores a alguna otra.
La eliminación e insersición al comienzo de la lista son
algoritmos especiales y en todo caso engorroso
![Page 50: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/50.jpg)
Computación II - 324
Búsqueda de un elemento en una lista
Esta operación consiste en visitar cada uno de los
nodos, tomando al campo siguiente como puntero
al siguiente nodo a visitar.
<<Análisis de ejercicio lista .pas>>
![Page 51: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/51.jpg)
Computación II - 324
Listas Dobles
Es una colección de nodos, donde cada nodo tiene
dos punteros, uno de ellos apuntando a su
predecesor (li) y otro a su sucesor(ld).
Estructura de un nodo:
PI DATO PD
![Page 52: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/52.jpg)
Computación II - 324
Tipos Listas Dobles
Listas dobles lineales.
En este tipo de lista doble, tanto el puntero
izquierdo del primer nodo como el derecho
del último nodo apuntan a NIL.
Se puede recorrer una serie de nodos donde
desde cualquier nodo excepto el último y el
primero. Se puede viajar al nodo anterior o al
siguiente utilizando dos punteros llamados
P_prox y P_ant.
![Page 53: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/53.jpg)
Computación II - 324
Tipos Listas Dobles
Listas dobles circulares.
En este tipo el puntero izquierdo del primer nodo
apunta al último nodo de la lista, y el puntero
derecho del último nodo apunta al primer nodo de
la lista.
![Page 54: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/54.jpg)
Computación II - 324
Pilas.
Tipo especial de lista lineal en la cual un elemento sólo puede ser
añadido o eliminado por un extremo llamado cima.
Esto significa que los elementos se sacan de la pila en orden
inverso al que se pusieron en ella.
LIFO (LAST IN- FIRST OUT). Primero que entra último que sale.
![Page 55: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/55.jpg)
Pila: caso particular de una lista enlazada
La imagen muestra como quedaría una pila de enteros al agregarle un
valor 3, luego un 2 y luego un 1.
Computación II - 324
<<Analizar ejercicio de pila>>
![Page 56: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/56.jpg)
Computación II - 324
Colas
Una cola es una lista en las que las supresiones se realizan
solamente solamente al principio de la lista y las inserciones al final
de la misma.
Son conocidas como listas FIFO (First In, First Out: El primero en
entrar es el primero en salir). Los elementos se almacenan en
fila, pero sólo pueden añadirse por un extremo y leerse por el
otro.
Analizar ejercicio de cola
![Page 57: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/57.jpg)
Cola
Computación II - 324
![Page 58: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/58.jpg)
Computación II - 324
Recursividad
Es una herramienta de programación utilizada para resolver
problemas que al subdividirlos en subproblemas presentan la
misma estructura.
Casos Típicos definir objetos en sí mismo ejemplo árboles, colas,
listas, listas enlazadas.
Un programa que se llame a sí mismo se dice que es recursivo
![Page 59: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/59.jpg)
Computación II - 324
Tipos de Recursividad
Directa e indirecta
Diseño de la Recursividad
Estado básico: Es el estado en el cual la solución no se presenta
de manera recursiva sino directamente.
Estado General: Se debe poder resolverse en función del caso
base y un caso general de menor tamaño (que progrese hacia una
solución más sencilla, hacia el caso base)
![Page 60: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/60.jpg)
Computación II - 324
Desventajas de la Recursividad
No es más rápida que la iteración (ya que implica guardar entornos).
Consume muchos recursos (memoria)
Funcionamiento de la Recursividad
Es necesario guardar el estado de cada programa antes de cada
llamada (variables locales, parámetros y punto de ejecución) para que
sepa seguir después de la llamada.
![Page 61: Computación ii 324-1-estructuras dinamicas-con enlaces](https://reader033.fdocumento.com/reader033/viewer/2022052323/559145231a28ab685d8b462d/html5/thumbnails/61.jpg)
Computación II - 324
Análisis del cálculo del factorial de un número program factorial;
uses crt;
var
n,i,mul:integer;
begin
mul:=1;
i:=1;
writeln (‘Numero a sacarle el factorial');
readln (n);
repeat
mul:=mul*i;
i:=i+1;
until (i>n);
writeln ('el factorial es ',mul);
readln;
end.
program FactorialNum;
var
num:integer;
function factorial(n:integer):integer;
begin
if (n > 1) then
factorial:= n * factorial(n-1)
else factorial:=1;
end;
begin
write(' Ingrese el valor de n: ');
readln(num);
writeln(' El resultado es: ',factorial(num));
readln;
end.
Realice la corrida de cada uno