Answered: C++ Dividing a linked list into two…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Please do not copy from chegg.

C++

Dividing a linked list into two sublists of almost equal sizes

Add the operation divideMid to the class ListData in Chapter17.cpp on Canvas as follows:

void divideMid(ListData &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: ListData myList; ListData subList; 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.

chapter 17.cpp

#include <iostream>#include <stdlib.h>using namespace std;template<class Data>struct Node { Data info; Node* link;};template<class Data>class ListData {protected: Node<Data>* first; Node<Data>* last; int count;public: ListData(); void destroyList(); void reset(); void print() const; int length() const; Data front() const; Data back() const; bool isEmpty() const; bool search(const Data& searchItem) const; void insertFirst(const Data& newItemData); void insertLast(const Data& newItemData); void deleteNode(const Data& newItemData);};template<class Data>ListData<Data>::ListData() { first = NULL; last = NULL; count = 0;}template<class Data>void ListData<Data>::destroyList() { Node<Data>* temp; while (first != NULL) { temp = first; first = first->link; delete temp; } last = NULL; count = 0;}template<class Data>void ListData<Data>::reset() { destroyList();}template<class Data>void ListData<Data>::print() const { Node<Data>* current;

current = first; while (current != NULL) { cout << current->info << " "; //overload the operator<< current = current->link; } cout << endl; }template<class Data>int ListData<Data>::length() const { return count; }template<class Data>Data ListData<Data>::front() const { assert(first != NULL); return first->info;}template<class Data>Data ListData<Data>::back() const { assert(last != NULL); return last->info;}template<class Data>bool ListData<Data>::isEmpty() const { //return (count == 0); // return (first == NULL); return (last == NULL);}template<class Data>bool ListData<Data>::search(const Data& searchItem) const { Node<Data>* current; current = first; while (current != NULL) { if (current->info == searchItem) return true; current = current->link; } return false;}template<class Data>void ListData<Data>::insertFirst(const Data& newItemData) { Node<Data>* newNode; newNode = new Node<Data>; newNode->info = newItemData; newNode->link = first; first = newNode; count++; if (last == NULL) { last = newNode; }}template<class Data>void ListData<Data>::insertLast(const Data& newItemData) {

Node<Data>* newNode; newNode = new Node<Data>; newNode->info = newItemData; newNode->link = NULL; if(first == NULL) { first = newNode; last = newNode; } else { last->link = newNode; last = newNode; } count++; }template<class Data>void ListData<Data>::deleteNode(const Data& deleteItemData) { Node<Data>* del; Node<Data>* prevDel; if (first==NULL) { //first case where the list is empty cout << "The list is empty!" << endl; } else { if (first->info == deleteItemData) { // second case: first node is deleted del = first; first = first->link; delete del; count--; if (first==NULL) { last = NULL; } } else { bool found = false; prevDel = first; del = first->link; while (del != NULL && !found) { if (del->info != deleteItemData) { del = del->link; prevDel = prevDel->link; } else { found = true; } } if (found) { prevDel->link = del->link; if (last == del) { last = prevDel; } count--; delete del; } else { cout << "The item is not in the list." << endl; } } }}

template <class Data>class orderLinkedList : public ListData<Data> {public: bool search(const Data& searchItem) const; void insert(const Data& newItem); void insertFirst(const Data& newItem); void insertLast(const Data& newItem); void deleteNode(const Data& deleteItem);};template <class Data>bool orderLinkedList<Data>::search(const Data& searchItem) const { bool found = false; Node<Data>* current = this->first; while (current != NULL && !found) { if (current->info >= searchItem) { // 2 3 4 5 6 8 9 NULL... seach 5 found = true; } else { current = current->link; } } if (found) { return (current->info == searc

...................

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.