有人可以帮我解决这个问题吗，作为一个持续的个人兴趣，我正在努力创建一个二叉树类，并且还创建了我自己的双端队列类 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;
}
任何关于我从根本上出错的地方的见解都将不胜感激。
非常感谢。
亚历克斯
最佳答案
这是一个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 。等瞧!
关于c++ - 创建了一个双端队列类，但无法在我的二叉树类方法中声明，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27002291/