*Note: its not a fully functional hashTable for technical purposes
My priority is to get it to store the strings properly. I approached this a different
yet similar way to my other post and I have gotten much farther! The problem now is that my output prints duplicates each and table. More confounding is why only these words don't output properly. I will provide the source so you can try it out for yourself.
I compiled with visual c++ 2008 & 05 and received same output. My next goal would be to
implement it as an ADT, but for now solving this issue is crucial.
Once again thanks for any help I receive.
#include <iostream>
#include <string>
#include <fstream>
#include <cctype>
#include <iomanip>
using namespace std;
//function prototypes
int hashFunction(const char *key, int keyLenght, const int HTSIZE);
void LinearProbing(int upindex, string words[], string item ,int noitems[]);
string StringToLower(string strToConvert);
int main()
{
string getString; //used to read the strings
const int HTSIZE = 131; //Holds up to 130 words
string hashTable[HTSIZE]; //stores unique words
const char *cphashTable; //holds c-string value for processing
int IndexStatusList[131]; //holds the number of times a word is inserted at its location
ifstream DataIn; //filestream object
int size = 0; //no use yet
int lenght; //stores lenght of a string
int hIndex; //stores the index in where to store a string
//will be used as a constructor when implemented as ADT
//initializes both arrays. The first for empty strings, the other for ints
for(int c = 0; c < HTSIZE; c++)
{
hashTable[c] = " ";
IndexStatusList[c] = 0;
}
DataIn.open("blah.txt"); //Fail Safe test
if(!DataIn)
{
cout <<"Error opening data file\n";
}
else //Sucess
{
while(DataIn >> getString) //Gets the first string and reads until
{ //there is no more data to be read
lenght = static_cast<int>(getString.length()); //gets lenght of a string to be used for processing
cphashTable = getString.data(); //returns a c-string copy of a string
hIndex = hashFunction(cphashTable,lenght,HTSIZE); //computes the index. see def below
LinearProbing(hIndex,hashTable, cphashTable, IndexStatusList); //cphashTable //getString
} //tried both no difference in results
}
cout << "Count\t" << "Index\t" << "WORD\n"; //Title of Columns
for(int i = 0; i < HTSIZE;i++) // Outputs number of occurences followed by
{ // the location of the word in the hashtable
if(hashTable[i] != " ") // the content of that location e.g cat
{
cout << IndexStatusList[i] << "\t" << i << "\t" << hashTable[i] << endl ;
}
}
return 0;
} //end of main
/* Def of Linear Probring
Places the item, in this case a string in the appropriate location in the array.
The location hIndex is calculated by the function hashFunction and then passed
to this function as an argument. If the location to where hIndex points is empty
in the hashTable insert the item there and update its number of currence:(parralel array)
StatusListIndex. While the location is occupied find next available location by incrementing
the current location to one until an available space is found. My current list is less than
130 elements so no need to worry about space at this time. Then insert item at this new location
and update the IndexStatusList. You also need to check if at a certain location it is the same
instance of that item, to update its IndexStatusList. Eg, cat is inserted into location 1,
IndexStatusList is 1. Then another cat is found just update the IndexStatusList by one rather than
inserting it in a new location. Cat still at loc 1 IndexStatusList is 2
*/
void LinearProbing(int upindex, string words[], string item ,int noitems[])
{
item = StringToLower(item); //i tried this in hopes of being able to compare both
//strings properly but im not so sure.
if(item == words[upindex])
{
int inc = noitems[upindex]; //this section takes care of duplicates
inc++;
noitems[upindex] = inc;
}
else if(words[upindex] == " ")
{
words[upindex] = item; //if location is empty
noitems[upindex] = 1;
}
else
{
while(noitems[upindex] != 0)
{
upindex = ((upindex + 1) % 131); //collision
}
words[upindex] = item;
noitems[upindex] = 1;
}
}
/*
Adds the values of each character in the string then % it with HTSIZe which
is to be used as hIndex. There is no distinction between lowercase and uppercase
A is converted to the ascii equivalent of a
ex string ab = 97+98 then lets say htsize was 3
hIndex would then be 0.
*/
int hashFunction(const char *key, int keyLenght, const int HTSIZE)
{
int sum = 0;
for(int j =0; j < keyLenght ; j++)
{
sum = sum + static_cast<int>(tolower(key[j]));
}
return sum = sum % HTSIZE;
}
//change each element of the string to lower case
string StringToLower(string strToConvert)
{
for(unsigned int i=0;i<strToConvert.length();i++)
{
strToConvert[i] = tolower(strToConvert[i]);
}
return strToConvert;//return the converted string
}