有人可以帮我解决这个问题，作为一项持续不断的个人兴趣，我正在创建一个二叉树类，并且还创建了自己的双端队列类dequeList，我想在我的二叉树类FibTree中使用它，非常新手C++程序员，并且在基础方面有困难。
我已经创建了斐波纳契数的二叉树，并且试图写出集合，并且我使用startWriteSets和writeSets方法来做到这一点；我的问题是我试图用dequeList方法声明一个新的startWriteSets，然后将其传递给writeSets方法，但是我得到了编译错误；有人可以帮助我利用我的dequeList而没有编译错误，我正在使用Xcode 3.2.2。
编译错误:Compile main.cpp'dequeList has not been declaredCompile deque.cpp'dequeList has not been declaredCompile fibtree.cpp'dequeList has not been declaredCompile fibtree.cpp'dequeList has not been declarederror: no matching function for call to 'FibTree::writeSets(dequeList*&, const FibTree::Node*&)'note: candidates are: void FibTree::writeSets(int*&, const FibTree::Node*)error: prototype for 'void FibTree::writeSets(dequeList*&, const FibTree::Node*)' does not match any in class 'FibTree'error: candidate is: void FibTree::writeSets(int*&, const FibTree::Node*)error: 'setsList' was not declared in this scopeerror: 'setsList' was not declared in this scope
我的代码在下面列出，但有错误:
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
deque.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;
}
对于我从根本上犯了错误的任何见解，将不胜感激。
提前谢谢了。
亚历克斯
最佳答案
这是circular dependency问题，导致包含项无法按预期工作。
说明:
在main.cpp中，您包括deque.h。但是deque.h在声明任何内容之前包括fibtree.h本身。 Unfortunatley FibTree类需要dequeList，因此 header 在其开头包含自身deque.h。由于此刻已经定义了DEQUE_H，因此不再包含该文件。当鼓励在dequeList中首次使用fibtree.h时，此类尚未定义!因此，错误。
解决方案:
当您有两个相互依赖的类时，您需要使用前向声明。
为了解决这个问题，您可以在fibtree.h定义之前的以下行中添加FibTree:
class dequeList; // Forward declaration
像在此文件中一样，您不引用
dequeList对象，而仅引用dequeList的指针，此前向声明足以使编译器知道您的类存在。然后可以完全定义FibTree类，然后编译器可以处理dequeList header 。等等!关于c++ - 创建了双端队列类，但是无法在我的二叉树类方法中声明，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27002291/