c++ - 创建了一个双端队列类，但无法在我的二叉树类方法中声明

Question

有人可以帮我解决这个问题吗，作为一个持续的个人兴趣，我正在努力创建一个二叉树类，并且还创建了我自己的双端队列类 dequeList，我想使用它在我的二叉树类 FibTree 中，我是一个非常新的 C++ 程序员并且在基础知识方面有困难。

我已经创建了一个斐波那契数列的二叉树，我正在尝试写出集合，我正在使用方法 startWriteSets 和 writeSets 来执行此操作;我的问题是我试图用 startWriteSets 方法声明一个新的 dequeList，然后将它传递给 writeSets 方法，但我得到编译错误；有人可以帮我使用我的 dequeList 而不会出现编译错误吗，我使用的是 Xcode 3.2.2。

编译错误:编译main.cpp
'dequeList 尚未声明

编译deque.cpp
'dequeList 尚未声明

编译fibtree.cpp
'dequeList 尚未声明

编译fibtree.cpp
'dequeList 尚未声明

错误:没有用于调用“FibTree::writeSets(dequeList*&, const FibTree::Node*&)”的匹配函数

注意:候选者是:void FibTree::writeSets(int*&, const FibTree::Node*)

错误:“void FibTree::writeSets(dequeList*&, const FibTree::Node*)”的原型(prototype)与类“FibTree”中的任何内容都不匹配

错误:候选是:void FibTree::writeSets(int*&, const FibTree::Node*)

错误:“setsList”未在此范围内声明

错误:“setsList”未在此范围内声明

我的代码如下，有错误:

deque.h

/*
 *  deque.h
 *  fibonacci / deque / interface
 *  deque holding FibTree::Node datatype
 *  using a double-linked list implementation
 */

#ifndef DEQUE_H
#define DEQUE_H

#include "fibtree.h"

class dequeNode {
public:
    dequeNode* prev;
    dequeNode* next;
    FibTree::Node const* data;

    dequeNode( void );
    dequeNode( FibTree::Node const* );

};

class dequeList {
public:
    dequeNode* firstNode;
    dequeNode* lastNode;

    dequeList( void );

    void enque( FibTree::Node const* );
    void enqueFront( FibTree::Node const* );

    FibTree::Node const* deque( void );
    FibTree::Node const* dequeFront( void );
    bool isEmpty( void );

private:
    void insertAfter( dequeList* list, dequeNode* node, dequeNode* newNode );
    void insertBefore( dequeList* list, dequeNode* node, dequeNode* newNode );
    void insertBeginning( dequeList* list, dequeNode* newNode );
    void insertEnd( dequeList* list, dequeNode* newNode );
    void removeNode( dequeList* list, dequeNode* node );

    dequeNode* frontNode( dequeList* list ); // examine front
    dequeNode* backNode( dequeList* list ); // examine back
    void popFront( dequeList* list ); // delete first
    void popBack( dequeList* list ); // delete last
    void pushBack( dequeList* list, FibTree::Node const* n );
    void pushFront( dequeList* list, FibTree::Node const* n );

};

#endif

双端队列.cpp

/*
 *  deque.cpp
 *  fibonacci / deque / implementation
 *
 */

#include "deque.h"
#include <cstddef>

// Constructors
dequeNode::dequeNode()
: prev( NULL ), next( NULL ), data( NULL )
{
};

dequeNode::dequeNode( FibTree::Node const* n )
: prev( NULL ), next( NULL ), data( n )
{
};

dequeList::dequeList()
: firstNode( NULL ), lastNode( NULL )
{
};

// Public Methods
void dequeList::enque( FibTree::Node const* n ) {
    pushBack( this, n );
}

void dequeList::enqueFront( FibTree::Node const* n ) {
    pushFront( this, n );
}

const FibTree::Node* dequeList::deque( void ) {
    dequeNode* node = frontNode( this );
    const FibTree::Node* data = node->data;
    popFront( this );
    return data;
}

