7

Estoy haciendo unas pruebas con listas simplemente enlazadas y me falla al insertar datos, he probado esto:

struct nodo
{
    int dato;
    nodo *siguiente;
};

typedef nodo * lista;

void insertar(lista l, int dato)
{
    nodo *n = new nodo;
    n->siguiente = NULL;
    n->dato = dato;
    l->siguiente = n;
}

int main()
{
    lista mi_lista;
    insertar(mi_lista, 42);
    std::cout << mi_lista->dato;
    return 0;
}

Esperaba que el programa mostrase 42, pero en lugar de eso muestra:

Segmentation fault

¿Cómo se hace para insertar datos en listas simplemente enlazadas?

1
  • +1. Su pregunta-respuesta cae como maná del cielo para mí. Justo voy a estudiar estos temas y ya tengo un enlace de referencia. Si pudiera le daría más upvotes.
    – Xam
    Commented el 1 jun. 2018 a las 2:04

2 respuestas 2

11

1. Los nodos no son listas.

He visto en StackOverflow en Español varias veces esta confusión, y me resulta muy curioso que tantos usuarios cometan ese error.

Tienes una estructura de datos llamada nodo que almacena un puntero al siguiente elemento y un dato, lo primero que haces con ella es declarar un alias diciendo que un puntero a nodo es una lista. Y eso es tan erróneo como decir que un escalón es una escalera, sinceramente ¿Te parecen lo mismo?:



Organizar las estructuras de datos de esta manera y poner nombres que no las describen adecuadamente es confuso y propenso a errores como has podido ver.

2. El alias oculta el tipo subyacente.

Normalmente cuando en C++ definimos una variable de tipo puntero, le añadimos el asterisco:

tipo_de_datos *puntero;
//            ~ <--- ¡Esto es un puntero!

Pero podemos ocultar el puntero en un alias:

typedef tipo_de_datos * otro_tipo;
otro_tipo dato;
//        ~~~~ <--- Aunque sea puntero, ¡no lo sabemos de un vistazo!

Debido a este uso del alias, no es evidente que lista sea un puntero y acabas declarado un puntero que no apunta a nada:

int main()
{
    lista mi_lista; // 'lista' es un puntero (nodo *) ¡aunque no lo parezca!
    insertar(mi_lista, 42);
    std::cout << mi_lista->dato;
    return 0;
}

En la llamada a insertar se usa el puntero (con el operador flecha ->) y como no apunta a nada obtienes el error de fallo en la memoria (Segmentation fault):

void insertar(lista l, int dato)
{
    nodo *n = new nodo;
    n->siguiente = NULL;
    n->dato = dato;
    l->siguiente = &n; // l es un puntero, pero no apunta a nada ¡Segmentation fault!
}

Propuesta.

Empecemos por resolver el primer punto: las listas y los nodos son cosas diferentes, así que crearemos un objeto lista:

struct lista
{
    void insertar(int dato);
private:
    struct nodo
    {
        int dato = 0;
        nodo *siguiente = nullptr;
    };

    nodo *inicio = nullptr;
    nodo *fin = inicio;
};

Si te fijas, el nodo es ahora un sub-objeto de lista que está en la zona privada de dicho objeto, de esta manera seguimos los principios de encapsulamiento. También hemos añadido inicializadores a todos los miembros para que tengan información controlada en el momento de crearse; por último, el usar dos punteros (uno para el inicio de la lista y otro para el final) nos ayuda a ahorrar trabajo a la hora de insertar datos.

La implementación corregida de insertar quedaría así:

void lista::insertar(int dato)
{
    if (fin)
    {
        fin->siguiente = new nodo{dato};
        fin = fin->siguiente;
    }
    else
    {
        inicio = fin = new nodo{dato};
    }
}
2

Con ánimo de complementar la contestación anterior, quería comentarte varios asuntos. En primer lugar, que estás creando una lista al estilo C desde C++. Por ejemplo, usas typedef. En C++ el compilador ya considera la struct como un tipo nuevo de datos. Es posible crear codigo C y compilarlo con un compilador de C++. Este último está más fuertemente tipado y te puede mostrar avisos y errores que un compilador de C se va a tragar y luego puede funcionar mal el programa. Además, dicen en Thinking C++ que si compila en C++ en C tiene todas las de funcionar. Siguiendo con el código, creo que lo que tratas de hacer es lo siguiente:

#include <stdlib.h>
#include <stdio.h>

struct Nodo {
  int dato;
  struct Nodo *siguiente;
};

typedef struct Nodo* Lista;

Lista lista_vacia(void) {
  return NULL;
}

Lista insertar (Lista lista, int dato) {
  struct Nodo *nuevo, *aux;

  nuevo=malloc(sizeof (struct Nodo));

  nuevo->dato=dato;
  nuevo->siguiente=NULL;

  if ( lista == NULL )
     lista=nuevo;
  else {
    for ( aux=lista; aux->siguiente != NULL; aux=aux->siguiente );

    aux->siguiente=nuevo;
  }
  return lista;  
}

int main (void) {
  Lista mi_lista;

  mi_lista=lista_vacia();

  mi_lista=insertar(mi_lista,10);

  printf("Valor: %d ", mi_lista->dato);

  return 0;
}

Además, tu código tiene un problema y es que cuando sale de la función insertar, n se destruye, sale de su ámbito pues sólo existe en la pila de la función insertar,por eso el Segmentation fault. Al desaparecer ¿adonde apunta l->siguiente?. No pierdas tampoco de vista la apreciación de Paula_plus_plus: confundes la escalera y el escalón. Desde el punto de vista del código en C++ hay varias formas de abordar el problema. Tú pareces decidirte porque la propia clase que define los objetos contenidos en la lista sea nodo, algo como lo siguiente: a) Integración en la propia clase de dominio b) uso de Herencia c) Contenedor de elementos de tipo nulo Si bien, las listas están implementadas en la STL como plantillas para poder ser usadas como datos genéricos. Te pondré código base de la primera opción que es la que parece has elegido y, de la plantilla en STL

class Lista {
   public:
      // Funcionalidad
      Lista* getSiguiente ();
      void eliminar ();
      void insertar (Lista *pNuevo);
   private:
      // Puntero
      Lista *_pSiguiente;
      int dato;
};

Con plantillas sería así:

template<class T>
class NodoLista {
  public:
    NodoLista (T datos);
    T & getDatos ();
    NodoLista * siguiente ();
  private:
    T _datos;
};
template<class T>
class Lista {
  public:
    NodoLista<T> getCabeza ();
    void insertarFinal (T datos);
    // Resto funcionalidad...
 private:
   NodoLista<T> *_cabeza;
};

Este último es el modelo que veo más razonable, una clase lista (objeto) que contiene los nodos. Los nodos son otro objeto. En los nodos guardo los datos y las operaciones correspondientes a ellos. Como la lista contiene un puntero a nodos, podre recorrerlos, insertar, eliminar y, mirar lo que contienen.

Espero haber sido de ayuda.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

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