Homework SourseC HELP The main focus of this assignment is chained hash and
C++ HELP!
The main focus of this assignment is chained hash and template functions and class. . The material from Ch1 ~ 12 of the textbook can help you tremendously. You can get a lot of good information about implementing this assignment from chapter 12.
You can add any number of paramours, functions and classes for this assignment and use any advance skills you learned. But there need to have at least two .h files, two template files and one .cpp file to generate the expecting result.
In sections 12.2 ~ 12.4 discuss the hashing concept and implementation. This assignment we will implement a chaining (data structure of a hash table).
Some information
Files that you need to know or write:
table2.h: A header file for this assignment’s Table class. This is a template class. The template parameter, called RecordType, may be instantiated as any struct or class that contains an integer member variable called key.
The following are definition of a Table class, some useful functions and variables.
Table<RecordType>
This class is a container template class for a Table of records. The template parameter, RecordType, is the data type of the records in the Table. It may any type with a default constructor, a copy constructor,an assignment operator, and an integer member variable called key. In the Table<RecordType> template class assignments and the copy constructor may be used with Table objects. If there is insufficient dynamic memory, then the copy constructor, insert, the assignment operator can add new memory.
CONSTRUCTOR for the Table<RecordType> template class:
Table( )
Postcondition: The Table has been initialized as an empty Table.
MODIFICATION MEMBER FUNCTIONS for the Table<RecordType> class:
1. void insert(const RecordType& entry)
Precondition: entry>= 0. Also if entry is not already a key in the table, then the Table has space for another record. (i.e., size( ) < CAPACITY).
Postcondition: If the table already had a record with a key equal to entry, then that record is replaced by entry. Otherwise, the entry will be added as a new record of the Table.
2. void remove(int key)
Postcondition: If a record was in the Table with the specified key, then that record has been removed; otherwise the table is unchanged.
3. void print(int index)const;
Postcondition: If the Table with the index has data, then print the index and data in a chining format
d. CONSTANT MEMBER FUNCTIONS for the Table<RecordType> class:
1. bool is_present(const RecordType & target) const
Postcondition: The return value is true if there is a record in the Table with the specified key. Otherwise, the return value is false.
2. void find(int key, bool& found, RecordType& result) const
Postcondition: If a record is in the Table with the specified key, then found is true and result is set to a copy of the record with that key. Otherwise found is false and the result contains garbage.
3. size_t size( ) const
Postcondition: Return value is the total number of records in the Table.
Private data members:
Node<RecordType> *data[TABLE_SIZE];
size_t total_records;
// HELPER FUNCTION
size_t hash(int key) const;
Node<RecordType>* find_node(Node<RecordType> *&cursor,Node<RecordType> *&precursor, int key) const;
table2.template: is the implementation file for the table2.h.
link2.h is a header file to provide a toolkit of ten template functions for manipulating linked lists. Each node of the list contains a piece of data and a pointer to the next node (provided).
link2.template is the implementation file for the linke.h (provided).
CISP430V4A6.cpp is the driver for this assignment and there are several steps you need to do to test the program.
1 Instantiate two Table objects and each with 10 fields.
2 Display the two Table objects’ information.
3 Use random number generator to generate 70 numbers each in between 0~200 for the Table objects.
4 Display the two Table objects’ information.
5 Removes all the data in first object.
6 Display the two Table objects’ information.
7 Using = to assign 2nd object to the first one.
8 Display the two Table objects’ information.
There is a CISP430V4A6.zip file comes with this assignment. There should have link2.h, link2.template and CISP430V4A6.exe files in it. You can double click on the exe file to get to the following result.
+++++++++++FILES++++++++++++++++
//link2.h
#ifndef LINK2_H
#define LINK2_H
#include <stdlib.h> // Provides size_t
template <class Item>
struct Node
{
Item data;
Node *link;
};
// FUNCTIONS for the linked list toolkit
template <class Item>
size_t list_length(Node<Item>* head_ptr);
template <class Item>
void list_head_insert(Node<Item>*& head_ptr, const Item& entry);
template <class Item>
void list_insert(Node<Item>*& previous_ptr, const Item& entry);
template <class Item>
Node<Item>* list_search(Node<Item>* head_ptr, const Item& target);
template <class Item, class SizeType>
Node<Item>* list_locate(Node<Item>* head_ptr, SizeType position);
template <class Item>
void list_head_remove(Node<Item>*& head_ptr);
template <class Item>
void list_remove(Node<Item>* previous_ptr);
template <class Item>
void list_clear(Node<Item>*& head_ptr);
template <class Item>
void list_copy
(Node<Item>* source_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr);
template <class Item>
void list_piece
(Node<Item>* source_ptr, Node<Item>* end_ptr,
Node<Item>*& head_ptr, Node<Item>*& tail_ptr);
#include \"link2.template\" // Include the implementation
#endif
+++++++++++FILE NO 2+++++++++++++
// FILE: link2.template
// IMPLEMENTS: The ten template functions of the linked list toolkit
// (see link2.h). Note that this file is not compiled on its own.
// Instead, this file is included with an include directive at the bottom
// of link2.h.
#include <assert.h> // Provides assert
#include <stdlib.h> // Provides NULL and size_t
template <class Item>
size_t list_length(Node<Item>* head_ptr)
// Library facilities used: stdlib.h
{
Node<Item> *cursor;
size_t answer;
answer = 0;
for(cursor = head_ptr; cursor != NULL; cursor = cursor->link)
answer++;
return answer;
}
template <class Item>
void list_head_insert(Node<Item>*& head_ptr, const Item& new_item)
{
Node<Item> *insert_ptr;
insert_ptr = new Node<Item>;
insert_ptr->data = new_item;
insert_ptr->link = head_ptr;
head_ptr = insert_ptr;
//cout<<\" **list_head_insert** head_ptr->data \"<< head_ptr->data<< \" \ \";
}
template <class Item>
void list_insert(Node<Item>* &previous_ptr, const Item& new_item)
{
Node<Item> *insert_ptr;
insert_ptr = new Node<Item>;
insert_ptr->data = new_item;
// insert_ptr->link = NULL;
// previous_ptr->link = insert_ptr;
insert_ptr->link = previous_ptr->link;
previous_ptr->link = insert_ptr;
// cout<<\" $$list_insert$$ previous_ptr->data \"<< previous_ptr->data<< \" \ \";
// cout<<\" $$list_insert$$ insert_ptr->data \"<< insert_ptr->data<< \" \ \";
}
template <class Item>
Node<Item>* list_search(Node<Item>* head_ptr, const Item& target)
{
Node<Item> *cursor;
Solution
CISP430V4A6.cpp
#include <iostream>
#include \"table2.h\"
#include \"link2.h\"
using namespace std;
struct GenericRecord
{
double data;
int key;
};
void printTables(table<GenericRecord> t1, table<GenericRecord> t2);
int main()
{
/* Instantiate two Table objects and each with 10 fields. */
table<GenericRecord> table1, table2;
GenericRecord record;
/* Display the two Table objects’ information. */
cout << \"Instantiate two Table objects.\" << endl << endl;
printTables(table1, table2);
/* Use random number generator to generate 70 numbers
each in between 0~200 for the Table objects. */
cout << endl << \"**Using random number generator generates 70 numbers for the objects.**\" << endl << endl;
record.data = 2.5;
for(int i = 0; i < 70; i++)
{ //fill our tables with random numbers (0 - 199)
record.key = rand() % 201;
table1.insert(record);
record.key = rand() % 201;
table2.insert(record);
}
/* Display the two Table objects’ information. */
printTables(table1, table2);
/* Removes all the data in first object. */
cout << endl << \"**Calling clear function to clear all contents of first object.**\" << endl << endl;
table1.clear();
/* Display the two Table objects’ information. */
printTables(table1, table2);
/* Using = to assign 2nd object to the first one. */
cout << endl << \"**Using table1 = table2 displays the assignment operator overloading.**\" << endl << endl;
table1 = table2;
/* Display the two Table objects’ information. */
printTables(table1, table2);
system(\"pause\");
//cout << endl << \"Press enter key to continue . . . \"; //non-windows end
//fflush(stdin);
//getchar();
}
void printTables(table<GenericRecord> t1, table<GenericRecord> t2)
{
/* Display the two Table objects’ information. */
cout << \"\\t\\tTotal records in the first Table object is \" << t1.size();
cout << endl << \"\\t\\tContains of the first object display at below: \" << endl;
for(int i = 0; i < 10; i++)
{
t1.print(i);
}
cout << \"-------------------------------------------\" << endl;
cout << \"\\t\\tTotal records in the second Table object is \" << t2.size();
cout << endl << \"\\t\\tContains of the second object display at below: \" << endl;
for(int i = 0; i < 10; i++)
{
t2.print(i);
}
cout << \"===========================================\" << endl;
}
link2.h
// FUNCTIONS in the linked list toolkit:
// template <class Item>
// size_t list_length(Node<Item>* head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The value returned is the number of nodes in the linked
// list. The list itself is unaltered.
//
// template <class Item>
// void list_head_insert(Node<Item>*& head_ptr, const Item& entry)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: A new node containing the given entry has been added at
// the head of the linked list; head_ptr now points to the head of the new,
// longer linked list.
//
// template <class Item>
// void list_insert(Node<Item>* previous_ptr, const Item& entry)
// Precondition: previous_ptr points to a node in a linked list.
// Postcondition: A new node containing the given entry has been added
// after the node that previous_ptr points to.
//
// template <class Item>
// Node<Item>* list_search(Node<Item>* head_ptr, const Item& target)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The pointer returned points to the first node containing
// the specified target in its data member. If there is no such node, the
// null pointer is returned. The list itself is unaltered.
//
// template <class Item, class SizeType>
// Node<Item>* list_locate(Node<Item>* head_ptr, SizeType position)
// Precondition: head_ptr is the head pointer of a list, and position > 0.
// Postcondition: The pointer returned points to the node at the specified
// position in the list. (The head node is position 1, the next node is
// position 2, and so on). If there is no such position, then the null
// pointer is returned. The list itself is unaltered.
//
// template <class Item>
// void list_head_remove(Node<Item>*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list, with at
// least one node.
// Postcondition: The head node has been removed and returned to the heap;
// head_ptr is now the head pointer of the new, shorter linked list.
//
// template <class Item>
// void list_remove(Node<Item>* previous_ptr)
// Precondition: previous_ptr points to a node in a linked list, and this
// is not the tail node of the list.
// Postcondition: The node after previous_ptr has been removed.
//
// template <class Item>
// void list_clear(Node<Item>*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: All nodes of the list have been returned to the heap,
// and the head_ptr is now NULL.
//
// template <class Item>
// void list_copy
// (Node<Item>* source_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr)
// Precondition: source_ptr is the head pointer of a linked list.
// Postcondition: head_ptr and tail_ptr are the head and tail pointers for
// a new list that that contains the same items as the list pointed to by
// source_ptr.
//
// template <class Item>
// void list_piece
// (Node<Item>* source_ptr, Node<Item>* end_ptr,
// Node<Item>*& head_ptr, Node<Item>*& tail_ptr)
// Precondition: source_ptr and end_ptr are pointers to nodes on the same
// linked list, with the source_ptr node at or before the end_ptr node.
// Postcondition: head_ptr and tail_ptr are the head and tail pointers for
// a new linked list that contains the items from source_ptr to end_ptr.
// The original list is unaltered.
#ifndef LINK2_H
#define LINK2_H
#include <stdlib.h> // Provides size_t
template <class Item>
struct Node
{
Item data;
Node *link;
};
// FUNCTIONS for the linked list toolkit
template <class Item>
size_t list_length(Node<Item>* head_ptr);
template <class Item>
void list_head_insert(Node<Item>*& head_ptr, const Item& entry);
template <class Item>
void list_insert(Node<Item>*& previous_ptr, const Item& entry);
template <class Item>
Node<Item>* list_search(Node<Item>* head_ptr, const Item& target);
template <class Item, class SizeType>
Node<Item>* list_locate(Node<Item>* head_ptr, SizeType position);
template <class Item>
void list_head_remove(Node<Item>*& head_ptr);
template <class Item>
void list_remove(Node<Item>* previous_ptr);
template <class Item>
void list_clear(Node<Item>*& head_ptr);
template <class Item>
void list_copy
(Node<Item>* source_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr);
template <class Item>
void list_piece
(Node<Item>* source_ptr, Node<Item>* end_ptr,
Node<Item>*& head_ptr, Node<Item>*& tail_ptr);
#include \"link2.template\" // Include the implementation
#endif
link2.template
#include <assert.h> // Provides assert
#include <stdlib.h> // Provides NULL and size_t
template <class Item>
size_t list_length(Node<Item>* head_ptr)
// Library facilities used: stdlib.h
{
Node<Item> *cursor;
size_t answer;
answer = 0;
for(cursor = head_ptr; cursor != NULL; cursor = cursor->link)
answer++;
return answer;
}
template <class Item>
void list_head_insert(Node<Item>*& head_ptr, const Item& new_item)
{
Node<Item> *insert_ptr;
insert_ptr = new Node<Item>;
insert_ptr->data = new_item;
insert_ptr->link = head_ptr;
head_ptr = insert_ptr;
//cout<<\" **list_head_insert** head_ptr->data \"<< head_ptr->data<< \" \ \";
}
template <class Item>
void list_insert(Node<Item>* &previous_ptr, const Item& new_item)
{
Node<Item> *insert_ptr;
insert_ptr = new Node<Item>;
insert_ptr->data = new_item;
// insert_ptr->link = NULL;
// previous_ptr->link = insert_ptr;
insert_ptr->link = previous_ptr->link;
previous_ptr->link = insert_ptr;
// cout<<\" $$list_insert$$ previous_ptr->data \"<< previous_ptr->data<< \" \ \";
// cout<<\" $$list_insert$$ insert_ptr->data \"<< insert_ptr->data<< \" \ \";
}
template <class Item>
Node<Item>* list_search(Node<Item>* head_ptr, const Item& target)
{
Node<Item> *cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
if (cursor->data == target)
return cursor;
return NULL;
}
template <class Item, class SizeType>
Node<Item>* list_locate(Node<Item>* head_ptr, SizeType position)
// Library facilities assert.h, stdlib.h
{
Node<Item> *cursor;
size_t i;
assert(position > 0);
cursor = head_ptr;
for(i = 1; (i != position) && (cursor != NULL); i++)
cursor = cursor->link;
return cursor;
}
template <class Item>
void list_head_remove(Node<Item>*& head_ptr)
{
Node<Item> *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link;
delete remove_ptr;
}
template <class Item>
void list_remove(Node<Item>* previous_ptr)
{
Node<Item> *remove_ptr;
remove_ptr = previous_ptr->link;
previous_ptr->link = remove_ptr->link;
delete remove_ptr;
}
template <class Item>
void list_clear(Node<Item>*& head_ptr)
// Library facilities used: stdlib.h
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}
template <class Item>
void list_copy
(Node<Item>* source_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr)
// Library facilities used: stdlib.h
{
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list
if (source_ptr == NULL)
return;
// Make the head node for the newly created list, and put data in it
list_head_insert(head_ptr, source_ptr->data);
tail_ptr = head_ptr;
// Copy the rest of the nodes one at a time, adding at the tail of new list
for (source_ptr = source_ptr->link; source_ptr != NULL; source_ptr = source_ptr->link)
{
list_insert(tail_ptr, source_ptr->data);
tail_ptr = tail_ptr->link;
}
}
template <class Item>
void list_piece
(Node<Item>* start_ptr, Node<Item>* end_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr)
// Library facilities used: assert.h, stdlib.h
{
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list
if (start_ptr == NULL)
return;
// Make the head node for the newly created list, and put data in it
list_head_insert(head_ptr, start_ptr->data);
tail_ptr = head_ptr;
if (start_ptr == end_ptr)
return;
// Copy the rest of the nodes one at a time, adding at the tail of new list
for (start_ptr = start_ptr->link; start_ptr != NULL; start_ptr = start_ptr->link)
{
list_insert(tail_ptr, start_ptr->data);
tail_ptr = tail_ptr->link;
if (start_ptr == end_ptr)
return;
}
}
/*template <class Item>
void operator =(const Node<Item>& source)
// Library facilities used: link2.h, stdlib.h
{
size_t i;
// Node<Item>* tail_ptr; // Needed for list_copy
if (this == &source)
return; // Avoid self-assignment
this=&&source;
}*/
table2.h
/*--------------------------------------------------------------------------------*/
// TEMPLATE CLASS PROVIDED: Table<RecordType>
// This class is a container template class for a Table of records.
// The template parameter, RecordType, is the data type of the records in the
// Table. It may any type with a default constructor, a copy constructor,
// an assignment operator, and an integer member variable called key.
//
// CONSTRUCTOR for the Table<RecordType> template class:
// Table( )
// Postcondition: The Table has been initialized as an empty Table.
//
// MODIFICATION MEMBER FUNCTIONS for the Table<RecordType> class:
// void insert(const RecordType& entry)
// Precondition: entry.key >= 0. Also if entry.key is not already a key in
// the table, then the Table has space for another record
// (i.e., size( ) < CAPACITY).
// Postcondition: If the table already had a record with a key equal to
// entry.key, then that record is replaced by entry. Otherwise, entry has
// been added as a new record of the Table.
//
// void remove(int key)
// Postcondition: If a record was in the Table with the specified key, then
// that record has been removed; otherwise the table is unchanged.
//
// CONSTANT MEMBER FUNCTIONS for the Table<RecordType> class:
// bool is_present(const Item& target) const
// Postcondition: The return value is true if there is a record in the
// Table with the specified key. Otherwise, the return value is false.
//
// void find(int key, bool& found, RecordType& result) const
// Postcondition: If a record is in the Table with the specified key, then
// found is true and result is set to a copy of the record with that key.
// Otherwise found is false and the result contains garbage.
//
// size_t size( ) const
// Postcondition: Return value is the total number of records in the
// Table.
//
// VALUE SEMANTICS for the Table<RecordType> template class:
// Assignments and the copy constructor may be used with Table objects.
//
// DYNAMIC MEMORY USAGE by the Table<RecordType> template class:
// If there is insufficient dynamic memory, then the following functions
// can call new_handler: the copy constructor, insert, the assignment
// operator.
#ifndef TABLE2_H
#define TABLE2_H
#include <cstdlib> // Provides size_t
#include \"link2.h\" // Provides the node type, from Figure 6.5 on page 306
template <class RecordType>
class table
{
public:
// MEMBER CONSTANT -- See Appendix E if this fails to compile.
static const std::size_t TABLE_SIZE = 10;
// CONSTRUCTORS AND DESTRUCTOR
table( );
table(const table& source);
~table( );
// MODIFICATION MEMBER FUNCTIONS
void insert(const RecordType& entry);
void remove(int key);
void clear();
void print(int index) const;
void operator =(const table& source);
// CONSTANT MEMBER FUNCTIONS
void find(int key, bool& found, RecordType& result) const;
bool is_present(int key) const;
std::size_t size( ) const { return total_records; }
private:
Node<RecordType> *data[TABLE_SIZE];
std::size_t total_records;
// HELPER MEMBER FUNCTION
std::size_t hash(int key) const;
};
#include \"table2.template\" // Include the implementation
#endif
table2.template
#include \"table2.h\"
using std::cout;
using std::endl;
template <class RecordType>
table<RecordType>::table( )
{ //constructor
total_records = 0;
for(int i = 0; i < TABLE_SIZE; i++)
{ //initialize linked lists as null head ptr
data[i] = NULL;
}
//test memory leakage
// Node<RecordType> *test = new Node<RecordType>;
// test->link = NULL;
}
template <class RecordType>
table<RecordType>::table(const table& source)
{
Node<RecordType> *tempTail;
//initialize and copy values
for(int i = 0; i < TABLE_SIZE; i++)
{ //list_copy(source, head, tail)
list_copy(source.data[i], data[i], tempTail);
//this->data[i] = tempHead; //set head for data set
}
this->total_records = source.total_records;
}
template <class RecordType>
table<RecordType>::~table( )
{
for(int i = 0; i < TABLE_SIZE; i++)
{ //clear via toolkit function
list_clear(data[i]);
}
}
template <class RecordType>
void table<RecordType>::insert(const RecordType& entry)
{
if(is_present(entry.key) == false) //ensure no duplicate keys
{
Node<RecordType> *cursor = data[hash(entry.key)]; //set cursor to head chain node
if(cursor == NULL)
{
//create new head pointer (and set cursor to it)
cursor = data[hash(entry.key)] = new Node<RecordType>;
cursor->data = entry;
cursor->link = NULL;
}
else
{
//first, find insert point
while(cursor->link != NULL && cursor->data.key != entry.key)
{
cursor = cursor->link;
} //cursor now contains last node in list
cursor->link = new Node<RecordType>;
//create new ptr, set values for new entry
cursor = cursor->link;
cursor->link = NULL;
cursor->data = entry;
//else - duplicate key - do not insert
}
total_records++; //new entry added -- increment count
}
} //else, key already exists in table -- no duplicates allowed
template <class RecordType>
void table<RecordType>::remove(int key)
{
Node<RecordType> *cursor = data[hash(key)],
*precursor = NULL;
/* find node for deletion
(cant use is_present since we need the node address) */
bool found = false;
while(cursor != NULL)
{ //search for node containing key
if(cursor->data.key == key)
{ //node found -- time to delete
found = true;
break;
}
precursor = cursor;
cursor = cursor->link;
}
if(found == true)
{
//unwanted node found -- time to delete
//cursor contains node to be deleted
list_remove(precursor);
total_records--;
}
//else - no node to delete - do nothing
}
template <class RecordType>
void table<RecordType>::clear()
{
for(int i = 0; i < TABLE_SIZE; i++)
{ //use toolkit clear on all indexes
list_clear(data[i]);
}
}
template <class RecordType>
void table<RecordType>::print(int index) const
{
Node<RecordType> *cursor = data[index];
//print header
cout << \"[< \" << index << \" >]----> \";
while(cursor != NULL)
{ //traverse nodes, printing each data key
cout << \"[\" << cursor->data.key << \"]-->\";
cursor = cursor->link;
}
cout << \" NULL\" << endl; //end node
}
template <class RecordType>
void table<RecordType>::operator=(const table& source)
{
if(this == &source) //handle self-assignment case
return;
clear(); //reset object -- prevent leaks
Node<RecordType> *tempTail;
//initialize and copy values
for(int i = 0; i < TABLE_SIZE; i++)
{ //list_copy(source, head, tail)
list_copy(source.data[i], data[i], tempTail);
//this->data[i] = tempHead; //set head for data set
}
this->total_records = source.total_records;
}
template <class RecordType>
void table<RecordType>::find(int key, bool& found, RecordType& result) const
{
/*Postcondition: If a record is in the Table with the specified key, then found is true and result is set to a copy of the record with that key. Otherwise found is false and the result contains garbage. */
Node<RecordType> *cursor = data[hash(key)];
found = false;
while(cursor != NULL && cursor->data.key != key)
{
if(cursor->data.key == key)
{ //we have found our match
found = true;
result = cursor->data;
break;
}
//advance through list
cursor = cursor->link;
}
}
template <class RecordType>
bool table<RecordType>::is_present(int key) const
{
Node<RecordType> *cursor = data[hash(key)];
bool found = false;
while(cursor != NULL)
{
if(cursor->data.key == key)
{ //we have found our match
found = true;
break; //escape while loop
}
cursor = cursor->link; //advance list
}
return found;
}
template <class RecordType>
std::size_t table<RecordType>::hash(int key) const
{ //find which index we wish to slot our entry into
return key % TABLE_SIZE;
}
