[C] Listas enlazadas utilizando arreglos

[GGZ]

Las listas enlazadas implementadas con punteros tienen la flexibilidad de poder insertar elementos en cualquier parte de ellas sin mover los elementos anteriores ni posteriores, mientras que los arreglos no cuentan con esta flexibilidad.
Proponga una implementación de similar a listas enlazadas, pero de longitud fija, utilizando arreglos, y que provea esta flexibilidad.

Me maté pensandolo pero no me sale, no tengo alguna idea para empezar, ¿alguien que me pueda encaminar?, por favor.



Y tengo otra duda con un problema de tipos que tengo en mi cabeza al parecer(no tiene nada que ver con el anterior ejercicio):

Código (c) [Seleccionar] Expandir

SList slist_append(SList list, int data)
{
     SList newNode = malloc(sizeof(SNode));
     SList node;
     slist_data(newNode) = data;
     slist_next(newNode) = NULL;
     if (list == slist_nil()) {
        return newNode;
     }
     node = list;
     while (slist_next(node) != slist_nil()) {
           node = slist_next(node);
     }
     /* ahora 'node' apunta al ultimo nodo en la lista */
     slist_next(node) = newNode;
     return list;
}


¿Por qué retorna list, no sería node?
Si yo estoy trabajando con node y no con list, a list ni siquiera lo he tocado es porque es algún puntero o algo así?

No lo entiendo

Saludos!

[AlbertoBSD]

Hay un parte del codigo que dice..

Código (c) [Seleccionar] Expandir

node = list;

Tendriamos que ver la estructura de slist.

Ayer hice una implementacion similar

Un nodo en una lista doblemwnte ligada tiene 2 apuntadores.

Uno apunta an nodo anterior y otro al siguiente nodo.

Y Nodo Lista se podria interpretar que apunta al primer nodo y al ultimo nodo asi la lista completa sigue siendo del tipo nodo.

[MAFUS]

Hace una cosa extraña.

Está pensado para modificar la misma lista que se le pasa, pero en vez de modificar directamente el parámetro list lo que hace es modificarlo y regresar un puntero con el dato modificado. Seguramente el autor pensó en esa solución para dar un valor en caso de que list fuera NULL. Pero hubiera hecho lo mismo con un puntero a puntero y el resultado habría sido más natural.

Supongamos el siguiente trozo de código:

Código (c) [Seleccionar] Expandir


SList mi_lista = NULL;

mi_lista = slist_append(mi_lista, 5);

Ahora mi_lista pasa a tener un elemento con un valor en data de 5. Continuamos con la variable mi_lista tal y como la hemos dejado en el siguiente código:

Código (c) [Seleccionar] Expandir


mi_lista = slist_append(mi_lista, 7);
Ahora mi_lista tiene dos elementos, uno que contiene el 5 y otro que contiene el 7. Se puede representar así [5 , 7].

Pero qué pasaría si hubiera:

Código (c) [Seleccionar] Expandir


SList lista_uno = NULL;
SList lista_dos = NULL;

lista_uno = slist_append(lista_uno, 5);
lista_dos = slist_append(lista_uno, 7);
¿Era esto lo que esperaba el autor que se hiciera?

Casi mejor hubiera sido definir la función con un puntero a puntero.

Código (c) [Seleccionar] Expandir


void slist_append(SList * list, int data) {
    /* Implementación de la función */
}

/* Código y más código */

SList mi_lista = NULL;
slist_append(&mi_lista, 5);
slist_append(&mi_lista, 7);

Ahora mi_lista estaría actualizada con [5 , 7] pero no habría posibilidad de darle a otra lista la posibilidad de acceder a los datos de ésta con lo que se previenen errores a la hora de escribir el programa.

Por otra parte esconder un puntero dentro de un typedef no es muy buena práctica, pero cada uno hace lo que quiere.

Por otra parte, sobre la primera pregunta: tal vez un array de punteros. Los elementos apuntados no se mueven de su sitio, lo que cambias son los punteros del array y tienes un array para acceder a ellos.

[GGZ]

Esta es la implementación ahora te leo MAFUS xD

Código (c) [Seleccionar] Expandir

typedef struct _SNode {
       int    data;
       struct _SNode *next;
} SNode;

typedef SNode *SList;

#define slist_data(l)       (l)->data
#define slist_next(l)       (l)->next
#define slist_nil()         NULL


Código (c) [Seleccionar] Expandir

#include <stdlib.h>
#include "SList.h"

SList slist_append(SList list, int data)
{
     SList newNode = malloc(sizeof(SNode));
     SList node;
     slist_data(newNode) = data;
     slist_next(newNode) = NULL;
     if (list == slist_nil()) {
        return newNode;
     }
     node = list;
     while (slist_next(node) != slist_nil()) {
           node = slist_next(node);
     }
     /* ahora 'node' apunta al ultimo nodo en la lista */
     slist_next(node) = newNode;
     return list;
}

