Listas C

From Movaxes

(Difference between revisions)
(→Lista Lineal)
Line 52: Line 52:
</pre>
</pre>
-
'''(actualmente escribiendo código de implementación de listas lineales...)'''
+
====Implementación de Lista Lineal====
 +
 
 +
En este ejemplo se implementa una lista lineal, con las siguientes funciones:
 +
*nuevo_nodo = crea un nodo antes del indicado
 +
*borrar_nodo = borra el nodo pasado como argumento
 +
*buscar_nodo = busca el nodo que tenga el valor pasado como argumento
 +
*es_vacia = devuelve 1 si la lista esta vacia
 +
*mostrar_lista = muestra la lista completa
 +
 
 +
<pre>
 +
#include <stdlib.h> //para malloc
 +
#include <stdio.h> //para printf
 +
 
 +
//nuestra estructura
 +
typedef struct elemento
 +
{
 +
int dato; //valor
 +
struct elemento *siguiente; //apunta al siguiente nodo o es NULL
 +
} nodo;
 +
 
 +
nodo *lista = NULL; //creamos la lista
 +
 
 +
void mostrar_lista(nodo *list); //muestra lista completa
 +
void nuevo_nodo(nodo **list, int valor); //crea un nuevo nodo al principio de la lista
 +
char es_vacia(nodo *list); //regresa 1 si la lista es vacia
 +
void borrar_nodo(nodo **list); //borra el primer nodo de la lista
 +
nodo **buscar_nodo(nodo **list, int valor); //busca el nodo con este valor
 +
 
 +
/**************/
 +
int main(void)
 +
{
 +
int i;
 +
for(i=1; i<11; i++) nuevo_nodo(&lista, i); //creamos lista del 1 al 10
 +
borrar_nodo(buscar_nodo(&lista,5)); //borramos el nodo con valor 5
 +
nuevo_nodo(buscar_nodo(&lista,4),5); //agregamos el nodo con valor 5
 +
mostrar_lista(lista); //mostramos la lista completa
 +
return 0;
 +
}
 +
 
 +
//regresa 1 si está vacia
 +
char es_vacia(nodo *list)
 +
{
 +
return(list==NULL); //1 si la lista esta vacia
 +
}
 +
 
 +
//Muestra en pantalla todos los nodos
 +
