插入()中的分割故障，C 上的双重链接列表

Question

我正在尝试在C 中实现双重链接列表，但是当我尝试实现insert()函数时，我会遇到错误。这是节点的结构：

struct NodoLDL
{
   T dato;
   NodoLDL *anterior;
   NodoLDL *siguiente;
   NodoLDL(const T &elem, NodoLDL *ant = nullptr, NodoLDL *sig = nullptr):
      dato(elem),
      anterior(ant),
      siguiente(sig)
   {}
};

这是列表类：

 template <typename T>
class LDL
{
private:
   #include "nodoldl.h"
   size_t listSize;
   NodoLDL *listFront; //head
   NodoLDL *listBack; //tail
public:
   LDL() : listSize(0), listFront(nullptr), listBack(nullptr)
   {}
   void insert(size_t position, const T &elem);
(. . .)
}

这是我正在使用的insert()函数，但是我在" temp2->anterior = temp3"上获得了分割故障

template<typename T>
void LDL<T>::insert(size_t position, const T &elem)
{    
    if(empty()){
        listFront = new NodoLDL(elem); 
        listBack = listFront;
        listSize+=1;
    }else if(listSize>0 && position==0){ //push_front()
        //The implementation for push_front() works fine.
    }else if(position==listSize){ //push_back()
        //The implementation for push_back() also works fine.           
    }else if(position > 0 && position<listSize){
        NodoLDL *temp1, *temp2, *temp3;
        temp1 = listFront;
        for(size_t i=0; i<position; i++){
            temp1 = temp1->siguiente;
        }
        temp2 = temp1->siguiente;
        temp3 = new NodoLDL (elem);
        temp1 -> siguiente = temp3;
        temp3 -> anterior = temp1;
        temp3 -> siguiente = temp2;
        temp2 -> anterior = temp3;
        listSize+=1;
    }else if(position > listSize){
        throw invalid_argument("insert() on invalid position");
    }
}

在开始和最后插入，但是如果我在列表的中间插入，我该如何修复它？为什么那个逻辑错误？我不确定else if(position>0 && position<listSize)中的一行还是所有逻辑是不正确的。

Answer 1

好吧，首先，首先必须检查列表中是否只有一个元素。在这种情况下，您不能这样做：

    temp2 = temp1->siguiente;
    temp3 = new NodoLDL (elem);
    temp1 -> siguiente = temp3;
    temp3 -> anterior = temp1;
    temp3 -> siguiente = temp2;
    temp2 -> anterior = temp3;

如果您做这样的事情，则temp1->siguiente将是一个无效的指针，因此，temp2也将是无效的指针。调用temp2->anterior时，将发生分割故障。由于您将要加入一无所有的领域。

我将鼓励您尝试在不同功能中始终将这种过程分开。一个用于推回去，另一个用于在第一个if。

中打电话。

template<typename T>
void LDL<T>::insert(size_t position, const T &elem) {   
    if (position > listSize) { //I tend to always check this things first
        throw invalid_argument("insert() on invalid position");
    }
    if (empty() || position == 0) {
        push_front(elem);
        return;
    }
    if (position == listSize){ //push_back()           
        push_back(elem)
        return;
    }
    NodoLDL *temp1, *temp2, *temp3;
    temp1 = listFront;
    for(size_t i=0; i<position; i++){
        temp1 = temp1->siguiente;
    }
    temp2 = temp1->siguiente;
    temp3 = new NodoLDL (elem);
    temp1 -> siguiente = temp3;
    temp3 -> anterior = temp1;
    temp3 -> siguiente = temp2;
    temp2 -> anterior = temp3;
    listSize++;
}

从理论上讲，您的插入物在任何情况下都应该有效，但是我知道您是否刚开始学习并以这种方式更好地看到解决方案。Linus Torvalds有一个不错的Tedtalk，他谈论写漂亮的代码，我认为他为该班选择的示例是列表插入。