Question

In this assignment, you will use a Hashtable to determine the common elements in all the lists. If an element appears more than once in one or more lists, the algorithm should capture the instances the element is present in all the lists.

You are given a code that implements a Hashtable as an array of linked lists. You are also given a main function that will create an array of Lists using the input variable values that you enter. Your task is to find the common elements in all the Lists and print them. Implement your algorithm as an extension of the code in the main function, as indicated in the file.

I suggest an idea (described below) to accomplish the above objective using a Hash table. You could use this idea or any other idea (that would use a Hash table) to determine the common elements in all the Lists. You should not use any additional space (barring a Hash table and a List to store the common elements across all the Lists) that would grow with the size of the Lists and the number of Lists.

A brief description of the suggested idea is as follows:

Create and maintain a List (called CommonElementsList that will store the common elements in all the lists that are scanned until then: this is a property that will be maintained throughout the execution of the algorithm). Setup the hash table (say, 'H') using the contents of the first List in the array of Lists as well as copy the contents of the first List to the CommonElementsList.

Now, go through a loop to scan the elements in the other Lists of the array of Lists.
Before beginning to scan a particular List, empty the contents of the CommonElementsList (you could set the nextNodePtr for the head node to be null to accomplish this).
For a particular List that is scanned

If a value in the List is in the Hash table H, then remove an instance of the value from H as well as insert the value to the CommonElementsList.

After scanning a particular List
Empty the contents of the Hash table H
Fill up the Hash table H using the contents of the CommonElementsList
Print out the contents of the CommonElementsList
// This will correspond to the common elements across all the Lists scanned until then

The contents of the CommonElementsList after scanning all the Lists will be the elements that are present in all the Lists. If a value appears more than once in all the Lists, then the number of instances of the value in the CommonElementsList should correspond to the number of instances the value is present in all the Lists.

Note: As part of your deliverables, you are required to develop a pseudo code for the above idea as well as analyze its time complexity and space complexity (without taking into account the space for the Hash table and the CommonElementsList). If you are using any other idea, you should provide a brief description of the idea along with a pseudo code as well as analyze its time complexity and space complexity (without taking into account the space for the Hash table and the CommonElementsList, if you use one).

A sample screenshot is shown below (note that there are at least three instances of '1' in all the five lists, so there are three instances of '1' in the CommonElementsList; similarly, there are at least two instances of '6' in all the five lists).

Enter the number of lists: 5 Enter the number of elements per list: 25 Enter the maximum value for an element: 10 Enter the size of the hash table : 7 Elements generated in List_#0 1 1 2 4 2 3 9 4 2 7 9 7 6 5 809 70 7690 7 1 Elements generated in List # 1 3 9099 38 4 9 5 8 1 3 7 4 6 3 6 6 5 2 1 7 1 0 Elements generated in List # 2 8 1 1 3 3 399 3 4 9 1 6 8 1 4 9 6 2 8 0 1 6 10 Elements generated in List # 3 6 6 4 9 6 1 1 2 3 4 6 1 9 4 8 5 1 5 6 0 7 5 1 8 7 Elements generated in List # 4 5 1 1 2 0 8 1 5 6 8 5 6 6 8 1 9 5 2 7 6 8 7 2 7 5 Common elements from list #o to list # 1 3 9 9 9 9 8 4 9 5 1 7 4 6 6 2 1 7 10 Common elements from list # O to list # 2 8 1 1 3 9 9 4 9 1 6 40 620 Common elements from list #o to list # 3 6 6 4 9 1 1 2 3 4 1 980 Common elements from list #o to list # 4 1 1 2 0 8 1669 Common elements in all the lists 1 1 2 0 8 1 6 6 9 Press any key to continue

#include <iostream>

#include <stdlib.h> //srand, rand

#include <time.h>//clock_t, clock, CLOCKS_PER_SEC

using namespace std;

// implementing hash tables as an array of linked lists

class Node{

private:

int data;

Node* nextNodePtr;

public:

Node(){}

void setData(int d){

data = d;

}

int getData(){

return data;

}

void setNextNodePtr(Node* nodePtr){

nextNodePtr = nodePtr;

}

Node* getNextNodePtr(){

return nextNodePtr;

}

};

