Embed Size (px)
DESCRIPTION
Guía Práctica de Listas Doblemente Encadenadas. Hay ejemplos de como alimentar una lista; tanto a la izquierda como a la derecha del nodo principal.
Citation preview
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
Las Listas doblemente encadenas tienen la siguiente estructura:nodo
Nodoanterior Nodosiguiente
Nododato
La estructura esta clasificada con tres elementos:
1.El tipo de Estructura se llama Nodo2.Nodoanterior hace referencia a la dirección de otro nodo3.Nodosiguiente hace referencia a la dirección de otro nodo4.Nododato es la parte en donde se almacena información.
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
EJEMPLO C++:nodo
Nodoanterior Nodosiguiente
Nodovalor
Pedir memoria para los nodos:
Tenemos que definir una constante con el tipo de estructura para que nos reserve memoria dinámica
#define Localizar = (struct *nodo) malloc (size(struct nodo)
Struct nodo { int valor; struct nodo *anterior, struct nodo *siguiente, };
Struct nodo *cab, *cola, *nuevo;
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
EJEMPLO C++:
Primer Nodo:
nuevo = Localizar
Struct nodo { int valor; struct nodo *anterior, struct nodo *siguiente, };
Struct nodo *cab, *cola, *nuevo;
nuevo
001A Dirección de la Estructura
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
NULL
EJEMPLO C++:
Primer Nodo:
nuevo = Localizarnuevoanterior = NULL;
Struct nodo { int valor; struct nodo *anterior, struct nodo *siguiente, };
Struct nodo *cab, *cola, *nuevo;
nuevo
nuevoanterior
001A Dirección de la Estructura
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
NULLNULL
EJEMPLO C++:
Primer Nodo:
nuevo = Localizarnuevoanterior = NULL;nuevosiguiente = NULL;
Struct nodo { int valor; struct nodo *anterior, struct nodo *siguiente, };
Struct nodo *cab, *cola, *nuevo;
nuevo
nuevoanterior nuevosiguiente
001A Dirección de la Estructura
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 NULLNULL
EJEMPLO C++:
Primer Nodo:
nuevo = Localizarnuevoanterior = NULL;nuevosiguiente = NULL;Cout << “Favor ingresar Datos”;Cint >> nuevovalor; //supongamos que el usuario ingresa el Número 50 y Enter.
Struct nodo { int valor; struct nodo *anterior, struct nodo *siguiente, };
Struct nodo *cab, *cola, *nuevo;
nuevo
nuevoanterior nuevosiguiente
nuevovalor
001A Dirección de la Estructura
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 NULLNULL
EJEMPLO C++:
Primer Nodo:
nuevo = Localizarnuevoanterior = NULL;nuevosiguiente = NULL;Cout << “Favor ingresar Datos”;Cint >> nuevovalor; //supongamos que el usuario ingresa el Número 50 y Enter.cab = nuevo;
Struct nodo { int valor; struct nodo *anterior, struct nodo *siguiente, };
Struct nodo *cab, *cola, *nuevo;
nuevo
nuevoanterior nuevosiguiente
nuevovalor
001A Dirección de la Estructura
cab
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 NULLNULL
EJEMPLO C++:
Primer Nodo:
nuevo = Localizarnuevoanterior = NULL;nuevosiguiente = NULL;Cout << “Favor ingresar Datos”;Cint >> nuevovalor; //supongamos que el usuario ingresa el Número 50 y Enter.cab = nuevo;cola = nuevo;
Struct nodo { int valor; struct nodo *anterior, struct nodo *siguiente, };
Struct nodo *cab, *cola, *nuevo;
nuevo
nuevoanteriornuevosiguiente
nuevovalor
001A Dirección de la Estructura
cabcola
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
No ta:En las listas doblemente encadenas podemos adicionar nodos tanto a la derecha como a la izquierda.
nodo
Nodoanterior Nodosiguiente
Nododatoq
qanterior q siguienteqvalor
q
qanterior q siguienteqvalor
Alimentar a la Izquierda Alimentar a la Derecha
nuevocabcola
Primer Nodo
Ing. Heiver Cuesta Dávila
INICIOAGREGAR A LA IZQUIERDA
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 nullnull
No ta:Si desea alimentar nodos a la Izquierda la estructura se alimenta así:
nodo
Nodoanterior Nodosiguiente
Nododatoq
qanterior q siguienteqvalor
Alimentar a la Izquierda
nuevocabcola
Primer Nodo
q = Localizar
Ejemplo de ingreso a la Izquierda:
Ing. Heiver Cuesta Dávila
q
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 nullnull
No ta:Si desea alimentar nodos a la Izquierda la estructura se alimenta así:
nodo
Nodoanterior Nodosiguiente
Nododato
null
q
qanterior q siguienteqvalor
Alimentar a la Izquierdanuevocabcola
Primer Nodo
q = Localizarqanterior = null;
001A
002A
Ejemplo de ingreso a la Izquierda:
q
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 nullnull
Nota:Si desea alimentar nodos a la Izquierda la estructura se alimenta así:
nodo
Nodoanterior Nodosiguiente
Nododato
nullnull
q
qanterior q siguienteqvalor
Alimentar a la Izquierdanuevocabcola
Primer Nodo
q = Localizarqanterior = null;qsiguiente = null;
001A
002A
Ejemplo de ingreso a la Izquierda:
q
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 nullnull
Nota:Si desea alimentar nodos a la Izquierda la estructura se alimenta así:
nodo
Nodoanterior Nodosiguiente
Nododato
200 nullnull
q
qanterior q siguienteqvalor
Alimentar a la Izquierdanuevocabcola
Primer Nodo
q = Localizarqanterior = null;qsiguiente = null;Cout << “Digitar Datos”;Cint >> qvalor; //Dato ingresado 200
001A
002A
Ejemplo de ingreso a la Izquierda:
q
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 nullnull
Nota:Vamos a Proceder a Unir los Dos Nodos así:
nodo
Nodoanterior Nodosiguiente
Nododato
200 001Anull
qanterior q siguienteqvalor
Alimentar a la Izquierda
nuevocabcola
Primer Nodo
q = Localizarqanterior = null;qsiguiente = null;Cout << “Digitar Datos”;Cint >> qvalor; //Dato ingresado 200qsiguiente = cab;
001A002A
Ejemplo de ingreso a la Izquierda:
q
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 null002A
Nota:Vamos a Proceder a Unir los Dos Nodos así:
nodo
Nodoanterior Nodosiguiente
Nododato
200 001Anull
q
qanterior q siguienteqvalor
Alimentar a la Izquierda
nuevocabcola
Primer Nodo
q = Localizarqanterior = null;qsiguiente = null;Cout << “Digitar Datos”;Cint >> qvalor; //Dato ingresado 200qsiguiente = cab;cabanterior = q;
001A002A
Ejemplo de ingreso a la Izquierda:
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 null002A
No ta:Ahora corremos la cabecera al nuevo Nodo:
nodo
Nodoanterior Nodosiguiente
Nododato
200 001Anull
q
qanterior q siguienteqvalor
Alimentar a la Izquierda
nuevocab
cola
Primer Nodo
q = Localizarqanterior = null;qsiguiente = null;Cout << “Digitar Datos”;Cint >> qvalor; //Dato ingresado 200qsiguiente = cab;cabanterior = q;cab = q;
001A002A
Ejemplo de ingreso a la Izquierda:
FINAGREGAR A LA IZQUIERDA
INICIOAGREGAR A LA DERECHA
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 nullnull
Nota:Si desea alimentar nodos a la Derecha de la estructura se alimenta así:
nodo
Nodoanterior Nodosiguiente
Nododatoq
qanterior q siguienteqvalor
Alimentar a la Derecha
nuevo
cola
Primer Nodo
q = Localizar
Ejemplo de ingreso a la Derecha:
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 nullnull
Nota:Si desea alimentar nodos a la Derecha de la estructura se alimenta así:
nodo
Nodoanterior Nodosiguiente
Nododato
null
q
qanterior q siguienteqvalor
Alimentar a la Derecha
nuevo
cola
Primer Nodo
q = Localizarqanterior = null;
001A
003b
Ejemplo de ingreso a la Derecha:
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 nullnull
Nota:Si desea alimentar nodos a la Derecha la estructura se alimenta así:
nodo
Nodoanterior Nodosiguiente
Nododato
nullnull
q
qanterior q siguienteqvalor
Alimentar a la Izquierdanuevo
cola
Primer Nodo
q = Localizarqanterior = null;qsiguiente = null;
001A
003b
Ejemplo de ingreso a la Derecha
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 nullnull
Nota:Si desea alimentar nodos a la Derecha de la estructura se alimenta así:
nodo
Nodoanterior Nodosiguiente
Nododato
400 nullnull
q
qanterior q siguienteqvalor
Alimentar a la Izquierdanuevo
cola
Primer Nodo
q = Localizarqanterior = null;qsiguiente = null;Cout << “Digitar Datos”;Cint >> qvalor; //Dato ingresado 400
001A
003b
Ejemplo de ingreso a la Izquierda:
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 nullnull
Nota:Vamos a Proceder a Unir los Dos Nodos así:
nodo
Nodoanterior Nodosiguiente
Nododato
400 NULL001A
q
qanterior q siguienteqvalor
Alimentar a la Izquierda
nuevo
cola
Primer Nodo
q = Localizarqanterior = null;qsiguiente = null;Cout << “Digitar Datos”;Cint >> qvalor; //Dato ingresado 200qanterior = cola;
001A
003b
Ejemplo de ingreso a la Derecha:
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 003boo2a
Nota:Vamos a Proceder a Unir los Dos Nodos así:
nodo
Nodoanterior Nodosiguiente
Nododato
400 NULL001A
q
qanterior q siguienteqvalor
Alimentar a la Izquierda
nuevo
cola
Primer Nodo
q = Localizarqanterior = null;qsiguiente = null;cout << “Digitar Datos”;cint >> qvalor; //Dato ingresado 400qanterior = cola;colasiguiente = q;
001A 003b
Ejemplo de ingreso a la Derecha:
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 003boo2a
Nota:Ahora corremos la cola al nuevo nodo así:
nodo
Nodoanterior Nodosiguiente
Nododato
400 NULL001A
q
qanterior q siguienteqvalor
Alimentar a la Izquierda
nuevo cola
Primer Nodo
q = Localizarqanterior = null;qsiguiente = null;Cout << “Digitar Datos”;Cint >> qvalor; //Dato ingresado 200qanterior = cola;colasiguiente = q;cola = q;
001A 003b
Ejemplo de ingreso a la Izquierda:
FINAGREGAR A LA DERECHA
UNIVERSIDAD ANTONIO NARIÑOEstructuras de Datos
Tema: Listas Doblemente Encadenadas
50 003b002A
Finalmente la Lista debe quedar de la siguiente manera.
nodo
200 001ANULL 400 NULL001A
q
Segundo nodo Tercer nodo
nuevocabcola
Primer Nodo001A 003b002A
Vemos que los apuntadores cab y cola se han movido para cada extremo.Si seguimos alimentando la Lista no olvidar que cab y cola deben seguirseMoviendo para el extremo que les corresponde.
GRACIAS
