The goal of this assignment is to reinforce implementation of linked lists in C+

ID: 3793904 • Letter: T

Question

The goal of this assignment is to reinforce implementation of linked lists in C++. Specifically, the assignment is to implement a set using the author's implementation of linked lists. You need to implement the following set operations

union

intersection

relative complement

insertion - if the element is already in the set, then nothing happens

deletion - if the element is not in the set, then nothing happens

query to check whether an element is in a set

query to find the number of elements in a set

display the set

destructor

copy constructor

overloading assignment operator

The assignment must follow the author's guidelines of preconditions and postconditions for the functions. In addition, the efficiency of each function must be stated.

Explanation / Answer

#include<iostream>
#include<stdlib.h>
using namespace std;
//Creating a template
template<class type>
struct node
{
type data;
node *next;
};
//Creating a template class
template <class type>
class list
{
public :
//Member function
list();
int length()const;
void insert();
void remove();
void display();
int search(int);

private:
//Data member
node<type>*linklist;
int count;
};
//Function to display linked list
template<class type>
void list<type>::display(void)
{
node<type>*cur=linklist;
cout<<" The linked list is... ";
//Moves till end of the linked list
while(cur != NULL)
{
cout<<"->"<<cur->data;
//Moves to the next list
cur = cur->next;
}
}

//Function to search a data in the linked list
template<class type>
int list<type>::search(int item)
{
node<type>*cur=linklist;
//Moves till end of linked list
while(cur != NULL)
{
//If the current list data is equal to the search data then return 1
if(cur->data == item)
return 1;
else
//Otherwise move to next
cur = cur->next;
}
cout<<" Data not found ";
return 2;
}

//Constructor
template<class type>
list<type>::list()
{
count = 0;
linklist=NULL;
}

//Returns the length of the linked list
template<class type>
int list<type>::length(void)const
{
return count;
}

//Function to insert a data in the linked list
template<class type>
void list<type>::insert(void)
{
node<type>*cur=linklist;
node<type>*temp;
type item;
cout<<" Enter the data to insert...";
cin>>item;
//Checks whether the data is already available or not
//If available search function will return 1
if(search(item) == 1)
{
cout<<" Data already available cannot insert";
return;
}
//If data is not available then insert the data
temp = new node<type>;
temp->data=item;
temp->next=linklist;
linklist=temp;
//Increase the counter for number of data available
count++;
}

//Function to delete a data from the linked list
template<class type>
void list<type>::remove(void)
{
node<type>*cur=linklist;
type item;
cout<<" Enter the data to remove...";
cin>>item;
node<type>*temp;
//If the data is the first data
if(item==linklist->data)
{
temp=cur;
linklist=linklist->next;
delete temp;
count--;
return;
}
else
{
//Search whether the data is available or not
if(search(item) == 1)
{
cur->next=(cur->next)->next;
delete temp;
//Decrease the counter for number of data available in the linked list
count--;
return;
}
}
cout<<" Data not found";
}

//Main method
int main()
{
int ch;
list<int>list1;
//Loops till user enters 6
while(1)
{
cout<<" MENU ";
cout<<" 1. Insert 2. Delete 3. Length 4. Display 5. Search 6. Exit ";
cout<<" Enter your choice...";
cin>>ch;
switch(ch)
{
case 1:
list1.insert();
break;
case 2:
if(list1.length() > 0)
{
list1.remove();
}
else
cout<<" List Empty";
break;
case 3:
cout<<" Number of elements: "<<list1.length();
break;
case 4:
list1.display();
break;
case 5:
int item;
cout<<" Enter the data to search ";
cin>>item;
if(list1.search(item) == 1)
cout<<" Data "<<item<<" found";
else
cout<<" Data "<<item<<" not found";
break;
case 6:
exit(0);
default:
cout<<" invalid choice ";
}//end of switch
}//end of while
}//end of main

Output: