使用 "raw" 指针的问题。如何从自定义链接列表中删除重复值？

Question

现在我的代码有点……过于复杂了。我觉得我必须缺少一个更简单的算法来完成这项任务。基本上这个分配的唯一规则是我们不能使用容器或其他库。我将在下面包含我的代码，这样您可能会更好地了解我要做什么。代码可以编译，但有时只会给我正确的输出。

代码有几个步骤，它首先遍历一个可以有任何数据类型的链表，并一次提取一个元素。然后它将每个元素与列表中的每个其他元素进行比较，如果在列表中的所有数据中找到 2 个匹配项，则删除第二个匹配元素并将匹配项数设置回 1.

我正在对每个元素执行 push_back() 和 pop_front()，但只对重复的数据执行 pop_front()（当 numMatches = 2 时）。

最后，我根据删除的数量（或额外元素的数量）重新组织，使列表恢复原状。

我不太确定错误是从哪里弹出来的，我觉得这一定与push_back()和pop_front()的方法有关，但我想不出另一种方法在没有元素访问选项的情况下遍历指针。

举个例子i/o如果输入{1, 2, 4, 2, 3, 2, 3}，输出就是{1, 2, 4, 3}

void unique(){
    if (this->size_ <= 0){
      throw std::domain_error("unique() : must be 1 or more elements");
    }
    // check each value against every other value
    // nested for loops?
    // always push, pop for any matches
    Node* outerElem = this->head_;
    int numDeletions;
    for (unsigned i = 0; i < this->size_; ++i){
      int numMatches = 0;
      auto cmp = outerElem->data;
      Node* innerElem = this->head_;
      for(unsigned j = 0; j < this->size_ + 1; ++j) {
        if (innerElem->data == cmp){
          ++numMatches;
        }
        if (numMatches <= 1) {
          // not delete, means we found same element
          // or non-matching element
          push_back(innerElem->data);
          innerElem = innerElem->next; 
          pop_front();
        } else if (numMatches == 2) {
          // means there are at least 2 instances of the same element
          innerElem = innerElem->next;
          pop_front();
          ++numDeletions;
          --numMatches; // reset numMatches so it can detect if there's another match
        }
      }
    }
    for(unsigned k = 0; k < numDeletions; ++k) { // put values in original order
      push_back(this->head_->data);
      pop_front();
    }
  }

这是节点 class 的代码，其中包含使用的指针：

 struct Node {
    T data;  // Actual value for list element
    Node* next = nullptr;
    Node* prev = nullptr;
  };
  Node* head_ = nullptr;
  Node* tail_ = nullptr;
  std::size_t size_ = 0;
};

Answer 1

我建议在您的链接列表上提供一个 remove 方法，然后您可以删除嵌套循环中找到的所有重复项：

    void removeNode(Node* node) {
        // This method assumes that the provided node is a member of the list
        if (node == head_) {
            head_ = head_->next;
        } else {
            node->prev->next = node->next;
        }
        if (node == tail_) {
            tail_ = tail_->prev;
        } else {
            node->next->prev = node->prev;
        }
        size_--;
        delete node;
    }

    void unique() {
        Node* outerElem = this->head_;
        while (outerElem != nullptr) {
            auto cmp = outerElem->data;
            Node* innerElem = outerElem;
            while (innerElem->next != nullptr) {
                if (innerElem->next->data == cmp) {
                    removeNode(innerElem->next);
                } else {
                    innerElem = innerElem->next;
                }
            }
            outerElem = outerElem->next;
        }
    }

使用 "raw" 指针的问题。如何从自定义链接列表中删除重复值？

Issues working with "raw" pointers. How do I remove duplicate values from a custom Linked List?

c++

pointers

linked-list