I got this assignment from my teacher the other day and i am having a hard time understanding it. I asked him for help and im even more confused. I AM NOT ASKING FOR YOU TO DO IT. I AM ASKING FOR ADVICE AND HOW TO DO IT
Write a C++ program to create an array of linked lists. The program will store variables as they come from a file in a hash table (to be explained later). The program will also keep track of the number of accesses to each variable.
You will need to modify the node class to hold two data fields, a string and a count field. The program will use an array of linked lists to store variables in memory. The program will use an array of linked lists to store variables in memory. You will go to each array position by using a hash function to select the array element.
Declare the array with the following constant
const int PRIME=5;
Do not create a separate class for the array of bags; use the existing bag class only.
You will select each array position by hashing. After selecting the appropriate index, search the linked list to see if the string or variable is present. If it is, then update the count field by adding 1. If it is not present, then create a new node (storing it at the head of the list) and store the string, setting its count file to 1 ( since there has been an occurrence). You will need head_insert, either as a member function or a utility to add the values to the list.
Hashing involves adding the ASCII codes for each value and then using remainder division to select the array index. The hash table insures even distribution of the variables for fast access. Note that the data will not be sorted.
The output of the program will be a printout of each linked list, starting at index zero. Print the variables plus the count of each.
The algorithm will be discussed in more detail in class. You will need a search yielding a pointer to update the count field when a variable is present. Further specifications will be given if needed.
INPUT: File containing strings representing variables.
OUTPUT: As described above.
TO HAND IN:
Hardcopy of the C++ Code.
Hardcopy of the output
Your recording device
SPECIFICATIONS for the HASH FUNCTION:
output type: int
input type: a string or cstring
algorithm: sum the ASCII code for the string and return the sum modulo the size of the array. Ignore overflow when doing the sum.
Data for program 4
educe
line
educe
primrose
depart
line
thwart
line
grand
cellular
line
educe
depart
manage
depart
headline
empire
torch
headline
line
myth
deposit
balance
cellular
educe
distance
SPECIFICATIONS for PROGRAM
For the node class, add the following:
Private member
string word
two functions, a transformer and observer for the new private member
modify the constructor for the new data member
For the bag class
Public:
The “Big Four”, constructor, copy constructor, destructor, overloaded =.
bool search_list
// tells the client wheather a specific value is in the list. Calls a function search.
void head_insert
//should be a member function rather than a utility.
void add_to_count
//access the “current” pointer (in the private section)
//to update the count field of the node if the search is successful
friend ostream operator << (ostream &, const bag & mylist)
//prints a linked list.
//Overloaded operator to print both the data and the count field for each node.
Protected:
node * search1_list
//Called by the public function search_list.
//Sets the private memebr current to the node to be updated
//or is NULL if the value is not there.
Private:
node * head_ptr;
node * current;
//add to the bag class. This pinter will be used in the search
//and again used to update the node if the data is already present.
In The Main Program
The main should have an EOF loop and a two-way decision to decide whether
to update the count field or add a new node to the head of the list.
Print the list in the main after the EOF loop. (the output will not be sorted)
The call to the output operator is as follows:
out4<<hashtable[i]//out4 is an ofstream object
Suggestion: code the program at first with a single, linked list, then add the hash table.
