Question

Type up and get the Hash table on pages 19 - 22 to work. Show your sample test run at the bottom of your code using a multiline comment

I typed everything but the code is not working please help me fix the mistakes.

These are pages 19-22.

#include <iostream #include <iomanip> #include sstack #include <vector #include <cstdlib> #include <ctime> using namespace std; llforrandom numbers //for random numbers I IIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIIIIII HASH TABLE VITTI //hash.cpp //demonstrates hash table with linear probing class DataItem 14 public: int data; // DataItem(int newdata) //(could have more data) //data item (key) data = newData; } //constructor ) //-- //end class DataItem 23 }; 24 25 class HashTable { private: vector<DataItem hashArray: 7/vector holds hash table int arraySize; DataItem* pNonItem; //for deleted items 33 public: HashTable(int size) //constructor 39 arraySize = size; hashArray.resize(arraysize); for(int j=0; j<arraySize; j++) hashArray[j] = NULL; pNonItem = new DataItem(-1); //size the vector //initialize elements //deleted item key is -1 42 }

The code I have:

#include <iostream>

#inlcude <iomanip>

#include <stack>

#include <vector>

#include <cstdlib>

#include <ctime>

using namespace std;

//////////////////////////////HASH TABLE///////////////////////////////////////////////

//hash.cpp

//demonstrate hash table with linear probing

///////////////////////////////////////////////////////////////////////////////////////

class DataItem

{ public:

int data;

DataItem(int newData)

{data = newData;

  

}

  

};

class HashTable

{

private:

vector<DataItem*>hashArray;

int arraySize;

DataItem* pNonItem;

public:

HashTable(int size)

{

arraySize = size;

hashArray.resize(arraySize);

for(int j=0; j<arraySize;j++)

hashArray[j] = NULL;

pNonItem = new DataItem(-1);

}

void displayTable();

cout <<"Table:";

for( int j=0; j<arraySize;j++);

{

if(hashArray[j] != NULL)

cout <<hashArray[j]->data << " ";

else

cout << "**";

}

cout <<endl;

}

int hashFunc (int key)

{

return key % arraySize;

}

void insert(DataItem*pItem)

{

int key = pItem->data;

int hashVal = hashFunc(key);

while(hashArray[hashVal] !=NULL &&

hashArray[hashVal]->data != -1)

{++hashVal;

hashVal %= arraySize;

}

hashArray[hashVal] = pItem;

}

DataItem* remove(int key)

{

int hashVal = hashFunc(key);

while(hashArray[hashVal] !=NULL)

{ if(hashArray[hashVal]->data == key)

{DataItem* pTemp = hashArray[hashVal];

hashArray[hasVal] = pNonItem;

return pTemp;

}

++hashVal;

hashVal %= arraySize;

}

return Null;

}

DataItem* find(int key)

