ListasLigadas_08b

Programacin I 2010

Lenguaje de programacin C - 08

M.C. Yalu Galicia Hdez. (FCC/BUAP) 1

M.C. Yalu Galicia Hdez. (FCC/BUAP)1

Estructuras de datos

Listas ligadas simples



La representacin de la informacin es fundamental en Ciencias de la Computacin. El propsito principal de la mayora de los programas de computadoras es almacenar y recuperarinformacin, adems de realizar clculos.

Una estructura de datos es cualquier representacin de datos y sus operaciones asociadas.

Una estructura de datos es una organizacin o estructuracin de una coleccin de elementos .



Estticas (tradicionales)

Arreglos, matrices, registros (structs)


Dinmicas

lineales: pilas, colas y listas

no lineales: rboles y grfos

Recordando

Hemos visto como estructuras de datos a los vectores, matrices y cadenas.

Estas estructuras agrupan en un mismo nombre a un conjunto de elementos del mismo tipo.

M.C. Yalu Galicia Hernndez 4

H O L A \0

0 1 2 3 4 5 6 7

0 1 2 3 4

3

5 6

2

0

1

2

Los registros o estructuras

Un registro o estructurason colecciones de variables relacionadas bajo un mismo nombre.

Las estructuras pueden contener variables de diferentes tipos de datos

A los elementos de un registro se les denomina campos o miembros. Cada campo tiene su propio nombre.

M.C. Yalu Galicia Hernndez 5

n o m b r e

promedio

dato

char

float

int

Struct

El segundo campo se llama

promedio



En las estructuras de datos estticas, el tamao en memoria se establece durante la compilacin y permanece inalterable durante la ejecucin del programa.

Las estructuras de datos dinmicas crecen y se contraen a medida que se ejecuta el programa.

Programacin I 2010





Estructuras de datos dinmicas

Listas ligadas o enlazadas simples


Una lista ligada o enlazada es una estructura de datos dinmica, esto es, que crece y se reduce durante la ejecucin.

Una lista ligada es una coleccin lineal de elementos; donde cada elemento, conocido como nodo, est conectado mediante una liga o enlace , y tiene un nico sucesor y un nico antecesor

Nodo

Dato Dato Dato Dato

cabeza

Liga o enlace

Acceso a la lista


Se puede tener acceso a una lista ligada mediante un apuntador al primer nodo de la lista, llamado generalmente cabeza o inicio.

El acceso a los nodos subsecuentes se obtiene mediante un referencia de enlace almacenado en cada nodo.

Por convencin, el enlace en el ltimo nodo de la lista se establece como nulo (NULL), para marcar el final de la misma

Como los datos en una lista se almacenan dinmicamente, cada nodo se crea en tiempo de ejecucin, segn el usuario lo requiera.

Listas ligadas

10

Cada nodo esta constituido por dos campos: Informacin o dato (que puede ser cualquier tipo de dato) y un enlace o liga (apuntador).

Un nodo se implementa se la siguiente manera:

dato

Nodo

sgtetypedef struct nodo_ {

int dato; //informacin

struct nodo *sgte; //enlace

} Nodo;



Para marcar el inicio o cabeza de la lista se utiliza un apuntador al nodo que est al inicio de la lista, llamado normalmente cabeza, inicio o principio.

Opcionalmente se puede contar con una referencia al ltimo nodo de la lista, llamado generalmente cola, final o ltimo.

La cabeza de la lista es la nica forma de acceder a los elementos de esta.

Nodo

5 3 8 20

Nodo Nodo Nodo

iniciofinal

Listas Ligadas


Una lista ligada sin ningn elemento se llama lista vaca, y se representa poniendo la variable inicio a null.

Si existe la variable final, tambin va a null.

inicio final Lista vaca

Programacin I 2010



Operaciones en Listas enlazadas


Las operaciones bsicas que podemos realizar en una lista son: Creacin: crear una lista vaca. Insercin: aadir elementos (nodos) a la lista en

alguna posicin especfica: Al inicio

Al final

Entre dos nodos de la lista

Eliminacin: quitar un nodo de la lista de alguna posicin especfica Al inicio

Al final

Dato especfico x (que puede estar entre dos elementos)

Operaciones en Listas enlazadas

14

Recorrido: Moverse sobre los elementos de la lista, partiendo del inicio y llegando al final de la misma.

