在鏈接列表（C++）中實現pop（）函數

我對鏈接列表的概念感到困惑。所以我試圖實現一些功能來幫助我理解。在鏈接列表（C++）中實現pop（）函數

struct Node { 
    string val; 
    Node* next; 
    Node* prev; 
}; 

struct Stew { 
    Node* first; 
    Node* last; 
};

所以這裏，燉具有特殊的指針，前面的元素和最後一個元素。

我試圖刪除第一個元素（彈出）。

所以我嘗試過如下，我似乎無法找出什麼在它的錯誤是：

void pop (Stew& q) { 
    assert (!isEmpty(q)); 
    q.first = q.first->next; 
    q.first -> prev = NULL; 
}

任何幫助，將不勝感激，謝謝！

順便說一下，我目前使用C++ 98，而不是C++ 11。

來源

2014-02-27 E 4 6

什麼告訴你這是錯誤的？你會得到編譯時/運行時錯誤還是行爲不正確，在哪些情況下不正確？ – Nabla

是否有某些原因，你沒有在鏈表類中封裝'pop'函數？ –

請注意，一個'pop'函數應該從列表中刪除第一個項目並**返回**，現在你只是失去了這個項目，沒有指向它的指針，沒有辦法使用它或釋放它使用的內存。 –

我才意識到你已經實現了一個last pontier您Stew類，因此，您可以：

struct Node { 
    string val; 
    Node* next; 
    Node* prev; 
}; 

struct Stew { 
    Node* first; 
    Node* last; 
}; 


typedef struct Node node_t; 
typedef struct Stew stew_t; 

node_t* pop(stew_t& q) 
{ 
    node_t* last = q->last; 
    if (q->last == q->first)  // List is empty or has only one element. 
    { 
     q->first = NULL; 
     q->last = NULL; 
    } 
    else 
    { 
     q->last = last->prev;  // Update the last pointer. 
    } 

    return last; 
}

來源

2014-02-27 18:17:20

你忘了釋放被刪除節點的內存delete，你沒有照顧的情況下該列表正好是一個元素長。因爲如果是這樣的話，那麼後

q.first = q.first->next;

q.first是NULL。然後嘗試取消引用q.first下一行：

q.first -> prev = NULL;

不要做這一步，如果列表是原來的一個元素長，是繼空的。相反，採取q.last照顧，不會被指向分配的內存了：

q.first = q.first->next; 
if(q.first) 
    q.first->prev = NULL; 
else 
    q.last = NULL;

（雖然取決於鏈接列表的其餘部分else塊將沒有必要實施，因爲無論是信息列表爲空的完全包含在q.last或q.first中）

另外pop通常返回移除的值。你的pop不這樣做。

來源

2014-02-27 18:17:50 Nabla

謝謝！我看到我現在出錯了。 –

在鏈接列表（C++）中實現pop（）函數

回答

相關問題