Remove Ith element

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

这是我的代码，用于删除双向链接列表中的Node ith

我的双向链接列表是：

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

您没有删除任何内容。您正在围绕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;
        }
    }
}

只需将其画在一张纸上，就可以解决。事先这样做将完全消除该问题。计划是编程最重要的方面之一。

Answer 2

一个双链表应具有2个分别名为begin和end的属性，指向两个“ empty”位置，head-> next应该指向第一个元素，而end-> pre应该指向最后一个元素，您的代码假定head为第一个元素，当它尝试删除第一个元素时，它将删除head之后的元素，head是第一个元素之后的元素。

正确的代码可能看起来像这样：

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

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