Home / Questions / 169453
Accepted
PaperBirdMaster
Asked: 2020-05-31 23:51:25 +0800 CST 2020-05-31 23:51:25 +0800 CST

我有一个单链表，如何向其中添加数据？

  • 772

我正在用简单的链表做一些测试，插入数据时它失败了，我试过这个：

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;
}

我希望程序显示42，但它显示：

Segmentation fault

如何将数据插入到简单链表中？

c++

2 Answers

  1. 1. 节点不是列表。

    我曾多次在西班牙语的 StackOverflow 上看到这种混乱，我对这么多用户犯这个错误感到非常好奇。

    您有一个名为的数据结构nodo，它存储指向下一个元素和一些数据的指针，您使用它做的第一件事是声明一个别名，说明指向的指针nodo是lista. 这就像说阶梯是阶梯一样是错误的，老实说，它们在您看来是否相同？：

    如您所见，以这种方式组织数据结构并给它们命名不足以描述它们是令人困惑和容易出错的。

    2.别名隐藏了底层类型。

    通常，当我们在 C++ 中定义指针类型的变量时，我们会添加星号：

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

    但是我们可以将指针隐藏在别名中：

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

    由于这种别名的使用，lista它是一个指针并不明显，并且您最终声明了一个不指向任何东西的指针：

    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;
}

    在调用insertar指针时使用（使用箭头运算符->），因为它没有指向任何东西，所以你会得到内存错误（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!
}

    提议。

    让我们从解决第一点开始：列表和节点是不同的东西，所以我们将创建一个列表对象：

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

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

    如果您注意到，nodo现在是一个子对象lista，位于所述对象的私有区域中，这样我们就遵循了封装原则。我们还为所有成员添加了初始化程序，以便他们在创建时控制信息；最后，使用两个指针（一个指向列表的开头，一个指向列表的末尾）有助于我们在插入数据时节省工作。

    的正确实现insertar如下所示：

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

    为了补充前面的答案，我想就几个问题发表评论。首先，您正在从 C++ 创建一个 C 样式的列表。例如，您使用 typedef。在 C++ 中，编译器已经将结构视为一种新的数据类型。可以创建 C 代码并使用 C++ 编译器对其进行编译。后者的类型更强，可以给你警告和错误，C 编译器会吞下这些警告和错误，然后使程序发生故障。此外，他们在 Thinking C++ 中说，如果你从 C++ 编译到 C，它就有机会工作。继续代码，我认为您正在尝试执行以下操作：

    #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;
}

    此外，您的代码有一个问题，即当它退出插入函数时， n 被销毁，它超出范围，因为它只存在于插入函数堆栈中，因此出现分段错误。当它消失时，l->next 指向哪里？不要忽视对 Paula_plus_plus 的评价：你混淆了梯子和台阶。从 C++ 代码的角度来看，有几种方法可以解决这个问题。您似乎决定定义列表中包含的对象的类是节点，类似于以下内容：a）域类本身的集成 b）继承的使用 c）空类型元素容器虽然它们是在列表中实现的将 STL 作为模板用作通用数据。我会给你第一个选项的基本代码，这是你似乎选择的那个，

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

    使用模板会是这样的：

    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;
};

    最后一个是我看到的最合理的模型，一个包含节点的列表类（对象）。节点是另一个对象。在节点中，我存储数据和与它们对应的操作。由于列表包含指向节点的指针，我将能够遍历它们、插入、删除并查看它们包含的内容。

    我希望我对您有所帮助。

    • 2