0

tengo una tarea de estructura de datos, donde debo de poner para cada nodo un siguiente, un anterior y un dato de tipo string.

struct node {
    string data;
    struct node* prev;
    struct node* next;
};

donde para cada nuevo nodo uso un constructor, que por alguna razon si le asigno a newnode->data = data, el programa truena y no corre.

struct node* makeNode()
{
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->prev = newnode;
    newnode->next = newnode;
    return newnode;
}

Imprimo para tener una idea cada nodo con su respectiva informacion.

void Print(struct node* head)
{
    cout << "node->prev: " << head->prev << endl;
    cout << "node->data: " << head->data << endl;
    cout << "node->next: " << head->next << endl;
    cout << endl;
}

El problema es que tengo que hacer una lista doblemente ligada circular, que no tengo problema al crearla de la siguiente manera:

#include <iostream>
#include <stdlib.h>

using namespace std;
int main()
{
    struct node* head = makeNode();
    head->data = "Juan";

    struct node* newnode = makeNode();
    newnode->data = "Carlos";

    struct node* temp = head->next;
    newnode->next = temp;
    newnode->prev = head;
    head->next = newnode;
    newnode->prev = head->next;

    Print(head);
    Print(newnode);

    return 0;
}

Ejemplo:

node->prev: 0x6000009782a0
node->data: Juan
node->next: 0x6000009782d0

node->prev: 0x6000009782d0
node->data: Carlos
node->next: 0x6000009782a0

donde se cumple que el siguiente de el ultimo nodo es la direccion de el anterior del primer nodo.

pero al momento de ponerlo en una funcion, todo truena como siempre en los metodos no soy tan habilidoso.

struct node* addEnd(struct node* head, string data)
{
    struct node* newnode = makeNode();
    if(head == NULL)
    {
        head = newnode;
        return newnode;
    }
    else
    {
        struct node* temp = head->next;
        newnode->next = temp;
        newnode->prev = head;
        head->next = newnode;
        newnode->prev = head->next;
        return head;
    }
}

