PDF de programación - Algoritmos y estructuras de datos

Algoritmos y estructuras de 

datos

Dr. Eduardo A. Rodríguez Tello

Laboratorio de Tecnologías de Información

Cinvestav‐Tamaulipas
Cinvestav Tamaulipas

[email protected]

Cursos de inducción a la MCC

© Cinvestav‐Tamaulipas 2012

1

Temario

O d

t

Introducción
I.
Estructuras de datos estáticas y dinámicas
II. Estructuras de datos estáticas y dinámicas
II
III. Tipos de datos abstractos
IV. Ordenamientos
i
V. Búsquedas
C
t
Conceptos
Búsquedas en listas
Búsquedas en árboles
Búsquedas en árboles

a.
b.
c
c.

VI. Resumen

Cursos de inducción a la MCC

Estructuras de datos

© Cinvestav‐Tamaulipas 2012  

2

Búsquedas

 Consiste en solucionar un problema de membresía de
un elemento determinado en un conjunto finito de
un elemento determinado en un conjunto finito de
elementos

 Un algoritmo de búsqueda está diseñado para localizar
 Un algoritmo de búsqueda está diseñado para localizar
un elemento concreto dentro de una estructura de
datos

Cursos de inducción a la MCC

Estructuras de datos

© Cinvestav‐Tamaulipas 2012  

3

Algoritmos de búsqueda

 Búsqueda Secuencial
 Búsqueda Binaria
 Búsqueda Binaria
 Hashing
 Bú
d
 Búsqueda en Arboles Multiway
 Búsqueda en Trie
 Hashing Dinámico
 Búsqueda de claves múltiples

H hi Di á i

A b l M lti

Cursos de inducción a la MCC

Estructuras de datos

© Cinvestav‐Tamaulipas 2012  

4

Búsquedas en listas: secuencial

 Se trata de encontrar un elemento dado en una lista observando cada

elemento en la lista para verificar si es el elemento buscado

 Para listas sin ordenar,

secuencial

LinearSearch(List, SearchKey)
LinearSearch(List, SearchKey)

lo único que se puede hacer es una búsqueda

if  (List is not empty)

then {

TestEntry  first entry in List
while  (SearchKey > TestEntry

TestEntry  next entry in List
T tE t
Li t

t

t

i

AND entries remaining)  do

if  (SearchKey = TestEntry)

then  

succes!

failure!

} else

else  

failure!

Cursos de inducción a la MCC

Estructuras de datos

© Cinvestav‐Tamaulipas 2012  

5

Búsquedas en listas: binaria

 Método de búsqueda que progresivamente va

generando mejores suposiciones
generando mejores suposiciones

 Es un algoritmo de tipo divide y vencerás dicotómico

int binarySearch(List, SearchKey, starting, ending) 

if ending < starting 

return ‐1 

mid = (starting + ending) / 2
mid = (starting + ending) / 2 
if List[mid] = value
return mid 
if List[mid] > value 

ending = mid ‐ 1 

if List[mid]< value

starting = mid + 1

return binarySearch(List, SearchKey, starting, ending) 

Cursos de inducción a la MCC

Estructuras de datos

© Cinvestav‐Tamaulipas 2012  

6

Búsquedas en árboles binarios no ordenados

 Mismo principio que un recorrido, ya sea en amplitud
o en profundidad solo que la búsqueda termina
o en profundidad, solo que la búsqueda termina
cuando:
 se encuentra el elemento (éxito) o
 cuando se ha recorrido todo el árbol sin encontrarlo

(fracaso)

Cursos de inducción a la MCC

Estructuras de datos

© Cinvestav‐Tamaulipas 2012  

7

Búsquedas en árboles binarios ordenados

 Mismo principio que un recorrido en profundidad
 La clave buscada se compara con la clave del nodo raíz
 La clave buscada se compara con la clave del nodo raíz
 Si las claves son iguales, la búsqueda se detiene
 Si la clave buscada es mayor que la clave raíz, la búsqueda se

q

q

y

,

reanuda en el subárbol derecho.

 Si la clave buscada es menor que la clave raíz, la búsqueda se

reanuda en el subárbol izquierdo
i d

bá b l i

d

l

Cursos de inducción a la MCC

Estructuras de datos

© Cinvestav‐Tamaulipas 2012  

8

Temario

Introducción
I.
Estructuras de datos estáticas y dinámicas
II. Estructuras de datos estáticas y dinámicas
II
III. Tipos de datos abstractos
IV. Ordenamientos
i
V. Búsquedas
VI. Resumen

O d

t

R

Cursos de inducción a la MCC

Estructuras de datos

© Cinvestav‐Tamaulipas 2012  

9

Resumen

 Estructuras de datos estáticas y dinámicas

Estáticas: arreglos y estructuras


 Dinámicas: apuntadores y listas ligadas
 Dinámicas: apuntadores y listas ligadas

 Tipos de datos abstractos

 Listas
 Colas
 Colas
 Pilas
 Arboles
 Grafos
 Grafos

 Ordenamientos

 De listas: Bubble sort, Quick sort
 De árboles

D á b l
 Búsquedas

 En listas: secuencial y binaria
 En árboles

Cursos de inducción a la MCC

Estructuras de datos

© Cinvestav‐Tamaulipas 2012  

10

Referencias

 Weiss, Mark A. Data Structures and Algorithm Analysis

in C++ 3rd Ed Addison‐Wesley 2007
in C++, 3rd Ed. Addison Wesley, 2007.

 Joyanes Aguilar,

C++:
Algoritmos, estructuras de datos y objetos. McGraw
Algoritmos, estructuras de datos y objetos. McGraw
Hill, 2000.

Luis.

Programación

en

Cursos de inducción a la MCC

Estructuras de datos

© Cinvestav‐Tamaulipas 2012  

11