Estructuras de Datos Resumen

ESTRUCTURAS DE DATOS
El objetivo fundamental de las estructuras de datos es la optimizacin de la representacin

de los datos atendiendo a dos factores:
(a) almacenamiento eficiente en memoria.
(b) acceso rpido a la informacin almacenada.
Tipos de datos. Un dato es aquella informacin relativa a un objeto y manipulable

por la mquina.
Un tipo de dato se define como:
(1) Un conjunto de valores, aquellos que puede tomar cualquier dato de dicho tipo.
(2) Un conjunto de operaciones, definidas sobre dichos valores, que permiten operar
adecuadamente con ellos.
Clasificacin del conjunto de datos

Podemos dividir los datos en:
Datos elementales.
Datos Estructurados o Estructuras de Datos.
Son datos elementales aquellos que se consideran indivisibles en unidades ms simples.
Bsicamente los podemos dividir en definidos por el usuario y predefinidos
Las estructuras de datos consisten en una agrupacin lgica de elementos individuales,
cada uno de los cuales, es a su vez, o bien un dato simple u otra estructura de datos. Ejemplos
de estructuras de datos son Vectores, Matrices, Registros, etc.
TIPO DATO REAL. La representacin de los reales no es unvoca, ya que lo que
verdaderamente se representan son intervalos de la recta real.
TIPO DATO CARCTER. La nica operacin interna que tiene este tipo es la asignacin de un
carcter a una variable.
TIPO DATO ENUMERADO. Los datos de este tipo se definen explcitamente dando un
conjunto finito de valores.
Estructura de Datos. Llamamos estructura de datos o tipo de dato estructurado a los
tipos de datos construidos a partir de otros tipos de datos.
CLASIFICACIN.
De acuerdo al tipo de dato que la componen.
homogneas, cuando todos los datos elementales que la forman son del mismo tipo.
heterogneas, en caso contrario.
De acuerdo a cmo se almacenan y gestionan en memoria.
estticas si poseen un nmero fijo de elementos. Los ejemplos ms tpicos son los
arrays y registros.
dinmicas si el nmero de elementos que contienen puede variar durante la
ejecucin del programa.
De acuerdo a la forma de acceso.
acceso por nombre, es decir, para acceder a cada elemento de la estructura de
datos es necesario conocer el nombre (p. e. los registros).
acceso por posicin, donde para acceder a un elemento de la E. D. o bien se
conoce su posicin, o bien el acceso se reduce a ciertos elementos.
acceso por clave, en la que para acceder a un determinado elemento es preciso
conocer nicamente el contenido de uno de sus campos, normalmente llamado clave.
REGISTRO
Un registro es una estructura de datos que engloba varios elementos (simples o estructurados)
y que contiene informacin relativa a un mismo ente. Cada unin informativa sobre un objeto
particular se denomina registro. A cada uno de los elementos del registro se le denomina
campo. Evidentemente, los campos pueden ser de un tipo estructurado.
Ejemplo:
La ficha de un empleado en una empresa puede ver como un registro con los siguientes
campos:
- NIF (string)
- Nombre (string)
- Apellido1 (string)
- Apellido2 (string)
- N_Hijos (entero)
- NSS (string)
- Fecha_Nacimiento (fecha)
donde tipo_fecha es otro registro con los campos:
- da (subrango 1..31)
- mes (subrango 1..12)
- ao (entero)
LISTAS.
Las flechas que aparecen en la figura son la representacin grfica de los valores de un tipo
de datos llamado puntero. Las variables de tipo puntero guardan direcciones de memoria. Para
cada elemento de la lista se almacena, junto a dicho elemento, un puntero que contiene la
direccin del elemento siguiente.
Si en una lista slo se permite aadir (push) y eliminar (pop) elementos por uno de los
extremos (la cima), hablamos de PILA o LIFO ( Last In, First Out).
Mtodos de Ordenamiento
1. Ordenacin por Seleccin
Este mtodo es muy sencillo y se trata de buscar el elemento ms pequeo del arreglo y
llevarlo a la primera posicin, luego se avanza a la siguiente posicin, y se coloca el elemento
ms pequeo del arreglo y as sucesivamente.
2. Ordenacin por Insercin
Este mtodo es capaz de mantener un arreglo ordenado insertando elementos en su
correspondiente posicin, por ejemplo si mi arreglo contiene los valores {1,3,4} y quiero insertar
un nuevo elemento 2, el arreglo quedar de esta forma {1,2,3,4}.
3. Ordenacin de Burbuja
Este es un mtodo de ordenacin elemental, que hace todas las comparaciones necesarias
para colocar un elemento en la posicin que le corresponde.
4. Ordenacin MergeSort
5. Ordenacin QuickSort, etc.
Mtodos de Bsqueda
1. Bsqueda Secuencial
Esta bsqueda realiza un recorrido lineal (uno por uno) por todos los elementos de un arreglo.
Es til cuando el tamao del arreglo no es grande y no tiende a crecer su nmero de
elementos.
2. Bsqueda Binaria
Dicha bsqueda es aplicable en arreglos ordenados, pues su Funcionamiento depende de este
hecho.
Cadenas.
Carcter. Un carcter ocupa 8 bits en memoria, y existen 256 caracteres diferentes.
Cadena. Una cadena o cadena de caracteres nos es ms que una serie de caracteres
manipulados como una unidad.
RECURSIVIDAD
Un algoritmo recursivo es un algoritmo que expresa la solucin de un problema en trminos
de una llamada a s mismo. La llamada a s mismo se conoce como llamada recursiva o
recurrente.
La recursividad es una tcnica de programacin importante. Se utiliza para realizar una llamada
a una funcin desde la misma funcin. La recursividad y la iteracin (ejecucin en bucle) estn
muy relacionadas, cualquier accin que pueda realizarse con la recursividad puede realizarse
con iteracin y viceversa.
RECURSIVIDAD VS ITERACIN
La recursividad y la iteracin (ejecucin en bucle) estn muy relacionadas, cualquier
accin que pueda realizarse con la recursividad puede realizarse con iteracin y
viceversa.
Tanto la iteracin como la recursin se basan en una estructura de control:
La iteracin utiliza una estructura repetitiva
La recursin utiliza una estructura de seleccin.
La iteracin y la recursin implican ambas repeticin:
La iteracin utiliza explcitamente una estructura repetitiva
La recursin consume la repeticin mediante llamadas repetidas.
La iteracin y la recursin implican cada una un test mientras que la recursin termina
cuando se reconoce un caso base o la condicin de salida se alcanza.
VENTAJAS Y DESVENTAJAS de la Recursin

