sweetvirgogirl

This assignment is to implement a symbol table which uses "hashing" to
organize the symbols in the table so that they can be accessed efficiently.
The table uses the following C++ declarations:

template <class AT>
class item {
public:
item(string s);
string getName(void); // returns the name
AT attr; // attributes other than name
private:
string name;
};

template <class AT>
class SymTab {
public:
SymTab(); //initializes to the empty table
item<AT> * find(string s); //returns item pointer or null
item<AT> * insert(string s); //inserts if necessary and
//returns item pointer
};

For each symbol stored in the table there is a record of type AT which contains the values associated with the symbol. This information is stored with the symbol's name in an instance of the class item. AT is a type parameter in these declarations because the attributes of a symbol
typically vary from application to application. A symbol table is an
instance of class SymTab whose find function returns a pointer to the item
in which its input symbol is stored. If the symbol is not stored in the
table, find returns NULL. The function insert performs the same function as
find except that it always returns a pointer to the item instance for the
symbol because it creates a new instance of item for a symbol that is not
stored in the table, and then stores it in the table before returning.
Thus, insert never returns NULL.

The hash table itself is implemented as an array of 137 linked-lists which
is "hidden" from clients of SymTab. Each linked-list represents the set of
symbols that "hash" to that entry of the array; i. e., each element in the
list contains the item for a symbol that hashes to the index of the array
element which points to the list. You may use any reasonable hashing
function in your implementation. You may implement the linked-lists yourself or you may use the implementation in the C++ Standard Template Library (STL).
^^ I'm confused about sentences in the bigger font.
like I dont even know what they are asking ...
and why 137?!

DaWei

Read the forum's rules/FAQ.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

The Dark

A hash is a function that given some input (in this case your string) and returns a number for it. The number returned for any given string must always be the same. A good hash function scatters the hash values around.

In this case 137 is a (semi) arbitrary number of hash values your function should return.

When you get given a string, use your hash function to return a number from 0 to 136. Then put (or find) the string in the list in the array entry associated with that hash number. The idea is that the hash function is much faster than searching the full list of all names, so you end up with your string searches (and insert) being approximately 137 times fast.

Give it a go and see how far you can get. Post some code here if you get stuck.

sweetvirgogirl

well I didnt ask anyone to do my assignment, all I'm asking is at least explain the assignment to me so that I can do it .... I mean you have to agree that I cant do assignment if I dont even know what they are asking
if I cant post this question here ... then where should I post it?

nnxion

He means that you are supposed to ask your question differently, using code tags and formulating your question nicely.

__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for."
-- Socrates

sweetvirgogirl

how do covert a string into an integer?

suppose the string is "blah"
how do i get a numerical value for the string?

sweetvirgogirl

^i dont even know if it's possible ...
but if it is not, i need someone to tell me that it's not lol

nindoja

If you are on windows, look into atoi, and itoa to store an integer in a character array.

sweetvirgogirl

yeah i looked into that ... no luck
it just gives me 0 ... !!

if i use "42" as a string, it will tell me 42
but if i use "blah" as a string, it'll give me plain zero..
see my problem?

DaWei

You don't get an integer from a string containing the word "blah." You get integers from strings containing numeric characters such as '0', '1', et. al. Try to be rational. If you like, you can assign binary numerical values to each of the codes (as they did with ASCII back in the olden days), and do with them whatever you like. You might even try to put them in the bank to supplement your salary as a programmer.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers