C++中的哈希表实现

Hash table implementation in C++

提问by user3340866

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!

我正在尝试使用 C++ 中的哈希表实现以下代码。程序编译并接受输入，然后出现一个弹出窗口，说“项目已停止工作，Windows 正在检查问题的解决方案。我觉得程序在某个地方进入无限循环。有人能发现错误吗？？请帮忙！

    #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.

程序的输出是哈希表中发生冲突的点、对应的桶号和该桶中元素的数量。

回答by preetam

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

尝试配音后，我开始知道，在调用构造函数时，您不会清空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;
    } 

回答by Kshitiz

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

你可以做的是你可以使用
bucket[bucketIndex].end() 获得 posInsert

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

这样就定义了 posInsert->
并且不需要
while(posInsert->next != NULL){
posInsert=posInsert->next;

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

因为 end() 函数就是这样做的所以使用 end() 函数