[Utu-emt-prog2-info] listas

Jue Ago 4 11:58:43 CEST 2011

fuente: transparencias de Gonzalo Pastor, 
http://en.wikipedia.org/wiki/List_%28computing%29 y producción propia

Listas

Las listas se usan para muchas cosas en la vida real (de materias, de 
palabras del diccionario, de letras de una palabra, de elementos de un 
conjunto) por lo tanto nos interesa poder representarlas en la computadora.

Para representarlo mediante una estructura estática se usa un array y un 
indice que indica la cantidad de elementos.

Cada elemento que insertemos en la Listas se hará de forma ordenada, 
mediante algún criterio. Si recorremos la lista todos los datos 
aparecerán ordenados.

Declaración

tipo lista[MAX_TAMANO];
int elementos; //indica cuantos elementos tiene la lista

ejemplo: int lista[10];
	   int elementos;

Crear lista vacía

elementos=0;

Insertar

Cuando agregamos datos debemos tener en cuenta 3 casos:

1. Insertar un elemento "e" en la primera posición de una lista
	if (elementos==10)
		printf("no hay lugar");
	else
	{
		for (int i=elementos;i>0;i--)
			lista[i]=lista[i-1];
		lista[0]=e;
		elementos++;
	}
2. Insertar un elemento "e" en la última posición de una lista
	if (elementos==10)
		printf("no hay lugar");
	else
	{

		lista[elementos]=e;
		elementos++;
	}
3. Insertar un elemento "e" a continuación de un nodo "n" cualquiera de 
una lista
	if (elementos==10)
		printf("no hay lugar");
	else
	{
		for (int i=elementos;i>n+1;i--)
			lista[i]=lista[i-1];
		lista[n+1]=e;
		elementos++;
	}	

Borrar

Es el proceso inverso al insertado. Por lo tanto existen los mismos 3 
casos anteriores, pero a la inversa. A esto se le agrega la complejidad 
de que debe ingresarse y buscar el dato a eliminar.

Quitar un elemento "e" de una lista

if (elementos==0)
	printf("no hay elementos");
else
{
	int i=0;
	while (i<elementos && lista[i]!=e)
	{
		i++;
	}
	for (int h=i;h<elementos-1;h++)
		lista[h]=lista[h+1]; 		
	}
	if (i<elementos)
		elementos--;
}

Un caso particular es el vaciado donde se borran todos los nodos.

elementos=0;

Ejercicios:

1.Hacer una función que devuelva la cantidad de elementos de una lista.
2.Hacer una función que devuelva el quinto elemento de una lista, en 
caso de que la lista tenga menos de 5 elementos debe devolver el último 
elemento de la lista.
3.Crear una lista con los elementos 1, 4, 5, 8
4.Hacer una función que devuelva el menor elemento de una lista de enteros.
5.Hacer una función que devuelva la suma de los elementos de la lista.
6.Quitar el elemento 5 de la lista del ejercicio 3.
7.Vaciar la lista del ejercicio 3.