[ Foro de C ]

Ayuda listas doble enlazada

18-Aug-2010 00:06
javi asdl asdnpwnd
2 Respuestas

Buenas!!!!. A ver si me podeis echar una mano con esto de las listas, porque me estoy volviendo loco. JAJAJAJA.

A ver, en el ejemplo 82, usamos una lista simple. Eso lo entiendo. A partir de ahi, no se ni por donde empezar para hacer una lista doble enlazada. Se que tengo que crear otro puntero al dato anterior de la lista, pero a partir de ahi, nada mas, y tampoco se en que mejoraria el programa con una lista doble.

GRACIAS!!!!


18-Aug-2010 23:40
javi asdl asdnpwnd

Otra duda mas. En el ejemplo 82, cuando insertamos un elemento de la lista, con la funcion CrearLista ,si el campo numero este elemento es mayor que todas las fichas, es decir, se coloca al principio de la lista. En que momento, enlazamos el elemento anterior a ese???

No se si me he explicado bien
xDD

GRACIAS!!!


22-Aug-2010 22:50
Nacho Cabanes (+31)

Hola, Javi. Perdona el retraso en contestar. Vamos con tus dudas...

- Una lista doblemente enlazada tiene un puntero al dato anterior y otro al siguiente, efectivamente.

- Para añadir un dato, vas recorriendo en orden como harías con una lista simple, y cuando encuentras la posición en que debería quedar, reservas espacio, y enlazas con el dato siguiente y (esa es la "novedad") con el dato anterior.

- La mejora es en que puedes buscar "hacia atrás". Por ejemplo, si estás haciendo un diccionario y tienes que buscar un dato que empieza por Y, que tú sabes que estará más cerca del final que del principio, puedes empezar a buscarlo desde el final de la lista. Además, mejora otras cosas "menos importantes" de la lista simple: no hace falta ver "el siguiente del siguiente", sino que puedes tomarte la libertad de avanzar hasta que te pases... porque sabes que puedes retroceder.

- En cuanto al ejemplo 82, en la función CreaLista se crea una lista vacía, formada por un único elemento. Por eso el siguiente valor se pone a NULL. Se puede aprovechar para insertar el último dato en una lista que ya existe, sin necesidad de cambios (mira el último "else" de InsertaLista), o bien para insertar un dato intermedio si luego te acuerdas de cambiar el valor de "siguiente" para enlazar con el dato que debería haber a continuación (es lo que hace el primero de los "else"):


struct lista* CrearLista(int valor) {  /* Crea la lista, claro */
 struct lista* r;        /* Variable auxiliar */
 r = (struct lista*)
   malloc (sizeof(struct lista)); /* Reserva memoria */                          
 r->numero = valor;      /* Guarda el valor */
 r->sig = NULL;          /* No hay siguiente */
 return r;               /* Crea el struct lista* */
};


void InsertaLista( struct lista **lista, int valor) {
 struct lista* r;        /* Variable auxiliar, para reservar */
 struct lista* actual;   /* Otra auxiliar, para recorrer */

 actual = *lista;        
 if (actual)                           /*  Si hay lista */
   if (actual->numero < valor)         /*    y todavía no es su sitio */
     InsertaLista(&actual->sig,valor); /*   mira la siguiente posición */
   else {                     /* Si hay lista pero ya es su sitio */
     r = CrearLista(valor);   /* guarda el dato */
     r->sig = actual;         /* pone la lista a continuac. */
     *lista = r;              /* Y hace que comience en el nuevo dato */
   }
 else {              /* Si no hay lista, hay que crearla */
   r = CrearLista(valor);
   *lista = r;       /* y hay que indicar donde debe comenzar */
  }
}

¿Se podría escribir de forma más legible? Sí, un poco. Pero este tipo de fuentes nunca va a ser sencillo: el manejo de estructuras dinámicas es una de las posibilidades más complicadas de hacer en C.






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)