bool dequeList::isEmpty( void ) {
    if ( this->firstNode == NULL && this->lastNode == NULL ) {
        return true;
    } else {
        return false;
    }

}

// Private methods
void dequeList::insertAfter( dequeList* list, dequeNode* node, dequeNode* newNode ) {
    newNode->prev = node;
    newNode->next = node->next;
    if ( node->next == NULL ) {
        list->lastNode = newNode;
    } else {
        node->next->prev = newNode;
    }
    node->next = newNode;

}

void dequeList::insertBefore( dequeList* list, dequeNode* node, dequeNode* newNode ) {
    newNode->prev = node->prev;
    newNode->next = node;
    if ( node->prev == NULL ) {
        list->firstNode = newNode;
    } else {
        node->prev->next = newNode;
    }
    node->prev = newNode;

}

void dequeList::insertBeginning( dequeList* list, dequeNode* newNode ){
    if ( list->firstNode == NULL ) {
        list->firstNode = newNode;
        list->lastNode = newNode;
        newNode->prev = NULL;
        newNode->next = NULL;
    } else {
        insertBefore( list , list->firstNode, newNode );
    }

}

void dequeList::insertEnd( dequeList* list, dequeNode* newNode ){
    if (list->lastNode == NULL) {
        insertBeginning( list, newNode );
    } else {
        insertAfter( list, list->lastNode, newNode );
    }
}

void dequeList::removeNode( dequeList* list, dequeNode* node ) { // pop_front / pop_back
    if (node->prev == NULL) {
        list->firstNode = node->next;
    } else {
        node->prev->next = node->next;
    }
    if (node->next == NULL) {
        list->lastNode = node->prev;
    } else {
        node->next->prev = node->prev;
    }
    delete node;

}

dequeNode* dequeList::frontNode( dequeList* list ) { // Examine first
    return list->lastNode;
}

dequeNode* dequeList::backNode( dequeList* list ) { // Examine last
    return list->firstNode;
}

void dequeList::popFront( dequeList* list ) { // Delete first
    removeNode(list, list->lastNode);
}

void dequeList::popBack( dequeList* list ) { // Delete last
    removeNode(list, list->firstNode);
}

void dequeList::pushBack( dequeList* list, FibTree::Node const* n ) { // Append (Enque)
    dequeNode* newNode = new dequeNode( n );
    insertBeginning(list, newNode);
}

void dequeList::pushFront( dequeList* list, FibTree::Node const* n ) { // Prepend
    dequeNode* newNode = new dequeNode( n );
    insertEnd(list, newNode);
}

fibtree.h

/*
 *  fibtree.h
 *  Fibonacci binary tree / interface
 *
 */

#ifndef FIBTREE_H
#define FIBTREE_H

#include <string>
#include <iostream>
#include <vector>
#include "deque.h"

class FibTree {

public:
    class Node {
    public:
        int data;
        Node const* left;
        Node const* right;
        Node const* parent;
        int n;
        int level;
        int index;

        Node (void);

        bool isLeftChild(void) const;
        bool isRightChild(void) const;
        bool isLeafNode(void) const;
        bool hasLeftChild(void) const;
        bool hasRightChild(void) const;
        bool hasParent(void) const;
    };

    Node const* root; // 'root' pointer to constant Node

    FibTree (int);

    Node const* getRoot(void); // Getters
    int getHeight(Node const* root);

    void preOrder(Node const* root); // Tree traversals
    void preOrderFormatted(Node const* root, std::string indent = "");
    void inOrder(Node const* root);
    void postOrder(Node const* root);

    void breadthFirst(Node const* root);
    void levelOrderBreadthFirst(Node const* root);
    void loBFStructured(Node const* root);

    void writeFibTree(Node const* root); // Serialisation
    ***error: 'dequeList' has not been declared***

    void startWriteSets(Node const* root); // Write all sets of tree
    void writeSets(dequeList* &leftQueue, Node const* cur); // Used by startWriteSets

