/*题目：利用BST存储数据库记录实现一个城市数据库。没 个数据库接点包含城市名称（一个任意长度的字符串）
和以整数X和Y表示的城市坐标。根据城市的名称组织该BST。这个数据库应该允许记录的插入，
根据名称或坐标的 删除，以及根据名称或坐标惊醒检索。
另一个应该实现的操作是打印出与指定点的距离在给顶值之内的所有城市记录。
统计各个操作的时间。利用BST时，那些操作的实现理所当然效率高 ？
如增加一个或多个根据坐标组织的BST，能是数据库性同更高效吗？*/
/*如果觉得看程序太复杂，那麻烦你先帮写一个，先交上去完成任务，以后在自己慢慢琢磨。
记得要写主函数测试。麻烦了啊*/
#include<iostream.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
class ID{//城市坐标类
public:
int x;
int y;};
class Cityset{//城市信息类
public:
// friend istream & operator >>( istream &input, Cityset C);
char* name;
ID id;
};
/*istream & operator >>( istream &input, Cityset C)
{
input>>C.name>>C.id.x>>C.id.y; return input;}*/
class BinNode{//二叉查找树结点类
public:
Cityset it;
BinNode* lc;
BinNode* rc;
public:
BinNode()//构造函数
{lc=NULL;rc=NULL;}
BinNode(const Cityset d)
{lc=NULL; rc=NULL;it=d;}
BinNode(const Cityset d,BinNode* l,BinNode* r)
{lc=l; rc=r;it=d;}
Cityset& val(){return it;}//获得结点信息
void setVal(const Cityset& e)
{it=e;}
inline BinNode* left()
{return lc;}
void setLeft(BinNode* a){
lc=(BinNode*)a;}
inline BinNode* right()
{return rc;}
void setRight(BinNode* a)
{rc=(BinNode*)a;}
bool isleaf()//判断是否是叶接点
{return (lc==NULL)&&(rc==NULL);}
};
class idKEComp {//判断坐标的大小
public:
static bool lt(const Cityset& k,Cityset& e)
{return (k.id.y<e.id.y)&&(k.id.x<e.id.x) ;}
static bool eq(const Cityset& k,Cityset& e)
{return (k.id.y==e.id.y)&&(k.id.x==e.id.x);}
static bool gt(const Cityset& k,Cityset& e)
{return (k.id.y>e.id.y)&&(k.id.x>e.id.x);}
};
class NameKEComp {//比较名字的大小
public:
static bool lt(const Cityset& k,Cityset& e)
{return strcmp(k.name,e.name)<0;}
static bool eq(const Cityset& k,Cityset& e)
{return strcmp(k.name,e.name)==0;}
static bool gt(const Cityset& k,Cityset& e)
{return strcmp(k.name,e.name)>0;}
};
class BST//二叉查找树类的定义
{ friend istream & operator >>( istream &input, Cityset C);
friend ostream & operator <<( ostream &output, const Cityset C);
private:
BinNode *root;
int nodecout;
void clearhelp(BinNode*);//清空
//void inOrderHelper(BinNode *)const;
BinNode* inserthelp(BinNode* ,const Cityset&);//插入
BinNode* deletemin(BinNode*,BinNode*&);//删除最小元素
BinNode* removehelp(BinNode*,const Cityset&,BinNode*&);//删除
bool findhelp(BinNode*,const Cityset&,Cityset&) const;//寻找
void printhelp(BinNode*,int) const;//打印
public:
BinNode *g()
{return root;}
BST()
{root=NULL;nodecout=0;}
~BST()
{clearhelp(root);}
//void inOrderTraversal() const;
void clear()
{clearhelp(root);
root=NULL;nodecout=0;}
bool insert(const Cityset& e){
root=inserthelp(root,e);
nodecout++;
return true;
}
bool remove(const Cityset& k,Cityset& e)
{BinNode* t=NULL;
root=removehelp(root,k,t);
if(t==NULL)
return false;
e=t->val();
nodecout--;
delete t;
return true;
}
bool find(const Cityset& k,Cityset& e) const
{return findhelp(root,k,e);}
int size() {return nodecout;}
void print() const{
if(root==NULL) cout<<"the BST is empty.\n";
else printhelp(root,0);
}
};
istream & operator >>( istream &input, Cityset C)//
{
input>>C.name>>C.id.x>>C.id.y; return input;}
ostream & operator <<( ostream &output, const Cityset C)
{
output<<C.name<<C.id.x<<C.id.y; return output;}
bool BST::findhelp(BinNode* subroot ,const Cityset& k,Cityset& e) const{
if(subroot==NULL)
return false;
else if(NameKEComp::lt(k,subroot->val()))
return findhelp(subroot->left(),k,e);
else if(NameKEComp::gt(k,subroot->val()))
return findhelp(subroot->right(),k,e);
else {
e=subroot->val(); return true;}
}
/*void BST::inOrderTraversal() const
{
inOrderHelper( root );
} // end function inOrderTraversal
// utility function to perform inorder traversal of Tree
void BST::inOrderHelper(
BinNode *ptr ) const
{
if ( ptr != 0 ) {
inOrderHelper( ptr->left() ); // go to left subtree
cout << ptr->val() << ' '; // process node
inOrderHelper( ptr->right() ); // go to right subtree
} */
BinNode* BST::deletemin(BinNode* subroot,BinNode*& min){
if(subroot->left()==NULL){
min=subroot; return subroot->right();}
else{
subroot->setLeft(deletemin(subroot->left(),min));
return subroot;
}
}
void BST::clearhelp(BinNode* subroot){
if(subroot==NULL)
return;
clearhelp(subroot->left());
clearhelp(subroot->right());
delete subroot;
}
BinNode* BST::removehelp(BinNode* subroot,const Cityset& k,BinNode*& e){
if(subroot==NULL)
return NULL;
else if(idKEComp::lt(k,subroot->val())||NameKEComp::lt(k,subroot->val()))
subroot->setLeft(removehelp(subroot->left(),k,e));
else if(idKEComp::gt(k,subroot->val())||NameKEComp::gt(k,subroot->val()))
subroot->setRight(removehelp(subroot->left(),k,e));
else
{BinNode* temp;
e=subroot;
if(subroot->left()==NULL)
subroot=subroot->right();
else if(subroot->right()==NULL)
subroot=subroot->left();
else {
subroot->setRight(deletemin(subroot->right(),temp));
Cityset te=subroot->val();
subroot->setVal(temp->val());
temp->setVal(te);
e=temp;
}
}
return subroot;
}
BinNode* BST::inserthelp(BinNode* k,const Cityset& e)
{if(k==NULL)
{root=(BinNode*)malloc(sizeof(BinNode));
//k=new BinNode(e);
if(k==NULL){cout<<"out of space"<<endl;
exit(1);
}
}
else if(NameKEComp::lt(e,k->val()))
inserthelp(k->left(),e);
else if(NameKEComp::gt(e,k->val()))
inserthelp(k->right(),e);
return k;}
void BST::printhelp(BinNode* subroot,int level) const{
if(subroot==NULL)return;
printhelp(subroot->left(),level+1);
for(int i=0;i<level;i++)
cout<<" ";
cout<<subroot->val()<<"\n";
printhelp(subroot->right(),level+1);}
void main()
{BST dyz_citymap;
//cout<<"输入你所建城市的信息：";
Cityset city_1,city_2;
city_1.name="s";city_1.id.x=1;city_1.id.y=1;
//cin>>city_1.name>>city_1.id.x>>city_1.id.y;
dyz_citymap.insert(city_1);
dyz_citymap.print( );
/*cin>>city_2.name>>city_2.id.x>>city_2.id.y;
dyz_citymap.insert(city_2);
cout<<(dyz_citymap.g())->it.name<<(dyz_citymap.g())->it.id.x<<(dyz_citymap.g())->it.id.y;*/
}
/*int main(){
BST bst;
char E[20];
char name[20];
cout<<"十个城市:\n";
bst.insert("beijing");
bst.insert("hanzhou");
bst.insert("tianjing");
bst.insert("nanjing");
bst.insert("wuhan");
bst.insert("guangzhou");
bst.insert("shenzhen");
bst.insert("hangzhou");
bst.insert("haerbing");
bst.insert("yunnan");
bst.print();
cout<<endl;
cout<<"找到和北京相距在30之内的城市\n";
bst.findval("beijing",30.0);
cout<<"删除一个城市\n";
cin>>name;
bst.remove(name,E);
bst.print();
cout<<endl;
cout<<"删除最小城市名\n";
bst.removeany(E);
bst.print();
cout<<endl;
cout<<"查找一个城市的坐标"<< endl;
cin>>name;
bst.find(name,E);
return 0;
}*/
刚开C++和数据结构的课老师就要我们做这么复杂的问题
好不容易编译通过了
却始终运行不成功
我查了一个多星期都没发现
找同学也无能为力
已超过一天的上缴期限
无奈才向大家求助
同时也希望能作个朋友
我的邮箱:dyz_1984@126.com