SList slist_prepend(SList list, int data)
{
     SList newNode = malloc(sizeof(SNode));
     slist_next(newNode) = list;
     slist_data(newNode) = data;
     return newNode;
}

void  slist_destroy(SList list)
{
     SList nodeToDelete;

     while (list != slist_nil()) {
           nodeToDelete = list;
           list = slist_next(list);
           free(nodeToDelete);
     }
}

void  slist_foreach(SList list, VisitorFuncInt visit, void *extra_data)
{
     SList node = list;

     while (node != slist_nil()) {
           visit(slist_data(node), extra_data);
           node = slist_next(node);
     }
}


Tengo un lío de tipos en la cabeza. ¿Por qué regresa un puntero si los dos están declarados de la misma forma AAAHHHH WTFF !! ?

¿Era esto lo que esperaba el autor que se hiciera?

No te entiendo bien, pero no creo ¿por qué así?
Yo sólo pregunté por qué retorna node jaja tengo más confusión ahora.

[AlbertoBSD]

Por otra parte, sobre la primera pregunta: tal vez un array de punteros. Los elementos apuntados no se mueven de su sitio, lo que cambias son los punteros del array y tienes un array para acceder a ellos.

La solucion de MAFUS es totalmente valida.

Proponga una implementación de similar a listas enlazadas, pero de longitud fija, utilizando arreglos, y que provea esta flexibilidad.

Aun así si lo que quieren es no usar apuntadores, el campo next podría ser una variable entera que sea el index relativo al elemento de la tabla por ejemplo si next  es 4 y quien inserta ahi un nuevo nodo, el nodo se escribe al final de la tabla y entonce el nodo que tenia next = 4 se cambia por final y ahora el nodo final es su valor next tendría 4.

Es casi lo mismo pero es otra solución, aun así utilizando arreglos lo veo poco practico por que no sabes cuantos nodos serán insertados

[GGZ]

AlbertoBSD, puedes escribir un troso de código o algún ejemplo así me queda un poco más claro para guiarme no digo que lo hagas es que estoy medio perdido.
Encima el Viernes de la semana que viene rindo, pero llego bien si entiendo esto.

[AlbertoBSD]

Código (c) [Seleccionar] Expandir



typedef struct {
int anterior;
int valor;
int siguiente;
}Nodo;

int main() {
Nodo lista[100];
}


Los nodos podrían insertarse en el primer hueco disponible dentro del arreglo, las variables anterior y siguiente podrian apuntar a la posicion relativa dentro del la lista.

[GGZ]

Está pensado para modificar la misma lista que se le pasa, pero en vez de modificar directamente el parámetro list lo que hace es modificarlo y regresar un puntero con el dato modificado. Seguramente el autor pensó en esa solución para dar un valor en caso de que list fuera NULL. Pero hubiera hecho lo mismo con un puntero a puntero y el resultado habría sido más natural.

¿Cómo que un puntero al dato modificado si los dos tienen el mismo tipo!?

Último ejercicio que me queda sigo intentando pero pregunto por si las dudas después me quedo trabado

Suponga que está implementando una lista doblemente enlazada. Si en lugar de guardar punteros a los nodos previo y siguiente, guarda un xor de ambos punteros: ¿puede recorrer la lista en ambas direcciones ¿Cómo? Defina en C la estructura correspondiente, ¿qué problemas puede encontrar?

Es lo último, denme una mano en esta.

Saludos!

[MAFUS]

La funciones lo que hacen es devolver el inicio de la lista modificada.
Le entregas la lista y la modificación y la función te la devuelve modificada.

Si quieres que sea más específico deberás decirme exactamente que es que no entiendes.

[GGZ]

Código (c) [Seleccionar] Expandir


SList slist_append(SList list, int data)
{
     SList newNode = malloc(sizeof(SNode));
     SList node;
     slist_data(newNode) = data;
     slist_next(newNode) = NULL;
     if (list == slist_nil()) {
        return newNode;
     }
     node = list;
     while (slist_next(node) != slist_nil()) {
           node = slist_next(node);
     }
     /* ahora 'node' apunta al ultimo nodo en la lista */
     slist_next(node) = newNode;
     return list;
}


Ya sé que el objetivo de la funcón es que devuelva la lista modificada pero no entiendo adónde la modifica, si no toca a list.
A la lista original (list) nunca lo toca, lo único que hace es decir que node = list y de ahí trabaja con node, pisa todos los datos que hay en node (por el node = slist_next(node)), por eso para mí falta algo como slist_next(list)=node;

No logro entender la lógica del código, no sé donde la modifica a lista, para mi esta devolviendo la misma lista que se le pasó sin modificación alguna.