inputting words from a file

This is a discussion on inputting words from a file within the C++ Programming forums, part of the General Programming Boards category; hi, working on a hash table here. the nextword function has to enter words from a file into the hash ...

  1. #1
    Registered User
    Join Date
    Mar 2003
    Posts
    75

    inputting words from a file

    hi, working on a hash table here. the nextword function has to enter words from a file into the hash table. For some reason it doesnt do anything. Please someone help me out.....is there something wrong with the implementation of the hash table itself.
    Here is the link to the explanation of the assignment

    http://k4shif.netfirms.com/program4/prog4.html
    hashTable.h
    Code:
    #ifndef _hashTable_h
    #define _hashTable_h
    
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    template<class KeyType, class DataType>
    struct mypair
    {   KeyType key;//words
        DataType data;//frequencies
    };
    
    template<class KeyType, class DataType>
    class hashTable
    {   
    public:
           
    	     hashTable(long int tSize = 0);//defined
            //Constructor function. Dynamically allocates the arrays, table
            //and status, with dimensions of the next prime number > tSize. 
            //Initializes the status array to show all positions in the table 
            //are empty and initializes size, tableSize, numSearches and
            //numProbes. Uses non-member function nextPrime.
            
            ~hashTable();//defined
            
            
        void find(const KeyType& k, long int& i, bool& found);
            //Looks for key, k, in table. If found then sets i to the subscript
            //where the key is located and sets found to true. If not found 
            //then sets i to the subscript where the key could be inserted
            //and sets found to false. Uses linear probing for collision 
            //resolution with inc determined from the hash value as follows: 
            //i = hash(...); inc = i; if (inc == 0) inc = tableSize - 1 ; This  
            //is a little better than always taking inc = 1. Uses non-member 
            //function hash.
      
        void insert(const KeyType& k, const DataType& d);
            //Inserts a pair with key k and data d into the table. If a pair 
            //with the same key part already occurs in the table then it prints 
            //an error message and does not insert the pair. If the table is 
            //now more than 75% full then it rehashes into a larger table. Uses 
            //the public member function find and the private member function 
            //rehash.
            
     //************************************************************************
     //The following functions provide simialr capabilties to iterators in STL.
     //They allow one to examine all elements of the hash table. You could use
     //these for example to output all elements of the hash table or to copy all 
     //elements to a vector outside the hashTable class for sorting, etc.
           
        const mypair<KeyType, DataType>& element(long int i) const;//defined
            //Returns the pair at subscript i in the table. Cannot be used
            //to assign a new value to the pair.
            
        DataType& data(long int i) const;//defined
            //Returns a reference to the data at subscript i in the table. 
            //Can be used to assign a new value to the data. 
            
        long int begin() const;//defined
            //Returns the subscript of the first element in the table; returns
            //the same value as end(), i.e. tableSize, if the table is empty.
            
        long int end() const;//defined
            //Returns subscript just past end of table, i.e. tableSize.
                
        long int next(long int i) const;//defined
            //Returns the subscript of the next element after i; if there is no 
            //next element then returns the same as end(), i.e. tableSize.
    	
    	
    
    //*************************************************************************
            
        float averageSearchLength() const;//defined
            //returns the average length of all searches numProbes/numSearches.
       
            
            
    private:
        mypair<KeyType, DataType>* table; //dynamically allocated array of pairs
        short int* status;   //dynamically allocated status array; contains 
                             //staus info: 0=empty, 1=occupied
        long int size; //number of elements in table
        long int tableSize; //size of table array
        long int numSearches; //total number of searches done in looking up keys. 
                              //Increment numSearches each time find called.
        long int numProbes;   //total number of probes done during all searches.
                              //Increment each time find looks at a spot.
                                      
        void rehash();
            //The rehash function remembers the current table, status and tableSize
            //by assigning them to local variables, oldTable, oldStatus and 
            //oldTableSize. It then dynamically allocates new table and status 
            //arrays of size the next larger prime than oldTableSize and sets 
            //tableSize to the new size. It then goes through the old table 
            //and rehashes each element into the new table using the insert 
            //function. Uses non-member function nextPrime.
    };
    
    template<class KeyType, class DataType>
    const mypair<KeyType, DataType>& 
    hashTable<KeyType, DataType>::element(long int i) const
    {   return table[i];
    }
        
    template<class KeyType, class DataType>
    DataType& hashTable<KeyType, DataType>::data(long int i) const
    {   return table[i].data;
    }  
    
    template<class KeyType, class DataType>
    long int hashTable<KeyType, DataType>::begin() const
    {   long int i = 0;
    
        while(i < tableSize && status[i] != 1)
            i++;
        return i;
    }
    
    template<class KeyType, class DataType>
    long int hashTable<KeyType, DataType>::end() const
    {   return tableSize;
    }
    
    template<class KeyType, class DataType>
    long int hashTable<KeyType, DataType>::next(long int i) const
    {   
        i++;
        while(i < tableSize && status[i] != 1)
            i++;
        return i;
    }
    
    template<class KeyType, class DataType>
    float hashTable<KeyType, DataType>::averageSearchLength()const
    {
    	return float(numProbes/numSearches);
    }
    
    
    template<class KeyType, class DataType>
    hashTable<KeyType, DataType>::hashTable(long int tSize=0)
    {
    	tableSize=nextPrime(tSize);
    	table = new mypair<KeyType, DataType>[tableSize];
    	status=new short int [tableSize];
    	for(int k=0;k<tableSize;k++)status[k]=0;
    	size=0;
    	numSearches=0;
    	numProbes=0;
    
    }
    
    template<class KeyType, class DataType>
    hashTable<KeyType, DataType>::~hashTable()
    {
    	delete [] table;
    	delete [] status;
    }
    
    template<class KeyType, class DataType>
    void hashTable<KeyType, DataType>::insert(const KeyType& k, const DataType& d)
    {
    			bool found=false;
    			long int i=0;
    
    			find( k,  i, found);
    			
    
    			if(found == true)cout<<"duplicated not allowed"<<endl;
    	
    	
    			if(found==false)
    			{	
    				table[i].data=d;
    				table[i].key=k;
    				status[i]=1;
    				size++;
    			}
    		
    	
    
    	if(size > .75*(tableSize))rehash();
    }
    
    template<class KeyType, class DataType>
    void hashTable<KeyType, DataType>::find(const KeyType& k, long int& i, bool& found)
    {
    	numSearches++;
    	i=hash(k, tableSize);
    	long int inc = i;
    
    	if(inc == 0)inc = tableSize -1;
    
    	while(status[i] != 1 && found == false)
    	{
    		if(table[inc].key==k)
    		{
    			found=true;
    			i=inc;
    			table[inc].data++;
    		}
    		inc++;
    		numProbes++;
    		if(inc == tableSize)inc=0;
    	}
    
    	if(found == false)
    	{
    		long int k =i;
    
    		while(status[k]!=0)
    		{
    			k++;
    			numProbes++;
    			if(k==tableSize)k=0;
    		}
    		i=k;
    		found=false;
    	}
    	
    }
    
    template<class KeyType, class DataType>
    void hashTable<KeyType, DataType>::rehash()
    {
    	//The rehash function remembers the current table, status and tableSize
        //by assigning them to local variables, oldTable, oldStatus and 
        //oldTableSize
    
    	mypair<KeyType, DataType> *oldTable=table;
    	short int* oldStatus = status;
    	long int oldTableSize = tableSize;
    	bool doesIt=false;
    
    	    //It then dynamically allocates new table and status 
            //arrays of size the next larger prime than oldTableSize and sets 
            //tableSize to the new size. It then goes through the old table 
            //and rehashes each element into the new table using the insert 
            //function. Uses non-member function nextPrime.
    
    	table = new mypair<KeyType, DataType>[nextPrime(oldTableSize)];
    	status = new short int[nextPrime(oldTableSize)];
    	tableSize=nextPrime(oldTableSize);
    
    	for(int h =0; h < tableSize;h++)status[h]=0;
    
    	for(int j=0; j < oldTableSize;j++)
    	{
    		while(oldStatus[j] != 0)
    		{
    			insert(oldTable[j].key, oldTable[j].data);
    		}
    
    	}
    
    	delete[] oldTable;
    	delete[] oldStatus;
    
    	
    
    
    }
    
    
    
       
    
    //************************************************************************
    //Non-member functions used in hashTable class.
    
        //This is the hash function to use for strings. If the KeyType is
        //anything other than string then this non-member function would 
        //need to be changed to hash that type of key.
    long int hash(string s, int tableSize)
    {   unsigned long int j; 
        unsigned long int sum = 0;
    
        for (j = 0; j < s.length(); j++)
            sum = (sum << 5) + s[j];
            
        return sum % tableSize;
    }
    
        //Returns the next prime >= n from a list of primes where
        //each is about twice as big as the previous one.
    long int nextPrime(long int n)
    {   long int i;
        long int p[18] = {      31,      61,     127,     251,     509,    1021,                        
                              2039,    4093,    8191,   16381,   32749,   65521,  
                            131071,  262139,  524287, 1048573, 2097143, 4194301 
                         };
    
        for (i = 0; i < 18; i++)
           if (p[i] > n) return p[i];
           
        cerr<<"Next prime too large"<<endl;
        return p[17];
    }
    
    bool operator < (const mypair<string, int>& p,const mypair<string, int>& q)
    {
    	if(p.data < q.data)return true;
    
    	else if ( p.data > q.data)return false;
    
    	else
    		return (p.key < q.key);
    }
    
    
    
    //************************************************************************
    #endif
    main file with next word
    Code:
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <fstream>
    #include <cctype>
    #include "hashTable.h"
    
    using namespace std;
    
    
    void nextWord(ifstream& ifs, string& word, bool& found);
    
    int main()
    {
    	char fname[20];
    	ifstream infile1;
    	char ch;
    	string word;
    
    	hashTable<string, int>ht(31);
    	vector< mypair<string, int> >h;
    	bool found,doesIt;
    	long int i=0;
    	int dat =1;
    
    
    	cout<< "Enter File Name:";
    	cin>>fname;
    
    	
    
    	infile1.open(fname);
    
    	if(infile1.fail())
    	{
    		cerr<<"Input file" <<fname<<"doesnt exist"<<endl;
    		cin.get(ch);
    		exit(1);
    	}
    
    	while( !infile1.fail())
    	{
    		nextWord(infile1, word, found);
    		
    			if(found == true)
    			{
    				ht.find(word, i, doesIt);
    				
    				if(doesIt == false)
    				{
    					ht.insert(word,dat); 
    				}//end of if
    			}//end of outer if
    		
    		dat=1;
    		
    	}//end of while
    	infile1.close();
    
    	for(int s = ht.begin(); s < ht.end(); s++)
    	{
    		h.push_back(ht.element(i));
    	}
    
    	sort(&h[0],&h[h.size()]);
    
    	cout<<"Average search length in hash table = " <<ht.averageSearchLength()<<endl;
    	cout<<"Frequency"<<"Word" <<endl;
    
    	for(unsigned long int i=0; i < h.size(); i++)
    	{
    		cout<<h[i].data <<   h[1].key<<endl;
    	}
    
    
    	
    
    	
    	return 0;
    
    }
    
    void nextWord(ifstream& ifs, string& word, bool& found)
    {
    	int k=0;
    	int j=0;
    	string word2;
    	getline(ifs, word2);
    	if(ifs == NULL)found=false;
    
    	else
    	{
    		found=true;
    		while(isalnum(word2[k]))k++;
    
    		while(j < k)
    		{
    			word[j]=word2[j++];
    
    		}
    
    	}
    
    }

  2. #2
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    Do you have a debugger? If so, use it to step through your code and find the error. There's too much code there for anyone to easily see the problem. If you dont have a debugger, tell me, and I'll give it a shot.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  3. #3
    Registered User
    Join Date
    Mar 2003
    Posts
    134
    thanks for that, I dont have a debugger. Actually there are a lot of comments in the code and that makes it look big, if you want i can email you the program or somthing....thanks for helping me out.

  4. #4
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    Yeah, if you could send a project file over or a zip with all the source code, that would be easier. By the way, I've never used templates or hashing before, but I'm a good programmer so I should be able to debug it. So, send away.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  5. #5
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    I have two compiling errors:
    1. In one function, you defined 'i' twice, I removed that.

    2. This code:
    Code:
    template<class KeyType, class DataType>
    hashTable<KeyType, DataType>::hashTable(long int tSize=0)
    {
    	tableSize=nextPrime(tSize);
    	table = new mypair<KeyType, DataType>[tableSize];
    	status=new short int [tableSize];
    	for(int k=0;k<tableSize;k++)status[k]=0;
    	size=0;
    	numSearches=0;
    	numProbes=0;
    }
    gives this error:
    'hashTable<KeyType,DataType>::hashTable<KeyType,Da taType>' : redefinition of default parameter : parameter 1
    I'm not sure how to resolve that, but until I do, I can't get to work.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  6. #6
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    Okay, got that error. It was the redefinition of a default parameter, that's a no no. After doing that, I got 36 warnings which I think all resulted from identifiers being too long. I believe that may be a result of interlacing templates together or something like that, just a guess there.

    I'm afraid it would take far too much effort for me to debug this code. I got an access violation after opening a text file, and I can see that your problem is likely not checking arrays correctly or similar, but it would be a long process to debug it.

    I suggest you start again and work gradually up, compiling frequently to ensure that what code you have works correctly. That way, you'll know exactly what causes the problem. Good luck!
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. seg fault at vectornew
    By tytelizgal in forum C Programming
    Replies: 2
    Last Post: 10-25-2008, 01:22 PM
  2. Basic text file encoder
    By Abda92 in forum C Programming
    Replies: 15
    Last Post: 05-22-2007, 01:19 PM
  3. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  4. Problem with malloc() and sorting words from text file
    By goron350 in forum C Programming
    Replies: 11
    Last Post: 11-30-2004, 09:01 AM
  5. System
    By drdroid in forum C++ Programming
    Replies: 3
    Last Post: 06-28-2002, 10:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21