Hash table implementation in C++

Question

I am trying the following code for Hash table implementation in C++. The program compiles and accepts input and then a popup appears saying " the project has stopped working and windows is checking for a solution to the problem. I feel the program is going in the infinite loop somewhere. Can anyone spot the mistake?? Please help!

    #include <iostream>
    #include <stdlib.h>
    #include <string>
    #include <sstream>

    using namespace std;

    /* Definitions as shown */
    typedef struct CellType* Position;
    typedef int ElementType;

    struct CellType{
    ElementType value;
    Position next;
    };

    /* *** Implements a List ADT with necessary functions.
    You may make use of these functions (need not use all) to implement your HashTable ADT    */          

    class List{

    private:
        Position listHead;
        int count;

    public:
        //Initializes the number of nodes in the list
        void setCount(int num){
            count = num;
        }

        //Creates an empty list
        void makeEmptyList(){
            listHead = new CellType;
            listHead->next = NULL;
        }        

        //Inserts an element after Position p
        int insertList(ElementType data, Position p){
            Position temp;
            temp = p->next;
            p->next = new CellType;
            p->next->next = temp;
            p->next->value = data;    
            return ++count;            
        }        

        //Returns pointer to the last node
        Position end(){
            Position p;
            p = listHead;
            while (p->next != NULL){
                p = p->next;
            }
            return p;            
        }

        //Returns number of elements in the list
        int getCount(){
            return count;
        }
};
class HashTable{
    private:
        List bucket[10];
        int bucketIndex;
        int numElemBucket;
        Position posInsert;
        string collision;
        bool reportCol; //Helps to print a NO for no collisions

        public:    
        HashTable(){ //constructor
            int i;
            for (i=0;i<10;i++){
                bucket[i].setCount(0);
            }
            collision = "";
            reportCol = false;
        }


            int insert(int data){
                           bucketIndex=data%10;
                            int col;

                           if(posInsert->next==NULL) 

              bucket[bucketIndex].insertList(data,posInsert);

                      else { while(posInsert->next != NULL){
                                posInsert=posInsert->next;

                               }
                           bucket[bucketIndex].insertList(data,posInsert);
                                reportCol=true;}
                                if (reportCol==true) col=1;
                                else col=0;
                                numElemBucket++;       

                                       return col ;        
            /*code to insert data into 
              hash table and report collision*/
         }

         void listCollision(int pos){
            cout<< "("<< pos<< "," << bucketIndex << "," << numElemBucket << ")"; /*codeto      generate a properly formatted 
               string to report multiple collisions*/ 
        }

        void printCollision();

     };

     int main(){

     HashTable ht;
     int i, data;


     for (i=0;i<10;i++){
        cin>>data;
       int abc= ht.insert(data);
       if(abc==1){
       ht.listCollision(i);/* code  to call insert function of HashTable ADT and if there is  a collision, use listCollision to generate the list of collisions*/
      }


   //Prints the concatenated collision list
     ht.printCollision(); 

     }}

     void HashTable::printCollision(){
      if (reportCol == false)
          cout <<"NO";
      else
          cout<<collision;
      }

The output of the program is the point where there is a collision in the hash table, thecorresponding bucket number and the number of elements in that bucket.

Answer 1

After trying dubbuging, I come to know that, while calling a constructor you are not emptying the bucket[bucketIndex].

So your Hash Table constructor should be as follow:

HashTable(){ //constructor
            int i;
            for (i=0;i<10;i++){
                bucket[i].setCount(0);
                 bucket[i].makeEmptyList();  //here we clear for first use
            }
            collision = "";
            reportCol = false;

        }

//Creates an empty list
void makeEmptyList(){
        listHead = new CellType;
        listHead->next = NULL;
    } 

Answer 2

what you can do is you can get posInsert using
bucket[bucketIndex].end()

so that posInsert-> is defined
and there is no need to
while(posInsert->next != NULL){
posInsert=posInsert->next;

because end() function is doing just that so use end() function