我正在尝试用C++实现一个队列。队列包含字符串。
我使用以下代码：
#include <iostream>
#include <stdlib.h>
struct qnode {
std::string data;//it stores a string
qnode *link;//and has a pointer to the next node in the structure.
};
class queue {
private:
qnode *front; // Pointer to first node.
qnode *rear; // Pointer to last node.
public:
// Constructor.
queue();
//Is the queue empty?
bool empty() ;
//peeks first element
int first(std::string *c);
// Adds element to the queue.
int enqueue(std::string c);
// Extracts an element from the queue.
int dequeue(std::string *c);
// Destructor.
~queue();
};
//////////// ACTUAL CODE /////////////
//Constructor, front and rear initially point to null.
queue::queue() {
front = NULL;
rear = NULL;
}
// If front points to null then the queue is empty.
bool queue::empty() {
return (front == NULL);
}
int queue::first(std::string *c) {
int res = 1;
if (!empty()) {
res = 0;
*c = front->data;
}
return res;
}
//Function for adding an element to the end of queue.
int queue::enqueue (std::string c){
int res = 1;
qnode *tmp; // Auxiliar pointer.
tmp = new qnode; //Auxiliar new node.
if(tmp != NULL) {
// If the queue is empty then we store the data in tmp and make its link point to null and front and rear become tmp.
if(empty()){
tmp->data = c;
tmp->link = NULL;
front = tmp;
rear = tmp;
rear->link = tmp;
} else {
// If it is not, then last node's link point to tmp, we store the data in tmp and tmp's link point to null.
rear->link = tmp;
tmp->data = c;
tmp->link = NULL;
// Rear of the queue points to tmp now.
rear = tmp;
}
res = 0;
}
return res;
}
// Function for extracting an element from the queue.
int queue::dequeue(std::string *c){
int res = 1;
// We make sure queue is not empty and access first node's data with the help of tmp.
if(!empty()) {
qnode *tmp;
tmp = front;
//The data extracted is stored in the character container c, passed by reference.
*c = tmp->data;
// Front now has to point to the next node and the old element has to be deleted.
front = front->link;
delete tmp;
res = 0;
}
return res;
}
// Destructor
queue::~queue() {
// If it is already empty we don't have to do anything.
if (empty()){
return;
}
qnode *tmp;
// We take front element and delete it throught a tmp node till the queue is empty.
while (!empty()){
tmp = front;
front = front->link;
delete tmp;
}
}
//////////// MAIN ///////////
int main(int argc, char *argv[]) {
queue queue;
std::string str2;
queue.enqueue("hello");
queue.dequeue(&str2);
std::cout << str2;
}
遗憾的是，我得到了以下错误：
$g++-o问题issue.cpp$/问题问题（23060,0x7fff71058310）malloc：*对象0x7f962b403920出错：释放的指针未分配*在malloc_error_break中设置断点以调试helloAbort陷阱：6
如果我对队列析构函数（"while"块）进行注释，则实现工作正常。使用char元素（只有单个字母），实现也很好。
有人能启发我吗？
您的问题是，在入队函数中将rear->链接初始化为tmp-在enqueue()的空队列部分将行rear->link = tmp更改为rear->link = NULL，这对我来说很好^^您的最后一个节点不应该指向任何东西，当您到达终点时，您试图删除同一内存两次，因为该内存是链接到自己的。
编辑：现在是更重要的答案。您的列表和队列实现都不遵循三巨头规则。规则的基本概述是这样的（尽管你肯定仍然应该阅读链接——这是C++中最重要的习惯用法之一）：
如果一个类动态管理资源，它应该提供一个复制构造函数、赋值运算符和一个析构函数任何违反此规则的类（即您的类）都有创建指针副本，然后将其删除的风险。在您的示例中，它看起来是这样的：
您的队列已使用所需的字符串初始化。一切看起来都很好。然后调用函数l.insert(queue, 0)，其原型如下：int insert(queue c, int position);
需要注意的重要一点是，队列是由VALUE传递的，这意味着它会被复制（使用复制构造函数-三大规则#1），然后列表节点会用THET COPY的数据创建，也就是头指针，最具体地说。由于您没有提供复制构造函数，该指针只是按位复制的——这意味着队列的副本（您要插入到列表中的数据）具有与您传入的队列完全相同的头指针，但它是一个不同的对象。
然后，编写行tmp->data=c;，这是三大函数中的另一个，赋值运算符。同样，您没有提供一个，因此指针再次按位分配，这导致了与复制构造函数相同的问题。
到目前为止，我们已经获得了传入的队列对象的三个副本，它们都具有相同的头指针。看到我们要去哪里了吗？
现在，当list::insert()函数结束时，它将销毁它创建的所有本地对象。这是什么意思？这意味着在按值传递队列时调用创建的副本的析构函数。由于它与队列的其他两个副本具有相同的头指针，因此它会遍历它们的列表以及自己的列表，随意删除所有内容。所以现在，您的列表节点的队列数据是垃圾，但我们还没有完全崩溃和烧毁。让我们看看程序退出时会发生什么。
现在有趣的开始了——你看到的两次免费错误（事实上，这是三次免费，因为我们做了三次，还记得吗？）。当程序退出时，其他两个副本的析构函数也会被调用，它们会尝试遍历列表，再次删除所有内容。
那么，我们该如何解决这些问题呢
提供的链接将为您提供更深入的解释，但您需要做的是确保这些类都提供三巨头规则中的所有函数，并且这些函数在必要时进行深度复制，而不是将指针复制到头部（例如），您的队列应该创建一个new qnode;，将其设置为头部，并用另一个列表的头部数据的副本来填充其数据。例如（我没有编译这个，也没有错误检查等等），队列的复制构造函数可能看起来像这样：
Queue::Queue(const Queue &other)
{
head = new qnode; //IMPORTANT: don't copy the value of the pointer (like the compiler
// will by default if you let it)
head->data = other.head->data;
qnode *tmp = other.head->link;
while (tmp != nullptr)
{
qnode *tmp2 = new qnode; //again, don't copy the value of the pointer!
tmp2->data = tmp.data; //make a new node and copy the data
tmp2->link = nullptr;
rear->link = tmp2; //update the tail of the list
rear = tmp2;
}
}
希望能有所帮助。。。打字比我预想的要多！但是你举了一个非常好的例子来说明为什么三巨头规则是C++中最重要的习惯用法之一。每当你打破三巨头规则，这些事情就会发生。