Hash Table Problems
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: Hash Table Problems

  1. #1
    Join Date
    Apr 2014
    Posts
    17

    Hash Table Problems

    I'm hoping to get some help with a few things for this homework assignment. I have included the assignment requirements below along with the my code so far. I am having trouble getting the cout statements that I commented out to work properly. And I can't figure out why the first movie in the movies.txt file displays at the end of the list in my output screen when it should only display once as the first item. I am also having trouble figuring out where and how to set up the static variable.

    Purpose
    This assignment requires that you to develop a program using the classes listed above. Specifically you will build a hash table containing movie data. The collision strategy will be to build linked lists as the array elements.

    Program Specifications
    Your program will read the data from the file named Movies.txt located in the StudentFiles1.zip file on the Connections Portal. Each record contains 2 fields separated by a space. They are:


    Fields Data Type
    Motion Picture Association Code (MPAC) Integer
    Movie Name String

    Your application program will read each record, create a Movie structure instance and place that structure instance into the hash table.

    You will need to modify the appropriate code to provide for an audit trail of the hash table construction. To accomplish this, you will use cout statements in the above class member functions. You will need to modify them to include couts, but the modifications will be relatively small. If not, you are doing it wrong. The hashing algorithm to use is:

    Index = int ( 0.618033 * MPAC) % size

    Make the array size a constant and set it to 10.

    Include a counter for the number of collisions that occurred in building the hash table. Including a static variable in the LinkedList or List class is the best method for doing that.

    See the sample audit trail below for the first 5 records on Movies.txt and the size of the hash table set to 3. This is shown for illustration only. The full file will have different locations calculated.

    1101-Casablanca is being added
    The hashed location is 2
    There was no collision loading 1101-Casablanca
    ------------------------------------------------
    1200-Duck Soup is being added
    The hashed location is 0
    There was no collision loading 1200-Duck Soup
    ------------------------------------------------
    5570-From Here to Eternity is being added
    The hashed location is 1
    There was no collision loading 5570-From Here to Eternity
    ------------------------------------------------
    6601-Wizard of Oz is being added
    The hashed location is 2
    There was a collision loading 6601-Wizard of Oz
    It collided with 1101-Casablanca
    ------------------------------------------------
    1301-Citizen Kane is being added
    The hashed location is 0
    There was a collision loading 1301-Citizen Kane
    It collided with 1200-Duck Soup
    ------------------------------------------------
    The number of collisions is 2
    Enter a MPAC to locate (0 to end): 6601
    -----------------------------------------------
    After the above is displayed, prompt the user to enter the MPAC of a movie to locate. Produce an audit trail when locating the requested movie as shown below: Make sure you list all movies that have collided at the hashed location. That may also cause you to modify one of the existing ADTs a little.

    Will search for 6601
    at the hashed location is 2
    There was a collision here with 6601-Wizard of Oz
    There was a collision here with 1101-Casablanca
    retrieved from hash table: 6601-Wizard of Oz
    -----------------------------------------------
    Enter a MPAC to locate (0 to end): 9999
    -----------------------------------------------
    Will search for 9999
    at the hashed location is 2
    There was a collision here with 6601-Wizard of Oz
    There was a collision here with 1101-Casablanca
    Could not find 9999
    -----------------------------------------------
    Enter a MPAC to locate (0 to end): 0
    The number of collisions is 2
    Press any key to continue . . .

    Movies.cpp
    Code:
    #include <iostream>
    #include <iomanip>
    #include<string>
    #include <fstream>
    #include "HashTable.h"
    using namespace std;
    
    struct Movie
    {
    	int MPAC;
    	string movieName;
    	Movie(){MPAC = 0; movieName = "Unassigned";}
    	bool operator==(const Movie& m)
    	{if(MPAC == m.MPAC)return true;return false;}
    	friend ostream& operator<< (ostream& out, const Movie& m)
    	{
    		out << m.MPAC << " - " << m.movieName << endl;
    		return out;
    	}   
    };
    
    void getData(HashTable<Movie>&);  
    void displayMovie(HashTable<Movie>);
    //  hash function prototype goes here
    int hashFunc(const Movie &);
    
    const int SIZE = 10;
    
    int main()
    {
    	HashTable<Movie> COSC3100(hashFunc, SIZE);
    	getData(COSC3100);  
    	displayMovie(COSC3100);
    	return 0;
    }
    void getData(HashTable<Movie>& clm)
    {
    	Movie movie;
    	ifstream inFile("Movies.txt");
    	if(!inFile)
    	{
    		cout << "Problem opening Movies.txt file" <<endl;
    		exit (99);
    	}
    	inFile >> movie.MPAC;
    	inFile.ignore();
    	getline(inFile, movie.movieName);
    	
    	while(!inFile.eof())
    	{
    
    		clm.insert(movie);
    		inFile >> movie.MPAC;
    		inFile.ignore();
    
    		/*cout << " is being added" << endl;*/
    		/*cout << "The hashed location is " << hashFunc(movie) << endl;
    
    		cout << "There was a collision loading " << movie << endl;
    		cout << "It collided with " <<  << endl;*/
    
    		if(movie.MPAC != 0)
    		{
    			getline(inFile, movie.movieName);
    
    			/*cout << "There was a collision loading " << movie << endl;
    			cout << "It collided with " << clm. << endl;*/
    		}
    		/*else
    			cout << "There was no collision loading " << movie << endl;*/
    	}
    }
    
    void displayMovie(HashTable<Movie> m)
    {
    	Movie movie;
    	int MPAC;
    	bool found = false;
    	cout << "Enter a MPAC to locate (0 to end): ";
    	cin >> MPAC;
    
    	while(MPAC != 0)
    	{
    		cout << "Will search for " << MPAC << endl;
    		cout << "at the hashed location " << hashFunc(movie) << endl;
    		
    		movie.MPAC = MPAC;
    		found = m.retrieve(movie);
    
    		if(found)
    			/*cout << "There was a collision here with " << endl;*/
    		else
    			cout << "Could not find " << MPAC << endl;
    			cout << "Enter a MPAC to locate (0 to end): ";
    		cin >> MPAC;
    	}
    }
    
    //  Hash function goes here
    int hashFunc(const Movie &m)
    {
    	int index = int(0.618033 * m.MPAC) % SIZE;
    	
    	/*cout << "The hashed location is " << index << endl;*/
    
    	return index;
    }

    List.h
    Code:
    // List.h -- class for a linked list as a data structure
    
    template <class DT>
    struct Node {
    	DT info;
    	Node<DT> *next;
    };
    
    template <class DT>
    class List
    {
    public:
    	List( );
    	List( const List<DT> & );
    	~List( );
    	List<DT> & operator =( const List<DT> & );
    	void insert( const DT &); // no current position after use
    	bool first( DT & );	  // returns first element of list in listEl
    										  // and current position is set to this element; 
    										  // if list is empty, returns false and there is
    										  // no current position; otherwise, returns true
    	inline bool getNext( DT & );	  // retrieves the next element of a linked list
    										  // beyond the last element that was retrieved
    										  // by first or getNext functions and returns
    										  // it in listEl;
    										  // current position is set to this element.
    										  // if no element exists at this position, 
    										  // getNext returns false and there is no 
    										  // current position; returns true otherwise	
    	bool find ( const DT & );  // returns true if element is found
    									      // returns false if element is not found
    										  // if found, found element becomes current
    										  // position in list; if not found, there is
    										  // no current position
    	bool retrieve( DT & );  // like find, except returns found element
    	bool isEmpty( ) const;				  // returns true if linked list is empty
    										  // returns false otherwise; current position
    										  // unchanged
    	void makeEmpty( );					  // no current position
    private:
    	Node<DT> *start;
    	Node<DT> *current;			  // points to node at current position	
    	inline void deepCopy( const List<DT> & );
    };
    
    // List.cpp -- function definitions for the linked list data structure
    
    #include <iostream>
    
    using namespace std;
    
    template <class DT>
    List<DT>::List( )
    {
    	start = current = NULL;
    }
    
    template <class DT>
    List<DT>::List( const List<DT> & aplist )
    {
    	deepCopy( aplist );
    }
    
    template <class DT>
    List<DT>::~List( )
    {
    	makeEmpty( );
    }
    
    template <class DT>
    List<DT> & List<DT>::operator =( const List<DT> & rlist )
    {
    	if ( this == &rlist )
    		return *this;
    	makeEmpty( );
    	deepCopy( rlist );
    	return *this;
    }
    
    // inserts at the beginning of the linked list
    // no current position after use		
    template <class DT>
    void List<DT>::insert( const DT & element )
    {
    	current = NULL;
    	Node<DT> *newNode = new Node<DT>;
    	newNode->info = element;
    	newNode->next = start;
    	start = newNode;
    	Node<DT> *ptr = start;
    	while(ptr != NULL)
    	{
    		cout << ptr->info;
    		ptr = ptr->next;
    	}
    }	
    
    // returns first element of list in listEl and current position is set to this element; 
    // if list is empty, returns false and there is no current position; 
    // otherwise, returns true
    template <class DT>
    bool List<DT>::first( DT & listEl )
    {
    	if ( start == NULL ) 
    		return false;
    
    	current = start;
    	listEl = start->info;
    	return true;
    }
    
    // retrieves the next element of a linked list beyond the last element that was retrieved
    // by first or getNext functions and returns it in listEl;
    // current position is set to this element.
    // if no element exists at this position, getNext returns false and there is no 
    // current position; returns true otherwise	
    template <class DT>
    inline bool List<DT>::getNext( DT & listEl )				  
    {
    	if ( current == NULL ) 
    		return false;
    	if ( current->next == NULL ) {
    		current = NULL;
    		return false;
    		}
    
    	current = current->next;
    	listEl = current->info;
    	return true;
    }
    
    
    // returns true if element is found; returns false if element is not found
    // if found, found element becomes current position in list; 
    // if not found, there is no current position
    template <class DT>
    bool List<DT>::find( const DT & element )
    {
    	int pass = 1;
    	DT item;
    	if ( !first( item ) )
    		return false;
    	do 
    	{
    		if ( item == element ) 
    			return true;
    	}
    	while ( getNext( item ) );
    
    	return false;
    }
    
    // returns true if element is found; returns false if element is not found
    // if found, found element becomes current position in list; 
    // if not found, there is no current position
    template <class DT>
    bool List<DT>::retrieve( DT & element )
    {
    	if ( !find( element ) )
    		return false;
    	Node<DT> *ptr = start;
    	while(ptr!=NULL)
    	{
    		cout<<ptr->info;
    		ptr=ptr->next;
    	}
    	element = current->info;
    	return true;
    }
    
    template <class DT>
    bool List<DT>::isEmpty( ) const				  
    {
    	return start == NULL;
    }
    
    template <class DT>
    void List<DT>::makeEmpty( )					  
    {
    	while ( start != NULL ) {
    		current = start;
    		start = start->next;
    		delete current;
    	}
    
    	current = NULL;
    }
    
    template <class DT>
    inline void List<DT>::deepCopy( const List<DT> & original )
    {
    	start = current = NULL;
    	if ( original.start == NULL )
    		return;
    	Node<DT> *copyptr = start = new Node<DT>;
    	Node<DT> *originalptr = original.start;
    	copyptr->info = originalptr->info;
    	if ( originalptr == original.current )
    		current = copyptr;
    	while ( originalptr->next != NULL ) {
    		originalptr = originalptr->next;
    		copyptr->next = new Node<DT>;
    		copyptr = copyptr->next;
    		copyptr->info = originalptr->info;
    		if ( originalptr == original.current )
    			current = copyptr;
    	}
    	copyptr->next = NULL;
    }

    HashTable.h
    Code:
    #include "list.h"
    
    template<class DT>
    class HashTable
    {
    public:
    	HashTable(int (*hf) (const DT &), int);    // overloaded constructor
    	HashTable(const HashTable<DT>&);    // Copy constructor
    	HashTable<DT>& operator=(const HashTable<DT>&);   // Overloaded assignment operator
    	~HashTable();    // destructor
    	bool insert(const DT &);   // insert
    	bool retrieve(DT &);   // retrieve
    private:
    	int (*hashfunc) (const DT &);   // pointer to function that user passed to the class
    	List<DT>* table;  //pointer to the array of linked lists which is the hash table
    	int size;
    	inline void deepCopy(const HashTable<DT>&);    // Deep copy
    };
    
    template<class DT>
    HashTable<DT>::HashTable(int (*hf) (const DT &), int s)
    {
    	size=s;
    	table = new List<DT>[size];
    	hashfunc = hf;
    }
    
    template <class DT>
    HashTable<DT>::HashTable(const HashTable<DT>& original)
    {
    	deepCopy(original);
    }
    
    template <class DT>
    HashTable<DT>& HashTable<DT>::operator=(const HashTable<DT>& origianl)
    {
    	if(&original == this)
    		return *this;
    	delete [] table;
    	deepCopy(original);
    	return *this;
    }
    
    template <class DT>
    inline void HashTable<DT>::deepCopy(const HashTable<DT>& original)
    {
    	size = original.size;
    	table = new List<DT>[size];
    	hashfunc = original.hashfunc;
    	for(int i = 0; i < size; i++)
    		table[i] = original.table[i];
    }
    
    template<class DT>
    HashTable<DT>::~HashTable()
    {
    	delete [] table;
    }
    
    template <class DT>
    bool HashTable<DT>::insert(const DT & newObject)
    {
    	int location = hashfunc(newObject);
    	if(location < 0 || location > size - 1)
    		return false;
    	table[location].insert(newObject);
    	return true;
    }
    
    template<class DT>
    bool HashTable<DT>::retrieve(DT & retrieved)
    {
    	int location = hashfunc(retrieved);
    	if(location < 0 || location > size - 1)
    		return false;
    	if(table[location].retrieve(retrieved))
    		return true;
    	return false;
    }

    Movies.txt
    Code:
    1101 Casablanca
    1200 Duck Soup
    5570 From Here to Eternity
    6601 Wizard of Oz
    1301 Citizen Kane
    1350 Animal House
    5102 Young Frankenstein
    5234 King Kong
    1405 My Favorite Brunette
    2200 Gone with the Wind
    3103 White Christmas
    3670 It's a Wonderful Life
    2345 Public Enemy
    2870 Jazz Singer
    4490 Doctor Zhivago
    4876 Sound of Music
    8330 Topper
    9400 Caine Mutiny
    7109 Sergeant York
    7405 It Happened One Night
    2467 Bringing Up Baby
    3411 Mr. Hobbs Builds a Dreeam Home
    4444 Terror by Night
    5555 Charlie Chan in Paris
    6666 Charlie Chan in London
    7777 The Hound of Baskersville
    8888 West Side Story
    9999 Vacation
    1111 Christmas Vacation
    2222 Road to Rio
    3333 Road to Hong Kong
    1212 A Night in Casablanca
    1313 Animal Crackers
    1414 Horse Feathers
    5111 Star Wars
    5222 Return of the Jedi
    6111 The Empire Strikes Back
    7111 Good Night Vietnam
    8111 Midnight Cowboy
    9111 The Graduate

  2. #2
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,383

    Re: Hash Table Problems

    I am having trouble getting the cout statements that I commented out to work properly.
    What trouble, how is it nor working properly - is this compile error or run-time issue? What is the error message or change from expected output?

    I can't figure out why the first movie in the movies.txt file displays at the end of the list in my output screen when it should only display once as the first item.
    What debugging of the program have you done? Where does it depart from what is expected from your design?
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #3
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,383

    Re: Hash Table Problems

    Ok. I've got your program compiled and running. From where does your output get displayed - and why do you think its wrong that casablanca displays at the end of the output? Work through the various class functions so you understand what is happening in each.

    To get the output as shown in post #1, you are going to have to modify some of the class List functions and HashTable functions so that the required output is displayed. Which, as stated in post #1, are relatively small.

    NB you can't have an if statement with no body - so the following is incorrect
    Code:
    if (a = 0)
       //cout << "a = 0\n";
    else
       cout << "a is not 0\n";
    If you want something like that you'll need
    Code:
    if (a = 0) ;
       //cout << "a = 0\n";
    else
       cout << "a is not 0\n";
    note the ; at the end of the if statement

    For the static variable, you need to define an apropriate one in the class List and then initialise it outside of any function - usually just before main().

    As this is an assignment, we can't post fully working code [see http://forums.codeguru.com/showthrea...rk-assignment] but we can provide you with help and guidance for specific c++ related questions.

    If you still have difficulties, post your updated code and we'll provide some further advice and guidance. Have fun!
    Last edited by 2kaud; April 22nd, 2014 at 06:48 PM.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  4. #4
    Join Date
    Apr 2014
    Posts
    17

    Re: Hash Table Problems

    Quote Originally Posted by 2kaud View Post
    What trouble, how is it nor working properly - is this compile error or run-time issue? What is the error message or change from expected output?
    the program runs but the output is all jumbled up and not displaying in the correct format that the teacher required.

    This is what my output looks like if: ( I know I don't have it coded correctly but am unsure what to do to fix it. For example:
    cout << "There was a collision loading " << movie << endl; I'm not sure what I should replace for "movie" with)

    The hashed location is 8
    There was a collision loading 3670 - White Christmas

    It collided with 3670 - White Christmas

    3670 - It's a Wonderful Life
    1405 - My Favorite Brunette
    is being added
    The hashed location is 9
    There was a collision loading 2345 - It's a Wonderful Life

    It collided with 2345 - It's a Wonderful Life

    2345 - Public Enemy
    2200 - Gone with the Wind
    6601 - Wizard of Oz
    is being added
    The hashed location is 3
    There was a collision loading 2870 - Public Enemy

    It collided with 2870 - Public Enemy

    2870 - Jazz Singer
    5102 - Young Frankenstein
    is being added
    The hashed location is 4
    There was a collision loading 4490 - Jazz Singer

    It collided with 4490 - Jazz Singer

    4490 - Doctor Zhivago
    5234 - King Kong
    1350 - Animal House
    1301 - Citizen Kane
    is being added
    The hashed location is 3
    There was a collision loading 4876 - Doctor Zhivago

    It collided with 4876 - Doctor Zhivago

    4876 - Sound of Music
    2870 - Jazz Singer
    5102 - Young Frankenstein
    is being added
    The hashed location is 8
    There was a collision loading 8330 - Sound of Music

    It collided with 8330 - Sound of Music

    8330 - Topper
    3670 - It's a Wonderful Life
    1405 - My Favorite Brunette
    is being added
    The hashed location is 9
    There was a collision loading 9400 - Topper

    It collided with 9400 - Topper

    9400 - Caine Mutiny
    2345 - Public Enemy
    2200 - Gone with the Wind
    6601 - Wizard of Oz
    is being added
    The hashed location is 3
    There was a collision loading 7109 - Caine Mutiny

    It collided with 7109 - Caine Mutiny

    7109 - Sergeant York
    4876 - Sound of Music
    2870 - Jazz Singer
    5102 - Young Frankenstein
    is being added
    The hashed location is 6
    There was a collision loading 7405 - Sergeant York

    It collided with 7405 - Sergeant York

    7405 - It Happened One Night
    is being added
    The hashed location is 4
    There was a collision loading 2467 - It Happened One Night

    It collided with 2467 - It Happened One Night

    2467 - Bringing Up Baby
    4490 - Doctor Zhivago
    5234 - King Kong
    1350 - Animal House
    1301 - Citizen Kane
    is being added
    The hashed location is 8
    There was a collision loading 3411 - Bringing Up Baby

    It collided with 3411 - Bringing Up Baby

    3411 - Mr. Hobbs Builds a Dreeam Home
    8330 - Topper
    3670 - It's a Wonderful Life
    1405 - My Favorite Brunette
    is being added
    The hashed location is 6
    There was a collision loading 4444 - Mr. Hobbs Builds a Dreeam Home

    It collided with 4444 - Mr. Hobbs Builds a Dreeam Home

    4444 - Terror by Night
    7405 - It Happened One Night
    is being added
    The hashed location is 3
    There was a collision loading 5555 - Terror by Night

    It collided with 5555 - Terror by Night

    5555 - Charlie Chan in Paris
    7109 - Sergeant York
    4876 - Sound of Music
    2870 - Jazz Singer
    5102 - Young Frankenstein
    is being added
    The hashed location is 9
    There was a collision loading 6666 - Charlie Chan in Paris

    It collided with 6666 - Charlie Chan in Paris

    6666 - Charlie Chan in London
    9400 - Caine Mutiny
    2345 - Public Enemy
    2200 - Gone with the Wind
    6601 - Wizard of Oz
    is being added
    The hashed location is 6
    There was a collision loading 7777 - Charlie Chan in London

    It collided with 7777 - Charlie Chan in London

    7777 - The Hound of Baskersville
    4444 - Terror by Night
    7405 - It Happened One Night
    is being added
    The hashed location is 3
    There was a collision loading 8888 - The Hound of Baskersville

    It collided with 8888 - The Hound of Baskersville

    8888 - West Side Story
    5555 - Charlie Chan in Paris
    7109 - Sergeant York
    4876 - Sound of Music
    2870 - Jazz Singer
    5102 - Young Frankenstein
    is being added
    The hashed location is 9
    There was a collision loading 9999 - West Side Story

    It collided with 9999 - West Side Story

    9999 - Vacation
    6666 - Charlie Chan in London
    9400 - Caine Mutiny
    2345 - Public Enemy
    2200 - Gone with the Wind
    6601 - Wizard of Oz
    is being added
    The hashed location is 6
    There was a collision loading 1111 - Vacation

    It collided with 1111 - Vacation

    1111 - Christmas Vacation
    7777 - The Hound of Baskersville
    4444 - Terror by Night
    7405 - It Happened One Night
    is being added
    The hashed location is 3
    There was a collision loading 2222 - Christmas Vacation

    It collided with 2222 - Christmas Vacation

    2222 - Road to Rio
    8888 - West Side Story
    5555 - Charlie Chan in Paris
    7109 - Sergeant York
    4876 - Sound of Music
    2870 - Jazz Singer
    5102 - Young Frankenstein
    is being added
    The hashed location is 9
    There was a collision loading 3333 - Road to Rio

    It collided with 3333 - Road to Rio

    3333 - Road to Hong Kong
    9999 - Vacation
    6666 - Charlie Chan in London
    9400 - Caine Mutiny
    2345 - Public Enemy
    2200 - Gone with the Wind
    6601 - Wizard of Oz
    is being added
    The hashed location is 9
    There was a collision loading 1212 - Road to Hong Kong

    It collided with 1212 - Road to Hong Kong

    1212 - A Night in Casablanca
    3333 - Road to Hong Kong
    9999 - Vacation
    6666 - Charlie Chan in London
    9400 - Caine Mutiny
    2345 - Public Enemy
    2200 - Gone with the Wind
    6601 - Wizard of Oz
    is being added
    The hashed location is 1
    There was a collision loading 1313 - A Night in Casablanca

    It collided with 1313 - A Night in Casablanca

    1313 - Animal Crackers
    1200 - Duck Soup
    is being added
    The hashed location is 3
    There was a collision loading 1414 - Animal Crackers

    It collided with 1414 - Animal Crackers

    1414 - Horse Feathers
    2222 - Road to Rio
    8888 - West Side Story
    5555 - Charlie Chan in Paris
    7109 - Sergeant York
    4876 - Sound of Music
    2870 - Jazz Singer
    5102 - Young Frankenstein
    is being added
    The hashed location is 8
    There was a collision loading 5111 - Horse Feathers

    It collided with 5111 - Horse Feathers

    5111 - Star Wars
    3411 - Mr. Hobbs Builds a Dreeam Home
    8330 - Topper
    3670 - It's a Wonderful Life
    1405 - My Favorite Brunette
    is being added
    The hashed location is 7
    There was a collision loading 5222 - Star Wars

    It collided with 5222 - Star Wars

    5222 - Return of the Jedi
    3103 - White Christmas
    is being added
    The hashed location is 6
    There was a collision loading 6111 - Return of the Jedi

    It collided with 6111 - Return of the Jedi

    6111 - The Empire Strikes Back
    1111 - Christmas Vacation
    7777 - The Hound of Baskersville
    4444 - Terror by Night
    7405 - It Happened One Night
    is being added
    The hashed location is 4
    There was a collision loading 7111 - The Empire Strikes Back

    It collided with 7111 - The Empire Strikes Back

    7111 - Good Night Vietnam
    2467 - Bringing Up Baby
    4490 - Doctor Zhivago
    5234 - King Kong
    1350 - Animal House
    1301 - Citizen Kane
    is being added
    The hashed location is 2
    There was a collision loading 8111 - Good Night Vietnam

    It collided with 8111 - Good Night Vietnam

    8111 - Midnight Cowboy
    5570 - From Here to Eternity
    is being added
    The hashed location is 0
    There was a collision loading 9111 - Midnight Cowboy

    It collided with 9111 - Midnight Cowboy

    9111 - The Graduate
    1101 - Casablanca
    is being added
    The hashed location is 0
    There was a collision loading 9111 - The Graduate

    It collided with 9111 - The Graduate

    Enter a MPAC to locate (0 to end):


    Thank you

  5. #5
    Join Date
    Apr 2014
    Posts
    17

    Re: Hash Table Problems

    I'm not even sure where these cout statements should go or if I have them in the correct spot..

    cout << " is being added" << endl;
    cout << "The hashed location is " << hashFunc(movie) << endl;

    cout << "There was a collision loading " << movie << endl;
    cout << "It collided with " << movie << endl;

    When I run the code with these statements it doesn't display correctly.

  6. #6
    Join Date
    Apr 2014
    Posts
    17

    Re: Hash Table Problems

    I was able to get some of it working properly but still need help in some spots, which I've marked with comments.
    If you could look over it and let me know if I'm on the right track, that would be great!

    Thank you!

    Code:
    void getData(HashTable<Movie>& clm)
    {
    	Movie movie;
    	ifstream inFile("Movies.txt");
    	if(!inFile)
    	{
    		cout << "Problem opening Movies.txt file" <<endl;
    		exit (99);
    	}
    	inFile >> movie.MPAC;
    	inFile.ignore();
    	getline(inFile, movie.movieName);
    	
    	while(!inFile.eof())
    	{
    
    		clm.insert(movie);
    		inFile >> movie.MPAC;
    		inFile.ignore();
    
    		cout << " is being added" << endl;
    		cout << "The hashed location is " << hashFunc(movie) << endl;
    
    		if(movie.MPAC != 0) // this isn't working because it says every movie has a collision //Need Help here
    		{
    			getline(inFile, movie.movieName);
    
    			cout << "There was a collision loading " << movie << endl;
    			/*cout << "It collided with " << NOT SURE WHAT GOES HERE << endl;*/ //Need Help here
    		}
    		else
    			cout << "There was no collision loading " << movie << endl;
    		cout << LINE << endl;
    	}
    }
    Last edited by VictorN; April 23rd, 2014 at 08:39 AM. Reason: Added CODE tags

  7. #7
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,383

    Re: Hash Table Problems

    Please use code tags when posting code as you did in your post #1.

    What has testing movie.MPAC for 0 got to do with collision? movie.MPAC is the MPAC of the movie read from the file and won't be zero (unless there is a problem with the file). Why are you replicating the lines that read from the file twice - once before the while and once within the while loop? You only need this code once within a loop.

    Hint. The test for collision and display doesn't go in this function. It goes as part of one of the List class functions. clm.insert() will return true if the item has been inserted (whether or not there has been a collision) and false if it has not (because the hash number is out of range). Thus there is no current way of determining in getData() whether there has been a collision or not.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  8. #8
    Join Date
    Apr 2014
    Posts
    17

    Re: Hash Table Problems

    I removed the replication of the lines that read from the file and kept them within the while loop and I'm still not getting the correct output. Here are the changes I made.

    Code:
    void getData(HashTable<Movie> & mov)
    {
    	Movie movie;
    	ifstream inFile("Movies.txt");
    	if(!inFile)
    	{
    		cout << "Problem opening Movies.txt file" << endl;
    		exit (99);
    	}
    	
    	
    	while(!inFile.eof())
    	{
    		mov.insert(movie);
    		inFile >> movie.MPAC;
    		inFile.ignore();
    
    		cout << " is being added" << endl;
    		cout << "The hashed location is " << hashFunc(movie) << endl;
    
    		if(movie.MPAC != 0)
    		{
    			getline(inFile, movie.movieName);
    		}
    
    		cout << LINE << endl;
    	}
    }

  9. #9
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    17,392

    Re: Hash Table Problems

    Your first call of
    Code:
    	mov.insert(movie);
    within the while loop happens before any reading from the file. Is it "by design"?
    Victor Nijegorodov

  10. #10
    Join Date
    Apr 2014
    Posts
    17

    Re: Hash Table Problems

    No, I'm not sure what order to place each line to make it work properly. I've tried moving it around and have had no luck.

    Thank you

  11. #11
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,383

    Re: Hash Table Problems

    Quote Originally Posted by elephant7 View Post
    No, I'm not sure what order to place each line to make it work properly. I've tried moving it around and have had no luck.

    Thank you
    Thinking about it logically, where should record insertion go - before the record is read, part way through reading the record or after the record has been read? Once you know this, then you know where the record insert statement should go in the code.

    Code:
    while(!inFile.eof())
    You are just checking for eof here. What about the other error file states - fail and bad? If an invalid MPAC value is encountered (eg not an integer) then fail will be set but its not eof.
    See http://www.cplusplus.com/reference/ios/ios/good/
    Last edited by 2kaud; April 23rd, 2014 at 02:04 PM.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center