Download MemoriaDinamicaYRecursividad

Estructuras de Datos
1.
1
RECURSIVIDAD
 DEFINICIÓN
Recursión, recursividad o recurrencia es la forma en la cual se especifica un proceso
basado en su propia definición.
Por ejemplo, el acrónimo GNU significa GNU is Not Unix y el acrónimo PHP significa PHP
Hypertext Preprocessor.
Esto permite establecer instancias complejas de un proceso en términos de instancias más
simples y de una o más instancias finales definidas explícitamente.
Un algoritmo recursivo es aquel que expresa la solución de un problema en términos de sí
mismo y de una solución simple conocida; ésta, es una referencia que permite completar la
solución en una cantidad finita de pasos.
Los algoritmos recursivos pueden adoptar la forma de funciones que retornan un valor o que
causan un efecto.
 EJEMPLOS
Las funciones solicitadas se implementan en lenguaje C.
 El Terminal de un número entero no negativo n se define mediante la recurrencia
0 si n=0
n¡ =
n + (n1)¡ si n>0
Implementar la función recursiva suma(n).
int suma(int n)
{ if (n==0)
return 0;
else
return n + suma(n-1);
}
suma(5)
5 + suma(4)
5 + 4 + suma(3)
5 + 4 + 3 + suma(2)
5 + 4 + 3 + 2+ suma(1)
5 + 4 + 3 + 2+ 1 + suma(0)
5 + 4 + 3 + 2+ 1 + 0
5 + 4 + 3 + 2+ 1
5+4+3+3
5+4+6
5 + 10
15
 El Factorial de un número entero no negativo n se define mediante la recurrencia
1 si n=0
n! =
n*(n1)! si n>0
Héctor Pincheira Conejeros
Estructuras de Datos
2
Implementar la función recursiva factorial(n).
int factorial(int n)
{ if (n==0)
return 1;
else
return n*factorial(n-1);
}
 Con respecto a un vector v de valores enteros, implementar la función recursiva
printvec(v, n) que despliega los n elementos de v, según un orden ascendente de sus
índices.
typedef int vector[100];
void printvec(vector v, int n) // 1  n  100
{ if (n>0)
{ printvec(v, n1);
printf("%d", v[n-1]);
}
}
 Implementar la función recursiva binario(n) que imprime los dígitos de la representación
binaria de un número natural n.
void binario(int n)
{ int d;
if(n>0)
{ d = n%10;
binario(n/10);
printf(“%d”, d);
}
}
 El n–ésimo número de la sucesión de Fibonacci (orden 1) se define mediante la recurrencia
0 si n=0
Fn = 1 si n=1
Fn-1 + Fn-2 si n>1
Implementar la función recursiva fibo(n).
int fibo(int n)
{ if (n==0)
return 0;
else
if(n==1)
return 1;
else
return fibo(n-1) + fibo(n-2);
}
Héctor Pincheira Conejeros
Estructuras de Datos
2.
3
LISTAS ENLAZADAS
 DEFINICIÓN
Una lista enlazada es:
 Un objeto vacío.
 Ó, un nodo ligado a una lista enlazada.
 REPRESENTACIÓN
En lenguaje C
typedef struct nodo
{ int dato;
struct nodo *link;
} nodo;
typedef nodo *enlace;
En lenguaje C++
struct Nodo
{ int dato;
Nodo *link;
}
typedef Nodo *Enlace;
 EJEMPLOS
 Implementar una función recursiva que acepte un puntero de acceso a una lista lineal de
