Foro de elhacker.net

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):

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!

Hay un parte del codigo que dice..

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.

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:

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:

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:

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.

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.

Esta es la implementación ahora te leo MAFUS xD

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
 

#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 !! ?



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.
 

La solucion de MAFUS es totalmente valida.


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

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.

 
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.

¿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!

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.

 
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.

La premisa para que funcione la función es que la lista siempre debe estar terminada con NULL. Si está vacía debe estar apuntando a NULL.

La función pondrá el nodo generado con el dato al final de la lista. Siguiendo la primera premisa éste último nodo debe apuntar a NULL en next.

Lo que se hace es:
Se genera un nodo a partir de la información dada por data.

Si la lista está vacía, NULL, pasará a apuntar al nodo nuevo.
Si la lista no está vacía hay que recorrerla hasta encontrar el último elemento (aquel que apunte a NULL), cambiar el valor next para que apunte al nuevo nodo generado y regresar la lista entera, eso es el primer elemento (list).

Lo que ves en

while (slist_next(node) != slist_nil()) {
    node = slist_next(node);

es precisamente ese recorrido. node apunta al principio de la lista (list) y vamos a trabajar sobre node. Mientras el elemento next de node no sea NULL, node apuntará a node->next (en el código esto está encapsulado por node = slist_next(node). Una vez llegado a éste último elemento la orden list_next(node) = newNode; coloca el nuevo nodo al final de la lista.
Como el inicio de la lista no ha sido modificado (list) y hay que regresar un puntero, precisamente al inicio de la lista, devolvemos list.

Otra versión sin estas macros es así:

SList slist_append(SList list, int data) {
    Slist node;
    SList newNode = malloc(sizeof(SNode));
 
    newNode->data = data;
    newNode->next = NULL;
 
    if(list == NULL)
        return newNode;
 
    node = list;
 
    while(node->next != NULL)
        node = node->next;
 
    node->next = newNode;
 
    return list;
}

Me explicaste todo lo que yo ya sabía, se como trabaja la función se lo que hace, pero no entiendo como la enlaza o sea como relaciona list con node, eso es lo que no entiendo.

O sea como que yo modifico node y también se modifica list si nunca lo relacioné sólo dije node = list (pero acá no estoy cambiando ningún valor de list) y nada más.


ENTIENDO TODO LO QUE HACE LA FUNCIÓN, LO QUE NO ENTIENDO ES PORQUE RETORNA LIST SI NUNCA LO TOCA SI NUNCA LO MODIFICA A LIST, NUNCA DICE "EL SIGUIENTE ELEMENTO DE LIST APUNTA AL NODE"

A ver si me se explicar ahora:
node es una variable puntero auxiliar. Su única función es, junto al while, encontrar el último nodo de la lista.
La variable list no se toca, es el inicio de la lista, lo que hay que regresar. Pero la lista sí que se ha modificado, ha crecido en un elemento.

node = list; es porqué la lista es un dato dinámico y no sabemos que extensión tiene pero sabemos que list, al menos, tiene un nodo válido y que ése es el primero; por tanto hay que empezar a buscar el último nodo de la lista por el primero y recorrerla hasta llegar al final.

A ver si me salen los dibujitos esquemáticos:

node, ya no me sirve y lo dejo tranquilo. Desaparecerá cuándo desaparezca la función ya que es una variable local.

La lista se queda ya que es algo que hay en el motón y por tanto permanente.

Debo retornar list porqué apunta a la lista modificada.

Ahora me puedes decir: pero si list tiene la misma posición de memoria al principio de la función que al final, no se ha modificado en nada el valor que guarda, no hace falta devolverla.

Y te digo: sí que hace falta porqué también sirve la función para generar la lista desde cero. Si se le pasa list=NULL a la función ocurre lo siguiente:

Ahora si no devuelvo list fuera de la función no existiría esta modificación.

Lo que yo no entiendo es este paso:


Ya sé que el next de node es el ÚLTIMO elemento ya sé eso, pero no sé como lo enlaza capaz no entendí bien la definición de las estructuras o sea yo tenía entendido que se debe poner CUAL ES EL SIGUIENTE elemento.

Es decir uno define node y busca hasta el último elemento y luego lo enlaza con newNode PERFECTO! ESO SE ENTIENDE.

La pregunta es: ¿cuando enlaza list con node? capaz hay algo de la defición que no entiendo

O sea para mi falta un list->next=node; ¿me entendés?
Así como hace node->next=newNode;

¿Por qué no hace falta enlazar de algún modo list con node? yo lo estoy pensando mal y lo sé pero es por alguna estructura o algo que no entendí

No se puede hacer list->next = node porqué node es solo un puntero y no tiene dato.
En la práctica es esto:

int* pint = malloc((sizeof(int));
int* node;
 
node = pint;
 
 

Cuándo haces node = list ya creas la relación. node es list.

AAahhh ¡Claro! que tonto, ahora si entendí
Eso era todo lo que quería que me digas no que me expliques el código entero  :xD


Muchas gracias!

Perfecto  ;-) ;-)