这是小东的实验作业,觉得还有点意思,就分享给大家瞅瞅
实验内容:
利用BST实现一个城市数据库:每个数据库结点包括城市名称和以整数x与y表示的城市坐标。根据城市名称组织该BST;
在该数据库上实现按城市名称进行的插入、删除和检索;
打印出以指定字母打头的所有城市记录;
打印出与指定点的距离在给定值之内的所有城市记录;
最后提交完整的实验报告和源程序
实现代码:
/* * title: City database * author: DYBOY * time: 2017-11-05 * description: nothing... ***/ #include <iostream> #include <string> #include <cmath> #include <iomanip> using namespace std; class City{ //The class describe the name and coordinate,function:getKey(),==,print(),printWithoutPoint(),>> public: string name; //city's name int x,y; //the coordinate x & y City(){ name = ""; } City(string name,int x,int y):name(name),x(x),y(y){} ~City(){} string& getKey(){ return name; } //key==name bool operator==(City&c){ return this->name == c.name; } //if name is same void print(){ cout<<name<<" ("<<x<<", "<<y<<")"<<endl; } //print the name and coordinate void printWithoutPoint(){ cout<<name<<endl; } //just print the name friend istream& operator >> (istream &in, City &obj); //>> overloaded input }; istream& operator >> (istream& input, City& obj){ //friend cout<<"Please input the city's name and coordinate\n"<<endl; input>>obj.name>>obj.x>>obj.y; //name,point return input; } class CityNode{ //City Node private: string key; //key City value; //value CityNode *ln; //left node pointer CityNode *rn; //right node pointer public: CityNode(){ this->ln=this->rn=NULL;this->value=City(); } CityNode(string key,City value,CityNode *ln=NULL,CityNode *rn=NULL):key(key),value(value),ln(ln),rn(rn){} ~CityNode(){} City& getValue(){ return this->value;} //return value void setValue(City& value){ this->value=value; } //... string getKey(){ return key; } //return key void setKey(string key){ this->key=key; } //... CityNode* left(){ return ln; } //return left void setLeft(CityNode* ln){ this->ln=ln; } //... CityNode* right(){ return rn; } //return right void setRight(CityNode* rn){ this->rn=rn; } //... }; //City Tree class CityTree{ private: CityNode* inserthelp(CityNode*,string&,City&); //key valve CityNode* removehelp(CityNode*,string&,City&); CityNode* getmin(CityNode*); CityNode* deletemin(CityNode*); City& findhelp(CityNode*,string&,City&); void findhelpAll(CityNode*,char&); void findInDistanceHelp(CityNode*,int,int,int); void printhelp(CityNode*); void clearhelp(CityNode*); public: CityNode* root; int size; CityTree(){ root = NULL;size = 0; } ~CityTree(){ clearhelp(root); } void insert(string& key,City& value){ root=inserthelp(root,key,value);size++; } void findAll(char key){ findhelpAll(root,key); } void findInDistance(int x,int y,int d){ findInDistanceHelp(root,x,y,d); } City& remove(string key,City& value){ //remove City temp = findhelp(root,key,value); if(temp.name != ""){ root = removehelp(root,key,value);size--; } return temp; } void print(){ if (root == NULL) cout<<"The city does't exist!' "<<endl; else printhelp(root); } }; void CityTree::printhelp(CityNode *root) { if(root == NULL) return; //if root is null printhelp(root->left()); //find the left root->getValue().printWithoutPoint(); printhelp(root->right()); } CityNode* CityTree::getmin(CityNode *root) { //find the minnode if(root->left() == NULL) return root; else return getmin(root->left()); } CityNode* CityTree::deletemin(CityNode *root) { //delete the minnode if(root->left() == NULL) return root->right(); else root->setLeft(deletemin(root->left())); return root; } CityNode* CityTree::removehelp(CityNode *root, string &key, City &value) { //removehelp if(root == NULL) return NULL; else if(key<root->getKey()) root->setLeft(removehelp(root->left(),key,value)); else if(key>root->getKey()) root->setRight(removehelp(root->right(),key,value)); else{ if(value==root->getValue()){ CityNode* temp=root; if(root->left()==NULL){ root=root->right(); delete temp; }else if(root->right()==NULL){ root=root->left(); delete temp; }else{ CityNode* t=getmin(root->right()); root->setValue(t->getValue()); root->setKey(t->getKey()); root->setRight(deletemin(root->right())); delete t; } } } return root; } City& CityTree::findhelp(CityNode*root,string&key,City&value){ //findhelp if(root==NULL){ City temp=City();return temp; } if(key<root->getKey()) return findhelp(root->left(),key,value); else if(key>root->getKey()) return findhelp(root->right(),key,value); else{ return root->getValue(); } } void CityTree::findhelpAll(CityNode*root,char&key) { //find all if(root==NULL){ return; } if(key<root->getValue().name[0]) findhelpAll(root->left(),key); else if(key>root->getValue().name[0]) findhelpAll(root->right(),key); else{ findhelpAll(root->left(),key); root->getValue().print(); findhelpAll(root->right(),key); } } void CityTree::findInDistanceHelp(CityNode *root, int x, int y, int d) { //find distance if(root==NULL) return; findInDistanceHelp(root->left(),x,y,d); City city=root->getValue(); float distance=sqrtf((city.x-x)*(city.x-x)+(city.y-y)*(city.y-y)); if(distance<=(float)d) city.print(); findInDistanceHelp(root->right(),x,y,d); } CityNode* CityTree::inserthelp(CityNode *root, string &key, City &value) { //indert if(root==NULL) return new CityNode(key,value); if(key<root->getKey()) root->setLeft(inserthelp(root->left(),key,value)); else root->setRight(inserthelp(root->right(),key,value)); return root; } void CityTree::clearhelp(CityNode *root) { //clear if(root==NULL) return; clearhelp(root->left()); clearhelp(root->right()); delete root; } //main int main() { CityTree tree=CityTree(); int size; cout<<"Please input the data's number:"; cin>>size; cout<<"The you need to input the citys' detail data,include name,x,y:"; for(int i=0;i<size;i++){ City temp=City(); cin>>temp; tree.insert(temp.getKey(),temp); } int code; cout<<"************************************************************"<<endl; cout<<"Now you can input the 0,1,2 to operate the database:"<<endl; cout<<"0.delete"<<endl; cout<<"1.insert"<<endl; cout<<"2.end insert or end delete"<<endl; cout<<"************************************************************"<<endl; while(cin>>code&&code !=2){ if(code==0){ string name; cin>>name; City t=City(name,0,0); tree.remove(t.getKey(),t); cout<<"delete it success!"; }else if(code==1){ City t; cin>>t; tree.insert(t.getKey(),t); cout<<"insert success!"; } } tree.print(); char key; cout<<"Please input the city's first letter,it will search the city:"; cin>>key; tree.findAll(key); int x,y,d; cout<<"\nPlease input the coordinate x,y and distance,it will find the citys' distance around the coordinate:"; cin>>x>>y>>d; tree.findInDistance(x,y,d); return 0; }
总结
仅作为参考,大家吐槽轻点…
版权声明:《 [C++]实现城市数据库管理 》为DYBOY原创文章,转载请注明出处!
最后编辑:2018-6-13 21:06:03
2018-12-03 10:42
2018-12-01 13:44