在链接列表（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（）函数

回答

相关问题