從鏈表中刪除元素，採訪暴露的書蟲？

Pg。編程面試攻略書29具有下面的示例代碼從鏈表中刪除一個元素：從鏈表中刪除元素，採訪暴露的書蟲？

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

我的問題是有關語句「刪除DELETEME」，這是實現的效果，我們希望即實際刪除元素在那個位置，還是它只是刪除指向deleteMe元素的指針的副本？

來源

2012-10-04 user1487551

行'delete = deleteMe;'似乎是一個錯誤; '='是錯誤的。 – misha

感謝趕上 – user1487551

C++混合C？什麼書。 – texasbruce

它實際上是刪除節點本身，而不是它的副本。

來源

2012-10-04 04:08:17 Mahesh

delete deleteMe;調用元素上的析構函數並釋放其關聯的內存。這個代碼是C++，順便說一句。

代碼的其餘部分改變數據結構，即列表，將元素從其鄰居中解除鏈接。

來源

2012-10-04 04:12:16

什麼會刪除* deleteMe;做？ – user1487551

@ user1487551：它不會編譯。 delete的參數必須是一個指向你想要刪除的對象的指針，而deleteMe不是一個指針。 –

@ user1487551按照俗語說，是的，它會刪除'* deleteMe'。但用C++來說，它會刪除'deleteMe'。 –

你的問題已經回答了，但我覺得有必要指出，如果我正在採訪某人，並且他們用這種方式編寫了代碼，我不會感到非常驚訝。

對於初學者來說，這裏使用指向指針的指針雖然在C中合理，但在C++中完全沒有必要。相反，我寧願看到對指針的引用。其次，常量是正確的代碼通常是可取的。

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

他們正在尋找的整個列表，以找到以前的元素，這樣他們就可以後刪除元素。相反，我們只需將下一個節點複製到當前節點，然後刪除下一個節點（注意：在某些情況下，交換數據而不是複製將會更好/更快）。還要注意，如果別的東西可能持有一個指向下一個節點的指針，這可能/會破壞事情（非常徹底）。

[對於它的價值，我原來學到算法+數據結構此技術=程序，由尼古拉斯·沃斯，但我相信它起源於克努特]

不管怎樣，一旦我們有，我們只需添加一些代碼來deleteElement使用，除非該節點將被刪除恰好是在列表的最後：

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

凡原來一直線性複雜度，這有恆定在大多數情況下的複雜性。通過在末尾使用帶有標記值而不是空指針的列表，可以確保在所有情況下始終保持複雜性（並且simple_delete可處理所有個案例 - 您可以完全消除其餘代碼）。

來源

2012-10-04 05:01:33

從鏈表中刪除元素，採訪暴露的書蟲？

回答

相關問題