estructuras dinamicas lineales (estructuras de datos)

8/18/2019 Estructuras Dinamicas Lineales (Estructuras de Datos)

1/56

Estructuras

Dinámicas Lineales

1

Estructuras de Datos UDEM 2015


2/56

2

Listas Dinámicas

2


3/56

Lista dinámica

• Lista ≠ Arreglo – Lista es fexible y permite cambios de implementación, es un

concepto

• Operaciones

– Insertar, Borrar, Modicar, etc!

• "ipos de listas – #imples

– Ordenadas

– $ilas – %ilas

– Doblemente enla&adas 'LDE(

– )irculares

– Etc!

3


4/56

"AD Lista Simple* operacionesCrear una lista crearLista ()

Comprobar del estado listaLlena ()→ Boolean

listaVacia ()→ Boolean

Insertar un elemento Insertar (valorInfo, posición)

Insertar (valorInfo)

Borrar un elemento Borrar (posición)

Borrar (valorInfo)

Búsquar de un elemento Buscar (dato)→ información

Buscar (dato)→ referenciaElemento

Pertenece (información)→

Booleanecorrer la lista ecorrer ()

!cceder a un elemento Info (referenciaElemento)→ Informacion

"i#uiente (referenciaElemento)→ enlace (referencia)

$odificar un elemento asi#narInfo (referenciaElemento, valorInfo)

asi#narEnlace (referenciaElemento, valorEnlace)4


5/56

%&u' es un odo

• Un nodo es un registro con varios campos (objeto) :

unos campos (atributos) contienen datos y un

campo es un apuntador (referencia). Los primeros

son información y el último es una referencia al

siguiente nodo de la lista. l último nodo de la lista

contiene una referencia con valor !null!.

5

Dato25

Siguiente

null

nodo


6/56

Clase nodo

public class Nodo {

int dato; // almacena el dato

Nodo sig; // ”liga” al siguiente nodo

}

6

El campo dato representa los datos quealmacena el nodo. Puede ser de

diferentes tipos de datos, adems que!ste puede contener la cantidad dedatos que se ocupen.


7/56


8/56

*efinición de la lista dinámica

• Se compone de nodos enlazados.• Se debe hacer en una clase separada.

• Sólo requiere conocer dónde se encuentra el primer

nodo de la lista.

• Para el nombre de la referencia al primer nodo se

hace uso de la metfora! "cabeza de la lista# o

"inicio# $ "tope# o al%o similar.

• &na lista 'ac(a comenzar(a con un 'alor null en inicio.

)

inicio


9/56

jemplo de Lista din"mica

*

inicio

cla'e dato si% cla'e dato si% cla'e dato null

+odo 1 +odo 2 +odo 3


10/56

Creación de una lista dinámica

• Lista vac+a

1,

inicio

null


11/56

11

-nserción de un nodo

Caso1: #nserción al principio de la lista

cla'e dato null

-nicio

cla'e dato si% cla'e dato si%

+odo 1 +odo 2 +odo 3cla'e dato si%

+odo nue'o


12/56