{int hashVal = hashFunc(key);

while(hashArray[hashVal !=Null )

{

if(hashArray[hashVal]->data == key)

return hashArray[hashVal];

++hashVal;

hashVal %= }

return NULL; }

int main(){

DataItem* pDataItem;

int key ,size ,n, keysPerCell;

time_t aTime;

char choice ='b';

cout << " Enter size of hash table:";

cin >> size;

cout << "Enter initial number of item:";

cin >> n;

keysPerCell = 10;

  

HashTable theHashTable(size);

srand( static_cast<unsigned>(time(&aTime)));

for (int j=0;j<n; j++)

{

aKey = rand() % (keysPerCe;;*size);

pDataItem = new DataItem(key);

theHashTable.insert(pDataItem);

}

while (choice != 'x')

{

cout<< "Enter first letter of "<<"show, inserts delete, or find:";

char choice;

cin >> choice;

switch(choice)

{

case 's':

theHashTable.displayTable();

break;

case 'i':

cout << "Enter key value to insert:";

cin >> aKey;

pDataItem = new DataItem(aKey);

theHashTable.insert(pDataItem);

break ;

case 'd':

cout << "Enter key value to delete: ";

cin >> aKey;

theHashTable.remove(aKey);

break;

case'f':

cout << "Enter key value to find:";

cin >> aKey;

pDataItem = theHashTable.find(aKey);

if(pDataItem != NULL)

cout <<"found" <<aKey <<endl;

else

cout << "Could not find" << aKey << end;

break;

default:

cout << "invalid entry/n";

}

}

}

Answer 1

--------------------------------I used Visual Studio 2013, C++ language, Console App----------------

--------------TEST CASES-----------

Test Case 1:
If the values are enter correctly output showing perfectly

D:\Hari Hash TableProject Debug\HashTableProject.exe Enter size of hash table: 5 Enter initial number of item: 1 Enter first letter of show, inserts delete, or find: s Table:******18 ** Enter first letter of show, inserts delete, or find: i Enter key value to insert: 10 Enter first letter of show, inserts delete, or find: s Table:10 ****18 ** Enter first letter of show, inserts delete, or find: i, Enter key value to insert: 5 Enter first letter of show, inserts delete, or find: di Enter key value to delete: 5 Enter first letter of show, inserts delete, or find: s Table:10 -1 **18 ** Enter first letter of show, inserts delete, or find: i Enter key value to insert: 12 Enter first letter of show, inserts delete, or find: 5 Table:10 -1 12 18 ** Enter first letter of show, inserts delete, or find: i Enter key value to insert: 15 Enter first letter of show, inserts delete, or find: s Table:10 15 12 18 ** Enter first letter of show, inserts delete, or find: f Enter key value to find: 12 Found 12 Enter first letter of show, inserts delete, or find: j Invalid entry Enter first letter of show, inserts delete, or find:

---------------------------------

Test Case 2:
If entered initial number of item is greater than hash table size, It is not showing anything.
It is because in the insert method it is looping.

ED: Hari HashTableProject Debug\HashTable Project.exe Enter size of hash table: 5 Enter initial number of item: 6

---------------------------------

Test Case 3:
If entered delete number is not in the hash table, it is not showing "not found" message.

D: Hari HashTableProject Debug\Hash Table Project.exe Enter size of hash table: 5 Enter initial number of item: 1 Enter first letter of show, inserts delete, or find: s Table:****47 **** Enter first letter of show, inserts delete, or find: i Enter key value to insert: 12 Enter first letter of show, inserts delete, or find: i Enter key value to insert: 10 Enter first letter of show. inserts delete, or find: 5 fable:10 **47 12 ** Enter first letter of show, inserts delete, or find: di Enter key value to delete: 5 Enter first letter of show, inserts delete, or find:

---------------------------------

Test Case 4:
If inserted more than hash table capacity, It is not showing any error message and no other options. It is because in the insert method it is looping.

D:\Hari Hash TableProject Debug\HashTableProject.exe Enter size of hash table: 3 Enter initial number of item: 1 Enter first letter of show, inserts delete, or find: s Table: ****26 Enter first letter of show, inserts delete, or find: i Enter key value to insert: 12 Enter first letter of show, inserts delete, or find: i Enter key value to insert: 10 Enter first letter of show, inserts delete, or find: i Enter key value to insert: 5

---------------------------------

Test Case 5:
Enter first letter of show,inserts delete or find is passed single character: then show correct error output "Invalid Entry". But when i pass two letter character like "as" it is showing unwanted error messages.

D: Hari Hash TableProject\Debug\HashTableProject.exe Enter size of hash table: 5 Enter initial number of item: 1 Enter first letter of show, inserts delete, or find: j Invalid entry Enter first letter of show, inserts delete, or find: as Invalid entry Enter first letter of show, inserts delete, or find: Table:****7 **** Enter first letter of show, inserts delete, or find:

---------------------------------

Test Case 6:
If hash table size is passed as letter or string then unexpected error is showing

- D X 2 D:\Hari Hash TableProject Debug HashTableProject.exe Enter size of hash table: a Enter initial number of item: - 0 Sign in x a |- Hash Table Project (Debugging) - Microsoft Visu... 7 Quick Launch (Ctrl+Q) FILE EDIT VIEW PROJECT BUILD DEBUG TEAM TOOLS TEST ARCHITECTURE ANALYZE WINDOW HELP 0-0 8 - 2-5- Continue - 0 - Debug - Process: [8540 HashTableProject.exe Suspend-Thread [1320] MainThread HashTableProject.cpp - X (Global Scope) - main Microsoft Visual Studio vector :. Solution Explorer Unhandled exception at Ox76A7FD62 in HashTableProject.exe: Microsoft C++ exception: stdilength_error at memory location 0.006FF500. Team Explorer Break when this exception type is thrown Open Exception Settings Break Continue gnore 100 % Output Autos - x Name Value Type arraysiz -856993460 > hashArsize) std vect -858993460 size 858993460 this 00061fa20 (hashArray{size HashTab "HashTableProject.exe' (Win32): Loaded "CA The thread ex22ac has exited with code The thread exa64 has exited with code e ( First-chance exception at @x76A7FD62 in He Unhandled exception at Ox76A7FD62 in Hashi Autos Locals Watch 1 Call Stack Breakpoi... Comman... Immediat... Output In 39 Col1 Ch 1 INS GRA 006 ENG 22.02.2010 17:32 - - Type here to search Type here to search

------------------------------------------------------------------------------------------------------------------------------------

------------------Working Old Code-------------

#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <stack>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <sstream>
#include <string>
using namespace std;

//////////////////////////////HASH TABLE///////////////////////////////////////////////

//hash.cpp

//demonstrate hash table with linear probing

///////////////////////////////////////////////////////////////////////////////////////

class DataItem
{
public:
   int data;
   DataItem(int newData)
   {
       data = newData;
   }
};

class HashTable
{
private:
   vector<DataItem*>hashArray;
   int arraySize;
   DataItem* pNonItem;
public:
   HashTable(int size)
   {
       arraySize = size;
       hashArray.resize(arraySize);
       for (int j = 0; j < arraySize; j++)
           hashArray[j] = NULL;
       pNonItem = new DataItem(-1);
   }
   void displayTable()
   {
       cout << "Table:";
       for (int j=0; j<arraySize; j++)
       {
           if (hashArray[j] != NULL)
               cout << hashArray[j]->data << " ";
           else
               cout << "**";
       }
       cout << endl;
   }

   int hashFunc(int key)
   {
       return key % arraySize;
   }

   void insert(DataItem*pItem)
   {
       int key = pItem->data;
       int hashVal = hashFunc(key);
       while (hashArray[hashVal] != NULL &&
           hashArray[hashVal]->data != -1)
       {
           ++hashVal;
           hashVal %= arraySize;
       }
       hashArray[hashVal] = pItem;
   }

   DataItem* remove(int key)
   {
       int hashVal = hashFunc(key);
       while (hashArray[hashVal] != NULL)
       {
           if (hashArray[hashVal]->data == key)
           {
               DataItem* pTemp = hashArray[hashVal];
               hashArray[hashVal] = pNonItem;
               return pTemp;
           }
           ++hashVal;
           hashVal %= arraySize;
       }
       //cout << "Entered number is not found." << endl;
       return NULL;
   }

   DataItem* find(int key)
   {
       int hashVal = hashFunc(key);
       while (hashArray[hashVal] != NULL)
       {
           if (hashArray[hashVal]->data == key)
               return hashArray[hashVal];
           ++hashVal;
           hashVal %= arraySize;
       }
       return NULL;
   }
};

int main(){
   DataItem* pDataItem;
   int aKey, keysPerCell;
   string stringSize, stringN;
   int intSize;
   int intN;
   time_t aTime;
   char choice = 'b';
   cout << "Enter size of hash table: ";
   cin >> stringSize;

   istringstream iss1(stringSize);
   iss1 >> intSize;
   if (iss1.fail()) {
       cout << "Please enter numeric values" << endl;
       system("pause");
       return 0;
   }
   cout << "Enter initial number of item less than or equal to hash table size " << intSize << ": ";
   cin >> stringN;

   istringstream iss2(stringN);
   iss2 >> intN;
   if (iss2.fail()) {
       cout << "Please enter numeric values" << endl;
       system("pause");
       return 0;
   }
   keysPerCell = 10;

   if (intN > intSize)
   {
       cout << "Please enter number less than or equal to hash table size." << endl;
       system("pause");
       return 0;
   }

   HashTable theHashTable(intSize);
   srand(static_cast<unsigned>(time(&aTime)));
   for (int j = 0; j<intN; j++)
   {
       aKey = rand() % (keysPerCell*intSize);
       pDataItem = new DataItem(aKey);
       theHashTable.insert(pDataItem);
   }
   while (choice != 'x')
   {
       char choice = NULL;
       cout << "Enter first letter of " << "show, inserts delete, or find: ";
       cin >> choice;
       int length = sizeof(choice);
       if ((choice >= 65 && choice <= 90) || (choice >= 97 && choice <= 122))
           cout << " Alphabet ";
       switch (choice)
       {
       case 's':
           theHashTable.displayTable();
           break;
       case 'i':
           cout << "Enter key value to insert: ";
           cin >> aKey;
           pDataItem = new DataItem(aKey);
           theHashTable.insert(pDataItem);
           break;
       case 'd':
           cout << "Enter key value to delete: ";
           cin >> aKey;
           theHashTable.remove(aKey);
           break;
       case'f':
           cout << "Enter key value to find: ";
           cin >> aKey;
           pDataItem = theHashTable.find(aKey);
           if (pDataItem != NULL)
               cout << "Found " << aKey << endl;
           else
               cout << "Could not find " << aKey << endl;
           break;
       default:
           cout << "Invalid entry\n";
           break;
       }
   }
}

------------------Working New Code, Solved test cases problem-------------

#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <stack>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <sstream>
#include <string>
using namespace std;

//////////////////////////////HASH TABLE///////////////////////////////////////////////

//hash.cpp

//demonstrate hash table with linear probing

///////////////////////////////////////////////////////////////////////////////////////

class DataItem
{
public:
   int data;
   DataItem(int newData)
   {
       data = newData;
   }
};

class HashTable
{
private:
   vector<DataItem*>hashArray;
   int arraySize;
   DataItem* pNonItem;
public:
   HashTable(int size)
   {
       arraySize = size;
       hashArray.resize(arraySize);
       for (int j = 0; j < arraySize; j++)
           hashArray[j] = NULL;
       pNonItem = new DataItem(-1);
   }
   void displayTable()
   {
       cout << "Table:";
       for (int j=0; j<arraySize; j++)
       {
           if (hashArray[j] != NULL)
               cout << hashArray[j]->data << " ";
           else
               cout << "**";
       }
       cout << endl;
   }

   int hashFunc(int key)
   {
       return key % arraySize;
   }

   DataItem* insert(DataItem*pItem)
   {
       int count = 0;
       int key = pItem->data;
       int hashVal = hashFunc(key);
       while (hashArray[hashVal] != NULL &&
           hashArray[hashVal]->data != -1)
       {
           ++hashVal;
           hashVal %= arraySize;
           if (++count == arraySize)
           {
               return NULL;
           }
       }
       hashArray[hashVal] = pItem;
       DataItem* pTemp = hashArray[hashVal];
       return pTemp;
   }

   DataItem* remove(int key)
   {
       int count = 0;
       int hashVal = hashFunc(key);
       while (hashArray[hashVal] != NULL)
       {
           if (hashArray[hashVal]->data == key)
           {
               DataItem* pTemp = hashArray[hashVal];
               hashArray[hashVal] = pNonItem;
               return pTemp;
           }
           ++hashVal;
           hashVal %= arraySize;
           if (++count == arraySize)
           {
               return NULL;
           }
       }
       return NULL;
   }

   DataItem* find(int key)
   {
       int hashVal = hashFunc(key);
       while (hashArray[hashVal] != NULL)
       {
           if (hashArray[hashVal]->data == key)
               return hashArray[hashVal];
           ++hashVal;
           hashVal %= arraySize;
       }
       return NULL;
   }
};

int main(){
   DataItem* pDataItem;
   int aKey, keysPerCell;
   string stringSize, stringN;
   int intSize;
   int intN;
   time_t aTime;
   char choice = 'b';
   cout << "Enter size of hash table: ";
   cin >> stringSize;

   istringstream iss1(stringSize);
   iss1 >> intSize;
   if (iss1.fail()) {
       cout << "Invalid input!!! Please enter numeric values" << endl;
       system("pause");
       return 0;
   }
   cout << "Enter initial number of item less than or equal to hash table size " << intSize << ": ";
   cin >> stringN;

   istringstream iss2(stringN);
   iss2 >> intN;
   if (iss2.fail()) {
       cout << "Invalid input!!! Please enter numeric values" << endl;
       system("pause");
       return 0;
   }
   keysPerCell = 10;

   if (intN > intSize)
   {
       cout << "Please enter number less than or equal to hash table size." << endl;
       system("pause");
       return 0;
   }

   HashTable theHashTable(intSize);
   srand(static_cast<unsigned>(time(&aTime)));
   for (int j = 0; j<intN; j++)
   {
       aKey = rand() % (keysPerCell*intSize);
       pDataItem = new DataItem(aKey);
       theHashTable.insert(pDataItem);
   }
   while (choice != 'x')
   {
       string stringChoice = "";
       char choice = NULL;
       cout << "Enter first letter of " << "show, inserts delete, or find: ";
       cin >> stringChoice;
       int length = stringChoice.length();

       choice = stringChoice[0];

       if (length > 1 || choice >= 48 && choice <= 57)
       {
           cout << "Invalid input!!! Please enter one letter." << endl;
           continue;
       }

       switch (choice)
       {
       case 's':
           theHashTable.displayTable();
           break;
       case 'i':
           cout << "Enter key value to insert: ";
           cin >> aKey;
           pDataItem = new DataItem(aKey);
           pDataItem = theHashTable.insert(pDataItem);
           if (pDataItem != NULL)
               cout << aKey << " inserted successfully " << endl;
           else
               cout << "Hash table is full!" << endl;
           break;
       case 'd':
           cout << "Enter key value to delete: ";
           cin >> aKey;
           pDataItem = theHashTable.remove(aKey);
           if (pDataItem != NULL)
               cout << aKey << " deleted successfully " << endl;
           else
               cout << "Entered key is not found!" << endl;
           break;
       case'f':
           cout << "Enter key value to find: ";
           cin >> aKey;
           pDataItem = theHashTable.find(aKey);
           if (pDataItem != NULL)
               cout << "Found " << aKey << endl;
           else
               cout << "Could not find " << aKey << endl;
           break;
       default:
           cout << "Invalid entry\n";
           break;
       }
   }
}

------------New code Screenshot---------------

Test Case 2: SOLVED
If entered initial number of item is greater than hash table size, It is not showing anything.
It is because in the insert method it is looping.

D:\Hari HashTableProject Debug\HashTableProject.exe Enter size of hash table: 5 Enter initial number of item less than or equal to hash table size 5: 6 Please enter number less than or equal to hash table size. Press any key to continue ...

---------------------------------

Test Case 3:
If entered delete number is not in the hash table, it is not showing "not found" message.

ID: Hari HashTableProject\Debug\HashTableProject.exe Enter size of hash table: 5 Enter initial number of item less than or equal to hash table size 5: 5 Enter first letter of show, inserts delete, or find: s Table:35 31 45 18 49 Enter first letter of show, inserts delete, or find: d Enter key value to delete: 45 45 deleted successfully Enter first letter of show, inserts delete, or find: d Enter key value to delete: 10 Entered key is not found! Enter first letter of show, inserts delete, or find:

---------------------------------

Test Case 4:
If inserted more than hash table capacity, It is not showing any error message and no other options. It is because in the insert method it is looping.

ID: Hari HashTableProject Debug\HashTableProject.exe Enter size of hash table: 5 Enter initial number of item less than or equal to hash table size 5: 4 Enter first letter of show, inserts delete, or find: s Table:**26 46 8 11 Enter first letter of show, inserts delete, or find: i Enter key value to insert: 15 15 inserted successfully Enter first letter of show, inserts delete, or find: i Enter key value to insert: 25 Hash table is full! Enter first letter of show, inserts delete, or find:

---------------------------------

Test Case 5:
Enter first letter of show,inserts delete or find is passed single character: then show correct error output "Invalid Entry". But when i pass two letter character like "as" it is showing unwanted error messages.

DA Hari Hash TableProject\Debug\HashTableProject.exe Enter size of hash table: 5 Enter initial number of item less than or equal to hash table size 5: 5 Enter first letter of show, inserts delete, or find: j Invalid entry first letter of show, inserts delete, or find: asd Invalid input!!! Please enter one letter. r first letter of show, inserts delete, or find: 1 Invalid input!!! Please enter one letter. Enter first letter of show, inserts delete, or find: aq Invalid input!!! Please enter one letter. Enter first letter of show, inserts delete, or find: h Invalid entry Enter first letter of show, inserts delete, or find: a Invalid entry Enter first letter of show, inserts delete, or find: s Table:35 16 35 17 43 Enter first letter of show, inserts delete, or find:

---------------------------------

Test Case 6:
If hash table size is passed as letter or string then unexpected error is showing

D: Hari HashTableProject Debug\Hash Table Project.exe Enter size of hash table: asd Invalid input!!! Please enter numeric values Press any key to continue . ...