2

PG。暴露出来的 29 本书的 Programming interviews 有以下示例代码，用于从链表中删除一个元素：

bool deleteElement(IntElement **head, IntElement *deleteMe)
{

     IntElement *elem = *head;

     if(deleteMe == *head){ /*special case for head*/
         *head = elem->next;
         delete deleteMe;
         return true;
     }

     while (elem){
         if(elem->next == deleteMe){
             /*elem is element preceding deleteMe */
             elem->next = deleteMe->next;
             delete deleteMe;
             return true;
         }
         elem = elem->next;
     }

     /*deleteMe not found */
     return false;   
}

我的问题是关于“delete deleteMe”语句，这是否达到了我们想要的效果，即实际删除该位置的元素，还是只是删除指向 deleteMe 元素的指针的副本？

4

3 回答 3

4

delete deleteMe;调用元素的析构函数并释放其关联的内存。这段代码是 C++，顺便说一句。

其余代码更改数据结构列表，以取消元素与其相邻元素的链接。

于 2012-10-04T04:12:16.173 回答
3

您的问题已经得到解答，但我觉得有必要指出，如果我正在采访某人，并且他们以这种方式编写代码，我不会印象深刻。

对于初学者来说，这里使用指向指针的指针虽然在 C 中是合理的，但在 C++ 中完全没有必要。相反，我更愿意看到对指针的引用。其次，const 正确的代码通常更可取。

bool deleteElement(IntElement const *&head, IntElement const *deleteMe)
{
     IntElement *elem = head;

     if(deleteMe == head){ /*special case for head*/
         head = elem->next;
         delete deleteMe;
         return true;
     }    
     while (elem){
         if(elem->next == deleteMe){
             /*elem is element preceding deleteMe */
             elem->next = deleteMe->next;
             delete deleteMe;
             return true;
         }
         elem = elem->next;
     }    
     /*deleteMe not found */
     return false;   
}

最后，我会再添加一个特殊情况，以避免不必要地遍历列表。除非要删除的项目恰好位于列表的最后，否则您可以避免遍历。假设您的 IntElement 类似于：

struct IntElement { 
    int data;
    IntElement *next;
};

在这种情况下：

bool simple_delete(IntElement *deleteMe) {
    IntElement *temp = deleteMe->next;
    deleteMe->data = temp->data;
    deleteMe->next = temp->next;
    delete temp;
    return true;
}

他们正在搜索整个列表以找到前一个元素，因此他们可以删除它之后的元素。相反，我们只需将下一个节点复制到当前节点，然后删除下一个节点（注意：在某些情况下，交换数据而不是复制会更好/更快）。另请注意，如果其他东西可能持有指向下一个节点的指针，这可能/将会破坏事情（非常彻底）。

[对于它的价值，我最初是从Niklaus Wirth 的Algorithms + Data Structures = Programs中学习到这项技术的，尽管我相信它起源于 Knuth。]

无论如何，一旦我们有了它，我们只需添加一些代码来deleteElement使用它，除非要删除的节点恰好是列表中的最后一个：

bool deleteElement(IntElement const *&head, IntElement *deleteMe) { 
    if (deleteMe->next != NULL)
        return simple_delete(deleteMe);
    // previous body of deleteElement
}

原件总是具有线性复杂性，而在大多数情况下，这具有恒定的复杂性。通过使用带有标记值的列表而不是末尾的 NULL 指针，您可以确保在所有情况下都保持恒定的复杂性（并simple_delete处理所有情况——您可以完全消除其余代码）。

于 2012-10-04T05:01:33.653 回答
1

它实际上是删除节点本身而不是它的副本。

于 2012-10-04T04:08:17.640 回答