Question

C++ 模板 二叉树实现的map 编译不过，请问是什么原因?

/*
* average.cpp
* ------------
* This program adds scores and prints their average.
*/
#include "simpio.h"
#include <iostream>
#include "error.h"
#include "random.h"

/*
#ifdef _MAP_H
#define _MAP_H
*/

template <typename KeyType,typename ValType>
class map
{
public:
map();
~map();
void PrintMap();
void Insert(KeyType key,ValType value);
bool Remove(KeyType key);
ValType GetValue(KeyType key);
int size();
bool IsContain(KeyType key);
private:
struct node{
KeyType key;
ValType value;
node* left,*right;
};
node* root;
node* treeSearch(node *n,KeyType key);
void treeEnter(node * &n,KeyType key,ValType value);
void PrintMap(node * root);
//DISALLOW_COPY(map);
};
template <typename KeyType,typename ValType>
void map<KeyType,ValType>::PrintMap()
{
PrintMap(root);
}

template <typename KeyType,typename ValType>
map<KeyType,ValType>::map()
{
root = NULL;
}
template <typename KeyType,typename ValType>
map<KeyType,ValType>::~map()
{
}
template <typename KeyType,typename ValType>
void map<KeyType,ValType>::PrintMap(node * root)
{
if(root !=NULL)
{
std::cout<<" key: "<< root->key;
std::cout<<" value: "<< root->value;
std::cout<<std::endl;
PrintMap(root->left);
PrintMap(root->right);
}
}

template <typename KeyType,typename ValType>
ValType map<KeyType,ValType>::GetValue(KeyType key)
{
node* found = treeSearch(root,key);
if(found != NULL)
return found->value;
else
ERROR("The key does not in exsit this map");
}
template <typename KeyType,typename ValType>
node* map<KeyType,ValType>::treeSearch(node *n,KeyType key)
{
if(n->key == key)
return n;
if(n==NULL) return NULL
else
{
if(key<n->value)
{
treeSearch(n->left, key);
}
else
{
treeSearch(n->right, key);
}
}

}
template <typename KeyType,typename ValType>
void map<KeyType,ValType>::treeEnter(node * &n,KeyType key,ValType value)
{
if(n == NULL)
{
n = new node;
n->key =key;
n->value =value;
n->left = n->right = NULL;
}
else if( key == n->key)
{
n->value = value;
}
else if(key < n->key)
{
treeEnter(n->left,key,value);
}
else
treeEnter(n->right,key,value);

}
template <typename KeyType,typename ValType>
void map<KeyType,ValType>::Insert(KeyType key,ValType value){
return treeEnter(root,key,value);
}

//#endif

int main(int argc, char **argv)
{
map<int,int> *a = new map<int,int>();
for(int i = 0 ;i<1000;i++){
a->Insert(randomInteger(1,10000),randomInteger(1,10000));
}
a->PrintMap();
system("pause");
return 0;
}

错误 4 error C2065: “KeyType”: 未声明的标识符
错误 5 error C2065: “ValType”: 未声明的标识符

Answer 1

node*  map<KeyType,ValType>::treeSearch(node *n,KeyType key)
	{
		if(n->key == key)
			return n;
		if(n==NULL) return NULL;
		else
		{
			if(key<n->value)
			{
	    		treeSearch(n->left, key);
			}
			else
			{
				treeSearch(n->right, key);
			}
		}
	 
	}

这个函数放到类里面定义，不要放在类外面，最终修改如下：

template <typename KeyType,typename ValType>
class map
{
public:
	map();
	~map();
	void PrintMap();
	void Insert(KeyType key,ValType value);
	bool Remove(KeyType key);
	ValType GetValue(KeyType key);
	int size();
	bool IsContain(KeyType key);

	struct node{
		KeyType key;
		ValType value;
		node* left,*right;
	};

private:
	
	node* root;
	//node* treeSearch(node *n,KeyType key);
	void treeEnter(node * &n,KeyType key,ValType value);
	void PrintMap(node * root);
	
	node*  map<KeyType,ValType>::treeSearch(node *n,KeyType key)
	{
		if(n->key == key)
			return n;
		if(n==NULL) return NULL;
		else
		{
			if(key<n->value)
			{
	    		treeSearch(n->left, key);
			}
			else
			{
				treeSearch(n->right, key);
			}
		}
	 
	}

	//DISALLOW_COPY(map);
};
template <typename KeyType,typename ValType>
void map<KeyType,ValType>::PrintMap()
{
	PrintMap(root);
}
 
template <typename KeyType,typename ValType>
 map<KeyType,ValType>::map()
{
	root = NULL;
}
template <typename KeyType,typename ValType>
 map<KeyType,ValType>::~map()
{
}
template <typename KeyType,typename ValType>
void  map<KeyType,ValType>::PrintMap(node * root)
{
	if(root !=NULL)
	{
		std::cout<<" key: "<< root->key;
		std::cout<<" value: "<< root->value;
		std::cout<<std::endl;
		PrintMap(root->left);
		PrintMap(root->right);
	}
}
 
template <typename KeyType,typename ValType>
ValType  map<KeyType,ValType>::GetValue(KeyType key)
{
	node* found = treeSearch(root,key);
	if(found != NULL)
		return found->value;
	else
		ERROR("The key does not in  exsit this map");
}

template <typename KeyType,typename ValType>
void  map<KeyType,ValType>::treeEnter(node * &n,KeyType key,ValType value)
{	
	if(n == NULL)
	{
		n = new node;
		n->key =key;
		n->value =value;
		n->left = n->right = NULL;
	}
	else if( key == n->key)
	{
		 n->value = value;
	}
	else if(key < n->key)
	{
		treeEnter(n->left,key,value);
	}
	else
		treeEnter(n->right,key,value);
 
}
template <typename KeyType,typename ValType>
void map<KeyType,ValType>::Insert(KeyType key,ValType value){
		return treeEnter(root,key,value);
}
 
//#endif
 
int main(int argc, char **argv)
{
	map<int,int> *a = new map<int,int>();
	for(int i = 0 ;i<1000;i++){
		a->Insert(randomInteger(1,10000),randomInteger(1,10000));
	}
	a->PrintMap();
	system("pause");
	return 0;
}

由于你给的也不是全部代码，剩下的问题需要你按如上修改后再看一下还有什么问题。也许问题不是出在你给的上述代码中。

追问

你的代码是怎么贴成这样的格式的？ 挺整齐的！

追答

Answer 2

node 的定义出了问题 ，在类外引用类中类的名称需要带名字域

Answer 3

node* map<KeyType,ValType>::treeSearch(node *n,KeyType key)这个函数放到类里面定义
也可以把node的定义放在外面，不过他也要template，很麻烦
放在里面吧

Answer 4

声明一下不就完了！