在此代码上获取分段错误以删除链表中的节点

Question

我正在尝试编写一个用于删除链表中节点的函数，给定一个指向头部的双指针和一个指向要删除的节点的指针。（要删除的节点不会是尾节点）这是我试过的：-

public: 
    int value; 
    Node* next; 
};
 
/* 
headPtr is a reference to the head node(i.e. pointer to pointer) and
deleteNodePtr is the node which is to be deleted. You can see the Node definition above.
It is guaranteed that deleteNodePtr will not point to the last element.
*/ 
void deleteNode(Node** headPtr, Node* deleteNodePtr) {

     
    Node* current;  
    current=*headPtr;
    if (*headPtr==deleteNodePtr){
        *headPtr=deleteNodePtr->next;
        //delete current;
        return;
        
    }
    else {
        Node* prev = current;
        while(current->next!=deleteNodePtr){
            prev = current;
            current=current->next;
        }
        prev->next =current->next;
        //delete current;
        return;
    }
    return;

}

Answer 1

我可以看到很多东西：

1 - 在你的 while 条件下，你没有检查电流是否有效：

while(current->next!=deleteNodePtr){
            prev = current;
            current=current->next;
        }

2- 你现在可能发生了什么：deleteNodePtr 指向列表中的第二个元素，所以你永远不会进入 while 循环，这意味着 prev == current 这意味着你正在分配 current->next = current->next.

对此的解决方案是：

void deleteNode(Node** headPtr, Node* deleteNodePtr) {


    Node* current;
    current = *headPtr;
    if (current == deleteNodePtr) {
        current = deleteNodePtr->next;
        delete current;
    }
    else {
        Node* prev = current;
        current = current->next;
        while (current!= nullptr && current != deleteNodePtr) {
            prev = current;
            current = current->next;
        }

        if(current!=nullptr)
        {
            prev->next = current->next;
            delete current;
        }
    }
    return;

}

3- 你永远不会检查 headPtr 是否有效，它不可能。

4- 与其说是代码问题，倒不如说是时尚方面的建议，所以如果你不认同这个观点，可以随意忽略。在一开始，您将 *headPtr 分配给 current，但为了进一步使用 current，您使用了 headPtr。相反，如果您始终使用 current:

，那就更清楚了

原文：

 Node* current;  
    current=*headPtr;
    if (*headPtr==deleteNodePtr){
        *headPtr=deleteNodePtr->next;
        //delete current;
        return;
        
    }

建议：

 Node* current;  
    current=*headPtr;
    if (current==deleteNodePtr){
        current=deleteNodePtr->next;
        //delete current;
        return;    
    }

Answer 2

乍一看，这是用 C++ 编写的 C 风格链表。很难确定，因为我们对您的代码没有更全面的了解。 C++ 链表至少将这些函数放在 class 中，并且没有全局节点。

节点就是所谓的实现细节。它帮助我们编写列表，但是列表class的用户不应该能够声明自己的节点，也不应该知道节点的存在。希望使用您的 class 的人不会明确调用此删除功能。

您的列表 class might/should（取决于）的用户更喜欢让迭代器可供他们使用。如果为您的容器编写迭代器将允许它们与基于范围的 for 循环一起使用的话。由于您的链接列表似乎是单链接的，因此您的迭代器只能向前移动。我还用迭代器编写了 class，因为我认为在大多数情况下这将有助于防止 copy/paste 作业提交。

现在开始你的活动。根据我的评论，将头部作为双指针传递是没有意义的。您一次也没有将它用作双指针；你总是取消引用它。所以去掉中间人，从一开始就给它传递一个节点指针。

有一种情况是保证不会发生的，那就是deleteNodePtr永远不会是最后一个节点。听起来很糟糕。人们可能想要删除最后一个节点，但他们被允许并且没有给出理由。

没有代码可以捕获对空列表的删除尝试。

您的具体问题似乎出在这里：

while(current->next!=deleteNodePtr){
    prev = current;
    current=current->next;
}

当 current->next 是要删除的节点而不是 current 时，您跳出循环。您最终删除了错误的节点（current，即 deleteNodePtr 之前的 1），这可能会导致后续问题。例如，如果第二个节点应该被删除，你最终会删除你的头，这会破坏东西。我想从您的布尔条件中删除 ->next 会解决这个问题。如果没有看到更多您的代码，我无法提供更深入的解决方案。

===选读===
这是一个用 C++ class 编写的极其精简的链表。您可以在此处运行此代码：https://godbolt.org/z/7jnvje
或者自己编译。

#include <iostream>

// A simple linked list for integers
class List {
public:
  List() = default;
  ~List();
  // List(const List& other);  // Copy ctor needed for Rule of 5
  // List(List&& other) noexcept;  // Move ctor needed for Rule of 5
  void push_back(int val);

  class iterator;

  iterator begin();
  iterator end();

