Почему я получаю этот сигнал SIGSEGV в моем тесте catch2? - PullRequest
Новая
       38

Почему я получаю этот сигнал SIGSEGV в моем тесте catch2?

0 голосов
/ 06 апреля 2020

В настоящее время я изучаю 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"), но если я удалю этот тест затем я получаю сигнал на следующем.

Я знаю, что эти сигналы обычно приходят из доступа к памяти, которую вы не должны, однако я не уверен, где именно это может происходить.

(Обратите внимание, что перегрузка конструктора копирования и оператора присваивания еще не реализована. Я не думаю, что это может вызвать это, но, пожалуйста, исправьте меня, если я ошибаюсь)

Любая помощь будет принята с благодарностью!

1 Ответ

1 голос
/ 07 апреля 2020

Ваша append функция нарушена. На самом деле только первый, если условие нарушено. Вам нужно увеличить m_size и вернуться, если вы добавляете пустой список.

Вот код, который не обрабатывает sh (по крайней мере при append вызовах). 

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

Если вы не выполняете возврат, вы в конечном итоге выделяете дополнительные узлы и неправильно связываете вещи.

В примечании, этот фрагмент кода странный 

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

Вы пишете класс связанного списка, который выделяет памяти, но удаление памяти слишком сложно?

Кроме того, не используйте NULL, используйте nullptr.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...