Mostrar: Recorrer la lista mostrando los elementos en esta.

Bsqueda: Recorrer la lista para verificar la existencia de un elemento dado dentro de la lista.

Ordenamiento: colocar en algn orden especfico (ascendente o descendente) los elementos de la lista.

Implementando una Lista Enlazada


#include #include

//declara el tipo del nodotypedef struct nodo_{

int dato;struct nodo *sgte;

} Nodo;

//declarar como globales el inicio y final de la listaNodo *inicio;

Nodo *fin;

int main() {//establece la lista como vaca

inicio = NULL;fin = NULL;

}

Crear un nuevo nodo


Los elementos (nodos) de una lista ligada se van creando dinmicamente, esto es, en tiempo de ejecucin, cada vez que el usuario inserta un nuevo nodo a la lista.

Para crear un nuevo nodo, se utiliza la funcin malloc(en stdlib.h) cuyo prototipo es.

void *malloc(nmero de bytes);

Para obtener el numero de bytes de un tipo especfico se usa la funcin sizeof(tipo).

Entonces para crear un nodo, la instruccin correcta es:Nodo *nuevo = (Nodo *) malloc (sizeof(Nodo));

Donde Nodo es una estructura creada por el usuario.

Si no hay memoria disponible malloc devolver NULL

Mostrar contenido de la lista


Para mostrar el contenido de la lista tenemos que considerar dos situaciones: Si la lista esta vaca (inicio y fin son NULL),

entonces no hacer nada solo indicar lista vaca Si la lista tiene al menos un elemento

Crear un apuntador auxiliar e inicializarlo con el inicio de la lista (el apuntador inicio nunca se debe perder).

Recorrer la lista utilizando la variable auxiliar hasta que sea NULL (fin de la lista)

dato

2 5 8 10 15

inicio fin

Nodo *aux = inicio //aux apunta donde apunta iniciowhile (aux != NULL) {

printf(%d , aux -> dato); //dato del nodo apuntado por auxaux = aux -> sgte; //aux apunta donde apunta sgte

}

aux aux aux aux auxaux

sgte

Bsqueda de un dato


Para buscar un elemento de la lista tenemos que considerar dos situaciones: Si la lista esta vaca (inicio y fin son NULL), entonces

regresar NULL para indicar que no se encontr Si la lista tiene al menos un elemento

Inicializar un apuntador auxiliar con el inicio de la lista Recorrer la lista hasta que aux sea NULL, al mismo tiempo

que se va comparando el nodo apuntado por aux con el elemento a buscar. Si se encuentra regresar aux.

dato

2 5 8 10 15

inicio fin

Nodo *aux = inicio //aux apunta donde apunta iniciowhile (aux != null && aux->dato != x) //busca el dato

aux = aux-> sgte;return aux;

aux aux aux aux auxaux

sgte

Programacin I 2010



Insertar al inicio


Para insertar al inicio de una lista enlazada tenemos que considerar dos situaciones

Si la lista esta vaca (inicio y fin son NULL)

Si la lista tiene al menos un elemento

inicio finNodo *nv = (Nodo *) malloc(sizeof(Nodo)); nv->dato = dato;

nv->sgte = NULL; if(inicio == NULL && fin == NULL) {

inicio = nv;fin = nv;

}else {

nv->sgte = inicio;inicio = nv;

}

5nuevo

3nuevo

sgte

M.C. Yalu Galicia Hdez. (FCC/BUAP)

20

Para insertar al final, nuevamente tenemos que considerar dos situaciones

Si la lista esta vaca (inicio y fin son Null)

Si la lista tiene al menos un elemento

Insertar al fin

M.C. Yalu Galicia Hdez. (FCC/BUAP)

inicio finNodo *nv = (Nodo *) malloc(sizeof(Nodo)); nv->dato = dato;

nv->sgte = NULL; if(inicio == NULL && fin == NULL) {

inicio = nv;fin = nv;

}else {

fin->sgte = nv;fin = nv;

}

5nuevo

3nuevo

sgte

Actividad Individual


Supn que cuentas con una lista como la que se muestra, en la que no se tiene el apuntador al final de la lista.

Implementa la funcin insertarFinal, la cual permita insertar el dato 3 .

dato

2 5 8 15

inicio

sgte

3nuevo

Insertar entre dos nodos

22