    int countNodes(Node const* root); // Node counting
    int countLeafNodes(Node const* root);
    int countInteriorNodes(Node const* root);


private:
    static Node* buildTree( int n, int level = 0, int i = 1, Node* parent = NULL );
    void printNode (Node const* root);

};

#endif

fibfree.cpp

/*
*  fibtree.cpp
*  Fibonacci binary tree / implementation
*
*/

#include <string>
#include <vector>
#include <iostream>
#include "deque.h"
#include "fibtree.h"

// FibTree Constructor
FibTree::FibTree(int n) {
    this->root = buildTree( n );
};

// Getters
FibTree::Node const* FibTree::getRoot(void) {
    return this->root;
}

int FibTree::getHeight( Node const* root ) {
    if( root == NULL || root->isLeafNode() ) {
        return 0;
    }
    return std::max(getHeight(root->left), getHeight(root->right)) + 1; 

}

// Traversals
void FibTree::preOrder(Node const* root) { // Preorder Depth First Traversal (root, left, right)
    if (root == NULL)
        return;
    printNode(root);
    preOrder(root->left);
    preOrder(root->right);
}

void FibTree::preOrderFormatted(Node const* root, std::string indent ) { // Pre-order formatted

    if (root != NULL) {
        std::cout << indent;
        if ( !root->isLeafNode() ) {
            std::cout << "|-";
            indent += "| ";
        } else {
            std::cout << "\\-";
            indent += " ";
        }
        if ( root->isLeftChild() ) {
            std::cout << root->data << " [L]" << " i=" << root->index << std::endl;
        } else if ( root->parent != NULL ) {
            std::cout << root->data << " [R]" << " i=" << root->index << std::endl;
        } else {
            std::cout << root->data << " i=" << root->index << std::endl;
        }

        if ( root->hasLeftChild() ) {
            preOrderFormatted( root->left, indent );
        }
        if ( root->hasRightChild() ) {
            preOrderFormatted( root->right, indent );
        }

    }
}

void FibTree::inOrder(Node const* root) { // Inorder (Symetric) Depth First Traversal (left, root, right); producing a sorted sequence.
    if (root == NULL)
        return;
    inOrder(root->left);
    printNode(root);
    inOrder(root->right);
}

void FibTree::postOrder(Node const* root) { // Postorder Depth First Traversal (left, right, root).
    if (root == NULL)
        return;
    postOrder(root->left);
    postOrder(root->right);
    printNode(root);
}

void FibTree::breadthFirst(Node const* root) { // Breadth-first traversal
    dequeList* list = new dequeList();
    list->enque(root);
    while ( !list->isEmpty() ) {
        Node const* node = list->deque();
        printNode( node );
        if ( node->hasLeftChild() ) {
            list->enque( node->left );
        }
        if ( node->hasRightChild() ) {
            list->enque( node->right );
        }

    }
}

void FibTree::levelOrderBreadthFirst(Node const* root) { // Level-order Breadth-first traversal
    dequeList* thisLevel = new dequeList();

    thisLevel->enque(root);

    while ( !thisLevel->isEmpty() ) { 

        dequeList* nextLevel = new dequeList();

        dequeNode* thisNode = thisLevel->lastNode; // iterate thisLevel
        while ( thisNode != NULL ) {
            printNode( thisNode->data );
            thisNode = thisNode->prev;
        }
        std::cout << std::endl;

        while ( !thisLevel->isEmpty() ) { // get next level
            Node const* node = thisLevel->deque();

            if ( node->hasLeftChild() ) {
                nextLevel->enque( node->left );
            }
            if ( node->hasRightChild() ) {
                nextLevel->enque( node->right );
            }
        }

        thisLevel = nextLevel;
    }
}

