0

所以我有一个 Queue 类的双向链表实现（见下文）当我尝试将整数和字符串排入队列时，这个队列类工作得非常好，但由于某种原因，当我尝试将自定义类排入队列时，我的程序永远不会移过enqueue()main 中调用的行。我认为这可能是一个无限循环，但我不确定。简而言之，为什么我的enqueue()方法适用于 int、char 和字符串等基本数据类型，但不适用于自定义类？

这是我的队列课...

//
//  queue.h
//  
//
//  Created by Aaron Mamparo on 2/22/13.
//
//

#ifndef _queue_h
#define _queue_h

#include <iostream>
#include <stdio.h>

using namespace std;

template<class Type>
class Node {
public:
    Type elem;
    Node* next;
    Node* prev;
    Node() {}
    Type Elem() { return elem; }
    Node* Next() { return next; }
    Node* Prev() { return prev; }
};

template<class Type>
class Queue {
    Node<Type> *head;
    Node<Type> *tail;
public:
    Queue();
    ~Queue();
    bool isEmpty();
    int size();
    void enqueue(Type);
    Type dequeue();
    Node<Type>* at(int);
    Type get(int);
};

//default constructor
template<class Type>
Queue<Type>::Queue(){
    head = NULL;
    tail = NULL;
}

//destructor
template<class Type>
Queue<Type>::~Queue(){
    if(!isEmpty()){
        while(head){
            Node<Type> *del = head;
            head = head->next;
            delete[] del;
        }
    }
}

//return true if queue is empty
template<class Type>
bool Queue<Type>::isEmpty(){
    return head == NULL;
}

//return number of elems in queue
template<class Type>
int Queue<Type>::size(){
    int count = 0;
    Node<Type> *temp = head;
    while(temp){
        temp = temp->next;
        count++;
    }
    delete temp;
    return count;
}

//insert elem to back of queue
template<class Type>
void Queue<Type>::enqueue(Type T){
    Node<Type> *newNode = new Node<Type>();
    newNode->elem = T;
    newNode->next = NULL;
    if(head==NULL){
        head = tail = newNode;
        newNode->prev = NULL;
    } else {
        newNode->prev = tail;
        tail->next = newNode;
        tail = newNode;
    }
}

//remove elem from front of queue
template<class Type>
Type Queue<Type>::dequeue(){
    if(isEmpty()){
        cerr << "Error: trying to dequeue from empty queue" << endl;
    } else {
        Type ret = head->Elem();
        Node<Type> *del = head;
        head = head->next;
        delete del;
        return ret;
    }
}

//return a pointer to element at position i
template<class Type>
Node<Type>* Queue<Type>::at(int i){
    if(isEmpty()){
        return '\0';
    } else if (i>size()-1){
        return NULL;
    } else {
        Node<Type> *temp = new Node<Type>();
        temp = head;
        for(int j=0; j<i; j++){
            temp = temp->next;
        }
        return temp;
    }
}

//remove & return element at position i
template<class Type>
Type Queue<Type>::get(int i){
    if(isEmpty()){
        return NULL;
    } else if (i>size()-1){
        return NULL;
    } else {
        Node<Type> *temp = new Node<Type>();
        temp = head;
        for(int j=0; j<i; j++){
            temp = temp->next;
        }
        temp->prev->next = temp->next;
        temp->next->prev = temp->prev;
        Type ret = temp->Elem();
        delete temp;
        return ret;
    }
}
#endif

和我的主要司机不会过去stateQueue.enqueue(state);

int main() {
    Queue<State> stateQueue;
    State newState = readInput();    //'readInput()' returns an instance of 'State'
    stateQueue.enqueue(newState);

    cout << "DONE" << endl;
    return 0;
}

在上面的代码中，永远不会显示“DONE”......我确定这readInput()不是问题，因为当我在.enqueue()调用之前插入它时会打印“DONE”......有什么想法吗？

提前致谢

编辑：这是我的类的默认构造函数、复制构造函数、析构函数和重载赋值运算符State...

State::State(){
    pieces = Queue<Piece>();
    stateHistory = Queue<string>();
    moveHistory = Queue<string>();
    rows = 0;
    cols = 0;
}

//copy constructor
State::State(const State& rhs){
    pieces = rhs.pieces;
    stateHistory = rhs.stateHistory;
    moveHistory = rhs.moveHistory;
    rows = rhs.rows;
    cols = rhs.cols;
}

//destructor
State::~State(){
}

//overloaded assignment operator
State& State::operator=(const State &rhs){
    pieces = rhs.pieces;
    stateHistory = rhs.stateHistory;
    moveHistory = rhs.moveHistory;
    rows = rhs.rows;
    cols = rhs.cols;
    return *this;
}

编辑：这是我刚刚实现的复制构造函数和重载赋值运算符......

template<class Type>
Queue<Type>::Queue(const Queue<Type>&Q)
{
    *this = Q;
}

template<class Type>
Queue<Type>& Queue<Type>::operator=(const Queue<Type> &Q)
{
    head = Q.head;
    tail = Q.tail;
    return *this;
}
4

1 回答 1

0

简而言之，为什么我的 enqueue() 方法适用于 int、char 和字符串等基本数据类型，但不适用于自定义类？

很难确定，因为您没有提供 State 类的详细信息，但问题似乎存在，您有一个原始指针或其他东西，并且没有实现您在 Queue::enqueue() 中使用的正确赋值运算符方法：

newNode->elem = T;

PS您添加了 State 实现（虽然不是定义），但它表明它在内部使用 Queue 类本身。状态赋值使用编译器生成的队列赋值运算符，但队列类有原始指针，所以你得到头指针的双重删除。

一种可能的解决方案是将指向对象的指针存储在队列中，而不是对象本身：

typedef boost::shared_ptr<State> StatePtr;
int main() {
    Queue<StatePtr> stateQueue;
    StatePtr newState = readInput();    //'readInput()' now returns a smart pointer to 'State'
    stateQueue.enqueue(newState);

    cout << "DONE" << endl;
    return 0;
}

您将需要相应地更改 readInput() 。另外我建议禁止复制和分配 Queue 对象，因此编译器将帮助您防止此类问题。

于 2013-02-23T18:21:32.380 回答