c++ - C++中哈希表的实现

Question

我正在尝试使用以下代码在 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;
      }

程序的输出是哈希表中发生碰撞的点、对应的桶号以及该桶中元素的个数。

Answer 1

在尝试调试之后，我了解到，在调用构造函数时，您并没有清空bucket[bucketIndex]。

因此您的哈希表构造函数应如下所示:

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;
    }