C++ | 实现城市数据库

日期:2017-11-5  小东  技术教程   热度:80830℃

【摘要】实验内容：利用BST实现一个城市数据库：每个数据库结点包括城市名称和以整数x与y表示的城市坐标。根据城市名称组织该BST；在该数据库上实现按城市名称进行的插入、删除和检索；&...

实验内容：
    利用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++ | 实现城市数据库
标签: 玩转代码

 小东
 简介：专业团队网站开发、安全运维，合作意向请联系！

相关推荐:

扫码关注微信公众号：ITDYBOY，学前端，学安全，从0到1，从1到精通！

扫码关注微信公众号：ITDYBOY

发表评论

游客
送你一朵小花花~

帅人已评（8）