Listas

Insertar al final de la lista

void insertarFin (struct nodo **L, struct info *x){

struct nodo *tmp;

struct nodo *aux;

tmp=(struct nodo *)malloc(sizeof(struct nodo));

tmp->siguiente=NULL;

if(*L==NULL) /* Lista vacía */

*L=tmp;

else { /* Lista con información */

aux=*L;

while (aux->siguiente !=NULL)

aux=aux->siguiente;

aux->siguiente=tmp;

}

}

Insertar en posición concreta (tras nodo determinado apuntado por p)

void insertarPos (struct nodo **L, struct nodo *p, struct info *x) {

struct nodo *tmp;

tmp=(struct nodo *)malloc (sizeof(struct nodo));

tmp->elemento=*x;

if (L==NULL){ /* Lista vacía */

tmp->siguiente=NULL;

*L=tmp;

}

else {

tmp->siguiente=p->siguiente;

p->siguiente=tmp;

}

}

Eliminar el elemento apuntado por p

void eliminar (struct nodo **L, struct nodo *p) {

struct nodo *tmp;

if (*L==p) /* Eliminar el primer elemento */

*L=p->siguiente;

else {

tmp=*L;

while (tmp->siguiente!=p)

tmp=tmp->siguiente;

/* tmp apunta al anterior */

tmp->siguiente=p->siguiente;

} 

free(p);

}

Calcular el tamaño de una lista

int tamagno (struct nodo **L) {

int n;

struct nodo *tmp;

tmp=*L;

n=0;

while (tmp!=NULL) {

n++;

tmp=tmp->siguiente;

}

return (n);

}

Comentario sobre tamaño

Las EDD nos las creamos nosotros y podemos decidir implementarlas de muy diversas formas.

Si se va a utilizar de forma intensiva la función tamagno, se puede modificar la implementación para hacer que esta función sea más eficiente (ya que tener que recorrer cada vez que es llamada todos los elementos no resulta especialmente eficiente).

Podríamos, por ejemplo, guardar explícitamente información sobre el número de elementos, de tal manera que la lista en vez de ser un único puntero al primer elemento, sería un struct que tendría el número de elementos además del puntero al primer elemento.

En caso de optar por esta implementación, tendríamos que asegurarnos que esa información se actualiza adecuadamente cada vez que se inserta o borra un elemento, en las correspondientes funciones.

Localizar (el primer elemento de la lista, que tiene un campo entero igual a uno fijado)

struct nodo *localizar(struct nodo**L, int x) {

struct nodo *tmp;

tmp=*L;

while ((tmp!=NULL) && ((tmp->elemento).campo_x!=x))

tmp=tmp->siguiente;

return tmp;

}

C realiza una evualuación cortocircuitada. Es decir, si en el anterior while, por ejemplo, no se cumple la primera condición, no continúa examinando la segunda.

De otro modo, el anterior código reventaría porque si fuera NULL intentaría leer el siguiente elemento pasado NULL, dando un fallo de segmentación.

Ejemplo de utilización

main() {

struct info c;

struct nodo *Lista;

struct nodo *p;

Lista=NULL;

c.campo_x=5;

insertarPrincipio(&Lista, &c);

c.campo_x=12;

insertarFin(&Lista, &c);

/* Ver contenido */

p=Lista;

while (p!=NULL){

printf(“%d”,(p->elemento).campo_x);

p=p->siguiente;

}

p=Lista; /* Apunta a “5” */

p=p->siguiente; /* Apunta a “12” */

c.campo_x=56;

/* Voy a insertar tras “12” */

insertarPos(&Lista, p, &c);

p=Lista; /* Apunta a 5 */

p=p->siguiente; /* Apunta a 12 */;

/* Voy a eliminar “12” */

eliminar(&Lista, p);

}

Listas ordenadas

Si necesitamos una lista ordenada tenemos dos alternativas:

è Manejar una lista genérica y ordenarla cuando haga falta (usando algoritmos similares que para ordenar vectores). Se puede ofrecer una operación de ordenación.

è Mantener una lista ordenada siempre. Modificaciones necesarias:

· Insertar. Ya no hay que indicar la posición. La función deberá encargarse de insertar en la posición adecuada.

· Localizar. Podemos detener la búsqueda cuando encontremos un elemento mayor que el que buscamos.

Para llevar a cabo lo anterior, hay que tener en cuenta que mecanismo vamos a utilizar.

Ejemplo de aplicación de las listas

Almacenar un polinomio. En este caso podría ser útil una lista de estructura del siguiente tipo:

struct info {

int exponente;

float coeficiente;

}