为什么我在 catch2 测试中收到这个 SIGSEGV 信号?

Why am I getting this SIGSEGV signal in my catch2 test?

我目前正在学习 C++,作为练习,我一直在尝试实现链表数据结构。我正在 Catch2 中为它编写测试,但我一直收到 SIGSEGV 信号,但我不明白为什么。

这是我的链表头文件:

#pragma once

namespace datastructures{
  template <typename T>
  class LinkedList{
    private:
      class Node
      {
        private:
          T m_data;
          Node *m_next;
        public:
          Node(T data);

          ~Node();

          Node* get_next();

          void set_next(T data);

          void set_next(Node* next);

          T get_data();

          void set_data(T data);
      };

      Node *m_head;
      int m_size;

    public:

      /**
       * @brief Construct a new Linked List object
       * 
       */
      LinkedList();

      LinkedList(const LinkedList &other);

      LinkedList & operator=(const LinkedList &other);

      /**
       * @brief Destroy the Linked List object
       * 
       */
      ~LinkedList();

      /**
       * @brief get the size of the list
       * 
       * @return int 
       */
      int size();

      /**
       * @brief Returns true if the list is empty
       * 
       * @return true 
       * @return false 
       */
      bool is_empty();

      /**
       * @brief Get the first value in the list
       * 
       * @return T 
       */
      T first();

      /**
       * @brief get the value from the given index in the list
       * 
       * @param index 
       * @return T 
       */
      T get(int index);

      /**
       * @brief remove the value from the given index from the list
       * 
       * @param index 
       * @return T the removed value
       */
      T remove(int index);

      /**
       * @brief Sets the value at the given index to the given value
       * 
       * @param index 
       * @param val
       */
      void set(int index, T val);

      /**
       * @brief Inserts the given value at the given index in the list
       * 
       * @param index 
       * @param val 
       */
      void insert(int index, T val);

      /**
       * @brief Appends the given value to the end of the list
       * 
       * @param val 
       */
      void append(T val);
  };
}

#include "templates/linked_list.tcc"

这是我的链表实现文件:

#include <datastructures/linked_list.hpp>

using namespace datastructures;

#pragma region Node Implementation

template <typename T>
LinkedList<T>::Node::Node(T data){
  m_data = data;
  m_next = NULL;
}

template <typename T>
LinkedList<T>::Node::~Node(){
  //Do nothing. Deletion of member m_next is out of this classes scope.
}

template <typename T>
typename LinkedList<T>::Node* LinkedList<T>::Node::get_next(){
  return m_next;
}

template <typename T>
void LinkedList<T>::Node::set_next(T data){
  LinkedList<T>::Node* tmp = new LinkedList<T>::Node(data);

  //Don't delete previous next object. That is handled by the linked list class

  m_next = tmp;
}

template <typename T>
void LinkedList<T>::Node::set_next(LinkedList<T>::Node* next){

  //Don't delete previous next object. That is handled by the linked list class

  m_next = next;
}

template <typename T>
T LinkedList<T>::Node::get_data(){
  return m_data;
}

template <typename T>
void LinkedList<T>::Node::set_data(T data){
  m_data = data;
}

#pragma endregion

#pragma region Linked List Implementation

template <typename T>
LinkedList<T>::LinkedList(){
  m_size = 0;
  m_head = NULL;
}

template <typename T>
LinkedList<T>::~LinkedList(){
  typename LinkedList<T>::Node* currentNode = m_head;

  while (currentNode != NULL)
  {
    typename LinkedList<T>::Node* tmp = currentNode->get_next();

    delete currentNode;

    currentNode = tmp;
  }

}

template <typename T>
int LinkedList<T>::size(){
  return m_size;
}

template <typename T>
bool LinkedList<T>::is_empty(){
  return m_size == 0;
}

template <typename T>
T LinkedList<T>::first(){
  if (m_head == NULL)
  {
    throw "List is empty";
  }

  return m_head->get_data();

}

template <typename T>
T LinkedList<T>::get(int index){
  if (index >= m_size || index < 0)
  {
      throw "Index out of bounds";
  }

  typename LinkedList<T>::Node* currentNode = m_head;
  int currentIndex = 0;

  while (currentIndex < index)
  {
    currentNode = currentNode->get_next();
    currentIndex++;
  }

  return currentNode->get_data();
}


template <typename T>
T LinkedList<T>::remove(int index){
  if (index >= m_size || index < 0)
  {
      throw "Index out of bounds";
  }


  typename LinkedList<T>::Node *prevNode = NULL;
  typename LinkedList<T>::Node *currentNode = m_head;
  int currentIndex = 0;

  while (currentIndex < index)
  {

    prevNode = currentNode;
    currentNode = currentNode->get_next();
    currentIndex++;
  }

  T removed_val;

  // Special case if deleting the first element
  if (prevNode == NULL){
    m_head = currentNode->get_next();
    removed_val = currentNode->get_data();
    delete currentNode;
  }
  else{
    prevNode->set_next(currentNode->get_next());
    removed_val = currentNode->get_data();
    delete currentNode;
  }

  m_size--;

  return removed_val;
}


template <typename T>
void LinkedList<T>::set(int index, T val){
  if (index >= m_size || index < 0)
  {
      throw "Index out of bounds";
  }

  typename LinkedList<T>::Node* currentNode = m_head;
  int currentIndex = 0;

  while (currentIndex < index)
  {
    currentNode = currentNode->get_next();
    currentIndex++;
  }

  currentNode->set_data(val);
}