  iterator find(int val);
  void erase(iterator it);

  void clear();
  // friend void swap(List& lhs, List& rhs);  // Not Rule of 5; aids Rule of 5
  // List& operator=(List other);  // Assignment operator needed for Rule of 5
  /*
   * Quick note on Rule of 5 functions.
   * If your class deals with heap-allocated resources, certain functions become
   * required. The only one I included was the destructor. The signature of my
   * assignment operator is different than you might see, but the reason is
   * it's written to take advantage of the copy/swap idiom.
   * 
   */
private:
  // Data
  struct Node {
    int value = 0;
    Node *next = nullptr;

    Node(int val) : value(val) {}
  };

  Node *m_head = nullptr;
  Node *m_tail = nullptr;

  // Functions
  Node *find_node(int val);
};

class List::iterator {
public:
  iterator(Node *loc) : location(loc) {}
  iterator &operator++();
  int operator*();
  bool operator==(const List::iterator &rhs);
  bool operator!=(const List::iterator &rhs);

private:
  Node *location;
};

// List Implementation
List::~List() { clear(); }

void List::push_back(int val) {
  if (m_tail) {
    m_tail->next = new Node(val);
    m_tail = m_tail->next;
    return;
  }

  m_head = new Node(val);
  m_tail = m_head;

  return;
}

List::iterator List::begin() { return iterator(m_head); }

List::iterator List::end() { return iterator(nullptr); }

List::iterator List::find(int val) { return iterator(find_node(val)); }

void List::erase(iterator it) {
  // Emtpy list or end()
  if (!m_head || it == end())
    return;

  Node *toDelete = find_node(*it);

  // Deleting head
  if (toDelete == m_head) {
    m_head = m_head->next;
    delete toDelete;

    return;
  }

  // Deleting tail
  if (toDelete == m_tail) {
    Node *walker = m_head;
    while (walker->next != m_tail) {
      walker = walker->next;
    }
    m_tail = walker;
    delete m_tail->next;
    m_tail->next = nullptr;

    return;
  }

  // Delete any middle node; by moving value until it is the tail, then
  // deleting the tail
  while (toDelete->next) {
    toDelete->value = toDelete->next->value;
    if (toDelete->next == m_tail) {
      m_tail = toDelete;
    }
    toDelete = toDelete->next;
  }
  delete toDelete;
  m_tail->next = nullptr;
}

void List::clear() {
  while (m_head) {
    Node *tmp = m_head;
    m_head = m_head->next;
    delete tmp;
  }
  m_tail = nullptr;
}

List::Node *List::find_node(int val) {
  if (!m_head) {
    return nullptr;
  }

  Node *walker = m_head;
  while (walker && walker->value != val) {
    walker = walker->next;
  }

  return walker;
}

// List iterator implementation
List::iterator &List::iterator::operator++() {
  location = location->next;

  return *this;
}

int List::iterator::operator*() { return location->value; }

bool List::iterator::operator==(const List::iterator &rhs) {
  return location == rhs.location;
}

bool List::iterator::operator!=(const List::iterator &rhs) {
  return !(*this == rhs);
}

// Free function
// NOTE: Should take list by const reference, but I didn't add the necessary
// code for that. I'm not passing by value because I also left out Rule of 5
// code that is otherwise required.
// NOTE 2: Could also be templatized and made more generic to print any
// container, but that's outside the scope of this answer.
void print(List &list) {
  for (auto i : list) {
    std::cout << i << ' ';
  }
  std::cout << '\n';
}

int main() {
  List list;

  for (int i = 1; i <= 10; ++i) {
    list.push_back(i);
  }

  print(list);
  list.erase(list.find(1));
  print(list);
  list.erase(list.find(10));
  print(list);
  list.erase(list.find(6));
  print(list);

  auto it = list.begin();
  for (int i = 0; i < 3; ++i) {
    ++it;
  }
  list.erase(it);
  print(list);

  list.erase(list.find(25));  // Bogus value; could throw if so desired
  print(list);
}

使用双向链表擦除更容易，但我们没有。我的擦除功能进行了一些检查并分别处理了头部和尾部的情况。对于列表中间的任何节点，我都懒得专门删除该节点。我做的是将要删除的值洗牌到列表的尾部，然后删除尾部。

我的评论指出了一些遗漏的内容。我也没有将任何函数标记为 const。我的迭代器不满足 ForwardIterator 的所有要求。人们可能会找到我遗漏的其他东西。我有几个原因。主要是这是快速而肮脏的代码，我不想提供 copy/paste 解决方案的诱惑。

不过，如果所有 C++ 讲师都真正教授 C++，那就太好了。这种形式的链表不应该再在 C++ 中教授 class。

在此代码上获取分段错误以删除链表中的节点

getting segmentation fault on this code for deletion of node in linked list

c++

linked-list

segmentation-fault