void mostrar_lista(nodo *list)
 +
{
 +
if(es_vacia(list)) printf("La lista esta vacia\
 +
");
 +
while(list!=NULL) //mientras encontremos nodos
 +
{
 +
printf("%p es = %i, siguiente es = %p\
 +
", list, list->dato, list->siguiente);
 +
list = list->siguiente; //apuntamos al siguiente
 +
}
 +
}
 +
 
 +
//inserta un nodo al principio de la lista
 +
void nuevo_nodo(nodo **list, int valor)
 +
{
 +
if(list==NULL) return;
 +
nodo *nuevo = (nodo *)malloc(sizeof(nodo)); //creamos el nuevo nodo
 +
nuevo->siguiente = *list; //el nuevo nodo apunta al primero
 +
nuevo->dato = valor; //ponemos el dato
 +
*list = nuevo; //el primer nodo es ahora el nuevo
 +
}
 +
 
 +
//borra el primer nodo de la lista o el nodo indicado
 +
void borrar_nodo(nodo **list)
 +
{
 +
if(list==NULL) return;
 +
nodo *primero = *list; //copiamos el nodo
 +
if(es_vacia(primero)) //esta vacio?
 +
{
 +
printf("Error al borrar, lista vacia?\
 +
");
 +
return; //regresar
 +
}
 +
*list = primero->siguiente; //apuntamos al siguiente del que va a ser borrado
 +
free(primero); //borramos
 +
}
 +
 
 +
//busca el nodo que contenga este valor y lo regresa al encontrarlo
 +
nodo **buscar_nodo(nodo **list, int valor)
 +
{
 +
while(*list!=NULL) //mientras encontremos nodos
 +
{
 +
if((*list)->dato == valor) return list; //si lo encontramos lo regresamos
 +
list = &(*list)->siguiente; //apuntamos al siguiente
 +
}
 +
printf("No hay nodo con el valor = %i\
 +
",valor);
 +
return NULL; //no lo encontramos
 +
}
 +
</pre>
 +
 
 +
'''NOTA:''' por favor indicarme cualquier bug o mejora en la implementación (gracias!!).
===Lista Circular===
===Lista Circular===

Revision as of 14:52, 12 March 2007

Contents

Listas

Las listas enlazadas son usadas como base para muchos otros tipos de estructuras de datos como la pila (stacks), cola (queue), etc.

Lista Contigua

Es una lista en la cual los elementos son adyacentes en la memoria y tiene un límite sobre la cantidad de elementos que puede contener. Su implementación e suele hacerce por medio de arreglos (arrays) por lo que se procesa como un array unidimensionales.

Uno de los inconvenientes de usar las listas contiguas es que tienen un límite de elementos posibles.

Listas Enlazadas

Terminología:

  • Nodo: se refiere a uno de los elementos en la lista
  • Campo: se refiere a uno de los componentes de un nodo (Un nodo tiene al menos dos campos: dato o valor y enlace)

Lista Lineal

Son aquellas en las cuales los elementos no están almacenados de forma adyacente, por lo cual cada elemento almacena la dirección del siguiente elemento de la lista. Esta es mucho más potente y flexible que las listas contiguas, por ejemplo, no requiere el desplazamiento de otros elementos para poder insertar uno nuevo.

El último elemento (nodo) contiene el valor NULL ya que no apunta a ningún elemento por ser este el último. Esta estructura de dato debe contener al menos dos campos, un valor (sea un int, char, etc) y un puntero al siguiente nodo.

Para insertar un nuevo elemento lo único que se hace es cambiar el puntero del elemento anterior al nuevo elemento y este contiene ahora el puntero al siguiente elemento. Así suponiendo que tenemos un elemento número 40 en nuestra lista, este apunta al número 41, si queremos ingresar un nuevo nodo entre estos elementos lo único que necesitamos es que el número 40 ahora apunte al nuevo nodo que ahora es el número.

Implementación de un elemento (nodo): 

typedef struct elemento
{
	int dato; //esto puede ser cualquier tipo de dato (o datos)
	struct elemento *siguiente;
} nodo;

Implementación de nuevo_nodo: 

void nuevo_nodo(int valor, nodo *enlace)
{
	nodo *s;
	s = (nodo *)malloc(sizeof(nodo));
	s->dato = valor;
	s->siguiente = enlace;
}

Para crear el primer nodo y empezar así la lista usamos: 

primero = nuevo_nodo(1,NULL);

Para crear un segundo nodo usamos: 

primero = nuevo_nodo(2,primero);

Implementación de Lista Lineal

En este ejemplo se implementa una lista lineal, con las siguientes funciones:

  • nuevo_nodo = crea un nodo antes del indicado
  • borrar_nodo = borra el nodo pasado como argumento
  • buscar_nodo = busca el nodo que tenga el valor pasado como argumento
  • es_vacia = devuelve 1 si la lista esta vacia
  • mostrar_lista = muestra la lista completa 
#include <stdlib.h> //para malloc
#include <stdio.h> //para printf

//nuestra estructura
typedef struct elemento
{
	int dato; //valor
	struct elemento *siguiente; //apunta al siguiente nodo o es NULL
} nodo;

nodo *lista = NULL; //creamos la lista

void mostrar_lista(nodo *list); //muestra lista completa
void nuevo_nodo(nodo **list, int valor); //crea un nuevo nodo al principio de la lista
char es_vacia(nodo *list); //regresa 1 si la lista es vacia
void borrar_nodo(nodo **list); //borra el primer nodo de la lista
nodo **buscar_nodo(nodo **list, int valor); //busca el nodo con este valor

/**************/
int main(void)
{
	int i;
	for(i=1; i<11; i++) nuevo_nodo(&lista, i); //creamos lista del 1 al 10
	borrar_nodo(buscar_nodo(&lista,5)); //borramos el nodo con valor 5
	nuevo_nodo(buscar_nodo(&lista,4),5); //agregamos el nodo con valor 5
	mostrar_lista(lista); //mostramos la lista completa
	return 0;
}

//regresa 1 si está vacia
char es_vacia(nodo *list)
{
	return(list==NULL); //1 si la lista esta vacia
}

//Muestra en pantalla todos los nodos
void mostrar_lista(nodo *list)
{
	if(es_vacia(list)) printf("La lista esta vacia\
");
	while(list!=NULL) //mientras encontremos nodos
	{
		printf("%p es = %i, siguiente es = %p\
", list, list->dato, list->siguiente);
		list = list->siguiente; //apuntamos al siguiente
	}
}

//inserta un nodo al principio de la lista
void nuevo_nodo(nodo **list, int valor)
{
	if(list==NULL) return;
	nodo *nuevo = (nodo *)malloc(sizeof(nodo)); //creamos el nuevo nodo
	nuevo->siguiente = *list; //el nuevo nodo apunta al primero
	nuevo->dato = valor; //ponemos el dato
	*list = nuevo; //el primer nodo es ahora el nuevo
}

//borra el primer nodo de la lista o el nodo indicado
void borrar_nodo(nodo **list)
{
	if(list==NULL) return;
	nodo *primero = *list; //copiamos el nodo
	if(es_vacia(primero)) //esta vacio?
	{
		printf("Error al borrar, lista vacia?\
");
		return; //regresar
	}
	*list = primero->siguiente; //apuntamos al siguiente del que va a ser borrado
	free(primero); //borramos
}

//busca el nodo que contenga este valor y lo regresa al encontrarlo
nodo **buscar_nodo(nodo **list, int valor)
{
	while(*list!=NULL) //mientras encontremos nodos
	{
		if((*list)->dato == valor) return list; //si lo encontramos lo regresamos
		list = &(*list)->siguiente; //apuntamos al siguiente
	}
	printf("No hay nodo con el valor = %i\
",valor);
	return NULL; //no lo encontramos
}

NOTA: por favor indicarme cualquier bug o mejora en la implementación (gracias!!).

Lista Circular

Esta estructura es una modificación de la lista inicial porque el último nodo en lugar de contener NULL apunta al primer nodo.

Lista doblemente enlazada

Funciona de forma parecida a la lista lineal pero en esta cada nodo apunta al anterior (excepto el primero que contiene NULL).

Listas doblemente enlazadas circulares

Estas contienen en el primer nodo un puntero (anterior) al último nodo y el último nodo contiene un puntero (siguiente) al primer nodo.



Retrieved from "http://editthis.info/movaxes/Listas_C"
Personal tools