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

程序的输出是那里是在哈希表的碰撞，thecorresponding桶数目，并在该区块的元素数量的点。

Answer 1

你可以做的是，你可以得到pos插入使用
存储桶[bucketIndex] .end（）

，使得posInsert->被定义为
并且不需要
而（posInsert-> next！= NULL）{
posInsert = posInsert-> next;

，因为最终（）函数正是这样做的所以使用end（）函数

Answer 2

试图dubbuging后，我才知道，虽然调用构造函数，你不排空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; 
    }