Sandy
17 de Febrero del 2004

Estoy teniendo dificultades en entender lo de
Listas encadenadas(enlazadas), por ejemplo en un archivo, cómo a través de listas leer del archivo, añadir información al archivo, buscar una información particular y borrar información del archivo.
Si no estoy pidiendo mucho y me pueden ayudar.
Gracias.
Sandy.

psugasti
17 de Febrero del 2004

¿que es exactamente lo que necesitarias? ¿Teoria, ejemplos? ¿Que necesitas hacer?

martin ribelotta
17 de Febrero del 2004

Las listas enlasadas son estructuras en memoria que contienen datos (de cualquier tipo) y pueden crecer indefinidamente (mientras alla memoria) a diferencia de los arrays estaticos y sin las complicaciones de los arrays dinamicos (que necesitan zonas contiguas de RAM)
Existen dos tipos basicos de listas enlasadas:
- Listas simplemente enlazadas
- Listas doblemente enlazadas
Las simplemente enlasadas son estructuras de datos que contienen (en el caso de, por ejemplo querer leer lineas de un archivo como lo aria el Less de UNIX/Linux)

typedef struct cLista {
char buffer[80];
struct cLista *next;
} TLista;

Buffer es un arreglo de chars donde se meten los datos (puede ser cualquier tipo de datos que queramos almacenar, lo mas usual es que sea un puntero a *void para almacenar cualquier dato, pero esto es mas complejo)
*next es un puntero al siguiente que sera NULL si no existe siguiente.
Para insertar algo en la lista debemos tener un puntero base que apunta al principio de la lista (en condicion inicial apunta a NULL) y una funcion como la que sigue:

TLista *base = NULL;

TLista *newLista (char d[])
{
TLista *ptr = malloc(sizeof(TLista))));
ptr->next = NULL;
strcmp(ptr->buffer, dato);
return ptr;
}

void inserta(char dato[], TLista *prev)
{
if (!prev) base = newLista(dato); /* Si no existe lista */
else {
/* Si ya existe pero no llego al final */
if (prev->next) insert(dato, prev->next);
/* Si ya es el final inserta aqui */
else prev->next = newLista(dato);
}
}

Para buscar el elemento TLista *q seria:

int pos (TLista *q) {
int i=0;
TLista *ptr = base;
while (ptr) {
if (ptr=q)
return i;
i++; ptr=ptr->next;
}
return -1;
}

Si no se encontro debuelve -1;
Para borrar *q de la lista seria:

void borrar (TLista *q, TLista *prev)
{
if (!prev) {
if (base == q) {
free (q);
base = NULL;
}
} else if (q==prev->next) {
prev->next = prev->next->next;
free(q);
}
}

Y para obtener el elemento n de la lista:

TLista *en (int n)
{
int i;
TLista *ptr = base;
for (i=0; ptr; ptr=ptr->next, i++) {
if (i==n) return ptr;
}
return NULL;
}

Estos algoritomos son aplicables a cualquier lista simplemente enlazada. Tambien existen las listas doblemente enlazadas que incluyen ademas de *next, un puntero a *prev que es un poquito mas dificil de mantener y ocupa un poco mas de RAM que las simples pero los algoritmos se acortan bastante y son mas confiables. No me enrroyo mas. El que quiera alguna esplicacion, por fabor escribame a [email protected]

PD: Los algoritmos son mas claros si se usan clases C++