C++ code: (1) Implement the concepts of a union, and difference as defined noted
ID: 3871860 • Letter: C
Question
C++ code:
(1) Implement the concepts of a union, and difference as defined noted in Chapter 1 questions 6, and 8 using a linked list. You should not use arrays, dynamic arrays or the STL vector or STL list classes. Note: You can follow the books definition of union (so 3 items with some duplicates + 4 items with some duplicates = 7 items with duplicates...duplicates are also allowed for the difference, per the description)
You will be linking a series of nodes together to implement a single linked list class. Define a Node as a struct that holds a character (like they did in the book) and a pointer to another Node:
struct Node {
char data;
Node* nextPtr;
};
Then define a LinkedList class which has (at a minimum) these member functions:
LinkedList();
~LinkedList();
bool insertAtFront(char value);
bool insertBeforePosition(char value, int index); //first Node after headptr is 1
//false if pos zero or out of range
bool insertAtBack(char value);
bool deleteAtFront();
bool deletePosition(int index); //first Node after headptr is 1
//false if pos zero or out of range
bool deleteAtBack();
//false if empty
friend ostream& operator << (ostream &out, LinkedList list);
Implement each of these functions to provide the correct functionality. These functions return true if successful in inserting or deleting, otherwise they return false (indicating the operation was not successful).
Finally, create an overloaded + operator to handle the Union of two linked lists and an overloaded - operator to handle the Difference of two linked lists. (similar to the rules of HW02)
Because we are dealing with pointers you should have both a LinkedList Constructor and Destructor. Remember that you do not directly call a Constructor or Destructor Function. The Destructor is automatically called when the variable loses scope or the program ends. Remember, that we are dealing with not just one dynamically allocated Node (with the new operator), but many, so you will have to start at the head of the list and go until the Node points to nullptr. Then keep deleting the previous Node pointer until there are no Nodes left to delete.
(2) To verify your LinkedList class, write a main function that takes two lines of characters from the input file input.txt (you can create two lines of characters separated by spaces) and store each line of characters into two separate linked lists. Then using these two lists, perform the Union and set Difference of the characters from the file, and print the results to the console.
(3) Please also complete an asymptotic (Big O) analysis of your insertAtFront() and insertAtBack() member functions. Place this in a file called analysis.txt.
bool insertAtFront();
bool insertBeforePosition(int
index);
bool insertAtBack();
bool deleteAtFront();
bool deleteBeforePosition(int
index);
bool deleteAtBack();
Explanation / Answer
#include<iostream>
using namespace std;
struct Node {
char data;
Node* nextPtr;
Node(char ch) {
data = ch;
nextPtr = nullptr;
}
};
class LinkedList {
private:
Node *head;
public:
LinkedList();
~LinkedList();
bool insertAtFront(char value);
bool insertBeforePosition(char value, int index); //first Node after headptr is 1
//false if pos zero or out of range
bool insertAtBack(char value);
bool deleteAtFront();
bool deletePosition(int index); //first Node after headptr is 1
//false if pos zero or out of range
bool deleteAtBack();
//false if empty
friend ostream& operator << (ostream &out, LinkedList list)
{
Node *curr = list.head;
while (curr)
{
out << curr->data << " ";
curr = curr->nextPtr;
}
return out;
}
/* A utility function that returns true if data is
present in linked list else return false */
friend bool isPresent(LinkedList li, int data)
{
Node *t = li.head;
while (t != NULL)
{
if (t->data == data)
return true;
t = t->nextPtr;
}
return false;
}
friend LinkedList& unionOfList(LinkedList& l1, LinkedList& l2)
{
LinkedList result;
Node *t1 = l1.head;
Node *t2 = l2.head;
// Insert all elements of list1 to the result list
while (t1 != NULL)
{
result.insertAtFront(t1->data);
t1 = t1->nextPtr;
}
// Insert those elements of list2 which are not
// present in result list
while (t2 != NULL)
{
if (!isPresent(result, t2->data))
result.insertAtFront(t2->data);
t2 = t2->nextPtr;
}
return result;
}
/* Function to get intersection of two linked lists
head1 and head2 */
friend LinkedList& getIntersection(LinkedList& l1, LinkedList& l2)
{
LinkedList result;
Node *t1 = l1.head;
// Traverse list1 and search each element of it in
// list2. If the element is present in list 2, then
// insert the element to result
while (t1 != nullptr)
{
if (isPresent(l2, t1->data))
result.insertAtFront(t1->data);
t1 = t1->nextPtr;
}
return result;
}
};
LinkedList::LinkedList()
{
head = nullptr;
}
LinkedList::~LinkedList()
{
delete head;
}
bool LinkedList::insertAtFront(char value)
{
Node *n = new Node(value);
if (n == nullptr)
return false;
n->nextPtr = head;
head = n;
return true;
}
bool LinkedList::insertBeforePosition(char value, int index)
{
int i = 1;
Node *prev = nullptr;
Node* curr = head;
while (curr && i < index)
{
prev = curr;
curr = curr->nextPtr;
i++;
}
if (curr == nullptr)
return false;
if (prev == nullptr)
{
insertAtFront(value);
}
else
{
Node *n = new Node(value);
if (n == nullptr)
return false;
prev->nextPtr = n;
n->nextPtr = curr;
}
return true;
}
bool LinkedList::insertAtBack(char value)
{
Node *curr = head;
while (curr->nextPtr != nullptr)
curr = curr->nextPtr;
Node *n = new Node(value);
if (n == nullptr)
return false;
else
{
curr->nextPtr = n;
return true;
}
}
bool LinkedList::deleteAtFront()
{
if (head == nullptr)
return false;
else {
Node *tmp = head;
head = head->nextPtr;
delete tmp;
}
}
bool LinkedList::deletePosition(int index)
{
int i = 1;
Node *prev = nullptr;
Node *curr = head;
while (curr && i < index)
{
prev = curr;
curr = curr->nextPtr;
}
if (curr == nullptr)
return false;
else {
if (prev == nullptr) {
Node *tmp = head;
head = head->nextPtr;
delete tmp;
}
else {
prev->nextPtr = curr->nextPtr;
delete curr;
}
return true;
}
}
bool LinkedList::deleteAtBack()
{
if (head == nullptr)
return false;
Node *prev = nullptr;
Node *curr = head;
while (curr->nextPtr)
{
prev = curr;
curr = curr->nextPtr;
}
if (prev == nullptr)
{
head = nullptr;
}
else
{
prev->nextPtr = nullptr;
}
return true;
}
int main()
{
LinkedList li1;
li1.insertAtFront('a');
li1.insertAtFront('b');
li1.insertAtFront('g');
li1.insertAtFront('k');
cout << li1 << endl;
LinkedList li2;
li2.insertAtFront('a');
li2.insertAtFront('b');
li2.insertAtFront('p');
cout << li2 << endl;
cout << "union of two list:";
cout << unionOfList(li1, li2) << endl;
cout << getIntersection(li1,li2) << endl;
system("pause");
return 0;
}
bool insertAtFront(); O(1)
bool insertBeforePosition(int index); O(n)
bool insertAtBack(); O(n)
bool deleteAtFront(); O(1)
bool deleteBeforePosition(int index); O(n)
bool deleteAtBack(); O(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.