1//////////////// #pragma once #include  #include  #include "LinkedListType.h" using namespace std; template  struct nodeType { Type info; nodeType *link; }; template  class linkedListIterator { public: linkedListIterator(); linkedListIterator(nodeType *ptr); Type operator*(); linkedListIterator operator++(); bool operator==(const linkedListIterator& right) const; bool operator!=(const linkedListIterator& right) const; private: nodeType *current; }; //***************** class linkedListType **************** template  class linkedListType { public: const linkedListType& operator=(const linkedListType&); void initializeList(); bool isEmptyList() const; void print() const; int length() const; void destroyList(); Type front() const; Type back() const; virtual bool search(const Type& searchItem) const = 0; virtual void insertFirst(const Type& newItem) = 0; virtual void insertLast(const Type& newItem) = 0; virtual void deleteNode(const Type& deleteItem) = 0; virtual void deleteAll(const Type& deleteItem) = 0; virtual void deleteSmallest() = 0; linkedListIterator begin(); linkedListIterator end(); linkedListType(); linkedListType(const linkedListType& otherList); ~linkedListType(); protected: int count; nodeType *first; nodeType *last; private: void copyList(const linkedListType& otherList); }; ////////////////////////////////////////////////////////////////////////////////////////////////// //***************** class linkedListIterator **************** template  linkedListIterator::linkedListIterator() { current = nullptr; } template  linkedListIterator::linkedListIterator(nodeType *ptr) { current = ptr; } template  Type linkedListIterator::operator*() { return current->info; } template  linkedListIterator linkedListIterator:: operator++() { current = current->link; return *this; } template  bool linkedListIterator::operator==(const linkedListIterator& right) const { return (current == right.current); } template  bool linkedListIterator::operator!=(const linkedListIterator& right) const { return (current != right.current); } //***************** class linkedListType **************** template  bool linkedListType::isEmptyList() const { return (first == nullptr); } template  linkedListType::linkedListType() { first = nullptr; last = nullptr; count = 0; } template  void linkedListType::destroyList() { nodeType *temp; while (first != nullptr) { temp = first; first = first->link; delete temp; } last = nullptr; count = 0; } template  void linkedListType::initializeList() { destroyList(); } template  void linkedListType::print() const { nodeType *current; current = first; while (current != nullptr) { cout << current->info << " "; current = current->link; } } template  int linkedListType::length() const { return count; } template  Type linkedListType::front() const { assert(first != nullptr); return first->info; } template  Type linkedListType::back() const { assert(last != nullptr); return last->info; } template  linkedListIterator linkedListType::begin() { linkedListIterator temp(first); return temp; } template  linkedListIterator linkedListType::end() { linkedListIterator temp(nullptr); return temp; } template  void linkedListType::copyList(const linkedListType& otherList) { nodeType *newNode; nodeType *current; if (first != nullptr) destroyList(); if (otherList.first == nullptr) { first = nullptr; last = nullptr; count = 0; } else { current = otherList.first; count = otherList.count; first = new nodeType; first->info = current->info; first->link = nullptr; last = first; current = current->link; while (current != nullptr) { newNode = new nodeType; newNode->info = current->info; newNode->link = nullptr; last->link = newNode; last = newNode; current = current->link; } } } template  linkedListType::~linkedListType() { destroyList(); } template  linkedListType::linkedListType(const linkedListType& otherList) { first = nullptr; copyList(otherList); } template  const linkedListType& linkedListType::operator=(const linkedListType& otherList) { if (this != &otherList) { copyList(otherList); } return *this; } 

2///////////////////////////////

