a. Add the following operation to the class orderedLinkedList: void mergeLists(o
ID: 3776599 • Letter: A
Question
a. Add the following operation to the class orderedLinkedList: void mergeLists(orderedLinkedList &list1, orderedLinkedList &list2); //This function creates a new list by merging the //elements of list1 and list2. //Postcondition: first points to the merged list; list1 // and list2 are empty Example: Consider the following statements: orderedLinkedList newList; orderedLinkedList list1; orderedLinkedList list2; Suppose list1 points to the list with the elements 2 6 7 and list2 points to the list with the elements 3 5 8. The statement: newList.mergeLists(list1, list2); 350 | Chapter 5: Linked Lists creates a new linked list with the elements in the order 2 3 5 6 7 8 and the object newList points to this list. Also, after the preceding statement executes, list1 and list2 are empty.
b. Write the definition of the function template mergeLists to implement the operation mergeLists. Also write a program to test your function
Explanation / Answer
Explanations for each line of code is given
Code to copy:
#ifndef H_orderedListType
#define H_orderedListType
#include "linkedListType.h"
#include <iostream>
using namespace std;
template <class Type>
class orderedLinkedList: public linkedListType<Type>
{
public:
bool search(const Type& searchItem) const;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the list,
// otherwise the value false is returned.
void insert(const Type& newItem);
//Function to insert newItem in the list.
//Postcondition: first points to the new list, newItem
// is inserted at the proper place in the
// list, and count is incremented by 1.
void insertFirst(const Type& newItem);
//Function to insert newItem at the beginning of the list.
//Postcondition: first points to the new list, newItem is
// inserted at the beginning of the list,
// last points to the last node in the
// list, and count is incremented by 1.
void insertLast(const Type& newItem);
//Function to insert newItem at the end of the list.
//Postcondition: first points to the new list, newItem
// is inserted at the end of the list,
// last points to the last node in the
// list, and count is incremented by 1.
void deleteNode(const Type& deleteItem);
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the list;
// first points to the first node of the
// new list, and count is decremented by 1.
// If deleteItem is not in the list, an
// appropriate message is printed.
};
template <class Type>
bool orderedLinkedList<Type>::search(const Type& searchItem) const
{
bool found = false;
nodeType<Type> *current; //pointer to traverse the list
current = first; //start the search at the first node
while (current != NULL && !found)
if (current->info >= searchItem)
found = true;
else
current = current->link;
if (found)
found = (current->info == searchItem); //test for equality
return found;
}//end search
template <class Type>
void orderedLinkedList<Type>::insert(const Type& newItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
nodeType<Type> *newNode; //pointer to create a node
bool found;
newNode = new nodeType<Type>; //create the node
newNode->info = newItem; //store newItem in the node
newNode->link = NULL; //set the link field of the node
//to NULL
if (first == NULL) //Case 1
{
first = newNode;
last = newNode;
count++;
}
else
{
current = first;
found = false;
while (current != NULL && !found) //search the list
if (current->info >= newItem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
if (current == first) //Case 2
{
newNode->link = first;
first = newNode;
count++;
}
else //Case 3
{
trailCurrent->link = newNode;
newNode->link = current;
if (current == NULL)
last = newNode;
count++;
}
}//end else
}//end insert
template<class Type>
void orderedLinkedList<Type>::insertFirst(const Type& newItem)
{
insert(newItem);
}//end insertFirst
template<class Type>
void orderedLinkedList<Type>::insertLast(const Type& newItem)
{
insert(newItem);
}//end insertLast
template<class Type>
void orderedLinkedList<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if (first == NULL) //Case 1
cout << "Cannot delete from an empty list." << endl;
else
{
current = first;
found = false;
while (current != NULL && !found) //search the list
if (current->info >= deleteItem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
if (current == NULL) //Case 4
cout << "The item to be deleted is not in the "
<< "list." << endl;
else
if (current->info == deleteItem) //the item to be
//deleted is in the list
{
if (first == current) //Case 2
{
first = first->link;
if (first == NULL)
last = NULL;
delete current;
}
else //Case 3
{
trailCurrent->link = current->link;
if (current == last)
last = trailCurrent;
delete current;
}
count--;
}
else //Case 4
cout << "The item to be deleted is not in the "
<< "list." << endl;
}
}//end deleteNode
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.