void FibTree::loBFStructured(Node const* root) { // Level-order Breadth-first traversal structured output
    // Each node is centred above it's children

    // Calculate width of of each node:
    // Amount of Hoz space required to display this node's entire subtree, 
    // such that it doesn't overlap with it's left or right siblings' subtree

    // width = 1 + sum (width of children's nodes)

    // DF traversal through tree to calc each node's width

    // To display: LOBF traversal
    dequeList* thisLevel = new dequeList();

    thisLevel->enque(root);

    while ( !thisLevel->isEmpty() ) { 

        dequeList* nextLevel = new dequeList();

        dequeNode* thisNode = thisLevel->lastNode; // iterate thisLevel

        while ( thisNode != NULL ) {
            int width = countNodes(thisNode->data);

            width +=2;

            while(width--)
                std::putchar(' ');

            std::cout << thisNode->data->data << '(' << thisNode->data->index << ')';
            thisNode = thisNode->prev;
        }
        std::cout << std::endl;

        while ( !thisLevel->isEmpty() ) { // get next level
            Node const* node = thisLevel->deque();

            if ( node->hasLeftChild() ) {
                nextLevel->enque( node->left );
            }
            if ( node->hasRightChild() ) {
                nextLevel->enque( node->right );
            }
        }

        thisLevel = nextLevel;
    }

}



// Serialisation
void FibTree::writeFibTree(Node const* root) { // Preorder tree serialisation method    
    if ( root == NULL ) {
        std::cout << "# ";
        return;
    } else {
        std::cout << root->data << " ";
        writeFibTree( root->left );
        writeFibTree( root->right );
    }
}

// Write sets of tree
void FibTree::startWriteSets(Node const* root) {
    //std::vector<Node const*> setsList;

    dequeList* leftQueue = new dequeList();

    std::cout << root->data << '(' << root->index << ')' << ',';
    writeSets(leftQueue, root);
    ***error: no matching function for call to 'FibTree::writeSets(dequeList*&, const FibTree::Node*&)'***
}

//void FibTree::writeSets(std::vector<Node const*> &setsList, Node const* cur) {
void FibTree::writeSets(dequeList* &leftQueue, Node const* cur) {
    ***error: prototype for 'void FibTree::writeSets(dequeList*&, const FibTree::Node*)' does not match any in class 'FibTree'***

    std::vector<Node const*>::iterator nodeIterator;
    std::cout << '(';

    if (! setsList.empty()) { ***error: 'setsList' was not declared in this scope***

        setsList.pop_front();
    }

    // Displays all preceding left values
    for (nodeIterator = setsList.begin(); nodeIterator != setsList.end(); nodeIterator++) { ***error: 'setsList' was not declared in this scope***



        std::cout << (*nodeIterator)->data << '(' << (*nodeIterator)->index << ')' << ',';
    }

    if (cur->hasLeftChild()) {
        std::cout << cur->left->data << '(' << cur->left->index << ')' << ',';
        setsList.push_back(cur->left);
    }
    if (cur->hasRightChild()) {
        std::cout << cur->right->data << '(' << cur->right->index << ')' << ',';

        writeSets(setsList,cur->right);

    }
    setsList.pop_back();
    std::cout << ')';


}


// Node counting
int FibTree::countNodes(Node const* root) { // Count all tree nodes
    int count = 0;

    if ( root->hasLeftChild() )
        count += countNodes(root->left);

    if ( root->hasRightChild() )
        count += countNodes(root->right);

    count += 1;
    return count;

}

int FibTree::countLeafNodes(Node const* root) { // count all leaf nodes
    // An almost complete strictly binary tree with n leafs has 2n - 1 nodes
    int count = 0;

    if ( root->hasLeftChild() )
        count += countLeafNodes(root->left);

    if ( root->hasRightChild() )
        count += countLeafNodes(root->right);

    if (!root->hasLeftChild() && !root->hasRightChild())
        count += 1;
    return count;
}

int FibTree::countInteriorNodes(Node const* root) { // Return number of internal nodes in tree
    int count = 0;

    if ( root->hasLeftChild() )
        count += countInteriorNodes(root->left);

    if ( root->hasRightChild() )
        count += countInteriorNodes(root->right);

    if ( (root->hasLeftChild() || root->hasRightChild()) && root->hasRightChild() )
        count += 1;
    return count;
}

