Implementing hash table adt using linked list and arrays

Question

2.00/5 (1 vote)

See more:

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.

C++

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

[Edit member="Tadit"]
Added pre tags.
[/Edit]

Posted 7-Apr-14 3:04am

Member 10006194

Updated 7-Apr-14 5:29am

SOHAM_GANDHI

v3

Add a Solution

Comments

Suk@nta 7-Apr-14 9:36am

why you are wrote that way i don't know
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*/
}
inside for loop you put return statement without any condition. so it is worthless to put forloop

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

bling · Answer 1 · 2014-04-07T13:41:00

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

C++

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

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.