Binary Trees and Hash Tables
Please send photos/screenshots of output from the command prompt along with the other files.
1)
Write a program in C++ that:
- accepts an unlimited number of strings (none of which will contain spaces)
typed by the user
- adds those strings, as they are typed, into an initially empty binary tree
The order of the tree is alphabetical, and case INsensitive, so cat and CAT
are the same string, and ant comes before Zebra.
- when the user signals that the data entry phase is over, the program must then
accept another unlimited sequence of strings from the user
- when each string is typed, the program searches the tree for it, and prints
“yes” if it is present, or “no” if it isn’t.
2)
Hash Table of all Named Places
Using the data file linked to in class 4’s notes,
http://rabbit.eng.miami.edu/class/een318/named-places.txt
which can be accessed directly as a file on rabbit
/home/www/class/een318/named-places.txt,
Write a program that reads the entire file, creating a separate struct/classfor each entry. The struct should contain separate members for the:
+ state abbreviation (string)
+ place name (string)
+ population (int)
+ area (float or double)
+ latitude (float or double)
+ longitude (float or double)
+ representative intersection (int)
+ distance to intersection (float or double)
For THIS assignment, destructors are not expected and not recommended.
Numeric values should be stored as the appropriate C++ types, not strings.
Place names should be trimmed so that they have no spaces AT THE END.
Store all of these objects in a Hash Table.
The hash table must be structured to give fast search based on place name.
(Notice that place names are not unique. For example, there is an Aberdeen
in Idaho, Maryland, Missouri, North Carolina, Ohio, South Dakota, and
Washington)
After reading all the data, your program must interact with the user like this:
Step 1: Invite the user to type a place name,
Step 2: List all the states that contain a place with that name,
Step 3: Invite the user to type one of those states,
Step 4: Print all known information about the selected place.
Detect user input errors,
Be ready for names that contain spaces.
Example run: This is just an illustration, you don’t need to duplicate it exactly.
Enter a place name: Aberdeen
Select from ID, MD, MS, NC, OH, SD, WA: NC
Aberdeen, NC
Population 3400
Area 6.164109
Latitude 35.138494 N
Longitude 79.427701 W
Intersection 19565
Distance 0.6712
Enter a place name: Aberdeen
Select from ID, MD, MS, NC, OH, SD, WA: PR
There is no Aberdeen in PR
Enter a place name: Trumptown
No such place
Enter a place name: New York
Select from NY: NY
Population 8008278
Area 303.310732
Latitude 40.704234 N
Longitude 73.917927 W
Intersection 6792
Distance 1.5444
Enter a place name: ^C
Solution
ConsoleApplication2.cpp
// ConsoleApplication2.cpp : Defines the entry point for the console application.
//
#include “stdafx.h”
#include <iostream>
#include<fstream>
#include <cstdio>
#include<sstream>
#include <map>
using namespace std;
int main()
{
ifstream file;
file.open(“named-places.txt”);
string s=”hello world”;
//cout << s.substr(0,7) << endl;
cout << “starting program…location data is loading please wait…” << endl;
//getline(file, s);
multimap<string, Node*>* map = new multimap<string,Node*>();
while (getline(file, s)) {
stringstream ss(s);
string word;
string s1;
string s2;
string s3;
string s4;
string s5;
string s6;
string s7;
Node* node = new Node();
int i = 0;
//cout << “here” << endl;
while (!ss.eof()) {
ss >> word;
//cout << word << endl;
if (i == 0) {
s1 = word;
i++;
}
else if (i == 1) {
if (isDigit(word[0])) {
i++;
s2 = word;
}
else {
s1 += ” ” + word;
}
}
else if (i == 2) {
s3 = word;
i++;
}
else if (i == 3) {
if (word.length() > 9) {
s4 = word.substr(0, 10);
s5 = word.substr(10);
i += 2;
}
else {
i++;
s4 = word;
}
}
else if (i == 4) {
if(word.length() > 10) {
s5 = word.substr(0, 11);
s6 = word.substr(11);
i += 2;
}
else {
i++;
s5 = word;
}
}
else if(i==5) {
i++;
s6 = word;
s7 = “”;
}
else {
s7 = word;
break;
}
}
//cout << s7 << endl;
//cout << s1 << ” ” << s2 << ” ” << s3 << ” ” << s4 << ” ” << s5 << ” ” << s6 << ” ” << s7 << endl;
//cout << “here77” << endl;
//cout << s7 << endl;
if (s7 == “”) {
//cout << “here7788” << endl;
s7 = s6.substr(3);
s6 = s6.substr(0, 3);
}
//cout << “here” << endl;
//cout << s1 << ” ” << s2 << ” ” << s3 << ” ” << s4 << ” ” << s5 << ” ” << s6 << ” ” << s7 << endl;
//cout << “here” << endl;
node->place = s1.substr(10);
node->state = s1.substr(8, 2);
stringstream ss1(s2);
int p;
ss1 >> p;
node->population = p;
stringstream ss2(s3);
float f1;
ss2 >> f1;
node->area = f1;
stringstream ss3(s4);
float f2;
ss3 >> f2;
node->lat = f2;
stringstream ss4(s5);
float f3;
ss4 >> f3;
node->lon = f3;
stringstream ss5(s6);
int p1;
ss5 >> p1;
node->repInt = p1;
stringstream ss6(s7);
float f4;
ss6 >> f4;
node->dist = f4;
//printf(“%s %s %d %f %f %f %d %f\n”, node->place.c_str(),node->state.c_str(),node->population,node->area,node->lat,node->lon,node->repInt,node->dist);
pair<string, Node*> pa;
pa.first = node->place;
pa.second = node;
map->insert(pa);
}
cout << “the location data has been loaded. size : ” <<map->size() << endl;
/*int count = 0;
for (multimap<string, Node*>::iterator i = map->begin(); i != map->end();i++) {
Node* n = i->second;
cout << n->place << ” ” << n->state << ” ” << n->population << endl;
count++;
if (count > 20)break;
}*/
string ser;
cout << “please enter the place you want to search or enter \”exit\” to exit” << endl;
cout << “warning: search is case sensitive” << endl;
cin >> ser;
while (ser != “exit”) {
cout << “searching for : ” << ser << endl;
if (map->find(ser) == map->end()) {
cout << ser << ” was not found” << endl;
}
else {
//cout << map->count(ser) << endl;
cout << “select from : “;
for (multimap<string, Node*>::iterator it = map->find(ser); it->first==ser ; it++) {
cout << it->second->state << “,”;
}
cout << endl;
string st;
cin >> st;
for (multimap<string, Node*>::iterator it = map->find(ser); it->first == ser; it++) {
if (it->second->state==st) {
Node* no = it->second;
cout << no->place << “,” << no->state << endl;
cout << “Population : “<<no->population<<endl;
cout << “Area : ” << no->area<<endl;
cout << “Latitude : ” << no->lat<<endl;
cout << “Longitude : ” << no->lon<<endl;
cout << “Intersection : ” << no->repInt << endl;
cout << “Distance : “<<no->dist;
break;
}
}
}
cout << “please enter the place you want to search or enter \”exit\” to exit” << endl;
cin >> ser;
}
return 0;
}
stdafx.cpp
// stdafx.cpp : source file that includes just the standard includes
// ConsoleApplication2.pch will be the pre-compiled header
// stdafx.obj will contain the pre-compiled type information
#include “stdafx.h”
// TODO: reference any additional headers you need in STDAFX.H
// and not in this file
bool isDigit(char c) {
return(‘0’ <= c && c <= ‘9’);
}
stdafx.h
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//
#pragma once
#include “targetver.h”
#include <string>
#include <stdio.h>
#include <tchar.h>
using namespace std;
class Node {
public:
string place;
string state;
int population;
float area;
float lat;
float lon;
int repInt;
float dist;
};
bool isDigit(char c);
// TODO: reference additional headers your program requires here
targetver.h
#pragma once
// Including SDKDDKVer.h defines the highest available Windows platform.
// If you wish to build your application for a previous Windows platform, include WinSDKVer.h and
// set the _WIN32_WINNT macro to the platform you wish to support before including SDKDDKVer.h.
#include <SDKDDKVer.h>
stringTree.cpp
#include <iostream>
#include<bits/stdc++.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef struct node
{
string key;
node * left;
node * right;
}node;
// A utility function to create a new BST node
bool search(struct node* root, string key)
{
// Base Cases: root is null or key is present at root
if (root == NULL )
return false;
if(root->key==key){
return true;
}
// Key is greater than root’s key
if (root->key < key)
return search(root->right, key);
// Key is smaller than root’s key
return search(root->left, key);
}
void printPreOrder(node* root){
if(root!=NULL){
cout<<root->key<<endl;
printPreOrder(root->left);
printPreOrder(root->right);
}
}
/* A utility function to insert a new node with given key in BST */
node * addNode(string value){
struct node * temp = new node;
//cout<<“here”<<endl;
temp->key = value;
temp->left = NULL;
temp -> right = NULL;
//cout<<“here1″<<endl;
return temp;
}
node * insert(node * root, string value)
{
node * ptr = root;
if(ptr == NULL)
return addNode(value);
else if(ptr -> key > value){
ptr->left = insert(ptr -> left, value);
}
else if(ptr -> key < value){
ptr->right = insert(ptr -> right, value);
}
return root;
}
int main() {
cout<<“Welcome to the program”<<endl;
cout<<“Enter the strings you want to insert into the tree”<<endl;
cout<<” or Enter \”stop\” to stop the insertion”<<endl;
string inp;
cin>> inp;
transform(inp.begin(), inp.end(), inp.begin(), ::tolower);
struct node *root = NULL;
while(inp!=”stop”){
root = insert(root, inp);
cout<<“Insert String/ \”stop\””<<endl;
cin>> inp;
transform(inp.begin(), inp.end(), inp.begin(), ::tolower);
}
cout<<“input stopped”<<endl;
cout<<“enter string to search or \”stop\” to stop searching”<<endl;
cin>> inp;
transform(inp.begin(), inp.end(), inp.begin(), ::tolower);
while(inp!=”stop”){
if(search(root,inp)){
cout<<“yes”<<endl;
}
else{
cout<<“no”<<endl;
}
cin>> inp;
transform(inp.begin(), inp.end(), inp.begin(), ::tolower);
}
printPreOrder(root);
return 0;
}