The programming language is C++. 1. Do not change anything in the supplied Ch16_
ID: 3854057 • Letter: T
Question
The programming language is C++.
1. Do not change anything in the supplied Ch16_Ex5_MainProgram.cpp.
2. Please use the file names listed below since your file will have the following components:
Ch16_Ex5_MainProgram.cpp - given file
//22 34 56 4 19 2 89 90 0 14 32 88 125 56 11 43 55 -999
#include <iostream>
#include "unorderedLinkedList.h"
using namespace std;
int main()
{
unorderedLinkedList<int> list, subList;
int num;
cout << "Enter numbers ending with -999" << endl;
cin >> num;
while (num != -999)
{
list.insertLast(num);
cin >> num;
}
cout << endl;
cout << "List: ";
list.print();
cout << endl;
cout << "Length of the list: " << list.length() << endl;
list.divideMid(subList);
cout << "Lists after splitting list" << endl;
cout << "list: ";
list.print();
cout << endl;
cout << "Length of the list: " << list.length() << endl;
cout << "sublist: ";
subList.print();
cout << endl;
cout << "Length of subList: " << subList.length() << endl;
system("pause");
return 0;
}
linkedList.h
unorderedLinkedList.h
3. Dividing a linked list into two sublists of almost equal sizes:
a. Add the operation divideMid to the class linkedListType as follows:
void divideMid(linkedListType &sublist);
//This operation divides the given list into two sublists
//of (almost) equal sizes.
//Postcondition: first points to the first node and last
// points to the last node of the first
// sublist.
// sublist.first points to the first node
// and sublist.last points to the last node
// of the second sublist.
Consider the following statements:
unorderedLinkedList <int> myList;
unorderedLinkedList <int> subList;
b. Suppose myList points to the list with elements 34 65 27 89 12 (in this order). The statement:
myList.divideMid(subList);
divides myList into two sublists: myList points to the list with the elements 34 65 27, and subList points to the sublist with the elements 89 12.
Write the definition of the function template to implement the operation divideMid. Also, write a program to test your function.
Explanation / Answer
public class UnorderedLinkedList extends LinkedListClass { public UnorderedLinkedList() { super(); } public UnorderedLinkedList(UnorderedLinkedList otherList) { super(otherList); } //Method to determine whether searchItem is in //the list. //Postcondition: Returns true if searchItem is found // in the list; false otherwise. public boolean search(DataElement searchItem) { LinkedListNode current; //variable to traverse the list boolean found; current = first; //set current to point to the first //node in the list found = false; //set found to false while(current != null && !found) //search the list if(current.info.equals(searchItem)) //item is found found = true; else current = current.link; //make current point to //the next node return found; } //Method to delete deleteItem from the list. //Postcondition: If found, the node containing // deleteItem is deleted from the // list. Also first points to the first // node, last points to the last // node of the updated list, and count // is decremented by 1. public void deleteNode(DataElement deleteItem) { LinkedListNode current; //variable to traverse the list LinkedListNode trailCurrent; //variable just before current boolean found; if(first == null) //Case 1; the list is empty System.err.println("Cannot delete from an empty list."); else { if(first.info.equals(deleteItem)) //Case 2 { first = first.link; if(first == null) //the list had only one node last = null; count--; } else //search the list for the node with the given info { found = false; trailCurrent = first; //set trailCurrent to point to //the first node current = first.link; //set current to point to the //second node while(current != null && !found) { if(current.info.equals(deleteItem)) found = true; else { trailCurrent = current; current = current.link; } }//end while if(found) //Case 3; if found, delete the node { count--; trailCurrent.link = current.link; if(last == current) //node to be deleted was //the last node last = trailCurrent; //update the value of last } else System.out.println("Item to be deleted is " + "not in the list."); }//end else }//end else }//end deleteNode }
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.