// Private FibTree methods
FibTree::Node* FibTree::buildTree( int n, int level, int i, Node* parent ) { // Build Tree structure
    Node* thisNode = new Node();
    thisNode->n = n;
    thisNode->level = level;
    thisNode->index = i;
    thisNode->parent = parent;
    if (n < 2) {
        thisNode->left = NULL;
        thisNode->right = NULL;
        thisNode->data = n;
        return thisNode;
    } else {
        thisNode->left = buildTree( n - 1 , level + 1, i*2, thisNode );
        thisNode->right = buildTree( n - 2, level + 1, i*2+1, thisNode );
        thisNode->data = thisNode->left->data + thisNode->right->data;
        return thisNode;

    }
}

void FibTree::printNode(Node const* node) {
    std::cout << node->data << "[" << node->index << "]" << " ";
}


// FibTree Node constructor
FibTree::Node::Node()
: data( 0 ),
left( NULL ),
right( NULL ),
parent( NULL ),
n( 0 ),
level( 0 ),
index( 0 )
{
};

bool FibTree::Node::isLeftChild(void) const { // a pointer (Root) to const parameter, can only call const methods on it
    bool hasParent = this->parent != NULL;

    if ( hasParent ) {
        return this == this->parent->left;
    } else {
        return false;
    }
}

bool FibTree::Node::isRightChild(void) const {
    bool hasParent = this->parent != NULL;

    if ( hasParent ) {
        return this == this->parent->right;
    } else {
        return false;
    }
}

bool FibTree::Node::isLeafNode(void) const {
    if (this->left == NULL && this->right == NULL) {
        return true;
    } else {
        return false;
    }

}

bool FibTree::Node::hasLeftChild(void) const {
    if ( this->left != NULL ) {
        return true;
    } else {
        return false;
    }
}

bool FibTree::Node::hasRightChild(void) const {
    if ( this->right != NULL ) {
        return true;
    } else {
        return false;
    }
}

bool FibTree::Node::hasParent(void) const {
    if ( this->parent != NULL ) {
        return true;
    } else {
        return false;
    }
}

main.cpp

#include <iostream>

#include "deque.h"
#include "fibtree.h"

int main (int argc, const char* argv[]) {


    if (argc > 1) {

        int n = atoi( argv[1] ); // convert string to int
        FibTree f(n);
        //f.preOrder(f.getRoot());
        std::cout << "All Nodes count: " << f.countNodes(f.getRoot()) << std::endl;
        std::cout << "Leaf Nodes count: " << f.countLeafNodes(f.getRoot()) << std::endl;
        std::cout << "Interior Nodes count: " << f.countInteriorNodes(f.getRoot()) << std::endl;
        std::cout << "Tree Height: " << f.getHeight(f.getRoot()) << std::endl;
        //f.writeFibTree(f.getRoot());

        f.loBFStructured(f.getRoot());

        f.startWriteSets(f.getRoot());

        std::cout << std::endl;


    }

    return 0;

}

任何关于我从根本上出错的地方的见解都将不胜感激。

非常感谢。

亚历克斯

Answer 1

这是一个circular dependency问题，导致包含无法按预期工作。

解释:

在 main.cpp 中包含 deque.h。但是 deque.h 在声明任何内容之前包含它自己 fibtree.h。不幸的是，FibTree 类需要 dequeList，因此 header 在其开头包含自身 deque.h。由于此时已经定义了 DEQUE_H，因此不会再次包含该文件。当在 fibtree.h 中第一次使用 dequeList 时，这个类还没有定义!因此错误。

解决方案:

当你有两个相互依赖的类时，你需要使用前向声明。

要解决这个问题，您可以在 fibtree.h 中的 FibTree 定义之前添加以下行:

class dequeList;   // Forward declaration

因为在这个文件中你没有引用一个dequeList对象，而只是一个指向dequeList的指针，这个前向声明足以让编译器知道你的类(class)存在。然后可以完全定义您的 FibTree 类，然后您的编译器可以处理 dequeList header 。等瞧!