Thread: extra word printing

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

    extra word printing

    HI, in the output of this program an extra word is being printed .

    Enter File Name:trial.txt
    Average search length in hash table = 19
    Frequency Word
    6 the
    1 ====> wrong
    Press any key to continue . . .

    I cant understand why that is being being printed out....any ideas??

    hashTable.h
    Code:
    #ifndef _hashTable_h
    #define _hashTable_h
    
    #include <iostream>
    #include <string>
    #include <cassert>
    
    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);
            //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();
            
        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;
            //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;
            //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;
            //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;
            //Returns subscript just past end of table, i.e. tableSize.
                
        long int next(long int i) const;
            //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;
            //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
    {
    	assert(numSearches != 0);//assert that numSearches isnt 0
    	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==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;
    
    	for( int g=0; g < tableSize; g++)
    	{
    		if(status[g] ==1)
    		{
    			if(table[g].key == k)
    			{
    				found = true;
    				table[g].data++;
    				break;
    			}
    		}
    		numProbes++;
    	}
    	
    	if(found == false)//now determine where I can put in in.
    	{
    		while(status[inc] != 0)
    		{
    			inc++;
    			numProbes++;
    			if(inc == tableSize)inc=0;
    		}
    		i=inc;
    
    	}
    }
    
    template<class KeyType, class DataType>
    void hashTable<KeyType, DataType>::rehash()
    {
    	mypair<KeyType, DataType>* oldTable=table;
    	short int* oldStatus = status;
    	long int oldTableSize = tableSize;
    	bool doesIt=false;
    
    	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++)
    	{
    		if(oldStatus[j] != 0)
    		{
    			insert(oldTable[j].key, oldTable[j].data);
    		}
    
    	}
    
    	delete[] oldTable;
    	delete[] oldStatus;
    }
    
    
    
       
    
    //************************************************************************
    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;
    }
    
    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(p.key < q.key);
    
    	else
    		return (p.data > q.data);
    }
    
    
    
    //************************************************************************
    #endif
    main.cpp
    Code:
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <fstream>
    #include <cctype>
    #include <cstdlib>
    #include "hashTable.h"
    
    using namespace std;
    
    
    void nextWord(ifstream& ifs, string& word, bool& found);
    
    int main()
    {
    	char fname[20];//array to store the name of the file
    	ifstream infile1;//the infile stream
    	string word;//this while store the word
    	bool found=true;;
    	bool finder=false;
    	long int i;
    	int d=1;
    	char ch;
    	
    	hashTable<string, int>ht(0);//start off to a table of size 31
    	vector< mypair<string, int> >h;//the vector
    
    	
    	cout<< "Enter File Name:";
    	cin>>fname;
    
    	
    	
    
    	infile1.open(fname);
    
    	if(infile1.fail())
    	{
    		cerr<<"Input file <<fname << does not exist"<<endl;
    		cin.get(ch);
    		exit(1);
    	}
    
    	//after this point the whole nextWord crap occurs
    	//and the hash table is formed
    
    	while(found == true)
    	{
    		nextWord(infile1, word, found);
    
    		ht.find(word,i,finder);
    
    		if(finder == false)
    		{
    			ht.insert(word,d);
    		}
    		word.erase(word.begin(),word.end());
    		d=1;
    		finder=false;
    	}
    
    
    	//this bit of code to copy the hash table into the vector for sorting
    
    	infile1.close();
    
    	for(long int l = ht.begin(); l!= ht.end(); l = ht.next(l))
    	{
    		h.push_back(ht.element(l));
    	}
    
    	//once this is done we sort using the generic sort function of STL.
    
    	sort(&h[0],&h[h.size()]);
    
    	//and now we output
    	cout<<"Average search length in hash table = "<<ht.averageSearchLength()<<endl;
    	cout<<"Frequency"<<'\t'<<"Word"<<endl;
    	for(unsigned long int u =0; u < h.size(); u++)
    	{
    		cout<<h[u].data<<'\t'<<h[u].key<<endl;
    	}
    	system("PAUSE");
    	return 0;
    
    }
    
    void nextWord(ifstream& ifs, string& word, bool& found)
    {
    	char ch='/';
    	
    	
    
    	while( !isalpha(ch) && !ifs.fail() )
    	{
    		ifs.get(ch);
    	}
    	if(ifs.fail())found=false;
    	else
    		found=true;
    
    	while(isalpha(ch) && !ifs.fail()&& !isspace(ch))
    	{
    		word.push_back(tolower(ch));
    		ifs.get(ch);
    	}
    
    
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > nextWord(infile1, word, found);
    Try checking found before trying to find/insert the word into the hash table
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Mar 2003
    Posts
    75
    lemme try that.


    worked thanks a bunch
    Last edited by kashifk; 10-25-2003 at 04:09 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 01-23-2008, 04:22 AM
  2. Microsoft Word Automation
    By BobS0327 in forum Windows Programming
    Replies: 12
    Last Post: 11-22-2007, 05:53 PM
  3. Help with a troublesome C++ program
    By Kristina in forum C++ Programming
    Replies: 4
    Last Post: 05-18-2002, 01:28 PM
  4. length of string etc.
    By Peachy in forum C Programming
    Replies: 5
    Last Post: 09-27-2001, 12:04 PM