IMPORTANT Create an integer array of size 30. Assign -1 to each location in the

ID: 3826073 • Letter: I

Question

IMPORTANT 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

Explanation / Answer

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

using namespace std;

const int n = 30;
int numbers[n];
int probes[n];
int no_probes[n];

void makeArrayEmpty();
void fillHalfArray();
void displayArray();
void insertNumber(int original_no, int random_no, int prob);
void displayLinearProbes();
int searchNumber(int number);

int main()
{
cout << "Hello World" << endl;

// Assign arraylist empty
makeArrayEmpty();

// Fill half of array with random values
fillHalfArray();

// Display Generated Array
displayArray();

// Display menu to users

int option = 0;
int no = 0;

while(option != 5) {

       cout << endl << endl << "....................................................................";
       cout << endl << "1. Display the generated array";
       cout << endl << "2. Search for a number ( between 100 - 500 ) in the array";
       cout << endl << "3. Insert new number ( between 100 - 500 ) in the array";
       cout << endl << "4. Delete a number ( between 100 - 500 ) from the array";
       cout << endl << "5. End the program";
       cout << endl << "....................................................................";
       cout << endl << "Choose an option : ";
       cin >> option;

       switch(option) {
           case 1 : // Display array
               displayArray();
               break;

           case 2 : // Search number
               cout << endl << "Enter number between 100 - 500 : ";
               cin >> no;

               if(no >= 100 && no <= 500) {
               int pos = searchNumber(no);
               if(pos == -1) {
               cout << endl << no << " not found in array";
               } else {
               cout << endl << no << " found on position " << pos << " (array position 0-29)";
               }
               } else {
               cout << endl << "Enter number from given range";
               }

break;

case 3 : // Insert number

cout << endl << "Enter number between 100 - 500 : ";
cin >> no;

               if(no >= 100 && no <= 500) {
               insertNumber(no, no, 0);
               } else {
               cout << endl << "Enter number from given range";
               }

break;

           case 4 : // Delete number
               cout << endl << "Enter number between 100 - 500 : ";
               cin >> no;

               if(no >= 100 && no <= 500) {
               int pos = searchNumber(no);
               if(pos == -1) {
               cout << endl << no << " not found in array";
               } else {
               cout << endl << no << " found on position " << pos << " (array position 0-29) and deleted";
               numbers[pos] = -1;
               no_probes[pos] = 0;
               }
               } else {
               cout << endl << "Enter number from given range";
               }

break;

           default : // terminate program
               option = 5;
               displayLinearProbes();
               break;
       }
   }

return 0;
}

void makeArrayEmpty() {
   for(int i=0; i<n; i++) {
       numbers[i] = -1;
       probes[i] = 0;
       no_probes[i] = 0;
   }
}

void fillHalfArray() {
   for(int i=0; i<n/2; i++) {
       int random_no = rand() % 400 + 100; // starting number 100 and ending number = 100 + 400
       insertNumber(random_no, random_no, 0);
   }
}

void displayArray() {
   cout << endl << "Generated Array : " << endl;
   for(int i=0; i<n; i++) {
       cout << numbers[i];
       if(i == 14)
           cout << endl;
       else
           cout << " ";
   }
}

void insertNumber(int original_no, int random_no, int prob) {
   int pos = random_no % n;
   probes[pos] += 1;
   prob ++ ;
   if(numbers[pos] != -1) {
       insertNumber(original_no, random_no + 1, prob);
   } else {
       numbers[pos] = original_no;
       no_probes[pos] = prob;
   }
}

void displayLinearProbes() {
   cout << endl << "Number of times position/location is hashed : " << endl;
   for(int i=0; i<n; i++) {
       cout << endl << "position " << i << " : " << probes[i];
   }

   cout << endl << endl << "Number of linear probes for each element : " << endl;
   for(int i=0; i<n; i++) {
       if(numbers[i] != -1)
           cout << endl << "number " << numbers[i] << " : " << no_probes[i];
   }
}

int searchNumber(int number) {
   int num_pos = -1;
   for(int i=0; i<n; i++) {
       int pos = (number + i) % n;
       if(numbers[pos] == number) {
           num_pos = pos;
           break;
       }
   }
   return num_pos;
}

/* Output ::::::

Generated Array :
390 -1 -1 -1 -1 215 186 127 -1 159 -1 -1 192 283 462
435 286 -1 -1 349 -1 321 -1 293 263 -1 -1 477 -1 -1

....................................................................
1. Display the generated array
2. Search for a number ( between 100 - 500 ) in the array
3. Insert new number ( between 100 - 500 ) in the array
4. Delete a number ( between 100 - 500 ) from the array
5. End the program
....................................................................
Choose an option : 3

Enter number between 100 - 500 : 300

Generated Array :
390 300 -1 -1 -1 215 186 127 -1 159 -1 -1 192 283 462
435 286 -1 -1 349 -1 321 -1 293 263 -1 -1 477 -1 -1

Enter number between 100 - 500 : 300

300 found on position 1 (array position 0-29)

Enter number between 100 - 500 : 300

Generated Array :
390 -1 -1 -1 -1 215 186 127 -1 159 -1 -1 192 283 462
435 286 -1 -1 349 -1 321 -1 293 263 -1 -1 477 -1 -1

....................................................................
1. Display the generated array
2. Search for a number ( between 100 - 500 ) in the array
3. Insert new number ( between 100 - 500 ) in the array
4. Delete a number ( between 100 - 500 ) from the array
5. End the program
....................................................................
Choose an option : 5

Number of times position/location is hashed :

position 0 : 2
position 1 : 1
position 2 : 0
position 3 : 0
position 4 : 0
position 5 : 1
position 6 : 1
position 7 : 1
position 8 : 0
position 9 : 1
position 10 : 0
position 11 : 0
position 12 : 2
position 13 : 2
position 14 : 1
position 15 : 1
position 16 : 1
position 17 : 0
position 18 : 0
position 19 : 1
position 20 : 0
position 21 : 1
position 22 : 0
position 23 : 2
position 24 : 1
position 25 : 0
position 26 : 0
position 27 : 1
position 28 : 0
position 29 : 0

Number of linear probes for each element :

number 390 : 1
number 215 : 1
number 186 : 1
number 127 : 1
number 159 : 1
number 192 : 1
number 283 : 1
number 462 : 3
number 435 : 1
number 286 : 1
number 349 : 1
number 321 : 1
number 293 : 1
number 263 : 2
number 477 : 1

Navigate

IMPORTANT C++ ONLY multiplication (Iteratively and Recursively) Write two functi

IMPORTANT INSTRUCTIONS 1. Read the Scenario below. Decide upon the appropriate c

IMPORTANT Create an integer array of size 30. Assign -1 to each location in the

Question

Explanation / Answer

Related Questions

Navigate