Estructura de Datos.
Pilas.
• Características:
– LIFO (Last in first Out).
– Parte Siempre en 0.
• Necesito:
– Ultimo (Top)
•Diagrama PUSH.
Datos
0 dato
1
2
3
4
5
6
7
Top
• Primero Guardo El Dato
0
1
• Y luego actualizo el
último
•Diagrama POP.
Datos
0 dato
1 dato
2 dato
3
4
5
6
7
Top
•Sólo debo decir que el último
ahora está antes
3
2
(para efectos de
recorrido el dato borrado
ya no existirá)
•Diagrama BUSCAR.
Datos
0 dato1
1 dato2
2 dato3
3 dato4
4 dato5
5
6
7
Top
•Recorro hasta Top 0 hasta que
encuentr el elemento
=buscado??
5
buscado
dato3
•Pregunto si es igual a
buscado, sino sigo el
recorrido
•Hasta que lo encuentro
o el final.
Colas.
• Características:
– FIFO (First in first Out).
– El inicio no es siempre el mismo.
• Necesito:
– Inicio
– Final (Top)
•Diagrama PUSH.
Datos
0 dato
Inicio
0
1
• Y luego actualizo el
final de la cola
1
2
Final
1
0
3
4
5
6
7
• Primero Guardo El Dato
•Diagrama POP.
Datos
0 dato
Inicio
1
0
1 dato
2 dato
Final
3
3
4
5
6
7
•Sólo debo decir que el primero
ahora está una posicion después
(para efectos de
recorrido el dato borrado
ya no existirá)
•Diagrama BUSCAR.
Datos
0 dato1
1 dato2
2 dato3
3 dato4
4 dato5
5
6
7
Top
•Recorro hasta Top o hasta que
encuentr el elemento
=buscado??
5
buscado
dato3
•Pregunto si es igual a
buscado, sino sigo el
recorrido
•Hasta que lo encuentro
o el final.
Lista Enlazada Simple.
• Características:
– Push y Pop donde sea
– Trabaja con punteros.
• Necesito:
– Inicio
– Final
– Blancos
•Diagrama PUSH.
Datos Puntero
0 dato
100
1
1
2
2
3
Inicio
0
100
•Al insertar guardo el dato en
el primer vacío (si lo hay)
Final
100
0
3
4
4
5
5
6
6
7
7
0
•Blancos apunta al primer vacío
e Inicio apunta a ningún lado
Blancos
0
1
•De ser necesario apunto
inicio a la lista, sino apunto al
que corresponda
•Copio la posicion del primer
vacío al final
•Aviso que el dato es el
último
•Y actualizo el primer
Blancos
•Diagrama POP.
Datos
0 dato
Inicio
1
0
1 dato
2 dato
Final
3
3
4
5
6
7
•Sólo debo decir que el primero
ahora está una posicion después
(para efectos de
recorrido el dato borrado
ya no existirá)
•Diagrama BUSCAR.
Datos
0 dato1
1 dato2
2 dato3
3 dato4
4 dato5
5
6
7
Top
•Recorro hasta Top o hasta que
encuentro el elemento
=buscado??
5
buscado
dato3
•Pregunto si es igual a
buscado, sino sigo el
recorrido
•Hasta que lo encuentro
o el final.
Listas Circulares.
• Características:
– Pueden Ser Fifo o Lifo.
– Es similar a listas simples pero el último
apunta al primero.
• Necesito:
– Inicio
– Blancos
•Diagrama PUSH.
Datos Puntero
0 dato
100
1
1
2
2
3
3
4
4
5
5
6
6
7
7
0
Inicio
0
100
•El último apunta al primero (eso
lo hace circular), lo demás es igual
a la lista enlazada simple.
•Blancos apunta al primer vacío
e Inicio apunta a ningún lado
Blancos
0
1
•Al insertar guardo el dato en
el primer vacío (si lo hay)
•De ser necesario apunto
inicio a la lista, sino apunto al
que corresponda
•Aviso que el dato es el
último
•Y actualizo el primer
Blancos
•Diagrama POP FIFO.
Datos Puntero
0 dato
1
1 dato
2
2 dato
3
Inicio
0
1
Blancas
4
3 dato
100
4
5
5
6
6
7
7
0
•Para borrar el primero sólo
avanzo Inicio
(para efectos de
recorrido el dato borrado
ya no existirá)
•Diagrama POP LIFO.
Datos Puntero
0 dato
1
1 dato
2
2 dato
3
100
Inicio
0
100
4
4
5
5
6
6
7
7
0
•Para borrar el último lo apunto al
primer Blancas
•Ahora digo que ese puesto está
libre, retrocedo Blancas
Blancas
3
4
3 dato
1
•Por último marco el último como
último
•Diagrama BUSCAR.
•Recorro hasta el ultimo o hasta
que encuentro el elemento
Datos Puntero
0 dato1
1
1 dato2
2
2 dato3
3
3 dato4
100
=buscado??
•Pregunto si es igual a
buscado, sino sigo el
recorrido
Inicio
4
5
5
6
6
7
7
0
buscado
dato3
0
•Hasta que lo encuentro
o el final.
Listas Enlazadas Dobles.
• Características:
– No tiene orden de inserción o borrado.
– Trabaja con punteros
• Necesito:
– Inicio
– Blancos
– Último
•Diagrama PUSH.
Ant
Datos
Sig
0 dato1
100
1
1 dato2
0
2
2 dato3
1
3
3 dato4
2
100
4
4 dato5
100
3
100
5
5
100
5
6
6
6
7
7
7
Inicio
Blancos
0
4
5
= lleno??
100
Insertar
dato5
•(Insertaré al final) Primero
guardo el dato
•Deberé buscar el último
lleno
•Y lo apunto al primer
Blancos
•Y el ultimo lo apunto al
anterior
•Ahora digo que el último es
el último
•Actualizo el primer Blancos
•Y, por último, digo que es el
primer vacío en la tabla
•Diagrama POP el primero.
Ant
Datos
0 dato1
Sig
100
7
1
100
1 dato2 100
0
2
2 dato3
1
3
3 dato4
2
4
4 dato5
3
100
5
100
6
6
6
7
7
7
100
0
Inicio
Blancos
0
1
5
•Para borrar el primero avanzo inicio
= lleno??
•Digo que el segundo ahora es el
primero
•Busco el último lleno y lo apunto al
recién borrado
•El recién borrado lo apunto, como
anterior, al último
•El recién borrado lo apunto a nada
(último Blancos)
•Diagrama POP cualquiera.
Ant
Datos
Sig
•El último Blanco lo linkeo al que se va a
borrar
•El anterior al que se va a borrar apunta
al que viene del que se va a borrar
0 dato1
100
1
1 dato2
0
2
2 dato3
1
43
3 dato4
2
7
100
4
4 dato5
3
2
100
5
100
6
6
6
7
7
7
3
100
Inicio
Blancos
0
5
1
Pos a
borrar
3
•El siguiente al que se borrará lo señalo
al anterior
•El borrado lo linkeo, anterior, al último
Blancos
•Y lo señalo como último de Blancos
•Diagrama BUSCAR.
Ant
Datos
Sig
0 dato1
100
1
1 dato2
0
2
2 dato3
1
3
3 dato4
2
4
4 dato5
3
100
5
100
6
6
6
7
7
7
100
=buscado??
Inicio
Blancos
Buscado
0
5
Dato3
•Recorro hasta el ultimo o hasta
que encuentro el elemento
•Pregunto si es igual a
buscado, sino sigo el recorrido
•Hasta que lo encuentro o el
final.
Descargar

Estructura de Datos.