Question

Write a c++ program that does the following

Create an integer array of size 30. Assign -1 to each location in the array indicating that the array is empty. Populate half of the array with random integer values between 100 and 500 inclusive. Use the following formula in order to hash and store each number in its proper position/location. Generated Number Table Size: Should a collision occurs, use linear probing to find next available position location. Use the following probing hashing function. Generated Number 1 Table Size; Display and introduction message followed by the generated array. The generated array should be displayed in 2 lines. Each line contain 15 numbers separated by 2 spaces

Answer 1

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

using namespace std;

class Array
{
        int size;
        int *arr;
public:
    Array(int size)
    {
        arr= new int[size];
        this->size=size;
        for(int i=0;i<size;i++)
        {
            arr[i]=-1;
        }
    }
    int populateArray();
    int search(int element);
    void display();
    bool insert(int num,int *collisions);
    bool deleteElement(int num);
};

bool Array::insert(int element,int *collisions)
{
    *collisions=0;

    int generated_index = element%30;

       if(arr[generated_index] == -1)
       {
           arr[generated_index]= element;
           return true;
       }
       else
        {

            int index= generated_index;//to break later
            while(arr[++index]!=-1 )
            {
                *collisions++;
                if(index==29)
                        index=0;
                if(index==generated_index)
                    return false;;
            }
            arr[index]=element;
        }

    return true;
}

void Array::display()
{
    for(int i=0;i<size;i++)
            cout<<arr[i]<<" ";
}

int Array::search(int element)
{
    for(int i=0;i<size;i++)
            if(arr[i]==element)
                return i+1;
}
bool Array::deleteElement(int ele)
{
    for(int i=0;i<size;i++)
        if(arr[i]==ele)
        {
            arr[i]=-1;
            return true;
        }
    return false;
}

int main()
{
    int generatedNo,element,collisions,ch,ele;
    Array arr(30);

    for(int i=0;i<15;i++)
    {
        generatedNo = rand() % 500 + 100 ;
        arr.insert(generatedNo,&collisions);
    }
    do{
        cout<<"1. Add element";
        cout<<"\n2. Display";
        cout<<"\n3. Search an element";
        cout<<"\n4. Delete an element";
        cout<<"\n5. Exit";
        cout<<"\n\nEnter your choice: ";
        cin>>ch;
        switch(ch)
        {
            case 1:
                cout<<"\nEnter an element: ";
                cin>>ele;
                arr.insert(ele,&collisions);
                cout<<"\nNumber of collisions: "<<collisions;
                break;
            case 2:
                cout<<"\nContents of the array are: ";
                arr.display();
                break;
            case 3:
                cout<<"Enter an element to search(100-500): ";
                cin>>ele;
                do{
                    if(ele>=100 && ele<=500)
                        arr.search(ele);
                else
                    cout<<"Please enter a correct number";
                }while(ele>=100 && ele<=500);
                break;
            case 4:
                cout<<"\nEnter an element you want to delete(100-500): ";
                cin>>ele;
                do{
                    if(ele>=100 && ele<=500)
                        arr.deleteElelment(ele);
                    else
                        cout<<"Please enter a correct number";
                }while(ele>=100 && ele<=500);
                break;
            default:
                cout<<"\nExiting...\n";
        }
    }while(ch!=5);
    return 0;
}

Output:

℃:\Users\Mayank Bhardwaj\Desktop\array.exe 5. Exit Enter your choice: 2 Contents of the array are: -1 -1-1-1 -1 305 245 427 578 458 100 5 -1-1 434 -1 -1 -1 -1 -1 -1 141 562 381 324 564 561 567 -1 269 1. Add element 2. Display 3. Search an element 4. Delete an element 5. Exit Enter your choice: 4 Enter an element you want to delete (100-500): 5 1. Add element 2. Display 3. Search an element 4. Delete an element 5. Exit Enter your choice: 2 Contents of the array are: -1 -1-1 -1 -1 305 245 427 578 458 100 -1 -1 -1 434 1 -1 -1 1 -1 -1 141 562 381 324 564 561 567 -1 269 1. Add element 2. Display 3. Search an element 4. Delete an element 5. Exit