C++实现UnionFind时动态链表数组出现Segmentation Fault问题

核心BUG点 #

• LinkedList::clear() 非法内存访问（段错误核心诱因）
  函数中执行delete pom释放节点内存后，仍执行pom->next = nullptr访问已释放的野指针，直接触发未定义行为；且空链表调用clear返回EXIT_FAILURE属于逻辑错误，空链表清空空为合法操作，无需返回失败。
• LinkedList::push_back() 实现逻辑错误
  命名为尾部追加，但实际实现为头部插入，且tail指针仅在链表长度为2时赋值，后续插入元素永远不会更新tail，后续访问tail会得到无效值。
• LinkedList::operator[] 无边界检查
  传入索引大于等于链表长度时，会遍历到nullptr后直接解引用触发段错误：你调试代码中out[0]为空链表时，调用<<运算符会执行operator[0]，直接解引用空指针，就是第34行代码触发段错误的直接原因。
• LinkedList::operator<< 效率低下且不安全
  用索引遍历链表的时间复杂度为O(n²)，且会触发无边界检查的operator[]，风险极高。

修复代码示例 #

修复clear函数 #

template <class T>
bool LinkedList<T>::clear()
{
    node<T> *pom1;
    for (node<T> *pom = this->head; pom != nullptr; pom = pom1)
    {
        pom1 = pom->next;
        delete pom;
    }
    this->head = nullptr;
    this->tail = nullptr;
    this->list_size = 0;
    return EXIT_SUCCESS;
}

修复push_back实现真正的尾部追加 #

template <class T>
void LinkedList<T>::push_back(T obj)
{
    node<T> *pom = new node<T>;
    pom->value = obj;
    pom->next = nullptr;
    if (this->list_size == 0)
    {
        this->head = pom;
        this->tail = pom;
    }
    else
    {
        this->tail->next = pom;
        this->tail = pom;
    }
    this->list_size++;
}

给operator[]增加边界检查 #

template <class T>
T &LinkedList<T>::operator[](int index)
{
    if (index < 0 || (unsigned int)index >= this->list_size)
    {
        throw std::out_of_range("LinkedList index out of range");
    }
    node<T> *pom = this->head;
    for (int x = 0; x < index; x++)
        pom = pom->next;
    return pom->value;
}

优化<<运算符实现 #

template <class U>
std::ostream &operator<<(std::ostream &os, LinkedList<U> &obj)
{
    auto cur = obj.head;
    while (cur != nullptr)
    {
        os << cur->value << " ";
        cur = cur->next;
    }
    return os;
}

内容的提问来源于stack exchange，提问作者Plebania