DaniWeb Forum Index > Software Development > C++

C++ RSS

hash table /independent rehaching

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Nov 2009

Posts: 6

Reputation: gedas is an unknown quantity at this point

Solved Threads: 0

gedas

Offline

Newbie Poster

hash table /independent rehaching

25 Days Ago

Hi everyone,
Well I come to a point that I have run out of ideas and time and I’m going to ask for help from anyone that can help.
I hope that there will be someone that could give me a hint how to solve my problem.
About my problem I can say that I just received a huge coursework, I was trying to do it my self but now there isn’t much time left till it has to be done and I’m still not confident enough about c++ to be able to implement it my self and I’m not even close to finishing it.

This is what I need to do create a program that demonstrates the use of static Hash Table structures: using ‘independent rehashing’ to resolve
collisions, for constructing a dictionary object, dictionary, with a string ‘word’ and a list
of ‘meaning’s. The default value for a ‘dictionary’ data entry is the NULL string.

Implement the following definition for a C++ class, Meaning which contains facilities for storing and
manipulating the record containing the ‘meaning’ of a ‘word’.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
//Definition file for Meaning.h
#ifndef MEANING
#define MEANING
#include <string>
class Meaning
{
public:
Meaning(); // constructor
~Meaning(); // destructor
// setter methods
void setMeaning(string);
void setNext(Meaning*);
// getter methods
void printMeaning(); // display the meaning of a word on the screen
string getMeaning(); // return the meaning of a word
Meaning* getNext(); // get the next meaning for a word if it exists
private:
string meaning;
Meaning* next;
};
#endif
//Definition file for Meaning.h
#ifndef MEANING
#define MEANING
#include <string>
class Meaning
{
public:
Meaning(); // constructor
~Meaning(); // destructor
// setter methods
void setMeaning(string);
void setNext(Meaning*);
// getter methods
void printMeaning(); // display the meaning of a word on the screen
string getMeaning(); // return the meaning of a word
Meaning* getNext(); // get the next meaning for a word if it exists
private:
string meaning;
Meaning* next;
};
#endif

Implement the following definition for a C++ class ‘linked list’ which declares facilities
for storing and manipulating a singly linked list of ‘meaning’ nodes.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
 
// Definition file for List.h
#ifndef LIST
Page 3 of 12
#define LIST
#include <string>
#include “Meaning.h”
class List
{
public:
List(); // constructor – initialise empty list
~List(); // destructor
// check whether the list is empty and return true if empty,
// otherwise return false.
bool isEmpty() const;
// insert meaning at the rear (i.e. end) of the list
void insertAtRear(string meaning);
// display the list contents.
void printList();
private:
Meaning* head; // points to head of list
};
#endif
 
// Definition file for List.h
#ifndef LIST
Page 3 of 12
#define LIST
#include <string>
#include “Meaning.h”
class List
{
public:
List(); // constructor – initialise empty list
~List(); // destructor
// check whether the list is empty and return true if empty,
// otherwise return false.
bool isEmpty() const;
// insert meaning at the rear (i.e. end) of the list
void insertAtRear(string meaning);
// display the list contents.
void printList();
private:
Meaning* head; // points to head of list
};
#endif

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
//Definition file for IndDicT.h
#ifndef IDT
#define IDT
#include <string>
#include “List.h”
const int MAX_TABLESZ = 23;
Page 6 of 12
class IndDicT
{
public:
IndDicT(); // constructor – create empty table
~IndDicT(); // destructor
/* This function uses the algorithm in Appendix A to convert the ‘word’ string
into a positive number equivalent. It also uses the ‘division-remainder’
method to divide the numeric value by the MAX_TABLESZ to
return the table index. */
int hashKey(string );
/* The function uses the hashKey() function to find the ‘table index’.
If the ‘word’ is not in the table and the table location given by the
index is empty, the ‘word’ is inserted in the table and its associated
‘meaning’ is inserted at the end of the list.
If the ‘word’ already exists in the table, the function will only update the
existing linked list by adding the new ‘meaning’ at the end of it. */
void insert(string word, string meaning);
/* return the list of meaning(s) associated with the primary key 'word'.
Return null (i.e. empty) list if the ‘word’ is not present in the table */
List* lookUp( string word );
/* Print the non-empty dictionary entries in alphabetical order in an output
file.
It uses the ‘sort’ algorithm from the Standard Template Library ‘list’ class
to display the ‘word’ and its associated meanings in alphabetical order. */
void traverse();
private:
struct
{
string word;
List* meaningList;
} dictionary[MAX_TABLESZ]; // table to store the word and its meaning(s)
};
#endif
//Definition file for IndDicT.h
#ifndef IDT
#define IDT
#include <string>
#include “List.h”
const int MAX_TABLESZ = 23;
Page 6 of 12
class IndDicT
{
public:
IndDicT(); // constructor – create empty table
~IndDicT(); // destructor
/* This function uses the algorithm in Appendix A to convert the ‘word’ string
into a positive number equivalent. It also uses the ‘division-remainder’
method to divide the numeric value by the MAX_TABLESZ to
return the table index. */
int hashKey(string );
/* The function uses the hashKey() function to find the ‘table index’.
If the ‘word’ is not in the table and the table location given by the
index is empty, the ‘word’ is inserted in the table and its associated
‘meaning’ is inserted at the end of the list.
If the ‘word’ already exists in the table, the function will only update the
existing linked list by adding the new ‘meaning’ at the end of it. */
void insert(string word, string meaning);
/* return the list of meaning(s) associated with the primary key 'word'.
Return null (i.e. empty) list if the ‘word’ is not present in the table */
List* lookUp( string word );
/* Print the non-empty dictionary entries in alphabetical order in an output
file.
It uses the ‘sort’ algorithm from the Standard Template Library ‘list’ class
to display the ‘word’ and its associated meanings in alphabetical order. */
void traverse();
private:
struct
{
string word;
List* meaningList;
} dictionary[MAX_TABLESZ]; // table to store the word and its meaning(s)
};
#endif