Para insertar entre dos nodos, tenemos que considerar dos situaciones: Si la lista esta vaca (inicio y fin son Null) Si la lista tiene al menos un elemento, localizar

posicin del nuevo nodo a insertar. Por ejemplo despus del 5 Se necesita otro apuntador (aux). En donde se coloca?

Insertar nuevo nodo

17 5 8 56 34

inicio finaux

9nuevo sgte

Solucin


Antes de continuar con la funcin insertar, vamos a crear dos funciones que nos sern muy tiles

Nodo * creaNodo(int valor)

{Nodo *nv =(Nodo *) malloc(sizeof(Nodo)); //solicita memoria

nv->dato = valor; //coloca el valor deseado en el campo dato

nv->sgte = NULL; //inicialmente siempre ponemos el apuntador a NULLreturn nv; //regresa la direccin de memoria donde est el nodo

}

int estaVacia(){

if(inicio == NULL && fin == NULL)

return 1;return 0;

}

Solucin


void insertarDespues(int elemento, int dato)

{

Nodo *nv, *aux;

nv = creaNodo(dato);

if(estaVacia()) { //solo insertar

inicio = fin = nv; //ambos apuntan al mismo nodo

}

else { //hay al menos un dato

aux = inicio;

while(aux!= NULL && aux->dato != elemento)

aux = aux -> sgte;

if(aux != NULL) //si se encontr elemento, insertar despus

{

nv -> sgte = aux -> sgte;

aux -> sgte = nv;

}

}

}

Programacin I 2010



Actividad Individual


Implementa la funcin insertarAntes(x, y)

Insertar un nodo antes de otro.

Por ejemplo insertar el nodo con dato x = 9 antes del nodo con dato y =15

2 6 15 23 57

inicio fin

9nuevo

Eliminar del inicio


Para eliminar del inicio tenemos que considerar tres situaciones:

Si la lista esta vaca (inicio y fin son Null), no hacer nada, solo indicar lista vaca

Si la lista tiene solo UN elemento (inicio == fin), entonces eliminarlo y actualizar inicio y fin a Null.

Si la lista tiene ms de un elemento

Donde se deben colocar el otro apuntador?

2 65 8 23 15

fininicio inicio

Nodo *aux = inicio;inicio = inicio -> sgte; //inicio se recorre uno

Free(aux); //libera la memoria

Eliminar del final


Para eliminar del final tenemos que considerar tres situaciones: Si la lista esta vaca (inicio y fin son null), no hacer

nada, solo indicar lista vaca Si la lista tiene solo UN elemento (inicio == fin),

entonces eliminarlo y actualizar inicio y fin a Null. Si la lista tiene ms de un elemento

19 5 3 10 15

inicio fin

tmp

Nodo *tmp = inicio; //tmp apunta donde apunta iniciowhile (tmp -> sgte != fin) tmp = tmp -> sgte;

fin = tmp; //fin apunta donde apunta tmptmp = tmp -> sgte;

fin -> sgte = null;Free(tmp); //libera memoria

tmp tmp tmp

fin

Eliminar un dato


Para eliminar un elemento especfico, tenemos que considerar varias situaciones:

Localizar el elemento a borrar (por ejemplo el 8) Cuantos apuntadores auxiliares se necesitan?

Donde se deben colocar?, en el nodo con el dato o en el nodo anterior?

2 15 8 10 35

inicio fin

Nodo *act, *ant; ant = act = inicio;while (act != NULL && act->dato != x) { ant=act; act=act->sgte; }

if (act != null) { ant->sgte = act->sgte;if(act == fin) fin = ant;

free(act); }

ant act actant actant

Eliminar un dato

29

Si la lista esta vaca (inicio y fin son Null), no hacer nada, solo indicar lista vaca

Qu pasa si el elemento a borrar est al inicio? (por ejemplo el 2) Llamar a EliminarDelInicio()

Qu pasa si el elemento a borrar est al final? (por ejemplo el 15) Llamar a EliminarDelFinal()

2 9 8 23 15

inicio fin

30

Actividad IndividualActividad: Escribir el mtodo para eliminar un elemento antes de otro.

Ejemplo borrar el elemento antes del 9

6 15 9 2 45

inicio fin

Programacin I 2010



Qu hemos aprendido?

Yal Galicia Hdez. (FCC-BUAP)31

Documents

ListasLigadas_08b