c++ - 在 C++ 中将结构元素地址设置为 null(单链表)

Question

我有这个结构:

struct Node {
    int num;
    Node *next;

    Node(int, Node*);
};

在类 Collection 中。

当我尝试删除列表的最后一个元素时，使用这个函数:

void Collection::remove(int num){
   Node *target = find(num);
   if (target == nullptr) return;
   n--;
   Node *temp = target ->next;
   if (temp == nullptr) {
       delete target;  
       target = nullptr;       // This is where the problem occurs
       return;
   } 
   target->num = temp->num;
   target->next = temp->next;
   delete temp;
}

前一个Node的*next仍然指向现在为空的地址位置，如何设置target内存位置为null ？

有关更多信息，这是我的函数 find()

Collection::Node* Collection::find(int num) {
    Node *temp = head;
    while (temp != nullptr && temp->num != num) temp = temp->next;
    return temp;
}

Answer 1

您实际上对正常的删除逻辑使用了轻微的变体，这在大多数 情况下都有效。该变体不是删除当前元素，而是将数据 从后续元素移入其中，然后删除该后续元素。这意味着您永远不必返回到前一个元素，这是使用单链表很难做到的(无需存储额外信息或再次遍历列表)。

不幸的是，当您删除列表中的最后一个元素时，不会 起作用的一种情况是。在这种情况下，没有后续元素可以从中移动数据，因此您需要删除当前元素并调整前一个元素以成为列表的新结尾。

而且，既然你无论如何都需要这样做，你也可以恢复到所有情况下的正常逻辑:-)

根据该逻辑，您基本上需要在要删除的元素之前访问该元素。然后设置它的 next 指针以绕过您要删除的指针。

您还需要处理删除列表中第一个 元素的特殊情况。假设您有一个 head 成员指向第一个元素，curr/prev 成员分别指向您要删除的节点及其前身，伪代码将是:

if curr is head:
    set head to curr.next
else
    set prev.next = curr.next
free curr

---

在不涉及太多更改的情况下轻松完成此操作的一种方法是修改您的 find 方法，以便您可以也使用它来获取前一个节点:

Node* Collection::find(
    int num,
    Node **pPrev = nullptr
) {
    // Initially store null as previous item.

    if (pPrev != nullptr) *pPrev = nullptr;

    // Cycle through list until found or not there.

    Node *temp = head;
    while ((temp != nullptr) && (temp->num != num)) {
        // Update previous before advancing.

        if (pPrev != nullptr) *pPrev = temp;
        temp = temp->next;
    }
    return temp;
}

请注意，我只是在代码中使用了 Node 而不是 Collection::Node，因为你的问题有两种变体，我不确定你是否在名为 Collection 的 namespace 中。根据您的实际使用情况，根据需要进行简单调整。

在任何情况下，将第二个参数默认为 nullptr 将允许您像当前一样调用它(使用一个参数，它不会费心尝试存储前一个节点指针)。

但是，如果您想要之前的指针，您可以使用类似这样的方法来删除:

Node *prev;
Node *curr = find(num, &prev);    // Get previous as well.
if (curr != nullptr) {            // Only delete if actually found.
    if (prev == nullptr)          // Null means current is head.
        head = curr->next;
    else                          // Otherwise adjust previous.
        prev->next = curr->next;
    delete curr;                  // Regardless of head-ness, delete.
}