enlace simple y un valor entero, debiendo almacenar el valor recibido en un nuevo nodo y
agregarlo en el "extremo derecho" de la lista. Luego, escribir un "main" que genere una
lista utilizando la función implementada.
void agregar(enlace *l, int e)
{ if (*l == NULL)
{ *l = (enlace)malloc(sizeof(nodo));
(*l)->dato = e;
(*l)->link = NULL;
}
else agregar(&((*l)->link), e);
}
void main()
{ int k; enlace q = NULL;
scanf("%d", &k);
while (k != 0)
{ agregar(&q, k);
scanf("%d", &k);
}
}
void agregar(Enlace &l, int e)
Héctor Pincheira Conejeros
Estructuras de Datos
4
{ if (l == NULL)
{ l = new Nodo;
l->dato = e;
l->link = NULL;
}
else agregar(l->link,e);
}
void main()
{ int k; Enlace q = NULL;
cin >> k;
while (k)
{ agregar(q, k);
cin >> k;
}
}
 Implementar la función recursiva invierte, que invierte el sentido de los enlaces de una
lista lineal de enlace simple t y cambia su acceso al extremo opuesto.
enlace invierte(enlace p, enlace q)
{ enlace z;
if(p != NULL)
{ z = invierte(p->link, p);
p->link = q;
q->link = NULL;
return z;
}
else return q;
}
/* Para una lista t se debe invocar invierte(t, t) */
void invierte(enlace p, enlace q, enlace *z)
{ if(p != NULL)
{ invierte(p->link,p,l);
p->link = q;
q->link = NULL;
}
else *z = q;
}
/* Para una lista t se debe invocar invierte(t, t, &t) */
3.
MULTILISTAS
 DEFINICIÓN
Una multilista es una expresión:
 Vacía.
 Ó, un elemento seguido de una expresión.
Cada elemento de una multilista es:
Héctor Pincheira Conejeros
Estructuras de Datos
5
 Un átomo.
 Ó, una multilista.
Por ejemplo, si M = ( 1 2 ( 3 4 ( 5 ) 6 ) 7 8 ) es una multilista, entonces M consta de cinco
elementos: los átomos 1, 2, 7, 8 y la multilista ( 3 4 ( 5 ) 6 ) la cual, a su vez, consta de cuatro
elementos.
 REPRESENTACIÓN
En lenguaje C
typedef struct nodo
{ int atomo;
union
{ int dato;
struct nodo *next;
} var;
struct nodo *link;
} nodo;
typedef nodo *multilista;
 EJEMPLOS
 Implementar la función imprime(m), que imprime el contenido de una multilista m
incorporando los paréntesis necesarios.
void imprimir(multilista m)
{ if (m != NULL)
if (m->atomo)
{ printf("%d", m->var.dato);
listar(m->link);
}
else
{ printf("(");
imprimir(m->var.next);
printf(")");
imprimir (m->link);
}
}
 Implementar el operador existe(m, e), que determina si un elemento e existe o no en una
multilista m.
int existe(multi m, int e)
{ if (m != NULL)
if (m->atomo)
if (m->var.dato = e)
return 1;
else
return existe(m->link, e);
Héctor Pincheira Conejeros
Estructuras de Datos
6
else
return existe(m->var.next, e) || existe(m->link, e);
else
return 0;
}
4.
ÁRBOLES BINARIOS
 DEFINICIÓN
Un árbol binario es:
 Un objeto vacío.
 Ó, un nodo con dos árboles binarios llamados subárbol izquierdo y subárbol derecho.
 JERARQUÍA
Todo árbol manifiesta relaciones de dependencia o parentesco entre sus nodos.
Si T = n1 ( n2 ( n3 , n4 (n5 , n6 ) ) , n7 ( , n8 ) ) entonces
Raíz(T) = n1
Padre(n5) = n4
Hijos(n4) = {n5, n6}
Primos(n8) = {n3, n4}
 DEFINICIONES
 Ruta: Es la secuencia de nodos n1, ..., nk de un árbol binario, de modo que ni es padre de
ni+1,  i=1..k-1. Por ejemplo, Ruta(n1, n5) = (n1, n2, n4, n5).
 Arco: Es la trayectoria entre dos nodos consecutivos.
 Longitud de ruta (módulo de ruta): Es la cantidad de arcos entre dos nodos.
