Question
IN C++ FORMAT PLEASE: INCLUDE COMMENTS NEXT TO THE IMPLEMENTED CODES YOU WRITE 1. Copy and paste the following code into a header file named
IN C++ FORMAT PLEASE: INCLUDE COMMENTS NEXT TO THE IMPLEMENTED CODES YOU WRITE
1. Copy and paste the following code into a header file named HashTable.h
2. Please do not alter this file in any way or you may not receive credit for this lab
3. implement each of the hash table functions whose prototypes are in HashTable.h.
4. Write these functions in a file named HashTable.cpp.
5. Please test each hash table function as you write it in a file named HashTableTest.cpp (which should include your main function).
6. Additionally, you will need to include your templated, doubly-linked List.h and the files Book.h and Book.cpp from Lab 7 in the same project as your Hash Table. (INCLUDED AT THE VERY BOTTOM PLEASE CHECK)
#ifndef HASHTABLE_H_ #define HASHTABLE_H_ #include
//destructor
HashTable(const HashTable& ht); //copy constructor /**Access Functions*/ int hash(string key); //returns the hash value for the given key //the hash value is the sum of //of the ASCII values of each char in the key //% the size the of the table //Key for this table: title + author int countBucket(int index); //counts the number of Books at this index //returns the count //pre: 0<= index < SIZE int search(Book b); //Searches for b in the table //returns the index at which b is located //returns -1 if b is not in the table /**Manipulation Procedures*/ void insert(Book b); //inserts a new book into the table //calls the hash function on the key to determine //the correct bucket void remove(Book b); //removes b from the table //calls the hash function on the key to determine //the correct bucket /**Additional Functions*/ void printBucket(int index); //Prints all the books at index //pre: 0<= index < SIZE
//Should print according to the following formula:
//"Printing index
//skips two lines
//Next, prints each book at that index in the format: //
LIST.H FILE:
#ifndef LIST_H_ #define LIST_H_
#include
template
Node(listdata data): data(data), next(NULL), previous(NULL){} };
typedef struct Node* Nodeptr;
Nodeptr first; Nodeptr last; Nodeptr iterator;
int size;
void reverse(Nodeptr node); //Helper function for the public printReverse() function. //Recursively prints the data in a List in reverse.
bool isSorted(Nodeptr node); //Helper function for the public isSorted() function. //Recursively determines whether a list is sorted in ascending order.
int binarySearch(int low, int high, listdata data); //Recursively searchs the list by dividing the search space in half //Returns the index of the element, if it is found in the List //Returns -1 if the element is not in the List
public:
/**Constructors and Destructors*/
List(); //Default constructor; initializes and empty list //Postcondition: A new list object is created
List (const List &list); //copy constructor
~List(); //Destructor. Frees memory allocated to the list //Postcondition: Memory that was created has been freed
/**Accessors*/
listdata getFirst(); //Returns the first element in the list //Precondition: List cannot be empty (there must be a first element)
listdata getLast(); //Returns the last element in the list //Precondition: List cannot be empty (there must be a last element)
bool isEmpty(); //Determines whether a list is empty.
int getSize(); //Returns the size of the list
listdata getIterator(); //returns the element currently pointed at by the iterator
bool offEnd(); //returns whether the iterator is off the end of the list, i.e. is NULL
bool isSorted(); //Wrapper function that calls the isSorted helper function to determine whether //a list is sorted in ascending order. //We will consider that a list is trivially sorted if it is empty. //Therefore, no precondition is needed for this function
int getIndex(); //Indicates the index of the Node where the iterator is currently pointing //Nodes are numbered from 1 to size of the list //Pre: size != 0 //Pre: !off_end()
int linearSearch(listdata data); //Searchs the list, element by element, from the start of the List to the end of the List //Returns the index of the element, if it is found in the List //Calls the above indexing functions in its implementation //Returns -1 if the element is not in the List //Pre: size != 0
int binarySearch(int value, int low, int high); //Returns the index where data is located in the List //Calls the private helper function binarySearch to perform the search //Pre: size != 0 //Pre: List is sorted (must test on a sorted list)
/**Manipulation Procedures*/
void removeLast(); //Removes the value of the last element in the list //Precondition: List cannot be empty (there must be a last element to remove) //Postcondition: The last element is removed
void removeFirst(); //Removes the value of the first element in the list //Precondition: List cannot be empty (there must be a first element to remove) //Postcondition: The first element is removed
void insertLast(listdata data); //Inserts a new element at the end of the list //If the list is empty, the new element becomes both first and last //Postcondition: There is a new last element
void insertFirst(listdata data); //insertFirst inserts a new Node IN FRONT OF the first node in the list each time it is called, //effectively creating a new front of the list. //Inserts a new element at the start of the list //If the list is empty, the new element becomes both first and last //Postcondition: There is a new first element
void startIterator (); // moves the iterator to the start of the list
void removeIterator(); //removes the element currently pointed to by the iterator. Iterator then points to NULL.
void insertIterator(listdata data); //inserts an element after the node currently pointed to by the iterator
void advanceIterator(); //advanceIterator: moves the iterator up by one node
void advanceToIndex(int index); //Moves the iterator to the node whose index number is specified in the parameter //Pre: size != 0 //Pre: index <= size
/**Additional List Operations*/
void printList(); //Prints to the console the value of each element in the list sequentially //and separated by a blank space //Prints nothing if the list is empty
bool operator==(const List &list); //Tests two lists to determine whether their contents are equal //Postcondition: returns true if lists are equal and false otherwise
void printReverse(); //Wrapper function that calls the reverse helper function to print a list in reverse //prints nothing if the List is empty
};
template
//default constructor List
}
//copy constructor template
while(temp->next != NULL) {
temp = temp->next; //advance up to the next node in the original list iterator->next = new Node(temp->data); //using node constructor to create a new node with copy of data iterator = iterator->next; //advance to this new node
}
last = iterator; //Why do I need this line of code? iterator = NULL;
} }
//default destrcutor template
} }
template
template
template
template
template
return iterator->data;
}
template
else { return false; }
}
template
if (first->next == NULL) {
delete last; first = NULL; last = NULL; size = 0;
}
else {
Nodeptr temp = first;
while (temp->next != last) { temp = temp->next; }
delete last; last = temp; last->next = NULL;
} size --;
}
template
{ assert(size!=0);
if (size == 1) { delete first; first = last = NULL; size = 0;
}
else {
Nodeptr temp= first; first = first->next; delete temp; size --;
} }
template
else { last -> next = new Node(data); last = last -> next; }
size++; }
template
}
else { Nodeptr N = new Node(data); N->next = first; first->previous = N; first = N; }
size++; }
template
}
template
if (iterator == last) {
removeLast(); }
else if (iterator == first) { removeFirst(); } else { iterator->previous->next = iterator->next; iterator->next-> previous = iterator->previous; delete iterator; iterator = NULL; } size --; }
template
if (iterator == last) { insertLast(data); } else { Nodeptr N = new Node(data); N->previous = iterator; N->next = iterator->next; iterator->next->previous = N; iterator->next = N; size++; }
}
template
iterator = iterator->next;
}
template
}
template
template
if (temp == NULL) return;
else { cout << temp->data << endl; temp = temp->previous;
} }
template
}
template
} else reverse (last); return true; }
template
int count =1 ; Nodeptr temp= first;
while (temp != iterator) { count++; temp = temp->next; } return cout ;
}
template
iterator = first;
for (int i = 1; i < index; i++) {
iterator = iterator->next;
} }
template
Nodeptr temp; temp = first; int location = 1;
while (temp != NULL) {
if (temp->data == data) { return location; }
else { location++; temp = temp->next; } }
return -1;
}
template
if (mid % 2 != 0) { return mid; }
else advanceToIndex(mid); if (getIterator() == value) { return mid; }
else if (value < getIterator()) { return binarySearch(low, mid -1, value); }
else return binarySearch( low, mid +1, value); }
#endif /* LIST_H_ */
BOOK.H FILE:
#ifndef BOOK_H_ #define BOOK_H_
#include
class Book { private: string title; string author; unsigned isbn; double price;
public:
/**Constructors*/ Book();
Book(string t, string a, unsigned i, double p);
/**Access Functions*/ string get_title(); string get_author(); unsigned get_isbn(); double get_price();
/**Manipulation Procedures*/ void set_title(string t); void set_author(string a); void set_isbn(unsigned i); void set_price(double p);
/**Additional Functions*/
friend ostream& operator<<(ostream& os, const Book& book); //prints out a book to the designated stream in the following format //
bool operator==(const Book& book); //compares two books to determine if they are the same book
bool operator<(const Book& book); //compares two books to determine if one comes before the other //alphabetically by title and secondarily by author if the two //books contain the same title //returns false if the two books are the same
bool operator>(const Book& book); //compares two books to determine if one comes after the other //alphabetically by title and secondarily by author if the two //books contain the same title //returns false if the two books are the same
};
#endif /* BOOK_H_ */
BOOK.CPP FILE:
#include "Book.h"
#include
#include
Book::Book() :
title(""), author(""), isbn(0), price(0.0) {
}
;
Book::Book(string t, string a, unsigned i, double p) {
title = t;
author = a;
isbn = i;
price = p;
}
/**Access Functions*/
string Book::get_title() {
return title;
}
string Book::get_author() {
return author;
}
unsigned Book::get_isbn() {
return isbn;
}
double Book::get_price() {
return price;
}
/**Manipulation Procedures*/
void Book::set_title(string t) {
title = t;
}
void Book::set_author(string a) {
author = a;
}
void Book::set_isbn(unsigned i) {
isbn = i;
}
void Book::set_price(double p) {
price = p;
}
/**Additional Functions*/
ostream& operator <<(ostream& os, const Book& book) {
os << book.title << " by " << book.author << endl;
os << "$" << book.price << endl;
os << "isbn #" << book.isbn << endl;
return os;
}
bool Book::operator ==(const Book& book) {
return (title == book.title && author == book.author);
}
bool Book::operator <(const Book& book) {
if (title == book.title) {
return (author < book.author);
}
else {
return (title < book.title);
}
}
bool Book::operator >(const Book& book) {
if (title == book.title) {
return (author > book.author);
}
else {
return (title > book.title);
}
}
Calling the Hash Function:
For the purposes of this assignment, we will be using the algorithm defined in class which sums the ASCII values of all the characters in the string key and scales the result to indices of the table.
You are welcome to use this or an alternate hash algorithm for your course project. However, please use the provided hash algorithm for Lab 8
The key that you should pass to the hash function is the Book's title concatenated with the Book's author. This key should provide enough unique information to differentiate among each book, even if the books have the same title or the same author. If both author and title are the same as another book's title and author, we can assume the book would be a duplicate entry in the table.
Hash Table Constructor and Destructor:
These functions should be left blank in HashTable.cpp.
The List constructor is already called inside of the HashTable.h, at the following line:
List
Likewise, the destructor should be left blank, as the List destructor will automatically be called once Table goes out of scope.
Adding Values to the Hash Table:
The next step in the process is to be able to add a value to the hash table.
Since we are using the separate chaining approach to collisions, we are using an array of Lists to represent our table.
Each time we insert a new book into the table, we need to complete these steps:
Call the hash function to determine at which index or bucket to place the Book inside the table
Insert the Book at this index of the Table array.
Note that you need to call the correct function from the List class to insert this book onto the end of the chain of books.
Each time you insert a new book, it should be added onto the end of the chain.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started