0

以下代码是二叉树的实现，来自 C++ 数据结构文本。我无法成功编译代码，收到一些错误消息。主要是，错误行来自代码的最后两个。如何解决这个问题？我的 IDE 是 CODE::BLOCK 12.11。

#include<iostream>
#include<list>
using namespace std;

typedef int Elem;
struct Node
{
Elem elt;
Node *par;
Node *left;
Node *right;
Node():elt(),par(NULL),left(NULL),right(NULL){}
};

class Position
{
private:
Node *v;
public:
Position(Node *_v=NULL):v(_v){}
Elem &operator*(){return v->elt;}
Position left()const{return Position(v->left);}
Position right()const{return Position(v->right);}
Position parent()const{return Position(v->par);}
bool isRoot()const{return v->par==NULL;}
bool isExternal()const{return v->left==NULL&&v->right==NULL;}
friend class LinkedBinaryTree;
};
typedef std::list<Position> PositionList;

class LinkedBinaryTree
{
protected:
struct Node; //This line is by me, the text merely tell you "insert Node declaration here. . ."  I don't know whether this line is correct or not.
public:
class Position; // Also by me, the text merely tell you "insert Position declaration here. . ." I don't know wwhether this line is correct or not.
public:
LinkedBinaryTree();
int size()const;
bool empty()const;
Position root()const;
PositionList positions()const;
void addRoot();
void expandeExternal(const Position& p);
protected:
void preorder(Node* v,PositionList& pl)const;
private:
Node* _root;
int n;
};


LinkedBinaryTree::LinkedBinaryTree():_root(NULL),n(0){}
int LinkedBinaryTree::size()const{return n;}
bool LinkedBinaryTree::empty()const{return size()==0;}
LinkedBinaryTree::Position LinkedBinaryTree::root()const{Position(_root);} //canot compile successfully, this error messages is : C:\Users\user\Documents\aa\main.cpp|58|error: return type 'class LinkedBinaryTree::Position' is incomplete
void LinkedBinaryTree::addRoot(){_root=new Node;n=1;} //canoot compile successfully, this error message is C:\Users\user\Documents\aa\main.cpp|59|error: invalid use of incomplete type 'struct LinkedBinaryTree::Node'

有很多错误信息，我选择其中一个来表示错误信息。

4

2 回答 2

1

嵌套声明通常应该发生在类内部，如下所示：

#include<iostream>
#include<list>
using namespace std;

class LinkedBinaryTree
{
  protected:
  typedef int Elem;
  struct Node
  {
     Elem elt;
     Node *par;
     Node *left;
     Node *right;
     Node():elt(),par(NULL),left(NULL),right(NULL){}
  };

  public:
  class Position
  {
    private:
    Node *v;
    public:
    Position(Node *_v=NULL):v(_v){}
    Elem &operator*(){return v->elt;}
    Position left()const{return Position(v->left);}
    Position right()const{return Position(v->right);}
    Position parent()const{return Position(v->par);}
    bool isRoot()const{return v->par==NULL;}
    bool isExternal()const{return v->left==NULL&&v->right==NULL;}
    friend class LinkedBinaryTree;
  };
  typedef std::list<Position> PositionList;
  public:
  LinkedBinaryTree();
  int size()const;
  bool empty()const;
  Position root()const;
  PositionList positions()const;
  void addRoot();
  void expandeExternal(const Position& p);
  protected:
  void preorder(Node* v,PositionList& pl)const;
  private:
  Node* _root;
  int n;
};


LinkedBinaryTree::LinkedBinaryTree():_root(NULL),n(0){}
int LinkedBinaryTree::size()const{return n;}
bool LinkedBinaryTree::empty()const{return size()==0;}
LinkedBinaryTree::Position LinkedBinaryTree::root()const{Position(_root);} //canot compile successfully, this error messages is : C:\Users\user\Documents\aa\main.cpp|58|error: return type 'class LinkedBinaryTree::Position' is incomplete
void LinkedBinaryTree::addRoot(){_root=new Node;n=1;}
于 2013-09-30T03:45:07.647 回答
1

这个：

class LinkedBinaryTree {
protected:
 struct Node;

称为前向声明 (of Node)。它告诉编译器有一个具有该名称的类型，但它不是类的定义。你不能创建一个类型的实例，除非它的定义是可见的。前向声明不是定义。

如果你写过：

class LinkedBinaryTree {
protected:
 struct Node { /* ... */ };

然后你就可以创建一个Node.

当您有相互依赖的类型，或者您更喜欢以特定方式对声明进行排序时，嵌套类的前向声明通常很有用。

前向声明有助于告诉编译器有一个具有该名称的类型，因此它可以在使用之前理解您的意图：

class LinkedBinaryTree {
protected:
 struct Node;
 void foo(Node*);
 struct Node { /* ... */ };

在这种情况下，指针不需要物理依赖，所以名称足以让编译器在看到foo.

另请注意，您的前向声明在类的范围内声明了Nodeand Position，因此编译器将其视为void preorder(Node* v,PositionList& pl)const;使用类本地的类型；例如void LinkedBinaryTree::preorder(LinkedBinaryTree::Node* v, LinkedBinaryTree::PositionList& pl)const;，而不是在代码示例的全局命名空间中声明的Positionand 。Node

于 2013-09-30T04:05:01.853 回答