NotasEstructurales

Estructuras de Datos con Java
H´ctor Tejeda V
e
Abril, 2010

´
Indice general
1. Introducci´n
o
1.1. Que son las estructuras de datos . . . . . . . . . . . . . . . . . .
1.2. Generalidades de las Estructuras de Datos . . . . . . . . . . . . .

5
5
5

2. Arreglos, listas enlazadas y recurrencia
2.1. Arreglos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1.Guardar entradas de juego en un arreglo . . . . . . . . .
2.1.2. Ordenar un arreglo . . . . . . . . . . . . . . . . . . . . .
2.1.3. M´todos para arreglos y n´meros aleatorios . . . . . . .
e
u
2.1.4. Arreglos bidimensionales y juegos de posici´n . . . . . .
o
2.2. Listas simples enlazadas . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Inserci´n en una lista simple enlazada . . . . . . .. . .
o
2.2.2. Inserci´n de un elemento en la cola . . . . . . . . . . . .
o
2.2.3. Quitar un elemento de una lista simple enlazada . . . .
2.3. Listas doblemente enlazadas . . . . . . . . . . . . . . . . . . . .
2.3.1. Inserci´n entre los extremos de una lista doble enlazada
o
2.3.2. Remover en el centro de una lista doblemente enlazada .
2.3.3. Una implementaci´n de una listadoblemente enlazada .
o
2.4. Listas circulares y ordenamiento . . . . . . . . . . . . . . . . .
2.4.1. Listas circularmente enlazadas . . . . . . . . . . . . . .
2.4.2. Ordenando una lista enlazada . . . . . . . . . . . . . . .
2.5. Recurrencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.1. Recurrencia binaria . . . . . . . . . . . . . . . . . . . .
2.5.2. Recurrencia m´ltiple . .. . . . . . . . . . . . . . . . . .
u

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

9
9
9
14
17
20
23
25
26
27
28
31
31
33
35
35
39
40
46
49

3. Herramientas de an´lisis
a
3.1. Funciones . . . . . . . . . . . . . . . . . . . .
3.1.1. La funci´n constante . . . . . . . . . .
o
3.1.2. La funci´n logar´
o
ıtmica . . . . . . . . .
3.1.3. La funci´n lineal. . . . . . . . . . . .
o
3.1.4. La funcion N-Log-N . . . . . . . . . .
3.1.5. La funci´n cuadr´tica . . . . . . . . .
o
a
3.1.6. La funci´n c´bica y otras polinomiales
o u
3.1.7. La funci´n exponencial . . . . . . . . .
o

.
.
.
.
.
.
.
.

51
51
51
51
52
53
53
54
54

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
..
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

´
INDICE GENERAL
3.2. An´lisis de algoritmos . . . . .
a
3.2.1. Estudios experimentales
3.2.2. Operaciones primitivas .
3.2.3. Notaci´n asint´tica . . .
o
o
3.2.4. An´lisis asint´tico . . .
a
o

3
.
.
.
.
.

.
.
.
..

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

55
56
56
57
60

4. Pilas y colas
4.1. Gen´ricos . . . . . . . . . . . . . . . . . . . . . . . . . .e
4.2. Pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1. El tipo de dato abstracto pila . . . . . . . . . . .
4.2.2. Implementaci´n de una pila usando un arreglo .
o
4.2.3. Implementaci´n de una pila usando lista simple .
o
4.2.4. Invertir un arreglo con una pila . . . . . . . . . .
4.2.5. Aparear par´ntesis y etiquetas HTML . . . . . .
e
4.3. Colas . . . . . . . .. . . . . . . . . . . . . . . . . . . . .
4.3.1. Tipo de dato abstracto cola . . . . . . . . . . . .
4.3.2. Interfaz cola . . . . . . . . . . . . . . . . . . . . .
4.3.3. Implementaci´n simple de la cola con un arreglo
o
4.3.4. Implementar una cola con una lista enlazada . .
4.3.5. Planificador Round Robin . . . . . . . . . . . . .
4.4. Colas con doble terminaci´n . . . . . . . . . . . ....