Appendix A Function hashKey()

The function hashKey() converts a given string into a positive numeric value and then
the division-remainder method is applied on the numeric result to return the table index.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int hashKey(string word)
{
int result = 0;
for (int i=0; i < word.length(); i++)
{ // obtain the ASCII integer value of character i in the string ‘word’.
result = result + static_cast<int>(word[i]);
}
// Make sure that the result is a positive numeric value first
return (result % MAX_TABLESZ); // where MAX_TABLESZ is given as 23
}
int hashKey(string word)
{
int result = 0;
for (int i=0; i < word.length(); i++)
{ // obtain the ASCII integer value of character i in the string ‘word’.
result = result + static_cast<int>(word[i]);
}
// Make sure that the result is a positive numeric value first
return (result % MAX_TABLESZ); // where MAX_TABLESZ is given as 23
}

Appendix B File “listTest.dat” for testing the linked list
“To deliberately act in a way intended to anger someone.”
“In everyday language is a synonym for information.”
“Bachelor of Arts”
“A woodland plant with blue bell-shaped flowers”

Appendix C File “meanings.dat” for testing the Hash Table structures
provoke “To deliberately act in a way intended to anger someone.”
data “In everyday language is a synonym for information.”
BA “Bachelor of Arts”
bluebell “A woodland plant with blue bell-shaped flowers”
wizard “A person who is talented in some specified field.”
provoke “To incite or stimulate.”
B2B “business to business.”
cook To prepare by boiling, baking, frying, etc.
program A list of the acts, speeches, pieces.
Bluetooth “A short-range radio technology that allows wireless communication between
computers, mobile phones, etc.”
sextet “A composition of six instruments.”
multimedia “Refers to the use of electronic media to store and experience multimedia
content.”
wizard “A man in fairy tales who has magical powers.”
provoke “(often foll. by into) to cause a person to react in a particular, often angry, way.”
BA “British Airways”
Page 11 of 12

Appendix D An example of the expected screen output, in order, produced by
running the program using the input file “meanings.dat”
The dictionary is:
BA:
1 “Bachelor of Arts”
2 “British Airways
Bluetooth:
1 “A short-range radio technology that allows wireless communication between
computers, mobile phones, etc.”
bluebell:
1 “A woodland plant with blue bell-shaped flowers”
cook:
1 “To prepare by boiling, baking, frying, etc.”
multimedia
1 “Refers to the use of electronic media to store and experience multimedia content.”
program:
1 “A list of the acts, speeches, pieces.”
provoke
1 “To deliberately act in a way intended to anger someone.”
2 “To incite or stimulate.”
3 “(often foll. by into) to cause a person to react in a particular, often angry, way.”
sextet:
1 “A group of six performers.”
wizard:
1 “A person who is talented in some specified field.”
2 “A man in fairy tales who has magical powers.”