[C++]实现城市数据库管理

这是小东的实验作业,觉得还有点意思,就分享给大家瞅瞅

实验内容:

利用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;
}

总结

仅作为参考,大家吐槽轻点…

发表评论 / Comment

用心评论~

金玉良言 / Appraise
QnnerLV 1
2018-12-03 10:42
感谢学长提供的代码
233sclLV 1
2018-12-01 13:44
感谢学长提供示例代码