Macomb Community College C++ CPP Data Structure and Design Programming Task

Please use the code I provided

This pic above is part of the ft_chicago.csv

The supplied input file in this module – ft_chicago.csv – contains approx. 300 entries of name and location information for food trucks throughout Chicago (this comes from the public data site here (Links to an external site.)). This is another CSV file similar to what we used in Lab #7. Here are the details:

• Each line contains info about a single food truck.
• The first line is a header and contains the column names.
• Each line has 3 comma-separated fields, in this order:
  • business_name – the name under which the truck is doing business
  • zip – the zip code where the truck operates
  • license_description – the type of license, either “Mobile Food Dispenser” or “Mobile Food License”.
• There is a header line which indicates the 3 columns in the file. Each line of the file represents a “row” and has a value for each of these columns.
• You can assume the business_name field of each entry is unique in the file (this will be important for your hash function), but this may not be true of the other fields. All of the fields may include spaces and punctuation.

Assignment

Write a program that implements a hash table using any of the methods described in Chapter 18 or the class videos or slides. You are free to use any hash function and any method you choose to handle hash collisions. A good place to start for a hash key is to use something about the business_name — the first character? the last character? the first three characters? (these will all work, but none are a very good choice!). To handle collisions, you could chain them with a linked list on each “bucket”, or use open addressing with linear probing, for example.

A starter file — chicago_foodtruck_starter.cpp — is provided. This file implements the framework for the hash table and reading of the file. Some functions are marked for your implementation (such as find() and insert()). You do not need to use this file, or you can use any part of it or modify it as needed.

Requirements

The program should ask for a business name, and output the business_name, zip, and license_description fields for that entry after finding it in the hash. Here are the other requirements:

• Loop until an exit is requested (blank name, -1, etc.).
• Use a case-sensitive search (assume queries are for the exact case in the file, no need to convert strings).
• Your program only needs to implement the “add” and “lookup” functionality, not deletes or rehashing/resizing of the table.
• If the business name is not found, output “Not found in the table” or similar.
• This time, do not use any STL or any third-party libraries (for example, a Map) to implement the hash — it must be a hash of your own creation.
• Do not use any hard-coded values, i.e. fixed strings that return responses to fixed questions. The program must be able to retrieve any of the keys available in the file.
• Each entry should be hashed (some key generated, based in something about the record) i.e. do not just read the data into an array or some other fixed structure.
• To test the performance of your hash function, your program should output the number of comparisons for each successful or failed lookup.

See if you can bring down the number of comparisons from your first attempt. A little Google searching will yield some string-optimized hash functions. There is no “right” answer, but hash functions that perform very poorly (close to a linear search) will lose points.

Assuming your table size is 49 (the value in the starter file) successful queries should generally be in the range of 1-7. If your numbers are consistently higher, try using a different hash function. Be sure to test both the unsuccessful and successful query cases.

Example Output

Read 290 food trucks.Enter a business name (<return> to quit): Teriyaki BowlComparisons: 2Business name: Teriyaki BowlZIP: 60612License type: Mobile Food LicenseEnter a business name (<return> to quit): The RoostComparisons: 1Business name: The RoostZIP: 60614License type: Mobile Food LicenseEnter a business name (<return> to quit): Piko Street KitchenComparisons: 5Business name: Piko Street KitchenZIP: 60193License type: Mobile Food LicenseEnter a business name (<return> to quit): Big Kahuna BurgerNot found in the database.Comparisons: 5Enter a business name (<return> to quit):Exiting...

A starter file — chicago_foodtruck_starter.cpp — is provided.

This file implements the framework for the hash table and reading of the file. Some functions are marked for your implementation (such as find() and insert()). You do not need to use this file, or you can use any part of it or modify it as needed.

#include <iostream>
#include <sstream>
#include <fstream>
#include <cstdlib>
#include <iomanip>
using namespace std;

//
// This is a starter file to help frame your ideas around
// Lab #9. The reading of each line in the file is completed
// for you.
//

const string FILENAME = “ft_chicago.csv”; // Input file (CSV)
const int NFIELDS = 3; // Number of fields in
// each line of the input file

// This holds a single food truck entry. Each line in the file should
// correspond to one of these.
typedef struct _foodtruck {
string business_name;
string zip;
string license_type;
} foodtruck;

// Starting size, adjust as needed — should be prime.
// This strikes a good balance without having too many empty buckets.
const int HASH_SIZE = 53;

// Hash table for all of the food trucks — static so it’s zeroed
static foodtruck *truckHash[HASH_SIZE];

// Reads a single truck, filling in the
// fields (name, etc.) passed by the caller.
void readSingleTruck(const string &str,
foodtruck *newFT) {
istringstream istr(str);
string fields[NFIELDS];
string tmp;
int i = 0;

while (getline(istr, tmp, ‘,’) && i < NFIELDS) {
fields[i++] = tmp;
}

// Fill in the newly allocated entry.
// A pointer to it was passed to us.
newFT->business_name = fields[0];
newFT->zip = fields[1];
newFT->license_type = fields[2];
}

// Generate a hash key, given a string (this would come from the
// string the user typed to find). your hash function goes here.
//
// Don’t use this one, it performs poorly!
unsigned int genHashKey(string key) {
unsigned int sum = 0;

// use the first letter of the key
sum = (int)key[0];

// for debugging — add a statement like this to
// see the hash key generated for an entry.
//
// cout << “name: ” << key
// << ” hash key: ” << sum % hash_size << endl;

return (sum % HASH_SIZE);
}

// Insert a new truck into the hash table
void truckInsert(foodtruck *newFT) {

//
// Implement this function.
//
// (These are example parameters)
//
// Accepts a new food truck entry, finds the location in the
// hash table where it should go, and inserts.
//
}

// This function accepts a string name and a reference
// to an empty foodtruck.
//
// Upon return,
// – ‘foundFT’ will be filled-in with what was found.
// – The function will return ‘true’ if something was found, ‘false’ otherwise.
//
bool truckFind(const string &name, foodtruck &foundFT, int &ncmp) {
int key = genHashKey(name);

//
// Implement this function.
//
// (These are example parameters)
//
//
// Accepts a key, a reference to a found entry, and reference to
// number of comparisons. Fill-in the values of the ‘foundFT’ with
// the values from the entry found in the hash table.
//

}

int main() {
ifstream inFile(FILENAME);
string inputLine, inputStr;
int linesRead = 0;

// Discard the first header line
getline(inFile, inputLine);

// Read in each food truck entry
while (getline(inFile, inputLine)) {

// Dynamically allocate a new struct
foodtruck *ftptr = new foodtruck;

// Read the next line from the file,
// filling in the new truck
// just allocated.
readSingleTruck(inputLine, ftptr);

// Hash it and insert into the table where needed.
truckInsert(ftptr);

// Keep a counter of read lines.
linesRead++;

// (for debugging)
// Output the number of lines read every so often.
// if (linesRead % 25 == 0)
// cout << “Inserted ” << linesRead << ” entries”
// << endl;
}

// Handle errors and/or summarize the read
if (linesRead == 0) {
cerr << “Read failed.” << endl;
return (-1);
} else {
cout << “Read ” << linesRead << ” food trucks.” << endl;
cout << fixed << setprecision(2) << endl;
}

// (example) Forever loop until the user requests an exit
for (;;) {
//
// Your input loop goes here.
//
}
return (0);
}