template <typename T>
void LinkedList<T>::insert(int index, T val){

  if (index >= m_size || index < 0)
  {
      throw "Index out of bounds";
  }

  typename LinkedList<T>::Node* prevNode = NULL;
  typename LinkedList<T>::Node* currentNode = m_head;
  typename LinkedList<T>::Node* newNode = new LinkedList<T>::Node(val);
  int currentIndex = 0;

  while (currentIndex < index)
  {
    prevNode = currentNode;
    currentNode = currentNode->get_next();
    currentIndex++;
  }

  // Special case if inserting the first element
  if (prevNode == NULL){
    m_head = newNode;
    newNode->set_next(currentNode);
  }
  // All other cases should be covered by this
  else{
    prevNode->set_next(newNode);
    newNode->set_next(currentNode);
  }

  m_size++;
}

template <typename T>
void LinkedList<T>::append(T val){
  if(m_size == 0 && m_head == NULL){
    m_head = new LinkedList<T>::Node(val);
  }

  typename LinkedList<T>::Node* prevNode = NULL;
  typename LinkedList<T>::Node* currentNode = m_head;
  typename LinkedList<T>::Node* newNode = new LinkedList<T>::Node(val);
  int currentIndex = 0;

  while (currentIndex < m_size)
  {
    prevNode = currentNode;
    currentNode = currentNode->get_next();
    currentIndex++;
  }

  prevNode->set_next(newNode);

  m_size++;
}

#pragma endregion

这是我的 catch2 测试:

#include <catch2/catch.hpp>
#include <datastructures/linked_list.hpp>

#include <iostream>

using namespace datastructures;

TEMPLATE_TEST_CASE("linked_list", "[linked_list][Template]", int){
  SECTION("can be constructed without issue"){
    LinkedList<int> list = LinkedList<int>();

    REQUIRE(list.size() == 0);
  }

  SECTION("Can append values"){
    LinkedList<int> list = LinkedList<int>();

    list.append(1);

    REQUIRE(list.size() == 1);
    REQUIRE(list.get(0) == 1);

    list.append(2);

    REQUIRE(list.size() == 2);
    REQUIRE(list.get(1) == 2);
  }


  SECTION("Can remove values"){
    LinkedList<int> list = LinkedList<int>();

    for (int i = 0; i < 5; i++)
    {
      list.append(i);
    }

    REQUIRE(list.size() == 5);
    REQUIRE(list.get(4) == 4);

    list.remove(4);

    REQUIRE(list.size() == 4);

    list.remove(0);

    REQUIRE(list.size() == 3);
    REQUIRE(list.get(0) == 1);

  }


  SECTION("Can set arbitrary values"){
    LinkedList<int> list = LinkedList<int>();

    for (int i = 0; i < 5; i++)
    {
      list.append(i);
    }

    REQUIRE(list.size() == 5);
    REQUIRE(list.get(4) == 4);

    list.set(0, 9);

    REQUIRE(list.size() == 5);
    REQUIRE(list.get(0) == 9);

    list.set(4, 22);

    REQUIRE(list.size() == 5);
    REQUIRE(list.get(4) == 22);
  }

  SECTION("Can get arbitrary values"){
    LinkedList<int> list = LinkedList<int>();

    for (int i = 0; i < 5; i++)
    {
      list.append(i);
    }

    REQUIRE(list.get(0) == 0);
    REQUIRE(list.get(1) == 1);
    REQUIRE(list.get(2) == 2);
    REQUIRE(list.get(3) == 3);
    REQUIRE(list.get(4) == 4);
  }

  SECTION("Can insert values at arbitrary indices"){
    LinkedList<int> list = LinkedList<int>();

    for (int i = 0; i < 5; i++)
    {
      list.append(i);
    }

    REQUIRE(list.size() == 5);
    REQUIRE(list.get(4) == 4);

    list.insert(3, 99);

    REQUIRE(list.size() == 6);
    REQUIRE(list.get(3) == 99);;
    REQUIRE(list.get(4) == 3);

  }

  SECTION("Accurately tracks the list's size"){
    LinkedList<int> list = LinkedList<int>();

    for (int i = 0; i < 5; i++)
    {
      REQUIRE(list.size() == i);
      list.append(i);
    }

  }

  SECTION("Can tell when the list is empty"){
    LinkedList<int> list = LinkedList<int>();

    REQUIRE(list.is_empty());

    list.append(0);

    REQUIRE_FALSE(list.is_empty());
  }
}

我打开 SIGSEGV 信号的测试是 SECTION("can append values"),但是如果我删除这个测试,那么我会在下一个测试上获得信号。

我知道这些信号通常来自您不应该访问的内存,但我不确定具体发生在何处。

(注意复制构造函数和赋值运算符重载尚未实现。我不认为这会导致这种情况,但如果我错了请纠正我)

如有任何帮助,我们将不胜感激!

您的 append 功能已损坏。实际上只是第一个 if 条件被打破。如果附加到空列表,则需要增加 m_size 和 return。

这是一个不会崩溃的代码(至少在 append 次调用时)。

if(m_size == 0 && m_head == NULL)
{
    m_head = new LinkedList<T>::Node(val);
    m_size++;  // increment size
    return;    // and return right away
}

如果您不执行 return,您最终会分配额外的节点,并且无法正确链接。

附带说明一下,这段代码很奇怪

template <typename T>
LinkedList<T>::Node::~Node(){
  //Do nothing. Deletion of member m_next is out of this classes scope.
}

你正在写一个链表class,分配内存,但是删除内存太复杂了?

还有,不要用NULL,请用nullptr