algun alma bendita que me pueda ayudar porfavor :( llevo como dos semanas intentado que funcione, pero lo maximo que he logrado es sin usar funciones.

tambien intente lo siguiente en el metodo de addEnd():

temp = head;
while(temp->next !=head)
{
temp = temp->next;
}

2 respuestas 2

0

El problema se encuentra, como es de esperar, en la función addEnd

struct node* addEnd(struct node* head, string data)
{
    struct node* newnode = makeNode();
    if(head == NULL)
    {
        head = newnode; // <<< AQUI
        return newnode;
    }
    else
    {
        struct node* temp = head->next;
        newnode->next = temp;
        newnode->prev = head;
        head->next = newnode;
        newnode->prev = head->next;
        return head;
    }
}

Tu intención en la línea marcada es modificar el puntero head ... pero en lo que no has caido es que ese cambio es local a la función. Se ve más facil si dejamos de usar punteros:

void func(int val)
{
    val = 123;
}

int main()
{
    int x = 1;
    func(x);
    std::cout << x;
}

¿Qué imprime el programa? Así de un primer vistazo podría parecer que imprime 123, ya que es el valor que establece func. Sin embargo, val es una copia de x, luego los cambios que se hagan en val no afectarán de ninguna forma a x.

Puesto en una sola función, la situación sería equivalente a la siguiente:

int main()
{
    int x = 1;
    int val = x;
    val = 123;
    std::cout << x;
}

Con los punteros simples pasa lo mismo. La particularidad de los punteros es que almacenan direcciones de memoria. Que dos punteros apunten a la misma región de memoria les permitirá hacer cambios en la misma región de memoria, por lo que los cambios que un puntero haga podrán ser visibles desde el otro.

Peeero si cogemos uno de los dos punteros y hacemos que apunte a otra dirección de memoria diferente, el segundo puntero no va a sufrir cambio alguno. Esto es justamente lo que te está pasando.

Una solución rápida sería usar punteros dobles (o referencia a puntero):

struct node* addEnd(struct node** head, string data)
{
    struct node* newnode = makeNode();
    if(*head == NULL)
    {
        *head = newnode;
        return newnode;
    }
    else
    {
        struct node* temp = *head->next;
        newnode->next = temp;
        newnode->prev = *head;
        head->next = newnode;
        newnode->prev = *head->next; // Aqui hay otro error
        return *head;
    }
}

Sin embargo, esta solución no sería la deseable en C++.

A la hora de diseñar un programa todo el código tiene que trabajar en armonía para que el comportamiento sea el esperado. Si mezclas responsabilidades entonces el código será más propenso a errores y más complicado de probar.

En tu caso, pretendes manejar una lista doblemente enlazada. Una lista doblemente enlazada debería comprender, al menos, dos entidades diferentes: La lista en si misma y los nodos de la lista:

struct Node
{
    string data;
    Node* prev = nullptr;
    Node* next = nullptr;

    Node(std::string const& value)
        : data(value)
    { }
};

class List
{
public:

private:
    Node * head = nullptr;
};

La idea es que la clase List contenga todas las funciones que vayan a ser necesarias para manipular la lista. Esto te permite aislarte de los problemas propios de la gestión de la lista una vez hayas programado esos métodos:

  • A la hora de manipular la lista, evita la proliferación de diferentes soluciones casi casi idénticas, pero distintas al fin y al cabo
  • Reutilizarás código, aprovechando algoritmos que has ido perfeccionando a base de ejecutar diferentes pruebas
  • Reduces el acoplamiento del código
  • otras ventajas ...

Con este nuevo diseño, la función add ahora podría quedar de la siguiente forma:

class List
{
public:
    void AddEnd(std::string const& value);
private:
    Node * head = nullptr;
};

void List::AddEnd(std::string const& value)
{
    Node* newNode = new Node(value);

    if (nullptr == head)
    {
        head = newNode;
        head->prev = newNode;
        head->next = newNode;
    }
    else
    {
        Node * prev = head->prev;

        // Actualizamos el penultimo nodo
        prev->next = newNode;

        // Actualizamos el nodo actual
        newNode->prev = prev;
        newNode->next = head;

        // Actualizamos head
        head->prev = newNode;
    }
}

head ya no es un parámetro de la función luego los cambios que hagas sobre dicho puntero serán persistentes. Por otro lado evitas que alguien pueda acceder al puntero head libremente, lo que evita que se puedan realizar usos incorrectos en cualquier parte del código

0

Constructores

donde para cada nuevo nodo uso un constructor

Esto:

struct node* makeNode()
{
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->prev = newnode;
    newnode->next = newnode;
    return newnode;
}

No es un constructor. Un constructor es:

El constructor es una función miembro especial, no estática, de una clase que se usa para inicializar objetos de su tipo de clase.
Referencia.

Nótese la parte importante:

que se usa para inicializar objetos de su tipo de clase

El constructor se encarga de la inicialización.

Si tomamos tu función, primero asignas la memoria, y luego la usas sin inicializar. Ya que utilizas memoria sin inicializar, tu programa cae en comportamiento indefinido. Esto significa que tu programa puede:

  • Funcionar
  • Funcionar a veces si y otras no
  • Funcionar en algunos lados y en otros no
  • Ser cerrado por tu sistema operativo
  • O peor, hacerte esto.

Cuando caes en comportamiento indefinido, todo vale, todo puede pasar, ya que:

el programa compilado no está obligado a hacer nada significativo.
Referencia

Y porque no corre?

Técnicamente al caer en comportamiento tu programa no sirve, no se necesita ningún otro diagnostico. Pero en este caso hay un motivo claro por el que:

si le asigno a newnode->data = data, el programa truena y no corre.

data es un std::string. Esta clase, de forma sobre simplificada, se ve algo asi:

class string {
    char *data;
    size_t size;
}

Ya que no inicializas la memoria, data tendrá un valor indefinido (como si fuera al azar). Si algo podemos asegurar, es que es prácticamente imposible que data contenga una dirección de memoria valida.

Cuando llamas al operador de asignacion, el string va a asignar memoria para guardar la data del string que le das, y luego va a limpiar la memoria en la que esta guardando la data que tiene ahora (Si la data que tiene ahora no es un nullptr). Como data tiene un valor "al azar", le vas a pedir al sistema operativo que despeje memoria en una dirección donde tu no eres dueño de ella. En este punto lo mas probable es que tu sistema operativo decida terminar tu programa.

Test en godbolt. Puedes ver las quejas del address sanitizer, y como cometes una violación de segmento.

Posibles soluciones

Deja de escribir "estilo C"

Esta seria la solución optima. Si estas usando C++, escribe C++. Mejor si escribes C++ Moderno. Pero mencionas que es tarea, así que supongo que no es una opción de la noche a la mañana presentar tus trabajos con un estilo de código completamente diferente al que te están enseñando.

Inicializa newnode

En C++ tenemos el placement new, que sirve para inicializar una dirección de memoria. La función makeNode quedaría algo como:

struct node* makeNode()
{
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    new (newnode) struct node;
    newnode->prev = newnode;
    newnode->next = newnode;
    // ... Algo con `data` ...
    return newnode;
}

Nótese que en la función que se encargue que limpiar los nodos tendrás que llamar al destructor de node.

    nodo_a_limpiar->~node();
    free(nodo_a_limpiar);

Inicializa newnode V2.0

Como comento correctamente @Mateo, porque no usar las herramientas que te da C++ desde un principio. Usar simplemente new va a asignar la memoria, y la va a inicializar.

struct node* makeNode()
{
    struct node* newnode = new struct node;
    newnode->prev = newnode;
    newnode->next = newnode;
    // ... Algo con `data` ...
    return newnode;
}

Nótese que en la función que se encargue que limpiar los nodos tendrás que llamar delete en lugar de free:

    delete nodo_a_limpiar;

Usa un estándar de C++ mas moderno.

Resulta que el problema con el que te topas es relativamente común en programas que están destinados a compilarse tanto en C como en C++. Usualmente estos funcionan, ya que escriben puramente C de una forma en la que es compatible con los compiladores de C++. El tuyo da problema porque incluyes un std::string, que ya explicamos como pudo haber causado el problema.

Pero, a pesar de que usualmente funcionen, seguían cayendo en comportamiento indefinido según el estándar de C++, hasta que llego C++20.

Para C++20 se aprobó la propuesta P0593R6. Que entre otras cosas, busca solucionar este problema (El ejemplo en 2.1 se te hará familiar). Si usas GCC 11, Clang 11, o MSVC, deberías poder simplemente indicar que quieres compilar para C++20, y tengo entendido que tu código debería funcionar (Aunque puede que no, ya que estas haciendo un tejemaneje entre C y C++).

7
  • ¿Por qué no usar directamente new? Me refiero a algo como: int* = new int;. Después de todo sino estuviera usando C++, tampoco podría usar iostream.
    – Mateo
    el 25 mar. 2022 a las 4:08
  • No hay comportamiento indefinido en este programa
    – eferion
    el 25 mar. 2022 a las 7:34
  • @eferion Pudiste a ver la propuesta? El ejemplo en 2.1 es prácticamente calcado a lo que tenemos aquí. Como comento, usualmente funciona, pero sigue siendo comportamiento indefinido ya que nunca se construyen los objetos. En este caso seria peor porque usa un std::string, del que no conocemos su estado inicial. Aquí un ejemplo que incluye el Address sanitizer replicando el comportamiento. el 25 mar. 2022 a las 13:03
  • @eferion Si te fijas, removiendo el address sanitizer el programa corre "perfectamente", porque es comportamiento indefinido. Viendo tu respuesta, parece que había mas de un problema con el código que publico el OP. Error mío por no fijarme en eso, vi UB y mi cerebro entro en modo "no se requiere ningún otro diagnostico, ese es el problema". Bueno, ahora el OP tiene una respuesta por problema. el 25 mar. 2022 a las 13:10
  • @Mateo, buen punto. No se como pensé en en el placement new, y no en usar new directamente. En mi defensa, ya eran las 9 y me iba a ir a dormir XD. Ahora lo añado a la respuesta el 25 mar. 2022 a las 13:12

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.