C++ Hash Table with Chaining: Example of input and output The following example

Question

C++ Hash Table with Chaining:

Example of input and output

The following example shows an execution of the program in interactive mode. See the input

files and output files under the testfiles folder for examples where input and output are separated.

2

i4

i2

i6

i3

o

0:6->2->4->;

1:3->;

s2

2:FOUND_AT0,1;

s4

4:FOUND_AT0,2;

d5

5:DELETE_FAILED;

d2

2:DELETED;

o

0:6->4->;

1:3->;

e

Then lines will follow starting with 'i', 's', 'd','o', or 'e'. The details are as follows: ·Use the hash function h(k) = k mod m i(key): Insert (key) into the table. For example, "i2" implies "Insert key 2 into the table." For collisions, insert the colliding key at the beginning of the linked list. You just need to insert the key and don't have to output anything in this case. · d(key): delete (key) from the table. For example. d2 implies "Delete key 2 from the table." If there are multiple elements of the same key value, delete the element of the key value that appears the earliest in the list. If the delete was successful, you have to output (key) :DELETED; If not (since there was no element with the key value), output (key) :DELETE_FAILED; · s(key): search (key) in the table. If there is an element with the key value, then you have to output (key) : FOUND_ATi,j; where i is the hash table index and j is the linked list index. If there are multiple elements with the same key value, choose the first one appearing in the linked list. If you couldn't find the key, then output (key) :NOT_FOUND; · o: output the table. Output the entire hash table. Each line should begin with the 3 and slot hash table index followed by key values in the linked list. For example, if m we inserted 3, 6, and 1 into an empty table in this order, then you should output 0:6-3-> e: nnlsh your program

Explanation / Answer

Code:

#include <iostream>
#include <list>
using namespace std;

class HashTable{
private:
list<int> *hashTable;
public:
HashTable(){
hashTable=NULL;
};

~HashTable(){
if(hashTable!=NULL){
delete [] hashTable;
}
}

void createHashTable(int size){
hashTable=new list<int>[size];
}

void insert(int key,int size){
  
hashTable[key%size].push_front(key);

}
  bool deleteKey(int key,int size){
list<int> l=hashTable[key%size]; size
list<int>::iterator it;
if(l.empty())
return false;
else{

for (it=l.begin(); it!=l.end(); ++it)
{
if(*it==key)
{
l.erase(it);
hashTable[key%size]=l;
return true;
}
}
return false;
}
}
void search(int key,int size){
list<int> l=hashTable[key%size];
list<int>::iterator it;
int index=0;
if(l.empty())
cout<<key<<":NOT_FOUND"<<endl;
else{

for (it=l.begin(); it!=l.end(); ++it)
{
if(*it==key)
{
cout<<key<<":Found_At "<<(key%size)<<","<<index<<endl;
return;
}
index++;
}
cout<<key<<":NOT_FOUND"<<endl;
}
  
}
void output(int size){
list<int> l;
list<int>::iterator it;
for(int i=0;i<size;i++){
l=hashTable[i];

if(l.empty())
{
cout<<i<<":null"<<endl;
}
else{
cout<<i<<":";
for (it=l.begin(); it!=l.end(); ++it)//print list
{
cout<< *it<<"->";
}
cout<<endl;
}
}
}

};

int main()
{
int size,key;
cin>>size;
char ch;

HashTable table;
table.createHashTable(size);
cin>>ch;
while(ch!='e'){
if(ch=='i'){
cin>>key;
table.insert(key,size);
}else if(ch=='d'){
cin>>key;
if(table.deleteKey(key,size))
cout<<key<<":DELETED"<<endl;
else
cout<<key<<":DELETE_FAILED"<<endl;
}else if(ch=='s'){
cin>>key;
table.search(key,size);
  
}else if(ch=='o'){
table.output(size);
}
  
cin>>ch;
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.