Create the same City Database that you created in the first question using Hash table. Add another attribute in the City record, that is, city_id. Use city_id to compute the hashing. Implment member functions to insert, delete, search and display city records. Use the chained hashing to resolve the collision issue. ------------------------------------------------------------------------- so here is my out put from the first question #include #include #include using namespace std; struct city{ string name; int x; int y; city *left; city *right; bool deleted; }; class database{ private: city *root; void insert(city *&temp, string name, int x, int y){ if(temp == NULL){ temp = new city(); temp->name = name; temp->x = x; temp->y = y; temp->left = NULL; temp->right = NULL; temp->deleted = false; } else{ if(name < temp->name){ insert(temp->left, name, x, y); } else if(name > temp->name){ insert(temp->right, name, x, y); } else{ if(temp->deleted == true){ temp->deleted = false; temp->x = x; temp->y = y; } else{ insert(temp->right, name, x, y); } } } } city *findByName(city *temp, string name){ if(temp != NULL){ if(temp->name == name) return (temp->deleted == false ? temp : findByName(temp->right, name)); else if(name < temp->name) return findByName(temp->left, name); else if(name > temp->name) return findByName(temp->right, name); } else{ return NULL; } } city *findByCoordinates(city *temp, int x, int y){ if(temp == NULL){ return NULL; } else{ city *ret = NULL; if(temp->x == x && temp->y == y){ if(temp->deleted == false){ ret = temp; } } if(ret == NULL){ ret = findByCoordinates(temp->left, x, y); } if(ret == NULL){ ret = findByCoordinates(temp->right, x, y); } return ret; } } void print(city *temp, int x, int y, double d){ if(temp != NULL){ print(temp->left, x, y, d); if(temp->deleted == false){ double distance = sqrt(pow(temp->x - x, 2) + pow(temp->y - y, 2)); if(distance < d){ cout << temp->name << " at (" << temp->x << ", " << temp->y << ")" << endl; } } print(temp->right, x, y, d); } } public: database(){ root = NULL; } void insertCity(string name, int x, int y){ insert(root, name, x, y); } void searchByName(string name){ city *found = findByName(root, name); if(found == NULL){ cout << "City not found" << endl; } else{ cout << "City " << found->name << " found at (" << found->x << ", " << found->y << ")" << endl; } } void searchByCoordinates(int x, int y){ city *found = findByCoordinates(root, x, y); if(found == NULL){ cout << "City not found" << endl; } else{ cout << "City " << found->name << " found at (" << found->x << ", " << found->y << ")" << endl; } } void deleteByName(string name){ city *found = findByName(root, name); if(found == NULL){ cout << "City not found" << endl; } else{ cout << "City " << found->name << " found at (" << found->x << ", " << found->y << ") has been deleted" << endl; found->deleted = true; } } void deleteByCoordinates(int x, int y){ city *found = findByCoordinates(root, x, y); if(found == NULL){ cout << "City not found" << endl; } else{ cout << "City " << found->name << " found at (" << found->x << ", " << found->y << ") has been deleted" << endl; found->deleted = true; } } void printInDistance(int x, int y, double d){ print(root, x, y, d); } }; int main(){ database db; db.insertCity("city2", 1, 1); db.insertCity("city1", 2, 3); db.insertCity("city3", 1, 3); db.printInDistance(0, 0, 10); return 0; }
Create the same City
-------------------------------------------------------------------------
so here is my out put from the first question
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
struct city{
string name;
int x;
int y;
city *left;
city *right;
bool deleted;
};
class database{
private:
city *root;
void insert(city *&temp, string name, int x, int y){
if(temp == NULL){
temp = new city();
temp->name = name;
temp->x = x;
temp->y = y;
temp->left = NULL;
temp->right = NULL;
temp->deleted = false;
}
else{
if(name < temp->name){
insert(temp->left, name, x, y);
}
else if(name > temp->name){
insert(temp->right, name, x, y);
}
else{
if(temp->deleted == true){
temp->deleted = false;
temp->x = x;
temp->y = y;
}
else{
insert(temp->right, name, x, y);
}
}
}
}
city *findByName(city *temp, string name){
if(temp != NULL){
if(temp->name == name) return (temp->deleted == false ? temp : findByName(temp->right, name));
else if(name < temp->name) return findByName(temp->left, name);
else if(name > temp->name) return findByName(temp->right, name);
}
else{
return NULL;
}
}
city *findByCoordinates(city *temp, int x, int y){
if(temp == NULL){
return NULL;
}
else{
city *ret = NULL;
if(temp->x == x && temp->y == y){
if(temp->deleted == false){
ret = temp;
}
}
if(ret == NULL){
ret = findByCoordinates(temp->left, x, y);
}
if(ret == NULL){
ret = findByCoordinates(temp->right, x, y);
}
return ret;
}
}
void print(city *temp, int x, int y, double d){
if(temp != NULL){
print(temp->left, x, y, d);
if(temp->deleted == false){
double distance = sqrt(pow(temp->x - x, 2) + pow(temp->y - y, 2));
if(distance < d){
cout << temp->name << " at (" << temp->x << ", " << temp->y << ")" << endl;
}
}
print(temp->right, x, y, d);
}
}
public:
database(){
root = NULL;
}
void insertCity(string name, int x, int y){
insert(root, name, x, y);
}
void searchByName(string name){
city *found = findByName(root, name);
if(found == NULL){
cout << "City not found" << endl;
}
else{
cout << "City " << found->name << " found at (" << found->x << ", " << found->y << ")" << endl;
}
}
void searchByCoordinates(int x, int y){
city *found = findByCoordinates(root, x, y);
if(found == NULL){
cout << "City not found" << endl;
}
else{
cout << "City " << found->name << " found at (" << found->x << ", " << found->y << ")" << endl;
}
}
void deleteByName(string name){
city *found = findByName(root, name);
if(found == NULL){
cout << "City not found" << endl;
}
else{
cout << "City " << found->name << " found at (" << found->x << ", " << found->y << ") has been deleted" << endl;
found->deleted = true;
}
}
void deleteByCoordinates(int x, int y){
city *found = findByCoordinates(root, x, y);
if(found == NULL){
cout << "City not found" << endl;
}
else{
cout << "City " << found->name << " found at (" << found->x << ", " << found->y << ") has been deleted" << endl;
found->deleted = true;
}
}
void printInDistance(int x, int y, double d){
print(root, x, y, d);
}
};
int main(){
database db;
db.insertCity("city2", 1, 1);
db.insertCity("city1", 2, 3);
db.insertCity("city3", 1, 3);
db.printInDistance(0, 0, 10);
return 0;
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
