unidad 5 listas enlazadas bibliografía: algoritmos y estructuras de datos de aguilar y martinez....
TRANSCRIPT
Unidad 5 Listas Enlazadas
•Bibliografía: “Algoritmos y Estructuras de datos” de Aguilar y Martinez. Unidad 9
•Autor: Ing Rolando Simon Titiosky.
Fundamentos TeóricosSi en tiempo de Diseño del Algoritmo: • Se conoce la cantidad de elementos a EnListar.
– Podemos usar Organización Estática de Memoria: Arrays.• Obliga en tiempo de Compilación a reservar la memoria a usar.• Implementaciones mas rápidas: Ya se Gestionó la Memoria.• Uso Ineficiente de Memoria: Una posición que no se utiliza no
puede ser usada por nadie mas.• Si no se conoce la cantidad de elementos a EnListar
– Debemos usar Organización Dinámica: Listas Enlazadas.• Colección de Nodos lógicamente uno detrás de otro. • C/Nodo y se compone al menos de 2 campos
– La información propiamente dicha– Un puntero al próximo elemento de la lista.
InfoPtro
InfoPtro
InfoPtro
Info Null
Ptro
CAB
Clasificación de Listas Enlazadas
Apunta al PrimeroNullUltimo Nodo
Forward y Backward Circular
Forward Circular
Forward y Backward
ForwardRecorrido Eficiente
1 al sucesor1al predecesor
1 al sucesor1 al sucesor1al predecesor
1 al sucesor# Enlaces del Nodo
Circular Doblemente Enlazada
Circular Simplemente Enlazada
Doblemente Enlazada
Simplemente Enlazada
• Se pueden implementar con Arrays o Punteros.• Todas tiene Cabeza y Cola.
– Una Lista Vacía tiene su Cabeza=Cola=Null• Pueden almacenar cualquier tipo de información
– Las inserciones se pueden realizar en cualquier punto de la lista• Los elementos se insertan ordenados
Operaciones Típicas en Listas• Inicialización o creación• Insertar elementos en la lista
– Al principio, al final– Antes o después de la posición i– Antes o después del elemento con la información x.
• Eliminar elementos en la lista– La cabeza, el final– El elemento de la posición i– El elemento con la información x.
• Buscar elementos en la lista– El elemento de la posición i– El elemento con la información x.
• Modificar– El elemento de la posición i– El elemento con la información x.
• Recorrer los Nodos de la Lista• Comprobar si la lista esta vacía.• Cantidad de elementos de una lista.• Intercambiar dos elementos de la lista• …
Especificación TAD Lista Simplemente Encadenada (SE)
Se hace una Especificación básica de ejemplo. Aunque está siempre ligada al asunto que se quiera resolver.
TAD Lista– (a1, a2, …ai, .., an) siendo n>=0; Si n=0 entonces Lista Vacia
• Sintaxis L Lista, x Lista, p puntero– ListaVacia(L): Inicializa la Lista L vacía.– EsVacia(L): Determina si L es vacía– Insertar(L, x, p): Inserta en la Lista L un nodo con el campo dato x,
delante del nodo de dirección p– Localizar(L, x): Localiza en L, el nodo con campo de información x.– Suprimir(L, x): Elimina en L, el nodo con campo de información x.– Anterior(L,x): Devuelve el Nodo anterior al nodo con campo de
información x.– ….
Ejemplo Simple de Listas SE
#include <stdio.h>#include <stdlib.h>
#define MX 99
typedef int Item;typedef struct Elemento{ Item dato;
struct Elemento* siguiente;} Nodo;
void inserPrimero(Nodo** cabeza, Item entrada);Nodo* crearNodo(Item x);…
Cargar una lista simplemente enlazada con números aleatorios hasta encontrar el número 0. Luego se muestran por pantalla solo aquellos que sean números pares.
Ejemplo Simple de Listas SE
void main(){ Item d;
Nodo *cabeza, *ptr;int k;cabeza = NULL; /* lista vacía */randomize();for (d = random(MX); d; ) /*Bucle termina cuando se genera el número 0*/{ inserPrimero(&cabeza, d);
d = random(MX);}for (k = 0, ptr = cabeza; ptr!=NULL; ptr = ptr -> siguiente) if (ptr -> dato%2 == 0) /* se recorre la lista para escribir los pares */
{ printf("%d ", ptr -> dato);k++;printf("%c",(k%12 ? ' ' : '\n')); /* 12 datos por línea */
}printf("\n\n");
}
Ejemplo Simple de Listas SENodo* crearNodo(Item x){ Nodo *a ;
a = (Nodo*)malloc(sizeof(Nodo)); /* asigna nuevo nodo */
a -> dato = x; a -> siguiente = NULL;return a;
}
void inserPrimero(Nodo** cabeza, Item entrada){ Nodo *nuevo ; nuevo = crearNodo(entrada); nuevo -> siguiente = *cabeza; *cabeza = nuevo;}
Grafica de Punteros Lista SE6
Ptro
10 NullPtro
CAB 3
Ptro
PtroNuevo 5 Null
Nuevo=crearNodo(5)
6Ptro
10Null
Ptro
CAB 3Ptro
Ptro
Nuevo 5
Nuevo–>Siguiente=*Cabeza
6Ptro
10Null
Ptro
CAB 3Ptro
Ptro
Nuevo 5
*Cabeza=Nuevo
Inserción al Final de la Lista SE
• Es menos eficiente pues hay que recorrer toda la lista.
Void inserFinal(Nodo** cabeza, Ítem entrada){ Nodo *ultimo;
ultimo=*cabeza;if(ultimo==NULL) /*lista vacía*/
*cabeza=crearNodo(entrada); else { for(;ultimo–>siguiente;)
ultimo=ultimo–>siguiente; ultimo–>siguiente=crearNodo(entrada);}
}
Algoritmo de Inserción de un Nodo entre 2 existentes SE
1. Asignar un nuevo nodo apuntado por el ptr nuevo• Si la lista está vacía se lo inserta como primer Nodo.
2. Buscar la posición del nodo Después, que contiene el campo dato de referencia.
• Si no existe (posición o referencia) No se Inserta.
3. Hacer que el nuevo–>siguiente apunte al nodo Despues–>siguiente, o Null si es el último.
4. Hacer que despues–>siguiente apunte al nuevo
1Ptro
6Ptro
DESPUES
Ptro10 Null
Ptro
CAB
NUEVO
void insertan(Nodo** cabeza, Ítem testigo, Item entrada){ Nodo *nuevo, *después;
nuevo = crearNodo(entrada);if (*cabeza == NULL) *cabeza = nuevo;else { int esta=0;
después=*cabeza;while ((despues->siguiente != NULL) && !esta){ if (después–>dato !=testigo) despues=despues–>siguiente;
else esta=1;}if (esta) /* Se enlasa el nuevo nodo */{ nuevo -> siguiente = despues -> siguiente;
despues -> siguiente = nuevo;}
}}
Inserción de un Nodo entre 2 existentes
1Ptro
6Ptro
3Ptro
10 NullPtro
CAB
4
Nuevo
PtroDespues
Búsqueda Por Contenido
• Parámetros:– cabeza: cabeza de lista
– destino: valor de referencia que se está buscando.
• Localiza un elemento por referencia del contenido.– Si lo encuentra devuelve su ptro. Sino devuelve NULL
Nodo * localizar(Nodo*cabeza, Ítem destino)
{ Nodo *indice;
for(indice=cabeza; indice!=NULL; indice=indice–>siguiente)
if(destino==indice–>dato) return indice;
return NULL;
}
Búsqueda por Posición
• Parámetros:– cabeza: cabeza de lista– posición: posición de referencia que se esta buscando.
• Localiza un elemento por referencia a su posición dentro de la lista.– Si lo encuentra devuelve su ptro. Sino devuelve NULL
Nodo * buscarPosicion(Nodo*cabeza, int posición){ Nodo *indice;
int i;indice=cabeza;for(i=1; (i<posición) && (indice!=NULL);i++)
indice=indice–>siguiente;return indice;
}
Eliminar un Nodo de la Lista SE• Se enlazará el nodo anterior con el siguiente al que se debe eliminar.
void eliminar (Nodo** cabeza, Item entrada){ Nodo* actual = *cabeza;
Nodo *anterior = NULL; int encontrado = 0;while ((actual!=NULL) && (!encontrado)) /* búsqueda del nodo y del anterior */
{ encontrado = (actual -> dato == entrada); if (!encontrado){ anterior = actual;
actual = actual -> siguiente;}
}if (actual != NULL) /* Enlace nodo anterior con siguiente. Si es NULL No existe elemento */
{ if (actual == *cabeza) /* distingue entre el nodo cabecera o el resto de la lista */
*cabeza = actual -> siguiente; else
anterior -> siguiente = actual -> siguiente;free(actual);
}}
Listas Doblemente Enlazadas (DE)• Cada elemento contiene 2 ptro: hacia atrás y hacia delante
en la Lista• Las Operaciones son las mismas que para las Simplemente
Enlazadas, pero aquí se pueden dar en ambas direcciones.• El Borrado supone realizar los enlaces entre el ptr del nodo
anterior con siguiente al que se desea eliminar.
NullNull
INS
Inserción
DEL
NullNull
Borrado
Creación de una Lista DEtypedef struct tipoNodo{ Item dato;
struct tipoNodo* adelante;struct tipoNodo* atras;
}Nodo;
void main(){ Nodo *cabeza,*ptr;
int n;cabeza = NULL; /* lista vacía */while (n!=0){ scanf (“%i”, &n);
inserPrim(&cabeza,n);}
}
Cargar una lista doblemente enlazada con números capturaods por consola hasta encontrar el número 0.
Nodo* crearNodo(Item x){ Nodo *a ;
a = (Nodo*)malloc(sizeof(Nodo));a -> dato = x;a -> adelante = a -> atras = NULL;return a;
}
void inserPrim(Nodo** cabeza, Item entrada){ Nodo* nuevo;
nuevo = crearNodo(entrada);nuevo -> adelante = *cabeza; /*Apuntará al primer elemento antes de la INS*/
nuevo -> atras = NULL; /*Nuevo apuntará a Cabeza*/
if (*cabeza != NULL)(*cabeza)-> atras = nuevo; /* cabeza es ptr de ptr: esta referencia es */
/*hacia el ptr atrás del elemento al que apunta cabeza*/
*cabeza = nuevo; /*cabeza apuntará al nuevo primer elemento*/
}
Creación de una Lista DE
Null nuevo
Insertar entre elementos DEYa se encontró el elemento anterior al punto de Inserción.Void insertar(Nodo **cabeza, Ítem entrada, Nodo *anterior){ Nodo *nuevo;
if ((*cabeza)==NULL) || anterior==NULL) /*Principio de Lista*/
inserPrim(&cabeza, entrada);else
{ nuevo=crearNodo(entrada);nuevo–>adelante=anterior–>adelante;if (anterior–>delante!=NULL) /*No es fin de lista*/
/*atrás del siguiente apunta al nodo nuevo*/ (anterior–>delante)–>atrás=nuevo;
anterior–>delante=nuevo;nuevo–>atrás=anterior;
}} Null ANTE
Null
nuevo
Eliminar entre Elementos DEvoid eliminar (Nodo** cabeza, Ítem entrada){ Nodo* actual = *cabeza;
int encontrado=0;while ((actual!=NULL) && (!encontrado) /*Búsqueda del Nodo*/
{ encontrado=(actual–>dato==entrada);if (!encontrado) actual=actual–>adelante;
}if (actual !=NULL) /*enlazará el anterior con el siguiente. */
{ if(actual==*cabeza) /*1er elemento de la lista */
{*cabeza = actual -> adelante; if (actual -> adelante != NULL)
(actual -> adelante) -> atras = NULL; /*El nuevo 1er elemento de la lista debe tener el ptr atrás igual a NULL*/
}else if (actual -> adelante != NULL) /*Nodo Intermedio*/
{(actual -> atrás) -> adelante = actual -> adelante; (actual -> adelante) -> atras = actual -> atras;}
else (actual -> atrás) -> adelante = NULL; /*Es el ultimo Nodo*/
free(actual); }
}ACT
NullNull
Lista Circular
• Idealmente No tiene ni principio ni fin.– Sigue existiendo Cabeza, pero es usada solo para
comenzar a recorrer la lista.• El Nodo Cola apunta al primer elemento de la
lista: Cola–>siguiente==cabeza.– Aunque esto puede variar pues no tiene primer
elemento de la lista• Las Operaciones posibles son las mismas que
en las otras listas.
InfoPtro
InfoPtro
InfoPtroPtro
CAB
Ejercicios Complementarios
1. Con Array, crear una lista doblemente enlazada que no tenga espacios vacíos intermedios.
• Además, implementar las operaciones básicas: Crear, Insertar, Borrar, Modificar.
2. Especificar e implementar un TAD string que permita manipular cadenas de caracteres.– Especifique al menos 10 operaciones.– Implemente al menos 4. Entre ellas, comprobar si
una determinada palabra es Palíndromo (la lectura directa o inversa son iguales. Ej: alila)