Caso 1) *nserci(n al principio +algoritmo

12

-nsertarinicio info/

00este al%oritmo inserta un nodo al inicio de la lista00nue'o! del tipo nodo/

1 crear nue'o/ 00con ne en a'a

2 hacer nue'o.dato info

nue'o.si% inicio

inicio nue'o

Inicio


13/56


14/56

Caso 2.1 Insertar antes de ….

InsertAntes (ino! "al#

//au$! nue"o! % & son "ariables de tipo Nodo. ' es una "ariable boolean! ) si no se

*a llegado al inal de la lista

+, *acer au$ - inicio! ' - "erdadero

, mientras (au$.dato 0- "al# % (' -- "erdadero# //buscando el nodo con "al

si au$.sig 0- null

{ & - au$! au$ - au$.sig } // a"an1ar

sino ' - also // in de la lista

2, si (' -- "erdadero# //se encontró el nodo

Crear (nue"o#nue"o.dato - ino

nue"o.sig - au$

si (au$ -- inicio# inicio - nue"o //es el primer nodo

si no &.sig - nue"o 14


15/56

Caso 2.2 Inserta despu3s de …

Insert4espues (ino! "al#//nue"o % au$ son "ariables del tipo de inicio! ' es boolean +, au$ - inicio! ' - "erdadero

, 5ientras (au$.dato 0- "al# % (' -- "erdadero# *acer

si au$.sig 0- null entonces au$ - au$.sig

sino ' - also

2, 6i (' - - "erdadero#

entonces crear (nue"o#nue"o.dato - inonue"o.sig - au$.sigau$.sig - nue"o

15


16/56

16

Caso 3. -nserción al final de la lista

-nsertafinal info/

00 nue'o 8 au9 son del tipo inicio1 :acer au9 inicio

2 mientras au9.si% ; null 00no es el


17/56

7liminar Nodos

Casos1:liminar el primer nodo

Eliminaprimero - // Se redene el apuntador inicio.

Si inicio nullinicioinicio.sig //que s' 3a4 al menosun elemento

si no // no se puedeeliminar

17

#nicio


18/56

Caso 7liminar en medio

Caso 2.1 limina nodo con información $

7liminaNodo8 ($#

// au$ % & son "ariables del mismo tipo de inicio! ' es boolean

+, 9acer au$ - inicio ! o - "erdadero, :epetir mientras (au$.dato 0- $# % (o# *acersi au$.sig 0- null // *a% más nodos

entonces & - au$! au$ - au$.sig si no o - also

2, si au$.dato 0- $

entonces // el elemento $ no e$iste si no si inicio -- au$ // $ es el primer elemento de la lista

entonces inicio - au$.sig si no &.sig - au$.sig

au$ - null

1)

#nicio


19/56

aso 2.2 =limina nodo antes del nodo con 'alor 9

Algoritmo 7liminaAntes8 ($#

// au$ ! & % : son "ariables del mismo tipo de inicio (apuntador#! ' es boolean

+, 6i inicio.dato -- $ // $ está en el primer nodoentonces // no *a% nodo ue precede a $sino au$ - inicio; & - inicio; ' - also; mientras ((au$.dato0-$# % (0'## si au$.sig 0- null

entonces : - &; & - au$;

au$- au$.sig; si no ' - "erdadero; , 6i au$.dato 0- $

entonces // el elemento $ no e$iste no se elimina nada si no si inicio.sig - au$ // el elemento a eliminar es el primero entonces inicio - au$

sino :.sig - au$; & - null; 1*

X

inicio R T aux


20/56

aso 3 =limina au9

au9 au9.si% A

3. >.si% null 00 corta con au9

au9 null 00quita au9


21/56

:ecorrido de una lista dinámica

5etodo Correlista (#;

//imprime cada dato de la lista

{

Nodo au$;

au$ - inicio;


22/56


23/56

%ilas

Dinámicas

23


24/56

aracter'sticas de una 6ila

• El primer elemento en llegar es el primero en salir6*67) 6rist *n 6rist 7ut-.

• El 8ltimo en llegar se agrega al nal• El apuntador posee la direcci(n del siguiente nodo• El apuntador puede ser null o puede apuntar al

siguiente nodo

• Esta estructura se utili9a en ) – Simulaciones – Sistemas operati&os etc:

24

sigdato sigdato sigdato sigdato B-nicio


25/56

7peraciones de una 6ila

• )rearla '(

•Agregarla 'int dato(• -uitar%ila '(

• .acio '(

25


26/56

)rea la

crea%ila /

0odo inicio 1 null2

3

26

inicio* null


27/56

Agregar un nodo al nal de una%ilaAgrega 'int ino( /

0odo nue4o 1 ne5 0odo'( nue4o!dato 1 ino2 nue4o!sig1 null2

#i inicio 11 null // caso ila "acia entonces inicio 1 nue4o2

#ino / 0odo aux 1 inicio2 // caso ila no"ac>a

mientas 'aux!sig 61 null( aux 1aux!sig2 aux!sig 1 nue4o2 3

3

27

sigdato nullinicio


28/56

Eliminar un elemento de la %ila

++ se manda a llamar si la la no está 4acia

int 7uitar '( / d 1 inicio!dato2

inicio 1 inicio!sig23

8egresa d23

2)

nullincio

sigdato sigdato sigdato


29/56

La la está 4ac9a:

Boolean 4acia '( / return 'inicio 11 null(2

3

2*

incio

sigdato sigdato sigdato

null


30/56

$ilas

Dinámicas

3,


31/56

)aracter9sticas

• #e remue4e del tope y se agrega en eltope de la pila 'LI%O Last In %rist Out(!

Operaciones)reapila '(

-uitar '( ++'1 pop(

Agregar 'int dato( ++'1 pus;(

.acia '(

31


32/56

)rear una $ila

crea$ila /

0odo inicio 1 null2

3

32


33/56

Agregar un nodo a la $ila 'pus;(

agrega$odo int info-#

nodo nue4o 1 ne5 nodo'(2

nue4o!dato 1 ino2 nue4o!sig 1 inicio2

inicio 1 nue4o2

3

33

siginfo sigdato sigdato sigdato null

nuevo

inicio


34/56

-uitar elemento de la $ila'pop( int 7uitar '(/

int d2 d 1 inicio!dato2

inicio 1 inicio!sig2 return d2

3

34

siginfo sigdato sigdato sigdato null

inicio


35/56

$ara 4ericar si una pila está4ac9a

Boolean 4acia '(/

return 'inicio 11 null(2

3

35


36/56

Ligas de animación para la y

pila• ;ttp*++555!cse!iit?+applets+#tac


37/56

Lista doblemente enla%ada

37


38/56

$odo

public class Nodo {

pri"ate int dato; // almacena el dato

pri"ate Nodo sig; // enlace al pró$imo nodo

pri"ate Nodo ant; // enlace al nodo anterior

}

3)

anterior

Datos

25

siguiente

nodo


39/56

&peraciones de una lista doblemente enla%ada

• 'adir o insertar elementos.

• uscar elementos.

• orrar elementos.

• *overse a trav+s de la lista, siguiente y

anterior.

3*

-nicio si%

antnull


40/56

4,

Presentación %rfica


41/56

41

Presentación %rfica


42/56

'adir elemento a una lista vac-a

42

nue'o.ant 8 nue'o.si% son +&CC.

nue'o

inicio


43/56


44/56

Caso Insertar un elemento en la @ltima posición

Insertarltimo (Nodo nue"o#

+,. nue"o.sig - null // por ocupar la @ltima posición

,. au$.sig - nue"o // el @ltimo nodo actual

2,. nue"o.ant - au$ // apuntará a au$.

44

+ue'oau9

1ato 1ato 1ato

1atonull

0

/

. . . . nue'o

au9


45/56


46/56

=liminar

Caso + 7liminar el @nico nodo 7n este caso! ese nodo es el apuntado por inicio.

7liminamos el nodo! *acemos ue inicio sea NDD

inicio - null;

46

. . . .

inicio


47/56


48/56


49/56


50/56

Lista )ircular

5,


51/56

Cista ircular

• @na lista circular es una lista linealen la 7ue el ltimo nodo apunta alprimero!

51

inicio fin


52/56

&peraciones de una lista circular

las operaciones 7ue se pueden reali&arsobre las listas circulares *

– ?@adir o insertar elementos.

– >uscar o locali9ar elementos.

– >orrar elementos.

– Mo&erse a tra&!s de la lista recorrer-

52


53/56

#nsertar un elemento

*nsertar elemento en la lista &ac'a>! inicio ++apunta a nodo

=! inicio!sig ++apunta a nodo

*nsertar elemento en una lista no&ac'a

! nodo!sig 1 n!sigC! n!sig 1 nodo

53

inicio

fininicio


54/56

liminar un elemento de la lista

• Eliminar el nico nodo de la lista!>! Borramos el nodo apuntado por

inicio!

=! acemos 7ue inicio 4alga 0@LL!

• Eliminar un nodo en una listacircular con más de un elemento >! 0odo aux 1 inicio

=! mientras aux!sig 61 nodo

aux1aux!sig! aux!sig 1 nodo!sig

54

au9


55/56

liminar un elemento de la lista circular

• )aso general 0odo aux 1nodo!sig

>! )opiamos el contenido del nodo!sig sobre elcontenido de nodo* nodo!dato 1 aux!dato

=! acemos 7ue nodo!sig 1 aux!sig

! Eliminamos nodo!sig aux1null

55

inicio


56/56

%in del cap9tulo LI#"A#, %ILA# y

$ILA# dinámicas

estructuras dinamicas lineales (estructuras de datos)

Documents