移除第 I 个元素

Question

void removeIelement(Dlist& d, int i) {
    if (d.head == NULL) {
        cout << "EMPTY" << endl;
        return;
    }
    else {
        int count = 1;
        Node* cur = d.head;
        while (cur != NULL) {
            if (count == i) {
                Node* temp = cur->next;
                Node* temp2 = temp->next;
                cur->next = temp->next;
                temp2->prev = cur;
            }
            count++;           
            cur = cur->next;
        }
    }
}

这是我删除双向链表中第 i 个节点的代码

我的双向链表是：

1 2 3 4 5 6 7 8 9 10

但是当我运行这个程序时如果我输入 i = 1 它会删除

 1 3 4 5 6 7 8 9 10

与 i = 2 相同....它将在元素 i (i+1) 之后删除

1 2 4 5 6 7 8 9 10

你能帮我修复这个功能吗？谢谢

Answer 1

一个双向链表应该有两个属性begin和end，指向两个“empty”的地方，head->next应该指向第一个元素，end- >pre 应该指向最后一个元素，你的代码假定 head 作为第一个元素，当它试图删除第一个元素时，它会删除 head 之后的元素，即第一个元素之后的元素。 A.K.A第二个元素。

正确的代码可能是这样的：

void removeElement(Dlist& d, int id){
    if(d.head->next==d.tail){
        // the list is empty
        cout << "empty list" <<endl;
    }
    else{
        int count = 1; Node* cur = d.head->next;
        while(cur->next != NULL)
            if(count == id){
                cur->prev->next=cur->next, cur->next->prev=cur->prev;
                delete cur;
                return; //removal successful
            }
            else
                count++, cur = cur->next;
        cout << "does not exist." << endl;
    }
}

请注意，我没有测试代码。可能会有一些问题，但你明白了。

Answer 2

您没有删除任何内容。您正在围绕 temp 进行链接，但由于它从未真正被删除，因此您只是泄漏了内存。您与 cur 匹配，这意味着您想要删除 cur，但随后您将 temp 分配给 cur->next。您正在围绕 cur + 1 进行链接，这就是为什么您总是取消链接（而不是删除）第 (i + 1) 个节点的原因。您也不需要任何临时工；该列表是双向链接的。利用这一点。在双向链表中擦除非常容易。在删除命令之后，您的函数也应该立即 return。它的工作完成了。

此代码不考虑删除尾节点，因为我不知道您是否跟踪它。如果你这样做，你也需要考虑这种情况。

void removeIelement(Dlist& d, int i) {
    if (d.head == NULL) {
        cout << "EMPTY" << endl;
        return;
    }
    else {
        int count = 1;
        Node* cur = d.head;
        while (cur != NULL) {
            if (count == i) {
                cur->next->prev = cur->prev;  // Added
                cur->prev->next = cur->next;  // Changed
                if (cur == head) {            // Added
                    head = cur->next;         // Added
                }                             // Added
                delete cur;                   // Added
                return;                       // Added
            }
            count++;           
            cur = cur->next;
        }
    }
}

只要把它画在一张纸上就可以解决这个问题。事先这样做会完全消除这个问题。规划是编程中最重要的方面之一。

移除第 I 个元素

Remove Ith element

c++

doubly-linked-list