class List{

private:

Node *headPtr;

public:

List(){

headPtr = new Node();

headPtr->setNextNodePtr(0);

}

Node* getHeadPtr(){

return headPtr;

}

bool isEmpty(){

if (headPtr->getNextNodePtr() == 0)

return true;

return false;

}

void insert(int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

while (currentNodePtr != 0){

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(0);

prevNodePtr->setNextNodePtr(newNodePtr);

}

void insertAtIndex(int insertIndex, int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == insertIndex)

break;

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(currentNodePtr);

prevNodePtr->setNextNodePtr(newNodePtr);

}

int read(int readIndex){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == readIndex)

return currentNodePtr->getData();

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

return -1; // an invalid value indicating

// index is out of range

}

bool deleteElement(int deleteData){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

Node* nextNodePtr = headPtr;

while (currentNodePtr != 0){

if (currentNodePtr->getData() == deleteData){

nextNodePtr = currentNodePtr->getNextNodePtr();

prevNodePtr->setNextNodePtr(nextNodePtr);

return true;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return false;

}

int countList(){

Node* currentNodePtr = headPtr->getNextNodePtr();

int numElements = 0;

while (currentNodePtr != 0){

numElements++;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return numElements;

}

void IterativePrint(){

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

cout << currentNodePtr->getData() << " ";

currentNodePtr = currentNodePtr->getNextNodePtr();

}

cout << endl;

}

bool containsElement(int searchData){

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

if (currentNodePtr->getData() == searchData)

return true;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return false;

}

};

class Hashtable{

private:

List* listArray;

int tableSize;

public:

Hashtable(int size){

tableSize = size;

listArray = new List[size];

}

int getTableSize(){

return tableSize;

}

void insert(int data){

int hashIndex = data % tableSize;

listArray[hashIndex].insert(data);

}

void deleteElement(int data){

int hashIndex = data % tableSize;

//while (listArray[hashIndex].deleteElement(data));

listArray[hashIndex].deleteElement(data);

}

bool hasElement(int data){

int hashIndex = data % tableSize;

return listArray[hashIndex].containsElement(data);

}

void printHashTable(){

for (int hashIndex = 0; hashIndex < tableSize; hashIndex++){

cout << "Hash Index: " << hashIndex << " : " ;

listArray[hashIndex].IterativePrint();

}

}

void removeAllElements(){

for (int hashIndex = 0; hashIndex < tableSize; hashIndex++)

listArray[hashIndex].getHeadPtr()->setNextNodePtr(0);

}

};

int main(){

int numLists;

cout << "Enter the number of lists: ";

cin >> numLists;

int numElements;

cout << "Enter the number of elements per list: ";

cin >> numElements;

int maxValue;

cout << "Enter the maximum value for an element: ";

cin >> maxValue;

int hashTableSize;

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

cin >> hashTableSize;

cout << endl;

Hashtable hashTable(hashTableSize);

srand(time(NULL));

List* listArray = new List[numLists];

for (int listArrayIndex = 0; listArrayIndex < numLists; listArrayIndex++){

cout << "Elements generated in List # " << (listArrayIndex) << endl;

for (int index = 0; index < numElements; index++){

int value = rand() % maxValue;

listArray[listArrayIndex].insert(value);

}

listArray[listArrayIndex].IterativePrint();

}

List CommonElementsList;

for (int index = 0; index < numElements; index++){

int value = listArray[0].read(index);

hashTable.insert(value);

CommonElementsList.insert(value);

}

// Continue with the above code and implement here your algorithm to determine

// the common elements in all the lists

// Include print statements to print the common elements found

// among the lists scanned (the lists are scanned one at a time)

// as shown in the sample screenshot in the assignment description.

cout << "\nCommon elements in all the lists " << endl;

CommonElementsList.IterativePrint();

system("pause");

return 0;

}

Answer 1

Code:-

#include <iostream>
#include <stdlib.h> //srand, rand
#include <time.h>//clock_t, clock, CLOCKS_PER_SEC
using namespace std;
class Node
{
   private:
   int data;
   Node* nextNodePtr;
   public:
   Node() {}
   void setData(int d)
   {
       data = d;
   }
   int getData()
   {
       return data;
   }
   void setNextNodePtr(Node* nodePtr)
   {
       nextNodePtr = nodePtr;
   }
   Node* getNextNodePtr()
   {
       return nextNodePtr;
   }
};
class List
{
   private:
   Node *headPtr;
   public:
   List()
   {
       headPtr = new Node();
       headPtr->setNextNodePtr(0);
   }
   Node* getHeadPtr()
   {
       return headPtr;
   }
   bool isEmpty()
   {
       if (headPtr->getNextNodePtr() == 0)
           return true;
       return false;
   }
   void insert(int data)
   {
       Node* currentNodePtr = headPtr->getNextNodePtr();
       Node* prevNodePtr = headPtr;
       while (currentNodePtr != 0)
       {
           prevNodePtr = currentNodePtr;
           currentNodePtr = currentNodePtr->getNextNodePtr();
       }
       Node* newNodePtr = new Node();
       newNodePtr->setData(data);
       newNodePtr->setNextNodePtr(0);
       prevNodePtr->setNextNodePtr(newNodePtr);
   }
   void insertAtIndex(int insertIndex, int data)
   {
       Node* currentNodePtr = headPtr->getNextNodePtr();
       Node* prevNodePtr = headPtr;
       int index = 0;
       while (currentNodePtr != 0)
       {
           if (index == insertIndex)
               break;
           prevNodePtr = currentNodePtr;
           currentNodePtr = currentNodePtr->getNextNodePtr();
           index++;
       }
       Node* newNodePtr = new Node();
       newNodePtr->setData(data);
       newNodePtr->setNextNodePtr(currentNodePtr);
       prevNodePtr->setNextNodePtr(newNodePtr);
   }
   int read(int readIndex)
   {
       Node* currentNodePtr = headPtr->getNextNodePtr();
       Node* prevNodePtr = headPtr;
       int index = 0;
       while (currentNodePtr != 0)
       {
           if (index == readIndex)
               return currentNodePtr->getData();
           prevNodePtr = currentNodePtr;
           currentNodePtr = currentNodePtr->getNextNodePtr();
           index++;
       }
       return -1; // an invalid value indicating
       // index is out of range
   }
   bool deleteElement(int deleteData)
   {
       Node* currentNodePtr = headPtr->getNextNodePtr();
       Node* prevNodePtr = headPtr;
       Node* nextNodePtr = headPtr;
       while (currentNodePtr != 0)
       {
           if (currentNodePtr->getData() == deleteData)
           {
               nextNodePtr = currentNodePtr->getNextNodePtr();
               prevNodePtr->setNextNodePtr(nextNodePtr);
               return true;
           }
           prevNodePtr = currentNodePtr;
           currentNodePtr = currentNodePtr->getNextNodePtr();
       }
       return false;
   }
   int countList()
   {
       Node* currentNodePtr = headPtr->getNextNodePtr();
       int numElements = 0;
       while (currentNodePtr != 0)
       {
           numElements++;
           currentNodePtr = currentNodePtr->getNextNodePtr();
       }
       return numElements;
   }
   void IterativePrint()
   {
       Node* currentNodePtr = headPtr->getNextNodePtr();
       while (currentNodePtr != 0)
       {
           cout << currentNodePtr->getData() << " ";
           currentNodePtr = currentNodePtr->getNextNodePtr();
       }
       cout << endl;
   }
   bool containsElement(int searchData)
   {
       Node* currentNodePtr = headPtr->getNextNodePtr();
       while (currentNodePtr != 0)
       {
           if (currentNodePtr->getData() == searchData)
               return true;
           currentNodePtr = currentNodePtr->getNextNodePtr();
       }
       return false;
   }
   void removeAllElements()
   {
       headPtr->setNextNodePtr(0);
   }
};
class Hashtable
{
   private:
   List* listArray;
   int tableSize;
   public:
   Hashtable(int size)
   {
       tableSize = size;
       listArray = new List[size];
   }
   int getTableSize()
   {
       return tableSize;
   }
   void insert(int data)
   {
       int hashIndex = data % tableSize;
       listArray[hashIndex].insert(data);
   }
   void deleteElement(int data)
   {
       int hashIndex = data % tableSize;
       //while (listArray[hashIndex].deleteElement(data));
       listArray[hashIndex].deleteElement(data);
   }
   bool hasElement(int data)
   {
       int hashIndex = data % tableSize;
       return listArray[hashIndex].containsElement(data);
   }
   void printHashTable()
   {
       for (int hashIndex = 0; hashIndex < tableSize; hashIndex++)
       {
           cout << "Hash Index: " << hashIndex << " : ";
           listArray[hashIndex].IterativePrint();
       }
   }
   void removeAllElements()
   {
       for (int hashIndex = 0; hashIndex < tableSize; hashIndex++)
       listArray[hashIndex].getHeadPtr()->setNextNodePtr(0);
   }
};
int main()
{
   int numLists;
   cout << "Enter the number of lists: ";
   cin >> numLists;
   int numElements;
   cout << "Enter the number of elements per list: ";
   cin >> numElements;
   int maxValue;
   cout << "Enter the maximum value for an element: ";
   cin >> maxValue;
   int hashTableSize;
   cout << "Enter the size of the hash table: ";
   cin >> hashTableSize;
   cout << endl;
   Hashtable hashTable(hashTableSize);
   srand(time(NULL));
   List* listArray = new List[numLists];
   for (int listArrayIndex = 0; listArrayIndex < numLists; listArrayIndex++)
   {
       cout << "Elements generated in List # " << (listArrayIndex) << endl;
       for (int index = 0; index < numElements; index++)
       {
           int value = rand() % maxValue;
           listArray[listArrayIndex].insert(value);
       }
       listArray[listArrayIndex].IterativePrint();
   }
   List CommonElementsList;
   for (int index = 0; index < numElements; index++)
   {
       int value = listArray[0].read(index);
       hashTable.insert(value);
       CommonElementsList.insert(value);
   }
   // Continue with the above code and implement here your algorithm to determine
   // the common elements in all the lists
   // Include print statements to print the common elements found
   // among the lists scanned (the lists are scanned one at a time)
   // as shown in the sample screenshot in the project description.
   for (int i = 1; i < numLists; i++)
   {
       cout << "\nCommon elements from list # 0 to list "<<i<<"\n";
       CommonElementsList.removeAllElements();
       for (int j = 0; j < numElements; j++)
       {
           if (hashTable.hasElement(listArray[i].read(j)) != false)
           {
               hashTable.deleteElement(listArray[i].read(j));
               CommonElementsList.insert(listArray[i].read(j));
           }
       }
       hashTable.removeAllElements();
       int count = CommonElementsList.countList();
       for (int j = 0; j < count; j++)
       {
           hashTable.insert(CommonElementsList.read(j));
       }
       CommonElementsList.IterativePrint();
   }
   cout << "\nCommon elements in all the lists " << endl;
   CommonElementsList.IterativePrint();
   system("pause");
   return 0;
}

Output:-

C:\Users\Siva Kumar\Desktop\1.exe Enter the number of lists: 5 Enter the number of elements per list: 25 Enter the maximum value for an element: 10 Enter the size of the hash table: 7 Elements generated in List # 0 4 1 7 8 7 8 9 5 6 7 6 3 0 2 5 6 0 0 2 1 8 6 3 6 1 Elements generated in List # 1 4 0 5 5 6 6 9 8 3 1 8 1 6 2 2 8 6 7 8 6 4 8 6 9 5 Elements generated in List # 2 4 8 7 8 4 1 5 5 7 3 8 3 6 1 2 2 4 0 9 2 2 0 2 3 5 Elements generated in List # 3 4 8 3 9 7 4 2 1 17 7 6 5 0 3 8 1 1 6 6 4 7 6 10 Elements generated in List # 4 1 5 6 3 4 1 5 4 4 9 7 3 1 9 0 5 7 1 0 8 0 0 8 8 6 Common elements from list # o to list 1 4 0 5 5 6 6 9 8 3 1 8 1 6 2 2 8 6 7 6 Common elements from list # 0 to list 2 4 8 7 8 1 5 5 3 8 6 1 2 2 0 9 Common elements from list # 0 to list 3 4 8 3 9 7 2 1 1 6 5 0 8 Common elements from list # o to list 4 1 5 6 3 4 1 9 7 0 8 8 Common elements in all the lists 1 5 6 3 4 1 9 7 0 8 8 Press any key to continue .

Please UPVOTE thank you...!!!