|Ruta(n1, n5)| = #(Ruta(n1, n5))  1 = Arcos(n1, n5) = 3.
 Hoja: Es un nodo que no tiene hijos.
 Nodo interior: Es un nodo que no es hoja.
 Altura: La altura de un nodo ni es h(ni) = max(|Ruta(ni, nk)|) donde nk es una hoja. Si n1 es
la raíz de un árbol T entonces h(n1) es la altura de T.
 Profundidad: Si n1 es la raíz de un árbol T entonces la profundidad de un nodo ni es p(ni) =
|Ruta(n1, ni)|.
 Nivel: El nivel de un nodo ni es su Profundidad.
 Grado: Es el número de descendientes directos de un nodo. El máximo de los grados para
todos los nodos de un árbol se conoce como grado del árbol. Luego, un árbol binario es un
árbol de grado 2.
 Árbol completo: El aquel que tiene todos sus niveles completos.
 Máximo de nodos de un árbol: El máximo número de nodos de un árbol se alcanza cuando
está completo. El número de nodos de un árbol completo de grado g y altura h es
g h 1  1
N(g, h) =
Árbol binario  g = 2. Luego N(2, h) = 2 h 1  1
g 1
Héctor Pincheira Conejeros
Estructuras de Datos
7
 RECORRIDO
En un árbol, un recorrido es una secuencia n1, ..., nk tal que ni  nj  ij y, además, para un
nodo cualquiera el siguiente nodo en la secuencia sólo puede ser su padre, un hijo ó su
hermano. Por ejemplo, si T = n1 (n2 (n3 , n4 ) , n5 ) entonces para el nodo n2 el siguiente nodo
en la secuencia sólo puede ser n1, n3 ó n4, o bien, n5.
Al recorrer un árbol binario, en cada nodo puede ocurrir uno de los tres siguientes eventos:
 Ejecutar alguna acción sobre la raíz (R)
 Recorrer el subárbol izquierdo (I)
 Recorrer el subárbol derecho (D)
Luego, existen seis posibles formas distintas de ordenar tales eventos:
RID, RDI, IRD, DRI, IDR, DIR
Sin embargo, por convención, siempre se recorre el subárbol izquierdo antes que el derecho,
razón por la cual existen tan sólo tres recorridos normalizados:
 Predorden (RID)
 Enorden (IRD)
 Postorden (IDR)
Formalmente, para un árbol binario T:
i) Si T = n entonces Preorden(T) = n
Enorden(T) = n
Postorden(T) = n
ii) Si T = n ( Ti , Td )entonces Preorden(T) = n, Preorden(Ti), Preorden(Td)
Enorden(T) = Enorden(Ti), n, Enorden(Td)
Postorden(T) = Postorden(Ti), Postorden(Td), n
 REPRESENTACIÓN
En lenguaje C
typedef struct nodo
{ int dato;
struct nodo *izq;
struct nodo *der;
} nodo;
typedef nodo *ab;
 EJEMPLOS
 Implementar funciones para imprimir el contenido de un árbol binario t según los tres
recorridos normalizados.
void imprimerid(ab t)
{ if (t != NULL)
{ printf ("%d", t->dato);
imprimerid(t->izq);
imprimerid(t->der);
Héctor Pincheira Conejeros
Estructuras de Datos
8
}
}
void imprimeird(ab t)
{ if (t != NULL)
{ imprimeird(t->izq);
printf ("%d", t->dato);
imprimeird(t->der);
}
}
void imprimeidr(ab t)
{ if (t != NULL)
{ imprimeidr(t->izq);
imprimeidr(t->der);
printf ("%d", t->dato);
}
}
 Implementar la función hojas(t), que determina la cantidad de hojas presentes en un árbol
binario t.
int hojas(ab t)
{ if (t != NULL)
if (t->izq == NULL && t->der == NULL)
return 1;
else
return hojas(t->izq) + hojas(t->der);
else
return 0;
}
Héctor Pincheira Conejeros