0

我目前正在学习 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")，但是如果我删除这个测试，那么我会在下一个得到信号。

我知道这些信号通常来自访问您不应该访问的内存，但是我不确定这可能发生在哪里。

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

任何帮助将不胜感激！

4

1 回答 1

1

你的append功能坏了。实际上只是第一个 if 条件被打破。m_size如果附加到空列表，则需要递增并返回。

这是一个不会崩溃的代码（至少在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。

于 2020-04-06T21:17:04.687 回答