使用链表和数组实现哈希表adt [英] Implementing hash table adt using linked list and arrays

问题描述

大家好，我在这里尝试了一些代码，但没有得到如何继续使用插入功能代码。我正在粘贴我的代码供您参考。谢谢提前。任何帮助都会很感激。

Hello people I have attempted a code here but not getting how to move forward with the insert function code. I am pasting my code for your reference.Thanks in advance.Any help would be appreciative.

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

using namespace std;

/* Definitions as shown in the lecture */
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 x)
        
        {
         //CODE 
        }
        void listCollision(int pos){
            //CODE
        }
        
        void printCollision();
            
};

int main(){
    
    HashTable ht;
    int i, data;
        
    for (i=0;i<10;i++){
        cin>>data;
        return 0;
        /*Write your code here 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;
}

添加了 pre 标签。

[/ Edit]

推荐答案

您需要一个哈希函数来将插入的值映射到存储桶索引。这是让你入门的东西。

You need a hash function to map the inserted value to a bucket index. Here's something to get you started.

#define _countof(arg) ( (sizeof arg) / (sizeof arg[0]) )

int insert(ElementType x)        
{
    int index = x % _countof(bucket); // using '%' as hash function
    bucket[index].insert(x);          // you'll need to write this.
    return 0;                         // have no idea your intent for return value.
}

您需要在List上编写一个接受元素类型的插入操作。



您上面显示的insertList操作无法使用，因为没有可公开访问的位置。

You'll need to write an insert operation on List that accepts an element type.

The insertList operation you've shown above isn't usable since there is no publicly accessible position.

这篇关于使用链表和数组实现哈希表adt的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！