I am trying to implement a simple open hash in c for the sake of learning. I am getting very confused about the interaction of functions with array pointers, and I am at the end of my wits.

The code:

struct node{
    int data;
    node* next;
    node* prev;
    bool state;
    node(){
        prev = next = NULL;
        state = true;
    }
};

//state true means empty, state false  means full.
void insert(node *array,int value){
    node *current = array;
    if(array->state == true){
        array->data = value;
        array->state = false;
    } else {
        node* add = new node();
        add->data = value;
        add->state = false;
        while(current->next != NULL){
            current = current->next;
        }
        current->next =  add;
        add->prev = current;
        
    }
}

void display(node *array, int size){
    node *show = new node();
    for(int i = 0; i< size; i  ){
        if(array->state == false){
            cout<<array->data;
            show = array;
            while(show->next != NULL){
                show = show->next;
                cout<<" --> "<<show->data;
            }
            
        } else {
            cout<<"Empty.";
        }
        cout<<"\n\n";
    }
}
int main(){
    int size;
    cout<<"Enter size of the hash table: ";
    cin>>size;
    node *array = new node[size];
    int value;
    cout<<"Enter Value: ";
    cin>>value;
    int index = value%size;
    //inserting single value
    insert(&array[index],value);
    //Hash table output.
    display(array,size);
    
    return 0;
}

When I run this code, instead of showing "empty" in places where the array's state is empty, it seems as if the entire array has the same value. The problem lies in the insert function, but I cannot figure it out.

CodePudding user response：

Updated code:

void display(node *array, int size){
    node *show;
    for(int i = 0; i< size; i  ){
        if(array[i].state == false){
            cout<<array[i].data;
            show = &array[i];
            while(show->next != NULL){
                show = show->next;
                cout<<" --> "<<show->data;
            }
            
        } else {
            cout<<"Empty.";
        }
        cout<<"\n\n";
    }
}

CodePudding user response：

You can simplify this by making the Hashtable an array of pointers to Node. A nullptr then means the slot is empty and you don't have empty and full nodes. Also Nodes only need a next pointer and usually new entries are added to the beginning of the buckets instead of the end (allows duplicate entries to "replace" older ones). Inserting at the beginning of a list becomes real easy with Node **.

#include <cstddef>
#include <iostream>

struct Table {
    struct Node {
        Node * next;
        int data;
        Node(Node **prev, int data_) : next{*prev}, data{data_} {
            *prev = this;
        }
    };

    std::size_t size;
    Node **tbl;
    Table(std::size_t size_) : size{size_}, tbl{new Node*[size]} { }
    ~Table() {
        for (std::size_t i = 0; i < size;   i) {
            Node *p = tbl[i];
            while(p) {
                Node *t = p->next;
                delete p;
                p = t;
            }
        }
        delete[] tbl;
    }
    void insert(int value) {
        Node **slot = &tbl[value % size];
        new Node(slot, value);
    }
    void display() const {
        for(std::size_t i = 0; i < size; i  ) {
            std::cout << "Slot " << i << ":";
            for (const Node *node = tbl[i]; node; node = node->next) {
                std::cout << " " << node->data;
            }
            std::cout << std::endl;
        }
    }
};

int main(){
    std::size_t size;
    std::cout << "Enter size of the hash table: ";
    std::cin >> size;
    Table table{size};
    int value;
    std::cout << "Enter Value: ";
    std::cin >> value;
    //inserting single value
    table.insert(value);
    //Hash table output.
    table.display();
    
    return 0;
}