#pragma once #include "LinkedListType.h" template  class unorderedLinkedList : public linkedListType { public: bool search(const Type& searchItem) const; void insertFirst(const Type& newItem); void insertLast(const Type& newItem); void deleteNode(const Type& deleteItem); void deleteAll(const Type& deleteItem); void deleteSmallest(); }; //////////////////////////////////////////////////////////////////////////////////////////// template  bool unorderedLinkedList::search(const Type& searchItem) const { nodeType *current; bool found = false; current = first; while (current != nullptr && !found) if (current->info == searchItem) found = true; else current = current->link; return found; } template  void unorderedLinkedList::insertFirst(const Type& newItem) { nodeType *newNode; newNode = new nodeType; newNode->info = newItem; newNode->link = first; first = newNode; count++; if (last == nullptr) last = newNode; } template  void unorderedLinkedList::insertLast(const Type& newItem) { nodeType *newNode; newNode = new nodeType; newNode->info = newItem; newNode->link = nullptr; if (first == nullptr) { first = newNode; last = newNode; count++; } else { last->link = newNode; last = newNode; count++; } } template  void unorderedLinkedList::deleteNode(const Type& deleteItem) { nodeType *current; nodeType *trailCurrent; bool found; if (first == nullptr) cout << "Cannot delete from an empty list." << endl; else { if (first->info == deleteItem) { current = first; first = first->link; count--; if (first == nullptr) last = nullptr; delete current; } else { found = false; trailCurrent = first; current = first->link; while (current != nullptr && !found) { if (current->info != deleteItem) { trailCurrent = current; current = current->link; } else found = true; } if (found) { trailCurrent->link = current->link; count--; if (last == current) last = trailCurrent; delete current; } else cout << "The item to be deleted is not in " << "the list." << endl; } } } template  void unorderedLinkedList::deleteAll(const Type& deleteItem) { nodeType *current; nodeType *trailCurrent = nullptr; if (first == nullptr) cout << "Can not delete from an empty list." << endl; else { current = first; while (current != nullptr) { if (current->info == deleteItem) { if (current == first) { first = first->link; delete current; current = first; if (first == nullptr) last = nullptr; } else { trailCurrent->link = current->link; if (current == last) last = trailCurrent; delete current; current = trailCurrent->link; } count--; } else { trailCurrent = current; current = current->link; } } } } template  void unorderedLinkedList::deleteSmallest() { nodeType *current; nodeType *trailCurrent = nullptr; nodeType *small; nodeType *trailSmall = nullptr; if (first == nullptr) cout << "Cannot delete from an empty list." << endl; else if (first->link == nullptr) { first = nullptr; delete last; last = nullptr; count = 0; } else { small = first; trailCurrent = first; current = first->link; while (current != nullptr) { if (small->info > current->info) { trailSmall = trailCurrent; small = current; } trailCurrent = current; current = current->link; } if (small == first) first = first->link; else { trailSmall->link = small->link; if (small == last) last = trailSmall; } delete small; count--; } } 

3/////////////////////////////////////////////

//Programming Exercise 2: Test Program //38 70 20 6 51 82 70 1 66 44 70 70 99 120 63 6 -999 #include "stdafx.h" #include  #include "unorderedLinkedListType.h" using namespace std; int main() { unorderedLinkedList list, otherList; int num; cout << "Enter numbers ending with -999" << endl; cin >> num; while (num != -999) { list.insertLast(num); cin >> num; } cout << endl; cout << "Enter the number at which to split list: "; cin >> num; cout << endl; list.divideAt(otherList, num); cout << "list and otherList after splitting at " << num << endl; cout << "list: "; list.print(); cout << endl; cout << "Length of list: " << list.length() << endl; cout << "otherList: "; otherList.print(); cout << endl; cout << "Length of subList: " << otherList.length() << endl; return 0; } 

(Splitting a linked list, at a given node, into two sublists) a. Add the following operation to the class linkedListType: void divideAt (11nkedListType &secondList, const Type& 1tem) //Divide the 1ist at the node with the info item into two //sublists //Postcondition: first and last point to the first and last nodes of the first subl1st secondList.first and secondList.last point to the first and last nodes of the second subl1st. Consider the following statements: unorderedLinkedList myList; unorderedLinkedList otherList; Suppose myList points to the list with the elements 34 65 18 39 27 89 12 (in this order). The statement myList.divideAt (otherList, 18) i divides myL1st into two sublists: myL1st points to the list with the elements 34 65, and otherList points to the sublist with the ele- ments 18 39 27 89 12 b. Write the definition of the function template to implement the operation divideAt. Also, write a program to test your function. Note Use the attached code as a start up point. The test program is already given in the attached files LinkedListType( unorderedLinked