Austen944's Profile User Rating: -----

Reputation: 1 Apprentice
Group:
Members
Active Posts:
39 (0.07 per day)
Joined:
08-February 13
Profile Views:
767
Last Active:
User is offline Aug 01 2013 06:17 PM
Currently:
Offline

Previous Fields

Dream Kudos:
0
Icon   Austen944 has not set their status

Posts I've Made

  1. In Topic: C++ Hash Table Class Error "undefined reference to"

    Posted 1 Aug 2013

    Never mind. Just realized that it was only incrementing when a duplicated string appeared. Moved the incrementor to the "if statement" in put() and it now displays correctly.
  2. In Topic: C++ Hash Table Class Error "undefined reference to"

    Posted 1 Aug 2013

    After messing around I decided to do this for counting the collisions at each slot in the hash table.

    I declared a array "int collisionArray[SIZE]" in hashtable.h and set it equal to 0 in "HashTable()".
    Next in "put(string s)" I made a else statement to increment the appropriate element when a collision is found.

    hashtable.cpp
    #include <iostream>
    #include <string>
    #include "listtools.h"
    #include "listtools.cpp"
    #include "hashtable.h"
    
    using LinkedListSavitch::Node;
    using LinkedListSavitch::search;
    using LinkedListSavitch::headInsert;
    using namespace std;
    
    #define HASH_WEIGHT 31
    
    namespace HashTableSavitch
    {
       HashTable::HashTable()
       {
        for (int i = 0; i < SIZE; i++)
        {
         hashArray[i] = NULL;
         collisionArray[i] = 0;
        }
       }
    
       HashTable::~HashTable()
       {
         for (int i=0; i<SIZE; i++)
         {
           Node<string> *next = hashArray[i];
           while (next != NULL)
           {
             Node<string> *discard = next;
    	 next = next->getLink( );
    	 delete discard;
           }
         }
       }
    
       unsigned int HashTable::computeHash(string s) const
       {
        unsigned int hash = 0;
        for (unsigned int i = 0; i < s.length( ); i++)
        {
        	hash = HASH_WEIGHT * hash + s[i];
        }
        return hash % SIZE;
       }
    
       bool HashTable::containsString(string target) const
       {
        int hash = this->computeHash(target);
        Node<string>* result = search(hashArray[hash], target);
        if (result == NULL)
           return false;
        else
           return true;
       }
    
       void HashTable::put(string s)
       {
    	   int hash = computeHash(s);
    	   if (search(hashArray[hash], s) == NULL)
           {
    		   // Only add the target if it's not in the list
    		   headInsert(hashArray[hash], s);
           }
    	   else
    	   {
    		   collisionArray[hash]++;
    	   }
       }
    
       void HashTable::printArray()
       {
    	   int number;
    	   for(int i = 0; i < SIZE; i++)
    	   {
    		   number = collisionArray[i];
    		   cout << "----------------\n";
    		   cout << "index = " << i << endl;
    		   cout << "Collisions = " << number << endl;
    		   cout << "----------------\n";
    	   }
       }
    } // HashTableSavitch
    
    


    I made a void function called "printArray()" to print out the number of collisions at each slot, but it displays 0 collisions for each slot.

    Is my code wrong for counting the number of collisions at each slot or am I missing something really simple here? Thanks for explaining what a hash collision is btw.
  3. In Topic: C++ Hash Table Class Error "undefined reference to"

    Posted 31 Jul 2013

    This is my final assignment and I am pretty stumped on what I should do for a couple parts.

    I am to create a Dictionary as a Hash Table with Linked List to spell check a text document. The source code for the HashTable class with linked list is given.

    I have to do the following :

    1.Display any misspelled word (A word is considered misspelled if its not in the dictionary)

    2.Count the number of collisions for each cell of the Hash Table when loading the dictionary "words.txt",
    and store/display the data 20 per line

    3.Count the number of words that are misspelled and are correct
    - In each case, count the number of operations performed and store/display these numbers
    - Also, store/display the average number of operations for a misspelled and correct word
    - Note : "number of operations" refers to the number of nodes visited in the linked list for each word


    listtools.h
    //This is the header file listtools.h. This contains type definitions and
    //function declarations for manipulating a linked list to store data of any type T.
    //The linked list is given as a pointer of type Node<T>* which points to the
    //head (first) node of the list. The implementation of the functions are given
    //in the file listtools.cpp.
    #ifndef LISTTOOLS_H
    #define LISTTOOLS_H
    
    namespace LinkedListSavitch
    {
        template<class T>
        class Node
        {
        public:
            Node(const T& theData, Node<T>* theLink) : data(theData), link(theLink){}
            Node<T>* getLink( ) const { return link; }
            const T& getData( ) const { return data; }
            void setData(const T& theData) { data = theData; }
            void setLink(Node<T>* pointer) { link = pointer; }
        private:
            T data;
            Node<T> *link;
        };
    
        template<class T>
        void headInsert(Node<T>*& head, const T& theData);
        //Precondition: The pointer variable head points to
        //the head of a linked list.
        //Postcondition: A new node containing theData
        //has been added at the head of the linked list.
    
        template<class T>
        void insert(Node<T>* afterMe, const T& theData);
        //Precondition: afterMe points to a node in a linked list.
        //Postcondition: A new node containing theData
        //has been added after the node pointed to by afterMe.
    
        template<class T>
        void deleteNode(Node<T>* before);
        //Precondition: The pointers before point to nodes that has
        //at least one node after it in the linked list.
        //Postcondition: The node after the node pointed to by before
        //has been removed from the linked list and its storage
        //returned to the freestore.
    
        template<class T>
        void deleteFirstNode(Node<T>*& head);
        //Precondition: The pointers head points to the first
        //node in a linked list; with at least one node.
        //Postcondition: The node pointed to by head has been removed
        //for the linked list and its storage returned to the freestore.
    
        template<class T>
        Node<T>* search(Node<T>* head, const T& target);
        //Precondition: The pointer head points to the head of a linked list.
        //The pointer variable in the last node is NULL. head (first) node
        //head (first) node has been defined for type T.
        //(== is used as the criterion for being equal).
        //If the list is empty, then head is NULL.
        //Returns a pointer that points to the first node that
        //is equal to the target. If no node equals the target,
        //the function returns NULL.
    }//LinkedListSavitch
    
    #endif //LISTTOOLS_H
    
    


    listtools.cpp
    //This is the implementation file listtools.cpp. This file contains
    //function definitions for the functions declared in listtools.h.
    #include <cstddef>
    #include "listtools.h"
    
    namespace LinkedListSavitch
    {
        template<class T>
        void headInsert(Node<T>*& head, const T& theData)
        {
            head = new Node<T>(theData, head);
        }
    
        template<class T>
        void insert(Node<T>* afterMe, const T& theData)
        {
            afterMe->setLink(new Node<T>(theData, afterMe->getLink( )));
        }
    
        template<class T>
        void deleteNode(Node<T>* before)
        {
            Node<T> *discard;
            discard = before->getLink( );
            before->setLink(discard->getLink( ));
            delete discard;
        }
    
        template<class T>
        void deleteFirstNode(Node<T>*& head)
        {
            Node<T> *discard;
            discard = head;
            head = head->getLink( );
            delete discard;
        }
    
        //Uses cstddef:
        template<class T>
        Node<T>* search(Node<T>* head, const T& target)
        {
            Node<T>* here = head;
    
            if (here == NULL) //if empty list
            {
                return NULL;
            }
            else
            {
                while (here->getData( ) != target && here->getLink( ) != NULL)
                    here = here->getLink( );
    
                if (here->getData( ) == target)
                    return here;
                else
                    return NULL;
            }
        }
    
    }//LinkedListSavitch
    
    


    hashtable.h
    #ifndef HASHTABLE_H
    #define HASHTABLE_H
    #include <string>
    #include "listtools.h"
    using LinkedListSavitch::Node;
    using namespace std;
    
    namespace HashTableSavitch
    {
      const int SIZE = 1000;
    
      class HashTable
      {
       public:
            HashTable(); // Initialize empty hash table
    
            // Normally a copy constructor and overloaded assignment
            // operator would be included.  They have been omitted
            // to save space.
    
            virtual ~HashTable();  // Destructor destroys hash table
    
            bool containsString(string target) const;
            // Returns true if target is in the hash table,
            // false otherwise
    
            void put(string s);
            // Adds a new string to the hash table
    
            unsigned int computeHash(string s) const;   // Compute hash value for string
    
       private:
            Node<string> *hashArray[SIZE];
    
      }; // HashTable
    } // HashTableSavitch
    #endif // HASHTABLE_H
    
    


    hashtable.cpp
    #include <string>
    #include "listtools.h"
    #include "listtools.cpp"
    #include "hashtable.h"
    
    using LinkedListSavitch::Node;
    using LinkedListSavitch::search;
    using LinkedListSavitch::headInsert;
    using namespace std;
    
    #define HASH_WEIGHT 31
    
    namespace HashTableSavitch
    {
       HashTable::HashTable()
       {
        for (int i = 0; i < SIZE; i++)
        {
         hashArray[i] = NULL;
        }
       }
    
       HashTable::~HashTable()
       {
         for (int i=0; i<SIZE; i++)
         {
           Node<string> *next = hashArray[i];
           while (next != NULL)
           {
             Node<string> *discard = next;
    	 next = next->getLink( );
    	 delete discard;
           }
         }
       }
    
       unsigned int HashTable::computeHash(string s) const
       {
        unsigned int hash = 0;
        for (unsigned int i = 0; i < s.length( ); i++)
        {
        	hash = HASH_WEIGHT * hash + s[i];
        }
        return hash % SIZE;
       }
    
       bool HashTable::containsString(string target) const
       {
        int hash = this->computeHash(target);
        Node<string>* result = search(hashArray[hash], target);
        if (result == NULL)
           return false;
        else
           return true;
       }
    
       void HashTable::put(string s)
       {
        int hash = computeHash(s);
        if (search(hashArray[hash], s) == NULL)
        {
          // Only add the target if it's not in the list
          headInsert(hashArray[hash], s);
        }
       }
    } // HashTableSavitch
    
    



    main.cpp (What I have so far)
    #include <iostream>
    #include <fstream>
    #include <cctype>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include "hashtable.h"
    using namespace std;
    using HashTableSavitch::HashTable;
    
    void upToLow(string & str);
    void removePunct(string & str);
    
    int main()
    {
    	HashTable h;
    	string currWord;
    	string word;
    	int countMisspelled = 0;
    	int countCorrect = 0;
    
    	//Get input from words.rtf
    	ifstream dictionary("words.txt");
    
    	//File checking
    	if (dictionary.fail())
    	{
    		cout << "File does not exist" << endl;
    		cout << "Exit program" << endl;
    	}
    
        //Create the dictionary as a hash table
        while(dictionary >> currWord)
        {
        	h.put(currWord);
        }
        dictionary.close();
    
    
        //Get input from gettysburg_address.txt
        ifstream input("gettysburg_address.txt");
    
    	//File checking
    	if (input.fail())
    	{
    		cout << "File does not exist" << endl;
    		cout << "Exit program" << endl;
    	}
    
    	//Spell check gettysburg_address.txt
    	cout << "Misspelled words : " << endl;
    	cout << endl;
    
    	//If a word is not in the dictionary assume misspelled
    	while(input >> word)
    	{
    		removePunct(word);
    		upToLow(word);
    		if(h.containsString(word) == false)
    		{
    			countMisspelled++; // Increment misspelled words count
    			cout << word << " ";
    			if(countMisspelled % 20 == 0) // Display misspelled words 20 per line
    			{
    				cout << endl;
    			}
    		}
    		else
    		{
    			countCorrect++; // Increment correct words count
    		}
    	}
    	input.close();
    
    	cout << endl;
    	cout << endl;
    
    	cout << "Number of misspelled words : " << countMisspelled << endl;
    	cout << "Number of correct words : " << countCorrect << endl;
    
    	return 0;
    }
    
    
    /*Function to convert uppercase letters to lowercase*/
    void upToLow(string & str)
    {
    	for (unsigned int i = 0; i < strlen(str.c_str()); i++)
    		 if (str[i] >= 0x41 && str[i] <= 0x5A)
    			  str[i] = str[i] + 0x20;
    }
    
    
    /*Function to remove punctuation from string*/
    void removePunct(string & str)
    {
    	str.erase(remove_if(str.begin(), str.end(), static_cast<int(*)(int)>(&ispunct)),str.end());
    }
    
    


    I've managed so far to spell check the text file given and display the words that are misspelled and the counts for "correct" and "misspelled". But I don't really know what I should do for counting the collisions and operations. My instructor very briefly went over hash tables and linked lists so I am quite a noob at this.

    For counting the number of collisions, would I compare the hash value for each string in "words.txt" and if the hash value is the same, increment a counter for the number of collisions? Not quite sure about this.

    I have no idea how I would go about counting the "number of operations performed". Any ideas for this?

    Help is very much appreciated.
  4. In Topic: C++ Hash Table Class Error "undefined reference to"

    Posted 29 Jul 2013

    Thank very much. I've resolved the errors now.
  5. In Topic: C++ Hash Table Class Error "undefined reference to"

    Posted 29 Jul 2013

    I might be doing something wrong from one of the above mentioned but I'm not quite sure. Here are the other files

    hashtable.h
    #ifndef HASHTABLE_H
    #define HASHTABLE_H
    #include <string>
    #include "listtools.h"
    using LinkedListSavitch::Node;
    using std::string;
    
    namespace HashTableSavitch
    {
      const int SIZE = 10;
    
      class HashTable
      {
       public:
            HashTable(); // Initialize empty hash table
    
            // Normally a copy constructor and overloaded assignment
            // operator would be included.  They have been omitted
            // to save space.
    
            virtual ~HashTable();  // Destructor destroys hash table
    
            bool containsString(string target) const;
            // Returns true if target is in the hash table,
            // false otherwise
    
            void put(string s);
            // Adds a new string to the hash table
    
       private:
            Node<string> *hashArray[SIZE];
            static int computeHash(string s);   // Compute hash value for string
      }; // HashTable
    } // HashTableSavitch
    #endif // HASHTABLE_H
    
    


    listtools.h
    #ifndef LISTTOOLS_H
    #define LISTTOOLS_H
    
    namespace LinkedListSavitch
    {
        template<class T>
        class Node
        {
        public:
            Node(const T& theData, Node<T>* theLink) : data(theData), link(theLink){}
            Node<T>* getLink( ) const { return link; }
            const T& getData( ) const { return data; }
            void setData(const T& theData) { data = theData; }
            void setLink(Node<T>* pointer) { link = pointer; }
        private:
            T data;
            Node<T> *link;
        };
    
        template<class T>
        void headInsert(Node<T>*& head, const T& theData);
        //Precondition: The pointer variable head points to
        //the head of a linked list.
        //Postcondition: A new node containing theData
        //has been added at the head of the linked list.
    
        template<class T>
        void insert(Node<T>* afterMe, const T& theData);
        //Precondition: afterMe points to a node in a linked list.
        //Postcondition: A new node containing theData
        //has been added after the node pointed to by afterMe.
    
        template<class T>
        void deleteNode(Node<T>* before);
        //Precondition: The pointers before point to nodes that has
        //at least one node after it in the linked list.
        //Postcondition: The node after the node pointed to by before
        //has been removed from the linked list and its storage
        //returned to the freestore.
    
        template<class T>
        void deleteFirstNode(Node<T>*& head);
        //Precondition: The pointers head points to the first
        //node in a linked list; with at least one node.
        //Postcondition: The node pointed to by head has been removed
        //for the linked list and its storage returned to the freestore.
    
        template<class T>
        Node<T>* search(Node<T>* head, const T& target);
        //Precondition: The pointer head points to the head of a linked list.
        //The pointer variable in the last node is NULL. head (first) node
        //head (first) node has been defined for type T.
        //(== is used as the criterion for being equal).
        //If the list is empty, then head is NULL.
        //Returns a pointer that points to the first node that
        //is equal to the target. If no node equals the target,
        //the function returns NULL.
    }//LinkedListSavitch
    
    #endif //LISTTOOLS_H
    
    


    listtools.cpp
    #include <cstddef>
    #include "listtools.h"
    
    namespace LinkedListSavitch
    {
        template<class T>
        void headInsert(Node<T>*& head, const T& theData)
        {
            head = new Node<T>(theData, head);
        }
    
        template<class T>
        void insert(Node<T>* afterMe, const T& theData)
        {
            afterMe->setLink(new Node<T>(theData, afterMe->getLink( )));
        }
    
        template<class T>
        void deleteNode(Node<T>* before)
        {
            Node<T> *discard;
            discard = before->getLink( );
            before->setLink(discard->getLink( ));
            delete discard;
        }
    
        template<class T>
        void deleteFirstNode(Node<T>*& head)
        {
            Node<T> *discard;
            discard = head;
            head = head->getLink( );
            delete discard;
        }
    
        //Uses cstddef:
        template<class T>
        Node<T>* search(Node<T>* head, const T& target)
        {
            Node<T>* here = head;
    
            if (here == NULL) //if empty list
            {
                return NULL;
            }
            else
            {
                while (here->getData( ) != target && here->getLink( ) != NULL)
                    here = here->getLink( );
    
                if (here->getData( ) == target)
                    return here;
                else
                    return NULL;
            }
        }
    
    }//LinkedListSavitch
    
    


    Spot anything wrong?

My Information

Member Title:
New D.I.C Head
Age:
Age Unknown
Birthday:
Birthday Unknown
Gender:

Contact Information

E-mail:
Private

Friends

Comments

Page 1 of 1
  1. Photo

    burakaltr Icon

    16 Feb 2013 - 17:57
    Hey check out the JAVA Forum. I've come up with an answer for your question.
Page 1 of 1