Ventajas:
Soluciones simples, claras
Soluciones elegantes.
Soluciones a problemas complejos.
Desventajas:
Ineficiencia
Sobrecarga asociada con las llamadas a sub-algoritmos.
Una simple llamada puede generar un gran nmero de llamadas recursivas.
(factorial(n) genera n llamadas recursivas)
El valor de la recursividad reside en el hecho de que se puede usar para
resolver problemas sin fcil solucin iterativa.
La ineficiencia inherente de algunos algoritmos recursivos.
La claridad compensa la sobrecarga?
La recursividad se debe usar cuando sea realmente necesaria, es decir,
cuando no exista una solucin iterativa simple.
Factorial RECURSIVO
int f(int n) {
if (0==n)
3 return 1;
4 else
5 return n * f(n-1);
6}
1
2
Fibonacci RECURSIVO
int fib(int n) {
if (n<=2)
3 return 1;
4 else
5 return fib(n-1)+fib(n-2);
6}
1
2
Decimal a binario RECURSIVO

typedef unsigned long int base;
void dec2bin(base n) {
3 if (n >= 2){
4 dec2bin(n / 2);
5 cout << n % 2;
6 } else {
7 cout << n;
8}
1
2
Factorial de un nmero RECURSIVO
funcion factorial(n)
si n=1 entonces
factorial = 1
sino
factorial = n * factorial(n-1)
fin funcin
Torres de Hanoi RECURSIVO

Algoritmo Mueve(N, origen, auxiliar, destino)
Inicio
3 SI N == 1 ENTONCES
4 Mueve un disco del palo origen al destino
5 EN OTRO CASO
6 Mueve(N-1, origen, destino, auxiliar)
7 Escribe("Mueve un disco del palo ", origen, " al ", destino)
8 Mueve(N-1, auxiliar, origen, destino)
9 FINSI
10 Fin
1
2
Potencia de un nmero RECURSIVO

long int potencia(int base,int e){
if(e==0) return 1;
if(e==1) return base;
else return base*potencia(base,e-1);
}
Suma n primero nmeros RECURSIVO

int sumaNumeros(int n)
{
if(n==0) return 0;
return n+sumaNumeros(n-1);
}
Producto de dos nmeros RECURSIVO

int producto(int a, int b)
{
if(b==0) return 0;
return a+producto(a,b-1);
MCD de dos nmeros RECURSIVO

int mcd(int a, int b){
if(b==0) return a;
else mcd(b,a%b);
}
Sumatoria de a hasta b RECURSIVO

Si a==b return a
SiNo reutrn b + Sumatoria(a, b-1)
Minimo Comn Mltiplo RECURSIVO

int MCM(int a,int b)
{ if(a>=b && a%b==0)
return b;
else
return MCM(b,a%b);
}
ALGORTIMOS DE ORDENAMIENTO
BURBUJA
Como lo describimos en el item anterior, la burbuja ms simple de todas es la que
compara todos con todos, generando comparaciones extras, por ejemplo, no tiene
sentido que se compare con sigo mismo o que se compare con los valores
anteriores a l, ya que supuestamente, ya estn ordenados.
for (i=1; i<LIMITE; i++)

for j=0 ; j<LIMITE - 1; j++)
if (vector[j] > vector[j+1])
temp = vector[j];
vector[j] = vector[j+1];
vector[j+1] = temp;
BURBUJA MEJORADA. Ya no se compara consigo misma.

Bubblesort(int matriz[])
{
int buffer;
int i,j;
for(i = 0; i < matriz.length; i++)
{
for(j = 0; j < i; j++)
{
if(matriz[i] < matriz[j])
{
buffer = matriz[j];
matriz[j] = matriz[i];
matriz[i] = buffer;
}
}
}
}
BURBUJA OPTIMIZADA
Si al cambio anterior (el de la burbuja mejorada) le sumamos otro cambio, el
hecho que los elementos que estn detrs del que se est comparando, ya
estn ordenados, las comparaciones serian an menos y el mtodo sera an
ms efectivo.
INSERCIN y SELECCIN
Insercion(int matrix[])
{
int i, temp, j;
for (i = 1; i < matrix.length; i++)
{
temp = matrix[i];
j = i - 1;
while ( (matrix[j] > temp) && (j >= 0) )
{
matrix[j + 1] = matrix[j];
j--;
}
matrix[j + 1] = temp;
}
}
Seleccion(int[]matrix)
{
int i, j, k, p, buffer, limit = matrix.length-1;
for(k = 0; k < limit; k++)
{
p = k;
for(i = k+1; i <= limit; i++)
if(matrix[i] < matrix[p])
p = i;
if(p != k)
{
buffer = matrix[p];
matrix[p] = matrix[k];
matrix[k] = buffer;
}
}
}
El bucle principal de la ordenacin por insercin va examinando sucesivamente todos los
elementos de la matriz desde el segundo hasta el n-esimo, e inserta cada uno en el lugar
adecuado entre sus predecesores dentro de la matriz.
La ordenacin por seleccin funciona seleccionando el menor elemento de la matriz y
llevndolo al principio; a continuacin selecciona el siguiente menor y lo pone en la segunda
posicin de la matriz y as sucesivamente.
ORDENAMIENTO POR MERGE SORT (MEZCLA)

Si se piensa en este algoritmo recursivamente, podemos imaginar que dividir la lista
hasta tener un elemento en cada lista, luego lo compara con el que est a su lado y
segn corresponda, lo sita donde corresponde.
ORDENAMIENTO SHELL SORT
Este mtodo es una mejora del algoritmo de ordenamiento por Insercin (Insertsort).
Si tenemos en cuenta que el ordenamiento por insercin es mucho ms eficiente si
nuestra lista de nmeros esta semi-ordenada y que desplaza un valor una nica
posicin a la vez.
Durante la ejecucin de este algoritmo, los nmeros de la lista se van casi-ordenando y
finalmente, el ltimo paso o funcin de este algoritmo es un simple mtodo por
insercin que, al estar casi-ordenados los nmeros, es ms eficiente.
public void shellSort(int[] matrix)
{
for ( int increment = matrix.length / 2; increment > 0; increment =
(increment == 2 ? 1 : (int) Math.round(increment / 2.2)))
{
for (int i = increment; i < matrix.length; i++)
{
for (int j = i; j >= increment && matrix[j - increment] >
matrix[j]; j -= increment)
{
int temp = matrix[j];
matrix[j] = matrix[j - increment];
matrix[j - increment] = temp;
}
}
}
}
ORDENAMIENTO QUICKSORT
Sin duda, este algoritmo es uno de los ms eficientes. Este mtodo es el ms rpido
gracias a sus llamadas recursivas, basndose en la teora de divide y vencers.
Lo que hace este algoritmo es dividir recursivamente el vector en partes iguales,
indicando un elemento de inicio, fin y un pivote (o comodn) que nos permitir
segmentar nuestra lista. Una vez dividida, lo que hace, es dejar todos los mayores que
el pivote a su derecha y todos los menores a su izq. Al finalizar el algoritmo, nuestros
elementos estn ordenados.
COMPLEJIDAD
Algoritmo Operaciones maximas

Burbuja (n2)
Insercion (n2/4)
Seleccion (n2)
Shell (n log2n)
Merge (n logn)
Quick (n2) en peor de los casos y (n logn) en el
promedio de los casos.
Anlisis de algoritmos
Determinar las caractersticas de la performance del algoritmo.
Tiempo.
Memoria.
Ancho de banda de la comunicacin.
Porque analizar algoritmos?
De todos los algoritmos que se tenga, elegir aquel que
sea el ms eficiente para el mismo problema.
COSTO DE UN ALGORITMO
Cuando el Costo de un Algoritmo es igual al Menor Costo
Posible, entonces el algoritmo es ptimo.
Funcin de complejidad de tiempo f(n):
Mide el tiempo que es necesario para ejecutar un algoritmo en un
problema de tamao n.
Funcin de Complejidad de Espacio f(n):
Mide la cantidad de memoria necesaria para ejecutar un algoritmo en
un problema de tamao n.
Clases de comportamiento asinttico
Complejidad
Complejidad
Complejidad
Complejidad
constante: f(n) = O(1)

logartmica: f(n) = O(log n)
lineal: f(n) = O(n)
lineal logaritmica: f(n) = O(nlog n)
Ocurre en algoritmos que solucionan un problema

dividindolo en subproblemas. Luego resuelve cada
subproblema y finalmente agrupa las soluciones.
Complejidad cuadrtica: f(n) = O(n2)
Ocurre en algoritmos que presentan anillos (loops) uno
dentro del otro.
Complejidad exponencial: f(n) = O(2n)
Complejidad factorial: f(n) = O(n!)
Jerarqua de funciones
Del punto de vista asinttico est dado por:

Estructuras de Datos Resumen

Cargado por

Copyright:

Formatos disponibles

Estructuras de Datos Resumen

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Estructuras de Datos Resumen

Cargado por

Copyright:

Formatos disponibles

ESTRUCTURAS DE DATOS

El objetivo fundamental de las estructuras de datos es la optimizacin de la representacin

Tipos de datos. Un dato es aquella informacin relativa a un objeto y manipulable

Clasificacin del conjunto de datos

VENTAJAS Y DESVENTAJAS de la Recursin

Decimal a binario RECURSIVO

Factorial de un nmero RECURSIVO

Torres de Hanoi RECURSIVO

Potencia de un nmero RECURSIVO

Suma n primero nmeros RECURSIVO

Producto de dos nmeros RECURSIVO

MCD de dos nmeros RECURSIVO

Sumatoria de a hasta b RECURSIVO

Minimo Comn Mltiplo RECURSIVO

for (i=1; i<LIMITE; i++)

BURBUJA MEJORADA. Ya no se compara consigo misma.

ORDENAMIENTO POR MERGE SORT (MEZCLA)

Algoritmo Operaciones maximas

constante: f(n) = O(1)

Ocurre en algoritmos que solucionan un problema

También podría gustarte