使用“原始”指標的問題。如何從自定義鏈接串列中洗掉重復值？

現在我的代碼有點……過于復雜了。我覺得我必須缺少一個更簡單的演算法來完成這項任務。基本上這個分配的唯一規則是我們不能使用容器或其他庫。我將在下面包含我的代碼，以便您更好地了解我正在嘗試做什么。代碼編譯，但有時只給我正確的輸出。

該代碼有幾個步驟，它首先遍歷一個可以具有任何資料型別的鏈表，并一次提取一個元素。然后它將每個元素與串列中的每個其他元素進行比較，如果在串列中的所有資料中找到 2 個匹配項，則洗掉第 2 個匹配元素并將匹配項數設定回 1。

我正在對每個元素執行 a push_back()and pop_front()，但只pop_front()對重復的資料執行 a and （當 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();
    }
  }

這是 Node 類的代碼，其中包含使用的指標：

 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;
};

uj5u.com熱心網友回復：

我建議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;
        }
    }

標籤：C 指针 链表

上一篇：對結構的參考

下一篇：PHP遞回函式-如何避免使用全域變數